基于点密度与邻域信息的模糊C均值算法

吴鹏

摘 要：Fuzzy C-Means（FCM）模糊c均值聚类算法是一个应用广泛、有效的无监督聚类算法。但传统FCM算法存在对所有样本等划分的缺点，导致聚类精度不高、鲁棒性不强。针对上述问题，从整体上引入点密度关系，从局部上引入点邻域信息，用以标记每个样本点，提出基于点密度和邻域信息的模糊c均值算法（DLFCM）。该算法能标记每个不同的样本，克服了FCM算法等划分的缺点，提高了算法的聚类精度和鲁棒性。人造数据集和UCI真实数据集实验验证了该算法的有效性。

关键词：聚类算法；目标函数；邻域信息；鲁棒性

DOI：10.11907/rjdk.172554

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2018）004-0085-04

Abstract：Fuzzy c-means （FCM） cluster algorithm is a widely used and an effective unsupervised cluster algorithm. But the traditional FCM algorithm classifies all the samples equally， which leads to low clustering accuracy and low robustness. To deal with this problem， this paper introduces dot density relation from the overall and the local information from the local， to tag every sample point then based on the point density and local information a new FCM algorithm is proposed named DLFCMand proposes a fuzzy C-means algorithm based on dot density and local information（DLFCM）. The algorithm can mark each different sample， overcome the disadvantages of FCM algorithm and improve the clustering accuracy and robustness Synthetic data and UCI data experiments have proved the effectiveness of the new algorithm.

Key Words：clustering algorithm； objective function； local Information； robustness

0 引言

聚类（clustering）通俗说就是“物以类聚”，将本身没有给出类标签的数据集，根据样本间的某种关系进行类别划分，以达到类内样本间相似度尽可能高、类间样本相似度尽可能低的目的。近年来，由于大数据时代的到来，数据处理变得越来越重要，聚类作为数据处理的一个重要工具被广泛研究。数据挖掘、模式识别、图像处理等众多领域都离不开聚类算法，该类算法中有大量的经典算法，例如基于划分的K-means和K-medoids[1-3]聚类算法、基于层次的CURE和BRICH聚类算法、基于密度[4-8]的DBSCAN聚类算法等。

传统的聚类算法都属于硬聚类算法，即某样本要么只属于某一类，要么只属于其它某一类。这种“非此即彼”的关系并不符合实际。1974年Dunn[4]将模糊数学和K-means聚类算法结合，提出了模糊C均值（FCM）聚类算法，以隶属度来标记样本点和所有类中心间的隶属关系，使类内误差平方和达到最小值。

传统的FCM算法存在许多不足，FCM算法的最小化误差平方和目标函数等同作为样本，具有对数据进行等划分的趋势，这个趋势导致算法的聚类精度低、鲁棒性差。针对这一问题，本文提出两个解决方案：①整体上，用样本点的分布密度标记每个样本的分布特性；②局部上，用样本邻域空间信息反映样本与邻域样本之间的关系。结合这两点，提出了基于点密度和邻域信息的模糊C-均值（DLFCM）算法，该算法唯一标记每个样本对聚类的影响因子，在一定程度上克服了FCM对数据集所有样本等划分趋势的缺陷，增强了FCM算法的聚类精度，一定程度上提高了FCM算法的鲁棒性。

1 模糊C均值（FCM）算法

模糊C均值（FCM）聚类算法是Dunn在K均值算法的基础上提出，并由Bezdek[5]拓展开来。FCM算法通过不断迭代得到c个类，使得类内平方误差目标函数J达到最小值。

FCM算法步骤如下：①选定聚类数目c、模糊指数m、最大迭代次数T和阈值ε，初始化划分矩阵U并令迭代计数器b=0；②根据公式（5）计算新的聚类中心；③根据公式（6）计算新的隶属度矩阵，并令b=b+1；④根据当前的V和U，计算目标函数式（1）的值。若迭代次数大于T或者目标函数相对于上次的函数值变量的绝对值小于阈值ε，则算法停止运行，否则返回步骤②继续进行。

2 基于点密度与邻域信息的FCM算法

2.1 点密度加权系数计算

对于某个给定的数据集一般无法确定其准确的分布模型，自然也就没有準确的点密度分布情况，但通常情况下可以这样认为：某个样本点的周围样本点越多，则该点就处于越密集的区域，自然对分类的影响也就越大。

为了衡量样本点所处数据集的密度分布情况，本文解决方案如下：

这样一来就可以用wi作为一个加权系数，表示某个样本点xi对分类的影响程度。密度系数是从数据集的整体上观察不同样本对聚类的影响。

2.2 邻域空间信息

Ahmed[9]曾针对噪声图像分割提出了一个改进的FCM算法，该算法引入样本点的邻域空间信息作为该点目标函数的一个偏移量，其目标函数定义如下：

可以看到式（11）中的1/NR*∑r∈Nixr本质是对样本点xi邻域内的样本求平均值，且式（9）中的a需要人工确定。目标函数式（9）的第二项中的xi邻域点对它的影响因子因a/NR而平均化，显然不太合理，既然每个点都不同，对xi的影响因子也应该不同。为了在没有先验条件下标记每个不同的样本点，本文将a/NR换成与距离相关的表达形式1/（dij+1），写成分数的形式是为了防止目标函数的第二项对整个函数的贡献超过第一项，分母加1是为了防止dij<1而导致分式的值过大。由该表达式可以看出，该式无需人工确定参数，所有的参数都是自适应确定的。因此，可以重新定义邻域信息影响因子：

式（12）中，第i个点可以看作是邻域数据点组成的小窗口（比如3*3的小窗口）中心，xj表示位于这个小窗口里的数据点，Ni是窗口内数据点的数目，dij是对应的第i个点和窗口内第j个点的欧式距离，vk是上一次迭代时第k类的聚类中心，ukj对应第j个样本点在第k类中的隶属度，m是模糊指数。

2.3 DLFCM总体框架

结合式（8）的点密度权值wi和式（12）的邻域信息因子Gki，在FCM算法基础上提出基于点密度和邻域信息的FCM算法（DLFCM），定义该算法的目标函数如下：

由于FCM算法的初始聚类中心是随机的，因此迭代收敛得到的最优解很容易受到初始值影响。为了减弱初始值对聚类精度的影响，本文采用如下选择初始聚类中心策略，其步骤描述如下：①设m=1，在數据集X中计算每个点到其它点的距离，找到距离值最小的一对点，令Am（1≤m≤k，k表示类别数）包含这一对点，并将这一对点从X中除去；②继续从X中找到距离Am最近的点加到其中，并从X中除去；③不断重复步骤②直到Am中的点达到α*N/k（α一般取3/4）；④若m

DLFCM算法步骤如下：①用上述算法初始化聚类中心；初始化模糊指数m阈值ε，并根据式（6）计算初始隶属度矩阵，设定最大迭代次数T；②利用式（10）计算点密度权系数；③令迭代计数器b=0；④根据式（15）计算隶属度矩阵；⑤运用式（16）计算聚类中心；⑥若‖v（b+1）-v（b）‖<ε或者b>T，停止计算，否则令b=b+1跳到步骤④继续执行。

3 实验研究

为验证本文所提出的DLFCM算法性能，用人工数据集和UCI[11]数据库数据分组进行仿真实验。本文实验在Intel Core（TM）2 Duo CPU E7200 2.53GHz，2.00GB内存：Windows 7，Matlab 2012b环境下完成。

为了体现DLFCM算法的可比性，用FCM、KFCM、PCM和KPCM算法作为比较算法，并采用如下的NMI（normalized mutual information） [10-12]和RI（rand index）[13-14]两种评价指标[15-18]对聚类算法性能进行分析比较。

NMI（X，Y）中，X为初始样本数据集，Y是算法的聚类结果，I（X，Y）表示X和Y的互信息量，H（X）和H（Y）分别表示X和Y的熵；RI（X，Y）中，a表示任意两个样本数据在X和Y中属于同一类数目，b表示任意两个样本数据都不属于同一类数目，n为数据集X中的样本数。0≤NMI（X，Y）≤1，0≤RI（X，Y）≤1，若X和Y完全相同时，这两个指标的值都为1。X和Y越接近，这两个指标的值就越大，说明聚类算法的结果越准确。

3.1 人造数据集

用人造数据集对5个算法进行分析和比较，该人造数据集由2维欧几里德空间中服从高斯分布的3类数据共900个点组成，其中心点分别为（1，3），（2，10），（9，4），所对应的各类样本点个数分别为400个、300个和200个；类方差分别为[6，0；0，5]，[6，0；0，6]，[5，0；0，6]，人造数据集分布如图1所示。

令迭代阈值ε为1e-5，最大迭代次数为500，也就是说算法迭代的终止条件为‖v（b+1）-v（b）‖<ε或者b>100。为了验证DLFCM的鲁棒性，在人造数据集上施加了噪声参数为[0，1]的随机噪声，聚类结果如表1所示。

从表1可以清楚地看到，在无噪声的情况下，DLFCM算法性能略高于其它4种算法，在加有随机噪声数据后的DLFCM算法也略高于其它4种算法。在这个过程中，DLFCM算法的性能波动最小，所以说DLFCM在算法的鲁棒性上较FCM有一定的提高。

3.2 真实数据集

为了对DLFCM算法聚类性能作进一步分析，使用UCI真实数据集对FCM、KFCM、PCM、KPCM和DLFCM算法进行比较，所使用的数据集基本信息如表2所示。同样，本部分实验初始化参数迭代阈值ε=1e-5，最大迭代次数为500。

表3显示对表2中的UCI数据集分别运行5种聚类算法的NMI、RI指标值。

由表3可以很清楚地看到5类算法在UCI数据集上的性能表现，大多数情况下DLFCM的性能指标都要高于其它算法，验证了本文算法的有效性。

4 结语

为解决FCM算法中样本点对目标函数贡献平等这一缺点，本文首先在整体上引入了点密度加权信息，然后针对每个样本点的邻域信息提出自适应邻域信息因子，综合两者唯一标记每个样本对聚类的影响因子，提出新的FCM算法——DLFCM算法。大量的人造数据集和经典UCI真实数据集实验结果表明：①DLFCM算法受噪声的影响相对较小，具有一定的鲁棒性；②DLFCM算法在一定程度上提高了聚类算法的聚类精度，具有一定的实用性。

参考文献：

[1] KRINIDIS S， CHATZIS V. A robust fuzzy local information C-means clustering algorithm[J]. Image Processing， IEEE Transactions on，2010，19（5）：1328-1337.

[2] ZHU C， YANG S， ZHAO Q， et al. Robust semi-supervised kernel-FCM algorithm incorporating local spatial information for remote sensing image classification[J]. Journal of the Indian Society of Remote Sensing，2014，42（1）：35-49.

[3] SINGH K K， NIGAM M J， PAL K， et al. A Fuzzy Kohonen Local Information C-Means Clustering for Remote Sensing Imagery[J]. IETE Technical Review，2014，31（1）：75-81.

[4] DUNN J C. A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters[EB/OL]. https：//www.tandfonline.com/doi/abs/10.1080/01969727308546046.

[5] BEZDEK J C. Pattern recognition with fuzzy objective function algorithms[M]. Kluwer Academic Publishers，1981.

[6] 劉小芳，曾黄麟，吕炳朝.点密度函数加权模糊C-均值算法的聚类分析[J].计算机工程与应用，2004，40（24）：64-65.

[7] 高新波，裴继红，谢维信.模糊c-均值聚类算法中加权指数 m 的研究[J].电子学报，2000（4）：156-159.

[8] 刘小芳.基于模糊聚类理论的模式识别研究[D].成都：电子科技大学，2004.

[9] AHMED M N， YAMANY S M， MOHAMED N， et al. A modified fuzzy c-means algorithm for bias field estimation and segmentation of MRI data[J]. Medical Imaging， IEEE Transactions on，2002，21（3）：193-199.

[10] YUAN F， MENG Z H， ZHANG H X， et al. A new algorithm to get the initial centroids[J].Machine Learning and Cybernetics， 2004. Proceedings of 2004 International Conference on. IEEE，2004（2）：1191-1193.

[11] PAL N R， BEZDEK J C. On cluster validity for the fuzzy c-means model[J]. Fuzzy Systems， IEEE Transactions on，1995，3（3）：370-379.

[12] GHOSH J. Multiclassifier systems： back to the future[M].Multiple classifier systems，Springer Berlin Heidelberg，2002：1-15.

[13] IWAYAMA M， TOKUNAGA T. Hierarchical bayesian clustering for automatic text classification[C].Proceedings of the 14th international joint conference on Artificial intelligence-Volume 2. Morgan Kaufmann Publishers Inc.，1995：1322-1327.

[14] RAND W M. Objective criteria for the evaluation of clustering methods[J]. Journal of the American Statistical association，1971，66（336）：846-850.

[15] 张杰，范洪辉.一种改进的模糊聚类图像分割算法研究与仿真[J].计算机仿真，2015，32（4）：380-383.

[16] 谭营军，李翠霞.加权模糊C均值文本聚类算法研究及仿真[J].计算机仿真，2011，28（5）：220-223.

[17] 刘小芳，曾黄麟，吕炳朝，等.部分监督加权模糊C-均值算法的聚类分析[J].计算机仿真，2005，22（3）：114-116.

[18] 刘笛，朱学峰，苏彩红.一种新型的模糊C均值聚类初始化方法[J].计算机仿真，2004，21（11）：148-151.

（责任编辑：杜能钢）