核聚类算法
引言
聚类是将一组给定的未知类标号的样本分成内在的多个类别,使得同一类中
的样本具有较高的相似度,而不同类中的样本差别大。聚类分析的目的是揭示和
刻画数据的内在结构,其内容涉及统计学、生物学、以及机器学习等研究领域,
并在模式识别、数据分析和挖掘、图像处理等领域获得了广泛的应用
[JD88][JMF99] [JDM00]。常用的聚类方法可分为如下几类 [HK00]:划分方法,
层次聚类方法,基于密度的方法,基于网格的方法和基于模型的方法。本 章侧重
于第一种方法,即划分聚类方法的研究。
最著名与最常用的划分聚类方法是 C-均值 [Mac67] 及其推广模糊 C-均值
(Fuzzy C-Means,简称为 FCM)[Bez81] 算法。C-均值算法首先由 J. MacQueen
[Mac67]
提出,其原理是:首先定义一个准则函数,并随机选择
C
个初始聚类
中心,然后根据样本与聚类中心的距离,将 该 样本划分到该类中;再重新计算每
个类的聚类中心。此过程不断重复,直到准则函数最小。通常,准则函数选为样
本和聚类中心的平方误差的总和。C-均值算法的缺点是:1)准则函数是不可微
的,不能直接应用无约束最优化的梯度方法,导致算法训练没有一个终止准则,
结果严重依赖初始聚类中心的选取;2)由于采用平方误差和准则,该方法仅适
合于发现球形或类似球形分布的类别;3)难以发现大小差别很大的类别;4)对
噪声和野值( Outlier)敏感;5)类别数 C 必须要事先确定。此后,J. C. Bezdek [Bez81]
提出了里程碑式的模糊
C-
均值算法,通过引入样本到聚类中心的隶属度,使准
则函数不仅可微,而 且软化了模式的归属,由此解决了第一个问题。为了解决第
二个问题,许多学者在 FCM 算法的基础上,通过修改准则函数,从而达到对不
同形状分布样本的聚类。例如,适合椭球形分布样本聚类的 Gustafson-Kessel 算
法 [GK79],适合线形分布样本聚类的模糊 C-方差算法 [Bez81],以及适合环形
分布样本聚类的模糊 C-球壳算法 [Dav90]。除此之外,R. O. Duda 和 P. E. Hart
[DH73] 还提出用类内散度矩阵的行列式作为准则函数,R. Krishnapuram 等人
[KK00] 给出了此准则函数下的迭代求解公式。K. L. Wu 和 M. S. Yang [WY02]
最近又提出一种指数型准则函数,得到的算法可以有效发现大小差别很大的类
别,并且对噪声不敏感。
上述大多数算法是由修改 FCM 中的准则函数得到,其缺点是往往只能对某
一种分布形式的样本有效聚类,并 且 和 FCM 算法一样,对噪声很敏感。Y. Ohashi
[Oha84] 首先对 FCM 的噪声敏感性问题进行研究,提出修改的鲁棒型准则函数。
- 1
- 2
- 3
- 4
- 5
- 6
前往页