一種快速全局中心模糊聚類(lèi)方法

孫冬璞 譚潔瓊

摘 要：針對(duì)模糊C均值算法對(duì)初始中心敏感、容易陷入局部最優(yōu)解，且算法迭代速度慢等問(wèn)題，依據(jù)模糊聚類(lèi)的全局中心理論，建立了一種快速全局中心模糊聚類(lèi)系統(tǒng)模型，并給出了相關(guān)理論分析和算法流程。該模型通過(guò)DKC值方案對(duì)各數(shù)據(jù)成員進(jìn)行密集度分析來(lái)確定初始質(zhì)心，并結(jié)合AM度量提出自定義尋優(yōu)函數(shù)，依據(jù)該函數(shù)在算法運(yùn)行的每一個(gè)階段來(lái)逐一動(dòng)態(tài)增加聚類(lèi)中心，直至算法收斂。通過(guò)實(shí)驗(yàn)對(duì)比和驗(yàn)證，該過(guò)程降低了隨機(jī)選取聚類(lèi)中心對(duì)聚類(lèi)結(jié)果的影響，跳出局部最優(yōu)解，減少計(jì)算量，具有更高的聚類(lèi)精度和更快的收斂速度。

關(guān)鍵詞：模糊聚類(lèi);全局中心;DKC;AM度量;噪聲點(diǎn)

DOI：10.15938/j.jhust.2019.04.019

中圖分類(lèi)號(hào)： TP311

文獻(xiàn)標(biāo)志碼： A

文章編號(hào)： 1007-2683（2019）04-0110-08

Abstract：In terms of the problems that the fuzzy C-means algorithm is sensitive to the initial center， easy to fall into the local optimal solution， and the algorithm iteration speed is slow， a rapid global center fuzzy clustering system model is established according to the global center theory of fuzzy clustering， and the relevant theoretical analysis and algorithm process is given. In the model， the initial centroid is determined by the DKC value scheme， and the self-defined optimization function is proposed based on the AM metric. According to this function， the cluster centers are dynamically added one by one to every stage of algorithm operation until the algorithm converges. Through experimental comparison and verification， the process reduces the influence of random selection of cluster centers on clustering results， and jumps out of local optimal solution， reduces computation， and has higher clustering accuracy and faster convergence speed.

Keywords：fuzzy clustering; global center; DKC; AM metric; noise point

0 引 言

模糊C均值聚類(lèi)[1-2]（fuzzy C means clustering，F(xiàn)CM）是眾多模糊聚類(lèi)的代表，在傳統(tǒng)的硬聚類(lèi)算法中，每一個(gè)數(shù)據(jù)成員只隸屬于一個(gè)類(lèi)別[3]，但在真實(shí)世界的數(shù)據(jù)集中，各成員對(duì)各自屬于哪一類(lèi)往往沒(méi)有明顯的界限。而FCM算法在執(zhí)行過(guò)程中，根據(jù)不同的隸屬度值，每個(gè)數(shù)據(jù)成員可以按照一定概率屬于多個(gè)類(lèi)別，F(xiàn)CM通過(guò)迭代式爬山算法來(lái)尋找問(wèn)題的最優(yōu)解。然而，該算法具有一定的局限性，比如，對(duì)初始條件較為敏感[4]，容易陷入局部最優(yōu)，易受噪聲點(diǎn)影響，且聚類(lèi)數(shù)目難以確定，算法執(zhí)行速度慢等缺陷[5-6]。為此，國(guó)內(nèi)外學(xué)者做了大量研究。有通過(guò)模擬自然進(jìn)化過(guò)程的搜索最優(yōu)解的方法，將遺傳算法引入模糊聚類(lèi)[7-8]，避免算法陷入局部最優(yōu)解，但仍存在局部搜索能力較弱、容易陷入“早熟”等缺點(diǎn)。也有將模擬退火算法與FCM相結(jié)合，使算法具有較強(qiáng)的局部搜索能力[9]，但模擬退火算法本身對(duì)全局搜索空間了解不多，運(yùn)算效率不高。文獻(xiàn)[10]提出了一種非噪聲敏感性FCM算法（INFCM），取消了對(duì)隸屬度的限制條件，構(gòu)建出一種增加了懲罰因子的目標(biāo)方程，具有較好的魯棒性，但算法依然不能保證跳出局部極小值、取得全局最優(yōu)解。文[11]提出了快速全局FCM聚類(lèi)算法，雖然該方法在很多方面彌補(bǔ)了FCM算法的不足，改善了算法性能，但仍容易受噪聲點(diǎn)或孤立點(diǎn)的影響，且聚類(lèi)精度低、速度慢等問(wèn)題依然存在。

針對(duì)以上分析，本文提出將動(dòng)態(tài)規(guī)劃的全局思想和改進(jìn)聚類(lèi)中心點(diǎn)選取方法結(jié)合，在動(dòng)態(tài)增加聚類(lèi)劃分并選取最佳聚類(lèi)中心的過(guò)程中，通過(guò)計(jì)算所有數(shù)據(jù)對(duì)象的DKC值[12]確定樣本分布密集區(qū)域且排除稀疏區(qū)域，降低外圍孤立點(diǎn)的影響。同時(shí)，本文采用AM度量[13]來(lái)提高算法穩(wěn)定性，并通過(guò)DKC值和AM度量所確定的自定義尋優(yōu)函數(shù)尋找一個(gè)周?chē)鷶?shù)據(jù)對(duì)象點(diǎn)分布比較密集且距離當(dāng)前已有聚類(lèi)中心都比較遠(yuǎn)的數(shù)據(jù)對(duì)象點(diǎn)作為下一個(gè)簇的最佳聚類(lèi)初始中心，該函數(shù)綜合AM度量和DKC值兩者優(yōu)勢(shì)，更能快速且準(zhǔn)確的確定出最佳聚類(lèi)中心，加快算法收斂速度。

1 相關(guān)工作

FCM聚類(lèi)算法是一種基于目標(biāo)函數(shù)優(yōu)化的無(wú)監(jiān)督數(shù)據(jù)聚類(lèi)方法，即一個(gè)反復(fù)更新聚類(lèi)中心及隸屬度從而使目標(biāo)函數(shù)J最小化的過(guò)程，其工作原理是：隨機(jī)初始化c個(gè)數(shù)據(jù)對(duì)象作為初始聚類(lèi)中心，分別計(jì)算剩余對(duì)象與該c個(gè)成員的歐氏距離，再根據(jù)距離值將所有對(duì)象按照一定概率依次分配給最近的聚類(lèi)中心，得到隸屬度矩陣，分別計(jì)算新的類(lèi)內(nèi)成員平均值，再次更新聚類(lèi)中心。將以上過(guò)程不斷重復(fù)至算法收斂，則聚類(lèi)過(guò)程結(jié)束[14]。

FCM算法雖然應(yīng)用廣泛、靈敏，卻存在對(duì)初始值敏感、易陷入局部最優(yōu)的問(wèn)題，為此，模糊聚類(lèi)的全局思想應(yīng)運(yùn)而生。

全局模糊聚類(lèi)算法不再隨機(jī)地為所有簇分別選取初始聚類(lèi)中心，而是從一個(gè)簇的聚類(lèi)問(wèn)題開(kāi)始，在算法每一次迭代過(guò)程中，試圖動(dòng)態(tài)地添加一個(gè)新的聚類(lèi)中心，具體做法是：從次數(shù)q=1開(kāi)始，實(shí)現(xiàn)一個(gè)簇的聚類(lèi)劃分，得到一個(gè)簇的最佳聚類(lèi)中心;在尋找q=2簇劃分結(jié)果時(shí)，默認(rèn)第一個(gè)聚類(lèi)中心為上一次迭代過(guò)程得到的聚類(lèi)中心，并通過(guò)數(shù)據(jù)集中剩余的每一個(gè)樣本作為第二個(gè)聚類(lèi)中心的候選集合，然后用FCM算法對(duì)候選集合中的所有成員進(jìn)行聚類(lèi)，得到各自的聚類(lèi)誤差平方和，最后選擇誤差平方和最小的數(shù)據(jù)點(diǎn)作為第二個(gè)最佳聚類(lèi)中心。在q=2聚類(lèi)結(jié)果的基礎(chǔ)上解決q=3的聚類(lèi)劃分，以此類(lèi)推，得到q=c個(gè)簇的聚類(lèi)問(wèn)題。應(yīng)用全局思想的模糊聚類(lèi)算法不再受初始點(diǎn)影響，有效地避免了陷入局部最優(yōu)解的風(fēng)險(xiǎn)，提高了聚類(lèi)精確度。

2 快速全局中心模糊聚類(lèi)算法

2.1 算法的基本思想

單純的全局模糊聚類(lèi)算法依然沒(méi)有解決c值不確定的問(wèn)題，且在聚類(lèi)的每次劃分過(guò)程中都需要進(jìn)行N（N為數(shù)據(jù)集合中對(duì)象總個(gè)數(shù)）次算法迭代，整個(gè)過(guò)程共需進(jìn)行c×N次，導(dǎo)致算法的運(yùn)行速度較慢，其直接原因是在確定下一聚類(lèi)中心點(diǎn)的過(guò)程中，要將數(shù)據(jù)集合中的每一個(gè)數(shù)據(jù)對(duì)象都作為聚類(lèi)中心候選點(diǎn)進(jìn)行算法迭代測(cè)試。實(shí)際上，數(shù)據(jù)集的各個(gè)聚類(lèi)中心一定會(huì)分布在樣本相對(duì)密集的區(qū)域，數(shù)據(jù)集合中的外圍孤立點(diǎn)、稀疏區(qū)域?qū)ο蠹筒豢赡艹蔀樽罴丫垲?lèi)中心備選點(diǎn)，故算法在選取下一聚類(lèi)中心的過(guò)程中，無(wú)需將集合中所有數(shù)據(jù)對(duì)象都作為初始聚類(lèi)候選中心進(jìn)行測(cè)試運(yùn)算，只要在樣本分布相對(duì)密集的區(qū)域?qū)ふ易罴丫垲?lèi)中心即可，故本文提出了一種確定樣本分布密集度的全局中心的模糊聚類(lèi)算法，基本思想為：

1）計(jì)算密集度，確定初始中心點(diǎn)

通過(guò)計(jì)算數(shù)據(jù)集中所有對(duì)象的密集程度，選擇密集度最大的數(shù)據(jù)成員作為第一個(gè)聚類(lèi)中心，并從質(zhì)心備選集中刪除稀疏區(qū)域樣本點(diǎn)。

2）重新劃分?jǐn)?shù)據(jù)對(duì)象，更新聚類(lèi)中心

對(duì)于當(dāng)前確定的聚類(lèi)中心，將數(shù)據(jù)集中的所有數(shù)據(jù)對(duì)象分配到距離當(dāng)前已有聚類(lèi)中心最近的簇，并更新聚類(lèi)中心。

3）判斷終止條件

前后兩次目標(biāo)函數(shù)差值的絕對(duì)值ΔJ小于等于給定的某個(gè)閾值ε時(shí)，算法停止，返回結(jié)果。

4）選取下一個(gè)聚類(lèi)中心

在質(zhì)心備選集中按照某種自定義優(yōu)化規(guī)則選擇下一個(gè)聚類(lèi)中心，而不是把備選集中所有對(duì)象依次進(jìn)行測(cè)試。

2.3 聚類(lèi)中心的動(dòng)態(tài)選擇

在傳統(tǒng)算法中，采用歐氏距離度量樣本之間的相似性，但歐氏距離的度量方式只對(duì)同尺寸、同密度、同形狀等相同信息且分布均勻的理想化數(shù)據(jù)具有穩(wěn)定性。然而，現(xiàn)實(shí)數(shù)據(jù)往往都具有不同的特征，故歐氏距離度量方式使算法很容易受到外圍孤立點(diǎn)、噪聲點(diǎn)的影響，造成聚類(lèi)結(jié)果的不穩(wěn)定。本文在更新聚類(lèi)中心和隸屬度的過(guò)程中，利用基于非歐氏距離度量方式—AM度量[13][16]的單調(diào)有界性降低外圍點(diǎn)或噪聲點(diǎn)對(duì)確定聚類(lèi)中心過(guò)程的影響，來(lái)增強(qiáng)聚類(lèi)算法的穩(wěn)定性和魯棒性，并減少算法的迭代次數(shù)。

4 結(jié) 語(yǔ)

針對(duì)FCM聚類(lèi)算法對(duì)初始聚類(lèi)中心選取敏感，易受噪聲點(diǎn)影響，以及聚類(lèi)最終結(jié)果容易陷入局部最優(yōu)的問(wèn)題，本文提出了ADGFCM算法，該算法采用全局中心聚類(lèi)思想，結(jié)合DKC值與AM度量，并提出自定義尋優(yōu)函數(shù)fi，全面考慮了所有數(shù)據(jù)對(duì)象點(diǎn)的分布情況，緩解對(duì)噪聲點(diǎn)敏感的問(wèn)題。選取一個(gè)周?chē)鷶?shù)據(jù)對(duì)象分布比較密集，且距離現(xiàn)有聚類(lèi)中心都比較遠(yuǎn)的數(shù)據(jù)對(duì)象點(diǎn)作為下一個(gè)最佳聚類(lèi)中心，不但使聚類(lèi)結(jié)果趨于穩(wěn)定，提高聚類(lèi)精確度，而且減少了算法累加過(guò)程中的計(jì)算負(fù)擔(dān)，加快聚類(lèi)速度，在一定程度上跳出局部最優(yōu)。實(shí)驗(yàn)結(jié)果表明，ADGFCM算法相比FCM算法和其他改進(jìn)后的FCM算法精確度均有所提高，運(yùn)行時(shí)間較短，聚類(lèi)效果較為穩(wěn)定，在實(shí)際數(shù)據(jù)集上有較好的應(yīng)用價(jià)值。

參 考 文 獻(xiàn)：

[1] SANAKAL R， JAYAKUMARI T. Prognosis of Diabetes Using Data Mining Approach-fuzzy C Means Clustering and Support Vector Machine[J]. Int. J. Comput. Trends Technol.（IJCTT）， 2014， 11（2）： 94.

[2] LIU L， SUN S Z， YU H， et al. A Modified Fuzzy C-Means （FCM） Clustering Algorithm and Its Application on Carbonate Fluid Identification[J]. Journal of Applied Geophysics， 2016， 129：28.

[3] 吳明陽(yáng)， 張芮， 岳彩旭，等. 應(yīng)用K-means聚類(lèi)算法劃分曲面及實(shí)驗(yàn)驗(yàn)證[J]. 哈爾濱理工大學(xué)學(xué)報(bào)， 2017（1）：54.

[4] 武俊峰， 艾嶺. 一種基于改進(jìn)聚類(lèi)算法的模糊模型辨識(shí)[J]. 哈爾濱理工大學(xué)學(xué)報(bào)， 2010， 15（3）：1.

[5] NAYAK J， NAIK B， KANUNGO D P， et al. A Hybrid Elicit Teaching Learning Based Optimization with Fuzzy C-means （ETLBO-FCM） Algorithm for Data Clustering[J]. Ain Shams Engineering Journal， 2016（5）：148.

[6] FILHO T M S， PIMENTEL B A， SOUZA R M C R， et al. Hybrid Methods for Fuzzy Clustering Based on Fuzzy C-means and Improved Particle Swarm Optimization[J]. Expert Systems with Applications， 2015， 42（17）：6315.

[7] PAN X， LIU P， REN M， et al. Optimization of fuzzy C-means based on OBL-genetic algorithm[C]//Natural Computation， Fuzzy Systems and Knowledge Discovery （ICNC-FSKD）， 2016 12th International Conference on. IEEE， 2016： 109.

[8] YE A X， JIN Y X. A Fuzzy C-Means Clustering AlgorithmBasedon Improved Quantum Genetic Algorithm[J]. International Journal of Database Theory and Application， 2016， 9（1）： 227.

[9] LIU P，DUAN L， CHI X， et al. An Improved Fuzzy C-means Clustering Algorithm Based on Simulated Annealing[C]//Fuzzy Systems and Knowledge Discovery （FSKD）， 2013 10th International Conference on. IEEE， 2013： 39.

[10]陳加順， 皮德常. 一種非噪聲敏感性的模糊C均值聚類(lèi)算法[J]. 小型微型計(jì)算機(jī)系統(tǒng)， 2014， 35（6）：1427.

[11]WANG W， ZHANG Y， LI Y， et al. The Global Fuzzy C-means Clustering Algorithm[C]//2006 6th World Congress on Intelligent Control and Automation. IEEE， 2006， 1：3604.

[12]任培花， 王麗珍. 不確定域環(huán)境下基于DKC值改進(jìn)的K-means聚類(lèi)算法[J]. 計(jì)算機(jī)科學(xué)， 2013， 40（4）：181.

[13]WU K L， YANG M S. Alternative C-means Clustering Algorithms[J]. Pattern Recognition， 2002， 35（10）：2267.

[14]李遠(yuǎn)成， 陰培培， 趙銀亮. 基于模糊聚類(lèi)的推測(cè)多線(xiàn)程劃分算法[J]. 計(jì)算機(jī)學(xué)報(bào)， 2014， 37（3）：580.

[15]謝娟英， 蔣帥， 王春霞，等. 一種改進(jìn)的全局K-均值聚類(lèi)算法[J]. 陜西師范大學(xué)學(xué)報(bào)：自然科學(xué)版， 2010，38（2）：18.

[16]ZHANG Dao-qiang， Chen. A Comment on “Alternative C-means Clustering Algorithms”[J]. Pattern Recognition， 2004， 37（2）：173.

[17]RASTGARPOUR M， ALIPOUR S， SHANBEHZADEH J. Improved Fast Two Cycle by using KFCM Clustering for Image Segmentation[J]. Lecture Notes in Engineering & Computer Science， 2012， 2195（1）.

[18]AHMAD A，DEY L. A K-mean Clustering Algorithm for Mixed Numeric and Categorical Data[J]. Data & Knowledge Engineering， 2007， 63（2）：503.

[19]BEZDEK J C. A Physical Interpretation of Fuzzy ISODATA[J]. IEEE Transactions on Systems Man & Cybernetics， 1976， 6（5）：615.

[20]VANI H Y，ANUSUYA M A. Isolated Speech Recognition Using Fuzzy C Means Technique[C]// International Conference on Emerging Research in Electronics， Computer Science and Technology. IEEE， 2016：352-357.

（編輯：關(guān) 毅）