目录
- 三、层次聚类方法
- （一）层次聚类策略
- （二）AGNES算法
- （三）DIANA算法
- 四、密度聚类方法
- （一）基本概念
- （二）算法描述
- （三）计算实例
- （四）算法的性能分析
三、层次聚类方法
（一）层次聚类策略
层次聚类方法对给定的数据集进行层次的分解，直到某种条件满足为止。具体又有凝聚的 (agglomerative) 和分裂的 (divisive) 两种策略。
1、凝聚的层次聚类
这是一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有的对象都在一个簇中，或者某个终结条件被满足，绝大多数层次聚类方法属于这一类，其区别仅在于簇间相似度的选择上有所不同。
2、分裂的层次聚类
这个策略与凝聚的层次聚类相反的，为自顶向下的策略，它首先将所有对象放置在同一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇，或者达到了某个终止条件。
层次凝聚的代表是AGNES (AGglomerative NESting) 算法，层次分裂的代表是DIANA (DIvisive ANAlysis) 算法。图10-15描述了对5个数据对象进行层次聚类计算过程。
最初， AGNES将每个对象作为一个簇，然后根据某种准则 (簇间距离最近或簇间相似度最大)，将这些簇一步一步地合并成较大的簇。例如，如果簇
C
1
C_1
C1与簇
C
2
C_2
C2之间的距离，比其他任意两个簇的距离都小，则将
C
1
C_1
C1和
C
2
C_2
C2合并为一个簇。合并后的簇与其他簇同等看待，继续寻找簇间距离最小的两个簇，并将其合并，直到所有的对象最终都在一个簇中。
在DIANA算法的处理过程中，所有的对象开始都放在一个簇中，然后根据某种原则将该簇分裂，其分裂过程反复进行，直到每个新的簇只包含一个对象为止。
（二）AGNES算法
1、算法描述
AGNES算法是一个典型的凝聚层次聚类方法：最初将每个对象作为一个簇，再根据某种准则 (簇间距离或相似度)，将这些簇逐渐合并成较大的簇，直到所有数据对象都在同一个簇或簇数达到用户指定数目。
簇的凝聚准则可以选择簇间最短距离、最长距离、中心距离和平均距离等。以下算法采用簇间中心距离为目标函数。
算法10-5 AGNES算法 (凝聚层次算法)
输入：数据集 S = { X 1 , X 2 , ⋯ , X n } S=\{X_1,X_2,\cdots,X_n\} S={X1,X2,⋯,Xn}和正整数 k k k (簇的数目)
输出：含 k k k个簇的一个聚类 C = { C 1 , C 2 , ⋯ , C k } C=\{C_1,C_2,\cdots,C_k\} C={C1,C2,⋯,Ck}
（1）将 S S S的每个对象当成一个初始簇，形成初始聚类 C C C
（2）REPEAT
（3） 找出中心距离最近的两个簇
（4） 合并这两个簇，并生成新的聚类 C C C
（5）UNTIL簇的数目等于 k k k
2、计算实例
例10-5 设 S S S为有8个数据对象的数据集 S S S (表10-5)，用户需要的簇数 k = 2 k=2 k=2。试用AGNES算法对其进行划分聚类。
解：首先将表10-15各个点的位置在二维平面给出。如下图10-17。
根据算法10-5，因为
S
S
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 } \{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步、为方便使用簇间中心距离平方。此例开始时有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
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_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(X1,X2)2=d(X1,X3)2=d(X2,X4)2=d(X3,X4)2=1d(X5,X6)2=d(X5,X7)2=d(X6,X8)2=d(X7,X8)2=1 而其它对象之间的中心距离平方，如
d
(
X
1
,
X
4
)
2
、
d
(
X
5
,
X
8
)
2
d(X_1,X_4)^2、d(X_5,X_8)^2
d(X1,X4)2、d(X5,X8)2 等都大于1。
由于有多个簇间中心距离最小且相等。因此，按照数据对象坐标编号小者顺序优先合并，即选择
{
X
1
}
,
{
X
2
}
\{X_1\},\{X_2\}
{X1},{X2} 合并为
{
X
1
,
X
2
}
\{X_1,X_2\}
{X1,X2}。
即得7个簇
{
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_1,X_2\}
{X1,X2} 的中心点为
C
(
1
)
=
(
1
,
1.5
)
C^{(1)}=(1, 1.5)
C(1)=(1,1.5)，并增加计算
C
(
1
)
C^{(1)}
C(1) 与
{
X
3
}
,
…
,
{
X
8
}
\{X_3\},…,\{X_8\}
{X3},…,{X8} 的距离平方。
d
(
C
(
1
)
,
X
3
)
2
=
1.25
,
d
(
C
(
1
)
,
X
4
)
2
=
1.25
d(C^{(1)},X_3)^2=1.25, d(C^{(1)},X_4)^2=1.25
d(C(1),X3)2=1.25,d(C(1),X4)2=1.25，其它
d
(
C
(
1
)
,
X
5
)
2
,
…
,
d
(
C
(
1
)
,
X
8
)
2
d(C^{(1)},X_5)^2, …, d(C^{(1)},X_8)^2
d(C(1),X5)2,…,d(C(1),X8)2 等都大于1.25。因
d
(
X
3
,
X
4
)
2
=
1
d(X_3,X_4)^2=1
d(X3,X4)2=1，故簇
{
X
3
}
\{X_3\}
{X3} 和
{
X
4
}
\{X_4\}
{X4} 合并为
{
X
3
,
X
4
}
\{X_3,X_4\}
{X3,X4}，见表10-6计算步骤2所在的行。
第3步、重新计算簇
{
X
3
,
X
4
}
\{X_3,X_4\}
{X3,X4} 的中心点为
C
(
2
)
=
(
2
,
1.5
)
C^{(2)}=(2, 1.5)
C(2)=(2,1.5)，并增加计算
C
(
2
)
C^{(2)}
C(2) 与
C
(
1
)
,
{
X
5
}
,
{
X
6
}
,
{
X
7
}
,
{
X
8
}
C^{(1)},\{X_5\},\{X_6\},\{X_7\},\{X_8\}
C(1),{X5},{X6},{X7},{X8} 的距离平方。
d
(
C
(
1
)
,
C
(
2
)
)
2
=
1
,
d
(
C
(
2
)
,
X
5
)
2
=
7.25
d(C^{(1)},C^{(2)})^2=1, d(C^{(2)},X_5)^2=7.25
d(C(1),C(2))2=1,d(C(2),X5)2=7.25，且
d
(
C
(
2
)
,
X
6
)
2
,
d
(
C
(
2
)
,
X
7
)
2
,
d
(
C
(
2
)
,
X
8
)
2
d(C^{(2)},X_6)^2,d(C^{(2)},X_7)^2,d(C^{(2)},X_8)^2
d(C(2),X6)2,d(C(2),X7)2,d(C(2),X8)2 更大。因此簇
{
X
1
,
X
2
}
\{X_1,X_2\}
{X1,X2} 和
{
X
3
,
X
4
}
\{X_3,X_4\}
{X3,X4} 合并为
{
X
1
,
X
2
,
X
3
,
X
4
}
\{X_1,X_2,X_3,X_4\}
{X1,X2,X3,X4}，见表10-6计算步骤3所在的行。
第4步、重新计算簇
{
X
1
,
X
2
,
X
3
,
X
4
}
\{X_1,X_2,X_3,X_4\}
{X1,X2,X3,X4} 的中心点为
C
(
3
)
=
(
1.5
,
1.5
)
C^{(3)}=(1.5, 1.5)
C(3)=(1.5,1.5)，并增加计算
C
(
3
)
C^{(3)}
C(3) 与
{
X
5
}
,
{
X
6
}
,
{
X
7
}
,
{
X
8
}
\{X_5\},\{X_6\},\{X_7\},\{X_8\}
{X5},{X6},{X7},{X8} 的距离平方。
d
(
C
(
3
)
,
X
5
)
2
=
8.5
d(C^{(3)},X_5)^2=8.5
d(C(3),X5)2=8.5，且
d
(
C
(
3
)
,
X
6
)
2
,
d
(
C
(
3
)
,
X
7
)
2
,
d
(
C
(
3
)
,
X
8
)
2
d(C^{(3)},X_6)^2,d(C^{(3)},X_7)^2,d(C^{(3)},X_8)^2
d(C(3),X6)2,d(C(3),X7)2,d(C(3),X8)2 更大。而
d
(
X
5
,
X
6
)
=
1
d(X_5,X_6)=1
d(X5,X6)=1，因此簇
{
X
5
}
\{X_5\}
{X5} 和
{
X
6
}
\{X_6\}
{X6} 合并为
{
X
5
,
X
6
}
\{X_5,X_6\}
{X5,X6}，见表10-6计算步骤4所在的行。
第5步、重新计算簇
{
X
5
,
X
6
}
\{X_5,X_6\}
{X5,X6} 的中心点为
C
(
4
)
=
(
3
,
4.5
)
C^{(4)}=(3, 4.5)
C(4)=(3,4.5)，并增加计算
C
(
4
)
C^{(4)}
C(4) 与
C
(
3
)
,
{
X
7
}
,
{
X
8
}
C^{(3)},\{X_7\},\{X_8\}
C(3),{X7},{X8} 的距离平方。
d
(
C
(
4
)
,
C
(
3
)
)
2
=
11.25
d(C^{(4)},C^{(3)})^2=11.25
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(C^{(4)},X_7)^2=1.25,d(C^{(4)},X_8)^2=1.25,
d(C(4),X7)2=1.25,d(C(4),X8)2=1.25, 而
d
(
X
7
,
X
8
)
2
=
1
d(X_7,X_8)^2=1
d(X7,X8)2=1。因此簇
{
X
7
}
\{X_7\}
{X7} 和
{
X
8
}
\{X_8\}
{X8} 合并为
{
X
7
,
X
8
}
\{X_7,X_8\}
{X7,X8}，见表10-6计算步骤5所在的行。
第6步、重新计算簇
{
X
7
,
X
8
}
\{X_7,X_8\}
{X7,X8} 的中心点为
C
(
5
)
=
(
4
,
4.5
)
C^{(5)}=(4, 4.5)
C(5)=(4,4.5)，并增加计算
C
(
5
)
C^{(5)}
C(5) 与
C
(
3
)
,
C
(
4
)
,
C
(
1
)
C^{(3)},C^{(4)},C^{(1)}
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^{(3)})^2=11.25, d(C^{(5)},C^{(4)})^2=1
d(C(5),C(3))2=11.25,d(C(5),C(4))2=1 而
d
(
C
(
5
)
,
C
(
1
)
)
2
=
15.25
d(C^{(5)},C^{(1)})^2=15.25
d(C(5),C(1))2=15.25。因此簇
{
X
5
,
X
6
}
\{X_5,X_6\}
{X5,X6} 和
{
X
7
,
X
8
}
\{X_7,X_8\}
{X7,X8} 合并为
{
X
5
,
X
6
,
X
7
,
X
8
}
\{X_5,X_6,X_7,X_8\}
{X5,X6,X7,X8}，见表10-6计算步骤6所在的行。
由于合并后的簇的数目 k = 2 k=2 k=2 已经达到用户输入的终止条件，程序结束。
3、算法的性能分析
AGNES算法思想比较简单，但经常会因为出现多个簇间距离相等的情况，这时究竟选择哪两个簇优先合并是非常关键的，但又是比较困难的。因为两个簇合并的决定一经做出，以后的处理只能在新生成的簇上进行，即使后来发现聚类效果不好，但前面已经做过的合并处理却不能撤销，而每个簇之间又不能交换对象。即如果在某一步对簇进行合并时没有选择恰当，最终可能导致低质量的聚类结果。
AGNES算法的时间复杂性为
O
(
n
2
)
O(n^2)
O(n2)，因为对
n
n
n个对象的数据集，算法必须计算所有对象两两之间的距离，其乘法计算量就达到
n
(
n
−
1
)
/
2
n(n-1)/2
n(n−1)/2。此外，因为刚开始的时候就有
n
n
n个簇，如果最后以1个簇结束，则主循环中有
n
n
n次迭代，在第
i
i
i次迭代中，我们必须在
n
−
i
+
1
n-i+1
n−i+1 个簇中找到最靠近的两个簇进行合并。因此，这种聚类方法不具有很好的可伸缩性，即该算法在
n
n
n很大的情况就不是很适用。
（三）DIANA算法
1、算法描述
DIANA算法属于分裂的层次聚类。它的计算思路与凝聚的层次聚类方法相反，采用一种自顶向下的分裂策略。它首先将所有对象置于一个簇中，然后逐渐将其细分为越来越小的簇，直到每个对象自成一簇，或者达到了某个终结条件，例如达到了用户希望的簇数目，或者是两个最近簇之间的距离超过了指定的某个阈值等。
在DIANA算法的处理过程中，刚开始将所有的对象都放在一个簇中，然后根据一定的评价函数将其分裂为两个子簇，其中一个叫原始 (original) 簇，简记为
C
s
C_s
Cs，另一个叫分裂 (split或divisive) 的子簇，记作
C
s
C_s
Cs，再从中找出最应该被分裂 (比如，直径最大) 的子簇将其分裂为两个子簇，重复进行这个分裂过程，直到每个子簇中仅包含一个对象，或者已经达到用户指定的终止条件。
与AGNES算法类似，用户可以在DIANA聚类算法中指定簇的数目
k
k
k作为算法的一个结束条件。因此，根据算法10-2 (划分聚类算法框架)，我们可以得到DIANA算法的详细计算步骤。
算法10-6 DIANA算法 (分裂层次算法)
输人：数据对象集 S = { X 1 , X 2 , ⋯ , X n } S=\{X_1,X_2,\cdots,X_n\} S={X1,X2,⋯,Xn}和正整数 k k k (簇的数目)
输出：含 k k k个簇的聚类 C = { C 1 , C 2 , ⋯ , C k } C=\{C_1,C_2,\cdots,C_k\} C={C1,C2,⋯,Ck}
（1）将 S S S作为聚类的唯一初始簇，即聚类 C = { S } C=\{S\} C={S}
（2）FOR h = 1 , 2 , . . . , k − 1 h=1,2,...,k-1 h=1,2,...,k−1
（3）在聚类 C C C中挑出具有最大直径的簇记作 C o C_o Co。且令 C s = ∅ C_s=\varnothing Cs=∅
（4）计算簇 C o C_o Co中每个点到其余点的平均距离，找出具有最大平均距离的一个点 X X X，并令 C o = C o − { X } , C s = C s ∪ { X } C_o=C_o-\{X\},C_s=C_s\cup \{X\} Co=Co−{X},Cs=Cs∪{X}
（5）REPEAT
（6）从 C o C_o Co中任取一点 X o X_o Xo，计算 X o X_o Xo到 C s C_s Cs的最小距离 d s ( X o , C s ) d_s(X_o,C_s) ds(Xo,Cs)
（7）计算 C o − { X o } C_o-\{X_o\} Co−{Xo}到 X o X_o Xo的最小距离，并记 X r ∈ C o − { x o } X_r\in C_o-\{x_o\} Xr∈Co−{xo}是取得最小距离的点
（8）若 d s ( X o , C s ) ≤ d ( X o , X r ) d_s(X_o,C_s)≤d(X_o,X_r) ds(Xo,Cs)≤d(Xo,Xr)，则将 X o X_o Xo从 C o C_o Co分裂出去，并分配给 C s C_s Cs，即令 C o = C o − { X o } , C s = C s ∪ { X o } C_o=C_o-\{X_o\},C_s=C_s\cup\{X_o\} Co=Co−{Xo},Cs=Cs∪{Xo}
（9）UNTIL集合 C o C_o Co中没有新的点可以分配给 C s C_s Cs
（10）将簇 C o C_o Co、簇 C s C_s Cs和 C C C中未被分裂的簇共同组成新的聚类 C C C
（11）END FOR
2、计算实例
例10-6 设 S S S为有8个数据对象的数据集 (例10-5的表10-5)，用户需要的簇数 k = 2 k=2 k=2。试用DIANA算法对其进行划分聚类。
解：根据算法10-6，因为 S S S有8个数据对象，因此，刚开始所有对象作为一个簇 C o = { X 1 , X 2 , X 3 , X 4 , X 5 , X 6 , X 7 , X 8 } C_o=\{X_1,X_2,X_3,X_4,X_5,X_6,X_7,X_8\} Co={X1,X2,X3,X4,X5,X6,X7,X8}。详见下表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_o Co中分裂成两个簇，要计算每个对象 X i X_i Xi到其它对象 X j ( j = 1 , 2 , … , 8 ; i ≠ j ) X_j (j=1, 2, …, 8; i≠j) Xj(j=1,2,…,8;i=j)的平均相异度。
第一轮循环 (FOR h=1) 时，
由于
d
a
(
{
X
1
}
,
{
⋅
}
)
=
d
a
(
{
X
8
}
,
{
⋅
}
)
=
2.96
d_a(\{X_1\},\{\cdot\})=d_a(\{X_8\},\{\cdot\})=2.96
da({X1},{⋅})=da({X8},{⋅})=2.96 取得最大平均距离，按照对象下标编号小者优先的原则，将
X
1
X_1
X1 从
C
o
C_o
Co 中分裂出去，并分配给
C
s
C_s
Cs，即得
C
s
=
{
X
1
}
C_s=\{X_1\}
Cs={X1}，
C
o
=
{
X
2
,
X
3
,
X
4
,
X
5
,
X
6
,
X
7
,
X
8
}
C_o=\{X_2,X_3,X_4,X_5,X_6,X_7,X_8\}
Co={X2,X3,X4,X5,X6,X7,X8}。
内循环REPEAT 包括以下4个步骤：
第1步（1）从
C
o
=
{
X
2
,
X
3
,
X
4
,
X
5
,
X
6
,
X
7
,
X
8
}
C_o=\{X_2,X_3,X_4,X_5,X_6,X_7,X_8\}
Co={X2,X3,X4,X5,X6,X7,X8} 中取一点
X
2
X_2
X2，计算它到
C
s
C_s
Cs 最小距离，经计算可得
d
s
(
X
2
,
C
s
)
=
1
d_s(X_2,C_s)=1
ds(X2,Cs)=1;
（2）计算点
X
2
X_2
X2 到
C
o
C_o
Co 中其它点的最小距离，即有
d
(
X
2
,
X
4
)
=
1
d(X_2,X_4)=1
d(X2,X4)=1;
（3）因
d
(
X
2
,
C
s
)
≤
d
(
X
2
,
X
4
)
d(X_2,C_s)≤d(X_2,X_4)
d(X2,Cs)≤d(X2,X4)，所以将
X
2
X_2
X2 从
C
o
C_o
Co 中分裂出去，并分配给
C
s
C_s
Cs，即得
C
o
=
{
X
3
,
X
4
,
X
5
,
X
6
,
X
7
,
X
8
}
C_o=\{X_3,X_4,X_5,X_6,X_7,X_8\}
Co={X3,X4,X5,X6,X7,X8}，
C
s
=
{
X
1
,
X
2
}
C_s=\{X_1 , X_2\}
Cs={X1,X2}。
第2步 把
X
3
X_3
X3 从
C
o
C_o
Co 中分裂出去，并分配给
C
s
C_s
Cs，即得
C
o
=
{
X
4
,
X
5
,
X
6
,
X
7
,
X
8
}
C_o=\{X_4,X_5,X_6,X_7,X_8\}
Co={X4,X5,X6,X7,X8}，
C
s
=
{
X
1
,
X
2
,
X
3
}
C_s=\{X_1,X_2, X_3\}
Cs={X1,X2,X3}。
第3步（1）从
C
o
=
{
X
4
,
X
5
,
X
6
,
X
7
,
X
8
}
C_o=\{X_4,X_5,X_6,X_7,X_8\}
Co={X4,X5,X6,X7,X8} 取一点
X
4
X_4
X4，计算它到
C
s
C_s
Cs 最小距离，经计算可得
d
s
(
X
4
,
C
s
)
=
1
d_s(X_4,C_s)=1
ds(X4,Cs)=1；
（2）计算点
X
4
X_4
X4 到
C
o
C_o
Co 中其它点的最小距离，即有
d
(
X
4
,
X
5
)
=
2.24
d(X_4,X_5)=2.24
d(X4,X5)=2.24；
（3）因
d
(
X
4
,
X
2
)
≤
d
(
X
4
,
X
5
)
d(X_4,X_2)≤d(X_4,X_5)
d(X4,X2)≤d(X4,X5)，因此把
X
4
X_4
X4 从
C
o
C_o
Co 中分裂出去，并分配给
C
s
C_s
Cs，即得
C
o
=
{
X
5
,
X
6
,
X
7
,
X
8
}
C_o=\{X_5,X_6,X_7,X_8\}
Co={X5,X6,X7,X8}，
C
s
=
{
X
1
,
X
2
,
X
3
,
X
4
}
C_s=\{X_1, X_2, X_3, X_4\}
Cs={X1,X2,X3,X4}。
第4步 按照上面方法，分别计算
X
5
,
X
6
,
X
7
,
X
8
X_5,X_6,X_7,X_8
X5,X6,X7,X8 到
C
s
C_s
Cs 的最小距离
d
s
(
X
i
,
C
s
)
(
i
=
5
,
6
,
7
,
8
)
d_s(X_i,C_s) (i=5,6,7,8)
ds(Xi,Cs)(i=5,6,7,8)，但有
d
s
(
X
i
,
C
s
)
>
d
(
X
i
,
X
j
)
(
i
=
5
,
6
,
7
,
8
;
i
≠
j
)
d_s(X_i,C_s)>d(X_i,X_j) (i=5,6,7,8;i≠j)
ds(Xi,Cs)>d(Xi,Xj)(i=5,6,7,8;i=j)，即
C
o
C_o
Co 中没有点需要分裂出去分配给
C
s
C_s
Cs；至此，得到聚类
C
=
{
{
X
1
,
X
2
,
X
3
,
X
4
}
,
{
X
5
,
X
6
,
X
7
,
X
8
}
}
=
{
C
1
,
C
2
}
C=\{\{X_1,X_2,X_3,X_4\},\{X_5,X_6,X_7,X_8\}\}=\{C_1,C_2\}
C={{X1,X2,X3,X4},{X5,X6,X7,X8}}={C1,C2}。
由于 k = 2 k=2 k=2，因此算法结束并输出聚类 C C C，将其与图10-17比较可以发现，这个聚类结果还是相当令人满意的。但是，如果在例10-6中指定 k = 4 k=4 k=4，则算法需要进入第二轮和第三轮循环。
第二轮循环 (FOR h=2)，得聚类 C = { { X 1 , X 2 , X 3 } , { X 4 } , { X 5 , X 6 , X 7 , X 8 } } = { C 1 , C 2 , C 3 } C=\{\{X_1,X_2,X_3\},\{X_4\},\{X_5,X_6,X_7,X_8\}\}=\{C_1,C_2,C_3\} C={{X1,X2,X3},{X4},{X5,X6,X7,X8}}={C1,C2,C3}
第三轮循环 (FOR h=3)，得聚类 C = { { X 1 , X 2 } , { X 3 } , { X 4 } , { X 5 , X 6 , X 7 , X 8 } } = { C 1 , C 2 , C 3 , C 4 } C=\{\{X_1,X_2\},\{X_3\},\{X_4\},\{X_5,X_6,X_7,X_8\}\}=\{C_1,C_2,C_3,C_4\} C={{X1,X2},{X3},{X4},{X5,X6,X7,X8}}={C1,C2,C3,C4}。
即DIANA算法得到了包括4个簇的聚类，算法结束。将以上结果与图10-17比较发现，虽然DIANA算法得到了包括4个簇的聚类，但这个聚类 C = { { X 1 , X 2 } , { X 3 } , { X 4 } , { X 5 , X 6 , X 7 , X 8 } } = { C 1 , C 2 , C 3 , C 4 } C=\{\{X_1,X_2\},\{X_3\},\{X_4\},\{X_5,X_6,X_7,X_8\}\}=\{C_1,C_2,C_3,C_4\} C={{X1,X2},{X3},{X4},{X5,X6,X7,X8}}={C1,C2,C3,C4} 显得很不靠谱，这个例子进一步说明，DIANA算法对k值的选取也是敏感的。
3、算法的性能分析
DIANA算法与AGNES算法一样，其时间复杂性为 O ( n 2 ) O(n^2) O(n2)，因为对有 n n n个数据对象的数据集，算法也必须计算所有对象两两之间的距离，其乘法计算量就达到 n ( n − 1 ) / 2 n(n-1)/2 n(n−1)/2。因此，这种聚类方法同样不具有很好的可伸缩性，即该算法在 n n n很大的情况就不是很适用。
四、密度聚类方法
密度聚类方法的指导思想是，只要一个区域中对象的密度大于某个域值，就把它加到与之相近的簇中去。这种算法可发现任意形状的簇，对噪声数据也不敏感。
DBSCAN (Density Based Spatial Clustering of Applications with Noise) 是基于密度的聚类算法代表，且是一种部分聚类算法，即聚类
C
C
C中所有簇的并集不能覆盖数据集
S
S
S本身。
（一）基本概念
定义10-2 给定一个对象集 S S S 和实数 ε > 0 \varepsilon>0 ε>0，则对于任意 X ∈ S X\in S X∈S，称 ε ( X ) = { Y ∣ Y ∈ S , d ( Y , X ) ≤ ε } \varepsilon(X)=\{Y | Y\in S, d(Y,X)≤\varepsilon\} ε(X)={Y∣Y∈S,d(Y,X)≤ε} 为 X X X 在 S S S 中的 ε \varepsilon ε-邻域，简称 X X X 的 ε \varepsilon ε-邻域。
显然，如果 S S S为在平面上有20个对象的集合，且距离函数采用欧几里距离，则 X X X的 ε \varepsilon ε-邻域是以 X X X为中心， ε \varepsilon ε为半径的圆内所有对象构成。对于图10-19所示的数据集 S S S，其 X X X的 ε \varepsilon ε-邻域就由圆内 (含圆周上) 的8个深色点构成。另外，如果在定义10-2中采用的距离函数 d ( Y , X ) d(Y,X) d(Y,X) 不同，则 X X X在 S S S中的 ε \varepsilon ε-邻域 ε ( X ) \varepsilon(X) ε(X) 也会不同。比如，当 d ( Y , X ) d(Y,X) d(Y,X) 选用切比雪夫距离时， ε ( X ) \varepsilon(X) ε(X) 确定的区域就是一个矩形而不是圆形。因此，我们一般应该根据实际问题的特点选用合适的距离函数。
定义10-3 对于给定的实数
ε
>
0
\varepsilon>0
ε>0 和正整数
MinPts
\text{MinPts}
MinPts，称 (
ε
\varepsilon
ε,
MinPts
\text{MinPts}
MinPts) 是为
S
S
S指定的一个密度，简称 (
ε
\varepsilon
ε,
MinPts
\text{MinPts}
MinPts) 为密度。
在DBSCAN算法中，密度 ( ε \varepsilon ε, MinPts \text{MinPts} MinPts) 专门用于刻画一个簇中对象的密集程度，为此引入核心对象的概念。
定义10-4 对给定的密度 ( ε \varepsilon ε, MinPts \text{MinPts} MinPts) 和任意 X ∈ S X\in S X∈S，若 ε ∣ ( X ) ∣ ≥ MinPts \varepsilon|(X)|≥\text{MinPts} ε∣(X)∣≥MinPts，则称 X X X是 S S S关于密度 ( ε \varepsilon ε, MinPts \text{MinPts} MinPts) 的一个核心点，简称 X X X为核心点 (对象)。
例10-7 假设给定 ε = 2.5 c m \varepsilon=2.5cm ε=2.5cm， MinPts = 8 \text{MinPts}=8 MinPts=8，则图10-19中的点 X X X就是 S S S的一个核心对象。但如果指定 MinPts = 10 \text{MinPts}=10 MinPts=10，即使 ε \varepsilon ε 取值不变， X X X也不再是 S S S的核心点了。
定义10-5 ∀ Y , X ∈ S \forall Y, X\in S ∀Y,X∈S，若 X X X是一个核心点且 Y ∈ ε ( X ) Y\in\varepsilon(X) Y∈ε(X)，则称点 Y Y Y从 X X X出发关于 ( ε , MinPts ) (\varepsilon,\text{MinPts}) (ε,MinPts) 是直接密度可达的，简称从 X X X到 Y Y Y是直接密度可达的。
例10-8 根据定义10-5，下图10-20中的对象 Y Y Y从 X X X出发关于 ( ε , MinPts ) (\varepsilon,\text{MinPts}) (ε,MinPts) 是直接密度可达的，即从 X X X到 Y Y Y是直接密度可达的。然而，从 X X X到 Z i ( i = 1 , 2 , 3 ) Z_i (i=1,2,3) Zi(i=1,2,3) 就不是直接密度可达的。
定义10-6 如果
S
S
S存在一个对象链
X
1
,
X
2
,
…
,
X
n
,
X
1
=
X
,
X
n
=
Y
X_1,X_2, …, X_n,X_1=X,X_n=Y
X1,X2,…,Xn,X1=X,Xn=Y，且从
X
i
(
1
≤
i
≤
n
−
1
)
X_i (1≤i≤n-1)
Xi(1≤i≤n−1) 到
X
i
+
1
X_{i+1}
Xi+1 是直接密度可达的，则称从
X
X
X到
Y
Y
Y是密度可达的。
例10-9 对包含21个点的平面数据集 S S S (图10-21)，如果密度参数 ε = 2.5 c m \varepsilon=2.5cm ε=2.5cm 且 MinPts = 8 \text{MinPts}=8 MinPts=8，请说明从 X X X到 Y Y Y关于 ( ε , MinPts ) (\varepsilon,\text{MinPts}) (ε,MinPts) 是密度可达的。
定义10-7 对于任意
Y
,
Z
∈
S
Y,Z\in S
Y,Z∈S，如果存在
X
∈
S
X\in S
X∈S，使从
X
X
X到
Y
Y
Y，从
X
X
X到
Z
Z
Z都是关于
(
ε
,
MinPts
)
(\varepsilon,\text{MinPts})
(ε,MinPts) 密度可达的，则称
Y
Y
Y和
Z
Z
Z关于
(
ε
,
MinPts
)
(\varepsilon,\text{MinPts})
(ε,MinPts) 是密度相连的。
定义10-8 设有对象集
S
S
S，若它的非空子集
C
o
C_o
Co满足以下条件：
（1）对于任意
X
,
Y
∈
S
X,Y\in S
X,Y∈S，如果
X
∈
C
o
X\in C_o
X∈Co，且从
X
X
X到
Y
Y
Y关于
(
ε
,
MinPts
)
(\varepsilon,\text{MinPts})
(ε,MinPts) 是密度可达的，则
Y
∈
C
o
Y\in C_o
Y∈Co；
（2）对于任意
X
,
Y
∈
C
o
X,Y\in C_o
X,Y∈Co，则
X
X
X和
Y
Y
Y关于
(
ε
,
MinPts
)
(\varepsilon,\text{MinPts})
(ε,MinPts) 是密度相连的，则称
C
o
C_o
Co是一个关于密度
(
ε
,
MinPts
)
(\varepsilon,\text{MinPts})
(ε,MinPts) 的簇，简称
C
o
C_o
Co是基于密度的簇。
从定义10-8可知，一个基于密度的簇是基于密度可达性的最大的密度相连对象的集合。
定义10-9 对于任意 Y ∈ S Y\in S Y∈S，若 Y Y Y不是关于密度 ( ε , MinPts ) (\varepsilon,\text{MinPts}) (ε,MinPts) 的核心点，但存在核心点 X X X，使 Y ∈ ε ( X ) Y\in \varepsilon(X) Y∈ε(X)，则称 Y Y Y为 S S S边界点。
定义10-10 对于意 Y ∈ S Y\in S Y∈S，如果 Y Y Y既不是关于密度 ( ε , MinPts ) (\varepsilon,\text{MinPts}) (ε,MinPts) 核心点，也不是边界点，则称 Y Y Y为 S S S关于密度 ( ε , MinPts ) (\varepsilon,\text{MinPts}) (ε,MinPts) “噪声”点，简称 Y Y Y为 S S S的噪声点。
从定义10-10可知， S S S的一个对象 Y Y Y是否为噪声点，完全与给定的密度 ( ε , MinPts ) (\varepsilon,\text{MinPts}) (ε,MinPts) 相关。一般地说，若 Y Y Y关于 ( ε , MinPts ) (\varepsilon,\text{MinPts}) (ε,MinPts) 为噪声点，则只要让 ε \varepsilon ε足够大，或适当减小 MinPts \text{MinPts} MinPts，就可以使 Y Y Y不再是噪声点。
根据以上定义，我们可以得出以下两个有用的定理。
定理10-1 对于任意
X
∈
S
X\in S
X∈S，如果
X
X
X是一个核心点，即
∣
ε
(
X
)
∣
≥
MinPts
|\varepsilon(X)|≥\text{MinPts}
∣ε(X)∣≥MinPts，则集合
C
X
=
{
Y
∣
Y
∈
S
且从
X
到
Y
关于
(
ε
,
MinPts
)
是密度可达的
}
C_X=\{Y | Y\in S且从X到Y关于(\varepsilon,\text{MinPts})是密度可达的\}
CX={Y∣Y∈S且从X到Y关于(ε,MinPts)是密度可达的} 称为
S
S
S上一个关于密度
(
ε
,
MinPts
)
(\varepsilon,\text{MinPts})
(ε,MinPts) 的簇。
此定理其实是一个关于密度 ( ε , MinPts ) (\varepsilon,\text{MinPts}) (ε,MinPts) 的簇的生成方法，即由核心对象 X X X及其所有从 X X X密度可达对象 Y Y Y所构成的集合，就是一个关于密度 ( ε , MinPts ) (\varepsilon,\text{MinPts}) (ε,MinPts) 的簇，我们将其称为由核心对象 X X X生成的簇。
定理10-2 设
C
o
C_o
Co为一个关于密度
(
ε
,
MinPts
)
(\varepsilon,\text{MinPts})
(ε,MinPts) 的簇，
X
∈
C
o
且
ε
∣
(
X
)
∣
≥
MinPts
X\in C_o且\varepsilon|(X)|≥\text{MinPts}
X∈Co且ε∣(X)∣≥MinPts，则
C
o
=
{
Y
∣
Y
∈
S
且从
X
到
Y
关于
(
ε
,
MinPts
)
是密度可达的
}
C_o=\{Y | Y\in S且从X到Y关于(\varepsilon,\text{MinPts})是密度可达的\}
Co={Y∣Y∈S且从X到Y关于(ε,MinPts)是密度可达的} 此定理进一步说明，一个关于密度
(
ε
,
MinPts
)
(\varepsilon,\text{MinPts})
(ε,MinPts) 的簇
C
o
C_o
Co，都等同于它的任一核心对象
X
X
X生成的簇。
（二）算法描述
DBSCAN算法通过检查数据集 S S S中每个点 X X X的 ε \varepsilon ε-邻域 ε ( X ) \varepsilon(X) ε(X) 来寻找一个由 X X X生成的簇。对于每一个 X ∈ S X\in S X∈S，如果有 ε ( X ) ≥ MinPts \varepsilon(X)≥\text{MinPts} ε(X)≥MinPts，则创建一个以 X X X为核心点的新簇，并将从 X X X密度可达的所有对象并入这个新簇，直到没有任何新的点可以添加到这个簇时，才开始检查 S S S中下一个点，直到 S S S中的每个点都已经检查完毕。
算法10-7 DBSCAN算法
输入：数据对象集 S = { X 1 , X 2 , … , X n } S=\{X_1,X_2,…,X_n\} S={X1,X2,…,Xn}和密度 ( ε , MinPts ) (\varepsilon,\text{MinPts}) (ε,MinPts)
输出：达到密度要求的聚类 C = { C 1 , C 2 , . . . , C k } C=\{C_1,C_2,...,C_k\} C={C1,C2,...,Ck}
（1） C = ∅ C=\varnothing C=∅
（2）REPEAT
（3）从数据集 S S S中抽取一个未处理过的对象 X u X_u Xu
（4）如果 X u X_u Xu是核心对象且名，不在 C C C的任何簇中，则将 X u X_u Xu连同从它出发密度可达的所有对象形成簇 C u C_u Cu，并令 C = C ∪ { C u } C=C\cup\{C_u\} C=C∪{Cu}
（5）否则转第 (2) 步
（6）UNTIL所有对象都被处理
（三）计算实例
例10-10 设数据集 S S S共有12个对象，密度 ( ε = 1 , MinPts = 4 ) (\varepsilon=1, \text{MinPts}=4) (ε=1,MinPts=4)。试用DBSCAN算法对其进行聚类。
解：将12个对象及其相对位置展示在平面上 (图10-25)。
按照算法步骤，依次选择
S
S
S中的点
X
i
X_i
Xi，并检查它是否为关于密度
(
ε
=
1
,
MinPts
=
4
)
(\varepsilon=1, \text{MinPts}=4)
(ε=1,MinPts=4) 的核心点，如果是则将
X
i
(
i
=
1
,
2
,
…
,
12
)
X_i (i=1,2,…,12)
Xi(i=1,2,…,12) 以及所有从它密度可达的点形成一个新簇。其详细计算过程描述如下。
第1步，在
S
S
S中选择一点
X
1
X_1
X1，由于以
X
1
X_1
X1为中心，
ε
=
1
\varepsilon=1
ε=1半径的圆内仅包含2个点
{
X
1
,
X
4
}
\{X_1,X_4\}
{X1,X4}，即
ε
(
X
1
)
=
2
<
MinPts
\varepsilon(X_1)=2<\text{MinPts}
ε(X1)=2<MinPts，因此它不是核心点，继续选择下一个点。
第2步，在
S
S
S中选择一点
X
2
X_2
X2，它也不是核心点，继续选下一个点。
第3步，在
S
S
S中选择一点
X
3
X_3
X3，它也不是核心点，继续选下一个点。
第4步，在
S
S
S中选择一点
X
4
X_4
X4，由于以
X
4
X_4
X4为中心，
ε
=
1
\varepsilon=1
ε=1为半径的圆内仅包含5个点
{
X
1
,
X
3
,
X
4
,
X
5
,
X
10
}
\{X_1, X_3, X_4, X_5, X_{10}\}
{X1,X3,X4,X5,X10}，即
ε
(
X
4
)
=
5
≥
MinPts
\varepsilon(X_4)=5≥\text{MinPts}
ε(X4)=5≥MinPts，因此它是关于密度
(
ε
=
1
,
MinPts
=
4
)
(\varepsilon=1, \text{MinPts}=4)
(ε=1,MinPts=4) 的一个核心点，寻找从它出发密度可达的点，其中直接密度可达4个，密度可达3个，因此，得到以核心点
X
4
X_4
X4出发密度可达的所有对象形成的簇，记作
C
1
=
{
X
1
,
X
3
,
X
4
,
X
5
,
X
9
,
X
10
,
X
12
}
C_1=\{X_1, X_3, X_4, X_5, X_9, X_{10}, X_{12}\}
C1={X1,X3,X4,X5,X9,X10,X12}。按算法步骤继续选择下一个点。
第5步，在
S
S
S中选择一点
X
5
X_5
X5，由于
X
5
X_5
X5已在簇
C
1
C_1
C1中，因此无需判断是否为核心点，继续选择下一个点。
类似地，依次选择一点
X
6
,
X
7
,
X
8
,
X
9
,
X
10
,
X
11
,
X
12
X_6, X_7, X_8, X_9, X_{10}, X_{11}, X_{12}
X6,X7,X8,X9,X10,X11,X12，其计算结果汇总于下表。
（四）算法的性能分析
DBSCAN需要对数据集中的每个点进行考察，通过检查每个点的
ε
\varepsilon
ε-邻域来寻找聚类。如果某个点
X
X
X为核心对象，则创建一个以该点
X
X
X为核心对象的新簇，该簇包括核心对象
X
X
X以及从
X
X
X出发密度可达的所有点。如果
S
S
S中有
n
n
n对象，则其时间复杂性是
O
(
n
2
)
O(n^2)
O(n2)。
DBSCAN算法将达到或超过密度
(
ε
,
MinPts
)
(\varepsilon,\text{MinPts})
(ε,MinPts) 生成的区域划分为簇，并可以在带有“噪声”的数据集中发现任意形状的簇，形成
S
S
S的一个部分聚类。
说明：DBSCAN算法对用户定义的密度
(
ε
,
MinPts
)
(\varepsilon,\text{MinPts})
(ε,MinPts) 参数是敏感的，即
ε
\varepsilon
ε 和
MinPts
\text{MinPts}
MinPts 的设置将直接影响聚类的效果。如果两个参数的设置稍有不同，就可能导致完全不同的聚类结果。
