【统计学习方法】||5决策树

【决策树】

1986年Quinlan提出ID3算法，1993年Quinlan又提出C4.5算法，1984年Breiman等人提出CART算法。

决策树是一个呈树形的分类与回归模型。（判别模型）

决策树学习包括3个步骤：特征选择、决策树的生成和决策树的修剪。

奥卡姆剃刀定律：“如无必要 勿增实体”， 即”简单有效原理”。

0.预备信息

熵，信息量的期望；

互信息，度量X在知道Y以后不确定性的减少程度。

1.模型

分类决策树模型是一种描述对实例进行分类的树形结构。

决策树由结点（node）和有向边（directed edge）组成。

结点有两种类型：（1）内部节点（internal node）：表示一个特征或属性；（2）叶结点（leaf node）：表示一个类。

2.ID3算法

不足：

（1）没有考虑连续特征；

（2）采用信息增益大的优先建立节点；

（3）没有考虑缺失值；

（4）没有考虑过拟合。

3.C4.5算法

优化：

（1）→连续的特征离散化；

（2）→信息增益比

（3）→确定属性权重

（4）→正则化系数初步剪枝

4.CART算法

优化：

（1）优化剪枝算法（预剪枝，后剪枝）

（2）多叉树→二叉树

（3）只能用于分类→可用于回归

（4）熵模型对数运算强度大→基尼指数

•Q：基尼系数简化模型的同时，会不会丢失熵模型的优点？

从上图可以看出，基尼系数和熵之半的曲线非常接近，仅仅在45度角附近误差稍大。因此，基尼系数可以做为熵模型的一个近似替代。

5.决策树的剪枝

• 预剪枝

预剪枝的核心思想是在树中结点进行扩展之前，先计算当前的划分是否能带来模型泛化能力的提升，如果不能，则不再继续生长子树此时可能存在不同类别的样本同时存于结点中，搜照多数投票的原则判断该结点所属类别。

何时停止决策树的生长方法：

( 1 ）当树到达一定深度的时候，停止树的生长；
( 2 ）当到达当前结点的样本数 小于某个闺值的时候，停止树的生长；
( 3 ）计算每次分裂对测试集的准确度提升，当小于某个阈值的时不再继续扩展。

优缺点：

预剪枝具有思想直接、算法简单、效率高等特点，适合解决大规模问题。

预剪枝存在一定局限性，有欠拟台的风险，虽然当前的划分会导致测试集准确率降低，但在之后的划分中，准确率可能会有显著上升。（需要依赖一定的经验判断）

• 后剪枝

后剪枝的核心思想是让算法生成一棵完全生长的决策树，然后从最底层向上计算是否剪枝。剪枝过程将子树删除，用一个叶子结点替代，该结点的类别同样按照多数投票的原则进行判断。

优缺点：相比于预剪枝，后剪枝方法通常可以得到泛化能力更强的决策树，但时间开销会更大。

常见的后剪枝方法：

错误率降低剪枝（ Reduced Error Pruning, REP ）、悲观剪枝（ Pess mistic Error Pruning, PEP ）、代价复杂度剪枝（ Cost Complexity Pruning , CCP ）、最小误差剪枝（ Minimum Error Pruning , MEP ）、 CVP ( Critical Value Pruning ）、 OP ( Optimal Pruning ）等方法

6.损失函数（回归）

• 对于位于节点t的任意一颗子树Tt，如果没有剪枝，它的损失是：

• 如果将其剪掉，仅仅保留根节点，则损失是：

• 什么时候需要剪枝呢？就是子树不剪枝的损失比剪枝的损失大，即：

其中，C(Tt)为训练数据的预测误差，即模型与训练数据的拟合程度，分类树是用基尼系数度量，回归树是均方差度量。|Tt|是子树T的叶子节点的数量，表示模型复杂度，参数alpha>=0，为正则化参数，控制两者之间的影响。较大的alpha促使选择较简单的模型，较小的选择复杂的。=0则只考虑拟合程度不考虑复杂度。

交叉验证策略：

计算所有的节点是否剪枝的值α，然后分别针对不同α所对应的剪枝后的最优子树做交叉验证。这样就可以选择一个最好的α，以此对应的最优子树作为最终结果。

7.优缺点

【优：】

计算法复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。

【缺：】

（1）非常容易过拟合，泛化能力不强（过拟合，可以通过设置节点最少样本数量和限制决策树深度来改进）；

（2）决策树会因为样本发生一点点的改动，就会导致树结构的剧烈改变；

（3）寻找最优的决策树是一个NP难的问题，我们一般是通过启发式方法，容易陷入局部最优。

8.三者的差异

1.评价标准不一：

ID3 是采用信息增益作为评价标准，倾向于取值较多的特征。因为信息增益反映的是给定条件以后不确定性减少的程度，特征取值越多就意味确定性更高，也就是条件熵越小，信息增益越大。

C4.5 是采用信息增益比作为评价标准，实际上是对 ID3进行优化。一定程度上对取值比较多的特征进行惩罚，避免ID3出现过拟合的特性，提升决策树的泛化能力。

2.样本类型不一：

ID3只能处理离散型变量，C4.5和CART都可以处理连续型变量。

C4.5 处理连续型变量，通过对数据排序之后找到类别不同的分割线作为切分点，根据切分点把连续属性转换为布尔型，从而将连续型变量转换成多个取值区间的离散型变量。 

CART由于其构建时每次都会对特征进行二值划分，因此可以很好地适用于连续性变量。

3.应用任务不一：

ID3和C4.5 只能用于分类任务，而CART (Classfication and Regression Tree ，分类回归树）从名字就可以看出其不仅可以用
于分类，也可以应用于回归任务（回归树使用最小平方误差准则）。

4.实现细节、优化过程也不一：

比如 ID3 对样本特征缺失值比较敏感，而 C4.5和CART 可以对缺失值进行不同方式的处理；

ID3合C4. 5可以在每个结点上产生出多叉分支，且每个特征在层级之间不会复用，而 CART 每个结点只会产生两个分支，因此最后会形成 颗二叉树，且每个特征可以被重复使用；
ID3 C4.5 通过剪枝来权衡树的准确性与泛化能力，而 CART 直接利用全部数据发现所有可能的树结构进行对比。
 

9.代码

def calc_H_D(trainLabelArr):
    '''
    计算数据集D的经验熵，参考公式5.7 经验熵的计算
    :param trainLabelArr:当前数据集的标签集
    :return: 经验熵
    '''
    #初始化为0
    H_D = 0
    #将当前所有标签放入集合中，这样只要有的标签都会在集合中出现，且出现一次。
    #遍历该集合就可以遍历所有出现过的标记并计算其Ck
    #这么做有一个很重要的原因：首先假设一个背景，当前标签集中有一些标记已经没有了，比如说标签集中
    #没有0（这是很正常的，说明当前分支不存在这个标签）。 式5.7中有一项Ck，那按照式中的针对不同标签k
    #计算Cl和D并求和时，由于没有0，那么C0=0，此时C0/D0=0,log2(C0/D0) = log2(0)，事实上0并不在log的
    #定义区间内，出现了问题
    #所以使用集合的方式先知道当前标签中都出现了那些标签，随后对每个标签进行计算，如果没出现的标签那一项就
    #不在经验熵中出现（未参与，对经验熵无影响），保证log的计算能一直有定义
    trainLabelSet = set([label for label in trainLabelArr])
    #遍历每一个出现过的标签
    for i in trainLabelSet:
        #计算|Ck|/|D|
        #trainLabelArr == i：当前标签集中为该标签的的位置
        #例如a = [1, 0, 0, 1], c = (a == 1): c == [True, false, false, True]
        #trainLabelArr[trainLabelArr == i]：获得为指定标签的样本
        #trainLabelArr[trainLabelArr == i].size：获得为指定标签的样本的大小，即标签为i的样本
        #数量，就是|Ck|
        #trainLabelArr.size：整个标签集的数量（也就是样本集的数量），即|D|
        p = trainLabelArr[trainLabelArr == i].size / trainLabelArr.size
        #对经验熵的每一项累加求和
        H_D += -1 * p * np.log2(p)

    #返回经验熵
    return H_D

def calcH_D_A(trainDataArr_DevFeature, trainLabelArr):
    '''
    计算经验条件熵
    :param trainDataArr_DevFeature:切割后只有feature那列数据的数组
    :param trainLabelArr: 标签集数组
    :return: 经验条件熵
    '''
    #初始为0
    H_D_A = 0
    #在featue那列放入集合中，是为了根据集合中的数目知道该feature目前可取值数目是多少
    trainDataSet = set([label for label in trainDataArr_DevFeature])

    #对于每一个特征取值遍历计算条件经验熵的每一项
    for i in trainDataSet:
        #计算H(D|A)
        #trainDataArr_DevFeature[trainDataArr_DevFeature == i].size / trainDataArr_DevFeature.size:|Di| / |D|
        #calc_H_D(trainLabelArr[trainDataArr_DevFeature == i]):H(Di)
        H_D_A += trainDataArr_DevFeature[trainDataArr_DevFeature == i].size / trainDataArr_DevFeature.size \
                * calc_H_D(trainLabelArr[trainDataArr_DevFeature == i])
    #返回得出的条件经验熵
    return H_D_A

def calcBestFeature(trainDataList, trainLabelList):
    '''
    计算信息增益最大的特征
    :param trainDataList: 当前数据集
    :param trainLabelList: 当前标签集
    :return: 信息增益最大的特征及最大信息增益值
    '''
    #将数据集和标签集转换为数组形式
    #trainLabelArr转换后需要转置，这样在取数时方便
    #例如a = np.array([1, 2, 3]); b = np.array([1, 2, 3]).T
    #若不转置，a[0] = [1, 2, 3]，转置后b[0] = 1, b[1] = 2
    #对于标签集来说，能够很方便地取到每一位是很重要的
    trainDataArr = np.array(trainDataList)
    trainLabelArr = np.array(trainLabelList).T

    #获取当前特征数目，也就是数据集的横轴大小
    featureNum = trainDataArr.shape[1]

    #初始化最大信息增益
    maxG_D_A = -1
    #初始化最大信息增益的特征
    maxFeature = -1
    #对每一个特征进行遍历计算
    for feature in range(featureNum):
        #“5.2.2 信息增益”中“算法5.1（信息增益的算法）”第一步：
        #1.计算数据集D的经验熵H(D)
        H_D = calc_H_D(trainLabelArr)
        #2.计算条件经验熵H(D|A)
        #由于条件经验熵的计算过程中只涉及到标签以及当前特征，为了提高运算速度（全部样本
        #做成的矩阵运算速度太慢，需要剔除不需要的部分），将数据集矩阵进行切割
        #数据集在初始时刻是一个Arr = 60000*784的矩阵，针对当前要计算的feature，在训练集中切割下
        #Arr[:, feature]这么一条来，因为后续计算中数据集中只用到这个（没明白的跟着算一遍例5.2）
        #trainDataArr[:, feature]:在数据集中切割下这么一条
        #trainDataArr[:, feature].flat：将这么一条转换成竖着的列表
        #np.array(trainDataArr[:, feature].flat)：再转换成一条竖着的矩阵，大小为60000*1（只是初始是
        #这么大，运行过程中是依据当前数据集大小动态变的）
        trainDataArr_DevideByFeature = np.array(trainDataArr[:, feature].flat)
        #3.计算信息增益G(D|A)    G(D|A) = H(D) - H(D | A)
        G_D_A = H_D - calcH_D_A(trainDataArr_DevideByFeature, trainLabelArr)
        #不断更新最大的信息增益以及对应的feature
        if G_D_A > maxG_D_A:
            maxG_D_A = G_D_A
            maxFeature = feature
    return maxFeature, maxG_D_A

def createTree(*dataSet):
    '''
    递归创建决策树
    :param dataSet:(trainDataList， trainLabelList) <<-- 元祖形式
    :return:新的子节点或该叶子节点的值
    '''
    #设置Epsilon，“5.3.1 ID3算法”第4步提到需要将信息增益与阈值Epsilon比较，若小于则
    #直接处理后返回T
    #该值的大小在设置上并未考虑太多，观察到信息增益前期在运行中为0.3左右，所以设置了0.1
    Epsilon = 0.1
    #从参数中获取trainDataList和trainLabelList
    #之所以使用元祖作为参数，是由于后续递归调用时直数据集需要对某个特征进行切割，在函数递归
    #调用上直接将切割函数的返回值放入递归调用中，而函数的返回值形式是元祖的，等看到这个函数
    #的底部就会明白了，这样子的用处就是写程序的时候简洁一点，方便一点
    trainDataList = dataSet[0][0]
    trainLabelList = dataSet[0][1]
    #打印信息：开始一个子节点创建，打印当前特征向量数目及当前剩余样本数目
    print('start a node', len(trainDataList[0]), len(trainLabelList))

    #将标签放入一个字典中，当前样本有多少类，在字典中就会有多少项
    #也相当于去重，多次出现的标签就留一次。举个例子，假如处理结束后字典的长度为1，那说明所有的样本
    #都是同一个标签，那就可以直接返回该标签了，不需要再生成子节点了。
    classDict = {i for i in trainLabelList}
    #如果D中所有实例属于同一类Ck，则置T为单节点数，并将Ck作为该节点的类，返回T
    #即若所有样本的标签一致，也就不需要再分化，返回标记作为该节点的值，返回后这就是一个叶子节点
    if len(classDict) == 1:
        #因为所有样本都是一致的，在标签集中随便拿一个标签返回都行，这里用的第0个（因为你并不知道
        #当前标签集的长度是多少，但运行中所有标签只要有长度都会有第0位。
        return trainLabelList[0]

    #如果A为空集，则置T为单节点数，并将D中实例数最大的类Ck作为该节点的类，返回T
    #即如果已经没有特征可以用来再分化了，就返回占大多数的类别
    if len(trainDataList[0]) == 0:
        #返回当前标签集中占数目最大的标签
        return majorClass(trainLabelList)

    #否则，按式5.10计算A中个特征值的信息增益，选择信息增益最大的特征Ag
    Ag, EpsilonGet = calcBestFeature(trainDataList, trainLabelList)

    #如果Ag的信息增益比小于阈值Epsilon，则置T为单节点树，并将D中实例数最大的类Ck
    #作为该节点的类，返回T
    if EpsilonGet < Epsilon:
        return majorClass(trainLabelList)

    #否则，对Ag的每一可能值ai，依Ag=ai将D分割为若干非空子集Di，将Di中实例数最大的
    # 类作为标记，构建子节点，由节点及其子节点构成树T，返回T
    treeDict = {Ag:{}}
    #特征值为0时，进入0分支
    #getSubDataArr(trainDataList, trainLabelList, Ag, 0)：在当前数据集中切割当前feature，返回新的数据集和标签集
    treeDict[Ag][0] = createTree(getSubDataArr(trainDataList, trainLabelList, Ag, 0))
    treeDict[Ag][1] = createTree(getSubDataArr(trainDataList, trainLabelList, Ag, 1))

    return treeDict

 

REFERENCE

《统计学习方法》李航

ID3.py