模糊等价矩阵.ppt

2024/5/21 周二1第第4章章 模糊关系与聚类分析模糊关系与聚类分析2024/5/21 周二2本章内容本章内容l4.1 模糊关系模糊关系l4.2 模糊等价关系模糊等价关系l4.3 聚类分析聚类分析2024/5/21 周二3模糊关系的三个性质模糊关系的三个性质l自反性自反性l对称性对称性l传递性传递性2024/5/21 周二4自反性自反性l若模糊关系若模糊关系R满足满足R(u,u)=1或或IR，则称，则称R具具有自反性有自反性l模糊自反矩阵模糊自反矩阵lrii=1l例如：例如：2024/5/21 周二5自反矩阵的定理自反矩阵的定理定理定理.设模糊矩阵设模糊矩阵 A Mnn是自反矩阵，则有是自反矩阵，则有I AA2 A3 An-1 An证明证明:2024/5/21 周二6对称性对称性l若模糊关系若模糊关系R满足满足R(u,v)=R(v,u)，则称，则称R具有具有对称性对称性l模糊对称矩阵模糊对称矩阵lrij=rjil例如：例如：2024/5/21 周二7传递性传递性l若模糊关系若模糊关系R满足满足RRR，则称，则称R具有具有传递传递性性l模糊传递矩阵模糊传递矩阵2024/5/21 周二8模糊传递矩阵模糊传递矩阵例例2024/5/21 周二9模糊传递矩阵的定理模糊传递矩阵的定理定理定理.设模糊矩阵设模糊矩阵 Q Mnn是传递矩阵，是传递矩阵，则有则有Q Q2 Q3 Qn-1 Qn 证明证明:2024/5/21 周二10模糊等价关系模糊等价关系定义定义.模糊关系模糊关系RF(UU),满足满足（1）自反性：）自反性：R(u,u)=1;（2）对称性：）对称性：R(u,v)=R(v,u);（3）传递性：）传递性：R2 R则称则称R为为模糊等价关系模糊等价关系2024/5/21 周二11模糊等价矩阵模糊等价矩阵l若论域若论域U是有限论域，则是有限论域，则U上的模糊等价关上的模糊等价关系系R可表示为模糊等价矩阵可表示为模糊等价矩阵l模糊等价矩阵模糊等价矩阵l自反性自反性 rii=1l对称性对称性 rij=rjil传递性传递性2024/5/21 周二12R是否为模糊等价矩阵？是否为模糊等价矩阵？2024/5/21 周二13等价布尔关系等价布尔关系l一个布尔矩阵具有如下特性，则称其为等一个布尔矩阵具有如下特性，则称其为等价的布尔矩阵，对应一个普通的等价关系价的布尔矩阵，对应一个普通的等价关系l自反性自反性l对称性对称性l传递性传递性2024/5/21 周二14模糊等价矩阵的性质模糊等价矩阵的性质l若若R为模糊等价矩阵，则为模糊等价矩阵，则 R=R2=R3=Rn-1=Rn 证明：证明：自反性：自反性：RR2 Rn-1 Rn传递性传递性:RR2Rn-1Rn2024/5/21 周二15模糊等价矩阵的定理模糊等价矩阵的定理1定理定理1.R是模糊等价矩阵是模糊等价矩阵对于任何对于任何0,1，R是等价布尔矩阵。是等价布尔矩阵。证明：证明：l对称性、自反性显然对称性、自反性显然l传递性传递性2024/5/21 周二16定理定理1的意义的意义l模糊等价矩阵模糊等价矩阵普通等价矩阵普通等价矩阵l普通等价矩阵普通等价矩阵普通等价关系普通等价关系l普通等价关系可以分类普通等价关系可以分类l当当在在0,1上变动时，得到不同的上变动时，得到不同的R,从而从而得到不同的分类得到不同的分类2024/5/21 周二17模糊等价矩阵分类模糊等价矩阵分类例例设设X=x1,x2,x3,x4,x5 求当求当 1,0.8,0.6,0.5,0.4时的聚类结果。时的聚类结果。2024/5/21 周二18 1l利用利用 1时的截关系，将时的截关系，将X分成分成5个等价个等价类：类：lx1,x2,x3,x4,x52024/5/21 周二19 0.8l利用利用 0.8时的截关系，将时的截关系，将X分成分成4个等个等价类：价类：lx1,x3,x2,x4,x52024/5/21 周二20 0.6l利用利用 0.6时的截关系，将时的截关系，将X分成分成3个等个等价类：价类：lx1,x3,x2,x4,x52024/5/21 周二21 0.5l利用利用 0.5时的截关系，将时的截关系，将X分成分成2个等个等价类：价类：lx1,x3,x4,x5,x22024/5/21 周二22 0.4l利用利用 0.4时的截关系，将时的截关系，将X分成分成1个等个等价类：价类：lx1,x2,x3,x4,x52024/5/21 周二23动态聚类图动态聚类图由由1变到变到0，R的分类由细到粗的分类由细到粗x1 x2 x3 x4 x5=1=0.8=0.4=0.6=0.52024/5/21 周二24模糊等价矩阵的定理模糊等价矩阵的定理2l定理定理2.R nn是模糊等价矩阵，则对于是模糊等价矩阵，则对于任何任何,0,1，且，且 I RR2 Rnt(R)=Rn Rm k=1 Rk=t(R)传递闭包的定理传递闭包的定理42024/5/21 周二36模糊相似矩阵模糊相似矩阵模糊等价矩阵模糊等价矩阵l将相似矩阵改造成等价矩阵将相似矩阵改造成等价矩阵l只需求相似矩阵的传递闭包只需求相似矩阵的传递闭包2024/5/21 周二37定理定理5.设设Rnn 是模糊相似矩阵，则存在是模糊相似矩阵，则存在一个最小自然数一个最小自然数k(kn)，使得传递闭包，使得传递闭包t(R)=Rk，对于任何自然数，对于任何自然数bk，都有，都有Rb=Rk，此时，此时，t(R)是模糊等价矩阵。是模糊等价矩阵。传递闭包的定理传递闭包的定理52024/5/21 周二38平方法求传递闭包平方法求传递闭包从模糊相似矩阵从模糊相似矩阵R出发，依次求平出发，依次求平方：方：当第一次出现当第一次出现Rk Rk=Rk时，时，Rk就是就是所求的传递闭包所求的传递闭包t(R)2024/5/21 周二39时间复杂度时间复杂度2024/5/21 周二40课堂作业课堂作业2024/5/21 周二41课堂作业课堂作业4-1设设l请问至多几次平方可以到达传递闭包？请问至多几次平方可以到达传递闭包？l请给出传递闭包请给出传递闭包t(R)2024/5/21 周二42课堂作业课堂作业4-2l证明：若证明：若Q,R是传递的，则是传递的，则QR也是传递也是传递的的.2024/5/21 周二43本章内容本章内容l4.1 模糊关系模糊关系l4.2 模糊等价关系模糊等价关系l4.3 聚类分析聚类分析2024/5/21 周二444-3 聚类分析聚类分析2024/5/21 周二45n 聚聚类类分分析析是是把把对对象象自自动动划划分分成成多多个个类类簇簇，使得同类簇内对象相近、异类簇间对象相异；使得同类簇内对象相近、异类簇间对象相异；n 聚聚类类分分析析对对于于发发现现数数据据的的隐隐含含模模式式、获获取取知知识识、预预测测数数据据的的功功能能或或行行为为等等，具具有有十十分重要的意义。分重要的意义。移动通信网客户聚类移动通信网客户聚类 图像像素点聚类图像像素点聚类蛋白质聚类蛋白质聚类聚类分析聚类分析2024/5/21 周二46聚类分析聚类分析与模式分类的区别：与模式分类的区别：l模式分类是已知若干模式，要求我们正确判断模式分类是已知若干模式，要求我们正确判断当前的新样本属于哪个模式；当前的新样本属于哪个模式；l聚类分析所讨论的对象是一大批样本，事先没聚类分析所讨论的对象是一大批样本，事先没有给定任何模式供参考，要求我们按样本各自有给定任何模式供参考，要求我们按样本各自的属性值加以分类。的属性值加以分类。l从机器学习的角度来看，分类是有监督学习，从机器学习的角度来看，分类是有监督学习，聚类是无监督学习。聚类是无监督学习。2024/5/21 周二47聚类分析方法聚类分析方法 简单说，简单说，聚类分析就是用数学方法对事物进行分类。通聚类分析就是用数学方法对事物进行分类。通过适当聚类，事物便于研究，事物的内部规律容易为人过适当聚类，事物便于研究，事物的内部规律容易为人类所掌握。现有方法主要有：类所掌握。现有方法主要有：（1）层次聚类算法：通过数据的分裂或聚合，以形成层）层次聚类算法：通过数据的分裂或聚合，以形成层次类簇。适用于小规模数据集。次类簇。适用于小规模数据集。（2）划分式聚类：事先指定类簇数或类簇中心，通过反）划分式聚类：事先指定类簇数或类簇中心，通过反复迭代，逐步降低目标函数的值。当目标函数收敛时，复迭代，逐步降低目标函数的值。当目标函数收敛时，得到最终类簇。得到最终类簇。（3）基于密度和网格的聚类：通过密度或网格发现类簇。）基于密度和网格的聚类：通过密度或网格发现类簇。适用于大规模数据集。适用于大规模数据集。2024/5/21 周二48模糊聚类分析模糊聚类分析l模糊数学产生之前，聚类分析是数理统计模糊数学产生之前，聚类分析是数理统计多元分析的一个分支。多元分析的一个分支。l现实分类问题往往具有模糊性，例如现实分类问题往往具有模糊性，例如“环环境污染分类境污染分类”、“临床症状资料分类临床症状资料分类”、“岩石分类岩石分类”等等，因此，用模糊数学语等等，因此，用模糊数学语言进行模糊聚类分析更为自然。言进行模糊聚类分析更为自然。2024/5/21 周二49基于模糊等价矩阵的聚类分析方法基于模糊等价矩阵的聚类分析方法2024/5/21 周二50基于模糊等价矩阵的聚类分析步骤基于模糊等价矩阵的聚类分析步骤第一步：建立模糊矩阵第一步：建立模糊矩阵；第二步：建立模糊等价矩阵；第二步：建立模糊等价矩阵；第三步：聚类（求动态聚类图）第三步：聚类（求动态聚类图）2024/5/21 周二51第一步：建立模糊矩阵第一步：建立模糊矩阵l设设U=u1,u2,un 为待分类的全体对象，为待分类的全体对象，其中每个待分类对象由一组其中每个待分类对象由一组数据表征数据表征如下：如下：l问题转化为：如何建立对象问题转化为：如何建立对象ui与与uj之间的相似之间的相似关系关系2024/5/21 周二52例例1环境污染环境污染l例如，要对一些环境单元进行聚类，判断它们例如，要对一些环境单元进行聚类，判断它们的污染程度的污染程度l每个环境单元包括四个要素：空气、水分、土每个环境单元包括四个要素：空气、水分、土壤、作物壤、作物l环境单元的污染状况由环境单元的污染状况由污染物在四个要素中含污染物在四个要素中含量的超限度量的超限度来描述来描述2024/5/21 周二53l现有现有5个污染单元，个污染单元，U=,l它们的污染数据如下它们的污染数据如下:=(5,5,3,2),=(2,3,4,5),=(5,5,2,3),=(1,5,3,1),=(2,4,5,1)2024/5/21 周二54建立模糊矩阵建立模糊矩阵l如何建立对象如何建立对象ui与与uj之间的相似关系？之间的相似关系？l有许多方法，应用时根据实际情况，选有许多方法，应用时根据实际情况，选择一种方法来求择一种方法来求ui与与uj的相似关系的相似关系R(ui,uj)=rijl在在“环境污染环境污染”的例子中，如何给出模的例子中，如何给出模糊相似矩阵？糊相似矩阵？2024/5/21 周二55建立模糊相似矩阵建立模糊相似矩阵建立模糊相似矩阵的注意事项：建立模糊相似矩阵的注意事项：lrij0,1l自反自反l对称对称l“环境环境”例中，采用例中，采用“绝对值减数法绝对值减数法”l问：问：得到的相似矩阵的维数是多少？得到的相似矩阵的维数是多少？2024/5/21 周二56模糊相似矩阵模糊相似矩阵2024/5/21 周二57步骤步骤2：相似关系：相似关系等价关系等价关系l步骤步骤1得到的矩阵一般满足自反性和对称得到的矩阵一般满足自反性和对称性性l将模糊相似矩阵改造成模糊等价矩阵将模糊相似矩阵改造成模糊等价矩阵l平方法平方法l求传递闭包求传递闭包2024/5/21 周二58至多计算多少次？至多计算多少次？l模糊相似矩阵模糊相似矩阵55lk=log25+1=2+1=3l最坏情况下，最坏情况下，RR2R4R8，计算到，计算到R82024/5/21 周二592024/5/21 周二60模糊等价矩阵模糊等价矩阵2024/5/21 周二61步骤步骤3：聚类：聚类lR的传递闭包的传递闭包t(R)=R4l对于对于t(R)，依次取截关系，依次取截关系2024/5/21 周二62 1l利用利用 1时的截关系，将时的截关系，将X分成分成5个等价个等价类：类：lx1,x2,x3,x4,x52024/5/21 周二63 0.8l利用利用 0.8时的截关系，将时的截关系，将X分成分成4个等个等价类：价类：lx1,x3,x2,x4,x52024/5/21 周二64 0.6l利用利用 0.6时的截关系，将时的截关系，将X分成分成3个等个等价类：价类：lx1,x3,x2,x4,x52024/5/21 周二65 0.5l利用利用 0.5时的截关系，将时的截关系，将X分成分成2个等个等价类：价类：lx1,x3,x4,x5,x22024/5/21 周二66 0.4l利用利用 0.4时的截关系，将时的截关系，将X分成分成1个等个等价类：价类：lx1,x2,x3,x4,x52024/5/21 周二67动态聚类图动态聚类图由由1变到变到0，R的分类由细到粗的分类由细到粗x1 x2 x3 x4 x5=1=0.8=0.4=0.6=0.52024/5/21 周二68讨论讨论2024/5/21 周二69讨论讨论1：建立相似矩阵的其他方法：建立相似矩阵的其他方法l非常多！主要分为非常多！主要分为3类类l相似系数法相似系数法l距离法（绝对值减数法就是距离法之一）距离法（绝对值减数法就是距离法之一）l主观法主观法l在后面给出在后面给出2024/5/21 周二70讨论讨论2：直接基于相似矩阵聚类？：直接基于相似矩阵聚类？l建立模糊相似矩阵建立模糊相似矩阵R后，求其传递闭包后，求其传递闭包t(R)计算量较大。计算量较大。l若直接从若直接从R出发，进行聚类，会怎么样？出发，进行聚类，会怎么样？2024/5/21 周二71l取取=1(最大值最大值)，对每个，对每个xi，确定其相似类，确定其相似类xi1l将满足将满足rij=1的的xi和和xj放在一类，构成相似类放在一类，构成相似类x1,x2,x3,x4,x5 2024/5/21 周二72l取取=0.8(次大值次大值)，对每，对每个个xi,确定其相似类确定其相似类xiRlx1,x3,x2,x4,x52024/5/21 周二73l依次取依次取=0.6、0.4等，等，确定其相似类。确定其相似类。lx1,x3,x2,x4,x5lx1,x3,x4,x2,x5,x1,x3,x1,x4,x5,x2,x4,x52024/5/21 周二74相似矩阵直接聚类相似矩阵直接聚类vs.等价矩阵聚类等价矩阵聚类l对于一个固定的对于一个固定的，等价矩阵聚类得到的，等价矩阵聚类得到的等价类没有公共元素！等价类没有公共元素！l相似矩阵聚类得到的相似矩阵聚类得到的相似类则有公共元素相似类则有公共元素，这是因为不具有这是因为不具有“传递性传递性”2024/5/21 周二75讨论讨论3：如何选取：如何选取？l在实际应用中，需要选择适当的在实际应用中，需要选择适当的，从而，从而给给出一个出一个较较明确的分明确的分类类。1）由具有丰富）由具有丰富经验经验的的领领域域专专家家结结合合领领域知域知识识确定确定，从而得到，从而得到水平上的等价分水平上的等价分类类。2）用用统计统计学中的学中的F检验检验方法，刷掉不合格方法，刷掉不合格的的类类，使分，使分类变类变得得较较清晰。清晰。2024/5/21 周二76最佳阈值确定最佳阈值确定F统计量统计量lF统计量：统计量：l分子表示类间平均距离，分母表示类内样分子表示类间平均距离，分母表示类内样本间的距离，本间的距离，F值越大，表示类与类间的值越大，表示类与类间的差异越大，分类越好。差异越大，分类越好。2024/5/21 周二77讨论讨论1:模糊相似矩阵的建立模糊相似矩阵的建立2024/5/21 周二781、数据预处理、数据预处理数据标准化数据标准化设论域设论域U=x1,x2,xn 为待聚类对象，为待聚类对象，每个对象由每个对象由m个指标表示其性状：个指标表示其性状：将原始数据矩阵中的元素通过将原始数据矩阵中的元素通过适当的变换适当的变换压缩到压缩到0,1上。上。2024/5/21 周二79程序程序3：玉米螟：玉米螟1:78月平均气温月平均气温2:上年上年122月平均月平均气温气温3:4月份温湿系数月份温湿系数4:4月份雨日数月份雨日数5:4月份日照数月份日照数6:4月份平均风速月份平均风速7:5月上旬温湿系数月上旬温湿系数8:5月田间调查的玉月田间调查的玉米螟卵数米螟卵数2024/5/21 周二80数据标准化数据标准化数据标准化常用的两种变换：数据标准化常用的两种变换：l平移极差变换平移极差变换l平移标准差变换平移标准差变换2024/5/21 周二81数据标准化数据标准化l平移极差变换平移极差变换(变换至变换至0-1区间区间)：请计算请计算:=(5,5,3,2),=(2,3,4,5),=(5,5,2,3),=(1,5,3,1),=(2,4,5,1)2024/5/21 周二82数据标准化数据标准化l平移标准差变换平移标准差变换(消除量纲消除量纲)：2024/5/21 周二832、模糊相似矩阵的建立、模糊相似矩阵的建立l相似系数法相似系数法 l距离法距离法l其它方法：主观评分法其它方法：主观评分法2024/5/21 周二841)相似系数法相似系数法(1)数量积法数量积法|rij|0,1，若为负，要将其压缩到，若为负，要将其压缩到0,1，压，压缩方法：平移极差变换或缩方法：平移极差变换或rij(rij+1)/22024/5/21 周二851)相似系数法相似系数法(2)夹角余弦法：夹角余弦法：(3)相关系数法：相关系数法：2024/5/21 周二1)相似系数法相似系数法(4)指数相似系数法：指数相似系数法：2024/5/21 周二871)相似系数法相似系数法(5)最大最小法：最大最小法：(6)算数平均最小法：算数平均最小法：(7)几何平均最小法：几何平均最小法：上述三种方法要求上述三种方法要求xij0，否则也要作适当变换。，否则也要作适当变换。2024/5/21 周二882)距离法距离法(1)绝对值倒数法：绝对值倒数法：(2)绝对值指数法：绝对值指数法：2024/5/21 周二892)距离法距离法(3)直接距离法：直接距离法：rij1-c*d(xi,xj)海明距离：海明距离：欧式距离：欧式距离：切比雪夫距离：切比雪夫距离：2024/5/21 周二903)主观评分法主观评分法专家直接给出相似度，专家数为专家直接给出相似度，专家数为N，rij(k)表示第表示第k个专家给出的个专家给出的i与与j的相似度，的相似度，aij(k)为专家的自信度。为专家的自信度。2024/5/21 周二91程序演示程序演示2024/5/21 周二92程序程序1：环境：环境l第第4章章数据文件数据文件编辑编辑E.exe 打开打开”环境环境.dat”l第第4章章模糊聚类模糊聚类E.exe 2024/5/21 周二93程序程序1：环境：环境程序程序1：环境：环境2024/5/21 周二942024/5/21 周二95程序程序2：家族：家族l论域论域U=x1,x2,x3,x4,x5表示来自表示来自2个家族的个家族的5个个人人,已经利用某种方法建立了相似矩阵：已经利用某种方法建立了相似矩阵：l第第4章章数据文件数据文件编辑编辑E.exe 打开打开”家族家族.dat”l用模糊聚类分析确定他们的家族关系。用模糊聚类分析确定他们的家族关系。l第第4章章模糊聚类模糊聚类E.exe 2024/5/21 周二96程序程序2：家族：家族2024/5/21 周二97程序程序3：玉米螟：玉米螟l第第4章章数据文件数据文件编辑编辑E.exe 打开打开”玉米螟玉米螟.dat”l用模糊聚类分析确定各年份间关系，以应用于用模糊聚类分析确定各年份间关系，以应用于害虫预报。害虫预报。l第第4章章模糊聚类模糊聚类E.exe 2024/5/21 周二98程序程序3：玉米螟：玉米螟2024/5/21 周二99程序程序3：玉米螟：玉米螟2024/5/21 周二100程序程序4：土壤：土壤l第第4章章数据文件数据文件编辑编辑E.exe 打开打开”土壤土壤.dat”l21个土壤样本，每个样本个土壤样本，每个样本9个量化指标：含氮百个量化指标：含氮百分比、含磷百分比、有机质、分比、含磷百分比、有机质、PH值、耕层厚度、值、耕层厚度、持水量等。持水量等。l第第4章章模糊聚类模糊聚类E.exe 分析结果为进一步做土分析结果为进一步做土壤分类提供参考。壤分类提供参考。2024/5/21 周二101程序程序4：土壤：土壤2024/5/21 周二102课后作业课后作业2024/5/21 周二1031、著名聚类的例子、著名聚类的例子l日本学者日本学者Tamura给出，在模糊数学中广泛使用给出，在模糊数学中广泛使用l有三个家庭，共有三个家庭，共16人。每个家庭人数为人。每个家庭人数为4-7人。人。l每人提供一张照片，共计每人提供一张照片，共计16张张l由若干素不相识的中学生对照片两两进行比较，按相貌由若干素不相识的中学生对照片两两进行比较，按相貌相似程度进行评分，分数在相似程度进行评分，分数在0,1上。每对照片的相似程上。每对照片的相似程度由所有人对他们的评分的平均值确定。度由所有人对他们的评分的平均值确定。l要求：把三个家庭区分开来（即对这要求：把三个家庭区分开来（即对这16个人进行聚类），个人进行聚类），可使用直接聚类法可使用直接聚类法2024/5/21 周二104得到相似矩阵得到相似矩阵2024/5/21 周二105作业2l要建立下面四个对象的相似矩阵，请给出要建立下面四个对象的相似矩阵，请给出合理的建立公式，并用传递闭包法进行模合理的建立公式，并用传递闭包法进行模糊聚类。糊聚类。