◆董 雪

?

一種基于人工免疫網(wǎng)絡(luò)的模糊c均值聚類算法

◆董 雪

（四川大學(xué)計(jì)算機(jī)學(xué)院 四川 610065）

傳統(tǒng)模糊c均值聚類算法（FCM）需要對(duì)整個(gè)數(shù)據(jù)集進(jìn)行復(fù)雜地迭代計(jì)算，當(dāng)數(shù)據(jù)量增大時(shí)，算法變得耗時(shí)。為減少參與FCM迭代計(jì)算的數(shù)據(jù)量，提出一種基于人工免疫網(wǎng)絡(luò)的模糊c均值聚類算法。首先利用人工免疫網(wǎng)絡(luò)對(duì)原始數(shù)據(jù)集進(jìn)行預(yù)處理，產(chǎn)生考慮了原始數(shù)據(jù)密度信息的代表性樣本，然后用樣本數(shù)據(jù)代替原始數(shù)據(jù)參與FCM的迭代計(jì)算，最后將聚類信息擴(kuò)展到原始數(shù)據(jù)集并調(diào)整聚類中心。實(shí)驗(yàn)結(jié)果顯示，相較于傳統(tǒng)FCM算法，新算法在保持相近聚類準(zhǔn)確度的情況下，有效地降低了聚類時(shí)間。

模糊c均值聚類算法; 模糊聚類; 人工免疫網(wǎng)絡(luò)

0 引言

模糊c均值算法（FCM）是一類代表性的模糊聚類算法，它能夠定量地描述每個(gè)數(shù)據(jù)點(diǎn)對(duì)各個(gè)聚類中心的隸屬度，相較于硬聚類算法，更好地貼合人類的思維模式。FCM算法通過(guò)最小化一個(gè)目標(biāo)函數(shù)來(lái)得到聚類結(jié)果，巧妙地將模糊聚類問(wèn)題轉(zhuǎn)化為最優(yōu)化問(wèn)題，目前FCM算法及其改進(jìn)算法已被廣泛應(yīng)用于圖像分割、模式識(shí)別、網(wǎng)絡(luò)安全等領(lǐng)域[1-3]。

然而，傳統(tǒng)的FCM算法使用整個(gè)數(shù)據(jù)集參與復(fù)雜的迭代運(yùn)算，當(dāng)處理大量數(shù)據(jù)的聚類問(wèn)題時(shí)，變得相對(duì)耗時(shí)。如果我們能夠找到少量的代表性樣本數(shù)據(jù)，代替原始數(shù)據(jù)參與迭代計(jì)算獲得近似的聚類結(jié)果，將會(huì)大幅降低聚類時(shí)間。這個(gè)問(wèn)題可以通過(guò)一個(gè)數(shù)據(jù)壓縮過(guò)程來(lái)實(shí)現(xiàn)。

人工免疫網(wǎng)絡(luò)算法因其在數(shù)據(jù)壓縮、優(yōu)化等領(lǐng)域的卓越表現(xiàn)已得到廣泛關(guān)注[4-5]。它受生物免疫系統(tǒng)中選擇和記憶機(jī)制的啟發(fā)，由Jerne率先提出的免疫網(wǎng)絡(luò)理論[6]發(fā)展而來(lái)，隨后一系列人工免疫網(wǎng)絡(luò)模型被相繼提出[7-8]。目前，由De Castro提出的aiNet免疫網(wǎng)絡(luò)模型[7]被研究和應(yīng)用得相對(duì)較廣，它能通過(guò)模擬生物體內(nèi)抗體學(xué)習(xí)抗原的過(guò)程，對(duì)原始數(shù)據(jù)集進(jìn)行學(xué)習(xí)，生成一個(gè)精簡(jiǎn)的代表性樣本數(shù)據(jù)集。在aiNet模型的基礎(chǔ)上，Bezzera等人提出了適應(yīng)性半徑免疫網(wǎng)絡(luò)算法（ARIA）[9]。該算法考慮了抗原數(shù)據(jù)中呈現(xiàn)的密度信息，與aiNet算法相比，ARIA學(xué)習(xí)到的抗體數(shù)據(jù)集能夠更好地代表抗原數(shù)據(jù)集的分布特點(diǎn)。

基于此，本文提出一種基于人工免疫網(wǎng)絡(luò)的模糊c均值聚類算法ARAIN-FCM，減少參與FCM迭代計(jì)算的數(shù)據(jù)量。經(jīng)實(shí)驗(yàn)驗(yàn)證，在數(shù)據(jù)量足夠的情況下，該算法能夠在保持傳統(tǒng)FCM算法聚類準(zhǔn)確度的情況下，有效地提高FCM算法的聚類時(shí)間效率。

1 模糊c均值算法

模糊c均值聚類算法（FCM）[10]定義了一個(gè)目標(biāo)函數(shù)，如公式（1）。通過(guò)最小化目標(biāo)函數(shù)，獲得聚類結(jié)果。

2 ARAIN-FCM算法

本文提出的基于人工免疫網(wǎng)絡(luò)的模糊c均值聚類算法ARAIN-FCM基本思想如下：首先，利用基于人工免疫網(wǎng)絡(luò)的數(shù)據(jù)壓縮算法得到數(shù)量較少的樣本數(shù)據(jù)，這些樣本數(shù)據(jù)能夠很好地代表原始數(shù)據(jù)在特征空間中的分布情況。然后一個(gè)來(lái)自標(biāo)準(zhǔn)FCM算法的聚類過(guò)程被應(yīng)用到這些代表性樣本數(shù)據(jù)上，獲得一組初始聚類中心。接著，通過(guò)評(píng)估每個(gè)原始數(shù)據(jù)點(diǎn)對(duì)于這些初始數(shù)據(jù)中心的隸屬度，將聚類劃分信息擴(kuò)展到整個(gè)數(shù)據(jù)集，建立隸屬度矩陣。最后，通過(guò)獲得的隸屬度矩陣再次更新聚類中心，如圖1。

圖1 ARAIN-FCM算法示例

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

算法包含如下四個(gè)階段，如圖2：

圖2 ARAIN-FCM算法四個(gè)階段

表1 Aria(AIN)

2.1獲得代表性樣本集

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

抗體與抗原間的距離越小，其親和力（相似度）越大，如公式（3）。這里用歐式距公式作為距離評(píng)估標(biāo)準(zhǔn)。

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

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

2.2生成初始聚類中心

保留下來(lái)的少量代表性樣本數(shù)據(jù)將代替原始數(shù)據(jù)參與FCM算法中的迭代運(yùn)算，以獲得初始的聚類中心，如表2所示。

表2 Sample-Cluster(FCM)

為了獲得聚類中心，需要最小化公式（1）中的目標(biāo)函數(shù)。

這通過(guò)迭代地更新聚類中心和模糊隸屬度矩陣來(lái)完成，如公式（5）（6）。當(dāng)目標(biāo)函數(shù)值的變化小于一個(gè)給定閾值的時(shí)候，循環(huán)終止。

2.3建立原始數(shù)據(jù)集的隸屬度矩陣

本階段的目標(biāo)在于將基于樣本數(shù)據(jù)所得到的聚類信息擴(kuò)展到原始數(shù)據(jù)集。通過(guò)評(píng)估每一個(gè)原始數(shù)據(jù)與由樣本數(shù)據(jù)所產(chǎn)生的初始聚類中心的相似度，建立隸屬度矩陣。算法如表3。

表3 Membership

2.4更新聚類中心

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

3 實(shí)驗(yàn)結(jié)果與分析

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

五組不同數(shù)據(jù)量大小的合成數(shù)據(jù)集被用來(lái)測(cè)試，分別包含100,500,1000,1500,2000個(gè)數(shù)據(jù)，每組數(shù)據(jù)按五個(gè)高斯分布，高斯分布如下：

ARAIN-FCM算法和標(biāo)準(zhǔn)FCM算法被用來(lái)對(duì)這些數(shù)據(jù)聚類，圖3、圖4展示了兩種算法分別對(duì)不同大小數(shù)據(jù)集聚類的運(yùn)行時(shí)間和聚類準(zhǔn)確度。

由圖3可見，標(biāo)準(zhǔn)FCM算法和ARAIN-FCM算法（不同抽樣比例）的聚類時(shí)間都隨數(shù)據(jù)量大小的增加而增加。當(dāng)數(shù)據(jù)量?jī)H僅只有100時(shí)，兩種算法時(shí)間開銷的差異并不明顯，這是因?yàn)榇藭r(shí)FCM算法的聚類時(shí)間已經(jīng)很?。?0.005），很難再被壓縮。除此以外，在數(shù)據(jù)量大小從500變化到2000時(shí)，ARAIN-FCM算法與FCM算法相比，明顯花費(fèi)更少的聚類時(shí)間，當(dāng)抽樣比例為50%、20%和10%時(shí)，聚類時(shí)間分別降低為標(biāo)準(zhǔn)FCM算法的52.3%、25%和14.7%。

圖4 Adjusted Rand Index vs data size

由圖4可見，當(dāng)數(shù)據(jù)量只有100時(shí)，ARAIN-FCM算法較小程度地?fù)p失了部分聚類準(zhǔn)確度，這是因?yàn)楫?dāng)數(shù)據(jù)量太少時(shí)，數(shù)據(jù)冗余程度低，在數(shù)據(jù)壓縮過(guò)程中被壓縮的數(shù)據(jù)將帶走更多的有用信息。當(dāng)數(shù)據(jù)量達(dá)到500及以上時(shí)，ARAIN-FCM算法保持了較高的聚類準(zhǔn)確度（>0.92）。而且，此時(shí)無(wú)論ARAIN-FCM算法所抽樣的比例如何，其聚類準(zhǔn)確度都與標(biāo)準(zhǔn)FCM算法保持相當(dāng)水平。

4 結(jié)束語(yǔ)

本文提出了一種基于人工免疫網(wǎng)絡(luò)的模糊c均值聚類算法ARAIN-FCM，利用人工免疫網(wǎng)絡(luò)算法從原始數(shù)據(jù)集中學(xué)習(xí)得到更加精簡(jiǎn)的樣本數(shù)據(jù)集來(lái)參與聚類，以減少傳統(tǒng)FCM算法中參與復(fù)雜迭代計(jì)算的數(shù)據(jù)量，從而提高其聚類時(shí)間效率。實(shí)驗(yàn)結(jié)果顯示，相較于傳統(tǒng)FCM聚類算法，本文提出的算法有效降低了聚類時(shí)間，并能夠保持與其相近的聚類準(zhǔn)確度。

[1]周文剛, 孫挺, 朱海.一種基于自適應(yīng)空間信息改進(jìn)FCM的圖像分割算法[J].計(jì)算機(jī)應(yīng)用研究，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]劉緒崇, 陸紹飛, 趙薇等.基于改進(jìn)模糊 C 均值聚類算法的云計(jì)算入侵檢測(cè)方法[J].中南大學(xué)學(xué)報(bào):自然科學(xué)版，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.

國(guó)家重點(diǎn)研發(fā)計(jì)劃（2016yfb0800604,2016yfb0800605），國(guó)家自然科學(xué)基金項(xiàng)目（61572334）。