决策树（本文使用id3算法的准则决策）

1. 决策树的背景

决策树是一种常见的机器学习方法。决策树由根节点、内部节点、叶子节点和边组成。叶子节点对应每个决策结果，内部节点对应一个属性的测试。

2. 决策树实战

在生成决策树的过程，会用到信息熵和信息增益：

信息熵(information entropy)是度量样本集合的纯度。假定当前样本集合 \(D\) 中第\(k\)类样本所占的比例为\(p_k\)，则 \(D\) 的信息熵定义为：

\[Ent(D)=-\sum_{k=1}^{|y|}{p_klog_{2}p_k} \]

一般认为，熵值越大纯度越小，混乱程度越大。

注意：计算信息熵时，若\(p=0\),则\(plog_2{p}=0\).

根据熵的定义计算每个分支的信息熵：

假设离散属性\(a\)有\(V\)个可能的取值\(\{a^1,a^2,...,a^V\}\)，若使用\(a\)来对样本集\(D\)进行划分，则会产生\(V\)个分支结点，其中第\(v\)个分支结点包含了\(D\)中所有在属性\(a\)上取值为\(a^v\)的样本，记为\(D^v\).考虑到分支结点包含的样本数目不同，给予每个分支结点一个权重\(\frac{|D^v|}{|D|}\),即样本数越多的分支结点的影响越大。下面是用属性\(a\)对数据集\(D\)进行划分所获得的信息增益(information gain)为：

\[Gain(D,a)=Ent(D)-\sum_{v=1}^V{\frac{|D^v|}{|D|}Ent(D^v)} \]

一般，信息增益越大，则意味着使用属性\(a\)来划分所获得的纯度提升越大。

表一

ID	年龄	有工作	有自己的房子	信贷情况	类别
1	青年	否	否	一般	否
2	青年	否	否	好	否
3	青年	是	否	好	是
4	青年	是	是	一般	是
5	青年	否	否	一般	否
6	中年	否	否	一般	否
7	中年	否	否	好	否
8	中年	是	是	好	是
9	中年	否	是	非常好	是
10	中年	否	是	非常好	是
11	老年	否	是	非常好	是
12	老年	否	是	好	是
13	老年	是	否	好	是
14	老年	是	否	非常好	是
15	老年	否	否	一般	否

属性集{年龄，有工作，有自己的房子，信贷情况}

标签集{9是，6否}

\[Ent(D) =-(\frac{9}{15}log_2{\frac{9}{15}+\frac{6}{15}log_2{\frac{6}{15}}}) =0.97 \]

graph TB id1[年龄]--青年-->id2[2是</br>3否</br>5] id1[年龄]--中年-->id3[3是</br>2否</br>5] id1[年龄]--老年-->id4[4是</br>1否</br>5]

\[Ent(青年) = -(\frac{2}{5}log_2{\frac{2}{5}}+\frac{3}{5}log_2{\frac{3}{5}})=0.97 \\ Ent(中年) = -(\frac{3}{5}log_2{\frac{3}{5}}+\frac{2}{5}log_2{\frac{2}{5}})=0.97 \\ Ent(老年) = -(\frac{4}{5}log_2{\frac{4}{5}}+\frac{1}{5}log_2{\frac{1}{5}})=0.72 \\ w_{青年}=\frac{5}{15} \\ w_{中年}=\frac{5}{15} \\ w_{老年}=\frac{5}{15} \\ Gain(D,年龄) = Ent(D)-\frac{1}{3}(0.97+0.97+0.72)=0.083 \]

graph TB id1[有工作]--是-->id2[5是</br>0否</br>5] id1[有工作]--否-->id3[4是</br>6否</br>10]

\[Ent(是) = -(\frac{0}{5}log_2{\frac{0}{5}}+\frac{5}{5}log_2{\frac{5}{5}})=0 \\ Ent(否) = -(\frac{6}{10}log_2{\frac{6}{10}}+\frac{4}{10}log_2{\frac{4}{10}})=0.97 \\ w_{是}=\frac{5}{15}=\frac{1}{3} \\ w_{否}=\frac{10}{15}=\frac{2}{3} \\ Gain(D,有工作)=0.97-0.97\times{\frac{2}{3}}=0.97\times{\frac{1}{3}}=0.324 \]

graph TB id1[有自己的房子]--是-->id2[6是</br>0否</br>6] id1[有自己的房子]--否-->id3[3是</br>6否</br>9]

\[Ent(是) = -(\frac{0}{6}log_2{\frac{0}{6}}+\frac{6}{6}log_2{\frac{6}{6}})=0 \\ Ent(否) = -(\frac{3}{9}log_2{\frac{3}{9}}+\frac{6}{9}log_2{\frac{6}{9}})=0.917 \\ w_{是}=\frac{6}{15}=\frac{2}{5} \\ w_{否}=\frac{9}{15}=\frac{3}{5} \\ Gain(D,有自己的房子)=0.97-0.917\times{\frac{3}{5}}=0.420 \]

graph TB id1[信贷情况]--一般-->id2[1是</br>4否</br>5] id1[信贷情况]--好-->id3[4是</br>2否</br>6] id1[信贷情况]--非常好-->id4[4是</br>0否</br>4]

\[Ent(一般) = -(\frac{1}{5}log_2{\frac{1}{5}}+\frac{4}{5}log_2{\frac{4}{5}})=0.72 \\ Ent(好) = -(\frac{4}{6}log_2{\frac{4}{6}}+\frac{2}{6}log_2{\frac{2}{6}})=0.917 \\ Ent(非常好) = -(\frac{4}{4}log_2{\frac{4}{4}}+\frac{0}{4}log_2{\frac{0}{4}})=0 \\ w_{一般}=\frac{5}{15} \\ w_{好}=\frac{6}{15} \\ w_{非常好}=\frac{4}{15} \\ Gain(D,信贷情况) = Ent(D)-(\frac{1}{3}\times0.72+\frac{2}{5}\times0.917)=0.97-0.6068=0.363 \]

从上面计算可以看出，“有自己的房子”的属性划分数据集后的信息增益最大，所以选择“有自己的房子”作为根结点。

下表是“没有房子”的列表：

表二
（a）

ID	年龄	有工作	信贷情况	类别
1	青年	否	一般	否
2	青年	否	好	否
3	青年	是	好	是
5	青年	否	一般	否
6	中年	否	一般	否
7	中年	否	好	否
13	老年	是	好	是
14	老年	是	非常好	是
15	老年	否	一般	否

（b）

ID	年龄	有工作	信贷情况	类别
4	青年	是	一般	是
8	中年	是	好	是
9	中年	否	非常好	是
10	中年	否	非常好	是
11	老年	否	非常好	是
12	老年	否	好	是

类别标记{6否，3是}

\[Ent(没房子)=-(\frac{3}{9}\times{log_2{\frac{3}{9}}}+\frac{6}{9}\times{log_2{\frac{6}{9}}})=0.917 \]

计算表二中每个属性的信息增益：

graph TB id1[年龄]--青年-->id2[1是</br>3否</br>4] id1[年龄]--中年-->id3[0是</br>2否</br>2] id1[年龄]--老年-->id4[2是</br>1否</br>3]

\[Ent(青年)=-(\frac{1}{4}\times{log_2{\frac{1}{4}}}+\frac{3}{4}\times{log_2{\frac{3}{4}}})=0.8113 \\ Ent(中年)=-(\frac{0}{2}\times{log_2{\frac{0}{2}}}+\frac{2}{2}\times{log_2{\frac{2}{2}}})=0 \\ Ent(老年)=-(\frac{2}{3}\times{log_2{\frac{2}{3}}}+\frac{1}{3}\times{log_2{\frac{1}{3}}})=0.9183 \\ w_{青年} = \frac{4}{9} \\ w_{中年} = \frac{2}{9} \\ w_{老年} = \frac{3}{9} \\ Gain(没房子，年龄)=0.917-(\frac{4}{9}\times0.8113+\frac{2}{9}\times0+\frac{3}{9}\times0.9183)=0.2503 \]

graph TB id1[有工作]--是-->id2[3是</br>0否</br>3] id1[有工作]--否-->id3[0是</br>6否</br>6]

\[Ent(是)=-(\frac{3}{3}\times{log_2{\frac{3}{3}}}+\frac{0}{3}\times{log_2{\frac{0}{3}}})=0 \\ Ent(否)=-(\frac{0}{6}\times{log_2{\frac{0}{6}}}+\frac{6}{6}\times{log_2{\frac{6}{6}}})=0 \\ w_{是} = \frac{3}{9} \\ w_{否} = \frac{6}{9} \\ Gain(没房子，年龄)=0.917-(\frac{3}{9}\times0+\frac{6}{9}\times0)=0.917 \]

graph TB id1[信贷情况]--一般-->id2[0是</br>4否</br>4] id1[信贷情况]--好-->id3[2是</br>2否</br>4] id1[信贷情况]--非常好-->id4[1是</br>0否</br>1]

\[Ent(一般) = -(\frac{0}{4}log_2{\frac{0}{4}}+\frac{4}{4}log_2{\frac{4}{4}})=0 \\ Ent(好) = -(\frac{2}{4}log_2{\frac{2}{4}}+\frac{2}{4}log_2{\frac{2}{4}})=1 \\ Ent(非常好) = -(\frac{1}{1}log_2{\frac{1}{1}}+\frac{0}{1}log_2{\frac{0}{1}})=0 \\ w_{一般}=\frac{4}{9} \\ w_{好}=\frac{4}{9} \\ w_{非常好}=\frac{1}{9} \\ Gain(D,信贷情况) = Ent(D)-(\frac{4}{9}\times0+\frac{4}{9}\times1+\frac{1}{9}\times0)= 0.4726 \]

从上面计算可以看出，“有工作”的属性划分“没有房子”数据集后的信息增益最大，所以选择“有工作”作为没有自己房子的下一个结点。

下表是“有房子”的列表：

表三

ID	年龄	有工作	信贷情况	类别
3	青年	是	好	是
13	老年	是	好	是
14	老年	是	非常好	是

表四

ID	年龄	信贷情况	类别
1	青年	一般	否
2	青年	好	否
5	青年	一般	否
6	中年	一般	否
7	中年	好	否
15	老年	一般	否

graph TB id1[有自己的房子]--否-->id3[有工作] id1[有自己的房子]--是-->id2[是] id3[有工作]--否-->id5[否] id3[有工作]--是-->id4[是]

参考文献:
周志华. 机器学习[M].北京：清华出版社,2016:73-93.