FCIVI算法的改進及仿真實驗研究

黃勝　曹宇

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

關鍵詞：模糊C均值聚類算法;拉普拉斯系數;緊湊性;魯棒性

中圖分類號：TP391.9 文獻標識碼：A 文章編號：1006-8228（2020）08-75-04

0 引言

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

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

1 FCM聚類算法的缺陷分析

FCM算法（模糊C均值聚類算法）的基本思想是：在HCM算法的基礎上引入不同類別樣本的隸屬函數矩陣和模糊系數m。與HCM算法相比，該算法在數據分類、聚類點計算、目標函數等方面進行了調整。

（6）輸出聚類結果（V，U）。

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

如圖1所示，這是一個均勻分布的數據集，沒有自然的結構，但是當設置聚類簇個數c=3時，FCM算法將產生圖2中的劃分，不同的數據分區是由不同的初始化產生的。因此，很難對聚類結果做出合理的解釋，也不可能揭示數據中包含的結構信息，幫助用戶產生新的想法或形成新的假設。

2 基于拉普拉斯系數優化目標函數的FCM聚類算法

2.1 基于拉普拉斯系數的優化目標函數

本文利用拉普拉斯系數對標準FCM算法的目標函數進行優化。拉普拉斯系數S=（S ij）用來表示樣本j屬于聚類中心i的加權系數。S ij的定義如下：

當我們把噪聲點作為一個單獨的類型時，它的重量是比其他類別更大，它也會影響整個有效性度量的值，因此更能抵抗噪音。只用來做一些小的調整以達到更好的分割結果。

3 算法仿真實驗

為了驗證本文提出的改進算法的性能，進行了仿真實驗。首先，選取了UCI標準數據集Iris和Wine的數據集，設置模糊加權參數m=2和停止迭代條件8=0.01，經過20次迭代，結果表明該數據集被分為3類。同時將改進的FCM算法與標準FCM算法進行比較，如果聚類簇個數不同，得到的結果也不同。結果見表1。

從表1可以看出，與標準FCM算法相比，改進后的FCM算法更加精確。

然后利用Bupa肝損傷數據集檢驗有效性函數的降噪能力。數據集如圖3所示。

數據集都用有效性函數進行了檢驗，我們使用不同的初始值進行了幾次實驗，都得到了相同的結果。因此，只需列出一個實驗結果，不同數據集的有效性函數的變化如圖4所示。

為了驗證功能的魯棒性，在圖5所示的肝損傷數據集中隨機加入100個噪聲點，變化示意圖如圖6所示。

從圖6可以看出，所提出的有效性函數能夠給出兩個數據集正確的聚類數，實驗結果表明，該函數不受噪聲的影響，具有較強的魯棒性。

4 總結與展望

本文針對FCM聚類算法存在的缺陷，提出了一種基于拉普拉斯系數的目標函數FCM聚類優化算法。

仿真結果表明，改進的FCM算法的聚類效果比標準算法更準確，值得推廣。但是在對目標函數進行優化的同時必定以損失時間為代價，合理的平衡二者之間的關系是未來需要研究的。此外如何在保證算法優化性的同時減少時間的損耗，是未來一段時間可以做的工作。

參考文獻（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

★基金項目：湖南省教育廳科研項目“基于大數據分析的改進模糊C均值聚類算法研究”（No.18C1104）;校級科研項目“基于大數據的改進模糊C均值聚類算法研究”（No.2018809）;湖南涉外經濟學院大學生創新訓練項目“基于學生借閱行為分析的圖書推薦系統”

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