机器学习 | 决策树理论知识（二）

上周我们学习了决策树特征选择的方法，本周我们来学习决策树的生成与剪枝算法。

决策树的生成

这周生成算法我们主要讲解ID3算法和C4.5算法，下周讲解CART算法。

ID3算法

ID3算法的核心是在决策树各个节点上应用信息增益准则选择特征，递归地构建决策树。

具体方法是：从根结点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止。最后得到一个决策树。

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- \lbrace A_g \rbrace\)为特征集，递归地调用步（1）~步（5），得到子树\(T_i\)，返回\(T_i\)。

C4.5算法

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

算法：

步骤与ID3相同，比较标准由信息增益变为信息增益比，故不再赘述。

决策树的剪枝

决策树生成算法递归地产生决策树，直到不能继续下去为止。这样产生的树很容易产生过拟合现象。过拟合的原因在于学习时过多地考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树。解决这个问题的办法是考虑决策树的复杂度，对已生成的决策树进行简化。

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

决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现。设树T的叶结点个数为|T|，t是树T的叶结点，该叶结点有\(N_t\)个样本点，其中k类的样本点有\(N_{tk}，k = 1,2,...,K，H_t(T)\)为叶结点t上的经验熵，\(\alpha \geq 0\)为参数，则决策树学习的损失函数可以定义为（1式）： \[ C_\alpha(T) = \sum^{|T|}_{t = 1}N_tH_t(T)+\alpha|T| \] 其中经验熵为（2式）： \[ H_t(T) = -\sum_k\frac{N_{tk} }{N_t}log\frac{N_{tk} }{N_t} \] 在损失函数中，将1式右端的第一项记作（3式）： \[ C(T) = \sum^{|T|}_{t = 1}N_tH_t(T)=-\sum^{|T|}_{t = 1}\sum^{K}_{k = 1}N_{tk}log\frac{N_{tk} }{N_t} \] 这时有（4式）： \[ C_\alpha(T) =C（T） + \alpha|T| \] 在4式中，C(T)表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，|T|表示模型复杂度，参数\(\alpha \geq 0\)控制两者之间的影响。较大的\(\alpha\)促使选择较简单的模型树，较小的则是促使选择较复杂的模型。\(\alpha = 0\)意味着只考虑模型与训练数据的拟合程度，不考虑模型的复杂度。

剪枝，就是当\(\alpha\)确定时，选择损失函数最小的模型，即损失函数最小的子树。决策树生成学习局部的模型，决策树剪枝学习整体的模型。

1式或4式定义的损失函数的极小化等价于正则化的极大似然估计。所以，利用损失函数最小原则进行剪枝就是用正则化的极大似然估计进行模型选择。

算法：

输入：生成算法产生的整个树T，参数\(\alpha\)；

输出：修剪后的子树\(T_\alpha\)。

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

（2）递归地从树的叶结点向上回缩。设一组叶结点回缩到其父结点之前与之后的整体树分别为\(T_B\)和\(T_A\)，其对应的损失函数值分别为\(C_\alpha(T_B)\)和\(C_\alpha(T_A)\)，如果\(C_\alpha(T_A) \leq C_\alpha(T_B)\)，则进行剪枝，即将父结点变为新的叶结点。

（3）返回（2），直到不能继续为止，得到损失函数最小的子树\(T_\alpha\)。

下周我们将对CART法构建决策树以及剪枝进行讲解，谢谢大家的观看！