第9章 分类规则挖掘
第一题
1、设网球俱乐部有打球与气候条件的历史统计数据如下表1所示。它有“天气”、“气温”、“适度”和“风力”4个描述气候的条件属性，类别属性为“是”与“否”的二元取值，分别表示在当时的气候条件下是否适宜打球的两种类别。
表1 打球与气候情况的历史数据样本集S
X_1晴高大无否
X_8晴中大无否
X_2晴高大无否
X_9晴低小无是
X_3云高大无是
X_{10}雨中小无是
X_4雨中大无是
X_{11}晴中小有是
X_5雨低小无是
X_{12}云中大有是
X_6雨低小有否
X_{13}云高小无是
X_7云低小有是
X_{14}雨中大有否
对
S 中的任意两个数据对象
X,Y，定义其在4个条件属性上的相异度为
d(X,Y)=\sum_{j=1}^r\delta(x_j,y_j) 其中
x_j,y_j 是数据对象
X,Y 的第
j 个分量值；如果
x_j=y_j，
\delta(x_j,y_j)=0，否则
\delta(x_j,y_j)=1。
根据天气预报得知，后天的天气情况
X_H=(雨、高、小、无)，若令，请用
k-最近邻分类算法预测后天是否适合打球。
解：
首先，计算相异度。根据提供的相异度定义，可以使用欧氏距离来计算相异度。欧氏距离的计算公式如下所示：
d(\mathbf{p}, \mathbf{q}) = \sqrt{(p_1 - q_1)^2 + (p_2 - q_2)^2 + (p_3 - q_3)^2 + (p_4 - q_4)^2}其中 (
p_i) 和 (
q_i) 分别是两个数据对象在第 (
i) 个属性上的取值。现在开始计算相异度。对于样本中的每个数据对象，将其表示为一个向量，其中每个分量对应于一个条件属性。然后，使用欧氏距离计算每对数据对象之间的相异度。接下来，将根据计算得到的相异度找出与后天天气情况最相似的 k 个样本，以进行预测。
计算后天天气情况（雨、高、小、无）与每个样本之间的相异度。现在，让计算后天天气情况（雨、高、小、无）与每个样本之间的相异度。使用欧氏距离公式来计算相异度：
d(\mathbf{p}, \mathbf{q}) = \sqrt{(p_1 - q_1)^2 + (p_2 - q_2)^2 + (p_3 - q_3)^2 + (p_4 - q_4)^2}其中，(
\mathbf{p}) 表示后天天气情况，(
\mathbf{q}) 表示样本数据中的每个数据对象。
后天天气情况为：天气=雨，温度=高，湿度=小，风力=无。现在，计算后天天气情况与每个样本之间的相异度。先将后天的天气情况表示为向量：
\mathbf{p_{\text{H}}} = (雨, 高, 小, 无)然后，逐个计算后天天气情况与每个样本之间的相异度。将每个样本的条件属性值代入欧氏距离公式中，并计算相异度。下面是计算结果：
\begin{align*} d(\mathbf{p_{\text{H}}}, \mathbf{q_1}) &= \sqrt{(雨 - 晴)^2 + (高 - 高)^2 + (小 - 大)^2 + (无 - 无)^2} \ = \sqrt{1^2 + 0^2 + 1^2 + 0^2} \ = \sqrt{2} \ \approx 1.414 \ \\[1ex] d(\mathbf{p_{\text{H}}}, \mathbf{q_2}) &= \sqrt{(雨 - 晴)^2 + (高 - 高)^2 + (小 - 大)^2 + (无 - 无)^2} \ = \sqrt{1^2 + 0^2 + 1^2 + 0^2} \ = \sqrt{2} \ \approx 1.414 \ \\[1ex] d(\mathbf{p_{\text{H}}}, \mathbf{q_3}) &= \sqrt{(雨 - 云)^2 + (高 - 高)^2 + (小 - 大)^2 + (无 - 无)^2} \ = \sqrt{1^2 + 0^2 + 1^2 + 0^2} \ = \sqrt{2} \ \approx 1.414 \ \\[1ex] d(\mathbf{p_{\text{H}}}, \mathbf{q_4}) &= \sqrt{(雨 - 雨)^2 + (高 - 中)^2 + (小 - 大)^2 + (无 - 无)^2} \ = \sqrt{0^2 + 1^2 + 1^2 + 0^2} \ = \sqrt{2} \ \approx 1.414 \\[1ex] d(\mathbf{p_{\text{H}}}, \mathbf{q_5}) &= \sqrt{(雨 - 雨)^2 + (高 - 低)^2 + (小 - 小)^2 + (无 - 无)^2} \ = \sqrt{0^2 + 1^2 + 0^2 + 0^2} \ = 1 \\[1ex] d(\mathbf{p_{\text{H}}}, \mathbf{q_6}) &= \sqrt{(雨 - 雨)^2 + (高 - 低)^2 + (小 - 小)^2 + (无 - 有)^2} \ = \sqrt{0^2 + 1^2 + 0^2 + 1^2} \ = \sqrt{2} \ \approx 1.414 \\[1ex] d(\mathbf{p_{\text{H}}}, \mathbf{q_7}) &= \sqrt{(雨 - 云)^2 + (高 - 低)^2 + (小 - 小)^2 + (无 - 有)^2} \ = \sqrt{1^2 + 1^2 + 0^2 + 1^2} \ = \sqrt{3} \ \approx 1.732 \\[1ex] d(\mathbf{p_{\text{H}}}, \mathbf{q_8}) &= \sqrt{(雨 - 晴)^2 + (高 - 中)^2 + (小 - 大)^2 + (无 - 无)^2} \ = \sqrt{1^2 + 1^2 + 1^2 + 0^2} \ = \sqrt{3} \ \approx 1.732 \\[1ex] d(\mathbf{p_{\text{H}}}, \mathbf{q_9}) &= \sqrt{(雨 - 晴)^2 + (高 - 低)^2 + (小 - 小)^2 + (无 - 无)^2} \ = \sqrt{1^2 + 1^2 + 0^2 + 0^2} \ = \sqrt{2} \ \approx 1.414 \\[1ex] d(\mathbf{p_{\text{H}}}, \mathbf{q_{10}}) &= \sqrt{(雨 - 雨)^2 + (高 - 中)^2 + (小 - 小)^2 + (无 - 无)^2} \ = \sqrt{0^2 + 1^2 + 0^2 + 0^2} \ = 1 \\[1ex] d(\mathbf{p_{\text{H}}}, \mathbf{q_{11}}) &= \sqrt{(雨 - 晴)^2 + (高 - 中)^2 + (小 - 小)^2 + (无 - 有)^2} \ = \sqrt{1^2 + 1^2 + 0^2 + 1^2} \ = \sqrt{2} \ \approx 1.414 \\[1ex] d(\mathbf{p_{\text{H}}}, \mathbf{q_{12}}) &= \sqrt{(雨 - 云)^2 + (高 - 中)^2 + (小 - 大)^2 + (无 - 有)^2} \ = \sqrt{1^2 + 1^2 + 1^2 + 1^2} \ = 2 \\[1ex] d(\mathbf{p_{\text{H}}}, \mathbf{q_{13}}) &= \sqrt{(雨 - 云)^2 + (高 - 高)^2 + (小 - 小)^2 + (无 - 无)^2} \ = \sqrt{1^2 + 0^2 + 0^2 + 0^2} \ = 1 \\[1ex] d(\mathbf{p_{\text{H}}}, \mathbf{q_{14}}) &= \sqrt{(雨 - 雨)^2 + (高 - 中)^2 + (小 - 大)^2 + (无 - 有)^2} \ = \sqrt{0^2 + 1^2 + 1^2 + 1^2} \ = \sqrt{3} \ \approx 1.732 \end{align*}接下来，找出与后天天气情况最相似的 k 个样本。
假设选择 k=3，即找出与后天天气情况最相似的三个样本。根据之前计算的相异度，可以列出相异度最小的三个样本。
样本
X_5: 相异度为 1；样本
X_{10}: 相异度为 1；样本
X_{13}: 相异度为 1。因此，与后天天气情况最相似的三个样本是
X_5、
X_{10} 和
X_{13}。
最后，将根据这三个样本的类别来预测后天是否适合打球。在这三个样本中，类别为“是”，所以可以预测后天适合打球。
第二题
2、设有动物分类样本集如下表2，其中是否温血、有无羽毛、有无毛皮、会否游泳为条件属性，卵生动物类别属性，取值1表示该动物为卵生动物，0表示非卵生动物。试用ID3算法对样本集进行学习并生成其决策树，再由决策树获得动物的分类规则。
表2 数据集S有8个带类别标号的数据对象
X_111001
X_200011
X_311001
X_411001
X_510010
X_610100
解：
第一步：选择
S 增益最大的属性构造决策树的根结点。
（1）计算分类属性
C 的分类信息熵
已知
S=\{X_1,X_2,…,X_6\}共有6个样本点，故
|S|=6，而分类属性
C=\{1, 0\}=\{C_1,C_2\}，即
C_1 为 “1” 是卵生动物，
C_2 为 “0” 是非卵生动物，
C_1=\{X_1, X_2, X_3, X_4\},
C_2=\{X_5, X_6\}。
根据信息熵公式有
E(S,C)=-\sum_{i=1}^{2}\frac{|C_i|}{|S|}\log_2\frac{|C_i|}{|S|}=-\left(\frac{4}{6}\log_2\frac{4}{6}+\frac{2}{6}\log_2\frac{2}{6}\right) \approx 0.918（2）计算每个条件属性
A 相对
C 的信息熵
样本集
S 有是否温血、有无羽毛、有无毛皮、会否游泳等4个条件属性，因此，应分别计算它们相对
C 的分类信息熵。
① 当
A_1=“是否温血” 时，属性
A_1 将
S 划分为
S_1=\{X_1, X_3, X_4, X_5, X_6\}，
S_2=\{X_2\}。
因为
C_1\cap S_1 =\{X_1, X_3,X_4\}，
C_2\cap S_1=\{X_5, X_6\}，根据信息熵公式有
E(S_1,C)=-\sum_{i=1}^{2}\frac{|C_i\cap S_1|}{|S_1|}\log_2\left(\frac{|C_i\cap S_1|}{|S_1|}\right)=-\left(\frac{3}{5}\log_2\frac{3}{5}+\frac{2}{5}\log_2\frac{2}{5}\right) \approx 0.971 同理有
C_1\cap S_2 =\{X_2\}，
C_2\cap S_2=\varnothing，根据信息熵公式有
E(S_2,C)=-\sum_{i=1}^{2}\frac{|C_i\cap S_2|}{|S_2|}\log_2\left(\frac{|C_i\cap S_2|}{|S_2|}\right)=-\left(\frac{1}{1}\log_2\frac{1}{1}+\frac{0}{1}\log_2\frac{0}{1}\right)=0 条件属性
A_1 划分样本集
S 相对于
C 的信息熵为
E(S,A_1|C)=\sum_{j=1}^{2}\frac{|S_j|}{|S|}E(S_j,C)=\frac{|S_1|}{|S|}E(S_1,C)+\frac{|S_2|}{|S|}E(S_2,C)=\frac{5}{6}\times0.971+\frac{1}{6}\times0\approx0.809② 当
A_2=“有无羽毛” 时，属性
A_2 将
S 划分为
S_1=\{X_1, X_3, X_4\}，
S_2=\{X_2, X_5, X_6\}。
因为
C_1\cap S_1 =\{X_1, X_3,X_4\}，
C_2\cap S_1=\varnothing，根据信息熵公式有
E(S_1,C)=-\sum_{i=1}^{2}\frac{|C_i\cap S_1|}{|S_1|}\log_2\left(\frac{|C_i\cap S_1|}{|S_1|}\right)=-\left(\frac{3}{3}\log_2\frac{3}{3}+\frac{0}{3}\log_2\frac{0}{3}\right)=0 同理有
C_1\cap S_2 =\{X_2\}，
C_2\cap S_2=\{X_5,X_6\}，根据信息熵公式有
E(S_2,C)=-\sum_{i=1}^{2}\frac{|C_i\cap S_2|}{|S_2|}\log_2\left(\frac{|C_i\cap S_2|}{|S_2|}\right)=-\left(\frac{1}{3}\log_2\frac{1}{3}+\frac{2}{3}\log_2\frac{2}{3}\right) \approx 0.918 条件属性
A_2 划分样本集
S 相对于
C 的信息熵为
E(S,A_2|C)=\sum_{j=1}^{2}\frac{|S_j|}{|S|}E(S_j,C)=\frac{|S_1|}{|S|}E(S_1,C)+\frac{|S_2|}{|S|}E(S_2,C)=\frac{3}{6}\times0+\frac{3}{6}\times0.918=0.459③ 当
A_3=“有无毛皮” 时，属性
A_3 将
S 划分为
S_1=\{X_6\}，
S_2=\{X_1, X_2,X_3, X_4,X_5\}。
同理可得，
E(S_1,C)=0，
E(S_2,C)\approx 0.722，
E(S,A_3|C)\approx0.241④ 当
A_4=“会否游泳” 时，属性
A_4 将
S 划分为
S_1=\{X_2,X_5\}，
S_2=\{X_1,X_3, X_4,X_6\}。
同理可得，
E(S_1,C)=1，
E(S_2,C)\approx0.811，
E(S,A_4|C)=0.874（3）计算每个属性
A 的信息增益
根据公式
gain(S,A|C)=E(S,C)-E(S,A|C) 可得
① 是否温血：
gain(S,A_1|C)=0.918-0.809=0.109② 有无羽毛：
gain(S,A_2|C)=0.918-0.459=0.459③ 有无毛皮：
gain(S,A_3|C)=0.918-0.241=0.677④ 会否游泳：
gain(S,A_4|C)=0.918-0.874=0.044因此，最大增益的属性为“有无毛皮”，即以“有无毛皮”作为根节点，并以“有无毛皮”划分
S 所得子集
S_1，
S_2。
第二步：选择
S_2 中增益最大的属性作为“有无毛皮”的子女结点，即选择属性“有无羽毛”。
第三步：选择
S_2 中增益最大的属性作为“有无羽毛”的子女结点，即选择属性“是否温血”。
最终，得到样本集的决策树，如下图所示。
第三题
3、设网球俱乐部有打网球与气候条件的历史统计数据(如下表3)。它共有“天气”、“温度”、“湿度”和“风力”4个描述气候的条件属性，其中“湿度”为连续属性，类别属性为“是”与“否”的二元取值，分别表示在当时的气候条件下是否适宜打球的两种类别。假设湿度离散化为高中低三个等级，湿度值<75被认为湿度为低，湿度>85被认为湿度为高，其他情况湿度为中。请用C4.5算法构造关于气候条件与是否适宜打球的决策树。
表3 打球与气候情况的历史数据样本集S
X_1晴高95无否
X_8晴中85无否
X_2晴高90无否
X_9晴低70无是
X_3云高85无是
X_{10}雨中75无是
X_4雨中80无是
X_{11}晴中70有是
X_5雨低75无是
X_{12}云中80有是
X_6雨低70有否
X_{13}云高75无是
X_7云低65有是
X_{14}雨中78有否
解：
首先，需要计算每个属性的信息增益，以选择最有用的属性作为根节点。以下是计算信息增益的步骤：
第一步，计算数据集的熵
H(D)：
H(D)=-(P_Y\log_2P_Y+P_N\log_2P_N) 其中，
P_Y为类别为“是”的样本占比，
P_N为类别为“否”的样本占比。
根据样本数据，
P_Y=\frac{9}{14},P_N=\frac{5}{14}，因此：
H(D)=-\left(\frac{9}{14}\log_2\frac{9}{14}+\frac{5}{14}\log_2\frac{5}{14}\right)\approx0.940第二步，对于每个属性
A，计算其条件熵
H(D|A)：
H(D|A)=\sum_{i=1}^n\frac{|D_i|}{|D|}H(D_i)其中，
n为属性
A的取值数，
|D_i|为样本集中属性
A取值为第
i个取值的样本数量，
H(D_i)为属性
A取值为第
i个取值时的样本的熵。对于离散属性，
H(D_i)可以根据与属性
A的取值相对应的样本计算得出，对于连续属性，需要先对其进行离散化处理。对于本题，我们需要对湿度进行离散化处理。
根据题目要求，湿度离散化为高中低三个等级，湿度值<75被认为湿度为低，湿度>85被认为湿度为高，其他情况湿度为中。因此，可以将样本集中湿度小于75的样本归为“低"类，湿度大于85的样本归为“高"类，其余样本归为“中”类。
对于其他属性，可以直接计算条件熵。以下是每个属性的条件熵计算公式：
① 天气：
H(D|天气)=\frac{5}{14}H(D_1)+\frac{4}{14}H(D_2)+\frac{5}{14}H(D_3) 其中，
D_1为天气为“晴”的样本集，
D_2为天气为“云”的样本集，
D_3为天气为“雨”的样本集。
\begin{align*} H(D_1)&=-\left(\frac{2}{5}\log_2\frac{2}{5}+\frac{3}{5}\log_2\frac{3}{5}\right)\approx0.971\\[2ex] H(D_2)&=-\left(\frac{4}{4}\log_2\frac{4}{4}+\frac{0}{4}\log_2\frac{0}{4}\right)=0\\[2ex] H(D_3)&=-\left(\frac{3}{5}\log_2\frac{3}{5}+\frac{2}{5}\log_2\frac{2}{5}\right)\approx0.971 \end{align*} 因此
H(D|天气)\approx0.694② 温度：
H(D|温度)=\frac{4}{14}H(D_1)+\frac{4}{14}H(D_2)+\frac{6}{14}H(D_3) 其中，
D_1为温度为“高”的样本集，
D_2为温度为“中”的样本集，
D_3为温度为“低”的样本集。
\begin{align*} H(D_1)&=-\left(\frac{2}{4}\log_2\frac{2}{4}+\frac{2}{4}\log_2\frac{2}{4}\right)=1\\[2ex] H(D_2)&=-\left(\frac{4}{6}\log_2\frac{4}{6}+\frac{2}{6}\log_2\frac{2}{6}\right)\approx0.918\\[2ex] H(D_3)&=-\left(\frac{3}{4}\log_2\frac{3}{4}+\frac{1}{4}\log_2\frac{1}{4}\right)\approx0.811 \end{align*} 因此
H(D|温度)\approx0.911③ 湿度：
H(D|湿度)=\frac{4}{14}H(D_1)+\frac{8}{14}H(D_2)+\frac{2}{14}H(D_3) 其中，
D_1为湿度为“低”的样本集，
D_2为湿度为“中”的样本集，
D_3为湿度为“高”的样本集。
同理可得，
H(D_1)\approx0.811；
H(D_2)\approx0.811；
H(D_3)=0，
H(D|湿度)\approx0.695④ 风力：
H(D|风力)=\frac{9}{14}H(D_1)+\frac{5}{14}H(D_2) 其中，
D_1为风力为“无”的样本集，
D_2为风力为“有”的样本集。
同理可得，
H(D_1)\approx0.918；
H(D_2)\approx0.971,
H(D|风力)\approx0.937第三步，计算每个属性的信息增益
gain(D,A)：
gain(D,A)=H(D)-H(D|A) 每个属性的信息增益结果如下：
① 天气：
gain(D,天气)\approx0.246② 温度：
gain(D,温度)\approx0.029③ 湿度：
gain(D,湿度)\approx0.245④ 风力：
gain(D,风力)\approx0.003第四步，计算每个属性的信息增益率。
① 天气：
gainRatio(D,天气)=gain(D,天气)/H(D|天气)\approx0.156② 温度：
gainRatio(D,温度)=gain(D,温度)/H(D|温度)\approx0.019③ 湿度：
gainRatio(D,湿度)=gain(D,湿度)/H(D|湿度)\approx0.415④ 风力：
gainRatio(D,风力)=gain(D,风力)/H(D|风力)\approx0.003因此，选择信息增益率最大的属性“湿度”作为根节点。将样本集按照湿度的取值划分为三个子集，分别为湿度为“低”的子集
D_1，湿度为“中”的子集
D_2，湿度为“高”的子集
D_3。
第五步，对于每个子集，继续选择最有用的属性作为划分依据，构造子树。以下是构造子树的过程：
至此，我们已经得到了一棵完整的决策树，可以用于对新样本进行分类。其中，“高”、“中”、“低”表示湿度的不同取值，“有”、“无”表示风力的不同取值，叶子节点的标记“是”表示适宜打球，“否”表示不适宜打球。
第四题
4、设有4个属性14条记录的数据库(如下表4)，它记录了顾客身份、年龄、收入和信用等级等个人信息，以及前来商店咨询电脑事宜，其中“电脑”属性标记了一个顾客咨询结束后买了电脑，或者没买就直接离开商店的信息。
表4 记录了14位顾客购买电脑与否的数据库
X_1否≤30岁高一般否
X_8否≤30岁中一般否
X_2否≤30岁高优等否
X_9是≤30岁低一般是
X_3否31~40岁高一般是
X_{10}是≥41岁中一般是
X_4否≥41岁中一般是
X_{11}是≥41岁中优等是
X_5是≥41岁低一般是
X_{12}否31~40岁中优等是
X_6是≥41岁低优等否
X_{13}是31~40岁高一般是
X_7是31~40岁低优等是
X_{14}否≥41岁中优等否
现在来了一位新顾客
X=(学生=是, 年龄≤30岁, 收入等=中等, 信用=一般)，试用贝叶斯分类方法，预测顾客
X 是否会买电脑。
解：
现在来了一位新顾客
X=(x_1,x_2,x_3,x_4)=(学生=“是”,年龄=“≤30岁”,收入=“中”,信用=“一般”)，试用朴素贝叶斯分类方法，预测顾客
X是否会买电脑。
由于
S的类别属性
C取值为“是”和“否”，因此将
S分为两个类别集合
\begin{aligned}&C_1=C_{是}=\{X_3,X_4,X_5,X_7,X_9,X_{10},X_{11},X_{12},X_{13}\}\\[1ex] &C_2=C_{否}=\{X_1,X_2,X_6,X_8,X_{14}\}\end{aligned}（1）计算
p(C_1),p(C_2)由公式
\begin{aligned}p(C_j)=\frac{|C_j|}{|S|}\end{aligned} 得
p(C_1)=\frac{|C_1|}{|S|}=\frac{9}{14}\ ,\ \ p(C_2)=\frac{|C_2|}{|S|}=\frac{5}{14}（2）计算
p(X|C_1)由公式
\begin{aligned}p(X|C_1)=\prod_{k=1}^{4}p(x_k|C_1)\end{aligned} 得
p(x_1|C_1)=\frac{|S_{11}|}{|C_1|}=\frac{6}{9}\ ,\ \ p(x_2|C_1)=\frac{|S_{12}|}{|C_1|}=\frac{1}{9}\\[2ex] p(x_3|C_1)=\frac{|S_{13}|}{|C_1|}=\frac{4}{9}\ ,\ \ p(x_4|C_1)=\frac{|S_{14}|}{|C_1|}=\frac{5}{9} 因此，
\begin{aligned}p(X|C_1)=\frac{6}{9}×\frac{1}{9}×\frac{4}{9}×\frac{5}{9}\approx0.0183\end{aligned}（3）计算
p(X|C_2)由公式
\begin{aligned}p(X|C_2)=\prod_{k=1}^{4}p(x_k|C_2)\end{aligned} 得
p(x_1|C_2)=\frac{|S_{21}|}{|C_2|}=\frac{1}{5}\ ,\ \ p(x_2|C_2)=\frac{|S_{22}|}{|C_2|}=\frac{3}{5}\\[2ex] p(x_3|C_2)=\frac{|S_{23}|}{|C_2|}=\frac{2}{5}\ ,\ \ p(x_4|C_2)=\frac{|S_{24}|}{|C_2|}=\frac{2}{5} 因此，
\begin{aligned}p(X|C_2)=\frac{1}{5}×\frac{3}{5}×\frac{2}{5}×\frac{2}{5}=0.0192\end{aligned}（4）求最大
p(X|C_i)p(C_i)p(X|C_1)p(C_1)=0.0183×\frac{9}{14}\approx0.0118\\[2ex] p(X|C_2)p(C_2)=0.0192×\frac{5}{14}\approx0.0069 根据公式
p(X|C_i)p(C_i)=max\{p(X|C_1)p(C_1), p(X|C_2)P(C_2), \cdots, p(X|C_k)p(C_k)\} 得
max\{p(X|C_1)p(C_1), p(X|C_2)P(C_2)\}=p(X|C_1)p(C_1) 即把类别标号
C_1=“是” 赋予
X。
因此，根据朴素贝叶斯分类方法，预测顾客
X会买电脑。
