摘  要： 基于K-means算法思想改進(jìn)蟻群聚類算法聚類規(guī)則，提出一種新的K-means蟻群聚類算法，并通過實(shí)驗(yàn)驗(yàn)證其聚類效果；引入具有全局最優(yōu)性的支持向量機(jī)SVM，取各類中心附近適當(dāng)數(shù)據(jù)訓(xùn)練支持向量機(jī)，然后利用已獲模型對整個(gè)數(shù)據(jù)集進(jìn)行重新分類，進(jìn)一步優(yōu)化聚類結(jié)果，使聚類結(jié)果達(dá)到全局最優(yōu)。UCI數(shù)據(jù)集實(shí)驗(yàn)結(jié)果表明，新的算法可以明顯提高聚類質(zhì)量。
關(guān)鍵詞： K-平均算法；蟻群算法；聚類；支持向量機(jī)

    聚類是數(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ù)影響較大，針對這些問題，本文首先使用K-means算法思想改進(jìn)蟻群聚類算法規(guī)則，提出一種新的K-means蟻群聚類算法(KM-AntClust)，使聚類中數(shù)據(jù)歸屬有更合理的判定依據(jù)，使聚類結(jié)果局部最優(yōu)。KM-AntClust繼承了AntClust的優(yōu)勢，且從距離的角度明了地反映螞蟻與巢的歸屬關(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ī)，然后利用已獲模型對整個(gè)數(shù)據(jù)集進(jìn)行重新分類，從而使聚類結(jié)果達(dá)到全局最優(yōu)。UCI數(shù)據(jù)集實(shí)驗(yàn)結(jié)果表明新算法的聚類效果得到了進(jìn)一步提高。
1 蟻群聚類算法簡介
    Labroche等提出的蟻群聚類方法AntClust[3-4]利用化學(xué)識別系統(tǒng)原理聚類。它不需假設(shè)對象的表示，僅用相似度sim(i，j)表示對象i和j的關(guān)系。每只人工蟻均有標(biāo)簽Labeli、基因Genetici、模板Templatei[5]以及兩個(gè)判斷參數(shù)Mi、Mi+。算法規(guī)則如下：
    (1)兩只無巢螞蟻相遇時(shí)創(chuàng)建一個(gè)新巢；
    (2)無巢螞蟻與有巢螞蟻相遇則將無巢螞蟻歸到對方所屬巢中；
    (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)定。對于大數(shù)據(jù)集，其強(qiáng)伸縮性和高效性常使聚類結(jié)果以局部最優(yōu)結(jié)束。
    引入K-means算法改進(jìn)聚類規(guī)則，優(yōu)化后的算法簡稱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)勢，且從距離的角度更明了地反映了螞蟻與巢的歸屬關(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ī)，對所聚類結(jié)果以類中心為基準(zhǔn)選取適當(dāng)數(shù)據(jù)訓(xùn)練支持向量機(jī)，利用獲取的模型對整個(gè)數(shù)據(jù)集進(jìn)行重新測試與分類，從而使得聚類結(jié)果達(dá)到全局最優(yōu)。
4 實(shí)驗(yàn)及結(jié)果分析
4.1 實(shí)驗(yàn)平臺、數(shù)據(jù)集及度量標(biāo)準(zhǔn)
    實(shí)驗(yàn)平臺：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。
    聚類性能評價(jià)采用了參考文獻(xiàn)[10]中介紹的F-measure方法。F-measure組合了信息檢索中查準(zhǔn)率(precision)和查全率(recall)的思想。一個(gè)聚類 j 相對于分類i的 precision和recall定義為：


    從圖1可知當(dāng)Pdel≤0.06 時(shí)，聚類總數(shù)平均值越來

 
    參考文獻(xiàn)[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ù)相差甚小。             
    本文對蟻群聚類算法進(jìn)行研究后，首先提出一種新的K-means蟻群聚類算法(KM-AntClust)，使用K-means算法改進(jìn)蟻群聚類算法規(guī)則，解決了AntClust存在的聚類判斷條件隨機(jī)的問題，提高了聚類效果。受K-means算法局部最優(yōu)限制，為獲取更佳聚類效果，本文在KM-AntClust聚類結(jié)果基礎(chǔ)上引入支持向量機(jī)SVM，選取適當(dāng)數(shù)據(jù)訓(xùn)練SVM分類機(jī)，然后利用已獲模型對整個(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.