1 ID3算法
ID——Iterative Dichotomiser(迭代二分器)
从根结点(root node)开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；在对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止，最后得到一个决策树。整个过程相当于用极大似然估计法进行概率模型的选择。
算法流程：
输入：训练数据集D，特征集A， 阈值\(\epsilon\)；
输出：决策树T。
-
首先判断T是否为单结点树：
- 若D中所有的实例都是同一类\(C_k\)，将类\(C_k\)作为该结点的类标记，返回单结点树T;
- 若\(A=\varnothing\)，将D中实例数最大的类\(C_k\)作为该结点的类标记，返回单结点树T；
-
若T非单结点树，则计算A中各特征对D的信息增益，选择信息增益最大的特征\(A_g\)；
-
如\(A_g\)的信息增益小于阈值\(\epsilon\)，则置T为单结点树，将D中实例数最大的类\(C_k\)作为该结点的类标记，返回单结点树T；
-
如\(A_g\)的信息增益大于等于阈值\(\epsilon\)，以\(A_g=a_i\)将D分割成若干非空子集\(D_i\)，将\(D_i\)中实例数最大的类作为标记，构建子结点，由结点和其子结点构成数T，返回T;
-
对第i个子结点，以\(D_i\)为训练集，以\(A-{A_g}\)为特征集，递归地调用步(1)~步(5)，得到子树\(T_i\)，返回\(T_i\)。
注：ID3算法只有树的生成，所以该算法生成的树容易产生过拟合；对可取值数目较多的属性有所偏好。
2 C4.5算法
C4.5算法与ID3算法相似，C4.5算法对ID3算法进行了改进。C4.5在生成的过程中，对取值数目较少的属性有所偏好，所以使用一种启发式方法，先从候选划分属性中找出信息增益高于平均水平的特征，再用信息增益比来选择特征。
算法流程：
输入：训练数据集D，特征集A， 阈值\(\epsilon\)；
输出：决策树T。
-
首先判断T是否为单结点树：
- 若D中所有的实例都是同一类\(C_k\)，将类\(C_k\)作为该结点的类标记，返回单结点树T;
- 若\(A=\varnothing\)，将D中实例数最大的类\(C_k\)作为该结点的类标记，返回单结点树T；
-
若T非单结点树，则计算A中各特征对D的信息增益，选择信息增益高于平均水平的特征，再用信息增益比选择其中最大的特征\(A_g\)；
-
如\(A_g\)的信息增益比小于阈值\(\epsilon\)，则置T为单结点树，将D中实例数最大的类\(C_k\)作为该结点的类标记，返回单结点树T；
-
如\(A_g\)的信息增益比大于等于阈值\(\epsilon\)，以\(A_g=a_i\)将D分割成若干非空子集\(D_i\)，将\(D_i\)中实例数最大的类作为标记，构建子结点，由结点和其子结点构成数T，返回T;
-
对第i个子结点，以\(D_i\)为训练集，以\(A-{A_g}\)为特征集，递归地调用步(1)~步(5)，得到子树\(T_i\)，返回\(T_i\)。
3 C5.0算法
C5.0算法是昆兰在C4.5算法的基础上提出的商用改进版本，目的是对含有大量数据的数据集进行分析。
与C4.5对比：
-
执行效率更高，内存使用更少；
-
生成的决策树更小，拥有更少的叶子结点；
-
支持Boosting技术，提高分类精度；
-
支持加权和成本敏感学习。
4 决策树的剪枝
决策树的剪枝（pruning）是将已生成的树进行简化的过程。具体的剪枝是从已生成的树上剪掉一些子树或叶结点，并将根结点或父结点作为新的叶结点，从而简化分类树模型，避免出现过拟合现象和模型过于复杂，同时提高分类树模型的泛化能力。
损失函数
决策树的剪枝往往通过极小化决策树整体的损失函数(loss function)或代价函数(cost function)来实现，其实就是用正则化的极大似然估计进行剪枝。
损失函数\(C_{\alpha}(T)\)：
\[C_{\alpha}(T)=\Sigma_{t=1}^{|T|}N_tH_t(T) + \alpha|T| \]叶结点t的经验熵：
\[H_t(T)=-\Sigma_{k=1}^K \frac{N_{tk}}{N_t}log\frac{N_{tk}}{N_t} \]令：\(C(T)=\Sigma_{t=1}^{|T|}N_tH_t(T)=-\Sigma_{t=1}^{|T|}\Sigma_{k=1}^{K} N_{tk}log\frac{N_{tk}}{N_t}\)
则：\(C_{\alpha}(T)=C(T)+\alpha T\)
式中：|T| —为树T的叶结点个数；\(N_t\) —为叶结点t的样本数；\(N_{tk}\) —为叶结点t的k类的样本数；\(H_t(T)\)—为叶结点t上的经验熵；\(\alpha\)—为选取的参数（正则化系数）。
要点：
-
\(C(T)\)表示模型对训练数据的预测误差，即拟合的程度；|T|表示模型复杂度，参数\(\alpha \geq 0\)控制着拟合和复杂度的平衡；当\(\alpha\)较大时，选择较简单的模型；当\(\alpha\)较小时，选择较复杂的模型；当\(\alpha\)=0时，只考虑拟合程度，不考虑复杂度。
-
剪枝：其实就是当\(\alpha\)确定时，选择损失函数最小的模型。当\(\alpha\)确定时，子树越大，拟合越好，但模型更复杂；相反，子树越小，模型复杂度越低，损失函数正好表示对两者的平衡。
-
决策树生成只考虑了通过提高信息增益（或信息增益比）对训练数据进行了更好的拟合；而决策树剪枝通过优化损失函数，考虑了减小模型复杂度；决策树生成学习局部的模型，而决策树剪枝学习整体的模型。
-
算法只需考虑两个树的损失函数的差，计算在局部进行，因此决策树的剪枝算法可以由一种动态规划的算法实现。
剪枝算法
输入：生成算法产生的整个树T，选择的参数\(\alpha\);
输出：修剪后的子树\(T_{\alpha}\)。
- 计算每个结点的经验熵；
- 递归地从树的叶结点向上回缩：设一组叶结点回缩到其父结点之前与之后的整体树分别为\(T_A\)和\(T_B\)，如果\(C_{\alpha}(T_B) \leq C_{\alpha}(T_A)\)，即回缩后的整体树的损失减小了，则进行剪枝，将父结点变成新的叶结点；
- 返回步骤（2），直到不能继续为止，得到损失最小的子树\(T_{\alpha}\)。
5 CART算法
分类与回归树（classification and regression tree, CART) 模型即可以用于分类也可以用于回归，由特征选择、决策树的生成、决策树的剪枝三部分组成。
CART假设决策树是二叉树，内部结点特征取值为“是”和“否”，左分枝取“是”，右分枝取“否”，递归地开展构建。对应回归树用平方误差最小化准则，对分类树用基尼指数（Gini index）最小化准则，进行特征选择，生成二叉树。
5.1 回归树的生成
CART生成的回归树也叫最小二乘回归树(least squares regression tree)，利用平均误差来表达回归树对于训练数据的预测误差。
要点：
-
设X与Y分别为输入和输出变量，Y为连续变量，对于给定训练数据集为：
\(D=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}\)
-
设输入空间划分为M个单位\(R_1,R_2,\cdots,R_M\)，每个单元\(R_m\)上有一个固定的输出值\(c_m\)，回归树模型为：\(f(x)=\Sigma_{m=1}^Mc_mI \quad (x \in R_m)\)
-
单元\(R_m\)上的\(c_m\)的最优值\(\hat c_m\)是\(R_m\)上的所有输入实例\(x_i\)对应的输出\(y_i\)的均值：
\(\hat c_m=avg(y_i | x_i \in R_m)\)
-
启发式方法划分输入空间：选择第j个变量\(x^{(j)}\)和它的取值s,作为切分变量(splitting variable)和切分点(splitting point),切分成两个区域：
\(R_1(j,s)=\{x|x^{(j)} \leq s\}\)和\(R_2(j,s)=\{x|x^{(j)} > s\}\)
-
寻找最优切变量j和最优切分点s，使切分空间\(R_1\)和\(R_2\)后，各空间中的每个输出值\(y_i\)与输出平均值\(c_m\)（m=1,2)的差值和最小，即求解以下公式最小值：
\(min_{(j,s)}[min_{(c_1)}\Sigma_{(x_i \in R_1(j,s))} (y_i-c_1)^2+min_{(c_2)}\Sigma_{(x_i \in R_2(j,s))} (y_i-c_2)^2]\)
-
对应固定输入变量j , 最优切分点s :
\(\hat c_1 = ave(y_i | x_i \in R_1(j,s))\)和\(\hat c_2 = ave(y_i | x_i \in R_2(j,s))\)
-
遍历所有输入变量，找到最优的切分变量j，构成一个对(j,s)，依次将输入空间划分两个区域，直到不能划分，生成一颗回归树。
算法流程：
- 输入：训练数据集D;
- 输出：回归树f(x).
在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉树决策树：
-
选择最优切分变量j 与切分点s，求解：
\(min_{(j,s)}[min_{(c_1)}\Sigma_{(x_i \in R_1(j,s))} (y_i-c_1)^2+min_{(c_2)}\Sigma_{(x_i \in R_2(j,s))} (y_i-c_2)^2]\)
遍历变量j，对固定的切分变量j扫描切分点s，选择使上式达到最小值的对(j,s)。
-
用选定的对(j,s)划分区域并决定相应的输出值：
-
继续对两个子区域调用步骤(1),(2)，直至满足停止条件。
-
将输入空间划分为M个区域\(R_1,R_2,\cdots,R_M\)，生成决策树：
\(f(x)=\Sigma_{m=1}^{M} \hat c_m I (x \in R_m)\)
5.2 分类树的生成
分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点。
基尼指数定义：从数据集D中随机抽取两个样本，其类别标记不一致的概率。
在分类问题中，假设有K个类，样本点属于第k类的概率为\(p_k\)，则概率分布的基尼指数为：
\[Gini(p)=\Sigma_{k=1}^Kp_k(1-p_k)=1-\Sigma_{k=1}^Kp_{k=1}^2 \]二分类概率分布的基尼指数：\(Gini(p)=2p(1-p)\)
给定样本集合D，其基尼指数为：
\[Gini(D)=1-\Sigma_{k=1}^K(\frac{|C_k|}{|D|})^2 \]式中：\(C_k\)为D中属于第k类的样本子集，K为类的个数。
如给定样本集合D被特征A的可能值a划分为\(D_1\)和\(D_2\)，则在特征A条件下，集合D的基尼指数为：
\[Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1) + \frac{|D_2|}{|D|}Gini(D_2) \]基尼指数\(Gini(D)\)表示集合D的不确定性，\(Gini(D,A)\)表示经\(A=a\)分割后集合D的不确定性，基尼指数越大，样本集合的不确定性就越大，与熵相似。
基尼指数和熵之半曲线很接近，都可以近似表示分类误差率。
算法流程：
输入：训练数据集D，停止计算的条件；
输出：CART决策树。
根据训练数据集，从根结点开始，递归地对每个结点进行以下操作，构建二叉决策树。
-
对结点的训练数据集D，计算现有特征对该数据集的基尼指数。如样本点对特征A=a的为“是”或“否”进行划分两个部分，计算A=a时的基尼指数；
-
计算所有可能的特征A以及它们所有可能的切分点a处的基尼指数，选择基尼指数最小的特征及其对应的切分点左右最优特征与最优切分点，从现结点生成两个子结点，同时将训练数据集特征分配到两个子结点中去；
-
对两个子结点递归地调用步骤（1）,（2），直至满足停止条件；
-
生成CART决策树。
算法停止条件：
- 结点的样本个数小于预定阈值；
- 样本集的基尼指数小于预定阈值；
- 没有更多特征。
5.3 CART剪枝
CART剪枝算法是从“完全生长”生成的决策树底端剪去一些子树，使决策树变小（模型变简单）, 从而能够对未知数据有更准确的预测（泛化能力）。
主要分两步：
（1）剪枝，生成子树序列：从生成算法产生的决策树\(T_0\)底端开始不断剪枝，直到\(T_0\)的根结点，形成一个子树序列{\(T_0,T_1,\cdots,T_n\)}。
子树的损失函数：\(C_{\alpha}(T)=C(T)+\alpha|T|\)
式中：T为任意子树，C(T)对训练数据的预测误差（如基尼指数），|T|为子树的叶结点个数，\(\alpha \geq 0\)为参数，\(C_{\alpha}(T)\)为参数是\(\alpha\)时的子树T的整体损失，参数\(\alpha\)权衡训练数据的拟合程度与模型的复杂度。
对应固定的\(\alpha\)，一定存在损失函数\(C_{\alpha}(T)\)最小的子树（最优），且是唯一的，表示为\(T_{\alpha}\)。当\(\alpha\)大时，最优子树\(T_{\alpha}\)偏小；当\(\alpha\)小时，最优子树\(T_{\alpha}\)偏大；当\(\alpha\)=0时，最优子树\(T_{\alpha}\)为整体树；当\(\alpha \rightarrow \infty\)时，根结点组成的单结点树是最优的。
-
从整体树\(T_0\)开始剪枝，对于\(T_0\)的任意内部结点t，以t为单结点树的损失函数为：
\(C_{\alpha}(t)=C(t)+\alpha\)
-
以t为根结点的子树\(T_t\)的损失函数为：
\(C_{\alpha}(T_{t})=C(T_{t})+\alpha |T_t|\)
-
当\(\alpha \rightarrow 0\)时 ：\(C_{\alpha}(T_t) < C_{\alpha}(t)\)，整体树最优；当\(\alpha\)逐步增大至\(\alpha=\frac{C(t)-C(T_{t})}{|T_t|-1}\) 时：\(C_{\alpha}(T_t) = C_{\alpha}(t)\)，此时\(T_t\)与t有相同的损失函数值，而t的结点少，因此t比\(T_t\)更可取，对\(T_t\)进行剪枝；当\(\alpha\)再增大，\(\alpha \rightarrow \infty\)，\(C_{\alpha}(T_t) > C_{\alpha}(t)\)，单结点树最优；
-
因此，需对整体树\(T_0\)的每一个结点t，计算：\(g(t)=\frac{C(t)-C(T_{t})}{|T_t| - 1}\)；g(t)表示剪枝后整体损失函数减少的程度，在\(T_0\)中减去g(t)最小的\(T_t\)，将得到得子树作为\(T_1\)，同时将最小的\(g(t)\)设为\(\alpha_1\)，\(T_1\)为区间\([ \alpha_1, \alpha_2)\)的最优子树。
-
一直递归地剪枝下去，直到根结点，在这一过程中，\(\alpha\)的值不断增加（\(0=\alpha_0 < \alpha_1 < \cdots < \alpha_n < + \infty\)），产生一系列的区间[\(\alpha_{i},\alpha_{i+1}\))，\(i=0,1,\cdots,n\)，并存在最优子树序列{\(T_0,T_1,\cdots,T_n\)}与之对应。
（2）交叉验证，选取最优子树\(T_{\alpha}\)：利用独立的验证数据集，测试子树序列\(T_0,T_1,\cdots,T_n\)中各棵子树的平均误差或基尼指数；平均误差或基尼指数最小的决策树被认为是最优的决策树；每一棵子树\(T_1,\cdots,T_n\)都对应着一次参数\(\alpha_1,\alpha_2, \cdots, \alpha_n\).所以当最优子树\(T_{\alpha}\)确定时，对应的\(\alpha_k\)也确定了，即得到最优决策树\(T_{\alpha}\).
算法流程：
输入：CART算法生成的决策树\(T_0\)；
输出：最优决策树\(T_{\alpha}\)。
-
设k=0, T=\(T_0\);
-
设\(\alpha=+\infty\);
-
自下而上对各内部结点t计算\(C(T_{t})\)，\(|T_{t}|\)以及
式中：\(T_t\)表示以t为根结点的子树，\(C(T_t)\)是对训练数据的预测误差，\(|T_t|\)是\(T_t\)的叶结点个数。
-
自上而下访问内部结点t，如果有\(g(t)=\alpha\)，进行剪枝，并对叶结点t以多数表决法决定其类，得到树T；
-
设\(k = k + 1, \alpha_k = \alpha, T_k = T\)；
-
如果T不是由根结点单独构成的树，则回到步骤4 （自上而下访问）；
-
采用交叉验证法在子树序列\(T_0,T_1,\cdots,T_n\)中选取最优子树\(T_{\alpha}\)。
scikit-learn 使用的CART算法的优化版本，但是不支持分类变量。
6 计算案例
样本数据集D
| ID | 年龄 | 有工作 | 有自己的房子 | 信贷情况 | 类别 |
|---|---|---|---|---|---|
| 1 | 青年 | 否 | 否 | 一般 | 否 |
| 2 | 青年 | 否 | 否 | 好 | 否 |
| 3 | 青年 | 是 | 否 | 好 | 是 |
| 4 | 青年 | 是 | 是 | 一般 | 是 |
| 5 | 青年 | 否 | 否 | 一般 | 否 |
| 6 | 中年 | 否 | 否 | 一般 | 否 |
| 7 | 中年 | 否 | 否 | 好 | 否 |
| 8 | 中年 | 是 | 是 | 好 | 是 |
| 9 | 中年 | 否 | 是 | 非常好 | 是 |
| 10 | 中年 | 否 | 是 | 非常好 | 是 |
| 11 | 老年 | 否 | 是 | 非常好 | 是 |
| 12 | 老年 | 否 | 是 | 好 | 是 |
| 13 | 老年 | 是 | 否 | 好 | 是 |
| 14 | 老年 | 是 | 否 | 非常好 | 是 |
| 15 | 老年 | 否 | 否 | 一般 | 否 |
5.1 ID.3 算法生成决策树
分别以\(A_1,A_2,A_3,A_4\)表示年龄、有工作、有自己的房子和信贷情况4个特征，则：
- 计算经验熵H(D) :
- 计算经验条件熵H(D|A)：
- 计算信息增益：
-
比较各特征的信息增益，可知特征\(A_3\)（有自己的房子）的信息增益值最大，取\(A_3\)作为根结点最优特征。它将训练数据集D划分为两个子集\(D_1,(A_3="是")\) 和\(D_2,(A_3="否")\)，\(D_1\)只有标记类别为同一类的样本点，则它成为一个叶结点，类别标记为“是”；\(D_2\)则需进行下一步选择判断。
-
对\(D_2\)计算经验熵：\(H(D_2)=0.918\)
同时计算各特征的经验条件熵：
\(H(D_2|A_1)=0.667 、H(D_2|A_2)=0、H(D_2|A_4)=0.444\)
各特征的信息增益为：
-
选择信息增益最大的特征\(A_2\)(有工作)作为结点\(D_2\)的最优特征。
- 从\(D_2\)根据特征\(A_2=“是”\)引出子结点，包含3个样本，均为同一类，则该子结点为一个叶结点，类标记为“是”；
- 从\(D_2\)根据特征\(A_2=“否”\)引出子结点，包含6个样本，均为同一类，则该子结点为一个叶结点，类标记为“否”。
-
最终根据两个特征\(A_3\)和\(A_2\)生成决策树如下：
注：C4.5决策树的生成过程与同ID3的类似，只是将信息增益变为信息增益比。
5.2 CART算法生成决策树
设\(A_1,A_2,A_3,A_4\)表示年龄、有工作、有自己的房子和信贷情况4个特征，并用1,2,3表示年龄的值为青年、中年和老年，以1,2表示有工作和有自己的房子的值为是和否，以1,2,3表示信贷情况的值为非常好、好和一般。
- 计算所有特征\(A_1,A_2,A_3,A_4\)基尼指数：
局部：\(Gini(D,A_1=1)\),\(Gini(D,A_1=3)\)都是最小，则\(A_1=1,A_1=3\) 为 \(A_1\)最优切分点；,\(Gini(D,A_4=3)\)最小，则\(A_4=3\) 为 \(A_4\)最优切分点。
-
在特征\(A_1,A_2,A_3,A_4\)基尼指数中，\(Gini(D,A_3=1)=0.27\)最小，所以选择\(A_3\)为最优特征，\(A_3=1\)为其最优切分点，把根结点D切分为两个子集\(D_1,(A_3=1)\) 和\(D_2\) ，\(D_1\)只有标记类别为同一类的样本点，则它成为一个叶结点，类别标记为“是”；\(D_2\)则需进行下一步选择判断。
-
\(D_2\)结点依照步骤1中的方法计算\(A_1,A_2,A_4\)的基尼指数\(Gini(D_2,A_1)、Gini(D_2,A_2)、Gini(D_2,A_4)\)，最终计算得的值最小，为\(D_2\)最优切分点，最后得到的下一步结点都是叶结点。
注：在本训练数据集中，CART与ID3算法生成的决策树一样,，只是将信息增益变为基尼指数。
$ $
参考资料
- https://scikit-learn.org/stable/modules/tree.html
- 李航 —— 《统计学习方法 第2版》