文档介绍：第二章 聚 类 分 析
2・4聚类的算法
聚类的技术方案
⑴ 简单聚类
根据相似性阈值和最小距离原则聚类
Vx 三0={ x , x ,…，x } = w uw ；
i 1 2 n 1 2 c
if D(x , m ) WT,
设待分类的模式特征矢量为国毘，…，心｝，鸳)表示第k次合并时的第g类。
基本思想
首先将"个模式视作各自成为一类，然后计算类与类之间的距离，选择距 离最小的一对合并成一个新类，计算在新产生的类别分划下各类之间的距离，再 将距离最近的两类合并，直至所有模式聚成两类为止。
算法步骤
⑴ 初始分类。令^ = °，每个模式自成一类，即即=｛瑞。=12…疋)。
(2)计算各类间的距离D&，生成一个对称的距离矩阵吐' = 碍，为类
的个数。
⑶ 找出前一步求得的矩阵刮引中的最小元素，设它是空炕和©炕间的距离, 将◎引和色灯两类合并成一类，于是产生新的聚类护◎巴…,令心険_1。
⑷检查类的个数。如果类数険大于2,令七二七+ 1，转至⑵；否则，停止。 如果某一循环中具有最小类间距离不止一个类对，则对应这些最小距离的类 可以同时合并。上述算法步骤给出了从"类至2类的完整聚类过程，
停止条件
•以类间距离门限f作为停止条件，即取距离门限八 当口⑻中最小阵元 大于尸时，聚类过程停止；
•以预定的类别数目作为停止条件，当类别合并过程中，类数等于预定值 时，聚类过程停止。
类间距离的定义与递推 在该算法中可以采用上节已详细介绍过的不同的类间距离定义方式，并使用 类间距离递推公式。所采用的类间距离定义不同，聚类过程及结果是不一样的。
上述算法在归并的每次迭代过程中，距离矩阵的最小元素值不断地改变，如果有
单调不减关系则称类间距离对并类具有单调性。最近距离法、最远距离法、平均 法及离差平方和法等定义的类间距离都具有这个性质，而重心法没有这个性质。
算法特点 聚类过程中类心不断地调整，但某一模式一旦分划到某一类中就不再改变。 从粗到细的层次聚类 这类技术的另一个算法和上述算法过程相反，依据类的离差平方和递推公式
按1类至"类进行谱系分解，这里不作介绍了。聚类过程可以表示成一个树图。
例：给出&个样本特征矢量如下，按最小距离原则进行聚类。
2（03iay 亍2 = （iscuoy 冠=（Moaiy
瓦二（1丄02盯 禺二〔32121）'耳=〔4丄1丄0丁
解：
⑴ 将每一样本看成自成一类
=[?i） G2（01 =国｝ *=区｝
G4（0）= ｛^｝ 6® = ｛耳｝ 二｛耳｝
计算距离矩阵川°'（表2-4-1）。
⑵ 中最小阵元为仮它是时）与时）之间的距离，将它们合并为一类,
得一新的分类为
甲=｛型烤卜区芯｝ 电Y
驾=胃】 鹉=Gf） 帶=G^'｝
计算合并后的距离矩阵刀⑴（表2-4-2）。在这里使用了距离递推公式，如 錯二mrn｛型与第）距离，酸）与第）距离｝
=mm 4^
⑶。⑴中距离最小者为胡，它是第）与&护间的距离，合并玄“和帶,得新的 分类
Gf）=驾 霽）=｛窣,身）｝
同样计算D⑵（表2-4-3），进一步聚类得
Gf）=｛Gf）,G^）｝ 蔚）二酸） 題=筒
即 G⑶=｛卫皿伽｝ 。驴=｛曲｝ 潸）=■［心那｝
计算D⑶（表2-4-4）。
⑷ 由表可知， 甫、囲'和型刃可以一起合并成一类。
表(2-4-1)
表(2-4-2) D⑴
<![endif]>
表(2-4-3)沪
表（2-4-4）。⑶
动态聚类法(Dynamic clus tering algorithm)
最大距离和层次聚类算法的一个共同特点是某个模式一旦划分到某一类之 后，在后继的算法过程中就不改变了，而
简单聚类算法中类心一旦选定后在后继 算法过程中也不再改变了，这类方法效果一般不会太理想。和上述各算法相对应 有一种动态聚类法。其要点为：
⑴ 确定模式和聚类的距离测度。当采用欧氏距离时，是计算此模式和该类中 心的欧氏距离；为能反映出类的模式分布结构，应采用马氏距离，设该类的均矢 为口，协方差阵为Z,贝U模式云和该类的距离平方为无与该类均矢口的马氏距离
宀优-口）迟丿任-山
⑵ 确定评估聚类质量的准则函数。
⑶ 确定模式分划及聚类合并或分裂的规贝。
动态聚类算法的基本步骤：
⑴ 建立初始聚类中心，进行初始聚类；
⑵ 计算模式和类的距离，调整模式的类别；
⑶ 计算各聚类的参数，删除、合并或分裂一些聚类；
⑷ 从初始聚类开始，运用迭代算法动态地改变模式的类别和聚类的中心使准
贝函数取得极值或设定的参数达到设计要求时停止。
动态聚类原理框图如下：
图 （2-4-3）
㈠c—均值法（匕一means）
条件及