模糊聚类分析.ppt

模糊聚类分析(一),1聚类分析的基本概念,“聚类”就是按照一定的要求和规律对事物进行区分和分类的过程,在这一过程中没有任何关于分类的先验知识,仅靠事物间的相似性作为类属划分的准则,属于无监督分类的范畴。“聚类分析”是指用数学的方法研究和处理给定对象的分类。“人以群分,物以类聚”,聚类是一个古老的问题,它伴随着人类社会的产生和发展而不断深化,人类要认识世界就必须区别不同的事物并认识事物间的相似性。,聚类分析的基本概念,聚类分析是多元统计分析的一种,它把一个没有类别标记的样本集按某种准则划分成若干个子集(类),使相似的样本尽可能归为一类,而不相似的样本尽量划分到不同的类中。传统的聚类分析是一种硬划分,它把每个待辨识的对象严格地划分到某类中,具有非此即彼的性质,因此这种类别划分的界限是分明的。而实际上大多数对象并没有严格的属性,它们在性态和类属方面存在着中介性,具有亦此亦彼的性质,因此适合进行软划分。,聚类分析的基本概念,模糊集理论的提出为软划分提供了有力的分析工具,用模糊数学的方法来处理聚类问题,被称之为模糊聚类分析。由于模糊聚类得到了样本属于各个类别的不确定性程度,表达了样本类属的中介性,更能客观地反映现实世界,从而成为聚类分析研究的主流。模糊聚类已经在诸多领域获得了广泛的应用,如模式识别、图像处理、信道均衡、矢量量化编码、神经网络的训练、参数估计、医学诊断、天气预报、食品分类、水质分析等。,聚类分析的基本概念,常用的模糊聚类分析方法大致可分为两大类：其一是基于模糊关系(矩阵)的聚类分析方法,而作为其中核心步骤的模糊分类,有下述的主要方法：模糊传递闭包法、直接聚类法、最大树法和编网法;其二是基于目标函数的聚类分析方法,称为模糊C均值(FCM)聚类算法(或称为模糊ISODATA聚类分析法)。本讲先介绍第一类方法,作为准备先讲解模糊关系传递闭包的基本概念。,模糊关系的传递闭包,设X,Y是非空经典集,X到Y的一个模糊(二元)关系R是指XY上的一个模糊集R:XY0,1.X到X的模糊关系称为X上的模糊关系。设R是X上的模糊关系,即RF(XX).称R是自反的,如果R(x,x)=1,xX.称R是对称的,如果R(x,y)=R(y,x),x,yX.若R是X上的自反、对称的模糊关系,则称R是X上的模糊相似关系。,模糊关系,某家庭子女和父母外貌相像关系为R,父母和祖父母、外祖父母相像关系为S,它们分别用以下模糊矩阵确定,计算其max-min合成。,模糊关系的传递闭包,设RF(XX).称R是传递的,如果对任意0,1及任意x,y,zX成立:R(x,y),R(y,z)R(x,z).若R是X上的自反、对称、传递的模糊关系,则称R是X上的模糊等价关系。设RF(XX).则(1)R是自反的IR,这里I是恒等关系,即当x=y时I(x,y)=1,当xy时I(x,y)=0.(2)R是对称的R=R1.(3)R是传递的R2R.,模糊关系的传递闭包,设RF(XX).则R是模糊等价关系当且仅当对任意0,1,R是等价关系。论域X上的经典等价关系可以导出X的一个分类。论域X上的一个模糊等价关系R对应一族经典等价关系R:0,1.这说明模糊等价关系给出X的一个分类的系列。这样,在实际应用问题中可以选择“某个水平”上的分类结果,这就是模糊聚类分析的理论基础。实际问题中建立的模糊关系常常不是等价关系而是相似关系,这就需要将模糊相似关系改造为模糊等价关系,传递闭包正是这样一种工具。,模糊关系的传递闭包,定义9.2.1设RF(XX).若R1F(XX)是传递的且满足：1)RR1,2)若S是X上的模糊传递关系且RS,必有R1S.则称R1为R的传递闭包,记为t(R).根据上述定义,模糊关系R的传递闭包是包含R的最小传递关系。定理9.2.2设RF(XX).则t(R)=n=1Rn.证明：容易验证A,BiF(XX),Ai=1Bi=i=1(ABi),(i=1Bi)A=i=1(BiA).据此可以证明n=1Rn是传递的：,模糊关系的传递闭包,计算有限论域上自反模糊关系R的传递闭包的方法：从R出发,反复自乘,依次计算出R2,R4,当第一次出现RkRk=Rk时得t(R)=Rk.,模糊关系的传递闭包,定理9.2.5设RF(XX).则R的传递闭包t(R)具有以下性质:(1)若IR,则It(R);(2)(t(R)1=t(R1);(3)若R=R1,则(t(R)1=t(R).上述结论表明：自反关系的传递闭包是自反的,对称关系的传递闭包是对称的。于是,模糊相似关系的传递闭包是模糊等价关系。例设|X|=5,R是X上的模糊关系,R可表示为如下的55模糊矩阵。求R的传递闭包。,模糊关系的传递闭包,解容易看出R是自反的对称模糊关系(即模糊相似关系)。依次计算R2,R4,R8知:R8=R4R4=R4(参见下页计算结果),所以R的传递闭包t(R)=R4.,基于模糊关系的聚类分析,基于模糊关系的聚类分析的一般步骤:(1)数据规格化;(2)构造模糊相似矩阵;(3)模糊分类。上述第三步又有不同的算法,以下先介绍利用模糊传递闭包进行模糊分类的方法。设被分类对象的集合为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的特性指标矩阵。,基于模糊关系的聚类分析,步骤一：数据规格化由于m个特性指标的量纲和数量级不一定相同,故在运算过程中可能突出某数量级特别大的特性指标对分类的作用,而降低甚至排除了某些数量级很小的特性指标的作用。数据规格化使每一个指标值统一于某种共同的数值特性范围。,基于模糊关系的聚类分析,数据规格化的方法有：(1)标准化方法:对特性指标矩阵X*的第j列,计算均值和方差,然后作变换,基于模糊关系的聚类分析,(2)均值规格化方法:对特性指标矩阵X*的第j列,计算标准差j,然后作变换xij=xij/j,i=1,2,n,j=1,2,m.(3)中心规格化方法:对特性指标矩阵X*的第j列,计算平均值xj,然后作变换xij=xijxj,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.,9.3基于模糊关系的聚类分析,步骤二：构造模糊相似矩阵聚类是按某种标准来鉴别X中元素间的接近程度,把彼此接近的对象归为一类。为此,用0,1中的数rij表示X中的元素xi与xj的接近或相似程度。经典聚类分析中的相似系数以及模糊集之间的贴近度,都可作为相似程度(相似系数)。设数据xij(i=1,2,n,j=1,2,m)均已规格化,xi=(xi1,xi2,xim)与xj=(xj1,xj2,xjm)之间的相似程度记为rij0,1,于是得到对象之间的模糊相似矩阵R=(rij)nn.,9.3基于模糊关系的聚类分析,对于相似程度(相似系数)的确定,有多种方法,常用的有：(1)数量积法,其中M0为适当选择的参数且满足Mmaxxixj|ij.这里,xixj为xi与xj的数量积.,9.3基于模糊关系的聚类分析,(2)夹角余弦法,(3)相关系数法,9.3基于模糊关系的聚类分析,(4)贴近度法当对象xi的特性指标向量xi=(xi1,xi2,xim)为模糊向量,即xik0,1(i=1,2,n;k=1,2,m)时,xi与xj的相似程度rij可看作模糊子集xi与xj的贴近度。在应用中,常见的确定方法有：最大最小法、算术平均最小法、几何平均最小法。,9.3基于模糊关系的聚类分析,(5)距离法利用对象xi与xj的距离也可以确定它们的相似程度rij,这是因为d(xi,xj)越大,rij就越小。一般地,取rij=1c(d(xi,xj),其中c和是两个适当选取的正数,使rij0,1.在实际应用中,常采用如下的距离来确定rij.,9.3基于模糊关系的聚类分析,(6)绝对值倒数法如右所示,其中c是适当选取的正数,使rij0,1.,9.3基于模糊关系的聚类分析,(7)主观评定法在一些实际问题中,被分类对象的特性指标是定性指标,即特性指标难以用定量数值来表达。这时,可请专家和有实际经验的人员用评分的办法来主观评定被分类对象间的相似程度。步骤三：模糊分类由于由上述各种方法构造出的对象与对象之间的模糊关系矩阵R=(rij)nn,一般说来只是一个模糊相似矩阵,而不一定具有传递性。因此,要从R出发构造一个新的模糊等价矩阵,然后以此模糊等价矩阵作为基础,进行动态聚类。,9.3基于模糊关系的聚类分析,如上所述,模糊相似矩阵R的传递闭包t(R)就是一个模糊等价矩阵。以t(R)为基础而进行分类的聚类方法称为模糊传递闭包法。具体步骤如下:(1)利用平方自合成方法求出模糊相似矩阵R的传递闭包t(R);(2)适当选取置信水平值0,1,求出t(R)的截矩阵t(R),它是X上的一个等价的Boole矩阵。然后按t(R)进行分类,所得到的分类就是在水平上的等价分类。,9.3基于模糊关系的聚类分析,对于xi,xjX,若rij()=1,则在水平上将对象xi和对象xj归为同一类。(3)画动态聚类图:为了能直观地看到被分类对象之间的相关程度,通常将t(R)中所有互不相同的元素按从大到小的顺序编排:1=12得到按t(R)进行的一系列分类。将这一系列分类画在同一个图上,即得动态聚类图。例考虑某个环保部门对该地区5个环境区域X=x1,x2,x3,x4,x5按污染情况进行分类。设每个区域包含空气、水分、土壤、作物4个要素。,9.3基于模糊关系的聚类分析,环境区域的污染情况由污染物在4个要素中的含量超标程度来衡量。设这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*规格化为:,9.3基于模糊关系的聚类分析,(2)构造模糊相似矩阵:采用最大最小法来构造模糊相似矩阵R=(rij)55,这里,9.3基于模糊关系的聚类分析,(3)利用平方自合成方法求传递闭包t(R)依次计算R2,R4,R8,由于R8=R4(见下页的计算结果),所以t(R)=R4.,9.3基于模糊关系的聚类分析,(4)选取适当的置信水平值0,1,按截矩阵t(R)进行动态聚类。把t(R)中的元素从大到小的顺序编排如下:10.700.63062053.依次取=1,0.70,0.63,062,053得:,9.3基于模糊关系的聚类分析,这时X被分类成5类:x1,x2,x3,x4,x5.,X被分类成4类:x1,x2,x4,x3,x5.,9.3基于模糊关系的聚类分析,这时X被分类成3类:x1,x2,x4,x3,x5.,X被分类成2类:x1,x2,x3,x4,x5.,9.3基于模糊关系的聚类分析,这时X被分类成1类:x1,x2,x3x4,x5.,9.4求模糊传递闭包的C程序,当被分类对象很多时,计算模糊相似矩阵R的传递闭包的工作量很大。为了减少计算工作量,以下介绍求解模糊传递闭包的C语言程序。使用本程序时,需要输入下列数据:N模糊相似关系矩阵的阶数;矩阵R模糊相似关系矩阵,以RIJ表示其元素,其中I,J=0,1,2,N1.矩阵R的元素应一行一行地输入。将相似关系矩阵R改造成为模糊等价关系矩阵R*是采用平方自合成方法求R的传递闭包t(R),即R*=t(R).,9.4求模糊传递闭包的C程序,t(R)的计算方法:首先,计算RR,若RRR,则取R*=R.否则,再计算(RR)(RR),这种过程继续进行直到相邻两次所得到的平方