决策树是一类常用的机器学习算法，是一种人类在面临决策问题时一种很自然的处理机制。例如，我们要判断“这是不是一个好瓜？”

1.划分选择

在上图数据集的划分过程中，关键的问题是如何选择我们在当前节点选择哪个属性进行划分。一般而言，随着划分过程不断进行，我们希望决策树的分支节点所包含的样本尽可能属于同一类别，即节点的“纯度”越来越高。

1.1 信息增益

“信息熵”是度量样本集合纯度最常用的一种指标，假设当前样本集合D中第k类样本的比例是(p_k(k=1,2,…,|gamma|))，则D的信息熵定义为$$Ent(D)=-sum_{k=1}^{|gamma|}p_klog_2p_k $$ Ent(D)的值越小，则D的纯度越高。

假定离散属性a有V个可能的取值({a^1,a^2,…,a^V})，若使用a来对样本集D进行划分，则会产生V个分支节点，其中第v个分支节点包含了D中所有在属性a上取值为(a^v)，记为(D^v)。我们可根据信息熵公式计算出(D^v)的信息熵，再考虑到不同的分支节点所包含的样本数不同，给分支节点赋予权重(frac{|D^v|}{|D|}),即样本数越多的分支节点影响越大，于是可以计算出使用属性a对样本集D进行划分所获得的“信息增益”(information gain)$$Gain(D,a)=Ent(D)-sum_{v=1}^Vfrac{|Dv|}{D}Ent(D^v) $$
一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大。因此，我们使用信息增益来进行决策树的划分属性选择，即选择(a_*=arg max_{ain A}Gain(D,a))，ID3决策树学习算法使用的就是信息增益作为属性划分的准则。

以上表的西瓜数据集为例，该数据集包含17个训练样例，用以学习一个瓜是不是好瓜的决策树，(|gamma|=2)，根节点包含所有样例，其中正例占(p_1=frac{8}{17})，反例占(frac{7}{17})，于是计算出根节点的信息熵$$Ent(D)=-sum_{k=1}^2p_klog_2p_k=-(frac{8}{17}log_2frac{8}{17}+frac{9}{17}log_2frac{9}{17})=0.998.$$
然后我们要计算出当前属性集合{色泽，根蒂，敲声，纹理，脐部，触感}中，每个属性的信息增益。以“色泽”为例，他有三个可能的取值：{青绿，乌黑，浅白}，若使用该属性对D进行划分，则可得到3个子集，分别记为：(D^1)(色泽=青绿)，(D^2)(色泽=乌黑)，(D^3)(色泽=浅白)。子集(D^1)包含编号为{1,4,6,10,13,17}的6个样例，其中正例占(p_1=frac{3}{6})，反例占(p_2=frac{3}{6})；(D^2)编号包含{2,3,7,8,9,15}，其中正例占(p_1=frac{4}{6})，反例占(p_1=frac{2}{6})；(D^3)包含编号{5,11,12,14,16}的5个样例，其中正例占(p_1=frac{1}{5})，反例占(p_1=frac{4}{5})。根据上式计算出用“色泽”划分之后所获得的3个分支节点的信息熵为$$Ent(D^{1)=-(frac{3}{6}log_2frac{3}{6}+frac{3}{6}log_2frac{3}{6})=1.000$$，$$Ent(D}2)=-(frac{4}{6}log_2frac{4}{6}+frac{2}{6}log_2frac{2}{6})=0.918$$，$$Ent(D^3)=-(frac{1}{5}log_2frac{1}{5}+frac{4}{5}log_2frac{4}{5})=0.722$$
于是，计算出“色泽”的信息增益为$$Gain(D,色泽)=Ent(D)-sum_{v=1}^3frac{Dv}{D}Ent(D^v)=0.998-(frac{6}{17}1.000+frac{6}{17}0.918+frac{5}{17}*0.722)=0.109$$
类似的，我们可以计算出其他属性的信息增益：(Gain(D,根蒂)=0.143)，(Gain(D,敲声)=0.141)，(Gain(D,纹理)=0.381)，(Gain(D,脐部)=0.289)，(Gain(D,触感)=0.006)。

显然，属性“纹理”的信息增益最大，于是它被选为划分属性，下图是基于“纹理”对根节点进行划分的结果，各分支节点所包含的样例子集显示在节点上。

然后，决策树学习算法将对每个分支做进一步划分，以第一个节点为例，该节点包含的样例集合(D^1)中有编号为{1,2,3,4,5,6,8,10,15}的9个样例，可用属性集合为{色泽，根蒂，敲声，脐部，触感}，基于(D^1)计算出各属性的信息增益：
(Gain(D^1,根蒂)=0.458)，(Gain(D^1,敲声)=0.331)，(Gain(D^1,脐部)=0.458)，(Gain(D^1,触感)=0.458).

“根蒂”，“触感”，“脐部”均取得了最大的信息增益，可任选其中的一个作为划分属性。类似的，对每个分支节点进行上述操作，最终得到的决策树如下

1.2 增益率

当我们使用信息增益去划分属性时，实际上隐含了一个不公平因素，那就是信息增益对可取数目较多的属性有偏好，如下：

[Ent(D)=-(frac{1}{2}log_2frac{1}{2}+frac{1}{2}log_2frac{1}{2})=1$$,$$Ent(D)=-(frac{1}{4}log_2frac{1}{4}+frac{1}{4}log_2frac{1}{4}+frac{1}{4}log_2frac{1}{4}+frac{1}{4}log_2frac{1}{4})=2
]

但实际上可取数目多的属性并不一定好，如Id属性，为了解决这个问题，提出了“增益率”的概念来选择最优划分属性，增益率的定义为$$Gain_ratio(D,a)=frac{Gain(D,a)}{IV(a)}$$,$$IV(a)=-sum_{v=1}^Vfrac{|Dv|}{|D|}log_2frac{|D^v|}{|D|}$$
IV(a)是属性a的固有值，属性a的可能取值数目越多（V越大），则IV(a)的值就会越大。

需要注意的是，增益率准则对可取数目较少的属性有所偏好，因此，C4.5算法并不是直接选取增益率最大的划分属性，而是采用启发式，先从候选属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

1.3 基尼系数

CART决策树使用“基尼系数”来选择划分属性，基于数据集D的纯度可用基尼值来度量

[Gini(D)=1-sum_{k=1}^{|gamma|}p_k^2
]

直观的看，Gini(D)反应了从数据集D中随机抽取两个样本，其类别标记不一致的概率。因此，Gini(D)越小，则数据集D的纯度越高。

属性a的基尼指数定义为$$Gini_index(D,a)=sum_{v=1}^Vfrac{|Dv|}{|D|}Gini(D^v).$$于是，我们在候选属性集合A中，选择那个使得划分后基尼指数最小的属性作为最优划分属性，即(a_*=argmin_{ain A} Gini\_index(D,a))

2. 剪枝处理

剪枝是决策树学习算法对付“过拟合”的主要手段，为了尽可能的正确分类训练样本，节点划分过程将不断重复，有时会造成因训练样本学习的太好了，以至于把训练集自身的一些特点当做所有数据都具有的一般性质而导致过拟合，因此可通过主动去掉一些分支来降低过拟合的风险。决策树的剪枝有“预剪枝”和“后剪枝”，预剪枝是指在决策树生成过程中，对每个节点在划分前先进性估计，若当前节点标记不能带来决策树泛化性能的提升，则停止划分并将当前节点当做是叶节点；后剪枝则是先从训练集生成一颗完整的树，然后自底向上地对非叶节点进行考察，若将该节点对应的子树换成叶节点能带来决策树泛化性能的提升，则将该子树替换为叶节点，泛化性能的判断需要从训练集中划分出一部分当做验证集。

3.连续与缺失值

3.1 连续值处理

之前讨论的都是基于离散属性来生成决策树，现实任务中常常会遇到连续属性，由于连续属性可取数目很多，因此不能根据连续属性的可取值来对节点进行划分。这时，连续属性离散化技术将派上用场，使用二分法对连续属性进行处理。

给定样本集D和连续属性a，假定a在D上出现了n个不同的取值，将这些值从小到大进行排序，记为({a^1,a^2,…,a^n}).基于划分点t可将D分为子集(D_t^-),(D_t^+),其中(D_t^-)包含那些在属性a上取值不大于t的样本，而(D_t^+)代表在属性a上取值大于t的样本。对连续属性a，我们可考察包含n-1个元素的候选划分点集合$$T_a={frac{a^i+a{i+1}}{2}|1<=i<=n-1}$$,
这样把区间的中位点作为候选划分点。然后，我们就可以像离散属性值一样来考察这些划分点，选取最优的划分点进行样本集合的划分，新的增益系数为$$Gain(D,a)=max_{tin T_a}Gain(D,a,t)=max_{tin T_a} {Ent(D)-sum_{lambda in {-,+}}frac{D_t^{{lambda}}{D}Ent(D_t}{lambda})}$$
其中Gain(D,a,t)是样本集D基于划分点t二分后的信息增益。于是，我们就可选择使Gain(D,a,t)最大化的划分点。

需要注意的是，与离散属性不同，若当前节点划分属性为连续属性，该属性还可作为其后代节点的划分属性。

3.2 缺失值处理

现实任务中常会遇到不完整样本，即样本的某些属性值缺失。尤其在属性数目较多的情况下，往往会有大量样本出现缺失值，如果简单的放弃不完整样本，仅使用无缺失值的样本进行训练，显然是对数据信息的浪费，所以我们要考虑在有缺失属性值的训练样例来进行学习。在此需要解决两个问题：（1）如何在属性值缺失的情况下进行划分属性选择？（2）给定划分属性，若样本在该属性上有缺失，如何对样本进行划分？

C4.5算法使用的解决方案如下所示：

开始时，根节点包含样本集D中全部17个样例，各样例的权值均为1.以属性“色泽”为例，该属性上无缺失值的样例子集D包含编号为{2,3,4,6,7,8,9,10,11,12,14,15,16,17}的14个样例，显然D的信息熵为$$Ent(D)=sum_{k=1}^2p_klog_2p_k=-(frac{6}{14}log_2frac{6}{14}+frac{8}{14}log_2frac{8}{14})=0.985$$
令(D_1),(D_2),(D_3)分别代表属性“色泽”上取值为“青绿”，“乌黑”以及“浅白”的样本子集，有

[Ent(D_1)=-(frac{2}{4}log_2frac{2}{4}+frac{2}{4}log_2frac{2}{4})=1.000
]

[Ent(D_2)=-(frac{4}{6}log_2frac{4}{6}+frac{2}{6}log_2frac{2}{6})=0.918
]

[Ent(D_3)=-(frac{0}{4}log_2frac{0}{4}+frac{4}{4}log_2frac{4}{4})=0.000
]

因此，样本子集(D)上属性“色泽”的增益信息为$$Gain(D,色泽)=Ent(D)-sum_{v=1}^3 r_vEnt(D)=0.985-(frac{4}{14}1.000+frac{6}{14}0.918+frac{4}{14}0.000)=0.306$$
于是，样本集D上属性“色泽”的信息增益为$$Gain(D,色泽)=frac{14}{17}0.306=0.252.$$
类似的可以计算出所有属性在D上的信息增益：

(Gain(D,色泽)=0.252);(Gain(D,根蒂)=0.171);
(Gain(D,敲声)=0.145);(Gain(D,纹理)=0.424);
(Gain(D,脐部)=0.289);(Gain(D,触感)=0.006);
“纹理”在所有属性中的值是最大的信息增益，采用纹理进行划分。划分的结果是使编号{1,2,3,4,5,6,15}的样本进入“纹理=清晰”分支，编号为{7,9,13,14,17}的样本进入“纹理=稍糊”分支，而编号为{11,12,16}的样本进入“纹理=模糊”分支。由于{8,10}在属性“纹理”上出现了缺失值，因此它将同时进入三个分支中。

上述结点划分过程递归执行，最终生成的决策树如下图所示