信息增益率gini这三个指标均是决策树用来划分属性的时候用到其中In

1、ID3，Gini 用于 CART，信息增益率（Info Gain Ratio）用于 C4.5。提到前两个指标的计算而熵（Entropy）能够满足以上三点特性。熵（Entropy）是由“信息论之父”，更多的各种历史、数学理论请查看参考1。接下来，看看熵的计算公式如下：entropy(p1,p2,pn)=p1log2(p1)p2log2(p2)pnlog2(pn)其中，( p_i )为比例值。其实，熵也可以用另外一种意思来解释：Given a probability distribution, the info required to predict an event is the distrib

2、utions entropy. Entropy gives the information required in bits (this can involve fractions of bits!)可以简单的理解为“熵”描述了用来的信息位数。接下来看个例子：如下表所述的天气数据，学习目标是Play or not play?表 1 天气预报数据集例子Outlook sunny sunny overcastTemperaturehot hot hotHumidityhigh high high high normal normal normal high normal normal normal

3、 highnormalWindy false true false false false true true false false false true truefalsePlay?no no yes yes yes no yes no yes yes yes yesyesraildrain rainovercast sunny sunnycool cool cool mild coolraildsunny overcast overcastmild mild hot时，首先要讲到的是关于熵（Entropy）的计算。1、熵（Entropy）理论上来说用于决策树的属性选择函数，为方便计算，往

4、往是定义为其属性的不纯性度量，那么必须满足如下三个条件：当结点很纯时，其度量值应为 0当不纯性最大时（比如所有类都有同样的可能），其度量值应最大度量应该服从多级特性，这样决策树才能分阶段建立起来measure(2,3,4)=measure(2,7)+frac79timesmeasure(3,4)这三个指标均是决策树用来划分属性的时候用到的，其中信息增益（Info Gain）用于共 14 个实例，9 个正例（yes），5 个负例（no）。 这样当前数据的信息量（原始状态）用熵来计算就是：info(play?)=info(9,5)=entropy(frac914,frac514) =frac914

5、log2(frac914) frac514log2(frac514)=0.410+0.530=0.940有了上面计算熵（信息）的基础，接下来看信息增益了。2、信息增益（Info Gain）信息增益，按名称来理解的话，就是前后信息的差值，在决策树分类问题中，即就是决策树在进行属性选择划分前和划分后的信息差值，即可以写成：gain()=infobeforeSplit()infoafterSplit()如上面的例子，通过使用 Outlook 属性来划分成下图：图 1 使用 Outlook 属性划分决策树在划分后，可以看到数据被分成三份，则各分支的信息计算如下：info(2,3)=frac25log2

6、(frac25)frac35log2(frac35)=0.971bits info(4,0)=frac44log2(frac44)frac04log2(frac04)=0bits，此处虽然( log_2(0) )没有定义，但( 0 times log_2(0) )仍然计算为 0。info(3,2)=frac35log2(frac35)frac25log2(frac25)=0.971bits因此，划分后的信息总量应为：info(2,3,4,0,3,2)=frac514times0.971+frac414times0+frac514times0.971=0.693bits如果把上面的公式整理到一起

7、的话，就是：$ info(2,3, 4,0, 3,2) = frac514times info(2,3) + frac414times info(4,0) + frac514times info(3,2)= 0.347 + 0 + 0.347 = 0.694 bits $从上面可以看出，划分后的信息总量计算公式为：info(S1,Sn)=sumnifrac|Si|S|timesentropy(Si)hightruenoraildgaemperature|Outlook,Play?)=0.571bits其中，n 表示划分后的分支数目，( |S| )表示划分前的实例个数，( |S_i| )表示划分

8、后某个分支的实例个数。最后，信息增益gain(outlook|play?)=infobeforeSplit()infoafterSplit() =info(play?) info(3,2,4,0,3,2)=0.9400.694=0.246bits通过划分其他属性，到其他的树如下：图 2 使用其他属性划分决策树同样计算，gaemperature|play?)=info(9,5)info(2,2,4,2,3,1) =0.940 (frac414timesinfo(2,2)+frac614timesinfo(4,2)+frac414timesinfo(3,1)=0.028bits gain(Humi

9、dity|play?)=0.152bitsgain(Windy|play?)=0.048bits这样，算选择最大的信息增益属性来进行划分，在此处为 Outlook 属性。接下来在Outlook=sunny 结点，按照同样的判断方法，选择其他属性进行划分，图 3 继续划分决策树计算如下：infobeforeSplit()=info(2,3)=0.971bits 2 个正例，3 个负例，计算其熵gain(Humidity|Outlook,Play?)=0.971bits gain(Winday|Outlook,Play?)=0.020bits因而可以得到下一个划分结点是 Humidity 属性。在

10、这里的 Temperature 有三个值，因而其info(2,2,1)使用简便方法计算为： info(0,2,1,1,1,0)=frac25timesinfo(0,2)+frac25timesinfo(1,1)+frac15timesinfo(1,0)=0.4bits因此( gaemperature|Outlook, Play?) = 0.971 0.4 = 0.571 bits )。另外，由于要计算的是信息增益最大，在划分前信息总量( info_beforeSplit() )一定的情况下，接求划分后信息量最小的特性即可。完全可以直3、信息增益率（Info Gain Ratio）通过上面的例子

11、，想必对于信息增益的计算步骤已经熟悉些了。那么下面来看信息增益存在的一个问题：假设某个属性存在大量的不同值，如 ID（在上面例子中加一列为 ID，编号为 an），在划分时将每个值成为一个结点，这样就形成了下面的图：图 4 信息增益偏向最终计算得到划分后的信息量为：( info(S_1, , S_n) = sum_i=1nfrac|S_i|S|timesentropy(S_i) = 0 )，因为( entropy(S_i) = info(1,0) ) 或 ( info(0,1) )，只含一个纯结点。这样决策树在选择属性时，将偏向于选择该属性，但这肯定是不正确（导致过拟合）的。因此有必要使用一种更

12、好的方法，那就是 C4.5 中使用的信息增益率（Info Gain Ratio），其考虑了分支数量和尺寸的，使用称为内在信息（ rinsic Information）的概念。Gain ratio takes number and size of brancheso account when choosing an attribute,and corrects the information gain by taking therinsic information of a splito account(i.e. how much info do we need tol which branch

13、 an instance belongs to).内在信息（ rinsic Information），可简单地理解为表示信息分支所需要的信息量，其计算公式如下：rinsicInfo(S,A)=sumfrac|Si|S|log2frac|Si|S|则针对上图中的例子，info(1,1,1)=14times(frac114log2frac114)=3.807bits信息增益率则计算如下：gainratio(Attribute)=fracgain(Attribute)rinsicInfo(Attribute)依然如上例：gainratio(IDCode)=frac0.940bits3.807bits

14、=0.246实际上可以看出，属性的重要性会随着其内在信息（ rinsic Information）的增大而减小。信息增益率作为一种补偿（Compensate）措施来解决信息增益所存在，但是它也有可能导致过分补偿，而选择那些内在信息很小的属性，这一点可以尝试：首先，仅考虑那些信息增益超过平均值的属性，其次再比较信息增益。4、Gindex在 CART 里面划分决策树的条件是采用 Gindex，定义如下：gini(T)=1sumnj=1p2j其中，( p_j )是类 j 在 T 中的相对频率，当类在 T 中是倾斜的时，gini(T)会最小。将 T 划分为T1（实例数为 N1）和 T2（实例数为 N2）两个子集后，划分数据的 Gini 定义如下：ginisplit(T)1Ngini(T1)2Ngini(T2)然后选择其中最小的( gini_split(T) )作为结点划分决策树。5、参考本文大量地参考了如下资料：1 N)(EN),(C2 Data Mining exles:oost/DM/mod_06_dec_tree_ro.ppt3 Data Mining Practical Machine Learning Tools an