一種基于人工免疫網絡的模糊c均值聚類算法

◆董 雪

?

一種基于人工免疫網絡的模糊c均值聚類算法

◆董 雪

（四川大學計算機學院 四川 610065）

傳統模糊c均值聚類算法（FCM）需要對整個數據集進行復雜地迭代計算，當數據量增大時，算法變得耗時。為減少參與FCM迭代計算的數據量，提出一種基于人工免疫網絡的模糊c均值聚類算法。首先利用人工免疫網絡對原始數據集進行預處理，產生考慮了原始數據密度信息的代表性樣本，然后用樣本數據代替原始數據參與FCM的迭代計算，最后將聚類信息擴展到原始數據集并調整聚類中心。實驗結果顯示，相較于傳統FCM算法，新算法在保持相近聚類準確度的情況下，有效地降低了聚類時間。

模糊c均值聚類算法; 模糊聚類; 人工免疫網絡

0 引言

模糊c均值算法（FCM）是一類代表性的模糊聚類算法，它能夠定量地描述每個數據點對各個聚類中心的隸屬度，相較于硬聚類算法，更好地貼合人類的思維模式。FCM算法通過最小化一個目標函數來得到聚類結果，巧妙地將模糊聚類問題轉化為最優化問題，目前FCM算法及其改進算法已被廣泛應用于圖像分割、模式識別、網絡安全等領域[1-3]。

然而，傳統的FCM算法使用整個數據集參與復雜的迭代運算，當處理大量數據的聚類問題時，變得相對耗時。如果我們能夠找到少量的代表性樣本數據，代替原始數據參與迭代計算獲得近似的聚類結果，將會大幅降低聚類時間。這個問題可以通過一個數據壓縮過程來實現。

人工免疫網絡算法因其在數據壓縮、優化等領域的卓越表現已得到廣泛關注[4-5]。它受生物免疫系統中選擇和記憶機制的啟發，由Jerne率先提出的免疫網絡理論[6]發展而來，隨后一系列人工免疫網絡模型被相繼提出[7-8]。目前，由De Castro提出的aiNet免疫網絡模型[7]被研究和應用得相對較廣，它能通過模擬生物體內抗體學習抗原的過程，對原始數據集進行學習，生成一個精簡的代表性樣本數據集。在aiNet模型的基礎上，Bezzera等人提出了適應性半徑免疫網絡算法（ARIA）[9]。該算法考慮了抗原數據中呈現的密度信息，與aiNet算法相比，ARIA學習到的抗體數據集能夠更好地代表抗原數據集的分布特點。

基于此，本文提出一種基于人工免疫網絡的模糊c均值聚類算法ARAIN-FCM，減少參與FCM迭代計算的數據量。經實驗驗證，在數據量足夠的情況下，該算法能夠在保持傳統FCM算法聚類準確度的情況下，有效地提高FCM算法的聚類時間效率。

1 模糊c均值算法

模糊c均值聚類算法（FCM）[10]定義了一個目標函數，如公式（1）。通過最小化目標函數，獲得聚類結果。

2 ARAIN-FCM算法

本文提出的基于人工免疫網絡的模糊c均值聚類算法ARAIN-FCM基本思想如下：首先，利用基于人工免疫網絡的數據壓縮算法得到數量較少的樣本數據，這些樣本數據能夠很好地代表原始數據在特征空間中的分布情況。然后一個來自標準FCM算法的聚類過程被應用到這些代表性樣本數據上，獲得一組初始聚類中心。接著，通過評估每個原始數據點對于這些初始數據中心的隸屬度，將聚類劃分信息擴展到整個數據集，建立隸屬度矩陣。最后，通過獲得的隸屬度矩陣再次更新聚類中心，如圖1。

圖1 ARAIN-FCM算法示例

從原始數據集獲取代表性樣本集的預處理過程，可以減少后期參與聚類迭代計算的數據量，從而顯著地減少了聚類的時間開銷。與此同時，在學習代表性樣本集的過程中，原始數據中呈現的結構特征和密度信息都被較好地保留，使獲得的樣本數據能夠較好地代表原始數據。所以，通過對樣本數據集進行聚類所獲得的初始聚類中心，在一定程度上反映了真實情況，再加上最后一階段的調整，最終得到較準確的聚類信息。

算法包含如下四個階段，如圖2：

圖2 ARAIN-FCM算法四個階段

表1 Aria(AIN)

2.1獲得代表性樣本集

這一預處理過程可以借助適應性半徑免疫算法（ARIA）[9]來實現。原始數據被視為抗原，樣本數據作為抗體，三個基本步驟重復執行：首先，抗體識別抗原，計算各個抗體與抗原之間的親和力，具有較高親和力的抗體被保留。然后，被保留的抗體經過增殖和變異產生新的后代。最后，抗體之間進行相互抑制作用，刪除冗余抗體。其中，親和力的高低與抗體抗原之間的距離成反比，親和力越高表示兩者越相似。每一個抗體具有位置和壓縮半徑兩個屬性，抗體的壓縮半徑根據抗體周圍抗原的密度適應性地調整，密度越大，半徑越小。在抑制階段，如果兩個抗體之間的距離小于其中一個抗體的壓縮半徑，則具有較大半徑的抗體將被清除。基于此，抗原密度越高的地方，抗體將被較多的保留。表1展示了這個過程。

抗體與抗原間的距離越小，其親和力（相似度）越大，如公式（3）。這里用歐式距公式作為距離評估標準。

抗體的克隆變異同時完成，如公式（4）：

抗體重復地進行增殖、變異和相互抑制的過程。最后，對抗原具有較高親和力（相似度）的記憶抗體被保留下來，保留下來的記憶抗體（代表性樣本集）能夠較好地代表原始數據集在特征空間中的分布。

2.2生成初始聚類中心

保留下來的少量代表性樣本數據將代替原始數據參與FCM算法中的迭代運算，以獲得初始的聚類中心，如表2所示。

表2 Sample-Cluster(FCM)

為了獲得聚類中心，需要最小化公式（1）中的目標函數。

這通過迭代地更新聚類中心和模糊隸屬度矩陣來完成，如公式（5）（6）。當目標函數值的變化小于一個給定閾值的時候，循環終止。

2.3建立原始數據集的隸屬度矩陣

本階段的目標在于將基于樣本數據所得到的聚類信息擴展到原始數據集。通過評估每一個原始數據與由樣本數據所產生的初始聚類中心的相似度，建立隸屬度矩陣。算法如表3。

表3 Membership

2.4更新聚類中心

我們利用2.3中得到的隸屬度矩陣，依照公式（5）更新初始的聚類中心，得到最終的結果。這最后的一步用于獲得更加精準的聚類信息。

3 實驗結果與分析

運行時間(Run-time)和調整蘭德系數(Adjusted rand index)[11]被作為評估算法性能的指標參數。運行時間指兩種算法分別用于聚類時迭代計算所消耗的實際時間。ARAIN-FCM算法后期將數據劃分信息擴展到原始數據集并調整聚類中心，這部分時間沒有納入運行時間的計算，因為與迭代計算相比，該部分的時間開銷很少，可忽略不計。調整蘭德系數（ARI）通過計算聚類結果與真實類別情況的相似度評估聚類質量。ARI值越高表示算法的聚類準確度越高。計算ARI時，我們將數據點硬性地歸為其具有最大隸屬度值的聚類。

五組不同數據量大小的合成數據集被用來測試，分別包含100,500,1000,1500,2000個數據，每組數據按五個高斯分布，高斯分布如下：

ARAIN-FCM算法和標準FCM算法被用來對這些數據聚類，圖3、圖4展示了兩種算法分別對不同大小數據集聚類的運行時間和聚類準確度。

由圖3可見，標準FCM算法和ARAIN-FCM算法（不同抽樣比例）的聚類時間都隨數據量大小的增加而增加。當數據量僅僅只有100時，兩種算法時間開銷的差異并不明顯，這是因為此時FCM算法的聚類時間已經很?。?0.005），很難再被壓縮。除此以外，在數據量大小從500變化到2000時，ARAIN-FCM算法與FCM算法相比，明顯花費更少的聚類時間，當抽樣比例為50%、20%和10%時，聚類時間分別降低為標準FCM算法的52.3%、25%和14.7%。

圖4 Adjusted Rand Index vs data size

由圖4可見，當數據量只有100時，ARAIN-FCM算法較小程度地損失了部分聚類準確度，這是因為當數據量太少時，數據冗余程度低，在數據壓縮過程中被壓縮的數據將帶走更多的有用信息。當數據量達到500及以上時，ARAIN-FCM算法保持了較高的聚類準確度（>0.92）。而且，此時無論ARAIN-FCM算法所抽樣的比例如何，其聚類準確度都與標準FCM算法保持相當水平。

4 結束語

本文提出了一種基于人工免疫網絡的模糊c均值聚類算法ARAIN-FCM，利用人工免疫網絡算法從原始數據集中學習得到更加精簡的樣本數據集來參與聚類，以減少傳統FCM算法中參與復雜迭代計算的數據量，從而提高其聚類時間效率。實驗結果顯示，相較于傳統FCM聚類算法，本文提出的算法有效降低了聚類時間，并能夠保持與其相近的聚類準確度。

[1]周文剛, 孫挺, 朱海.一種基于自適應空間信息改進FCM的圖像分割算法[J].計算機應用研究，2015.

[2]Polat K. Intelligent recognition of diabetes disease via FCM based attribute weighting[J]. World Acad Sci Eng Technol Int J Comput Electr Autom Control Inform Eng，2016.

[3]劉緒崇, 陸紹飛, 趙薇等.基于改進模糊 C 均值聚類算法的云計算入侵檢測方法[J].中南大學學報:自然科學版，2016.

[4]Stibor T, Timmis J. An investigation on the compression quality of aiNet[C]. Foundations of Computational Intelligence, 2007. FOCI 2007. IEEE Symposium on. IEEE，2007.

[5]Dasgupta D, Yu S, Nino F. Recent advances in artificial immune systems: models and applications[J]. Applied Soft Computing，2011.

[6]Jerne N K. Towards a network theory of the immune system[C]//Annales d'immunologie，1974.

[7]de Castro L N, Von Zuben F J. aiNet: an artificial immune network for data analysis[J]. Data mining: a heuristic approach，2001.

[8]Timmis J, Neal M. A resource limited artificial immune system for data analysis[J]. Knowledge-Based Systems，2001.

[9]Bezerra G B, Barra T V, de Castro L N, et al. Adaptive radius immune algorithm for data clustering[M]//Artificial Immune Systems. Springer Berlin Heidelberg，2005.

[10]Bezdek J C, Ehrlich R, Full W. FCM: The fuzzy c-means clustering algorithm[J]. Computers & Geosciences，1984.

[11]Hubert and P.Arabie, “Comparing partitions,” J. Class，1985.

國家重點研發計劃（2016yfb0800604,2016yfb0800605），國家自然科學基金項目（61572334）。