信息熵与ID3决策树

在机器学习中,决策树(decision tree)是一种预测模型,它用于代表对象属性和对象值之间额一种映射关系。一般一颗决策树包含一个根结点、若干个内部结点和若干个叶结点,叶节点对应于决策的结果,其他结点则对应于对象的属性,每个结点包含的样本集合根据对应的不同属性被划分到不同的子结点中。

章节:

  1. 决策树原理
  2. 信息熵-最优属性划分

1.决策树原理

图 1所示为一颗简单的决策树,长方形框为内部结点对应于属性的判断,椭圆框为叶结点对应决策的结果。当需要判别一个西瓜是否为好瓜时,根据该决策树进行一系列判断,首先看这个西瓜的色泽是否为“青绿”,如果是则看这个西瓜的根蒂是否为“卷缩”,如果是则看这个西瓜的敲声是否为“浊响”,如果是则这个西瓜为“好瓜”。从根结点到每个叶结点的路径都对应着一个判定测试序列,决策树学习的目的就是生成一个泛化能力强,并能处理未见样本的决策树。

图1 决策树示例

现在给定如下一份西瓜数据,通过学习这份西瓜数据生成用于西瓜判别的决策树,当得到新的西瓜数据时,通过该决策树可以对新西瓜的好坏进行判别。

表1 西瓜集数据

编号

色泽根蒂敲声纹理脐部触感好瓜

1

青绿蜷缩浊响清晰凹陷硬滑

2

乌黑蜷缩沉闷清晰凹陷硬滑

3

乌黑蜷缩浊响清晰凹陷硬滑

4

青绿蜷缩沉闷清晰凹陷硬滑

5

浅白蜷缩浊响清晰凹陷硬滑

6

青绿稍蜷浊响清晰稍凹软粘

7

乌黑稍蜷浊响稍糊稍凹软粘

8

乌黑稍蜷浊响清晰稍凹硬滑

9

乌黑稍蜷沉闷稍糊稍凹硬滑

10

青绿硬挺清脆清晰平坦软粘

11

浅白硬挺清脆模糊平坦硬滑

12

浅白蜷缩浊响模糊平坦软粘

13

青绿稍蜷浊响稍糊凹陷硬滑

14

浅白稍蜷沉闷稍糊凹陷硬滑

15

乌黑稍蜷浊响清晰稍凹软粘

16

浅白蜷缩浊响模糊平坦硬滑

17青绿蜷缩沉闷稍糊稍凹硬滑

对于上述西瓜数据来说,通过不同的划分属性序列,可能得到多种不同的决策树,如图 2中,不同决策决策树有着不同的根结点和子结点,不同决策树的样本分类能力也不同。如何选择最优划分属性使得样本分类能力达到最好是决策树学习的一个关键。

图 2 不同的可能决策树

2.信息熵-最优属性划分

决策树学习的关键在于如何选择最优划分属性。

“信息熵”(information entropy)是用于一个系统的信息含量的量化指标[1],其公式定义如下:

\(H(X)=-\sum_{i=1}^{n} p\left(x_{i}\right) \log _{2} p\left(x_{i}\right) \)     公式1

(使用信息熵来选择最优属性的决策树被称为ID3决策树[2])

其中X表示当前系统中所有样本,n为X中样本所有的类别,\(x_{i} \)表示第i个类别,\(p\left(x_{i}\right)\)表示当前类别样本占总样本数的比例。通过公式 1则可以计算出样本集合X的信息熵。信息熵的值越小,则表示样本集合的纯度越高(包含的样本尽可能的属于同一类别的程度)。

以表 1的西瓜数据为例,该数据中共包含17个样本数据,类别分为好瓜\(x_{1} \)和坏瓜\(x_{2} \),即n=2。好瓜数量为8个,即\(P\left(x_{1}\right)=\frac{8}{17}\)。坏瓜数量为9个,即\(P\left(x_{2}\right)=\frac{9}{17}\)。所以样本集合X的信息熵计算过程如下。

\(H(X)=-\sum_{i=1}^{n} p\left(x_{i}\right) \log _{2} p\left(x_{i}\right)=-\left(\frac{8}{17} \log _{2} \frac{8}{17}+\frac{9}{17} \log _{2} \frac{9}{17}\right)=0.998\)

假定X样本中存在某个离散属性a,该属性有k个可能的取值{\(a^{1}\)、\(a^{2}\)、……、\(a^{n}\)}那么如果使用属性a对样本集合X进行划分,则会产生k个分支节点,第k个分支结点则包含了X中所有在属性a上取值为\(a^{k}\)的样本,记为\(X^{k}\)。对于\(X^{k}\)的信息熵同样可以使用公式 1进行计算,但是由于不同分支结点包含的样本数不同,还需要给予分支结点不同的权重,该权重为\(X^{k} / X\)。属性a对于样本X进行划分所得到的信息增益可用如下公式计算。

\(G(X, a)=H(X)-\sum_{k=1}^{K} \frac{\left|X^{k}\right|}{|X|} H\left(X^{k}\right)\)    公式2

通过公式 2计算当前X集合中当前每个属性的信息增益。

以纹理为例,其可能取值为{清晰,稍糊,模糊},使用纹理属性对X进行划分,可以得到3个子集,\(X^{1}\)(纹理=清晰),\(X^{2}\)(纹理=稍糊),\(X^{3}\)(纹理=模糊)。

\(X^{1}\)包含编号为{1,2,3,4,5,6,8,10,15}的9个样本,其中好瓜包含编号为{1,2,3,4,5,6,8}的7个样本,比例为\(P\left(x_{1}\right)=\frac{2}{9}\);坏瓜包含编号为{10,15}的2个样本,比例为\(P\left(x_{2}\right)=\frac{7}{9}\)。

\(X^{2}\)包含编号为{7,9,13,14,17}的5个样本,其中好瓜包含编号为{7}的1个样本,比例为\(P\left(x_{1}\right)=\frac{1}{5}\);坏瓜包含编号为{9,13,14,17}的4个样本,比例为\(P\left(x_{2}\right)=\frac{4}{5}\)。

\(X^{3}\)包含编号为{11,12,16}的3个样本样本,其中不包含好瓜,所有样本均为坏瓜,即信息熵为0。

根据公式 1计算\(X^{1}\),\(X^{2}\),\(X^{3}\)三个分支结点的信息熵如下:

\(\begin{array}{c}
H\left(X^{1}\right)=-\left(\frac{2}{9} \log _{2} \frac{2}{9}+\frac{7}{9} \log _{2} \frac{7}{9}\right)=0.764 \\
H\left(X^{2}\right)=-\left(\frac{1}{5} \log _{2} \frac{1}{5}+\frac{4}{5} \log _{2} \frac{4}{5}\right)=0.722 \\
H\left(X^{3}\right)=0
\end{array}\)

根据公式 2计算纹理属性的信息增益如下:

\(\begin{aligned}
G(X, \text { 纹理 }) &=H(X)-\sum_{k=1}^{3} \frac{\left|X^{k}\right|}{|X|} H\left(X^{k}\right) \\
&=0.998-\left(\frac{9}{17} \times 0.764+\frac{5}{17} \times 0.722+\frac{3}{17} \times 0\right) \\
&=0.381
\end{aligned}\)

同理,计算出色泽、根蒂、敲声、脐部和触感的信息增益:

\(\begin{array}{l}
G(X, \text { 色泽 })=0.109 \\
G(X \text { ,根蒂 })=0.143 \\
G(X \text { ,敲声 })=0.141 \\
G(X \text { ,脐部 })=0.289 \\
G(X \text { ,触感 })=0.006
\end{array}\)

在所有属性中,纹理属性的信息增益最大,因此将纹理属性选为划分属性,即基于根结点进行划分如图 3所示。对于当前结点包含的样本全属于同一类别时,无需继续划分,该结点为叶节点。如纹理属性为模糊,该结点中全为坏瓜,该结点不用继续划分,该结点为叶节点,对应的决策结果为坏瓜。

图3  基于“纹理”属性进行根结点划分

接下来,将对图 3中每个分支结点做进一步划分,以最左侧纹理为清晰集合\(X^{1}\)为例。\(X^{1}\)中包含编号为{1,2,3,4,5,6,8,10,15}的9个样本,此时的可用属性为色泽、根蒂、敲声、脐部和触感,基于集\(X^{1}\)合计算出各属性的信息增益。

集合信息\(X^{1}\)熵为:

\(H\left(X^{1}\right)=-\left(\frac{2}{9} \log _{2} \frac{2}{9}+\frac{7}{9} \log _{2} \frac{7}{9}\right)=0.764\)

通过公式 2计算当前集合中当前可用的每个属性的信息增益。

以根蒂为例,其可能取值为{蜷缩,稍蜷,硬挺},使用根蒂属性对\(X^{1}\)进行划分,可以得到3个子集,\(X^{11}\)(根蒂=蜷缩),\(X^{12}\)(根蒂=稍蜷),\(X^{13}\)(根蒂=硬挺)。

\(X^{11}\)包含编号为{1,2,3,4,5}的5个样本,其中全为好瓜,则信息增益为0。

\(X^{12}\)包含编号为{6,8,15}的3个样本,其中好瓜包含编号为{6,8}的2个样本,比例为\(P\left(x_{1}\right)=\frac{2}{3}\);坏瓜包含编号为{15}的1个样本,比例为\(P\left(x_{2}\right)=\frac{1}{3}\)。

\(X^{13}\)包含编号为{10}的1个样本样本,其中全为坏瓜,即信息熵为0。

根据公式 1计算\(X^{11}\),\(X^{12}\),\(X^{13}\),三个分支结点的信息熵如下:

\(\begin{array}{c}
H\left(X^{11}\right)=0 \\
H\left(X^{12}\right)=-\left(\frac{2}{3} \log _{2} \frac{2}{3}+\frac{1}{3} \log _{2} \frac{1}{3}\right)=0.918 \\
H\left(X^{13}\right)=0
\end{array}\)

根据公式 2计算根蒂属性的信息增益如下:

\(\begin{aligned}
G\left(X^{1}, 根蒂\right)=& H\left(X^{1}\right)-\sum_{k=1}^{3} \frac{\left|X^{1 k}\right|}{|X|} H\left(X^{1 k}\right) \\
&=0.764-\left(\frac{5}{9} \times 0+\frac{3}{9} \times 0.918+\frac{1}{9} \times 0\right) \\
&=0.458
\end{aligned}\)

同理,计算出色泽、敲声、脐部和触感的信息增益:

\(G\left(X^{1}, 色泽\right)=0.043\)

\(G\left(X^{1}, 敲声\right)=0.331\)

\(G\left(X^{1}, 脐部\right)=0.458\)

\(G\left(X^{1}, 触感\right)=0.458\)

在剩下属性中,根蒂、脐部和触感的信息增益都最大,因此随机选择一个选为划分属性即可,即此时划分如图 4所示。

图 4 基于根蒂属性对子结点进行划分

根蒂属性为蜷缩的结点中全为好瓜,该结点为叶节点不用继续划分,对应的决策结果为好瓜。根蒂属性为硬挺的结点中全为坏瓜,该结点为叶节点不用继续划分,对应的决策结果为坏瓜。

依据上述规则循环递归每个分支,可以得到最终的决策树。

引用:

[1] Shannon C E. A mathematical theory of communication[J]. The Bell system technical journal, 1948, 27(3): 379-423.

[2] Mitchell, Tom M. Machine Learning. McGraw-Hill, 1997.

信息熵与ID3决策树》有1个想法

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注