基于點密度與鄰域信息的模糊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.

（責任編輯：杜能鋼）