第三章-模糊关系课件.ppt

1、 1 模糊关系的定义与性质 设U，V是两个论域，在普通集合论中，记 做与的笛卡尔乘积。可能状态集是由与中任意搭配所构成，笛卡儿乘积集是两集合元素之间的约束搭配。若给搭配以约束便体现了一种特殊关系。是笛卡儿集中的一个子集。 ( , ),UVu vuU vV 记 定义3.1定义(模糊关系)：称 的模糊子集 为从U到V的一个模糊关系，记作 称U到V的模糊关系为U中的（二元）模糊关系。()RUVRP U V VU RVUR 模糊关系 由其隶属函数 所刻画。 叫做 具有关系 的模糊程度。 例1 设身高的论域为 U=140，150，160，170，180 单位 ：厘米 :0,1RUVR00(,)Rv),(

2、00vuR 设体重的论域为 V=40，50，60，70，80 单位：公斤 表示身高与体重之间的相互关系 。标准体重关系：体重（kg）=身高（cm）-100cm。 模糊关系的表示：图、表、函数、矩阵R 上述U与V的关系可用表来表示 :40506070801401.00.80.20.10.01500.81.00.80.20.11600.20.81.00.80.21700.10.20.81.00.81800.00.10.20.81.0iuiv 例：用矩阵表示模糊关系 U，V有限论域， 用矩阵R来表示： ，显然 R叫模糊矩阵：R( ),ijRr01(1,)ijri jn(,)ijRijrv10.80.

3、20.100.810.80.20.10.20.810.80.20.10.20.810.800.10.20.81R 例：用函数表示关系 表示实数域上“远远大于的关系”120( , )1001()Rxyx yxyx yR(1,0)0.001R99. 0)1000 ,(R 例：二人博弈具有相同的策略集。 U=V=石头，剪刀，布 ，胜为1，平为0.5，负为00.51000.51100.5R石剪布石剪布 用图表示关系：石剪布布剪石010.50.50.51100布布剪剪石石0.50.50.5111 对于同一论域上：1布剪石110.50.50.5 2 模糊矩阵的运算 设 表示全体n行m列的模糊矩阵。对任意

4、： 定义： 分别叫做R与S的并，交，R的余矩阵。mn,n mR S( ),()ijijRrSs)(ijijsrSR)(ijijsrSR)1(ijcrR 例： 则： 若 对所有i，j成立，则称R=S。 8 . 04 . 03 . 05 . 0R7 . 03 . 05 . 08 . 0S8 . 04 . 05 . 08 . 0SR7 . 03 . 03 . 05 . 0SR8 . 06 . 03 . 05 . 0CRijijsr 模糊矩阵满足下列性质： 性质1 交换律： 性质2 结合律：RSSRRSSR)()(TSRTSR)()(TSRTSR 性质3 分配律： 性质4 幂等律：)()()(TSTR

5、TSR)()()(TSTRTSRRRRRRR 性质5 吸收律： 性质6 复原律：SSSR)(SSSR)(RRCC)( 记0000O零矩阵10.001.0.00.1I单位矩阵11.111.1.11.1E全矩阵性质70RR00R ERERREEAAC 称S包含R记 。 如果对任意（i，j）都有 。 性质8 性质9 SR ijijrsRSRSSRSRERO 性质10 若 ， 则11SR 22SR )()(2121SSRR)()(2121SSRR1212ijijijijrrss 性质11 记 若 必有 即 对任意 ，记 其中ccRSRS1,cijijrr ijijcss1ijijrs ijijsr11

6、ijcijcsrCCSR 1 , 0)(rRijijijijrrr当当01 称 为R的 截矩阵。其所对应的关系叫 的截关系。 例 则 RR4 . 06 . 00018 . 05 . 07 . 03 . 0R0100110106 .0R 性质14 证明： 取 0,1RSRS 11ijijijijijijRSrsrrss 0,1,ijijrs 11ijijijijijrrssr 性质15 证： SRSRSRSRijijijijrsrsRS或ijijijijrsrsRS且 3 模糊关系的合成 普通关系的合成 U：人群， Q：兄弟， R：父子， S：叔侄 三个关系中有这样的联系： x是z的叔叔 至少有

7、一个 ，使y是x的哥哥 而且y是z的父亲 我们称叔侄关系是弟兄关系对父子关系的合成。记： 叔侄=弟兄父子合成关系Szx),( , )x yQRzy),(y 一般地，设 若： 则称关系S是关系Q对R的合成，记做 有(),QP UV(),RP VW(U),SPW( ,)() ( , ),( ,)u wSvu vQ v wR RQS),( ,),)( | ),(RwvQvuvWURQ 用特征函数来表示，有 由此，可以给出模糊关系合成的定义。),(),(),(wvvuVvwuRQRQ 定义3.2 设 所谓 对 的合成,是指从U到W的一个模糊关系,记做 ，它具有隶属函数 当 ，记),(VUFQ),(WV

8、FRQRRQ),(),(),(wvvuwuRQVvRQ)(VUFRRRR2RRR1nn 对于有限论域 : 定义模糊矩阵的乘积 定义3.3 (模糊矩阵乘积)：设 ， 则定义 ，使有,1nuuU,1nvvV,1nwwWmnijqQ lmijrRlnRQS1()mikijjkjsqr S叫矩阵Q对R的合成，也称Q对R的模糊乘积。 性质16 对模糊矩阵有 证：设 则 RQRQSRQijijss1)(1ijijmjrq()ijijjqr (jkjkjqr 且）11ijjkjqr （且）1)(1jkijmjrq 故 10ijijss1()1mijjkjqr 1()0mijjkjqr 布尔阵1()mikij

9、jkjsqr 性质17 模糊乘法满足结合律 性质18 22)()(RRRRSRQSRQnmnmRRR)()()(SRSQSRQ)()()(RSQSRQS 证： 设 有 ,QRT Q SM R SN TSLjkijijjjkijmjiksrqstl)(1 ijjkijjkjqsrs ijjkijjkjjikikqsrsmn 性质18a 例： ()()()QRSQSRS()()()SQRS QS R6 . 05 . 04 . 03 . 0R4 . 06 . 03 . 05 . 0S7 . 04 . 05 . 02 . 0Q 性质19 5 . 04 . 04 . 03 . 0)()(QSQR5 .

10、04 . 03 . 03 . 0)(QSROORRORIRRI 性质20 定义3.4 1） 叫自反关系，如果 2） 叫作自反矩阵，如果 SRSQRQRSQSRQnnRQRQ)(VUFR1,uuRnnRIR 3）包含R而有被任何包含R的自反矩阵所包含的自反矩阵，叫做R的自反闭包。 记 由自反闭包的定义可知： a) ； b) ； c) 任意包含R的自反矩阵Q都满足 )(RrIRr)(RRr)(； )(RrQ 性质21 IRRr)( 4 倒置关系与转置矩阵 定义3.5 设 ，所谓 的倒置 是指： 兄弟”关系是“弟兄”关系的倒置关系，“信任”是“被信任”的倒置关系。 )(VUFRR()TRF VU(

11、,)(,)TRRv uu v 定义3.6 称 ，是U中的对称关系，如果 是对称关系，且仅当 “朋友”是对称关系。“差异”是对称关系。“父子”就不是对称关系。 )(UUFR( , )( , ),RRTu vu vu vUR( , )( , )TRRv uu v 定义3.7 设 称 是R的转置矩阵，如果 称R为对称矩阵，如果 且有 性质22 mnR()TTijm nRr(1,1)Tijijrrimjn mnRRRTRRTT 性质23 性质24 性质25 TTTQRSRTTTQRSRTTQRQRTTRR 性质26 证明：设 TTTQRRQnTTnRRSRQ()()TTTikkikjjijkijjjs

12、sqsqr()TTjkijjqr 故 又 TTTQRS22TTTTTRRRRRR211TtnTTnTnRRRRRRTNTTTnTRRRRRR21nTR 性质27 对任意 必为对称，且被所有包含R的对称矩阵所包含。 证： 故 是对称矩阵； 又设Q是任意一个包含R的对称矩阵 ，故 有： ,Tn nRRRTTTTTTRRRRRRTRR QR TTRQ Q对称 故 故 对称闭包 包含R而又被任何包含R的对称矩阵所包含的对称矩阵叫做R的对称闭包，记s(R)。其结果为：TQQTRQ()TRRQQQQ( )TS RRR 由对称闭包的定义可知： a) ； b) ； c) 任意包含R的对称矩阵Q都满足 例： )

13、()(RsRsTRRs)()(RsQ 7 . 05 . 03 . 01 . 08 . 04 . 03 . 02 . 06 . 06 . 07 . 01 . 0R4 . 05 . 06 . 03 . 01 . 09 . 0Q 0.10.70.60.50.60.90.10.60.20.30.60.30.30.60.40.80.10.40.60.50.40.30.50.70.50.5R Q5 .06 .03 .06 .05 .04 .06 .05 .0TQR 7 . 01 . 03 . 06 . 05 . 08 . 02 . 07 . 03 . 04 . 06 . 01 . 0TR4 . 06 .

14、01 . 05 . 03 . 09 . 0TQ0.10.60.40.30.90.30.50.70.20.80.50.10.60.40.60.30.10.7TTQR 5 . 06 . 03 . 06 . 05 . 04 . 06 . 05 . 0TTTRQQR 5 模糊关系的传递性 普通关系中：RP（UU）称为是具有传递性的，若 (u，v)R， (v，w)R (u，w)R 定义3.8(模糊关系的传递性): 设 若对任意的0,1均有 称 是具有传递性的。()RF UU,RRRu vv wu w R 传递性的充分必要条件是： 证： 任给 ，取 显然 由定义3.8知 从而 wvvuwuRRVvR,00

15、,RRu vv w0vV00,RRu vv wwuR,00,RRRu wu vv w0v由于 的任意性，定义成立。“” 显然成立 上式定理的右端乃是 ,故可得 或 传递关系是指：它包含着它与它自己的合成。 “”wuRR,wuwuRR,2RRR 定义3.9： 设 ，称R是传递矩阵，如果满足 . 传递关系的性质： 性质1： 若 和 是传递的，则 也是传递的。 证： 和 是传递的, nnRRR 21R2R12 RR1R2R121RR222RRQRSQ SR S SQRS QSR 1212 RRRR 11122122 RRRRRRRR 是传递的。 性质2： 若 是传递的， 也是传递的。 证： 是传递的

16、 2212122112 RRRRRRRR12 RRRnRR2RR222 nnRRRR RR 也是传递的。2nnRR2nnRRnR 传递闭包：包含R而又被任意包含R的传递矩阵所包含的传递矩阵，叫做R的传递闭包。记t(R) 由传递闭包的定义可知： a) ； b) ； c) 任意包含R的对称矩阵Q都满足 RRt)()()()(RtRtRt)(RtQ 性质28：对任意的 ，总有 证： t(R)具有传递性R RR ； t(R)基于R产生 n nR21( )nkkt RRRRR1111() ()kjkjkjkjRRRR 234RRR11kjkjRR 11kjkjR 345RRR23RR21RkkRRR传递

17、性矩阵包含 传递关系的性质： 性质1 若 和 是传递的，则 也是传递的。 证 ： 是传递的， 1R2R12RR1,2RR211RR222RR()()()()()()QRSQSRSSQRSQSR1212111221212212122112() ()()()() ()()()RRRRRRRRRRRRRRRRRRRR12RR21212()RRRR是传递的。 性质2 若 是传递的， 也是传递的。 证： 是传递的 也是传递的 RnRR2RRnR22()()nnnnRRRR222nnRRRR RR 2）设Q是任意包含R的传递矩阵 又Q是传递矩阵 由于k的任意性知 kkQRQR23kkQQQQQR1kkQR

18、 引理3.1 设 则 证明： 一般情况下nnR1( )kkt RR11111111112112212(2)1(3)(2)11111()()()()nikijj kjnnnikijj kijijj kjjjnnijijjkjj 112112()111()jmmnnnmikijjjkjjj 当mn时，上式右端的足码必有重复出现； 当mn时，上式足码i,j1,j2,.jm-1k (m+1)个，不同的足码只能有n个。 于是 即 当mn ()( )1nmsikiks 1nmssRR1111( )()()nsiiiit nniit RRRRR 例: 已知 ，求传递闭包 。 解： 6 . 01 . 02 .

19、 02 . 09 . 04 . 07 . 05 . 01 . 0R)(Rt6 . 01 . 02 . 02 . 09 . 04 . 07 . 05 . 01 . 02RRR0.10.50.70.40.90.20.20.10.6 0.40.50.60.40.90.40.20.20.6 6 . 02 . 02 . 04 . 09 . 04 . 06 . 05 . 04 . 023RRR0.10.50.70.40.90.20.20.10.6 0.40.50.60.40.90.40.20.20.6 2R20.10.50.7( )0.40.90.20.20.10.6t RRR 0.40.50.60.40

20、.90.40.20.20.6 0.40.50.70.40.90.40.20.20.6 6 相似矩阵 相似矩阵：自反、对称的矩阵叫做相似矩阵。 定理.1 设 为相似矩阵，则对于任意kn均有 证明：（需证 ） R是自反的， （1in）则 故有 从而 当kn时 n nR( )kt RR( )( )kkt RRt RR且即可1ijr ijijiitjitnijrrrrrR122RR221(1)kkkkRRRRRRk1( )ntktt RRR 又由定义 故 且 相似矩阵求传递闭包的方法： 需 便可得到传递闭包。 n=30 需要5次便可得到。 kttRRRt1 kRRt kRRt kRRt242( )kR

21、RRRt R122kkn21logknk 1log2n 例：求相似矩阵的传递闭包1.00.20.50.80.21.00.70.40.50.710.60.80.40.61R 21.00.20.50.80.21.00.70.40.50.710.60.80.40.61R 1.00.20.50.80.2 1.00.70.40.50.7 10.60.80.40.6 1 1.0 0.5 0.6 0.80.5 1.0 0.70.60.6 0.7 1.0 0.60.8 0.6 0.6 1.0 41.00.50.60.80.51.00.70.60.60.71.00.60.80.60.61.0R 1.00.50.

22、60.80.51.00.70.60.60.71.00.60.80.60.61.0 1.00.60.60.80.61.00.70.60.60.71.00.60.80.60.61.0 81.00.60.60.80.61.00.70.60.60.71.00.60.80.60.61.0R 1.00.60.60.80.6 1.00.70.60.60.7 1.00.60.80.60.6 1.01.00.60.60.80.6 1.00.70.60.60.71.00.60.80.60.6 1.0 4t RR 7 模糊等价关系 普通的等价关系：同时具备自反、对称、传递三性的关系。 普通的等价关系决定一个分类：彼

23、此等价的元素同属一类。 所谓U的一个分类是指：可将U分成若干个子集 使得 定义3.10 叫做U上的一个模糊等价关系,如果它是自反、对称、传递的模糊关系， 叫做等价矩阵，如果它是自反、对称、传递的模糊矩阵。 tA tT(,)stAAsts t TUAtTtUUFRn nR 定理3.2 是等价矩阵,当且仅当对任意 , 都是等价的布尔矩阵。 证：R自反 自反 （显然） R对称 对称 若 ，不妨设 ，取 便有 从而 。 （）显然。 R传递传递 （由传递性定义） 描述了一个普通等价关系。 n nR0,1RRRjiijrr ijjirrijjirr0,1ijjirrijjirr()R R 定理3.3 若0

24、1,则 所分出的每一个类必是 所分出的某一类的子类。 证: 亦即: 若i、j按 归为一类，则按 亦归为一类。 从1降至0，分类由细变粗，逐步归并，形成一个动态的聚类图。 设U=， RuR11ijijijijrrrr11ijijrrRR 1） 2） 3）1.00.40.80.50.50.41.00.40.40.40.80.41.00.50.50.50.40.51.00.60.50.40.50.61.0R ,RI自反,TRR对称2,RR传递 R是等价矩阵。 令由1降至0，写出 ，按 分类，i与j 归为同类 相应的分类 ，。 21.00.40.80.50.50.41.00.40.40.40.80.4

25、1.00.50.50.50.40.51.00.60.50.40.50.61.0RR RR RR1ijr11000001000001000001000001R 相应的分类 ， ，。 相应的分类 ， ，。 0.81010001000101000001000001R 0.61010001000101000001000011R 相应的分类 ，。 相应的分类 ，。 0.51011101000101111011110111R 0.41111111111111111111111111RI 8 聚类分析 定义：对事物按一定要求进行分类的数学方法，叫做聚类分析。聚类分析有许多方法，我们采用模糊等价关系进行聚类分

26、析。 一、等价聚类 步骤1：根据样本集合U中元素的属性，建立模糊关系R。（将详细讨论） 步骤2：求R的递归闭包t(R)，它就是R的模糊等价关系(需证明) 步骤3：根据实际问题的要求，选定一个恰当的 ,求 就是普通的等价关系0,1R 步骤4：求出商集，它对应着U的一个划分,即是一种分类。 定理：若 是相似矩阵，则t(R)=e(R),其中e(R)是R的等价闭包。 e(R):包含R,而又被任一包含R的等价矩阵所包含的最小的等价矩阵 证明： 1证明t(R)是等价的， a. 所以t(R)是自反的 ； b. 利用 即t(R)是对称的。 n nR1( )nkkt RU rR1 ( )TnTKkt RU RT

27、nTTTnTRTRSRR和111 ( )( )TnnnKTKTKkkkt RU RURU Rt R c. t(R)显然是传递的； 所以t(R)是一等价矩阵。 2证明 t(R)被任一Q所包含 证： 设Q为包含R的任一等价矩阵, 故Q是传递的， 3t(R) 显然包含R 故t(R)=e(R)为等价闭包。 ( )Qt R 二、模糊关系的建立-校定 设被分类的每一对象 由一组数据 来表征，则 的相似程度可按实际情况，从下列方式中选择一种来确定。 1)数量积,ijuuiu12,iiimxxx11/mijikjkkijrxxMijmkjkikijxxMM1,max, 0 2)夹角余弦 3)相关系数mkjkm

28、kikmkjkikijxxxxr12121,12211mikijkjkijmmikijkjkkxx xxrxxxxmkjkjmkikixmxxmx111,1其中 4)指数相似系数 5)非参数方法mkSxxijkjkikemr143221为适当选定的函数kSiikikxxx令的个数中大于0,.,2211jmimjijixxxxxxn的个数小于0nnnnnrij 6)最大最小方法 7)算术平均最小方法mkjkikmkjkikijxxxxr11,max,minmkjkikmkjkikijxxxxr1121,min 8)几何平均最小方法 9)绝对值指数方法mkjkikmkjkikijxxxxr11,m

29、inmkjkikxxijer1 10)绝对值倒数方法 11) 绝对值减数方法 12) 主观评定法 打分jixxMjirmkjkikij当当1110ijrM常数，使111-mijikjkkijrCxxij 例：A=(5,5,3,2) B=(2,3,4,5) C=(5,5,2,3) D=(1,5,3,1) E=(2,4,5,1) 取论域U=A,B,C,D,E 按（11）方法建立相似关系（C=0.1） 16 . 01 . 04 . 03 . 06 . 013 . 02 . 05 . 01 . 03 . 011 . 08 . 04 . 02 . 01 . 011 . 03 . 05 . 08 . 01

30、 . 01R R是相似矩阵，不能直接分类，对它进行改造。 是等价矩阵 16 . 06 . 04 . 05 . 06 . 015 . 04 . 05 . 03 . 05 . 012 . 08 . 04 . 04 . 02 . 013 . 05 . 05 . 08 . 03 . 012R0 . 16 . 05 . 04 . 05 . 06 . 015 . 04 . 05 . 05 . 05 . 014 . 08 . 04 . 04 . 04 . 014 . 05 . 05 . 08 . 04 . 014R4R0.6 , , A CBD E 三、聚类分析的其它方法 1. 直接聚类法 由此不需改造R直

31、接根据聚类原则得到聚类图。 聚类原则： ui和uj在 水平上同类 在R图中存在一条权重不低于 的路连接ui uj 例： 设U=，表示父、子、女、邻居、母。( ( )()t Rt R1( )()nkkt RRRSRS10.80.60.10.20.810.80.20.850.60.8100.90.10.2010.10.20.850.90.10R 取 和存在一条路 ； 取 （，）（，）（，）存在路，故 取 0.1 0.10.20.80.90.80.90.850.8 模糊关系图 在同一个论域中，一条路可以定义成一个元素序列 （s为有限数），元素可以重复出现， 叫起点 ， 终点。这条路是由下面这些箭头连

32、接起来的： 其中，每个箭头叫做一步，这条路由s-1步，s-1又叫它的长度。 称为这步路的权重，一条路上最轻的一步 权重叫做路的权重。 123,iiiisuuuu1 iuisu1 22 3112231,i iiiisisrrriiiiisisuuuuuuiir 两条路的起点和终点相同称两条路等效。 一个模糊矩阵 对应着一个由n个元素及 个箭头所组成的带权图。 对应图与R 对应图的差别，仅仅在于它的权重。 在 图中每一个箭头的权重等于在R图中与它等效的二部路中最重要的一条二步路的权重。 例：n nR2n2R2R12120.20.30.50.1uuuRu121220.30.20.20.3uuuRu1

33、2120.20.30.50.1uuuu120.20.30.50.1uu1u1u1u2u2u2u0.30.30.20.20.1 同理：在 图中，每一步权重等于在 R图中与它等效的k步路径中最重要的一条路的权重。 2、编网法 A取矩阵 ； B将对角线填入元素符号； C在对角线下方，以 “*” 取代1，以空格取代0； D将*所在位置称为结点，向对角线引经线（竖线）及纬线（横线）； E所谓编网是在每一个结点，将所经过经纬线捆绑起来，实现分类，通过打结而能互相联结的点属于同类。kRR 例：10.10.80.50.30.110.10.20.40.80.110.30.10.50.20.310.60.30.4

34、0.10.61R 0.61010001000101000001100011R * * 3、最大生成树法 步骤1.建立模糊关系 ，由 得到模糊图 步骤2.求出图 的最大生成树 步骤3.对给出的 ，若小于则把树枝e去掉，得到的各连通分支就是 水平上的分类。 例：0,110.80.60.1 0.20.810.8 0.20.850.60.8100.90.10.2010.10.20.85 0.90.10R1v2v3v4v5v0.10.10.90.850.60.80.80.2GGRRT 采用破圈法得到G的最大生成树123 540.9( )0.9 T evvv vv将边去掉12 3 540.85 vv v vv1 2 3 540.8 v v v vv1v2v3v4v5v0.80.20.850.9