参考书籍：《大数据：互联网大规模数据挖掘与分布式处理》（第二版）

原版英文书籍：Mining of Massive Datasets

注：答案为本人自己做的，并非标准答案，仅供参考。
如有错误，请私信我，我将及时修改。

《大数据：互联网大规模数据挖掘与分布式处理》（第二版）第七章习题答案

注：本书包含大量习题，较难的习题或习题中较难的部分都会用！标记，最难的习题用！！标记。

!习题7.1.1

!!习题7.1.2

!习题7.1.3

夹角余弦计算公式中分子的值满足均值为0的正态分布。

当d不断增大时，向量夹角余弦的期望值不变。

习题7.2.1

初始点集为：{1, 4, 9, 16, 25, 36, 49, 64, 81}。

趟数	点集	说明
1	{2.5, 9, 16, 25, 36, 49, 64, 81}	1和4距离最近，合并，质心为2.5
2	{5.75, 16, 25, 36, 49, 64, 81}	2.5和9距离最近，合并，质心为5.75
3	{5.75, 20.5, 36, 49, 64, 81}	16和25距离最近，合并，质心为20.5
4	{5.75, 20.5, 42.5, 64, 81}	36和49距离最近，合并，质心为42.5
5	{13.125, 42.5, 64, 81}	5.75和20.5距离最近，合并，质心为13.125
6	{13.125, 42.5, 72.5}	64和81距离最近，合并，质心为72.5
7	{27.8125, 72.5}	13.125和42.5距离最近，合并，质心为27.8125
8	{50.15625}	27.8125和72.5距离最近，合并，质心为50.15625

习题7.2.2

(a)

(b)

习题7.2.3

习题7.2.4

(a)

若合并簇1和簇2，质心为(31/7, 44/7)，半径为4.926，结果为0.7037。

若合并簇1和簇3，质心为(8, 29/8)，半径为6.2162，结果为0.7770。

若合并簇2和簇3，质心为(25/3, 19/3)，半径为5.6765，结果为0.6307。

这些结果都大于各个簇的半径和簇点数的商，说明簇不应该合并。

(b)

若合并簇1和簇2，直径为9.4340，结果为1.3477。

若合并簇1和簇3，直径为10.7703，结果为1.3463。

若合并簇2和簇3，直径为10.6301，结果为1.1811。

这些结果都大于各个簇的直径和簇点数的商，说明簇不应该合并。

习题7.2.5

!习题7.2.6

按距离和，我们选a或b或c作为中心点。

按最大距离最小，我们选a或b或c作为中心点。

只要选的中心点不同，就满足题意。

习题7.3.1

选择的第一个点是(3, 4)，剩下的2个点是(12, 6)，(4, 10)。

!!习题7.3.2

簇1：{(2, 2), (3, 4)}

簇2：{(4, 8), (6, 8), (4, 10)}

簇3：{(9, 3), (10, 5), (11, 4), (12, 3)}

三个簇的直径分别是√5、2√2、3。

最小簇间距离分别是√17、5、√37。

一般地，当最小簇间距离是簇的直径的几倍时，簇的合并可以停止了。

采用最大距离选择初始点，在簇合并结束后，初始点在相同的簇中的概率为0。

!习题7.3.3

点集：{(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)}

按7.3.2节的方法初始化5个簇，再进行簇的合并，最后簇{(0, 0)}重分配到另一个簇中。

习题7.3.4

(a)

(b)

习题7.3.5

习题7.4.1

习题7.5.1

簇中点的数目N=12。

簇的中心点(10, 5)。

簇中心点的ROWSUM=342。

k=2，离簇中心点最近的2个点为(9, 3)和(11, 4)，它们的ROWSUM分别为352、446。

k=2，离簇中心点最远的2个点为(2, 2)和(4, 10)，它们的ROWSUM分别为688、604。

习题7.5.2

簇半径为：

习题7.6.1

桶的初始化：

注：这只是一种初始化方法。

从右到左，按k-mean算法聚类，k=3。

桶序号	质心	簇中点数目
1	48	3
2	54	3
3	50.1667	6
4	45.6667	6
5	未知	12

合并后，

桶序号	质心	簇中点数目
1	51	6
2	47.9167	12
3	未知	12

习题7.6.2

最佳质心为48。