[机器学习] 决策树

决策树概述

当数据特征很多，并且特征之间关系错综复杂的时候，利用线性回归等全局模型（拟合所有样本点）会比较困难。并且，现实世界中有很多非线性的问题，无法使用线性回归这样的线性模型进行拟合。

决策树的思想就是：将数据集切分为多个易于建模的数据，然后使用树模型或者回归法进行拟合。

它采用的是自顶向下的递归方法，以信息熵为度量构造一棵熵值下降最快的树，到叶子节点处的熵值为零，此时每个叶节点中的实例都属于同一类。

以下解释来自维基百科：

机器学习中，

决策树

是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表某个可能的属性值，而每个叶节点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。数据挖掘中决策树是一种经常要用到的技术，可以用于分析数据，同样也可以用来作预测。

决策树的学习算法：

ID3 （Iterative Dichotomiser）：使用

信息增益

作为标准来构建模型。信息增益表示得知特征A的信息而使得类X的信息的不确定性减少的程度。ID3 的做法是每次选取当前最佳的特征来分割数据，并按照该特征的所有可能取值来切分。计算特征A的信息增益 : g(D,A)=H(D) – H(D|A)。
C4.5 ：使用

信息增益率

作为标准构建模型。

$g_r(D,A) = g(D,A) / H(A)$
。
CART （ Classification and regression tree ）：使用

基尼系数

来构建模型。CART 可以用来切分离散值和连续值。

$Gini(p) = \sum_{k=1}^K p_k(1-p_k) = 1-\sum_{k=1}^K p_k^2 = 1- \sum_{k=1}^K \left(\frac{|C_k|}{|D|}\right)$
。

Scikit-learn 应用

def test_DecisionTreeClassifier(*data):
    '''
    测试 DecisionTreeClassifier 的用法

    :param data: 可变参数。它是一个元组，这里要求其元素依次为：训练样本集、测试样本集、训练样本的标记、测试样本的标记
    :return:  None
    '''
    X_train,X_test,y_train,y_test=data
    clf = DecisionTreeClassifier()
    clf.fit(X_train, y_train)

    print("Training score:%f"%(clf.score(X_train,y_train)))


def test_DecisionTreeClassifier_criterion(*data):
    '''
    测试 DecisionTreeClassifier 的预测性能随 criterion 参数的影响

    :param data:  可变参数。它是一个元组，这里要求其元素依次为：训练样本集、测试样本集、训练样本的标记、测试样本的标记
    :return:  None
    '''
    X_train,X_test,y_train,y_test=data
    criterions=['gini','entropy']
    for criterion in criterions:
        clf = DecisionTreeClassifier(criterion=criterion)
        clf.fit(X_train, y_train)
        print("criterion:%s"%criterion)
        print("Training score:%f"%(clf.score(X_train,y_train)))
        print("Testing score:%f"%(clf.score(X_test,y_test)))


def test_DecisionTreeClassifier_splitter(*data):
    '''
    测试 DecisionTreeClassifier 的预测性能随划分类型的影响

    :param data: 可变参数。它是一个元组，这里要求其元素依次为：训练样本集、测试样本集、训练样本的标记、测试样本的标记
    :return:  None
    '''
    X_train,X_test,y_train,y_test=data
    splitters=['best','random']
    for splitter in splitters:
        clf = DecisionTreeClassifier(splitter=splitter)
        clf.fit(X_train, y_train)
        print("splitter:%s"%splitter)
        print("Training score:%f"%(clf.score(X_train,y_train)))
        print("Testing score:%f"%(clf.score(X_test,y_test)))
def test_DecisionTreeClassifier_depth(*data,maxdepth):
    '''
    测试 DecisionTreeClassifier 的预测性能随 max_depth 参数的影响

    :param data:  可变参数。它是一个元组，这里要求其元素依次为：训练样本集、测试样本集、训练样本的标记、测试样本的标记
    :param maxdepth: 一个整数，用于 DecisionTreeClassifier 的 max_depth 参数
    :return:  None
    '''
    X_train,X_test,y_train,y_test=data
    depths=np.arange(1,maxdepth)
    training_scores=[]
    testing_scores=[]
    for depth in depths:
        clf = DecisionTreeClassifier(max_depth=depth)
        clf.fit(X_train, y_train)
        training_scores.append(clf.score(X_train,y_train))
        testing_scores.append(clf.score(X_test,y_test))

决策树原理

基础知识

基本记号

设训练数据集为D ，

$\left|D\right|$
表示样本个数。
设有K个类

$C_k$
, k = 1,2,…,K，

$\left|C_k\right|$
为属于类

$C_k$
的样本个数，有:

$\sum\left|C_k\right| = \left|D\right|$
设特征A有n个不同的取值

$\{a_1, a_2,...,a_n\}$
，根据特征A的取值将D划分为n个子集

$D_1, D_2, ... , D_n$
，

$\left|D_i\right|$
为

$D_i$
的样本个数，有：

$\sum_i \left|D_i\right| = \left|D\right|$
记子集

$D_i$
中属于类

$C_k$
的样本的集合为

$D_{ik}$
，

$\left|D_{ik}\right|$
为

$D_{ik}$
的样本个数。

信息熵

物理意义：描述物质的混乱程度。
数学定义：

$H\left[x\right] = - \sum_x p\left(x\right)log_2 p\left(x\right)$
。
解释：我们用熵来评价整个随机变量x平均的信息量，而平均最好的量度就是随机变量的期望。（负号用以保证为正数；log 的底一般取2，也可以取其他，没有影响）
计算数据集D的经验熵

$H\left(x\right) = - \sum_{k=1}^K \frac{|C_k|}{|D|} log \frac{|C_k|}{|D|}$

条件熵

条件熵：(X,Y)发生所包含的熵，减去X单独发生包含的熵:在X发生的前提下，Y发生“新”带来的熵。
$H(Y|X) = H(X,Y) - H(X) = - \sum_{x,y}p(x,y) log p(y|x) = \sum_x p(x)H(Y|X=x)$
经验条件熵

$H(D|A) = -\sum_{i=1}^n \frac{|D_i|}{|D|}\sum_{k=1}^K \frac{|D_{ik}|}{|D_i|}log\frac{|D_{ik}|}{|D_i|}$

信息增益

物理意义：用于衡量某个属性降低样本集合的混乱程度。
数学定义：计算特征A的信息增益

$g\left(D,A\right) = H\left(D\right) - H\left(D|A\right)$
解释：特征A信息增益越大，其降低样本集合混乱程度越大，所以选择信息增益最大的特征作为当前的分裂特征。

信息增益率

物理意义：将纯度作为分母考虑进来，计算混乱降低的程度。
数学定义：

$g_r(D,A) = g(D,A) / H(A)$

Gini 指数

物理意义：表示一个随机选中的样本被分错的概率。
数学定义：

$Gini(p) = \sum_{k=1}^K p_k(1-p_k) = 1-\sum_{k=1}^K p_k^2 = 1- \sum_{k=1}^K \left(\frac{|C_k|}{|D|}\right)$

三种决策树算法

生成树的关键在于节点属性选择及分裂值的标准，剪枝的关键在于衡量全局损失的代价函数。

ID3

ID3 使用

信息增益

作为标准构建树模型，算法如下：

输入：X-数据；y-标签； 

输出：决策树 

过程： 

1. 属性集Fea = {F1, F2, F3, ... Fn}。 

    计算属性集内所有属性对应的信息增益G（S, Fi）。 

2. 选择信息增益最大值对应的属性，作为当前分裂节点属性Fopt。 

    按照Fopt属性的类别，划分子集（分叉）。 

    剔除已经选择的属性，Fea = Fea - Fopt。 

    重复步骤1和2，直到属性集Fea为空。 

3. 剪枝

ID3 优缺点：

便于理解，形象直观。
可以处理费数值型数据。
取值多的属性，更容易使数据更纯，其信息增益更大。所以训练得到的是一棵庞大且深度浅的树，这不合理。
由第2步中，划分子集看出来，ID3不能处理连续值。
无法处理大规模数据集。

C4.5

使用

信息增益率

作为标准划分，算法：

输入：X-数据；y-标签； 

输出：决策树 

过程： 

1. 离散化处理，将连续型的属性变量进行离散化处理，形成训练集 

    1.1 按照连续变量从大到小的顺序排序 

    1.2 假设有N个属性值，则计算两两之间的中间值，N-1个候选属性值分割点。 

    1.3 用信息增益率选择最佳属性。 

    缺失值处理，处理空缺的属性值策略。 

    1.4 策略一：丢弃该样本 

    1.5 策略二：赋值为该属性对应的均值 

    1.6 策略三：赋予其可能值的概率。（计算信息增益如何使用？） 

2. 属性集Fea = {F1, F2, F3, … Fn}。 

    计算属性集内所有属性的信息增益率GainRatio(S, Fi)。 

3. 选择信息增益率最大值对应的属性，作为当前分裂节点属性Fopt。 

    按照Fopt属性的类别，划分子集（分叉）。 

    剔除已选的属性，Fea = Fea – Fopt。 

    重复步骤2和3，知道属性集Fea为空。 

4. 剪枝。

C4.5 优缺点：

继承了ID3的优点。
用信息增益率选择属性，克服了信息增益选择属性时，偏向于多分类属性的问题。
能够处理连续值，引入了离散化处理。
能够处理空缺值，引入了空缺值处理。
C5.0是C4.5的改进算法，引入Boosting方法，提高效率，节省内存。
构造树的过程中，多次顺序扫描数据集并且排序，效率较低。
无法处理大规模数据。

CART

选用

基尼指数

作为标准，算法如下：

1. 连续值的处理： 

    1.1 对取值进行升序排序。 

    1.2 取相邻两点的中点，作为可能的分裂点。 

    1.3 #计算GiniGain，选择最佳属性分裂点。 

    （修正GiniGain，则减去log2(N-1)/|D|，N是连续特征取值个数，D是训练数据数量） 

    缺失值的处理 

2. 属性集Fea = {F1, F2, F3, … Fn}。 

    2.1 回归树-利用方差选择分支特征。 

    （计算组内方差最小，组间方差最大，使得左右分支的差异化最大。） 

    方差计算方法：数据集均值std，计算每个数据点与std的方差，然后平方求和。 

    组间方差：两组的均值，求方差。 

    2.2 分类树-利用GiniGain选择分支特征。 

    将所有二分情况下可能存在的GiniGain计算一遍，选择最小值对应的属性及分裂值，作为当前分裂属性Fopt和分裂点。 

    如果：左右分支上的Fopt的取值>=2，则Fopt保存， 

    否则：Fea = Fea – Fopt 

    重复2.1和2.2步骤 

    （终止条件，计算X2，X2很小时表示分类条件和类别是独立的，此时节点停止分裂。） 

3. 剪枝。

CART 的优缺点：

可以处理连续值、非数值数据
分类、回归同时实现。
二叉树结构简洁，避免了多分叉树的数据碎片偏多现象。
只能产生两个子节点；类别过多时，错误可能会增加。
无法处理大规模数据。
是一种大样本的统计分析方法，样本量较小时，模型不稳定。

决策树的评价

假定样本的总类别为 K 个。
对于决策树的某个叶节点，假设该叶节点含有的样本数目为 n ，其中第 k 类的样本点数目为

$n_k, k=1,2,3,...,K$
。
- 若某类样本
  
  $n_j = n$
  ，而
  
  $n_1,...,n_{j-1},n_{j+1},...,n_K=0$
  ，称该节点为纯节点。
- 若各类样本
  
  $n_1=n_2=...=n_K=n/K$
  ，称该样本均纯节点。
纯节点的熵

$H_p = 0$
，熵最小。均节点的熵

$H_p = ln K$
，熵最大。
对所有叶节点的熵求和，该值越小说明对样本的分类越精确。
评价函数：

$C (T) = \sum t \in l e a f N t \cdot H (t)$
$C(T) = \sum_{t \in leaf} N_t \cdot H(t)$
由于该评价函数越小越好，所有，称之为 “

损失函数

”。

树剪枝

树节点过多，意味着模型对数据 “ 过拟合 ”，需要降低其复杂度来避免过拟合，称为

剪枝

。生成过程中提前终止条件，称为

预剪枝

。

后剪枝

则需要用到训练集和测试集。

预剪枝 Pre-Pruning

Pre-pruning

that stop growing the tree earlier, before it perfectly classifies the training set.

通过设置停止条件，提前结束树的增长。以下代码来自 < Machine Learning in Actionby> ( Peter Harrington）:

def chooseBestSplit(dataSet, leafType=regLeaf, errType=regErr, ops=(1,4)):
    tolS = ops[0]; tolN = ops[1]
    #if all the target variables are the same value: quit and return value
    if len(set(dataSet[:,-1].T.tolist()[0])) == 1: #exit cond 1
        return None, leafType(dataSet)
    m,n = shape(dataSet)
    #the choice of the best feature is driven by Reduction in RSS error from mean
    S = errType(dataSet)
    bestS = inf; bestIndex = 0; bestValue = 0
    for featIndex in range(n-1):
        for splitVal in set(dataSet[:,featIndex]):
            mat0, mat1 = binSplitDataSet(dataSet, featIndex, splitVal)
            if (shape(mat0)[0] < tolN) or (shape(mat1)[0] < tolN): continue
            newS = errType(mat0) + errType(mat1)
            if newS < bestS: 
                bestIndex = featIndex
                bestValue = splitVal
                bestS = newS
    #if the decrease (S-bestS) is less than a threshold don't do the split
    if (S - bestS) < tolS:  #exit cond 2
        return None, leafType(dataSet)
    mat0, mat1 = binSplitDataSet(dataSet, bestIndex, bestValue)
    if (shape(mat0)[0] < tolN) or (shape(mat1)[0] < tolN):  #exit cond 3
        return None, leafType(dataSet)
    return bestIndex,bestValue#returns the best feature to split on
                              #and the value used for that split

该函数的伪代码大致是：

对于每个特征 ：
    对每个特征值：
        将数据集合切分为两份
        计算切分的误差
        若当前误差小于当前最小误差，则设定当前切分为最佳
返回最佳切分的特征和阈值

代码中，有三种条件会使得函数不再进行切分。

函数统计不同剩余特征的数目，如果为1就不在进行切分：
if len(set(dataSet[:,-1].T.tolist()[0])) == 1: #exit cond 1
上一步之后，函数计算了当前数据集的规模大小和误差，如果切分后数据集效果提升不明显，则不再切分直接创建叶节点：
if (S - bestS) < tolS: #exit cond 2
检查两个切分后数据子集的大小，如果某个子集大小小于超参数 tolN，也不再进行切分：
if (shape(mat0)[0] < tolN) or (shape(mat1)[0] < tolN): #exit cond 3

预剪枝存在的问题：

树的构建对参数 tolS 和 tolN 非常敏感，若使用其他设置可能会得到效果很差的树
或许可以通过不断修正停止条件的方式来训练，但很多情况下我们并不知道需要什么结果，机器学习应该可以给出总体概貌。

后剪枝Post-Pruning

Post-pruning

that allows the tree to perfectly classify the training set, and then post prune the tree.

剪枝的总体思路

由完全树

$T_0$
开始，剪枝部分节点得到

$T_1$
，再次剪枝部分节点得到

$T_2$
…… 直到仅剩根节点的树

$T_k$
；
在验证数据集上对这 k 个树分别评价，选择损失函数最小的树

$T_\alpha$
。

剪枝系数的确定

损失函数：

$C (T) = \sum t \in l e a f N t \cdot H (t)$
$C(T) = \sum_{t \in leaf} N_t \cdot H(t)$
叶节点越多，决策树越复杂，损失越大，修正为：

C

α

(

T

)

=

C

(

T

)

+

α

⋅

∣

∣

T

l

e

a

f

∣

∣

$C_\alpha(T) = C(T) + \alpha \cdot \left| T_{leaf}\right|$
- 当
  
  $\alpha = 0$
  时，未剪枝的决策树损失最小
- 当
  
  $\alpha = +\infty$
  时，单根节点的决策树损失最小
假定当前对

以 r 为根的子树

剪枝，剪枝后只保留 r 本身而删除所有的叶子节点
考察以 r 为根的子树：
- 剪枝后的损失函数：
  
  $C_\alpha \left(r\right) = C(r) + \alpha$
- 剪枝前的损失函数：
  
  $C_\alpha \left(R\right) = C(R) + \alpha \cdot \left|R_{leaf}\right|$
- 令
  
  $C_\alpha \left(r\right) = C_\alpha \left(R\right)$
  ，得到：
  
  $α = C ( r ) - C ( R ) < R l e a f > - 1$
  $\alpha = \frac{C(r)-C(R)}{<R_{leaf}> - 1}$
- $\alpha$
  称为节点 r 的剪枝系数

剪枝算法

对于给定的决策树

$T_0$
：

计算所有内部节点的

剪枝系数
查找

最小剪枝系数

的节点，剪枝得到决策树

T_k
重复以上步骤，直到决策树

$T_k$
只有1 个节点
得到决策树序列

$T_0 T_1 T_2 ... T_k$
使用

验证样本集

数据选择最优子树，评价标准可以使用：

$C(T) = \sum_{t \in leaf} N_t \cdot H(t)$

剪枝代码示例

以下代码来自 < Machine Learning in Actionby> ( Peter Harrington）：

def prune(tree, testData):
    if shape(testData)[0] == 0: return getMean(tree) #if we have no test data collapse the tree
    if (isTree(tree['right']) or isTree(tree['left'])):#if the branches are not trees try to prune them
        lSet, rSet = binSplitDataSet(testData, tree['spInd'], tree['spVal'])
    if isTree(tree['left']): tree['left'] = prune(tree['left'], lSet)
    if isTree(tree['right']): tree['right'] =  prune(tree['right'], rSet)
    #if they are now both leafs, see if we can merge them
    if not isTree(tree['left']) and not isTree(tree['right']):
        lSet, rSet = binSplitDataSet(testData, tree['spInd'], tree['spVal'])
        errorNoMerge = sum(power(lSet[:,-1] - tree['left'],2)) +\
            sum(power(rSet[:,-1] - tree['right'],2))
        treeMean = (tree['left']+tree['right'])/2.0
        errorMerge = sum(power(testData[:,-1] - treeMean,2))
        if errorMerge < errorNoMerge: 
            print "merging"
            return treeMean
        else: return tree
    else: return tree

函数的伪代码大致如下：

基于当前的树切分测试数据集：
    如果存在任一子集是一棵树，则在该子集递归剪枝过程
    计算将当前两个叶节点合并后的误差
    计算不合并叶子节点的误差
    如果误差降低，则将叶节点合并

原文链接：https://blog.csdn.net/Lookka/article/details/77232529