掌握CART算法的决策树流程

什么是决策树算法CART？

CART（Classification and Regression Trees，分类回归树）是一种常用的决策树算法，能够根据数据特征分割出两个或多个类别，较为常见的应用是在分类或回归问题上。CART决策树算法是基于二叉树的结构构建的，通过树的每个内部节点将数据集分割成两个子集，直到所有数据集都属于同一类别。

CART算法流程

CART算法流程的核心是决策树的生成和剪枝过程。

决策树生成过程

CART算法的决策树生成过程采用递归地二分特征的方法，划分当前局部数据集。构建二叉树后，为每个内部节点设置对应的阈值，选取最佳的划分特征，使各子集之间的基尼系数（gini coefficient）最小。

1.选择最佳的划分特征

计算数据集每个特征与当前结点特征的基尼系数，选取基尼系数最小的特征作为本次划分所采用的特征。利用基尼系数来评估待选特征中哪一个对分类插入带来更大的影响，基尼系数越低说明带来的影响越大。

2.创建当前划分节点

将当前数据集按照选取的最佳特征划分成两个子集。

3.递归生成子树

根据各子集数据重复执行步骤1~3，进行递归子树生成，直到满足停止条件时，树的生成过程结束。

剪枝过程

对生成的决策树进行剪枝可以避免过拟合的问题。常用的两种剪枝方法是预剪枝和后剪枝。

1.预剪枝

预剪枝将未分类的项随机选择一部分用于验证分类器，验证结果不好则停止向下划分、进行剪枝，否则继续向下划分。预剪枝的优点在于递归终止条件较为明确，减少决策树复杂度。

2.后剪枝

后剪枝在整个决策树构建完毕后，自底向上进行梳理子树，考虑树的分支能否被剪掉以达到剪枝的目的。目的是为了减少复杂度，在不影响分类结果的前提下保持较好的泛化能力。

CART算法的应用

CART算法的应用非常广泛，如：对于网站广告精准投放，可以根据用户的搜索内容、浏览历史、年龄、性别等属性，对他们的关注点、兴趣点等作出概括，进而为其投放更加个性化的广告；又如：将其应用到选举预测领域，产品销售预测等等，实现更为精准、高效的预测。

CART在中小型数据处理任务上应用非常方便，能够很好地与现有的ML工具集成。CART也有自己的不足，缺点是算法对噪声比较敏感，在噪声较多的情形下泛化能力大打折扣；CART还倾向于产生不平衡树，树高度较高，预测效果不是特别理想。