Decision Tree Principles and Implementation (Part II) -- CART Algorithm and Pruning

本节将重点阐述决策树中应用最为广泛的CART方法及其剪枝策略，主要参考资料。

在上一节中，我们介绍了ID3算法及其改进版本C4.5算法。针对C4.5算法，我们也指出了其存在的局限性，尤其是在处理连续型数据方面存在不足。相比之下，当前最为常见的CART方法不仅适用于回归问题，也可用于分类任务，在sklearn包中的决策树实现也采用了这一方式。

特征选择方法

在先前的讨论中，无论是ID3算法还是C4.5算法，我们均采用“熵”作为衡量特征选择的标准。然而，计算熵的过程涉及大量对数运算，是否还有其他可行的特征选择方式呢？答案是明确的。在此引入统计学中的基尼系数作为替代方案，该系数用于衡量模型的不纯度。基尼系数数值越低，表明模型的不纯度越小，所选特征的质量越高。这一特性与信息增益（比）呈现出相反的趋势。

在处理分类问题时，若存在K个类别，其中第k个类别的概率为p_k，则基尼系数可表示为：

从直观角度理解，基尼系数可以被视为某种属性导致分类错误的概率指标。

对于给定的数据集D，假设有若干类别，其中第k个类别的样本数量为C_k，那么该数据集对应的基尼系数表达式如下：

后续我们将构建二叉树结构，在仅包含两个节点的情况下，其计算公式可简化为：

二叉树