十分钟搞懂决策树的数学原理

决策树方法在分类、预测等领域有广泛的应用，在机器学习研究者Quinlan提出ID3算法之后，决策树在机器学习、数据挖掘领域得到极大的发展。

ID3算法：该算法是以信息论为基础，以信息熵和信息增益为衡量标准，从而实现对数据的归纳分类。根据信息论理论，采用划分后样本集的不确定性作为衡量划分好坏的标准，用信息增益度量不确定性：信息增益越大，不确定性越小

信息增益

信息熵：香农提出的，为解决信息的量化问题，一条信息的信息量和他的不确定性有直接关系，一个问题不确定性越大，要搞清楚这个问题就需要了解更多的信息，其信息熵就越大，对于任意一个随机变量X，它的信息熵定义如下，单位为比特(bit)，计算公式为：

其中P(x)表示事件x出现的概率

例如：一个盒子中分别有5个白球和5个红球，随机取出一个球，问，这个球是红色还是白色？这个问题信息量多大呢？由于红球和白球出现的概率都是1/2，那么久可以得到其信息熵为：H(x)=-(1/2*log2(1/2)+1/2log2(1/2))=1，是的，这个信息量是1bit。

如果一个盒子里有10个红球，随机取出一个，这个球什么颜色？这个问题的信息量是多少？信息量是0，因为这是一个确定事件，概率P(x)=1

信息熵其实是一个随机变量信息量的数学期望。

参考一个别人的例子：

1，计算总信息熵。数据记录34条，销量为高的有18条，为低的16条

总信息熵H(x)=-(18/34)*log2(18/34)-(16/34)*log2(16/34)=0.997503

2,计算各个属性的信息熵

对于天气，属性值有好与坏，其中好天气下，销量为高的记录11条，为低的记录6条

在坏天气下，销量为高记录7条，为低的记录10条

H(天气=好)= -(11/17)*log2(11/17)-(6/17)*log2(6/17)=0.936667

H(天气=坏)= -(7/17)*log2(7/17)-(10/17)*log2(10/17)=0.977418

H(天气)=(17/34)* H(天气=好)+(17/34)* H(天气=坏) = 0.957043

对于是否周末，属性值有是与否，其中是周末下，销量为高的记录11条，为低的记录3条

在否周末下，销量为高记录7条，为低的记录13条

H(周末=是)= -(11/14)*log2(11/14)-(3/14)*log2(3/14)=0.749595

H(周末=否)= -(7/20)*log2(7/20)-(13/20)*log2(13/20)=0.934068

H(周末)=(14/34)* H(周末=是)+(10/34)* H(周末=否) = 0.858109

对于是否促销，属性值有是与否，其中促销下，销量为高的记录15条，为低的记录7条

在否促销下，销量为高记录3条，为低的记录9条

H(促销=是)= -(15/22)*log2(15/22)-(7/22)*log2(7/22)=0.902393

H(促销=否)= -(3/12)*log2(3/12)-(9/12)*log2(9/12)=0.811278

H(促销)=(22/34)* H(促销=是)+(12/34)* H(促销=否) = 0.870235

3，计算天气，是否周末，是否促销的信息增益值

Gain(天气)= H(x)- H(天气)=0.04046

Gain(是否周末)= H(x)- H(周末)=0.139394

Gain(是否促销)= H(x)- H(促销) = 0.127268,4

4，由第三步可知，是否周末的信息增益最大，他的两个属性'是'，'否'作为跟结点的两个分支，

然后从未被选择的特征中继续进行一至三步，选择最优数据划分特征来划分子数据集，

何时停止？一是一直到所有的特征都用完了，二是划分后额信息增益足够小，就可以停止了，最终构成一颗决策树

信息熵与概率的关系图如下：

可以看出，当概率P(x)越接近0或者1是，信息熵越小，其不确定性越小，即数据越纯，我们在选择特征时，选择信息增益最大的特征，即，让数据尽量往更纯净的方向上变换，因此，信息增益是用来衡量数据变得更有序、更纯净的指标。

1,数据离散化

如果一个特征时连续值怎么办？此时需要进行离散化，对连续数据进行离散化处理，比如：

当成绩大于90标识为优，当成绩大于70小于90，标识为良，当成绩大于60小于70，标识为及格，当成绩小于60标识为不及格

经过离散化处理就可以构建决策树了

2，正则项

信息增益的一个大问题就是容易造成偏向选择分支多的属性导致，那么我们能想到的解决办法就是加上一个与类别个数成正比的正则项来作为最终的信息熵，这样当算法选择的某个类别较多的特征，是信息熵较小的时候，受到正则项的惩罚，最终导致信息熵也比较大，这样通过合适的参数，可以是算法训练得到平衡

另外一个解决办法是使用信息增益比来作为特征选择的标准，就是特征的增益值除以特征熵，可以解决优先选取类别多的特征的问题

3，基尼不纯度

信息熵是衡量信息不确定性的指标，实际上是 衡量信息纯度的指标，除此之外，基尼不纯度也是衡量信息不纯度的指标，公式如下：

P(x)是样本属于x类别的概率

如图：

可以看出，其形状和信息熵的几乎一样

解决过拟合问题

使用决策树模型拟合数据时，容易过拟合，解决过拟合的方法一般是对决策树进行剪枝，有两种思路，前剪枝和后剪枝

1，前剪枝

前剪枝是在构建决策树的同时进行剪枝，在构建过程中，如果无法进一步降低信息熵，就是停止创建分支，为了避免过拟合，可以设定一个阈值，当信息熵减小的数量小于这个阈值，计算还会降低熵，也要停止继续创建分支。还可以限制叶子节点样本个数，当样本个数小于设定值，则不再继续创建分支

2，后剪枝

后剪枝是在决策树构建完成后进行剪枝。剪枝的过程就是对拥有同样父节点的一组节点进行检查，判断其如果合并是否信息熵的增加量小于某一个阈值，如果小于阈值，这一组节点可以合并成一个节点。后剪枝是目前比较普遍都得做法