模糊相似矩阵课件.ppt

2022/10/41本章内容本章内容l4.1 模糊关系模糊关系l4.2 模糊等价关系模糊等价关系l4.3 聚类分析聚类分析2022/10/42模糊关系的三个性质模糊关系的三个性质l自反性自反性l对称性对称性l传递性传递性2022/10/43自反性自反性l若模糊关系若模糊关系R满足满足R(u,u)=1或或IR，则称，则称R具具有自反性有自反性l模糊自反矩阵模糊自反矩阵lrii=1l例如：例如：2022/10/44自反矩阵的定理自反矩阵的定理定理定理.设模糊矩阵设模糊矩阵 A Mnn是自反矩阵，则有是自反矩阵，则有I AA2 A3 An-1 An证明证明:2022/10/45对称性对称性l若模糊关系若模糊关系R满足满足R(u,v)=R(v,u)，则称，则称R具有具有对称性对称性l模糊对称矩阵模糊对称矩阵lrij=rjil例如：例如：2022/10/46传递性传递性l若模糊关系若模糊关系R满足满足RRR，则称，则称R具有具有传递传递性性l模糊传递矩阵模糊传递矩阵2022/10/47模糊传递矩阵模糊传递矩阵例例2022/10/48模糊传递矩阵的定理模糊传递矩阵的定理定理定理.设模糊矩阵设模糊矩阵 Q Mnn是传递矩阵，是传递矩阵，则有则有Q Q2 Q3 Qn-1 Qn 证明证明:2022/10/49模糊等价关系模糊等价关系定义定义.模糊关系模糊关系RF(UU),满足满足（1）自反性：）自反性：R(u,u)=1;（2）对称性：）对称性：R(u,v)=R(v,u);（3）传递性：）传递性：R2 R则称则称R为为模糊等价关系模糊等价关系2022/10/410模糊等价矩阵模糊等价矩阵l若论域若论域U是有限论域，则是有限论域，则U上的模糊等价关上的模糊等价关系系R可表示为模糊等价矩阵可表示为模糊等价矩阵l模糊等价矩阵模糊等价矩阵l自反性自反性 rii=1l对称性对称性 rij=rjil传递性传递性2022/10/411R是否为模糊等价矩阵？是否为模糊等价矩阵？2022/10/412等价布尔关系等价布尔关系l一个布尔矩阵具有如下特性，则称其为等一个布尔矩阵具有如下特性，则称其为等价的布尔矩阵，对应一个普通的等价关系价的布尔矩阵，对应一个普通的等价关系l自反性自反性l对称性对称性l传递性传递性2022/10/413模糊等价矩阵的性质模糊等价矩阵的性质l若若R为模糊等价矩阵，则为模糊等价矩阵，则 R=R2=R3=Rn-1=Rn 证明：证明：自反性：自反性：RR2 Rn-1 Rn传递性传递性:RR2Rn-1Rn2022/10/414模糊等价矩阵的定理模糊等价矩阵的定理1定理定理1.R是模糊等价矩阵是模糊等价矩阵对于任何对于任何0,1，R是等价布尔矩阵。

是等价布尔矩阵证明：证明：l对称性、自反性显然对称性、自反性显然l传递性传递性2022/10/415定理定理1的意义的意义l模糊等价矩阵模糊等价矩阵普通等价矩阵普通等价矩阵l普通等价矩阵普通等价矩阵普通等价关系普通等价关系l普通等价关系可以分类普通等价关系可以分类l当当在在0,1上变动时，得到不同的上变动时，得到不同的R,从而从而得到不同的分类得到不同的分类2022/10/416模糊等价矩阵分类模糊等价矩阵分类例例设设X=x1,x2,x3,x4,x5 求当求当 1,0.8,0.6,0.5,0.4时的聚类结果时的聚类结果2022/10/417 1l利用利用 1时的截关系，将时的截关系，将X分成分成5个等价个等价类：类：lx1,x2,x3,x4,x52022/10/418 0.8l利用利用 0.8时的截关系，将时的截关系，将X分成分成4个等个等价类：价类：lx1,x3,x2,x4,x52022/10/419 0.6l利用利用 0.6时的截关系，将时的截关系，将X分成分成3个等个等价类：价类：lx1,x3,x2,x4,x52022/10/420 0.5l利用利用 0.5时的截关系，将时的截关系，将X分成分成2个等个等价类：价类：lx1,x3,x4,x5,x22022/10/421 0.4l利用利用 0.4时的截关系，将时的截关系，将X分成分成1个等个等价类：价类：lx1,x2,x3,x4,x52022/10/422动态聚类图动态聚类图由由1变到变到0，R的分类由细到粗的分类由细到粗x1 x2 x3 x4 x5=1=0.8=0.4=0.6=0.52022/10/423模糊等价矩阵的定理模糊等价矩阵的定理2l定理定理2.R nn是模糊等价矩阵，则对于是模糊等价矩阵，则对于任何任何,0,1，且，且 I RR2 Rnt(R)=Rn Rm k=1 Rk=t(R)传递闭包的定理传递闭包的定理42022/10/435模糊相似矩阵模糊相似矩阵模糊等价矩阵模糊等价矩阵l将相似矩阵改造成等价矩阵将相似矩阵改造成等价矩阵l只需求相似矩阵的传递闭包只需求相似矩阵的传递闭包2022/10/436定理定理5.设设Rnn 是模糊相似矩阵，则存在是模糊相似矩阵，则存在一个最小自然数一个最小自然数k(kn)，使得传递闭包，使得传递闭包t(R)=Rk，对于任何自然数，对于任何自然数bk，都有，都有Rb=Rk，此时，此时，t(R)是模糊等价矩阵。

是模糊等价矩阵传递闭包的定理传递闭包的定理52022/10/437平方法求传递闭包平方法求传递闭包从模糊相似矩阵从模糊相似矩阵R出发，依次求平出发，依次求平方：方：当第一次出现当第一次出现Rk Rk=Rk时，时，Rk就是就是所求的传递闭包所求的传递闭包t(R)2022/10/438时间复杂度时间复杂度2022/10/439课堂作业课堂作业2022/10/440课堂作业课堂作业4-1设设l请问至多几次平方可以到达传递闭包？请问至多几次平方可以到达传递闭包？l请给出传递闭包请给出传递闭包t(R)2022/10/441课堂作业课堂作业4-2l证明：若证明：若Q,R是传递的，则是传递的，则QR也是传递也是传递的的.2022/10/442本章内容本章内容l4.1 模糊关系模糊关系l4.2 模糊等价关系模糊等价关系l4.3 聚类分析聚类分析2022/10/4434-3 聚类分析聚类分析2022/10/444n 聚聚类类分分析析是是把把对对象象自自动动划划分分成成多多个个类类簇簇，使得同类簇内对象相近、异类簇间对象相异；使得同类簇内对象相近、异类簇间对象相异；n 聚聚类类分分析析对对于于发发现现数数据据的的隐隐含含模模式式、获获取取知知识识、预预测测数数据据的的功功能能或或行行为为等等，具具有有十十分重要的意义。

分重要的意义移动通信网客户聚类移动通信网客户聚类 图像像素点聚类图像像素点聚类蛋白质聚类蛋白质聚类聚类分析聚类分析2022/10/445聚类分析聚类分析与模式分类的区别：与模式分类的区别：l模式分类是已知若干模式，要求我们正确判断模式分类是已知若干模式，要求我们正确判断当前的新样本属于哪个模式；当前的新样本属于哪个模式；l聚类分析所讨论的对象是一大批样本，事先没聚类分析所讨论的对象是一大批样本，事先没有给定任何模式供参考，要求我们按样本各自有给定任何模式供参考，要求我们按样本各自的属性值加以分类的属性值加以分类l从机器学习的角度来看，分类是有监督学习，从机器学习的角度来看，分类是有监督学习，聚类是无监督学习聚类是无监督学习2022/10/446聚类分析方法聚类分析方法 简单说，简单说，聚类分析就是用数学方法对事物进行分类通聚类分析就是用数学方法对事物进行分类通过适当聚类，事物便于研究，事物的内部规律容易为人过适当聚类，事物便于研究，事物的内部规律容易为人类所掌握现有方法主要有：类所掌握现有方法主要有：（1）层次聚类算法：通过数据的分裂或聚合，以形成层）层次聚类算法：通过数据的分裂或聚合，以形成层次类簇。

适用于小规模数据集适用于小规模数据集2）划分式聚类：事先指定类簇数或类簇中心，通过反）划分式聚类：事先指定类簇数或类簇中心，通过反复迭代，逐步降低目标函数的值当目标函数收敛时，复迭代，逐步降低目标函数的值当目标函数收敛时，得到最终类簇得到最终类簇3）基于密度和网格的聚类：通过密度或网格发现类簇基于密度和网格的聚类：通过密度或网格发现类簇适用于大规模数据集适用于大规模数据集2022/10/447模糊聚类分析模糊聚类分析l模糊数学产生之前，聚类分析是数理统计模糊数学产生之前，聚类分析是数理统计多元分析的一个分支多元分析的一个分支l现实分类问题往往具有模糊性，例如现实分类问题往往具有模糊性，例如“环环境污染分类境污染分类”、“临床症状资料分类临床症状资料分类”、“岩石分类岩石分类”等等，因此，用模糊数学语等等，因此，用模糊数学语言进行模糊聚类分析更为自然言进行模糊聚类分析更为自然2022/10/448基于模糊等价矩阵的聚类分析方法基于模糊等价矩阵的聚类分析方法2022/10/449基于模糊等价矩阵的聚类分析步骤基于模糊等价矩阵的聚类分析步骤第一步：建立模糊矩阵第一步：建立模糊矩阵；第二步：建立模糊等价矩阵；第二步：建立模糊等价矩阵；第三步：聚类（求动态聚类图）第三步：聚类（求动态聚类图）2022/10/450第一步：建立模糊矩阵第一步：建立模糊矩阵l设设U=u1,u2,un 为待分类的全体对象，为待分类的全体对象，其中每个待分类对象由一组其中每个待分类对象由一组数据表征数据表征如下：如下：l问题转化为：如何建立对象问题转化为：如何建立对象ui与与uj之间的相似之间的相似关系关系2022/10/451例例1环境污染环境污染l例如，要对一些环境单元进行聚类，判断它们例如，要对一些环境单元进行聚类，判断它们的污染程度的污染程度l每个环境单元包括四个要素：空气、水分、土每个环境单元包括四个要素：空气、水分、土壤、作物壤、作物l环境单元的污染状况由环境单元的污染状况由污染物在四个要素中含污染物在四个要素中含量的超限度量的超限度来描述来描述2022/10/452l现有现有5个污染单元，个污染单元，U=,l它们的污染数据如下它们的污染数据如下:=(5,5,3,2),=(2,3,4,5),=(5,5,2,3),=(1,5,3,1),=(2,4,5,1)2022/10/453建立模糊矩阵建立模糊矩阵l如何建立对象如何建立对象ui与与uj之间的相似关系？之间的相似关系？l有许多方法，应用时根据实际情况，选有许多方法，应用时根据实际情况，选择一种方法来求择一种方法来求ui与与uj的相似关系的相似关系R(ui,uj)=rijl在在“环境污染环境污染”的例子中，如何给出模的例子中，如何给出模糊相似矩阵？糊相似矩阵？2022/10/454建立模糊相似矩阵建立模糊相似矩阵建立模糊相似矩阵的注意事项：建立模糊相似矩阵的注意事项：lrij0,1l自反自反l对称对称l“环境环境”例中，采用例中，采用“绝对值减数法绝对值减数法”l问：问：得到的相似矩阵的维数是多少？得到的相似矩阵的维数是多少？2022/10/455模糊相似矩阵模糊相似矩阵2022/10/456步骤步骤2：相似关系：相似关系等价关系等价关系l步骤步骤1得到的矩阵一般满足自反性和对称得到的矩阵一般满足自反性和对称性性l将模糊相似矩阵改造成模糊等价矩阵将模糊相似矩阵改造成模糊等价矩阵l平方法平方法l求传递闭包求传递闭包2022/10/457至多计算多少次？至多计算多少次？l模糊相似矩阵模糊相似矩阵55lk=log25+1=2+1=3l最坏情况下，最坏情况下，RR2R4R8，计算到，计算到R82022/10/4582022/10/459模糊等价矩阵模糊等价矩阵2022/10/460步骤步骤3：聚类：聚类lR的传递闭包的传递闭包t(R)=R4l对于对于t(R)，依次取截关系，依次取截关系2022/10/461 1l利用利用 1时的截关系，将时的截关系，将X分成分成5个等价个等价类：类：lx1,x2,x3,x4,x52022/10/462 0.8l利用利用 0.8时的截关系，将时的截关系，将X分成分成4个等个等价类：价。