1.决策树

决策树是一种既可以用于分类又可用于回归的算法。决策树可以认为是if-then规则，也可认为是输入空间和类空间条件概率。决策树的生成分为三步：特征值的选择，决策树生成，决策树剪枝。

2.决策树模型

决策树由有向边和结点构成，决策树的结点有两种，一种是内部结点，一种是叶结点。分类决策树中，内部结点代表特征，叶结点代表类。回归树中，内部结点代表输入空间的划分区域，叶结点代表输出值。

特征数模型是树状结构。对于一个输入实例，特征树从根结点开始对实例特征进行测试，根据测试结果，将其分到某一子结点，直至到达叶结点。

3.决策树学习策略

这里涉及到熵、条件熵、经验熵、经验条件熵、信息增益、信息增益比等概念，逐一介绍。

3.1基本概念

（1）熵：熵是表达随机变量不确定性的一种度量。对于随机变量X，P(X=xi)=pi定义

当对数以2为底时，单位为比特，当对数以e为底时单位为纳特。由定义可知，熵只和随机变量X的分布有关和X的取值无关。

（2）条件熵：设随机变量X,Y,条件熵是在随机变量X确定的条件下，随机变量Y的不确定性。定义在X确定的条件下Y的条件概率的熵的数学期望条件熵。

（3）经验熵、经验条件熵：当熵、条件熵是由数据估计（极大似然估计）出来的时候，称为经验熵、经验条件熵。

设训练数据集为D，|D|表示其样本容量，有K个类Ck,|Ck|为属于类Ck的样本个数，设特征A有n个不同的取值{a1,a2,⋯,an},根据特征A将数据集D划分为n个子集，D1,D2,⋯,Dn,|Di|为Di的样本个数，记子集Di中属于类Ck的样本集合为Dik

经验熵：

条件经验熵：

为什么极大似然估计的公式是这样的，在朴素贝叶斯一章中已经证明过。

（4）信息增益：给定数据集D,和特征A,定义信息增益为数据集D的熵和在A给定的条件下的条件熵的差。

等价于类和特征的互信息。

（5）信息增益比：信息增益的大小和数据集中实例的数量有关，为了解决这一问题（这一问题，我的理解是当用信息增益判断树的生长和剪枝时，阈值给定的问题），定义信息增益比

3.2学习策略

损失函数最小。

定义损失函数

其中

C(T)代表每个叶结点对于训练数据的不确定性大小，也就是拟合误差，|T|代表决策树的复杂程度，α≥0控制两者之间的影响。

4.决策树学习方法

有两种经典算法，ID3和C4.5，两者思想大致相同，C4.5比ID3做了一些改进，用信息增益比代替信息增益来进行特征选择。

（1）特征选择

选择信息增益/信息增益比最大的特征用于分类，提高分类效率。

（2）决策树生成

给定数据集D,特征A取值集合{a1,a2,⋯,an}，特征A将数据集D分为n个非空的子集D1,D2,⋯,Dn,每个子集分配到相应的子结点中，再对子结点递归地调用以上方法，直至没有可用的特征或所有特征的信息增益/信息增益比都很小。

（3）剪枝

由决策树的生成方法可以看出，和贪心算法很像，有很大的可能发生过拟合，即对训练数据能够很好的拟合，但是对未知数据不能很好的预测。解决的办法是将决策树的复杂程度考虑进去，类似于正则化的思想，这一点在损失函数C(T)中已经体现。决策树的剪枝通过极小化损失函数实现。可以看出，决策树的生成时局部最优，而特征数的剪枝是求取全局最优。

4.1决策树生成算法

ID3：

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

输出：决策树T

（1）若数据集D中的实例都属于同一类Ck，生成树为单结点树，标记为Ck.

（2）若A=∅,则生成树为单结点树，数据集D中大多数实例所属类Ck为结点标记。

（3）否则，计算每一特征的信息增益。

（4）取信息增益最大的特征Ag,若Ag<ε,则生成树为单结点树，数据集D中大多数实例所属类Ck为结点标记。

（5）若Ag>ε,根据特征Ag所有可能取值ai将数据集D分为若干非空子集Di,取Di中实例数最大的类作为标记，构建子结点，由结点和子结点构成树T，返回T

（6）对于每一个子结点，将Di作为数据集，A−Ag作为特征，递归地调用（1）~（5）,得到子树Ti

4.2决策树剪枝算法

输入：决策树T，参数α

输出：剪枝后的决策树Tα

（1） 计算决策树T每个结点t的经验熵Ht(T)

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

设一组叶结点回缩到其父结点前后分别为TA,TB,若损失函数Cα(TB)<Cα(TA),则进行剪枝，其父结点变为新的叶结点。

（3）返回（2），直到不能继续，返回损失函数最小的决策树Tα