一. K-means 算法

问题

给定的数据如下：

a b c d e f g h
1,1 2,1 3,1 1,3 1,4 2,3 3,2 4,1

初始的中心点为：a 和 d

求解

K-means 算法实际是迭代求解，迭代的主要步骤是：

  • 将每个样本聚类到最近的中心
  • 重新计算样本点的平均值作为新的中心

因此，首先计算出其他样本点到初始两个样本点的欧几里得距离平方为：（并选出较小距离者作为一个聚簇）

b c e f g h
到 a 的距离平方 1 4 9 5 5 9
到 d 的距离平方 5 8 1 1 5 13

可以将 （a, b, c, g, h） 和 (d, e, f) 作为两类，从而使用平均距离计算出新的两个类中心为： 机器学习第四次作业 - 图1 和 机器学习第四次作业 - 图2
继续计算其他样本点到新两类中心的欧几里得距离平方为(一位小数四舍五入)：

a b c d e f g h
到 a 的距离平方 2.6 0.4 0.2 5.8 10.4 3.6 0.8 2
到 d 的距离平方 5.6 5.9 8.2 0.2 0.6 0.6 4.6 12.6

可以将 (a, b, c, g, h) 和 (d, e, f) 作为两类，从而使用平均距离计算出类中心为：机器学习第四次作业 - 图3 和 机器学习第四次作业 - 图4
迭代结束，最终计算出的类分别为：（a, b, c, g, h）和 (d, e, f) ，如下图所示
image.png

二. 层次聚类

问题

层次聚类首先将所有数据点看作一簇，采用不同的凝聚方法（两簇变为一簇的方法）

  • 单链方式，将不同簇最近点之间的邻近度看作簇的邻近度
  • 全链方式，将不同簇最远点之间的邻近度看作簇的邻近度

相似度矩阵如下，相似度越高表示邻近度越低：


 p1 p2 p3 p4 p5
p1 1.00 0.10 0.41 0.55 0.35
p2 0.10 1.00 0.64 0.47 0.98
p3 0.41 0.64 1.00 0.44 0.85
p4 0.55 0.47 0.44 1.00 0.76
p5 0.35 0.98 0.85 0.76 1.00

单链方式

计算步骤以表格形式呈现：（红色表示邻近度最大开始进行聚类）

p1 p2 p3 p4 p5
p1 1.00 0.10 0.41 0.55 0.35
p2 0.10 1.00 0.64 0.47 0.98
p3 0.41 0.64 1.00 0.44 0.85
p4 0.55 0.47 0.44 1.00 0.76
p5 0.35 0.98 0.85 0.76 1.00
p1 p2/p5 p3 p4
p1 1.00 0.35 0.41 0.55
p2/p5 0.35 1.00 0.85 0.76
p3 0.41 0.85 1.00 0.44
p4 0.55 0.76 0.44 1.00
p1 p2/p5/p3 p4
p1 1.00 0.41 0.55
p2/p5/p3 0.41 1.00 0.76
p4 0.55 0.76 1.00
p1 p2/p5/p3/p4
p1 1.00 0.55
p2/p5/p3/p4 0.55 1.00
p2/p5/p3/p4/p1
p2/p5/p3/p4/p1 1.00

树状图如下：
image.png

全链方式

计算步骤以表格形式呈现：（红色表示邻近度最大开始进行聚类）

p1 p2 p3 p4 p5
p1 1.00 0.10 0.41 0.55 0.35
p2 0.10 1.00 0.64 0.47 0.98
p3 0.41 0.64 1.00 0.44 0.85
p4 0.55 0.47 0.44 1.00 0.76
p5 0.35 0.98 0.85 0.76 1.00
p1 p2/p5 p3 p4
p1 1.00 0.10 0.41 0.55
p2/p5 0.10 1.00 0.64 0.47
p3 0.41 0.64 1.00 0.44
p4 0.55 0.47 0.44 1.00
p1 p2/p5/p3 p4
p1 1.00 0.10 0.55
p2/p5/p3 0.10 1.00 0.44
p4 0.55 0.44 1.00
p1/p4 p2/p5/p3
p1/p4 1.00 0.10
p2/p5/p3 0.10 1.00
p2/p5/p3/p1/p4
p2/p5/p3/p1/p4 1.00

树状图如下：
image.png