模糊聚类理论发展及研究毕业论文.doc

模糊聚类理论发展及研究毕业论文.doc

《模糊聚类理论发展及研究毕业论文.doc》由会员分享，可在线阅读，更多相关《模糊聚类理论发展及研究毕业论文.doc（14页珍藏版）》请在冰点文库上搜索。

模糊聚类理论发展及研究

摘要　从模糊聚类准则函数的演化、算法实现的途径、有效性度量方式以及在模式识别与图像处理中的应用等4个方面对模糊聚类理论的研究进展做了综述和评价，指出模糊聚类进一步研究的几个重要方向及其应用前景.　

关键词　聚类分析　模糊聚类　聚类有效性　模式识别　图像处理

　　聚类就是按照事物间的相似性进行区分和分类的过程，在这一过程中没有教师指导，因此是一种无监督的分类.　聚类分析则是用数学方法研究和处理所给定对象的分类.　“人以群分，物以类聚”，聚类是一个古老的问题，它伴随着人类社会的产生和发展而不断深化，人类要认识世界就必须区别不同的事物并认识事物间的相似性［1］.　

传统的聚类分析是一种硬划分，它把每个待辨识的对象严格地划分到某个类中，具有非此即彼的性质，因此这种分类的类别界限是分明的.　而实际上大多数对象并没有严格的属性，它们在性态和类属方面存在着中介性，适合进行软划分.　Zadeh［2］提出的模糊集理论为这种软划分提供了有力的分析工具，人们开始用模糊的方法来处理聚类问题，并称之为模糊聚类分析.　由于模糊聚类得到了样本属于各个类别的不确定性程度，表达了样本类属的中介性，即建立起了样本对于类别的不确定性的描述，能更客观地反映现实世界，从而成为聚类分析研究的主流.

模糊划分的概念最早由Ruspini［3］提出，利用这一概念人们提出了多种聚类方法，比较典型的有：

基于相似性关系和模糊关系的方法（包括聚合法和分裂法）［4］，基于模糊等价关系的传递闭包方法［5］、基于模糊图论最大树方法［6］，以及基于数据集的凸分解、动态规划和难以辨识关系等方法.　然而由于上述方法不适用于大数据量情况，难以满足实时性要求高的场合，因此其实际的应用不够广泛，故在该方面的研究也就逐步减少了.　实际中受到普遍欢迎的是基于目标函数的方法，该方法设计简单、解决问题的范围广，最终还可以转化为优化问题而借助经典数学的非线性规划理论求解，并易于计算机实现.　因此，随着计算机的应用和发展，该类方法成为聚类研究的热点.　

以下将从目标函数的演化、算法的实现途径、有效性度量方式以及在实际中的应用等4个方面综述基于目标函数的模糊聚类方法的研究进展.　有关传统聚类分析以及其他的模糊聚类方法的系统总结可参见文献［1，7～10］.　

1　模糊聚类目标函数的演化

模糊聚类问题可以用数学语言描述为：

把一组给定的模式O={o1,o2,…，on}划分为c个模糊子集（聚类）S1,S2,…,Sc.　如果用μik（1≤i≤c,1≤k≤n）表示模式ok隶属于模糊子集Si的程度，那么就得到了这组模式的模糊c-划分U={μik|1≤i≤c,1≤k≤n}.　完成这样一组无类别标记模式集模糊划分的操作就是模糊聚类分析.为了获得有意义的分类，需要定义划分的准则，如相似性或相异性准则D（.）等.　假定每个模糊子集Si（1≤i≤c）都有一个典型模式pi，常被称做聚类原型，这样任一模式ok与模糊子集Si的相似性可以通过模式ok与聚类原型pi间的失真度dik=D（ok,pi）来度量.　

基于目标函数的模糊聚类主要是利用模式集O的观测值X={x1,x2,…,xn}Rs与原型特征值B={βi,1≤i≤c}之间的距离构造一个目标函数，然后通过优化这一带约束的非线性规划问题获得最佳的模糊c-划分：

（1）

其中，ζ为惩罚项，f（μik）∈C为约束条件，m为加权指数.　这样，模糊聚类的目标函数就由参量集{U,D（.）,B,m,X}而确定.　对应于这些参量，模糊聚类目标函数的发展演化可以从以下5个大的方面来概括.　

1.1　对模糊划分矩阵U的研究

传统的聚拎分析为一种硬划分，μi（xk）∈{0,1}为样本xk类属的指示函数，而类别标记矢量μ（xk）=（μ1k,μ2k,…,μck）T则成为欧氏c-空间的基矢量.　为了表达模式间的相近信息，Ruspini［3］引入了模糊划分的概念，令μi（xk）∈［0,1］，把标记矢量μ（xk）扩展为欧氏c-空间中的超平面，这样标记矢量既可称做模糊标记又可称为概率标记.　由于存在概率约束，使得隶属函数只能表示模式在模糊类间的分享程度，而不能反映典型性，为此Krishnapuram等人［11］提出可能性c-划分的概念，放松了概率约束，从而使标记矢量μ（xk）变为除去原点的单位超立方体.　由此而产生的可能性聚类算法具有良好的抗噪性能，但收敛速度慢，容易陷入局部极值点而得不到最优分类.　为了结合传统硬聚类的收敛速度和模糊聚类的对初始化不敏感（获得全局最优解的概率大）而且能反映样本间相近信息等优点，Selim和Ismail［12］提出了半模糊划分的概念，只保留划分矩阵中较模糊的元素，其余的元素作去模糊处理.　这样使划分矩阵U既具有一定的明晰性，又保持了样本在空间分布的模糊性，从而提高了分类识别的正确性.　后来，Kamel等人［13］以及裴继红等人［14］分别从不同的角度提出了改进型的半模糊划分方法，即为阈值型软聚类算法和截集模糊软聚类算法.　上述几种软划分的比较显示在表1中.　

表1　4种空间划分概念的比较

项目

可能性聚类

模糊聚类

传统聚类

半模糊聚类

标记矢量集

Npc=［0,1］c-O

O={（0,0,…,0）T}

Nhc={μi∈Nfc:

μi∈{0,1},i}

Nsc=Nfc

∪Nhc

物理意义

表示每个样本

属于各类的典型程度

表示每个样本在

各类间的分享程度

是样本严格类属

的指示函数

只有部分样

本类分模糊

收敛速度

慢

较慢

快

较快

对初始化

的敏感性

很敏感

不很敏感

敏感

不很敏感

抗噪性能

强

较强

弱

较强

　　如何提高可能性划分的收敛速度并降低它对初始化的敏感程度，仍然是从模糊划分角度进一步研究模糊聚类的一个重要方向.如果在这方面有所突破，就可以得到一种既具有良好的抗噪鲁棒性，同时又能快速收敛到满意解的空间划分方法，不仅能从理论上完善现有的模糊软聚类方法，也必将缩短它的实用化进程.

1.2　对相似性准则D（.）的研究

单一的聚类准则不能解决所有可能的无监督分类问题，因此人们提出了多种相似性函数，比如：

最大似然准则［15］、最大熵准则［16］、最小体积准则［17］和信息论准则［18］等.　不过，实际中最常用的还是基于最小类内加权平方误差和准则.　

经典的类内平方误差和（WGSS:

within-groupsumofsquarederror）准则函数最早被用来定义传统的硬c-均值聚类算法和ISODATA算法.　随着模糊集理论的提出，Dunn［19］首先把它推广到加权的WGSS函数，后由Bezdek［20］扩展到加权WGSS的无限族，形成了模糊c-均值类型算法的通用聚类准则，形式如式

（1）所示.　对该准则函数的研究主要集中在相似性测度或者误差度量D（.）上，一般用样本与原型间的距离表示.　不同距离度量用来检测不同结构的数据子集，常用的距离函数见表2.　

表2　常见的距离函数及特点

名称

距离函数

特点功能

Minkowski

对应1≤p≤∞为一族距离测度，可用来检测从◇形超立方体到□形超立方体结构的数据子集

Euclidean

对应p=2的Minkowski距离，可用以检测特征空间中○形超球体结构的数据子集

Hamming

对应p=1的Minkowski距离，可用以检测特征空间中◇形超立方体结构的数据子集

Maximum

对应p=∞的Minkowski距离，可用以检测特征空间中□形超立方体结构的数据子集

Mahalanobis

DA（a,b）=（a-b）TA（a-b）,

A为正定矩形

可用来检测特征空间中超椭球结构的数据子集

　　Bobrowski等人［21］分别讨论了L1和L∞范数下的模糊聚类算法（即Hamming和Maximum距离），发现在许多情况下它们比常用的欧氏范数L2能获得更好的结果，建议在聚类分析中要选择合适的距离函数.　另外Mahalanobis距离的一种特例——加权欧氏距离（对应A为对角阵）还被广泛地使用于模式各维特征对分类贡献不同的应用背景［22］.　

在给定数据中搜索一个结构可以看做寻找合适的距离函数.　这就给我们留下了一个问题：

选择合适距离的准则是什么?

能否构造一种不依赖于事先定义距离测度的模糊聚类算法?

现有文献很少涉及这一问题，仍属于有待解决的范畴.　

1.3　对聚类原型B的研究

基于目标函数的模糊聚类又称做基于原型的聚类，因为目标函数的构造依赖于原型的定义，因此原型的类型必须事先给定.　聚类原型的研究是伴随着聚类应用的发展和需求而展开的，最初的聚类分析只应用于特征空间中超球体聚类结构的检测，因此原型为特征空间中的“点”，或者叫聚类中心［20］；为了处理非超球体的聚类结构，Bezdek［23］提出了通过点v∈Rp的r（0≤r≤p-1）维线性簇原型Br（v:

{si}）={v}+Span（{si}），其特点见表3.

表3　几种原型的特点比较

线性簇维数

聚类原型

功能特点

r=0

B0（v;I）=v：

点

检测超球体和椭球体结构的子集

r=1

B1（v;s）=L（v;s）：

线

检测线性结构的模式子集

r=2

B2（v;s1,s2）=P（v;s1,s2）:

平面

检测平面结构的模式子集

2

Bp-1（v；{si}）=HP（v；{si}）：

超平面

检测超平面结构的模式子集

　　此外，为了检测呈“薄壳”结构的模式子集，Dave提出球壳［24］和椭球壳［25］两种原型，并将其应用于边缘检测中获得了较好的效果.　随着应用的需求壳原型被推广到矩形壳［26］、多面体壳［27］以及任意形状的壳原型［28］等多种类型，而对于线性原型也逐步被扩展为抛物线［29］、二次曲线以及任意二次多项式形式的原型［30］.　

基于目标函数的聚类对原型有较强的依赖性，因此要求一方面必须充分利用先验知识选择合适的原型，另一方面必须与距离测度相结合研究，构造合理的相似性度量.　

1.4　对加权指数m的研究

在模糊聚类目标函数{Jm:

1

（1），如果不给隶属度乘一个权重，这种推广则是无效的.　参数m又称为平滑因子，控制着模式在模糊类间的分享程度［20］，因此，要实现模糊聚类就必须选定一个m，然而最佳m的选取目前尚缺乏理论指导.　

Bezdek［31］给出过一个经验范围1.1≤m≤5；后又从物理解释上得出m=2最有意义；Chan等人［32］从汉字识别的应用背景得出m的最佳取值应在1.25～1.75之间；Bezdek等人［33］从算法收敛性角度着手，得出m的取值与样本数目n有关的结论，建议m的取值要大于n/（n-2）；Pal等人［34］则从聚类有效性的实验研究中得到m的最佳选取区间应为［1.5，2.5］，在不作特殊要求下可取区间中值m=2.　

上述有关m取值范围，大都来自实验和经验，均为启发式的，一方面不够系统，另一方面没有给出具体的优选算法.　此外，也还缺乏最优m的检验方法.　这一系列的开放问题，都值得进一步的探索，以便奠定m优选的理论基础.　

1.5　对各种数据集X聚类的研究

在实际应用中会遇到不同的数据类型，因此要研究模糊聚类的目标函数就必须首先研究所要处理的数据类型.　常见的数据大都为特征空间中的点集，除此以外，人们还研究了关系数据［35］、方向数据［36］、区间型数据和模糊数［37］等形式，并得出了一些有意义的结论.　还有一种类型的数据——符号数据［38］，也引起了广泛的关注.　这种数据不仅包括一般数值型数据，还包括区间数、模糊数和语言量等形式，在模糊概念聚类方面有着较多的研究和应用，但这些类型的数据并不常用，实际中最常遇到的数据多数为部分有标记的、噪声污染的和多种结构混合的数据.　

针对存在部分标记的数据，为了获得更好的聚类效果，Pezdrcy［39］提出了部分监督的模糊聚类算法，以利用数据中蕴涵的先验知识.　Bensaid［40］又进一步发展了该理论，把它应用于图像分割中，并取得了良好的效果.　对于噪声污染的数据，更是涌现了大批的鲁棒聚类算法以克服噪声干扰，Dave等人［41］对这些方法做了很好的总结，在此不再赘述.　至于多种结构并存的数据，只有Gustafson等人［42］提出的模糊协方差矩阵聚类方法能同时检测椭球形结构和线性结构，Jawahar等人［43］又对不同的几何结构聚类的检测做了一定的尝试，除此以外很少有这方面的研究报道.　

因此，对于这3种数据集的分析遗留了很多问题，要使模糊聚类真正走向实用化，就必须进一步分析实际数据的各种情况，研究“可充分利用先验知识的聚类算法”、“能容噪的鲁棒算法”和“可同时检测多种结构的聚类方法”等.　

2　模糊聚类算法实现途径的研究

有了聚类的准则函数，接下来就是如何优化目标函数获得最佳聚类的问题了，即研究算法的实现途径.　现有的实现途径主要分为3类：

基于交替优化（AO）、神经网络（NN）和进化计算（EC）等方法.　以下概述这3方面的研究进展.　

2.1　基于交替优化的实现

在优化目标函数的过程中，人们曾试探过动态规划、分支定界和凸切割等方法，然而大量的存贮空间和运行时间限制了其应用.　实际中应用最为广泛的是Dunn和Bezdek［19，20］提出的迭代优化算法——模糊c-均值类型的算法，到目前为止，对它的研究主要集中在收敛性证明、算法停止准则的设立以及原型初始化等方面.　

几经修补，最后证得交替优化算法沿一个子序列收敛到目标函数的极值点或鞍点［44，45］.　对于停止准则，提出了以连续两代的原型变化量小于某个阈值和划分矩阵变化量小于某个阈值两类方法［46］.　不幸的是，由于迭代优化本质上属于局部搜索的爬山法，很容易陷入局部极值点，因此对初始化较敏感.　为了获得全局最优解或满意解，人们把希望寄托在好的初始化上，比较有名的初始化方法有Yager等人［47］提出的山函数或势函数法，不过该方法的计算量随样本维数呈指数增长，为此，Chiu［48］提出改进算法使计算量只与样本数目有关，解决了计算精度与复杂度之间的矛盾；此外还有Chaudhuri［49］的密度函数估计法、Postaire［50］的形态学方法以及模糊测度法和Marr算子等方法.　

2.2　基于神经网络的实现

神经网络在聚类分析中的应用首先起源于Kohonen［51］的两项工作——学习矢量量化和自组织特征映射以及Grossberg［52］的自适应共振理论，两者的主要情况如表4所示.　

表4　2种聚类神经网络的比较

项目

Kohonen聚类网络　　

Grossberg聚类网络　　

输入量

精确的数值量

数值量或模糊语言量

输出量

聚类原型（特征矢量）

分类结果和类别数

学习方式

竞争学习（梯度下降）

模糊逻辑操作

聚类数目

事先给定

自动确定

功能用途

球型硬聚类、特征映射

球型硬聚类、模式分类

　　用神经网络实现聚类分析显著的优势在于神经网络的并行处理，因为在大数据量情况下聚类是相当耗时的.　然而，以上两种聚类网络仍存在应用的局限性——只能实现球型的硬聚类，为此人们在模糊神经网络的集成研究方面做了不懈的努力.从总体上看，模糊聚类神经网络的研究可分为两类：

一类是从目标函数法演变而来的，其基础是模糊竞争学习算法，比较有代表性的如Pal和Bezdek［53］提出的基于竞争学习的模糊聚类网络，解决了球型分布样本的模糊聚类；Xu［54］提出了带惩罚项的竞争学习算法，可以自动确定聚类数；Zhang［55］提出了一种基于Gauss非线性的竞争学习算法，用于模糊聚类并给出了硬件实现方法.另一类模糊聚类神经网络由模糊逻辑操作构成，比如Carpenter等人［56］在ART基础上发展的模糊ART，比ART在性能上有较大的改善，Simpson［57］提出的模糊Min-Max网络实现了超盒子形状的模糊聚类，但这类网络的研究很分散，不仅数量少，理论上也不很成熟.　

2.3　基于进化计算的实现

进化计算是建立在生物进化基础之上基于自然选择和群体遗传机理的随机搜索算法.　由于它全局并行搜索，故可以较高的概率获得全局最优解.　此外进化计算还具有简单、通用和鲁棒性强等优点.　为了获得快速准确的聚类，人们把进化计算引入到模糊聚类中，形成了一系列基于进化计算的模糊聚类算法.　

这一系列算法大致可分为3种类型：

一是基于模拟退火的方法，比如有对模糊分类矩阵U退火处理的［58］，有对聚类原型渐进优化的［59］，然而由于模拟退火算法只有当温度下降足够慢时才能收敛到全局最优点，极大的运算时间限制了其实用性；二是基于遗传算法［60］和进化策略［61］的方法，这方面的研究主要集中在解的编码方案、适应度函数的构造以及遗传算子和操作参数等方面1）；三是基于Tabu搜索的算法，主要是AL-Sultan做了一些探索和尝试［62］，这方面的研究还是很初步的，有待于进一步的深入.

对比上述3类模糊聚类的实现途径，得到如表5所示的结果.　从表中可知，3种方法各有优缺点，从而启发我们结合各自的优点去构造速度快、精度高而且对初始化不敏感的模糊聚类算法，比如把梯度算子引入进化计算中，用进化计算来训练神经网络等，都是很有前途的方向.

表5　3种模糊聚类实现途径的比较

项目

基于迭代优化的方法

基于神经网络的方法

基于进化计算的方法

搜索本质

梯度下降

梯度下降

随机搜索

收敛速度

较快

快

慢

算法精度

高

高

受编码长度限制

算法结构

串行

各维特征间并行

各个体间并行

初始化敏感性

敏感

敏感

不敏感

3　模糊聚类有效性的研究

对于给定的数据集，首先需要判断有无聚类结构，这属于聚类趋势研究的课题，如果已经确认有聚类结构则需要用算法来确定这些结构，这属于聚类分析研究的课题.　得到聚类结构后，则需要分析聚类的结果是否合理，这属于聚类有效性研究的课题.　对聚类分析而言，有效性问题又可以转化为最佳类别数c的确定［20］.　

历史上有关聚类有效性问题的研究大都是基于硬c-均值和模糊c-均值算法的，Dubes［9］和Jain［63］曾对80年前的研究做过评述.　现有的聚类有效性函数按其定义方式可分为：

基于数据集模糊划分的、基于数据集几何结构的和基于数据集统计信息的3类，3类的理论基础和特点均列于表6中.　

表6　3类聚类有效性函数的特点比较

比较项目

基于模糊划分

基于几何结构

基于统计信息

理论基础

好的聚类分析对应于数据集较“分明”的划分

每个子类应当是紧致的而且子类间是尽可能分离的

最佳分类对应的数据结构提供的统计信息最好

优点

简单、运算量小

与数据集的结构密切相关

与数据集分布密切相关

缺点

与数据集的结构特征缺乏直接联系

表述比较复杂、运算量大

性能依赖统计假设与数据分布的一致性

代表性研究

Zadeh的分离度［20］

Bezdek的划分熵［20］

Windham的比例系数［64］

Dunn的划分系数［65］

Gunderson的分离系数［66］

Xie-Beni指标［67］

Vogel等人的PFS聚类［68］

Jain等人的自举法［69］

Beni的熵形式有效性函数［70］

　　没有万能的模糊聚类有效性函数，这也是有效性函数层出不穷的原因.　既然单一的度量方式不能解决所有可能的聚类有效性问题，那么现有的有效性函数将长期并存.能否给出一种启发式的方法来帮助人们选择适合于待分析问题的有效性函数呢?

答案是肯定的，但这将是一项艰巨的工程.　另外，现有聚类有效性函数多是针对模数c-均值算法的，除了Dave［71］和Krishnapuram［30］提出过针对模糊c-壳聚类的有效性函数外，很少有人讨论面向模糊线、面以及其他原型聚类算法的有效性问题，此外对可能性聚类、半模糊聚类的有效性度量也需要进一步丰富和发展，以便完善聚类有效性理论.　

上述模糊聚类有效性函数，主要被用来确定合理的聚类数，以保证算法得到更有效的分类结果.　而在实际的聚类中，即使分类数选取得合适，由于选取的算法不合适或者算法的参数选取得不合适，也可能得不到数据的真实结构.　这促使人们去寻找能指导聚类算法得到更符合实际分类的函数.　这方面的工作首先是由Huntsbergery［72］进行的，他将模糊c-均值聚类算法应用于图像分割，为了得到理想的分割效果，引入了一个指导分割的函数；后来，Bcnsaid等人［73］修改了Xie-Beni指标［67］，提出了一个指导分类的新标准，并在其文章中明确指出对聚类有效性函数的研究不仅能回答数据集的最佳分类问题，而且能有效地指导聚类算法得到更符合实际的分类.　

4　模糊聚类的应用研究

模糊聚类理论的发展推动了其在生产实践中的应用，反过来实际应用的需求又促进了模糊聚类理论的不断丰富和完善.　随着理论的发展，模糊聚类已经在众多的领域获得广泛的应用，并取得了令人满意的效果和可观的效益.　其应用范围涉及到通讯系统中的信道均衡、矢量量化编码中的码书设计、时间序列的预测、神经网络的训练、参数估计、医学诊断、天气预报、食品分类、水质分析等领域.　对上述应用的介绍，有兴趣的读者可参见文献［1，7～10，20］和高新波的论文1），本文不再赘述.　鉴于模糊聚类在模式识别和图像处理两个领域中相当成功的应用，以下主要对这两方面详细介绍.　

4.1　模糊聚类在模式识别中的应用

模式识别中两大主要的分支为有监督的分类和无监督分类，而其中无监督分类与聚类分析相对应.　正是由于模糊聚类与模式识别的天然联系，使得它首先在模式识别领域获得成功的应用.　模糊聚类不需要训练样本，可直接通过机器学习达到自动分类的目的.　

模式识别中一个最重要的问题是特征提取，模糊聚类不但能从原始数据中直接提取特征［74］，还能对已经得到的特征进行优选和降维操作［75］，以免造成“维数灾难”；在提取完特征后就需要分类器设计，模糊聚类算法既可以提供最近邻原型分类器［75］，还可以用来进行特征空间划分和模糊规则提取，以构造基于模糊IF-THEN规则的分类器［76］；在物体识别或线条检测中，模糊聚类既可以直接用于原始数据上［24，25，30］，也可以用于变换域中，比如Hough变换中峰值检测问题一直困绕着其推广应用，Jolion等人［77］提出基于模糊聚类的峰值检测方法，解决了这一难题，使得Hough变换可以自动执行，方便快捷；另外在不变性模式识别中也有借助模糊聚类技术的报道.　

在一些模式识别的具体应用中，模糊聚类也取得了较好的效果，比如汉字字符识别中的字符预分类［78］；语音识别中的分类和匹配［79］；雷达目标识别中目标库的建立和新到目标的归类［80］等等，在此不再一一列举.　

4.2　模糊聚类在图像处理中的应用

图像处理是计算机视觉的重要组成部分，由于人眼视觉的主观性使图像比较适合用模糊手段处理，同时训练样本图像的匮乏又需要无监督分析，而模糊聚类正好满足这两方面的要求，因此成为图像处理中一个强大的研究分析工具.　

模糊聚类在图像处理中最为广泛的应用为图像分割，由于图象分割问题可以等效为象素的无监督分类，因此早在1979年Coleman和Andrews［81］就提出用聚类算法进行图像分割，此后基于二维直方图［82］、塔型结构［83］、小波分析［84］、分形分维［85］等一系列新技术，人们又相继提出了多种基于模糊聚类的灰度图像分割新方法，并且在纹理图像分割［86］、彩色图像分割1）、序列图像分割1）、遥感图像分割［86］等方面也获得了很大的进展.　

基于模糊聚类的方法在边缘检