决策树算法梳理

信息论基础

熵

熵的英文为entropy，表示一个系系统在不受外部干扰时，其内部最稳定的状态。

1948年，香农Claude E. Shannon引入信息（熵），将其定义为离散随机事件的出现概率。一个系统越是有序，信息熵就越低；反之，一个系统越是混乱，信息熵就越高。信息熵被认为是系统有序化程度的一个度量。

如果一个随机变量 $X$ 的可能取值为 $X = {x_1, x_2,\dots, x_k}$，其概率分布为 $P(X = x_i) = p_i（i = 1,2, \dots, n）$，则随机变量 $X$ 的熵定义为：

$H(X) =-\sum_xp(x)logp(x)$

联合熵

两个随机变量 $X$，$Y$ 的联合分布，可以形成联合熵 Joint Entropy，用 $H(X,Y)$ 表示。

条件熵

在随机变量 $X$ 发生的前提下，随机变量 $Y$ 发生所新带来的熵定义为 $Y$ 的条件熵，用 $H(Y|X)$ 表示，用来衡量在已知随机变量 $X$ 的条件下随机变量 $Y$ 的不确定性。

且有此式成立：$H(Y|X) = H(X,Y) – H(X)$，整个式子表示 $(X,Y)$ 发生所包含的熵减去 $X$ 单独发生包含的熵。

相对熵

又称互熵，交叉熵，鉴别信息，Kullback熵，Kullback-Leible散度等。
设 $p(x)$、$q(x)$ 是 $X$ 中取值的两个概率分布，则 $p$ 对 $q$ 的相对熵是：

$D(p\|q)=\sum_xp(x)log\frac{p(x)}{q(x)}=E_{p(x)}log\frac{p(x)}{q(x)}$

在一定程度上，相对熵可以度量两个随机变量的“距离”，且有 $D(p|q) ≠D(q|p)$。并且 $D(p|q)$ 必然大于等于 $0$ 。

互信息

两个随机变量 $X$，$Y$ 的互信息定义为 $X$，$Y$ 的联合分布和各自独立分布乘积的相对熵，用 $I(X,Y)$ 表示：

$I(X,Y)=\sum_{x,y}p(x,y)log\frac{p(x,y)}{p(x)p(y)}$

且有 $I(X,Y)=D(P(X,Y) | P(X)P(Y))$。

有 $H(Y)-I(X,Y) = H(Y|X)$，通过条件熵的定义，有：$H(Y|X) = H(X,Y) - H(X)$，根据互信息定义展开得到 $H(Y|X) = H(Y) - I(X,Y)$，把前者跟后者结合起来，便有 $I(X,Y)= H(X) + H(Y) - H(X,Y)$，此结论被多数文献作为互信息的定义。

信息增益

信息增益在决策树算法中是用来选择特征的指标，信息增益越大，则这个特征的选择性越好，在概率中定义为：待分类的集合的熵和选定某个特征的条件熵之差。

对于样本集合 $D$，类别数 $K$，数据集 $D$ 的经验熵表示为：

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

其中，$C_k$ 是样本集合 $D$ 中属于第 $k$ 类的样本子集，$|C_k|$ 表示该子集的元素个数，$|D|$ 表示样本集合的元素个数。

计算某个特征 $A$ 对于数据集 $D$ 的经验条件熵 $H(D|A)$：

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

其中，$D_i$ 是样本集合 $D$ 中特征 $A$ 取第 $i$ 个值的样本子集，$D_{ik}$ 表示 $D_i$ 中属于第 $k$ 类的样本子集。

信息增益 $g(D,A)$ 表示为二者之差：

$g(D,A) = H(D)-H(D|A)$

原理解释：对于待划分的数据集 $D$，其 entroy(前)是一定的，但是划分之后的熵 entroy(划分后)是不定的，entroy(划分后)越小说明使用此特征划分得到的子集的不确定性越小（也就是纯度越高），因此 entroy(划分前) - entroy(划分后)差异越大，说明使用当前特征划分数据集 $D$ 的话，其纯度上升的更快。在构建最优的决策树的时候总希望能更快速到达纯度更高的集合，希望集合往最快到达纯度更高的子集合方向发展，因此总是选择使得信息增益最大的特征来划分当前数据集 $D$。

缺点：信息增益偏向取值较多的特征

原因：当特征的取值较多时，根据此特征划分更容易得到纯度更高的子集，因此划分之后的熵更低，由于划分前的熵是一定的，因此信息增益更大。

信息增益比

信息增益比 = 惩罚参数 * 信息增益

在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大。

特征 $A$ 对于数据集 $D$ 的信息增益比定义为:

$g_R(D,A) = \frac{g(D,A)}{H_A(D)}$

其中，

$H_A(D) = \sum_{i=1}^{n}\frac{|D_i|}{|D|}log\frac{|D_i|}{|D|})$

称为数据集 $D$ 关于 $A$ 的取值熵。

惩罚参数：数据集 $D$ 以特征 $A$ 作为随机变量的熵的倒数，即：将特征 $A$ 取值相同的样本划分到同一个子集中（之前所说数据集的熵是依据类别进行划分的）

缺点：信息增益比偏向取值较少的特征

原因：当特征取值较少时 $H_A(D)$ 值较小，因此其倒数较大，因而信息增益比较大。

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

基尼不纯度

基尼指数（基尼不纯度）：表示在样本集合中一个随机选中的样本被分错的概率。

Gini指数越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高，反之，集合越不纯。

基尼指数（基尼不纯度）= 样本被选中的概率 * 样本被分错的概率

$Gini(D) = \sum_{k=1}^n\frac{|C_k|}{|D|}(1-\frac{|C_k|}{|D|})=1-\sum_{k=1}^n(\frac{|C_k|}{|D|})^2$

特征 $A$ 的Gini指数定义为：

$Gini(D|A) = \sum_{i=1}^n\frac{|D_i|}{|D|}Gini(D_i)$

从所有的可能划分的 $Gini(D,A_i)$ 中找出Gini指数最小的划分，这个划分的划分点，便是使用特征 $A$ 对样本集合 $D$ 进行划分的最佳划分点。

决策树的不同分类算法的原理及应用场景

ID3算法

ID3算法是决策树的一种，它是基于奥卡姆剃刀原理的，即用尽量用较少的东西做更多的事。ID3算法，即 Iterative Dichotomiser 3，迭代二叉树3代，是Ross Quinlan发明的一种决策树算法，这个算法的基础就是上面提到的奥卡姆剃刀原理，越是小型的决策树越优于大的决策树，尽管如此，也不总是生成最小的树型结构，而是一个启发式算法。

在信息论中，期望信息越小，那么信息增益就越大，从而纯度就越高。ID3算法的核心思想就是以信息增益来度量属性的选择，选择分裂后信息增益最大的属性进行分裂。该算法采用自顶向下的贪婪搜索遍历可能的决策空间。

决策树停止的条件：如果发生以下的情况，决策树将停止分割

改群数据的每一笔数据已经归类到每一类数据中，即数据已经不能继续在分。
该群数据已经找不到新的属性进行节点分割
该群数据没有任何未处理的数据

ID3算法只能处理离散型变量。

C4.5

C4.5算法是用于生成决策树的一种经典算法，是ID3算法的一种延伸和优化。C4.5算法对ID3算法主要做了一下几点改进：

通过信息增益率选择分裂属性，克服了ID3算法中通过信息增益倾向于选择拥有多个属性值的属性作为分裂属性的不足；
能够处理离散型和连续型的属性类型，即将连续型的属性进行离散化处理；
构造决策树之后进行剪枝操作；
能够处理具有缺失属性值的训练数据。

C4.5算法即是将ID3算法中选择特征的标准用信息增益比代替。

优点：

通过信息增益率选择分裂属性，克服了ID3算法中通过信息增益倾向于选择拥有多个属性值的属性作为分裂属性的不足；
能够处理离散型和连续型的属性类型，即将连续型的属性进行离散化处理；
构造决策树之后进行剪枝操作；
能够处理具有缺失属性值的训练数据。

缺点：

算法的计算效率较低，特别是针对含有连续属性值的训练样本时表现的尤为突出。
算法在选择分裂属性时没有考虑到条件属性间的相关性，只计算数据集中每一个条件属性与决策属性之间的期望信息，有可能影响到属性选择的正确性。

CART分类树

CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。

CART算法由以下两步组成：

决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；
决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时损失函数最小作为剪枝的标准。

CART决策树的生成就是递归地构建二叉决策树的过程。CART决策树既可以用于分类也可以用于回归。对分类树而言，CART用Gini系数最小化准则来进行特征选择，生成二叉树。

CART既可以处理离散性也可以处理连续型数据，既可以分类也可以回归。

回归树原理

回归树总体流程类似于分类树，区别在于，回归树的每一个节点都会得一个预测值，以年龄为例，该预测值等于属于这个节点的所有人年龄的平均值。分枝时穷举每一个 feature 的每个阈值找最好的分割点，但衡量最好的标准不再是最大熵，而是最小化平方误差。也就是被预测出错的人数越多，错的越离谱，平方误差就越大，通过最小化平方误差能够找到最可靠的分枝依据。分枝直到每个叶子节点上人的年龄都唯一或者达到预设的终止条件(如叶子个数上限)，若最终叶子节点上人的年龄不唯一，则以该节点上所有人的平均年龄做为该叶子节点的预测年龄。

回归树使用最大均方差划分节点；每个节点样本的均值作为测试样本的回归预测值。

决策树防止过拟合手段

有几种途径用来避免决策树学习中的过度拟合。它们可被分为两类：

及早停止增长树法，在ID3算法完美分类训练数据之前停止增长树；
修剪法，即对这个树后修剪。

尽管第一种方法可能看起来更直接，但是对过度拟合的树进行后修剪的第二种方法被证明在实践中更成功。这是因为在第一种方法中精确地估计何时停止增长树很困难。无论是通过及早停止还是后修剪来得到正确大小的树，一个关键的问题是使用什么样的准则来确定最终正确树的大小。

剪枝**是一个简化过拟合决策树的过程。有两种常用的剪枝方法：

预剪枝（pre-pruning）

通过提前停止树的构建而对树“剪枝”，一旦停止，节点就成为树叶。该树叶可以持有子集元组中最频繁的类；

预剪枝的方法有多种不同的方式可以让决策树停止生长，下面介绍几种停止决策树生长的方法：

限制决策树的高度和叶子结点处样本的数目

定义一个高度，当决策树达到该高度时就可以停止决策树的生长，这是一种最为简单的方法；
定义一个阈值，当达到某个结点的实例个数小于该阈值时就可以停止决策树的生长；
定义一个阈值，通过计算每次扩张对系统性能的增益，并比较增益值与该阈值的大小来决定是否停止决策树的生长。

后剪枝（post-pruning）

它首先构造完整的决策树，允许树过度拟合训练数据，然后对那些置信度不够的结点子树用叶子结点来代替，该叶子的类标号用该结点子树中最频繁的类标记。相比于先剪枝，这种方法更常用，正是因为在先剪枝方法中精确地估计何时停止树增长很困难。

后剪枝的方法

REP

REP方法是一种比较简单的后剪枝的方法，在该方法中，可用的数据被分成两个样例集合：一个训练集用来形成学习到的决策树，一个分离的验证集用来评估这个决策树在后续数据上的精度，确切地说是用来评估修剪这个决策树的影响。这个方法的动机是：即使学习器可能会被训练集中的随机错误和巧合规律所误导，但验证集合不大可能表现出同样的随机波动。所以验证集可以用来对过度拟合训练集中的虚假特征提供防护检验。

该剪枝方法考虑将书上的每个节点作为修剪的候选对象，决定是否修剪这个结点有如下步骤组成：

删除以此结点为根的子树；
使其成为叶子结点；
赋予该结点关联的训练数据的最常见分类；
当修剪后的树对于验证集合的性能不会比原来的树差时，才真正删除该结点。

因为训练集合的过拟合，使得验证集合数据能够对其进行修正，反复进行上面的操作，从底向上的处理结点，删除那些能够最大限度的提高验证集合的精度的结点，直到进一步修剪有害为止(有害是指修剪会减低验证集合的精度)。

REP是最简单的后剪枝方法之一，不过由于使用独立的测试集，原始决策树相比，修改后的决策树可能偏向于过度修剪。这是因为一些不会再测试集中出现的很稀少的训练集实例所对应的分枝在剪枝过如果训练集较小，通常不考虑采用REP算法。

PEP，悲观错误剪枝

悲观错误剪枝法是根据剪枝前后的错误率来判定子树的修剪。该方法引入了统计学上连续修正的概念弥补REP中的缺陷，在评价子树的训练错误公式中添加了一个常数，假定每个叶子结点都自动对实例的某个部分进行错误的分类。

把一棵子树（具有多个叶子节点）的分类用一个叶子节点来替代，在训练集上的误判率肯定是上升的，但是在测试数据上不一定，我们需要把子树的误判计算加上一个经验性的惩罚因子，用于估计它在测试数据上的误判率。对于一棵叶子节点，它覆盖了 $N$ 个样本，其中有 $E$ 个错误，那么该叶子节点的错误率为 $（E+0.5）/N$。这个 $0.5$ 就是惩罚因子，那么对于该棵子树，假设它有 $L$ 个叶子节点，则该子树的误判率估计为:

$(\sum E_i+0.5*L)/\sum N_i$

剪枝后该子树内部节点变成了叶子节点，该叶子结点的误判个数 $J$ 同样也需要加上一个惩罚因子，变成 $J+0.5$。那么子树是否可以被剪枝就取决于剪枝后的错误 $J+0.5$ 在$\sum E_i+0.5*L
$ 的标准误差内。对于样本的误差率 $e$，我们可以根据经验把它估计成伯努利分布，那么可以估计出该子树的误判次数均值和标准差

$E(subtree\_err\_count)=N*e \\ var(subtree\_err\_count)=\sqrt{N*e*(1-e)}$

使用训练数据，子树总是比替换为一个叶节点后产生的误差小，但是使用校正的误差计算方法却并非如此。剪枝的条件：当子树的误判个数大过对应叶节点的误判个数一个标准差之后，就决定剪枝：

$E(subtree\_err\_count)-var(subtree\_err\_count)>E(leaf\_err\_count)$

sklearn参数详解，Python绘制决策树

分类树

>>> sklearn.tree.DecisionTreeClassifier(criterion=’gini’, splitter=’best’, max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features=None, random_state=None, max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None, class_weight=None, presort=False)

参数：

criterion：string类型，可选参数（默认=”gini”）。度量划分属性质量：”gini”指基尼不纯度（Gini impurity）；”entropy”指信息增益。
splitter：string类型，可选参数（默认=”best”）。每个结点选择划分属性的策略：“best”选择最好的划分；”random”选择最好的随机划分。
max_features：int或float或string类型或None，可选参数（默认=None）。选择划分时所用的特征数目：
1. 若是int类型，则使用max_features个特征；
2. 若是float类型，则使用int(max_features*特征总数)个特征；
3. 若是”auto“或”sqrt“，则使用sqrt(特征总数)个特征；
4. 若是“log2”，则使用log2(特征总数)个特征；
5. 若是None，则使用全部特征。
max_depth：int类型或None，可选参数（默认=None）。树的最大深度。
min_samples_split： int或float类型，可选参数（默认=2）。划分一个内部结点所需的最小样本数：若是int类型，则最少使用min_samples_split个样本；若是float类型，则最少使用ceil(min_samples_split*特征总数)个样本。
min_samples_leaf：int或float类型，可选参数（默认=1）。叶子结点所需的最小样本数：若是int类型，则最少为min_samples_leaf个样本；若是float类型，则最少为ceil(min_samples_leaf*特征总数)个样本。
min_weight_fraction_leaf：float类型，可选参数（默认=0）。限制了叶子节点所有样本权重和的最小值，如果小于这个值，则会和兄弟节点一起被剪枝。
max_leaf_nodes：int类型或None，可选参数（默认=None）。叶子结点数目最大值。
class_weight：dict或list或”balanced”或None，可选参数（默认=None）。类别权重：
1. dict：{类别标签：权重}指定类别权重；
2. list：多输出问题，应给定一个包含多个dict的list参数；
3. “balanced”：自动调整类别权重根据类别样本个数所占比例：样本总数/（类别的样本数）；
random_state：int类型或RandomState实例或None，可选参数（默认=None）。
1. 若是int，random_state是随机数生成器的种子；
2. 若是RandomState实例，random_state是随机数生成器；
3. 若是None，则随机数生成器是使用np.random的RandomState实例。
min_impurity_split：float类型，可选参数（默认=1e-7）。树增长的早停阈值：如果某结点的不纯度小于这个阈值，则该结点为叶子结点。
presort：bool类型，可选参数（默认=False）。是否在拟合过程中预排序数据to加速寻找最好的划分：对于样本量大的决策树，设为True可能会减慢训练过程；当使用样本量少或者受限深度的决策树，设置为true会加速训练。

属性：

classes_：类别标签（数组或列表）
feature_importances_：特征重要性（数组）
max_features_：max_features的inferred（推测？）值（int）
n_classes_：类别数目（int）
n_features_：特征数目（int）
n_outputs_：输出数目（int）
tree_：树对象

回归树

>>> sklearn.tree.DecisionTreeRegressor(criterion=’mse’, splitter=’best’, max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features=None, random_state=None, max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None, presort=False)

参数：

criterion：string类型，可选参数（默认=”gini“）。度量划分属性质量：”mse”指均方误差，”mae“指平均绝对误差。

其余参数同DecisionTreeClassifier，但是没有class_weight这个参数。属性和方法也和DecisionTreeClassifier一致，没有class_这个属性。

决策树绘制

from sklearn.externals.six import StringIO
from sklearn import tree
import pydotplus

clf = tree.DecisionTreeClassifier()
clf = clf.fit(X, Y)

dot_data = StringIO()
tree.export_graphviz(clf,out_file = dot_data, 
					 feature_names = feature_name, 
					 class_names = target_name, filled = True, 
					 rounded = True, special_characters = True)
graph = pydotplus.graph_from_dot_data(dot_data.getvalue())
graph.write_pdf("WineTree.pdf")
print('Visible tree plot saved as pdf.')

自动生成的可视化决策树被保存在当前目录下的“WineTree.pdf”文件中。