毕业论文（设计）-模糊聚类理论发展及研究.doc

模糊聚类理论发展及研究摘要 从模糊聚类准则函数的演化、算法实现的途径、有效性度量方式 以及在模式识别与图像处理中的应用等4个方面对模糊聚类理论的研究 进展做了综述和评价，指出模糊聚类进一步研究的儿个重要方向及其应 用前景.关键词聚类分析模糊聚类聚类有效性模式识别图像处理聚类就是按照事物间的相似性进行区分和分类的过程，在这一过程 中没有教师指导，因此是一种无监督的分类.聚类分析则是用数学方 法研究和处理所给定对象的分类.“人以群分，物以类聚”，聚类是一 个古老的问题，它伴随着人类社会的产生和发展而不断深化，人类耍认 识世界就必须区别不同的事物并认识事物间的相似性⑴.传统的聚类分析是一种硬划分，它把每个待辨识的对象严格地划分到某 个类中，具有非此即彼的性质，因此这种分类的类别界限是分明的.而 实际上大多数对象并没有严格的属性，它们在性态和类属方面存在着中 介性，适合进行软划分.Zadeh [2]提出的模糊集理论为这种软划分提 供了有力的分析工具，人们开始用模糊的方法来处理聚类问题，并称Z 为模糊聚类分析.由于模糊聚类得到了样本属于各个类别的不确定性 程度，表达了样本类属的中介性，即建立起了样本对于类别的不确定性 的描述，能更客观地反映现实世界，从而成为聚类分析研究的主流.模糊划分的概念最早由Ruspini⑷提出，利用这一概念人们提出了多种 聚类方法，比较典型的有：基丁相似性关系和模糊关系的方法（包括聚合 法和分裂法）⑷，基丁模糊等价关系的传递闭包方法⑸、基于模糊图论 最大树方法⑹，以及基于数据集的凸分解、动态规划和难以辨识关系 等方法.然而由于上述方法不适用于大数据量情况，难以满足实时性耍 求高的场合，因此其实际的应用不够广泛，故在该方而的研究也就逐步 减少了.实际中受到普遍欢迎的是基丁 FI标函数的方法，该方法设计简 单、解决问题的范围广，最终还可以转化为优化问题而借助经典数学的 非线性规划理论求解，并易于计算机实现.因此，随着计算机的应用和 发展，该类方法成为聚类研究的热点.以下将从冃标函数的演化、算法的实现途径、有效性度量方式以及在实 际中的应用等4个方面综述基于冃标函数的模糊聚类方法的研究进展. 有关传统聚类分析以及其他的模糊聚类方法的系统总结可参见文献[1, 7〜10].1模糊聚类目标函数的演化模糊聚类问题可以用数学语言描述为：把一组给定的模式0二{oi,s…， 0讣划分为C个模糊子集（聚类）S“S2,…,Sc・如果用Uik（lWiWc, lWkWn）表示模式6隶属于模糊子集Si的程度，那么就得到了这组模式 的模糊c-划分U={uik| lWiWc, 1 WkWn}・完成这样一组无类别标记 模式集模糊划分的操作就是模糊聚类分析•为了获得有意义的分类，需耍定义划分的准则，如相似性或相异性准则D()等.假定每个模糊子集 Si(lWiWc)都有一个典型模式p,常被称做聚类原型，这样任一模式6 与模糊子集Si的相似性可以通过模式5与聚类原型Pi间的失真度 血二D(0k, pj来度量.基于冃标函数的模糊聚类主耍是利用模式集0的观测值X二｛xi,d…,叮 &与原型特征值B二｛, lWiWc｝Z间的距离构造一个冃标函数，然 后通过优化这一带约束的非线性规划问题获得最佳的模糊c-划分：min * Jm = 如)"• D(如 十「s.l. /(网)W C* (1)其中，为惩罚项，f(uQwC为约朿条件，in为加权指数.这样，模 糊聚类的冃标函数就由参量集｛U,D( ),B, m, X｝而确定.对应丁这些参 量，模糊聚类冃标函数的发展演化可以从以下5个大的方面来概括.1.1对模糊划分矩阵U的研究传统的聚拎分析为一种硬划分，卩i(xj e ｛0, 1｝为样本&类属的指示函 数，而类别标记矢量u (xk) = (ulk, g,…，uck)T则成为欧氏c-空间的基 矢量.为了表达模式间的相近信息,Ruspini[3]引入了模糊划分的概念, 令Ui(xk)e [0,1],把标记矢量u (xj扩展为欧氏c-空间中的超平面这样标记矢量既可称做模糊标记乂可称为概率标记.由于存在概率约束，使得隶属函数只能表示模式在模糊类间的分享程度, 而不能反映典型性，为此Krishnapuram等人小提出可能性c-划分的概士M(勺)=1念，放松了概率约朿心】 ,从而使标记矢量U (xk)变为除去原点的单位超立方体.由此而产生的可能性聚类算法具有良好的抗噪 性能，但收敛速度慢，容易陷入局部极值点而得不到最优分类.为了结 合传统硬聚类的收敛速度和模糊聚类的对初始化不敏感(获得全局最优 解的概率大)而且能反映样本间相近信息等优点，Selim和Ismail何提 出了半模糊划分的概念，只保留划分矩阵中较模糊的元素，其余的元素 作去模糊处理.这样使划分矩阵U既具有一定的明晰性，乂保持了样本 在空间分布的模糊性，从而提高了分类识别的正确性.后来，Kamei等 人3以及裴继红等人[⑷分别从不同的角度提出了改进型的半模糊划分 方法，即为阈值型软聚类算法和截集模糊软聚类算法.上述儿种软划分 的比较显示在表1中.表1 4种空间划分概念的比较项目可能性聚类税糊聚类二聚类半模嘲聚类标记矢龄Npc= [0,1] 0 0二{(0, 0,…,0)t}N& =亦€ N云 站1}iXhc-{u eNfc:u e{0. 1}. i}Nsc=NfcUNhc物理意义花示毎个样本屈于各类的貝型程度茨示毎个样本在 备类间的分享程度是样本严格类属的折示函数只有部分样本类分蟆制吹叙速度较慢快较怏対初始化 的敏感性很敏感不很敏感敏感不很敏感抗噪性能强较强弱较颈如何提高可能性划分的收敛速度并降低它对初始化的敏感程度，仍 然是从模糊划分角度进一步研究模糊聚类的一个重耍方向.如果在这方 面有所突破，就可以得到一种既具有良好的抗噪鲁棒性，同时乂能快速 收敛到满意解的空间划分方法，不仅能从理论上完善现有的模糊软聚类 方法，也必将缩短它的实用化进程.1.2对相似性准则D()的研究单一的聚类准则不能解决所有可能的无监督分类问题，因此人们提出了 多种相似性函数，比如:最大似然准则购、最大爛准则［⑹、最小体积 准则⑷和信息论准则3等.不过，实际中最常用的还是基于最小类内 加权平方误差和准则.经典的类内平方误差和(WGSS: wi thin-group sum of squared error) 准则函数最早被用来定义传统的便c-均值聚类算法和IS0DATA算法. 随着模糊集理论的提出，Dunn L,9］首先把它推广到加权的WGSS函数，后 由Bezdek™扩展到加权WGSS的无限族，形成了模糊c-均值类型算法的 通用聚类准则，形式如式(1)所示.对该准则函数的研究主耍集中在相 似性测度或者误差度量D()上，一般用样木与原型间的距离表示.不同 距离度量用来检测不同结构的数据子集，常用的距离函数见表2.表2常见的距离函数及特点名称距离函数特点功能Minkowskil)gb)二[ 1 ①-几 1"] 卩i = i対应1W卩W为-族距處测度・可用來檢测从◊形超立方 体到口形超立方体结构的数摇子集Euclideana，b> = [ ( a, - b,)2] * ~ = 1对应p-2的Minkowski距离.可用以检测特征空间中O形趨球体结构的数拖:子集Hamming$Dj( 6)= I (ii — bi 1= !对应I)1的Minkowski距离，可用以检测特征空间中◊形 超立方体结构的数据子集Max i mimD) a、b) = max 1 a； - 6； 1对应1尸8的Minkowski距离，可用以检测特征空间中□形超立方体结构的数摇子尖UahalanobisDa (a, b.) = (a-b) A (a-b.).A为正定矩形可用來检测特征空间小超柿球结构的数据子集Bobrowski等人［2,］分别讨论了 4和J范数下的模糊聚类算法(即 Hamming和Maximum距离),发现在许多情况下它们比常用的欧氏范数L2 能获得更好的结果，建议在聚类分析中要选择合适的距离函数.另外Mahalanobis距离的一种特例——加权欧氏距离(对应A为对角阵)还被 广泛地使用于模式各维特征对分类贡献不同的应用背景［22］・ 在给定数据中搜索一个结构可以看做寻找合适的距离萌数.这就给我 们留下了一个问题：选择合适距离的准则是什么？能否构造一种不依赖丁• 事先定义距离测度的模糊聚类算法?现有文献很少涉及这一问题，仍属丁 有待解决的范畴.1.3对聚类原型B的研究基于冃标函数的模糊聚类乂称做基于原型的聚类，因为冃标函数的构造 依赖于原型的定义，因此原型的类型必须事先给定.聚类原型的研究是 伴随着聚类应用的发展和需求而展开的，最初的聚类分析只应用于特征 空间中超球体聚类结构的检测，因此原型为特征空间中的“点”，或者 叫聚类中心［剜；为了处理非超球体的聚类结构，Bezdek［23］提出了通过 点 V丘Rp的 r (O0Wp-l)维线性簇原型 Br(v:{Si}) = {v} +Span({Si}),其 特点见表3.表3儿种原型的特点比较线性簇錐数聚类原型功能特点1-0Bc （v; D-v：点检测超球体和椭珠体结构的子集r=l1人(v：s.2L(v：sh 线检测线性结构的模式子集r=2SP-P（V；S|, Sa> :平面检测平面结构的模式子集Bri（v： ［s}）=HP（v： {sj）：超平面检测超平面结构的模式子集此外，为了检测呈“薄売”结构的模式子集，Dave提出球売⑵］和 椭球売［25］两种原型，并将其应用于边缘检测中获得了较好的效果.随 着应用的需求壳原型被推广到矩形壳⑵］、多面体壳［如以及任意形状的 壳原型［遡等多种类型，而对于线性原型也逐步被扩展为抛物线⑵］、二 次曲线以及任意二次多项式形式的原型［30］・基于1=1标函数的聚类对原型有较强的依赖性，因此要求一方面必须充分 利用先验知识选择合适的原型，另一方面必须与距离测度相结合研究， 构造合理的相似性度量.1.4对加权指数m的研究在模糊聚类目标函数{Jm： l〈m<}中，Bezdek L20j引入了加权指数m,使 Dunn的聚类准则变成m二2时的特例.有人认为从数学上看参数m的出 现不自然也没有必耍［叩，但是对丁•从硬聚类准则函数推广得到的H标函 数(1),如果不给隶属度乘一个权重，这种推广则是无效的.参数m 乂 称为平滑因子，控制着模式在模糊类间的分享程度〔刘，因此，要实现模 糊聚类就必须选定一个ni,然而最佳m的选取冃前尚缺乏理论指导.Bezdek 3给出过一个经验范围1. 后乂从物理解释上得出呼2最有意义；Chan等人［32］从汉字识别的应用背景得岀m的最佳取值应在 1.25〜1.75Z间;Bezdek等人顷］从算法收敛性角度着手,得出m的取 值与样本数冃n有关的结论，建议m的取值耍大于n/(n-2) ； Pal等人⑶】 则从聚类有效性的实验研究中得到m的最住选取区间应为［1・5, 2. 5］, 在不作特殊要求下可取区间中值m=2.上述有关ni取值范围，大都来自实验和经验，均为启发式的，一方面不 够系统，另一方面没有给出具体的优选算法.此外，也还缺乏最优m 的检验方法.这一系列的开放问题，都值得进一步的探索，以便奠定m 优选的理论慕础.1.5对各种数据集X聚类的研究在实际应用中会遇到不同的数据类型，因此要研究模糊聚类的H标函数 就必须首先研究所要处理的数据类型.常见的数据人都为特征空间中 的点集x 。