likes
comments
collection
share

机器学习之 决策树(Decision Tree)python实现

作者站长头像
站长
· 阅读数 42
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
from math import log

我们使用西瓜书中的一个数据集，来进行我们的决策树的建立

data = pd.read_csv("decision_tree_data3.txt",names=['编号','色泽','根蒂','敲声','纹理','脐部','触感','密度','含糖率','好瓜' ])
data.head()
编号 色泽 根蒂 敲声 纹理 脐部 触感 密度 含糖率 好瓜
0 1 青绿 蜷缩 浊响 清晰 凹陷 硬滑 0.697 0.460 是
1 2 乌黑 蜷缩 沉闷 清晰 凹陷 硬滑 0.774 0.376 是
2 3 乌黑 蜷缩 浊响 清晰 凹陷 硬滑 0.634 0.264 是
3 4 青绿 蜷缩 沉闷 清晰 凹陷 硬滑 0.608 0.318 是
4 5 浅白 蜷缩 浊响 清晰 凹陷 硬滑 0.556 0.215 是

首先，我们需要将数据集做下处理，将对应文字转换成离散型数据

# def initdata_feature(data):
#     len_columns = data.shape[1]
#     data_columns = data.columns
#     for i in range(len_columns):
#         if(i>0 and i<len_columns-3):
#             str_values = data.iloc[:,i].unique()
#             for j in range(len(str_values)):
#                 data.loc[data[data_columns[i]]==str_values[j],data_columns[i]] = j
def initdata_y(data):
    data.loc[data.好瓜 == '是 ','好瓜'] = 1
    data.loc[data.好瓜 == '否 ','好瓜'] = 0

测试下看看

# initdata_feature(data)
initdata_y(data)
data
编号 色泽 根蒂 敲声 纹理 脐部 触感 密度 含糖率 好瓜
0 1 青绿 蜷缩 浊响 清晰 凹陷 硬滑 0.697 0.460 1
1 2 乌黑 蜷缩 沉闷 清晰 凹陷 硬滑 0.774 0.376 1
2 3 乌黑 蜷缩 浊响 清晰 凹陷 硬滑 0.634 0.264 1
3 4 青绿 蜷缩 沉闷 清晰 凹陷 硬滑 0.608 0.318 1
4 5 浅白 蜷缩 浊响 清晰 凹陷 硬滑 0.556 0.215 1
5 6 青绿 稍蜷 浊响 清晰 稍凹 软粘 0.403 0.237 1
6 7 乌黑 稍蜷 浊响 稍糊 稍凹 软粘 0.481 0.149 1
7 8 乌黑 稍蜷 浊响 清晰 稍凹 硬滑 0.437 0.211 1
8 9 乌黑 稍蜷 沉闷 稍糊 稍凹 硬滑 0.666 0.091 0
9 10 青绿 硬挺 清脆 清晰 平坦 软粘 0.243 0.267 0
10 11 浅白 硬挺 清脆 模糊 平坦 硬滑 0.245 0.057 0
11 12 浅白 蜷缩 浊响 模糊 平坦 软粘 0.343 0.099 0
12 13 青绿 稍蜷 浊响 稍糊 凹陷 硬滑 0.639 0.161 0
13 14 浅白 稍蜷 沉闷 稍糊 凹陷 硬滑 0.657 0.198 0
14 15 乌黑 稍蜷 浊响 清晰 稍凹 软粘 0.360 0.370 0
15 16 浅白 蜷缩 浊响 模糊 平坦 硬滑 0.593 0.042 0
16 17 青绿 蜷缩 沉闷 稍糊 稍凹 硬滑 0.719 0.103 0

先把编号那个无用的特征去掉

data = data.drop('编号', axis = 1)
data
色泽 根蒂 敲声 纹理 脐部 触感 密度 含糖率 好瓜
0 青绿 蜷缩 浊响 清晰 凹陷 硬滑 0.697 0.460 1
1 乌黑 蜷缩 沉闷 清晰 凹陷 硬滑 0.774 0.376 1
2 乌黑 蜷缩 浊响 清晰 凹陷 硬滑 0.634 0.264 1
3 青绿 蜷缩 沉闷 清晰 凹陷 硬滑 0.608 0.318 1
4 浅白 蜷缩 浊响 清晰 凹陷 硬滑 0.556 0.215 1
5 青绿 稍蜷 浊响 清晰 稍凹 软粘 0.403 0.237 1
6 乌黑 稍蜷 浊响 稍糊 稍凹 软粘 0.481 0.149 1
7 乌黑 稍蜷 浊响 清晰 稍凹 硬滑 0.437 0.211 1
8 乌黑 稍蜷 沉闷 稍糊 稍凹 硬滑 0.666 0.091 0
9 青绿 硬挺 清脆 清晰 平坦 软粘 0.243 0.267 0
10 浅白 硬挺 清脆 模糊 平坦 硬滑 0.245 0.057 0
11 浅白 蜷缩 浊响 模糊 平坦 软粘 0.343 0.099 0
12 青绿 稍蜷 浊响 稍糊 凹陷 硬滑 0.639 0.161 0
13 浅白 稍蜷 沉闷 稍糊 凹陷 硬滑 0.657 0.198 0
14 乌黑 稍蜷 浊响 清晰 稍凹 软粘 0.360 0.370 0
15 浅白 蜷缩 浊响 模糊 平坦 硬滑 0.593 0.042 0
16 青绿 蜷缩 沉闷 稍糊 稍凹 硬滑 0.719 0.103 0

下面就开始实现决策树算法，上篇文章已经知道，要根据样本集建立一棵决策树，具体算法流程如下：

机器学习之 决策树(Decision Tree)python实现

下面我们来分模块进行实现。

首先，来看下给定数据集的信息熵的求解

#求对应数据集的信息熵
def getInfoEntropy(data):
    #print('################################')
    #print(data)
    count_class = pd.value_counts(data.iloc[:,-1], sort=True)  #根据输出值，统计不同样本个数
    #print(count_class)
    data_count = len(data.iloc[:,-1])
    #print(data_count)
    Entropy = 0.0
    for i in range(len(count_class)):
        p = count_class.iloc[i]/data_count
        Entropy = Entropy + (-p * log(p,2))
    #print('当前数据集的信息熵为：',Entropy)
    return Entropy

测试下看看，求取下整个样本集的信息熵

getInfoEntropy(data)

0.9975025463691153

下来我们实现下，根据对应特征，划分数据。需要分两种情况

  1. 离散型特征，直接根据离散的相应类别进行划分
  2. 连续型数据，需要参照数据离散化，选出最优的划分值。具体原理可查看上篇文章中的连续型特征处理

下面来看下具体代码实现

#离散型数据划分
def split_data(data, column):
    splt_datas = pd.Series()   #将划分的多个数据集保存在Series中
    str_values = data.iloc[:,column].unique()  #获取当前数据集中，对应特征的所有类别
    for i in range(len(str_values)):   #遍历对应类别，找出类别所对应的数据集
        df = data.loc[data.iloc[:,column] == str_values[i]]
#         print(df)
        splt_datas[str(i)] = df
    return splt_datas


#连续型数据划分
#返回划分后的左右两个数据集以及所对应的最优划分点，还有以此划分点进行划分数据后，对应的信息熵
def split_continuous(data,column):
    splt_datas = pd.Series()
    series_data_sort = data.iloc[:,column].sort_values()  #对应对应连续型特征的在当前数据集中的所有值，进行从小到大排序
    split_values = []   #创建一个list,用于存储所有的划分点
#     print(series_data_sort)
    for i in range(len(series_data_sort)-1):    #求得所有划分点
        split_values.append((series_data_sort.iloc[i] + series_data_sort.iloc[i+1])/2)  # 注意，这块不能用series_data_sort[i]
    best_split_value = 0.    #所要找出的最佳划分点
    minInfoGain = 100.             
#     print(split_values)
    for i in range(len(split_values)):   #遍历所有划分点
       # print('split_values[i]==',split_values[i])
        #根据对应划分点，将数据集划分为左右两个数据集（即二分）
        left_data = data.loc[data.iloc[:,column]<=split_values[i]]
        right_data = data.loc[data.iloc[:,column]>split_values[i]]
        #求得对应信息熵
        InfoGain = len(left_data)/len(data) * getInfoEntropy(left_data) + len(right_data)/len(data) * getInfoEntropy(right_data)
        #print('InfoGain====',InfoGain)
        if(InfoGain < minInfoGain):   #找出最小的信息熵
            minInfoGain = InfoGain
            best_split_value = split_values[i]
    left_data = data.loc[data.iloc[:,column]<=best_split_value]
    right_data = data.loc[data.iloc[:,column]>best_split_value]
    series = pd.Series()
    series['0'] = left_data
    series['1'] = right_data
    return series,best_split_value,minInfoGain

测试下看看

seris = split_data(data,0)
for i in range(len(seris)):
    print (seris.iloc[i])

    色泽  根蒂  敲声  纹理  脐部  触感     密度    含糖率  好瓜
0   青绿  蜷缩  浊响  清晰  凹陷  硬滑  0.697  0.460   1
3   青绿  蜷缩  沉闷  清晰  凹陷  硬滑  0.608  0.318   1
5   青绿  稍蜷  浊响  清晰  稍凹  软粘  0.403  0.237   1
9   青绿  硬挺  清脆  清晰  平坦  软粘  0.243  0.267   0
12  青绿  稍蜷  浊响  稍糊  凹陷  硬滑  0.639  0.161   0
16  青绿  蜷缩  沉闷  稍糊  稍凹  硬滑  0.719  0.103   0
    色泽  根蒂  敲声  纹理  脐部  触感     密度    含糖率  好瓜
1   乌黑  蜷缩  沉闷  清晰  凹陷  硬滑  0.774  0.376   1
2   乌黑  蜷缩  浊响  清晰  凹陷  硬滑  0.634  0.264   1
6   乌黑  稍蜷  浊响  稍糊  稍凹  软粘  0.481  0.149   1
7   乌黑  稍蜷  浊响  清晰  稍凹  硬滑  0.437  0.211   1
8   乌黑  稍蜷  沉闷  稍糊  稍凹  硬滑  0.666  0.091   0
14  乌黑  稍蜷  浊响  清晰  稍凹  软粘  0.360  0.370   0
    色泽  根蒂  敲声  纹理  脐部  触感     密度    含糖率  好瓜
4   浅白  蜷缩  浊响  清晰  凹陷  硬滑  0.556  0.215   1
10  浅白  硬挺  清脆  模糊  平坦  硬滑  0.245  0.057   0
11  浅白  蜷缩  浊响  模糊  平坦  软粘  0.343  0.099   0
13  浅白  稍蜷  沉闷  稍糊  凹陷  硬滑  0.657  0.198   0
15  浅白  蜷缩  浊响  模糊  平坦  硬滑  0.593  0.042   0


series,best_split_value,minInfoGain  = split_continuous(data,6)
for i in range(len(series)):
    print (series.iloc[i])

    色泽  根蒂  敲声  纹理  脐部  触感     密度    含糖率  好瓜
9   青绿  硬挺  清脆  清晰  平坦  软粘  0.243  0.267   0
10  浅白  硬挺  清脆  模糊  平坦  硬滑  0.245  0.057   0
11  浅白  蜷缩  浊响  模糊  平坦  软粘  0.343  0.099   0
14  乌黑  稍蜷  浊响  清晰  稍凹  软粘  0.360  0.370   0
    色泽  根蒂  敲声  纹理  脐部  触感     密度    含糖率  好瓜
0   青绿  蜷缩  浊响  清晰  凹陷  硬滑  0.697  0.460   1
1   乌黑  蜷缩  沉闷  清晰  凹陷  硬滑  0.774  0.376   1
2   乌黑  蜷缩  浊响  清晰  凹陷  硬滑  0.634  0.264   1
3   青绿  蜷缩  沉闷  清晰  凹陷  硬滑  0.608  0.318   1
4   浅白  蜷缩  浊响  清晰  凹陷  硬滑  0.556  0.215   1
5   青绿  稍蜷  浊响  清晰  稍凹  软粘  0.403  0.237   1
6   乌黑  稍蜷  浊响  稍糊  稍凹  软粘  0.481  0.149   1
7   乌黑  稍蜷  浊响  清晰  稍凹  硬滑  0.437  0.211   1
8   乌黑  稍蜷  沉闷  稍糊  稍凹  硬滑  0.666  0.091   0
12  青绿  稍蜷  浊响  稍糊  凹陷  硬滑  0.639  0.161   0
13  浅白  稍蜷  沉闷  稍糊  凹陷  硬滑  0.657  0.198   0
15  浅白  蜷缩  浊响  模糊  平坦  硬滑  0.593  0.042   0
16  青绿  蜷缩  沉闷  稍糊  稍凹  硬滑  0.719  0.103   0

接下来,我们要做的就是，给定一个数据集，我们需要求得最优的划分特征，先来来看下代码实现

# 查找当前数据集data 的 最优划分特征。返回对应最优特征在数据集data中的索引
def find_best_feature(data):
    best_feature_index = 0    #用来保存最优划分特征的索引
    minInfoGain = 100.      #保存信息增益
    samplenumber = len(data)   #当前数据集的个数
    best_split_value_return = 0.  #如果最优划分特征是个连续类型的，则还需要保存对应的连续特征的最优划分点
    best_split_value = 0.
    best_Series = pd.Series()
    for i in range(data.shape[1]-1):    #遍历数据集的所有特征
        InfoGain = 0.
        series = pd.Series()
        if(i < data.shape[1]-3):    #离散型属性
            series = split_data(data, i)   #根据特征划分数据，将划分的多个数据集（DataFrame）保存在一个Series中返回    
            for j in range(len(series)):
                df = series[j]
                InfoGain = InfoGain +len(df)/samplenumber *(getInfoEntropy(df))
#             print('InfoGain==',InfoGain,'----i=',i)
        else:                      #连续型属性
            series,best_split_value, InfoGain = split_continuous(data,i)
#             print('InfoGain==',InfoGain,'----i=',i)
        if(InfoGain < minInfoGain):
            minInfoGain = InfoGain
            InfoGain = 0.0
            best_feature_index = i
            best_Series = series
            if(i >= data.shape[1]-3):
                best_split_value_return = best_split_value
     
    return data.columns[best_feature_index],best_Series,best_split_value_return

测试下看看

find_best_feature(data)

('纹理', 0        色泽  根蒂  敲声  纹理  脐部  触感     密度    含糖率  好瓜
 0...
 1        色泽  根蒂  敲声  纹理  脐部  触感     密度    含糖率  好瓜
 6...
 2        色泽  根蒂  敲声  纹理  脐部  触感     密度    含糖率  好瓜
 1...
 dtype: object, 0.0)

接下来就要实现决策树的构建了

#创建树模型
def creat_Tree(data):
    y_values = data.iloc[:,-1].unique()   #得到当前数据集的y的类别
    if(len(y_values) == 1):             #如果只剩下一个类别，说明已经是纯净的数据，不需要再分，直接返回
        return y_values[0]
    flag = 0
    for i in range(data.shape[1]-1):   #当前节点中的所有样本在当前所剩属性集中取值相同，则直接返回当前数据集中类别样本多的那个类别
        if(len(data.iloc[:,i].unique()) != 1):
            flag = 1
            break
    if(flag == 0):
        value_count = pd.value_counts(data.iloc[:,-1])
        return value_count.index[0]
    best_feature, best_Series,best_split_value = find_best_feature(data)  #寻找最优特征，返回最优特征，划分后的数据集，已经如果是连续型特征，还需要划分点
    Tree = {best_feature:{}}    #用字典来模拟树
    for j in range(len(best_Series)):    #遍历划分后的数据集
        split_data = best_Series.iloc[j]
        value = ''
        if(best_split_value == 0.0):    #说明是离散型特征
            value = split_data.loc[:,best_feature].unique()[0]   #获取对应划分的特征中，对应的特征类别
            split_data = split_data.drop(best_feature, axis = 1) #离散型型特征，用完后需要删除
        else:                          #否则，说明是连续型特征
            if(j == 0):
                value = '<='+str(best_split_value)
            else:
                value = '>'+str(best_split_value)
        Tree[best_feature][value] = creat_Tree(split_data)   #采用递归思想，继续构建
    return Tree
    

Tree = creat_Tree(data)
Tree

{'纹理': {'模糊': 0,
  '清晰': {'密度': {'<=0.38149999999999995': 0, '>0.38149999999999995': 1}},
  '稍糊': {'触感': {'硬滑': 0, '软粘': 1}}}}

接下来，来实现下，使用训练出来的决策树，对新的数据进行分类

#预测一个样本
def classification_one(Tree, data):
    print(Tree)
    first_key = list(Tree.keys())[0]  #获取根节点的key
    first_value = Tree[first_key]     #获取根节点对应的value
    result = -1   #初始化，用来保存当前节点的结果
    if('<' in list(first_value.keys())[0]):     #连续型特征
        #解释下下面两行代码，里面的 list(first_value.keys())[0] 获取来的就是‘<=0.38...’这种格式，需要从这个里面解析出0.38...这个分割点
        left_key =  list(first_value.keys())[0]  #'<=分割点'
        right_key =  list(first_value.keys())[1] #'>分割点'
        split_poit = float(''.join(list(left_key)[2:]))  # '分割点'
        if(data[first_key] <= split_poit):   #如果属于左分支
            if(isinstance(first_value[left_key], dict)):   #判断是否是叶子节点，如果对应的value还是一个dict字典，则说明是个非叶子节点，继续递归
                result = classification_one(first_value[left_key],data)
            else:                                         #如果是叶子节点，返回结果值
                result = first_value[left_key]
        else:                              #如果属于左分支
            if(isinstance(first_value[right_key], dict)):
                result = classification_one(first_value[right_key],data)
            else:
                result = first_value[right_key]
    else:                        #离散型特征
        if(isinstance(first_value[data[first_key]], dict)):
            result = classification_one(first_value[data[first_key]],data)
        else:
            result = first_value[data[first_key]]
    return result

#预测多个样本
def classification_more(Tree, data):
    result_list = []
    for i in range(data.shape[0]):
        result = classification_one(Tree, data.iloc[i])
        result_list.append(result)
    return result_list

classification_more(Tree,data)

{'纹理': {'清晰': {'密度': {'<=0.38149999999999995': 0, '>0.38149999999999995': 1}}, '稍糊': {'触感': {'软粘': 1, '硬滑': 0}}, '模糊': 0}}
{'密度': {'<=0.38149999999999995': 0, '>0.38149999999999995': 1}}
{'纹理': {'清晰': {'密度': {'<=0.38149999999999995': 0, '>0.38149999999999995': 1}}, '稍糊': {'触感': {'软粘': 1, '硬滑': 0}}, '模糊': 0}}
{'密度': {'<=0.38149999999999995': 0, '>0.38149999999999995': 1}}
{'纹理': {'清晰': {'密度': {'<=0.38149999999999995': 0, '>0.38149999999999995': 1}}, '稍糊': {'触感': {'软粘': 1, '硬滑': 0}}, '模糊': 0}}
{'密度': {'<=0.38149999999999995': 0, '>0.38149999999999995': 1}}
{'纹理': {'清晰': {'密度': {'<=0.38149999999999995': 0, '>0.38149999999999995': 1}}, '稍糊': {'触感': {'软粘': 1, '硬滑': 0}}, '模糊': 0}}
{'密度': {'<=0.38149999999999995': 0, '>0.38149999999999995': 1}}
{'纹理': {'清晰': {'密度': {'<=0.38149999999999995': 0, '>0.38149999999999995': 1}}, '稍糊': {'触感': {'软粘': 1, '硬滑': 0}}, '模糊': 0}}
{'密度': {'<=0.38149999999999995': 0, '>0.38149999999999995': 1}}
{'纹理': {'清晰': {'密度': {'<=0.38149999999999995': 0, '>0.38149999999999995': 1}}, '稍糊': {'触感': {'软粘': 1, '硬滑': 0}}, '模糊': 0}}
{'密度': {'<=0.38149999999999995': 0, '>0.38149999999999995': 1}}
{'纹理': {'清晰': {'密度': {'<=0.38149999999999995': 0, '>0.38149999999999995': 1}}, '稍糊': {'触感': {'软粘': 1, '硬滑': 0}}, '模糊': 0}}
{'触感': {'软粘': 1, '硬滑': 0}}
{'纹理': {'清晰': {'密度': {'<=0.38149999999999995': 0, '>0.38149999999999995': 1}}, '稍糊': {'触感': {'软粘': 1, '硬滑': 0}}, '模糊': 0}}
{'密度': {'<=0.38149999999999995': 0, '>0.38149999999999995': 1}}
{'纹理': {'清晰': {'密度': {'<=0.38149999999999995': 0, '>0.38149999999999995': 1}}, '稍糊': {'触感': {'软粘': 1, '硬滑': 0}}, '模糊': 0}}
{'触感': {'软粘': 1, '硬滑': 0}}
{'纹理': {'清晰': {'密度': {'<=0.38149999999999995': 0, '>0.38149999999999995': 1}}, '稍糊': {'触感': {'软粘': 1, '硬滑': 0}}, '模糊': 0}}
{'密度': {'<=0.38149999999999995': 0, '>0.38149999999999995': 1}}
{'纹理': {'清晰': {'密度': {'<=0.38149999999999995': 0, '>0.38149999999999995': 1}}, '稍糊': {'触感': {'软粘': 1, '硬滑': 0}}, '模糊': 0}}
{'纹理': {'清晰': {'密度': {'<=0.38149999999999995': 0, '>0.38149999999999995': 1}}, '稍糊': {'触感': {'软粘': 1, '硬滑': 0}}, '模糊': 0}}
{'纹理': {'清晰': {'密度': {'<=0.38149999999999995': 0, '>0.38149999999999995': 1}}, '稍糊': {'触感': {'软粘': 1, '硬滑': 0}}, '模糊': 0}}
{'触感': {'软粘': 1, '硬滑': 0}}
{'纹理': {'清晰': {'密度': {'<=0.38149999999999995': 0, '>0.38149999999999995': 1}}, '稍糊': {'触感': {'软粘': 1, '硬滑': 0}}, '模糊': 0}}
{'触感': {'软粘': 1, '硬滑': 0}}
{'纹理': {'清晰': {'密度': {'<=0.38149999999999995': 0, '>0.38149999999999995': 1}}, '稍糊': {'触感': {'软粘': 1, '硬滑': 0}}, '模糊': 0}}
{'密度': {'<=0.38149999999999995': 0, '>0.38149999999999995': 1}}
{'纹理': {'清晰': {'密度': {'<=0.38149999999999995': 0, '>0.38149999999999995': 1}}, '稍糊': {'触感': {'软粘': 1, '硬滑': 0}}, '模糊': 0}}
{'纹理': {'清晰': {'密度': {'<=0.38149999999999995': 0, '>0.38149999999999995': 1}}, '稍糊': {'触感': {'软粘': 1, '硬滑': 0}}, '模糊': 0}}
{'触感': {'软粘': 1, '硬滑': 0}}





[1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]

我们还是使用的上面的那个数据集用来验证，可以看到，已经完全拟合了训练集，

但是，这样真的好吗？正如上篇文章说的，决策树如果不进行剪枝的话，肯定最后会一直分下去，直到所分的各个数据集完全是纯净的，这样，非常容易导致过拟合现象。所以，还需要进行剪枝操作。具体代码这块不演示了，只要掌握了整个决策树构建的原理，实现起来也很简单。

上面，演示的只是ID3算法的相关实现，还有决策的其他算法，例如C4.5决策树算法，主要区别就是最优划分特征的选择标准不同。流程基本都是一致的。

欢迎关注我的个人公众号 AI计算机视觉工坊，本公众号不定期推送机器学习，深度学习，计算机视觉等相关文章，欢迎大家和我一起学习，交流。

机器学习之 决策树(Decision Tree)python实现

转载自:https://juejin.cn/post/6844903619813179406
评论
请登录