基于周志华西瓜数据集的决策树算法及准确率测试
 
1.决策树介绍
 举个通俗的栗子来解释一下什么是决策树，想象一个女孩的母亲要给这个女孩介绍男朋友：
 
女儿：有没有房子？母亲：有。
 
女儿：长的帅不帅？母亲：挺帅的。
 
女儿：收入高不？
 母亲：不算很高，中等情况。
 
女儿：是公务员不？母亲：是，在税务局上班呢。
 
女儿：那好，我去见见。
 
这个女孩的决策过程就是典型的分类树决策。相当于通过是否有房、长相、收入和是否公务员对将男人分为两个类别：见和不见。下面我们通过流程图把女儿的决策树判断过程展现出来：
 
 
通过这个例子，大家已经对决策树算法有个基本了解了吧，这也是决策树算法的一大优势——数据形式非常容易理解。
 
2.用python构造决策树基本流程
 下图是西瓜书中的决策树学习基本算法，接下来我们将根据这个算法流程用python代码自己写一棵决策树。
 
 
在构造决策树时，要解决的第一个问题就是，当前数据集哪个特征在划分数据分类时起决定性作用。在前面相亲的例子中，女孩为何第一个问题是“是否有房子”呢，因为是否有房子这个特征能够提供的“信息量”很大，划分选择就是找提供“信息量”最大的特征，学术上叫信息增益。
 
3.划分选择(按照信息增益)
 什么是信息增益呢，官方介绍请参考西瓜书哈，个人认为就是一个信息提纯的过程，比如一堆黄豆和一堆红豆混在一起，这时候信息的纯度是很低的，如果我们把红豆挑出来了分成两堆，那这时候纯度就高了。这就是一个信息增益的过程，衡量信息纯度的标准，就是信息熵。
 
信息熵是度量样本集合纯度最常用的一种指标，我的个人理解是对一个事件进行编码，所需要的平均码长就是信息熵，纯度越高，需要的平均代码就越短，信息熵越低。
 
当前样本集合D中第k类样本所占的比例为pk(k=1,2,…,n)，则D的信息熵定义为
 Ent(D)=−∑k=1npklog2pk
 Ent(D)=−∑k=1npklog2pk
 。
 Ent(D)的值越小，则D的纯度越高。
 西瓜数据集：链接: https://pan.baidu.com/s/1jxZvzUYX6QUk0cVH3d1vfw 提取码: 3ee9
 随机1/3数据作为测试集
 最初代码：
 
import pandas as pd
import numpy as np
from matplotlib import pyplot as plt
import collections


#计算给定数据集的香浓熵
from math import log
def splitDataSet(dataSet, index, feature):
    splitedDataSet = []
    mD = len(dataSet)
    for data in dataSet:
        if(data[index] == feature):
            sliceTmp = data[:index]
            sliceTmp.extend(data[index + 1:])
            splitedDataSet.append(sliceTmp)
    return splitedDataSet
def Ent(dataset):
    n = len(dataset)
    label_counts = {}
    for item in dataset:#遍历数据集
        label_current = item[-1]#存入
        if label_current not in label_counts.keys():
            label_counts[label_current] = 0#将特征值存入，并标记为0
        label_counts[label_current] += 1
    ent = 0.0
    for key in label_counts:
        prob = label_counts[key]/n
        ent -= prob * log(prob,2)
    return ent

#测试我们编写的香浓熵计算函数
data = pd.read_csv('xigua1.csv',encoding='gbk')
print(data)

#test=pd.read_csv('textSet.csv')

#print(test)
#a=Ent(data.iloc[:,-1])#取数据集最后一列


#按照权重计算各分支的信息熵
def sum_weight(grouped,total_len):
    weight = len(grouped)/total_len
    return weight * Ent(grouped.iloc[:,-1])

#根据公式计算信息增益
def Gain(column, data):
    lenth = len(data)
    ent_sum = data.groupby(column).apply(lambda x:sum_weight(x,lenth)).sum()#按照column重新排列，然后计算信息熵，再加一块 ☆！！
    #print("11",ent_sum)
    ent_D = Ent(data.iloc[:,-1])
    #print("22",ent_D)
    return ent_D - ent_sum

#计算按照属性'色泽'的信息增益


# 计算获取最大的信息增益的feature，输入data是一个dataframe，返回是一个字符串
def get_max_gain(data):
    max_gain = 0.0
    cols = data.columns[:-1]

    for col in cols:
        gain = Gain(col,data)
        #print(gain)
        if gain > max_gain:
            max_gain = gain
            max_label = col
    return max_label

#获取data中最多的类别作为节点分类，输入一个series，返回一个索引值，为字符串
def get_most_label(label_list):
    return label_list.value_counts().idxmax()  #value_counts:指数据集中值有哪些，每个出现多少次

# 创建决策树，传入的是一个dataframe，最后一列为label

def TreeGenerate(data):
    feature = train.columns[:-1]
    label_list = data.iloc[:, -1]
    #如果样本全属于同一类别C，将此节点标记为C类叶节点
    if len(pd.unique(label_list)) == 1:
        return label_list.values[0]
    #如果待划分的属性集A为空，或者样本在属性A上取值相同，则把该节点作为叶节点，并标记为样本数最多的分类
    elif len(feature)==0 or len(data.loc[:,feature].drop_duplicates())==1:
        return get_most_label(label_list)
    #从A中选择最优划分属性
    best_attr = get_max_gain(data)
    tree = {best_attr: {}}
    #对于最优划分属性的每个属性值，生成一个分支
    for attr,gb_data in data.groupby(by=best_attr):
        if len(gb_data) == 0:
            tree[best_attr][attr] = get_most_label(label_list)
        else:
            #在data中去掉已划分的属性
            new_data = gb_data.drop(best_attr,axis=1)
            #递归构造决策树
            tree[best_attr][attr] = TreeGenerate(new_data)
    return tree


#使用递归函数进行分类
def tree_predict(tree, data):
  #print(data)
  feature = list(tree.keys())[0]#取树第一个结点的键（特征）
  #print(feature)
  label = data[feature]#该特征下所有属性
  next_tree = tree[feature][label]#下一个结点树
  if type(next_tree) == str:#如果是个字符串
    return next_tree
  else:
    return tree_predict(next_tree, data)





#切割训练集和测试集
 # 训练模型


from sklearn.metrics import accuracy_score
from sklearn.model_selection import train_test_split

#切割训练集和测试集
X_train, X_test, y_train, y_test = train_test_split(data.iloc[:,:-1], data.iloc[:,-1], test_size = 0.3, random_state=1)
train = pd.concat([X_train,y_train],axis=1)
print("train",X_train)
print("test",y_test)

decition_tree = TreeGenerate(train)


print(decition_tree)

y_predict = X_test.apply(lambda x:tree_predict(decition_tree, x),axis=1)
score = accuracy_score(y_test,y_predict)
print('第实验准确率为：'+repr(score*100)+'%')


 
其实上面算法是有缺陷的，有可能缺失分支，需要补全分支：
 
import numpy as np
import pandas as pd
import random
import csv
from sklearn.metrics import accuracy_score
from sklearn.model_selection import train_test_split

#计算熵
def calcEntropy(dataSet):
    mD = len(dataSet)
    dataLabelList = [x[-1] for x in dataSet]
    dataLabelSet = set(dataLabelList)
    ent = 0
    for label in dataLabelSet:
        mDv = dataLabelList.count(label)
        prop = float(mDv) / mD
        ent = ent - prop * np.math.log(prop, 2)

    return ent

# # 拆分数据集
# # index - 要拆分的特征的下标
# # feature - 要拆分的特征
# # 返回值 - dataSet中index所在特征为feature，且去掉index一列的集合
def splitDataSet(dataSet, index, feature):
    splitedDataSet = []
    mD = len(dataSet)
    for data in dataSet:
        if(data[index] == feature):
            sliceTmp = data[:index]
            sliceTmp.extend(data[index + 1:])
            splitedDataSet.append(sliceTmp)
    return splitedDataSet

#根据信息增益 - 选择最好的特征
# 返回值 - 最好的特征的下标
def chooseBestFeature(dataSet):
    entD = calcEntropy(dataSet)
    mD = len(dataSet)
    featureNumber = len(dataSet[0]) - 1
    maxGain = -100
    maxIndex = -1
    for i in range(featureNumber):
        entDCopy = entD
        featureI = [x[i] for x in dataSet]
        featureSet = set(featureI)
        for feature in featureSet:
            splitedDataSet = splitDataSet(dataSet, i, feature)  # 拆分数据集
            mDv = len(splitedDataSet)
            entDCopy = entDCopy - float(mDv) / mD * calcEntropy(splitedDataSet)
        if(maxIndex == -1):
            maxGain = entDCopy
            maxIndex = i
        elif(maxGain < entDCopy):
            maxGain = entDCopy
            maxIndex = i

    return maxIndex

# 寻找最多的，作为标签
def mainLabel(labelList):
    labelRec = labelList[0]
    maxLabelCount = -1
    labelSet = set(labelList)
    for label in labelSet:
        if(labelList.count(label) > maxLabelCount):
            maxLabelCount = labelList.count(label)
            labelRec = label
    return labelRec

#生成决策树
# featureNamesSet 是featureNames取值的集合
# labelListParent 是父节点的标签列表
def createDecisionTree(dataSet, featureNames):
    labelList = [x[-1] for x in dataSet]
    if(len(dataSet[0]) == 1): #没有可划分的属性了
        return mainLabel(labelList)  #选出最多的label作为该数据集的标签
    elif(labelList.count(labelList[0]) == len(labelList)): # 全部都属于同一个Label
        return labelList[0]

    bestFeatureIndex = chooseBestFeature(dataSet)
    bestFeatureName = featureNames.pop(bestFeatureIndex)
    myTree = {bestFeatureName: {}}
    featureList = [x[bestFeatureIndex] for x in dataSet]
    featureSet = set(featureList)
    for feature in featureSet:
        featureNamesNext = featureNames[:]
        splitedDataSet = splitDataSet(dataSet, bestFeatureIndex, feature)
        myTree[bestFeatureName][feature] = createDecisionTree(splitedDataSet, featureNamesNext)
    return myTree

def createFullDecisionTree(dataSet, featureNames, featureNamesSet, labelListParent):
    labelList = [x[-1] for x in dataSet]
    if(len(dataSet) == 0):
        return mainLabel(labelListParent)
    elif(len(dataSet[0]) == 1): #没有可划分的属性了
        return mainLabel(labelList)  #选出最多的label作为该数据集的标签
    elif(labelList.count(labelList[0]) == len(labelList)): # 全部都属于同一个Label
        return labelList[0]

    bestFeatureIndex = chooseBestFeature(dataSet)
    #print('index',bestFeatureIndex)
    bestFeatureName = featureNames.pop(bestFeatureIndex)
    myTree = {bestFeatureName: {}}
    featureList = featureNamesSet.pop(bestFeatureIndex)
    #print('ss',featureList)
    featureSet = set(featureList)
    #print('featureSet',featureSet)
    for feature in featureSet:
        featureNamesNext = featureNames[:]
        #print('featureNamesNext',featureNamesNext)
        featureNamesSetNext = featureNamesSet[:][:]
        #print('featureNamesSetNext',featureNamesSetNext)
        splitedDataSet = splitDataSet(dataSet, bestFeatureIndex, feature)
        myTree[bestFeatureName][feature] = createFullDecisionTree(splitedDataSet, featureNamesNext, featureNamesSetNext, labelList)
    return myTree




#读取西瓜数据集2.0
def readWatermelonDataSet():

    ifile = open("xigua1.txt")
    #print(ifile)
    featureName = ifile.readline()  #表头
    featureName = featureName.rstrip("\n")
    #print(featureName)
    featureNames = (featureName.split(' ')[0]).split(',')
    #print(featureNames)
    lines = ifile.readlines()
    dataSet = []
    for line in lines:
        tmp = line.split('\n')[0]
        #print('tmp',tmp)
        tmp = tmp.split(',')
        dataSet.append(tmp)
    random.shuffle(dataSet)
    dlen = int(len(dataSet) * 2 / 3)
    testDlen = len(dataSet) - dlen
    D = dataSet[0:dlen]
    #print('d',D)
    testD = dataSet[dlen:len(dataSet)]



    labelList = [x[-1] for x in D]
    #print('labelList',labelList)
    #获取featureNamesSet
    featureNamesSet = []
    for i in range(len(D[0]) - 1):
        col = [x[i] for x in D]
        colSet = set(col)
        featureNamesSet.append(list(colSet))
    #print('saa',featureNamesSet)

    return D, featureNames, featureNamesSet,labelList,testD

def tree_predict(tree, data):
  #print(data)
  feature = list(tree.keys())[0]#取树第一个结点的键（特征）
  #print(feature)
  label = data[feature]#该特征下所有属性
  next_tree = tree[feature][label]#下一个结点树
  if type(next_tree) == str:#如果是个字符串
    return next_tree
  else:
    return tree_predict(next_tree, data)



def main():
    #读取数据
    pingjun=0.0
    for i in range(1,11):
        dataSet, featureNames, featureNamesSet,labelList,testD = readWatermelonDataSet()
        #print('daas',dataSet)
        tree=createFullDecisionTree(dataSet, featureNames,featureNamesSet,labelList)
        tree2=createDecisionTree(dataSet, featureNames)
        #print('tree2',tree2)
        print(tree)
        train= pd.DataFrame(dataSet, columns=['色泽','根蒂','敲声','纹理','脐部','触感','好瓜'])
        #print('train',train)
        test=pd.DataFrame(testD, columns=['色泽','根蒂','敲声','纹理','脐部','触感','好瓜'])
        #print('test', test)
        feature = list(train.columns[:])
        #print('feat',feature)

        y_predict = test.apply(lambda x: tree_predict(tree, x), axis=1)
        label_list = test.iloc[:, -1]
        score = accuracy_score(label_list, y_predict)
        pingjun+=score
        print('第'+repr(i)+'次补全分支准确率为：' + repr(score * 100) + '%')
    print("平均准确率为："+repr(pingjun*10)+'%')


if __name__ == "__main__":
    main()

作者：張張張張
 github地址：https://github.com/zhanghekai
 【转载请注明出处，谢谢！】
 
【机器学习系列】之“西瓜数据集”决策树构建数学公式计算过程
 【机器学习系列】之决策树剪枝和连续值、缺失值处理数学公式计算
 【机器学习系列】之ID3、C4.5、CART决策树构建代码
 


 
文章目录
 
一、决策树概述
二、决策树场景
三、决策树概念须知
1.名词定义
2.构建“树”时的基本要求
   
四、三种决策树对比
五、 划分选择
1.ID3信息增益
2.C4.5信息增益率
3.CART基尼系数
  
 

 
一、决策树概述
 
决策树（Decision Tree）算法是一种基本的分类与回归方法，是最经常使用的数据挖掘算法之一。决策树是一种非线性有监督分类模型必须将已有的数据进行离散化，即：从字符串变成数值。构造决策树的基本思想是随着树深度的增加，节点的“熵”迅速降低，熵降低的速度越快越好，这样我们有望得到一棵高度最矮的决策树。
 
决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是 if-then 规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。
 
决策树的定义：分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点（node）和有向边（directed edge）组成。结点有两种类型：内部结点（internal node）和叶结点（leaf node）。内部结点表示一个特征或属性(features)，叶结点表示一个类(labels)。
 
用决策树对需要测试的实例进行分类：从根节点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点；这时，每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶结点。最后将实例分配到叶结点的类中。
 
决策树学习通常包括 3 个步骤：特征选择、决策树的生成和决策树的修剪。
 
二、决策树场景
 
 
一个叫做 “二十个问题” 的游戏，游戏的规则很简单：参与游戏的一方在脑海中想某个事物，其他参与者向他提问，只允许提 20 个问题，问题的答案也只能用对或错回答。问问题的人通过推断分解，逐步缩小待猜测事物的范围，最后得到游戏的答案。
 
 
一个邮件分类系统，大致工作流程如下：
 
 
 
 
 
首先检测发送邮件域名地址。如果地址为 myEmployer.com, 则将其放在分类 "无聊时需要阅读的邮件"中。
 如果邮件不是来自这个域名，则检测邮件内容里是否包含单词 “曲棍球” , 如果包含则将邮件归类到 “需要及时处理的朋友邮件”, 如果不包含则将邮件归类到 “无需阅读的垃圾邮件” 。
 
 
三、决策树概念须知
 
1.名词定义
 
熵（entropy）：指体系的混乱的程度，在不同的学科中也有引申出的更为具体的定义，是各领域十分重要的参量。
 
信息熵（information theory）：使度量样本集合纯度最常用的一种指标。信息熵度量了事物的不确定性，越不确定的事物，它的熵就越大。
 
信息增益（information gain）：在划分数据集前后信息熵发生的变化称为信息增益。信息增益越大，表明数据“纯度”提升越大。
 
信息增益率（infor gain ratio）：正信息增益的基础上，解决过拟合问题的方法。
 
基尼系数（Gini index）：CART决策树划分属性的指标，数据集的纯度可以用基尼值来度量，基尼值越小，数据集的纯度越高。
 
纯度（purity）：叶子节点中正确分类的标签所占该叶子节点中包含数据的比例。
 
2.构建“树”时的基本要求
 
决策树的生成是一个递归过程，即决策树以深度优先遍历进行构建。
每个节点可选择的特征为：除该节点的父节点和祖父节点之外的所有特征。
若当前节点为空集，对应的处理措施为：将其设置为叶节点，类别设置为其父节点，所含样本最多的类别。
 
四、三种决策树对比
 
支持模型
树结构
特征选择
连续值处理
ID3
分类
多叉树
信息增益
不支持
C4.5
分类
多叉树
信息增益率
支持
CART
分类、多回归
二叉树
基尼系数、均方差
支持
 
五、 划分选择
 
我们希望决策树的分支节点所包含的样本尽可能属于同一类别，即节点的“纯度”越来越高。
 
我们使用周志华一书《机器学习》中的“西瓜数据集”进行计算：
 
 
1.ID3信息增益
 
$$信息熵：Ent(D)=-\sum _{k=1}^{|Y|}{p}_{k}lo{g}_2{p}_k$$
 
$$信息增益：Gain(D,a)=Ent(D)-\sum _{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)$$
 
|Y|：代表分类标签的数量，“好瓜”、“坏瓜”，所以|Y|=2
a:代表数据集所包含的特征，a={色泽，根蒂，敲声，纹理，脐部，触感}
v：代表每一个特征下所包含的属性，例如特征“色泽“下v={青绿，乌黑，浅白}
正例：”是“好瓜
反例：”否“好瓜
$\frac{|D^v|}{|D|}$：代表该节点所包含的数据数量占其父节点数据数量的比例
 
 
 
根节点包含D中所有数据，数据总数：17，正例占p1=8/17，反例占p2=9/17。
 
根节点的信息熵为：
 $$Ent(D)=-\sum _{k=1}^2{p}_{k}lo{g}_2{p}_k=-(\frac{8}{17}lo{g}_2\frac{8}{17}+\frac{9}{17}lo{g}_2\frac{9}{17})=0.998$$
 
 
​ 然后，我们要计算出当前特征集合{色泽，根蒂，敲声，纹理，脐部，触感}中每个特征的信息熵和信息增益。
 
★特征”色泽“：
 ​ $D^1$（色泽=青绿）：{1，4，6，10，13，17}，正例p1=3/6，反例p2=3/6
 ​ $Ent(D^1)=-(\frac{3}{6}lo{g}_2\frac{3}{6}+\frac{3}{6}lo{g}_2\frac{3}{6})=1.000$
 
​ $D^2$（色泽=乌黑）：{2，3，7，8，9，15}，正例p1=4/6，反例p2=2/6
 ​ $Ent(D^2)=-(\frac{4}{6}lo{g}_2\frac{4}{6}+\frac{2}{6}lo{g}_2\frac{2}{6})=0.918$
 
​ $D^3$（色泽=浅白）：{5，11，12，14，16}，正例p1=1/5，反例p2=4/5
 ​ $Ent(D^3)=-(\frac{1}{5}lo{g}_2\frac{1}{5}+\frac{4}{5}lo{g}_2\frac{4}{5})=0.722$
 
"色泽"特征的信息增益：
 
$$\begin{gathered} Gain(D,色泽)=Ent(D)-\sum _{v=1}^V\frac{|D^v|}{|D|}Ent(D^v) \\ =0.998-(\frac{6}{17}\times 1+\frac{6}{17}\times 0.918+\frac{5}{17}\times 0.722)=0.109 \end{gathered}$$
 
类似的，计算出其他特征的信息增益：
 Gain（D，根蒂）=0.143 
    
     
      
       
      
      
       \quad
      
     
     Gain（D，敲声）=0.141 
    
     
      
       
      
      
       \quad
      
     
     Gain（D，纹理）=0.381
 Gain（D，脐部）=0.289 
    
     
      
       
      
      
       \quad
      
     
     Gain（D，触感）=0.006
 
特征”纹理”的信息增益最大，选他作为划分属性。
 
 
 
 
其中节点上方红色字体表示：创建该node节点时可选择的特征。
 
 
$D^1$中有编号为{1，2，3，4，5，6，8，10，15}，可用特征集合为{色泽，根蒂，敲声，脐部，触感}，其中正例p1=7/9，反例p2=2/9。
 
$D^1$节点的信息熵为：
 $$Ent(D^1)=-\sum _{k=1}^2{p}_{k}lo{g}_2{p}_k=-(\frac{7}{9}lo{g}_2\frac{7}{9}+\frac{2}{9}lo{g}_2\frac{2}{9})=0.763$$
 ★特征”色泽“：
 ​ $D^{11}$（色泽=青绿）：{1，4，6，10}，正例p1=3/4，反例p2=1/4
 ​ $Ent(D^{11})=-(\frac{3}{4}lo{g}_2\frac{3}{4}+\frac{1}{4}lo{g}_2\frac{1}{4})=0.811$
 
​ $D^{12}$（色泽=乌黑）：{2，3，8，15}，正例p1=3/4，反例p2=1/4
 ​ $Ent(D^{12})=-(\frac{3}{4}lo{g}_2\frac{3}{4}+\frac{1}{4}lo{g}_2\frac{1}{4})=0.811$
 
​ $D^{13}$（色泽=浅白）：{5}，正例p1=1，反例p2=0
 ​ $Ent(D^{13})=-(1lo{g}_{2}1+0lo{g}_{2}0)=0$
 
"色泽"特征的信息增益：
 
$$\begin{gathered} Gain(D^1,色泽)=Ent(D^1)-\sum _{v=1}^V\frac{|D^v|}{|D|}Ent(D^v) \\ =0.763-(\frac{4}{9}\times 0.811+\frac{4}{9}\times 0.811+\frac{1}{9}\times 0)=0.043 \end{gathered}$$
 
类似的，计算出其他特征的信息增益：
 Gain（D1，根蒂）=0.458 
    
     
      
       
      
      
       \quad
      
     
     Gain（D1，敲声）=0.331 
 Gain（D1，脐部）=0.458 
    
     
      
       
      
      
       \quad
      
     
     Gain（D1，触感）=0.458
 其中“根蒂”，“脐部”，“触感”均获得最大信息增益，可任选其一作为特征划分。此处我们选择“根蒂”特征。
 
 
$D^{11}$中有编号为{1，2，3，4，5}，可用特征集合为{色泽，敲声，脐部，触感}，其中正例p1=1，反例p2=0。
 $D^{11}$节点的信息熵为：
 $$Ent(D^{11})=-\sum _{k=1}^2{p}_{k}lo{g}_2{p}_k=-(1lo{g}_{2}1+0lo{g}_{2}0)=0$$
 
由于Ent（D11）的值已达最小，说明D11中数据纯度已达到最高，数据分类已完全分类，则无需再往下进行划分，将该节点设置为叶子节点。
 
$D^{12}$中编号为{6，8，15}，可用特征集合为{色泽，敲声，脐部，触感}，其中正例p1=2/3，反例p2=1/3。
 $D^{12}$节点的信息熵为：
 $$Ent(D^{12})=-\sum _{k=1}^2{p}_{k}lo{g}_2{p}_k=-(\frac{2}{3}lo{g}_2\frac{2}{3}+\frac{1}{3}lo{g}_2\frac{1}{3})=0.918$$
 ★特征“色泽”：
 ​ $D^{121}$（色泽=青绿）：{6}，正例p1=1，反例p2=0
 ​ $Ent(D^{121})=-(1lo{g}_{2}1+0lo{g}_{2}0)=0$

 $D^{122}$（色泽=乌黑）：{8，15}，正例p1=1/2，反例p2=1/2
 ​ $Ent(D^{122})=-(\frac{1}{2}lo{g}_2\frac{1}{2}+\frac{1}{2}lo{g}_2\frac{1}{2})=1$

 ​ $D^{123}$（色泽=浅白）：{ }，正例p1=0，反例p2=0
 ​ $Ent(D^{123})=-(0lo{g}_{2}0+0lo{g}_{2}0)=0$
 
"色泽"特征的信息增益：
 
$$\begin{gathered} Gain(D^{12},色泽)=Ent(D^{12})-\sum _{v=1}^V\frac{|D^v|}{|D|}Ent(D^v) \\ =0.918-(\frac{1}{3}\times 0+\frac{2}{3}\times 1+0\times 0)=0.251 \end{gathered}$$
 
类似的，计算出其他特征的信息增益：
 Gain（D12，敲声）=0 
    
     
      
       
      
      
       \quad
      
     
     Gain（D12，脐部）=0
    
     
      
       
      
      
       \quad
      
     
     Gain（D12，触感）=0.251
 
其中“色泽”和“触感”均获得最大信息增益，可任选其一作为特征划分。此处我们选择“色泽”特征。
 
 
 
$D^{121}$中编号为{6}，可用特征集合为{敲声，脐部，触感}，其中p1=1，p2=0。
 $D^{121}$节点的信息熵为：
 $$Ent(D^{121})=-\sum _{k=1}^2{p}_{k}lo{g}_2{p}_k=-(1lo{g}_{2}1+0lo{g}_{2}0)=0$$
 将该节点划分为叶子节点。
 
 
$D122$中编号为{8，15}，可用特征集合为{敲声，脐部，触感}，p1=1/2，p2=1/2。
 $D^{122}$节点的信息熵为：
 $$Ent(D^{122})=-\sum _{k=1}^2{p}_{k}lo{g}_2{p}_k=-(\frac{1}{2}lo{g}_2\frac{1}{2}+\frac{1}{2}lo{g}_2\frac{1}{2})=1$$
 ★特征“触感”：
 ​ $D^{1221}$（触感=硬滑）：{8}，正例p1=1，反例p2=0
 ​ $Ent(D^{1221})=-(1lo{g}_{2}1+0lo{g}_{2}0)=0$

 ​ $D^{1222}$（触感=软粘）：{15}，正例p1=0，反例p2=1
 ​ $Ent(D^{1221})=-(0lo{g}_{2}0+1lo{g}_{2}1)=0$
 
"触感"特征的信息增益：
 
 
$$\begin{gathered} Gain(D^{122},色泽)=Ent(D^{122})-\sum _{v=1}^V\frac{|D^v|}{|D|}Ent(D^v) \\ =1-(\frac{1}{2}\times 0+\frac{1}{2}\times 0)=1 \end{gathered}$$
 类似的，计算出其他特征的信息增益：
 Gain（D122，敲声）=0 
    
     
      
       
      
      
       \quad
      
     
     Gain（D122，脐部）=0
 
所以选择“触感”特征作为划分节点。
 
 
 
$D^{1221}$中编号为{8}，可用特征集合为{敲声，脐部}，p1=1，p2=0。
 $D^{1221}$节点的信息熵为：
 $$Ent(D^{1221})=-\sum _{k=1}^2{p}_{k}lo{g}_2{p}_k=-(1lo{g}_{2}1+0lo{g}_{2}0)=0$$
 所以将该节点设置为叶子节点。
 
 
$D^{1222}$中编号为{15}，可用特征集合为{敲声，脐部}，p1=0，p2=1。
 $D^{1222}$节点的信息熵为：
 $$Ent(D^{1222})=-\sum _{k=1}^2{p}_{k}lo{g}_2{p}_k=-(0lo{g}_{2}0+1lo{g}_{2}1)=0$$
 
 
 
 
此时需要往回遍历，找到第三层“色泽”特征下的D123属性集合。
 
 
$D^{123}$中为空集{ }，将其设置为叶节点，且类别设置为其父节点所含样本最多的类别即{6，8，15}
 中，p1=2/3，p2=1/3，所以该叶子节点类别为“好瓜”。
 
 
 
继续往回遍历，找到第二层“根蒂”特征下的D13属性集合。
 
 
$D^{13}$中编号为{10}，可用特征集合为{色泽，敲声，脐部，触感}，p1=0，p2=1。
 $D^{13}$节点的信息熵为：
 $$Ent(D^{13})=-\sum _{k=1}^2{p}_{k}lo{g}_2{p}_k=-(0lo{g}_{2}0+1lo{g}_{2}1)=0$$
 所以将该节点设置为叶子节点。
 
 
 
继续往回遍历，找到第一层“纹理”特征下的D2属性集合。
 
 
 
$D^2$中编号为{7，9，13，14，17}，可用特征集合为{色泽，根蒂，敲声，脐部，触感}，p1=1/5，p2=4/5。
 $D^2$节点的信息熵为：
 $$Ent(D^2)=-\sum _{k=1}^2{p}_{k}lo{g}_2{p}_k=-(\frac{1}{5}lo{g}_2\frac{1}{5}+\frac{4}{5}lo{g}_2\frac{4}{5})=0.722$$
 ★特征“色泽”：
 ​ $D^{21}$（色泽=青绿）：{13，17}，正例p1=0，反例p2=1
 ​ $Ent(D^{21})=-(0lo{g}_{2}1+1lo{g}_{2}0)=0$

 ​ $D^{22}$（色泽=乌黑）：{7，9}，正例p1=1/2，反例p2=1/2
 ​ $Ent(D^{22})=-(\frac{1}{2}lo{g}_2\frac{1}{2}+\frac{1}{2}lo{g}_2\frac{1}{2})=1$

 ​ $D^{23}$（色泽=浅白）：{14}，正例p1=0，反例p2=1
 ​ $Ent(D^{23})=-(0lo{g}_{2}0+1lo{g}_{2}1)=0$
 
"色泽"特征的信息增益：
 
 
$$\begin{gathered} Gain(D^2,色泽)=Ent(D^2)-\sum _{v=1}^V\frac{|D^v|}{|D|}Ent(D^v) \\ =0.722-(\frac{2}{5}\times 0+\frac{2}{5}\times 1+\frac{1}{5}\times 0)=0.322 \end{gathered}$$
 类似的，计算出其他特征的信息增益：
 Gain（D2，敲声）=0.322 
    
     
      
       
      
      
       \quad
      
     
     Gain（D2，脐部）= 0.172
 Gain（D2，触感）= 0.722 
    
     
      
       
      
      
       \quad
      
     
     Gain（D2，根蒂）= 0.073
 
特征“触感”的信息增益最大，选他作为划分属性。
 
 12. $D^{21}$中编号为{9，13，14，17}，可用特征集合为{色泽，根蒂，敲声，脐部}，其中正例p1=0，反例p2=1.
 
$D21$节点的信息熵为：
 $$Ent(D^{21})=-\sum _{k=1}^2{p}_{k}lo{g}_2{p}_k=-(0lo{g}_{2}0+1lo{g}_{2}1)=0$$
 所以将该节点划分为叶子节点。
 
$D^{22}$中编号为{7}，可用特征集合为{色泽，根蒂，敲声，脐部}，其中正例p1=1，反例p2=0.
 
$D22$节点的信息熵为：
 $$Ent(D^{22})=-\sum _{k=1}^2{p}_{k}lo{g}_2{p}_k=-(1lo{g}_{2}1+0lo{g}_{2}0)=0$$
 所以将该节点划分为叶子节点。
 
 
 
往回遍历，找到第一层“纹理”特征下的D3属性集合。
 
 
$D^3$中有编号为{11，12，16}，可用特征集合为{色泽，根蒂，敲声，脐部，触感},其中正例p1=0，反例p2=1。
 
$D3$节点的信息熵为：
 $$Ent(D^3)=-\sum _{k=1}^2{p}_{k}lo{g}_2{p}_k=-(0lo{g}_{2}0+1lo{g}_{2}1)=0$$
 
所以将其设置为叶子节点。
 
 
至此，使用信息增益构建的ID3决策树已经建立好了，如上图所示。
 
2.C4.5信息增益率
 
信息增益缺点：是对可取属性多的特征有偏好，比如如果把“编号”这一列当作特征也考虑在内，那么可以计算处它的信息增益大于其他的候选特征，因为“编号”有17个可取的数值，产生17个分支，每个分支节点仅包含一个样本，显然这些分支节点的纯度最大。但是，这样的决策树显然不具有泛化能力，无法对新样本进行有效预测。C4.5决策树算法：使用“信息增益率”来选择最优划分属性，可以很好的克服上述缺点。
 
信息增益率定义为：
 $$Gai{n}_{r}atio(D,a)=\frac{Gain(D,a)}{IV(a)}$$
 其中：
 $$IV(a)=-\sum _{v=1}^V\frac{|D^v|}{|D|}lo{g}_2\frac{|D^v|}{|D|}IV(a)$$
 IV(a)称为特征a的“固有值”，特征a的可能取值数目越多（即V越大），则 IV(a)的值通常会越大。但增益率也可能产生一个问题就是对属性较少的特征有所偏好。注意：C4.5算法并不是直接选择增益率最大的候选划分特征，而是先从候选划分特征中找出信息增益高于平均水平的特征，再从中选择增益率最高的。
 
 
 
 
由于信息增益的计算方法在ID3中已经详细介绍并给出计算例子，在这里不再赘述，重点计算信息增益率的求解。
 
 
 
计算数据集D中所有特征的信息增益和信息增益率：
 
Gain(D,色泽 ) = 0.109 
      
       
        
         
        
        
         \quad
        
       
       Gain(D,根蒂) = 0.143 
      
       
        
         
        
        
         \quad
        
       
       Gain(D,敲声) = 0.141
 
Gain(D,纹理) = 0.381 
      
       
        
         
        
        
         \quad
        
       
       Gain(D,脐部) = 0.289 
      
       
        
         
        
        
         \quad
        
       
       Gain(D,触感) = 0.006
 $$ave\_Gain(D)=\frac{0.109+0.143+0.141+0.381+0.289+0.006}{6}=0.178$$
 选择信息增益高于平均水平的特征，即选择“纹理”和“脐部”计算信息增益率：
 
★特征“纹理”：清晰：9；稍糊：5；模糊：3
 $$IV(纹理)=-(\frac{9}{17}lo{g}_2\frac{9}{17}+\frac{5}{17}lo{g}_2\frac{5}{17}+\frac{3}{17}lo{g}_2\frac{3}{17})=1.446$$
 信息增益率为：
 $$Gain\_ratio(D,纹理)=\frac{0.381}{1.446}=0.263$$
 ★特征“脐部”：凹陷：7；稍凹：6；平坦：4
 $$IV(脐部)=-(\frac{7}{17}lo{g}_2\frac{7}{17}+\frac{6}{17}lo{g}_2\frac{6}{17}+\frac{4}{17}lo{g}_2\frac{4}{17})=1.548$$
 信息增益率为：
 $$Gain\_ratio(D,脐部)=\frac{0.289}{1.548}=0.187$$
 “纹理”的信息增益率大于“脐部”的信息增益率，所以选择特征“纹理”当作节点，划分数据集。
 
 
 
计算数据集D1中可用特征的信息增益和信息增益率：
 
Gain(D1,色泽 ) = 0.043 
      
       
        
         
        
        
         \quad
        
       
       Gain(D1,根蒂) = 0.458 
      
       
        
         
        
        
         \quad
        
       
       Gain(D1,敲声) = 0.331
 
Gain(D1,脐部) = 0.458 
      
       
        
         
        
        
         \quad
        
       
       Gain(D1,触感) = 0.458
 $$ave\_Gain(D1)=\frac{0.043+0.458+0.331+0.458+0.458}{5}=0.3496$$
 选择信息增益高于平均水平的特征，即选择“根蒂”、“触感”和“脐部”计算信息增益率：
 
★特征“根蒂”：蜷缩：5；稍蜷：3；硬挺：1
 $$IV(根蒂)=-(\frac{5}{9}lo{g}_2\frac{5}{9}+\frac{3}{9}lo{g}_2\frac{3}{9}+\frac{1}{9}lo{g}_2\frac{1}{9})=1.351$$
 信息增益率为：
 $$Gain\_ratio(D1,根蒂)=\frac{0.458}{1.351}=0.339$$
 ★特征“脐部”：凹陷：5；稍凹：3；平坦：1
 $$IV(脐部)=-(\frac{5}{9}lo{g}_2\frac{5}{9}+\frac{3}{9}lo{g}_2\frac{3}{9}+\frac{1}{9}lo{g}_2\frac{1}{9})=1.351$$
 信息增益率为：
 $$Gain\_ratio(D1,脐部)=\frac{0.458}{1.351}=0.339$$
 ★特征“触感”：硬滑：6；软粘：3
 $$IV(触感)=-(\frac{6}{9}lo{g}_2\frac{6}{9}+\frac{3}{9}lo{g}_2\frac{3}{9})=0.918$$
 信息增益率为：
 $$Gain\_ratio(D1,触感)=\frac{0.458}{0.918}=0.499$$
 “触感”的信息增益率最大，所以选择特征“触感”当作节点，划分数据集。
 
 
 
计算数据集D11中的信息：
 
由于数据集D11的信息熵为0，所以此节点以完全分类，将其设置为叶子节点。
 
 
计算数据集D12中的信息：
 
Gain(D12,色泽)=0.251 
      
       
        
         
        
        
         \quad
        
       
       Gain(D12,根蒂)=0.251
 
Gain(D12,敲声)=0.251 
      
       
        
         
        
        
         \quad
        
       
       Gain(D12,脐部)=0.251
 
★特征“脐部”：凹陷：0；稍凹：2；平坦：1
 $$IV(脐部)=-(0lo{g}_{2}0+\frac{2}{3}lo{g}_2\frac{2}{3}+\frac{1}{3}lo{g}_2\frac{1}{3})=0.251$$
 ​ 不难发现，这四个特征均是一个属性包含数据为0，一个属性包含数据为2，另一个属性包含数据为1，所以他们的信息增益率均相同，这种情况我们可以任选其一划分数据，类别为其中包含最多的类别；也可以将其设置为叶子节点，牺牲正确率换取更低的决策树层数。在这里我采取的方法为后者。
 
 
 
计算数据集D2中的信息
 
类似于数据集D12的情况，由于D2中只包含一个正例，所以依然可以采取牺牲正确率换取更低的决策树层数，或是进行计算选出一个特征来划分。此处采取设置为叶节点，有兴趣的同学可以自行计算。
 
 
计算数据集D3中的信息
 
由于数据集D11的信息熵为0，所以此节点以完全分类，将其设置为叶子节点。
 
 
 
3.CART基尼系数
 
CART决策树：使用”基尼指数“来选择划分特征。数据集的纯度可用基尼值(Gini)来度量。Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率，Gini值越小，则数据集的纯度越高。
 $$Gini(D)=1-\sum _{k=1}^{|Y|}{p}_k^2$$
 特征的“基尼指数”(Gini index)定义如下，选择使得划分后基尼指数最小的特征作为最优划分特征。
 $$Gini\_index(D,a)=\sum _{v=1}^V\frac{|D^v|}{|D|}Gini(D^v)$$
 
计算每个特征的基尼指数前，先计算下该节点的基尼值，若基尼值为0，则表示该节点下的数据集已完全分类。
 
 
 
根节点包含D中所有数据，数据总数为17，可用特征{色泽，根蒂，敲声，纹理，脐部，触感}：
 
★特征“色泽”：
 
青绿：{1，4，6，10，13，17}，数据总计：6，正例p1= 3/6，反例p2= 3/6
 $$Gini(青绿)=1-\sum _{k=1}^{|Y|}{p}_k^2=1-(\frac{3}{6}\times \frac{3}{6}+\frac{3}{6}\times \frac{3}{6})=0.5$$
 乌黑：{2，3，7，8，9，15}，数据总计：6，正例p1= 4/6，反例p2= 2/6
 $$Gini(乌黑)=1-\sum _{k=1}^{|Y|}{p}_k^2=1-(\frac{4}{6}\times \frac{4}{6}+\frac{2}{6}\times \frac{2}{6})=0.444$$
 浅白：{5，11，12，14，16}，数据总计：5，正例p1= 1/5，反例p2= 4/5
 $$Gini(浅白)=1-\sum _{k=1}^{|Y|}{p}_k^2=1-(\frac{1}{5}\times \frac{1}{5}+\frac{4}{5}\times \frac{4}{5})=0.32$$
 
“色泽”特征的基尼指数为：
 $$Gini\_index(D,色泽)=\frac{6}{17}\times 0.5+\frac{6}{17}\times 0.444+\frac{5}{17}\times 0.32=0.427$$
 同理可以计算出其他特征的基尼指数为：
 
Gini_index(D,根蒂) = 0.422 
      
       
        
         
        
        
         \quad
        
       
       Gini_index(D,敲声) = 0.424 
      
       
        
         
        
        
         \quad
        
       
       Gini_index(D,纹理) = 0.277
 
Gini_index(D,脐部) = 0.345 
      
       
        
         
        
        
         \quad
        
       
       Gini_index(D,触感) = 0.494
 
选择基尼指数最小的特征进行划分，所以此次划分使用“纹理”特征。
 
 
 
D1中包含数据总数为9，可用特征{色泽，根蒂，敲声，脐部，触感}：
 
★特征“色泽”
 
青绿：{1，4，6，10}，数据总计：4，正例p1= 3/4，反例p2= 1/4
 $$Gini(青绿)=1-\sum _{k=1}^{|Y|}{p}_k^2=1-(\frac{3}{4}\times \frac{3}{4}+\frac{1}{4}\times \frac{1}{4})=0.375$$
 乌黑：{2，3，8，15}，数据总计：4，正例p1= 3/4，反例p2= 1/4
 $$Gini(乌黑)=1-\sum _{k=1}^{|Y|}{p}_k^2=1-(\frac{3}{4}\times \frac{3}{4}+\frac{1}{4}\times \frac{1}{4})=0.375$$
 浅白：{5}，数据总计：1，正例p1= 1，反例p2= 0
 $$Gini(浅白)=1-\sum _{k=1}^{|Y|}{p}_k^2=1-(1\times 1+0\times 0)=0$$
 “色泽”特征的基尼指数为：
 $$Gini\_index(D^1,色泽)=\frac{4}{9}\times 0.375+\frac{4}{9}\times 0.375+\frac{1}{9}\times 0=0.333$$
 同理可以计算出其他特征的基尼指数为：
 
Gini_index(D1,根蒂) = 0.148 
      
       
        
         
        
        
         \quad
        
       
       Gini_index(D1,敲声) = 0.185
 
Gini_index(D1,脐部) = 0.148 
      
       
        
         
        
        
         \quad
        
       
       Gini_index(D1,触感) = 0.148
 
由于“根蒂”、“脐部”和“触感”的基尼指数相同，任选其一作为特征进行划分数据集，这里我们选择“根蒂”特征：
 
 
 
D11中包含数据总数为5，其中正例p1=1，反例p2=0。
 
该节点基尼值为：
 $$Gini(D^{1}1)=1-\sum _{k=1}^{|Y|}{p}_k^2=1-(1\times 1+0\times 0)=0$$
 该节点基尼值已达最小，将其设置为叶子节点。
 
 
D12中包含数据总数位3，可用特征为{色泽，敲声，脐部，触感}
 
★特征“色泽”：
 
青绿：{6}，数据总计：1，正例p1= 1，反例p2= 1/40
 $$Gini(青绿)=1-\sum _{k=1}^{|Y|}{p}_k^2=1-(1\times 1+0\times 0)=0$$
 乌黑：{8，15}，数据总计：2，正例p1= 1/2，反例p2= 1/2
 $$Gini(乌黑)=1-\sum _{k=1}^{|Y|}{p}_k^2=1-(\frac{1}{2}\times \frac{1}{2}+\frac{1}{2}\times \frac{1}{2})=0.5$$
 浅白：{ }，数据总计：0，正例p1= 0，反例p2= 0
 $$Gini(浅白)=1-\sum _{k=1}^{|Y|}{p}_k^2=1-(0\times 0+0\times 0)=0$$
 “色泽”特征的基尼指数为：
 $$Gini\_index(D^{12},色泽)=\frac{1}{3}\times 0+\frac{2}{3}\times 0.5+0\times 0=0.333$$
 同理可以计算出其他特征的基尼指数为：
 
Gini_index(D12,敲声) = 0.444 
      
       
        
         
        
        
         \quad
        
       
       Gini_index(D12,脐部) = 0.444 
      
       
        
         
        
        
         \quad
        
       
       Gini_index(D12,触感) = 0.333
 
由于“色泽”和“触感”的基尼指数相同，任选其一作为特征进行划分数据集，这里我们选择“色泽”特征：
 
 
 
D121中已完全分类，设置为叶节点。
 
 
D122中包含数据总数为2，可用特征为{敲声，脐部，触感}
 
Gini_index(D122,敲声) = 0.5 
      
       
        
         
        
        
         \quad
        
       
       Gini_index(D122,脐部) = 0.5 
      
       
        
         
        
        
         \quad
        
       
       Gini_index(D122,触感) = 0
 
所以选择“触感”特征划分数据集。
 
 
 
 
D1221中已完全分类，设置为叶节点。
 
 
D1222中已完全分类，设置为叶节点。
 
 
 
 
往回遍历，找到第三层“色泽”特征下的D123属性集合。
 
 
该节点集合为空，设置为其父节点数据中类别最多的类。
 
 
 
往回遍历，找到第二层“根蒂”特征下的D13属性集合
 
 
 
D13中已完全分类，设置为叶节点。
 
 
 
 
 
往回遍历，找到第一层“纹理”特征下的D2属性集合
 
 
 
D2中包含数据总数为5，可用特征为{色泽，根蒂，敲声，脐部，触感}
 
Gini_index(D2,敲声) = 0.467 
      
       
        
         
        
        
         \quad
        
       
       Gini_index(D2,脐部) = 0.267 
      
       
        
         
        
        
         \quad
        
       
       Gini_index(D2,触感) = 0
 
Gini_index(D2,色泽) = 0.2 
      
       
        
         
        
        
         \quad
        
       
       Gini_index(D1,根蒂) = 0.3
 
所以选择“触感”作为特征划分数据集。
 
 
 
D21中已完全分类，设置为叶节点。
 
 
D22中已完全分类，设置为叶节点。
 
 
D3中已完全分类，设置为叶节点。
 
 
建立好的决策树如下图所示：
 
 
至此，三种决策树构建时的计算过程已经整理完了，在下一篇文章中我们来看看预剪枝与缺失值处理是怎么操作的。
 
【参考文献】
 
apache github主页：https://github.com/apachecn/AiLearning
天泽28 CSDN博客：https://blog.csdn.net/u012328159/article/details/70184415
刘建平 博客园：https://www.cnblogs.com/pinard/
周志华 《机器学习》

最近在搞一些关于机器学习的小东西，其中有一部分就是关于决策树的。过程中遇到了一些小问题，现记录并与大家分享。
 
一、问题描述：使用西瓜数据集构建决策树，并将构建的决策树进行可视化操作。
 
二、问题简析：首先我们简单的介绍一下什么是决策树。决策树是广泛用于分类和回归任务的模型。本质上，它从一层层的if/else问题中进行学习，并得出结论。然后不妨看看下面这个小思考题吧：（故事我瞎编的，看问题就好了嘛）
 
小鹿机缘巧合之下喜欢上了一个只有一面之缘的贝贝（一见钟情嘛）。对吧，爱情的力量是伟大的，小鹿就不顾一切的裸辞叻，去找人家。这不总算找到了人家里，但是考验接踵而至呀！人贝贝对小鹿还挺满意的哦，可姑娘的父母说还得考验一下不是？啥考验呢？
 
思辨：家里有两个卧室，老丈人，丈母娘各站一个卧室门外，贝贝就在其中一个卧室中。老丈人向来只说真话，丈母娘向来只说假话。现在只允许小鹿向两人中任意一个人提一个问题，只有成功问出贝贝在哪间卧室之中才能抱得美人归。小鹿该怎么提问？（答案在文章末尾）
 
为什么会来一个看似无关的废话连篇叻？其实问题有相通之处的，我们的目标是通过提出尽可能少的if/else问题来得到正确答案。
 
三、代码实现：
 为了控制文章篇幅，现在就直接给出问题的代码实现吧：
 
from random import choice
from collections import Counter
import math

# 定义数据集
D = [
    {'色泽': '青绿', '根蒂': '蜷缩', '敲声': '浊响', '纹理': '清晰', '脐部': '凹陷', '触感': '硬滑', '好瓜': '是'},
    {'色泽': '乌黑', '根蒂': '蜷缩', '敲声': '沉闷', '纹理': '清晰', '脐部': '凹陷', '触感': '硬滑', '好瓜': '是'},
    {'色泽': '乌黑', '根蒂': '蜷缩', '敲声': '浊响', '纹理': '清晰', '脐部': '凹陷', '触感': '硬滑', '好瓜': '是'},
    {'色泽': '青绿', '根蒂': '蜷缩', '敲声': '沉闷', '纹理': '清晰', '脐部': '凹陷', '触感': '硬滑', '好瓜': '是'},
    {'色泽': '浅白', '根蒂': '蜷缩', '敲声': '浊响', '纹理': '清晰', '脐部': '凹陷', '触感': '硬滑', '好瓜': '是'},
    {'色泽': '青绿', '根蒂': '稍蜷', '敲声': '浊响', '纹理': '清晰', '脐部': '稍凹', '触感': '软粘', '好瓜': '是'},
    {'色泽': '乌黑', '根蒂': '稍蜷', '敲声': '浊响', '纹理': '稍糊', '脐部': '稍凹', '触感': '软粘', '好瓜': '是'},
    {'色泽': '乌黑', '根蒂': '稍蜷', '敲声': '浊响', '纹理': '清晰', '脐部': '稍凹', '触感': '硬滑', '好瓜': '是'},
    {'色泽': '乌黑', '根蒂': '稍蜷', '敲声': '沉闷', '纹理': '稍糊', '脐部': '稍凹', '触感': '硬滑', '好瓜': '否'},
    {'色泽': '青绿', '根蒂': '硬挺', '敲声': '清脆', '纹理': '清晰', '脐部': '平坦', '触感': '软粘', '好瓜': '否'},
    {'色泽': '浅白', '根蒂': '硬挺', '敲声': '清脆', '纹理': '模糊', '脐部': '平坦', '触感': '硬滑', '好瓜': '否'},
    {'色泽': '浅白', '根蒂': '蜷缩', '敲声': '浊响', '纹理': '模糊', '脐部': '平坦', '触感': '软粘', '好瓜': '否'},
    {'色泽': '青绿', '根蒂': '稍蜷', '敲声': '浊响', '纹理': '稍糊', '脐部': '凹陷', '触感': '硬滑', '好瓜': '否'},
    {'色泽': '浅白', '根蒂': '稍蜷', '敲声': '沉闷', '纹理': '稍糊', '脐部': '凹陷', '触感': '硬滑', '好瓜': '否'},
    {'色泽': '乌黑', '根蒂': '稍蜷', '敲声': '浊响', '纹理': '清晰', '脐部': '稍凹', '触感': '软粘', '好瓜': '否'},
    {'色泽': '浅白', '根蒂': '蜷缩', '敲声': '浊响', '纹理': '模糊', '脐部': '平坦', '触感': '硬滑', '好瓜': '否'},
    {'色泽': '青绿', '根蒂': '蜷缩', '敲声': '沉闷', '纹理': '稍糊', '脐部': '稍凹', '触感': '硬滑', '好瓜': '否'},
]


# ==========
# 决策树生成类
# ==========
class DecisionTree:
    def __init__(self, D, label, chooseA):
        self.D = D  # 数据集
        self.label = label  # 哪个属性作为标签
        self.chooseA = chooseA  # 划分方法
        self.A = list(filter(lambda key: key != label, D[0].keys()))  # 属性集合A
        # 获得A的每个属性的可选项
        self.A_item = {}
        for a in self.A:
            self.A_item.update({a: set(self.getClassValues(D, a))})
        self.root = self.generate(self.D, self.A)  # 生成树并保存根节点

    # 获得D中所有className属性的值
    def getClassValues(self, D, className):
        return list(map(lambda sample: sample[className], D))

    # D中样本是否在A的每个属性上相同
    def isSameInA(self, D, A):
        for a in A:
            types = set(self.getClassValues(D, a))
            if len(types) > 1:
                return False
        return True

    # 构建决策树，递归生成节点
    def generate(self, D, A):
        node = {}  # 生成节点
        remainLabelValues = self.getClassValues(D, self.label)  # D中的所有标签
        remainLabelTypes = set(remainLabelValues)  # D中含有哪几种标签

        if len(remainLabelTypes) == 1:
            # 当前节点包含的样本全属于同个类别，无需划分
            return remainLabelTypes.pop()  # 标记Node为叶子结点,值为仅存的标签

        most = max(remainLabelTypes, key=remainLabelValues.count)  # D占比最多的标签

        if len(A) == 0 or self.isSameInA(D, A):
            # 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分
            return most  # 标记Node为叶子结点,值为占比最多的标签

        a = self.chooseA(D,A,self)  # 划分选择

        for type in self.A_item[a]:
            condition = (lambda sample: sample[a] == type)  # 决策条件
            remainD = list(filter(condition, D))  # 剩下的样本
            if len(remainD) == 0:
                # 当前节点包含的样本集为空，不能划分
                node.update({type: most})  # 标记Node为叶子结点,值为占比最多的标签
            else:
                # 继续对剩下的样本按其余属性划分
                remainA = list(filter(lambda x: x != a, A))  # 未使用的属性
                _node = self.generate(remainD, remainA)  # 递归生成子代节点
                node.update({type: _node})  # 把生成的子代节点更新到当前节点
        return {a: node}



#  定义划分方法

# 随机选择
def random_choice(D, A, tree: DecisionTree):
    return choice(A)

# 信息熵
def Ent(D,label,a,a_v):
    D_v = filter(lambda sample:sample[a]==a_v,D)
    D_v = map(lambda sample:sample[label],D_v)
    D_v = list(D_v)
    D_v_length = len(D_v)
    counter = Counter(D_v)
    info_entropy = 0
    for k, v in counter.items():
        p_k = v / D_v_length
        info_entropy += p_k * math.log(p_k, 2)
    return -info_entropy

# 信息增益
def information_gain(D, A, tree: DecisionTree):
    gain = {}
    for a in A:
        gain[a] = 0
        values = tree.getClassValues(D, a)
        counter = Counter(values)
        for a_v,nums in counter.items():
            gain[a] -= (nums / len(D)) * Ent(D,tree.label,a,a_v)
    return max(gain.keys(),key=lambda key:gain[key])
    
#  创建决策树
desicionTreeRoot = DecisionTree(D, label='好瓜',chooseA=information_gain).root
print('决策树:', desicionTreeRoot)

# 决策树可视化类
class TreeViewer:
    def __init__(self):
        from graphviz import Digraph
        self.id_iter = map(str, range(0xffff))
        self.g = Digraph('G', filename='decisionTree.gv')

    def create_node(self, label, shape=None):
        id = next(self.id_iter)
        self.g.node(name=id, label=label, shape=shape, fontname="Microsoft YaHei")
        return id

    def build(self, key, node, from_id):
        for k in node.keys():
            v = node[k]
            if type(v) is dict:
                first_attr = list(v.keys())[0]
                id = self.create_node(first_attr+"？", shape='box')
                self.g.edge(from_id, id, k, fontsize = '12', fontname="Microsoft YaHei")
                self.build(first_attr, v[first_attr], id)
            else:
                id = self.create_node(v)
                self.g.edge(from_id, id, k, fontsize = '12', fontname="Microsoft YaHei")

    def show(self, root):
        first_attr = list(root.keys())[0]
        id = self.create_node(first_attr+"？", shape='box')
        self.build(first_attr, root[first_attr], id)
        self.g.view()


# 显示创建的决策树
viewer = TreeViewer()
viewer.show(desicionTreeRoot)
 
四、可能出现的错误：
 实验中有一些库是必须要使用到的，总体上不会有太大的问题，但是我们需要特别注意一下graphviz库。一般情况下，使用AnaConda开发的话，我们会在AnaConda Prompt中直接使用pip install graphviz命令来安装包。这样使用之后，Jupyter Notebook中显示导包成功，但是有一堆报错，也无法让决策树成功可视化。上述问题的一般报错为graphviz.backend.ExecutableNotFound: failed to execute [‘dot’, ‘-Tpdf’, ‘-O’, ‘test-table.gv’], make sure the Graphviz executables are on your systems’ PATH为了解决这个问题在网上寻找了很多种方法，也基本上都尝试了一下。现在就直接给大家一个比较简便的解决方法！
 
解决方法：去graphviz官网上下载graphviz-2.38.msi官网下载路径，或者直接点这个链接去下载graphviz绿色简便下载
 
推荐使用绿色简便下载，当然要是不怕麻烦的话也可以选择去官网下载哈。下载解压完成之后还需要对graphivz进行配置，将graphviz文件夹的bin目录完整路径添加在系统变量Path中。最后重启Jupyter Notebook，便可以运行成功。
 
五、样例运行结果：
 
 
今天要分享的到这儿就快结束了，希望我们能在学习的道路上携手共进。自己不会的有太多，希望各位大佬能给予指点，也希望小鹿的文章对小伙伴们是有帮助的，喜欢的可以点点关注和👍
 
思辨部分的参考问法（以问老丈人为例）： “老丈人，你说我要是问丈母娘贝贝在哪间卧室，她会告诉我什么答案？”
 
这样问答案就出来了已经：因为老丈人只说真话，所以他告诉你的必然是丈母娘说的假话，故而正确的答案就是老丈人没有说的那一间卧室。向丈母娘提问也是一样的道理，解决问题的方法有很多，欢迎大家讨论发表意见。

 
目录
 
西瓜数据集2.0
求信息熵
第一次划分
第二次划分
最终结果
 

 
西瓜数据集2.0
 
编号,色泽,根蒂,敲声,纹理,脐部,触感,好瓜
1,   青绿,蜷缩,浊响,清晰,凹陷,硬滑,是
2,   乌黑,蜷缩,沉闷,清晰,凹陷,硬滑,是
3,   乌黑,蜷缩,浊响,清晰,凹陷,硬滑,是
4,   青绿,蜷缩,沉闷,清晰,凹陷,硬滑,是
5,   浅白,蜷缩,浊响,清晰,凹陷,硬滑,是
6,   青绿,稍蜷,浊响,清晰,稍凹,软粘,是
7,   乌黑,稍蜷,浊响,稍糊,稍凹,软粘,是
8,   乌黑,稍蜷,浊响,清晰,稍凹,硬滑,是
9,   乌黑,稍蜷,沉闷,稍糊,稍凹,硬滑,否
10,  青绿,硬挺,清脆,清晰,平坦,软粘,否
11,  浅白,硬挺,清脆,模糊,平坦,硬滑,否
12,  浅白,蜷缩,浊响,模糊,平坦,软粘,否
13,  青绿,稍蜷,浊响,稍糊,凹陷,硬滑,否
14,  浅白,稍蜷,沉闷,稍糊,凹陷,硬滑,否
15,  乌黑,稍蜷,浊响,清晰,稍凹,软粘,否
16,  浅白,蜷缩,浊响,模糊,平坦,硬滑,否
17,  青绿,蜷缩,沉闷,稍糊,稍凹,硬滑,否
 
求信息熵
 
    import math

    def ent(*ps: float) -> float:
        sum = 0.0
        for p in ps:
            if p == 0.0:
                sum += 0
            else:
                sum += -1 * p * math.log(p, 2)
        return sum
 
第一次划分
 
# 初始时的信息熵    
p1 = 8 / 17
p2 = 9 / 17
Ent = ent(p1, p2) = 0.9975025463691153

# 色泽青绿的信息熵
p1 = 3 / 6
p2 = 3 / 6
Ent1_1 = ent(p1, p2) = 1.0
# 色泽乌黑的信息熵
p1 = 4 / 6
p2 = 2 / 6
Ent1_2 = ent(p1, p2) = 0.9182958340544896
# 色泽浅白的信息熵
p1 = 1 / 5
p2 = 4 / 5
Ent1_3 = ent(p1, p2) = 0.7219280948873623
# 色泽的信息熵
Ent1 = 6 / 17 * Ent1_1 + 6 / 17 * Ent1_2 + 5 / 17 * Ent1_3 = 0.88937738110375

# 根蒂蜷缩的信息熵
p1 = 5 / 8
p2 = 3 / 8
Ent2_1 = ent(p1, p2) = 0.9544340029249649
# 根蒂稍蜷的信息熵
p1 = 3 / 7
p2 = 4 / 7
Ent2_2 = ent(p1, p2) = 0.9852281360342516
# 根蒂硬挺的信息熵
p1 = 0.0
p2 = 2 / 2
Ent2_3 = -(p2 * math.log(p2, 2)) = 0.0
# 根蒂的信息熵
Ent2 = 8 / 17 * Ent2_1 + 7 / 17 * Ent2_2 + 2 / 17 * Ent2_3 = 0.8548275868023224

# 敲声浊响的信息熵
p1 = 6 / 10
p2 = 4 / 10
Ent3_1 = ent(p1, p2) = 0.9709505944546686
# 敲声沉闷的信息熵
p1 = 2 / 5
p2 = 3 / 5
Ent3_2 = ent(p1, p2) = 0.9709505944546686
# 敲声清脆的信息熵
p1 = 0.0
p2 = 2 / 2
Ent3_3 = -(p2 * math.log(p2, 2)) = 0.0
# 敲声的信息熵
Ent3 = 10 / 17 * Ent3_1 + 5 / 17 * Ent3_2 + 2 / 17 * Ent3_3 = 0.8567211127541194

# 纹理清晰的信息熵
p1 = 7 / 9
p2 =  2 / 9
Ent4_1 = ent(p1, p2) = 0.7642045065086203
# 纹理稍糊的信息熵
p1 = 1 / 5
p2 = 4 / 5
Ent4_2 = ent(p1, p2) = 0.7219280948873623
# 纹理模糊的信息熵
p1 = 0.0
p2 = 3 / 3
Ent4_3 = -(p2 * math.log(p2, 2)) = 0.0
# 纹理的信息熵
Ent4 = 9 / 17 * Ent4_1 + 5 / 17 * Ent4_2 + 3 / 17 * Ent4_3 = 0.6169106490008467

# 脐部凹陷的信息熵
p1 = 5 / 7
p2 = 2 / 7
Ent5_1 = ent(p1, p2) = 0.863120568566631
# 脐部稍凹的信息熵
p1 = 3 / 6
p2 = 3 / 6
Ent5_2 = ent(p1, p2) = 1.0
# 脐部平坦的信息熵
p1 = 0.0
p2 = 4 / 4
Ent5_3 = -(p2 * math.log(p2, 2)) = 0.0
# 脐部的信息熵
Ent5 = 7 / 17 * Ent5_1 + 6 / 17 * Ent5_2 + 4 / 17 * Ent5_3 = 0.7083437635274363

# 触感硬滑的信息熵
p1 = 6 / 12
p2 = 6 / 12
Ent6_1 = ent(p1, p2) = 1.0
# 触感软粘的信息熵
p1 = 2 / 5
p2 = 3 / 5
Ent6_2 = ent(p1, p2) = 0.9709505944546686
# 触感的信息熵
Ent6 = 12 / 17 * Ent6_1 + 5 / 17 * Ent6_2 = 0.9914560571925497
 
纹理的信息增益（0.9975025463691153 - 0.6169106490008467 = 0.3805918973682686）最大，所以 纹理 被选为划分属性
 
 
第二次划分
 
模糊分支 都是坏瓜，划分完毕，下面 以 稍糊分支 为例
 
# 初始时的信息熵    
p1 = 1 / 5
p2 = 4 / 5
Ent = ent(p1, p2) = 0.7219280948873623

# 色泽青绿的信息熵
p1 = 0.0
p2 = 2 / 2
Ent1_1 = 0.0
# 色泽乌黑的信息熵
p1 = 1 / 2
p2 = 1 / 2
Ent1_2 = ent(p1, p2) = 1.0
# 色泽浅白的信息熵
p1 = 0.0
p2 = 1 / 1
Ent1_3 = 0.0
# 色泽的信息熵
Ent1 = 2 / 5 * Ent1_1 + 2 / 5 * Ent1_2 + 1 / 5 * Ent1_3 = 0.4

# 根蒂蜷缩的信息熵
p1 = 0.0
p2 = 1 / 1
Ent2_1 = 0
# 根蒂稍蜷的信息熵
p1 = 1 / 4
p2 = 3 / 4
Ent2_2 = ent(p1, p2) = 0.8112781244591328
# 根蒂硬挺的信息熵
p1 = 0.0
p2 = 0.0
Ent2_3 = 0.0
# 根蒂的信息熵
Ent2 = 1 / 5 * Ent2_1 + 4 / 5 * Ent2_2 + 0 * Ent2_3 = 0.64902249956730624

# 敲声浊响的信息熵
p1 = 1 / 2
p2 = 1 / 2
Ent3_1 = ent(p1, p2) = 1.0
# 敲声沉闷的信息熵
p1 = 0.0
p2 = 3 / 3
Ent3_2 = 0
# 敲声清脆的信息熵
p1 = 0.0
p2 = 0.0
Ent3_3 = 0.0
# 敲声的信息熵
Ent3 = 2 / 5* Ent3_1 + 3 / 5 * Ent3_2 + 0.0 * Ent3_3 = 0.4

# 脐部凹陷的信息熵
p1 = 0.0
p2 = 2 / 2
Ent5_1 = 0.0
# 脐部稍凹的信息熵
p1 = 1 / 3
p2 = 2 / 3
Ent5_2 = ent(p1, p2) = 0.9182958340544896
# 脐部平坦的信息熵
p1 = 0.0
p2 = 0.0
Ent5_3 = 0.0
# 脐部的信息熵
Ent5 = 2 / 5 * Ent5_1 + 3 / 5 * Ent5_2 + 0 * Ent5_3 = 0.5509775004326938

# 触感硬滑的信息熵
p1 = 0.0
p2 = 4 / 4
Ent6_1 = 0.0
# 触感软粘的信息熵
p1 = 1 / 1
p2 = 0.0
Ent6_2 = 0.0
# 触感的信息熵
Ent6 = 4 / 5* Ent6_1 + 1 / 5* Ent6_2 = 0.0
 
触感的信息增益（0.7219280948873623 - 0.0 = 0.7219280948873623）最大，所以 触感 被选为划分属性
 
最终结果
 
剩下的划分，具体操作 和 上述两次划分 是 一样的，不再赘述。