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

1、蟻群聚類組合方法參數(shù)m的研究韓強(qiáng)i邢潔清|1.瓊臺(tái)師范高等專科學(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ù)在不同取值情況下，常常會(huì)對(duì)算法的性能和求解效率產(chǎn)生重大影響。 本文在基于蟻群聚類組合方法的研究基礎(chǔ)上，重點(diǎn)研究了蟻群聚類組合方法kmaoc算法 中蟻群算法參數(shù)螞蟻數(shù)m對(duì)kmaoc算法性能的影響，対kmaoc算法中的參數(shù)螞蟻數(shù)m 分別取值進(jìn)行實(shí)驗(yàn)，通過兒組實(shí)驗(yàn)驗(yàn)證捉供了 kmaoc算法屮參數(shù)螞蟻數(shù)m配置的較好建 議。關(guān)鍵詞：聚類，蟻群算法，信息素，聚類組合 中圖分類號(hào)：tp311

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

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

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

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

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

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

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

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

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

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

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

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

17、行取值，對(duì)參數(shù)m取值得到了較好 的収值范圍。山于kmaoc算法較好的避免了經(jīng)典蟻群算法初始階段學(xué)習(xí)緩慢的缺點(diǎn)。因 而相比經(jīng)典蟻樣算法參數(shù)m取值而言，kmaoc算法的參數(shù)m取值可取得相對(duì)大些。建議 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.北京:機(jī)械工業(yè)出版社，2001： 223-251.3 曾洲等，蟻群算法不確定性分析j,計(jì)算機(jī)應(yīng)用,2004;10:136-138.4 陳應(yīng)顯，蟻群聚類算法中確定相鄰對(duì)彖方法的改進(jìn)j,計(jì)算機(jī)工程與應(yīng)用， 2009;45(18): 144-145邢潔清等，蟻群聚類組合方法的研究j,計(jì)算機(jī)工程與應(yīng)用，2009;45(18):146-1486楊燕等，基于閾值和蟻群算法結(jié)合的聚類方法j,西南交通人學(xué)學(xué)報(bào)，2006; 41:719723 高尚等，一種新的基于混合蟻群算法的聚類方法j,微電了學(xué)與計(jì)算機(jī)，2006;23(12):3842.8 張群，熊英，黃慶炬.基于蟻群算法的數(shù)據(jù)挖掘方法研究j.湖北工業(yè)人學(xué)學(xué) 報(bào),2007,22:59.9 徐寧等，幾種現(xiàn)代