支持向量機優化基于K-means的蟻群聚類算法

莫錦萍，張志剛

(1.廣西財經學院 現代教育技術部，廣西 南寧530003；2.廣西水利電力職業技術學院，廣西 南寧530024)

聚類是數據在算法的指導下進行無人監督的分類。以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定義為：

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

對分類i而言,F-measure值高的聚類代表分類i的映射,即F-measure表示分類i的評判分值。對聚類結果λ來說，其總F-measure可由每個分類i的 F-measure加權平均得到：

其中|i|為分類i中所有對象的數目。

4.2 實驗步驟

（1）蟻群算法參數Pdel與Iter的選擇。先用Breastcancer數據集進行參數訓練，訓練結果如圖1、圖2所示。

從圖1可知當Pdel≤0.06時，聚類總數平均值越來越接近，而Pdel≥0.06時聚類總數平均值有下降趨勢；同理Iter=60時，聚類取得最佳效果,故實驗中取Pdel=0.06，Iter=60。

(2)用蟻群聚類算法(AntClust)對UCI數據集進行聚類。

(3)用改進的蟻群聚類算法(KM-AntClust)對 UCI數據集進行聚類。

(4)對聚類結果以各類中心為基準，按螞蟻與中心距離大小升序對各類數據進行處理。

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

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

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

（6）以類中心為基準，選取各類百分比為 TrainPro的數據作為訓練集。

（7）采用交叉驗證選擇最佳參數 C與 g，參數選取圖如圖5所示。

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

（8）采用最佳參數C與g對整個訓練集進行訓練獲取支持向量機模型。

（9）利用獲取的模型對整個數據集進行重新測試與分類。

（10）結果比較與分析。

4.3 實驗結果及分析

為比較算法的聚類效果，各算法均運行10次取聚類總數平均值和F-measure平均值作為實驗結果，結果如表 1、表 2所示。

表1 數據集在各算法下運行10次的聚類總數平均值

表2 數據集在各算法下運行10次的F-measure平均值

[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算法局部最優限制，為獲取更佳聚類效果，本文在KMAntClust聚類結果基礎上引入支持向量機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.