机器学习--决策树理论知识（三）
机器学习 | 决策树理论知识（三）
这周我们将要学习使用CART算法进行决策树的生成和剪枝。
CART是一种采用基尼指数为标准的划分方法，在学习CART算法之前，我们要先知道什么是基尼指数。
基尼指数
在分类问题中，假设数据包括有K个类别，样本点属于第k类的概率为\(p_k\)，则概率分布的基尼指数定义为： \[ Gini(p)=\sum^K_{k = 1}p_k(1-p_k) = 1-\sum^K_{k=1}p_k^2-------(1) \] 因此，对于给定的样本集合D，其基尼指数为： \[ Gini(D) = 1-\sum^K_{k = 1}(\frac{|C_k|}{|D|})^2-------(2) \] 其中，\(C_k\)是D中属于第k类的样本子集，K是类别的个数。
如果样本集合D根据特征A是否取某一可能值a被分割成\(D_1, D_2\)两个部分，即 \[ D_1 = \lbrace(x,y)\in D|A(x)= a\rbrace,D_2 = D-D_1 \] 则在特征A的条件下，集合D的基尼指数定义为（类似于条件熵的感觉）： \[ Gini(D,A) = \frac{|D_1|}{|D|}Gini(D_1) + \frac{|D_2|}{|D|}Gini(D_2)-------(3) \] 基尼指数Gini(D)表示集合D的不确定性，即表示经A = a分割后集合D的不确定性。基尼指数越大，样本集合的不确定性也就越大，这点与信息熵相似。
CART算法
分类与回归算法（Classification and Regression Tree），即可以用于分类也可以用于回归，它是应用最为广泛的决策树学习方法之一。CART假设决策树是二叉树，内部结点特征的取值均为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价与递归地二分每个特征，将输入空间即特征空间划分为有限个单元。
生成算法
输入：训练数据集D，停止计算条件；
输出：CART决策树
根据训练集，从根节点开始，递归地对每个节点进行如下操作，构建二叉决策树：
<1> 设节点的训练集为D，利用公式(2)计算现有特征对该数据集的基尼指数。此时，对于每一个特征A，对其可能的每一个值a，根据样本点对A = a的测试为“是”或“否”将D分割成\(D_1,D_2\)两个部分，利用公式(3)计算时A = a的基尼指数；
<2> 在所有可能的特征A以及它们所有可能的切分点a中，选择基尼指数最小的特征作为划分标准将原有数据集划分为两个部分，并分配到两个子节点中去；
<3> 对两个子节点递归的调用<1>、<2>步骤，直到满足停止条件；
<4> 生成CART决策树
其中，算法停止计算的条件是：节点中的样本点个数小于预定阈值，或样本集的基尼指数小于预定阈值（也就是说此时样本基本属于同一类），或者没有更多特征。
剪枝算法
上周的文章中我们说到，复杂的决策树会导致过拟合问题，所以要进行剪枝处理。CART剪枝算法由两部分组成：
<1> 首先从之前生成的决策树\(T_0\)底端开始不断剪枝，直到\(T_0\)的根结点，形成一个子序列\(\lbrace T_0,T_1,...,T_n\rbrace\)；
<2> 然后通过交叉验证对这一子序列进行测试，从中选择最优的子树。
CART剪枝算法
输入：CART算法生成的决策树\(T_0\)；
输出：最优决策树\(T_\alpha\)
（1）设k = 0，T = \(T_0\)
（2）设\(\alpha = +\)∞
（3）自下而上地对各内部节点t计算\(C(T_t),|T_t|\)以及 \[ g(t) = \frac{C(t)-C(T_t)}{|T_t|-1} \]
\[ \alpha = min(\alpha,g(t)) \]
这里，\(T_t\)表示以t为根结点的子树，\(C(T_t)\)是对训练数据的预测误差，\(|T_t|\)是\(T_t\)的叶结点个数
（4）对\(g(t) = \alpha\)的内部节点t进行剪枝，并对叶结点t以多数表决法决定其类，得到树T
（5）设\(k = k+1,\alpha_k = \alpha,T_k = T\)
（6）如果\(T_k\)不是由根结点及两个叶结点构成的树，则回到步骤（3）；否则令\(T_k = T_n\)
（7）采用交叉验证法在子树序列\(T_0,T_1,T_2,...,T_n\)中选取最优子树\(T_\alpha\)
问题的关键在于该如何来剪枝生成这么一个子序列。
<1> 剪枝，形成一个子序列
在剪枝过程中，计算子树的损失函数： \[ C_\alpha(T) = C(T) + \alpha|T|-------(4) \] 其中，T为任意子树，C(T)为对训练集的预测误差，| T |为子树的叶节点个数，\(\alpha \ge 0\)为参数。需要指出的是不同与之前ID3和C4.5中剪枝算法的\(\alpha\)，前者是人为给定的，而此处则是通过计算得到，具体见后面。
具体地，从整体树\(T_0\)开始剪枝。对\(T_0\)的任意内部节点t，以t为根节点子树\(T_t\)（可以看作是剪枝前）的损失函数是: \[ C_\alpha(T_t) = C(T_t) + \alpha|T_t|-------(5) \] 以t为单结点树（可以看作是剪枝后）的损失函数是： \[ C_\alpha(t) = C(t) + \alpha · 1-------(6) \] ①当\(\alpha = 0\)或极小的时候，有不等式： \[ C_\alpha(T_t) < C_alpha(t)-------(7) \] 不等式成立的原因是因为，当\(\alpha = 0\)或者极小的时候，起决定作用的就是预测误差\(C(t),C(T_t)\)，而模型越复杂其训练误差总是越小的，因此不等式成立。
②当\(\alpha\)增大时，在某一\(\alpha\)有 \[ C_\alpha(T_t) = C_\alpha(t)-------(8) \] 等式成立的原因是，当\(\alpha\)慢慢增大时，就不能忽略模型复杂度所带来的影响（也就是式子(4)第二项。但由于相同取值的\(\alpha\)对于式子(5)(6)所对应模型的惩罚力度不同（剪枝前的惩罚力度更大），因此尽管式子(5)(6)所对应的模型复杂度均在减小（误差变大），但是(5)较小得更快（误差变大得更快），所以总有个时候等式会成立。
③当\(\alpha\)再增大时，不等式(8)反向。因此，当\(C_\alpha(T_t) = C_\alpha(t)\)，有\(\alpha = \frac{C(t)-C(T_t)}{|T_t|-1}\)，此时的子树\(T_t\)和单节点树t有相同的损失函数值，但t的节点少，模型更简单，因此t比\(T_t\)更可取，即对\(T_t\)进行剪枝。（此时的\(\alpha\)是通过\(C_\alpha(T_t) = C_\alpha(t)\)）计算得到）
为此，对决策树\(T_0\)中每一个内部节点t来说，都可以计算 \[ g(t) = \frac{C(t)-C(T_t)}{|T_t|-1}-------(9) \] 它表示剪枝后整体损失函数减少的程度。因为每个g(t)背后都对应着一个决策树模型，而不同的g(t)则表示损失函数变化的不同程度。接着，在树\(T_0\)中减去g(t)最小的子树\(T_t\)，将得到的子树作为\(T_1\)。如此剪枝下去，直到得到根节点。
如上图，对于树T来说，其内部可能的节点t有\(t_0,t_1,t_2,t_3\)；\(t_i\)表示其中任意一个。因此我们便可以计算得到\(g(t_0),g(t_1),g(t_2),g(t_3)\)，也即对应的\(\alpha_0,\alpha_1,\alpha_2.\alpha_3\)。从上面的第③种情况我们可以知道，g(t)是根据公式(9)所计算得到，因此这四种情况下\(t_i\)比\(T_{t_i}\)更可取，都满足剪枝。但是由于以\(t_i\)为根节点的子树对应的复杂度各不相同，也就意味着\(\alpha_i \neq \alpha_j,(i,j = 0,1,2,3;i\ne j)\)，即\(\alpha_i,\alpha_j\)存在着大小关系。又因为我们知道：当\(\alpha\)大的时候，最优子树\(T_\alpha\)偏小；当\(\alpha\)小的时候，最优子树\(T_\alpha\)偏大；且子树偏大意味着拟合程度更好。因此，在都满足剪枝的条件下，选择拟合程度更高的子树当然是最好的选择。所有选择减去其中g(t)最小的子树。
在得到子树\(T_1\)后，再通过上述步骤对\(T_1\)进行剪枝得到\(T_2\)。如此剪枝下去直到得到根节点，此时我们便得到了子树序列\(T_0,T_1,...,T_n\)。
<2> 交叉验证选择最优子树\(T_\alpha\)
通过第<1>步我们便可以得到一系列的子树序列\(T_0,T_1,...,T_n\)，然后便可以通过交叉验证来选取最优决的策树\(T_\alpha\)。
最后，通过sklearn来完成对于CART分类树的使用也很容易，只需要将类DecisionTreeClassifier()中的划分标准设置为criterion="gini"即可，
以上便是CART算法生成决策树和剪枝的内容，谢谢大家的观看！