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

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


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

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