决策树是用于分类的统计模型。

熵的概念

熵是来衡量随机变量的不确定性的。Shannon entropy来定量化了这种不确定性。

有以下公式

H(x)=∑iP(xi)I(xi)=−∑iP(xi)logbP(xi)

H(x)=∑iP(xi)I(xi)=−∑iP(xi)logbP(xi)

接下来通过例子来说明。

比如投硬币，正面和反面的概率都是1/2，在这种情况下，一个比特就可以来传递每一次的结果。投了4次硬币，2次正面，2次反面。根据香农公式那么熵就为E1=-1/2log2(1/2)-1/2log2(1/2)=1

同理如果每次都是证明的话，那么熵为0.

接下来来理解一下比特（bits）的概念

考虑三种可能结果的情况，正，负，中三种结果。其中正的结果2次，负的结果1次，中的结果1次。根据公式熵为1.5.

信息增益

信息增益是用来选取属性的。被选择的分类属性，信息增益是最高的。

信息增益的方法会偏向于选择将样本分为多类的属性，而这个属性对于机器学习可能是没有意义的。

因此用信息增益的方式来选取特征。

比如对于特征A的信息增益有以下公式

Gain(A)=Info(D)−InfoA(D)

Gain(A)=Info(D)−InfoA(D)

where

InfoA(D)=∑j=1v|Dj||D|×Info(Dj)

InfoA(D)=∑j=1v|Dj||D|×Info(Dj)

相当于增加了对于分类过多的惩罚。

首先通过信息增益的计算来进行选取。

1）如果选取性别作为特征，那么

Info(Dgender=male)=−2/2log2(2/2)=0

Info(Dgender=male)=−2/2log2(2/2)=0

同理可得Info(Dgender=female)=1Info(Dgender=female)=1

InfoGender(D)=2/4(0)+2/4(1)=0.5InfoGender(D)=2/4(0)+2/4(1)=0.5

Gain(Gender)=1Gain(Gender)=1

2）以年龄为特征，则

Gain(Age)=0.5Gain(Age)=0.5

Gain(Gender)>Gain(Age)Gain(Gender)>Gain(Age) 因此选性别作为特征。

但是这种选取有一个问题，假如我们增加了一个观点序号的特征，那个这个特征可以将数据分为4类。则Gain("Opinionno")=1.5Gain("Opinionno")=1.5 在这种情况下观点序号就被选作了特征，显然是不合理的。

增益率

用增益率来解决以上问题，这个方法很简单直接，就是对分类太多的特征进行一定的惩罚。

有以下公式

SplitInfoA(D)=−∑j=1v|Dj||D|×log2(|Dj||D|)

SplitInfoA(D)=−∑j=1v|Dj||D|×log2(|Dj||D|)

Gainratio(A)=Gain(A)SplitInfo(A)

Gainratio(A)=Gain(A)SplitInfo(A)

GainRatio("OpinionNo")=1.5/2=0.75

GainRatio("OpinionNo")=1.5/2=0.75

GainRatio(Gender)=1/1=1

GainRatio(Gender)=1/1=1

GainRatio(Age)=0.5/1=0.5

GainRatio(Age)=0.5/1=0.5