因为d2（A3，B1）最小，所以，A3->B1
d2（B1，A1）=(9-3)2+(5-2)2=45 d2（B1，B1）=(9-9)2+(5-5)2=0 d2（B1，C1）=(9-2)2+(5-6)2=50
因为d2（B1，B1）最小，所以，B1->B1
d2（B2，A1）=(2-3)2+(4-2)2=5 d2（B2，B1）=(2-9)2+(4-5)2=50 d2（B2，C1）=(2-2)2+(4-6)2=4
因为d2（B2，C1）最小，所以，B2->C1
d2（B3，A1）=(3-3)2+(10-2)2=64 d2（B3，B1）=(3-9)2+(10-5)2=61 d2（B3，C1）=(3-2)2+(10-6)2=17
因为d2（B3，C1）最小，所以，B3->C1
d2（C1，A1）=(2-3)2+(6-2)2=17 d2（C1，B1）=(2-9)2+(6-5)2=50 d2（C1，C1）=(2-2)2+(6-6)2=0
因为d2（C1，C1）最小，所以，C1->C1
d2（C2，A1）=(9-3)2+(6-2)2=50 d2（C2，B1）=(9-9)2+(6-5)2=1 d2（C2，C1）=(9-2)2+(6-6)2=49
因为d2（C2，B1）最小，所以，C2->B1
d2（C3，A1）=(2-3)2+(2-2)2=1 d2（C3，B1）=(2-9)2+(2-5)2=58 d2（C3，C1）=(2-2)2+(2-6)2=16
因为d2（C3，A1）最小，所以，C3->A1 所以第一次循环结束时，
第一类：A1，C3，质心为O1（2.5, 2）
第二类：B1，A3，C2, 质心为O2（9, 5.67） 第三类：C1，A2，B2，B3, 质心为O3（2.5, 7.25） (2) 第二次循环结束时，
第一类：A1，B2，C3,质心为O1（2.33,3）, 第二类：A3，B1，C2，质心为O2（8.67,5.67）， 第三类：A2，B3,C1，质心为O3（2.67,8.33）。 第三次循环结束时，
第一类：A1，B2，C3,质心为O1（2.33,3）, 第二类：A3，B1，C2，质心为O2（8.67,5.67）， 第三类：A2，B3,C1，质心为O3（2.67,8.33）。
结果与第二次循环结束的结果一样，故最后求得的结果为： 第一类：A1，B2，C3,质心为O1（2.33,3）, 第二类：A3，B1，C2，质心为O2（8.67,5.67）， 第三类：A2，B3,C1，质心为O3（2.67,8.33）。
四、给定数据集S，试根据前7个样本构造ID3决策树模型，并预测第8个样本的类别？
数据集S
Sample S1 S2 S3 S4 S5 S6 S7 S8 A a0 a0 a0 a1 a1 a1 a2 a2 B b0 b1 b2 b0 b1 b2 b0 b1 C c1 c1 c1 c2 c1 c2 c2
解：现计算每个属性的信息增益。 对给定样本分类所需的期望信息为：
E(S)= – (3/7)log2 (3/7)–(4/7)log2 (4/7)=0.5239+0.4613=0.9852 Values(A)={a0, a1, a2}，
Sa0 ={S1, S2, S3}，∣Sa0∣=3，其中3个都属于类C1，故有： E(Sa0)= – (5/5)log2(5/5) –(0/5)log2(0/5)=0
Sa1= {S4, S5, S6}，∣Sa1∣=3，其中，1个属于c1,2个属于c2，故有
E(Sa1)= – (1/3)log2(1/3) – (2/3)log2(2/3)=0.5283+0.3900=0.9183
同理，E(Sa2)= – (1/1)log2(1/1)–(0/1)log2(0/1)=0
因此属性A的期望熵为：E(S,A)=(3/7)E(Sa0)+ (3/7)E(Sa1)+(1/7)E(Sa2)=0.3936 故A的信息增益为：
Gain(S, A)= E(S) – E(S, A) =0. 9852– 0. 3936=0.5916
同理：
Values(B)={b0, b1, b2}，
Sb0 ={S1, S4, S7}，∣Sb0∣=3，其中，1个属于c1,2个属于c2，故有
E(Sb0)= – (1/3)log2(1/3) – (2/3)log2(2/3)=0.5283+0.3900=0.9183
Sb1= {S2, S5}，∣Sb1∣=2，其中2个都属于类C1, 故有
E(Sb1)= – (2/2)log2(2/2) –(0/2)log2(0/2)=0
同理，E(Sb2)= – (1/2)log2(1/2) – (1/2)log2(1/2)=1 因此属性B的期望熵为：
E(S, B)=(3/7)E(Sb0)+ (2/7)E(Sb1)+(2/7)E(Sb2)=0.3936+0+0.2857=0.6793 故B的信息增益为：
Gain(S,B)= E(S) – E(S, B) =0. 9852–0. 6793 =0.3059
故A的信息增益最大，令属性A为根节点的测试属性，并对应每个值（a0,,a1,a2）在根节点下建立分支，形成部分决策树： A a0 a1 a2
S1,S2,S3 S4,S5,S6 S7 对于A=a0和A=a2节点，它们对应的属性唯一，不需进一步讨论，而对于A=a1节点，需要进一步讨论。由于只有B属性可供讨论，因此依据不同的取值，可得最终的决策树： A a0 a1 a2
c1 B c2
b0 b1 b2 c2 c1 c2
根据以上决策树，可知第8个样本S8的类别为c2.
五、设论域
U={x1, x2 ,?, x6}，属性集A=C?D，条件属性集C={a, b, c}，决策属性集
D={d}，决策表如下：
决策表
x1 x2 x3 x4 x5 x6 a 1 1 1 1 2 2 b 0 0 2 2 1 1 c 2 2 0 2 0 1 d 1 1 2 0 2 2
问：决策表是否为一致决策表？利用分辨矩阵对决策表进行约简。
解：由决策表可知，
U/C={{x1, x2}, {x3}, {x4}, {x5}, {x6}} U/D={{x1, x2}, {x3, x5, x6}, {x4}} POSC(D)={x1, x2, x3, x4, x5, x6}
因为k=| POSC(D)|/|U|=1，故该决策表为一致决策表。 该决策表的分辨矩阵为6阶方阵，其元素为 1 2 3 1 2 3 4 5 6 {b,c} {b} {a,b,c} {a,b,c} {b,c} {b} {a,b,c} {a,b,c} {c} 4 {a,b,c} {a,b,c} 5 6 所以决策表的分辨函数为：
ρ=(b∨c)(b∨c)(b)(b)(c)(a∨b∨c)(a∨b∨c)(a∨b∨c)(a∨b∨c)(a∨b∨c)(a∨b∨c)=bc 故C的D约简为{b,c},C的D核为{b,c},约简的决策表为： U x1 x2 x3 x4 x5 x6
b 0 0 2 2 1 1 c 2 2 0 2 0 1 d 1 1 2 0 2 2 1. 假设数据挖掘的任务是将如下的8个点（用（x,y）代表位置）聚类为3个类：X1(2,10)、
X2(2,5)、X3(8,4)、X4(5,8)、X5(7,5)、X6(6,4)、X7(1,2)、X8(4,9)，距离选择欧几里德距离。假设初始选择X1(2,10)、X4(5,8)、X7(1,2)为每个聚类的中心，请用 K_means算法来计算： （1）在第一次循环执行后的3个聚类中心；
答：第一次迭代：中心点1：X1(2，10)，2：X4(5，8)，X7(1，2)
1 2 3 X1 0 9+4 1+64 X2 25 9+9 1+9 X3 36+36 9+16 53 X4 9+4 0 16+36 X5 25+25 4+9 45 X6 16+36 1+16 29 X7 1+64 16+36 0 X8 4+1 1+1 58 答案：在第一次循环执行后的3个聚类中心： 1：X1(2，10)
2：X3，X4，X5，X6，X8 （6，6） 3：X2，X7 （1.5，3.5）
（2）经过两次循环后，最后的3个族分别是什么？ 第二次迭代： d2 X1 X2 X3 X4 X5 X6 X7 X8 1 0 25 36+36 9+4 25+25 16+36 1+64 4+1 2 32 17 8 5 2 4 41 1+1 3 52+6.52 52+1.52 6.52+0.52 3.52+4.52 5.52+1.52 4.52+0.52 0.52+1.52 2.52+5.52 答案：1：X1，X8 (3.5，9.5)
2：X3，X4，X5，X6 （6.5，5.25） 3：X2，X7 （1.5，3.5）
2. 数据库有4个事务。设min_sup=60%,min_conf=80%。 TID T100 T200 T300 T400 答：
(a)Apriori算法：
{K} 1 ? {A} 4 ? {A,B} 4 ? {A,B,D} 3 {A} 4 {B} 4 {A,D} 3 {B} 4 {D} 3 {B,D} 3 {D} 3 {C} 2
data 6/6/2007 6/6/2007 6/7/2007 6/10/2007 Transaction K,A,D,B D,A,C,E,B C,A,B,E B,A,D a.使用Apriori算法找出频繁项集，并写出具体过程。