题目标题

1 CART树是如何做分类的,是如何做回归的,是如何处理多分类的?

难度:中级

机器学习 算法
参考解析

特征选择

特征选择决定了使用哪些特征来做判断。在训练数据集中,每个样本的属性可能有很多个,不同属性的作用有大有小。因而特征选择的作用就是筛选出跟分类结果相关性较高的特征,也就是分类能力较强的特征。

在特征选择中通常使用的准则是:信息增益。

决策树生成

选择好特征后,就从根节点触发,对节点计算所有特征的信息增益,选择信息增益最大的特征作为节点特征,根据该特征的不同取值建立子节点;对每个子节点使用相同的方式生成新的子节点,直到信息增益很小或者没有特征可以选择为止。

决策树剪枝

剪枝的主要目的是对抗「过拟合」,通过主动去掉部分分支来降低过拟合的风险。

ID3 算法

ID3 是最早提出的决策树算法,他就是利用信息增益来选择特征的。

C4.5 算法

他是 ID3 的改进版,他不是直接使用信息增益,而是引入“信息增益比”指标作为特征的选择依据。

CART(Classification and Regression Tree)

这种算法即可以用于分类,也可以用于回归问题。CART 算法使用了基尼系数取代了信息熵模型。

算法输入是训练集D,基尼系数的阈值,样本个数阈值。

  1. 输出是决策树T
  2. 我们的算法从根节点开始,用训练集递归的建立CART树。
  3. 1) 对于当前节点的数据集为D,如果样本个数小于阈值或者没有特征,则返回决策子树,当前节点停止递归。
  4. 2) 计算样本集D的基尼系数,如果基尼系数小于阈值,则返回决策树子树,当前节点停止递归。
  5. 3) 计算当前节点现有的各个特征的各个特征值对数据集D的基尼系数,对于离散值和连续值的处理方法和基尼系数的计算见第二节。缺失值的处理方法和上篇的C4.5算法里描述的相同。
  6. 4) 在计算出来的各个特征的各个特征值对数据集D的基尼系数中,选择基尼系数最小的特征A和对应的特征值a。根据这个最优特征和最优特征值,把数据集划分成两部分D1D2,同时建立当前节点的左右节点,做节点的数据集DD1,右节点的数据集DD2.
  7. 5) 对左右的子节点递归的调用1-4步,生成决策树。
  8. 对于生成的决策树做预测的时候,假如测试集里的样本A落到了某个叶子节点,而节点里有多个训练样本。则对于A的类别预测采用的是这个叶子节点里概率最大的类别。

CART回归树构建过程如下