離差最大化賦權(quán)的蟻群聚類算法

張新建

摘 要： 受螞蟻覓食過程啟發(fā)的聚類算法又被稱為蟻群聚類算法，把覓食行為分為搜索食物和搬運(yùn)食物兩個(gè)環(huán)節(jié)，把數(shù)據(jù)對(duì)象視為螞蟻，把聚類中心視為“食物源”，這樣數(shù)據(jù)對(duì)象的聚類過程就可以轉(zhuǎn)化為螞蟻覓食過程，但在該算法中沒有區(qū)分?jǐn)?shù)據(jù)對(duì)象不同屬性的重要性，通過采用離差最大化方法，根據(jù)每個(gè)屬性的重要性賦予它一個(gè)權(quán)值，從而改進(jìn)了原算法中的距離計(jì)算，使得相似的數(shù)據(jù)對(duì)象能快速的聚集到一起，提高了算法的運(yùn)行效率。

關(guān)鍵詞： 聚類算法； 蟻群算法； 離差； 權(quán)值

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2017）09-01-04

Abstract： Clustering algorithm inspired by the foraging process called ant colony clustering algorithm， the foraging behavior is divided into two aspects， food searching and food handling， the data object as an ant， the cluster center as a "food source"， so the clustering process of data objects can be converted to the ant foraging process， but did not distinguish between the importance of the different attributes of the data objects in the algorithm， this paper uses the maximum deviation method for each attribute according to its importance as it gives a weight， which improves the original algorithm in the distance calculation， makes similar objects fast together， and improves the efficiency of the algorithm.

Key words： clustering algorithm； ant colony algorithm； deviation； weigh

0 引言

通過對(duì)自然界中螞蟻尋找食物過程的觀察，學(xué)者們發(fā)現(xiàn)實(shí)際上整個(gè)尋找食物的過程可以簡(jiǎn)單地分為兩個(gè)環(huán)節(jié)：搜索食物和搬運(yùn)食物。螞蟻在尋找食物時(shí)不論是在搜索食物環(huán)節(jié)還是在搬運(yùn)食物環(huán)節(jié)，都會(huì)在它所經(jīng)過的路徑上釋放一定量的信息素，這種信息素的強(qiáng)度可以被其他螞蟻所感知到，同時(shí)信息素本身也具有一定的揮發(fā)性，即它的強(qiáng)度會(huì)隨著時(shí)間的推移而慢慢減弱以至消失。自然界中螞蟻不僅可以感知到信息素的強(qiáng)弱，也具有追逐信息素的傾向，即如果某條路徑上信息素的強(qiáng)度很高，那么螞蟻在選擇路徑時(shí)，選擇這條路徑的概率就很大。信息素對(duì)螞蟻選擇路徑行為的影響通過螞蟻群體行為的放大就可以表現(xiàn)出一種正反饋現(xiàn)象，即如果某條路徑上信息素強(qiáng)度高于其他路徑，那么螞蟻就會(huì)以較高的概率選擇此路徑，同時(shí)鑒于螞蟻在運(yùn)動(dòng)時(shí)也會(huì)在路徑上釋放一定量的信息素，因此該路徑上的信息素強(qiáng)度會(huì)逐漸增強(qiáng)，而隨著信息素強(qiáng)度的增強(qiáng)，它又會(huì)對(duì)其他螞蟻散發(fā)出更大的吸引力，會(huì)吸引更多的螞蟻通過此路徑；而其他路徑則因?yàn)橹挥休^少螞蟻通過，信息素強(qiáng)度得不到增強(qiáng)，同時(shí)又因?yàn)榭諝鈸]發(fā)作用使得信息素強(qiáng)度逐漸降低，使得該路徑對(duì)螞蟻的吸引力愈加低下，經(jīng)過一段時(shí)間之后螞蟻甚至?xí)巴洝痹撀窂降拇嬖?。螞蟻的這種通過信息素在彼此之間進(jìn)行信息交流的群體行為可以應(yīng)用在聚類算法之中。下面對(duì)基于螞蟻覓食原理的聚類算法的基本思想[1]進(jìn)行簡(jiǎn)單的介紹。

如果將待聚類的數(shù)據(jù)對(duì)象看成是螞蟻，而算法所要尋求的聚類中心看成是螞蟻所要尋找的“食物源”，那么就可以把數(shù)據(jù)聚類過程轉(zhuǎn)化為螞蟻尋找食物源的過程。假設(shè)待聚類的數(shù)據(jù)對(duì)象為：X={X|Xi（xi1，xi2，…，xim），i=1，2，…，N}，對(duì)算法進(jìn)行初始化，將各條路徑上的信息素初始化為0，即τij（0）=0，設(shè)置聚類簇的半徑r、統(tǒng)計(jì)誤差ε、概率閾值P0，以及α、β等參數(shù)。

1 離差最大化賦權(quán)算法

1.1 多屬性決策

多屬性決策是多目標(biāo)方案決策的一種，又稱有限方案多目標(biāo)決策，它是對(duì)具有多個(gè)屬性的有限方案，按照某種決定準(zhǔn)則進(jìn)行多方案選擇和排序。其理論方法已被廣泛地應(yīng)用于社會(huì)、經(jīng)濟(jì)、管理、軍事等領(lǐng)域，其求解方法和屬性權(quán)重有密切的關(guān)系。因?yàn)樗暮侠硇灾苯佑绊懼鄬傩詻Q策排序的準(zhǔn)確性，所以在多屬性決策中，權(quán)重問題的研究占有重要的地位。

1.2 離差最大化賦權(quán)算法

離差最大化賦權(quán)法是王應(yīng)明1998年在文獻(xiàn)[2]中提出的，到目前為止，在多屬性決策模型中它的應(yīng)用已經(jīng)比較廣泛了[3]。它是從對(duì)各方案排序的角度出發(fā)，認(rèn)為若各個(gè)方案的某個(gè)屬性值沒有差別，則該屬性對(duì)于方案排序?qū)⒉黄鹱饔茫诙鄬傩詻Q定中該屬性的意義就不大。所以，屬性對(duì)于各個(gè)方案而言差異越大，則該屬性在方案排序過程中的區(qū)分度越大，屬性越重要，應(yīng)該賦予該屬性較大的權(quán)重。

文獻(xiàn)[4]給出了離差最大化賦權(quán)法的計(jì)算過程。首先對(duì)樣本集的全體X作如下表示，即，其中是第j個(gè)樣本的第t個(gè)特征的賦值。

設(shè)特征的權(quán)向量為并滿足。

通常來說，需要進(jìn)行聚類處理的數(shù)據(jù)對(duì)象都包含兩個(gè)或者多個(gè)屬性，數(shù)據(jù)對(duì)象正是由對(duì)這些屬性進(jìn)行取值形成的，這些屬性反映了數(shù)據(jù)對(duì)象在某些方面的特征，而屬性的取值則是數(shù)據(jù)對(duì)象的本身特征的量化表示。因此對(duì)數(shù)據(jù)對(duì)象進(jìn)行聚類處理也就是對(duì)數(shù)據(jù)對(duì)象的屬性進(jìn)行處理，也就是說聚類處理的結(jié)果是由數(shù)據(jù)對(duì)象的屬性所決定的。數(shù)據(jù)對(duì)象具有多個(gè)屬性，每個(gè)屬性反映的是某方面的特征的信息，就屬性本身而言所有的屬性都是平等的，沒有主次之分，它們都是數(shù)據(jù)對(duì)象本身信息的客觀反映。然而每個(gè)屬性的取值范圍又是不同的，也就是說不同數(shù)據(jù)對(duì)象在同一個(gè)屬性上的取值，差異性大小是不同的，差異越小，表明數(shù)據(jù)對(duì)象之間在該屬性下的相異度較小，差異越大，則表明數(shù)據(jù)對(duì)象之間在該屬性下相異度較大，因此影響樣本Xj屬于某一類蔟的概率主要取決于每個(gè)樣本在同一屬性下賦值上的差異程度。endprint

由⑽式可知，數(shù)據(jù)對(duì)象的每個(gè)屬性的權(quán)重是在這個(gè)屬性下樣本之間的離差與所有屬性下樣本之間的總離差的比值。因此如果在某個(gè)屬性下樣本之間的離差越大，表明這類數(shù)據(jù)對(duì)象在這個(gè)屬性上的差異性很大，則該屬性對(duì)聚類結(jié)果的影響就越大，即它的權(quán)重就大，反之則小。由⑽式給出的權(quán)重的計(jì)算公式，容易計(jì)算，所得到的權(quán)重也能客觀真實(shí)的反映每個(gè)樣本屬性在聚類中貢獻(xiàn)。

2 基于離差最大化賦權(quán)的蟻群聚類算法

2.1 屬性權(quán)重對(duì)算法聚類結(jié)果的影響

2.1.1 對(duì)特征屬性進(jìn)行賦權(quán)的必要性分析

在聚類算法中經(jīng)常被使用的數(shù)據(jù)對(duì)象間的距離表示的是數(shù)據(jù)對(duì)象之間的相近程度，而事實(shí)上，相似不僅依賴于對(duì)象間的相近程度，還依賴于對(duì)象內(nèi)在的性質(zhì)，而對(duì)象內(nèi)在的性質(zhì)是通過它的屬性表示出來的，因此對(duì)象中每個(gè)屬性變量的重要性是不同的，因此在多屬性數(shù)據(jù)對(duì)象之間的距離計(jì)算中，不同的屬性很顯然對(duì)數(shù)據(jù)對(duì)象的內(nèi)在性質(zhì)有不同的貢獻(xiàn)，有的屬性很重要，而有的屬性則并不重要，甚至可有可無，它表明數(shù)據(jù)的各個(gè)不同的特征屬性對(duì)數(shù)據(jù)性質(zhì)的影響程度即對(duì)聚類結(jié)果的貢獻(xiàn)程度是不同，因此這需要算法在計(jì)算的時(shí)候體現(xiàn)出來，即在可以通過對(duì)不同的屬性變量賦予不同權(quán)重的方式來解決，即對(duì)每個(gè)變量根據(jù)其重要程度賦一個(gè)權(quán)重，

在算法對(duì)數(shù)據(jù)對(duì)象進(jìn)行聚類分析時(shí)，數(shù)據(jù)對(duì)象屬性個(gè)數(shù)的增加會(huì)使算法的計(jì)算量急劇膨脹，從而降低算法運(yùn)行的效率。因此在進(jìn)行聚類時(shí)合理地運(yùn)用加權(quán)歐氏距離，根據(jù)每個(gè)屬性對(duì)聚類結(jié)果貢獻(xiàn)的不同，給每個(gè)屬性賦一個(gè)權(quán)值，這樣既可以充分利用數(shù)據(jù)的分布特征，從而加快某些聚類算法的速度，同時(shí)又可以更準(zhǔn)確的反映數(shù)據(jù)對(duì)象的內(nèi)在性質(zhì)，進(jìn)而提高聚類結(jié)果的準(zhǔn)確性，對(duì)改進(jìn)聚類結(jié)果能起到較好的效果。

2.1.2 權(quán)重的設(shè)置方法

較常使用的加權(quán)方法有以下幾種：德爾菲（Delphi）法、層次分析（Analytic Hierarchy Process， AHP）法以及模糊聚類分析法。德爾菲法和AHP法都是基于專家群體的知識(shí)、經(jīng)驗(yàn)和價(jià)值判斷。盡管AHP法中對(duì)專家的主觀判斷做了數(shù)學(xué)處理，但專家知識(shí)的局限性并未消除，這兩種方法都存在一定的主觀性。模糊聚類分析法是基于樣本模糊數(shù)據(jù)的相似性對(duì)評(píng)價(jià)指標(biāo)群體做出相對(duì)重要程度分類，但該方法不能確定單個(gè)屬性的權(quán)重。

數(shù)據(jù)對(duì)象的屬性對(duì)于聚類任務(wù)非常重要。數(shù)據(jù)集用可分性越好的屬性子集來描述，具有相同類別的數(shù)據(jù)對(duì)象越集中，而不同類別的數(shù)據(jù)對(duì)象之間則相距越遠(yuǎn)。表現(xiàn)在數(shù)據(jù)分布圖上就是同類的數(shù)據(jù)對(duì)分布較為集中，而類與類之間的距離則比較大。

在多屬性數(shù)據(jù)對(duì)象的距離計(jì)算中，不同的屬性很顯然對(duì)數(shù)據(jù)對(duì)象的性質(zhì)有不同的影響。在本文第1章中介紹的離差最大化賦權(quán)算法，可以根據(jù)數(shù)據(jù)對(duì)象各屬性重要性的不同，計(jì)算出不同的權(quán)值，從而能夠客觀的反映數(shù)據(jù)對(duì)象的情況，這正好滿足了聚類運(yùn)算的目的，即客觀地反映出數(shù)據(jù)集中所隱藏的信息。

2.2 改進(jìn)后的算法

基于覓食的蟻群聚類算法利用了蟻群的分布式搜索的特性，因此相比于經(jīng)典的k-means算法，它改善了算法過早的陷入局部最優(yōu)的缺陷，但是在蟻群聚類算法進(jìn)行計(jì)算的時(shí)候，并沒有對(duì)各個(gè)特征屬性的重要性加以區(qū)分，因而不能有差異的反映各個(gè)屬性對(duì)聚類結(jié)果的不同影響。

本文將離差最大化賦權(quán)算法應(yīng)用于基于螞蟻覓食原理的聚類算法中對(duì)數(shù)據(jù)對(duì)象的屬性的權(quán)值的計(jì)算中，從而給不同的屬性賦予不同的權(quán)重，突出重要屬性的影響，同時(shí)弱化非重要屬性的影響，從而更快更好的獲得聚類結(jié)果。

2.2.1 改進(jìn)后的算法流程

Step 1 初始化聚類中心，設(shè)定參數(shù)N，m，r，ε0，α，β，ρ0

Step 2 求出上文介紹的加權(quán)向量ωk（k=1，2，…，m）

Step 3 計(jì)算樣本Xi到Xj之間的加權(quán)歐氏距離

Step 4 計(jì)算各路徑上的信息量：

Step 5 對(duì)象Xi合并到Xj的概率為：

Step 6 判斷是否成立，若成立則將Xi合并到Xj的鄰域。

Step 7 計(jì)算歸并Xj領(lǐng)域的數(shù)據(jù)集合的聚類中心。

Step 8 計(jì)算第j個(gè)聚類的偏離誤差：

其中cji表示第j個(gè)聚類中心的第i個(gè)分量。

Step 9 計(jì)算總體誤差

Step 10 判斷若成立，則停止，并輸出聚類個(gè)數(shù)；否則，轉(zhuǎn)步驟Step 3繼續(xù)迭代。

2.2.2 仿真實(shí)驗(yàn)及分析

為了驗(yàn)證改進(jìn)后的算法的有效性，將使用UCI機(jī)器學(xué)習(xí)數(shù)據(jù)集中的Iris（150，4）和Wine（178，13）數(shù)據(jù)集來進(jìn)行仿真實(shí)驗(yàn)，并對(duì)和原算法的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比分析。實(shí)驗(yàn)中設(shè)置的參數(shù)如下：ant=5，r（Iris）=1.5，r（Wine）=10，p0=0.000005，鑒于參數(shù)ε0的設(shè)定有太大的主觀性，根據(jù)離差最大化賦權(quán)法計(jì)算樣本Iris的4個(gè)屬性的權(quán)值分別為（0.1967，0.4507，0.5785，0.1798）。樣本W(wǎng)ine中的13個(gè)屬性權(quán)值為（0.1415，0.1063，0.1130，0.09014，0.1346，0.0814，0.0187，0.0457，0.0603，0.0559，0.0546，0.0809，0.5788）。結(jié)束條件設(shè)定為算法循環(huán)NC=200次。表1的數(shù)據(jù)是算法運(yùn)行50次，取每次運(yùn)行中的最佳聚類結(jié)果，取平均值得出。

通過表1可以看到改進(jìn)后的蟻群聚類算法相比較于原算法在聚類的準(zhǔn)確度上有了一定的改進(jìn)。這主要是因?yàn)楦倪M(jìn)后的算法根據(jù)數(shù)據(jù)的各個(gè)特征屬性的重要程度而賦予不同的權(quán)值，對(duì)于聚類貢獻(xiàn)較大的特征屬性賦予較大的權(quán)值，而對(duì)于聚類貢獻(xiàn)相對(duì)較小的特征屬性則賦予較小的權(quán)值，進(jìn)而突出了重要屬性的作用，弱化了非重要屬性對(duì)聚類結(jié)果的干擾，實(shí)驗(yàn)證明了，改進(jìn)后的算法取得了較好的效果。

3 結(jié)束語(yǔ)

本文研究了蟻群算法在數(shù)據(jù)挖掘聚類方法中的一個(gè)應(yīng)用，改進(jìn)了基于螞蟻覓食原理的聚類算法中的距離計(jì)算，采用離差最大化賦權(quán)算法給數(shù)據(jù)對(duì)象的屬性賦予一定的權(quán)值，從而使得數(shù)據(jù)對(duì)象屬性的重要程度得到了區(qū)分，利于相似的數(shù)據(jù)對(duì)象能快速的聚集到一起，并且弱化了非重要屬性對(duì)聚類結(jié)果的干擾，減少了無效的相似度計(jì)算，提高了聚類的準(zhǔn)確率，但是基于覓食的蟻群聚類算法受初始聚類中心的影響較大，而初始聚類中心的選取，在目前為止并沒有一個(gè)較為完善的方法，并且算法在運(yùn)行過程中需要設(shè)置的重要參數(shù)較多，如聚類半徑r，統(tǒng)計(jì)誤差ε，螞蟻數(shù)量m等，都需要根據(jù)實(shí)際情況及經(jīng)驗(yàn)作出確定，帶有一定的主觀性，因此，如何找到一個(gè)科學(xué)的參數(shù)設(shè)定方法將是今后研究工作的重點(diǎn)。

參考文獻(xiàn)（References）：

[1] 高新波，謝維信.模糊聚類理論發(fā)展及應(yīng)用的研究發(fā)展[J].科

學(xué)通報(bào)，1999.44（21）.

[2] 王應(yīng)明.運(yùn)用離差最大化方法進(jìn)行多指標(biāo)決策與排序[J].系

統(tǒng)工程與電子技術(shù)，1998.20（7）：24-26

[3] 王堅(jiān)強(qiáng).基于離差優(yōu)化的信息不完全確定的多準(zhǔn)則分類方法[J].

控制與決策，2006.21（5）：513-516

[4]李正義，曾雪蘭，覃菊瑩.離差最大化特征加權(quán)模糊C-劃分的

聚類分析[J].模糊系統(tǒng)與數(shù)學(xué)，2008.22（4）：171-172endprint