毕 业 设 计 （ 论文 ） 第 1 页
1 绪论
将物理或抽象对象的集合分成由类似的对象组成的多个类的过程被称为聚类。由聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似，与其他簇中的对象相异。“物以类聚，人以群分”，在自然科学和社会科学中，存在着大量的分类问题。聚类分析又称群分析，它是研究（样品或指标）分类问题的一种统计分析方法。聚类分析起源于分类学，但是聚类不等于分类。聚类与分类的不同在于，聚类所要求划分的类是未知的[1]。 1.1 课题背景及意义
聚类分析的应用范围很广，常常应用于商业，生物，地理，保险行业，因特网和电子商务等领域。例如，在商业中，聚类分析既可以被用来发现不同的客户群，并且通过购买模式刻画不同的客户群的特征，也可用于研究消费者行为，寻找新的潜在市场、选择实验的市场，并作为多元分析的预处理；在生物领域，聚类分析被用来动植物分类和对基因进行分类，获取对种群固有结构的认识；在保险行业，聚类分析通过一个高的平均消费来鉴定汽车保险单持有者的分组，同时根据住宅类型，价值，地理位置来鉴定一个城市的房产分组等等。所以，研究聚类分析的相关算法对于我们以后在各个领域中解决问题显得十分必要。 1.2 聚类算法的种类
聚类算法可以视为：通过考虑包含在X中的所有可能划分集合的一小部分，就可以得到可判断聚类的方案，这个结果依赖于使用的算法和准则。因此，聚类算法是一个试图识别数据集合聚类的特殊性质的学习过程。聚类算法主要包括以下几种[2]。
（1）顺序算法（Sequential algorithm）：这些算法产生一个独立的聚类，它们是非常直接和快速的算法。这种算法的大多数都至少将所有特征向量使用一次或几次（一般不超过五六次），最后的结果依赖于向量参与算法的顺序。这种方法会产生致密和超球面或超椭圆面形状的聚类（取决于使用的距离度量）。
（2）层次聚类算法（Hierarchical clustering algorithm）：这种方法被进一步分为 1、合并算法（Agglomerative algorithm）。这些算法会在每一步产生减少聚类数量m的聚类序列，聚类生成的结果都来自于前一步的两个聚类的合并。合并算法的典型代表
毕 业 设 计 （ 论文 ） 第 2 页
是单一和完全连接算法。合并算法被进一步分为由矩阵理论得到的算法和由图形理论得到的算法，这些算法适用于长轴聚类（用单一链接算法）和致密聚类（用完全链接算法）。
2、分裂算法（Divisive algorithm）。这种算法的原理与合并算法的原理相反，在每一步产生增加聚类数量m的聚类序列。在每一步聚类产生的结果都是将前一步的一个聚类分裂成两个得到的。
（3）基于代价函数最优的聚类算法（Clustering algorithms based on cost function optimization）：这种方法用代价函数J来量化可判断性，通常聚类数量m是固定的。这种算法用微分学概念，通过最优J产生连续的聚类，当J的局部最优确定时，算法才结束。这种类型的算法也称为迭代函数最优方法，这类算法又可细分为
1、硬或脆聚类算法（Hard or crisp clustering algorithm）。其中一个向量绝对属于特定聚类。根据选择的最优准则，以最优分类将向量分到各个聚类中。这种类型中最著名的算法是Isodata或者Lloyd算法。
2、概率聚类算法（Probabilistic clustering algorithm）。它是硬聚类算法的特例，采用贝叶斯分类方法，并且每个向量x被分到使P(Ci|x)最大的聚类Ci中，通过适当地定义优化任务完成概率估计。
3、模糊聚类算法（Fuzzy clustering algorithm）。在这种算法中，向量属于超过特定阈值的聚类。
4、可能聚类算法（Possibilistic clustering algorithm）。在这种情况下，我们测量向量
x属于聚类Ci的可能性。
5、边界检测算法（Boundary detection aigorithm）。不同于用向量本身来确定聚类，这些算法迭代调整聚类的边界。这些算法虽然包括了代价函数优化原理，但它们与以上算法有本质的区别。前述所有算法使用聚类表达，目的是用最优方法来确定局部空间，相反地，边界检测算法则是寻找聚类间边界最优放置的方法。
（4）其他算法：最后一类包括一些特殊的聚类技术，这些技术不能归结到上述任何一类中。这些算法主要有分支和约束聚类算法（Branch and bound clustering algorithm）、遗传聚类算法（Genetic clustering algorithm）、随机松弛算法（Stochatic relaxation method）、竞争学习算法（Competitive learning algorithm）等。 1.3 可能聚类的数量
毕 业 设 计 （ 论文 ） 第 3 页
给定时间和资源，将集合X中的特征向量xi,i?1,…,N分到聚类中的最好方法是识别所有可能的划分，并根据事先确定的准则选择可判断的聚类。然而，对于中等N值这都是不可能的。令S(N,m)表示将N个向量聚类到m组的所有可能结果。由定义可能，聚类不可能是空的，很明显需要满足下列条件：
（1）S(N,1)?1 （2）S(N,N)?1
（3）S(N,m)?0，对于m > N
令LN?1表示N?1个向量分到k类的所有可能，其中k?m,m?1。第N个向量 （1）或者添加到LN?1的任一个成员的聚类中 （2）或者对LN?1的每个成员形成一个新聚类 因此可以得出
m?1mkS(N,m)?mS(N?1,m)?S(N?1,m?1) (1.1)
式（1.1）的解就是所谓的第二类的Stirling数量
1mm?i?m?NS(N,m)??(?1)??i (1.2)
m!i?0?i?显然，如果聚类固定，则这种计算是有效的。如果不是这种情况，则需要对所有可能的m值计算所有可能的聚类。由上面的分析可知，即使对于中等值N，评估所有的聚类来寻找最可判断的一个也是不现实的。例如，如果要评估100个对象分到5类的所有可能类聚，用计算机计算每个聚类要用10的聚类[2]。
?12秒，大约需10年之后才会得到最可判断
48 毕 业 设 计 （ 论文 ） 第 4 页
2 聚类算法Ⅰ：顺序算法
2.1 基本顺序算法方案描述
令d(x,C)表示从向量x到聚类C的距离（或不相似性），这种定义既考虑了C中所有的向量，也考虑了它的表达向量。这个算法方案需要用户定义参数的不相似性阈值?和允许的最大聚类数q。算法的基本思想如下：由于要考虑每个新向量，根据向量到已有聚类的距离，将它分配到一个已有聚类中，或者一个新生成的聚类中。设由算法生成的聚类数为m，那么这个算法方案可以描述如下[2]。
基本顺序算法方案（BSAS）
m?1
Cn?{x1}
FOR i?2 to N
--FindCk:d(xi,Ck)?min1?j?md(xi,Cj)
--If(d(xi,Ck)??)AND(m?q)then *m?m?1 *Cm?{xi} -- Else
*Ck?Ck?{xi}
*如果必要，更新向量表达 -- End{if}
End{For}
选择不同的d(x,C)会产生不同的算法。当C由一个单向量表达时，d(x,C)变为
d(x,C)?d(x,mC)
其中mC是C的表达。在以均值向量为表达的情况下，更新会以迭代形式出现，即
newmC?kold(nCnew?1)mC?xkknCnewk
其中nCnew是将x分到该聚类后Ck的势，mCk（mCk）是将x分到该聚类后Ck的
knewold 毕 业 设 计 （ 论文 ） 第 5 页
表达。
不难看出，这些向量在BSAS中的顺序非常重要。无论是聚类的数量还是聚类本身，不同的顺序会导致完全不同的聚类结果。
另一个影响聚类算法结果的重要因素是阈值?的选择，这个值直接影响由BSAS产生的聚类数量。如果?选得太小，会生成不必要的聚类：另一方面，如果?选得太大，则聚类的数量又会不够。在这两种情况下都不会生成最适合数据集的聚类数量。 2.2 聚类数的估计
本节介绍一种确定聚类数的简单方法，该方法适用于BSAS，也适用于其它算法，其聚类数不是输入参数。下面，BSAS(?)指具有给定不相似阈值?的BSAS算法。
FOR ?= a to b step c
--算法BSAS(?)执行s次，每一次都用不同的顺序表示数据。
--估计聚数类，m?作为从s次BSAS(?)算法得出来的最常出现的聚类数。 Next?
a值和b值是X的所有向量对的最小和最大不相似级别，即a?mini,j=1,…Nd(xi,xj)，
b?maxi,j=1,…Nd(xi,xj)。c的选择直接受d(x,C)的影响。s值越大，统计采样就越大，因
此，结果的精度就越高。接下来，画出聚类数m?与?的关系图。该图有一定数量的平坦区域。我们估计聚类数将对应最宽的平坦区域。至少对于分离性很好的致密聚类情况，这个聚类数是理想的。下面直观地解释这个参数。假设数据形成两个分离性很好的致密聚类C1和C2。C1(C2)的两个向量间的最大距离是r1(r2)，并且假设r1?r2。另r(?r2)是所有距离d(xi,xj)中的最小值，这里xi?C1，且xj?C2。很明显，对于??[r2,r?r2]，由BSAS得到的聚类数是2。另外，如果r??r2，区间很大，因此在?与m?关系图中对应着一个很宽的范围。
在上述过程中，隐含假设了特征向量确实能够组成聚类。如果不是这种情况，这种方法就没有用了。如果向量是致密聚类，但是分离得不好，这种方法给出的结果是不可靠的，因为?与m?的图中不可能包含宽的平坦区域。
在有些情况下，应该考虑在?与m?图中比较大的平坦区域对应的所有聚类数m?。例如，如果有三个聚类，前两个很近，而远离第三个，最平坦区域的聚类数可能是m?=2，