最近在搞一些关于机器学习的小东西，其中有一部分就是关于决策树的。过程中遇到了一些小问题，现记录并与大家分享。

一、问题描述：使用西瓜数据集构建决策树，并将构建的决策树进行可视化操作。

二、问题简析：首先我们简单的介绍一下什么是决策树。决策树是广泛用于分类和回归任务的模型。本质上，它从一层层的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，便可以运行成功。

五、样例运行结果：

今天要分享的到这儿就快结束了，希望我们能在学习的道路上携手共进。自己不会的有太多，希望各位大佬能给予指点，也希望小鹿的文章对小伙伴们是有帮助的，喜欢的可以点点关注和👍

思辨部分的参考问法（以问老丈人为例）： “老丈人，你说我要是问丈母娘贝贝在哪间卧室，她会告诉我什么答案？”

这样问答案就出来了已经：因为老丈人只说真话，所以他告诉你的必然是丈母娘说的假话，故而正确的答案就是老丈人没有说的那一间卧室。向丈母娘提问也是一样的道理，解决问题的方法有很多，欢迎大家讨论发表意见。

基于周志华西瓜数据集的决策树算法及准确率测试

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()

周志华的西瓜书《决策树》部分的代码实现

#利用决策树算法，对mnist数据集进行测试
import numpy as np

#计算熵
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

#生成树
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

#读取西瓜数据集2.0
def readWatermelonDataSet():
    ifile = open("周志华_西瓜数据集2.txt")
    featureName = ifile.readline()  #表头
    labels = (featureName.split(' ')[0]).split(',')
    lines = ifile.readlines()
    dataSet = []
    for line in lines:
        tmp = line.split('\n')[0]
        tmp = tmp.split(',')
        dataSet.append(tmp)

    return dataSet, labels

def main():
    #读取数据
    dataSet, featureNames = readWatermelonDataSet()
    print(createDecisionTree(dataSet, featureNames))

if __name__ == "__main__":
    main()

最后输出的决策树是：
{‘纹理’: {‘模糊’: ‘否’, ‘清晰’: {‘根蒂’: {‘稍蜷’: {‘色泽’: {‘乌黑’: {‘触感’: {‘硬滑’: ‘是’, ‘软粘’: ‘否’}}, ‘青绿’: ‘是’}}, ‘蜷缩’: ‘是’, ‘硬挺’: ‘否’}}, ‘稍糊’: {‘触感’: {‘硬滑’: ‘否’, ‘软粘’: ‘是’}}}}

画出来是这个样子的：

这个地方和书上不太一样。
后来参考了一篇CSDN文章
说是需要补全决策树

后来又仔细看了伪代码

主要是对画红线处的理解。
这里的“每一个值”到底是原始数据集的？还是分割后的数据集的
上面的代码是后者，书上是前者

把createDecisionTree（） 和 readWatermelonDataSet（）函数修改为下面的：

#生成决策树
# featureNamesSet 是featureNames取值的集合
# labelListParent 是父节点的标签列表
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)
    bestFeatureName = featureNames.pop(bestFeatureIndex)
    myTree = {bestFeatureName: {}}
    featureList = featureNamesSet.pop(bestFeatureIndex)
    featureSet = set(featureList)
    for feature in featureSet:
        featureNamesNext = featureNames[:]
        featureNamesSetNext = featureNamesSet[:][:]
        splitedDataSet = splitDataSet(dataSet, bestFeatureIndex, feature)
        myTree[bestFeatureName][feature] = createFullDecisionTree(splitedDataSet, featureNamesNext, featureNamesSetNext, labelList)
    return myTree


#读取西瓜数据集2.0
def readWatermelonDataSet():
    ifile = open("周志华_西瓜数据集2.txt")
    featureName = ifile.readline()  #表头
    featureNames = (featureName.split(' ')[0]).split(',')
    lines = ifile.readlines()
    dataSet = []
    for line in lines:
        tmp = line.split('\n')[0]
        tmp = tmp.split(',')
        dataSet.append(tmp)

    #获取featureNamesSet
    featureNamesSet = []
    for i in range(len(dataSet[0]) - 1):
        col = [x[i] for x in dataSet]
        colSet = set(col)
        featureNamesSet.append(list(colSet))

    return dataSet, featureNames, featureNamesSet

现在和书上的一样了