决策树的主流算法有很多种, 接触一种记录一种.
一, CART: 二叉树, 一个节点一般分出左右两个孩子. 通过 Gini index 决定最优分割. 如果我们想对某一 Node 进行分割, 先测量分割前 node 的基尼系数, 再测量按照某一准则 (如 I{X<=c}) 分割后左右两字数的基尼系数之和, 两者相减则为不纯程度 (Imputiry) 下降的分数. 具体计算基尼系数的分数是:
二, 香农熵(Shannon entropy), 进化版本为 ID3->C4.5->C5.0. 主要原则是利用一个节点内熵的变化衡量纯度变动. 熵的计算公式为
类似的, 衡量节点分割前的香农熵, 以及节点分割后各个分区的香农熵之和, 两者之差被定义为信息增益(information gain). 值得注意的是, C5.0 算法可以 create multiple child nodes from one node.
三, Misclassification error. 没有详细了解, 应该是通过计算分割前后的误差之差决定最优分割.
三者对比. 个人认为该图片仅考虑了两个类的数据分割情况. p 代表结点中某一类的占比. 可以看到纯度随着结点中 A 类占比的增大呈现先上升后下降的趋势. 并且都在五五分割的时候不纯程度 (Impurity) 最大.
通过三者特性得出以下的对比结论:
1. 基尼系数和香农熵对于 node probability 的改变更为敏感(表现在图上就是曲线的斜率更大, 更为陡峭), 因此, 这两种度量方法旨在寻找更为 "pure" 的 nodes.
2. Misclassification error 可以用来评估一棵树的情况, 但是对于构造决策树, 略微有些敏感度不足了.
对于 categorical predictors 的分类, 原理相同, 对于一个取值范围再 1,...,Md 的名义变量我们寻找它取值范围的子集 A. 这时候我们的 splitting rule 为: I{X belongs to A}
可以看到, 我们有至多 2^(M-1)-1 中分类.
(注, 分类的组合为 Cm1+Cm2+...+Cm(m/2)中, 注意把一个 set 分为 1/4 和分为 4/1 的结果是一样的, 顶多树的左右子节点位置互换而已没有意义, 因此不是 Cm1+...+Cm(m-1). 但是 Cm1+Cm2+...+Cm(m/2)=1/2(Cm1+...Cm(m-1)). 所以我们通过求后者来计算前者. 这个式子的解法运用到高中排列知识的二次项定理,(1+1)^m 的系数正好是 Cm0+Cm1+Cm2+...+Cmm.
恩...... 为啥是横的. 随便吧. 这个分类数目是非常大的(computationally intense). 因此一种启发式的思想是对某一子节点采用 randomly sample 的方法选择子集, 然后比较这几个随机 splitting 的分类结果.
当 outcome y 是连续性的时候, 可以理解为我们在做回归. 这时候我们同意需要新的 Impurity 度量方法. 通过加权方差减少量来度量.
综上, 三种情况, 输入变量是连续性变量, 输入变量是分类变量, 输出变量是连续性变量. 前两种情况的不同主要是最优分类的分类准则不同, 对于分类后的分数计算和比较都是一样的. 第三种情况主要是分类后的分数计算要用连续性的方差来衡量.
来源: http://www.bubuko.com/infodetail-2581069.html