决策树（decision tree）

决策树是一种基本的分类和回归方法。本章主要讨论用于分类的决策树，决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程，它可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。其主要优点是模型具有可读性，分类速度快。学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型。预测时，对新的数据，利用决策树模型进行分类。

决策树学习通常包括3个步骤：特征选择、决策树的生成和决策树的修剪。这些决策树学习的思想主要源于ID3算法和C4.5算法以及CART算法。

决策树模型

定义：分类决策树模型是一种描述对实例进行分类的树形结构，决策树由结点（node）和有向边（directed edge）组成，结点有两种类型：内部结点（internal node）和叶节点（leaf node）。内部结点表示一个特征或属性，叶结点表示一个类。

用决策树分类，从根结点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点；这时，每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至达到叶结点。最后将实例分到叶结点的类中。

决策树与if-then规则

可以将决策树看成一个if-then规则的集合。将决策树转换成if-then规则的过程是这样的：

1.由决策树的根结点到叶结点的每一条路径构建一条规则；

2.路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。

决策树的路径或其对应的if-then规则集合具有一个重要的性质：互斥并且完备。这就是说，每一个实例都被一条路径或一条规则所覆盖，而且只被一条路径或一条规则所覆盖。这里所谓覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件。

决策树与条件概率分布

决策树还表示给定特征条件下类的条件概率分布。这一条件概率分布定义在特征空间的一个划分上。将特征空间划分为互不相交的单元或区域，并在每个单元定义一个类的概率分布就构成了一个条件概率分布。决策树的一条路径对应于划分中的一个单元。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。假设X为表示特征的随机变量，Y为表示类的随机变量，那么这个条件概率分布可以表示为P(Y|X)。X取值于给定划分下单元的集合，Y取值于类的集合。各叶结点（单元）上的条件概率往往偏向某一个类，即属于某一类的概率较大。决策树分类时将该结点的实例强行分到条件概率大的那一类去。

下图表示了特种空间的一个划分。大正方形表示特征空间。这个大正方形被若干个小矩形分割，每个小矩形表示一个单元。特征空间划分上的单元构成了一个集合，X取值为单元的集合。假设只有两类正类负类，Y=+1 -1；小矩形数字表示单元的类。第二个图表示给定条件下类的条件概率分布。P(Y=+1|X=c)>0.5时属于正类，实际上对应的就是矩形框的面积。

决策树学习

假设给定训练数据集D={(x₁,y₁),(x₂,y₂),……..(x_N,y_N)}

其中x_i=(x_i⁽¹⁾ ,x_i⁽²⁾,…….,x_i⁽ⁿ⁾)^T为输入实例（特征向量），n为特征个数，y_i∈{1，2，…..K}为类标记，i=1，2，3，……,N，N为样本容量。学习目标是根据给定的训练数据集构建一个决策模型，使它能够对实例进行正确的分类。

决策树学习本质上是从训练数据集中归纳出一组分类规则。与训练数据集不相矛盾的决策树（即能对训练数据进行正确分类的决策树）可能多个，也可能一个也没有。我们需要的是一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。从另一个角度看，决策树学习是由训练数据集估计条件概率模型。基于特征空间划分的类的条件概率模型有无穷多个。我们选择的条件概率模型应该不仅对训练数据有很好地拟合，而且对未知数据有很好地预测。

决策树学习用损失函数表示这一目标，如下所述，决策树学习的损失函数通常是正则化的极大似然函数。决策树学习的策略是以损失函数为目标函数的最小化。

当损失函数确定以后，学习问题就变为在损失函数意义下选择最优决策树的问题。因为从所有可能的决策树中选取最优决策树是NP完全问题，所以现实中决策树学习算法通常采用启发式方法，近似求解这一最优化问题。这样得到的决策树是次最优的。

决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分，也对应着决策树的构建。

开始，构建根结点，将所有训练数据集都放在根结点。选择一个最优特征，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。如果这些子集已经能够被基本正确分类，那么构建叶结点，并将这些子集分到所对应的叶结点中去；如果还有子集不能被基本正确分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的结点，如此递归地进行下去，直至所有训练数据子集被基本正确分类，或者没有合适地特征为止。最后每个子集都被分到叶结点上，即都有了明确的分类，这就生成了一棵决策树。

以上方法生成的决策树可能对训练数据有很好的分类能力，但对未知的测试数据却未必有很好的分类能力，即可能发生过拟合现象。我们需要对已生成的树自下而上进行剪枝，将树变得更简单，从而使其具有更好的泛化能力。具体地，就是去掉过于细分的叶结点，使其回退到父结点，甚至更高的结点，然后将父结点或更高的结点改为新的叶结点。

决策树的工作过程一般可以分为三步：
1、特征选择
2、决策树生成
3、剪枝

1.特征选择

特征选择在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征没有分类能力。通常特征选择的准则是信息增益或信息增益比。

熵在信息论与概率统计中，熵表示随机变量不确定性的度量。设X是一个取有限个值得离散随机变量，其概率分布为：

则随机变量X的熵定义为：

条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性：条件熵经验熵和经验条件熵：当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵和条件经验熵。

信息增益信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即：

信息增益一般地，熵H(Y)与条件熵H(Y|X)之差称为互信息。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。于是我们可以应用信息增益准则来选择特征，信息增益表示由于特征A而使得对数据集D的分类的不确定性减少的程度。对数据集D而言，信息增益依赖于特征，不同的特征往往具有不同的信息增益。信息增益大的特征具有更强的分类能力。

信息增益算法设训练数据集为D，|D|表示其样本容量，即样本个数。设有K个类Ck,k=1,2,⋅⋅⋅,K,|Ck|为属于类Ck的样本个数，∑Kk=1|Ck|=|D|。设特征A有n个不同的取值a1,a2,⋅⋅⋅,an,根据特征A的取值将D划分为n个子集D1,D2,⋅⋅⋅,Dn为Di的样本个数，∑ni=1|Di|=|D|。记子集Di中属于类Ck的样本的集合为Dik。具体信息如下：

信息增益的计算

信息增益比以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。使用信息增益比可以对这一问题进行校正。信息增益比表示特征A对训练数据集D的信息增益比。gR(D,A)定义为其信息增益g(D,A)与训练数据集D关于特征A的值的熵HA(D)之比，即：

信息增益比

基尼系数
分类问题中，假设有K个类，样本点属于第k类的概率为pk，则概率分布的基尼系数定义为：

基尼系数

若样本集合D根据特征A是否取某一可能值a被分割成D1和D2两部分，即：

对A的划分则在特征A的条件下，集合D的基尼指数定义为：

基尼系数

基尼系数Gini(D)表示集合D的不确定性，表示经A=a分割后集合D的不确定性。基尼系数越大，样本集合的不确定性越大，与熵类似。
从下图可以看出基尼指数和熵之半的曲线很接近，都可以近似地代表分类误差率。

2.决策树生成

ID3算法ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树，具体方法是：从根结点（root node）开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子结点递归地调用以上方法，构建决策树；直到所有特征地信息增益均很小或没有特征可以选择为止。最后得到一个决策树。ID3相当于用极大似然法进行概率模型的选择。具体算法：输入：训练数据集D，特征集A，阈值ε；输出：决策树T。（1）若D中所有实例属于同一类C_k,则T为单结点树，并将类C_k作为该结点的类标记，返回T（2）若A=空集，则T为单结点树，并将D中实例数最大的类C_k作为该结点的类标记，返回T.（3）否则，按信息增益算法计算A中各个特征对D的信息增益，选择信息增益最大的特征A_g（4）如果A_g的信息增益小于阈值ε，则置T为单结点树，并将D中实例数最大的类C_k作为该结点的类标记，返回T（5）否则，对A_g的每一可能值a_i,依A_g=a_i将D分割为若干非空子集D_i,将D_i中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T,返回T;（6）对第i个子结点，以D_i为训练集，以A-{A_g}为特征集，递归地调用步（1）~步（5）得到子树T_i,返回T_i

算法缺陷

ID3算法可用于划分标准称型数据，但存在一些问题：

• 没有剪枝过程，为了去除过渡数据匹配的问题，可通过裁剪合并相邻的无法产生大量信息增益的叶子节点;
• 信息增益的方法偏向选择具有大量值的属性，也就是说某个属性特征索取的不同值越多，那么越有可能作为分裂属性，这样是不合理的；
• 只可以处理离散分布的数据特征

• 总结基本思想：

  • 初始化属性集合和数据集合
  • 计算数据集合信息熵S和所有属性的信息熵，选择信息增益最大的属性作为当前决策节点
  • 更新数据集合和属性集合（删除掉上一步中使用的属性，并按照属性值来划分不同分支的数据集合）
  • 依次对每种取值情况下的子集重复第二步
  • 若子集只包含单一属性，则为分支为叶子节点，根据其属性值标记。
  • 完成所有属性集合的划分

  注意：该算法使用了贪婪搜索，从不回溯重新考虑之前的选择情况。

  C4.5算法

  C4.5算法与ID3算法相似，C4.5算法对ID3算法进行了改进。C4.5在生成的过程中，用信息增益比来选择特征

  具体算法：

  输入：训练数据集D，特征集A,阈值ε；

  输出：决策树。

  （1）若D中所有实例属于同一类C_k,则T为单结点树，并将类C_k作为该结点的类标记，返回T（2）若A=空集，则T为单结点树，并将D中实例数最大的类C_k作为该结点的类标记，返回T.（3）否则，按信息增益比算法计算A中各个特征对D的信息增益比，选择信息增益比最大的特征A_g（4）如果A_g的信息增益比小于阈值ε，则置T为单结点树，并将D中实例数最大的类C_k作为该结点的类标记，返回T（5）否则，对A_g的每一可能值a_i,依A_g=a_i将D分割为若干非空子集D_i,将D_i中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T,返回T;（6）对第i个子结点，以D_i为训练集，以A-{A_g}为特征集，递归地调用步（1）~步（5）得到子树T_i,返回T_i

  决策树的剪枝

  为什么要进行剪枝呢？因为我们递归产生的决策树往往可以对训练数据分类很准确，但对于未知的测试数据的分类却没有那么准确，即出现过拟合现象。过拟合的原因在于学习时过多地考虑如何提高对训练数据地正确分类，从而构建出过于复杂的决策树。解决这个问题的办法是考虑决策树的复杂度，对已生成的决策树进行简化。在决策树中对已生成的决策树进行简化的过程叫剪枝。

  具体地，剪枝从已生成的树上裁掉一些子树或叶结点，并将其根结点或父结点作为新的叶结点，从而简化分类树模型。

  决策树的剪枝往往通过极小化决策树整体的损失函数（loss function）或代价函数。对loss function 进行正则化处理。设树T的叶结点个数为|T|,t是树T的叶结点，该叶结点有N_t个样本点，其中k类的样本点有N_tk个，k=1,2,….K，H_t(T)为叶结点t上的经验熵，α≥0为参数，则决策树学习的损失函数可以定义为

  Cα=Σ_i=1^|T|N_tH_t(T)+α|T|

  其中经验熵为

  H_t(T)=-Σ_kN_tk/N_tlogN_tk/N_t

  我们可以记C_α(T)=C(T) +α|T|

  C(T)表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，|T|表示模型复杂度，参数α≥0控制两者之间的影响。

  树的剪切算法

  输入：生成算法产生的整个树T，参数α；

  输出：修剪后的子树Tα

  （1）计算每个结点的经验熵

  （2）递归地从树地叶结点向上回缩

  设一组叶结点回缩到其父结点之前与之后地整体树分别为T_B与T_A，其对应的损失函数值分别是C_α(T_B)与C_α(T_A)，如果C_α(T_A)≤C_α(T_B)则进行剪枝，即将父结点变为新的叶结点。

  （3）返回（2），直至不能继续为止，得到损失函数最小的子树Tα。

  注意，式C_α(T_A)≤C_α(T_B)只需考虑两个树的损失函数的差，其计算可以在局部进行，所以，决策树的剪枝算法可以由一种动态规划的算法实现。

  ---

  ---

  参考文献：

  1.http://blog.csdn.net/tuobadon/article/details/47382271

  2.统计学习方法