模糊聚类分析

1、第七讲 模糊聚类分析,7.1 聚类分析的基本概念,“聚类”就是按照一定的要求和规律对事物进行区分和分类的过程, 在这一过程中没有任何关于分类的先验知识, 仅靠事物间的相似性作为类属划分的准则, 属于无监督分类的范畴。 “聚类分析”是指用数学的方法研究和处理给定对象的分类。,聚类分析是多元统计分析的一种, 它把一个没有类别标记的样本集按某种准则划分成若干个子集(类), 使相似的样本尽可能归为一类, 而不相似的样本尽量划分到不同的类中。 传统的聚类分析是一种硬划分, 它把每个待辨识的对象严格地划分到某类中, 具有非此即彼的性质, 因此这种类别划分的界限是分明的。而实际上大多数对象并没有严格的属性,

2、 它们在性态和类属方面存在着中介性, 具有亦此亦彼的性质,因此适合进行软划分。,模糊集理论的提出为软划分提供了有力的分析工具, 用模糊数学的方法来处理聚类问题, 被称之为模糊聚类分析。由于模糊聚类得到了样本属于各个类别的不确定性程度, 表达了样本类属的中介性, 更能客观地反映现实世界, 从而成为聚类分析研究的主流。 模糊聚类已经在诸多领域获得了广泛的应用, 如模式识别、图像处理、信道均衡、矢量量化编码、神经网络的训练、参数估计、医学诊断、天气预报、食品分类、水质分析等。,常用的模糊聚类分析方法大致可分为两大类：其一是基于模糊关系(矩阵)的聚类分析方法, 而作为其中核心步骤的模糊分类,有下述的主

3、要方法：模糊传递闭包法、直接聚类法、最大树法和编网法; 其二是基于目标函数的聚类分析方法, 称为模糊C均值(FCM)聚类算法(或称为模糊ISODATA聚类分析法)。 第一类方法, 作为准备先讲解模糊关系传递闭包的基本概念。,7.2 模糊关系的传递闭包,设RF(XX). 则R是模糊等价关系当且仅当对任意0, 1, R是等价关系。 论域X上的经典等价关系可以导出X的一个分类。论域X上的一个模糊等价关系R对应一族经典等价关系R: 0, 1. 这说明模糊等价关系给出X的一个分类的系列。这样, 在实际应用问题中可以选择“某个水平”上的分类结果, 这就是模糊聚类分析的理论基础。 实际问题中建立的模糊关系常

4、常不是等价关系而是相似关系, 这就需要将模糊相似关系改造为模糊等价关系, 传递闭包正是这样一种工具。,定义 设RF(XX). 若R1F(XX)是传递的且满足：1) RR1, 2) 若S是X上的模糊传递关系且RS, 必有R1S. 则称R1为R的传递闭包, 记为t(R). 模糊关系R的传递闭包是包含R的最小传递关系。 定理 设RF(XX). 则 t(R)=n=1Rn.,(n=1Rn) (m=1Rm) =n=1 Rn (m=1Rm) =n=1 m=1 (Rn Rm) =k=2 (n+m=k Rn+m) =k=2Rk k=1Rk. 这说明n=1Rn是传递的。又, 显然Rn=1Rn.即n=1Rn是包含R

5、的模糊传递关系。 若有X上的模糊传递关系S满足RS, 下证 n=1Rn S (即证明n=1Rn “最小”) 由RS得 R2S2S, R3= R R2 R S S2S, ,证明：,一般地, RnS, nN. 于是n=1Rn S. 综上所述,n=1Rn是包含R的最小传递关系, 因而是R的传递闭包, 即t(R)=n=1Rn. 在论域有限的情况下, 传递闭包的计算更简捷: 定理 设|X|=n, RF(XX). 则 t(R)=k=1nRk.,计算有限论域上自反模糊关系R的传递闭包的方法：从R出发, 反复自乘, 依次计算出R2, R4, ,当第一次出现Rk Rk=Rk时得t(R)=Rk.,定理 设RF(X

6、X). 则R的传递闭包t(R)具有以下性质: (1) 若IR, 则 I t(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=R4 R4=R4 (参见下页计算结果), 所以R的传递闭包 t(R)=R4.,7.3 基于模糊关系的聚类分析,基于模糊关系的

7、聚类分析的一般步骤: (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个特性指标的量纲和数量级不一定相同,故在运算过程

8、中可能突出某数量级特别大的特性指标对分类的作用, 而降低甚至排除了某些数量级很小的特性指标的作用。数据规格化使每一个指标值统一于某种共同的数值特性范围。,数据规格化的方法有： (1) 标准化方法: 对特性指标矩阵X*的第j列, 计算均值和方差, 然后作变换,(2) 均值规格化方法: 对特性指标矩阵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) 最大值

9、规格化方法: 对特性指标矩阵X*的第j列, 计算最大值 Mj=maxx1j, x2j, , xnj , j=1, 2, , m. 然后作变换 xij =xij /Mj, i=1, 2, , n, j=1, 2, , m.,步骤二：构造模糊相似矩阵 聚类是按某种标准来鉴别X中元素间的接近程度, 把彼此接近的对象归为一类。为此, 用0, 1中的数rij表示X中的元素xi与xj的接近或相似程度。经典聚类分析中的相似系数以及模糊集之间的贴近度, 都可作为相似程度(相似系数)。 设数据xij(i=1, 2, , n, j=1, 2, , m)均已规格化, xi=(xi1, xi2, , xim)与xj=

10、(xj1, xj2, , xjm)之间的相似程度记为rij0, 1, 于是得到对象之间的模糊相似矩阵R=(rij)nn.,对于相似程度(相似系数)的确定, 有多种方法, 常用的有： (1) 数量积法,其中M0为适当选择的参数且满足Mmaxxixj | i j. 这里, xixj为xi与xj的数量积.,(2) 夹角余弦法,(3) 相关系数法,(4) 贴近度法 当对象xi的特性指标向量xi=(xi1, xi2, , xim)为模糊向量, 即xik0, 1 (i=1,2, ,n ; k=1,2, ,m)时, xi与xj的相似程度rij可看作模糊子集xi与xj的贴近度。在应用中, 常见的确定方法有：最

11、大最小法、算术平均最小法、几何平均最小法。,(5) 距离法 利用对象xi与xj的距离也可以确定它们的相似程度rij, 这是因为d(xi, xj)越大, rij就越小。一般地,取rij = 1 c (d(xi, xj), 其中c和是两个适当选取的正数, 使rij0, 1. 在实际应用中, 常采用如下的距离来确定rij.,(6) 绝对值倒数法 如右所示, 其中c是适当选取的正数, 使 rij0, 1.,(7) 主观评定法 在一些实际问题中,被分类对象的特性指标是定性指标, 即特性指标难以用定量数值来表达。这时, 可请专家和有实际经验的人员用评分的办法来主观评定被分类对象间的相似程度。 步骤三：模糊

12、分类 由于由上述各种方法构造出的对象与对象之间的模糊关系矩阵R=(rij)nn, 一般说来只是一个模糊相似矩阵, 而不一定具有传递性。因此, 要从R出发构造一个新的模糊等价矩阵, 然后以此模糊等价矩阵作为基础, 进行动态聚类。,如上所述, 模糊相似矩阵R的传递闭包t(R)就是一个模糊等价矩阵。以t(R)为基础而进行分类的聚类方法称为模糊传递闭包法。 具体步骤如下: (1) 利用平方自合成方法求出模糊相似矩阵R的传递闭包t(R); (2) 适当选取置信水平值0, 1, 求出t(R)的截矩阵t(R), 它是X上的一个等价的Boole矩阵。然后按t(R)进行分类, 所得到的分类就是在水平上的等价分类

13、。,对于xi, xjX, 若rij()=1, 则在水平上将对象xi和对象xj 归为同一类。 (3) 画动态聚类图:为了能直观地看到被分类对象之间的相关程度, 通常将t(R)中所有互不相同的元素按从大到小的顺序编排: 1=12 得到按t(R)进行的一系列分类。将这一系列分类画在同一个图上, 即得动态聚类图。 例 考虑某个环保部门对该地区5个环境区域 X= x1, x2, x3, x4, x5按污染情况进行分类。设每个区域包含空气、水分、土壤、作物4个要素。,环境区域的污染情况由污染物在4个要素中的含量超标程度来衡量。设这5个环境区域的污染数据为x1=(80, 10, 6, 2), x2=(50,

14、 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*规格化为:,(2) 构造模糊相似矩阵: 采用最大最小法来构造模糊相似矩阵R=(rij)55, 这里,(3) 利用平方自合成方法求传递闭包t(R) 依次计算R2, R4, R8, 由于R8=R4 (见下页的计算结果), 所以t(R)=R4.,(4) 选取适当的置信水平值0, 1, 按截矩阵t(R) 进行动态聚