索引：

在这本书里面，主要讨论关于决策树分类的问题。决策树呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合，也可以认为是定义在特征空间和类空间上的条件概率分布。它主要优点是具有可读性，分类速度快。
决策树学习通常分为三个步骤：

特征选择，决策树生成，决策树修剪

定义：

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

决策树学习

决策树学习的本质是从训练数据集中归纳出一组分类规则。
决策树学习的算法通常是递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好地分类的过程。这一过程对应着对特征空间的划分，也对应着决策树的构建。开始，构建根节点，将所有训练数据都放在根节点，选择一个最优特征，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。如果这些子集已经能够被基本正确分类，那么构建叶节点，并将这些子集分到对应的叶节点中去；如果还有子集不能被正确分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的节点。如此递归得进行下去，直至所有训练数据子集被基本正确分类，或者没有合适的特征为止。最后每个子集都被分到叶节点上去，即都有了明确的分类。这就生成了一颗决策树。
为了避免发生过拟合现象，常常需要对已生成的树自下而上进行剪枝，将树变得更简单，从而使它具有更好的泛化能力。具体来说就是去掉过于细分的叶节点，使其退回到父节点，甚至更高的节点，然后将父节点或更高的节点改为新的叶节点。
如果特征数量很多，也可以在决策树学习开始的时候，对特征进行选择，只留下对训练数据有足够分类能力的特征。

特征选择

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

信息增益

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

则随机变量X的熵定义为

由定义可知，熵只依赖于X的分布，而与X的取值无关，所以也可将X的熵记作H(p),即

熵越大，随机变量的不确定就越大。从而可以验证
0<=H(p)<=logn

可以看出来，如果可能性总数是确定的，当每一种可能性的概率都相等且都独立时，熵最大，为logn
设有随机变量(X,Y),其联合概率分布为

这里，pi=P(X=xi),i=1,2,...,n。
当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵和经验条件熵。
信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。

信息增益定义：特征A对训练数据集D的信息增益g(D,A),定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即

一般来说，熵H(Y)与条件熵H(Y|X)之差称为互信息。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

ID3算法

输入：训练数据集D，特征集A阈值
(1)若D中所有实例属于同一类Ck，则T为单节点树，并将Ck作为该节点的类标记，返回T；
(2)若A等于空集，则T为单节点树，并将D中实例数最大的类Ck作为该节点的类标记，返回T;
(3)否则，计算A中各特征对D的信息增益，选择信息增益最大的特征Ag；
(4)如果Ag的信息增益小于某阈值，则置T为单节点树，并将D中实例数最大的类Ck作为该节点的类标记，返回T；
(5)否则，对Ag的每一可能值ai，依Ag=ai，将D分割为若干非空子集Di，将Di中实例数最大的类作为标记，构建子节点，由节点及其子节构成树T，返回T；
(6)对第i个子节点，以Di为训练集，以A-{Ag}为特征集，递归地调用步(1)到(5)，得到子数Ti，返回Ti。

C4.5算法

与ID3算法类似，不过将信息增益换为了信息增益比

决策树的剪枝

决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现。设树T的叶节点个数为T的绝对值，t是树T的叶节点，该叶节点有Nt个样本点，其中k类的样本点有Ntk个，k=1，2，···，K，Ht(T)为叶节点t上的经验熵，α>=0为参数，则决策树学习的损失函数可以定义为

其中经验熵为

在损失函数中，右边第一项表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，第二项中T的绝对值表示模型复杂度，参数α控制两者之间的影响。较大的α促使选择简单的模型，较小的阿尔法促使选择较复杂的模型，α等于0说明不考虑模型的复杂度。

**决策树生成只考虑了通过提高信息增益（比）对训练数据进行更好的拟合。而决策树剪枝通过优化损失函数还考虑了减小模型复杂度。决策树生成学习局部模型，而决策树剪枝学习整体的模型。

CART算法

CART生成

决策树的生成就是递归地构建二叉决策树的过程。对回归树用平方误差最小化标准，对分类树用基尼指数最小化准则，进行特征选择，生成二叉树。

回归树的生成

设有训练集
一颗回归树对应着输入空间（即特征空间）的一个划分以及在划分单元上的输出值。假设已将输入空间划分为M个单元R1,R2,...RM,并在每个单元Rm上有一个固定的输出值cm，则回归树模型可表示为

此时我们在验证时，用平方误差来表示回归树对于训练数据的预测误差，用平方误差最小的准则求解每个单元上的最优输出值。找到最优切分变量以及它对应的切分值即可。

分类树的生成

这里在已知entropy的基础上引入另一个相近概念即基尼指数：

同样是表示集合不确定性的一个概念。
CART树在一些问题的处理中，和ID3算法类似，只是将entropy换为了基尼指数。

CART剪枝算法

输入：CART算法生成的决策树T0；
输出：最优决策树Tα
(1)设k=0，T=T0
(2)设α=+∞
(3)自下而上地对各内部节点t计算C(Tt),|Tt|以及

这里，Tt表示以t为根节点的子树，C(Tt)是对训练数据的预测误差，|Tt|是Tt的叶节点个数。
(4)对g(t)=α的内部节点t进行剪枝，并对叶节点t以多数表决法决定其类，得到树T。
(5)设k=k+1，αk=α，Tk=T
(6)如果Tk不是由根节点及两个叶节点构成的树，则回到(2)；否则令Tk=Tn。
(7)采用交叉验证法在子树序列T0，T1，···Tn中选取最优子树Tα。