浅谈决策树

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

用周老师的西瓜数据集2.0进行分析，在样本中正例占为$p_{1}$=8/17,反例为$p_{2}$=9/17,可以计算出根节点的信息熵为：
$Ent（D）=-\sum_{2}^{k=1}p_{k}log_{2}=-{\frac{8}{17}log_{2}\frac{8}{17}+\frac{9}{17}log_{2}\frac{9}{17}}=0.998$
先用颜色这一属性进行分类进行分类，得到三个属性值$D^1$(青绿)，$D^2$（乌黑)，$D^3$(浅白)，生成三个分支。其中$D^1$青绿包含6个样本，其中正例$p_1$=3/6，反例$p_2$=3/6；$D^2$乌黑含6个样本其中正例$p_{1}$=4/6,反例$p_{2}$=2/6；$D^3$浅白含5个样本其中正例$p_1$=1/5,反例$p_2$=4/5;三个分支节点的信息熵根据公式可求出：
$Ent(D_1)=-(\frac{3}{6}log_{2}\frac{3}{6}+\frac{3}{6}log_{2}\frac{3}{6})=1$
$Ent(D_2)=-(\frac{2}{6}log_{2}\frac{2}{6}+\frac{4}{6}log_{2}\frac{4}{6})=0.918$
$Ent(D_3)=-(\frac{1}{5}log_{2}\frac{1}{5}+\frac{4}{5}log_{2}\frac{4}{5})=0.722$
根据公式可计算出属性“色泽”的信息增益为：
$Gain(D,色泽)=Ent（D）-\sum_{v=1}^{3}\frac{|D^v|}{|D|}Ent(D^v)=0.998-(\frac{6}{17}*1.000+\frac{6}{17}*0.918+\frac{5}{17}*0.722)=0.109$
同理我们可以求出其他属性的信息增熵：
$Gain(D,根蒂)=0.143$;$Gain(D,敲声)=0.141$；
$Gain(D,纹理)=0.381$;$Gain(D,脐部)=0.289$;
$Gain(D,触感)=0.006$
从中可以看出纹理的信息增熵最大，所以用它来做为对根节点的划分属性较为适合，划分后如下图：

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

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