莫錦萍，張志剛

(1.廣西財(cái)經(jīng)學(xué)院 現(xiàn)代教育技術(shù)部，廣西 南寧530003；2.廣西水利電力職業(yè)技術(shù)學(xué)院，廣西 南寧530024)

聚類是數(shù)據(jù)在算法的指導(dǎo)下進(jìn)行無人監(jiān)督的分類。以K-means[1]和 K-medoid[2]為代表的劃分法是常用聚類算法中的一種。常用聚類算法多面向數(shù)值屬性，而蟻群聚類算法（AntClust）[3-4]能處理任意類型的數(shù)據(jù)，具有強(qiáng)魯棒性和適應(yīng)性，但其聚類結(jié)果受數(shù)據(jù)集大小和參數(shù)影響較大，針對(duì)這些問題，本文首先使用K-means算法思想改進(jìn)蟻群聚類算法規(guī)則，提出一種新的K-means蟻群聚類算法(KM-AntClust)，使聚類中數(shù)據(jù)歸屬有更合理的判定依據(jù)，使聚類結(jié)果局部最優(yōu)。KM-AntClust繼承了AntClust的優(yōu)勢(shì)，且從距離的角度明了地反映螞蟻與巢的歸屬關(guān)系，使聚類有合理的理論支撐，聚類效果得到提高。但K-means算法收斂準(zhǔn)則的主觀性及聚類過程中心的累積誤差，雖然使各類中心附近的數(shù)據(jù)能找到最優(yōu)的歸屬，但離類中心較遠(yuǎn)的數(shù)據(jù)因誤差累積不一定都能找到最佳歸屬，降低了聚類效果。支持向量機(jī)SVM是在統(tǒng)計(jì)學(xué)理論的VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小化原理基礎(chǔ)上發(fā)展起來的一種新的機(jī)器學(xué)習(xí)方法，具有適應(yīng)性強(qiáng)、全局優(yōu)化、訓(xùn)練效率高和泛化性強(qiáng)等優(yōu)點(diǎn)，其全局最優(yōu)性彌補(bǔ)了K-means算法的不足。為此在KM-AntClust基礎(chǔ)上引入SVM，以各類中心為基準(zhǔn)選取適當(dāng)數(shù)據(jù)訓(xùn)練支持向量機(jī)，然后利用已獲模型對(duì)整個(gè)數(shù)據(jù)集進(jìn)行重新分類，從而使聚類結(jié)果達(dá)到全局最優(yōu)。UCI數(shù)據(jù)集實(shí)驗(yàn)結(jié)果表明新算法的聚類效果得到了進(jìn)一步提高。

1 蟻群聚類算法簡(jiǎn)介

Labroche等提出的蟻群聚類方法AntClust[3-4]利用化學(xué)識(shí)別系統(tǒng)原理聚類。它不需假設(shè)對(duì)象的表示，僅用相似度sim(i，j)表示對(duì)象 i和j的關(guān)系。每只人工蟻均有標(biāo)簽 Labeli、基因 Genetici、模板 Templatei[5]以及兩個(gè)判斷參數(shù) Mi、Mi+。 算法規(guī)則如下：

(1)兩只無巢螞蟻相遇時(shí)創(chuàng)建一個(gè)新巢；

(2)無巢螞蟻與有巢螞蟻相遇則將無巢螞蟻歸到對(duì)方所屬巢中；

(3)兩只同巢螞蟻 i、j相遇，若相互接受，則增大 Mi、Mj和 Mi+、Mj+的值；

(4)兩只同巢螞蟻 i、j相遇，若互不接受，則減小 Mi、Mj和 Mi+、Mj+的值并將M+值小的螞蟻移出巢；

(5)兩只不同巢螞蟻相遇并相互接受則將兩巢合并；

(6)若不出現(xiàn)以上各情況，則不做任何操作。

2 使用K-means優(yōu)化蟻群聚類模型

2.1 蟻群聚類算法聚類質(zhì)量不高原因分析

蟻群聚類算法具有較好的魯棒性和適應(yīng)性，但其聚類結(jié)果不穩(wěn)定，主要原因如下：

(1)規(guī)則(4)依據(jù)Mi+判斷踢出螞蟻。根據(jù)算法思想，Mi+為隨機(jī)量，其值不僅與螞蟻所屬巢規(guī)模有關(guān)，還與循環(huán)次數(shù)相關(guān)。Mi+是螞蟻i被巢成員接受的程度，而不是反映螞蟻與巢的依存關(guān)系，Mi+大并不能說明此巢是螞蟻i的最優(yōu)歸屬，故依此踢出螞蟻產(chǎn)生累積誤差導(dǎo)致聚類質(zhì)量降低。

(2)循環(huán)迭代參數(shù)Iter和刪除概率Pdel的設(shè)置。循環(huán)次數(shù)NBIter=Iter×N不足[5]，數(shù)據(jù)覆蓋率低；太大導(dǎo)致過學(xué)習(xí)，聚類效果均受影響。參數(shù)Pdel太大聚出的類數(shù)目較少，相反則類過多，影響聚類質(zhì)量。因此，參數(shù)Iter和Pdel的確定是保證聚類質(zhì)量的重要環(huán)節(jié)。

2.2 使用K-means改進(jìn)蟻群聚類規(guī)則

K-means聚類算法基于誤差平方和最小準(zhǔn)則，聚類結(jié)果通常不受初始中心的影響，較為穩(wěn)定。對(duì)于大數(shù)據(jù)集，其強(qiáng)伸縮性和高效性常使聚類結(jié)果以局部最優(yōu)結(jié)束。

引入K-means算法改進(jìn)聚類規(guī)則，優(yōu)化后的算法簡(jiǎn)稱KM-AntClust。設(shè)di為螞蟻i到其所屬巢中心的距離，規(guī)則改進(jìn)如下：

(1)兩只無巢螞蟻i、j相遇時(shí)創(chuàng)建一個(gè)新巢并計(jì)算巢中心；

(2)無巢螞蟻i與有巢螞蟻j相遇則將螞蟻 i歸到螞蟻j所屬巢中并更新該巢中心；

(3)同巢互不接受的兩只螞蟻 i、j相遇時(shí)，計(jì)算 di、dj，將d值大的螞蟻踢出巢并更新巢中心；

(4)兩只不同巢的螞蟻相遇且相互接受時(shí)，將兩巢合并并更新巢中心；

(5)若不出現(xiàn)以上各情況，則不做任何操作。

3 使用SVM優(yōu)化K-means蟻群聚類算法

3.1 支持向量機(jī)SVM

支持向量機(jī)[6-7]SVM是在統(tǒng)計(jì)學(xué)理論的VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小化原理的基礎(chǔ)上發(fā)展起來的一種新的機(jī)器學(xué)習(xí)方法。它的基本思想是將輸入空間通過一種非線性變換映射到一個(gè)高維的特征空間，然后在這個(gè)新的高維特征空間中求解原始問題的最優(yōu)解[8-9]。

3.2 使用SVM優(yōu)化K-means蟻群聚類算法

K-means蟻群聚類算法繼承了蟻群算法的優(yōu)勢(shì)，且從距離的角度更明了地反映了螞蟻與巢的歸屬關(guān)系，摒棄了蟻群算法隨機(jī)的判斷條件，使聚類有合理的理論支撐，聚類效果得到提高。但是，K-means算法本身也存在缺點(diǎn)，源于其收斂準(zhǔn)則主觀設(shè)定，聚類過程中心重復(fù)計(jì)算更新，使各類中心附近的數(shù)據(jù)能找到最優(yōu)歸屬，而離類中心較遠(yuǎn)的數(shù)據(jù)因誤差累積效應(yīng)找到最佳歸類的性能減弱，從而使聚類結(jié)果達(dá)到局部最優(yōu)，影響聚類的效果。

SVM的強(qiáng)適應(yīng)性、全局最優(yōu)性等優(yōu)點(diǎn)彌補(bǔ)了K-means算法的不足。在已聚出類結(jié)果的基礎(chǔ)之上再引入支持向量機(jī)，對(duì)所聚類結(jié)果以類中心為基準(zhǔn)選取適當(dāng)數(shù)據(jù)訓(xùn)練支持向量機(jī)，利用獲取的模型對(duì)整個(gè)數(shù)據(jù)集進(jìn)行重新測(cè)試與分類，從而使得聚類結(jié)果達(dá)到全局最優(yōu)。

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

4.1 實(shí)驗(yàn)平臺(tái)、數(shù)據(jù)集及度量標(biāo)準(zhǔn)

實(shí)驗(yàn)平臺(tái)：PC 配置：Pentium 4，2.4 GHz CPU，512 MB內(nèi)存；Windows XP操作系統(tǒng)；使用VC算法編寫。數(shù)據(jù)集采用 UCI公共數(shù)據(jù)庫提供的數(shù)據(jù)集 Iris、Breast-cancer和KDDCUP。

聚類性能評(píng)價(jià)采用了參考文獻(xiàn)[10]中介紹的F-measure方法。F-measure組合了信息檢索中查準(zhǔn)率(precision)和查全率(recall)的思想。一個(gè)聚類 j相對(duì)于分類i的 precision和recall定義為：

其中，Nij是在聚類j中分類i的數(shù)目；Nj是聚類 j所有對(duì)象的數(shù)目；Ni是分類i所有對(duì)象的數(shù)目。分類i的F-measure定義為：

對(duì)分類i而言,F-measure值高的聚類代表分類i的映射,即F-measure表示分類i的評(píng)判分值。對(duì)聚類結(jié)果λ來說，其總F-measure可由每個(gè)分類i的 F-measure加權(quán)平均得到：

其中|i|為分類i中所有對(duì)象的數(shù)目。

4.2 實(shí)驗(yàn)步驟

（1）蟻群算法參數(shù)Pdel與Iter的選擇。先用Breastcancer數(shù)據(jù)集進(jìn)行參數(shù)訓(xùn)練，訓(xùn)練結(jié)果如圖1、圖2所示。

從圖1可知當(dāng)Pdel≤0.06時(shí)，聚類總數(shù)平均值越來越接近，而Pdel≥0.06時(shí)聚類總數(shù)平均值有下降趨勢(shì)；同理Iter=60時(shí)，聚類取得最佳效果,故實(shí)驗(yàn)中取Pdel=0.06，Iter=60。

(2)用蟻群聚類算法(AntClust)對(duì)UCI數(shù)據(jù)集進(jìn)行聚類。

(3)用改進(jìn)的蟻群聚類算法(KM-AntClust)對(duì) UCI數(shù)據(jù)集進(jìn)行聚類。

(4)對(duì)聚類結(jié)果以各類中心為基準(zhǔn)，按螞蟻與中心距離大小升序?qū)Ω黝悢?shù)據(jù)進(jìn)行處理。

(5)類訓(xùn)練集百分比參數(shù)TrainPro的選取。

以類中心為基準(zhǔn)，選取百分比為TrainPro的數(shù)據(jù)作為訓(xùn)練集訓(xùn)練SVM。同樣用Breast-cancer數(shù)據(jù)集進(jìn)行參數(shù)訓(xùn)練。對(duì)類而言，越接近類中心的數(shù)據(jù)說明其與該類越相似，歸屬于此類的概率也越大。若TrainPro值過小，訓(xùn)練集反應(yīng)出的類特征不全；過大則會(huì)混合其他類數(shù)據(jù)使得類特征被削弱。因此，訓(xùn)練時(shí)用聚類效果F-measure值和分類準(zhǔn)確率Accuracy共同來確定TrainPro的大小，實(shí)驗(yàn)結(jié)果如圖3、圖4所示。

從圖 3、圖 4可知，當(dāng) TrainPro漸趨于 0.6時(shí) F-measure和Accuracy值漸增，而當(dāng)TrainPro大于0.6后F-measure和Accuracy值有減小的趨勢(shì)，說明TrainPro取0.6時(shí)所取的訓(xùn)練數(shù)據(jù)集最能代表類的特征，當(dāng)超過0.6后因類夾雜其他類數(shù)據(jù)而使得聚類效果降低，故在實(shí)驗(yàn)中取TrainPro=0.6。

（6）以類中心為基準(zhǔn)，選取各類百分比為 TrainPro的數(shù)據(jù)作為訓(xùn)練集。

（7）采用交叉驗(yàn)證選擇最佳參數(shù) C與 g，參數(shù)選取圖如圖5所示。

即C=8，g=0.007 812 5時(shí)分類取得最佳效果。

（8）采用最佳參數(shù)C與g對(duì)整個(gè)訓(xùn)練集進(jìn)行訓(xùn)練獲取支持向量機(jī)模型。

（9）利用獲取的模型對(duì)整個(gè)數(shù)據(jù)集進(jìn)行重新測(cè)試與分類。

（10）結(jié)果比較與分析。

4.3 實(shí)驗(yàn)結(jié)果及分析

為比較算法的聚類效果，各算法均運(yùn)行10次取聚類總數(shù)平均值和F-measure平均值作為實(shí)驗(yàn)結(jié)果，結(jié)果如表 1、表 2所示。

表1 數(shù)據(jù)集在各算法下運(yùn)行10次的聚類總數(shù)平均值

表2 數(shù)據(jù)集在各算法下運(yùn)行10次的F-measure平均值

[11]中說明數(shù)據(jù)集Iris用于聚類時(shí)可作兩類處理。從表1可知，與AntClust相比較，KM-AntClust獲得更好的聚類效果，其F-measure平均值均比AntClust的高，最高達(dá)到了 0.988 722；聚類總數(shù)也越接近數(shù)據(jù)集原始分類。而SVM-KMAntClust使得聚類效果得到了進(jìn)一步提高，其F-measure平均值均比前兩種算法的高，有的甚至能全部正確分類，F(xiàn)-measure平均值為1，聚類總數(shù)與數(shù)據(jù)集原始分類數(shù)相差甚小。

本文對(duì)蟻群聚類算法進(jìn)行研究后，首先提出一種新的 K-means蟻群聚類算法(KM-AntClust)，使用 K-means算法改進(jìn)蟻群聚類算法規(guī)則，解決了AntClust存在的聚類判斷條件隨機(jī)的問題，提高了聚類效果。受K-means算法局部最優(yōu)限制，為獲取更佳聚類效果，本文在KMAntClust聚類結(jié)果基礎(chǔ)上引入支持向量機(jī)SVM，選取適當(dāng)數(shù)據(jù)訓(xùn)練SVM分類機(jī)，然后利用已獲模型對(duì)整個(gè)數(shù)據(jù)集進(jìn)行重新分類，充分發(fā)揮SVM的強(qiáng)適應(yīng)性和全局最優(yōu)性，使得聚類結(jié)果達(dá)到全局最優(yōu)。AntClust與K-means算法結(jié)合繼承了AntClust的優(yōu)點(diǎn)，同時(shí)保證了類的穩(wěn)定性；AntClust與SVM結(jié)合使聚類效果全局最優(yōu)時(shí)也擴(kuò)大了SVM的應(yīng)用領(lǐng)域。實(shí)驗(yàn)結(jié)果表明，三者相結(jié)合聚類質(zhì)量得到了進(jìn)一步的提高。

參考文獻(xiàn)

[1]QUEEN J M.Some methods for classification and analysis of multivariate observations[C].Proc.of the 5th Berkeley Symp.On Math Statist，1967：281-297.

[2]KAUFMAN J，ROUSSEEUW P J.Finding groups in data：an introduction to cluster analysis[M].New York：John Wiley&Sons，1990.

[3]LABROCHE N，MONMARCHE N，VENTURINI G.A new clustering algorithm based on the chemical recognition system of ants[C].Proc of 15th European Conference on Artificial Intelligence(ECAI 2002)，Lyon FRANCE，2002：345-349.

[4]LABROCHE N，MONMARCHE N，VENTURINI G.Web sessions clustering with artificial ants colonies[EB/OL].(2002-02)[2006-01-12].

[5]LABROCHE N，MONMARCHE N，VENTURINI G.AntClust：ant clustering and Web usage mining[C].GECCO 2003：25-36.

[6]VAPNIK V.The nature of statistical learning theory[M].New York：Springer-Verlag，1995.

[7]CORTES C，VAPNIK V.Support vector networks[J].Machine Learning，1995(20)：273-297.

[8]白亮，老松楊，胡艷麗.支持向量機(jī)訓(xùn)練算法比較研究[J].計(jì)算機(jī)工程與應(yīng)用，2005，41(17)：79-84.

[9]沈翠華，劉廣利，鄧乃揚(yáng).一種改進(jìn)的支持向量分類方法及其應(yīng)用[J].計(jì)算機(jī)工程，2005，31(8)：153-154.

[10]YANG Y,KAMEI M.Clustering ensemble using swarm intelligence[C].IEEE SWRFB intelligence symposium.Piscataway，NJ：IEEE service center，2003：65271.

[11]KANADE P M，HALL L O.Fuzzy ants as a clustering concept[C].Proc of the 22nd International Conference of the North American Fuzzy Information Processing Society，2003：227-232.