基于改进核模糊C均值类间极大化聚类算法

摘要：传统的核聚类仅考虑了类内元素的关系而忽略了类间的关系，对边界模糊或边界存在噪声点的数据集进行聚类分析时，会造成边界点的误分问题。为解决上述问题，在核模糊C均值（KFCM）聚类算法的基础上提出了一种基于改进核模糊C均值类间极大化聚类（MKFCM）算法。该算法考虑了类内元素和类间元素的联系，引入了高维特征空间的类间极大惩罚项和调控因子，拉大类中心间的距离，使得边界处的样本得到了较好的划分。在各模拟数据集的实验中，该算法在类中心的偏移距离相对其他算法均有明显降低。在人造高斯数据集的实验中，该算法的精度（ACC）、归一化互信息（NMI）、芮氏指标（RI）指标分别提升至0.9132，0.7575，0.9138。

对于边界模糊或边界存在噪声点的数据集，该聚类算法具有理论研究意义。

关键词：

核聚类；模糊C均值聚类；类间极大惩罚项；模糊边界

中图分类号： TP391.4； TP18 文献标志码：A

0引言

聚类分析是数据挖掘和无监督模式识别学习的主要任务之一，已广泛应用于数据挖掘、图像处理、计算机视觉、生物信息和文本分析等领域中。针对数据的分析方法一般分为三大类，即有监督的学习、半监督的学习以及无监督的学习。有监督的学习方法中，典型代表就是K近邻（KNearest Neighbor， KNN）算法；半监督的学习方法中，具有代表性的是支持向量机（Support Vector Machine， SVM），以及一些相关的改进算法[1-2]；而无监督方法主要是以聚类分析方法为主，聚类的方法可以分为基于划分的方法、基于分层的方法、基于密度的方法和基于网格的方法，其中，基于划分的聚类算法[3]在模式识别里是最常用的聚类分析方法，本文主要是针对此类算法进行讨论的。

聚类是指将一组给定的未知类标号的数据分类到不同的类，且保证同一个类内的对象有较大的相似性，而类间的对象有较大的差异性[4]。聚类算法有很多，典型的算法有基于硬划分的kmeans算法以及基于软划分的模糊C均值（Fuzzy CMeans， FCM）聚类算法[5]，此处的软硬即表示隶属度的模糊程度区别，隶属度越模糊则“软”的程度越大，隶属度越精确则越偏向“硬”的程度。FCM算法存在对噪声点与野值点敏感和只善于发现致密的球形结构等缺点。为了克服FCM的缺点，在模式识别的各个领域内出现了很多以FCM为基础的一些算法，比较突出的有可能性C均值（Possibilistic CMeans， PCM）聚类算法[6]、模糊可能性C均值（Possibilistic Fuzzy CMeans， FPCM）聚类算法[7]、基于核的可能C均值（Kernel Possibilistic CMeans， KPCM）聚类算法[8]等。

Aizerman等[9]在1964年把核函数的思想引入到机器学习领域。1995年，基于VC理论，Cortes等[10]提出支持向量机（SVM）分类算法，SVM在一些问题上得到比传统分类器更好的性能。SVM的成功使得核函数的应用得到重视并应用到机器学习的其他领域，如核主成分分析、核Fisher鉴别分析以及基于核的聚类分析等。基于核方法的聚类通过核函数把原始空间中的点映射到特征空间中，在特征空间直接或间接地进行算法设计、分析与计算，从而得到原始空间的聚类划分。在一定程度上，基于核的聚类方法提高了聚类的效果，但是，不管是传统聚类或者核聚类，大部分聚类算法都只是考虑类内关系，而忽略了类与类之间的关系。

类与类之间的关系被广泛应用于聚类的有效性指标问题中，例如：Xie等[11]提出的XB（XieBeni）指标；Fukuyama[12]提出的有FS（FukuyamaSugeno）指标；Zahid等[13]提出的SC指标；Gath等[14]提出的FHV（Fuzzy Hyper Volume）和PD（Partition Density）指标等。zdemir等[15]提出的簇间分离（InterCluster Separation， ICS）算法将分离项应用到聚类目标函数中。由于类与类之间的协方阵是表示类中心与类中心之间的距离，而它们的距离取得最大值会有更好的聚类效果。本文提到的基于核化距离的模糊C均值（Kernel Fuzzy CMeans，KFCM）聚类算法[16]，在一定程度上，该算法增强了对噪声点或野值点的鲁棒性，提高改善了聚类效果；但是KFCM算法始终是以模糊聚类为基础且忽略了类与类之间的距离信息。

综上，本文提出了一种基于改进核模糊C均值类间极大化（Maximum betweencluster based on improved Kernel Fuzzy CMeans， MKFCM）聚类算法。该算法由类内最小和类间最松散的聚类准则推导而出，将Wu等[17]提出的算法作进一步改进，使得类中心与类中心之间距离极大化，构造出全新的目标函数。实验结果表明，MKFCM算法比KFCM算法对噪声点或野值点有较好的鲁棒性，对样本不平衡数据集和边界模糊数据集具有更佳的聚类效果。

1基于核的模糊C均值聚类算法

2改进的基于核化距离的模糊C均值聚类算法

尽管KFCM算法在一定程度上，相对FCM算法在噪声点或野值点的鲁棒性上有所提高；但是KFCM仍存在以下两个主要缺点：1）由于仍然采用基于核空间的欧氏距离，没有考虑类与类之间的信息，而实际情况中，类与类之间的信息在聚类过程中发挥巨大的作用。2）由于采用梯度下降法迭代求解，易收敛于局部最优值，造成了KFCM对野值点或噪声点的鲁棒性不高。本文针对上述问题，提出了改进的基于核化距离的模糊C均值聚类（MKFCM）算法。该算法在KFCM算法的目标函数上引入了特征空间内的类间极大惩罚项，并通过引入调控因子λ实现对特征空间内类间划分的控制，使得聚类中心之间的距离最大化，使特征空间内类与类之间的间隔尽可能大。特征空间内的类间极大惩罚项的表达式如下：

2.1参数优化

2.2MKFCM的算法描述

根据定理1的推导，可得MKFCM算法的具体执行步骤如下：

步骤1设定核函数参数σ、聚类个数c和模糊指数m及收敛精度ε；初始化调控因子λ=1/n；最大迭代次数tmax；令迭代次数k=0。

步骤2用FCM算法初始化中心矩阵V（0）。

步骤3用式（12）计算U（k+1）。

步骤4用式（13）计算V（k+1）。

步骤5如果U（k）-U（k-1）≤ε，停止迭代；否则，k=k+1，转到步骤2。

当满足终止条件时，隶属度矩阵U和聚类中心矩阵V为算法的最优解。

3实验

实验是基于Matlab R2012a的编程环境中进行的。为了验证本文提出的算法的有效性，本文拟通过与FCM[5]、PCM[6]、FPCM[7]、KPCM[8]、KFCM[16]在模拟数据集和UCI真实数据集上进行对比实验，对本文所提出的算法进行评估和性能验证。

3.1评价指标

本文将选用以下三个指标，对聚类的结果进行评价，通过3个指标可以直观的评价本文算法的性能。

1）精度（ACCuracy， ACC）评价指标[19]。

ACC=[∑Ni=1δ（yi，map（ci））]/N（19）

其中：N表示数据点个数；yi表示真实的类标签，ci表示聚类过后的类标签；如果y=c，那么δ（y，c）=1，否则δ（y，c）=0a2+b2此处是否书写有误，是0乘以平方根吗？不就等于0吗？若有误，请作相应调整。；map（・）表示每个聚类过后的类标签到真实的类标签的一个置换函数，并且可以通过匈牙利算法获得最佳匹配。

2）归一化互信息（Normalized Mutual Information， NMI）评价指标[20]。

NMI=∑ci=1∑cj=1Nij lgN×NijNi×Nj（∑ci=1Ni lg Ni/N）×（∑cj=1Nj lg Nj/N）（20）

其中：Nij表示第i个聚类与类j之间的契合度；N表示样容量的大小；Nij表示第i个聚类的样本数目；Nj表示第j个聚类的样本数目。

3）芮氏（Rand Index， RI）评价指标[20]。

RI=f00+f11N（N-1）/2（21）

其中： f00表示数据点具有不同的类标签，且属于不同类的数据点数目； f11表示具有相同的类标签，且属于同一类别的数

据点数目；N表示样本的容量大小。

以上的3种评价指标的取值范围均为[0，1]，且数值越大，显示出算法的性能越优越。

3.2模拟数据实验

在模拟实验部分采用Diamond数据集[21]、Square数据集[22]、Bensaid数据集[23]，这3个数据集都是基于原始数据中存在噪声点或野值点的数据集，可以很好地验证MKFCM对噪声点和野值点的鲁棒性；采用人造高斯数据集，这个数据集中3个类边界非常模糊，对聚类过程的影响非常大，可以用来检测MKFCM对边界模糊数据集的聚类效果。

3.2.1Diamond数据集实验

Diamond数据集包含了12个样本点，其中10个点是关于Y轴对称的两个类，两类的准确中心分别为C1（-3.34，0）与C2（3.34，0），中间位置的两个样本点分别是噪声点和野值点，且它们到中心的距离相等。相关的实验结果如图1所示，较小的“+”表示第一类数据集，“”表示第一类数据集的聚类中心；“o”表示第二类数据集，“・”表示第二类数据集的聚类中心。相关的中心偏移距离如表1所示。

3.2.2Square数据集实验

Square数据集则包括一个小正方形数据集、一个大正方形数据行和部分噪声点，两个类的中心分别为C1（5.25，0.25）和C2（17，0），实验结果图2所示，“o”表示第一类数据集，“・”表示第一类数据集的聚类中心；“+”表示第二类数据集，“*”表示第二类数据集的聚类中心。实验结果数据如表2所示。

3.2.3Bensaid数据集实验

Bensaid数据集包括两个小的类和一个大的类以及各类之间的噪声点构成的，其3个准确的类中心为C1（3.2904，48.7730）、C2（55.3239，52.0772）和C3（112.1437，49.1043），实验结果如图3所示和，“o”表示第一类数据集，“・”表示第一类数据集的聚类中心；“+”表示第二类数据集，“”表示第二类数据集的聚类中心；“*”表示第三类数据集，“”表示第三类数据集的聚类中心。实验结果如表3所示。

通过图1～3以及图表1～3的实验结果可以看出MKFCM相比其他算法聚类中心偏离的最小，聚类效果更佳，对噪声点和野值点具有较好的鲁棒性。

通过上述3组数据集的实验可以看出：传统的FCM、KFCM对存在噪声点或野值点的数据集进行聚类分析时，易受噪声点或野值点的影响，因此聚类中心会发生较大的偏移。PCM、KPCM虽通过解除了隶属度和为1的约束，对噪声点或野值点具有较好的鲁棒性；但是它们在对边界模糊的数据集进行聚类时，会出现聚类中心重合的现象；本文算法通过类间极大惩罚项本文算法通过添加类间极大惩罚项此句完整吗？感觉未完或者描述有些问题？请作相应调整。，同时考虑了类内元素的紧密性和类间元素的相异性，对噪声点和野值点有很好的鲁棒性；同时对边界模糊的数据集可以通过拉大类中心间距离，使得边界处的数据集得到最佳分类。

3.2.4人造高斯数据集实验

人造高斯数据集由三类组成的，类之间边界模糊，实验结果如图4所示。“o”表示第一类数据集，“・”表示第一类数据集的聚类中心；“+”表示第二类数据集，“”表示第二类数据集的聚类中心；“*”表示第三类数据集，“”表示第三类数据集的聚类中心。

从图4以及表4可以看出：FCM、PCM、FPCM、KPCM和KFCM由于边界处的数据较模糊，因此容易造成误分的问题；而MKFCM则通过拉大类中心间的距离，同时考虑了类内与类间的关系，使得边界处的模糊数据得到了较好的划分，因此分类性能较其他4种算法有了一定的提高。

3.3UCI真实数据集实验

为了更好地证明本文算法的聚类优越性以及鲁棒性，与相关的传统算法进行比较，本文采用4个经典的UCI真实数据集进行实验。表5为本文采用的UCI数据集详细描述。

通过表6可以看出，MKFCM在公认的高维数据集中的聚类性能较之其余4种算法也有了明显的提升。

通过表2～4以及表6中MKFCM与传统的聚类算法在ACC、NMI、RI三种性能指标上的比较，可以得到一个结论：即本文算法能够很好地通过调节中心之间的距离来提高聚类效果，并且特别是对带有噪声和边界模糊的数据集有很好的鲁棒性。MKFCM算法，既继承了传统算法的可以很好地划分非线性可分数据的优点，又降低了对噪声点的敏感程度，还能较好地对边界模糊数据集进行聚类。通过几组实验，很好地证明了类间极大化的KFCM算法，相比其他几种聚类算法，在ACC、NMI、RI三种性能指标上有着明显的精度提升；但是本文提出的算法也有一些不足，即对聚类中心初始化以及参数选择问题仍有待改进。

4结语

KFCM是FCM在高维特征空间中的推广，本文从特征空间中类与类之间的距离关系进行改进，引入了类间极大惩罚项，并引入惩罚因子实现对类间划分的控制，提出了一种基于改进型核模糊C均值类间极大化（MKFCM）聚类算法。该算法优于现有的FCM、PCM、FPCM、KFCM等算法，聚类的准确性和稳定性有明显提高，对噪声点的鲁棒性较佳，对样本不平衡数据集和边界模糊数据集的聚类效果较好；但是该算法引入了新的参数且对参数的确定没有较好的办法，所以接下来的方向主要是研究如何确定参数使得聚类的效果最好。

参考文献：

[1]

CAI F， CHERKASSKY V. Generalized SMO algorithm for SVMbased multitask learning [J]. IEEE Transactions on Neural Networks and Learning Systems， 2012， 23（6）： 997-1003.

[2]

LIN K P， MING S C. On the design and analysis of the privacypreserving SVM classifier [J]. IEEE Transactions on Knowledge and Data Engineering， 2011， 23（11）： 1704-1717.

[3]

HALL L O， GOLDGOF D B. Convergence of the singlepass and online fuzzy Cmeans algorithms [J]. IEEE Transactions on Fuzzy Systems， 2011， 19（4）： 792-794.

[4]

CAMERON A C， MILLER D L. A practitioner’s guide to clusterrobust inference [J]. Journal of Human Resources， 2015， 50（2）： 317-372.

[5]

GONG M， LIANG Y， SHI J， et al. Fuzzy Cmeans clustering with local information and kernel metric for image segmentation [J]. IEEE Transactions on Image Processing， 2013， 22（2）： 573-584.

[6]

ZANG J， LI C. Possibilistic Cmeans algorithm based on collaborative optimization [C]// Proceedings of the 2014 International Conference on Computer Science and Information Technology. Berlin： Springer， 2014： 587-593.

[7]

RUBIO E， CASTILLO O. A new proposal for a granular fuzzy Cmeans algorithm [M]// Design of Intelligent Systems based on Fuzzy Logic， Neural Networks and NatureInspired Optimization. Berlin： Springer， 2015： 47-57.

[8]

RAZA M A， RHEE F C H. Interval type2 approach to kernel possibilistic Cmeans clustering [C]// Proceedings of the 2012 IEEE International Conference on Fuzzy Systems. Piscataway， NJ： IEEE， 2012： 1-7.

[9]

AIZERMAN A， BRAVERMAN E M， ROZONER L I. Theoretical foundations of the potential function method in pattern recognition learning [J]. Automation and Remote Control， 1964， 25（5）： 821-837.

[10]

CORTES C， VAPNIK V. Supportvector networks [J]. Machine Learning， 1995， 20（3）： 273-297.

[11]

XIE X L， BENI G. A validity measure for fuzzy clustering [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1991， 13（8）： 841-847.

[12]

FUKUYAMA F. What is governance？ [J]. Governance， 2013， 26（3）： 347-368.

[13]

ZAHID N， LIMOURI M， ESSAID A. A new clustervalidity for fuzzy clustering [J]. Pattern Recognition， 1999， 32（7）： 1089-1097.

[14]

GATH I， GEVA A B. Unsupervised optimal fuzzy clustering [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1989， 11（7）： 773-780.

[15]

ZDEMIR D， AKARUN L. Fuzzy algorithms for combined quantization and dithering [J]. IEEE Transactions on Image Processing， 2001， 10（6）： 923-931.

[16]

FERREIRA M R P， CARVALHO F D A T D. Kernel fuzzy Cmeans with automatic variable weighting [J]. Fuzzy Sets and Systems， 2014， 237（4）： 1-46.

[17]

WU K L， YU J， YANG M S. A novel fuzzy clustering algorithm based on a fuzzy scatter matrix with optimality tests [J]. Pattern Recognition Letters， 2005， 26（5）： 639-652.

[18]

WU K L， YANG M S. Alternative Cmeans clustering algorithms [J]. Pattern Recognition， 2002， 35（10）： 2267-2278.

[19]

HUANG Z， NG M K. A fuzzy kmodes algorithm for clustering categorical data [J]. IEEE Transactions on Fuzzy Systems， 1999， 7（4）： 446-452.

[20]

LIU J， MOHAMMED J， CARTER J， et al. Distancebased clustering of CGH data [J]. Bioinformatics， 2006， 22（16）： 1971-1978.

[21]

PAL N R， PAL K， KELLER J M， et al. A possibilistic fuzzy Cmeans clustering algorithm [J]. IEEE Transactions on Fuzzy Systems， 2005， 13（4）： 517-530.

[22]

ZADEH L A. Fuzzy sets [J]. Information and Control， 1965， 8（3）： 338-353.

[23]

BENSAID A M， HALL L O， BEZDEK J C， et al. Validityguided （re）clustering with applications to image segmentation [J]. IEEE Transactions on Fuzzy Systems， 1996， 4（2）： 112-123.