决策树的熵

一、信息熵

信息熵公式：代表随机变量不确定度的度量
不确定性的变化跟什么有关呢？一，跟事情的可能结果的数量有关；二，跟概率有关

信息论之父克劳德·香农，总结出了信息熵的三条性质：

• 单调性，即发生概率越高的事件，其所携带的信息熵越低。极端案例就是“太阳从东方升起”，因为为确定事件，所以不携带任何信息量。从信息论的角度，认为这句话没有消除任何不确定性。
• 非负性，即信息熵不能为负。这个很好理解，因为负的信息，即你得知了某个信息后，却增加了不确定性是不合逻辑的。
• 累加性，即多随机事件同时发生存在的总不确定性的量度是可以表示为各事件不确定性的量度的和。写成公式就是：

二、信息增益

信息增益 = 信息熵-条件熵 = 互信息
公式：g(D,A)=H(D)－H(D|A)

三、信息增益比

信息增益的一个大问题就是偏向选择特征值比较多的属性从而导致overfitting，那么我们能想到的解决办法自然就是对分支过多的情况进行惩罚(penalty)了。于是我们有了信息增益比：

信息增益偏向于选择取值较多的特征，但根据熵的公式可知，特征越多，熵越大，所以除A特征的熵正好抵消了特征变量的复杂程度，避免了过拟合的存在

四：基尼指数

在ID3算法中我们使用了信息增益来选择特征，信息增益大的优先选择。
在C4.5算法中，采用了信息增益比来选择特征，以减少信息增益容易选择特征值多的特征的问题。但是无论是ID3还是C4.5,都是基于信息论的熵模型的，这里面会涉及大量的对数运算。能不能简化模型同时也不至于完全丢失熵模型的优点呢？

CART分类树算法使用基尼系数来代替信息增益比，基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。这和信息增益(比)是相反的。

从上图可以看出，基尼系数和熵之半的曲线非常接近，仅仅在45度角附近误差稍大。因此，基尼系数可以做为熵模型的一个近似替代。而CART分类树算法就是使用的基尼系数来选择决策树的特征。同时，为了进一步简化，CART分类树算法每次仅仅对某个特征的值进行二分，而不是多分，这样CART分类树算法建立起来的是二叉树，而不是多叉树。这样一可以进一步简化基尼系数的计算，二可以建立一个更加优雅的二叉树模型。

总结：为什么CART树用基尼指数？
1、因为CART是二叉树，不是多叉树，所以只需用信息熵即可，无需用增益或增益比
2、信息熵的log计算麻烦，用基尼指数做近似。gini指数算得比较快点，可能因为不用算log

五、ID3，C4.5，CART三种树

	分类	回归	树叉	特征类型	选择特征的标准
ID3	✓	✘	多叉树	离散特征	信息增益
C4.5	✓	✘	多叉树	离散、连续特征	信息增益比
CART	✓	✓	二叉树	离散、连续特征	分类用基尼指数，回归用平方误差

总结

• 1、分类回归：前两种只能做分类
• 2、特征：ID3只能做类别特征，其他
• 4、多叉树，二叉树