---

决策树

案例:

假如现在我想买一个西瓜，需要判断好瓜，还是坏瓜。西瓜拿过来后先看纹理，纹理如果不清晰直接pass，纹理清晰的再看根蒂，触感等其他特征，如果我此时构建了一颗决策树，没问题，马上就可以知道是好瓜，还是坏瓜，如下图所示：

原理：

决策树（decision tree）是一个树结构（可以是二叉树或非二叉树）。其每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。
总结来说，决策树模型核心是下面几部分：

• 结点和有向边组成
• 结点有内部结点和叶结点俩种类型
• 内部结点表示一个特征，叶节点表示一个类

如果不考虑效率等，那么样本所有特征的判断级联起来终会将某一个样本分到一个类终止块上。实际上，样本所有特征中有一些特征在分类时起到决定性作用，决策树的构造过程就是找到这些具有决定性作用的特征，根据其决定性程度来构造一个倒立的树–决定性作用最大的那个特征作为根节点，然后递归找到各分支下子数据集中次大的决定性特征，直至子数据集中所有数据都属于同一类。所以，构造决策树的过程本质上就是根据数据特征将数据集分类的递归过程，我们需要解决的第一个问题就是，当前数据集上哪个特征在划分数据分类时起决定性作用。这里有一个问题，那就是该如何选择一个特征作为根节点？下一次决策又该选取哪个特征作为节点？决策树算法使用了一种称作信息增益的方法来衡量一个特征和特征之间的重要性，信息增益越大表明这个特征越重要，那么就优先对这个特征进行决策。在一种理想的情况下，我们构建的决策树上的每一个叶子节点都是一个纯粹的分类，也就是通过这条路径进入到这个叶子节点的所有数据都是同一种类别，但是这需要反复回溯修改非叶子节点的判定条件，而且要划分更多的分支来进行处理，所以实际上决策树实现的时候都采用了贪心算法，来寻找一个最近的最优解，而不是全局的最优解。
一棵决策树的生成过程主要分为以下3个部分:

• 特征选择：特征选择是指从训练数据中众多的特征中选择一个特征作为当前节点的分裂标准，如何选择特征有着很多不同量化评估标准标准，从而衍生出不同的决策树算法。
• 决策树生成： 根据选择的特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止决策树停止生长。树结构来说，递归结构是最容易理解的方式。
• 剪枝：决策树容易过拟合，一般来需要剪枝，缩小树结构规模、缓解过拟合。剪枝技术有预剪枝和后剪枝两种。

---

基于信息论的三种决策树算法：

划分数据集的最大原则是：使无序的数据变的有序。如果一个训练数据中有20个特征，那么选取哪个做划分依据？这就必须采用量化的方法来判断，量化划分方法有多重，其中一项就是“信息论度量信息分类”。基于信息论的决策树算法有ID3、CART和C4.5等算法，其中C4.5和CART两种算法从ID3算法中衍生而来。

1、ID3算法

信息熵:

在概率论中，信息熵给了我们一种度量不确定性的方式，是用来衡量随机变量不确定性的，熵就是信息的期望值。熵度量了事物的不确定性，越不确定的事物，它的熵就越大。具体的，随机变量X的熵的表达式如下：

同理，对于连续型随机变量Y，其熵可定义为：

当给定随机变量X的条件下随机变量Y的熵可定义为条件熵H(Y|X)：

所谓信息增益就是数据在得到特征X的信息时使得类Y的信息不确定性减少的程度。假设数据集D的信息熵为H(D)，给定特征A之后的条件熵为H(D|A)，则特征A对于数据集的信息增益g(D,A)可表示为：g(D,A) = H(D) - H(D|A)

信息增益越大，则该特征对数据集确定性贡献越大，表示该特征对数据有较强的分类能力。

案例：

我们用爱学习，打游戏，打球来对数据集D（是否是优秀学生）进行决策。我们可以通过上式计算出数据集D的信息熵。首先，计算是否是优秀学生的信息熵：

在考虑属性划分时，我们有多个策略，这里选用信息增益指标判断：
d为每个节点对应的属性，比如打游戏就分为d1=打游戏，d2=不打游戏。一般而言，信息增益越大，则意味着使用此属性来进行划分所获得的‘纯度提升’越大。
下面进行推导一下
是否打球标签：
D1为打球，D2为不打球：

信息增益为0，基本对判断一个学生是否优秀没啥帮助

从信息增益的结果我们发现学习好对判断一个学生是否优秀有很大提升，所以在决策树中我们会首选是否学习好作为决策属性，然后再对其余属性递归。

ID3算法的不足

a)ID3没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。这大大限制了ID3的用途。
　　b)ID3采用信息增益大的特征优先建立决策树的节点。很快就被人发现，在相同条件下，取值比较多的特征比取值少的特征信息增益大。比如一个变量有2个值，各为1/2，另一个变量为3个值，各为1/3，其实他们都是完全不确定的变量，但是取3个值的比取2个值的信息增益大。
　　c) ID3算法对于缺失值的情况没有做考虑
　　d) 没有考虑过拟合的问题

2、C4.5算法

针对ID3算法有四个主要的不足，一是不能处理连续特征，第二个就是用信息增益作为标准容易偏向于取值较多的特征，最后两个是缺失值处理的问和过拟合问题。昆兰在C4.5算法中改进了上述4个问题。

(1)、对不能处理连续值特征，C4.5思路：将连续的特征离散化。

将m个连续样本从小到大排列。(比如 m 个样本的连续特征A有 m 个，从小到大排列 a1，a2，…am取相邻两样本值的平均数，会得m-1个划分点。对于这m-1个点，分别计算以该点作为二元分类点时的信息增益。选择信息增益最大的点作为该连续特征的二元离散分类点。(比如取到的增益最大的点为at，则小于at的值为类别1，大于at的值为类别2，这样就做到了连续特征的离散化。注意的是，与离散属性不同，如果当前节点为连续属性，则该属性后面还可以参与子节点的产生选择过程。

(2)、对于信息增益作为标准容易偏向于取值较多特征的问题。引入一个信息增益比，它是信息增益与特征熵（也称分裂信息）的比

其中的HA(D)，对于样本集合D，将当前特征A作为随机变量（取值是特征A的各个特征值），求得的经验熵(个人感觉就是IV值)：

信息增益比本质： 是在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大。(惩罚参数即特征熵的倒数)

缺点：信息增益比偏向取值较少的特征
原因： 当特征取值较少时HA(D)的值较小，因此其倒数较大，因而信息增益比较大。因而偏向取值较少的特征。

使用信息增益比：基于以上缺点，并不是直接选择信息增益率最大的特征，而是现在候选特征中找出信息增益高于平均水平的特征，然后在这些特征中再选择信息增益率最高的特征。

C4.5算法的不足与改进：

(1)、决策树算法非常容易过拟合，因此对于生成的决策树要进行剪枝。C4.5的剪枝方法有优化的空间。思路主要是两种，一种是预剪枝，即在生成决策树的时候就决定是否剪枝。另一个是后剪枝，即先生成决策树，再通过交叉验证来剪枝。
(2)、C4.5生成的是多叉树，在计算机中二叉树模型会比多叉树运算效率高。多叉树改二叉树，可以提高效率。
(3)、C4.5只能用于分类。
(4)、C4.5由于使用了熵模型，里面有大量的耗时的对数运算,如果是连续值还有大量的排序运算。如果能够加以模型简化减少运算强度但又不牺牲太多准确性的话，因此用基尼系数代替熵模型。
C4.5算法过程跟ID3算法一样，只是选择特征的方法由信息增益改成信息增益比。

3、CART算法

分类回归树算法：CART(Classification And Regression Tree)算法采用一种二分递归分割的技术，将当前的样本集分为两个子样本集，使得生成的的每个非叶子节点都有两个分支。因此，CART算法生成的决策树是结构简洁的二叉树。

分类树两个基本思想：第一个是将训练样本进行递归地划分自变量空间进行建树的想法，第二个想法是用验证数据进行剪枝。

CART分类树算法使用基尼系数来代替信息增益比，基尼系数代表了模型的不纯度，基尼系数越小，不纯度越低，特征越好。这和信息增益（比）相反。分类问题中，假设有K个类，样本点属于第k类的概率为Pk，则概率分布的基尼指数定义为：（Pk表示选中的样本属于k类别的概率，则这个样本被分错的概率为(1-Pk)）：

其中基尼指数Gini(D)表示集合的不确定性，基尼指数G(D,A)表示A=a分解后集合的不决定性。基尼指数越大，样本集合的不确定性越大。

优点：

非常直观，可解释极强。 在生成的决策树上，每个节点都有明确的判断分支条件，所以非常容易看到为什么要这样处理，比起神经网络模型的黑盒处理，高解释性的模型非常受金融保险行业的欢迎。在后面的动手环节，我们能看到训练完成的决策树可以直接输出出来，以图形化的方式展示给我们生成的决策树每一个节点的判断条件是什么样子的。
预测速度比较快。 由于最终生成的模型是一个树形结构，对于一条新数据的预测，只需要按照条件在每一个节点进行判定就可以。通常来说，树形结构都有助于提升运算速度。
既可以处理离散值也可以处理连续值，还可以处理缺失值。

缺点：

容易过拟合。 试想在极端的情况下，我们根据样本生成了一个最完美的树，那么样本中出现的每一个值都会有一条路径来拟合，所以如果样本中存在一些问题数据，或者样本与测试数据存在一定的差距时，就会看出泛化性能不好，出现了过拟合的现象。
需要处理样本不均衡的问题。 如果样本不均衡，某些特征的样本比例过大，最终的模型结果将会更偏向这些特征。
样本的变化会引发树结构巨变。

关于剪枝：

上面提到的一个问题就是决策树容易过拟合，那么我们需要使用剪枝的方式来使得模型的泛化能力更好，所以剪枝可以理解为简化我们的决策树，去掉不必要的节点路径以提高泛化能力。剪枝的方法主要有预剪枝和后剪枝两种方式。
预剪枝： 在决策树构建之初就设定一个阈值，当分裂节点的熵阈值小于设定值的时候就不再进行分裂了；然而这种方法的实际效果并不是很好，因为谁也没办法预料到我们设定的恰好是我们想要的。
后剪枝： 后剪枝方法就是在我们的决策树已经构建完成以后，再根据设定的条件来判断是否要合并一些中间节点，使用叶子节点来代替。在实际的情况下，通常都是采用后剪枝的方案。

python鸢尾花案例：

from sklearn import datasets
from sklearn.tree import DecisionTreeClassifier#引入决策树算法包
import numpy as np 
np.random.seed(0)
#设置随机种子，不设置的话默认是按系统时间作为参数，设置后可以保证我们每次产生的随机数是一样的

iris=datasets.load_iris() #获取鸢尾花数据集
iris_x=iris.data #数据部分
iris_y=iris.target #类别部分
#从150条数据中选140条作为训练集，10条作为测试集。permutation 接收一个数作为参数(这里为数据集长度150),产生一个0-149乱序一维数组
randomarr= np.random.permutation(len(iris_x))
iris_x_train = iris_x[randomarr[:-10]] #训练集数据
iris_y_train = iris_y[randomarr[:-10]] #训练集标签
iris_x_test = iris_x[randomarr[-10:]] #测试集数据
iris_y_test = iris_y[randomarr[-10:]] #测试集标签# 在模型训练时，我们设置了树的最大深度为 4
clf = DecisionTreeClassifier(max_depth=4)
clf.fit(iris_x_train, iris_y_train)

#引入画图相关的包 
from IPython.display import Image
from sklearn import tree
#dot是一个程式化生成流程图的简单语言
import pydotplus
dot_data = tree.export_graphviz(clf, out_file=None,
                                feature_names=iris.feature_names,
                                class_names=iris.target_names,
                                filled=True, rounded=True,
                                special_characters=True)
graph = pydotplus.graph_from_dot_data(dot_data)
Image(graph.create_png())

iris_y_predict = clf.predict(iris_x_test)
score=clf.score(iris_x_test,iris_y_test,sample_weight=None)
print('iris_y_predict = ')
print(iris_y_predict)
print('iris_y_test = ')
print(iris_y_test)
print('Accuracy:',score)

"""
iris_y_predict = 
[1 2 1 0 0 0 2 1 2 0]
iris_y_test = 
[1 1 1 0 0 0 2 1 2 0]
Accuracy: 0.9
可以看到第二个测试样本预测错误了，其他的都预测正确，准确率是 90%
"""

经过运行上面的代码，就会输出下面这幅图，可以看到每一次的判定条件以及基尼系数，还有能够落入此决策的样本数量和分类的类别。