毕 业 设 计 （ 论文 ） 第 6 页
次平坦区域的聚类数可能是m?= 3.如果放弃次平坦的区域，就会丢掉三个聚类的解决方法。
2.3 BSAS的改进
已经讲过，BSAS的基本思想是每个输入向量x被分配到已有聚类或新形成的聚类中。因此，对于x的分配是在最后的聚类形成之前决定的，而最后的聚类是在所有的向量都处理后才形成的。下面介绍克服了这个缺点的BSAS，称之为改进的BSAS（MBSAS），这种改进的代价是X的向量必须参与算法两次。算法包括两个阶段，第一阶段是将X的一些向量分配到聚类中来形成类；在第二阶段中，没有被分配的向量第二次参与算法，并分配到合适的类中。MBSAS具有形式如下。
聚类的确定
m?1
--For i = 2 to N
--Find Ck:d(xi,Ck)?min1≤j≤md(xi,Cj) --If(d(xi,Ck)??)AND(m < q)then *m = m+1 *Cm?{xi} --End｛if｝ End｛For｝ 模式分类 For i = 1to N
--如果xi没有分配到一个聚类中，那么 *Find Ck:d(xi,Ck)?min1≤j≤md(xi,Cj) *Ck?Ck?{xi}
*如果必要，更新向量表达 --End｛if｝ End｛For｝
聚类数在第一阶段确定，然后不许改变。因此，在第二阶段，对每个向量做决定时，
Cm?{x1} 毕 业 设 计 （ 论文 ） 第 7 页
都要考虑所有的聚类。
同BSAS情况一样，MBSAS也对向量参与算法的顺序敏感。另外，因为MBSAS在数据集X上执行两遍（每个阶段一遍），按预期，它的速度应该慢于BSAS。但是，它的时间复杂度应该与BSAS处在统一数量级上，用O(N)表示。
最后必须指出，在改进之后，当使用相似性测度时，也可以使用MBSAS。 2.4 改进阶段
在所有上述算法中，可能出现两个聚类的位置离得很近的情况，把它们合并成一类是最理想的。对这种情况。上述所有算法都无能为力。解决这种问题的方法是在上述过程结束后，执行下面的合并过程。
合并过程
找到Ci，Cj（i < j），使d(Ci,Cj)?mink,r?1,…,m,k≠rd(Ck,Cr) If d(Ci,Cj) ≤ M1 then
--把Ci，Cj合并为Ci，并删除Cj --更新Ci的聚类表达
--分别将聚类Cj?1,…,Cm命名为Cj,…,Cm?1 --m = m-1 --Go to（A） Else --Stop End｛If｝
M1是用户定义的参数，用来量化Ci和Cj两个聚类之间的接近程度。
顺序算法的另一个缺点是对向量表达顺序的敏感性。例如，使用BSAS时，x2被赋给第一个聚类C1，算法结束之后，形成4个聚类。可是x2有可能更接近不同于C1的另外一个聚类，然而，对于x2，一旦赋给一个聚类，就没有办法将它移到另一个离它更近的聚类。解决这个问题的最简单的办法是用下面的重分配过程：
重分配过程 For i = 1 to N
--找到Cj使得d(xi,Cj)?min1,…,md(xi,Ck)
毕 业 设 计 （ 论文 ） 第 8 页
--令b(i) = j End{For} For j = 1 to m
--令Cj?{xi?X:b(i)?j} --更新表达 End｛For｝
在这个过程中，b(i)指示离xi最近的聚类。这个过程可在算法结束后应用，如果需要合并过程，就要在合并过程结束之后使用。
毕 业 设 计 （ 论文 ） 第 9 页
3 聚类算法Ⅱ：层次算法
层次聚类算法与顺序聚类算法有所不同。具体地说，它不产生单一聚类，而是产生层次聚类。层次算法通常应用于社会科学和生物学等领域。另外，其它领域也会用到这种算法，包括现代生物学、医学和考古学。计算机科学与工程领域也经常应用层次聚类算法[2]。
在描述基本思想之前，假设X?{xi,i?1,…,N}是将要聚类的l维向量集。 层次聚类算法产生一个嵌套聚类的层次。更具体地说，这些算法包含N步，与数据向量的数量一样多。在第t步，要在前t-1步的聚类基础上生成新聚类。有两种不同的算法：合并和分裂层次算法。
合并算法中，初始聚类?0由N个聚类组成，每个聚类仅包含X中的一个元素。第一步生成聚类?1，它包含N-1个集合，如?1??2。重复此过程直到产生最后一个聚类
?N?1，它只包含一个单个的聚类集合，即数据集X。因而得到聚类的层次为
?0??1?…??N?1
分裂算法与合并算法的思路恰好相反。在这种算法中，初始聚类?0仅包括一个集合X。第一步产生聚类?1，它由?2个集合组成，如?1??2。重复此过程直到产生最后一个聚类?N?1，它包含N个集合，每个集合仅包含X中的一个元素，在这种情况下可得
?N?1??N?2?…??0
3.1 合并算法
令g(Ci,Cj)为所有可能的X聚类对的函数，此函数用于测量Ci和Cj之间的近邻性，用t表示当前聚类的层次级别。因此，通用合并方法为
通用合并方法 初始化
--选择?0?{Ci?{xi},i?1,…,N}作为初始聚类。 --令t = 0. 重复执行下列步骤： --t = t + 1
毕 业 设 计 （ 论文 ） 第 10 页
--在?1的所有可能聚类对(Cr,Cs)中找一组(Ci,Cj)，满足
??minr,sg(Cr,Cs),若g为不相似函数g(Ci,Cj)??
maxg(C,C),若g为相似函数 ?r,srs? --定义Cq?Ci?Cj并产生新聚类?t?(?t?1?{Ci,Cj})?{Cq}。 直到所有向量全被加入到单一聚类中。
很明显，采用此方法可以构造N个聚类的一个层次，每个聚类嵌套在它的后继聚类中，即对于t1?t2，t2 = 1，?，N-1，有?t1??t2。另外，如果两个向量一起加入t层次的同一聚类中，我们认为它们的后继聚类相同。这是检验嵌套性质的另一种方法。
嵌套性质的缺点是不能从一个“坏”聚类中恢复，“坏”聚类可能产生在更早的层次上。
在层次t上，有N-t个聚类。为了确定t+1层上要合并的聚类对，必须考虑
?N?t?(N?t)(N?t?1)个聚类对。这样，聚类过程总共要考虑的聚类对数量为 ???22???N?t?N?k?(N?1)N(N?1) ????????226t?0??k?1??N?1也就是说，整个合并算法的全部运算在N3数量级上。此外，算法的复杂度与g的定义有关。 3.1.1 最短距离法
最短距离法认为，只要两类的最小距离小于阈值，就将两类合并成一类。定义Di,j为
?i类中所有样品和?j类中所有样品间的最小距离，即
Di,j?min{dUV}
式中，dUV表示?i类中的样品U与?j类中的样品V之间的距离。若?j类是由?m，
?n两类合并而成的，则
Di,m?min{dUA}，U??i类，A??m类
Di,n?min{dUB}，U??i类，B??n类
递推可得
Di,j?min{Di,m,Di,n}