聚类算法综述
Sunstone Zhang
1. 分层次聚类法（最短距离法）.........................................................................................................1
2. 最简单的聚类方法.............................................................................................................................2
3. 最大距离样本.....................................................................................................................................3
4. K 平均聚类法（距离平方和最小聚类法） ......................................................................................3
5. 叠代自组织（ISODATA）聚类法....................................................................................................4
6. ISODATA 法的改进 ...........................................................................................................................5
7. 基于“核”的评估聚类方法 ...............................................................................................................6
聚类（Cluster）：相似文档的分组表达方式。在向量空间模型中，用户可以通过
比较查询向量和聚类的中心进行检索，并在聚类中进一步检索以找到最相似的文
档。
向量空间模型（Vector Space Model ）：文档和查询的一种表达方式，将它们转
换为向量。向量的特征一般是对应文档或查询中处理过的单词（取过词根并且删
除了 stopword）。这些向量被赋予权重以强调那些与语义相关的词目，这在检索
中很有用。在检索中比较查询向量和文档向量，并将最接近的文档作为相关文档
返回给用户。SMART 是使用向量空间模型的最有名的例子。
1. 分层次聚类法（最短距离法）
思路：寻找“距离”最近的两个样本结合
1. 有 N 个样本的集合 Z
s
={Z
1
, Z
2
, ..., Z
N
}
2. 若想要聚成 K 个类 （事先给定 K）
[1] k=N, C
i
={Z
i
}, i=1,2,...,N
[2] if k=K then END
[3] 找到 C
i
与 C
j
之间的距离 d(C
i
, C
j
)最小的一对
[4] C
i
和 C
j
合成一个类 C
i
, 并计算新的 C
i
的中心
[5] 去除 C
j
, k=k-1. goto [2]
类间距离 d(C
i
, C
j
)
1. 类中心间距：d
1
=||M
i
– M
j
||，其中
∑
∈
=
i
CZ
i
i
Z
n
M
1
，n
i
是属于 C
i
的样本数。
2.
靠得最近的样本： ||||
,
min
2 ji
jjii
ZZ
CZCZ
d −
∈∈
=
