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

    聚類是數(shù)據(jù)在算法的指導下進行無人監(jiān)督的分類。以K-means[1]和 K-medoid[2]為代表的劃分法是常用聚類算法中的一種。常用聚類算法多面向數(shù)值屬性，而蟻群聚類算法（AntClust）[3-4]能處理任意類型的數(shù)據(jù)，具有強魯棒性和適應性，但其聚類結(jié)果受數(shù)據(jù)集大小和參數(shù)影響較大，針對這些問題，本文首先使用K-means算法思想改進蟻群聚類算法規(guī)則，提出一種新的K-means蟻群聚類算法(KM-AntClust)，使聚類中數(shù)據(jù)歸屬有更合理的判定依據(jù)，使聚類結(jié)果局部最優(yōu)。KM-AntClust繼承了AntClust的優(yōu)勢，且從距離的角度明了地反映螞蟻與巢的歸屬關系，使聚類有合理的理論支撐，聚類效果得到提高。但K-means算法收斂準則的主觀性及聚類過程中心的累積誤差，雖然使各類中心附近的數(shù)據(jù)能找到最優(yōu)的歸屬，但離類中心較遠的數(shù)據(jù)因誤差累積不一定都能找到最佳歸屬，降低了聚類效果。支持向量機SVM是在統(tǒng)計學理論的VC維理論和結(jié)構(gòu)風險最小化原理基礎上發(fā)展起來的一種新的機器學習方法，具有適應性強、全局優(yōu)化、訓練效率高和泛化性強等優(yōu)點，其全局最優(yōu)性彌補了K-means算法的不足。為此在KM-AntClust基礎上引入SVM，以各類中心為基準選取適當數(shù)據(jù)訓練支持向量機，然后利用已獲模型對整個數(shù)據(jù)集進行重新分類，從而使聚類結(jié)果達到全局最優(yōu)。UCI數(shù)據(jù)集實驗結(jié)果表明新算法的聚類效果得到了進一步提高。
1 蟻群聚類算法簡介
    Labroche等提出的蟻群聚類方法AntClust[3-4]利用化學識別系統(tǒng)原理聚類。它不需假設對象的表示，僅用相似度sim(i，j)表示對象i和j的關系。每只人工蟻均有標簽Labeli、基因Genetici、模板Templatei[5]以及兩個判斷參數(shù)Mi、Mi+。算法規(guī)則如下：
    (1)兩只無巢螞蟻相遇時創(chuàng)建一個新巢；
    (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ì)量不高原因分析
    蟻群聚類算法具有較好的魯棒性和適應性，但其聚類結(jié)果不穩(wěn)定，主要原因如下：
    (1)規(guī)則(4)依據(jù)Mi+判斷踢出螞蟻。根據(jù)算法思想，Mi+為隨機量， 其值不僅與螞蟻所屬巢規(guī)模有關，還與循環(huán)次數(shù)相關。Mi+是螞蟻i被巢成員接受的程度，而不是反映螞蟻與巢的依存關系，Mi+大并不能說明此巢是螞蟻i的最優(yōu)歸屬，故依此踢出螞蟻產(chǎn)生累積誤差導致聚類質(zhì)量降低。
    (2)循環(huán)迭代參數(shù)Iter和刪除概率Pdel的設置。循環(huán)次數(shù)NBIter=Iter×N不足[5]，數(shù)據(jù)覆蓋率低；太大導致過學習，聚類效果均受影響。參數(shù)Pdel太大聚出的類數(shù)目較少，相反則類過多，影響聚類質(zhì)量。因此，參數(shù)Iter和Pdel的確定是保證聚類質(zhì)量的重要環(huán)節(jié)。
2.2 使用K-means改進蟻群聚類規(guī)則
    K-means聚類算法基于誤差平方和最小準則，聚類結(jié)果通常不受初始中心的影響，較為穩(wěn)定。對于大數(shù)據(jù)集，其強伸縮性和高效性常使聚類結(jié)果以局部最優(yōu)結(jié)束。
    引入K-means算法改進聚類規(guī)則，優(yōu)化后的算法簡稱KM-AntClust。設di為螞蟻i到其所屬巢中心的距離，規(guī)則改進如下：
    (1)兩只無巢螞蟻i、j相遇時創(chuàng)建一個新巢并計算巢中心；
    (2)無巢螞蟻i與有巢螞蟻j相遇則將螞蟻i歸到螞蟻j所屬巢中并更新該巢中心；
    (3)同巢互不接受的兩只螞蟻i、j相遇時，計算di、dj，將d值大的螞蟻踢出巢并更新巢中心；
    (4)兩只不同巢的螞蟻相遇且相互接受時，將兩巢合并并更新巢中心；
    (5)若不出現(xiàn)以上各情況，則不做任何操作。
3 使用SVM優(yōu)化K-means蟻群聚類算法
3.1 支持向量機SVM
    支持向量機[6-7]SVM是在統(tǒng)計學理論的VC維理論和結(jié)構(gòu)風險最小化原理的基礎上發(fā)展起來的一種新的機器學習方法。它的基本思想是將輸入空間通過一種非線性變換映射到一個高維的特征空間，然后在這個新的高維特征空間中求解原始問題的最優(yōu)解[8-9]。
3.2 使用SVM優(yōu)化K-means 蟻群聚類算法
    K-means蟻群聚類算法繼承了蟻群算法的優(yōu)勢，且從距離的角度更明了地反映了螞蟻與巢的歸屬關系，摒棄了蟻群算法隨機的判斷條件，使聚類有合理的理論支撐，聚類效果得到提高。但是，K-means算法本身也存在缺點，源于其收斂準則主觀設定，聚類過程中心重復計算更新，使各類中心附近的數(shù)據(jù)能找到最優(yōu)歸屬，而離類中心較遠的數(shù)據(jù)因誤差累積效應找到最佳歸類的性能減弱，從而使聚類結(jié)果達到局部最優(yōu)，影響聚類的效果。
    SVM的強適應性、全局最優(yōu)性等優(yōu)點彌補了K-means算法的不足。在已聚出類結(jié)果的基礎之上再引入支持向量機，對所聚類結(jié)果以類中心為基準選取適當數(shù)據(jù)訓練支持向量機，利用獲取的模型對整個數(shù)據(jù)集進行重新測試與分類，從而使得聚類結(jié)果達到全局最優(yōu)。
4 實驗及結(jié)果分析
4.1 實驗平臺、數(shù)據(jù)集及度量標準
    實驗平臺：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。
    聚類性能評價采用了參考文獻[10]中介紹的F-measure方法。F-measure組合了信息檢索中查準率(precision)和查全率(recall)的思想。一個聚類 j 相對于分類i的 precision和recall定義為：


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

 
    參考文獻[11]中說明數(shù)據(jù)集Iris用于聚類時可作兩類處理。從表1可知，與AntClust相比較，KM-AntClust獲得更好的聚類效果，其F-measure平均值均比AntClust的高，最高達到了0.988 722；聚類總數(shù)也越接近數(shù)據(jù)集原始分類。而SVM-KMAntClust使得聚類效果得到了進一步提高，其F-measure平均值均比前兩種算法的高，有的甚至能全部正確分類，F(xiàn)-measure平均值為1，聚類總數(shù)與數(shù)據(jù)集原始分類數(shù)相差甚小。             
    本文對蟻群聚類算法進行研究后，首先提出一種新的K-means蟻群聚類算法(KM-AntClust)，使用K-means算法改進蟻群聚類算法規(guī)則，解決了AntClust存在的聚類判斷條件隨機的問題，提高了聚類效果。受K-means算法局部最優(yōu)限制，為獲取更佳聚類效果，本文在KM-AntClust聚類結(jié)果基礎上引入支持向量機SVM，選取適當數(shù)據(jù)訓練SVM分類機，然后利用已獲模型對整個數(shù)據(jù)集進行重新分類，充分發(fā)揮SVM的強適應性和全局最優(yōu)性，使得聚類結(jié)果達到全局最優(yōu)。AntClust與K-means算法結(jié)合繼承了AntClust的優(yōu)點，同時保證了類的穩(wěn)定性；AntClust與SVM結(jié)合使聚類效果全局最優(yōu)時也擴大了SVM的應用領域。實驗結(jié)果表明，三者相結(jié)合聚類質(zhì)量得到了進一步的提高。
參考文獻
[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].計算機工程與應用，2005，41(17)：79-84.
[9] 沈翠華，劉廣利，鄧乃揚.一種改進的支持向量分類方法及其應用[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.