核聚类算法
引言
聚类是将一组给定的未知类标号的样本分成内在的多个类别，使得同一类中
的样本具有较高的相似度，而不同类中的样本差别大。聚类分析的目的是揭示和
刻画数据的内在结构，其内容涉及统计学、生物学、以及机器学习等研究领域，
并在模式识别、数据分析和挖掘、图像处理等领域获得了广泛的应用
[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 的噪声敏感性问题进行研究，提出修改的鲁棒型准则函数。
