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

1、文檔來源為：從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持.蟻群聚類組合方法參數(shù)m的研究韓強1,邢潔濤11 .瓊臺師范高等專科學(xué)校信息技術(shù)系海南?？?71100ResearchcombinationmethodofparametermbasedonantColonyClusteringHanQiang1XingJie-qing11. DepartmentofModerneducationtechnology,QiongtaiteacherscollegeHainanHaiko571100,ChinaEmail:Abstract:Theant-basedclusteringparameterv

2、aluesindifferentcircumstances,oftenwillsolvetheperformanceandefficiencyofthealgorithmhaveasignificantimpact.Inthispaper,basedonantcolonyclusteringcombinationmethodbasedonthestudy,focusingontheantcolonyclusteringalgorithmcombinationmethodKMAOCantcolonyalgorithmparametersarethenumberofmpairsofKMAOCalg

3、orithmperformanceinfluenceontheparametersofthealgorithmKMAOCthenumberofantsm,respectivelyexperimentalvaluesbyseveralgroupsofexperimentalverificationprovidesthebetterproposalthataKMAOCintalgorithmparameterstoconfigurethenumberofm.Keywords:Clustering;Antcolonyalgorithm;Pheromone;Clusteringcombination摘

4、要：蟻群算法中參數(shù)在不同取值情況下，常常會對算法的性能和求解效率產(chǎn)生重大影響。本文在基于蟻群聚類組合方法的研究基礎(chǔ)上，重點研究了蟻群聚類組合方法KMAOC算法中蟻群算法參數(shù)螞蟻數(shù)m對KMAOC算法性能的影響，對KMAOC算法中的參數(shù)螞蟻數(shù)m分別取值進行實驗，通過幾組實驗驗證提供了KMAOC算法中參數(shù)螞蟻數(shù)m配置的較好建議。關(guān)鍵詞：聚類，蟻群算法，信息素，聚類組合中圖分類號：TP311;TP12文獻標識碼：A1引言聚類在科學(xué)數(shù)據(jù)探測、圖像處理、模式識別、醫(yī)療診斷、計算生物學(xué)、文檔檢索、Web分析等領(lǐng)域起著非常重要的作用，它已經(jīng)成為當前數(shù)據(jù)挖掘研究領(lǐng)域中一個非?；钴S的研究課題1.經(jīng)典聚類方法包括分

5、層算法，劃分方法如K均值算法、模糊C均值算法，圖論聚類法，神經(jīng)網(wǎng)絡(luò)法，以及基于統(tǒng)計的方法等2.近來隨著數(shù)據(jù)挖掘研究的深入，涌現(xiàn)了大量新的聚類算法，如蟻群聚類算法等.蟻群算法作為一種開創(chuàng)性的生物仿真算法，因其具有并行性、魯棒性等優(yōu)良性質(zhì)得到了廣泛的應(yīng)用3。由于蟻群算法的研究歷史還很短，在實際問題中應(yīng)用還較少，因些存在許多有待進一步研究改進的地方，如需要設(shè)置的參數(shù)太多、參數(shù)的設(shè)置還有一定難度4。算法收斂性差和較長時間的花費.特別是運用螞蟻覓食的原理利用信息素來實現(xiàn)聚類的蟻群聚類方法，如其信息素的值從0或相等值開始，各條路徑上的信息素要想明顯區(qū)別開，一般需要很長時間。研究表明蟻群聚類算法與K-mea

6、ns算法構(gòu)成的蟻群聚類組合方法（KMAOC）能較好的彌補這些缺陷5。目前國內(nèi)基于蟻群算法的組合算法研究也進行了不少，如楊燕等在文獻6中指出為了改善聚類分析的質(zhì)量提出了一種基于閾值和蟻群算法相結(jié)合的聚類方法。按此方法，首先由基于閾值的聚類算法進行聚類，生成聚類中心，聚類個數(shù)也隨之初步確定；然后將蟻群算法的轉(zhuǎn)移概率引入K-平均算法，對上述聚類結(jié)果進行二次優(yōu)化。將上述兩種算法結(jié)合，能夠優(yōu)勢互補，避免單獨應(yīng)用一種算法時的局限性，而基金項目：瓊臺師范高等?？茖W(xué)?？蒲许椖浚ㄅ鷾侍枺簈tky2009-20）作者簡介：韓強（1982），男，助教，主要研究領(lǐng)域為計算機應(yīng)用等；邢潔清（1977），男,碩士,副教授

7、，主要研究領(lǐng)域為軟件應(yīng)用，人工智能等；高尚等在文獻7研究中提出克服從不同聚類算法的輸出結(jié)果中求共識劃分的困難，較好地改善聚類質(zhì)量。建立了聚類分析問題模型，分析了K-均值算法、模擬退火算法和基本蟻群算法的優(yōu)缺點。對蟻群算法作了改進，思路是K-均值方法混合，利用K-均值方法的結(jié)果作為初值。經(jīng)過比較測試，兩種混合蟻群算法的效果都比較好，特別混合方法二的效果最好。本文基于KMAOC蟻群聚類組合算法的研究基礎(chǔ)上僅對組合方法中螞蟻參數(shù)m值進行討論并進行實驗分析。2 K-means聚類算法與經(jīng)典蟻群算法(1)K-means算法是基于劃分的聚類方法，也是最常用的聚類算法.該算法不斷計算每個聚類的中心，也就是聚

8、類中對象的平均值，作為新的聚類種子.K-means算法試圖找出使平方誤差函數(shù)值最小的k個劃分.當結(jié)果簇密集并且各簇之間的區(qū)別明顯時，它的效果較好.處理大數(shù)據(jù)集時，K-means算法具有較好的可伸縮性和高效率8.應(yīng)用K-means聚類算法時當結(jié)果簇密集并且各簇之間的區(qū)別明顯時，它的效果較好.但區(qū)別不明顯時則效果較差.該算法的缺點是必須事先給出要生成的聚類數(shù)目。3 2)經(jīng)典蟻群聚類算法蟻群算法的特點9：1) 蟻群算法具有很強的發(fā)現(xiàn)較好解的能力。由于算法本身采用了正反饋原理，加快了進化過程，且不易陷入局部最優(yōu)解；2)蟻群算法具有很強的并行性，個體之間不斷進行信息交流和傳遞，有利于發(fā)現(xiàn)較好解。單個個體

9、容易收斂于局部最優(yōu)，多個個體通過合作，可很快收斂于解空間的某一個子集，有利于對解空間的進一步探索，從而發(fā)現(xiàn)較好解。蟻群聚類算法存在的問題5：1) .算法效率：蟻群聚算法的收殮過程比較緩慢.特別是在迭代初期，由于系統(tǒng)參數(shù)改變很慢，導(dǎo)致整個計算過程非常耗時.在基于螞蟻覓食原理的聚類分析中，對各路徑上的信息素的初始化，為簡化操作，一般全都賦為相等的常量C(通常為0).因此，信息素的值從相等常量C開始，各條路徑上的信息素要想明顯區(qū)別開，一般需要很長時間.蟻群聚類算法與K-means算法構(gòu)成的蟻群聚類組合方法(KMAOC)能較好的解決這一問題。2) .初始值的選擇：初值的選擇對聚類的最終結(jié)果影響很大.而

10、在經(jīng)典蟻群算法中，確定初始參數(shù)時，一般缺乏已知的指導(dǎo)經(jīng)驗.初始參數(shù)的確定帶有很大的盲目性.該聚類方法中“，3m的選擇對算法運行效率和聚類結(jié)果都有較大影響，選擇不當將影響算法執(zhí)行效率和效果，所需時間增長等缺點.可以根據(jù)情況嘗試不同的方法避免算法陷于局部最優(yōu)。本文將重點研究m參數(shù)對算法的影響。3基本蟻群算法參數(shù)及參數(shù)m研究蟻群算法中參數(shù)在不同取值情況下，對算法的性能和求解效率會產(chǎn)生重大影響。蟻群算法是一種自適應(yīng)的、正發(fā)饋、分布式的模擬優(yōu)化算法，它在求解各復(fù)雜的組合優(yōu)化問題上表現(xiàn)出一定的優(yōu)勢，較好的“、3、P、m組合有較好的解質(zhì)量以及好的穩(wěn)定性，但如果對蟻群算法的參數(shù)選擇不當，蟻群算法較快收斂到局部

11、最優(yōu)或較慢地收斂，對算法性能有極大的影響10。張杰慧等在文獻11中就為了驗證螞蟻個數(shù)是不是越多越好的這一設(shè)想，選擇了wpbc數(shù)據(jù)集作為實驗數(shù)據(jù)。圖1反應(yīng)為選擇不同螞蟻數(shù)目時的實驗結(jié)果，并否認了螞蟻數(shù)目越多效果越好的假想,在其實驗中就取針對其實驗數(shù)據(jù)的參數(shù)m=5。圖1不同螞蟻數(shù)目的分類性能圖11由其研究可見，參數(shù)m的選取不是越大越好，但也不能取之過小。在TSP實驗中，螞蟻數(shù)目越大越有利于求解，但是計算的迭代次數(shù)也會變大。根據(jù)實驗，螞蟻數(shù)目一般設(shè)定在城市規(guī)模數(shù)的1/2到2/3之間較為合適12。4基于K-Means的蟻群聚類算法引入K-Means作為預(yù)計算求解聚類問題的基本蟻群算法(AOC)做為一種

12、蟻群聚類組合方法(KMAOC)如下5:Stepl任選k個初始聚類中心：Ci,C2,C3,Ck；Step2逐個將數(shù)據(jù)集X中各個數(shù)據(jù)對象按最小距離原則分配給k個聚類中心的某一個Cj；1Step3計算新的聚類中心Cj(j=1,2,k),即Cj'=X,其中Nj為第j個聚類域SjNxsj包含的個數(shù)；Step4若Cj'Cj(j=1,2,k)且未快速分類到設(shè)定聚類效果閥值丫或是指定次數(shù)時轉(zhuǎn)Step2.Step5nc0(nc為循環(huán)次數(shù)),由k-means算法分類結(jié)果計算出的聚類中心Cj(j=1,2,，k),計算每個樣本數(shù)據(jù)Xi相對應(yīng)的到不同聚類中心Cj的初值賦0)(i,j=1,2,N),.給出

13、Q、p(信息素持久卜n(螞蟻數(shù))的值，隨機給出分配方案；Step6對每個螞蟻按轉(zhuǎn)移概率pj(t)選擇下一個節(jié)點；Step7計算新的聚類中心，計算每個樣本數(shù)據(jù)到新的聚類中心的距離.由螞群聚類公式修改信息素強度(t).Step8若nc預(yù)定的迭代次數(shù)且無退化行為(即找到的都是相同的解)，則輸出最好的解；否則轉(zhuǎn)Step65算法測試本文采用外部評價F-measure方法13以及總的運行時間對提出的聚類算法與K均值算法和標準蟻群算法進行評價和比較。F-measure的取值在0,1之間，取值越接近1越好。實驗數(shù)據(jù)取于UCI機器學(xué)習(xí)數(shù)據(jù)庫的Wine數(shù)據(jù)集.數(shù)據(jù)集有自己的分類，可用于聚類性能的評價。對于聚類算法

14、的性能評價通常采用外部和內(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次實驗的平均值).表2參數(shù)m變化算法時間比與F-measure值參數(shù)m520406080100120140Runtime0.670.790.931.0000.83F-measure0.6950.7120.7040.7190.7140.7200.7210.721注在同一臺計算機上運行以KMAOC算法算法參數(shù)值：”=1,3=5,尸0.99,Q=

15、80,螞蟻數(shù)m=60.迭代次數(shù)nc為200次。以其為標準時間，取值為1.當算法參數(shù)m變化時的Runtime取值為算法參數(shù)m變化時實際運行時間/KMAOC算法參數(shù)m為60的實際運行時間得出的比值。.實驗結(jié)果表明：對于迭代次數(shù)與其它%&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值

16、，應(yīng)選取Runtime與F-measure取值都較為理想的情況。6結(jié)束語本文對引入K-Means作為預(yù)處理過程的蟻群算法(KMAOC)中參數(shù)螞蟻數(shù)m的取值進行了討論。提出參數(shù)取值情況應(yīng)根據(jù)不同數(shù)據(jù)對象進行取值，對參數(shù)m取值得到了較好的取值范圍。由于KMAOC算法較好的避免了經(jīng)典蟻群算法初始階段學(xué)習(xí)緩慢的缺點。因而相比經(jīng)典蟻群算法參數(shù)m取值而言，KMAOC算法的參數(shù)m取值可取得相對大些。建議m的取數(shù)應(yīng)是聚類數(shù)的1.6至2倍間取值較好。參考文獻1 JHandl,JKnowles,MDorigo.Ontheperformanceofant-basedclusteringC.In:Procofthe3

17、rdIntConfonHybridIntelligentSystems,IOSPress,Australia,2003-12.2 韓家煒，KAMBERM.數(shù)據(jù)挖掘:概念與技術(shù)M.北京:機械工業(yè)出版社，2001：223-251.3曾洲等，蟻群算法不確定性分析J,計算機應(yīng)用，2004;10:136-138.4 陳應(yīng)顯，蟻群聚類算法中確定相鄰對象方法的改進J,計算機工程與應(yīng)用，2009;45(18):144-1455 邢潔清等，蟻群聚類組合方法的研究J,計算機工程與應(yīng)用，2009;45(18):146-1486楊燕等，基于閾值和蟻群算法結(jié)合的聚類方法J,西南交通大學(xué)學(xué)報，2006;41(6):719-7237 高尚等，一種新的基于混合蟻群算法的聚類方法J,微電子學(xué)與計算機，2006;23(12):38-42.8 張群,熊英,黃慶炬.基于蟻群算法的數(shù)據(jù)挖掘方法研究J.湖北工業(yè)大學(xué)學(xué)報,2007,22(2):5-9.9 徐寧等,幾種現(xiàn)代優(yōu)化算法的比較研究J,系統(tǒng)工程與電子技術(shù),2002