一、决策树算法

  决策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。

  决策树算法的核心思想就是通过不断地决策来筛选出最终想要的结果，来看下面一个例子：

上图是一个女孩相亲中确定见不见男方的过程，她先根据年龄筛选，年龄大于30 的不见，小于30的看长相；长相丑的不见，不丑的见……然后就一直这样筛选直到确定见或者不见。

决策树的基本算法如下：

决策数的生成是一个递归的过程，在决策树基本算法中，有三种情形会导致递归返回：（1）当前节点所包含的样本均属于同一个类别，无需划分（2）当前节点在所有属性上取值相同或者没有属性，无法划分（3）当前节点所包含的样本集为空，不能划分。上述算法是一个递归的过程，情形二和情形三都是到了叶节点不能再划分的情况。情形二和情形三稍有不同，情形二是利用当前节点的后验分布，情形三是利用当前节点父节点的先验分布。

决策树划分选择的依据是信息熵。当数据没有分类时，信息熵是比较大的，分类完成时信息熵比较小，所以是一个熵减小的过程。为了使算法收敛的最快，就要选取使熵减小最快的划分。决策数的典型算法有ID3，C4.5,CART等，下面分别来说一下这三个算法。

信息增益与ID3决策树算法

ID3算法使用信息增益做为划分选择。一般而言，我们希望决策树所包含样本尽可能属于同一类别，即节点"纯度"越来越高。

信息增益表示在得知某一个特征A的情况下，使得某一类X的不确定性减少的程度。比如知道了西瓜的某一特征之后（如敲击响度），就能增大对它属于某一类瓜（好瓜、坏瓜等）的判断，信息增益就是用来度量这个增大程度的。

定义特征A对给定的训练数据集D的信息增益为g(D,A)

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

H(D)、H(D|A)分比为经验熵和经验条件熵。经验熵为从实际样本中根据经验估计（如极大似然估计）得到的熵，经验条件熵类似。

上述公式的含义为信息增益等于当前熵减去在知道特征A的情况下的熵，这也就是信息增益的定义。

因为经验熵H(D)的计算公式为：

其中k为某一类的个数，Ck为特征类，D为训练数据集，Ck/D即为第k类样本在所有数据集中的比重。（这里k用的有点混淆，k即代表了类别的总个数，也代表了某一类别，希望读者不要混淆）

经验条件熵的推导过程为：

上式的后半部分（后一个累加和后）即为经验熵的公式。

所以分别把H(D)和H(D|A)的计算公式带入到信息增益的计算公式即可得信息增益的计算公式。

信息增益率与C4.5决策树算法

C4.5算法采用信息增益率来进行划分。因为使用信息增益对可取值较多的属性有所偏好（因为在假定信息熵水平大致相等情况下，属性可取的值越多，以为这划分出更多的类别，所以每个类别占总体的比例变比较小，这样计算出来的H(D|A)较小，信息增益较大），为减少这种偏好可能带来的影响，C4.5算法采用增益率选择划分最优属性，增益率的定义如下：

即信息增益除以经验熵即为信息增益率。

但是使用增益率来划分则可能对取值数目较少的属性有所偏好（因为对H(A)属性值划分越多，值通常会越大，所以属性可取值多的信息增益率通常较小），因此C4.5选择了一个折中的方案，即先从候选划分属性中找出信息增益高于平均水平的属性，再在其中选择增益率最高的。

基尼指数与CART决策树算法

CART决策树算法选择基尼指数来选择划分属性。基尼系数的定义为：

Pk即为第k类样本占总样本的比例。                                     

直观来说基尼系数反映了从数据集D中随机抽取两个样本，其所属类别不一致的概率。因此基尼系数的值越小，数据集的纯度越高。

属性a的基尼指数定义为：

所以我们在候选属性集合中，选择使得划分后基尼指数最小的属性做为优先划分属性。

决策树评价

三种算法介绍完了，那么我们怎么去评价一棵决策树呢？

我们假定样本的总类别为K个，对于决策树的某一个叶节点，假定该叶节点含有样本数目为n，其中第k类的样本数目为nk：

(1):  若某类样本nj=n，而n1=n2=n3=...=nj-1=nj+1=...=nk=0，则称该结点为纯结点。即该节点下的所有样本均属于同一类，完美的分类。

(2):  若各个分类样本数目一样多n1=n2=...=nk=n/K，则称样本为均结点。该节点下所有样本分别属于不同的类别，最糟糕的分类。

纯结点的熵H = 0最小，均结点最大 H = lnK

那么我们就可以对所有的熵求和，该值越小说明分类越精确，由于各个结点的包含的样本数目不同，有的1000，有的1个，所以我们可以对叶结点加权。

评价函数：

Nt为每个节点下的样本数，H(t)为信息熵。

由于该值我们希望越小越好，所以又被称为损失函数（loss function）。

二、对决策树进行剪枝处理

剪枝是决策树算法对付过拟合的主要手段。因为决策树在划分过程中为了尽可能正确分类训练样本，可能会不断重复，产生过拟合现象。即可能会为了分类正确，将具有某一些属性的样本强行划分到某一类中，而这些样本本不应该属于这一类，只是在这个数据集中属于了这一类，不具有普遍的意义，这样就差生了过拟合。为了降低过拟合的风险可以主动去掉一些分支。剪枝可以分为后剪枝和预剪枝，预剪枝在决策树生成过程中进行，后剪枝在决策树生成完后进行。预剪枝可能产生欠拟合风险，后剪枝效果更好，但是训练时间要长一些，这里重点说一下后剪枝。

剪枝系数

决策树原本的损失函数为：

叶结点越多树也就越复杂，损失越大，那么我们就可以对原损失函数做修正：

Tleaf为叶节点数量。

当α=0时，未剪枝的决策树损失最小；

α为无穷时，全部剪枝只有根节点的决策树损失最小。

我们假定当前对以r为根的子树剪枝，剪枝后只保留r本身而删除所有的叶子。

那么我们可以看看剪枝前后的损失函数：

剪枝后：

剪枝前：

令二者相等求得：

α就称为r结点的剪枝系数。

剪枝算法

1.计算所有节点的剪枝系数

2.选择剪枝系数最小的节点进行剪枝，得到决策树Tk

3.重复上述步骤，直到决策树只有一个节点

4.在这个过程中，得到原本决策树的子树序列T0T1T2……Tk

使用验证集做最优子树的标准，可以使用原评价函数：

选出最优子树。

参考：

周志华《机器学习》

邹博 机器学习视频