蟻群聚類組合方法參數M的研究

摘要:蟻群算法中參數在不同取值情況下，常常會對算法的性能和求解效率產生重大影響。該文在基于蟻群聚類組合方法的研究基礎上，重點研究了蟻群聚類組合方法KMAOC算法中蟻群算法參數螞蟻數m對KMAOC算法性能的影響，對KMAOC算法中的參數螞蟻數m分別取值進行實驗，通過幾組實驗驗證提供了KMAOC算法中參數螞蟻數m配置的較好建議。

關鍵詞:聚類;蟻群算法;信息素;聚類組合

中圖分類號:TP311文獻標識碼:A文章編號:1009-3044(2009)36-10469-03

Research Combination Method of Parameter M Based on Ant Colony Clustering

HAN Qiang， XING Jie-qing

(Department of Modern Education Technology， Qiongtai Teachers College， Haikou 571100， China)

Abstract: The ant-based clustering parameter values in different circumstances， often will solve the performance and efficiency of the algorithm have a significant impact. In this paper， based on ant colony clustering combination method based on the study， focusing on the ant colony clustering algorithm combination method KMAOC ant colony algorithm parameters are the number of m pairs of KMAOC algorithm performance influence on the parameters of the algorithm KMAOC the number of ants m， respectively experimental values by several groups of experimental verification provides the better proposal that a KMAOC ant algorithm parameters to configure the number of m.

Key words: clustering; ant colony algorithm; pheromone; clustering combination

聚類在科學數據探測、圖像處理、模式識別、醫療診斷、計算生物學、文檔檢索、Web分析等領域起著非常重要的作用，它已經成為當前數據挖掘研究領域中一個非常活躍的研究課題[1]。經典聚類方法包括分層算法，劃分方法如K均值算法、模糊C均值算法，圖論聚類法，神經網絡法，以及基于統計的方法等[2]。近來隨著數據挖掘研究的深入，涌現了大量新的聚類算法，如蟻群聚類算法等.蟻群算法作為一種開創性的生物仿真算法，因其具有并行性、魯棒性等優良性質得到了廣泛的應用[3]。由于蟻群算法的研究歷史還很短，在實際問題中應用還較少，因些存在許多有待進一步研究改進的地方，如需要設置的參數太多、參數的設置還有一定難度[4]。算法收斂性差和較長時間的花費.特別是運用螞蟻覓食的原理利用信息素來實現聚類的蟻群聚類方法，如其信息素的值從0或相等值開始，各條路徑上的信息素要想明顯區別開，一般需要很長時間。研究表明蟻群聚類算法與K-means算法構成的蟻群聚類組合方法(KMAOC)能較好的彌補這些缺陷[5]。目前國內基于蟻群算法的組合算法研究也進行了不少，如楊燕等在文獻[6]中指出為了改善聚類分析的質量提出了一種基于閾值和蟻群算法相結合的聚類方法。按此方法，首先由基于閾值的聚類算法進行聚類，生成聚類中心，聚類個數也隨之初步確定;然后將蟻群算法的轉移概率引入K-平均算法，對上述聚類結果進行二次優化。將上述兩種算法結合，能夠優勢互補，避免單獨應用一種算法時的局限性，而高尚等在文獻[7]研究中提出克服從不同聚類算法的輸出結果中求共識劃分的困難，較好地改善聚類質量。建立了聚類分析問題模型，分析了K-均值算法、模擬退火算法和基本蟻群算法的優缺點。對蟻群算法作了改進，思路是K-均值方法混合，利用K-均值方法的結果作為初值。經過比較測試，兩種混合蟻群算法的效果都比較好，特別混合方法二的效果最好。本文基于KMAOC蟻群聚類組合算法的研究基礎上僅對組合方法中螞蟻參數m值進行討論并進行實驗分析。

1 K-means聚類算法與經典蟻群算法

1) K-means算法是基于劃分的聚類方法，也是最常用的聚類算法.該算法不斷計算每個聚類的中心，也就是聚類中對象的平均值，作為新的聚類種子.K-means算法試圖找出使平方誤差函數值最小的k個劃分.當結果簇密集并且各簇之間的區別明顯時，它的效果較好.處理大數據集時，K-means算法具有較好的可伸縮性和高效率[8]。應用K-means聚類算法時當結果簇密集并且各簇之間的區別明顯時，它的效果較好.但區別不明顯時則效果較差.該算法的缺點是必須事先給出要生成的聚類數目。

2) 經典蟻群聚類算法

蟻群算法的特點[9]:

① 蟻群算法具有很強的發現較好解的能力。由于算法本身采用了正反饋原理，加快了進化過程，且不易陷入局部最優解;

② 蟻群算法具有很強的并行性，個體之間不斷進行信息交流和傳遞，有利于發現較好解。單個個體容易收斂于局部最優，多個個體通過合作，可很快收斂于解空間的某一個子集，有利于對解空間的進一步探索，從而發現較好解。

蟻群聚類算法存在的問題[5]:

① 算法效率:蟻群聚算法的收殮過程比較緩慢.特別是在迭代初期，由于系統參數改變很慢，導致整個計算過程非常耗時.在基于螞蟻覓食原理的聚類分析中，對各路徑上的信息素的初始化，為簡化操作，一般全都賦為相等的常量C(通常為0).因此，信息素的值從相等常量C開始，各條路徑上的信息素要想明顯區別開，一般需要很長時間. 蟻群聚類算法與K-means算法構成的蟻群聚類組合方法(KMAOC)能較好的解決這一問題。

② 初始值的選擇:初值的選擇對聚類的最終結果影響很大.而在經典蟻群算法中，確定初始參數時，一般缺乏已知的指導經驗.初始參數的確定帶有很大的盲目性.該聚類方法中α，β，m的選擇對算法運行效率和聚類結果都有較大影響，選擇不當將影響算法執行效率和效果，所需時間增長等缺點.可以根據情況嘗試不同的方法避免算法陷于局部最優。本文將重點研究m參數對算法的影響。

2 基本蟻群算法參數及參數m研究

蟻群算法中參數在不同取值情況下，對算法的性能和求解效率會產生重大影響。蟻群算法是一種自適應的、正發饋、分布式的模擬優化算法，它在求解各復雜的組合優化問題上表現出一定的優勢，較好的α、β、ρ、m組合有較好的解質量以及好的穩定性，但如果對蟻群算法的參數選擇不當，蟻群算法較快收斂到局部最優或較慢地收斂，對算法性能有極大的影響[10]。

張杰慧等在文獻[11]中就為了驗證螞蟻個數是不是越多越好的這一設想，選擇了wpbc數據集作為實驗數據。圖1反應為選擇不同螞蟻數目時的實驗結果，并否認了螞蟻數目越多效果越好的假想，在其實驗中就取針對其實驗數據的參數m=5。

由其研究可見，參數m的選取不是越大越好，但也不能取之過小。在TSP實驗中，螞蟻數目越大越有利于求解，但是計算的迭代次數也會變大。根據實驗，螞蟻數目一般設定在城市規模數的1/2到2/3之間較為合適[12]。

3 基于K-Means的蟻群聚類算法

引入K-Means作為預計算求解聚類問題的基本蟻群算法(AOC)做為一種蟻群聚類組合方法(KMAOC)如下[5]:

Step1 任選k個初始聚類中心:C1，C2，C3，…CK;

Step2 逐個將數據集{X}中各個數據對象按最小距離原則分配給k個聚類中心的某一個Cj;

Step3 計算新的聚類中心Cj'(j=1，2， …，k)，即，其中Nj為第j個聚類域Sj 包含的個數;

Step4 若C'j≠Cj (j=1，2， …，k)且未快速分類到設定聚類效果閥值γ或是指定次數時轉Step2.

Step5 nc<-0 (nc為循環次數)，由k-means算法分類結果計算出的聚類中心Cj(j=1，2， …，k)，計算每個樣本數據Xi 相對應的到不同聚類中心Cj的初值τij(0)(i，j=1，2， …，N)，.給出Q、ρ(信息素持久)、n(螞蟻數)的值，隨機給出分配方案;

Step6 對每個螞蟻按轉移概率pij(t)選擇下一個節點;

Step7 計算新的聚類中心，計算每個樣本數據到新的聚類中心的距離.由螞群聚類公式修改信息素強度τij(t);

Step8 若nc<預定的迭代次數且無退化行為(即找到的都是相同的解)，則輸出最好的解;否則轉Step6。

4 算法測試

本文采用外部評價F-measure方法[13]以及總的運行時間對提出的聚類算法與K均值算法和標準蟻群算法進行評價和比較。F-measure的取值在[0，1]之間，取值越接近1越好。實驗數據取于UCI機器學習數據庫的Wine數據集.數據集有自己的分類，可用于聚類性能的評價。對于聚類算法的性能評價通常采用外部和內部兩種，其依據是有無關于數據集的先驗知識。

表2給出了KMAOC算法參數m為8種不同取值情況下Runtime①、F-measure的值(取100次實驗的平均值)。

注①在同一臺計算機上運行以KMAOC算法算法參數值:α=1，β=5，ρ=0.99，Q=80，螞蟻數m=60. 迭代次數nc為200次。以其為標準時間，取值為1. 當算法參數m變化時的Runtime取值為算法參數m變化時實際運行時間/KMAOC算法參數m為60的實際運行時間得出的比值。

實驗結果表明:對于迭代次數與其它α，β，ρ參數取值相同情況下，KMAOC算法參數m取值的不同其Runtime與F-measure值都不同。但相比而言，對本數據集取m值為60左右的Runtime與F-measure所得值較為理想。若取m值其較小時收斂時間減少，但F-measure也較小。 若取m值較大時雖然F-measure值增大，但同時收斂時間又增大較多。由實驗可知，根據實際問題的應用背景，確定m值，應選取Runtime與F-measure取值都較為理想的情況。

5 結束語

本文對引入K-Means作為預處理過程的蟻群算法(KMAOC)中參數螞蟻數m的取值進行了討論。提出參數取值情況應根據不同數據對象進行取值，對參數m取值得到了較好的取值范圍。由于KMAOC算法較好的避免了經典蟻群算法初始階段學習緩慢的缺點。因而相比經典蟻群算法參數m取值而言，KMAOC算法的參數m取值可取得相對大些。建議m的取數應是聚類數的1.6至2倍間取值較好。

參考文獻:

[1] Handl J， Knowles J， Dorigo M.On the performance of ant-based clustering[C].In:Proc of the 3rd Int Confon Hybrid Intelligent Systems， IOS Press，Australia，2003.

[2] 韓家煒， KAMBER M. 數據挖掘:概念與技術[M].北京:機械工業出版社，2001:223-251.

[3] 曾洲.蟻群算法不確定性分析[J].計算機應用，2004，10:136-138.

[4] 陳應顯.蟻群聚類算法中確定相鄰對象方法的改進[J].計算機工程與應用，2009，45(18):144-145.

[5] 邢潔清.蟻群聚類組合方法的研究[J].計算機工程與應用，2009，45(18):146-148.

[6] 楊燕.基于閾值和蟻群算法結合的聚類方法[J].西南交通大學學報，2006，41(6):719-723.

[7] 高尚.一種新的基于混合蟻群算法的聚類方法[J].微電子學與計算機，2006，23(12):38-42.

[8] 張群，熊英，黃慶炬.基于蟻群算法的數據挖掘方法研究[J].湖北工業大學學報，2007，22(2):5-9.

[9] 徐寧.幾種現代優化算法的比較研究[J].系統工程與電子技術，2002，24(12):101-105.

[10] 蔣玲艷.蟻群算法的參數分析[J].計算機工程與應用，2007，43(20):31-37.

[11] 張杰慧.基于自適應蟻群算法的組合式特征選擇算法[J].系統仿真學報，2009，3(6):1605-1610.

[12] 王軍.蟻群算法求解TSP時參數設置的研究[J].科學技術與工程，2007，7(17):4501-4505.

[13] Rijsbergen C. Information Retrieval[M].2nd edition，Butterworths，London，UK，1979:99.