写在前面

决策树(decision tree)是一种基本的分类和回归方法，是机器学习的基本模型，其模型是树形结构，其具体实现包括三种经典算法，分别为ID3，C4.5，CART。
决策树可以作为基本模型用于构建复合模型，比如通过集成学习的方法，比如bagging，adaboosting以及stacking。其中基于bagging思想最经典的算法实现就是随机森林。

决策树介绍

机器学习中，决策树是一个预测模型，代表的是对象属性与对象值之间的一种映射关系。对于样本数据集，对象属性就是样本特征，有很多，对象值就是类标签，只有一个。分类决策树模型由结点和有向边组成。结点分为内部结点和叶结点。内部结点表示一个特征（属性），叶结点表示一个类标签。

从数据产生决策树的机器学习技术叫做决策树学习。决策树学习的算法通常是一个递归地选择最优特征，并根据特征对数据集进行分割，使得各个子数据集有一个最好的分类的过程。
决策树学习过程：特征选择，决策树生成

决策树的构建

构建根节点，将所有训练数据都放在根结点，按照这一特征将训练数据集分割成子集，如果这些子集已经能够被基本正确分类，则构建叶结点，并将这些子集分到对应的叶结点去。如果还有子集不能被基本正确分类，则对这些子集继续选择新的最优特征，继续对其进行分割，构建相应的结点，如此递归下去，直到所有训练数据子集被基本正确分类或者没有合适的特征为止。最后每个子集都被分到叶结点上，都有了明确的类。这就构成了一颗决策树。

通俗的理解就是：首先对于一个数据集，每一个样本都包含n个特征以及一个标签。首先，我们把这n个特征都作为第一个分裂结点，然后来分裂数据集，然后通过量化来计算那个结点是当前最好的分类特征，就选用次特征作为这个结点的特征。这个特征有几属性值，则从这个结点出发有几条边，每一条边代表当前特征的一个属性值，根据此特征，将数据集分成多个子集。如果此时边的叶子结点所包含的数据子集都属于一种标签，则这条路径决策树生成结束。如果包含多种标签，则重做上面的过程，直到每条路径的叶子结点的数据子集都是同一标签的。

为了找到决定性的特征、划分出最好的结果，我们必须评估数据集中蕴含的每个特征，寻找分类数据集的最好特征。完成评估之后，原始数据集就被划分为几个数据子集。这些数据子***分布在第一个决策点的所有分支上。如果某个分支下的数据属于同一类型，则该分支处理完成，称为一个叶子节点，即确定了分类。如果数据子集内的数据不属于同一类型，则需要重复划分数据子集的过程。如何划分数据子集的算法分为几种，常见的算法有三个ID3、C4.5、CART。

要理解这三个算法，我们需要先理解一些基本概念。

基本概念

信息：信息是关于事物的运动状态和规律的认识，它可以脱离具体的事物而被摄取、传输、存贮、处理和变换。

信息论：用数理统计方法研究信息的基本性质以及度量方法，研究最佳解决信息的摄取、传输、存贮、处理和变换的一般规律的科学。它的成果将为人们广泛而有效地利用信息提供基本的技术方法和必要的理论基础。

自信息量：自信息量I(ai)表示一个消息ai出现后所带来的信息量，用其概率的负对数来表示，即I(ai)=-log2p(ai)，因此I(ai)是非负值，并且是概率p(ai)的单调递减函数。一个消息出现的概率越大，则它出现所带来的信息量越小，很好理解，举个例子，当你听说一件几乎不可能发生的事情发生时，你是不是会觉得信息量巨大。

熵：信息论中，熵表示的是不确定性的量度，不确定性越高，熵越高，其意义是整个系统中的平均信息量。香农把信息定义为“用来消除不确定性的东西”。熵也可以被视为描述一个随机变量的不确定性的数量。一个随机变量的熵越大，它的不确定性越大。那么，正确估计其值的可能性就越小。越不确定的随机变量越需要大的信息量用以确定其值。

熵在信息论中的定义如下：
　　如果有一个系统S内存在多个事件S = {E1,…,En}, 每个事件的机率分布 P = {p1, …, pn}，则每个事件本身的讯息为
　Ie = − log2pi
　　（对数以2为底，单位是位元(bit)）
　Ie = − lnpi

I(A)度量事件A发生所提供的信息量，称之为事件A的自信息，P(A)为事件A发生的概率。如果一个随机试验有N个可能的结果或一个随机消息有N个可能值，若它们出现的概率分别为p1,p2,…，pN,则这些事件的自信息的和：[H=-SUM(pi*log(pi)), i=1,2…N]称为熵。

通俗理解就是事件A的N个可能发生所带来的信息量分别乘以N个可能发生的概率。

但是我们通常使用H(X)符号代表随机变量X的熵，
H(X)=E(I(X))

E代表期望值函数，I(X)代表随机变量X的自信息量。

联合熵:
H(X)代表整个系统的平均信息量，因此，H(X,Y)代表包含X,Y二个随机变量系统的联合熵。通俗理解是，我们平均需要使用H(X,Y)个位元(bit)（此时底数选2）才能表达其中一个(x , y)元素。

条件熵:
假如x为已知的情况之下，那么我们需要再假如多少位元(bit)才能表示其中的(x，y)元素呢？这就是H(Y|X)的意义。

H(Y|X) = H(X,Y) – H(X)
证明：

互信息:
对于二个随机变量X.Y，假如其概率分布分别为p1(x)和p2(y)，其联合概率分布为p(x,y)，则X,Y的互信息I(X;Y)定义如下：

假如随机变量X和Y无关(条件独立)，则其互信息为0：

互信息代表二个随机变量间共有的信息位元数(关联性)，相当与X的熵H(X)与条件熵H(Y|X)之间的差：

由于互信息代表二者之间的关联性，关联性越强互信息越大，因此可用互信息度量二个随机变量之间的距离，定义距离为d(X,Y)：
d(X,Y) = H(X,Y) - I(X,Y)

或者正则化后变为D(X,Y)：

D(X,Y) = d(X,Y)/H(X,Y)<=1

信息增益:
特征A对训练数据集D的信息增益定义为g(D,A):
g(D,A)=H(D)-H(D|A)
决策树学习中信息增益等价于训练数据集中类与特征的互信息。
通俗的理解是：H(D)代表整个数据集的不确定性，H(D|A)表示知道A之后整个系统的不确定性，那么H(D)-H(D|A)就表示了加A之后系统不确定性减少的程度，即A带来的信息量。而我们需要遍历整个特征集，希望找到一个特征A，使得此次分裂，使得按照特征A分裂之后，整个系统的不确定性减少的程度越大越好，这样系统就更加确定了。

下面详细解释信息增益的计算方法：

输入：训练数据集D和特征A；
输出: 特征A对训练数据集D的信息增益g(D,A)

决策树中ID3算法根据信息增益选择特征:对训练数据集(或子集)D，计算其每个特征的信息增益，比较它们的大小，选择信息增益最大的特征。

g(D,A)也有下面计算公式:

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

决策树学习中信息增益等价于训练数据集中类与特征的互信息。
通俗的理解是：H(D)代表整个数据集的不确定性，H(D|A)表示知道A之后整个系统的不确定性，那么H(D)-H(D|A)就表示了加A之后系统不确定性减少的程度，即A带来的信息量。

信息增益比：
以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。这是什么意思呢？意思就是说，按照计算特征信息增益，选择信息增益最大的特征此时的划分，这样做会将数据集划分为很多分支，但是这样做是不好的。

举一个极端的例子，训练样本里面包含了一个时间特征，假设训练样本的每一个样本的时间特征都取不同的时间点，那么按照这个特征划分训练集，其每个分支下的结点都只包含一个样本，而此时分支也非常多(叶子结点的个数等于样本的个数)，这样做明显是不好的。

使用信息增益比可以在某种程度解决这个问题（为了防止分裂的结点太多）。
特征A对训练集D的信息增益比定义为：gA(D,A)=g(D,A)/HA(D)
其中HA(D)是数据集关于特征A的熵，特征A的可能取值越多，那么HA(D)的值通常会越大，1/HA(D)的值就会越小。我们遍历特征希望寻找一个特征A使得gA(D,A)越大越好，即同时考虑了，特征A的信息增益要大，且A的可能取值要较少一点。

注意：为什么特征A可能取值越多，HA(D)的值会越大？
我的理解是：A的可能性越多，系统不确定性越大，那么HA(D)越大。
最极端的情况就是对于n个训练样本，A的可能性有n(n>>2)种，此时按照熵的公式计算得到: HA(D)=lg(n)，此时应该是最大的。对于A的取值较少时：比如若A的可能性为2种，此时HA(D)=lg(2)。

基尼指数：
我们知道，在ID3算法中我们使用了信息增益来选择特征，信息增益大的优先选择。在C4.5算法中，采用了信息增益比来选择特征，以减少信息增益容易选择特征值多的特征的问题。但是无论是ID3还是C4.5,都是基于信息论的熵模型的，这里面会涉及大量的对数运算。能不能简化模型同时也不至于完全丢失熵模型的优点呢？有！CART分类树算法使用基尼系数来代替信息增益比，基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。这和信息增益(比)是相反的。

具体的，在分类问题中，假设有K个类别，第k个类别的概率为pk, 则基尼系数的表达式为：

如何理解这个基尼指数呢？
我的理解是：模型的纯度代表模型对类别的区分度，假设经过特征A划分为三堆结点x1，x2，x3，那么系统希望对于每一堆结点中，类别尽可能的一致，如果x1都是类别1，x2都是类别2，x3都是类别3，那么系统的纯度就最高。理解了这个之后，要如何量化呢？借鉴概率论，对于一个系统D，我们随机有放回采样2个样本，取到二个样本为同一类的概率为：

Ck是D中属于第k类的样本子集，K是类的个数。
那么，取到二次为不同类的概率为：

这个概率越小，即划分后的每一堆集包括不同类的概率越小，即纯度越高。
所以对于基尼指数，我们希望它越小越好。

决策树三个经典算法

常用的几种决策树算法有ID3、C4.5、CART：

ID3算法

选择信息熵增益最大的feature作为node，实现对数据的归纳分类。ID3算法由Ross Quinlan发明，建立在“奥卡姆剃刀”的基础上：越是小型的决策树越优于大的决策树（be simple简单理论）。ID3算法中根据信息论的信息增益评估和选择特征，每次选择信息增益最大的特征做判断模块。
ID3算法核心是在决策树各个结点上应用信息增益准则选择特征划分子集，递归地构建决策树。具体方法是：从根结点开始，对结点计算所有可能的特征都计算信息增益，选择值最大的作为结点的特征，根据该特征的不同取值划分子结点；对子结点递归调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止。ID3详细构建算法如下：

注意：
1. D中实例数最大的类Ck意思类似于样本多数表决的意思，D集合中，多数样本属于那个类那么D集合的结点就属于那个类。
2. 算法5.1和本文上述描述的计算信息增益的方法一样。
3. 由ID3构建算法可以发现，递归出口的条件是：特征的信息增益小于某一阈值或者特征集的特征被用完了。

C4.5算法

是ID3的一个改进，比ID3准确率高且快，可以处理连续值和有缺失值的feature。。C4.5算法用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足在树构造过程中进行剪枝；能够完成对连续属性的离散化处理；能够对不完整数据进行处理。准确率较高，但效率低。
之前我们谈到了ID3算法的缺陷，C4.5对ID3进行了改进，但是C4.5和ID3很相似，区别是采样了信息增益比来选择特征。C4.5算法详细过程如下：

CART算法

上面谈到的二种算法构建的决策树都是用于分类任务的，下面介绍一种可以同时用于分类与回归的树CART(classification and regression tree,分类与回归树)。CART假设决策树是二叉树，内部结点特征的取值为”是”和”否”，左分支为取值为”是”的分支，右分支为取值为”否”的分支。这样的决策树递归地二分每个特征。
CART算法主要由以下二步组成：
(1)决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；
(2)决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准(对回归树用平方误差，对分类树用基尼指数构建损失函数)；
下面对这两种分开来讲：

分类树的生成：

(3)对两个子结点递归的调用(1)(2)，直到满足停止条件。
(4)生成CART决策树。

注意：1.算法停止的条件是结点中的样本个数小于预定阈值，或样本的基尼指数小于预定阈值或者没有更多特征(这个地方要理解，虽然递归没有剔除特征，但是根据是否划分(比如根据是否ai划分)，划分到是此特征(ai)的子集在那个维度上一定都是那个特征，不会有其他的(这在个维度上不可能有a1，a2特征))。

回归树的生成：

通过这种方式生成的回归树也称为最小二乘回归树。
注意：每次选择特征j的某个值时，会遍历所有的特征，然后根据此时的特征，再遍历它所有的取值，对每个取值，都计算一下上式子，然后算完之后，选择最小的值对应的那个特征的那个取值，作为划分依据。不知道我这样理解有没有问题。

最小二乘回归树具体算法如下：

决策树剪枝

为什么构建决策树之后要进行剪枝操作，因为决策树学习可能会产生过拟合现象。在决策树的学习过程中，为了尽可能正确分类训练样本，结点划分过程将不断重复，这样可能会造成有时决策树的分支过多，以至于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合。我们可以通过主动去掉一些分支来降低过拟合的风险。决策树的剪枝主要分为预剪(prepruning)和后剪枝(post-pruning)。

后剪枝

后剪枝式先从训练集生成一颗完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换成叶结点(就是删除该结点的孩子结点)能带来决策树泛化性能的提升，则将该子树替换成叶结点。

预剪枝

预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。
如何判断泛化性能是否提升呢？(算这部分性能时，我们通常可以采用留出法，即预留一部分数据用作”验证集”，在验证集上算这个)可以通过极小化决策树整体的损失函数，损失函数的构建可以引入前面提到的方法，比如信息增益，再加入对整个树结构复杂程度的惩罚项(详细可以参考<<统计学习方法>>李航67页)。

CART剪枝

CART剪枝算法由二步组成：
(1) 从生成算法产生的决策树T0底端开始不断剪枝，直到T0的根结点，形成一个子树序列{T0,T1,T2,T3……Tn}。
(2)通过交叉验证法在独立的验证数据集上对树序列进行测试，从中选择最优子树。(详细见<<统计学习方法>>李航72页)

参考：
1.http://blog.csdn.net/yueyedeai/article/details/15225677
2.http://ccckmit.wikidot.com/st:mutualinformation
3.http://sklearn.lzjqsdd.com/modules/tree.html
4.李航统计学习方法
5.周志华机器学习

决策树详解