毕 业 设 计 （ 论文 ） 第 11 页
最短距离法的实现步骤如下 （1） 获得所有样品特征。
（2） 输入阈值T（计算所有样品距离的最大值与最小值，输出，作为阈值的参考）。 （3） 将所有样品各分一类，聚类中心数centerNum = 样品总数patternNum，
m_pattern(i).category = i；m_center(i).feature = m_pattern(i).feature。 （4） 对所有样品循环：
找到距离最近的两类pi、pj，设距离为minDis。
若minDis ? T，则合并pi、pj，将类号大的归入到类号小的类中，调整其他类保持类号连续。否则minDis > T，即两类间的最小距离大于阈值，则退出循环。
最短距离法的编程代码详见附录B。 3.1.2 最长距离法
在最长距离法中，两类中的所有样品间的距离必须都小于阈值，才能将两类合并。定义Di,j为?i类中所有样品和?j类中所有样品间的最大距离，则有
Di,j?max{dUV}
其中dUV表示?i类中的样品U与?j类中的样品V之间的距离。 若?j类是由?m，?n两类合并而成，则
Di,m?max{dUA}U??i类，A??m类，，
Di,n?max{dUB}U??i类，B??n类
递推可得
Di,j?max{Di,m,Di,n}
最长距离法的实现步骤如下 （1） 获得所有样品特征。
（2） 输入阈值T（计算所有样品距离的最大值与最小值，输出，作为阈值的参考）。 （3） 将所有样品各分一类，聚类中心数centerNum = 样品总数patternNum，
m_pattern(i).category = i；m_center(i).feature = m_pattern(i).feature。 （4） 对所有样品循环：
计算所有聚类中心间的距离，两类间的距离等于两类间样品的最大距离
毕 业 设 计 （ 论文 ） 第 12 页
maxDis。
取所有maxDis中的最小值。设pi类和pj类的距离最小，为minDis。 若minDis ? T，则将类号较大的类归入类号较小的类，重新排序类号，centerNum = centerNum-1.
否则minDis > T，即所有类间距离均大于阈值，则退出循环，归类完成。 最长距离法的编程代码详见附录B。 3.1.3 中间距离法
最短距离法和最长距离法采用的是分类距离的两个极端。中间距离法则介于两者之间，若?j类由?m，?n两类合并而成，则?i，?j两类的中间距离定义为
Di,j?Di,mn1212121?(Di,m?Di,n?Dm,n)2 （3.1） 224中间距离法的实现步骤如下 （1） 获得所有样品特征。
（2） 输入阈值T（计算所有样品距离的最大值与最小值，输出，作为阈值的参考）。 （3） 将所有样品各分一类，聚类中心数centerNum = 样品总数patternNum。
m_pattern(i).category = i；m_center(i).feature = m_pattern(i).feature。 （4） 建立距离矩阵centerDistance，记录各类之间的距离，初始值为各样品间的距
离。
（5） 对所有样品循环：
找到centerDistance中的最小值td = centerDistance(ti,tj)，即ti类和tj类距离最小。
若td < T，则将所有tj类成员归入ti类；centerNum = centerNum-1；重新顺序排列类号；根据式（3.1）重新计算距离矩阵centerDistance，否则（td?T）终止循环，分类结束。 中间距离法的编程代码详见附录B。 3.1.4 重心法
重心法的提出考虑了类中样品个数对类间距离的影响。设?j类由?m类和?n类合并而成，?m类有Nm个样品，?n类中有Nn个样品。则重心法定义类?i和类?j间的距离为
毕 业 设 计 （ 论文 ） 第 13 页
Di,j?Di,mn1NmNnNmNn222?(Di,m?Di,n?Dm,n)2 （3.2） Nm?NnNm?NnNm?Nn重心法的实现步骤如下 （1） 获得所有样品特征。
（2） 输入阈值T（计算所有样品距离的最大值与最小值，输出，作为阈值的参考）。 （3） 将所有样品各分一类，聚类中心数centerNum = 样品总数patternNum。
m_pattern(i).category = i；m_center(i).feature = m_pattern(i).feature。 （4） 建立距离矩阵centerDistance，记录各类之间的距离，初始值为各样品间的距
离。
（5） 对所有样品循环：
找到centerDistance中的最小值td = centerDistance(ti,tj)，即ti类和tj类距离最小（tj?ti）。
若td < T，则将所有tj类成员归入ti类；centerNum = centerNum-1；重新顺序排列类号；根据式（3.2）重新计算距离矩阵centerDistance，否则（td?T）终止循环，分类结束。 中间距离法的编程代码详见附录B。 3.1.5 类平均距离法
类平均距离的定义也考虑了样品的整体分布特性对其分类的影响。设?j类由?m类和?n类合并而成，?m类有Nm个样品，?n类中有Nn个样品，?i类中有Ni个样品。定义
Di,m为?i类和?m类间的平均距离，Di,n为?i类和?n类间的平均距离。则
Di,m1?(NiNm?‖X-X‖)im212
1Di,n?(NiNn?‖X-X‖)in212
递推可得
Di,j?Di,mn1NmNn222?(Di,m?Di,n) （3.3）
Nm?NnNm?Nn类平均距离法的实现步骤如下
毕 业 设 计 （ 论文 ） 第 14 页
（1） 获得所有样品特征。
（2） 输入阈值T（计算所有样品距离的最大值与最小值，输出，作为阈值的参考）。 （3） 将所有样品各分一类，聚类中心数centerNum = 样品总数patternNum。
m_pattern(i).category = i；m_center(i).feature = m_pattern(i).feature。 （4） 建立距离矩阵centerDistance，记录各类之间的距离，初始值为各样品间的距
离。
（5） 对所有样品循环：
找到centerDistance中的最小值td = centerDistance(ti,tj)，即ti类和tj类距离最小（tj?ti）。
若td < T，则将所有tj类成员归入ti类；centerNum = centerNum-1；重新顺序排列类号；根据式（3.3）重新计算距离矩阵centerDistance，否则（td?T）终止循环，分类结束。 类平均距离法的编程代码详见附录B。 3.2 分裂算法
分裂算法与合并算法的处理方式恰好相反。首先聚类包含单一集合X。在第一步，查找最好的划分，将该聚类分成两部分。最直接的方法是考虑所有2N?1?1种可能的划分，
然后根据指定的准则，选择最优的一种。这个过程重复应用于前一步生成的两个集合中的每一个集合，最后的聚类包含N个聚类，每一个聚类包含X中的单一向量。
下面正式地描述分裂算法。第t次聚类包含t+1个聚类，然后用Ctj表示第t次聚类
?t，t = 0，?，N-1，j = 1，?，t+1中的第j个聚类。令g(Ci,Cj)是所有可能聚类对定
义的不相似函数，初始聚类?0仅包含集合X，即C01 = X。为了确定下一个聚类，考虑X划分形成的所有可能的聚类对，选择使函数g取得最大值的聚类对（C11，C12）。这两个聚类形成下一个聚类?1，即?1= {C11，C12}。下一步考虑C11中所有的聚类对，仍然选择使用g取得最大值的聚类对，对C12重复相同的方法。假定从两个聚类对中得到
12了新的聚类对，而从C11中得到的聚类使g值最大，用（C11，C11）描述此聚类对。这样，12新聚类?2包括C11，C11和C12。分别用C21，C22，C23重新标记这些聚类，得到
?2?{C21,C22,C23}。用同样的方法可形成后续的所有聚类。通用的分裂方法描述如下：
毕 业 设 计 （ 论文 ） 第 15 页
通用的分裂法 初始化
--选择?0?{X}作为初始聚类。 --t = 0
重复执行下列步骤： --t = t+1 --For i = 1 to t
在由Ct?1,i划分形成的所有可能的聚类对(Cr,Cs)中，搜索使得g取最大值的聚类对(Ct1?1,i,Ct2?1,i)。 --Next i
--从上一步的t个聚类对中得到使g最大的聚类对(Ct1?1,j,Ct2?1,j)。 --形成新聚类t
?t?(?t?1?{Ct?1,j})?{Ct1?1,j,Ct2?1,j}
--重新标识聚类?t中的聚类。
直到每一个向量都在各自不同的聚类中。
选择不同的g将得到不同的算法。容易看出分裂方法的计算量很大，即使对于中等的N值也是如此。与合并算法比较，这是它的主要缺点。