当前位置：首页 > article >正文

机器学习之决策树（DecisionTree——C4.5）

article 2025/1/23 19:28:12

在机器学习之决策树（DecisionTree——ID3）中我们提到，ID3无法处理是连续值或有缺失值的属性。而C4.5算法可以解决ID3算的上述局限性。

1、连续值属性的处理

对于数据集 $D$ 和连续值属性 $A$ ，假设连续值属性 $A$ 有 $M$ 个不同的取值，可通过二分法bi-partition对联组织属性进行离散化处理，即：

对 $M$ 个不同的取值由小到大排序，得到排序后的取值，记为 ${a^1, a^2, ..., a^M\}$ ；
对相邻的属性取值 $a^{i}$ 与 $a^{i+1}$ ，取其均值作为划分点，即 $\frac{a^{i}+a^{i+1}}{2}$ ，划分后的子集表示为 $D_t^-$ 和 $D_t^+$ ；
对于连续值属性 $A$ ，可获得包含 $M - 1$ 个元素的候选划分点集合：
$T_A=\{\frac{a^{i}+a^{i+1}}{2}|1≤i≤M-1\}\tag1$
像离散属性值一样开考察上述候选划分点，选取最优的划分点进行样本集合的划分：
$\begin{aligned} Gain(D, A)&=\mathop{\max}\limits_{t\in T_a}Gain(D, A, t)\\ &=\mathop{\max}\limits_{t\in T_a}(Entropy(D)-\sum_{\lambda\in \{-, +\}}\frac{N_t^{\lambda}}{N}Entropy(D_t^{\lambda}))\tag2 \end{aligned}$
式(2)中， $G ain (D, A, t)$ 是样本集 $D$ 基于划分点 $t$ 二分后的信息增益， $D_t^{\lambda}$ 表示二分后的子集， $N_t^{\lambda}$ 表示二分后的子集的样本数量。

表1 西瓜数据集3.0

编号	色泽	根蒂	敲声	纹理	脐部	触感	密度	含糖率	好瓜
1	青绿	蜷缩	浊响	清晰	凹陷	硬滑	0.697	0.460	是
2	乌黑	蜷缩	沉闷	清晰	凹陷	硬滑	0.774	0.376	是
3	乌黑	蜷缩	浊响	清晰	凹陷	硬滑	0.634	0.264	是
4	青绿	蜷缩	沉闷	清晰	凹陷	硬滑	0.608	0.318	是
5	浅白	蜷缩	浊响	清晰	凹陷	硬滑	0.556	0.215	是
6	青绿	稍蜷	浊响	清晰	稍凹	软粘	0.403	0.237	是
7	乌黑	稍蜷	浊响	稍糊	稍凹	软粘	0.481	0.149	是
8	乌黑	稍蜷	浊响	清晰	稍凹	硬滑	0.437	0.211	是
9	乌黑	稍蜷	沉闷	稍糊	稍凹	硬滑	0.666	0.091	否
10	青绿	硬挺	清脆	清晰	平坦	软粘	0.243	0.267	否
11	浅白	硬挺	清脆	模糊	平坦	硬滑	0.245	0.057	否
12	浅白	蜷缩	浊响	模糊	平坦	软粘	0.343	0.099	否
13	青绿	稍蜷	浊响	稍糊	凹陷	硬滑	0.639	0.161	否
14	浅白	稍蜷	沉闷	稍糊	凹陷	硬滑	0.657	0.198	否
15	乌黑	稍蜷	浊响	清晰	稍凹	软粘	0.360	0.370	否
16	浅白	蜷缩	浊响	模糊	平坦	硬滑	0.593	0.042	否
17	青绿	蜷缩	沉闷	稍糊	稍凹	硬滑	0.719	0.103	否

表1中的西瓜数据集包含17个样本（ $n = 1, 2, 3, ..., 17$ ），每个样本有8个属性（ $k = 1, 2, 3, ..., 8$ ），样本共计有2个类别（ $c = 是, 否$ ）。17个样本中，好瓜样本有8个、差瓜样本有9个，数据集 $D$ 信息熵为：
$Entropy(D)=-(\frac{8}{17}\log\frac{8}{17}+\frac{9}{17}\log\frac{9}{17})=0.9975$

以属性"含糖率"为例，17个样本的在该属性的取值由小到大排序后为：

表2 西瓜数据集3.0——sort("含糖率")

编号	色泽	根蒂	敲声	纹理	脐部	触感	密度	含糖率	好瓜
16	浅白	蜷缩	浊响	模糊	平坦	硬滑	0.593	0.042	否
11	浅白	硬挺	清脆	模糊	平坦	硬滑	0.245	0.057	否
9	乌黑	稍蜷	沉闷	稍糊	稍凹	硬滑	0.666	0.091	否
12	浅白	蜷缩	浊响	模糊	平坦	软粘	0.343	0.099	否
17	青绿	蜷缩	沉闷	稍糊	稍凹	硬滑	0.719	0.103	否
7	乌黑	稍蜷	浊响	稍糊	稍凹	软粘	0.481	0.149	是
13	青绿	稍蜷	浊响	稍糊	凹陷	硬滑	0.639	0.161	否
14	浅白	稍蜷	沉闷	稍糊	凹陷	硬滑	0.657	0.198	否
8	乌黑	稍蜷	浊响	清晰	稍凹	硬滑	0.437	0.211	是
5	浅白	蜷缩	浊响	清晰	凹陷	硬滑	0.556	0.215	是
6	青绿	稍蜷	浊响	清晰	稍凹	软粘	0.403	0.237	是
3	乌黑	蜷缩	浊响	清晰	凹陷	硬滑	0.634	0.264	是
10	青绿	硬挺	清脆	清晰	平坦	软粘	0.243	0.267	否
4	青绿	蜷缩	沉闷	清晰	凹陷	硬滑	0.608	0.318	是
15	乌黑	稍蜷	浊响	清晰	稍凹	软粘	0.360	0.370	否
2	乌黑	蜷缩	沉闷	清晰	凹陷	硬滑	0.774	0.376	是
1	青绿	蜷缩	浊响	清晰	凹陷	硬滑	0.697	0.460	是

17个样本的在该属性的二分候选划分点为：

0.042
0.057
0.091
0.099
0.103
0.149
0.161
0.198
0.211
0.215
0.237
0.264
0.267
0.318
0.370
0.376
0.460

0.0495
0.074
0.095
0.101
0.126
0.155
0.1795
0.2045
0.213
0.226
0.2505
0.2655
0.2925
0.344
0.373
0.418

当划分点为0.0495，划分后两个子集分别为 $D_{0.0495}^-$ ：{16}和 $D_{0.0495}^+$ ：{11, 9, 12, 17, 7, 13, 14, 8, 5, 6, 3, 10, 4, 15, 2, 1}
$\begin{aligned} Entropy(D_{0.0495}^-)&=-(\frac{0}{1}\log\frac{0}{1}+\frac{1}{1}\log\frac{1}{1})=0\\ Entropy(D_{0.0495}^+)&=-(\frac{8}{16}\log\frac{8}{16}+\frac{8}{16}\log\frac{8}{16})=1.0\\ Gain(D, 含糖率, 0.0495)&= Entropy(D)-\sum_{\lambda\in\{-, +\}}\frac{N_{0.0495}^{\lambda}}{N} Entropy(D_{0.126}^{\lambda})\\ &= 0.9975-(\frac{1}{17}*0+\frac{16}{17}*1.0)\\ &=0.0563 \end{aligned}$
当划分点为0.074，划分后两个子集分别为 $D_{0.074}^-$ ：{16, 11}和 $D_{0.074}^+$ ：{9, 12, 17, 7, 13, 14, 8, 5, 6, 3, 10, 4, 15, 2, 1}
$\begin{aligned} Gain(D, 含糖率, 0.074)&= 0.9975-\{\frac{2}{17}*[-(\frac{0}{2}\log\frac{0}{2}+\frac{2}{2}\log\frac{2}{2})]+\frac{15}{17}*[-(\frac{8}{15}\log\frac{8}{15}+\frac{7}{15}\log\frac{7}{15})]\}=0.1179 \end{aligned}$
当划分点为0.095，划分后两个子集分别为 $D_{0.074}^-$ ：{16, 11, 9}和 $D_{0.074}^+$ ：{12, 17, 7, 13, 14, 8, 5, 6, 3, 10, 4, 15, 2, 1}
$\begin{aligned} Gain(D, 含糖率, 0.095)&= 0.9975-\{\frac{3}{17}*[-(\frac{0}{3}\log\frac{0}{3}+\frac{3}{3}\log\frac{3}{3})]+\frac{14}{17}*[-(\frac{8}{14}\log\frac{8}{14}+\frac{6}{14}\log\frac{6}{14})]\}=0.1861 \end{aligned}$
当划分点为0.101，划分后两个子集分别为 $D_{0.101}^-$ ：{16, 11, 9, 12}和 $D_{0.101}^+$ ：{17, 7, 13, 14, 8, 5, 6, 3, 10, 4, 15, 2, 1}
$\begin{aligned} Gain(D, 含糖率, 0.101)&= 0.9975-\{\frac{4}{17}*[-(\frac{0}{4}\log\frac{0}{4}+\frac{4}{4}\log\frac{4}{4})]+\frac{13}{17}*[-(\frac{8}{13}\log\frac{8}{13}+\frac{5}{13}\log\frac{5}{13})]\}=0.2624 \end{aligned}$
当划分点为0.126，划分后两个子集分别为 $D_{0.126}^-$ ：{16, 11, 9, 12, 17}和 $D_{0.126}^+$ ：{7, 13, 14, 8, 5, 6, 3, 10, 4, 15, 2, 1}
$\begin{aligned} Gain(D, 含糖率, 0.126)&= 0.9975-\{\frac{5}{17}*[-(\frac{0}{5}\log\frac{0}{5}+\frac{5}{5}\log\frac{5}{5})]+\frac{12}{17}*[-(\frac{8}{12}\log\frac{8}{12}+\frac{4}{12}\log\frac{4}{12})]\}=0.3492 \end{aligned}$
当划分点为0.155，划分后两个子集分别为 $D_{0.155}^-$ ：{16, 11, 9, 12, 17, 7}和 $D_{0.155}^+$ ：{13, 14, 8, 5, 6, 3, 10, 4, 15, 2, 1}
$\begin{aligned} Gain(D, 含糖率, 0.155)&= 0.9975-\{\frac{6}{17}*[-(\frac{1}{6}\log\frac{1}{6}+\frac{5}{6}\log\frac{5}{6})]+\frac{11}{17}*[-(\frac{7}{11}\log\frac{7}{11}+\frac{4}{11}\log\frac{4}{11})]\}=0.1561 \end{aligned}$
当划分点为0.1795，划分后两个子集分别为 $D_{0.1795}^-$ ：{16, 11, 9, 12, 17, 7, 13}和 $D_{0.1795}^+$ ：{14, 8, 5, 6, 3, 10, 4, 15, 2, 1}
$\begin{aligned} Gain(D, 含糖率, 0.1795)&= 0.9975-\{\frac{7}{17}*[-(\frac{1}{7}\log\frac{1}{7}+\frac{6}{7}\log\frac{6}{7})]+\frac{10}{17}*[-(\frac{7}{10}\log\frac{7}{10}+\frac{3}{10}\log\frac{3}{10})]\}=0.2354 \end{aligned}$
当划分点为0.2045，划分后两个子集分别为 $D_{0.2045}^-$ ：{16, 11, 9, 12, 17, 7, 13, 14}和 $D_{0.2045}^+$ ：{8, 5, 6, 3, 10, 4, 15, 2, 1}
$\begin{aligned} Gain(D, 含糖率, 0.2045)&= 0.9975-\{\frac{8}{17}*[-(\frac{1}{8}\log\frac{1}{8}+\frac{7}{8}\log\frac{7}{8})]+\frac{9}{17}*[-(\frac{7}{9}\log\frac{7}{9}+\frac{2}{9}\log\frac{2}{9})]\}=0.3371 \end{aligned}$
当划分点为0.213，划分后两个子集分别为 $D_{0.213}^-$ ：{16, 11, 9, 12, 17, 7, 13, 14, 8}和 $D_{0.213}^+$ ：{5, 6, 3, 10, 4, 15, 2, 1}
$\begin{aligned} Gain(D, 含糖率, 0.213)&= 0.9975-\{\frac{9}{17}*[-(\frac{2}{9}\log\frac{2}{9}+\frac{7}{9}\log\frac{7}{9})]+\frac{8}{17}*[-(\frac{6}{8}\log\frac{6}{8}+\frac{2}{8}\log\frac{2}{8})]\}=0.2111 \end{aligned}$
当划分点为0.226，划分后两个子集分别为 $D_{0.226}^-$ ：{16, 11, 9, 12, 17, 7, 13, 14, 8, 5}和 $D_{0.226}^+$ ：{6, 3, 10, 4, 15, 2, 1}
$\begin{aligned} Gain(D, 含糖率, 0.226)&= 0.9975-\{\frac{10}{17}*[-(\frac{3}{10}\log\frac{3}{10}+\frac{7}{10}\log\frac{7}{10})]+\frac{7}{17}*[-(\frac{5}{7}\log\frac{5}{7}+\frac{2}{7}\log\frac{2}{7})]\}=0.1237 \end{aligned}$
当划分点为0.2505，划分后两个子集分别为 $D_{0.2505}^-$ ：{16, 11, 9, 12, 17, 7, 13, 14, 8, 5, 6}和 $D_{0.2505}^+$ ：{3, 10, 4, 15, 2, 1}
$\begin{aligned} Gain(D, 含糖率, 0.2505)&= 0.9975-\{\frac{11}{17}*[-(\frac{4}{11}\log\frac{4}{11}+\frac{7}{11}\log\frac{7}{11})]+\frac{6}{17}*[-(\frac{4}{6}\log\frac{4}{6}+\frac{2}{6}\log\frac{2}{6})]\}=0.0615 \end{aligned}$
当划分点为0.2655，划分后两个子集分别为 $D_{0.2655}^-$ ：{16, 11, 9, 12, 17, 7, 13, 14, 8, 5, 6, 3}和 $D_{0.2655}^+$ ：{10, 4, 15, 2, 1}
$\begin{aligned} Gain(D, 含糖率, 0.2655)&= 0.9975-\{\frac{12}{17}*[-(\frac{5}{12}\log\frac{5}{12}+\frac{7}{12}\log\frac{7}{12})]+\frac{5}{17}*[-(\frac{3}{5}\log\frac{3}{5}+\frac{2}{5}\log\frac{2}{5})]\}=0.0202 \end{aligned}$
当划分点为0.2925，划分后两个子集分别为 $D_{0.2925}^-$ ：{16, 11, 9, 12, 17, 7, 13, 14, 8, 5, 6, 3, 10}和 $D_{0.2925}^+$ ：{4, 15, 2, 1}
$\begin{aligned} Gain(D, 含糖率, 0.2925)&= 0.9975-\{\frac{13}{17}*[-(\frac{5}{13}\log\frac{5}{13}+\frac{8}{13}\log\frac{8}{13})]+\frac{4}{17}*[-(\frac{3}{4}\log\frac{3}{4}+\frac{1}{4}\log\frac{1}{4})]\}=0.0715 \end{aligned}$
当划分点为0.344，划分后两个子集分别为 $D_{0.344}^-$ ：{16, 11, 9, 12, 17, 7, 13, 14, 8, 5, 6, 3, 10, 4}和 $D_{0.344}^+$ ：{15, 2, 1}
$\begin{aligned} Gain(D, 含糖率, 0.344)&= 0.9975-\{\frac{14}{17}*[-(\frac{6}{14}\log\frac{6}{14}+\frac{8}{14}\log\frac{8}{14})]+\frac{3}{17}*[-(\frac{2}{3}\log\frac{2}{3}+\frac{1}{3}\log\frac{1}{3})]\}=0.0241 \end{aligned}$
当划分点为0.373，划分后两个子集分别为 $D_{0.373}^-$ ：{16, 11, 9, 12, 17, 7, 13, 14, 8, 5, 6, 3, 10, 4, 15}和 $D_{0.373}^+$ ：{2, 1}
$\begin{aligned} Gain(D, 含糖率, 0.373)&= 0.9975-\{\frac{15}{17}*[-(\frac{6}{15}\log\frac{6}{15}+\frac{9}{15}\log\frac{9}{15})]+\frac{2}{17}*[-(\frac{2}{2}\log\frac{2}{2}+\frac{0}{2}\log\frac{0}{2})]\}=0.1041 \end{aligned}$
当划分点为0.373，划分后两个子集分别为 $D_{0.373}^-$ ：{16, 11, 9, 12, 17, 7, 13, 14, 8, 5, 6, 3, 10, 4, 15, 2}和 $D_{0.373}^+$ ：{1}
$\begin{aligned} Gain(D, 含糖率, 0.418)&= 0.9975-\{\frac{16}{17}*[-(\frac{7}{16}\log\frac{7}{16}+\frac{9}{16}\log\frac{9}{16})]+\frac{1}{17}*[-(\frac{1}{1}\log\frac{1}{1}+\frac{0}{1}\log\frac{0}{1})]\}=0.0669 \end{aligned}$

因此，属性"含糖率"划分后的最大信息增益为0.349，对应划分点为0.126：
$\begin{aligned} Gain(D, 含糖率)&=Gain(D, 含糖率, t=0.126)=0.3492 \end{aligned}$
同理，属性"密度"划分后的最大信息增益为0.2624，对应划分点为0.3815：
$\begin{aligned} Gain(D, 密度)&=Gain(D, 密度, t=0.3815)=0.2624 \end{aligned}$

以如此方式即可处理连续值的属性。

2、缺失值属性的处理

表3 西瓜数据集——缺失值

编号	色泽	根蒂	敲声	纹理	脐部	触感	好瓜
1	—	蜷缩	浊响	清晰	凹陷	硬滑	是
2	乌黑	蜷缩	沉闷	清晰	凹陷	—	是
3	乌黑	蜷缩	—	清晰	凹陷	硬滑	是
4	青绿	蜷缩	沉闷	清晰	凹陷	硬滑	是
5	—	蜷缩	浊响	清晰	凹陷	硬滑	是
6	青绿	稍蜷	浊响	清晰	—	软粘	是
7	乌黑	稍蜷	浊响	稍糊	稍凹	软粘	是
8	乌黑	稍蜷	浊响	—	稍凹	硬滑	是
9	乌黑	—	沉闷	稍糊	稍凹	硬滑	否
10	青绿	硬挺	清脆	—	平坦	软粘	否
11	浅白	硬挺	清脆	模糊	平坦	—	否
12	浅白	蜷缩	—	模糊	平坦	软粘	否
13	—	稍蜷	浊响	稍糊	凹陷	硬滑	否
14	浅白	稍蜷	沉闷	稍糊	凹陷	硬滑	否
15	乌黑	稍蜷	浊响	清晰	—	软粘	否
16	浅白	蜷缩	浊响	模糊	平坦	硬滑	否
17	青绿	—	沉闷	稍糊	稍凹	硬滑	否

（1）如何在属性值确实的情况下进行划分属性选择？

给定训练集 $D$ 和属性 $A$ ，假设 $\widetilde{D}$ 表示属性 $A$ 上没有缺失值的样本子集，假定属性 $A$ 有 $m$ 个可取值 ${a^1, a^2, ..., a^m\}$ ， $\widetilde{D}^m$ 表示 $\widetilde{D}$ 中属性 $A$ 上取值为 $a^m$ 的样本子集， $\widetilde{D}_k$ 表示 $\widetilde{D}$ 中属于第 $k$ 类（ $k = 1, 2, ..., K$ ）的样本子集，则有 $\widetilde{D}=\cup_{k=1}^{K}\widetilde{D}_k=\cup_{m=1}^{m}\widetilde{D}^m$ ，假定为每一个样本 $x$ 赋予一个权重 $w_x$ 定义：
$\rho=\frac{\sum_{x\in\widetilde{D}}w_x}{\sum_{x\in D}w_x}\\ \widetilde{p}_k=\frac{\sum_{x\in\widetilde{D}_k}w_x}{\sum_{x\in \widetilde{D}}w_x}\\ \widetilde{r}_m=\frac{\sum_{x\in\widetilde{D}^m}w_x}{\sum_{x\in \widetilde{D}}w_x}\\$
式中， $\rho$ 表示无缺失值样本所占的比例， $\widetilde{p}_k$ 表示无缺失值样本中第 $k$ 类所占的比例， $\widetilde{r}_m$ 表示无缺失值样本中属性 $A$ 上取值 $a^m$ 的样本所占的比例，故有 $\sum_{k=1}^K\widetilde{p}_k=\sum_{n=1}^m\widetilde{r}_m=1$

基于上述定义，可将信息增益的计算在缺失值上推广为：
$\begin{aligned} Entropy(\widetilde{D})&=-\sum_{k=1}^{K}\widetilde{p}_k\log\widetilde{p}_k\\ Gain(D, A)&=\rho\times Gain(\widetilde{D}, A)=\rho\times[Entropy(\widetilde{D})-\sum_{m=1}^{m}\widetilde{r}_mEntropy(\widetilde{D}^m)] \end{aligned}$
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17

属性"色泽"，无缺失值样本子集 $\widetilde{D}=\{2,3,4,6,7,8,9,10,11,12,14,15,16,17\}$ ，有"乌黑"、“青绿”、"浅白"3个取值
$\begin{aligned} Gain(D, 色泽)&=\rho\times[Entropy(\widetilde{D})-\sum_{m=1}^{m}\widetilde{r}_mEntropy(\widetilde{D}^m)]\\ &=\frac{14}{17}\times\{-(\frac{6}{14}\log\frac{6}{14}+\frac{8}{14}\log\frac{8}{14})-[\frac{6}{14}\times(-(\frac{4}{6}\log\frac{4}{6}+\frac{2}{6}\log\frac{2}{6}))+\frac{4}{14}\times(-(\frac{2}{4}\log\frac{2}{4}+\frac{2}{4}\log\frac{2}{4}))+\frac{4}{14}\times(-(\frac{0}{4}\log\frac{0}{4}+\frac{4}{4}\log\frac{4}{4}))]\}\\ &=0.2519 \end{aligned}$
属性"根蒂"，无缺失值样本子集 $\widetilde{D}=\{1,2,3,4,5,6,7,8,10,11,12,13,14,15,16\}$ ，有"蜷缩"、“稍蜷”、"硬挺"3个取值
$\begin{aligned} Gain(D, 根蒂)&=\frac{15}{17}\times\{- (\frac{8}{15}\log\frac{8}{15}+\frac{7}{15}\log\frac{7}{15})- [\frac{7}{15}\times(-(\frac{5}{7}\log\frac{5}{7}+\frac{2}{7}\log\frac{2}{7}))+ \frac{6}{15}\times(-(\frac{3}{6}\log\frac{3}{6}+\frac{3}{6}\log\frac{3}{6}))+ \frac{2}{15}\times(-(\frac{0}{2}\log\frac{0}{2}+\frac{2}{2}\log\frac{2}{2}))]\}\\ &=0.1711 \end{aligned}$
属性"敲声"，无缺失值样本子集 $\widetilde{D}=\{1,2,4,5,6,7,8,9,10,11,13,14,15,16,17\}$ ，有"浊响"、“沉闷”、"清脆"3个取值
$\begin{aligned} Gain(D, 敲声)&=\frac{15}{17}\times\{- (\frac{7}{15}\log\frac{7}{15}+\frac{8}{15}\log\frac{8}{15})- [\frac{8}{15}\times(-(\frac{5}{8}\log\frac{5}{8}+\frac{3}{8}\log\frac{3}{8}))+ \frac{5}{15}\times(-(\frac{2}{5}\log\frac{2}{5}+\frac{3}{5}\log\frac{3}{5}))+ \frac{2}{15}\times(-(\frac{0}{2}\log\frac{0}{2}+\frac{2}{2}\log\frac{2}{2}))]\}\\ &=0.1448 \end{aligned}$
属性"纹理"，无缺失值样本子集 $\widetilde{D}=\{1,2,3,4,5,6,7,9,11,12,13,14,15,16,17\}$ ，有"清晰"、“稍糊”、"模糊"3个取值
$\begin{aligned} Gain(D, 纹理)&=\frac{15}{17}\times\{- (\frac{7}{15}\log\frac{7}{15}+\frac{8}{15}\log\frac{8}{15})- [\frac{7}{15}\times(-(\frac{6}{7}\log\frac{6}{7}+\frac{1}{7}\log\frac{1}{7}))+ \frac{5}{15}\times(-(\frac{1}{5}\log\frac{1}{5}+\frac{4}{5}\log\frac{4}{5}))+ \frac{3}{15}\times(-(\frac{0}{3}\log\frac{0}{3}+\frac{3}{3}\log\frac{3}{3}))]\}\\ &=0.4235 \end{aligned}$
属性"脐部"，无缺失值样本子集 $\widetilde{D}=\{1,2,3,4,5,7,8,9,10,11,12,13,14,16,17\}$ ，有"凹陷"、“稍凹”、"平坦"3个取值
$\begin{aligned} Gain(D, 脐部)&=\frac{15}{17}\times\{- (\frac{7}{15}\log\frac{7}{15}+\frac{8}{15}\log\frac{8}{15})- [\frac{7}{15}\times(-(\frac{5}{7}\log\frac{5}{7}+\frac{2}{7}\log\frac{2}{7}))+ \frac{4}{15}\times(-(\frac{2}{4}\log\frac{2}{4}+\frac{2}{4}\log\frac{2}{4}))+ \frac{4}{15}\times(-(\frac{0}{4}\log\frac{0}{4}+\frac{4}{4}\log\frac{4}{4}))]\}\\ &=0.2888 \end{aligned}$
属性"触感"，无缺失值样本子集 $\widetilde{D}=\{1,3,4,5,6,7,8,9,10,12,13,14,15,16,17\}$ ，有"硬滑"、"软粘"2个取值
$\begin{aligned} Gain(D, 脐部)&=\frac{15}{17}\times\{- (\frac{7}{15}\log\frac{7}{15}+\frac{8}{15}\log\frac{8}{15})- [\frac{10}{15}\times(-(\frac{5}{10}\log\frac{5}{10}+\frac{5}{10}\log\frac{5}{10}))+ \frac{5}{15}\times(-(\frac{2}{5}\log\frac{2}{5}+\frac{3}{5}\log\frac{3}{5}))]\}\\ &=0.0057 \end{aligned}$
（2）给定划分属性，若样本在该属性上确实，如何对样本进行划分？
如果样本在划分属性上的取值已知，则将其分裂到与其取值对应的子节点，且样本权重在子节点中保持为1；
如若样本在划分属性上的取值未知，则将其同时分裂到所有子节点中，在各子节点中的权重为对应子节点的样本权重 $\rho$ 。

属性"纹理"的信息增益最大，用于进一步分裂，包含15个取值已知（清晰7个、稍糊5个、模糊3个）和2个取值未知的样本{8,10}。

属性: 取值	样本	好瓜	差瓜	缺失值	缺失值权重	总权重
纹理:清晰	{1,2,3,4,5,6,15}	{1,2,3,4,5,6}	{15}	{8,10}	$2\times\frac{7}{15}$	$7+2\times\frac{7}{15}$
纹理:稍糊	{7,9,13,14,17}	{7}	{9,13,14,17}	{8,10}	$2\times\frac{5}{15}$	$5+2\times\frac{5}{15}$
纹理:模糊	{11,12,16}	-	{11,12,16}	{8,10}	$2\times\frac{3}{15}$	$3+2\times\frac{3}{15}$

子节点属性纹理=清晰，包含7个有取值样本{1,2,3,4,5,6,15}，其中6个好瓜和1个差瓜，假设属性在缺失值处对应的类别分布与原始样本一致，分别为 $\frac{6}{7}$ 和 $\frac{1}{7}$ ，则子节点属性纹理=清晰的信息熵为：
$\begin{aligned} Entropy(D^{纹理=清晰})&=-\sum_{i=1}^{k}p_i\log p_i\\ &=-(\frac{6+\frac{6}{7}\times\frac{7}{15}\times2}{7+\frac{7}{15}\times2}\log\frac{6+\frac{6}{7}\times\frac{7}{15}\times2}{7+\frac{7}{15}\times2}+\frac{1+\frac{1}{7}\times\frac{7}{15}\times2}{7+\frac{7}{15}\times2}\log\frac{1+\frac{1}{7}\times\frac{7}{15}\times2}{7+\frac{7}{15}\times2})\\ &=0.5916 \end{aligned}$

子节点属性纹理=清晰，计算属性色泽的信息增益
- 色泽=乌黑的样本数为3（2个正样本和1个负样本）；色泽=青绿的样本数为2（2个正样本）；2个缺失值样本
- 缺失值样本的权重：色泽=乌黑的权重 $\frac{3}{5}$ ，总权重为 $2\times\frac{3}{5}=\frac{6}{5}$ ；色泽=青绿的权重 $\frac{2}{5}$ ，总权重为 $2\times\frac{2}{5}=\frac{4}{5}$
- 色泽=乌黑：正样本的权重： $2+\frac{2}{3}\times\frac{3}{5}\times2$ ；负样本的权重： $1+\frac{1}{3}\times\frac{3}{5}\times2$ ；总权重 $2+\frac{2}{3}\times\frac{3}{5}\times2+1+\frac{1}{3}\times\frac{3}{5}\times2=3+\frac{3}{5}\times2$
  $\begin{aligned} Entropy(D^{纹理=清晰},色泽=乌黑)&=-(\frac{2+\frac{2}{3}\times\frac{3}{5}\times2}{3+\frac{3}{5}\times2}\log\frac{2+\frac{2}{3}\times\frac{3}{5}\times2}{3+\frac{3}{5}\times2}+\frac{1+\frac{1}{3}\times\frac{3}{5}\times2}{3+\frac{3}{5}\times2}\log\frac{1+\frac{1}{3}\times\frac{3}{5}\times2}{3+\frac{3}{5}\times2})=0.6589 \end{aligned}$
- 色泽=青绿：正样本的权重： $2+\frac{2}{2}\times\frac{2}{5}\times2$ ；负样本的权重： $0+\frac{0}{2}\times\frac{2}{5}\times2$ ；总权重 $2+\frac{2}{2}\times\frac{2}{5}\times2+0+\frac{0}{2}\times\frac{2}{5}\times2=2+\frac{2}{5}\times2$
  $\begin{aligned} Entropy(D^{纹理=清晰},色泽=青绿)&=-(\frac{2+\frac{2}{5}\times2}{2+\frac{2}{5}\times2}\log\frac{2+\frac{2}{5}\times2}{2+\frac{2}{5}\times2}+\frac{0+\frac{0}{2}\times\frac{2}{5}\times2}{2+\frac{2}{5}\times2}\log\frac{0+\frac{0}{2}\times\frac{2}{5}\times2}{2+\frac{2}{5}\times2})=0.0 \end{aligned}$

$\begin{aligned} Gain(D^{纹理=清晰},色泽)&=0.5916-(\frac{3+\frac{3}{5}\times2}{7+\frac{7}{15}\times2}\times0.6598+\frac{2+\frac{2}{5}\times2}{7+\frac{7}{15}\times2}\times0.0)&=0.2423 \end{aligned}$

子节点属性纹理=清晰，计算属性根蒂的信息增益
- 根蒂=蜷缩的样本数为5（5个正样本）；根蒂=稍蜷的样本数为2（1个正样本和1个负样本）；无缺失值样本
  $\begin{aligned} Entropy(D^{纹理=清晰},根蒂=蜷缩)&=-(\frac{5}{5}\log\frac{5}{5}+\frac{0}{5}\log\frac{0}{5})=0.0\\ Entropy(D^{纹理=清晰},根蒂=稍蜷)&=-(\frac{1}{2}\log\frac{1}{2}+\frac{1}{2}\log\frac{1}{2})=1.0\\ Gain(D^{纹理=清晰},根蒂)&=0.5916-(\frac{5}{7}\times0.0+\frac{2}{7}\times1.0)=0.3058 \end{aligned}$
子节点属性纹理=清晰，计算属性敲声的信息增益
- 敲声=浊响的样本数为4（3个正样本和1个负样本）；敲声=沉闷的样本数为2（2个正样本）；1个缺失值样本
- 缺失值样本的权重：敲声=浊响的权重 $\frac{4}{6}$ ，总权重为 $\frac{4}{6}$ ；敲声=沉闷的权重 $\frac{2}{6}$ ，总权重为 $\frac{2}{6}$
- 敲声=浊响：正样本的权重： $3+\frac{3}{4}\times\frac{4}{6}$ ；负样本的权重： $1+\frac{1}{4}\times\frac{4}{6}$ ；总权重 $3+\frac{3}{4}\times\frac{4}{6}+1+\frac{1}{4}\times\frac{4}{6}=4+\frac{4}{6}$
  $\begin{aligned} Entropy(D^{纹理=清晰},敲声=浊响)&=-(\frac{3+\frac{3}{4}\times\frac{4}{6}}{4+\frac{4}{6}}\log\frac{3+\frac{3}{4}\times\frac{4}{6}}{4+\frac{4}{6}}+\frac{1+\frac{1}{4}\times\frac{4}{6}}{4+\frac{4}{6}}\log\frac{1+\frac{1}{4}\times\frac{4}{6}}{4+\frac{4}{6}})=0.8112 \end{aligned}$
- 敲声=沉闷：正样本的权重： $2+\frac{2}{2}\times\frac{2}{6}$ ；负样本的权重： $0+\frac{0}{2}\times\frac{2}{6}$ ；总权重 $2+\frac{2}{2}\times\frac{2}{6}+0+\frac{0}{2}\times\frac{2}{6}=2+\frac{2}{6}$
  $\begin{aligned} Entropy(D^{纹理=清晰},敲声=沉闷)&=-(\frac{2+\frac{2}{2}\times\frac{2}{6}}{2+\frac{2}{6}}\log\frac{2+\frac{2}{2}\times\frac{2}{6}}{2+\frac{2}{6}}+\frac{0+\frac{0}{2}\times\frac{2}{6}}{2+\frac{2}{6}}\log\frac{0+\frac{0}{2}\times\frac{2}{6}}{2+\frac{2}{6}})=0.0 \end{aligned}$
  $\begin{aligned} Gain(D^{纹理=清晰},敲声)&=0.5916-(\frac{4+\frac{4}{6}}{7+\frac{7}{15}\times2}\times0.8112+\frac{2+\frac{2}{6}}{7+\frac{7}{15}\times2}\times0.0)&=0.1144 \end{aligned}$