应该聚类的最大树法

用图形来进行直接聚类，更为方便。

任意点间都有通道的图形为连通图。起点与终点重合的链称为回路，无回路的连通图称为树（见图7.6.8）。

图7.6.8　通道与链

用图形法来进行直接聚类时，是把相似类归并为关于的等价类。归并时，使阈值λ逐步从大到小，依次把强度为λ的边连接有关的顶点，但注意不连回路，也就得到若干边的强度为λ的通道。对λ∈［0，1］，在不同λ水平上将若干通道相连，就得到若干互不相连的树。每棵树中任意两顶点间通道的强度大于等于λ，这些互不相连的树就给出了分类的结果：同一棵树的顶点归于同一类。λ从大到小，直至得到最大的树的过程，给出论域X中元素的一个动态分类结果。

例7.6.12　用最大树法对例7.6.11直接聚类。

λ=1时的图形如图7.6.9所示，对应的分类为｛x1，x4，x5，x7｝，｛x2｝，｛x3｝，｛x6｝。

图7.6.9　λ=1时的连通图

λ=0.8时的图形如图7.6.10所示，对应的分类为｛x1，x4，x5，x7｝，｛x2，x6｝，｛x3｝。

图7.6.10　λ=0.8时的连通图

λ=0.7时的图形如图7.6.11所示，对应的分类为｛x1，x4，x5，x7｝，｛x2，x3，x6｝。(www.xing528.com)

图7.6.11　λ=0.7时的连通图

λ=0.5时的图形如图7.6.12所示，是最大树，对应的分类为｛x1，x2，x3，x4，x5，x6，x7｝。

图7.6.12　最大树（例7.6.12）

从最大树图中可以看出，若去掉那些强度大于λ的边，就把最大树截成互不相连的几棵子树，这就是对应λ水平上的一种分类结果，同一棵树上的顶点属于同一等价类。

例7.6.13　用直接法求例7.6.10给出的相似矩阵的等价类，并作出最大树图。

直接从模糊相似矩阵来求等价类并作最大树图，先选x1作顶点，并选λ=1，此时知相似类为R1［x1］=｛x1，x6｝，R1［x2］=｛x2，x4，x7｝，R1［x3］=｛x3｝，R1［x5］=｛x5｝，各相似类不相交，所以上述相似类即等价类。

其次令λ=0.9，则从可知R0.9［x2］=｛x2，x4，x6｝，由于R0.9［x2］与R1［x1］及R1［x2］都相交，于是可以归并成P1［x1］=｛x1，x2，x4，x6，x7｝，此外还有R0.9［x3］=｛x3｝，R0.9［x5］=｛x5｝。此时的等价类就是P1（x1），R0.9［x3］，R0.9［x5］，即有｛x1，x2，x4，x6，x7｝，｛x3｝，｛x5｝。再令λ=0.8，易知R0.8［x5］=｛x1，x5，x6｝。它与P1［x1］相交可合并成P2（x1）=｛x1，x2，x4，x5，x6，x7｝，此外还有R0.8［x3］=｛x3｝。此时的等价类就是｛x1，x2，x4，x5，x6，x7｝，｛x3｝。

当λ=0.7时，因R0.7［x3］=｛x32，x4｝已与P2（x1）相交，所以全部元素为一类。

上述过程作出的最大树如图7.6.13所示。

图7.6.13　最大树（例7.6.13）