模糊数学2009-7（模糊等价关系）.pptVIP

吉林大学计算机科学与技术学院 模糊数学 7 孙舒杨 Email. sysun@ 作业答案 习题3-6 习题3-7 习题3-7答案 3-7 模糊等价关系及聚类图 模糊关系的三个概念 自反性 对称性 传递性 自反性 若模糊关系R满足R(u,u)=1或I?R，则称R具有自反性 模糊自反矩阵 rii = 1 例如： 自反矩阵的定理 定理. 设模糊矩阵 A ∈Mn×n是自反矩阵，则有 I ? A?A2 ? A3 ?…? An-1 ?An?… 证明: 对称性 若模糊关系R满足R(u,v)=R(v,u)，则称R具有对称性 模糊对称矩阵 rij = rji 例如： 传递性 若模糊关系R满足RоR?R，则称R具有传递性 模糊传递矩阵 模糊传递矩阵——例 模糊传递矩阵的定理 定理. 设模糊矩阵 Q ∈Mn×n是传递矩阵，则有 Q ?Q2 ? Q3 ?… ?Qn-1 ?Qn ?… 证明: 模糊等价关系 定义. 模糊关系R∈F(U×U) , 满足 （1）自反性：R (u,u)=1; （2）对称性：R(u,v)=R(v,u); （3）传递性：R2 ?R 则称R为模糊等价关系 模糊等价矩阵 若论域U是有限论域，则U上的模糊等价关系R可表示为模糊等价矩阵 模糊等价矩阵 自反性 rii = 1 对称性 rij = rji 传递性 R是否为模糊等价矩阵？ 设论域U={x1, x2}， 等价布尔关系 一个布尔矩阵具有如下特性，则称其为等价的布尔矩阵，对应一个普通的等价关系 自反性 对称性 传递性 模糊等价矩阵的性质 若R为模糊等价矩阵，则 R= R2 = R3 = … = Rn-1 = Rn 证明： 自反性： R?R2 ?…? Rn-1 ?Rn 传递性: R?R2?…?Rn-1?Rn 模糊等价矩阵的定理1 定理1. R是模糊等价矩阵? 对于任何λ∈[0,1]，Rλ是等价布尔矩阵。 证明： 对称性、自反性显然 传递性 定理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 ，则A的传递闭包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) 定理. 设R∈μn×n 为相似矩阵。则对于任意自然数m≥n, 都有t(R)=Rm 证明： R自反= I ? R?R2 ?… ?Rn t(R)=Rn ?Rm ? ∪k=1∞ Rk=t(R) 模糊相似矩阵?模糊等价矩阵 将相似矩阵改造成等价矩阵 只需求相似矩阵的传递闭包 可否更简单？t(R)=Rn 定理. 设R∈μn×n 是模糊相似矩阵，则存在一个最小自然数k (k≤n)，使得传递闭包t(R)=Rk，对于任何自然数b≥k，都有Rb=Rk