资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 模糊聚类分析,一、模糊关系,什么是关系,同学集合,X=,张三，李四，王五,外语选修课程集合,Y=,英，法，德，日,R= (,张三,英,), (,张三,法,), (,李四,德,), (,王五,日,), (,王五,英,),关系,定义,1,：集合,A,B,的直积,AB=(a,b)|aA,bB,的一个,子集,R,称为,A,到,B,的一个二元关系，简称关系。,可见，关系也是个集合。,关系,example1,设,X,为横轴，,Y,为纵轴，直积,X,Y,是整个平面，其上的普通关系,xy,：,Y,X,Y=X,R:XY,0,模糊关系,定义：以集合,A,B,的直积,AB,为论域，其上的一个模糊子集,R,称为,A,B,的一个模糊关系。若,A=B,，则称为“,A,上的模糊关系,R”,，,模糊关系,example1,其上的模糊关系,R=“x,远远,大于,y”,，怎么表示？,当,x=1000,y=100,时，,R(x,y,当,x=20,y=10,时，,R(x,y,当,x=20,y=18,时，,R(x,y,R(x,y),X,1,0,y,模糊关系,example2,例：设身高论域,U=,140,，,150,，,160,，,170,，,180,，体重论域,V=,40,，,50,，,60,，,70,，,80,，则身高与体重之间的模糊关系：,U,V,140,150,160,170,180,40,1,0.8,0.2,0.1,0,50,0.8,01,0.8,0.2,0.1,60,0.2,0.8,1,0.8,0.2,70,0.1,0.2,0.8,1,0.8,80,0,0.1,0.2,0.8,1,模糊关系的运算,模糊关系就是模糊子集，只不过其论域是直积,AB,罢了,模糊关系的运算法则完全服从模糊集合的运算法则,模糊关系的运算,设,R,S,都是,XY,上的模糊关系，则,1),2),模糊关系的运算,3),4),模糊关系的运算,5),模糊矩阵的概念,模糊关系的表示模糊矩阵,经典有限集合上的关系，可以使用矩阵来表示。,若论域,XY,是,有限集,，模糊关系可以表示为模糊矩阵。,模糊矩阵元素表示关系的隶属值。,若论域,XY,是,连续或无限的,，则该论域上的,(,模糊,),关系不能用,(,模糊,),矩阵来表示。,模糊矩阵的定义,如果对于任意,i=1,2,m, j=1,2,n,都有,r,ij,0,1,则称矩阵,R=(r,ij,),mn,为模糊矩阵。若,r,ij,0,1,则模糊矩阵变成,Boole,矩阵。,模糊矩阵可以表示模糊关系，对于“,A,上的模糊关系”用模糊方阵来表示。,模糊矩阵,Example,设有四种物品，苹果、乒乓球、书、花组成的论域,U,，分别用,x,1,x,2,，,x,n,表示，它们的相似程度可以用模糊关系,R,来表示：,模糊关系与模糊矩阵,如果给定,X,上的模糊关系,I,满足,则称,I,为,X,的“恒等关系”，表示恒等关系,I,的矩阵为单位矩阵。,模糊关系与模糊矩阵,若给定,XY,上的模糊关系,O,，满足,则称,O,为,XY,的“零关系”，,表示零关系,O,的矩阵为零矩阵。,模糊关系与模糊矩阵,如果给定,XY,上的模糊关系,E,满足,称,E,为,XY,的“全称关系”，表示全称关系,E,的矩阵为全称矩阵。,模糊关系与模糊矩阵,如果给定,XY,上的模糊关系,R,，定义,称,R,T,为,R,的“倒置关系”,表示模糊关系,R,T,的矩阵为,R,矩阵的转置矩阵。,模糊矩阵的运算及性质,模糊矩阵的关系,设,A,、,B,为模糊矩阵，记,A=(a,ij,), B=(b,ij,),，,i=1,2,m,j=1,2,n,则,(1),相等：,A=B ,对任意,i,j,有,a,ij,=b,ij,(2),包含：,AB ,对任意,i,j,有,a,ij,b,ij,模糊矩阵的运算,设,A,、,B,为模糊矩阵，记,A=(a,ij,),B=(b,ij,),，,i=1,2,m, j=1,2,n,则,(1),并：,AB (a,ij,b,ij,),mn,(2),交,: AB (a,ij,b,ij,),mn,(3),余,: A,c, (1-a,ij,),mn,模糊矩阵的运算,求,模糊矩阵的运算性质,（,1,）幂等律：,AA,A , AA=A;,（,2,）交换律：,AB=BA, AB=BA;,（,3,）结合律：,(AB)C=A(B C),(AB)C=A(BC);,（,4,）吸收律：,A(AB)= A,A(AB)=A;,（,5,）分配律,:,(AB)C=( AC)(BC),(AB)C= ( AC)(BC);,模糊矩阵的运算性质,（,6,）,0-1,律：,AO,A, AO,O;,EA=E,EA=A;,（,7,）还原律：,(A,c,),c,=A;,（,8,）对偶律：,(AB),c,= A,c,B,c,(AB),c,= A,c,B,c,.,排中律不成立！,A,c,A E, AA,c, O,注意,模糊矩阵的包含性质,模糊关系的合成,模糊关系的合成,设有三个论域,X,、,Y,、,Z,，,R,1,是,X,到,Y,上的模糊关系，,R,2,是,Y,到,Z,上的模糊关系，则,R,1,与,R,2,的合成,R,1,。,R,2,是,X,到,Z,的一个模糊关系，其隶属函数为,模糊关系的合成,当论域为有限时，模糊关系的合成转化为模糊矩阵的合成，合成运算相当于矩阵的合成运算。,模糊矩阵的合成运算,不满足交换律。,例：设,求,模糊方阵,模糊方阵的幂：,合成运算的性质,性质,1,（结合律）：,性质,2,：,性质,3,（分配律）可以推广到多个：,性质,4,（,0,1,律）：,合成运算的性质,合成运算的交运算的分配律不成立,注意,合成运算的性质,性质,5,：,性质,6,：,合成运算,Example1,设,R,1,为,XY,上的模糊关系,其隶属函数满足,设,R,2,为,YZ,上的模糊关系,其隶属函数满足,试求,R,1,、,R,2,的合成。,模糊矩阵的转置,与线性代数中，模糊矩阵的转置相同。,性质,1,：,性质,2,：,性质,3,：,性质,4,：,性质,5,：,模糊矩阵的转置,性质,3,证明：,设,A=(a,ik,),ms,，,B=(b,kj,),sn,，,A,。,B=(c,ij,),mn,则，,(A,。,B),T,(c,ij,T,),nm,，,A,T,=(a,ik,T,),sm,，,B=(b,kj,T,),ns,。于是，,模糊矩阵的,截矩阵,模糊矩阵的,截矩阵,模糊集合,- ,截集,模糊矩阵,- ,截矩阵,定义：设给定模糊矩阵,R=(r,ij,),，对任意, 0,1,，称,R,=(r,ij,(),),为,R,的,截矩阵，其中,模糊矩阵的,截矩阵,求模糊矩阵,R,在时的,截矩阵,截矩阵的性质,模糊矩阵,A,B,，, 0,1,，,性质,1.,截矩阵的性质,模糊矩阵,A,B,，, 0,1,，,性质,2.,截矩阵的性质,性质,3,：,证明,设,A=(a,ik,),ms,B=(b,kj,),sn,A,。,B=(c,ij,),mn,截矩阵的性质,模糊矩阵,A,B,，, 0,1,，,性质,4,：,模糊矩阵的基本定理,模糊矩阵的基本定理,定义,1.,若模糊矩阵,A M,nn,满足,AI,，则称,A,为,模糊自反矩阵,。,例如：,自反矩阵的定理,定理,1.,设模糊矩阵,A M,nn,是自反矩阵，则有,I A A,2, A,3, A,n-1,A,n,证明,:,模糊对称矩阵,定义,2.,若模糊矩阵,A M,nn,满足,A,T,=A,，则称,A,为,模糊对称矩阵,。,例如：,模糊传递矩阵,定义,3.,若模糊矩阵,A M,nn,满足,A,2, A,，则称,A,为,模糊传递矩阵,。,例如：,模糊传递矩阵,定理,2.,设模糊矩阵,Q M,nn,是传递矩阵，则有,Q Q,2, Q,3, Q,n-1, Q,n,证明,:,传递闭包,定义,4.,设,Q,S,A M,nn,，满足,（,1,）,S A (S,2,S);,（,2,）对于任何,Q A (Q,2,Q),，总有,Q S,，,则称,S,为,A,的,传递闭包,记为,S=t(A).,表示包含,A,，且被任何包含,A,的传递矩,阵所包含的传递矩阵。,传递闭包的定理,定理,3.,设模糊矩阵,A M,nn,，则,其中，,t(A),是传递闭包。,传递闭包的定理证明,传递闭包的定理,定理,4.,设模糊矩阵,A M,nn,，则,其中，,t(A),是传递闭包。,模糊等价关系,定义,5.,设论域,U=x,1, x,2, , x,n,，若模糊关系,RM,nn,满足,（,1,）自反性：,R (x,x)=1;,（,2,）对称性：,R(x,y)=R(y,x);,（,3,）传递性：,R,2,R,则称,R,为,模糊等价关系,模糊等价矩阵,定义,6.,设论域,U=x,1, x,2, , x,n,，,RM,nn, I,为单位矩阵，若,R,满足,（,1,）自反性：,R I;,（,2,）对称性：,R,T,=R;,（,3,）传递性：,R,2,R,则称,R,为,模糊等价矩阵,.,模糊等价矩阵,例,1.,设论域,U=x,1, x,2,，,R,是否为,模糊等价矩阵,？,模糊等价矩阵,若,R,为模糊等价矩阵，则,R= R,2,= R,3,= = R,n-1,= R,n,证明：,自反性：,R R,2, R,n-1,R,n,传递性：,R R,2, R,n-1, R,n,模糊等价矩阵的性质,定理,5. R,是模糊等价矩阵,对于任何,0,1,，,R,是等价布尔矩阵。,证明：（传递性）,反向是分解定理,模糊等价矩阵的性质,定理,5,的意义：,将,模糊等价矩阵,转化为,普通等价矩阵,。,普通等价矩阵,等价于有限论域上的,普,通等价关系,，普通等价关系可以分类。,因此，当,在,0,1,上变动时，得到不同,的,R,从而得到不同的分类。,模糊等价矩阵,例,2.,设,U=x,1, x,2, x,3,x,4, x,5,求当,1,，时的聚类结果。,模糊等价矩阵的性质,定理,6. R M,nn,是模糊等价矩阵，则对于任何, 0,1,，且,，,R,所决定的分类中的每个类都是,R,所决定的分类中的某个类的子类。,模糊等价矩阵,定理,6,说明，,越大，分类越细。,由,1,变到,0,的过程，是,R,的分类由细到粗的过程，从,而形成了一个动态的聚类图。,x1,x2,x3,x4,x5, =1,模糊相似矩阵及其性质,定义,7.,设,R,是,UU,上的模糊关系 ，若,R,满足,（,1,）自反性：,R(x,x)=1;,（,2,）对称性：,R(x,y)=R(y,x);,则称,R,为,U,上的模糊相似关系，其中隶,属度,R(x,y),表示,x,y,的相似程度。,例如：模糊关系“熟悉”，“朋友”,“同学”等。,模糊相似矩阵,定义,8.,设有限论域,U=x,1, x,2, , x,n,，,RM,nn,，,I,为单位矩阵，若,R,满足,（,1,）自反性：,R I,（即,r,ii,=1,）,;,（,2,）对称性：,R,T,=R,（即,r,ji,=r,ij,）,;,则称,R,为,模糊相似矩阵,。,模糊相似矩阵的性质,定理,7.,设,RM,nn,是模糊相似矩阵，则对于任何自然数,k,，,R,k,也是模糊相似矩阵。,请同学们用数学归纳法证明,模糊相似矩阵的性质,当,k,1,时，,R,K,是模糊相似矩阵。,假设,k=n,时，,R,K,是模糊相似矩阵，,模糊相似矩阵,vs.,模糊等价矩阵,定理,8.,设,RM,nn,是模糊相似矩阵，则存在一个最小自然数,k,（,k n,），使得传递闭包,t(R)=R,k,，对于任何自然数,bk,，都有,R,b,=R,k,，此时，,t(R),是模糊等价矩阵。,平方法求相似矩阵的传递闭包,从模糊相似矩阵,R,出发，依次求平,方：,当第一次出现,R,k,R,k,=R,k,时，,R,k,就是,所求的传递闭包,t(R),平方法例,设,求传递闭包,t(R),经过,i,次求得,nn,阶模糊相似矩阵,R,的传递,闭包,t(R)=R,2i,，必有,2,i,n,，,i,logn/log2,，,因此，最多计算,log,2,n,1,次便可求,t(R).,模糊聚类,何谓“聚类”,对所研究的事物按一定的标准进行分类的,数学方法，称为“聚类分析”。这是“物以类,聚”的一种分类方法,.,模糊聚类分析的步骤,第一步：数据标准化（建立模糊矩阵） ；,第二步：建立模糊相似矩阵；,第三步：聚类（求动态聚类图）,模糊聚类分析的步骤一,第一步：数据标准化（建立模糊矩阵）,设论域,U =x,1, x,2, , x,n,为被分类对象，,每个对象由,m,个指标表示其性状：,将原始数据矩阵中的元素通过,适当的变换,压缩到,0,1,上。,模糊聚类分析的步骤一,第一步：数据标准化（建立模糊矩阵）,常用的两种变换：,平移标准差变换,平移极差变换,模糊聚类分析的步骤一,平移标准差变换,(,消除量纲,),：,模糊聚类分析的步骤一,平移极差变换,(,变换至,0-1,区间,),：,例：,p98,例,1,、,p106,例,2,模糊聚类分析的步骤二,第二步：建立模糊相似矩阵,对于第一步所得到的模糊矩阵，建立其对应,的模糊相似矩阵,R,，,r,ij,R(x,i,x,j,),表示,x,i,与,x,j,的相似度。,模糊聚类分析的步骤二,第二步：建立模糊相似矩阵,1,、相似系数法：,数量积法、夹角余弦法、相关系数法、指数相似系数法、最大最小法、算数平均最小法、几何平均最小法。,2,、距离法：,绝对值倒数法、绝对值指数法、海明距离法、欧式距离法、切比雪夫距离法。,3,、其它方法：主观评分法,模糊聚类分析的步骤二,1,、相似系数法：,(1),数量积法,(P86,例,1),|r,ij,|,0,1,若为负，要将其压缩到,0,1,压缩,方法：平移极差变换、,r,ij,(r,ij,+1)/2,模糊聚类分析的步骤二,1,、相似系数法：,(2),夹角余弦法：,(3),相关系数法：,模糊聚类分析的步骤二,1,、相似系数法：,(4),指数相似系数法：,P110,相关系数法中一行表示一个母体的多个样本，,指数相似系数法中一行表示一个样本的多个属性,模糊聚类分析的步骤二,1,、相似系数法：,(5),最大最小法：,(6),算数平均最小法：,(7),几何平均最小法：,模糊聚类分析的步骤二,2,、距离法,(8),绝对值倒数法：,(9),绝对值指数法：,模糊聚类分析的步骤二,2,、距离法,直接距离法：,r,ij,1-c*d(x,i,x,j,),(10),海明距离：,(11),欧式距离：,P101,、,115,(12),切比雪夫距离：,模糊聚类分析的步骤二,3,、其它方法,(13),主观评分法,专家直接给出相似度，专家数为,N,，,r,ij,(k),表,示第,k,个专家给出的,i,与,j,的相似度，,a,ij,(k),为,专家的自信度。,模糊聚类分析的步骤三,第三步：聚类（求动态聚类图）,1,、基于模糊等价矩阵聚类方法,(1),传递闭包法；,(2),布尔矩阵法；,模糊聚类分析的步骤三,关于布尔矩阵法的一个定理：,定理,9,：设,RM,nn,是相似的布尔矩,阵，则,R,具有传递性，等价于矩阵,R,在,任一排列,下的矩阵都没有如下的特殊,子矩阵,模糊聚类分析的步骤三,1,、基于模糊等价矩阵聚类方法,(2),布尔矩阵法；,按定理将非等价布尔矩阵改造成等价,矩阵。,P89,页：例,2,模糊聚类分析的步骤三,按布尔矩阵法进行改造：,模糊聚类分析的步骤三,第三步：聚类（求动态聚类图）,2,、直接聚类法,(1),直接聚类法：不求传递闭包，也不求布尔矩阵，直接从模糊相似矩阵出发求得聚类图；,(2),最大树法；,(3),编网法；,模糊聚类分析的步骤三,(1),直接聚类法,取,1,x1,x3x3,x5,等价类,x1,x3,x5x2x4,P93,页例,3,模糊聚类分析的步骤三,(2),最大树法：,画以被分类元素为顶点，以相似矩阵,R,为权重的,一棵最大树。取,0,1,坎断权重低于,的枝，,所得图中每个连通分支为,水平的分类。,P94,：例,4,模糊聚类分析的步骤三,(3),编网法：,P95,例,5,模糊聚类分析,总结：,各种聚类方法各有优劣，传递闭包法适合于计算机操作，其它方法当矩阵阶数小时，容易手工实现。,模糊聚类分析最佳阈值确定,(1),专家给出,(2),使用,F,统计量,设论域,U =x,1, x,2, , x,n,为被分类对象，,每个对象有,m,个特征：,模糊聚类分析的步骤三,设分类数为,r,，第,j,类的样本数为,n,j,，分别为,x,1,(j),，,x,nj,(j),。第,j,类的聚类中心,模糊聚类分析的步骤三,F,统计量：,遵从自由度为,r-1,n-r,的,F,分布。,分子表示类与类的距离，分母表示类内样本间的,距离，,F,值越大，分类越好。,Homework,习题,2,：,2,、,9,、,13,、,19,、,25,
展开阅读全文