决策树的原理与实践

决策树是一种比较特殊的机器学习方法，它可以看作是一堆if-then规则的集合，某种程度上是更接近人类的思考方式的，具有一定的可读性，而其它机器学习方法更近似于一个个黑箱。

上图是一个是否打球的决策树，可以看到从上到下，不断考虑天气，湿度以及是否有风等情况来决定最后是否去打球，这个决策树建立起来之后，以后就可以根据这些特征来判断是否会去打球。
值得注意的一点就是上图中决策树的叶节点，玩或者不玩都是完全确定的，这也是理想的情况，但是实际中可能不会有这么好，但是只要够用就行，要防止过拟合。

决策树相关基本概念与生成

决策树顾名思义是一种树，由节点和有向边组成。内部节点如上图的圆角矩形，是一种特征，叶节点如上图的矩形表示一个类，也就是最终的决策结果。

决策树的学习就是不断地选择当前看来最好的属性将所有数据点尽可能的分开，，像是上图中一样，到最后叶节点中的类别相差越大越好，也就是“纯度”越高越好。所以这就引出一个问题，什么是“好”的属性，怎么才叫分的开？所以我们借用鼎鼎大名的信息熵（imformation entropy）的概念进行选择。
信息熵是度量样本集合纯度的一种指标。假定样本集合D*有N类样本，所占的比例分别为(p1,p2,⋯,pN)那么集合D的信息熵为

Ent(D)=−∑i=1Npilog2pi

令0log0=0那么可以看出当D是完全纯的时候，集合的信息熵为0。假设有两类相等数量的样本那么比例分别为0.5，可以算出信息熵最大为1。也就是这个时候我们完全不能接收到来自样本的信息，比如我们随便拿一个样本，猜它是某一类样本的概率和随机猜是一样的。

所以下一步就很好理解了，我们要选择一个属性，使这个属性让整个数据集减少的信息熵最多。
假设对于数据集D，我们有离散属性a，它有V个可能的取值{a1,a2,⋯,aV}，如果使用该属性对数据集进行划分，就会产生V个分支节点。其中第v个分支中的样本在a属性上的取值都是av，该分支的集合称为Dv。如上图所示，我们先采用outlook属性进行划分，就产生了sunny, overcast和rainy三个分支。
最终如何计算引入新属性之后的效果，我们引入信息增益的概念，公式如下：

Gain(D,a)=Ent(D)−∑v=1V|Dv||D|Ent(Dv)

可以看出公式右半部分减去的就是各个分支信息熵的加权平均，权重即为各个分支所占的比例。那么显然各个分支的信息熵越小，这个加权平均的数值越小，最后的信息增益越大。

但是这里又引出了一个问题，以信息增益为准则的话，算法倾向于选择分类类别特别多的属性。比如要对人进行分类，而如果有生日这个属性那么显然这个属性的信息增益是非常大的，因为每个节点最多也就一两个人，节点的“纯度”非常高，但是这样分是没有意义的 。所以我们又引入了信息增益率的概念。

Gain−ratio(D,a)=Gain(D,a)IV(a)

其中

IV(a)=−∑v=1V|Dv||D|log2|Dv||D|

这一项称为属性a的固有值，通常分的数目越多，这个值越大，是为了对分支数目多的情况进行“惩罚“。但是值得注意的是信息增益率准则倾向于选择分支数目较少的属性。

ID3算法

第一个决策树的算法ID3就是基于信息增益的。大致步骤就是选择当前特征集中信息增益最大的属性a进行分割。但是这得注意的是，如果信息增益小于某一阈值证明再分下去已经没有意义，应该返回。分割之后对每一分支递归地进行上面的步骤，但是属性集要减去已经选择过的属性比如a，这个倒是显然的。

C4.5算法

C4.5算法是对ID3算法的改进，但是基本步骤没有改变只是选择特征的时候使用的是信息增益比。

决策树的剪枝

在特征比较多的情况下，我们有可能生成一个很长的决策树，这个决策树在训练集上可能能力很好，但是泛化能力可能很差，也就是过拟合。因此我们需要对决策树进行剪枝。至于为什么剪枝之后的决策树泛化能力就会变好，一种解释是奥卡姆剃刀原理：如无必要，无增实体。也就是性能相近的情况下，我们选择结构更简单的决策树。
这里介绍的方法是通过最小化决策树增提的损失函数来进行剪枝
决策树的损失函数为：

Cα(T)=C(T)+α|T|=∑t=1|T|NtEntt(T)+α|T|

其中|T|表示决策树的叶节点个数，t为决策树的叶节点，改叶节点有Nt个样本点，其中第k类的样本有Ntk个所以式子中Entt(T)=−∑kNtkNtlogNtkNt表示第t个节点的信息熵。
因此C(T)这一项表示的是所有叶节点加权的熵，只不过权重是叶节点的样本点个数，样本点越多的节点权重更大。这一项决定整个决策树拟合的程度，训练的越好拟合程度越好，这一项越低。
第二项是对决策树复杂程度的惩罚，树越复杂，节点数越多，这一项越大。
最后α控制两者之间的影响。

因此完整的剪枝算法就是：
输入：生成算法产生的整个树，参数α
输出：修剪后的子树
递归地从每一个叶节点向上回缩（生成子节点的逆过程），每次回缩之后计算前后的整体的损失函数值，如果减少就进行回缩，直到整个树无法再进行回缩，就得到损失函数最小的子树。

CART算法

CART算法的全称就是分类与回归树（classification and regression tree），是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。CART决策树的一个重要特征就是它一定是二叉树，内部节点特征取值为“是”和“否”。

决策树的生成

CART分成回归树和分类树两种。对回归树使用平方误差最小化准则，对分类树使用基尼指数（Gini index）最小化准则。

回归树

一个回归树对应着输入空间的一个划分，假设最后分成了R1,R2,⋯,RM这M个单元，并且在每个单元上都有一个固定的输出值，那么回归树模型可以表示为

f(x)=∑m=1McmI(x∈Rm)

其中函数I为示性函数。
在空间划分确定的时候，我们使用平方误差最小化，也就是对误差项∑xi∈Rm(yi−f(xi))2求导，可以得出对cm最好的预测就是单元Rm上所有的输出yi的均值

那么只要我们能够确定输入空间的划分，最终的模型我们就能够得出来了，空间划分该如何确定？
对于第j个变量xj和它的取值s，将它们称为切分变量和切分点，并且可以得到两个区域

R1(j,s)={x|xj≤s}和R2(j,s)={x|xj>s}

之后求解

minj,s[minc1∑xi∈R1(j,s)(yi−c1)2+minc2∑xi∈R2(j,s)(yi−c2)2]

其实上式就是求一个切分，让切分形成的两个区域上误差之和最小，因为切分确定了之后，两个区域上的cm就确定了。式子看起来很复杂，其实就是遍历。对于固定的输入变量，遍历所有可能的取值，就能够找出最优的切分点。再遍历所有变量，可以找到最优切分变量，这样我们就找到了一个最优的切分(j,s)，最后对子区域不断切分直到达到条件就得到了最终的回归树。

分类树

CART分类树使用的是新的指标，叫做基尼指数。
在分类问题中，假设有K个类，样本点属于第k类的概率为pk，则概率分布的基尼指数定义为

Gini(p)=∑k=1Kpk(1−pk)=1−∑k=1Kp2k

对于二分类问题，样本点属于第1类的概率为p，则基尼指数为

Gini(p)=2p(1−p)

而这个也是在CART分类树中常用的。
如果样本集合D根据特征A是否可以取某一值a被分割成D1和D2,即

D1={(x,y)∈D|A(x)=a}D2=D−D1

那么在特征A的条件下，集合D的基尼指数为

Gini(D,A)=|D1||D|Gini(D1)+|D2||D|Gini(D2)

基尼指数的作用类似于熵，值越大表明集合的不确定性也越大

CART的生成算法
从根结点开始，对每个特征A，以及它的每个可能的取值a，按照是否能够取值为a切分成两个部分D1,D2，利用上式计算出A=a时的基尼指数，之后在所有的特征，以及它所有的可能的取值中找出基尼指数最小的A和a，也就是最优特征和切分点。这样就产生了两个子节点，然后对两个子节点再进行上面的步骤，直到满足停止条件。
同样一个特征使用过之后不能再用了。

CART的剪枝
CART的剪枝稍微有点复杂，这里大致说一下
CART的损失函数也是Cα(T)=C(T)+α|T|的形式，当α=0的时候整体树是最优的，当α−>+∞的时候单节点树是最优的。
从整体树开始，对任意内部节点t，以t为根结点的子树的损失函数为

Cα(Tt)=C(Tt)+α|Tt|

而以t为单节点的树的损失函数为

Cα(t)=C(t)+α

当α=C(t)−C(Tt)|Tt|−1的时候，两个树的损失函数相等，但是单节点的树结构更简单，所以进行剪枝，也就是缩成单节点。剪枝得到的子树称为T1
然后对新生成的T1继续进行上面的步骤，那么最后我们得到了一个序列T0,T1,⋯,Tn，最后进行交叉验证，得到最优的决策树Tα。

决策树在scikit-learn 中的应用

import numpy as np
import matplotlib.pyplot as plt

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier

# Parameters
n_classes = 3
plot_colors = "ryb"
#红黄蓝三色
plot_step = 0.02

# Load data
iris = load_iris()

for pairidx, pair in enumerate([[0, 1], [0, 2], [0, 3],
[1, 2], [1, 3], [2, 3]]):
# We only take the two corresponding features
    X = iris.data[:, pair]
#选择不同的特征
    y = iris.target

# Train
    clf = DecisionTreeClassifier().fit(X, y)
#训练，这个的用法也跟其他的分类器类似
# Plot the decision boundary
    plt.subplot(2, 3, pairidx + 1)

    x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
    y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
    xx, yy = np.meshgrid(np.arange(x_min, x_max, plot_step),
    np.arange(y_min, y_max, plot_step))
    plt.tight_layout(h_pad=0.5, w_pad=0.5, pad=2.5)

    Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)
    cs = plt.contourf(xx, yy, Z, cmap=plt.cm.RdYlBu)
    #画出决策区域的云图

    plt.xlabel(iris.feature_names[pair[0]])
    plt.ylabel(iris.feature_names[pair[1]])

# Plot the training points
    for i, color in zip(range(n_classes), plot_colors):
        idx = np.where(y == i)
        #找出输出的类别为i的样本点的indices
        plt.scatter(X[idx, 0], X[idx, 1], c=color, label=iris.target_names[i],
        cmap=plt.cm.RdYlBu, edgecolor='black', s=15)

plt.suptitle("Decision surface of a decision tree using paired features")
plt.legend(loc='lower right', borderpad=0, handletextpad=0)
plt.axis("tight")
plt.show()

上图是最后的输出，可以看到决策树的决策平面都是直的。以DecissionTreeClassifier的API为例，如下
class 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)

其中部分参数含义为
max_depth：树的最大深度
max_leaf_nodes：叶节点的最多数目

其他很多参数含义可以参考官方文档。