笔记：机器学习之决策树

目录

 

决策树概述

决策树的构建

特征选择

生成决策树

剪枝

特征选择

生成决策树

剪枝

用决策树对鸢尾花的预测

---

决策树概述

决策树（decision tree）是功能强大的且非常好用的的分类和预测方法，它是一种有监督的学习算法。以树状图为基础，故称为决策树。这里以分类为主题。对于离散值，决策树中的每一个非叶节点都是数据的一个特征，叶节点是数据的分类，决策树从根节点沿着不同的特征分支最终到达叶节点。

决策树的构建

决策树的构建主要分为3大步骤

• 特征选择

• 生成决策树

• 剪枝

特征选择

特征选择就是选取有较强分类能力的特征，其评判标准主要有信息增益、信息增益率和基尼系数来判定。

熵

熵是度量数据纯度最常用的一种指标。假设，样本集合D中的第k类样本的概率是,则D的信息熵为

                                                                  

值越小则数据纯度越高

条件熵

 

 

                                                                             E(D∣A)

表示在给定特征A的条件下，D的条件熵

 

                                                                           

其中

                                                          

信息增益

信息增益表示：已知集合D的经验熵E(D)，给定特征A下D的经验条件熵为E(D∣A)的差

                                                             

例如，以西瓜数据为例

                                                                 西瓜数据表（表来自周志华老师的机器学习）

     

集合D中有两类样本，既好瓜和坏瓜。故|y|=2,。其中好瓜有8个样本，坏瓜有9个样本，因此，信息熵为

然后计算特征集合{色泽，根蒂，敲声，纹理....}，以特征“色泽”为例对集合D进行划分，则有3个子集合分别是“色泽=青绿”，“色泽=乌黑”，“色泽=浅白”，样本数量分别为6、6、5,好瓜样本为3、4、1.因此，以“色泽”划分得到的3个节点的信息熵分别为

因此，特征“色泽”的信息增益为

同理可计算出其他特征的信息增益

由此可知，特征是纹理的信息增益最大，故选纹理作为决策树的根节点，再以同样的方法选取其余的特征作为节点，最终得出完整的一课决策树

               

增益率

值得注意的是，以信息增益作为训练集的特征选取方案，存在偏向于选取值较多的特征问题。极端情况下，特征以特征A划分的节点，每一个节点有且仅有一个样本时，其条件熵等于0（log1=0），此时信息增益最大，但是A并不是最佳的选择。例如，以西瓜数据表为例，“编号”将产生17个节点分支，并且每个分支只包括一个样本，这时其数据纯度最高等于1，信息增益达到最大。但是显然，以“编号”’划分对决策树的泛化能力无意义。为减少这种不利的影响。C4.5算法采用增益率来选择最优划分特征。增益率定义为

基尼系数

CART算法使用基尼系数来选取特征划分，基尼系数与熵一样，都是描述数据纯度的指标，基尼系数越大，则不确定性越大，数据纯度越低。

 

                                                               

特征a的基尼系数

                                                              

生成决策树

输入

      训练数据集D

      特征集A

      特征信息增益阈值

输出：决策树

算法步骤

      若D中所有实例均属于同一类，则T为单节点树，并将该类作为该节点的类标志，返回T。

      若特征集A为空，则T为单节点树，将D中实例数最大的类作为该节点的类标志，返回T

      否则计算，选择信心增益最大的特征

      判断的信心增益

            若 < ​​​​，则置T为单节点树，将D中实例数最大的类作为该节点的类标志，返回T

            若 >= ，则对​​​​特征的每个可能取值，根据=将D划分为若干个非空子集，将中实例数最大                          的类作为标志，构建子节点，由子节点及其子节点构成树T，返回T

      对第i个子节点，以为训练集，以为特征集，递归地调用前面的步骤，得到子树，返回。

剪枝

剪枝是处理决策树“过拟合”的有效手段。剪枝包括预剪枝和后剪枝。预剪枝是指在生成决策树的过程中，对每个节点划分之前预先做判断，若当前节点划分不能给提高决策树的泛化性能，则当前节点不继续划分。后剪枝是指在训练集中生成一棵完整的决策树再对非叶子结点自下向上进行判断，若将当前节点对应的子树以当前节点作为叶子结点能提升决策树的泛化性能，则以该节点变为叶子结点。对于决策树的泛化性能的评估，一般来说，将数据分成训练集和测试集，以测试集对决策树泛化性能的评估。

            

预剪枝

根据信息增益，对于表4.2，选择“脐部”作为根节点，测试集中编号为{4，5，8}的是好瓜，其余为坏瓜，则准确度为3/7*100%=42.9%.

特征“脐部”划分之后，分支分别为“凹陷”、“稍凹”、“平坦”分别包含编号为{1,2,3,14}、{6,7,15,17}、{10,16}，而其对应的节点分别为“好瓜”、“好瓜”、“坏瓜”。这时，测试集中编号为{4,5,8,11,12}正确分类出来，此时的准确度为5/7*100%=71.4%>42.9%.因此，特征“脐部”应该划分。对剩下的特征用同样的方法进行处理，最终得到的结果是

                     

从中可以看出，预剪枝的树少了很多分支，这可以减少决策树的“过拟合”的风险，还可以减少训练和测试的时间开销。但是同时，预剪枝导致有很多信息没有用到，虽然在当前节点上划分不会对决策树的泛化性能有所提高，但是在其基础上的后续划分则有可能大幅度提高决策树的泛化性能。

后剪枝

 

看节点6，若讲其分支剪掉，即以其自身作为叶节点，则替换后的叶节点包括编号为{7,15}的训练样本，将其类别归为“好瓜”，此时准确度为57.1%比未剪枝的准确度42.9%要高，因此，后剪枝策略决定剪掉该节点的分支。对于其他节点，以同样的方法进行比较，最终得出

 

可知，后剪枝得到的决策树要比预剪枝得到的树的分支要多，其泛化性能一般会优于预剪枝，但是后剪枝是在生成一棵完整的决策树之后再进行评估判断的，因此，其时间花销要比预剪枝要大。

用决策树对鸢尾花的预测

from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split
from sklearn import datasets
from sklearn.tree import export_graphviz
import pydot

def load_data():
    iris = datasets.load_iris()
    X_train = iris.data
    y_train = iris.target
    return train_test_split(X_train,y_train,test_size=0.25,random_state=0,stratify=y_train) #采用分成采样

def test_DecisionTreeClassifier(*data):
    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)))
    print('Testing score:%f' %(clf.score(X_test,y_test)))
    export_graphviz(clf,out_file='tree.dot') #将图转换为点文件
    (graph,) = pydot.graph_from_dot_file('tree.dot')#创建一个图
    graph.write_png('tree.png')#将图转换为图片

X_train, X_test, y_train, y_test=load_data()
test_DecisionTreeClassifier(X_train, X_test, y_train, y_test)

输出

Training score:1.000000

Testing score:0.973684

 

注：图片主要来源于周志华老师的机器学习

参考文献：[1]周志华.机器学习[M].

                  [2]华校专,王正林.python大战机器学习[M].电子工业出版社