《模煳聚类分析》PPT课件

1、 设设R = (rij)mn，假设，假设0rij1，那么称，那么称R为模为模糊矩阵糊矩阵. 当当rij只取只取0或或1时，称时，称R为布尔为布尔(Boole)矩矩阵阵. 当模糊方阵当模糊方阵R = (rij)nn的对角线上的元素的对角线上的元素rii都为都为1时，称时，称R为模糊自反矩阵为模糊自反矩阵. 设设A=(aij)mn,B=(bij)mn都是模糊矩阵，都是模糊矩阵，定义定义相等：相等：A = B aij = bij；包含：包含：AB aijbij；并：并：AB = (aijbij)mn；交：交：AB = (aijbij)mn；余：余：Ac = (1- aij)mn.0.10.30.20

2、.1,0.20.10.30.20.20.30.10.10.90.7,0.30.20.20.10.80.9cABABABA例 设，则 设设A = (aik)ms，B = (bkj)sn，称模糊矩阵，称模糊矩阵A B = (cij)mn，为为A 与与B 的合成，其中的合成，其中cij = (aikbkj) | 1ks .模糊方阵的幂模糊方阵的幂 定义：假设定义：假设A为为 n 阶方阵，定义阶方阵，定义A2 = A A，A3 = A2 A，Ak = Ak-1 A.7 . 04 . 03 . 03 . 07 . 04 . 03 . 01 . 07 . 04 . 03 . 03 . 07 . 04 .

3、03 . 01 . 03 定义定义 设设A = (aij)mn, 称称AT = (aijT )nm为为A的的转置矩阵，其中转置矩阵，其中aijT = aji.转置运算的性质：转置运算的性质：性质性质1：( AT )T = A；性质性质2：( AB )T = ATBT， ( AB )T = ATBT；性质性质3：( A B )T = BT AT；( An )T =( AT )n ；性质性质4：( Ac )T = ( AT )c ；性质性质5：AB AT BT . 设设A = (aij)mn,对恣意的对恣意的 0, 1，称，称A = (aij( )mn,为模糊矩阵为模糊矩阵A的的 - 截矩阵截矩阵

4、, 其其中中 当当aij 时，时，aij( ) =1； 当当aij 时，时，aij( ) =0. 显然，显然，A的的 - 截矩阵为布尔矩阵截矩阵为布尔矩阵. 1110110010110011,18 . 03 . 008 . 011 . 02 . 03 . 01 . 015 . 002 . 05 . 013 . 0AA 与模糊子集是经典集合的推行一样，模糊关与模糊子集是经典集合的推行一样，模糊关系是普通关系的推行系是普通关系的推行. . 设有论域设有论域X X，Y Y，X X Y Y 的一个模糊子集的一个模糊子集 R R 称为从称为从 X X 到到 Y Y 的模糊关系的模糊关系. . 模糊子集模

5、糊子集 R R 的隶属函数为映射的隶属函数为映射R : X R : X Y Y 0,1.0,1.并称隶属度并称隶属度R (x , y ) R (x , y ) 为为 (x , y ) (x , y )关于模糊关关于模糊关系系 R R 的相关程度的相关程度. . 特别地，当特别地，当 X =Y X =Y 时，称之为时，称之为 X X 上各元素之上各元素之间的模糊关系间的模糊关系. . 由于模糊关系由于模糊关系 R R就是就是X X Y Y 的一个模糊子集，的一个模糊子集，因此模糊关系同样具有模糊子集的运算及性质因此模糊关系同样具有模糊子集的运算及性质. .设设R，R1，R2均为从均为从 X 到到

6、 Y 的模糊关系的模糊关系.相等：相等：R1= R2 R1(x, y) = R2(x, y)；包含：包含： R1 R2 R1(x, y)R2(x, y)；并：并： R1R2 的隶属函数为的隶属函数为 (R1R2 )(x, y) = R1(x, y)R2(x, y)；交：交： R1R2 的隶属函数为的隶属函数为(R1R2 )(x, y) = R1(x, y)R2(x, y)；余：余：Rc 的隶属函数为的隶属函数为Rc (x, y) = 1- R(x, y). (R1R2 )(x, y) (R1R2 )(x, y)表示表示(x, y)(x, y)对模糊关系对模糊关系“R1R1或者或者R2R2的相关

7、程度，的相关程度， (R1R2 )(x, y) (R1R2 )(x, y)表示表示(x, (x, y)y)对模糊关系对模糊关系“R1R1且且R2R2的相关程度，的相关程度，Rc (x, y)Rc (x, y)表示表示(x, y)(x, y)对模糊关系对模糊关系“非非R R的相关程度的相关程度. . 对于有限论域对于有限论域 X = x1, x2, , xm X = x1, x2, , xm和和Y Y = y1, y2, , yn= y1, y2, , yn，那么，那么X X 到到Y Y 模糊关系模糊关系R R可用可用m mn n 阶模糊矩阵表示，即阶模糊矩阵表示，即R = (rij)mR =

8、(rij)mn n，其中其中rij = R (xi , yj )0, 1rij = R (xi , yj )0, 1表示表示(xi , (xi , yj )yj )关于模糊关系关于模糊关系R R 的相关程度的相关程度. . 又假设又假设R R为布尔矩阵时为布尔矩阵时, ,那么关系那么关系R R为普通关为普通关系系, ,即即xi xi 与与 yj yj 之间要么有关系之间要么有关系(rij = 1),(rij = 1),要么要么没有关系没有关系( rij = 0 ).( rij = 0 ). 设设 R1 R1 是是 X X 到到 Y Y 的关系的关系, R2 , R2 是是 Y Y 到到 Z Z

9、 的关系的关系, , 那么那么R1R1与与 R2 R2的合成的合成 R1 R1 R2 R2是是 X X 到到 Z Z 上的一个关系上的一个关系. .(R1 (R1 R2) (x, z) = R1 (x, y)R2 (y, R2) (x, z) = R1 (x, y)R2 (y, z)| yY z)| yY 当论域为有限时，模糊关系的合成化为模糊当论域为有限时，模糊关系的合成化为模糊矩阵的合成矩阵的合成. . 设设X = x1, x2, , xm,Y = y1 , X = x1, x2, , xm,Y = y1 , y2 , , ys, Z= z1, z2, , zn,y2 , , ys, Z=

10、 z1, z2, , zn,且且X X 到到Y Y 的模糊关系的模糊关系R1 = (aik)mR1 = (aik)ms s ，Y Y 到到Z Z 的模糊关的模糊关系系R2 = (bkj)sR2 = (bkj)sn n ，那么，那么X X 到到Z Z 的模糊关系可表的模糊关系可表示为模糊矩阵的合成：示为模糊矩阵的合成：R1 R1 R2 = (cij)m R2 = (cij)mn n 其中其中cij = (aikbkj) | 1ks.cij = (aikbkj) | 1ks. 假设模糊关系假设模糊关系R是是X上各元素之间的模糊关系，上各元素之间的模糊关系，且满足：且满足： (1)自反性：自反性：R

11、(x, x) =1； (2)对称性：对称性：R(x, y) =R(y, x)； (3)传送性：传送性：R2 R, 那么称模糊关系那么称模糊关系R是是X上的一个模糊等价关系上的一个模糊等价关系. 当论域当论域X = x1, x2, , xn为有限时为有限时, X 上的一上的一个模糊等价关系个模糊等价关系R就是模糊等价矩阵就是模糊等价矩阵, 即即R满足：满足：I R ( rii =1 )RT=R( rij= rji)R2R.R2R ( (rikrkj) | 1kn rij) .12345 ,10.40.80.50.50.410.40.40.40.80.410.50.50.50.40.510.60.

12、50.40.50.61Uu u u u uR 例设 210.40.80.50.50.410.40.40.40.80.410.50.50.50.40.510.60.50.40.50.61RR RR( ,)1( ,1,2,3,4,5)ijijuuR u ui j元素 与 归为一类的充要条件是 110.40.80.50.5100000.410.40.40.4010000.80.410.50.5001000.50.40.510.6000100.50.40.50.6100001RR0.810.40.80.50.5101000.410.40.40.4010000.80.410.50.5101000.50.

13、40.510.6000100.50.40.50.6100001RR12345: , , 5uuuuu相应的分类共分为 类13245: , 4u uuuu相应的分类共分为 类12345 , , uuuuu当 =1时，得到的分类为；13245 , u uuuu当 =0.8时，得到的分类为；13245 , ,u uuu u当 =0.6时，得到的分类为；13452 , u u u uu当 =0.5时，得到的分类为；12345 ,u u u u u当 =0.4时，得到的分类为； 假设模糊关系假设模糊关系 R 是是 X 上各元素之间的模糊关上各元素之间的模糊关系，且满足：系，且满足： (1) 自反性：自反

14、性：R( x , x ) = 1； (2) 对称性：对称性：R( x , y ) = R( y , x ) ； 那么称模糊关系那么称模糊关系 R 是是 X 上的一个模糊类似关系上的一个模糊类似关系. 当论域当论域X = x1, x2, , xn为有限时，为有限时，X 上的上的一个模糊类似关系一个模糊类似关系 R 就是模糊类似矩阵，即就是模糊类似矩阵，即R满满足：足： (1) 自反性：自反性：I R ( rii =1 )； (2) 对称性：对称性：RT = R ( rij = rji ). 定理定理1 假设假设R 是模糊类似矩阵，那么对恣意的是模糊类似矩阵，那么对恣意的自然数自然数 k，Rk 也

15、是模糊类似矩阵也是模糊类似矩阵. 定理定理2 假设假设R 是是n阶模糊类似矩阵，那么存在阶模糊类似矩阵，那么存在一个最小自然数一个最小自然数 k (kn )，对于一切大于，对于一切大于k 的自的自然数然数 l，恒有，恒有Rl = Rk，即，即Rk 是模糊等价矩阵是模糊等价矩阵(R2k = Rk ). 此时称此时称Rk为为R的传送闭包，记作的传送闭包，记作 t ( R ) = Rk . 上述定理阐明，任一个模糊类似矩阵可诱导出上述定理阐明，任一个模糊类似矩阵可诱导出一个模糊等价矩阵一个模糊等价矩阵.平方法求传送闭包平方法求传送闭包 t (R)：RR2R4R8R1610.10.2 0.110.30

16、.20.31( )RRt R例设容易验证， 是模糊相似矩阵，用平方法求其传递闭包210.10.210.10.210.20.20.110.30.110.30.210.30.20.310.20.310.20.31R RR 22210.20.210.20.210.20.20.210.30.210.30.210.30.20.310.20.310.20.31RRR 210.20.2( )0.210.30.20.31t RR故传递闭包1数据规范化数据规范化 设论域设论域X = x1, x2, , xn为被分类对象为被分类对象,每个每个对象又由对象又由m个目的表示其外形个目的表示其外形:xi = xi1,

17、xi2, , xim, i = 1, 2, , n于是于是,得到原始数据矩阵为得到原始数据矩阵为nmnnmmxxxxxxxxx.212222111211),.,2 , 1,.,2 , 1(mjnisxxxjjijij其中其中21111,()1nnjijjijjiixxsxxnnb 平移平移 极差变换极差变换1|min1|max1|minnixnixnixxxijijijijija 类似系数法类似系数法 -夹角余弦法夹角余弦法mkjkmkikmkjkikijxxxxr12121mkjjkmkiikmkjjkiikijxxxxxxxxr12121)()(| |其中其中1111,mmiikjjkkk

18、xxxxmmrij = 1 c d (xi, xj )其中其中c为适中选取的参数为适中选取的参数.海明间隔海明间隔mkjkikjixxxxd1|),(欧氏间隔欧氏间隔mkjkikjixxxxd12)(),(切比雪夫间隔切比雪夫间隔d (xi, xj ) = | xik- xjk | , 1km 在模糊聚类分析中，对于各个不同的在模糊聚类分析中，对于各个不同的 0,10,1，可得到不同的分类，从而构成，可得到不同的分类，从而构成一种动态聚类图，这对全面了解样本分类一种动态聚类图，这对全面了解样本分类情况是比较笼统和直观的情况是比较笼统和直观的. . 但在许多实践问题中，需求给出样本但在许多实践问

19、题中，需求给出样本的一个详细分类，这就提出了如何确定最的一个详细分类，这就提出了如何确定最正确分类的问题正确分类的问题. .111(1,2, ),( ,)nkikmixxkkxxxn设 称为总体样本的中心向量称为总体样本的中心向量.对应于对应于 值的分类数为值的分类数为r第第 j 类的样本数为类的样本数为nj，第，第 j 类的样本标志为类的样本标志为.,.,)()(2)(1jnjjjxxx第第 j 类样本的中心向量为类样本的中心向量为( )( )( )1:1(1,2,)jjknjjkikijxkxxkmn其中为第 个特征的平均值( )( )( )( )12,),jjjjmxxxx（作作F- 统

20、计量：统计量：), 1()/(|) 1/(|112)()(12)(rnrFrnxxrxxnFrjnkjjkrjjjj( )( )2( )1( )( )( )( )()mjjjkkkjjjjiixxxxxxxxjxx上式中为与 的距离为第 类中样本与中心的距离 假设满足不等式假设满足不等式FF ( r -1, n -r )的的F值不止值不止一个，那么可根据实践情况选择一个称心的分类，一个，那么可根据实践情况选择一个称心的分类，或者进一步调查差或者进一步调查差 ( F - F )/F 的大小，从较的大小，从较大者中找一个称心的大者中找一个称心的F值即可值即可. 实践上，最正确分类确实定方法与聚类方

21、法实践上，最正确分类确实定方法与聚类方法无关，但是选择较好的聚类方法，可以较快地找无关，但是选择较好的聚类方法，可以较快地找到比较称心的分类到比较称心的分类. . 左图给出了左图给出了9 9只只AfAf和和6 6只只ApfApf蠓的触角长和翼长蠓的触角长和翼长数据数据, , 其中其中“表示表示Apf,Apf,“表示表示Af.Af.根据触角长根据触角长和翼长来识别一个标本是和翼长来识别一个标本是AfAf还是还是ApfApf是重要的是重要的. . 给定一只给定一只AfAf族族或或ApfApf族的蠓族的蠓, ,如何如何正确地域分它属于正确地域分它属于哪一族？哪一族？ 将他的方法用将他的方法用于触角长

22、和翼长分于触角长和翼长分别为别为(1.24,1.80), (1.24,1.80), (1.28,1.84),(1.40,(1.28,1.84),(1.40,2.04)2.04)三个标本三个标本. .模糊判别方法模糊判别方法 先将知蠓重新进展分类先将知蠓重新进展分类. . 当当 = 0.919时时,分为分为3类类1, 2, 3, 6, 4, 5, 7, 8, 9,10, 11, 12, 13, 14, 15,三类的中心向量分别为三类的中心向量分别为(1.395, 1.770),(1.560, 2.080),(1.227, 1.927).用平移极差变换用平移极差变换227. 108. 2227.

23、1xx将它们分别变为将它们分别变为A1 = (0.200, 0.637) (Af 蠓蠓),A2 = (0.390, 1.000) (Af 蠓蠓),A3 = (0.000, 0.821) (Apf 蠓蠓),再将三只待识别的蠓用上述变换分别变为再将三只待识别的蠓用上述变换分别变为B1= (0.015, 0.672),B2 = (0.062, 0.719),B3 = (0.203, 0.953 ).采用贴近度采用贴近度 3 (A, B) =nkkkxBxAn1| )()(|11计算得：计算得： 3(A1, B1) = 0. 89, 3(A1, B1) = 0. 89, 3(A2, B1) = 0.6

24、5, 3(A2, B1) = 0.65, 3(A3, B1) = 0.92.3(A3, B1) = 0.92. 3(A1, B2) = 0.89, 3(A1, B2) = 0.89, 3(A2, B2) = 0.69, 3(A2, B2) = 0.69, 3(A3, 3(A3, B2) = 0.92. B2) = 0.92. 3(A1, B3) = 0.84, 3(A1, B3) = 0.84, 3(A2, B3) = 0.88, 3(A2, B3) = 0.88, 3(A3, 3(A3, B3) = 0.83.B3) = 0.83. 根据择近原那么及上述计算结果根据择近原那么及上述计算结果,

25、 ,第一只待识第一只待识别的蠓别的蠓(1.24, 1.80)(1.24, 1.80)属于第三类属于第三类, ,即即Apf Apf 蠓；第二蠓；第二只待识别的蠓只待识别的蠓(1.28, 1.84)(1.28, 1.84)属于第三类属于第三类, ,即即Apf Apf 蠓；蠓；第三只待识别的蠓第三只待识别的蠓(1.40, 2.04)(1.40, 2.04)属于第二类属于第二类, ,即即Af Af 蠓蠓. . 设设Af是传粉益虫是传粉益虫, Apf是某种疾病的载体是某种疾病的载体, 能能否应修正他的分类方法？假设需修正否应修正他的分类方法？假设需修正, 为什么？为什么？ 2000网易杯全国大学生数学建模竞赛题：生物网易杯全国大学生数学建模竞赛题：生物学家发现学家发现DNA序列是由四种碱基序列是由四种碱基A,T,C,G按一定按一定顺序陈列而成顺序陈列而成,其中既没有其中既没有“断句断句,也没有标点符也没有标点符号号,同时也发现