高新波 谢维信
摘要 从模糊聚类准则函数的演化、算法实现的途径、有效性度量方式以及在模式识别与图像处理中的应用等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种空间划分概念的比较
|