所得到的分类由粗变细，逐渐归并，从而形成一个动态的聚类谱系图.由此可见，
分类对象集Z上的模糊等价关系的建立是这种聚类分析方法中的一个关键性的
环节[9]。
为了建立分类对象集合X上的模糊等价关系瓦，通常需要首先计算各个分类
对象之间的相似性统计量，建立分类对象集合I上的模糊相似关系= k]， ?、 L IJ Jfjxn
0 象的相似性统计量的方法有如下几种[9]。 1.夹角余弦法 ■S 广’ J =广'. (2-11) V k=\\ k=\\ 2.数量积法 '1 i = j r,j = ‘ 1 (2-12) Mtl I* ] 这里，M是一个适当选取的正数，并且满足 M > max|^X丨k(2-13) 3.相关系数法 11 笫2苹聚类分析及;用实例 即合成的传递闭包： 巧==充。瓦.，R:=R^or；,?? 这样下去，就必然存在一个自然数I使得巧* = R'。紀?这时，^便是一个模糊 等价关系了.在此基础上，我们就可以利用不同水平下的截集得到该水平上的聚类 结果，所有不同水平的聚类结果形成聚类的谱系图[9]。 2. 2. 3图论聚类方法 图论聚类方法最早是由Zahn提出来的，又称作最大（小）支撑树聚类算法. 后来经过人们加以改造从而可以实现模糊聚类分析.图G中一条长度为尺的路径 (Path ) P是一系列连接的结点，P =々x,，X2，\〆，其中对 V/ e (0,Ar),(x,,x,+|)e E ；如果图G中没有一条非零长度的路径P = , 且X, =Xh,，则称图G不包含环（Cycle);图G的支撑树〈]是指由连接所有结点的 ?-1条边构成的无环图pr，r].显然，一个图中当且仅当任意两对结点之间 只有一条路径时才是树，通常在一个图G中可以构造多个支撑树[1,7；如 果我们给图中每条边e赋以权值，那么所谓的最小支撑树（Minimum Spanning Tree, MST)是指满足下列条件的支撑树： w(MST ) = minj^ w(e)| 对于一棵树如果移去一条边e,则生成两组连通的结点jc又和 A=X-A,我们定义y为共环边⑼， 0\ (2-26) 也就是说，f为图[X,G]中连接两组节点J和：？的一组边；森林是指不包含 环的非联通图，其中的每一个联通的部分被称为一棵树。 下面的定理给出了构造最小支撑树的充分必要条件.即：是图G的最小支撑 树的充分必要条件是，对于所有的边其共环边y满足 14 第2帝聚类分析及其应用实例 \ = e '=丨 (2'21) 10.绝对值倒数法 '1 i = j r =——M (2-22) y s 3?I i* j .i=l 这里，M是一个适当选取的数，使得SI. 在实际应用中，由于所获取的分类对象的数据比较复杂，往往不是[0,1]区间中 的数，因此首先需要把各个原始数据标准化.假设被分类的对象一共有n个，对于 每一维特征Xt共有〇个原始数据，设为x;\”?，x:p把它们叫做这一特征的各 个元素.为了把这些数据标准化，首先计算每一维特征的均值和方差[iG]: ^=-1? ‘ (2-23) H /=1 n /=1 下式（2.24)是求数据标准化值X；；的公式 X： (2-24) Sk 对上式（2.24)求出的值进行极值标准化，就能确保所有被标准化为[0，1]闭区间内 的值，极值标准化公式为： ?5 -:?“ (2-25) max 工 Amin 上式中，是指x;;，x丨” 中的最大值，而指最小值- 得到待分类对象集X上定义的模糊相似性关系足后，还要进一步改造成为模 糊等价关系足由前面有关模糊关系的介绍可知，模糊相似性关系足.满足自反性 和对称性，但一般而言并不满足传递性，也就是说，它并不是模糊等价关系.因此， 为了聚类我们必须采用传递闭包的性质，将这种模糊相似性关系足改造为模糊等 价关系民[9〗。 13 第2韋聚类分析及jl;应用实例 6\￠^), w{e) < w{s), s ^ 0'人s * e). 在传统的图论聚类分析，首先把待分类的对象X = ^[xi，x2,?，〃看作一 个全连接的无向图G = 中的结点，然后给每一条边赋以权值，比如我们可以 用任意两个结点(X,, Xj)在特征空间的汉明距离定义边e丨J (1 < /，j < n)的权值为 w{e,j) = ||x, - Xj II, x,,xj e X 然后，我们再对该组对象进行聚类分析，其具体步骤再次就不多讲. 下面，我们主要介绍模糊最大支撑树算法的具体步骤 步骤一：建立分类对象集上的模糊相似关系，构造模糊图： (1)计算各个分类对象之间的相似性统计量r\= l,2,?，n ,建立分类对象集 Z上的模糊相似关系瓦=h]； ‘、 L tj (2)将^^表示成由〇个结点所构成的模糊图6二|^，五1，使G中的任意两个结点 与Xj之间都有一条边相连接，且赋该边的权值为r,j. 步骤二：构造模糊图G上的最大模糊支撑树： ；：' (1)找出图G中最大权值的边?； (2)将存放在集合C中，将边上的新结点放入集合r中，若r中已含有所有 ?个结点时，转至（4); (3)检查r中每个结点与r外的结点组成的边的权值，找出其中最大者转至 (2)； (4)结束，此时G中的边就构成了 G的最大模糊支撑树!；?. 步骤三：由最大模糊支撑树进行聚类分析：选择某一个〇值对炎,=j作截集， 将r■中小于〇的边断开，使相连的各结点构成一类，当a由1下降到0 时，所得到的分类由细变粗，各结点所代表的分类对象逐渐归并，从而 形成一个动态聚类谱系图.