第七章模糊聚类分析课件.ppt

1、(1,2, )iixxxin11niixxn是原始数据的均值；是原始数据的标准差；211()1niixxn是数据处理后的数据。ix设12,nu uu为待分类的对象，uj有m个刻划其特征的数据，12,mjjjxxx，然后对于 ui与 uj ，用 rij 表示 ui 与 uj 的01,1ijiirr当rij0时，表示ui与uj截然不同；当rij1时，表示ui与uj可以等同(不能说是完全相同);rij可根据具体问题来选取。方法有：的相似程度，要求（1）数量积法）数量积法11,1,mijikjkkijrx xijM1maxmikjkijkMx x，其中显然0,1ijr 如果 rij 中出现负值，可采用

2、下面方法将全体 rij 进行重新调整方法1 令12ijijrr0,1ijr()ijijrmrijMmmin,ijijmrmax,ijijMr0,1 .ijr，则方法2 令其中于是（2）夹角余弦法）夹角余弦法12211,mikjkkijmmikjkkkx xrxx如果rij中出现负值，也可采用上面方法调整（3）相关系数法）相关系数法12211()(),()()mikijkjkijmmikijkjkkxxxxrxxxx1111,.mmiikjjkkkxxxxmm其中（4）最大最小法）最大最小法（5）算术平均最小法）算术平均最小法11().()mikjkkijmikjkkxxrxx112().()m

3、ikjkkijmikjkkxxrxx（6）几何平均最小法）几何平均最小法11()(,0).mikjkkijikjkmikjkkxxrxxxx（8）指数相似系数法）指数相似系数法21expikjkijkxxrms其中 sk 适当选择.（9）绝对值倒数法）绝对值倒数法11,ijmikjkkijMrijxxM 适当选取使 rij 在 0,1 中且分散开（7）绝对值指数法）绝对值指数法1expmijikjkkrxx（11）非参数法）非参数法,ikikijkjkjxxx xxx1122,ijijimjmnx xx xx x中正数个数，1122,ijijimjmnx xx xx x中负数个数，1(1)2i

4、jnnrnn令则（10）绝对值减数法）绝对值减数法11mijikjkkrcxx （12）贴近度法）贴近度法如果特征,0,1(1,2,),ikjkxxkm则 ui, uj 可看作模糊向量1212(,),(,)iiiimjjjjmuxxxuxxx, 以它们的贴近度 D(ui,uj)为其相似程度.i) 格贴近度1,( ,),ijijijrD u uij11( ,)()1()mmijikjkikjkkkD u uxxxx , 其中ii) 距离贴近度1( ,),ijijrc d u u 其中 c,a 为适当选择参数值，d(ui,uj) 为模糊集各种距离.iii) 算术平均最小贴近度1112()( ,).

5、mikjkkijijmmikjkkkxxrD u uxx（13）主观评定法）主观评定法 请有实际经验者直接对 ui，uj 的相似程度评分，作为 rij 的值. 通过标定求出相似系数后，便可得到以 rij 为元素的模糊相似矩阵 R(rij) .选择一种合适的聚类方法，便可得到分类结果.根据标定所得模糊矩阵R，求出其传递闭包( ),( )t R Rt R为模糊等价矩阵，对0,1，令从1降到0得到R，根据R进行分类：1ijijruu 与归为一类. 聚类图给出各值对应的分类，形成一种动态聚类，便于全面了解元素聚类，然后根据实际需要选择其阈值，便可确定元素的一种分类，至于如何选择阈值，使分类更加合理，除

6、了凭经验外，还可用 F-统计量来选取.F-统计量统计量：12 ,nUu uu为待分类事物的全体，12(,)jjjjmuxxx设xjk 为描述元素 uj 第 k 个特征的数据(1,2,)km.设 c 为对应于 值的类数，ni 为第 i 类元素的个数，第 i 类元素记为12,iiiinu uu记11(1,2,)inikjkjixxkmn为第 i 类元素的第 k 个特征的平均值, 而称12(,)iiiimuxxx为第 i 类的聚类中心向量；12( ,)mux xx为全体元素的中心向量，而11(1,2,)nkjkjxxkmn于是，称21211|(1)|()iiciiiincjijnuucFuunc为F

7、-统计量，其中|iuu为第i类中元素iju与中心iu的距离. 可见，F-统计量的分子表征类与类间的距离，分母表征类内元素间的距离. 因此，F 值越大，说明分类越合理，与此分类相对应的 F-统计量最大的阈值为最佳值.设()ijn nAa为模糊相似矩阵，求 t(A).(1) 求12maxjj na ,假定112maxmjj naa , 把 A 中的 a1m,am1,a11,amm 用圆圈圈起来，并记*11,mmmmmxaaa(2) 在 A 中第一行、第 m行中剩下的元素中找最大元素*2x, 即*21,;1,maxijim jmxa. 且设*2x在第 p 列. 用*122,mmmax ax即分别代替

8、 a1p 与 amp 以及它们的对称元素，最后用圆圈将它们及 圈起来.ppa(3) 假定 A 中有圈的 k 行(1,2,1)kn是12( 1), ,kiii行. 而*1kx所在的列是 ij 列，在这些行中剩下的元素中找最大元1212*,max ()kkkiji i iij i iixa并设 在第 l 行，用*kx12*,jjk ji iki iki ikax axax 分别代替12,ki li li laaa继续此过程，到 k = n-1,得到 t(A) .还有逐步平方法：及其对称矩阵，并把 all 圈起来 112422222kkkkkRRRRRRRt RR计算，直至出现，则2R 聚类原则是：

9、ui与uj在水平同类当且仅当在相似矩阵R的图中，存在一条权重不低于的路联结ui与uj.(1)画出以被分类元素为结点，以相似矩阵R的元素 rij 为权重的一颗最大树；(2)取定 ，砍断权重低于的枝，得到一个不连通图，各连通分支变构成了在水平上的分类.0,1对给定的模糊相似矩阵R，取定水平0,1, 作截矩阵R ，在 R 的主对角线上填入元素的符号，在对角线下方以结点号 “*” 代替 1，而 “0” 则略去不写，由结点向主对角线上引经线和纬线，称之为编网，通过经线和纬线能互相连接起来的元素，属于同类，从而实现了分类.如果划分把普通集合分成 c 类，则此划分就叫普通 c-划分，即：若设12,njUu

10、uuu的特征可表为12(,)jjjjmuxxx，那么U的普通c-划分是指U的c个子集1,2,(2)iA iccn满足: (1)1;ciiAU(2)()ijAAij 121112112212221212nnnccccnuuuAaaaAAaaaAaaac1,()0,()jijijjijuA uiauA ui属于第 类不属于第 类其中且满足 (1)(2)1,1cijija(表示每个uj必属于且仅属于一类)；1,01nijjia(表示每类Ai至少有一个元素)； 反过来，任一满足条件(1)、(2)、(3)的矩阵对应着U的一个分类.(1)(2)(3)这样的分类结果可以用一个 cn 矩阵(称为 c-划分)来

11、表示. 例如，设 U=u1,u2,u3,u4, 若分类结果为 u1, u2,u3, u4, 则对应的分类矩阵为123100010110200013nuuuu 如果分类矩阵为100001100001则对应着 U 的分类为 u1, u2,u3, u4.记 V 为 cn 实矩阵的集合，且11(),0,1 ,1,0cncijc nijijijijMA AaaaanV 显然，对于给定的 U 及分类数 c ，类的分法不是唯一的. Mc 包含了 U 的所有可能 c 类划分的结果，Mc 称为将 U 分成 c 类的分类空间. 这样的分类是通常的分类，称为硬分类.12,nUu uu12(,)jjjjmuxxx设,

12、一个 cn 模糊矩阵1112122122212nnccccnAaaaAaaaAAaaa若满足 (1)(2)1,1cijija( 表示每个 uj 属于 c 个模糊子集 Ai 的程度总和为 1 ) ；1,01nijjia(表示每类 Ai 不等于空集或 U ) ；则称 A 称为 U 的模糊 c-划分矩阵. 记11(),0,1,1,0cnfcijc nijijijijMA AaaaanMMfc 称为 U 的 c 类软分类空间. 显然.cfcMM若将 Mc 和Mfc 定义中的条件：10()nijjani10()nijjani放宽为则这样的分类空间分别称为退化的硬分类空间和退化的软分类空间. 分别记为 M

13、co 和 Mfco , 显然.cofcoMM(1) 目标函数法目标函数法 目标函数是对给定的 c 的所有候选类进行度量，最优的类就是使目标函数达到局部最小值的类. 对于硬分类情形，通常所选取的目标函数是总体组内误差平方和，其定义为211( , )|cnijjiijJ A Vauv这里将每类 Ai 中元素各特征分别取平均值，所得的聚类中心向量记为 vi，也称为 Ai 的聚类中心. 由于 Ai 类中元素个数1niijjna1nijjja u, Ai类中元素向量和为, 因此聚类中心向量11nniijjijjjva ua记11112121112112mmccccmvvvvvvvvVvvvvV 称为聚类

14、中心矩阵. 若jiuA, 则uj到聚类中心vi的距离为21|()mijjijkikkduvxvAi 中全体元素到中心距离平方和为21()nijijja d而 V 中所有元素到其所在类中心距离平方和为221111( , )()|cncnijijijjiijijJ A Va dauv最理想的 c-划分显然是使 J(A,V) 取极小的 A .(2) 硬硬 c-均值算法均值算法步骤1：假设给出 n 个数据点12 ,nUu uu12(,)mjjjjmuxxxR, 其中. 取定(2),ccn并初始化(0)cAM步骤2：当迭代次数为(0,1,2,)l l 时, 计算聚类中心向量( )( )( )11nnll

15、liijjijjjva ua( )( )1,2, .llijaAic其中,步骤3：用下式将 A(l) 更新为(1)(1)llijAa( )( )(1)11,| min(|)0,lljijklk cijuvuva 其它步骤4：比较 A(l) 和 A(l+1) , 若(1)( )|llAA, 则停止算法；否则，令 l=l+1，返回步骤2. 直观上看，硬 c-均值算法：猜想 c的硬分类（步骤1），寻找各分类的中心（步骤2），重新分配类的隶属度以减少数据和当前中心的误差平方（步骤3），当循环不再能显著的降低 J(A,V) 时，停止算法（步骤4）.定义目标函数211( , )() |cnrmijjiij

16、JA Vauv其中 是一个加权指数.1r 模糊 c-均值算法的目标在于找到ijfcAaM和12,()mniVv vvvR, 使得 Jm(A,V)最小 下面，首先建立这个最小化问题的必要条件，然后根据此条件提出模糊 c-均值算法.定理 令12,nUu uu，12(,)mjjjjmuxxxR为一给定数据集. 设定2,3,11,cnr和，假设对所有11,| 0jiknicuu 和有，则仅当2111,1,1|ijrcjijjjaicjnuvuv 11(),1()nrijjjinrijjauvica 和时，12,ijnAaVv vv和才是 Jm(A,V) 的局部最小值.模糊 c-均值算法 ( ISODA

17、TA方法 ) 步骤：步骤1：给定数据集12,nUu uu12(,).mjjjjmuxxxR设定, 并初始化(0).cAM步骤2：当迭代次数为(0,1,2,)l l 时, 计算聚类中心向量( )( )( )11,1nnrrllliijjijjjvauaic 步骤3：用下式将 ， 更新为(1)(1)llijAa2,3,11,cnr和( )( )llijAa(1)2( )1( )11, 1, 1|lijlrcjiljjjaicjnuvuv 步骤4：若(1)( )|llAA, 则停止算法；否则令 l=l+1，返回步骤2.注意：本方法要求ijvu, 因此取初始分类 A(0) 时, 遇到只有一个样本的类，要在聚类前先排除，待聚类后再加上该类，而参数 r 一般常取 r2 . 在实际问题中，最后的分类结果都要求是明确的，因此，在使用模糊 c-划分分类后，都必须将模糊划分清晰化，可用下述方法进行.方法1 对,juU若1| min(|)jijkk cuvuv 则将 uj 归入 Ai 类.方法2 对,juU若1maxijkjk caa 则将 uj 归入 Ai 类.