Decison Tree

Decison Tree

基本概念的定义、解释、总结。

相关概念

1、信息量

X X 存在多个取值，如果一个事件发生概率为1，那么他一定会发生，完全没有信息量。概率越小的事件(取值)发生时，它所含的信息量越大。(参考统计学里的p-value，所谓事出反常必有妖)。可以想到信息量和事件发生的概率成正比。   定义：出现概率为p的消息所含的信息量。

I=−log(p)I=−log(p)

函数图像如下：

curve(expr = -log(x))

2、熵

衡量某一个事件(随机变量的某个取值)的信息量可以用上面的定义表示，那么衡量某一个变量的信息量容易想到用数学期望。   定义： 熵是表示随机变量不确定性的度量。设X X 是一个取有限个值的离散随机变量，其概率分布为：

P(X=xi)=pi,i=1,2,...nP(X=xi)=pi,i=1,2,...n

则随机变量X

X 的熵定义为

H(X)=−∑i=1npilogpiH(X)=−∑i=1npilogpi

0⩽H(p)⩽log(n) 0 ⩽ H ( p ) ⩽ l o g ( n ) 。最大值取到log(n) l o g ( n ) 据说可以用凸优化的知识证明。容易知道当随机变量所有取值发生的概率均为1n 1 n 时，取到最大值。直观来说，此时随机变量任意一个取值发生的概率相同，该随机变量的不确定性最大。

3、条件熵

X X 的条件下随机变量YY的不确定性。定义为：

H(Y|X)=∑i=1npiH(Y|X=xi),其中pi=P(X=xi),i=1,2,...n H ( Y | X ) = ∑ i = 1 n p i H ( Y | X = x i ) , 其 中 p i = P ( X = x i ) , i = 1 , 2 , . . . n

4、信息增益

X X 的信息而使得类YY的信息的不确定性减少的程度。信息增益大的特征分类的能力更为强大。定义为集合D D 的经验熵H(D)H(D)与特征A A 给定这一条件下DD的经验条件熵H(D|A) H ( D | A ) 之差：

g(D,A)=H(D)−H(D|A) g ( D , A ) = H ( D ) − H ( D | A )

5、信息增益比

g(D,A) g ( D , A ) 与特征A的熵HA(D) H A ( D ) 之比。 如果特征A A 的取值比较多，那么通常HA(D)HA(D)也比较大。可以理解为加入HA(D) H A ( D ) 惩罚取值较多的特征，作为一种校正方法。定义公式如下：

gR(D,A)=g(D,A)HA(D) g R ( D , A ) = g ( D , A ) H A ( D )

其中

HA(D) H A ( D ) 为：

HA(D)=−∑i=1n|Di||D|log(|Di||D|) H A ( D ) = − ∑ i = 1 n | D i | | D | log ⁡ ( | D i | | D | )

n n 是特征AA的类别数， Di D i 是特征 A A 的第ii个取值对应的样本个数。 D D 为样本个数。

[from 周志华《机器学习》]信息增益比对可取值较少的属性有所偏好，C4.5算法并不是直接选择增益率最大的特征划分属性，而是先从候选特征中找到信息增益高于平均水平的属性，再从中选择信息增益比最高的。

[from Mitchell《机器学习》]特征太多的可能取值必然把训练样例分割成非常小的空间。此时对于训练集，它会有非常高的信息增益。但是对于未见实例它可能是一个非常差的目标函数预测器。(吐槽，这个翻译太生硬)

6、基尼指数

KK个类，样本点属于第 k k 类的概率为pkpk，则概率分布的基尼指数定义为：

Gini(p)=∑k=1Kpk(1−pk) G i n i ( p ) = ∑ k = 1 K p k ( 1 − p k )

其直观含义为从样本中随机抽取两个样本，不属于同一类的概率。

D D 根据特征AA是否取某一可能值a a 被分割成D1D1和D2 D 2 两部分。则在特征A A 的条件下，集合DD的基尼系数定义为：

Gini(D,A)=|D1||D|Gini(D1)+|D2||D|Gini(D2)其中|D1|表示D1部分样本量的大小 G i n i ( D , A ) = | D 1 | | D | G i n i ( D 1 ) + | D 2 | | D | G i n i ( D 2 ) 其 中 | D 1 | 表 示 D 1 部 分 样 本 量 的 大 小

决策树的生成和剪枝

生成

ID3采用信息增益进行特征选择，而C4.5算法采用信息增益率进行特征选择。细节需要看下paper了。先这么着吧。有空看下《机器学习实战》，用py复现下吧。

ID3算法流程如下所示：

C4.5算法流程如下所示：

剪枝

完全生长的决策树容易造成过拟合的问题，解决这一问题的方法可以分为两类:   1. 提前停止增长树，在ID3算法完美分类训练数据之前停止生长树，具体：在信息增益小于阈值时，不再分裂，取频数最大的作为叶节点的类别。或者提前设置决策树的深度等   2. 后修剪法，先允许树过度拟合数据，然后对这个树后修剪，修剪原理类似预剪枝，如果信息增益小于阈值，剪枝即可   不同的算法貌似剪枝的方法不一样，李航《统计学习方法》中介绍了一种剪枝算法，可以看看。

CART算法

CART算法根据基尼指数进行特征选择，基尼指数越大说明不确定性越大，所以在某特征条件下，基尼指数越小，特征的区分能力越强。这和条件熵类似，条件熵越小，信息增益越大，特征区分能力越强。   剪枝算法没有看明白，尴尬。。

CART剪枝

剪枝的内容​​Pinard的博客​​写的比较清楚，别人写的博客为什么这么好，自己的，捂脸。

问题总结

熵的含义，通俗的讲解熵的值域，为什么有上下界信息增益和信息增益比的差异

优缺点

优点

不需要任何先验假设解释性高，推理过程可以看成If-Then形式，容易转化成规则对缺失值不敏感 ，可以处理数值型、字符型数据没有复杂的参数设置，推理过程完全依赖于属性变量的取值特点判断属性变量的重要性，为特征选择提供参考

缺点

容易过拟合对异常值过于敏感求解时候容易陷入局部最优如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善

决策树调参

参考​​Pinard的博客​​​，基于scikit-learn，我只用过R的C50包。 scikit-learn的参数和R的参数有空不好。

Ref

[1] 李航《统计学习方法》 [2] 周志华《机器学习》 [3] ​​​《scikit-learn决策树算法类库使用小结》-Pinard​​​ [4] ​​​《决策树算法原理(下)》-Pinard​​​ [5] ​​​《决策树算法原理(上)》-Pinard​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。