【机器学习入门】决策树算法（四）：CART算法（Classification and Regression Tree）

CART算法的简介：

CART（Classification and Regression Tree）算法，即分类回归树算法，也是决策树构建的一种常用算法，CART的构建过程采用的是二分循环分割的方法，每次划分都把当前样本集划分为两个子样本集，使决策树中的节点均有两个分支，显然，这样就构造了一个二叉树。

如果分支属性有多于两个取值，在分裂时会对属性值进行组合，选择最佳的两个组合分支。假设某属性存在q个可能取值，那么以该属性作为分支属性，生成两个分支的分裂方法共有（2q−1−1）种。

度量指标：

CART算法在分支处理中分支属性的度量指标是Gini。设S为大小为n的样本集，其分类属性有m个不同取值，用来定义m个不同分类Ci(i=1，2，…，m)，则其Gini指标的计算公式为：

在CART算法中，针对样本集S，选取属性A作为分支属性，将样本集S分裂为A=a1的子样本集S1，与其余样本组成的样本集S2，则在此情况下的Gini指标为：

CART算法的优缺点：

优点：

• CART算法可以处理数值型和分类型数据，不需要进行数据预处理；

• CART算法生成的决策树可以直观的解释和可视化，易于理解；

• CART算法可以处理大规模数据集；

• CART算法可以处理高维数据；

• CART算法的分类和回归能力都很强。

缺点：

• CART算法是一种贪心算法，可能会导致局部最优解，不能保证全局最优解；

• CART算法对于噪声和异常值敏感；

• CART算法容易过拟合，需要采用剪枝等措施来避免过拟合；

• CART算法只能生成二叉树，无法处理多分类问题。