第8.8节 从零实现CART算法
各位朋友大家好，欢迎来到月来客栈，我是掌柜空字符。
本期推送内容目录如下，如果本期内容对你有所帮助，欢迎点赞、转发支持掌柜！
8.8 从零实现CART算法 8.8.1 连续型特征生成示例 8.8.2 连续型特征剪枝示例 8.8.3 节点定义实现 8.8.4 基尼指数实现 8.8.5 决策树构建实现 8.8.6 决策树预测实现 8.8.7 决策树剪枝实现 8.8.8 使用示例 8.8.9 小结 引用
8.8 从零实现CART算法
在上一节内容中，我们已经详细介绍了CART分类树的构建原理和剪枝过程。在本节内容中，将开始介绍如何从零开始编码实现一个简易版的CART分类树。同时，由于在实际场景中数据集的特征维度大多都是连续型的特征变量，因此需要对其进行离散化处理，后续也将以连续型特征为例进行编码实现。具体离散化方法见第8.2.5节内容，这里不再赘述。
下面，我们将直接通过表8-6中的样本数据来详细介绍在CART分类树中如何离散化连续型特征并构造相应的决策树。
8.8.1 连续型特征生成示例
在处理连续型特征变量时，第一步便是需要将各个维度的特征进行离散化，然后再根据离散化后的区间来对特征进行判断。具体地，表8-6中对应的3个特征在离散化后各特征的取值分割点分别为： ， 、。
由表8-6中的数据可知，根据式(8.35)可得，此时的其基尼不纯度为
并且对于特征来说，根据其取值是否满足条件，可以将原始样本划分为和两个部分。由式(8.37)得
同理，对于特征来说，根据其取值是满足条件，也可以将原始样本划分为和两个部分。此时有
进一步，对于特征来说，根据其取值是否分别满足条件和，每一次也可将原始样本划分为和两个部分。此时有
注意：此时每次划分时都是将样本集合划分为两个部分，即和。
由以上计算结果可知，使用时对样本集合进行划分所得到的基尼不纯度最小。故，根节点应该以是否成立来进行分割，如图8-20所示（在每个节点中，第1行表示当前节点的划分特征维度以及样本的索引，第2行分别表示判断区间和每个类别中的各个样本的数量）。
从图8-20可以看出，根据特征是否存满足条件可以将原始样本划分为和两个部分。经过这次划分后，原始的样本集合就被特征“有工作”分割成了左右两个部分。接下来，再对左右两个集合递归的进行上述步骤。
1. 对于左子树来说
在特征中有
在特征中有
此时，基尼指数最小，故选择作为判断区间，此时划分结果如表8-7所示。
表 8-7.信用卡审批数据划分结果表
2. 对于右子树来说
在特征中有
在特征中有
此时，基尼指数最小，故选择 作为判断区间，此时划分结果如表8-8所示。
表 8-8. 信用卡审批数据划分结果表
进一步，根据表8-7和表8-8的划分结果便可以得到如图8-21所示的结果。
根据图8-21可知，此时对于集合来说其只有一个类别，因此停止划分。
3. 对于集合来说
在特征中有
此时，基尼指数最小，故选择作为判断区间。
4. 对于集合来说
在特征中有
此时，基尼指数最小，故选择作为判断区间。当然，对于特征来说其只有一个取值区间，所以也可以不用计算。
对于集合来说其只有一个类别，所以也停止划分。这样便可以得到如表8-9所示的划分结果。
表 8-9. 信用卡审批数据划分结果表
最终，根据表8-9便可得到如图8-22所示的决策树。
这里值得一提的是，由于划分方式的不同，所以图8-22中的结果与图8-13中的结果略有差异。
为你认可的知识付费，欢迎订阅本专栏阅读更多优质内容！