一、CART 算法介绍
前面我们已经学习了 算法与 算法,并且也提到了算法的一些不足,比如 算法,模型它使用了较为复杂的多叉树,只能处理分类问题而不能处理回归问题等。对于这些问题,CART(Classification and Regression Tree)算法做了很多改进,它既可以做分类也可以做回归。
二、CART 分类树
(1)特征选择
我们知道, 算法使用信息增益来作为节点划分时的属性选择标准,而 算法使用信息增益率来作为节点划分时的属性选择标准,但是二者均是基于熵模型的,因此会涉及到大量的对数运算。所以,CART 分类算法使用了基尼系数作为属性选择的标准,在保留熵模型大部分优点的情况下也简化了模型。
(2)特征处理
A. 连续型变量。CART 分类树对于连续变量的处理思想基本与 算法一致,都是将连续型变量进行离散化处理,唯一的区别在于选择划分点时的度量方式不同,也就是说,对于切分后得到的个点,CART 分类算法会分别计算各个点作为二元分类点时的基尼系数,然后选择基尼系数最小的点作为该连续特征的离散化分类点。
B. 离散型变量。对于离散型变量,CART 分类树的基本思想是将其进行不停的二分。
回忆一下 算法与 算法,假设属性A被选取进行节点划分,其取值有3个类别A1、A2、A3,此时,我们就会建立一个三分叉的节点,最后生成一棵多叉树。而CART 分类树算法则不同,还是上面的例子,CART 分类树会考虑将属性A分为{A1;A2、A3}、{A2;A1、A3}、{A3;A1、A2},然后以基尼系数最小的组合进行节点划分,比如选择了{A3;A1、A2}建立二叉树节点,那么,实际上A1、A2的取值是没有被分开的,所以在后续的节点建立过程中,还可以继续选择属性A来划分A1和A2,而在 算法与 算法中,每个离散属性只会参与一次节点划分过程。
三、CART回归树
(1)概念理解
首先,我们要明白,什么是分类树,什么是回归树,其实二者的区别主要在于样本的输出,如果样本输出是离散值,那么就是分类树;如果样本输出是连续值,那么就是回归树。
(2)差异对比
CART 回归树与CART 分类树的建立算法大多数的相同的,这里我们主要来看下二者的区别,除了概念上的不同,还包括以下两点:
A. 连续值的处理方法不同
我们知道,CART 分类树采用基尼系数来衡量连续属性各个划分点的优劣,比较适合做分类,对于CART 回归模型而言,通常采用如下式子来选取属性和划分点:
其中,为D1数据集的样本输出均值,为D2数据集的样本输出均值,和分别代表属性和切分点。只要遍历所有属性的所有切分点,就能找到最优的切分属性和切分点,最终得到一棵回归树。
B. 预测方式不同
对于预测方式,我们知道CART 分类树采用叶节点中概率最大的类别作为当前节点的预测类别,例如,在某一叶节点中有50%的样本属于类别1,30%的样本属于类别2,20%的样本属于类别3,那么,如果新样本落到该叶节点,我们就说新样本属于类别1。但是,对于回归树而言,输出的不是类别,故它采用的是最终叶节点的均值或中位数作为预测结果。
请根据本节内容回答以下问题:
决策树的三种主要生长算法有哪些?