第三章模糊关系精选PPT.ppt

《第三章模糊关系精选PPT.ppt》由会员分享，可在线阅读，更多相关《第三章模糊关系精选PPT.ppt（101页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、重的论域为 V=40，50，60，70，80 单位：公斤 表示身高与体重之间的相互关系。标准体重关系：体重（kg）=身高（cm）-100cm。模糊关系的表示：图、表、函数、矩阵第5页，本讲稿共101页上述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.0第6页，本讲稿共101页例：用矩阵表示模糊关系 U，V有限论域，用矩阵R来表示：，显然 R叫模糊矩阵：第7页，本讲稿共101页例：用函数表示关系 表示实数域上“远远大于的

3、关系”第8页，本讲稿共101页例：二人博弈具有相同的策略集。U=V=石头，剪刀，布 ，胜为1，平为0.5，负为0第9页，本讲稿共101页用图表示关系：石剪布布剪石布布剪剪石石第10页，本讲稿共101页对于同一论域上：布剪石第11页，本讲稿共101页 2 模糊矩阵的运算设 表示全体n行m列的模糊矩阵。对任意 ：定义：分别叫做R与S的并，交，R的余矩阵。第12页，本讲稿共101页例：则：若 对所有i，j成立，则称R=S。第13页，本讲稿共101页模糊矩阵满足下列性质：性质1 交换律：性质2 结合律：第14页，本讲稿共101页性质3 分配律：性质4 幂等律：第15页，本讲稿共101页性质5 吸收律：

4、性质6 复原律：第16页，本讲稿共101页 记第17页，本讲稿共101页性质7第18页，本讲稿共101页 称S包含R记 。如果对任意（i，j）都有 。性质8性质9 第19页，本讲稿共101页性质10 若 ，则第20页，本讲稿共101页性质11 记 若 必有 即 对任意 ，记 其中第21页，本讲稿共101页 称 为R的 截矩阵。其所对应的关系叫 的截关系。例 则 第22页，本讲稿共101页性质14 证明：取 第23页，本讲稿共101页性质15 证：第24页，本讲稿共101页 3 模糊关系的合成普通关系的合成 U：人群，Q：兄弟，R：父子，S：叔侄 三个关系中有这样的联系：x是z的叔叔 至少有一个

5、 ，使y是x的哥哥 而且y是z的父亲 我们称叔侄关系是弟兄关系对父子关系的合成。记：叔侄=弟兄父子合成关系第25页，本讲稿共101页 一般地，设 若：则称关系S是关系Q对R的合成，记做 有第26页，本讲稿共101页 用特征函数来表示，有 由此，可以给出模糊关系合成的定义。第27页，本讲稿共101页定义3.2 设 所谓 对 的合成,是指从U到W的一个模糊关系,记做 ，它具有隶属函数 当 ，记第28页，本讲稿共101页 对于有限论域:定义模糊矩阵的乘积定义3.3 (模糊矩阵乘积)：设 ，则定义 ，使有第29页，本讲稿共101页 S叫矩阵Q对R的合成，也称Q对R的模糊乘积。性质16 对模糊矩阵有 证

6、：设 则 第30页，本讲稿共101页 第31页，本讲稿共101页 故 第32页，本讲稿共101页性质17 模糊乘法满足结合律性质18 第33页，本讲稿共101页 证：设 有 第34页，本讲稿共101页性质18a 例：第35页，本讲稿共101页性质19 第36页，本讲稿共101页性质20定义3.4 1）叫自反关系，如果 2）叫作自反矩阵，如果 第37页，本讲稿共101页 3）包含R而有被任何包含R的自反矩阵所包含的自反矩阵，叫做R的自反闭包。记 由自反闭包的定义可知：a)；b)；c)任意包含R的自反矩阵Q都满足；第38页，本讲稿共101页性质21 第39页，本讲稿共101页 4 倒置关系与转置矩

7、阵 定义3.5 设 ，所谓 的倒置 是指：兄弟”关系是“弟兄”关系的倒置关系，“信任”是“被信任”的倒置关系。第40页，本讲稿共101页定义3.6 称 ，是U中的对称关系，如果 是对称关系，且仅当 “朋友”是对称关系。“差异”是对称关系。“父子”就不是对称关系。第41页，本讲稿共101页定义3.7 设 称 是R的转置矩阵，如果 称R为对称矩阵，如果 且有性质22 第42页，本讲稿共101页 性质23 性质24 性质25 第43页，本讲稿共101页 性质26 证明：设 第44页，本讲稿共101页 故 又 第45页，本讲稿共101页性质27 对任意 必为对称，且被所有包含R的对称矩阵所包含。证：故

8、 是对称矩阵；又设Q是任意一个包含R的对称矩阵，故 有：第46页，本讲稿共101页 Q对称 故 故对称闭包 包含R而又被任何包含R的对称矩阵所包含的对称矩阵叫做R的对称闭包，记s(R)。其结果为：第47页，本讲稿共101页由对称闭包的定义可知：a)；b)；c)任意包含R的对称矩阵Q都满足例：第48页，本讲稿共101页 第49页，本讲稿共101页 第50页，本讲稿共101页 第51页，本讲稿共101页 5 模糊关系的传递性普通关系中：RP（UU）称为是具有传递性的，若 (u，v)R，(v，w)R(u，w)R定义3.8(模糊关系的传递性):设 若对任意的0,1均有 称 是具有传递性的。第52页，本

9、讲稿共101页传递性的充分必要条件是：证：任给 ，取 显然 由定义3.8知 从而 第53页，本讲稿共101页 显然成立 上式定理的右端乃是 ,故可得 或 传递关系是指：它包含着它与它自己的合成。第54页，本讲稿共101页定义3.9：设 ，称R是传递矩阵，如果满足 .传递关系的性质：性质1：若 和 是传递的，则 也是传递的。证：和 是传递的,第55页，本讲稿共101页 第56页，本讲稿共101页 是传递的。性质2：若 是传递的，也是传递的。证：是传递的 第57页，本讲稿共101页 也是传递的。第58页，本讲稿共101页传递闭包：包含R而又被任意包含R的传递矩阵所包含的传递矩阵，叫做R的传递闭包。

10、记t(R)由传递闭包的定义可知：a)；b)；c)任意包含R的对称矩阵Q都满足 第59页，本讲稿共101页性质28：对任意的 ，总有 证：t(R)具有传递性RRR；t(R)基于R产生 第60页，本讲稿共101页第61页，本讲稿共101页 传递关系的性质：性质1 若 和 是传递的，则 也是传递的。证：是传递的，第62页，本讲稿共101页性质2 若 是传递的，也是传递的。证：是传递的 也是传递的 第63页，本讲稿共101页 2）设Q是任意包含R的传递矩阵 又Q是传递矩阵 由于k的任意性知 第64页，本讲稿共101页引理3.1 设 则 证明：一般情况下第65页，本讲稿共101页 当mn时，上式右端的足

11、码必有重复出现；当mn时，上式足码i,j1,j2,.jm-1k(m+1)个，不同的足码只能有n个。于是 即 当mn 第66页，本讲稿共101页例:已知 ，求传递闭包 。解：第67页，本讲稿共101页第68页，本讲稿共101页 6 相似矩阵相似矩阵：自反、对称的矩阵叫做相似矩阵。定理.1 设 为相似矩阵，则对于任意kn均有证明：（需证 ）R是自反的，（1in）则 故有 从而 当kn时 第69页，本讲稿共101页 又由定义 故 且相似矩阵求传递闭包的方法：需 便可得到传递闭包。n=30 需要5次便可得到。第70页，本讲稿共101页例：求相似矩阵的传递闭包第71页，本讲稿共101页 第72页，本讲稿

12、共101页 7 模糊等价关系普通的等价关系：同时具备自反、对称、传递三性的关系。普通的等价关系决定一个分类：彼此等价的元素同属一类。所谓U的一个分类是指：可将U分成若干个子集 使得定义3.10 叫做U上的一个模糊等价关系,如果它是自反、对称、传递的模糊关系，叫做等价矩阵，如果它是自反、对称、传递的模糊矩阵。第73页，本讲稿共101页定理3.2 是等价矩阵,当且仅当对任意 ,都是等价的布尔矩阵。证：R自反 自反 （显然）R对称 对称 若 ，不妨设 ，取 便有 从而 。（）显然。R传递传递 （由传递性定义）描述了一个普通等价关系。第74页，本讲稿共101页定理3.3 若01,则 所分出的每一个类必

13、是 所分出的某一类的子类。证:亦即:若i、j按 归为一类，则按 亦归为一类。从1降至0，分类由细变粗，逐步归并，形成一个动态的聚类图。设U=，第75页，本讲稿共101页 1）2）3）第76页，本讲稿共101页 R是等价矩阵。令由1降至0，写出 ，按 分类，i与j 归为同类 相应的分类，。第77页，本讲稿共101页 相应的分类 ，。相应的分类 ，。第78页，本讲稿共101页 相应的分类 ，。相应的分类 ，。第79页，本讲稿共101页 8 聚类分析定义：对事物按一定要求进行分类的数学方法，叫做聚类分析。聚类分析有许多方法，我们采用模糊等价关系进行聚类分析。一、等价聚类 步骤1：根据样本集合U中元素

14、的属性，建立模糊关系R。（将详细讨论）步骤2：求R的递归闭包t(R)，它就是R的模糊等价关系(需证明)步骤3：根据实际问题的要求，选定一个恰当的 ,求 就是普通的等价关系第80页，本讲稿共101页 步骤4：求出商集，它对应着U的一个划分,即是一种分类。定理：若 是相似矩阵，则t(R)=e(R),其中e(R)是R的等价闭包。e(R):包含R,而又被任一包含R的等价矩阵所包含的最小的等价矩阵 证明：1证明t(R)是等价的，a.所以t(R)是自反的；b.利用 即t(R)是对称的。第81页，本讲稿共101页 c.t(R)显然是传递的；所以t(R)是一等价矩阵。2证明 t(R)被任一Q所包含 证：设Q为

15、包含R的任一等价矩阵,故Q是传递的，3t(R)显然包含R 故t(R)=e(R)为等价闭包。第82页，本讲稿共101页二、模糊关系的建立-校定 设被分类的每一对象 由一组数据 来表征，则 的相似程度可按实际情况，从下列方式中选择一种来确定。1)数量积第83页，本讲稿共101页 2)夹角余弦 3)相关系数第84页，本讲稿共101页 4)指数相似系数 5)非参数方法第85页，本讲稿共101页 6)最大最小方法 7)算术平均最小方法第86页，本讲稿共101页 8)几何平均最小方法 9)绝对值指数方法第87页，本讲稿共101页 10)绝对值倒数方法 11)绝对值减数方法 12)主观评定法 打分第88页，

16、本讲稿共101页 例：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）第89页，本讲稿共101页 R是相似矩阵，不能直接分类，对它进行改造。是等价矩阵 第90页，本讲稿共101页三、聚类分析的其它方法1.直接聚类法 由此不需改造R直接根据聚类原则得到聚类图。聚类原则：ui和uj在 水平上同类 在R图中存在一条权重不低于 的路连接ui uj 例：设U=，表示父、子、女、邻居、母。第91页，本讲稿共101页取 和存在一条路；取 （，）（，）（，）存在路，故 取 第92

17、页，本讲稿共101页模糊关系图 在同一个论域中，一条路可以定义成一个元素序列 （s为有限数），元素可以重复出现，叫起点，终点。这条路是由下面这些箭头连接起来的：其中，每个箭头叫做一步，这条路由s-1步，s-1又叫它的长度。称为这步路的权重，一条路上最轻的一步 权重叫做路的权重。第93页，本讲稿共101页 两条路的起点和终点相同称两条路等效。一个模糊矩阵 对应着一个由n个元素及 个箭头所组成的带权图。对应图与R 对应图的差别，仅仅在于它的权重。在 图中每一个箭头的权重等于在R图中与它等效的二部路中最重要的一条二步路的权重。例：第94页，本讲稿共101页第95页，本讲稿共101页同理：在 图中，每

18、一步权重等于在 R图中与它等效的k步路径中最重要的一条路的权重。2、编网法 A取矩阵 ；B将对角线填入元素符号；C在对角线下方，以“*”取代1，以空格取代0；D将*所在位置称为结点，向对角线引经线（竖线）及纬线（横线）；E所谓编网是在每一个结点，将所经过经纬线捆绑起来，实现分类，通过打结而能互相联结的点属于同类。第96页，本讲稿共101页 例：第97页，本讲稿共101页 *第98页，本讲稿共101页3、最大生成树法 步骤1.建立模糊关系 ，由 得到模糊图 步骤2.求出图 的最大生成树 步骤3.对给出的 ，若小于则把树枝e去掉，得到的各连通分支就是 水平上的分类。例：第99页，本讲稿共101页采用破圈法得到G的最大生成树第100页，本讲稿共101页第101页，本讲稿共101页