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

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

1、连续值属性的处理

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

1. 对$M$个不同的取值由小到大排序，得到排序后的取值，记为 { a 1 , a 2 , . . . , a M } \{a^1, a^2, ..., a^M\} {a1,a2,...,aM}；
2. 对相邻的属性取值$a^i$与$a^{i+1}$，取其均值作为划分点，即$\frac{a^i+a^{i+1}}{2}$，划分后的子集表示为$D_t^{-}$和$D_t^{+}$；
3. 对于连续值属性$A$，可获得包含$M-1$个元素的候选划分点集合：
   T A = { a i + a i + 1 2 ∣ 1 ≤ i ≤ M − 1 } (1) T_A=\{\frac{a^{i}+a^{i+1}}{2}|1≤i≤M-1\}\tag1 TA​={2ai+ai+1​∣1≤i≤M−1}(1)
4. 像离散属性值一样开考察上述候选划分点，选取最优的划分点进行样本集合的划分：
   G a i n ( D , A ) = max ⁡ t ∈ T a G a i n ( D , A , t ) = max ⁡ t ∈ T a ( E n t r o p y ( D ) − ∑ λ ∈ { − , + } N t λ N E n t r o p y ( D t λ ) ) (2) \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} Gain(D,A)​=t∈Ta​max​Gain(D,A,t)=t∈Ta​max​(Entropy(D)−λ∈{−,+}∑​NNtλ​​Entropy(Dtλ​))​(2)
   式(2)中，$Gain(D,A,t)$是样本集$D$基于划分点$t$二分后的信息增益，$D_t^{\lambda }$表示二分后的子集，$N_t^{\lambda }$表示二分后的子集的样本数量。

表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个样本的在该属性的取值由小到大排序后为：

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

• 当划分点为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}
  E n t r o p y ( D 0.0495 − ) = − ( 0 1 log ⁡ 0 1 + 1 1 log ⁡ 1 1 ) = 0 E n t r o p y ( D 0.0495 + ) = − ( 8 16 log ⁡ 8 16 + 8 16 log ⁡ 8 16 ) = 1.0 G a i n ( D , 含糖率 , 0.0495 ) = E n t r o p y ( D ) − ∑ λ ∈ { − , + } N 0.0495 λ N E n t r o p y ( D 0.126 λ ) = 0.9975 − ( 1 17 ∗ 0 + 16 17 ∗ 1.0 ) = 0.0563 \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} Entropy(D0.0495−​)Entropy(D0.0495+​)Gain(D,含糖率,0.0495)​=−(10​log10​+11​log11​)=0=−(168​log168​+168​log168​)=1.0=Entropy(D)−λ∈{−,+}∑​NN0.0495λ​​Entropy(D0.126λ​)=0.9975−(171​∗0+1716​∗1.0)=0.0563​
• 当划分点为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}
  G a i n ( D , 含糖率 , 0.074 ) = 0.9975 − { 2 17 ∗ [ − ( 0 2 log ⁡ 0 2 + 2 2 log ⁡ 2 2 ) ] + 15 17 ∗ [ − ( 8 15 log ⁡ 8 15 + 7 15 log ⁡ 7 15 ) ] } = 0.1179 \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} Gain(D,含糖率,0.074)​=0.9975−{172​∗[−(20​log20​+22​log22​)]+1715​∗[−(158​log158​+157​log157​)]}=0.1179​
• 当划分点为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}
  G a i n ( D , 含糖率 , 0.095 ) = 0.9975 − { 3 17 ∗ [ − ( 0 3 log ⁡ 0 3 + 3 3 log ⁡ 3 3 ) ] + 14 17 ∗ [ − ( 8 14 log ⁡ 8 14 + 6 14 log ⁡ 6 14 ) ] } = 0.1861 \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} Gain(D,含糖率,0.095)​=0.9975−{173​∗[−(30​log30​+33​log33​)]+1714​∗[−(148​log148​+146​log146​)]}=0.1861​
• 当划分点为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}
  G a i n ( D , 含糖率 , 0.101 ) = 0.9975 − { 4 17 ∗ [ − ( 0 4 log ⁡ 0 4 + 4 4 log ⁡ 4 4 ) ] + 13 17 ∗ [ − ( 8 13 log ⁡ 8 13 + 5 13 log ⁡ 5 13 ) ] } = 0.2624 \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} Gain(D,含糖率,0.101)​=0.9975−{174​∗[−(40​log40​+44​log44​)]+1713​∗[−(138​log138​+135​log135​)]}=0.2624​
• 当划分点为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}
  G a i n ( D , 含糖率 , 0.126 ) = 0.9975 − { 5 17 ∗ [ − ( 0 5 log ⁡ 0 5 + 5 5 log ⁡ 5 5 ) ] + 12 17 ∗ [ − ( 8 12 log ⁡ 8 12 + 4 12 log ⁡ 4 12 ) ] } = 0.3492 \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} Gain(D,含糖率,0.126)​=0.9975−{175​∗[−(50​log50​+55​log55​)]+1712​∗[−(128​log128​+124​log124​)]}=0.3492​
• 当划分点为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}
  G a i n ( D , 含糖率 , 0.155 ) = 0.9975 − { 6 17 ∗ [ − ( 1 6 log ⁡ 1 6 + 5 6 log ⁡ 5 6 ) ] + 11 17 ∗ [ − ( 7 11 log ⁡ 7 11 + 4 11 log ⁡ 4 11 ) ] } = 0.1561 \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} Gain(D,含糖率,0.155)​=0.9975−{176​∗[−(61​log61​+65​log65​)]+1711​∗[−(117​log117​+114​log114​)]}=0.1561​
• 当划分点为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}
  G a i n ( D , 含糖率 , 0.1795 ) = 0.9975 − { 7 17 ∗ [ − ( 1 7 log ⁡ 1 7 + 6 7 log ⁡ 6 7 ) ] + 10 17 ∗ [ − ( 7 10 log ⁡ 7 10 + 3 10 log ⁡ 3 10 ) ] } = 0.2354 \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} Gain(D,含糖率,0.1795)​=0.9975−{177​∗[−(71​log71​+76​log76​)]+1710​∗[−(107​log107​+103​log103​)]}=0.2354​
• 当划分点为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}
  G a i n ( D , 含糖率 , 0.2045 ) = 0.9975 − { 8 17 ∗ [ − ( 1 8 log ⁡ 1 8 + 7 8 log ⁡ 7 8 ) ] + 9 17 ∗ [ − ( 7 9 log ⁡ 7 9 + 2 9 log ⁡ 2 9 ) ] } = 0.3371 \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} Gain(D,含糖率,0.2045)​=0.9975−{178​∗[−(81​log81​+87​log87​)]+179​∗[−(97​log97​+92​log92​)]}=0.3371​
• 当划分点为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}
  G a i n ( D , 含糖率 , 0.213 ) = 0.9975 − { 9 17 ∗ [ − ( 2 9 log ⁡ 2 9 + 7 9 log ⁡ 7 9 ) ] + 8 17 ∗ [ − ( 6 8 log ⁡ 6 8 + 2 8 log ⁡ 2 8 ) ] } = 0.2111 \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} Gain(D,含糖率,0.213)​=0.9975−{179​∗[−(92​log92​+97​log97​)]+178​∗[−(86​log86​+82​log82​)]}=0.2111​
• 当划分点为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}
  G a i n ( D , 含糖率 , 0.226 ) = 0.9975 − { 10 17 ∗ [ − ( 3 10 log ⁡ 3 10 + 7 10 log ⁡ 7 10 ) ] + 7 17 ∗ [ − ( 5 7 log ⁡ 5 7 + 2 7 log ⁡ 2 7 ) ] } = 0.1237 \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} Gain(D,含糖率,0.226)​=0.9975−{1710​∗[−(103​log103​+107​log107​)]+177​∗[−(75​log75​+72​log72​)]}=0.1237​
• 当划分点为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}
  G a i n ( D , 含糖率 , 0.2505 ) = 0.9975 − { 11 17 ∗ [ − ( 4 11 log ⁡ 4 11 + 7 11 log ⁡ 7 11 ) ] + 6 17 ∗ [ − ( 4 6 log ⁡ 4 6 + 2 6 log ⁡ 2 6 ) ] } = 0.0615 \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} Gain(D,含糖率,0.2505)​=0.9975−{1711​∗[−(114​log114​+117​log117​)]+176​∗[−(64​log64​+62​log62​)]}=0.0615​
• 当划分点为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}
  G a i n ( D , 含糖率 , 0.2655 ) = 0.9975 − { 12 17 ∗ [ − ( 5 12 log ⁡ 5 12 + 7 12 log ⁡ 7 12 ) ] + 5 17 ∗ [ − ( 3 5 log ⁡ 3 5 + 2 5 log ⁡ 2 5 ) ] } = 0.0202 \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} Gain(D,含糖率,0.2655)​=0.9975−{1712​∗[−(125​log125​+127​log127​)]+175​∗[−(53​log53​+52​log52​)]}=0.0202​
• 当划分点为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}
  G a i n ( D , 含糖率 , 0.2925 ) = 0.9975 − { 13 17 ∗ [ − ( 5 13 log ⁡ 5 13 + 8 13 log ⁡ 8 13 ) ] + 4 17 ∗ [ − ( 3 4 log ⁡ 3 4 + 1 4 log ⁡ 1 4 ) ] } = 0.0715 \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} Gain(D,含糖率,0.2925)​=0.9975−{1713​∗[−(135​log135​+138​log138​)]+174​∗[−(43​log43​+41​log41​)]}=0.0715​
• 当划分点为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}
  G a i n ( D , 含糖率 , 0.344 ) = 0.9975 − { 14 17 ∗ [ − ( 6 14 log ⁡ 6 14 + 8 14 log ⁡ 8 14 ) ] + 3 17 ∗ [ − ( 2 3 log ⁡ 2 3 + 1 3 log ⁡ 1 3 ) ] } = 0.0241 \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} Gain(D,含糖率,0.344)​=0.9975−{1714​∗[−(146​log146​+148​log148​)]+173​∗[−(32​log32​+31​log31​)]}=0.0241​
• 当划分点为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}
  G a i n ( D , 含糖率 , 0.373 ) = 0.9975 − { 15 17 ∗ [ − ( 6 15 log ⁡ 6 15 + 9 15 log ⁡ 9 15 ) ] + 2 17 ∗ [ − ( 2 2 log ⁡ 2 2 + 0 2 log ⁡ 0 2 ) ] } = 0.1041 \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} Gain(D,含糖率,0.373)​=0.9975−{1715​∗[−(156​log156​+159​log159​)]+172​∗[−(22​log22​+20​log20​)]}=0.1041​
• 当划分点为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}
  G a i n ( D , 含糖率 , 0.418 ) = 0.9975 − { 16 17 ∗ [ − ( 7 16 log ⁡ 7 16 + 9 16 log ⁡ 9 16 ) ] + 1 17 ∗ [ − ( 1 1 log ⁡ 1 1 + 0 1 log ⁡ 0 1 ) ] } = 0.0669 \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} Gain(D,含糖率,0.418)​=0.9975−{1716​∗[−(167​log167​+169​log169​)]+171​∗[−(11​log11​+10​log10​)]}=0.0669​

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

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

2、缺失值属性的处理

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

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

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

• 属性"色泽"，无缺失值样本子集 D ~ = { 2 , 3 , 4 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 14 , 15 , 16 , 17 } \widetilde{D}=\{2,3,4,6,7,8,9,10,11,12,14,15,16,17\} D ={2,3,4,6,7,8,9,10,11,12,14,15,16,17}，有"乌黑"、“青绿”、"浅白"3个取值
  G a i n ( D , 色泽 ) = ρ × [ E n t r o p y ( D ~ ) − ∑ m = 1 m r ~ m E n t r o p y ( D ~ m ) ] = 14 17 × { − ( 6 14 log ⁡ 6 14 + 8 14 log ⁡ 8 14 ) − [ 6 14 × ( − ( 4 6 log ⁡ 4 6 + 2 6 log ⁡ 2 6 ) ) + 4 14 × ( − ( 2 4 log ⁡ 2 4 + 2 4 log ⁡ 2 4 ) ) + 4 14 × ( − ( 0 4 log ⁡ 0 4 + 4 4 log ⁡ 4 4 ) ) ] } = 0.2519 \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} Gain(D,色泽)​=ρ×[Entropy(D )−m=1∑m​r m​Entropy(D m)]=1714​×{−(146​log146​+148​log148​)−[146​×(−(64​log64​+62​log62​))+144​×(−(42​log42​+42​log42​))+144​×(−(40​log40​+44​log44​))]}=0.2519​
• 属性"根蒂"，无缺失值样本子集 D ~ = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 10 , 11 , 12 , 13 , 14 , 15 , 16 } \widetilde{D}=\{1,2,3,4,5,6,7,8,10,11,12,13,14,15,16\} D ={1,2,3,4,5,6,7,8,10,11,12,13,14,15,16}，有"蜷缩"、“稍蜷”、"硬挺"3个取值
  G a i n ( D , 根蒂 ) = 15 17 × { − ( 8 15 log ⁡ 8 15 + 7 15 log ⁡ 7 15 ) − [ 7 15 × ( − ( 5 7 log ⁡ 5 7 + 2 7 log ⁡ 2 7 ) ) + 6 15 × ( − ( 3 6 log ⁡ 3 6 + 3 6 log ⁡ 3 6 ) ) + 2 15 × ( − ( 0 2 log ⁡ 0 2 + 2 2 log ⁡ 2 2 ) ) ] } = 0.1711 \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} Gain(D,根蒂)​=1715​×{−(158​log158​+157​log157​)−[157​×(−(75​log75​+72​log72​))+156​×(−(63​log63​+63​log63​))+152​×(−(20​log20​+22​log22​))]}=0.1711​
• 属性"敲声"，无缺失值样本子集 D ~ = { 1 , 2 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 13 , 14 , 15 , 16 , 17 } \widetilde{D}=\{1,2,4,5,6,7,8,9,10,11,13,14,15,16,17\} D ={1,2,4,5,6,7,8,9,10,11,13,14,15,16,17}，有"浊响"、“沉闷”、"清脆"3个取值
  G a i n ( D , 敲声 ) = 15 17 × { − ( 7 15 log ⁡ 7 15 + 8 15 log ⁡ 8 15 ) − [ 8 15 × ( − ( 5 8 log ⁡ 5 8 + 3 8 log ⁡ 3 8 ) ) + 5 15 × ( − ( 2 5 log ⁡ 2 5 + 3 5 log ⁡ 3 5 ) ) + 2 15 × ( − ( 0 2 log ⁡ 0 2 + 2 2 log ⁡ 2 2 ) ) ] } = 0.1448 \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} Gain(D,敲声)​=1715​×{−(157​log157​+158​log158​)−[158​×(−(85​log85​+83​log83​))+155​×(−(52​log52​+53​log53​))+152​×(−(20​log20​+22​log22​))]}=0.1448​
• 属性"纹理"，无缺失值样本子集 D ~ = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 9 , 11 , 12 , 13 , 14 , 15 , 16 , 17 } \widetilde{D}=\{1,2,3,4,5,6,7,9,11,12,13,14,15,16,17\} D ={1,2,3,4,5,6,7,9,11,12,13,14,15,16,17}，有"清晰"、“稍糊”、"模糊"3个取值
  G a i n ( D , 纹理 ) = 15 17 × { − ( 7 15 log ⁡ 7 15 + 8 15 log ⁡ 8 15 ) − [ 7 15 × ( − ( 6 7 log ⁡ 6 7 + 1 7 log ⁡ 1 7 ) ) + 5 15 × ( − ( 1 5 log ⁡ 1 5 + 4 5 log ⁡ 4 5 ) ) + 3 15 × ( − ( 0 3 log ⁡ 0 3 + 3 3 log ⁡ 3 3 ) ) ] } = 0.4235 \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} Gain(D,纹理)​=1715​×{−(157​log157​+158​log158​)−[157​×(−(76​log76​+71​log71​))+155​×(−(51​log51​+54​log54​))+153​×(−(30​log30​+33​log33​))]}=0.4235​
• 属性"脐部"，无缺失值样本子集 D ~ = { 1 , 2 , 3 , 4 , 5 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 16 , 17 } \widetilde{D}=\{1,2,3,4,5,7,8,9,10,11,12,13,14,16,17\} D ={1,2,3,4,5,7,8,9,10,11,12,13,14,16,17}，有"凹陷"、“稍凹”、"平坦"3个取值
  G a i n ( D , 脐部 ) = 15 17 × { − ( 7 15 log ⁡ 7 15 + 8 15 log ⁡ 8 15 ) − [ 7 15 × ( − ( 5 7 log ⁡ 5 7 + 2 7 log ⁡ 2 7 ) ) + 4 15 × ( − ( 2 4 log ⁡ 2 4 + 2 4 log ⁡ 2 4 ) ) + 4 15 × ( − ( 0 4 log ⁡ 0 4 + 4 4 log ⁡ 4 4 ) ) ] } = 0.2888 \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} Gain(D,脐部)​=1715​×{−(157​log157​+158​log158​)−[157​×(−(75​log75​+72​log72​))+154​×(−(42​log42​+42​log42​))+154​×(−(40​log40​+44​log44​))]}=0.2888​
• 属性"触感"，无缺失值样本子集 D ~ = { 1 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 12 , 13 , 14 , 15 , 16 , 17 } \widetilde{D}=\{1,3,4,5,6,7,8,9,10,12,13,14,15,16,17\} D ={1,3,4,5,6,7,8,9,10,12,13,14,15,16,17}，有"硬滑"、"软粘"2个取值
  G a i n ( D , 脐部 ) = 15 17 × { − ( 7 15 log ⁡ 7 15 + 8 15 log ⁡ 8 15 ) − [ 10 15 × ( − ( 5 10 log ⁡ 5 10 + 5 10 log ⁡ 5 10 ) ) + 5 15 × ( − ( 2 5 log ⁡ 2 5 + 3 5 log ⁡ 3 5 ) ) ] } = 0.0057 \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} Gain(D,脐部)​=1715​×{−(157​log157​+158​log158​)−[1510​×(−(105​log105​+105​log105​))+155​×(−(52​log52​+53​log53​))]}=0.0057​
  （2） 给定划分属性，若样本在该属性上确实，如何对样本进行划分？
• 如果样本在划分属性上的取值已知，则将其分裂到与其取值对应的子节点，且样本权重在子节点中保持为1；
• 如若样本在划分属性上的取值未知，则将其同时分裂到所有子节点中，在各子节点中的权重为对应子节点的样本权重$\rho$。