第三章-模糊关系.ppt

1 模糊关系的定义与性质设U，V是两个论域，在普通集合论中，记 做与的笛卡尔乘积。可能状态集是由与中任意搭配所构成，笛卡儿乘积集是两集合元素之间的约束搭配。若给搭配以约束便体现了一种特殊关系。是笛卡儿集中的一个子集。记 定义3.1定义(模糊关系)：称 的模糊子集 为从U到V的一个模糊关系，记作 称U到V的模糊关系为U中的（二元）模糊关系。模糊关系 由其隶属函数 所刻画。叫做 具有关系 的模糊程度。例1 设身高的论域为 U=140，150，160，170，180 单位：厘米 设体重的论域为 V=40，50，60，70，80 单位：公斤 表示身高与体重之间的相互关系。标准体重关系：体重（kg）=身高（cm）-100cm。模糊关系的表示：图、表、函数、矩阵上述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例：用矩阵表示模糊关系 U，V有限论域，用矩阵R来表示：，显然 R叫模糊矩阵：例：用函数表示关系 表示实数域上“远远大于的关系”例：二人博弈具有相同的策略集。U=V=石头，剪刀，布 ，胜为1，平为0.5，负为0用图表示关系：石剪布布剪石布布剪剪石石对于同一论域上：布剪石 2 模糊矩阵的运算设 表示全体n行m列的模糊矩阵。对任意 ：定义：分别叫做R与S的并，交，R的余矩阵。例：则：若 对所有i，j成立，则称R=S。模糊矩阵满足下列性质：性质1 交换律：性质2 结合律：性质3 分配律：性质4 幂等律：性质5 吸收律：性质6 复原律：记性质7 称S包含R记 。如果对任意（i，j）都有 。性质8性质9 性质10 若 ，则性质11 记 若 必有 即 对任意 ，记 其中 称 为R的 截矩阵。其所对应的关系叫 的截关系。例 则 性质14 证明：取 性质15 证：3 模糊关系的合成普通关系的合成 U：人群，Q：兄弟，R：父子，S：叔侄 三个关系中有这样的联系：x是z的叔叔 至少有一个 ，使y是x的哥哥 而且y是z的父亲 我们称叔侄关系是弟兄关系对父子关系的合成。记：叔侄=弟兄父子合成关系 一般地，设 若：则称关系S是关系Q对R的合成，记做 有 用特征函数来表示，有 由此，可以给出模糊关系合成的定义。定义3.2 设 所谓 对 的合成,是指从U到W的一个模糊关系,记做 ，它具有隶属函数 当 ，记 对于有限论域:定义模糊矩阵的乘积定义3.3 (模糊矩阵乘积)：设 ，则定义 ，使有 S叫矩阵Q对R的合成，也称Q对R的模糊乘积。性质16 对模糊矩阵有 证：设 则 故 性质17 模糊乘法满足结合律性质18 证：设 有 性质18a 例：性质19 性质20定义3.4 1）叫自反关系，如果 2）叫作自反矩阵，如果 3）包含R而有被任何包含R的自反矩阵所包含的自反矩阵，叫做R的自反闭包。记 由自反闭包的定义可知：a)；b)；c)任意包含R的自反矩阵Q都满足；性质21 4 倒置关系与转置矩阵 定义3.5 设 ，所谓 的倒置 是指：兄弟”关系是“弟兄”关系的倒置关系，“信任”是“被信任”的倒置关系。定义3.6 称 ，是U中的对称关系，如果 是对称关系，且仅当 “朋友”是对称关系。“差异”是对称关系。“父子”就不是对称关系。定义3.7 设 称 是R的转置矩阵，如果 称R为对称矩阵，如果 且有性质22 性质23 性质24 性质25 性质26 证明：设 故 又 性质27 对任意 必为对称，且被所有包含R的对称矩阵所包含。证：故 是对称矩阵；又设Q是任意一个包含R的对称矩阵，故 有：Q对称 故 故对称闭包 包含R而又被任何包含R的对称矩阵所包含的对称矩阵叫做R的对称闭包，记s(R)。其结果为：由对称闭包的定义可知：a)；b)；c)任意包含R的对称矩阵Q都满足例：5 模糊关系的传递性普通关系中：RP（UU）称为是具有传递性的，若 (u，v)R，(v，w)R(u，w)R定义3.8(模糊关系的传递性):设 若对任意的0,1均有 称 是具有传递性的。传递性的充分必要条件是：证：任给 ，取 显然 由定义3.8知 从而 显然成立 上式定理的右端乃是 ,故可得 或 传递关系是指：它包含着它与它自己的合成。定义3.9：设 ，称R是传递矩阵，如果满足 .传递关系的性质：性质1：若 和 是传递的，则 也是传递的。证：和 是传递的,是传递的。性质2：若 是传递的，也是传递的。证：是传递的 也是传递的。传递闭包：包含R而又被任意包含R的传递矩阵所包含的传递矩阵，叫做R的传递闭包。记t(R)由传递闭包的定义可知：a)；b)；c)任意包含R的对称矩阵Q都满足 性质28：对任意的 ，总有 证：t(R)具有传递性RRR；t(R)基于R产生 传递关系的性质：性质1 若 和 是传递的，则 也是传递的。证：是传递的，性质2 若 是传递的，也是传递的。证：是传递的 也是传递的 2）设Q是任意包含R的传递矩阵 又Q是传递矩阵 由于k的任意性知 引理3.1 设 则 证明：一般情况下 当mn时，上式右端的足码必有重复出现；当mn时，上式足码i,j1,j2,.jm-1k(m+1)个，不同的足码只能有n个。于是 即 当mn 例:已知 ，求传递闭包 。解：6 相似矩阵相似矩阵：自反、对称的矩阵叫做相似矩阵。定理.1 设 为相似矩阵，则对于任意kn均有证明：（需证 ）R是自反的，（1in）则 故有 从而 当kn时 又由定义 故 且相似矩阵求传递闭包的方法：需 便可得到传递闭包。n=30 需要5次便可得到。例：求相似矩阵的传递闭包 7 模糊等价关系普通的等价关系：同时具备自反、对称、传递三性的关系。普通的等价关系决定一个分类：彼此等价的元素同属一类。所谓U的一个分类是指：可将U分成若干个子集 使得定义3.10 叫做U上的一个模糊等价关系,如果它是自反、对称、传递的模糊关系，叫做等价矩阵，如果它是自反、对称、传递的模糊矩阵。定理3.2 是等价矩阵,当且仅当对任意 ,都是等价的布尔矩阵。证：R自反 自反 （显然）R对称 对称 若 ，不妨设 ，取 便有 从而 。（）显然。R传递传递 （由传递性定义）描述了一个普通等价关系。定理3.3 若01,则 所分出的每一个类必是 所分出的某一类的子类。证:亦即:若i、j按 归为一类，则按 亦归为一类。从1降至0，分类由细变粗，逐步归并，形成一个动态的聚类图。设U=，1）2）3）R是等价矩阵。令由1降至0，写出 ，按 分类，i与j 归为同类 相应的分类，。相应的分类 ，。相应的分类 ，。相应的分类 ，。相应的分类 ，。8 聚类分析定义：对事物按一定要求进行分类的数学方法，叫做聚类分析。聚类分析有许多方法，我们采用模糊等价关系进行聚类分析。一、等价聚类 步骤1：根据样本集合U中元素的属性，建立模糊关系R。（将详细讨论）步骤2：求R的递归闭包t(R)，它就是R的模糊等价关系(需证明)步骤3：根据实际问题的要求，选定一个恰当的 ,求 就是普通的等价关系 步骤4：求出商集，它对应着U的一个划分,即是一种分类。定理：若 是相似矩阵，则t(R)=e(R),其中e(R)是R的等价闭包。e(R):包含R,而又被任一包含R的等价矩阵所包含的最小的等价矩阵 证明：1证明t(R)是等价的，a.所以t(R)是自反的；b.利用 即t(R)是对称的。c.t(R)显然是传递的；所以t(R)是一等价矩阵。2证明 t(R)被任一Q所包含 证：设Q为包含R的任一等价矩阵,故Q是传递的，3t(R)显然包含R 故t(R)=e(R)为等价闭包。二、模糊关系的建立-校定 设被分类的每一对象 由一组数据 来表征，则 的相似程度可按实际情况，从下列方式中选择一种来确定。1)数量积 2)夹角余弦 3)相关系数 4)指数相似系数 5)非参数方法 6)最大最小方法 7)算术平均最小方法 8)几何平均最小方法 9)绝对值指数方法 10)绝对值倒数方法 11)绝对值减数方法 12)主观评定法 打分 例：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）R是相似矩阵，不能直接分类，对它进行改造。是等价矩阵 三、聚类分析的其它方法1.直接聚类法 由此不需改造R直接根据聚类原则得到聚类图。聚类原则：ui和uj在 水平上同类 在R图中存在一条权重不低于 的路连接ui uj 例：设U=，表示父、子、女、邻居、母。取 和存在一条路；取 （，）（，）（，）存在路，故 取 模糊关系图 在同一个论域中，一条路可以定义成一个元素序列 （s为有限数），元素可以重复出现，叫起点，终点。这条路是由下面这些箭头连接起来的：其中，每个箭头叫做一步，这条路由s-1步，s-1又叫它的长度。称为这步路的权重，一条路上最轻的一步 权重叫做路的权重。两条路的起点和终点相同称两条路等效。一个模糊矩阵 对应着一个由n个元素及 个箭头所组成的带权图。对应图与R 对应图的差别，仅仅在于它的权重。在 图中每一个箭头的权重等于在R图中与它等效的二部路中最重要的一条二步路的权重。例：同理：在 图中，每一步权重等于在 R图中与它等效的k步路径中最重要的一条路的权重。2、编网法 A取矩阵 ；B将对角线填入元素符号；C在对角线下方，以“*”取代1，以空格取代0；D将*所在位置称为结点，向对角线引经线（竖线）及纬线（横线）；E所谓编网是在每一个结点，将所经过经纬线捆绑起来，实现分类，通过打结而能互相联结的点属于同类。例：*3、最大生成树法 步骤1.建立模糊关系 ，由 得到模糊图 步骤2.求出图 的最大生成树 步骤3.对给出的 ，若小于则把树枝e去掉，得到的各连通分支就是 水平上的分类。例：采用破圈法得到G的最大生成树