蟻群聚類組合方法參數(shù)m的研究

1、蟻群聚類組合方法參數(shù)m的研究韓強i邢潔清|1.瓊臺師范高等專科學(xué)校信息技術(shù)系海南?？?571100research combination method of parameter m based on ant colony clusteringhanqiang1 xing jie-qing1l. department of modem education technology, qiongtai teachers college hainan haiko 571100, china email: qqxjqabstract: the ant-based clustering parameter

2、 values in different circumstanccs, often will solve the performanee and efficiency of the algorithm have a significant impact tn 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 algo

3、rithm parameters are the number of m pairs of kmaoc algorithm performance influcneo on the parameters of the algorithm kmaoc the number of antsm,respectively experimental values by several groups of experimental verification provides the better proposal that a kmaoc ant algorithm parameters to confi

4、gure the number of m .keywords: clustering； ant colony algorithm; pheromone; clustering combination 摘要：蟻酬算法中參數(shù)在不同取值情況下，常常會對算法的性能和求解效率產(chǎn)生重大影響。 本文在基于蟻群聚類組合方法的研究基礎(chǔ)上，重點研究了蟻群聚類組合方法kmaoc算法 中蟻群算法參數(shù)螞蟻數(shù)m對kmaoc算法性能的影響，対kmaoc算法中的參數(shù)螞蟻數(shù)m 分別取值進(jìn)行實驗，通過兒組實驗驗證捉供了 kmaoc算法屮參數(shù)螞蟻數(shù)m配置的較好建 議。關(guān)鍵詞：聚類，蟻群算法，信息素，聚類組合 中圖分類號：tp311

5、 ;tp12 文獻(xiàn)標(biāo)識碼:a 1引言聚類在科學(xué)數(shù)據(jù)探測、圖像處理、模式識別、醫(yī)療診斷、計算牛物學(xué)、文檔檢索、web 分析等領(lǐng)域起著非常重要的作用，它已經(jīng)成為當(dāng)前數(shù)據(jù)挖掘研究領(lǐng)域中一個非?；钴S的研究 課題.經(jīng)典聚類方法包括分層算法，劃分方法如k均值算法、模糊c均值算法，圖論聚類 法，神經(jīng)網(wǎng)絡(luò)法，以及基于統(tǒng)計的方法等近來隨著數(shù)據(jù)挖掘研究的深入，涌現(xiàn)了大屋新的 聚類算法，如蟻群聚類算法等.蟻群算法作為一種開創(chuàng)性的生物仿真算法，因其具冇并行性、 魯棒性等優(yōu)良性質(zhì)得到了廣泛的應(yīng)用譏由于蟻群算法的研究歷史還很短，在實際問題屮應(yīng) 用還較少，因些存在許多有待進(jìn)一步研究改進(jìn)的地方，如需要設(shè)置的參數(shù)太多、參數(shù)的設(shè)

6、置 還冇一定難度。算法收斂性差和較長時間的花費.特別是運用螞蟻覓食的原理利用信息索來 實現(xiàn)聚類的蟻群聚類方法，如其信息素的值從0或相等值開始，各條路徑上的信息素要想明 顯區(qū)別開，一般需要很長時間。研究表明蟻群聚類算法與k-means算法構(gòu)成的蟻群聚類組 合方法(kmaoc)能鮫好的彌補這些缺陷。目前國內(nèi)基于蟻群算法的紐合算法研究也進(jìn)行 了不少，如楊燕等在文獻(xiàn)6中指出為了改善聚類分析的質(zhì)量提出了一種基于閾值和蟻群算 法相結(jié)合的聚類方法。按此方法，首先由基于閾值的聚類算法進(jìn)行聚類，生成聚類中心，聚 類個數(shù)也隨之初步確定；然麻將蟻群算法的轉(zhuǎn)移概率引入k平均算法，對上述聚類結(jié)果進(jìn) 行二次優(yōu)化。將上述兩

7、種算法結(jié)合，能夠優(yōu)勢互補，避免單獨應(yīng)用一種算法時的局限性，而 高尚等在文獻(xiàn)7研究中提出克服從不同聚類算法的輸出結(jié)果中求共識劃分的困難，鮫好地基金項目：瓊臺師范高等?？茖W(xué)校科研項目(批準(zhǔn)號:qtky2009-20)作者簡介：韓強(1982 ),男,助教，主要研究領(lǐng)域為計算機應(yīng)用等；邢潔清(1977 ),男，碩士，副教授，主要研究 領(lǐng)域為軟件應(yīng)用，人工智能等；改善聚類質(zhì)雖。建立了聚類分析問題模型，分析k均值算法、模擬退火算法和基木蟻群算 法的優(yōu)缺點。對蟻群算法作了改進(jìn)，思路是k均值方法混合，利用k均值方法的結(jié)果作為 初值。經(jīng)過比較測試，兩種混合蟻群算法的效果都比較好，特別混合方法二的效果最好。本

8、文基于kmaoc蟻群聚類組合算法的研究基礎(chǔ)上僅對組合方法中螞蟻參數(shù)m值進(jìn)行討論并 進(jìn)行實驗分析。2 k-means聚類算法為經(jīng)典蟻群算法(1) k-means算法是基于劃分的聚類方法，也是最常用的聚類算法.該算法不斷計算毎個聚類 的屮心，也就是聚類屮對象的平均值，作為新的聚類種子.k-means算法試圖找出使平方誤 養(yǎng)函數(shù)值最小的k個劃分.當(dāng)結(jié)果簇密集并且各簇之間的區(qū)別明顯時，它的效果較好.處理人 數(shù)據(jù)集0j', k-mcans算法具冇較好的可仲縮性和高效率巴應(yīng)用k-mcans聚類算法時當(dāng)結(jié)果簇 密集并且各簇之間的區(qū)別明顯時，它的效果較好.但區(qū)別不明顯時則效果較羌.該算法的缺點 是必須

9、事先給出要牛成的聚類數(shù)目。(2) 經(jīng)典蟻群聚類算法蟻群算法的特點汽1) 蟻群算法具有很強的發(fā)現(xiàn)較好解的能力。由于算法本身采用了正反饋原理，加快了進(jìn) 化過程，且不易陷入局部最優(yōu)解；2) 蟻群算法具冇很強的并行性，個體z間不斷進(jìn)行信息交流和傳遞，冇利于發(fā)現(xiàn)較好解。 單個個體容易收斂于局部最優(yōu)，多個個體通過合作，可很快收斂于解空間的某一個子集，有 利于對解空間的進(jìn)一步探索，從而發(fā)現(xiàn)較好解。蟻群聚類算法存在的問題：1) .算法效率：蟻群聚算法的收殮過程比較緩慢特別是在迭代初期，由于系統(tǒng)參數(shù)改 變很慢，導(dǎo)致整個計算過程非常耗時在基于螞蟻覓食原理的聚類分析中，対各路徑上的信 息素的初始化，為簡化操作，一般

10、全都賦為相等的常量c(通常為0).因此信息素的值從相 等常量c開始，各條路徑上的信息素要想明顯區(qū)別開，一般需要很長時間.蟻群聚類算法與 k-means算法構(gòu)成的蟻樣聚類組合方法(kmaoc)能較好的解決這一問題。2) .初始值的選擇：初值的選擇對聚類的最終結(jié)果影響很大.而在經(jīng)典蟻群算法中，確 定初始參數(shù)時，一般缺乏已知的指導(dǎo)經(jīng)驗.初始參數(shù)的確定帶有很大的盲目性.該聚類方法中 «, 0, m的選擇對算法運行效率和聚類結(jié)果都有較人彩響，選擇不當(dāng)將影響算法執(zhí)行效率 和效果，所需時間增長等缺點可以根據(jù)情況嘗試不同的方法避免算法陷于局部最優(yōu)。本文 將重點研究m參數(shù)對算法的影響。3基木蟻群算法參

11、數(shù)及參數(shù)m研究蟻群算法屮參數(shù)在不同取值情況卜-，對算法的性能和求解效率會產(chǎn)牛重人影響。蟻群算 法是一種自適應(yīng)的、正發(fā)饋、分布式的模擬優(yōu)化算法，它在求解各復(fù)朵的組合優(yōu)化問題上表 現(xiàn)出一定的優(yōu)勢，較好的a、b、p、m組合冇較好的解質(zhì)量以及好的穩(wěn)定性，但如果對蟻 群算法的參數(shù)選擇不當(dāng)，蟻群算法較快收斂到局部最優(yōu)或較慢地收斂，對算法性能有極人的 影響何。張杰慧等在文獻(xiàn)11中就為了驗證螞蟻個數(shù)是不是越多越好的這一設(shè)想，選擇了 wpbc 數(shù)據(jù)集作為實驗數(shù)據(jù)。圖1反應(yīng)為選擇不同螞蟻數(shù)目時的實驗結(jié)果，并否認(rèn)了螞蟻數(shù)目越多 效果越好的假想，在其實驗中就取針對其實驗數(shù)據(jù)的參數(shù)m=5。圖1不同螞蟻數(shù)目的分類性能圖】

12、由具研究可見，參數(shù)m的選取不是越人越好，但也不能取之過小。在tsp實驗屮，螞 蟻數(shù)目越大越有利于求解，但是計算的迭代次數(shù)也會變大。根據(jù)實驗，螞蟻數(shù)目一般設(shè)定在 城市規(guī)模數(shù)的1/2到2/3 z間較為合適問。4基于k-means的蟻群聚類算法引入k-means作為預(yù)計算求解聚類問題的基本蟻群算法(aoc)做為一種蟻群聚類組合 方法(kmaoc)如下：stepl任選k個初始聚類中心:c, c2, c3,ck；step2逐個將數(shù)據(jù)集x屮各個數(shù)據(jù)對象按最小距離原則分配給k個聚類屮心的某一個stcp3計算新的聚類中心cj'(j=l,2,k),即c戶丄v x , k中叫為第j個聚類域$n笛包含的個數(shù)

13、；step4若cj'hcj(j=l,2,k)幾未快速分類到設(shè)定聚類效果閥值丫或是指定次數(shù)時轉(zhuǎn) step2.step5 nc <0 (nc為循環(huán)次數(shù))，由k-means算法分類結(jié)果計算出的聚類屮心 cj(j=l,2,k),計算每個樣本數(shù)據(jù)&相對應(yīng)的到不同聚類中心cj的初值 軻(0)(訂=1,2,n),.給出q、p(信息素持久)、n(螞蟻數(shù))的值，隨機給出分配方案；step6對每個螞蟻按轉(zhuǎn)移概率pij(t)選擇下一個節(jié)點；step7計算新的聚類中心,計算每個樣本數(shù)據(jù)到新的聚類中心的距離.由螞群聚類公式修 改信息素強度勺.step8若nc<預(yù)定的迭代次數(shù)且無退化行為(即找

14、到的都是相同的解)，則輸出最好的解; 否則轉(zhuǎn)step65算法測試本文采用外部評價f-mcasurc方法【舊以及總的運行時間對提出的聚類算法與k均值算 法和標(biāo)準(zhǔn)蟻樣算法進(jìn)行評價和比較。f-measure的取值在0, 1z間，取值越接近1越好。 實驗數(shù)據(jù)取于uci機器學(xué)習(xí)數(shù)據(jù)庫的wine數(shù)據(jù)集.數(shù)據(jù)集有口己的分類，可用于聚類性能 的評價。對于聚類算法的性能評價通常采川外部和內(nèi)部兩種，其依據(jù)是冇無關(guān)于數(shù)據(jù)集的先 驗知識。表1數(shù)據(jù)庫描述數(shù)據(jù)庫名稱數(shù)據(jù)大小屬性個數(shù)分類數(shù)目wine178133表2給出了 kmaoc算法參數(shù)m為8種不同取值悄況下runtime f -measure的值(取100次實驗的平均

15、值).表2參數(shù)m變化算法時間比打f-measure值參數(shù)m520406080100120140runtime10. 670. 790. 931.0000. 851. 121. 211. 43f-measure0.6950.7120.7040.7190.7140.7200.7210.721注在同一臺計算機上運行以kmaoc算法算法參數(shù)值：a=l, p=5, p=0.99, q=80, 螞蟻數(shù)m=60.迭代次數(shù)nc為200次。以其為標(biāo)準(zhǔn)時間，取值為1.當(dāng)算法參數(shù)m變化時的 runtime取值為算法參數(shù)m變化時實際運行時間/kmaoc算法參數(shù)m為60的實際運行時間 得出的比值。.實驗結(jié)果表明：對于迭

16、代次數(shù)與其它a，p，p參數(shù)収值相同情況下，kmaoc算法參 數(shù)m取值的不同其runtime與f-measure值都不同。但相比而言，對本數(shù)據(jù)集取m值為60 左右的runtime與f-measure所得值較為理想。若取m值其較小時收斂時間減少，但f-measure 也較小。若取m值較大時雖然f-measure值增大，但同時收斂時間又增大較多。由實驗可 知，根據(jù)實際問題的應(yīng)用背景，確定m值，應(yīng)選取runtime a/ f-measure取值都鮫為理想的 情況。6結(jié)束語木文對引入k-means作為預(yù)處理過程的蟻群算法(kmaoc)中參數(shù)螞蟻數(shù)m的取值 進(jìn)行了討論。提出參數(shù)取值情況應(yīng)根據(jù)不同數(shù)據(jù)對彖進(jìn)

17、行取值，對參數(shù)m取值得到了較好 的収值范圍。山于kmaoc算法較好的避免了經(jīng)典蟻群算法初始階段學(xué)習(xí)緩慢的缺點。因 而相比經(jīng)典蟻樣算法參數(shù)m取值而言，kmaoc算法的參數(shù)m取值可取得相對大些。建議 m的取數(shù)應(yīng)是聚類數(shù)的1.6至2倍間取值較好。參考文獻(xiàn)1 j handl, j knowles, m dorigo. on the performance of ant-based clusteringc.in: proc of the 3rd int conf on hybrid intelligent systems, ios press, australia,2003-12.2 韓家煒，kambe

18、r m.數(shù)據(jù)挖掘:概念與技術(shù)m.北京:機械工業(yè)出版社，2001： 223-251.3 曾洲等，蟻群算法不確定性分析j,計算機應(yīng)用,2004;10:136-138.4 陳應(yīng)顯，蟻群聚類算法中確定相鄰對彖方法的改進(jìn)j,計算機工程與應(yīng)用， 2009;45(18): 144-145邢潔清等，蟻群聚類組合方法的研究j,計算機工程與應(yīng)用，2009;45(18):146-1486楊燕等，基于閾值和蟻群算法結(jié)合的聚類方法j,西南交通人學(xué)學(xué)報，2006; 41:719723 高尚等，一種新的基于混合蟻群算法的聚類方法j,微電了學(xué)與計算機，2006;23(12):3842.8 張群，熊英，黃慶炬.基于蟻群算法的數(shù)據(jù)挖掘方法研究j.湖北工業(yè)人學(xué)學(xué) 報,2007,22:59.9 徐寧等，幾種現(xiàn)代