模糊聚类分析课件.ppt

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

1、第七讲 模糊聚类分析17.1 聚类分析的基本概念聚类分析的基本概念“聚聚类类”就就是是按按照照一一定定的的要要求求和和规规律律对对事事物物进进行行区区分分和和分分类类的的过过程程,在在这这一一过过程程中中没没有有任任何何关关于于分分类类的的先先验验知知识识,仅仅靠靠事事物物间间的的相相似似性性作作为为类类属属划分的准则划分的准则,属于无监督分类的范畴。属于无监督分类的范畴。“聚聚类类分分析析”是是指指用用数数学学的的方方法法研研究究和和处处理理给给定对象的分类。定对象的分类。2聚聚类类分分析析是是多多元元统统计计分分析析的的一一种种,它它把把一一个个没没有有类类别别标标记记的的样样本本集集按按

2、某某种种准准则则划划分分成成若若干干个个子子集集(类类),使使相相似似的的样样本本尽尽可可能能归归为为一一类类,而而不不相相似似的样本尽量划分到不同的类中。的样本尽量划分到不同的类中。传传统统的的聚聚类类分分析析是是一一种种硬硬划划分分,它它把把每每个个待待辨辨识识的的对对象象严严格格地地划划分分到到某某类类中中,具具有有非非此此即即彼彼的的性性质质,因因此此这这种种类类别别划划分分的的界界限限是是分分明明的的。而而实实际际上上大大多多数数对对象象并并没没有有严严格格的的属属性性,它它们们在在性性态态和和类类属属方方面面存存在在着着中中介介性性,具具有有亦亦此此亦亦彼彼的的性性质质,因因此适合

3、进行此适合进行软划分软划分。3模模糊糊集集理理论论的的提提出出为为软软划划分分提提供供了了有有力力的的分分析析工工具具,用用模模糊糊数数学学的的方方法法来来处处理理聚聚类类问问题题,被被称称之之为为模模糊糊聚聚类类分分析析。由由于于模模糊糊聚聚类类得得到到了了样样本本属属于于各各个个类类别别的的不不确确定定性性程程度度,表表达达了了样样本本类类属属的的中中介介性性,更更能能客客观观地地反反映映现现实实世世界界,从从而而成成为为聚类分析研究的主流。聚类分析研究的主流。模模糊糊聚聚类类已已经经在在诸诸多多领领域域获获得得了了广广泛泛的的应应用用,如如模模式式识识别别、图图像像处处理理、信信道道均均

4、衡衡、矢矢量量量量化化编编码码、神神经经网网络络的的训训练练、参参数数估估计计、医医学学诊诊断断、天气预报、食品分类、水质分析等。天气预报、食品分类、水质分析等。4常常用用的的模模糊糊聚聚类类分分析析方方法法大大致致可可分分为为两两大大类类：其其一一是是基基于于模模糊糊关关系系(矩矩阵阵)的的聚聚类类分分析析方方法法,而而作作为为其其中中核核心心步步骤骤的的模模糊糊分分类类,有有下下述述的的主主要要方方法法：模模糊糊传传递递闭闭包包法法、直直接接聚聚类类法法、最最大大树树法法和和编编网网法法;其其二二是是基基于于目目标标函函数数的的聚聚类类分分析析方方法法,称称为为模模糊糊C均均值值(FCM)

5、聚聚类类算算法法(或或称称为为模模糊糊ISODATA聚类分析法聚类分析法)。第第一一类类方方法法,作作为为准准备备先先讲讲解解模模糊糊关关系系传传递递闭闭包包的基本概念。的基本概念。57.2 模糊关系的传递闭包模糊关系的传递闭包设设R F(X X).则则R是是模模糊糊等等价价关关系系当当且且仅仅当当对对任意任意 0,1,R 是等价关系。是等价关系。论论域域X上上的的经经典典等等价价关关系系可可以以导导出出X的的一一个个分分类类。论论域域X上上的的一一个个模模糊糊等等价价关关系系R对对应应一一族族经经典典等等价价关关系系R:0,1.这这说说明明模模糊糊等等价价关关系系给给出出X的的一一个个分分类

6、类的的系系列列。这这样样,在在实实际际应应用用问问题题中中可可以以选选择择“某某个个水水平平”上上的的分分类类结结果果,这这就就是是模模糊聚类分析的理论基础。糊聚类分析的理论基础。实实际际问问题题中中建建立立的的模模糊糊关关系系常常常常不不是是等等价价关关系系而而是是相相似似关关系系,这这就就需需要要将将模模糊糊相相似似关关系系改改造造为为模糊等价关系模糊等价关系,传递闭包正是这样一种工具。传递闭包正是这样一种工具。6定定义义 设设R F(X X).若若R1 F(X X)是是传传递递的的且且满满足：足：1)R R1,2)若若S是是X上的模糊传递关系且上的模糊传递关系且R S,必有必有R1 S.

7、则称则称R1为为R的传递闭包的传递闭包,记为记为t(R).模糊关系模糊关系R的传递闭包是包含的传递闭包是包含R的最小传递关系的最小传递关系。定理定理 设设R F(X X).则则 t(R)=n=1 Rn.7(n=1 Rn)(m=1 Rm)=n=1 Rn (m=1 Rm)=n=1 m=1 (Rn Rm)=k=2 (n+m=k Rn+m)=k=2 Rk k=1 Rk.这这说说明明n=1 Rn是是传传递递的的。又又,显显然然R n=1 Rn.即即n=1 Rn是包含是包含R的模糊传递关系。的模糊传递关系。若有若有X上的模糊传递关系上的模糊传递关系S满足满足R S,下证下证n=1 Rn S (即证明即证明

8、n=1 Rn“最小最小”)由由R S得得 R2 S2 S,R3=R R2 R S S2 S,证明：证明：8 一般地一般地,Rn S,n N.于是于是n=1 Rn S.综综上上所所述述,n=1 Rn是是包包含含R的的最最小小传传递递关关系系,因因而是而是R的传递闭包的传递闭包,即即t(R)=n=1 Rn.在论域有限的情况下在论域有限的情况下,传递闭包的计算更简捷传递闭包的计算更简捷:定理定理 设设|X|=n,R F(X X).则则 t(R)=k=1nRk.计计算算有有限限论论域域上上自自反反模模糊糊关关系系R的的传传递递闭闭包包的的方方法法：从从R出出发发,反反复复自自乘乘,依依次次计计算算出出

9、R2,R4,当第一次出现当第一次出现Rk Rk=Rk时得时得t(R)=Rk.9定定理理 设设R F(X X).则则R的的传传递递闭闭包包t(R)具具有有以以下性质下性质:(1)若若I R,则则 I t(R);(2)(t(R)1=t(R 1);(3)若若R=R 1,则则(t(R)1=t(R).上上述述结结论论表表明明：自自反反关关系系的的传传递递闭闭包包是是自自反反的的,对对称称关关系系的的传传递递闭闭包包是是对对称称的的。于于是是,模模糊糊相相似似关系的传递闭包是模糊等价关系。关系的传递闭包是模糊等价关系。例例 设设|X|=5,R是是X上上的的模模糊糊关关系系,R可可表表示示为为如如下下的的5

10、5模糊矩阵。求模糊矩阵。求R的传递闭包。的传递闭包。10解解 容容易易看看出出R是是自自反反的的对对称称模模糊糊关关系系(即即模模糊糊相相似似关关系系)。依依次次计计算算R2,R4,R8知知:R8=R4 R4=R4(参参见下页计算结果见下页计算结果),所以所以R的传递闭包的传递闭包 t(R)=R4.11127.3 7.3 基于模糊关系的聚类分析基于模糊关系的聚类分析基基于于模模糊糊关关系系的的聚聚类类分分析析的的一一般般步步骤骤:(1)数数据据规格化规格化;(2)构造模糊相似矩阵构造模糊相似矩阵;(3)模糊分类。模糊分类。上上述述第第三三步步又又有有不不同同的的算算法法,以以下下先先介介绍绍利

11、利用用模模糊传递闭包进行模糊分类的方法。糊传递闭包进行模糊分类的方法。设设被被分分类类对对象象的的集集合合为为X=x1,x2,xn,每每一一个个对对象象xi有有m个个特特性性指指标标(反反映映对对象象特特征征的的主主要要指指标标),即即xi可由如下可由如下m维维特性指标向量特性指标向量来表示来表示:xi=(xi1,xi1,xim),i=1,2,n其其中中xij表表示示第第i个个对对象象的的第第j个个特特性性指指标标。则则n个个对对象象的的所所有有特特性性指指标标构构成成一一个个矩矩阵阵,记记作作X*=(xij)nm,称称X*为为X的的特性指标矩阵特性指标矩阵。13步骤一：数据规格化步骤一：数据

12、规格化由由于于m个个特特性性指指标标的的量量纲纲和和数数量量级级不不一一定定相相同同,故故在在运运算算过过程程中中可可能能突突出出某某数数量量级级特特别别大大的的特特性性指指标标对对分分类类的的作作用用,而而降降低低甚甚至至排排除除了了某某些些数数量量级级很很小小的的特特性性指指标标的的作作用用。数数据据规规格格化化使使每每一一个个指指标标值统一于某种共同的数值特性范围。值统一于某种共同的数值特性范围。14数据规格化的方法有：数据规格化的方法有：(1)标标准准化化方方法法:对对特特性性指指标标矩矩阵阵X*的的第第j列列,计计算均值和方差算均值和方差,然后作变换然后作变换15(2)均均值值规规格

13、格化化方方法法:对对特特性性指指标标矩矩阵阵X*的的第第j列列,计计算算标标准准差差 j,然然后后作作变变换换 xij =xij/j,i=1,2,n,j=1,2,m.(3)中中心心规规格格化化方方法法:对对特特性性指指标标矩矩阵阵X*的的第第j列列,计计算算平平均均值值xj,然然后后作作变变换换 xij =xij xj,i=1,2,n,j=1,2,m.(4)最最大大值值规规格格化化方方法法:对对特特性性指指标标矩矩阵阵X*的的第第j列列,计计算算最最大大值值 Mj=maxx1j,x2j,xnj,j=1,2,m.然然后后作作变变换换 xij =xij/Mj,i=1,2,n,j=1,2,m.16步

14、骤二：构造模糊相似矩阵步骤二：构造模糊相似矩阵聚聚类类是是按按某某种种标标准准来来鉴鉴别别X中中元元素素间间的的接接近近程程度度,把把彼彼此此接接近近的的对对象象归归为为一一类类。为为此此,用用0,1中中的的数数rij表表示示X中中的的元元素素xi与与xj的的接接近近或或相相似似程程度度。经经典典聚聚类类分分析析中中的的相相似似系系数数以以及及模模糊糊集集之之间间的的贴近度贴近度,都可作为相似程度都可作为相似程度(相似系数相似系数)。设设数数据据xij(i=1,2,n,j=1,2,m)均均已已规规格格化化,xi=(xi1,xi2,xim)与与xj=(xj1,xj2,xjm)之之间间的的相相似似

15、程程度度记记为为rij 0,1,于于是是得得到到对对象象之之间间的的模模糊相似矩阵糊相似矩阵R=(rij)nn.17对对于于相相似似程程度度(相相似似系系数数)的的确确定定,有有多多种种方方法法,常常用的有：用的有：(1)数量积法数量积法其其中中M0为为适适当当选选择择的的参参数数且且满满足足M maxxi xj|i j.这里这里,xi xj为为xi与与xj的数量积的数量积.18(2)夹角余弦法夹角余弦法(3)相关系数法相关系数法19(4)贴近度法贴近度法当当对对象象xi的的特特性性指指标标向向量量xi=(xi1,xi2,xim)为为模模糊糊向向量量,即即xik 0,1(i=1,2,n;k=1

16、,2,m)时时,xi与与xj的的相相似似程程度度rij可可看看作作模模糊糊子子集集xi与与xj的的贴贴近近度度。在在应应用用中中,常常见见的的确确定定方方法法有有：最最大大最最小法、算术平均最小法、几何平均最小法。小法、算术平均最小法、几何平均最小法。20(5)距离法距离法利利用用对对象象xi与与xj的的距距离离也也可可以以确确定定它它们们的的相相似似程程度度rij,这这是是因因为为d(xi,xj)越越大大,rij就就越越小小。一一般般地地,取取rij=1 c(d(xi,xj),其其中中c和和 是是两两个个适适当当选选取取的的正正数数,使使rij 0,1.在在实实际际应应用用中中,常常采采用用

17、如如下下的距离来确定的距离来确定rij.21(6)绝对值倒数法绝对值倒数法如如右右所所示示,其其中中c是是适适当当选选取取的的正正数数,使使 rij 0,1.22(7)主观评定法主观评定法在在一一些些实实际际问问题题中中,被被分分类类对对象象的的特特性性指指标标是是定定性性指指标标,即即特特性性指指标标难难以以用用定定量量数数值值来来表表达达。这这时时,可可请请专专家家和和有有实实际际经经验验的的人人员员用用评评分分的的办办法法来主观评定被分类对象间的相似程度。来主观评定被分类对象间的相似程度。步骤三：模糊分类步骤三：模糊分类由由于于由由上上述述各各种种方方法法构构造造出出的的对对象象与与对对

18、象象之之间间的的模模糊糊关关系系矩矩阵阵R=(rij)nn,一一般般说说来来只只是是一一个个模模糊糊相相似似矩矩阵阵,而而不不一一定定具具有有传传递递性性。因因此此,要要从从R出出发发构构造造一一个个新新的的模模糊糊等等价价矩矩阵阵,然然后后以以此此模模糊等价矩阵作为基础糊等价矩阵作为基础,进行动态聚类。进行动态聚类。23如如上上所所述述,模模糊糊相相似似矩矩阵阵R的的传传递递闭闭包包t(R)就就是是一一个个模模糊糊等等价价矩矩阵阵。以以t(R)为为基基础础而而进进行行分分类类的的聚类方法称为聚类方法称为模糊传递闭包法模糊传递闭包法。具具体体步步骤骤如如下下:(1)利利用用平平方方自自合合成成

19、方方法法求求出出模模糊糊相相似似矩矩阵阵R的的传传递递闭闭包包t(R);(2)适适当当选选取取置置信信水水平平值值 0,1,求求出出t(R)的的 截截矩矩阵阵t(R),它它是是X上上的的一一个个等等价价的的Boole矩矩阵阵。然然后后按按t(R)进进行行分分类类,所得到的分类就是在所得到的分类就是在 水平上的等价分类。水平上的等价分类。24对对于于xi,xj X,若若r ij()=1,则则在在 水水平平上上将将对对象象xi和对象和对象xj 归为同一类。归为同一类。(3)画画动动态态聚聚类类图图:为为了了能能直直观观地地看看到到被被分分类类对对象象之之间间的的相相关关程程度度,通通常常将将t(R

20、)中中所所有有互互不不相相同同的的元元素素按按从从大大到到小小的的顺顺序序编编排排:1=1 2 得得到到按按t(R)进进行行的的一一系系列列分分类类。将将这这一一系系列列分分类类画在同一个图上画在同一个图上,即得动态聚类图。即得动态聚类图。例例 考考虑虑某某个个环环保保部部门门对对该该地地区区5个个环环境境区区域域 X=x1,x2,x3,x4,x5按按污污染染情情况况进进行行分分类类。设设每每个个区域包含空气、水分、土壤、作物区域包含空气、水分、土壤、作物4个要素。个要素。25 环环境境区区域域的的污污染染情情况况由由污污染染物物在在4个个要要素素中中的的含含量量超超标标程程度度来来衡衡量量。

21、设设这这5个个环环境境区区域域的的污污染染数数据据为为x1=(80,10,6,2),x2=(50,1,6,4),x3=(90,6,4,6),x4=(40,5,7,3),x5=(10,1,2,4).试试用用模模糊糊传传递闭包法对递闭包法对X进行分类。进行分类。解解 由题设知特性指标矩阵为由题设知特性指标矩阵为:(1)数数据据规规格格化化:采采用用最最大大值值规规格格化化,作作变变换换xij=xij/Mj,i=1,2,5,j=1,2,4.可将可将X*规格化为规格化为:26(2)构构造造模模糊糊相相似似矩矩阵阵:采采用用最最大大最最小小法法来来构构造造模模糊糊相相似似矩矩阵阵R=(rij)5 5,这

22、里这里27(3)利用平方自合成方法求传递闭包利用平方自合成方法求传递闭包t(R)依依次次计计算算R2,R4,R8,由由于于R8=R4(见见下下页页的的计计算算结结果果),所以所以t(R)=R4.28(4)选选取取适适当当的的置置信信水水平平值值 0,1,按按 截截矩矩阵阵t(R)进进行行动动态态聚聚类类。把把t(R)中中的的元元素素从从大大到到小小的的顺顺序序编编排排如如下下:10.700.63062053.依依次次取取=1,0.70,0.63,062,053得得:29这这时时X被被分分类类成成5类类:x1,x2,x3,x4,x5.X被被分分类类成成4类类:x1,x2,x4,x3,x5.30这这时时X被被分分类类成成3类类:x1,x2,x4,x3,x5.X被被分分类类成成2类类:x1,x2,x3,x4,x5.31这这时时X被被分分类类成成1类类:x1,x2,x3 x4,x5.32