模糊集理论及其应用第三章.ppt

《模糊集理论及其应用第三章.ppt》由会员分享，可在线阅读，更多相关《模糊集理论及其应用第三章.ppt（65页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、模糊集理论及其应用第三章 模糊关系与模糊聚类分析13.1 模糊关系及其运算模糊关系及其运算3.1.1 普通关系与普通关系与Boolean矩阵矩阵 定义定义 设U,V 为两个论域,若RP(UV),则称R为U到V 的一个普通关系普通关系.若(u,v)R,则称u对v有关系R,记作uRv;若(u,v)R,则称u对v没有关系R,记作 ;若U=V,且RP(UV),则称R为U上的普通关系.例如例如 设U表示某校全体学生的集合,R=(u,v)|v是u的同学.则R表示U上的“同学”关系 目 录3 定义定义 设U=u1,u2,um,V=v1,v2,vn,RP(UV),令rij=R(ui,vj)(i=1,2,m;j

2、=1,2,n),则R=(rij)mn 为一个mn 矩阵,由于故R=(rij)mn是一个布尔矩阵布尔矩阵.这说明:有限论域间的普通关系可由Boolean矩阵来表示.43.1.2 模糊关系与模糊关系与模糊模糊矩阵矩阵 定义定义 设U,V 为两个论域,若RF(UV)则称R为U到V的一个模糊关系.对(u,v)UV,称R(u,v)为u对v具有模糊关系R的相关程度.特别地 (1)称RF(UU)为U上的模糊关系;(2)若(u,v)UU,有 则称R为U上的恒等关系恒等关系,这时记R=I;(3)若(u,v)UV,有R(u,v)=0,则称 R为U到V的零关系零关系,这时记R=0;(4)若(u,v)UV,有R(u,

3、v)=1,则称R为全称全称关系关系,这时记R=E.目 录5 由定义可见,R(u,v)反映了u对于v的相关程度,若R(u,v)越接近于1,则u与v对R的关系越密切;若R(u,v)越接近于0,则u与v对R的关系越稀疏.特别地,当R(u,v)0,1时,与u与v对R具有明确关系.因此,模糊关系是普通关系的推广,它能从更深刻的意义上表现出事物的更广泛的联系.定义定义 设U=u1,u2,um,V=v1,v2,vn,RF(UV),则可以用一个mn阶矩阵来表示,即R=(rij)mn,其中rij=R(ui,vj)(i=1,2,m;j=1,2,n),由于R(ui,vj)0,1,故称R=(rij)mn为模糊矩阵模糊

4、矩阵.由于0,1 0,1,故模糊矩阵是Boole矩阵的推广.6 例例1 设设x,y为汽车，则为汽车，则“x比比y好好”这种关系就是模糊关这种关系就是模糊关系系例例2 设设x,y指人，则指人，则“x和和y 相象相象”这种关系也是模糊关系这种关系也是模糊关系例例3：设设:若X是指实数轴,则“x比y大得多”隶属度函数隶属度函数:7 例例 设身高论域设身高论域X=140,150,160,170,180(单位：单位：cm),体重论域体重论域Y=40,50,60,70,80(单位：单位：kg),下表给出了身高与体重的模糊关系下表给出了身高与体重的模糊关系.405060708014010.80.20.101

5、500.810.80.20.11600.20.810.80.21700.10.20.810.818000.10.20.8183.1.3 模糊关系的运算模糊关系的运算 由于模糊关系RF(UV),故模糊关系的运算其实就是模糊集合的运算,有关模糊集合的一切性质对模糊关系来说都成立.定义定义 设R,Q 为U到V的两个模糊关系,则 (1)称RQ为R与Q的并,其相关函数为(RQ)(u,v)=R(u,v)Q(u,v),(u,v)UV.(2)称 RQ为R与Q的交,其相关函数为(RQ)(u,v)=R(u,v)Q(u,v),(u,v)UV.(3)称R 为R的补,其相关函数为R(u,v)=1R(u,v),(u,v)

6、UV.目 录9 (4)称RTF(VU)为R的转置,其相关函数为RT(v,u)=R(u,v),(u,v)UV.(5)对0,1,称R=(u,v)UV|R(u,v).为R的 截关系截关系;而称RS=(u,v)UV|R(u,v).为R的 强截关系强截关系.(6)对0,1,称R为数与模糊关系R的模糊截积关系,其相关函数为(R)(u,v)=R(u,v),(u,v)UV.103.1.2 模糊关系与模糊关系与模糊模糊矩阵矩阵 下面介绍模糊转置关系的运算 定理定理 设R,QF(UV)则有 (1)复原律:(RT)T=R;(2)交换律:(RQ)T=RTQT,(RQ)T=RTQT;(3)单调性:RQ RT QT;(4

7、)0,1,(RT)=(R)T,(RT)S=(R S)T;(5)(RT)=(R)T.目 录11 例例 设U=u1,u2,u3,R,QF(UU),且目 录12 定义定义 设RF(UV),QF(VW),则对R,Q的合成RQ F(UW),定义为 RQ(u,w)=vV R(u,v)Q(v,w)(1)若RF(UU),则记R0=I,Rn=Rn-1 R (n=1,2,);(2)若R=(rij)mn ,Q=(qjk)nl,则RQ=(pik)ml,其中即pik为R中第i行的元素与Q中第k列的元素对应取小后再取大而得到.目 录13 例例 设U=u1,u2,u3,u4 为生产资料商品集,V=v1,v2为两种消费品的集

8、合,W=w1,w2,w3为三个市场的细分,以R表示U到V的原料供应关系,以Q表示V到W的市场占有关系.若取试求生产资料对市场的间接占有关系RQ.14解解:由定义3.1.6(2)知15 下面介绍模糊合成运算的一些基本性质 定理定理 设P,Q,R为三个模糊关系,且可进行合成运算,则有 (1)结合律:R(Q P)=(R Q)P (2)分配律:(RQ)P=(R P)(QP),P(RQ)=(P R)(P Q);(3)单调性:RQ R P QP (4)(RQ)P (R P)(QP),P(R Q)(P R)(P Q).注注3.1.1:定理3.1.2(4)中两个式子的等号一般不成立.目 录16 例如例如:取则

9、 故(RQ)P (R P)(QP)注注 对于合成运算来说,不满足交换律.例如例如 取故R Q QR .目 录17定理定理 设RF(UV),QF(VW),则(1)(R Q)T=Q T R T;(2)若RF(UU),则(R n)T=(R T)n,n N.定理定理 设RF(UV),QF(VW),0,1,有(1)(R Q)S=RS QS;(2)R Q (R Q)(3)若V为有限论域,则(R Q)=R Q.定理定理 设RF(UV),QF(VW),则 R Q=0,1(R Q).183.2 模糊等价关系及其性质模糊等价关系及其性质 3.2.1 模糊关系的自反性模糊关系的自反性 定义定义 设RF(UU),则

10、(1)R称为自反的,如果I R,即uU,R(u,u)=1;(2)称包含R的最小的自反模糊关系为R的自反闭包,记作r(R).例例 设U=u1,u2,u3,RF(UU),且则R为自反模糊矩阵.目 录19 定理定理 设RF(UU),则下列结论成立;(1)若R是自反的,则nN,Rn Rn+1 且Rn也是自反的;(2)R是自反的当且仅当0,1,R 是自反的;(3)r(R)=R I.3.2.2 模糊关系的对称性模糊关系的对称性 定义定义 设RF(UU),则 (1)R称为对称的,如果RT=R ;(2)称包含R的最小的对称模糊关系为R的对称闭包,记作S(R).20 例例 设U=(,),RF(UU),且 R(u

11、,v)=e|u+v|,(u,v)UU,则R为U上的对称模糊关系.显然,有限论域上的对称模糊关系可用对称模糊矩阵来表示.例如例如 设U=u1,u2,u3,RF(UU),且则R为U上的对称模糊矩阵.目 录21 定理定理 设R,QF(UU),则下列结论成立:(1)R是对称的当且仅当 0,1,R 是对称的 (2)若R是对称的,则nN,Rn也是对称的 (3)若R,Q是对称的,则 R Q为对称的当且仅当R Q=Q R (4)S(R)=RRT 223.2.3 模糊关系的传递性模糊关系的传递性 定义定义 设RF(UU),则 (1)R称为传递的,如果R R R (2)称包含R的最小的传递模糊关系为R的传递闭包,

12、记作t(R).例例 设U=u1,u2,u3,RF(UU),且则R2=R,故R是传递的模糊矩阵.目 录23定理定理 设RF(UU),则下列结论成立:(1)R为传递的当且仅当0,1,R 为传递的(2)若R为传递的,则nN,Rn也为传递的;(3)24因对任意固定的k,有目 录25 定理定理 设U=u1,u2,un,RF(UU),则有 (1)(2)若R是自反的,则mn,有t(R)=Rm 由此可见,当R为自反模糊关系时,必有自然数mn,使t(R)=Rm 下面介绍一种快速求一种快速求m的方法的方法-平方自合成法平方自合成法:第一步第一步:R R=R2 R,则t(R)=R;否则,进行如下第二步.第二步第二步

13、:R2 R2=R4 R2,则t(R)=R2;否则,进行如下第三步.第三步第三步:R4 R4=R8 R4,则t(R)=R4;否则,进行如下一步,如此继续下去,必有自然数k,使2k-1 2 m41(3)对=i(i=1,2,m),求出t(R)的-截矩阵然后按t(R)进行分类,所得到的分类就是在水平上的等价分类,具体聚类原则为:若 ,则在水平上将对象ui和对象uj归为同一类.(4)画动态聚类图 为了能直观地看到被分类对象之间的相关程度,通常将t(R)中所有互不相同的元素=i(i=1,2,m)水平上的等价分类画在同一个图上,即得动态聚类图.目 录42 例例 考虑某环保部门对该地区五个环境区域U=u1,u

14、2,u3,u4,u5,按污染情况进行分类,设每个区域包含空气、水分、土壤、作物四个要素,环境区域的污染情况有污染物在四个要素中的含量超过的程度来衡量。设这五个环境区域的污染数据为 u1=(80,10,6,2),u2=(50,1,6,4),u3=(90,6,4,5),u4=(40,5,7,3),u5=(10,1,2,4)试用模糊传递闭包法对U进行分类。43 解解:由题设知特性指标为污染物在空气、水分、土壤、作物这四个要素中的含量.其特性指标矩阵为 (1)数据规格化 采用最大值规格化,作变换把U*规格化为目 录44(2)构造模糊相似矩阵R=(rij)55 采用最大最小法,即确定模糊相似矩阵为45(

15、3)利用平方合成法求t(R)因为 而R8=R4 ,所以(4)选取适当的置信水平值0,1,按截矩阵进行t(R)动 态聚类 首先把t(R)中的元素从大到小排序为10.700.63 0.62 0.53目 录46取=1,得根据分类原则,U被分成五类:u1,u2,u3,u4,u5.取=0.70,得因为 根据分类原则,U被分成四类:u1,u2,u4,u3,u5.取=0.63,得因为根据分类原则,被分成三类:u1,u2,u4,u3,u5.同理可得,取=0.62,可得U被分成二类:u1,u2,u3,u4,u5.取=0.53,可得U被分成一类:u1,u2,u3,u4,u5.目 录47(5)画动态聚类图目 录48

16、2.直接聚类法直接聚类法(1)将模糊相似矩阵中的所有不同的元素从大到小 排序,设为1=1 2 m(2)选取=k(k=1,2,m)直接在R上找出k水平上 的相似类.并进行归并,即得到k水平上的等价 分类.寻找相似类和归并的原则:若rijk,则将ui与uj分为同一类,设B1,B2是k水平上的两个类,若B1B2,则称它们为相似的,将所有相似类的类合成一类,最后得到的分类就是k水平上的等价分类.(3)画动态聚类图49 例例 利用直接聚类法对例中给出的环境区域 U=u1,u2,u3,u4,u5,进行等价分类.解解:由例知模糊相似矩阵为 (1)将R中的元素进行排序为 10.70 0.63 0.62 0.5

17、60.55 0.54 0.53 0.380.370.24(2)取取=1,因相似程度为1的元素只有自己,故U被分成五类:u1,u2,u3,u4,u5.取取=0.70,因r24=r42=0.70,故得相似类为 u2,u4,u1,u2,u3,u4,u5.50将所有相似的类合并成一类,即得等价类为:u2,u4,u1,u3,u5.取取=0.63,因r14=r41=0.63,故得相似类为 u2,u4,u1,u4,u1,u3,u5.将所有相似的类合并成一类,即得等价类为:u1,u2,u4,u3,u5.取取=0.62,因r13=r31=0.62,故得相似类为 u1,u3,u1,u2,u4,u3,u5.将所有相

18、似的类合并成一类,即得等价类为:u1,u2,u3,u4,u5.同理可得同理可得,当=0.56,0.55,0.54时所有的等价类与=0.62的等价类相同.取取=0.53,因r25=r52=0.53,故得相似类为 u2,u5,u1,u2,u3,u4,u5.将所有相似的类合并成一类,即得等价类为:u1,u2,u3,u4,u5.目 录51 由此可见,利用模糊传递闭包法和利用直接聚类法所得到的等价类是一致的。3.最大树法最大树法 (1)以所有被分类的对象为顶点。(2)当rij 0时,将顶点ui与顶点uj用一条线连接起来,并在线 段上注明相关程度rij,具体画法如下:首先画出顶点集中处的某个顶点ui,然后

19、按rij从大到小的 顺序依次连边,并在线段上注明相关程度rij,在连边时要求不产生回路,不出现相交线,直到所有对象连通为止。这样就得到一棵最大树(注:由于连边方法不唯一,从而这种最大树不是唯一的)。(3)适当选取0,1,砍去线段上值小于的连线,剩下互相连通的对象归为同一类。这样就可得到在水平上的一种等价分类。(4)画出动态聚类图。目 录52 例例 利用最大树法对例中给出的环境区域U=u1,u2,u3,u4,u5,进行等价分类 解解:(i)构造一棵最大树 首先将例中的模糊相似矩阵R中的元素从大到小进行排序为10.70 0.63 0.62 0.560.55 0.54 0.53 0.380.370.

20、24 然后根据构造最大树的方法可得一棵最大树为53 (ii)进行等价分类 取=1,切掉线段上值小于1的连线,得到图3.4.3,这时U被分为五类:u1,u2,u3,u4,u5.取=0.70,切掉线段上值小于0.70的连线,得到图3.4.4,这时U被分为四类:u2,u4,u1,u3,u5.取=0.63,切掉线段上值小于0.63的连线,得到图3.4.5,这时U被分为三类:u1,u2,u4,u3,u5.目 录54 取=0.62,切掉线段上值小于0.62的连线,得到图3.4.6,这时U被分为二类:u1,u2,u3,u4,u5.取=0.53,切掉线段上值小于0.53的连线,得到图3.4.7,这时U被分为一

21、类:u1,u2,u3,u4,u5.由此可见,利用最大树法进行等价分类与利用模糊闭包法是一致的。(iii)画动态聚类图(与图一致)目 录554.编网法编网法 (1)适当选取0,1,求出截矩阵R,且去掉R的主对角线右上半部分的所有元素;(2)将主对角线上的”1”对应地用其对象ui的标号i来代替；(3)将主对角线左下方的”0”去掉,而用”代替”1”,而称所在的位置为结点;(4)用竖直线与横直线将结点与对角线上的序号连接,即编网。通过如此打结而连接的对象归为同一类,从而实现了等价分类；(5)画动态聚类图。56 例例 利用编网法对例中给出的U=u1,u2,u3,u4,u5,进行分类.解解 见教材.注注:

22、在应用模糊等价矩阵聚类分析方法解决实际问题时,有两点是值得注意的:1.如何选择计算相关程度rij=R(ui,uj)的合运算子?因为一般来说,当选择不同的算子计算rij时,所得到的模糊分类可能也不同。2.如何选择最佳的置信水平i进行等价分类?因为应用模糊等价矩阵进行分类的类数取决于i的选择。在教材中,我们介绍了利用传递偏差选择最佳计算相关程度rij的算法,以及利用-偏差度选择最佳置信水平i的算法.目 录573.5 基于目标函数的模糊基于目标函数的模糊ISODATA聚类分析聚类分析3.5.1 普通分类普通分类 设被分类对象集为U=u1,u2,un,其中每个对象有m个特性指标,设为ui=(ui1,u

23、i2,uim)如果要把U分成c类(2cn),则分法不唯一,且每种分法都对应一个cn阶的Boole矩阵,这里R=(rij)cn,例如例如:设U=u1,u2,u3,u4,u5,把U分成如下三类u1,u4,u2,u5,u3 则对应的分类矩阵为目 录58此矩阵有如下特性 反之,任一满足上述三条特性的Boole矩阵R都对应着一种分类.例如例如:对应的分类为:u2,u4,u3,u5,u1 593.5.2 模糊分类模糊分类 在实际问题中，对象uiU往往不是严格地归属于某一类,而是以一定的隶属度隶属于某一类,因此,每一类可认为是U上的一个模糊子集.如果对象集U被分成c类,则每一种分类结果对应的矩阵是一个模糊矩

24、阵,即R=(rij)cn其中rij(i=1,2,c;j=1,2,n)满足下列三条性质 反之,任一满足上述三条性质的矩阵R都对应着U的一种模糊分类.于是,研究模糊分类问题可归结为研究满足上述三条性质的模糊矩阵问题.目 录60记Mfc为所有满足上诉三条性质的模糊矩阵的集合,即Mfc=RVcn|R满足性质(1),(2),(3),称Mfc为对象集U被分成c类的模糊分类空间模糊分类空间.显然Mc Mfc Vcn 现在我们要解决的问题是:如何由特性指标矩阵U=(uij)nm出发寻找在一定条件下最佳的模糊分类矩阵R,使与R对应的模糊分类为最佳分类?613.5.3 模糊ISODATA聚类分析法 设要求将对象集

25、U分成c类(2cn),则每一类都对应着一个聚类中心向量,记为Vi=(vi1,vi2,vim),(i=1,2,c),以Vi作为行所构成的矩阵称为聚类中心矩阵V,即 为了获得一个最佳的模糊分类,可以按照下列聚类准则,从模糊分类空间Mfc 中优选一个最佳模糊分类.聚类准则:求出适当的模糊分类矩阵及聚类中心矩阵V,使目标函数达到极小值,这里q为参数(一般可取q=2),而|uk-Vi|表示对象uk与第i类聚类中心向量Vi的距离.1977年,证明了:当q1,ukVi时可以通过如下模糊ISODATA算法进行迭代运算,而求出最佳模糊分类矩阵R和最佳聚类中心向量Vi,具体方法如下:1.求最佳模糊分类矩阵和最佳聚

26、类中心矩阵第一步:选定分类数c(2cn),取一初始模糊分类矩阵R(0)=(rij(0)cnMfc,逐步迭代,l=0,1,2,目 录623.5.3 模糊ISODATA聚类分析法第二步:对于R(l),计算聚类中心矩阵V(l)=(v1(l),v2(l),vc(l)这里Vi(l),可按下式计算第三步:修正模糊分类矩阵R(l),取第四步 比较R(l)与R(l+1)若对取定的精度0,有max|rik(l+1)rik(l)|则R(l+1)和V(l)即为所求,即R=R(l+1),V=V(l),停止迭代;否则,l=l+1回到第三步,重复进行.一般说来,应用上述算法得到的模糊分类矩阵R(l+1)和V(l),是相对

27、于分类数c,初始模糊分类矩阵R(0),和参数q的局部最优解.目 录633.5.3 模糊ISODATA聚类分析法2.模糊聚类 在求出满足所要求的最佳模糊分类矩阵和最佳聚类中心矩阵之后,可按下列两个判别原则来进行分类.(1)利用最佳模糊分类聚类判别原则:设求的的最佳模糊分类矩阵为ukU在R的第k列中,如果rik=maxr1k,r2k,rck 则将对象uk归于第i类,即对象uk对哪一类的隶属度最大就将它归到哪一类.(2)利用最佳聚类中心向量聚类判别原则:设求得的最佳模糊中心矩阵为V =(V1,V2,Vc)TukU,如果|uk-Vi|=min|uk-V1|,|uk-V2|,|uk-Vc|,则将对象uk归于第i类,即对象uk与哪一个聚类中心向量最靠近,就将它归到哪一类目 录643.5.4 聚类效果的检验 由于应用模糊ISODATA方法获得的模糊聚类是相对于分类数c,初始模糊分类矩阵R(0),误差和参数q的局部最优解.如果改变c,R(0),和q则可以得到许多局部最优解.如何从这些局部最优解中选出最佳的呢?这就需要有鉴别指标.下面接好两个聚类效果的方法.1.利用分类系数进行检验考虑分类系数由于当R Mc时,Fc(R)=1,故Fc(R)愈接近于1,聚类效果愈好.2.利用平均模糊熵进行检验考虑平均模糊熵由于R Mc时,Hc(R)=0,故Hc(R)当越接近于0,聚类效果越好.目 录65