浅谈决策树

决策树（decision tree）是一种常见的机器学习方法。看了周志华西瓜书后来简要谈谈自己的认识：
首先，引入了“信息熵”的概念，信息熵（information entropy）是离散随机事件的出现概率，是衡量样本集合纯度最常用的一种指标，与热力学的熵有密切的关系。
通常，一个信源发送出什么符号是不确定的，衡量它可以根据其出现的概率来度量。概率大，出现机会多，不确定性小；反之就大。这种不确定性即为熵。
熵的函数需要满足以下两个条件：不确定性函数f是概率P的单调递降函数；两个独立符号所产生的不确定性应等于各自不确定性之和，即f（P1，P2）=f（P1）+f（P2），这称为可加性。同时满足这两个条件的函数f是对数函数，即 f(p)=log1p=−logp 。
假定当前样本集合D中第（k）类样本所占的比例为pk（k=1，2，….,|y|），D的信息熵定义为 Ent(D)=−∑|y|k=1pKlog2pk，其中y为样本种类数。
式中对数一般取2为底，单位为比特。但是，也可以取其它对数底，采用其它相应的单位，它们间可用换底公式换算。 Ent（D）的值越小，D的纯度越高。Ent(D)最小值为0，最大值为log2|y|
对于样本的属性a有V种可能的选择{a1，a2，...,aV}，在进行划分时会产生V个分支点，根据属性a对样本进行划分时可获得“信息增益”（information gain）：
Gain(D,a)=Ent(D)−∑Vv=1|Dv||D|Ent(Dv)
其中Dv属性为av的样本数，D表示总样本数；一般而言，信息增益越大，意味着使用属性a进行划分所获得的“纯度提升”越大，这是用来进行决策树属性划分的依据之一。ID3（Iterative Dichotomiser）决策树就是以信息增益为标准来划分的。

用周老师的西瓜数据集2.0进行分析，在样本中正例占为p1=8/17,反例为p2=9/17,可以计算出根节点的信息熵为：
Ent（D）=−∑k=12pklog2=−817log2817+917log2917=0.998
先用颜色这一属性进行分类进行分类，得到三个属性值D1(青绿)，D2（乌黑)，D3(浅白)，生成三个分支。其中D1青绿包含6个样本，其中正例p1=3/6，反例p2=3/6；D2乌黑含6个样本其中正例p1=4/6,反例p2=2/6；D3浅白含5个样本其中正例p1=1/5,反例p2=4/5;三个分支节点的信息熵根据公式可求出：
Ent(D1)=−(36log236+36log236)=1
Ent(D2)=−(26log226+46log246)=0.918
Ent(D3)=−(15log215+45log245)=0.722
根据公式可计算出属性“色泽”的信息增益为：
Gain(D,色泽)=Ent（D）−∑3v=1|Dv||D|Ent(Dv)=0.998−(617∗1.000+617∗0.918+517∗0.722)=0.109
同理我们可以求出其他属性的信息增熵：
Gain(D,根蒂)=0.143;Gain(D,敲声)=0.141；
Gain(D,纹理)=0.381;Gain(D,脐部)=0.289;
Gain(D,触感)=0.006
从中可以看出纹理的信息增熵最大，所以用它来做为对根节点的划分属性较为适合，划分后如下图：

分成三个支点：D1(清晰)，D2稍糊，D2模糊
对于支点D1可用属性{色泽，根蒂，敲声，脐部，触感}进行划分，仿照对根节点的划分方法，求出各属性的信息增熵：
Gain(D1,色泽)=0.043；Gain(D1,根蒂)=0.458；
Gain(D1,敲声)=0.331；Gain(D1,脐部)=0.458；
Gain(D1,触感)=0.458
从结果中可以看出根蒂，脐部，触感的信息增熵一样，可任选其一对D1进行分类，类似的对每个节点用信息增熵进行划分，最后可以得到：

这是ID3决策树对西瓜数据2.0进行划分的结果。