吳鵬

摘 要：Fuzzy C-Means（FCM）模糊c均值聚類算法是一個(gè)應(yīng)用廣泛、有效的無(wú)監(jiān)督聚類算法。但傳統(tǒng)FCM算法存在對(duì)所有樣本等劃分的缺點(diǎn)，導(dǎo)致聚類精度不高、魯棒性不強(qiáng)。針對(duì)上述問題，從整體上引入點(diǎn)密度關(guān)系，從局部上引入點(diǎn)鄰域信息，用以標(biāo)記每個(gè)樣本點(diǎn)，提出基于點(diǎn)密度和鄰域信息的模糊c均值算法（DLFCM）。該算法能標(biāo)記每個(gè)不同的樣本，克服了FCM算法等劃分的缺點(diǎn)，提高了算法的聚類精度和魯棒性。人造數(shù)據(jù)集和UCI真實(shí)數(shù)據(jù)集實(shí)驗(yàn)驗(yàn)證了該算法的有效性。

關(guān)鍵詞：聚類算法；目標(biāo)函數(shù)；鄰域信息；魯棒性

DOI：10.11907/rjdk.172554

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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）通俗說(shuō)就是“物以類聚”，將本身沒有給出類標(biāo)簽的數(shù)據(jù)集，根據(jù)樣本間的某種關(guān)系進(jìn)行類別劃分，以達(dá)到類內(nèi)樣本間相似度盡可能高、類間樣本相似度盡可能低的目的。近年來(lái)，由于大數(shù)據(jù)時(shí)代的到來(lái)，數(shù)據(jù)處理變得越來(lái)越重要，聚類作為數(shù)據(jù)處理的一個(gè)重要工具被廣泛研究。數(shù)據(jù)挖掘、模式識(shí)別、圖像處理等眾多領(lǐng)域都離不開聚類算法，該類算法中有大量的經(jīng)典算法，例如基于劃分的K-means和K-medoids[1-3]聚類算法、基于層次的CURE和BRICH聚類算法、基于密度[4-8]的DBSCAN聚類算法等。

傳統(tǒng)的聚類算法都屬于硬聚類算法，即某樣本要么只屬于某一類，要么只屬于其它某一類。這種“非此即彼”的關(guān)系并不符合實(shí)際。1974年Dunn[4]將模糊數(shù)學(xué)和K-means聚類算法結(jié)合，提出了模糊C均值（FCM）聚類算法，以隸屬度來(lái)標(biāo)記樣本點(diǎn)和所有類中心間的隸屬關(guān)系，使類內(nèi)誤差平方和達(dá)到最小值。

傳統(tǒng)的FCM算法存在許多不足，F(xiàn)CM算法的最小化誤差平方和目標(biāo)函數(shù)等同作為樣本，具有對(duì)數(shù)據(jù)進(jìn)行等劃分的趨勢(shì)，這個(gè)趨勢(shì)導(dǎo)致算法的聚類精度低、魯棒性差。針對(duì)這一問題，本文提出兩個(gè)解決方案：①整體上，用樣本點(diǎn)的分布密度標(biāo)記每個(gè)樣本的分布特性；②局部上，用樣本鄰域空間信息反映樣本與鄰域樣本之間的關(guān)系。結(jié)合這兩點(diǎn)，提出了基于點(diǎn)密度和鄰域信息的模糊C-均值（DLFCM）算法，該算法唯一標(biāo)記每個(gè)樣本對(duì)聚類的影響因子，在一定程度上克服了FCM對(duì)數(shù)據(jù)集所有樣本等劃分趨勢(shì)的缺陷，增強(qiáng)了FCM算法的聚類精度，一定程度上提高了FCM算法的魯棒性。

1 模糊C均值（FCM）算法

模糊C均值（FCM）聚類算法是Dunn在K均值算法的基礎(chǔ)上提出，并由Bezdek[5]拓展開來(lái)。FCM算法通過(guò)不斷迭代得到c個(gè)類，使得類內(nèi)平方誤差目標(biāo)函數(shù)J達(dá)到最小值。

FCM算法步驟如下：①選定聚類數(shù)目c、模糊指數(shù)m、最大迭代次數(shù)T和閾值ε，初始化劃分矩陣U并令迭代計(jì)數(shù)器b=0；②根據(jù)公式（5）計(jì)算新的聚類中心；③根據(jù)公式（6）計(jì)算新的隸屬度矩陣，并令b=b+1；④根據(jù)當(dāng)前的V和U，計(jì)算目標(biāo)函數(shù)式（1）的值。若迭代次數(shù)大于T或者目標(biāo)函數(shù)相對(duì)于上次的函數(shù)值變量的絕對(duì)值小于閾值ε，則算法停止運(yùn)行，否則返回步驟②繼續(xù)進(jìn)行。

2 基于點(diǎn)密度與鄰域信息的FCM算法

2.1 點(diǎn)密度加權(quán)系數(shù)計(jì)算

對(duì)于某個(gè)給定的數(shù)據(jù)集一般無(wú)法確定其準(zhǔn)確的分布模型，自然也就沒有準(zhǔn)確的點(diǎn)密度分布情況，但通常情況下可以這樣認(rèn)為：某個(gè)樣本點(diǎn)的周圍樣本點(diǎn)越多，則該點(diǎn)就處于越密集的區(qū)域，自然對(duì)分類的影響也就越大。

為了衡量樣本點(diǎn)所處數(shù)據(jù)集的密度分布情況，本文解決方案如下：

這樣一來(lái)就可以用wi作為一個(gè)加權(quán)系數(shù)，表示某個(gè)樣本點(diǎn)xi對(duì)分類的影響程度。密度系數(shù)是從數(shù)據(jù)集的整體上觀察不同樣本對(duì)聚類的影響。

2.2 鄰域空間信息

Ahmed[9]曾針對(duì)噪聲圖像分割提出了一個(gè)改進(jìn)的FCM算法，該算法引入樣本點(diǎn)的鄰域空間信息作為該點(diǎn)目標(biāo)函數(shù)的一個(gè)偏移量，其目標(biāo)函數(shù)定義如下：

可以看到式（11）中的1/NR*∑r∈Nixr本質(zhì)是對(duì)樣本點(diǎn)xi鄰域內(nèi)的樣本求平均值，且式（9）中的a需要人工確定。目標(biāo)函數(shù)式（9）的第二項(xiàng)中的xi鄰域點(diǎn)對(duì)它的影響因子因a/NR而平均化，顯然不太合理，既然每個(gè)點(diǎn)都不同，對(duì)xi的影響因子也應(yīng)該不同。為了在沒有先驗(yàn)條件下標(biāo)記每個(gè)不同的樣本點(diǎn)，本文將a/NR換成與距離相關(guān)的表達(dá)形式1/（dij+1），寫成分?jǐn)?shù)的形式是為了防止目標(biāo)函數(shù)的第二項(xiàng)對(duì)整個(gè)函數(shù)的貢獻(xiàn)超過(guò)第一項(xiàng)，分母加1是為了防止dij<1而導(dǎo)致分式的值過(guò)大。由該表達(dá)式可以看出，該式無(wú)需人工確定參數(shù)，所有的參數(shù)都是自適應(yīng)確定的。因此，可以重新定義鄰域信息影響因子：

式（12）中，第i個(gè)點(diǎn)可以看作是鄰域數(shù)據(jù)點(diǎn)組成的小窗口（比如3*3的小窗口）中心，xj表示位于這個(gè)小窗口里的數(shù)據(jù)點(diǎn)，Ni是窗口內(nèi)數(shù)據(jù)點(diǎn)的數(shù)目，dij是對(duì)應(yīng)的第i個(gè)點(diǎn)和窗口內(nèi)第j個(gè)點(diǎn)的歐式距離，vk是上一次迭代時(shí)第k類的聚類中心，ukj對(duì)應(yīng)第j個(gè)樣本點(diǎn)在第k類中的隸屬度，m是模糊指數(shù)。

2.3 DLFCM總體框架

結(jié)合式（8）的點(diǎn)密度權(quán)值wi和式（12）的鄰域信息因子Gki，在FCM算法基礎(chǔ)上提出基于點(diǎn)密度和鄰域信息的FCM算法（DLFCM），定義該算法的目標(biāo)函數(shù)如下：

由于FCM算法的初始聚類中心是隨機(jī)的，因此迭代收斂得到的最優(yōu)解很容易受到初始值影響。為了減弱初始值對(duì)聚類精度的影響，本文采用如下選擇初始聚類中心策略，其步驟描述如下：①設(shè)m=1，在數(shù)據(jù)集X中計(jì)算每個(gè)點(diǎn)到其它點(diǎn)的距離，找到距離值最小的一對(duì)點(diǎn)，令A(yù)m（1≤m≤k，k表示類別數(shù)）包含這一對(duì)點(diǎn)，并將這一對(duì)點(diǎn)從X中除去；②繼續(xù)從X中找到距離Am最近的點(diǎn)加到其中，并從X中除去；③不斷重復(fù)步驟②直到Am中的點(diǎn)達(dá)到α*N/k（α一般取3/4）；④若m

DLFCM算法步驟如下：①用上述算法初始化聚類中心；初始化模糊指數(shù)m閾值ε，并根據(jù)式（6）計(jì)算初始隸屬度矩陣，設(shè)定最大迭代次數(shù)T；②利用式（10）計(jì)算點(diǎn)密度權(quán)系數(shù)；③令迭代計(jì)數(shù)器b=0；④根據(jù)式（15）計(jì)算隸屬度矩陣；⑤運(yùn)用式（16）計(jì)算聚類中心；⑥若‖v（b+1）-v（b）‖<ε或者b>T，停止計(jì)算，否則令b=b+1跳到步驟④繼續(xù)執(zhí)行。

3 實(shí)驗(yàn)研究

為驗(yàn)證本文所提出的DLFCM算法性能，用人工數(shù)據(jù)集和UCI[11]數(shù)據(jù)庫(kù)數(shù)據(jù)分組進(jìn)行仿真實(shí)驗(yàn)。本文實(shí)驗(yàn)在Intel Core（TM）2 Duo CPU E7200 2.53GHz，2.00GB內(nèi)存：Windows 7，Matlab 2012b環(huán)境下完成。

為了體現(xiàn)DLFCM算法的可比性，用FCM、KFCM、PCM和KPCM算法作為比較算法，并采用如下的NMI（normalized mutual information） [10-12]和RI（rand index）[13-14]兩種評(píng)價(jià)指標(biāo)[15-18]對(duì)聚類算法性能進(jìn)行分析比較。

NMI（X，Y）中，X為初始樣本數(shù)據(jù)集，Y是算法的聚類結(jié)果，I（X，Y）表示X和Y的互信息量，H（X）和H（Y）分別表示X和Y的熵；RI（X，Y）中，a表示任意兩個(gè)樣本數(shù)據(jù)在X和Y中屬于同一類數(shù)目，b表示任意兩個(gè)樣本數(shù)據(jù)都不屬于同一類數(shù)目，n為數(shù)據(jù)集X中的樣本數(shù)。0≤NMI（X，Y）≤1，0≤RI（X，Y）≤1，若X和Y完全相同時(shí)，這兩個(gè)指標(biāo)的值都為1。X和Y越接近，這兩個(gè)指標(biāo)的值就越大，說(shuō)明聚類算法的結(jié)果越準(zhǔn)確。

3.1 人造數(shù)據(jù)集

用人造數(shù)據(jù)集對(duì)5個(gè)算法進(jìn)行分析和比較，該人造數(shù)據(jù)集由2維歐幾里德空間中服從高斯分布的3類數(shù)據(jù)共900個(gè)點(diǎn)組成，其中心點(diǎn)分別為（1，3），（2，10），（9，4），所對(duì)應(yīng)的各類樣本點(diǎn)個(gè)數(shù)分別為400個(gè)、300個(gè)和200個(gè)；類方差分別為[6，0；0，5]，[6，0；0，6]，[5，0；0，6]，人造數(shù)據(jù)集分布如圖1所示。

令迭代閾值ε為1e-5，最大迭代次數(shù)為500，也就是說(shuō)算法迭代的終止條件為‖v（b+1）-v（b）‖<ε或者b>100。為了驗(yàn)證DLFCM的魯棒性，在人造數(shù)據(jù)集上施加了噪聲參數(shù)為[0，1]的隨機(jī)噪聲，聚類結(jié)果如表1所示。

從表1可以清楚地看到，在無(wú)噪聲的情況下，DLFCM算法性能略高于其它4種算法，在加有隨機(jī)噪聲數(shù)據(jù)后的DLFCM算法也略高于其它4種算法。在這個(gè)過(guò)程中，DLFCM算法的性能波動(dòng)最小，所以說(shuō)DLFCM在算法的魯棒性上較FCM有一定的提高。

3.2 真實(shí)數(shù)據(jù)集

為了對(duì)DLFCM算法聚類性能作進(jìn)一步分析，使用UCI真實(shí)數(shù)據(jù)集對(duì)FCM、KFCM、PCM、KPCM和DLFCM算法進(jìn)行比較，所使用的數(shù)據(jù)集基本信息如表2所示。同樣，本部分實(shí)驗(yàn)初始化參數(shù)迭代閾值ε=1e-5，最大迭代次數(shù)為500。

表3顯示對(duì)表2中的UCI數(shù)據(jù)集分別運(yùn)行5種聚類算法的NMI、RI指標(biāo)值。

由表3可以很清楚地看到5類算法在UCI數(shù)據(jù)集上的性能表現(xiàn)，大多數(shù)情況下DLFCM的性能指標(biāo)都要高于其它算法，驗(yàn)證了本文算法的有效性。

4 結(jié)語(yǔ)

為解決FCM算法中樣本點(diǎn)對(duì)目標(biāo)函數(shù)貢獻(xiàn)平等這一缺點(diǎn)，本文首先在整體上引入了點(diǎn)密度加權(quán)信息，然后針對(duì)每個(gè)樣本點(diǎn)的鄰域信息提出自適應(yīng)鄰域信息因子，綜合兩者唯一標(biāo)記每個(gè)樣本對(duì)聚類的影響因子，提出新的FCM算法——DLFCM算法。大量的人造數(shù)據(jù)集和經(jīng)典UCI真實(shí)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果表明：①DLFCM算法受噪聲的影響相對(duì)較小，具有一定的魯棒性；②DLFCM算法在一定程度上提高了聚類算法的聚類精度，具有一定的實(shí)用性。

參考文獻(xiàn)：

[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] 劉小芳，曾黃麟，呂炳朝.點(diǎn)密度函數(shù)加權(quán)模糊C-均值算法的聚類分析[J].計(jì)算機(jī)工程與應(yīng)用，2004，40（24）：64-65.

[7] 高新波，裴繼紅，謝維信.模糊c-均值聚類算法中加權(quán)指數(shù) m 的研究[J].電子學(xué)報(bào)，2000（4）：156-159.

[8] 劉小芳.基于模糊聚類理論的模式識(shí)別研究[D].成都：電子科技大學(xué)，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ìn)的模糊聚類圖像分割算法研究與仿真[J].計(jì)算機(jī)仿真，2015，32（4）：380-383.

[16] 譚營(yíng)軍，李翠霞.加權(quán)模糊C均值文本聚類算法研究及仿真[J].計(jì)算機(jī)仿真，2011，28（5）：220-223.

[17] 劉小芳，曾黃麟，呂炳朝，等.部分監(jiān)督加權(quán)模糊C-均值算法的聚類分析[J].計(jì)算機(jī)仿真，2005，22（3）：114-116.

[18] 劉笛，朱學(xué)峰，蘇彩紅.一種新型的模糊C均值聚類初始化方法[J].計(jì)算機(jī)仿真，2004，21（11）：148-151.

（責(zé)任編輯：杜能鋼）