1. CART树
分类回归树(CART,Classification And Regression Tree)算法是一种决策树分类方法。CART每一个节点上都采用二分法,采用一种二分递归分割的技术,CART生成的树必须是二叉树,也就是无论回归还是分类,无论特征离散还是连续,无论属性取值有多个还是两个,内部节点只能根据属性进行二分。因此,CART算法生成的决策树是结构简洁的二叉树。 CART算法既可以用分类任务,也可用于回归任务。
1-2 回归树
CART作为回归树:使用**平方误差**最小准则来选择特征并进行划分,也叫最小二乘回归树。对于特征*j*,找到j所有的划分点*s,s*将数据集分为*c1、c2*两部分,找出使得两部分的方差最小,同时整体方差最小的特征j以及划分点*s*。对于离散特征,采用均值或者中位数作为节点的输出结果。
1-3 分类树
CART作为分类树:使用**Gini指数**最小化准则来选择特征并进行划分。
1-4 终止条件
CART算法构建二叉树 终止条件:
1、所有叶节点样本数为1,或属于同一类,或小于某一阈值;
2、树的高度到达某一阈值;
3、无剩余属性。
2. 基尼指与基尼指数
**2-1 基尼值 **
**基尼值**可用来度量数据集的纯度,数据集D的基尼系数Gini(D)反映了从数据集D中随机抽取两个样本,其类别标记不一致的概率,因此Gini(D)越小,则数据集D的纯度越高。pk表示选中的样本属于k类别的概率,则这个样本被分错的概率是(1-pk)
2-2 基尼指数
** 基尼指数(基尼不纯度):表示在样本集合中一个随机选中的样本被分错的概率。**
Gini指数越小表示集合中被选中的样本被分错的概率越小,也就是说集合的纯度越高,反之,集合越不纯。 即 基尼指数(基尼不纯度)= 样本被选中的概率 * 样本被分错的概率。
对于特征A,若其将数据集分为D1和D2两部分,则其基尼指数为:
在候选集中,选择那个使得划分后基尼指数最小的属性作为最优的划分属性。
2-3 案例
- 案例根据'有房者'、'婚姻'、'年收入'三个特征判断是否回拖欠贷款。2. 根据gini指数构建cart分类树的过程如下:
3.总结
基尼系数也是一种衡量信息不确定性的方法,与信息熵计算出来的结果差距很小,基本可以忽略,但是基尼系数要计算快得多,因为没有对数。熵和基尼指数的关系如下图:
Reference:
1.
版权归原作者 DonngZH 所有, 如有侵权,请联系我们删除。