模糊数学2008-8(等价关系及相似关系).ppt

吉林大学计算机科学与技术学院 模糊数学 8 孙舒杨 Email. sysun@jlu.edu.cn 作业答案 习题3-3 习题3-6 习题3-7 习题3-7答案 内容回顾 模糊等价关系（矩阵） 自反性 R (u,u)=1或I?R 对称性 R(u,v)=R(v,u); 传递性 R2 ?R 模糊等价矩阵的性质 若R为模糊等价矩阵，则 R= R2 = R3 = … = Rn-1 = Rn 证明： 自反性： R?R2 ?…? Rn-1 ?Rn 传递性: R?R2?…?Rn-1?Rn 模糊等价矩阵的定理1 定理1. R是模糊等价矩阵? 对于任何λ∈[0,1]，Rλ是等价布尔矩阵。 证明： 对称性、自反性显然 传递性的证明见3.6节定理1 定理1的意义 模糊等价矩阵?普通等价矩阵 普通等价矩阵?普通等价关系 普通等价关系可以分类 当λ在[0,1]上变动时，得到不同的Rλ, 从而得到不同的分类 模糊等价矩阵分类——例 设U={u1, u2, u3 ,u4, u5 } 求当λ ＝1，0.8，0.5，0.4时的聚类结果。 模糊等价矩阵的定理2 定理2. R ∈ μn×n是模糊等价矩阵，则对于任何λ,μ ∈[0,1]，且λμ，Rμ所决定的分类中的每个类都是Rλ所决定的分类中的某个类的子类。 说明什么？ λ越大，分类越细 动态聚类图 λ由1变到0的过程，是Rλ的分类由细到粗的过程，从而形成了一个动态的聚类图。 3-8 模糊相似关系 模糊相似关系的定义 设R∈F(U×U)，若R具有自反性和对称性，则称R为U上的一个模糊相似关系 例如：模糊关系“熟悉”、“朋友”、“同学”等 模糊相似关系vs.模糊等价关系 没有了传递性的要求 为何研究模糊相似关系？ 实际应用中，通常只能得到自反和对称矩阵（相似矩阵），模糊等价矩阵较为少见 Questions. 对具有相似关系的元素如何分类？ 相似矩阵可否改造为等价矩阵？ 全新概念——传递闭包 设A, ?, B∈F(U×U)，若 ?为包含A的传递关系 即A??且?2? ? 对于任何包含A的传递关系B，都有??B 则称?为A的传递闭包，记为t(A)= ? 传递闭包是什么？ R的传递闭包t(R) 是包含R的最小的传递关系 传递闭包的定理1 定理1. 设模糊矩阵 A ∈ μn×n ，则 其中，t(A)是传递闭包。 传递闭包定理1证明 传递闭包的定理2 定理2. 设模糊矩阵 A ∈ μn×n ，则 其中，t(A)是传递闭包。 定理2的意义 定理2说明，当R是n阶方阵时，至多用n次并运算，就可以得到R的传递闭包 定理2极大地简化了传递闭包的计算 内容回顾 模糊相似矩阵 自反性 对称性 传递闭包 传递性 模糊相似矩阵?传递闭包?模糊等价矩阵 改造有理！ 定理. 相似矩阵R∈μn×n 的传递闭包是等价矩阵，且t(R)=Rn 证明：只需证明自反性和对称性 R自反? I ? R?R2 ? … ?Rn ?t(R)=∪k=1n Rk= Rn是自反的 对称性。R= RT?(Rn)T= (RT)n = (Rn) 模糊相似矩阵?模糊等价矩阵 将相似矩阵改造成等价矩阵 只需求相似矩阵的传递闭包 可否更简单？t(R)=Rn 定理. 设R∈μn×n 是模糊相似矩阵，则存在一个最小自然数k (k≤n)，使得传递闭包t(R)=Rk，对于任何自然数b≥k，都有Rb=Rk，此时，t(R)是模糊等价矩阵。 平方法求传递闭包 从模糊相似矩阵R出发，依次求平 方： 当第一次出现Rk ?Rk =Rk时， Rk就是 所求的传递闭包t(R) 时间复杂度 课堂作业 设 请问至多几次平方可以到达传递闭包？ 请给出传递闭包t(R) 3-9 聚类分析 聚类分析 所谓聚类分析，就是用数学方法对事物进行分类 应用十分广泛 模糊数学产生之前，聚类分析是数理统计多元分析的一个分支 现实分类问题具有模糊性，例如“环境污染分类”、“岩石分类”等 用到模糊聚类分析 分类问题 设U ={u1, u2, …, un }为待分类的全体对象，其中每个待分类对象由一组数据表征如下： 问题转化为：如何建立对象ui与uj之间的相似关系 何谓数据表征 例如，要对一些环境单元进行分类，判断它们的污染程度 每个环境单元包括四个要素：空气、水分、土壤、作物 环境单元的污染状况由污染物在四个要素中含量的超限度来描述 《北京市东南郊环境污染治理》，获北京市科技成果一等奖 五个环境单元 步骤1：建立模糊相似关系 如何建立对象ui与uj之间的相似关系？ 有许多方法，应用时根据实际情况，选择一种方法来求ui与uj的相似关系R(ui, uj)=rij 在“环境污染”的例子中，如何给出模糊相似矩阵？ 建立相似矩阵 建立模糊相似矩阵的注意事项： rij∈[0,1] 自