CART(Classification And Regression Trees, 分类回归树)算法, CART 是一个独立于其他经典决策树算法的算法, 所以导致 CART 相对来说较为复杂. 因为它不仅仅可以作为分类树, 还可以作为回归树. 采用的是 Gini 指数 (选 Gini 指数最小的特征 s) 作为分裂标准, 同时它也是包含后剪枝操作. ID3 算法和 C4.5 算法虽然在对训练样本集的学习中可以尽可能多地挖掘信息, 但其生成的决策树分支较大, 规模较大. 为了简化决策树的规模, 提高生成决策树的效率, 就出现了根据 GINI 系数来选择测试属性的决策树算法 CART.
一, 基尼指数
定义: 基尼指数(基尼不纯度): 表示在样本集合中一个随机选中的样本被分错的概率.
注意: Gini 指数越小表示集合中被选中的样本被分错的概率越小, 也就是说集合的纯度越高, 反之, 集合越不纯.
即 基尼指数(基尼不纯度)= 样本被选中的概率 * 样本被分错的概率
公式说明
pk 表示选中的样本属于 k 类别的概率, 则这个样本被分错的概率是(1-pk)
样本集合中有 K 个类别, 一个随机选中的样本可以属于这 k 个类别中的任意一个, 因而对类别就加和
当为二元切分法时, Gini(P) = 2p(1-p), 它易于对树构建过程进行调整以处理连续性特征.
二, 基于特征 A 划分样本集合 D 之后的基尼指数
需要说明的是 CART 是个二叉树, 也就是当使用某个特征划分样本集合只有两个集合: 1. 等于给定的特征值的样本集合 D1 , 2. 不等于给定的特征值的样本集合 D2
实际上是对拥有多个取值的特征的二值处理.
举个栗子:
假设现在有特征 "学历", 此特征有三个特征取值: "本科","硕士", "博士",
当使用 "学历" 这个特征对样本集合 D 进行划分时, 划分值分别有三个, 因而有三种划分的可能集合, 划分后的子集如下:
1. 划分点: "本科", 划分后的子集合 : {本科},{硕士, 博士}
2. 划分点: "硕士", 划分后的子集合 : {硕士},{本科, 博士}
3. 划分点: "硕士", 划分后的子集合 : {博士},{本科, 硕士}
对于上述的每一种划分, 都可以计算出基于 划分特征 = 某个特征值 将样本集合 D 划分为两个子集的纯度:
因而对于一个具有多个取值 (超过 2 个) 的特征, 需要计算以每一个取值作为划分点, 对样本 D 划分之后子集的纯度 Gini(D,Ai),(其中 Ai 表示特征 A 的可能取值)然后从所有的可能划分的 Gini(D,Ai)中找出 Gini 指数最小的划分, 这个划分的划分点, 便是使用特征 A 对样本集合 D 进行划分的最佳划分点.
求基尼系数的含义: 基尼系数宏观表达的是描述一个集合的混乱程度.
基尼指数越大, 表示这个样本集合 D 越混乱. 这和熵的作用有些类似, 但这仅仅是一个指数, 能够判断大小, 但不能像熵一样线性的量化集合中的混乱程度.
---
三, CART 分类生成算法
输入: 训练数据集 D, 停止计算的条件;
输出: CART 决策树;
根据训练数据集, 从根结点开始, 递归地对每个结点进行以下操作, 构建二叉决策树:
设结点的训练数据集为 D, 计算现有特征对该数据集的基尼指数. 此时, 对每一个特征 A, 对其可能取的每个值 a, 根据样本点对 A=a 的测试为 "是" 或 "否" 将 D 分割成 D1 和 D2 两部分, 之后计算基尼指数.
在所有可能的特征 A 以及它们所有可能的切分点 a 中, 选择基尼指数最小的特征及其对应的切分点作为最有特征与最优切分点. 依照最优特征与最优切分点, 从现有结点生成两个子节点, 将训练数据集按照特征分配到两个子节点中去.
对两个子结点递归地调用两个子结点, 将训练数据集按特征分配到两个子节点中去.
生成 CART 决策树.
下面用一个案例理解计算过程:
四, CART 回归树算法
CART 生成回归树的算法是用来根据已有数据生成一个回归树, 具体算法如下:
这个算法比前面的那些算法要更加复杂一点, 有很多公式. 要想理解这个算法的作用, 我们得先从感性上理解这个算法是做什么的.
我们考虑最简单的最小二乘回归, CART 要求我们将所有输入数据都当作在二维的平面上若干个数据点. 以 x 轴为划分依据(也就是最后的回归树的分界线是 x 的值, x 大于或小于某个值会判断成什么).
1. 先自己认定一组切分点(一般认为是两个点 x 值的中点). 然后计算这一组切分点中每一个切分点对应的均方误差, 找到均方误差最小的那个切分点作为一个节点;
2. 这个切分点已经将整个空间划为两块(我们只考虑最简单的二维, 所以一个点代表一条垂直于 x 轴的线), 我们分别对这两块继续计算均方误差, 找到下一个节点;
3. 直到总的均方误差达到要求为止.
举个栗子:
科普
1. 信息增益( ID3 算法 )
定义: 以某特征划分数据集前后的熵的差值
在熵的理解那部分提到了, 熵可以表示样本集合的不确定性, 熵越大, 样本的不确定性就越大. 因此可以使用划分前后集合熵的差值来衡量使用当前特征对于样本集合 D 划分效果的好坏.
划分前样本集合 D 的熵是一定的 ,entroy(前),
使用某个特征 A 划分数据集 D, 计算划分后的数据子集的熵 entroy(后)
信息增益 = entroy(前) - entroy(后)
公式:
做法: 计算使用所有特征划分数据集 D, 得到多个特征划分数据集 D 的信息增益, 从这些信息增益中选择最大的, 因而当前结点的划分特征便是使信息增益最大的划分所使用的特征.
信息增益的理解:
对于待划分的数据集 D, 其 entroy(前)是一定的, 但是划分之后的熵 entroy(后)是不定的, entroy(后)越小说明使用此特征划分得到的子集的不确定性越小 (也就是纯度越高), 因此 entroy(前) - entroy(后) 差异越大, 说明使用当前特征划分数据集 D 的话, 其纯度上升的更快. 而我们在构建最优的决策树的时候总希望能更快速到达纯度更高的集合, 这一点可以参考优化算法中的梯度下降算法, 每一步沿着负梯度方法最小化损失函数的原因就是负梯度方向是函数值减小最快的方向. 同理: 在决策树构建的过程中我们总是希望集合往最快到达纯度更高的子集合方向发展, 因此我们总是选择使得信息增益最大的特征来划分当前数据集 D.
缺点: 信息增益偏向取值较多的特征
原因: 当特征的取值较多时, 根据此特征划分更容易得到纯度更高的子集, 因此划分之后的熵更低, 由于划分前的熵是一定的, 因此信息增益更大, 因此信息增益比较 偏向取值较多的特征.
2. 信息增益比( C4.5 算法 )
信息增益比 = 惩罚参数 * 信息增益
公式:
注意: 其中的 HA(D), 对于样本集合 D, 将当前特征 A 作为随机变量(取值是特征 A 的各个特征值), 求得的经验熵.
(之前是把集合类别作为随机变量, 现在把某个特征作为随机变量, 按照此特征的特征取值对集合 D 进行划分, 计算熵 HA(D))
信息增益比本质: 是在信息增益的基础之上乘上一个惩罚参数. 特征个数较多时, 惩罚参数较小; 特征个数较少时, 惩罚参数较大.
惩罚参数: 数据集 D 以特征 A 作为随机变量的熵的倒数, 即: 将特征 A 取值相同的样本划分到同一个子集中(之前所说数据集的熵是依据类别进行划分的)
缺点: 信息增益比偏向取值较少的特征
原因: 当特征取值较少时 HA(D)的值较小, 因此其倒数较大, 因而信息增益比较大. 因而偏向取值较少的特征.
使用信息增益比: 基于以上缺点, 并不是直接选择信息增益率最大的特征, 而是现在候选特征中找出信息增益高于平均水平的特征, 然后在这些特征中再选择信息增益率最高的特征.
来源: https://juejin.im/entry/5adfe8696fb9a07aab298378