一、算法表述

决策树学习的目的是为了产生一颗泛化能力强的数。

一般来说，一颗决策树包含一个根节点，若干个内部节点和若干个叶节点。

叶节点对应决策结果，其他每个节点对应一个属性测试。

每个节点包含的样本集合根据属性测试的结果被划分到子节点中，根节点包含样本全集。

从根节点到每个叶节点的路径就对应一个判定测试序列。

决策树的基本流程遵循“分而治之”策略。

生成决策树是一个递归的过程，有三种情况会导致递归返回：

1. 当前节点包含的样本全属于同一类别，无需划分。

2. 当前属性集为空，或者所有样本在所有属性上取值相同，无法划分。把当前节点标记为叶节点，并将其类别设定为该节点所含样本最多的类别。

3. 当前节点包含的样本集合为空，不能划分。把当前节点标记为叶节点，并将其类别设定为其父节点所含样本最多的类别。

二、划分选择

“信息熵”（information entropy）是度量样本集合纯度最常用的一种指标。

假设当前样本集合D中第k类样本所占的比例为pk（k=1,2,3，...，|y|），则D的信息熵定义为

Ent(D)的值越小，则D的纯度越高。

假定离散属性a有V个可能的取值{a1,a2,...,aV}，若使用a来对样本集D进行划分，则会产生V个分支节点，其中第v个分支节点包含了D中所有在属性a上取值为av的样本，记为Dv，则用属性a对样本集D进行划分所获得的“信息增益”（information gain）：

信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大。我们可以选择属性

来进行决策树的划分属性选择。

然而，信息增益准则对可取值数目较多的属性有偏好，为减少这种偏好可能带来的不利影响，可以使用“增益率”（gain ratio）来选择最优划分属性，定义为：

其中

相反，增益率准则对可取值数目较少的属性有所偏好。

所以可以先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

CART决策树使用“基尼指数”（Gini index）来选择划分属性。

Gini(D)越小，数据集D的纯度越高。

属性a的基尼指数定义为

所以可以选择划分后基尼指数最小的属性作为最优划分属性。

三、剪枝处理

剪枝是为了抑制决策树算法过拟合。

决策树剪枝的基本策略有“预剪枝”和“后剪枝”：

1.预剪枝是指在决策树生成过程中，对每个节点在划分前先进行估计，若当前节点的划分不能带来决策树泛化性能提升，则停止划分并将当前节点标记为叶节点。

2.后剪枝是先从训练集生成一颗完整的决策树，然后自底向上对非叶节点进行考察，若将该节点对应的子树替换为叶节点能带来决策树泛化性能提升，则将该子树替换为叶节点。