模糊数学教程第7章-模糊聚类分析ppt课件.ppt

《模糊数学教程第7章-模糊聚类分析ppt课件.ppt》由会员分享，可在线阅读，更多相关《模糊数学教程第7章-模糊聚类分析ppt课件.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第章第章 模糊聚类分析模糊聚类分析 一、模糊聚类分析及其步骤一、模糊聚类分析及其步骤二、基于模糊等价关系的传递闭包法二、基于模糊等价关系的传递闭包法三、基于模糊相似关系的直接聚类法三、基于模糊相似关系的直接聚类法四、基于模糊四、基于模糊c-划分的模糊聚类法划分的模糊聚类法.1 模糊聚类分析及步骤模糊聚类分析及步骤xxx x12,.,nUu uu iu12,.,iiinxxxijr,iju u01,ijr 0ijr ,iju u1ijr ,iju uijriuijr11,1,mijikjkkijrx xijM 1max()mijjkijkMx x 01,ijr ijrijr1,2ijijrr 0

2、,1ijr (),ijijrmrijMm 0,1ijr max,ijijMr min,ijijmr 12211mikjkkijmmikjkkkx xrxx ijr11()()mikjkkijmikjkkxxrxx 112()()mikjkkijmikjkkx xrxx 11mijikjkkrcxx ijrijr()ijRr 选择一种合适的聚类方法，便可以得到分类结果选择一种合适的聚类方法，便可以得到分类结果.2 据上面标定所得的模糊矩阵据上面标定所得的模糊矩阵R，求出其传递闭包求出其传递闭包( ),t R( )Rt R 为模糊等价矩阵，为模糊等价矩阵，然后由然后由3.4之方法，令之方法，令 从

3、从1降到降到0，便可按需要，便可按需要对对U进行分类，这样的聚类方法，称进行分类，这样的聚类方法，称例例7.17.1 环境单元分类环境单元分类设设12,.,nUu uu 为五个环境单元的集合，每个为五个环境单元的集合，每个环境单元有空气、水分、土壤、作物四个要素，环境环境单元有空气、水分、土壤、作物四个要素，环境单元的污染状况由污染物在四个要素中含量的超限度单元的污染状况由污染物在四个要素中含量的超限度来描述，若其污染数据为：来描述，若其污染数据为：1(5,5,3,2),u 2(2,3,4,5),u 3(5,5,2,3),u 4(1,5,3,1),u 5(2,4,5,1),u 试对试对U进进行

4、分类行分类.（1）按）按绝对值减数绝对值减数法进行标定，如取法进行标定，如取c=0.1，则，则4110.1ijikjkkrxx 于是得模糊相似矩阵于是得模糊相似矩阵10.10.80.50.30.110.10.20.40.80.110.30.10.50.20.310.60.30.40.10.61R （2）用逐次平方法计算）用逐次平方法计算R的传递闭包的传递闭包( ),t RR 因为因为210.30.80.50.50.310.20.40.40.80.210.30.10.50.40.510.60.50.40.30.61RR 4210.40.80.50.50.410.40.40.40.80.410.5

5、0.50.50.40.510.60.50.40.50.61RR 8410.40.80.50.50.410.40.40.40.80.410.50.50.50.40.510.60.50.40.50.61RR 所以传递闭包所以传递闭包4,RR 然后依次取然后依次取 的截矩阵的截矩阵,R 并按并按 将将U分成等价类分成等价类.R 若若 =1, 便将便将U分为分为5类类, 即即12345,;uuuuu若若 =0.8, 便将便将U分为分为4类类, 即即13245,;u uuuu若若 =0.6, 便将便将U分为分为3类类, 即即13245,;u uuu u若若 =0.5, 便将便将U分为分为2类类, 即即1

6、2342,;u u u uu若若 =0.4, 便将便将U全归为为全归为为1类类, 即即12345,u u u u u聚类图见教材聚类图见教材3.4图图3-3 设设12,.,nUu uu 为待分事物的全体为待分事物的全体, 1(,jjux 2,),jjmjkxxx为描述元素为描述元素 的第的第k个特征的数据个特征的数据,ju又设又设c为对应于为对应于 值的类数值的类数, 为第为第i类元素的个数类元素的个数,in第第i类元素记为类元素记为1,iiinuu记记11inikjkjixxn (1,)km 为第为第i类元素第类元素第k个特征的平均值个特征的平均值, 称称1(,)iiimuxx 为第为第i

7、类的类的; 1(,)muxx 为全体元素为全体元素的的, 而而11,nkjkjxxn 1,km 于是称于是称22111()/ ()(1)()iiiinccijiiijn uun uuFcnc , 其中其中21()miikkkuuxx 为第为第i类中心类中心,iiju u元素元素的距离的距离.例例7.2 气象预报中最佳或值的选取气象预报中最佳或值的选取(数据分析见教材数据分析见教材第第156页页).3 用传递闭包法分类需要先建立用传递闭包法分类需要先建立U U上上的模糊等价矩阵的模糊等价矩阵, , 但矩阵阶数较高时但矩阵阶数较高时, , 计算便变得较计算便变得较困难困难. .而采用相似矩阵而采用

8、相似矩阵R R进行分类的进行分类的其计算其计算量则要小很多量则要小很多, ,这种方法聚类的原则是这种方法聚类的原则是: :juiu与与在在 水平上同类水平上同类在在R的图中的图中, 存在一条权重存在一条权重不低于不低于 的路联结的路联结 与与iuju画出以被分类元素为结点画出以被分类元素为结点,以相似矩阵以相似矩阵R的元的元 素素 为权重的一棵最大树为权重的一棵最大树;取定取定0,1,砍断权重低于砍断权重低于 的枝的枝,得到一个不得到一个不连通图连通图,各连通分支便构成了在各连通分支便构成了在 水平上的分类水平上的分类ijr对给定的模糊相似矩阵对给定的模糊相似矩阵R,取定水平取定水平0,1,作

9、作截矩阵截矩阵R ,在在R 主对角线上填入元素的符号主对角线上填入元素的符号,在在对角线下方以结点号对角线下方以结点号”*”代替代替1,而而”0”则略去则略去不写不写,由结点向主对角线上引经线和纬线由结点向主对角线上引经线和纬线,叫叫由经纬线能相互连接起来的元素由经纬线能相互连接起来的元素,属于同类属于同类,从从实现了分类实现了分类.4 1、普通集合上的、普通集合上的c-划分划分集合集合 上的上的是指是指U的的c个子集个子集12,.,nUu uu :1, (2),iAiccn满足：满足：1;niiAU ijAA ()ij 记矩阵记矩阵12()(,) ,Tijc ncAaA AA 其中其中1,i

10、ja 若若jiuA ( 属于第属于第 i 类类);ju0,ija 若若jiuA 满足满足:1,1cijija (表示每个表示每个 属于且只属于某一类属于且只属于某一类)ju1,0nijjian (表示每类表示每类 至少有一个元素至少有一个元素)iA反之反之, 具有上述条件的矩阵具有上述条件的矩阵A对应着对应着U上的一个分类上的一个分类A称为集合称为集合U的一个的一个如给定四元集如给定四元集U一一个分类结果个分类结果1234,uu uu则对应分化矩阵为则对应分化矩阵为100001100001A 1u2u3u4u123若分类矩阵为若分类矩阵为10000100 ,0011A 则对应则对应U的分类的分

11、类为为1234,.uuu u记记c nV 为为cn 实矩阵的集合实矩阵的集合, 且且11(),0,1,1,0cncijc nijijijijMA AaaaanV 称为将称为将U分成分成c类的类的.这样的分类是通这样的分类是通cM常意义下的分类常意义下的分类, 称为称为2、模糊、模糊c-划分划分设设12,.,nUu uu 12(,),jjjjmuxxx 一个一个cn 模糊矩阵模糊矩阵11112122222212nncccnnAaaaAaaaAaaaA 若满足若满足:1,1cijija (表示每个表示每个 属于属于c个模糊子集个模糊子集 的的juiA1,0nijjian (表示每类表示每类 不等于

12、不等于 或或U )iA的程度总和为的程度总和为1);则则A称为称为U的的 记记11(),0,1,1,0cnf cijc nijijijijMA Aaaaan Mf cM称为称为显然显然cf cMM 在目标函数法中在目标函数法中, , 目标函数是对给定目标函数是对给定c c的所有候选分类的所有候选分类进行度量进行度量, ,最优的类就是使目标函数达到局部最小的类最优的类就是使目标函数达到局部最小的类对于硬分类情形对于硬分类情形, , 目标函数一般选为总体组内误差平目标函数一般选为总体组内误差平方和方和. .其定义如下其定义如下: :211( ,)cnijjiijJ A Vauv其中其中 为为 中元

13、素各特征分别取平均值后所得的聚类中元素各特征分别取平均值后所得的聚类iviA中心向量中心向量, 也称也称 的聚类中心的聚类中心.iAiv 11nijjjnijja ua 类中元素向量和类中元素向量和iA类中元素个数类中元素个数iA记记11112122122212mmncccmvvvvvvvvVvvvvV称为称为聚类中心矩阵聚类中心矩阵, 若若 则则 到聚类中心到聚类中心,jiuA juiv的距离为的距离为21()mijjijkikkduvxv 中全体元素到中心距离平方和为中全体元素到中心距离平方和为iA21()nijijjad 而而V中其它元素到其所在类中心距离平方和为中其它元素到其所在类中心

14、距离平方和为211( ,)()cnijijijJ A Vad 211cnijjiijauv最理想的最理想的c-c-划分应该是划分应该是J(A, V)J(A, V)取取极小的极小的A, A, 寻找最小的寻找最小的A A并非易事并非易事, ,这是因为这是因为McMc的容量的容量虽有限但非常大虽有限但非常大, , 最常见的方法是最常见的方法是硬硬c-c-均值算法均值算法: :Step1 假设给出假设给出n n个数据点个数据点12,.,nUu uu 其中其中12(,).mjjjjmuxxxR取定取定c (2cn), 并并初始化初始化(0).cAM Step2 当迭代次数为当迭代次数为(0,1,2,)l

15、 l 时时,计算聚类中计算聚类中心向量心向量( )1( )( )1nlijjjlinlijja uva 其中其中( )( )(),1,2,llijaAicStep3 用下式将用下式将( ) lA更新为更新为(1)(1)()llijAa (1)10lija ( )( )1min()lljijii cuvuv 其它其它和和Step4 比较比较( ) lA(1),lA 若若 (1)(1)llAA ( 是一个非常小的常数是一个非常小的常数),则停止算法则停止算法;否则否则, 令令1,ll 返回返回Step2关于算法的使用说明关于算法的使用说明, , 见教材见教材164-165164-165页页! !定

16、义目标函数定义目标函数211( ,)()cnrmijjiijJA Vauv其中其中r1是一个加权指数是一个加权指数.模糊模糊c-c-均值算法的目标在于找到均值算法的目标在于找到()ijfcAaM和和12(,)(),mcivv vvvR使得使得( ,)mJA V最小最小. .下面的定理给出了上述最小化问题之必要条件下面的定理给出了上述最小化问题之必要条件定理定理 令令12,.,nUu uu 12(,)mjjjjmuxxxR为一给定数据集为一给定数据集. 设设2,3,1cn和和(1,),r假设对所有假设对所有1kn和和1ic,有有0,jiuv则仅则仅当当 2111,1,1ijrcjijjjaicj

17、nuvuv 和和 11,1nijjjinijja uvica 时时,()ijAa 和和12(,)cVv vv 才是才是( ,)mJA V的的局部最小值局部最小值.注注: : 模糊模糊c-c-均值算法是建立在定理必要条件均值算法是建立在定理必要条件( ( ) )和和()的基础上的的基础上的, , 算法步骤如下算法步骤如下: :Step1Step1 给定数据集给定数据集12,.,nUu uu 1(,)jjjmuxx ,mR 设定设定2,3,1cn和和(1,),r并初始化并初始化(0).fcAM Step2Step2 当迭代次数为当迭代次数为(0,1,2,)l l 时时,计算聚类中计算聚类中心向量心

18、向量( )1( )( )1()()nlrijjjlinlrijjauva 1,2,ic Step3Step3 用下式将用下式将( ) lA更新为更新为(1)(1)()llijAa (1)2( )1( )11ijllrcjiljjjauvuv 1,1icjnStep4Step4若若 (1)(1)llAA 则停止算法则停止算法;否则否则, 令令1,ll 返回返回Step2( 是一个非常小的常数是一个非常小的常数), 此算法也称为模糊此算法也称为模糊ISODATA方法方法.遇到只有一个样本的类遇到只有一个样本的类,要在聚类前先排除要在聚类前先排除, 待聚类待聚类后再加上该类后再加上该类, 而参数而参

19、数r一般常取一般常取r=2. 此算法要求此算法要求 ,因此取初始分类因此取初始分类 时时ijvu (0)A 实际问题中实际问题中, 最后的分类结果都要求是明确的最后的分类结果都要求是明确的,因因此此,在使用模糊在使用模糊c-划分分类后划分分类后, 都必须将模糊划分清都必须将模糊划分清晰化晰化,可用下述方法进行可用下述方法进行:方法方法I 对对,juU若若1min()jijkk cuvuv 则将则将ju归入归入iA类类.iA类类.方法方法II 对对,juU若若1max,ijkjk caa 归入归入则将则将ju关于算法的使用说明关于算法的使用说明, , 见教材见教材168-169168-169页页! !例例7.3 模糊模糊ISODATA聚类算法的应用聚类算法的应用(教材第教材第169页页)例例7.4 应用模糊聚类分析对地下水位动态分类应用模糊聚类分析对地下水位动态分类(教材教材 第第170页页)