第七章模糊聚类分析

一、模糊聚类分析聚类分析：按照一定要求和原则对事物进行分类。聚类：普通分类——清晰事物模糊分类——带有模糊性的事物三种模糊聚类方法：传递闭包法——基于模糊等价关系；直接聚类法——基于模糊相似关系；模糊聚类法——基于模糊划分.二、模糊聚类分析的步骤1.选取特征指标特征要有明确的意义，要有较强的分辨力，有代表性，并确定描述特征的变量。分类事物的特征指标选择的如何，对分类结果有直接的影响。2.数据标准化（正规化）(1,2,,)iixxxin令其中，xi为原始数据；11niixxn是原始数据的均值；是原始数据的标准差；211()1niixxn是数据处理后的数据。ix3.标定设12,,,nuuu为待分类的对象，uj有m个刻划其特征的数据，就是根据实际情况，按一个准则或某一种方法，给论域U中的元素两两之间都赋以区间[0,1]内的一个数，叫做相似系数。它的大小表征两个元素彼此接近或相似的程度。12,,,mjjjxxx，然后对于ui与uj，用rij表示ui与uj的01,1ijiirr当rij＝0时，表示ui与uj截然不同；当rij＝1时，表示ui与uj可以等同(不能说是完全相同);rij可根据具体问题来选取。方法有：的相似程度，要求（1）数量积法11,1,mijikjkkijrxxijM1maxmikjkijkMxx，其中显然0,1ijr．如果rij中出现负值，可采用下面方法将全体rij进行重新调整．方法1令12ijijrr0,1ijr()ijijrmrijMmmin,ijijmrmax,ijijMr0,1.ijr，则方法2令其中于是（2）夹角余弦法12211,mikjkkijmmikjkkkxxrxx如果rij中出现负值，也可采用上面方法调整．（3）相关系数法12211()(),()()mikijkjkijmmikijkjkkxxxxrxxxx1111,.mmiikjjkkkxxxxmm其中（4）最大最小法（5）算术平均最小法11().()mikjkkijmikjkkxxrxx112().()mikjkkijmikjkkxxrxx（6）几何平均最小法11()(,0).mikjkkijikjkmikjkkxxrxxxx（8）指数相似系数法21expikjkijkxxrms其中sk适当选择.（9）绝对值倒数法11,,,ijmikjkkijMrijxxM适当选取使rij在[0,1]中且分散开（7）绝对值指数法1expmijikjkkrxx（11）非参数法,,ikikijkjkjxxxxxx1122,,,ijijimjmnxxxxxx中正数个数，1122,,,ijijimjmnxxxxxx中负数个数，1(1)2ijnnrnn令则（10）绝对值减数法11mijikjkkrcxx（12）贴近度法如果特征,[0,1](1,2,,),ikjkxxkm则ui,uj可看作模糊向量1212(,,,),(,,,)iiiimjjjjmuxxxuxxx,以它们的贴近度D(ui,uj)为其相似程度.i)格贴近度1,(,),ijijijrDuuij11(,)()1()mmijikjkikjkkkDuuxxxx,其中ii)距离贴近度1(,),ijijrcduu其中c,a为适当选择参数值，d(ui,uj)为模糊集各种距离.iii)算术平均最小贴近度1112()(,).mikjkkijijmmikjkkkxxrDuuxx（13）主观评定法请有实际经验者直接对ui，uj的相似程度评分，作为rij的值.通过标定求出相似系数后，便可得到以rij为元素的模糊相似矩阵R(rij).4.聚类选择一种合适的聚类方法，便可得到分类结果.三、传递闭包法1.传递闭包法根据标定所得模糊矩阵R，求出其传递闭包(),()tRRtR为模糊等价矩阵，对[0,1]，令λ从1降到0得到R，根据R进行分类：1ijijruu与归为一类.2.最佳阈值λ的选取聚类图给出各λ值对应的分类，形成一种动态聚类，便于全面了解元素聚类，然后根据实际需要选择其阈值λ，便可确定元素的一种分类，至于如何选择阈值λ，使分类更加合理，除了凭经验外，还可用F-统计量来选取.F-统计量：12{,,,}nUuuu为待分类事物的全体，12(,,,)jjjjmuxxx设xjk为描述元素uj第k个特征的数据(1,2,,)km.设c为对应于λ值的类数，ni为第i类元素的个数，第i类元素记为12,,,,iiiinuuu记11(1,2,,)inikjkjixxkmn为第i类元素的第k个特征的平均值,而称12(,,,)iiiimuxxx为第i类的聚类中心向量；12(,,,)muxxx为全体元素的中心向量，而11(1,2,,)nkjkjxxkmn于是，称21211||||(1)||||()iiciiiincjijnuucFuunc为F-统计量，其中||||iuu为第i类中元素iju与中心iu的距离.可见，F-统计量的分子表征类与类间的距离，分母表征类内元素间的距离.因此，F值越大，说明分类越合理，与此分类相对应的F-统计量最大的阈值λ为最佳值.求传递闭包的简便方法设()ijnnAa为模糊相似矩阵，求t(A).(1)求12maxjjna,假定112maxmjjnaa,把A中的a1m,am1,a11,amm用圆圈圈起来，并记*11,mmmmmxaaa(2)在A中第一行、第m行中剩下的元素中找最大元素*2x,即*21,;1,maxijimjmxa.且设*2x在第p列.用**122,mmmaxax即分别代替a1p与amp以及它们的对称元素，最后用圆圈将它们及圈起来.ppa(3)假定A中有圈的k行(1,2,,1)kn是12(1),,,kiii行.而*1kx所在的列是ij列，在这些行中剩下的元素中找最大元1212*,,,,,,max()kkkijiiiijiiixa并设在第l行，用*kx12***,,,jjkjiikiikiikaxaxax分别代替12,,,kilililaaa继续此过程，到k=n-1,得到t(A).还有逐步平方法：及其对称矩阵，并把all圈起来112422222kkkkkRRRRRRRtRR计算，直至出现，则2R四、基于模糊相似关系的直接聚类法1.最大树法聚类原则是：ui与uj在λ水平同类当且仅当在相似矩阵R的图中，存在一条权重不低于λ的路联结ui与uj.(1)画出以被分类元素为结点，以相似矩阵R的元素rij为权重的一颗最大树；(2)取定，砍断权重低于λ的枝，得到一个不连通图，各连通分支变构成了在λ水平上的分类.0,12.编网法对给定的模糊相似矩阵R，取定水平0,1,作截矩阵Rλ，在Rλ的主对角线上填入元素的符号，在对角线下方以结点号“*”代替1，而“0”则略去不写，由结点向主对角线上引经线和纬线，称之为编网，通过经线和纬线能互相连接起来的元素，属于同类，从而实现了分类.五、基于模糊划分的模糊聚类法1.c-划分(1)普通c-划分如果划分把普通集合分成c类，则此划分就叫普通c-划分，即：若设12,,,,njUuuuu的特征可表为12(,,,)jjjjmuxxx，那么U的普通c-划分是指U的c个子集1,2,,(2)iAiccn满足:(1)1;ciiAU(2)()ijAAij121112112212221212nnnccccnuuuAaaaAAaaaAaaac1,()0,()jijijjijuAuiauAui属于第类不属于第类其中且满足(1)(2)1,1cijija(表示每个uj必属于且仅属于一类)；1,01nijjia(表示每类Ai至少有一个元素)；反过来，任一满足条件(1)、(2)、(3)的矩阵对应着U的一个分类.(1)(2)(3)这样的分类结果可以用一个c×n矩阵(称为c-划分)来表示.例如，设U={u1,u2,u3,u4},若分类结果为{u1},{u2,u3},{u4},则对应的分类矩阵为123100010110200013nuuuu如果分类矩阵为100001100001则对应着U的分类为{u1},{u2,u3},{u4}.记V为c×n实矩阵的集合，且11(),0,1,1,0cncijcnijijijijMAAaaaanV显然，对于给定的U及分类数c，类的分法不是唯一的.Mc包含了U的所有可能c类划分的结果，Mc称为将U分成c类的分类空间.这样的分类是通常的分类，称为硬分类.(2)模糊c-划分12,,,,nUuuu12(,,,)jjjjmuxxx设,一个c×n模糊矩阵1112122122212nnccccnAaaaAaaaAAaaa若满足(1)(2)1,1cijija(表示每个uj属于c个模糊子集Ai的程度总和为1)；1,01nijjia(表示每类Ai不等于空集或U)；则称A称为U的模糊c-划分矩阵.记11(),[0,1],1,0cnfcijcnijijijijMAAaaaanMMfc称为U的c类软分类空间.显然.cfcMM若将Mc和Mfc定义中的条件：10()nijjani10()nijjani放宽为则这样的分类空间分别称为退化的硬分类空间和退化的软分类空间.分别记为Mco和Mfco,显然.cofcoMM2.目标函数聚类法和硬c-均值算法划分(1)目标函数法目标函数是对给定的c的所有候选类进行度量，最优的类就是使目标函数达到局部最小值的类.对于硬分类情形，通常所选取的目标函数是总体组内误差平方和，其定义为211(,)||||cnijjiijJAVauv这里将每类Ai中元素各特征分别取平均值，所得的聚类中心向量记为vi，也称为Ai的聚类中心.由于Ai类中元素个数1niijjna1nijjjau,Ai类中元素向量和为,因此聚类中心向量11nniijjijjjvaua记11112121112112mmccccmvvvvvvvvVvvvvV称为聚类中心矩阵.若jiuA,则uj到聚类中心vi的距离为21||||()mijjijkikkduvxvAi中全体元素到中心距离平方和为21()nijijjad而V中所有元素到其所在类中心距离平方和为221111(,)()||||cncnijijijjiijijJAVadauv最理想的c-划分显然是使J(A,V)取极小的A.(2)硬c-均值算法步骤1：假设给出n个数据点12{,,,}nUuuu12(,,,)mjjjjmuxxxR,其中.取定(2),ccn并初始化(0)cAM步骤2：当迭代次数为(0,1,2,)ll时,计算聚类中心向量()()()11nnllliijjijjjvaua()()1,2,,.llijaAic其中,步骤3：用下式将A(l)更新为(1)(1)llijAa()()(1)11,||||min(||||)0,lljijklkcijuvuva其它步骤4：比