第七章模糊聚类的有效性

第七章模糊聚类的有效性第七章模糊聚类的有效性#空间维数卩=4.00.560.910.940.960.98卩=32.00.920.940.970.980.98空间维数卩=4.00.560.910.940.960.98卩=32.00.920.940.970.980.98表7.4.3和7.4.4的数据表明，在半数框架制约下统计量T对多峰模式集可以建立较高的B功效检验，也就是说可以较好的区分单峰和多峰模式。另外，对于固定点数n的集合，聚类趋势检验的效随着d和卩的增加而变大，随着◎的增加而变小，这是因为当n固定，空间维数越高，类间相对距离就越大，聚类趋势变显著，而卩的增加意味着类内点数增加，聚类的个数减少，换句话说，类间趋向于良好分开。◎是类内分散程度的标志，◎变大说明类与类间越来越可能交叉重迭，以致于聚类现象完全消失，因而效的变小就是自然的。因为聚类分析通常是在高维空间中进行的，所以，效随空间维数增加而变大的性质对于聚类趋势的检验有利。因为聚类趋势检验的任务在于把那些不具有聚类结构的数据集除去，所以效随◎增加而变小的性质亦是我们所需要的。表7.4.4在d=5条件下对多峰模式的功效检验0.00.0250.050.0750.100.00.0250.050.0750.100.1250.15卩=4.01.00.980・960.950.910.740.45卩=32.01.00.980.960.950.92卩=32.0综上所述，半数框架制约下的T-平方统计量检验对于空间均匀分布的模式可以建立可信的检验基础，而对于单一Gauss模式的极低功效检验，使得关于随机模式的概念在聚类趋势检验的意义上可以溶均匀分布模式和Gauss模式于一体，从而拓宽了零假设的范围。同时，该方法对多峰模式极高的功效检验又使其完全可以用于聚类趋势的检验中。半数框架的应用，使关于模式可聚性检验，既避开了抽样始点设置对抽样窗口的要求，也消除了由于窗口设置而造成的边界对近邻距离分布规律的影响，因而是一个很有前途的方法。§4.4基于MonteCarlo和统计检验的模糊聚类新方法三、基于MonteCarlo和统计检验的模糊聚类新方法聚类分析是无监督的类分技术，事先没有任何有关数据集的先验知识，包括它的分布和类别数，因此应该是一种机器自动学习方法。通过对数据分布特性的分析，自动给出模式集是否具有类分性，如果可分，自动确定如何分类以及分为几类合适等问题。把多峰分布模式的数据集全部分解成单峰分布的模式类，最后根据类间的相近信息进行模式类的合并，获得数据集的多分辨表示，为用户提供多层次的信息，以帮助决策。由前一节的分析可知结合半数框架的T-平方抽样的统计量T,可有效的进行单峰模式的B假设检验。因此，本节中我们将用该统计检验方法进行聚类趋势和聚类有效性的判定，即分别对模式集X和聚类分析得到的各个模式子集S(i二1,2,…c)进行单峰检验，以此来指导聚i类分析，构造一种可同时进行聚类趋势检验、聚类分析和聚类有效性判定的模式综合分析自动机，如图7.4.8所示，以补偿现有聚类算法的功能单一所导致的无效操作。以下，分别介绍各模块的工作原理及相关的算法。合理分类输出合理分类输出图7.4.8结合聚类趋势、聚类分析和有效性判定的模式分析自动机1.基于k-近邻T-平方统计量T的单峰检验k对于一个给定的无标定模式集，如图7.4.8给出的模式分析自动机首先进行单峰分布的统计检验，以确定该模式集是否具有类分性，即聚类趋势检验。这里借用前面介绍的半数框架下的T-平方统计检验方法，统计量T的假设检验基于抽样点与模式间的最近邻(NN)信息，B不过，NN模式的选取存在随机性太强而统计性较差的问题。为了抽取鲁棒性较好的检验统计量，我们把NN模式间的距离替换为k-NN模式间的距离，把寻找最近邻模式转化为寻找k个近邻模式集，大大降低了模式出现的随机性，从而使所得到的统计量更稳定。这样以来，统计量T就被推广为k-NN的统计量T，Bk1券Ud(i)T=——Zk(7104)TOC\o"1-5"\h\zkMUd(i)+0.5Vd(i)'•丿i=1kk其中U(i)为抽样始点O到它的k-NN模式P的距离，而V(i)则为模式P与其k-NN模式Pk1k12间的距离。显然，统计量T为统计量T在k=1时的特例。仍借助前一节介绍的半数框架建Bk立抽样窗口，还利用MonteCarlo的方法进行*-显著性检验，这两个算法在此不在赘述。在对给定的无标定模式集进行*-显著性检验后，获得检验大小Size,然后按如下规则作出判决：如果Size与*相比拟，则模式集为单峰模式，否则，模式集有聚类趋势。2．聚类有效性判定方法在获知模式集X具有可分性后，首先令c=2，用现有的聚类算法(如FCM算法)获得X的c-划分。这里要求算法要收敛到最优解，否则将影响后续工作。而FCM类型的的聚类算法对初始化敏感，容易陷入局部极值点而得不到最优的分类结果。为此，我们可以利用第

三章中给出的基于形态学和图象描述技术的初始化方法来保证全局收敛，或者借助进化计算的方法进行全局优化。具体哪种方法可根据实际需要合理选取。得到模式集X在给定聚类数c条件下的最佳模式划分后，对c个子集S,S,,S分别12c做单峰分布的Q-显著性检验，只要还有一个子集不满足显著性检验，则说明仍存在可分性，•••令c=c+1重新聚类划分，直到所有c个子集均不具有类可分性后，则说明数据集X分布的峰态已经分解完全，每个聚类均为单峰分布模式了，则转入聚类后处理。3．聚类分析的后处理后处理主要是考虑到聚类的无监督性，为了满足不同的应用场合，为后续决策提供更多的信息，利用最小生成树技术进行聚类合并，然后给出一个不同水平上类分的谱系图，也就是说给出特征空间中模式矢量集的多分辨表示。当然最细微层次上的聚类即为上面得到的数据集X完全分解的结果，最粗略的层次上的聚类为整个模式集X聚合为一类。数据集的类分谱系图的建立要按如下步骤进行：(1)(2)在聚类分析中获得的c个聚类中心P=｛p,p,,p｝上构造最小生成树，其边的(1)(2)12c权值即为节点间的欧氏距离w=lip-pI；ijij分析最小生成树的权值｛w..｝，逐步在不同水平丫上删除满足条件的边集ijwewe'wijw＜丫丿，合并每条边连接的两个类；ij(3)构造新的最小生成树，重复步骤(2)的操作，直至合并成一个类，最后输出类分谱系(3)图。整个模式分析自动机就包括上述三大模块，即数据集的单峰模式检验、数据子集单峰模式检验指导的聚类分析和聚类后处理，可同时考察给定模式集的聚类趋势、聚类分析的有效性，并由此指导聚类算法把数据集完全分解为单峰分布的子集，最后通过后处理获得数据集的类分谱系图。整个流程如图4-4.1所示的框图，输入一组模式集，先判断其聚类趋势，如果可分便输出数据集类分的谱系图，实现简单，过程自动，避免了人为的干预，使聚类分析真正成为一种机器自动学习算法。§4.5实验结果与分析四、实验结果分析大量的实验结果表明本章提出的模式分析自动机能够合理有效地分析所给的空间数据集，并为后续工作提供不同层次的类分信息，使人们更清楚地认识待分析模式间的亲疏关系、分布形态和内在结构，整个过程自动执行，无须人为干预，为生产自动化提供了条件。本节中，我们将选择三个不同类型的实验结果来说明该方法的有效性。

00.200.20.40.60.8100.20.40.60.81(a)空间均匀分布的测试样本集(b)半数框架制约下的T-平方抽样图7.4.9用本章方法对空间均匀分布模式集的统计检验实验实验一：为了说明半数框架制约下T-平方统计量能够对空间均匀分布的模式集建立可信的检验，我们用空间Poisson过程产生如图7.4.9(a)所示的均匀分布的样本集，用半数框架算法设置如图7.4.9(b沖所示的抽样窗口(在图中用大圆表示)，在抽样域内设置M=10个抽样始点O(在图中用“•”表示)并按T-平方抽样原理得到最近邻模式匚,P2(图中分别用叠加在“X”上的“O”和“△”表示)，然后按公式计算统计量T，对以上的MonteCarlo试验重复100B次获得如图7.4.10的统计数据。(a)MonteCarlo试验得到的统计量的值(b)试验中统计量取值的统计直方图图7.4.10100次MonteCarlo试验所得到的T-平方统计量的统计数据图7.4.10(a)所示为100次MonteCarlo试验中所得到的T-平方统计量的值，如果取显著性水平0.05，则从标准正态分布函数可得临界值T二1.64484，从图中可很明显地看出大a于T的试验只有4次，因此检验大小为Size二0.04获得了合理的第一类错误概率的估计。图a(b)显示了100试验中T-平方统计量的统计直方图，其中虚线为标准正态分布曲线，可见在空间Poisson过程的条件下，T-平方统计量良好的遵循正态分布。实验结果与前面的理论分析获得了较好的一致性，也证实了方法的有效性。

(a)c=2时IRIS(a)c=2时IRIS数据的分类情况(b)c=3时IRIS数据的分类情况图7.4.11用实测数据的测试实验(图中显示的IRIS数据的1,2,4维特征)实验二：为了验证本章提出的单峰统计检验方法的有效性，我们选择了著名的IRIS实测数据作为测试样本，关于IRIS数据的情况在第二章中有详细说明，它包括三类共150个四维模式，每类50个样本，其样本分布情况如图7.4.11所示。用本章提出的模式分析自动机对类别数为c=1,2,3的条件下，分别进行Q=0.05,0.01的显著性检验，得到表7.4.5的结果。表7.4.5IRIS实测数据集的a-显著性检验的检验大小类别数c类别数c12a二0.050.78(0.03,0.57)a二0.010.59(0.02,0.44)3(0.03,0.05,0.07)(0.02,0.02,0.03)从表中可以看出，IRIS数据集具有明显的聚类趋势，于是令c=2用FCM算法进行数据划分，去模糊后得到图7.4.11(a)所示的分类结果，对得到的两类子集分别进行单峰检验后得知,有一个子集已经为单峰模式了，但另一个子集仍具有聚类趋势，然后令c=3再用FCM算法划分，划分的结果显示在图7.4.11(b)中，对每个子集的检验结果表明，三个子集均无聚类趋势,因此算法结束，最终得到合理的分类数(c=3)和分类结果。实验三：为了证实本章提出的模式分析自动机全面分析模式、提供多层次辅助决策信息的能力，我们用模拟数据设计了实验三。.X(a)二维空间中人造测试样本集(b)峰态分解完全后所得到分类结果0

.X(a)二维空间中人造测试样本集(b)峰态分解完全后所得到分类结果0图7.4.12用人造测试样本集对模式分析自动机的测试实验图7.4.12(a)所示为一组仿真数据集，包含二维平面上的300个模式，模式分析自动机对这组数据的分析表明：该数据集具有聚类趋势，因为其单峰a-显著性检验的大小远大于d(实验中取a=0.05)。于是，算法从c=2开始进行聚类分析，并对所得到的每个聚类分别进行单峰检验，不满足检验则令c=c+1重新聚类，直到c=6时，所得到的子集才全部通过a-显著性检验，分类结果如图7.4.12(b)所示，此时各个聚类皆为单峰分布的子集。表7.4.6在不同参数c,k条件下各子集统计检验中最大的第一类错误聚类数c1234561999747948992100655910099531008181991009410010010010010005100961001001002表7.4.6给出了不同分类数c和不同k值条件下,各个聚类进行T统计检验中得到的第一类错误的最大值，即为最大检验大小maxc《ize(S)},其中M=10，k取1到5。不同ki=1i值的T统计检验结果均表明：直到c取6时各类才均满足a-显著性检验，而对应于不同k值k的检验大小又反映出在k=1时，即统计量T的检验大小不很稳定，k=4时则较为理想。因B此，选择适当的k值，则更有利于模式分析的效果。得到样本集的c-划分后，模式分析自动机进行聚类的后处理，在不同水平上合并聚类,以输出样本类分的谱系图。首先，以所得到的六个聚类中心为节点，构造图7.4.13(a)所示的最小生成树，其中边权值为节点间的距离，节点上的数值1-6表示聚类的序号，