模糊数学2008-8等价关系与相似关系

1、吉林大学计算机科学与技术学院,1,模糊数学 8,孙舒杨 Email. ,吉林大学计算机科学与技术学院,2,作业答案,吉林大学计算机科学与技术学院,3,吉林大学计算机科学与技术学院,4,吉林大学计算机科学与技术学院,5,吉林大学计算机科学与技术学院,6,习题3-3,吉林大学计算机科学与技术学院,7,习题3-6,吉林大学计算机科学与技术学院,8,习题3-7,吉林大学计算机科学与技术学院,9,习题3-7答案,吉林大学计算机科学与技术学院,10,内容回顾,模糊等价关系（矩阵） 自反性 R (u,u)=1或IR 对称性 R(u,v)=R(v,u); 传递性 R2 R,吉林大学计算机科学与技术学院,11,

2、模糊等价矩阵的性质,若R为模糊等价矩阵，则 R= R2 = R3 = = Rn-1 = Rn 证明： 自反性： RR2 Rn-1 Rn 传递性: RR2Rn-1Rn,吉林大学计算机科学与技术学院,12,模糊等价矩阵的定理1,定理1. R是模糊等价矩阵 对于任何0,1，R是等价布尔矩阵。 证明： 对称性、自反性显然 传递性的证明见3.6节定理1,吉林大学计算机科学与技术学院,13,定理1的意义,模糊等价矩阵普通等价矩阵 普通等价矩阵普通等价关系 普通等价关系可以分类 当在0,1上变动时，得到不同的R, 从而得到不同的分类,吉林大学计算机科学与技术学院,14,模糊等价矩阵分类例,设U=u1, u2

3、, u3 ,u4, u5 求当 1，0.8，0.5，0.4时的聚类结果。,吉林大学计算机科学与技术学院,15,模糊等价矩阵的定理2,定理2. R nn是模糊等价矩阵，则对于任何, 0,1，且，R所决定的分类中的每个类都是R所决定的分类中的某个类的子类。 说明什么？ 越大，分类越细,吉林大学计算机科学与技术学院,16,动态聚类图,由1变到0的过程，是R的分类由细到粗的过程，从而形成了一个动态的聚类图。,吉林大学计算机科学与技术学院,17,3-8 模糊相似关系,吉林大学计算机科学与技术学院,18,模糊相似关系的定义,设RF(UU)，若R具有自反性和对称性，则称R为U上的一个模糊相似关系 例如：模糊

4、关系“熟悉”、“朋友”、“同学”等 模糊相似关系vs.模糊等价关系 没有了传递性的要求,吉林大学计算机科学与技术学院,19,为何研究模糊相似关系？,实际应用中，通常只能得到自反和对称矩阵（相似矩阵），模糊等价矩阵较为少见 Questions. 对具有相似关系的元素如何分类？ 相似矩阵可否改造为等价矩阵？,吉林大学计算机科学与技术学院,20,全新概念传递闭包,设A, , BF(UU)，若 为包含A的传递关系 即A且2 对于任何包含A的传递关系B，都有B 则称为A的传递闭包，记为t(A)= ,吉林大学计算机科学与技术学院,21,传递闭包是什么？,R的传递闭包t(R) 是包含R的最小的传递关系,吉林

5、大学计算机科学与技术学院,22,传递闭包的定理1,定理1. 设模糊矩阵 A nn ，则 其中，t(A)是传递闭包。,吉林大学计算机科学与技术学院,23,传递闭包定理1证明,吉林大学计算机科学与技术学院,24,传递闭包的定理2,定理2. 设模糊矩阵 A nn ，则 其中，t(A)是传递闭包。,吉林大学计算机科学与技术学院,25,定理2的意义,定理2说明，当R是n阶方阵时，至多用n次并运算，就可以得到R的传递闭包 定理2极大地简化了传递闭包的计算,吉林大学计算机科学与技术学院,26,内容回顾,模糊相似矩阵 自反性 对称性 传递闭包 传递性 模糊相似矩阵传递闭包模糊等价矩阵,吉林大学计算机科学与技术

6、学院,27,改造有理！,定理. 相似矩阵Rnn 的传递闭包是等价矩阵，且t(R)=Rn 证明：只需证明自反性和对称性 R自反 I RR2 Rn t(R)=k=1n Rk= Rn是自反的 对称性。R= RT(Rn)T= (RT)n = (Rn),吉林大学计算机科学与技术学院,28,模糊相似矩阵模糊等价矩阵,将相似矩阵改造成等价矩阵 只需求相似矩阵的传递闭包,吉林大学计算机科学与技术学院,29,可否更简单？t(R)=Rn,定理. 设Rnn 是模糊相似矩阵，则存在一个最小自然数k (kn)，使得传递闭包t(R)=Rk，对于任何自然数bk，都有Rb=Rk，此时，t(R)是模糊等价矩阵。,吉林大学计算机

7、科学与技术学院,30,平方法求传递闭包,从模糊相似矩阵R出发，依次求平 方： 当第一次出现Rk Rk =Rk时， Rk就是 所求的传递闭包t(R),吉林大学计算机科学与技术学院,31,时间复杂度,吉林大学计算机科学与技术学院,32,课堂作业,设 请问至多几次平方可以到达传递闭包？ 请给出传递闭包t(R),吉林大学计算机科学与技术学院,33,3-9 聚类分析,吉林大学计算机科学与技术学院,34,聚类分析,所谓聚类分析，就是用数学方法对事物进行分类 应用十分广泛 模糊数学产生之前，聚类分析是数理统计多元分析的一个分支 现实分类问题具有模糊性，例如“环境污染分类”、“岩石分类”等 用到模糊聚类分析,

8、吉林大学计算机科学与技术学院,35,分类问题,设U =u1, u2, , un 为待分类的全体对象，其中每个待分类对象由一组数据表征如下： 问题转化为：如何建立对象ui与uj之间的相似关系,吉林大学计算机科学与技术学院,36,何谓数据表征,例如，要对一些环境单元进行分类，判断它们的污染程度 每个环境单元包括四个要素：空气、水分、土壤、作物 环境单元的污染状况由污染物在四个要素中含量的超限度来描述 北京市东南郊环境污染治理，获北京市科技成果一等奖,吉林大学计算机科学与技术学院,37,五个环境单元,吉林大学计算机科学与技术学院,38,步骤1：建立模糊相似关系,如何建立对象ui与uj之间的相似关系？

9、 有许多方法，应用时根据实际情况，选择一种方法来求ui与uj的相似关系R(ui, uj)=rij 在“环境污染”的例子中，如何给出模糊相似矩阵？,吉林大学计算机科学与技术学院,39,建立相似矩阵,建立模糊相似矩阵的注意事项： rij0,1 自反 对称 “环境”例中，采用“绝对值减数法” 问：得到的相似矩阵的维数是多少？,吉林大学计算机科学与技术学院,40,模糊相似矩阵,吉林大学计算机科学与技术学院,41,步骤2：相似关系等价关系,步骤1得到的矩阵一般满足自反性和对称性 将模糊相似矩阵改造成模糊等价矩阵 平方法 求传递闭包,吉林大学计算机科学与技术学院,42,至多计算多少次？,模糊相似矩阵55

10、k=log25+1=2+1=3 最坏情况下，RR2R4R8，计算到R8,吉林大学计算机科学与技术学院,43,吉林大学计算机科学与技术学院,44,吉林大学计算机科学与技术学院,45,吉林大学计算机科学与技术学院,46,模糊等价矩阵,吉林大学计算机科学与技术学院,47,其他建立相似矩阵的方法,非常多！主要分为3类 相似系数法 距离法（绝对值减数法就是距离法之一） 主观法 在后面的附录中给出,吉林大学计算机科学与技术学院,48,聚类分析的步骤,建立初始矩阵 利用某个建立相似矩阵的方法，建立相似矩阵 利用平方法，相似矩阵等价矩阵 若相似矩阵的维数较大，需要多次自乘，工作量大,吉林大学计算机科学与技术学

11、院,49,直接聚类法,无需求相似矩阵的传递闭包 直接用相似矩阵进行聚类 有很多种直接聚类法 我们只讲其中一种,吉林大学计算机科学与技术学院,50,直接聚类法,取=1(最大值)，对每个ui,确定其相似类 取=0.8(次大值)，对每个ui,确定其相似类 取=0.6(第三大值)，对每个ui,确定其相似类 依此类推直到U归并到一类终止 得到聚类图,吉林大学计算机科学与技术学院,51,问题,相似矩阵直接聚类vs.等价矩阵聚类 看上去没有区别 有区别！ 对于一个固定的，等价矩阵聚类得到的等价类没有公共元素！,吉林大学计算机科学与技术学院,52,回忆等价矩阵聚类,设U=u1, u2, u3 ,u4, u5 求当 1，0.8，0.5，0.4时的聚类结果。,吉林大学计算机科学与技术学院,53,直接聚类法,对于一个固定的， 等价矩阵聚类得到的等价类没有公共元素！ 相似矩阵聚类得到的相似类则有公共元素，这是因为不具有“传递性” 直接聚类法把有公共元素的相似类归并为一类,吉林大学计算机科学与技术学院,54,用直接聚类法对“环境”例子聚类,吉林大学计算机科学与技术学院,55,课堂作业,吉林大学计算机科学与技术学院,56,著名聚类的例子,日本学者Tamura给出，在模糊数学中广泛使用 有三个家庭，共16人。每个家庭人数为4-7人。 每人提供一张照片，共计1