基于相似度的蟻群聚類算法?

沈興鑫 楊余旺 肖高權(quán) 徐益民 陳響洲

（1.南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 南京 210094）

（2.湖南云箭集團(tuán)有限公司 懷化 419500）

1 引言

聚類［1］（Clustering）是一種重要的數(shù)據(jù)挖掘分析方法，主要目標(biāo)是在海量數(shù)據(jù)中找出相似的數(shù)據(jù)并按照相似度分為不同的類，從而使得一個(gè)集群內(nèi)的數(shù)據(jù)項(xiàng)彼此相似，不同集合中的數(shù)據(jù)盡量不同。從生物學(xué)到社會(huì)學(xué)再到計(jì)算機(jī)科學(xué)等眾多領(lǐng)域都存在相同的需求，因此聚類算法得到了廣泛的應(yīng)用。

蟻群聚類（Ant Colony Clustering）是一種受蟻群?jiǎn)l(fā)的聚類算法。意大利學(xué)者Dorigo M［2］在模仿螞蟻群體行為的基礎(chǔ)上提出了蟻群算法，根據(jù)蟻群的信息素機(jī)制尋找蟻穴和食物間的最短路徑，并有效地解決TSP問(wèn)題。Deneubourg J［3］基于人工蟻群模型結(jié)合螞蟻的堆尸行為提出了聚類算法（Basic ant colony clustering model，BM）。Lumer E D和Fa?ieta B［4］在BM模型的基礎(chǔ)上改變螞蟻移動(dòng)速度提出了LF模型，很好地解決了大數(shù)據(jù)量時(shí)的聚類問(wèn)題。

相比于其他的聚類算法，蟻群聚類有以下幾個(gè)優(yōu)點(diǎn)，如靈活性、魯棒性、分布性和自組織性。因此該算法被更多的人研究并改進(jìn)。Bin W和Zhong?zhi S［5］研究了相似系數(shù)，并提出了一種更簡(jiǎn)單的概率轉(zhuǎn)換函數(shù)。王慧和甘泉［6］加入了參數(shù)自適應(yīng)調(diào)整策略，提高了蟻群聚類的準(zhǔn)確性。喬少杰［7］研究了蟻群的分布式模型在文本聚類中的應(yīng)用。Tan S C等［8］提出了一種簡(jiǎn)化的基于螞蟻的聚類方法，該方法基于現(xiàn)有的基于螞蟻的聚類系統(tǒng)的研究。林金灼［9］結(jié)合了主成分分析方法（Principal Compo?nent Analysis，PCA），提高了蟻群的聚類質(zhì)量。Tao等［10］重新定義了兩個(gè)數(shù)據(jù)對(duì)象之間的距離，并改進(jìn)了螞蟻丟棄和拾取數(shù)據(jù)對(duì)象的策略，從而提出了一種改進(jìn)的蟻群聚類算法。Xu X等［11］提出了一種約束螞蟻聚類算法，該算法嵌入了基于隨機(jī)游走的啟發(fā)式步行機(jī)制，以解決約束聚類問(wèn)題。張夢(mèng)佳［12］采用實(shí)時(shí)信息素更新規(guī)則，提高了蟻群聚類的收斂速度，同時(shí)提高了準(zhǔn)確度。周峰［13］提出一種結(jié)合蟻群聚類和模糊均值聚類思想的聚類算法算法，該算法具有全局優(yōu)化能力，優(yōu)化了蟻群聚類易陷入局部最優(yōu)的缺點(diǎn)。趙寶江［14］利用蟻群聚類算法來(lái)進(jìn)行結(jié)構(gòu)辨識(shí)，確定系統(tǒng)的模糊空間和模糊規(guī)則數(shù)，實(shí)現(xiàn)非線性系統(tǒng)的辨識(shí)，辨識(shí)精度高，可當(dāng)作復(fù)雜系統(tǒng)建模的一種有效手段。

雖然以上方法優(yōu)化了蟻群聚類算法，但是蟻群聚類前期收斂速度慢的問(wèn)題未有效的解決。由于螞蟻隨機(jī)移動(dòng)數(shù)據(jù)項(xiàng)的位置存在多次無(wú)效的移動(dòng)，導(dǎo)致算法計(jì)算效率和準(zhǔn)確性較低，對(duì)于復(fù)雜的工程，該問(wèn)題更為突出。為克服這些缺點(diǎn)，本文提出了一種新的蟻群聚類算法，通過(guò)添加相似度矩陣將原算法中螞蟻隨機(jī)移動(dòng)修改成按照相似度矩陣有目的地移動(dòng)，螞蟻隨機(jī)關(guān)聯(lián)修改成有目的地關(guān)聯(lián)。通過(guò)實(shí)際數(shù)據(jù)集驗(yàn)證了新算法的性能，并與先前研究中提出的蟻群聚類算法和其他算法進(jìn)行了比較，驗(yàn)證了新算法的有效性。

2 蟻群聚類算法

蟻群聚類算法是一種群體智能方法，受到蟻群堆積尸體和排序幼蟲行為的啟發(fā)而形成的一種聚類方法。因其靈活性、魯棒性、分散性和自組織性等特點(diǎn)被廣泛研究。

2.1 LF算法基本原理

在LF模型中，將螞蟻的尸體建模為需要聚類的數(shù)據(jù)項(xiàng)，螞蟻建模為在環(huán)境中隨機(jī)移動(dòng)的代理，螞蟻移動(dòng)的平面建模為一個(gè)具有邊界條件的二維網(wǎng)格。分散在平面中的數(shù)據(jù)項(xiàng)通過(guò)代理拾取、搬運(yùn)和放下從而將相似的數(shù)據(jù)項(xiàng)放在一起。數(shù)據(jù)項(xiàng)的取放概率受到該數(shù)據(jù)項(xiàng)與鄰域內(nèi)其他數(shù)據(jù)項(xiàng)的相似性和密度的影響，在拾取時(shí)，相似度越低越有可能拾取，相反，在放下時(shí)，相似度越高越可能放下。因此在網(wǎng)格上對(duì)數(shù)據(jù)項(xiàng)進(jìn)行排列，使得相似度越高的數(shù)據(jù)項(xiàng)在平面上越靠近。

2.2 蟻群聚類算法模型

首先，將N個(gè)數(shù)據(jù)項(xiàng)隨機(jī)地映射到一個(gè)M×M的二維平面中，并將E只螞蟻分散到數(shù)據(jù)平面中并為每只螞蟻ei關(guān)聯(lián)一個(gè)數(shù)據(jù)項(xiàng)，即形成螞蟻到數(shù)據(jù)項(xiàng)映射：

其中E是螞蟻集合，N是數(shù)據(jù)項(xiàng)集合，F(xiàn)是螞蟻到數(shù)據(jù)項(xiàng)的隨機(jī)映射函數(shù)。

再計(jì)算出當(dāng)前數(shù)據(jù)項(xiàng)與鄰域內(nèi)其他數(shù)據(jù)項(xiàng)的相似度f(wàn)(ei)，相似度計(jì)算式（2）所示。

其中α是自定義的參數(shù)，用來(lái)調(diào)節(jié)螞蟻間的相似度。V定義了螞蟻的移動(dòng)速度，vmax代表了最大速度，V隨機(jī)分布在[1 ，vmax]中。s是自定義的螞蟻的搜索長(zhǎng)度。Neighs×s(r)代表位置r的周圍s×s面積。d( ei，ej)是ei和ej之間的距離。d( ei，ej)采用歐式距離，公式如下：

其中m是數(shù)據(jù)項(xiàng)的維度。

當(dāng)螞蟻處于空載狀態(tài)需要拾起數(shù)據(jù)項(xiàng)時(shí)，按照如下公式計(jì)算拾起概率pp：

其中f(ei)是ei的相似函數(shù)，tanh(x)函數(shù)的定義如式（4）所示。

其中c為自定義的常量，用來(lái)調(diào)節(jié)算法匯聚的速度。

當(dāng)螞蟻處于負(fù)載狀態(tài)需要放下數(shù)據(jù)項(xiàng)時(shí)，按照如下公式計(jì)算放下概率pd：

tanh函數(shù)和pp概率曲線圖如圖1所示。

在本模型中，螞蟻在拾起或者放下數(shù)據(jù)項(xiàng)后隨機(jī)移動(dòng)，數(shù)據(jù)項(xiàng)與領(lǐng)域內(nèi)的數(shù)據(jù)項(xiàng)相似度可能不高，因此下次被移動(dòng)的概率又會(huì)增加，從而降低了聚類的速率。同時(shí)，當(dāng)負(fù)載的螞蟻放下數(shù)據(jù)項(xiàng)或者空載的螞蟻沒(méi)有拾起數(shù)據(jù)項(xiàng)而需要重新關(guān)聯(lián)數(shù)據(jù)項(xiàng)時(shí)，數(shù)據(jù)項(xiàng)的關(guān)聯(lián)也是隨機(jī)的，增大了再次關(guān)聯(lián)的概率，導(dǎo)致聚類速率降低。

圖1 tanh函數(shù)圖和pp概率曲線圖

針對(duì)以上兩個(gè)缺點(diǎn)，本文在原有算法基礎(chǔ)上設(shè)計(jì)了相似度矩陣，讓螞蟻按照相似度有目的地移動(dòng)，同時(shí)在螞蟻需要映射數(shù)據(jù)項(xiàng)時(shí)，根據(jù)相似度矩陣有選擇的映射，從而加快聚類的速度。

3 改進(jìn)的蟻群聚類算法

傳統(tǒng)的蟻群算法移動(dòng)蟻卵或者關(guān)聯(lián)蟻卵時(shí)都是隨機(jī)，存在無(wú)效移動(dòng)與映射，導(dǎo)致聚類效率降低。改進(jìn)的蟻群聚類算法在原有算法基礎(chǔ)上設(shè)計(jì)了相似度矩陣，螞蟻按照相似度有目標(biāo)地移動(dòng)，同時(shí)有選擇地映射到數(shù)據(jù)項(xiàng)，從而加快聚類速度。

3.1 算法原理

蟻群聚類通過(guò)螞蟻移動(dòng)數(shù)據(jù)項(xiàng)，使相似度高的數(shù)據(jù)項(xiàng)在平面上盡可能靠近，從而形成聚類簇。在此過(guò)程中，將數(shù)據(jù)項(xiàng)移動(dòng)到相似度高的區(qū)域附近可以大幅提高聚類速度。螞蟻因放下或者未能拾起數(shù)據(jù)項(xiàng)時(shí)需要重新關(guān)聯(lián)數(shù)據(jù)項(xiàng)。此時(shí)，當(dāng)前數(shù)據(jù)項(xiàng)和鄰域的相似度較高，需要移動(dòng)的概率較低，因此，關(guān)聯(lián)相似度低的數(shù)據(jù)項(xiàng)，增加操作次數(shù)可以提高聚類效率。

3.2 算法實(shí)現(xiàn)過(guò)程

3.2.1 建立相似度序列矩陣

首先計(jì)算每個(gè)數(shù)據(jù)項(xiàng)和其他數(shù)據(jù)項(xiàng)之間的距離。由于余弦相似度計(jì)算簡(jiǎn)單、直接，對(duì)于單獨(dú)判斷兩個(gè)數(shù)據(jù)對(duì)象的相似度準(zhǔn)確率高，因此本算法采用余弦相似度來(lái)計(jì)算數(shù)據(jù)項(xiàng)間的距離，其定義如下：

其中ei、ej表示兩個(gè)不同的數(shù)據(jù)項(xiàng)，eik、ejk表示不同數(shù)據(jù)項(xiàng)所代表的矢量坐標(biāo)值，n表示數(shù)據(jù)項(xiàng)的維度。

然后對(duì)余弦距離標(biāo)準(zhǔn)化，形成相似矩陣（Simi?larity Matrix）。該矩陣是一個(gè)N×N的對(duì)稱矩陣，表示N個(gè)數(shù)據(jù)項(xiàng)兩兩之間的相似度，形如：

其中，dij是數(shù)據(jù)項(xiàng)i和對(duì)象j之間余弦距離的標(biāo)準(zhǔn)化表示。當(dāng)數(shù)據(jù)項(xiàng)i和數(shù)據(jù)項(xiàng)j越相似，其值越接近0；相反，兩個(gè)數(shù)據(jù)項(xiàng)越不同，其值越接近1。

再以相似矩陣為基礎(chǔ)，以列為單位，按照相似度從高到地的順序進(jìn)行排序，形成相似度序列矩陣，形如以下公式：

其中函數(shù)f(x)是以矩陣x為參數(shù)的快速排序函數(shù)，sij表示與第i個(gè)數(shù)據(jù)項(xiàng)相似度排序第j個(gè)的數(shù)據(jù)項(xiàng)的序號(hào)，sij∈(1…n)。數(shù)據(jù)項(xiàng)與該數(shù)據(jù)項(xiàng)的 相 似 度 最 高 ，因 此 [s11s12…sn1]=[1 2…n]。

3.2.2 提高螞蟻的移動(dòng)目的性

在螞蟻移動(dòng)數(shù)據(jù)項(xiàng)時(shí)，首先根據(jù)以下公式確定當(dāng)前數(shù)據(jù)項(xiàng)的鄰域。

其中anti表示第i只螞蟻，位于( xi，yi)，Sx和Sy分別代表該螞蟻水平方向和豎直方向的視野。數(shù)據(jù)項(xiàng)領(lǐng)域如圖2所示。

圖2 數(shù)據(jù)項(xiàng)領(lǐng)域范圍

然后確定鄰域中的數(shù)據(jù)項(xiàng)，即ej∈N( anti)，再按照相似度序列矩陣找出鄰域中相似度最高的數(shù)據(jù)項(xiàng)，將當(dāng)前數(shù)據(jù)項(xiàng)移動(dòng)到該數(shù)據(jù)項(xiàng)附近。

Algorithm1：Similar Move

1）Input：Index of current spawn

2）Ouput：Index of most similar spawn

3）Calculate Neighbor Area（N(oi)）

4）Get column i of Indexmatix

5）For j=1；j

6）k←Indexmatix[i][j]

7）If ok?N(oi)

8） Move oinearby ok

9） Return k

10） Else

11） Continue

12） End if

13）End for

14）Return Spawn number-1

3.2.3 增加關(guān)聯(lián)的目的性

按照相似度序列矩陣找到和當(dāng)前數(shù)據(jù)項(xiàng)最不相似的數(shù)據(jù)項(xiàng)并映射到該螞蟻，偽代碼如下：

Algorithm2：Dissimilar Mapping

1）Input：Index of current ant i

2）Output：Index of most dissimilar spawn k

3）Get column i of Indexmatix

4）For j=Spawn number-1；j＞=1；j--

5）k←Indexmatix[i][j]

6）If oknot occupied

7） Map current antito ok

8） Return k

9）Else

10） Continue

11）End if

12）End for

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

為驗(yàn)證改進(jìn)算法的有效性，本文設(shè)計(jì)了仿真實(shí)驗(yàn)，通過(guò)不同數(shù)據(jù)集和不同算法的實(shí)驗(yàn)結(jié)果對(duì)比，驗(yàn)證了本算法的有效性。

4.1 實(shí)驗(yàn)環(huán)境與實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)所用的數(shù)據(jù)集：本實(shí)驗(yàn)采用了UCI數(shù)據(jù)集中最常用的Iris，Wine，Haberman，Balance-scale數(shù)據(jù)集，數(shù)據(jù)集的簡(jiǎn)介如表1所示。

表1 樣本參數(shù)

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

本文的算法采用了相似度矩陣（Similarity Ma?trix）提高算法的聚類效率，記改進(jìn)的蟻群聚類算法為SMACC（Similarity Matrix Ant Colony Clustering）。

用LF算法，文獻(xiàn)［15］中的GACC（GAnt Colo?ny Clustering）算法和SMACC算法對(duì)Iris，Wine和Haberman數(shù)據(jù)集進(jìn)行聚類，在同樣迭代4000次的情況下，運(yùn)行結(jié)果分別如圖3、圖4、圖5所示。由結(jié)果可以看出，對(duì)Iris，Wine和Haberman數(shù)據(jù)集迭代4000次后，SMACC算法聚類結(jié)果最明顯，GACC算法有明顯的聚類趨勢(shì)，而LF算法僅有聚類趨勢(shì)，這表明本算法相對(duì)其他兩種算法有較高的聚類效率。Balance-scale數(shù)據(jù)集的樣本個(gè)數(shù)遠(yuǎn)大于其他數(shù)據(jù)集，在迭代4000次后很難比較聚類的效果，圖6是三種算法迭代10000次后Balance-scale數(shù)據(jù)集的聚類結(jié)果。結(jié)果可以看出，SMACC在大數(shù)據(jù)集的聚類效果明顯優(yōu)于其他兩種算法。

圖3 Iris數(shù)據(jù)集

圖4 Wine數(shù)據(jù)集

圖5 Haberman數(shù)據(jù)集

圖6 Balance-scale數(shù)據(jù)集

Iris數(shù)據(jù)集和Wine數(shù)據(jù)集有相似的樣本個(gè)數(shù)，但Wine數(shù)據(jù)集的屬性個(gè)數(shù)遠(yuǎn)大于Iris數(shù)據(jù)集的屬性個(gè)數(shù)。比較圖1和圖2可知，屬性個(gè)數(shù)增加，聚類效果有所降低。但是，由于SMACC算法采用余弦距離計(jì)算數(shù)據(jù)項(xiàng)間的相似距離，余弦距離更有利于區(qū)分高維度的數(shù)據(jù)項(xiàng)，因此，SMACC在高維度數(shù)據(jù)項(xiàng)的聚類效果遠(yuǎn)優(yōu)于其他兩個(gè)算法。在相同的迭代次數(shù)下，Iris數(shù)據(jù)集的聚類效果比Wine數(shù)據(jù)集的聚類效果好。

在一次迭代過(guò)程中，如果放下或者未撿起數(shù)據(jù)項(xiàng)的螞蟻數(shù)量占總量的90%時(shí)，表明聚類基本完成。三種算法分別在四種數(shù)據(jù)集上收斂時(shí)的六次平均迭代次數(shù)如表2所示。

如表2所示，使用相同數(shù)據(jù)集時(shí)，SMACC的平均迭代次數(shù)明顯小于其他兩種算法，該結(jié)果表明本算法有效地提高了聚類速度。Balance-scala數(shù)據(jù)集中，SMACC的迭代次數(shù)遠(yuǎn)小于其他兩種算法，說(shuō)明該算法更適用于大數(shù)據(jù)集的聚類。

表2 平均迭代次數(shù)比較

F-measure從查準(zhǔn)率和查全率綜合的角度衡量聚類算法的結(jié)果。其一般形式如式（2）所示：

其中，β是查準(zhǔn)率和查全率的權(quán)重比，P是查準(zhǔn)率，R是查全率。

本文采用F1值比較四種數(shù)據(jù)集上三種算法的聚類效果，結(jié)果如圖7～10所示。

圖7 Iris數(shù)據(jù)集

圖8 Wine數(shù)據(jù)集

圖9 Haberman數(shù)據(jù)集

圖10 Balance-scale數(shù)據(jù)集

比較三種聚類算法對(duì)四種不同數(shù)據(jù)集的F1值，GACC和SMACC算法與LF算法的聚類效果總體相似，但GACC和SMACC略好于LF算法。隨著數(shù)據(jù)集中樣本數(shù)量的增加，三種算法的F1值總體有所下降，由于SMACC算法在螞蟻移動(dòng)的過(guò)程中有目的地移動(dòng)，所以數(shù)據(jù)簇中相似度總體比較高，所以在Balance-scale數(shù)據(jù)集中F1值明顯高于LF和GACC算法。同時(shí)，由于蟻群聚類是基于群體行為的聚類方法，隨著數(shù)據(jù)量的增加，聚類結(jié)果的波動(dòng)也減小。圖8中，由于數(shù)據(jù)的維度增加，樣本的區(qū)分度有所降低，但SMACC采用余弦距離作為相似距離，所以F1值略高于其他兩個(gè)算法。

5 結(jié)語(yǔ)

蟻群聚類是一種利用群體智能的聚類算法，其靈感來(lái)自蟻群聚集其尸體的行為。該算法具有魯棒性強(qiáng)，適合分布式等優(yōu)點(diǎn)，但是因?yàn)槲浵侂S機(jī)移動(dòng)數(shù)據(jù)項(xiàng)而造成多次無(wú)效移動(dòng)以及資源浪費(fèi)。針對(duì)該問(wèn)題，本文設(shè)計(jì)了相似度矩陣，使螞蟻在相似度矩陣的指導(dǎo)下有目的地移動(dòng)和關(guān)聯(lián)，從而加快聚類速度。

仿真實(shí)驗(yàn)中，對(duì)比了本算法和其他兩種算法對(duì)UCI數(shù)據(jù)集中四個(gè)實(shí)際數(shù)據(jù)集（Iris，Wine，Haber?man，Balance-scale）的聚類性能。結(jié)果表明，新的蟻群聚類算法在保證聚類精度的基礎(chǔ)上，能夠以較高的速度解決聚類問(wèn)題，同時(shí)具有很好的計(jì)算穩(wěn)定性。但是SMACC依然存在局部?jī)?yōu)化的問(wèn)題，在接下來(lái)的工作中希望通過(guò)參數(shù)的動(dòng)態(tài)調(diào)整來(lái)解決該問(wèn)題。