统计学习方法（4）决策树

决策树是一种基本的分类与回归方法。
决策树的学习过程：

特征的选择
决策树的生成
决策树的修剪

决策树生成只考虑了通过提高信息增益（或信息增益比）对训练数据进行更好的拟合，而决策树剪枝通过优化损失函数还考虑了减少模型复杂度。

决策树生成学习局部的模型
决策树剪枝学习整体的模型

1、决策树的选择

特征选择在于选取对训练数据具有分类能力的特征，划分数据集的大原则是：将无序数据变得更加有序。在划分数据集前后信息发生的变化称为信息增益，获得信息增益最高的特征就是最好的选择，所以必须先学习如何计算信息增益，集合信息的度量方式称为香农熵，或者简称熵。

熵定义为信息的期望值，如果待分类的事物可能划分在多个类之中，则符号xi的信息定义为：
l(xi)=−log2p(xi)其中，p(xi)是选择该分类的概率。

为了计算熵，我们需要计算所有类别所有可能值所包含的信息期望值，通过下式得到：
H=−i=1∑np(xi)log2p(xi)
其中，n为分类数目，熵越大，随机变量的不确定性就越大。

通常特征选择的准则是信息增益或信息增益比。

信息增益

信息增益表示得知特征X的信息而使得类Y的信息不确定性减少的程度。

条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性，随机变量X给定的条件下随机变量Y的条件熵(conditional entropy) H(Y|X)，定义X给定条件下Y的条件概率分布的熵对X的数学期望：
H(Y∣X)=i=1∑npiH(Y∣X=xi)其中，pi=P(X=xi)

当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的分别为经验熵和经验条件熵，此时如果有0概率，令0log0=0

信息增益：信息增益是相对于特征而言的。所以，特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即：
g(D,A)=H(D)−H(D∣A)
一般地，熵H(D)与条件熵H(D|A)之差成为互信息(mutual information)。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

信息增益比

信息增益与特征取值的数量有关，如果特征取值较多，会使得划分后的信息熵较小（极端情况下，特征的每一个取值只有一个样本，信息熵为0），因此，为了避免特征取值数量带来的影响，使用信息增益比惩罚取值多的特征。

信息增益比：特征A对训练数据集D的信息增益比gR(D,A)定义为其信息增益g(D,A)与训练数据集D的经验熵之比：
gR(D,A)=H(D)g(D,A)

计算信息熵

from math import log

def creatDataSet():
    # 数据集
    data_sets = [[0, 0, 0, 0, 'no'],
              [0, 0, 0, 1, 'no'],
              [0, 1, 0, 1, 'yes'],
              [0, 1, 1, 0, 'yes'],
              [0, 0, 0, 0, 'no'],
              [1, 0, 0, 0, 'no'],
              [1, 0, 0, 1, 'no'],
              [1, 1, 1, 1, 'yes'],
              [1, 0, 1, 2, 'yes'],
              [1, 0, 1, 2, 'yes'],
              [2, 0, 1, 2, 'yes'],
              [2, 0, 1, 1, 'yes'],
              [2, 1, 0, 1, 'yes'],
              [2, 1, 0, 2, 'yes'],
              [2, 0, 0, 0, 'no']]

    #分类属性
    features = ['年龄', '有工作', '有自己的房子', '信贷情况']

    #返回数据集和分类属性
    return data_sets, features

def calc_shannon_ent(data_set):
    num_entries = len(data_set)
    labels_count = {}
    for feat_vec in data_set:
        current_label = feat_vec[-1]
        if current_label not in labels_count.keys():
            labels_count[current_label] = 0
        labels_count[current_label] += 1

    shannon_ent = 0.0
    for label in labels_count:
        prob = float(labels_count[label]) / num_entries
        shannon_ent -= prob * log(prob, 2)

    return shannon_ent


if __name__ == '__main__':
    data, feature = creatDataSet()
    ent = calc_shannon_ent(data)
    print(ent)

# 输出
"""
0.9709505944546686
"""

计算信息增益

from math import log

def creatDataSet():
    # 数据集
    data_sets = [[0, 0, 0, 0, 'no'],
              [0, 0, 0, 1, 'no'],
              [0, 1, 0, 1, 'yes'],
              [0, 1, 1, 0, 'yes'],
              [0, 0, 0, 0, 'no'],
              [1, 0, 0, 0, 'no'],
              [1, 0, 0, 1, 'no'],
              [1, 1, 1, 1, 'yes'],
              [1, 0, 1, 2, 'yes'],
              [1, 0, 1, 2, 'yes'],
              [2, 0, 1, 2, 'yes'],
              [2, 0, 1, 1, 'yes'],
              [2, 1, 0, 1, 'yes'],
              [2, 1, 0, 2, 'yes'],
              [2, 0, 0, 0, 'no']]

    #分类属性
    features = ['年龄', '有工作', '有自己的房子', '信贷情况']

    #返回数据集和分类属性
    return data_sets, features

def calc_shannon_ent(data_set):
    num_entries = len(data_set)
    labels_count = {}
    for feat_vec in data_set:
        current_label = feat_vec[-1]
        if current_label not in labels_count.keys():
            labels_count[current_label] = 0
        labels_count[current_label] += 1

    shannon_ent = 0.0
    for label in labels_count:
        prob = float(labels_count[label]) / num_entries
        shannon_ent -= prob * log(prob, 2)

    return shannon_ent

def select_best_feature(data_set):
    num_features = len(data_set[0]) - 1
    num_entries = len(data_set)
    base_ent = calc_shannon_ent(data_set)

    best_feature_ent = 0.0
    best_feature = -1
    for feature in range(num_features):
        feat_list = [example[0] for example in data_set]
        feat_set = set(feat_list)
        new_ent = 0.0
        for value in feat_set:
            sub_data_set = split_data_set(data_set, feature, value)
            prob = len(sub_data_set) / num_entries
            new_ent += prob * calc_shannon_ent(sub_data_set)
        info_gain = base_ent - new_ent
        print(feature, "特征的信息增益: ", info_gain)

        if info_gain > best_feature_ent:
            best_feature_ent = info_gain
            best_feature = feature

    return best_feature, best_feature_ent


def split_data_set(data_set, axis, value):
    sub_data_set = []
    for example in data_set:
        if example[axis] == value:
            sub_data_set.append(example)
    return sub_data_set


if __name__ == '__main__':
    data, feature = creatDataSet()
    select_feature, max_ent = select_best_feature(data)
    print("最好的特征、信息增益：", select_feature, max_ent)

# 输出：
"""
0 特征的信息增益:  0.08300749985576883
1 特征的信息增益:  0.32365019815155627
2 特征的信息增益:  0.4199730940219749
3 特征的信息增益:  0.36298956253708536
最好的特征、信息增益： 2 0.4199730940219749
"""

2、决策树的生成

决策树的生成就是递归地构建二叉决策树的过程，决策树的每一个节点都是通过最优特征的选择来进行划分，决策树学习的生成算法常用的是ID3、C4.5、CART，这里先介绍ID3和C4.5：

ID3

ID3算法的核心是在决策树各个结点上对应信息增益准则选择特征，递归地构建决策树。

具体方法是：

（1）从根结点(root node)开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征。

（2）由该特征的不同取值建立子节点，再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止；

（3）最后得到一个决策树。

ID3相当于用极大似然法进行概率模型的选择。
统计学习方法（4）决策树-LMLPHP

C4.5

与ID3算法相似，但是做了改进，将信息增益比作为选择特征的标准，而且可以处理连续值特征（需要扫描排序，然后进行划分，性能会下降）。
统计学习方法（4）决策树-LMLPHP

3、决策树的剪枝

决策树生成算法递归的产生决策树，直到不能继续下去为止，这样产生的树往往对训练数据的分类很准确，但对未知测试数据的分类缺没有那么精确，即会出现过拟合现象。过拟合产生的原因在于在学习时过多的考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树，解决方法是考虑决策树的复杂度，对已经生成的树进行简化。

剪枝（pruning）：从已经生成的树上裁掉一些子树或叶节点，并将其根节点或父节点作为新的叶子节点，从而简化分类树模型。

实现方式：极小化决策树整体的损失函数或代价函数来实现，或者通过验证集比较剪枝前后的精度来决定是否剪枝。

决策树算法很容易过拟合（overfitting），剪枝算法就是用来防止决策树过拟合，提高泛化性能的方法。

剪枝分为预剪枝与后剪枝。

预剪枝是指在决策树的生成过程中，对每个节点在划分前先进行评估，若当前的划分不能带来泛化性能的提升，则停止划分，并将当前节点标记为叶节点，但是预剪枝基于“贪心”算法，只考虑当前情况，但是当前划分没有性能提升，可能后续的划分会带来很大的性能提升。所以，预剪枝容易出现欠拟合。

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

4、CART算法

CART同样由特征选择、树的生成和剪枝组成，既可以用于分类也可以用于回归。CART算法不像之前的算法直接对一个特征进行完全划分，而是递归地二分每个特征，在后续划分过程中，该特征仍旧可以参与划分，所以不至于对特征的划分过于快速。
CART的生成就是递归地构建二叉决策树的过程。
特征选择：

对回归树用平方误差最小化准则
对分类树用基尼指数（Gini index）最小化准则

4.1 回归树的生成

回归树用平方误差最小化准则选择最优切分。

给定训练数据集：
D=(x1,y1),(x2,y2),...,(xn,yn)
一个回归树对应着输入空间（即特征空间）的一个划分以及在划分的单元上的输出值。

输入空间的划分采用启发式的方法，选择第j个变量x(j)和它取的值s作为切分变量和切分点，并定义两个区域：
R1(j,s)=x∣x(j)≤s和R1(j,s)=x∣x(j)>s

寻找最优切分的准则是平方误差最小化准则，即求解：
j,smin[c1minx1∈R1(j,s)∑(yi−c1)2+c2minx1∈R2(j,s)∑(yi−c2)2]
其中：
c^1=ave(yi∣xi∈R1(j,s))和c^2=ave(yi∣xi∈R2(j,s))
利用平方误差最小化准则遍历所有变量，找到最优的切分变量j，构成一个对(j,s)，依次将输入空间划分为两个区域，直到满足停止条件，这样就生成一个最小二乘回归树。
统计学习方法（4）决策树-LMLPHP

4.2 分类树的生成

分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点。

分类问题中，假设有K个类，样本点属于第k类的概率为pk，则概率分布的基尼指数为：
Gini(p)=k=1∑Kpk(1−pk)=1−k=1∑Kpk2

对于给定的样本集合D，其基尼指数为：
Gini(D)=1−k=1∑K(∣D∣∣Ck∣)2其中，Ck是D中属于第k类的样本子集，K是类的个数。

如果样本集合D根据特征A是否去某一可能值a被分割成D1和D2两部分，则在特征A的条件下，集合D的基尼指数定义为：
Gini(D,A)=∣D∣∣D1∣Gini(D1)+∣D∣∣D2∣Gini(D2)
基尼系数Gini(D)表示集合D的不确定性，基尼系数Gini(D,A)表示集合经A=a分割后集合D的不确定性。与熵类似，基尼指数越大，不确定性越大。因此，应该选择划分之后不确定性小的划分，即基尼指数小的划分。

5、ID3、C4.5、CART的区别

这三个是非常著名的决策树算法。简单粗暴来说：

ID3 使用信息增益作为选择特征的准则；
C4.5 使用信息增益比作为选择特征的准则；
CART 使用 Gini 指数作为选择特征的准则。

（1）ID3

熵表示的是数据中包含的信息量大小。熵越小，数据的纯度越高，也就是说数据越趋于一致，这是我们希望的划分之后每个子节点的样子。

信息增益 = 划分前熵 - 划分后熵。信息增益越大，则意味着使用属性 a 来进行划分所获得的 “纯度提升” 越大。也就是说，用属性 a 来划分训练集，得到的结果中纯度比较高。

ID3 仅仅适用于二分类问题，ID3 仅仅能够处理离散属性。

（2）C4.5

C4.5 克服了 ID3 仅仅能够处理离散属性的问题，以及信息增益偏向选择取值较多特征的问题，使用信息增益比来选择特征。信息增益比 = 信息增益 / 划分前熵，选择信息增益比最大的作为最优特征。

C4.5 处理连续特征是先将特征取值排序，以连续两个值中间值作为划分标准。尝试每一种划分，并计算修正后的信息增益，选择信息增益最大的分裂点作为该属性的分裂点。

（3）CART

CART 与 ID3，C4.5 不同之处在于 CART 生成的树必须是二叉树。也就是说，无论是回归还是分类问题，无论特征是离散的还是连续的，无论属性取值有多个还是两个，内部节点只能根据属性值进行二分。

CART 的全称是分类与回归树。从这个名字中就应该知道，CART 既可以用于分类问题，也可以用于回归问题。

回归树中，使用平方误差最小化准则来选择特征并进行划分。每一个叶子节点给出的预测值，是划分到该叶子节点的所有样本目标值的均值，这样只是在给定划分的情况下最小化平方误差。

要确定最优化分，还需要遍历所有属性，以及其所有的取值来分别尝试划分并计算在此种划分情况下的最小平方误差，选取最小的作为此次划分的依据。由于回归树生成使用平方误差最小化准则，所以又叫做最小二乘回归树。

分类树中，使用Gini 指数最小化准则来选择特征并进行划分；

Gini 指数表示集合的不确定性，或者是不纯度。基尼指数越大，集合不确定性越高，不纯度也越大。这一点和熵类似。另一种理解基尼指数的思路是，基尼指数是为了最小化误分类的概率。

（4）信息增益 vs 信息增益比

之所以引入了信息增益比，是由于信息增益的一个缺点。那就是：信息增益总是偏向于选择取值较多的属性。信息增益比在此基础上增加了一个罚项，解决了这个问题。

（5）Gini 指数 vs 熵

既然这两个都可以表示数据的不确定性，不纯度。那么这两个有什么区别呢？

Gini 指数的计算不需要对数运算，更加高效；
Gini 指数更偏向于连续属性，熵更偏向于离散属性。

小蜜蜂