【文章內(nèi)容簡(jiǎn)介】 為代表對(duì)象(中心點(diǎn)).然后反復(fù)用非代表對(duì)象(非中心點(diǎn))代替中心點(diǎn),直到找到最合適的中心點(diǎn)。Kmeans法要求用戶(hù)必須實(shí)現(xiàn)好給出要?jiǎng)俪龅拇氐臄?shù)目，選擇初始劃分的最佳方向，更新分區(qū)和停止準(zhǔn)則。且結(jié)果與數(shù)據(jù)輸入順序有關(guān)，不同的初始值可能會(huì)導(dǎo)致不同的結(jié)果。，但不適合發(fā)現(xiàn)非凹面狀的簇。不適合大小差別較大的簇，這一方式通常首先根據(jù)距離來(lái)他調(diào)整確定類(lèi)，看然后再確定類(lèi)名，不能多維揭示其多重屬性,PAM法有效的消除了對(duì)孤立點(diǎn)數(shù)據(jù)的敏感性,比kmeans方法更強(qiáng)壯,不易受到極端數(shù)據(jù)的影響。但PAM只對(duì)小數(shù)據(jù)集非常有效(如100個(gè)對(duì)象聚成5類(lèi))，對(duì)大數(shù)據(jù)集效率并不高。（3）兩類(lèi)算法的比較為了比較兩類(lèi)算法我們選擇了幾種常用的算法列表如 表1從算法類(lèi)型，時(shí)間和空間負(fù)責(zé)性以及關(guān)于可用性幾個(gè)方面對(duì)兩類(lèi)算法進(jìn)行了比較，其中單連接，全連接和平均連接都是時(shí)間和空間復(fù)雜性O(shè)(n2)的層次算法，它們都是假定數(shù)據(jù)時(shí)一次性提供的，,但他們的時(shí)間和空間復(fù)雜性不一樣。 聚類(lèi)算法的比較算法類(lèi)型 空間時(shí)間備注單連接層次O(n2)O(kn2)非增量的平均連接層次O(n2)O(kn2)非增量的全連接層次O(n2)O(kn2)非增量的K均值劃分O(n)O(nkt)迭代的。非類(lèi)別PAM劃分O(n2)O(tk(nk)2)迭代的。自適應(yīng)凝聚,異常點(diǎn)傳統(tǒng)的聚類(lèi)已經(jīng)比較成功的解決了低維數(shù)據(jù)的聚類(lèi)問(wèn)題。但是由于實(shí)際應(yīng)用中數(shù)據(jù)的復(fù)雜性，在處理許多問(wèn)題時(shí)，現(xiàn)有的算法經(jīng)常失效，特別是對(duì)于高維數(shù)據(jù)和大型數(shù)據(jù)的情況。因?yàn)閭鹘y(tǒng)聚類(lèi)方法在高維數(shù)據(jù)集中進(jìn)行聚類(lèi)時(shí)，主要遇到兩個(gè)問(wèn)題。①高維數(shù)據(jù)集中存在大量無(wú)關(guān)的屬性使得在所有維中存在簇的可能性幾乎為零；②高維空間中數(shù)據(jù)較低維空間中數(shù)據(jù)分布要稀疏，其中數(shù)據(jù)間距離幾乎相等是普遍現(xiàn)象，而傳統(tǒng)聚類(lèi)方法是基于距離進(jìn)行聚類(lèi)的，因此在高維空間中無(wú)法基于距離來(lái)構(gòu)建簇。 主要聚類(lèi)蟻群算法計(jì)算機(jī)科學(xué)領(lǐng)域內(nèi)的研究者受自然界生物的啟發(fā)設(shè)計(jì)出新的有效算法，典型的例子為人工神經(jīng)網(wǎng)絡(luò)和機(jī)器人控制，作為人工免疫系統(tǒng)用在網(wǎng)絡(luò)安全系統(tǒng)中，另一典型的例子為重要的啟發(fā)式優(yōu)化方法，如進(jìn)化算法和模擬退火算法。，由此形成的蟻群算法成功的應(yīng)用于解決多個(gè)經(jīng)典的組合優(yōu)化問(wèn)題。由于螞蟻等群居類(lèi)昆蟲(chóng)具有分布式、自組織、信息素(pheromone)通信、合作等性能，模擬其智能行為的蟻群算法能夠解決許多復(fù)雜的問(wèn)題， 聚類(lèi)蟻群算法分類(lèi) 螞蟻行為 相應(yīng)的算法 螞蟻覓食 螞蟻聚類(lèi)算法 螞蟻?zhàn)晕揖奂? AntTree算法 螞蟻堆積尸體 AntClass算法 螞蟻構(gòu)建巢穴 AntClust算法 因此對(duì)它的研究逐漸受到越來(lái)越多的學(xué)者的關(guān)注，并提出許多聚類(lèi)蟻群算法。隨著蟻群算法研究的興起，人們發(fā)現(xiàn)在某些方面采用蟻群模型進(jìn)行聚類(lèi)更加接近實(shí)際的聚類(lèi)問(wèn)題。基于蟻群算法的聚類(lèi)方法從原理上主要分為一下幾類(lèi)：(1)運(yùn)用螞蟻覓食原理，利用信息素來(lái)實(shí)現(xiàn)聚類(lèi)[26]；(2)利用螞蟻?zhàn)晕揖奂袨榫垲?lèi)的；(3)基于螞蟻堆的形成原理實(shí)現(xiàn)數(shù)據(jù)聚類(lèi)；(4)運(yùn)用巢穴分類(lèi)模型，利用螞蟻化學(xué)識(shí)別系統(tǒng)進(jìn)行聚類(lèi)的。這些聚類(lèi)算法與傳統(tǒng)的算法最為不同的是具有極高的問(wèn)題獨(dú)立性。傳統(tǒng)的算法大都是伴隨著某一特定的問(wèn)題模式，有著相當(dāng)多的限制條件，而聚類(lèi)蟻群算法則沒(méi)有這些缺點(diǎn)。 K均值混合聚類(lèi)算法基于蟻群的聚類(lèi)算法是一種自組織聚類(lèi)算法，具備健壯性，可視化等特點(diǎn)，并能生成一些新的有意義的聚類(lèi)模式。但是由于算法有時(shí)收斂時(shí)間較長(zhǎng)，而且常常出現(xiàn)一些有一個(gè)模式組成的聚類(lèi)中心，雖然這些模式可以用于孤立點(diǎn)（outlier）分析，但是對(duì)于一般要求的聚類(lèi)分析，聚類(lèi)中心過(guò)多過(guò)散并沒(méi)有好處。于是2000年Monmarche在聚類(lèi)蟻群算法的基礎(chǔ)上，結(jié)合標(biāo)準(zhǔn)K均值算法，提出一種蟻群混合聚類(lèi)算法[28]，稱(chēng)為AntClass算法。利用這種方法擺脫了大多數(shù)聚類(lèi)方法對(duì)數(shù)據(jù)的聚類(lèi)基本特征先驗(yàn)信息的依賴(lài)，通過(guò)兩階段的算法結(jié)構(gòu)即可實(shí)現(xiàn)對(duì)數(shù)據(jù)的聚類(lèi)。首先利用蟻群算法實(shí)現(xiàn)對(duì)數(shù)據(jù)的初始聚類(lèi)，在此過(guò)程結(jié)束后，以當(dāng)前獲得聚類(lèi)信息作為K均值的初始劃分，從而提高劃分的正確性。然后，將第一步處理結(jié)束時(shí)未分配至任何數(shù)據(jù)簇中的個(gè)別數(shù)據(jù)逐一歸入相應(yīng)的簇中，這種方法避免了隨機(jī)的或預(yù)設(shè)的初始化數(shù)據(jù)劃分，通過(guò)隨機(jī)搜索形成類(lèi)簇，提高了初始類(lèi)的準(zhǔn)確性和算法整體的穩(wěn)健性。無(wú)論在BM模型中還是在LF算法中，每個(gè)網(wǎng)格內(nèi)只能放一個(gè)對(duì)象，螞蟻也只能拾起或放下一個(gè)對(duì)象。而在混合聚類(lèi)算法中，Monmarche建議一個(gè)網(wǎng)格單元內(nèi)可以放置多個(gè)對(duì)象，每只螞蟻的搬運(yùn)能力為，代替過(guò)去一只螞蟻一次只能搬運(yùn)一個(gè)對(duì)象。概率性的從一個(gè)堆上最多拾起對(duì)象為，并且往堆上丟下對(duì)象時(shí)要根據(jù)堆的特性，如堆中對(duì)象間的平均相異度。當(dāng)螞蟻決定拾起對(duì)象時(shí)，挑選那些與堆中心對(duì)象相異度最大的對(duì)象。此時(shí)螞蟻的運(yùn)載能力有兩種情況或，即可以搬運(yùn)一個(gè)對(duì)象，也可以是整個(gè)堆[29]?；旌暇垲?lèi)算法AntClass主要包括四個(gè)步驟：（1）在所要聚類(lèi)的對(duì)象上進(jìn)行聚類(lèi)蟻群；（2）利用初始劃分結(jié)果進(jìn)行K均值算法；（3）在堆上運(yùn)用聚類(lèi)蟻群；（4）對(duì)對(duì)象堆再次運(yùn)用K均值算法。最初利用基于螞蟻算法來(lái)形成初始的簇。由于劃分時(shí)間太長(zhǎng)，所以在算法收斂之前就終止了算法，致使創(chuàng)建的劃分存在錯(cuò)誤劃分，所以使用K均值算法除去小的分類(lèi)錯(cuò)誤，并分配“自由”對(duì)象，即算法停止時(shí)仍然有單獨(dú)存在單元上的對(duì)象或螞蟻仍在搬運(yùn)的對(duì)象。這雖然能除去分類(lèi)中的錯(cuò)誤，但是K均值算法是局部?jī)?yōu)化算法，不能得到高質(zhì)量的簇，所以需要再次利用基于螞蟻的算法。這次是對(duì)對(duì)象堆上而不是單個(gè)對(duì)象運(yùn)用算法.。前面基于螞蟻的算法同樣適用于堆，這些堆可以像單個(gè)對(duì)象那樣再次被拾起或放下，再次構(gòu)成新的簇。但像前面那樣仍然有未分配的堆，因而再次使用K均值算法來(lái)獲得最終的劃分。這次因?yàn)樘峁┙oK均值的輸入已經(jīng)很接近最佳了，所以輸出的結(jié)果質(zhì)量很高。與這個(gè)方法相似的另一種是與模糊C均值相結(jié)合的方法[30]，基于相對(duì)簡(jiǎn)單智能體直接或間接的反饋完成聚類(lèi)。 基于螞蟻覓食原理的聚類(lèi)算法 “物以類(lèi)聚，人以群分”是自然界的普遍現(xiàn)象，聚類(lèi)分析是根據(jù)這一現(xiàn)象經(jīng)過(guò)抽象發(fā)展起來(lái)的一種數(shù)學(xué)分析方法。人們發(fā)現(xiàn)在聚類(lèi)中有一種類(lèi)似于“能量場(chǎng)”的特點(diǎn)，即人們會(huì)首先確定一個(gè)核心，即聚類(lèi)中心，然后將周?chē)膶?duì)象“吸引”（歸并）到該核心的周?chē)瑥亩瓿删垲?lèi)過(guò)程。通過(guò)分析仿生學(xué)家的研究結(jié)果表明，螞蟻個(gè)體之間是通過(guò)一種稱(chēng)之為信息素（pheromone）的物質(zhì)進(jìn)行信息傳遞，從而能相互協(xié)作，完成復(fù)雜的任務(wù)。螞蟻在運(yùn)動(dòng)過(guò)程中，能夠在它所經(jīng)過(guò)的路徑上留下信息素，而且螞蟻在運(yùn)動(dòng)過(guò)程中能感知信息素的存在及其強(qiáng)度，并指導(dǎo)自己運(yùn)動(dòng)方向，螞蟻傾向于朝著信息素強(qiáng)度高的方向上移動(dòng)。因此，有大量螞蟻組成的蟻群的集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過(guò)的螞蟻越多，后面的螞蟻選擇該路徑的概率就越大。螞蟻個(gè)體間就是通過(guò)這種信息交流完成搜索食物。螞蟻的覓食過(guò)程可以分為搜索食物和搬運(yùn)食物兩個(gè)環(huán)節(jié)[31]。螞蟻覓食原理應(yīng)用到數(shù)據(jù)聚類(lèi)中，可以將數(shù)據(jù)視為具有不同屬性的螞蟻，聚類(lèi)中心既是螞蟻所要尋找的“食物源”，那么數(shù)據(jù)聚類(lèi)過(guò)程可以看作螞蟻尋找食物源的過(guò)程。 螞蟻能夠通過(guò)自我聚集行為構(gòu)建一個(gè)樹(shù)狀結(jié)構(gòu)，稱(chēng)之為螞蟻樹(shù)(AntTree)[34]。用螞蟻表示數(shù)據(jù)并代表該樹(shù)的節(jié)點(diǎn)，初始時(shí)螞蟻放在一個(gè)稱(chēng)為支點(diǎn)的固定點(diǎn)上，這個(gè)點(diǎn)相當(dāng)于樹(shù)根。螞蟻在這棵樹(shù)上或已經(jīng)固定在樹(shù)上的螞蟻身上移動(dòng)，來(lái)尋找適合自己的位置。假設(shè)螞蟻能夠到達(dá)樹(shù)的任何地方并能粘在該結(jié)構(gòu)的任何位置，不過(guò)在結(jié)構(gòu)樹(shù)形成的過(guò)程中由于受對(duì)象間的作用，螞蟻更趨于固定在樹(shù)枝的末端[3536]。樹(shù)的局部結(jié)構(gòu)及螞蟻表示的數(shù)據(jù)之間的相似性引導(dǎo)它的移動(dòng)，當(dāng)所有螞蟻都在樹(shù)上固定下來(lái)后，算法結(jié)束，獲得對(duì)數(shù)據(jù)集的劃分。 人工螞蟻構(gòu)建螞蟻樹(shù)的基本原理 General principles of tree building with artificial ants 為了更好描述算法過(guò)程,采用螞蟻表示的數(shù)據(jù)代表樹(shù)中的每個(gè)節(jié)點(diǎn)，用歐氏距離作為相似度尺度，用表示。 AntTree主要算法 Main algorithm of AntTree 其中表示每個(gè)數(shù)據(jù)對(duì)象的屬性值，表示數(shù)據(jù)對(duì)象的第個(gè)屬性。每對(duì)數(shù)據(jù)的相似度值在之間（表示數(shù)據(jù)集內(nèi)的對(duì)象個(gè)數(shù)），0意味著完全不同，1表示他們相同。 節(jié)點(diǎn)表示樹(shù)根，螞蟻逐步連接到這個(gè)初始節(jié)點(diǎn)上或連接到固定在該節(jié)點(diǎn)的螞蟻上，直到所有的螞蟻均連接到結(jié)構(gòu)上(螞蟻樹(shù)的停止標(biāo)準(zhǔn))。移動(dòng)的螞蟻根據(jù)值和它的局部鄰居決定自身的位置，計(jì)算螞蟻的鄰居。每只螞蟻只有一個(gè)父親結(jié)點(diǎn)，最多有個(gè)孩子結(jié)點(diǎn)。對(duì)每只螞蟻都定義一個(gè)相似度閥值和相異度閥值，并且由進(jìn)行局部更新，用來(lái)判斷螞蟻表示的數(shù)據(jù)與其它螞蟻表示的數(shù)據(jù)的相似或相異程度。 基于化學(xué)識(shí)別系統(tǒng)的聚類(lèi)蟻群算法現(xiàn)實(shí)中的螞蟻為了保護(hù)自己的巢穴不被敵人或食客攻擊破壞，必須具有區(qū)別伙伴和敵方的能力，它是靠識(shí)別群體間的氣味來(lái)實(shí)現(xiàn)的。當(dāng)兩只螞蟻相遇時(shí)分別檢查對(duì)方表皮所散發(fā)的氣味(也叫標(biāo)簽)，并與自身的模板比較。模板是螞蟻在幼年時(shí)期有群體中成年螞蟻喂養(yǎng)時(shí)通過(guò)身體接觸而獲得的，并在成長(zhǎng)過(guò)程中不斷更新。標(biāo)簽是由螞蟻基因及螞蟻間不斷交換化學(xué)物質(zhì)決定的。同伴間通過(guò)不斷交換化學(xué)物質(zhì)建立群體氣味，該氣味可以被每個(gè)伙伴識(shí)別，不同群體具有不同的氣味，同一群體分享相同的氣味，這就是所謂的“群體圈”，也是化學(xué)識(shí)別系統(tǒng)的基本原理。2002年Labroche等提出叫做螞蟻簇(AntClust)的聚類(lèi)方法，主要是利用化學(xué)識(shí)別系統(tǒng)原理來(lái)聚類(lèi)的。為了更好的說(shuō)明這個(gè)方法，給每只螞蟻定義如下參數(shù)：由螞蟻巢穴的屬性決定的標(biāo)簽，可以代表巢，開(kāi)始螞蟻不受任何巢穴的影響，所以，隨后標(biāo)簽不斷變換直到螞蟻找到最好的巢為止。模板是由螞蟻的基因和接受閥值組成的，前者對(duì)應(yīng)于數(shù)據(jù)集的對(duì)象且在算法過(guò)程中不斷變化，后者是在初始化階段獲得的，它是螞蟻與其它螞蟻相遇期間觀察到的最大相似度和平均相似度的函數(shù)，它是動(dòng)態(tài)的，螞蟻每次和其它螞蟻相會(huì)后對(duì)它進(jìn)行修改[3942]。 評(píng)價(jià)因子反映螞蟻間的相遇情況。相同標(biāo)簽的螞蟻相遇時(shí)增加，反之減少。開(kāi)始時(shí)，它反映螞蟻所在巢穴的規(guī)模。表示螞蟻被接受程度，如果具有相同標(biāo)簽的螞蟻相遇或兩只螞蟻彼此接受對(duì)方，增加，否則螞蟻不接受時(shí)減少。螞蟻接受與否可根據(jù)下面公式判斷，設(shè), 分別表示兩只螞蟻，則： 螞蟻相遇規(guī)則：(1) 兩只均沒(méi)有巢的螞蟻相遇并彼此接受時(shí)將創(chuàng)建一個(gè)新的巢，即產(chǎn)生初始簇，并作為“種子”聚集相似螞蟻以便產(chǎn)生最終的簇；(2) 沒(méi)有巢的螞蟻遇到有巢的螞蟻并且可以被接受時(shí)，沒(méi)有巢的螞蟻加入該巢內(nèi)，這個(gè)規(guī)則可以擴(kuò)大現(xiàn)存的簇；(3) 屬于同一個(gè)巢的螞蟻在彼此接受的情況下增加評(píng)價(jià)因子和，螞蟻依據(jù)感知其巢的大小，根據(jù)感知其與巢中其它螞蟻的接受度，該規(guī)則使巢變得更健壯；(4) 同巢的兩個(gè)螞蟻相遇且不能彼此接受，減少，當(dāng)小于一定程度該螞蟻的標(biāo)簽和重新被置為0，這時(shí)就被當(dāng)作“異類(lèi)”遭到排斥，將從巢中被驅(qū)除出去，使巢變得更完美；(5) 不同巢的螞蟻相遇且彼此接受時(shí)，合并它們的巢，即合并相似的簇，小簇被大簇吸收。算法結(jié)束時(shí)螞蟻集中在有限數(shù)目的巢內(nèi)，巢就是期望得到的劃分。 小結(jié)本節(jié)查找的研究資料為基礎(chǔ)，首先介紹了蟻群算法的基本模型，簡(jiǎn)單的構(gòu)建的蟻群算法的數(shù)學(xué)模型，其次介紹了聚類(lèi)分析的概念，它是數(shù)據(jù)挖掘技術(shù)里面一個(gè)非常重要的工具，還講述了一些關(guān)于聚類(lèi)算法的一些分類(lèi)，并且對(duì)比了它們的算法復(fù)雜度，最后重點(diǎn)分析了現(xiàn)在比較流行的聚類(lèi)蟻群算法，將蟻群模型和聚類(lèi)分析結(jié)合起來(lái)，針對(duì)每種方法分別從它的基本原理、設(shè)計(jì)思路、基本特性及主要步驟等進(jìn)行了論述與分析。根據(jù)對(duì)象的空間分布狀態(tài)指導(dǎo)螞蟻間的相互作用完成聚類(lèi)的，如基于螞蟻堆的形成原理的聚類(lèi)方法都是根據(jù)對(duì)象在網(wǎng)格上的分布情況實(shí)現(xiàn)的；其中基于螞蟻的混合聚類(lèi)方法，交替使用聚類(lèi)蟻群方法和kmeans算法，加速算法收斂并提高了聚類(lèi)質(zhì)量。聚類(lèi)蟻群方法具有許多特有的特性，如靈活性、健壯性、分布性和自組織性等，這些特性使其非常適合本質(zhì)上是分布、并行的問(wèn)題求解中，能解決無(wú)人監(jiān)督的聚類(lèi)問(wèn)題，具有廣闊的前景。下一節(jié)將重點(diǎn)研究基本并行性的聚類(lèi)蟻群算法3 并行算法概述 并行計(jì)算機(jī)并行計(jì)算機(jī)是能在同一時(shí)間內(nèi)執(zhí)行多條指令或處理多條數(shù)據(jù)的計(jì)算機(jī)，并行計(jì)算機(jī)是并行計(jì)算的物理載體根據(jù)指令流和數(shù)據(jù)流不同，通常把并行計(jì)算機(jī)系統(tǒng)分為4類(lèi)：（1）單指令流單數(shù)據(jù)流(SISD)；（2）單指令流多數(shù)據(jù)流(SIMD)；（3）多指令流單數(shù)據(jù)流(MISD)；（4）多指令流多數(shù)據(jù)流(MIMD)。SISD實(shí)際上是普通的順序執(zhí)行的串行計(jì)算機(jī)，SIMD和MIMD是2種典型的并行計(jì)算機(jī)，而MISD在實(shí)際上代表何種并行計(jì)算機(jī)在學(xué)術(shù)上沒(méi)有一致的意見(jiàn)。并行計(jì)算機(jī)系統(tǒng)除了少數(shù)的專(zhuān)用SIMD系統(tǒng)外，絕大部分是MIMD系統(tǒng)。（MI～f1)結(jié)構(gòu)的并行計(jì)算機(jī)包括并行向量處理機(jī)(PVP)、對(duì)稱(chēng)多處理機(jī)(SMP)、大規(guī)模并行處理機(jī)(MPP)、機(jī)群(Cluster)、分布式共享存儲(chǔ)器計(jì)算機(jī)(DSM)。 并行算法并行算法是指適合做各種并行計(jì)算機(jī)上求解問(wèn)題的算法。并行算法是可同時(shí)執(zhí)行的進(jìn)程的集合，這些進(jìn)程相互作用，協(xié)調(diào)處理，從而實(shí)現(xiàn)對(duì)給定問(wèn)題的求解。并行算法可以分為數(shù)值并行算法和非數(shù)值并行算法，或同步并行算法以及異步并行算法和分布式并行算法，或SI肋／MI如并行算法和VLSI并行算法等。數(shù)值并行算法是指基于代數(shù)運(yùn)算的問(wèn)題的求解算法(如矩陣運(yùn)算、多項(xiàng)式求值、解線(xiàn)性方程組等)。非數(shù)值并行算法是指基于關(guān)系運(yùn)算的問(wèn)題的求解算法(如排序、查找、遍歷等)。同步并行算法是指某些進(jìn)程必須等待其它進(jìn)程的并行算法，全部進(jìn)程均同步在一個(gè)給定的時(shí)鐘上，以等待最慢的進(jìn)程結(jié)束。運(yùn)行在SIMD機(jī)器模型上的并行算法屬于同步并行算法，其處理機(jī)之間的同步由硬件實(shí)