聚类算法 -- 层次聚类


我们坐在时间的列车上,却不知到目的地是何方


转载

https://www.ibm.com/developerworks/cn/analytics/library/ba-1607-clustering-algorithm/index.html#N100CF


简介

层次聚类分为凝聚式层次聚类和分裂式层次聚类

凝聚式层次聚类,就是在初始阶段将每一个点都视为一个簇,之后每一次合并两个最接近的簇,当然对于接近程度的定义则需要指定簇的邻近准则

分裂式层次聚类,就是在初始阶段将所有的点视为一个簇,之后每次分裂出一个簇,直到最后剩下单个点的簇为止

本文中我们将详细介绍凝聚式层次聚类算法

对于凝聚式层次聚类,指定簇的邻近准则是非常重要的一个环节,在此我们介绍三种最常用的准则,分别是 MAX, MIN, 组平均。如下图所示:


算法流程

凝聚式层次聚类算法也是一个迭代的过程,算法流程如下:

  1. 每次选最近的两个簇合并,我们将这两个合并后的簇称之为合并簇
  2. 若采用 MAX 准则,选择其他簇与合并簇中离得最远的两个点之间的距离作为簇之间的邻近度。若采用 MIN 准则,取其他簇与合并簇中离得最近的两个点之间的距离作为簇之间的邻近度。若组平均准则,取其他簇与合并簇所有点之间距离的平均值作为簇之间的邻近度
  3. 重复步骤 1 和步骤 2,合并至只剩下一个簇

算法举例

下面以五个点进行举例

先求出五个点的欧氏距离矩阵:

P1 P2 P3 P4 P5
P1 0 0.81 1.32 1.94 1.82
P2 0.81 0 1.56 2.16 1.77
P3 1.32 1.56 0 0.63 0.71
P4 1.94 2.16 0.63 0 0.71
P5 1.82 1.77 0.71 0.71 0

根据算法流程,我们先找出距离最近的两个簇,P3, P4

合并 P3, P4 为 {P3, P4},根据 MIN 原则更新矩阵如下:

MIN.distance({P3, P4}, P1) = 1.32;

MIN.distance({P3, P4}, P2) = 1.56;

MIN.distance({P3, P4}, P5) = 0.70;

继续更新举例矩阵

P1 P2 {P3, P4} P5
P1 0 0.81 1.32 1.82
P2 0.81 0 1.56 1.77
1.32 1.56 0 0.71
P5 1.82 1.77 0.71 0

接着继续找出距离最近的两个簇,{P3, P4}, P5

合并 {P3, P4}, P5 为 {P3, P4, P5},根据 MIN 原则继续更新矩阵:

MIN.distance(P1, {P3, P4, P5}) = 1.32;

MIN.distance(P2, {P3, P4, P5}) = 1.56;

继续更新举例矩阵

P1 P2 {P3, P4, P5}
P1 0 0.81 1.32
P2 0.81 0 1.56
1.32 1.56 0

接着继续找出距离最近的两个簇,P1, P2。

合并 P1, P2 为 {P1, P2},根据 MIN 原则继续更新矩阵:

MIN.distance({P1,P2}, {P3, P4, P5}) = 1.32

继续更新举例矩阵

{P1, P2} {P3, P4, P5}
0 1.32
1.32 0

最终合并剩下的这两个簇即可获得最终结果,如下图:

MAX,组平均算法流程同理,只是在更新矩阵时将上述计算簇间距离变为簇间两点最大欧式距离,和簇间所有点平均欧式距离即可


优缺点

优点:1,距离和规则的相似度容易定义,限制少;2,不需要预先制定聚类数;3,可以发现类的层次关系;4,可以聚类成其它形状

缺点:1,计算复杂度太高;2,奇异值也能产生很大影响;3,算法很可能聚类成链状