FCIVI算法的改進(jìn)及仿真實(shí)驗(yàn)研究

黃勝　曹宇

摘要：模糊C均值（FCM）聚類算法可以用來建立樣本對(duì)類別的不確定性描述。文章提出一種基于拉普拉斯系數(shù)優(yōu)化目標(biāo)函數(shù)的FCM聚類算法。在目標(biāo)函數(shù)中引入拉普拉斯系數(shù)，給對(duì)象之間的結(jié)構(gòu)信息賦予權(quán)重，從而提高算法的質(zhì)量和效率。通過緊湊性來優(yōu)化聚類的有效性，并利用最大有效性的方法來提高改進(jìn)算法的抗噪性能。仿真實(shí)驗(yàn)表明，改進(jìn)的FCM算法與標(biāo)準(zhǔn)算法相比具有更準(zhǔn)確的聚類效果，且受噪聲影響小，魯棒性強(qiáng)。

關(guān)鍵詞：模糊C均值聚類算法;拉普拉斯系數(shù);緊湊性;魯棒性

中圖分類號(hào)：TP391.9 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1006-8228（2020）08-75-04

0 引言

聚類技術(shù)是一種對(duì)有限類型的集合或聚類集合進(jìn)行搜索、識(shí)別、描述的數(shù)據(jù)挖掘技術(shù)。聚類分析是數(shù)據(jù)挖掘的一個(gè)重要功能，它可以獲得數(shù)據(jù)的分布情況，從而觀察到每個(gè)簇的特征，并對(duì)某些特定的簇進(jìn)行集中分析。此外，聚類分析可以作為其他算法的預(yù)處理步驟（特征提取和分類等），大大提高了這些算法的精確度和挖掘效率。因此，聚類分析已經(jīng)成為數(shù)據(jù)挖掘中一個(gè)非常活躍的研究領(lǐng)域。許多有效的聚類算法已經(jīng)被開發(fā)出來，新的算法也在不斷涌現(xiàn)。

為了提高聚類算法的性能和效果，有學(xué)者提出將其他領(lǐng)域的方法與聚類算法相結(jié)合，彌補(bǔ)聚類算法在數(shù)據(jù)挖掘領(lǐng)域的一些缺陷，充分發(fā)揮聚類算法的最優(yōu)性能。常用的方法有：遺傳算法、免疫算法、蟻群算法等。戴文華使用一種新型的可變長度染色體編碼方案，通過選擇隨機(jī)采樣點(diǎn)作為初始簇中心形成染色體，有效的避免了局部最優(yōu)解，通過種群內(nèi)遺傳變異和并行化得到最優(yōu)聚類數(shù)和聚類結(jié)果，種群間的“聯(lián)姻”結(jié)合了k-means算法的高效率和并行遺傳算法的全局尋優(yōu)能力[1]。近年來興起的人工免疫系統(tǒng)研究是一個(gè)新的應(yīng)用領(lǐng)域。隨著免疫算法的發(fā)展，為聚類分析領(lǐng)域帶來了新的活力。陳曦等成功地將免疫算法應(yīng)用于聚類分析[2]。在模糊聚類算法的研究中，Ruspini首先提出了基于目標(biāo)函數(shù)的模糊聚類算法[3]，而真正有效的模糊聚類算法FCM（fuzzy C-Means）是Dunn提出的[4]。FCM算法簡單、高效，在應(yīng)用領(lǐng)域得到了廣泛應(yīng)用。FCM算法的缺點(diǎn)也很明顯，針對(duì)FCM算法對(duì)初始化敏感、容易陷入局部極值點(diǎn)等缺點(diǎn)，李莉莉提出了一種基于模擬退火粒子群的模糊聚類優(yōu)化算法[5]。該算法利用粒子群強(qiáng)大的全局尋優(yōu)能力和模擬退火算法跳出局部極值的能力，克服了模糊c均值聚類算法的缺點(diǎn)。針對(duì)FCM算法容易陷入局部最優(yōu)的問題，人們將進(jìn)化計(jì)算的思想引入到FCM中，以達(dá)到全局優(yōu)化的目的。現(xiàn)有算法主要有粒子群優(yōu)化算法、基于模擬退火算法、遺傳算法、進(jìn)化策略算法等[6].

1 FCM聚類算法的缺陷分析

FCM算法（模糊C均值聚類算法）的基本思想是：在HCM算法的基礎(chǔ)上引入不同類別樣本的隸屬函數(shù)矩陣和模糊系數(shù)m。與HCM算法相比，該算法在數(shù)據(jù)分類、聚類點(diǎn)計(jì)算、目標(biāo)函數(shù)等方面進(jìn)行了調(diào)整。

（6）輸出聚類結(jié)果（V，U）。

FCM類型的聚類算法是一種基于劃分的方法，正如劃分方法本身存在缺點(diǎn)，它是依靠聚類簇個(gè)數(shù)c來對(duì)數(shù)據(jù)集進(jìn)行劃分，而不考慮數(shù)據(jù)的自然結(jié)構(gòu)和特征空間。因此，該算法有一個(gè)不合理的假設(shè)：待分析的數(shù)據(jù)是可以被聚類的。這種不合理的假設(shè)導(dǎo)致了現(xiàn)有的FCM類型的聚類算法沒有分析數(shù)據(jù)集的聚類可能性，而是難以應(yīng)用一定的數(shù)據(jù)隸屬度。這將導(dǎo)致一些數(shù)據(jù)在特征空間中均勻分布，沒有任何聚類結(jié)構(gòu)，對(duì)這類不適合應(yīng)用于FCM類型算法的數(shù)據(jù)集進(jìn)行了模糊劃分，從而得到難以解釋的聚類分析的結(jié)果。

如圖1所示，這是一個(gè)均勻分布的數(shù)據(jù)集，沒有自然的結(jié)構(gòu)，但是當(dāng)設(shè)置聚類簇個(gè)數(shù)c=3時(shí)，F(xiàn)CM算法將產(chǎn)生圖2中的劃分，不同的數(shù)據(jù)分區(qū)是由不同的初始化產(chǎn)生的。因此，很難對(duì)聚類結(jié)果做出合理的解釋，也不可能揭示數(shù)據(jù)中包含的結(jié)構(gòu)信息，幫助用戶產(chǎn)生新的想法或形成新的假設(shè)。

2 基于拉普拉斯系數(shù)優(yōu)化目標(biāo)函數(shù)的FCM聚類算法

2.1 基于拉普拉斯系數(shù)的優(yōu)化目標(biāo)函數(shù)

本文利用拉普拉斯系數(shù)對(duì)標(biāo)準(zhǔn)FCM算法的目標(biāo)函數(shù)進(jìn)行優(yōu)化。拉普拉斯系數(shù)S=（S ij）用來表示樣本j屬于聚類中心i的加權(quán)系數(shù)。S ij的定義如下：

當(dāng)我們把噪聲點(diǎn)作為一個(gè)單獨(dú)的類型時(shí)，它的重量是比其他類別更大，它也會(huì)影響整個(gè)有效性度量的值，因此更能抵抗噪音。只用來做一些小的調(diào)整以達(dá)到更好的分割結(jié)果。

3 算法仿真實(shí)驗(yàn)

為了驗(yàn)證本文提出的改進(jìn)算法的性能，進(jìn)行了仿真實(shí)驗(yàn)。首先，選取了UCI標(biāo)準(zhǔn)數(shù)據(jù)集Iris和Wine的數(shù)據(jù)集，設(shè)置模糊加權(quán)參數(shù)m=2和停止迭代條件8=0.01，經(jīng)過20次迭代，結(jié)果表明該數(shù)據(jù)集被分為3類。同時(shí)將改進(jìn)的FCM算法與標(biāo)準(zhǔn)FCM算法進(jìn)行比較，如果聚類簇個(gè)數(shù)不同，得到的結(jié)果也不同。結(jié)果見表1。

從表1可以看出，與標(biāo)準(zhǔn)FCM算法相比，改進(jìn)后的FCM算法更加精確。

然后利用Bupa肝損傷數(shù)據(jù)集檢驗(yàn)有效性函數(shù)的降噪能力。數(shù)據(jù)集如圖3所示。

數(shù)據(jù)集都用有效性函數(shù)進(jìn)行了檢驗(yàn)，我們使用不同的初始值進(jìn)行了幾次實(shí)驗(yàn)，都得到了相同的結(jié)果。因此，只需列出一個(gè)實(shí)驗(yàn)結(jié)果，不同數(shù)據(jù)集的有效性函數(shù)的變化如圖4所示。

為了驗(yàn)證功能的魯棒性，在圖5所示的肝損傷數(shù)據(jù)集中隨機(jī)加入100個(gè)噪聲點(diǎn)，變化示意圖如圖6所示。

從圖6可以看出，所提出的有效性函數(shù)能夠給出兩個(gè)數(shù)據(jù)集正確的聚類數(shù)，實(shí)驗(yàn)結(jié)果表明，該函數(shù)不受噪聲的影響，具有較強(qiáng)的魯棒性。

4 總結(jié)與展望

本文針對(duì)FCM聚類算法存在的缺陷，提出了一種基于拉普拉斯系數(shù)的目標(biāo)函數(shù)FCM聚類優(yōu)化算法。

仿真結(jié)果表明，改進(jìn)的FCM算法的聚類效果比標(biāo)準(zhǔn)算法更準(zhǔn)確，值得推廣。但是在對(duì)目標(biāo)函數(shù)進(jìn)行優(yōu)化的同時(shí)必定以損失時(shí)間為代價(jià)，合理的平衡二者之間的關(guān)系是未來需要研究的。此外如何在保證算法優(yōu)化性的同時(shí)減少時(shí)間的損耗，是未來一段時(shí)間可以做的工作。

參考文獻(xiàn)（References）：

[1]Dai Wenhua， Jiao Cuizhen， He Tingting. Research on K-means Cluster Based on Parallel Genetic Algorithm[J].Computer Science，2012.35（6）：171-174

[2]Chen Xi， Xu Jianing， Yang Jianxiong. Research on K-

means File Clustering Algorithm Based on ImmuneNehAiork[J].Computer Engineering and Design，2011.10：2629-2631

[3]Dunn J C.Well-separated Clusters and the Optimal FuzzyPartitions[J].J. Cybernet，1974.4（1）：95-104

[4]Ruspini E H.A New Approach to Clustering[J]， Information& Contr01，2009.15：22-32

[5]Li lili， Liu Xiyu， Liu Tao， Sun Xiujuan.A FCM clusteringalgorithm based on particle swarm optimization[J].Information technology and informationization， 2012.1：89-92

[6| Huang，S. Optimization of Big Data Fusion Scheduling inMaritime Communication Based on Fuzzy C-meansClustering Algorithm. CCAMLR SCIENCE， 2018.25（3）：229-236

★基金項(xiàng)目：湖南省教育廳科研項(xiàng)目“基于大數(shù)據(jù)分析的改進(jìn)模糊C均值聚類算法研究”（No.18C1104）;校級(jí)科研項(xiàng)目“基于大數(shù)據(jù)的改進(jìn)模糊C均值聚類算法研究”（No.2018809）;湖南涉外經(jīng)濟(jì)學(xué)院大學(xué)生創(chuàng)新訓(xùn)練項(xiàng)目“基于學(xué)生借閱行為分析的圖書推薦系統(tǒng)”

作者簡介：黃勝（1980-），男，湖南長沙人，碩士，高級(jí)工程師，主要研究方向：大數(shù)據(jù)，算法研究。