聚类分析方法（二）

Francek Chen

发布于 2025-01-23 00:03:16

630

文章被收录于专栏：智能大数据分析智能大数据分析

三、层次聚类方法

（一）层次聚类策略

层次聚类方法对给定的数据集进行层次的分解，直到某种条件满足为止。具体又有凝聚的 (agglomerative) 和分裂的 (divisive) 两种策略。

1、凝聚的层次聚类

这是一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有的对象都在一个簇中，或者某个终结条件被满足，绝大多数层次聚类方法属于这一类，其区别仅在于簇间相似度的选择上有所不同。

2、分裂的层次聚类

这个策略与凝聚的层次聚类相反的，为自顶向下的策略，它首先将所有对象放置在同一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇，或者达到了某个终止条件。层次凝聚的代表是AGNES (AGglomerative NESting) 算法，层次分裂的代表是DIANA (DIvisive ANAlysis) 算法。图10-15描述了对5个数据对象进行层次聚类计算过程。

最初， AGNES将每个对象作为一个簇，然后根据某种准则 (簇间距离最近或簇间相似度最大)，将这些簇一步一步地合并成较大的簇。例如，如果簇

C_1

与簇

C_2

之间的距离，比其他任意两个簇的距离都小，则将

C_1

和

C_2

合并为一个簇。合并后的簇与其他簇同等看待，继续寻找簇间距离最小的两个簇，并将其合并，直到所有的对象最终都在一个簇中。在DIANA算法的处理过程中，所有的对象开始都放在一个簇中，然后根据某种原则将该簇分裂，其分裂过程反复进行，直到每个新的簇只包含一个对象为止。

（二）AGNES算法

1、算法描述

AGNES算法是一个典型的凝聚层次聚类方法：最初将每个对象作为一个簇，再根据某种准则 (簇间距离或相似度)，将这些簇逐渐合并成较大的簇，直到所有数据对象都在同一个簇或簇数达到用户指定数目。簇的凝聚准则可以选择簇间最短距离、最长距离、中心距离和平均距离等。以下算法采用簇间中心距离为目标函数。

算法10-5 AGNES算法 (凝聚层次算法) 输入：数据集

S=\{X_1,X_2,\cdots,X_n\}

和正整数

k

(簇的数目) 输出：含

k

个簇的一个聚类

C=\{C_1,C_2,\cdots,C_k\}

（1）将

S

的每个对象当成一个初始簇，形成初始聚类

C

（2）REPEAT （3）找出中心距离最近的两个簇（4）合并这两个簇，并生成新的聚类

C

（5）UNTIL簇的数目等于

k

2、计算实例

例10-5 设

S

为有8个数据对象的数据集

S

(表10-5)，用户需要的簇数

k=2

。试用AGNES算法对其进行划分聚类。

解：首先将表10-15各个点的位置在二维平面给出。如下图10-17。

根据算法10-5，因为

S

有8个数据对象，因此，刚开始每个对象为一个簇，详见下表10-6。

计算步骤	最近距离	最近的两个簇	合并后的簇	簇的个数
0	—	—	{ X 1 } , { X 2 } , { X 3 } , { X 4 } , { X 5 } , { X 6 } , { X 7 } , { X 8 } \{X_1\},\{X_2\},\{X_3\},\{X_4\},\{X_5\},\{X_6\},\{X_7\},\{X_8\} {X1},{X2},{X3},{X4},{X5},{X6},{X7},{X8}	8
1	1	{ X 1 } , { X 2 } \{X_1\},\{X_2\} {X1},{X2}	{ X 1 , X 2 } , { X 3 } , { X 4 } , { X 5 } , { X 6 } , { X 7 } , { X 8 } \{X_1,X_2\},\{X_3\},\{X_4\},\{X_5\},\{X_6\},\{X_7\},\{X_8\} {X1,X2},{X3},{X4},{X5},{X6},{X7},{X8}	7
2	1	{ X 3 } , { X 4 } \{X_3\},\{X_4\} {X3},{X4}	{ X 1 , X 2 } , { X 3 , X 4 } , { X 5 } , { X 6 } , { X 7 } , { X 8 } \{X_1,X_2\},\{X_3,X_4\},\{X_5\},\{X_6\},\{X_7\},\{X_8\} {X1,X2},{X3,X4},{X5},{X6},{X7},{X8}	6
3		{ X 1 , X 2 } , { X 3 , X 4 } \{X_1,X_2\},\{X_3,X_4\} {X1,X2},{X3,X4}	{ X 1 , X 2 , X 3 , X 4 } , { X 5 } , { X 6 } , { X 7 } , { X 8 } \{X_1,X_2,X_3,X_4\},\{X_5\},\{X_6\},\{X_7\},\{X_8\} {X1,X2,X3,X4},{X5},{X6},{X7},{X8}	5
4	1	{ X 5 } , { X 6 } \{X_5\},\{X_6\} {X5},{X6}	{ X 1 , X 2 , X 3 , X 4 } , { X 5 , X 6 } , { X 7 } , { X 8 } \{X_1,X_2,X_3,X_4\},\{X_5,X_6\},\{X_7\},\{X_8\} {X1,X2,X3,X4},{X5,X6},{X7},{X8}	4
5	1	{ X 7 } , { X 8 } \{X_7\},\{X_8\} {X7},{X8}	{ X 1 , X 2 , X 3 , X 4 } , { X 5 , X 6 } , { X 7 , X 8 } \{X_1,X_2,X_3,X_4\},\{X_5,X_6\},\{X_7,X_8\} {X1,X2,X3,X4},{X5,X6},{X7,X8}	3
6	1	{ X 5 , X 6 } , { X 7 , X 8 } \{X_5,X_6\},\{X_7,X_8\} {X5,X6},{X7,X8}	{ X 1 , X 2 , X 3 , X 4 } , { X 5 , X 6 , X 7 , X 8 } \{X_1,X_2,X_3,X_4\},\{X_5,X_6,X_7,X_8\} {X1,X2,X3,X4},{X5,X6,X7,X8}	2

\{X_1\},\{X_2\},\{X_3\},\{X_4\},\{X_5\},\{X_6\},\{X_7\},\{X_8\}

811

\{X_1\},\{X_2\}

\{X_1,X_2\},\{X_3\},\{X_4\},\{X_5\},\{X_6\},\{X_7\},\{X_8\}

721

\{X_3\},\{X_4\}

\{X_1,X_2\},\{X_3,X_4\},\{X_5\},\{X_6\},\{X_7\},\{X_8\}

63

\{X_1,X_2\},\{X_3,X_4\}

\{X_1,X_2,X_3,X_4\},\{X_5\},\{X_6\},\{X_7\},\{X_8\}

541

\{X_5\},\{X_6\}

\{X_1,X_2,X_3,X_4\},\{X_5,X_6\},\{X_7\},\{X_8\}

451

\{X_7\},\{X_8\}

\{X_1,X_2,X_3,X_4\},\{X_5,X_6\},\{X_7,X_8\}

361

\{X_5,X_6\},\{X_7,X_8\}

\{X_1,X_2,X_3,X_4\},\{X_5,X_6,X_7,X_8\}

2

初始步，每个对象为一个簇

\{X_1\},\{X_2\},\{X_3\},\{X_4\},\{X_5\},\{X_6\},\{X_7\},\{X_8\}

。

第1步、为方便使用簇间中心距离平方。此例开始时有8个簇，共需计算28个簇间距离平方。但仅有

d(X_1,X_2)^2= d(X_1,X_3)^2= d(X_2,X_4)^2= d(X_3,X_4)^2= 1\\[2ex]d(X_5,X_6)^2= d(X_5,X_7)^2= d(X_6,X_8)^2= d(X_7,X_8)^2= 1

而其它对象之间的中心距离平方，如

d(X_1,X_4)^2、d(X_5,X_8)^2

等都大于1。由于有多个簇间中心距离最小且相等。因此，按照数据对象坐标编号小者顺序优先合并，即选择

\{X_1\},\{X_2\}

合并为

\{X_1,X_2\}

。即得7个簇

\{X_1,X_2\},\{X_3\},\{X_4\},\{X_5\},\{X_6\},\{X_7\},\{X_8\}

第2步、重新计算簇

\{X_1,X_2\}

的中心点为

C^{(1)}=(1, 1.5)

，并增加计算

C^{(1)}

与

\{X_3\},…,\{X_8\}

的距离平方。

d(C^{(1)},X_3)^2=1.25, d(C^{(1)},X_4)^2=1.25

，其它

d(C^{(1)},X_5)^2, …, d(C^{(1)},X_8)^2

等都大于1.25。因

d(X_3,X_4)^2=1

，故簇

\{X_3\}

和

\{X_4\}

合并为

\{X_3,X_4\}

，见表10-6计算步骤2所在的行。

第3步、重新计算簇

\{X_3,X_4\}

的中心点为

C^{(2)}=(2, 1.5)

，并增加计算

C^{(2)}

与

C^{(1)},\{X_5\},\{X_6\},\{X_7\},\{X_8\}

的距离平方。

d(C^{(1)},C^{(2)})^2=1, d(C^{(2)},X_5)^2=7.25

，且

d(C^{(2)},X_6)^2,d(C^{(2)},X_7)^2,d(C^{(2)},X_8)^2

更大。因此簇

\{X_1,X_2\}

和

\{X_3,X_4\}

合并为

\{X_1,X_2,X_3,X_4\}

，见表10-6计算步骤3所在的行。

第4步、重新计算簇

\{X_1,X_2,X_3,X_4\}

的中心点为

C^{(3)}=(1.5, 1.5)

，并增加计算

C^{(3)}

与

\{X_5\},\{X_6\},\{X_7\},\{X_8\}

的距离平方。

d(C^{(3)},X_5)^2=8.5

，且

d(C^{(3)},X_6)^2,d(C^{(3)},X_7)^2,d(C^{(3)},X_8)^2

更大。而

d(X_5,X_6)=1

，因此簇

\{X_5\}

和

\{X_6\}

合并为

\{X_5,X_6\}

，见表10-6计算步骤4所在的行。

第5步、重新计算簇

\{X_5,X_6\}

的中心点为

C^{(4)}=(3, 4.5)

，并增加计算

C^{(4)}

与

C^{(3)},\{X_7\},\{X_8\}

的距离平方。

d(C^{(4)},C^{(3)})^2=11.25

，

d(C^{(4)},X_7)^2=1.25,d(C^{(4)},X_8)^2=1.25,

而

d(X_7,X_8)^2=1

。因此簇

\{X_7\}

和

\{X_8\}

合并为

\{X_7,X_8\}

，见表10-6计算步骤5所在的行。

第6步、重新计算簇

\{X_7,X_8\}

的中心点为

C^{(5)}=(4, 4.5)

，并增加计算

C^{(5)}

与

C^{(3)},C^{(4)},C^{(1)}

的距离平方。

d(C^{(5)},C^{(3)})^2=11.25, d(C^{(5)},C^{(4)})^2=1

而

d(C^{(5)},C^{(1)})^2=15.25

。因此簇

\{X_5,X_6\}

和

\{X_7,X_8\}

合并为

\{X_5,X_6,X_7,X_8\}

，见表10-6计算步骤6所在的行。

由于合并后的簇的数目

k=2

已经达到用户输入的终止条件，程序结束。

3、算法的性能分析

AGNES算法思想比较简单，但经常会因为出现多个簇间距离相等的情况，这时究竟选择哪两个簇优先合并是非常关键的，但又是比较困难的。因为两个簇合并的决定一经做出，以后的处理只能在新生成的簇上进行，即使后来发现聚类效果不好，但前面已经做过的合并处理却不能撤销，而每个簇之间又不能交换对象。即如果在某一步对簇进行合并时没有选择恰当，最终可能导致低质量的聚类结果。 AGNES算法的时间复杂性为

O(n^2)

，因为对

n

个对象的数据集，算法必须计算所有对象两两之间的距离，其乘法计算量就达到

n(n-1)/2

。此外，因为刚开始的时候就有

n

个簇，如果最后以1个簇结束，则主循环中有

n

次迭代，在第

i

次迭代中，我们必须在

n-i+1

个簇中找到最靠近的两个簇进行合并。因此，这种聚类方法不具有很好的可伸缩性，即该算法在

n

很大的情况就不是很适用。

（三）DIANA算法

1、算法描述

DIANA算法属于分裂的层次聚类。它的计算思路与凝聚的层次聚类方法相反，采用一种自顶向下的分裂策略。它首先将所有对象置于一个簇中，然后逐渐将其细分为越来越小的簇，直到每个对象自成一簇，或者达到了某个终结条件，例如达到了用户希望的簇数目，或者是两个最近簇之间的距离超过了指定的某个阈值等。在DIANA算法的处理过程中，刚开始将所有的对象都放在一个簇中，然后根据一定的评价函数将其分裂为两个子簇，其中一个叫原始 (original) 簇，简记为

C_s

，另一个叫分裂 (split或divisive) 的子簇，记作

C_s

，再从中找出最应该被分裂 (比如，直径最大) 的子簇将其分裂为两个子簇，重复进行这个分裂过程，直到每个子簇中仅包含一个对象，或者已经达到用户指定的终止条件。与AGNES算法类似，用户可以在DIANA聚类算法中指定簇的数目

k

作为算法的一个结束条件。因此，根据算法10-2 (划分聚类算法框架)，我们可以得到DIANA算法的详细计算步骤。

算法10-6 DIANA算法 (分裂层次算法) 输人：数据对象集

S=\{X_1,X_2,\cdots,X_n\}

和正整数

k

(簇的数目) 输出：含

k

个簇的聚类

C=\{C_1,C_2,\cdots,C_k\}

（1）将

S

作为聚类的唯一初始簇，即聚类

C=\{S\}

（2）FOR

h=1,2,...,k-1

（3）在聚类

C

中挑出具有最大直径的簇记作

C_o

。且令

C_s=\varnothing

（4）计算簇

C_o

中每个点到其余点的平均距离，找出具有最大平均距离的一个点

X

，并令

C_o=C_o-\{X\},C_s=C_s\cup \{X\}

（5）REPEAT （6）从

C_o

中任取一点

X_o

，计算

X_o

到

C_s

的最小距离

d_s(X_o,C_s)

（7）计算

C_o-\{X_o\}

到

X_o

的最小距离，并记

X_r\in C_o-\{x_o\}

是取得最小距离的点（8）若

d_s(X_o,C_s)≤d(X_o,X_r)

，则将

X_o

从

C_o

分裂出去，并分配给

C_s

，即令

C_o=C_o-\{X_o\},C_s=C_s\cup\{X_o\}

（9）UNTIL集合

C_o

中没有新的点可以分配给

C_s

（10）将簇

C_o

、簇

C_s

和

C

中未被分裂的簇共同组成新的聚类

C

（11）END FOR

2、计算实例

例10-6 设

S

为有8个数据对象的数据集 (例10-5的表10-5)，用户需要的簇数

k=2

。试用DIANA算法对其进行划分聚类。

解：根据算法10-6，因为

S

有8个数据对象，因此，刚开始所有对象作为一个簇

C_o=\{X_1,X_2,X_3,X_4,X_5,X_6,X_7,X_8\}

。详见下表10-7计算步骤0对应的行。

计算步骤	最大直径的簇	C o C_o Co	C s C_s Cs	簇个数k
0	{ X 1 , X 2 , X 3 , X 4 , X 5 , X 6 , X 7 , X 8 } \{X_1,X_2,X_3,X_4,X_5,X_6,X_7,X_8\} {X1,X2,X3,X4,X5,X6,X7,X8}	{ X 1 , X 2 , X 3 , X 4 , X 5 , X 6 , X 7 , X 8 } \{X_1,X_2,X_3,X_4,X_5,X_6,X_7,X_8\} {X1,X2,X3,X4,X5,X6,X7,X8}	—	1
1	{ X 1 , X 2 , X 3 , X 4 , X 5 , X 6 , X 7 , X 8 } \{X_1,X_2,X_3,X_4,X_5,X_6,X_7,X_8\} {X1,X2,X3,X4,X5,X6,X7,X8}	{ X 2 , X 3 , X 4 , X 5 , X 6 , X 7 , X 8 } \{X_2,X_3,X_4,X_5,X_6,X_7,X_8\} {X2,X3,X4,X5,X6,X7,X8}	{ X 1 } \{X_1\} {X1}	1
2	{ X 1 , X 2 , X 3 , X 4 , X 5 , X 6 , X 7 , X 8 } \{X_1,X_2,X_3,X_4,X_5,X_6,X_7,X_8\} {X1,X2,X3,X4,X5,X6,X7,X8}	{ X 3 , X 4 , X 5 , X 6 , X 7 , X 8 } \{X_3,X_4,X_5,X_6,X_7,X_8\} {X3,X4,X5,X6,X7,X8}	{ X 1 , X 2 } \{X_1,X_2\} {X1,X2}	1
3	{ X 1 , X 2 , X 3 , X 4 , X 5 , X 6 , X 7 , X 8 } \{X_1,X_2,X_3,X_4,X_5,X_6,X_7,X_8\} {X1,X2,X3,X4,X5,X6,X7,X8}	{ X 4 , X 5 , X 6 , X 7 , X 8 } \{X_4,X_5,X_6,X_7,X_8\} {X4,X5,X6,X7,X8}	{ X 1 , X 2 , X 3 } \{X_1,X_2,X_3\} {X1,X2,X3}	1
4	{ X 1 , X 2 , X 3 , X 4 , X 5 , X 6 , X 7 , X 8 } \{X_1,X_2,X_3,X_4,X_5,X_6,X_7,X_8\} {X1,X2,X3,X4,X5,X6,X7,X8}	{ X 5 , X 6 , X 7 , X 8 } \{X_5,X_6,X_7,X_8\} {X5,X6,X7,X8}	{ X 1 , X 2 , X 3 , X 4 } \{X_1,X_2,X_3,X_4\} {X1,X2,X3,X4}	1
5	{ X 1 , X 2 , X 3 , X 4 , X 5 , X 6 , X 7 , X 8 } \{X_1,X_2,X_3,X_4,X_5,X_6,X_7,X_8\} {X1,X2,X3,X4,X5,X6,X7,X8}	{ X 5 , X 6 , X 7 , X 8 } \{X_5,X_6,X_7,X_8\} {X5,X6,X7,X8}	{ X 1 , X 2 , X 3 , X 4 } \{X_1,X_2,X_3,X_4\} {X1,X2,X3,X4}	2

C_o

C_s

簇个数k0