模糊聚类分析

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

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

3、方面存在着中介性类属方面存在着中介性, 具有亦此亦彼的性质具有亦此亦彼的性质,因此适合进行因此适合进行软划分软划分。2021/3/234 模糊集理论的提出为软划分提供了有力的分析模糊集理论的提出为软划分提供了有力的分析工具工具, 用模糊数学的方法来处理聚类问题用模糊数学的方法来处理聚类问题, 被称被称之为模糊聚类分析。由于模糊聚类得到了样本之为模糊聚类分析。由于模糊聚类得到了样本属于各个类别的不确定性程度属于各个类别的不确定性程度, 表达了样本类属表达了样本类属的中介性的中介性, 更能客观地反映现实世界更能客观地反映现实世界, 从而成为从而成为聚类分析研究的主流。聚类分析研究的主流。 模糊聚类

4、已经在诸多领域获得了广泛的应用模糊聚类已经在诸多领域获得了广泛的应用, 如如模式识别、图像处理、信道均衡、矢量量化编模式识别、图像处理、信道均衡、矢量量化编码、神经网络的训练、参数估计、医学诊断、码、神经网络的训练、参数估计、医学诊断、天气预报、食品分类、水质分析等。天气预报、食品分类、水质分析等。 2021/3/235 常用的模糊聚类分析方法大致可分为两大类常用的模糊聚类分析方法大致可分为两大类:其其一是基于模糊关系一是基于模糊关系(矩阵矩阵)的聚类分析方法的聚类分析方法, 而作而作为其中核心步骤的模糊分类为其中核心步骤的模糊分类,有下述的主要方法有下述的主要方法:模糊传递闭包法、直接聚类法

5、、最大树法和编模糊传递闭包法、直接聚类法、最大树法和编网法网法; 其二是基于目标函数的聚类分析方法其二是基于目标函数的聚类分析方法, 称称为模糊为模糊C均值均值(FCM)聚类算法聚类算法(或称为模糊或称为模糊ISODATA聚类分析法聚类分析法)。 第一类方法第一类方法, 作为准备先讲解模糊关系传递闭包作为准备先讲解模糊关系传递闭包的基本概念。的基本概念。2021/3/2367.2 模糊关系的传递闭包模糊关系的传递闭包 设设R F(X X). 则则R是模糊等价关系当且仅当对是模糊等价关系当且仅当对任意任意 0, 1, R 是等价关系。是等价关系。 论域论域X上的经典等价关系可以导出上的经典等价关

6、系可以导出X的一个分类。的一个分类。论域论域X上的上的一个模糊等价关系一个模糊等价关系R对应一族经典等对应一族经典等价关系价关系R : 0, 1. 这说明模糊等价关系给出这说明模糊等价关系给出X的一个分类的系列。这样的一个分类的系列。这样, 在实际应用问题中在实际应用问题中可以选择可以选择“某个水平某个水平”上的分类结果上的分类结果, 这就是模这就是模糊聚类分析的理论基础。糊聚类分析的理论基础。 实际问题中建立的模糊关系常常不是等价关系实际问题中建立的模糊关系常常不是等价关系而是相似关系而是相似关系, 这就需要这就需要将模糊相似关系改造为将模糊相似关系改造为模糊等价关系模糊等价关系, 传递闭包

7、正是这样一种工具。传递闭包正是这样一种工具。2021/3/237 定义定义 设设R F(X X). 若若R1 F(X X)是传递的且满是传递的且满足足:1) R R1, 2) 若若S是是X上的模糊传递关系且上的模糊传递关系且R S, 必有必有R1 S. 则称则称R1为为R的传递闭包的传递闭包, 记为记为t(R). 模糊关系模糊关系R的传递闭包是包含的传递闭包是包含R的最小传递关系的最小传递关系。 定理定理 设设R F(X X). 则则 t(R)=n=1 Rn.2021/3/238(n=1 Rn) (m=1 Rm) =n=1 Rn (m=1 Rm)=n=1 m=1 (Rn Rm)=k=2 (n+

8、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 (即证明即证明n=1 Rn “最小最小”) 由由R S得得 R2 S2 S, R3= R R2 R S S2 S, 证明证明:2021/3/239 一般地一般地, Rn S, n N. 于是于是n=1 Rn S. 综上所述综上所述,n=1 Rn是包含是包含R的最小传递关系的最小传递关系, 因因而是而是R的传递闭包的传递闭

9、包, 即即t(R)=n=1 Rn. 在论域有限的情况下在论域有限的情况下, 传递闭包的计算更简捷传递闭包的计算更简捷: 定理定理 设设|X|=n, R F(X X). 则则 t(R)=k=1nRk. 计算有限论域上自反模糊关系计算有限论域上自反模糊关系R的传递闭包的的传递闭包的方法方法:从从R出发出发, 反复自乘反复自乘, 依次计算出依次计算出R2, R4, ,当第一次出现当第一次出现Rk Rk=Rk时得时得t(R)=Rk.2021/3/2310 定理定理 设设R F(X X). 则则R的传递闭包的传递闭包t(R)具有以下具有以下性质性质: (1) 若若I R, 则则 I t(R); (2)

10、(t(R) 1=t(R 1); (3) 若若R=R 1, 则则(t(R) 1=t(R). 上述结论表明上述结论表明:自反关系的传递闭包是自反的自反关系的传递闭包是自反的, 对称关系的传递闭包是对称的。于是对称关系的传递闭包是对称的。于是, 模糊相似模糊相似关系的传递闭包是模糊等价关系。关系的传递闭包是模糊等价关系。 例例 设设|X|=5, R是是X上的模糊关系上的模糊关系, R可表示为如下可表示为如下的的55模糊矩阵。求模糊矩阵。求R的传递闭包。的传递闭包。2021/3/2311 解解 容易看出容易看出R是自反的对称模糊关系是自反的对称模糊关系 (即模糊相即模糊相似关系似关系)。依次计算。依次

11、计算R2, R4, R8知知: R8=R4 R4=R4 (参见下页计算结果参见下页计算结果), 所以所以R的传递闭包的传递闭包 t(R)=R4.10.10.80.50.30.110.10.20.40.80.110.30.10.50.20.310.60.30.40.10.61R2021/3/23127.3 7.3 基于模糊关系的聚类分析基于模糊关系的聚类分析 基于模糊关系的聚类分析的一般步骤基于模糊关系的聚类分析的一般步骤: (1) 数据数据规格化规格化; (2) 构造模糊相似矩阵构造模糊相似矩阵; (3) 模糊分类。模糊分类。 上述第三步又有不同的算法上述第三步又有不同的算法, 以下先介绍利用

12、模以下先介绍利用模糊传递闭包进行模糊分类的方法。糊传递闭包进行模糊分类的方法。 设被分类对象的集合为设被分类对象的集合为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、矩阵特性指标矩阵。2021/3/2313 步骤一步骤一:数据规格化数据规格化 由于由于m个特性指标的量纲和数量级不一定相同个特性指标的量纲和数量级不一定相同,故故在运算过程中可能突出某数量级特别大的特性指在运算过程中可能突出某数量级特别大的特性指标对分类的作用标对分类的作用, 而降低甚至排除了某些数量级而降低甚至排除了某些数量级很小的特性指标的作用。数据规格化使每一个指很小的特性指标的作用。数据规格化使每一个指标值统一于某种共同的数值特性范围。标值统一于某种共同的数值特性范围。111212122212*mmnnnmxxxxxxXxxx2021/3/2314 数据规格化的方法有数据规格化的方法有

14、: (1) 标准化方法标准化方法: 对特性指标矩阵对特性指标矩阵X*的第的第j列列, 计计算均值和方差算均值和方差, 然后作变换然后作变换,1,2, ;1,2, .jijijjxxxin jm 12211,1() ,1,2,njijinjjijixxnxxjmn 其中2021/3/2315 (2) 均值规格化方法均值规格化方法: 对特性指标矩阵对特性指标矩阵X*的第的第j列列, 计算标准差计算标准差 j, 然后作变换然后作变换 xij = xij / j, i=1, 2, , n, j=1, 2, , m. (3) 中心规格化方法中心规格化方法: 对特性指标矩阵对特性指标矩阵X*的第的第j列列

15、, 计算平均值计算平均值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.2021/3/2316 步骤二步骤二:构造模糊相似矩阵构造模糊相似矩阵 聚类是按某种标准来鉴别聚类是按某种标准来鉴别X中元素间的接近程中元素间的接近程度度, 把彼此接近的对象

16、归为一类。为此把彼此接近的对象归为一类。为此, 用用0, 1中的数中的数rij表示表示X中的元素中的元素xi与与xj的接近或相似程的接近或相似程度。经典聚类分析中的相似系数以及模糊集之度。经典聚类分析中的相似系数以及模糊集之间的贴近度间的贴近度, 都可作为相似程度都可作为相似程度(相似系数相似系数)。 设数据设数据xij(i=1, 2, , n, j=1, 2, , m)均已规格化均已规格化, xi=(xi1, xi2, , xim)与与xj=(xj1, xj2, , xjm)之间的相之间的相似程度记为似程度记为rij 0, 1, 于是得到对象之间的于是得到对象之间的模糊模糊相似矩阵相似矩阵R

17、=(rij)nn.2021/3/2317 对于相似程度对于相似程度(相似系数相似系数)的确定的确定, 有多种方法有多种方法, 常用的有常用的有: (1) 数量积法数量积法1 1 ijijijrxxijM1mijikjkkxxx x 其中其中M0为适当选择的参数且满足为适当选择的参数且满足M maxxi xj | i j. 这里这里, xi xj为为xi与与xj的数量积的数量积.2021/3/2318 (2) 夹角余弦法夹角余弦法ijijijxxrxx1221,1,2,miikkxxin (3) 相关系数法相关系数法12211 ()()mijikjkkijmmijikjkkkxxxxrxxxx1

18、111miikkmjjkkxxmxxm2021/3/2319 (4) 贴近度法贴近度法 当对象当对象xi的特性指标向量的特性指标向量xi=(xi1, xi2, , xim)为为模糊向量模糊向量, 即即xik 0, 1 (i=1,2, ,n ; k=1,2, ,m)时时, xi与与xj的相似程度的相似程度rij可看作模糊子集可看作模糊子集xi与与xj的贴近度。在应用中的贴近度。在应用中, 常见的确定方法有常见的确定方法有:最最大最小法、算术平均最小法、几何平均最小法。大最小法、算术平均最小法、几何平均最小法。11;mikjkkijmikjkkxxrxx11;12mikjkkijmikjkkxxr

19、xx11.mikjkkijmikjkkxxrxx2021/3/2320 (5) 距离法距离法 利用对象利用对象xi与与xj的距离也可以确定它们的相似程的距离也可以确定它们的相似程度度rij, 这是因为这是因为d(xi, xj)越大越大, rij就越小。一般地就越小。一般地,取取rij = 1 c (d(xi, xj) , 其中其中c和和 是两个适当选是两个适当选取的正数取的正数, 使使rij 0, 1. 在实际应用中在实际应用中, 常采用如常采用如下的距离来确定下的距离来确定rij.1( ,)max(Chebyshev)ijikjkk md x xxx 1( ,)(Hamming)mijikj

20、kkd x xxx2021/3/23211221( ,)(Euclid)mijikjkkd x xxx11( ,)(1,Minkowski)mppijikjkkd x xxxp (6) 绝对值倒数法绝对值倒数法 如右所示如右所示, 其中其中c是是适当选取的正数适当选取的正数, 使使 rij 0, 1. 1 1 ijmikjkkijcrijxx2021/3/2322 (7) 主观评定法主观评定法 在一些实际问题中在一些实际问题中,被分类对象的特性指标是定被分类对象的特性指标是定性指标性指标, 即特性指标难以用定量数值来表达。这即特性指标难以用定量数值来表达。这时时, 可请专家和有实际经验的人员用

21、评分的办法可请专家和有实际经验的人员用评分的办法来主观评定被分类对象间的相似程度。来主观评定被分类对象间的相似程度。 步骤三步骤三:模糊分类模糊分类 由于由上述各种方法构造出的对象与对象之间由于由上述各种方法构造出的对象与对象之间的模糊关系矩阵的模糊关系矩阵R=(rij)nn, 一般说来只是一个模一般说来只是一个模糊相似矩阵糊相似矩阵, 而不一定具有传递性。因此而不一定具有传递性。因此, 要从要从R出发构造一个新的模糊等价矩阵出发构造一个新的模糊等价矩阵, 然后以此模然后以此模糊等价矩阵作为基础糊等价矩阵作为基础, 进行动态聚类。进行动态聚类。2021/3/2323 如上所述如上所述, 模糊相

22、似矩阵模糊相似矩阵R的传递闭包的传递闭包t(R)就是就是一个模糊等价矩阵。以一个模糊等价矩阵。以t(R)为基础而进行分类为基础而进行分类的聚类方法称为的聚类方法称为模糊传递闭包法模糊传递闭包法。 具体步骤如下具体步骤如下: (1) 利用平方自合成方法求出模利用平方自合成方法求出模糊相似矩阵糊相似矩阵R的传递闭包的传递闭包t(R); (2) 适当选取置适当选取置信水平值信水平值 0, 1, 求出求出t(R)的的 截矩阵截矩阵t(R) , 它它是是X上的一个等价的上的一个等价的Boole矩阵。然后按矩阵。然后按t(R) 进进行分类行分类, 所得到的分类就是在所得到的分类就是在 水平上的等价分水平上

23、的等价分类。类。( )( ),( )( ( ),ijn nijn nt Rrt Rr设则1, ( )0, ijijijrrr 2021/3/2324 对于对于xi, xj X, 若若r ij( )=1, 则在则在 水平上将对象水平上将对象xi和对象和对象xj 归为同一类。归为同一类。 (3) 画动态聚类图画动态聚类图:为了能直观地看到被分类对为了能直观地看到被分类对象之间的相关程度象之间的相关程度, 通常将通常将t(R)中所有互不相同中所有互不相同的元素按从大到小的顺序编排的元素按从大到小的顺序编排: 1= 1 2 得得到按到按t(R) 进行的一系列分类。将这一系列分类进行的一系列分类。将这一

24、系列分类画在同一个图上画在同一个图上, 即得动态聚类图。即得动态聚类图。 例例 考虑某个环保部门对该地区考虑某个环保部门对该地区5个环境区域个环境区域 X= x1, x2, x3, x4, x5按污染情况进行分类。设每按污染情况进行分类。设每个区域包含空气、水分、土壤、作物个区域包含空气、水分、土壤、作物4个要素。个要素。2021/3/2325 环境区域的污染情况由污染物在环境区域的污染情况由污染物在4个要素中的个要素中的含量超标程度来衡量。设这含量超标程度来衡量。设这5个环境区域的污个环境区域的污染数据为染数据为x1=(80, 10, 6, 2), x2=(50, 1, 6, 4), x3=

25、(90, 6, 4, 6), x4=(40, 5, 7, 3), x5=(10, 1, 2, 4). 试用模糊传递闭包法对试用模糊传递闭包法对X进行分类。进行分类。 解解 由题设知特性指标矩阵为由题设知特性指标矩阵为:*80106250164906464057310124X(1) 数据规格化数据规格化: 采用最大采用最大值规格化值规格化, 作变换作变换xij = xij /Mj, i=1, 2, , 5, j=1, 2, 4. 可将可将X*规格化为规格化为:2021/3/2326 (2) 构造模糊相似矩构造模糊相似矩阵阵: 采用最大最小法采用最大最小法来构造模糊相似矩阵来构造模糊相似矩阵R=(rij)5 5, 这里这里00.8910.860.330.560.100.860.6710.600.5710.440.5010.500.110.100.290.67X4141ikjkkijikjkkxxrxx2021/3/2327 (3) 利用平方自合成方法求传递闭包利用平方自合成方法求传递闭包t(R) 依次计算依次计算R2, R4, R8, 由于由于R8=R4 (见下页的计算结见下页的计算结果果), 所以所以t(R