[数据结构与算法]【机器学习实验二】决策树(Decision Tree)及其在图像识别任务上的应用

经典有监督学习算法：决策树(Decision Tree)

——本篇博客的决策树算法以及实验仅针对分类问题

本次博客的所有源代码均已上传个人github仓库，若对您有帮助，欢迎给个star 😃
https://github.com/Scienthusiasts/Machine-Learning

1.算法简介

决策树算法属于有监督机器学习算法中的一类经典算法，最早的概念由心理学家E.B.Hunt于1962年提出，意在模仿人类做决策的一系列过程。算法的一大特点便是符合直觉且非常直观，可解释性强。决策树算法兴起于上世纪80年代，在这期间诞生了许多有名的决策树算法，其中最著名的便属三种决策树方法，分别是ID3[QuinLan 1986], C4.5[QuinLan 1993]和CART[Breiman et al. 1984]。其中ID3和C4.5主要用于分类任务，CART既可以用于分类任务，也适用于回归任务。

2.算法思想

在人类日常的生活当中，常常会遇到各种各样的决策问题(分类问题)，比如说上街买瓜。

对于一位有经验的人而言，在判断“一个西瓜是否是好瓜”这一决策问题上，一般会经历如下的流程。首先判断它的颜色，颜色如果青绿，则再判断它的根蒂形状，根蒂如果蜷缩，则再判断敲击是的声音，最后，根据以上的判断，一般就可以得出这个是个好瓜还是坏瓜的结论，如果把大致的判断过程绘制成一个树形结构，就会是：

不难发现，对比人类决策，决策过程在决策树上就转化为一个个判断结点和分支。而树的叶子结点就代表一系列决策过程之后的决策结果。

再专业一些的说法是，分类决策树模型实则是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有两种类型：内部结点和叶节点。内部结点表示一个特征或属性，叶节点表示一个类。

决策树学习的最终目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树

但和人类有所不同之处在于，人类的决策过程是基于经验的，而决策树的经验又从何而来呢？

这时候就要区分算法的训练过程与测试过程了。和上一篇博客所分析的kNN最近邻算法不同，决策树算法是区分训练过程与测试过程的，测试过程很好理解，就是上述的决策过程，接下来我们详细分析下算法的训练过程。

3.算法训练流程

对于使用树形结构的算法，无论是生成还是遍历，用到的最多的一个方法就是递归，决策树也不例外。对于决策树而言，训练过程通常是递归地选择决策条件，即决策分裂的条件(通常是训练集中某一个维度的特征)，并根据该特征对训练数据进行划分，使得各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的分割，也对应着决策树的构建。

3.1 算法的大致流程

1. 首先构建树的根节点，在一开始，将所有训练数据都放在根节点。
2. 选择一个最优特征，按着这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。
3. 如果这些子集为空或者已经能够被基本正确的分类，那么构建叶节点，将这些子集分到所对应的叶节点上去，其中叶节点的类别=该结点所含样本最多的类别。
4. 如果还有子集不能够被正确的分类，则递归执行步骤2。
5. 直到每个子集都被分到叶节点上，即都有了明确的类，这样就生成了一颗决策树。

3.2 算法的伪代码

上述伪代码完整的给出了决策树的整体训练流程，但是却缺少了一个关键信息。决策树学习的关键行为体现在伪代码的第10行，即如何选择最优划分属性。在ID3，C4.5，CART算法中，最主要的不同就体现在最优属性划分的决策上。

一般而言，随着划分过程的不断进行，我们希望决策树的分支节点所包含的样本尽可能属于同一类别，即节点的纯度(purity)越来越高：

如上图所示，显然分割方式2的纯度更高。

3.3 经典的属性划分方法

决策树经典的属性划分方法一般有三种，分别是信息增益，信息增益率和基尼系数。要想理解它们需要一些数学基础。

3.3.1 先验知识 : 信息熵与条件熵

信息熵用于描述一件事发生的不确定性，如果某个事件有 n 个结果，每个结果的概率为 p_n。那么这个事件的熵 H§ 定义为：(log以2为底的信息熵单位是bit，除此之外还可以e为底)
$$H(P)=?\sum _{i=1}^n{p}_i{\log }_2{p}_i$$
单变量下的信息熵曲线：

可以看出，对于一个事件而言，其发生的不确定性越大，其信息熵就越大。

信息熵的Python代码实现

    '''计算给定数据集(标签)的总信息熵'''
    # y:数据的标签, size=(batches,)
    def calcShannonEnt(self, y):
        entropy = 0.  # 信息熵
        size = len(y) # 数据集大小
        classes_idx_num = dict(Counter(y)) # 统计每类标签下包含的数据个数
        # 计算信息熵
        for key in classes_idx_num.keys():
            # 计算第key个标签的信息熵分量
            prob = classes_idx_num[key] / size # 用出现频率表示概率
            entropy -= prob * np.log2(prob)    # 信息熵计算公式
        return entropy

熵是对事件结果不确定性的度量，但在知道有些条件时，不确定性会变小。例如，一个人是否是艾滋病的阳性，这个事件的不确定性会随着医疗检测结果而降低。

条件熵衡量的就是在某个条件 Q 下，事件 P 的不确定性，记作 H(P|Q) 。其定义式为
$$\begin{gathered} H(P|Q)=?\sum _{i=1}^{n}P(p_i|q_i)?H(p_i) \\ =?\sum _{i=1}^{n}P(p_i|q_i)?p_i{\log }_2{p}_i \end{gathered}$$

假如现在我们有以下西瓜数据集，我们将从以下三种属性划分方法区别其中的不同：

3.3.2 信息增益 (代表算法：ID3)

信息增益定义为知道了某个条件a后，事件D的不确定性下降的程度。写作 Gain(D,a)。它的计算方式为熵减去条件熵.

现在我们假设数据集某一维度a可以有V个不同的取值，若使用a这一维度来对数据集D进行划分，则会产生V个分支节点，其中第v个分支节点包含了D中所有在属性a上取值为av的样本，记为D^v。
$$Gain(D,a)=H(D)?\sum _{i=1}^V\frac{|D^v|}{|D|}?H(D^v)$$
一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的子数据集的纯度提升越大。

现在如果我们要求得西瓜数据集中“色泽”这一维度的信息增益，首先得到该属性下分别有三个不同的取值，分别是（D1:青绿， D2:乌黑，D3:浅白），分别计算三个属性下的信息熵：
$$\begin{array}{rl}& \mathrm{Ent}\left(D^1\right)=?\left(\frac{3}{6}{\log }_2\frac{3}{6}+\frac{3}{6}{\log }_2\frac{3}{6}\right)=1.000\\ & \mathrm{Ent}\left(D^2\right)=?\left(\frac{4}{6}{\log }_2\frac{4}{6}+\frac{2}{6}{\log }_2\frac{2}{6}\right)=0.918\\ & \mathrm{Ent}\left(D^3\right)=?\left(\frac{1}{5}{\log }_2\frac{1}{5}+\frac{4}{5}{\log }_2\frac{4}{5}\right)=0.722\end{array}$$
“色泽”这一维度下的信息增益等于数据集的总信息熵减去不同属性下的信息熵的加权求和：
$$\begin{array}{rl}\mathrm{Gain}(D,\text{?色泽?})& =\mathrm{Ent}(D)?\sum _{v=1}^3\frac{\left|D^v\right|}{|D|}\mathrm{Ent}\left(D^v\right)\\ & =0.998?\left(\frac{6}{17}\times 1.000+\frac{6}{17}\times 0.918+\frac{5}{17}\times 0.722\right)\\ & =0.109\end{array}$$

信息增益python代码实现

    '''划分选择:使用信息增益'''
    # X:     输入数据, size=(batches, features)
    # y:     类别标签, size=(batches,)
    # dim:   当前是第几维度
    # num_D: 数据总数
    # ent_D: 数据集整体熵
    def Gain(self, X, y, num_D, ent_D, dim):
        a = X[:, dim] # 获取数据第dim维度
        v = set(a)    # 获取数据第dim维度可能的取值
        ent_a = 0     # 数据第dim维度的信息熵
        # 计算数据第dim维度的信息增益:
        for i in v:
            # 第dim维度第i个取值出现的频率
            prob_a_v = np.sum(a==i)/num_D
            # 第dim维度第i个取值下的信息熵
            ent_a_v_cls = self.calcShannonEnt(y[np.where(a==i)])
            ent_a += prob_a_v * ent_a_v_cls
        return ent_D - ent_a

但是这时候假如某个条件极其严格，比如某个同学提前知道了所有选择题的答案，那么将选择题的序号作为条件，就不存在任何不确定性，此时的信息增益就等于原始熵。所以可以得到最大的信息增益。实际上，信息增益准则对可取值数目较多属性有所偏好。但是这个结果是没有意义的，假设老师换一份考卷答案就全部作废了。(显然，这时候的决策树不具有泛化能力，必定是过拟合的)

3.3.3 信息增益率 (代表算法：C4.5)

信息增益率在信息增益的基础上增加了正则项，正则项是特征的固有值(intrinsic value)，可以理解为一个权重Wa，属性a的取值数目越多，则权重越小。因此，增益率准则对可取值数目较多的属性有所偏好。
$$\begin{gathered} W_a=\frac{1}{H(D_a)}=?\sum _{i=1}^V\frac{|D^v|}{|D|}?{\log }_2(\frac{|D^v|}{|D|}) \\ Gainratio(D,a)=W_a?Gain(D,a) \end{gathered}$$

如何计算西瓜数据集中“色泽”这一维度的信息增益，只需要计算该维度的信息熵的倒数再乘上信息增益即可：
$$\begin{array}{rl}& \mathrm{Ent}\left(D^{色泽}\right)=?\left(\frac{6}{17}{\log }_2\frac{6}{17}+\frac{6}{17}{\log }_2\frac{6}{17}+\frac{5}{17}{\log }_2\frac{5}{17}\right)=0.476\\ & gainratio=\frac{\mathrm{Gain}(D,\text{?色泽?})}{\mathrm{Ent}\left(D^{色泽}\right)}=0.229\end{array}$$

信息增益率python代码实现

    '''划分选择:使用信息增益率'''
    # X:     输入数据, size=(batches, features)
    # y:     类别标签, size=(batches,)
    # dim:   当前是第几维度
    # num_D: 数据总数
    # ent_D: 数据集整体熵
    def gainRatio(self, X, y, num_D, ent_D, dim):
        a = X[:, dim] # 获取数据第dim维度
        # 首先求取数据的信息增益
        gain = self.Gain(X, y, num_D, ent_D, dim)
        # 求取数据的固有值
        IV = self.calcShannonEnt(a)
        # 信息增益率= 1 / 固有值 *信息增益
        return  gain / IV

3.3.4 基尼系数 (代表算法：CART)

除了以上两种方法，数据集的纯度还可以用基尼系数(Gini index)来衡量

Gini系数大家可能比较耳熟，通常作为衡量一个国家或地区居民收入差距的常用指标，基尼系数最大为1，最小等于0。基尼系数越接近 0 表明收入分配越是趋向平等。
$$\mathrm{Gini}(p)=\sum _{k=1}^K{p}_k\left(1?p_k\right)=1?\sum _{k=1}^K{p}_k^2$$
上面这个变换很好理解。相当于，两者不相等的概率=1-两者相等的概率。直观的说，Gini(D)反映了从数据集D中随机抽两个样本，这两个样本类别不一致的概率。

以第a维度为决策条件下数据集D的基尼系数(基尼系数乘上一个权重)：
$$\begin{gathered} \mathrm{G}\mathrm{i}\mathrm{n}{\mathrm{i}}_{\mathrm{i}\mathrm{d}\mathrm{x}}(D,a)=\sum _{i=1}^{V}P(D^v)?Gini(D^v) \\ =\sum _{i=1}^V\frac{|D^v|}{|D|}?Gini(D^v) \end{gathered}$$

计算西瓜数据集中“色泽”这一维度的基尼系数：
$$\begin{array}{rl}& \mathrm{Gini}\left(D^1\right)=1?\left((\frac{3}{6}{)}^2+(\frac{3}{6}{)}^2\right)=\frac{1}{2}\\ & \mathrm{Gini}\left(D^2\right)=1?\left((\frac{4}{6}{)}^2+(\frac{2}{6}{)}^2\right)=\frac{4}{9}\\ & \mathrm{Gini}\left(D^3\right)=1?\left((\frac{1}{5}{)}^2+(\frac{4}{5}{)}^2\right)=\frac{8}{25}\\ & \mathrm{G}\mathrm{i}\mathrm{n}{\mathrm{i}}_{\mathrm{i}\mathrm{d}\mathrm{x}}(D,色泽)=\frac{6}{17}?\frac{1}{2}+\frac{6}{17}?\frac{4}{9}+\frac{5}{17}?\frac{8}{25}=0.44\end{array}$$

信息增益率python代码实现

    # 计算某一维度相对于标签的基尼指数
    def Gini(self, y):
        size = len(y) # 数据集大小
        gini_total = 0
        classes_idx_num = dict(Counter(y)) # 统计每类标签下包含的数据个数
        # 计算基尼系数:
        for key in classes_idx_num.keys():
            # 计算第key个标签的基尼系数分量
            prob = classes_idx_num[key] / size # 用出现频率表示概率
            gini_total += prob * prob
        return 1 - gini_total


    '''划分选择:使用基尼系数'''
    # X:     输入数据, size=(batches, features)
    # y:     类别标签, size=(batches,)
    # dim:   当前是第几维度
    # num_D: 数据总数
    def GiniIdx(self, X, y, num_D, dim):
        a = X[:, dim] # 获取数据第dim维度
        v = set(a)    # 获取数据第dim维度可能的取值
        gini_a = 0
        # 计算数据第dim维度的信息增益:
        for i in v:
            # 第dim维度第i个取值出现的频率
            prob_a_v = np.sum(a==i)/num_D
            gini_a_v = self.Gini(y[np.where(a==i)])
            gini_a += prob_a_v * gini_a_v
        return gini_a

3.4 决策树剪枝

由于训练样本只能反映真实世界的某种近似模拟，并不能代表真实世界的真实分布。与此同时，学习算法本身在训练集上学习出的归纳偏好将不可避免的导致模型本身的过拟合，这是机器学习算法的一个无法解决通病。对于决策树而言，剪枝(pruning)是决策树算法对付过拟合的主要手段，对于一棵未剪枝的决策树而言，若把训练集学的过好了，就会造成决策分支过多，有时甚至把某种噪声也作为一种决策条件。这时候算法就需要主动去掉一些分支来降低过拟合的风险。

预剪枝(prepruning)

预剪枝是指在决策树生成决策节点之前，先对每个划分结点进行估计，若当前节点的划分不能带来决策树泛化性能的提升，则停止划分并将当前节点标记为叶节点。

预剪枝的要点就在于“决策树泛化性能的提升”，如何判断一棵决策树增加一一个决策节点后泛化性能是否提升，可以通过将训练集划分为两部分，一部分作为训练集，另一部分作为验证集，这种方法叫”留出法“，通过训练集训练决策树，然后在验证集上评估其泛化性能。

以西瓜数据集为例：

在生成第一个决策节点时，首先计算不划分前的预测精度，我们默认假设全为好瓜，则预测精度为3/7。这时后倘若引入“脐部”决策结点，我们会将“凹陷”，“稍凹”属性划分为好瓜，将“平坦”属性划分为坏瓜，根据这个决策标准在验证集上，算法的正确率为5/7，说明加入该节点后验证集的精度提升了，则保留该决策节点 ，否则直接将其归纳为子数据集中类别最多的那个属性。以此类推：

后剪枝(postpruning)

后剪枝则是先依据训练集生成一棵完整的决策树，然后自底向上的对非叶子节点进行考察，若将该节点对于的子树替换为叶节点能带来决策树泛化性能的提升，则将该子树替换为叶子节点，否则保留。

比如，对于下图左侧的决策树，其在验证集上的精度为42.9%。后剪枝算法先考察最后一个非叶节点6，将其替换为叶子节点"好瓜"，此时模型在验证集的精度提升到57.1%，此时剪枝是更好的选择。然后考察节点5，此时无论是否剪枝，在验证集书上的精度均为57.1%，此时可以不进行剪枝。以此类推，直到根节点。

4.代码部分

ID3决策树算法 (以隐形眼镜数据集为例)

**数据导入部分 **myutils.py

数据集以txt文本文件格式存储，在读取之后将其转化为numpy.array格式，并拆分成数据集与标签。转化成numpy数组有一个好处：numpy数组除了具有广播机制以外，还能够方便我们以任意维度切片

'''读取数据集并转化为np.array'''
def readFile(path):
    file = open(path) # 读取文件
    cls_value = file.readline().split('\t')[:-1]
    # 切分数据的不同维度
    data = np.array([line.split('\t') for line in file.readlines()])
    return data[:, :-1], data[:, -1], np.array(cls_value)

将原始数据转化为numpy数组：

决策树可视化部分

由于可视化的具体方法不是本次博客的重点，再加上博主本人时间有限**(还要复习考研)**，因此这部分将采取书上的源代码，具体实现细节有兴趣的小伙伴们可以深入研究：

def plotMidText(cntrPt, parentPt, txtString):
    xMid = (parentPt[0]-cntrPt[0])/2.0 + cntrPt[0]
    yMid = (parentPt[1]-cntrPt[1])/2.0 + cntrPt[1]
    createPlot.ax1.text(xMid, yMid, txtString, va="center", ha="center", rotation=30)


def plotNode(nodeTxt, centerPt, parentPt, nodeType):
    createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords='axes fraction',
    xytext=centerPt, textcoords='axes fraction', 
    va='center', ha='center', bbox=nodeType, arrowprops=arrow_args
    )


def plotTree(DTree, parentPt, nodeTxt):#if the first key tells you what feat was split on
    numLeafs = getNumLeaves(DTree)  #this determines the x width of this tree
    depth = getTreeDepth(DTree)
    firstStr = list(DTree.keys())[0]     #the text label for this node should be this
    cntrPt = (plotTree.xOff + (1.0 + float(numLeafs))/2.0/plotTree.totalW, plotTree.yOff)
    plotMidText(cntrPt, parentPt, nodeTxt)
    plotNode(firstStr, cntrPt, parentPt, decisionNode)
    secondDict = DTree[firstStr]
    plotTree.yOff = plotTree.yOff - 1.0/plotTree.totalD
    for key in secondDict.keys():
        if type(secondDict[key]).__name__=='dict':#test to see if the nodes are dictonaires, if not they are leaf nodes   
            plotTree(secondDict[key],cntrPt,str(key))        #recursion
        else:   #it's a leaf node print the leaf node
            plotTree.xOff = plotTree.xOff + 1.0/plotTree.totalW
            plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)
            plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))
    plotTree.yOff = plotTree.yOff + 1.0/plotTree.totalD
#if you do get a dictonary you know it's a tree, and the first element will be another dict


# 决策树节点绘制主方法:
def createPlot(DTree):
    fig = plt.figure(1, facecolor='white')
    fig.clf()
    axprops = dict(xticks=[], yticks=[])
    createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)    #no ticks
    #createPlot.ax1 = plt.subplot(111, frameon=False) #ticks for demo puropses 
    plotTree.totalW = float(getNumLeaves(DTree))
    plotTree.totalD = float(getTreeDepth(DTree))
    plotTree.xOff = -0.5/plotTree.totalW
    plotTree.yOff = 1.0
    plotTree(DTree, (0.5,1.0), '')
    plt.show()

获取决策树的叶子节点数以及树深度：

# 递归获取树的叶子结点数(深度优先遍历)
def getNumLeaves(DTree):
    num_leaves = 0
    root = list(DTree.keys())[0]
    son_node = DTree[root]
    for key in son_node.keys():
        if type(son_node[key]).__name__ == 'dict':
            # 递归计算子节点
            num_leaves += getNumLeaves(son_node[key])
        else: 
            num_leaves += 1
    return num_leaves



# 递归获取树的深度(深度优先遍历)
def getTreeDepth(DTree):
    max_depth = 0
    root = list(DTree.keys())[0]
    son_node = DTree[root]
    # 返回当前层的最大深度
    for key in son_node.keys():
        if type(son_node[key]).__name__ == 'dict':
            # 递归计算子节点的深度
            this_depth = getTreeDepth(son_node[key])
        else: 
            # 如果子节点是叶子结点，则子节点的深度为1
            this_depth = 1
        # 子树的深度取决于最大的子节点的深度
        if this_depth > max_depth:
            max_depth = this_depth
    # 树的深度 = 1(根节点) + 子节点的深度
    return max_depth + 1

决策树模块decisionTree.py

算法的各个功能都集成到一个类中decisionTree

import numpy as np     
import pickle
import copy
from collections import Counter

from myutils import readFile, createPlot


class decisionTree:

    def __init__(self, X_train, y_train, X_test, y_test, label, mode="gain"):
        self.X_train = X_train
        self.y_train = y_train
        self.X_test = X_test
        self.y_test = y_test
        self.label = label
        self.mode = mode


    '''计算给定数据集(标签)的总信息熵'''
    # y:数据的标签, size=[batches,]
    def calcShannonEnt(self, y):
        entropy = 0.  # 信息熵
        size = len(y) # 数据集大小
        classes_idx_num = dict(Counter(y)) # 统计每类标签下包含的数据个数
        # 计算信息熵
        for key in classes_idx_num.keys():
            # 计算第key个标签的信息熵分量
            prob = classes_idx_num[key] / size # 用出现频率表示概率
            entropy -= prob * np.log2(prob)    # 信息熵计算公式
        return entropy


    '''选取特定维度下特定值的数据，返回剔除这个维度后的结果
    (相当于一次决策过程生成一个子数据集)
    '''
    # X:     输入数据
    # y:     输入数据的标签
    # label: 输入数据不同维度的属性
    # dim：  当前是第几维度
    # val：  该维度的指定取值
    def datasetSplit(self, X, y, label, dim, val):
        sub_X = []  # 保存划分后的子数据集
        sub_y = []  # 保存子数据集的标签
        # 遍历所有数据
        for i in range(X.shape[0]):
            # 如果指定维度下的特征等于指定值
            if X[i, dim] == val:
                data = X[i, :]
                # 则选择这个数据并剔除这一维度
                sub_X.append(np.delete(data, dim, 0))
                sub_y.append(y[i])
        # 删除已决策维度的标签
        sub_label = np.delete(label, dim, 0)
        return np.array(sub_X), np.array(sub_y), sub_label


    '''划分选择:使用信息增益'''
    # X:     输入数据, size=(batches, features)
    # y:     类别标签, size=(batches,)
    # dim:   当前是第几维度
    # num_D: 数据总数
    # ent_D: 数据集整体熵
    def Gain(self, X, y, num_D, ent_D, dim):
        a = X[:, dim] # 获取数据第dim维度
        v = set(a)    # 获取数据第dim维度可能的取值
        ent_a = 0     # 数据第dim维度的信息熵
        # 计算数据第dim维度的信息增益:
        for i in v:
            # 第dim维度第i个取值出现的频率
            prob_a_v = np.sum(a==i)/num_D
            # 第dim维度第i个取值下的信息熵
            ent_a_v_cls = self.calcShannonEnt(y[np.where(a==i)])
            ent_a += prob_a_v * ent_a_v_cls
        return ent_D - ent_a


    '''划分选择:使用信息增益率'''
    # X:     输入数据, size=(batches, features)
    # y:     类别标签, size=(batches,)
    # dim:   当前是第几维度
    # num_D: 数据总数
    # ent_D: 数据集整体熵
    def gainRatio(self, X, y, num_D, ent_D, dim):
        a = X[:, dim] # 获取数据第dim维度
        # 首先求取数据的信息增益
        gain = self.Gain(X, y, num_D, ent_D, dim)
        # 求取数据的固有值
        IV = self.calcShannonEnt(a)
        # 信息增益率=固有值*信息增益
        if IV == 0 :
            return 0 
        else :
            return (gain / IV)








    # 计算某一维度相对于标签的基尼指数
    def Gini(self, y):
        size = len(y) # 数据集大小
        gini_total = 0
        classes_idx_num = dict(Counter(y)) # 统计每类标签下包含的数据个数
        # 计算基尼系数:
        for key in classes_idx_num.keys():
            # 计算第key个标签的基尼系数分量
            prob = classes_idx_num[key] / size # 用出现频率表示概率
            gini_total += prob * prob
        return 1 - gini_total


    '''划分选择:使用基尼系数'''
    # X:     输入数据, size=(batches, features)
    # y:     类别标签, size=(batches,)
    # dim:   当前是第几维度
    # num_D: 数据总数
    def GiniIdx(self, X, y, num_D, dim):
        a = X[:, dim] # 获取数据第dim维度
        v = set(a)    # 获取数据第dim维度可能的取值
        gini_a = 0
        # 计算数据第dim维度的信息增益:
        for i in v:
            # 第dim维度第i个取值出现的频率
            prob_a_v = np.sum(a==i)/num_D
            gini_a_v = self.Gini(y[np.where(a==i)])
            gini_a += prob_a_v * gini_a_v
        return gini_a






    '''选取最佳划分维度'''
    def bestFeature(self, X, y):
        # 数据总信息熵
        ent_D = self.calcShannonEnt(y)
        # 数据的大小
        num_D = len(y)
        # 最佳信息增益对应的维度(初始化-1)
        best_dim = -1

        # 遍历所有维度寻找最佳信息增益
        if self.mode == "gain":
            # 最佳信息增益(初始化0)
            best_gain = 0
            for i in range(X.shape[1]):
                gain = self.Gain(X, y, num_D, ent_D, i) # 信息增益
                # 更新
                if best_gain < gain:
                    best_gain = gain 
                    best_dim = i
        if self.mode == "gain_ratio":
            # 最佳信息增益(初始化0)
            best_gain = 0
            for i in range(X.shape[1]):
                gain = self.gainRatio(X, y, num_D, ent_D, i) # 信息增益率
                # 更新
                if best_gain < gain:
                    best_gain = gain 
                    best_dim = i
        if self.mode == "gini":
            # 最佳信息增益(初始化inf)
            best_gain = np.inf
            for i in range(X.shape[1]):
                gain = self.GiniIdx(X, y, num_D, i)           # 基尼系数
                # 更新
                if best_gain > gain:
                    best_gain = gain 
                    best_dim = i

        return best_dim


    '''递归生成决策树'''
    def createTree(self, X, y, label):
        # 类别完全相同则停止继续划分
        if len(set(y)) == 1:
            return y[0]
        # 遍历完所有的维度返回出现次数最多的类别
        if X.shape[1] == 1:
            return np.argmax(np.bincount(y))
        # 选取最佳划分维度    
        best_dim = self.bestFeature(X, y)
        # 以当前维度为根节点创建决策树(字典的形式)
        DTree = {label[best_dim]:{}}
        # 获取当前维度的所有可能取值:
        dim_val = X[:, best_dim]
        unique_vals = set(dim_val)
        # 递归的创建决策树(深度优先遍历)
        for val in unique_vals:
            sub_X, sub_y, sub_label = self.datasetSplit(X, y, label, best_dim, val)
            # print(sub_y.shape)
            DTree[label[best_dim]][val] = self.createTree(sub_X, sub_y, sub_label)
        return DTree


    '''递归生成决策树'''
    def createTree_with_cut(self, X, y, label):
        # print(X.shape)
        # 类别完全相同则停止继续划分
        if len(set(y)) == 1:
            return y[0]
        # 遍历完所有的维度返回出现次数最多的类别
        if X.shape[1] == 1:
            return np.argmax(np.bincount(y))
        # 选取最佳划分维度    
        best_dim = self.bestFeature(X, y)
        print(best_dim)
        # 以当前维度为根节点创建决策树(字典的形式)
        DTree = {label[best_dim]:{}}
        #########################################################
        # 计算精度(剪枝)
        max_cls = max(list(y), key=list(y).count)
        before_acc = sum(self.y_test==max_cls)/self.y_test.shape[0]
        #########################################################
        # 获取当前维度的所有可能取值:
        dim_val = X[:, best_dim]
        unique_vals = set(dim_val)
        # 递归的创建决策树(深度优先遍历)
        for val in unique_vals:
            sub_X, sub_y, sub_label = self.datasetSplit(X, y, label, best_dim, val)
            # print(sub_y.shape)
            DTree[label[best_dim]][val] = self.createTree_with_cut(sub_X, sub_y, sub_label)
        #########################################################
        # 剪枝
        after_acc = self.calcAccuracy(DTree, label)
        if(before_acc > after_acc):
            return max_cls
        #########################################################

        return DTree

    '''计算测试集精度'''
    def calcAccuracy(self, DTree, label):
        acc = 0
        for i in range(self.y_test.shape[0]):
            acc += self.predict(DTree, self.X_test[i,:], label) == self.y_test[i]
        return acc / self.y_test.shape[0]


    '''创建决策树(调用递归函数)'''
    def initDTree(self):
        # DTree = self.createTree(self.X_train, self.y_train, self.label)
        DTree = self.createTree_with_cut(self.X_train, self.y_train, self.label)
        # 决策树的结构是一个嵌套字典:
        self.DTree = DTree


    '''决策树搜索预测过程(DFS)'''
    '''缺点在于每次只能喂入一条数据'''
    def predict(self, DTree, X, label):
        root = list(DTree.keys())[0]
        son_node = DTree[root]
        # 寻找当前决策节点在数据的哪一维度:
        index_0 = np.where(label == root)[0]
        index_1 = np.where(X == root)[0]
        index = index_1[0] if index_0.size == 0 else index_0[0]
        # 深度优先遍历:
        class_label = -1
        for key in son_node.keys():
            if X[index] == key:
                if type(son_node[key]).__name__ == 'dict':
                    # 如果不是叶子节点就递归搜索
                    class_label = self.predict(son_node[key], X, label)
                else:
                    # 如果是叶子节点就返回对应的类别
                    class_label = son_node[key]
        # 若决策树没有数据当前维度下的取值对应的决策属性，则直接返回该节点下数量最多的类别
        return self.getLeafCls(DTree) if class_label == -1 else class_label



    '''递归获取树的叶子结点类别(深度优先遍历)'''
    def _getLeafCls(self, DTree, leaf):
        root = list(DTree.keys())[0]
        son_node = DTree[root]
        for key in son_node.keys():
            if type(son_node[key]).__name__ == 'dict':
                # 递归计算子节点
                leaf = self._getLeafCls(son_node[key], leaf)
            else: 
                leaf.append(son_node[key])
        return leaf

    '''获取树的叶子结点数量最多的类别'''
    def getLeafCls(self, DTree):
        leaf_cls = []
        leaf_cls = self._getLeafCls(DTree, leaf_cls)

        # 返回当前节点下数量最多的叶子结点的类别：
        best_cls = max(leaf_cls, key=leaf_cls.count)
        return best_cls




    '''保存决策树模型'''
    def saveTree(self, path):
        # 以二进制文件保存
        file = open(path, 'wb')
        pickle.dump(self.DTree, file)

    '''读取决策树模型'''
    def loadTree(self, path):
        # 以二进制文件读取
        file = open(path, 'rb')
        self.DTree = pickle.load(file)

根据函数createTree的构造思路不难发现，决策树一旦生成了其中的某个决策节点，在接下来的构造过程中就不会再改变。因此我们说决策树的训练过程属于一种贪婪算法，虽然每一步都是当前的最优，但最终的结果可能陷入了局部最优

代码中的决策树信息划分分为3.3部分所述的三种实现方法，这里以Gain函数为例，我们可以输出其对于lense数据集所有维度的信息增益：

ent_D = DT.calcShannonEnt(y)
[print(DT.Gain(X, y, 24, ent_D, i)) for i in range(4)]

0.03939650364612124
0.039510835423565815
0.3770052300114771
0.5487949406953986

可见，数据集的第4维特征为信息增益最大的维度，通过观察也显而易见：reduced这一取值上的数据类别是纯的。

除此之外，值得注意的是，假如使用基尼系数作为划分标准，则越小反映数据越纯，这需要和另外两个算法区分开(之前没注意到这个细节调试半天气死了)：

# 最佳信息增益(初始化inf)
best_gain = np.inf
... ...
# 更新
if best_gain > gain:
    ... ...

主函数部分：

if __name__ == '__main__':
    path = './lenses.txt'
    # 读取数据集
    X, y, label = readFile(path)
    DT = decisionTree(X, y, label)
    # 训练
    DT.initDTree()
    # 可视化树结构
    createPlot(DT.DTree)
    # 保存模型
    DT.saveTree('./dtree.txt')
    # 读取模型
    DT.loadTree('./dtree.txt')
    # 预测
    print(DT.predict(DT.DTree, X[9,:], label))

通过打印DT.DTree可以显示决策树。划分节点存储结构为字典，每一个子字典都为一棵子树，字典的key为决策节点)：

{‘tearRate’: {‘normal’: {‘astigmatic’: {‘no’: {‘age’: {‘pre’: ‘soft\n’, ‘young’: ‘soft\n’, ‘presbyopic’: {‘prescript’: {‘hyper’: ‘soft\n’, ‘myope’: ‘no lenses\n’}}}}, ‘yes’: {‘prescript’: {‘hyper’: {‘age’: {‘pre’: ‘no lenses\n’, ‘young’: ‘hard\n’, ‘presbyopic’: ‘no lenses\n’}}, ‘myope’: ‘hard\n’}}}}, ‘reduced’: ‘no lenses\n’}}

当然这种形式未免太过于不直观，我们可以使用上述可视化模块createPlot来绘制一棵决策树:

可视化树结构：

5.实验部分

5.1基于决策树的二值化手写数字识别(书上的例子)

数据集可视化：

使用信息增益作为划分标准的决策树可视化:

测试集精度: 0.8805496828752643

使用信息增益率作为划分标准的决策树可视化:

测试集精度:0.861522198731501

使用基尼指数作为划分标准的决策树可视化:

测试集精度:0.8710359408033826

代码实现：

import numpy as np
import matplotlib.pyplot as plt

import sys; sys.path.append('../')
from decisionTree import decisionTree
from myutils import readFile, createPlot



# 读取数据集
X_train = np.load('X_train.npy').reshape(1934, 1024)
y_train = np.load('y_train.npy')
X_test = np.load('X_test.npy').reshape(946, 1024)
y_test = np.load('y_test.npy')
label = np.array([i for i in range(1024)])
print(X_train.shape,X_test.shape)



# 数据集可视化
for i in range(32):
    plt.subplot(4, 8, i+1)
    img = X_train[i*60,:].reshape(32, 32)
    plt.imshow(img)
    plt.title(y_train[i*60])
    plt.axis("off")                
    plt.subplots_adjust(hspace = 0.3)  # 微调行间距
plt.show()



DT = decisionTree(X_train, y_train, X_test, y_test, label, "gain")
DT.initDTree()
DT.saveTree('./digitsTree(gain).txt')
print(DT.DTree)
DT.loadTree('./digitsTree(gain).txt')
createPlot(DT.DTree)




acc = 0
for i in range(946):
    X = X_test[i,:]
    acc += DT.predict(DT.DTree, X, label) == y_test[i]
print(acc/946)

5.2分类树防止过拟合的一个方法(连续区间划分)

以Fashion MNIST数据集为例，数据集可视化:

分类决策树的构建过程依赖于每一个属性的不同的取值，对于图像数据集而言，每一个维度就代表着图像的每一个像素，而像素的灰度阶介于(0,255)之间，因此对于决策树而言，图像的每一个维度就包含有256个不同的属性，如果不采取措施，就会导致决策树的每一层过于枝繁叶茂，最终导致模型的过拟合(划分属性为信息增益)：

最终再测试集上的预测精度为0.1078，Fashion Mnist数据集共有10个类别，这样的结果和随机猜测别无二致。

一个有效且简便的方法是将图像的256个灰度阶划分区间，一个极端的情况就是图像二值化:

对数据集执行区间划分的预处理后，最终生成的决策树为一棵二叉树(划分属性为信息增益)。可以发现，决策树每个决策节点的广度降低了，取而代之的是树的深度增加了(可不可以这样理解，决策树的广度可以类比卷积神经网络每一层的卷积核数量，表示提取特征的多样性。而决策树的深度可以类比网络的深度，树的深度越深代表提取数据的语义特征越高级，因此也越能够抽象出数据的隐含特征。)上述只是博主的一个想法，若有任何不严谨的地方，欢迎各位机器学习大佬在评论区留言 😃

最终在测试集上的精度为0.8049(包含预剪枝，划分属性为信息增益)，精度明显得到了较大的改善。

对于数据集中存在连续变量的维度而言，区间划分这一方法均能起到很好的防止过拟合的效果。

模型在信息增益率的划分属性下的分类精度为(包含预剪枝)：0.7842

模型在基尼系数的划分属性下的测试精度为(包含预剪枝)：0.7866

5.3 可视化决策树在数据集上的“注意力映射”

对于图像分类任务而言，我们可以将决策树的决策节点映射到原始图像的坐标(维度)上，来直观的感受原始图像的哪一些区域是决策区域。我的思路是，越是浅层的节点其决策的重要程度就越大，在可视化映射过程中应该得到更多的权重：

如上图所示，注意力映射图基于数据集Fashion_MNIST。

代码实现：

import pickle
import numpy as np
import matplotlib.pyplot as plt



'''递归获取树的深度(深度优先遍历)'''
def getTreeDepth(DTree):
    max_depth = 0
    root = list(DTree.keys())[0]
    son_node = DTree[root]
    # 返回当前层的最大深度
    for key in son_node.keys():
        if type(son_node[key]).__name__ == 'dict':
            # 递归计算子节点的深度
            this_depth = getTreeDepth(son_node[key])
        else: 
            # 如果子节点是叶子结点，则子节点的深度为1
            this_depth = 1
        # 子树的深度取决于最大的子节点的深度
        if this_depth > max_depth:
            max_depth = this_depth
    # 树的深度 = 1(根节点) + 子节点的深度
    return max_depth + 1



'''递归获取树的叶子结点类别(深度优先遍历)'''
def getLeafCls(DTree, img_index):
    root = list(DTree.keys())[0]
    son_node = DTree[root]
    for key in son_node.keys():
        if type(son_node[key]).__name__ == 'dict':
            depth = getTreeDepth(son_node[key])
            img_index[root] += depth  
            getLeafCls(son_node[key], img_index)
        else: 
            return
    return img_index


tree = ['digitsTree(gini).txt','digitsTree(gain).txt','digitsTree(gain_ratio).txt']
for i in range(3):
    plt.subplot(1,3,i+1)
    Tree = pickle.load(open(tree[i], 'rb'))
    img_idx = np.zeros(784)
    img_idx = getLeafCls(Tree, img_idx).reshape(28,28)
    plt.imshow(img_idx)
    plt.title(tree[i].split('.')[0])
plt.show()

事实上，如果要再更进一步，我们可以通过决策树的叶子结点的类别来有针对的实现类别上的注意力映射，从而观察不同类别下决策树偏向于决策哪一部分区域，实现方法大致思路和求取两点间的所有路径相似，由于博主时间有限，先挖一个坑。

6.算法优缺点总结

优点：

1. 决策树易于理解和实现，这使得人们在学习过程中不需要使用者了解很多的背景知识，同时它的可解释性强，只要通过解释后都有能力去理解决策树所期望表达的意义。
2. 可以发现，决策树算法的超参数相对较少，上述介绍的经典算法中只有划分依据这一个超参数，对于模型本身而言不需要类似深度学习算法的“玄学调参”，因此如果数据本身复杂度不高，模型很容易训练。

缺点：

1. 就如实验中所展示的那样，决策树对于连续性的子段较难进行划分，对于这类数据而言需要很多的预处理的工作。
2. 当类别的划分属性普遍较多时，模型极其容易发生过拟合现象(同1)。
3. 模型以树形结构作为算法的基本框架，假如使用递归遍历方法，模型深度较深时，容易占用较大的内存空间。
4. 在模型验证时，无法通过矩阵运算的方式进行批量处理。

机器学习实验专栏系列文章：
【机器学习实验一】手撕 kNN(K-Nearest Neighbor, k最邻近算法)
【机器学习实验二】决策树(Decision Tree)及其在图像识别任务上的应用