張新建

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

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

中圖分類號：TP301.6 文獻標志碼：A 文章編號：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 引言

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

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

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

1.1 多屬性決策

多屬性決策是多目標方案決策的一種，又稱有限方案多目標決策，它是對具有多個屬性的有限方案，按照某種決定準則進行多方案選擇和排序。其理論方法已被廣泛地應用于社會、經(jīng)濟、管理、軍事等領域，其求解方法和屬性權(quán)重有密切的關(guān)系。因為它的合理性直接影響著多屬性決策排序的準確性，所以在多屬性決策中，權(quán)重問題的研究占有重要的地位。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 改進后的算法

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

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

2.2.1 改進后的算法流程

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

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

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

Step 4 計算各路徑上的信息量：

Step 5 對象Xi合并到Xj的概率為：

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

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

Step 8 計算第j個聚類的偏離誤差：

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

Step 9 計算總體誤差

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

2.2.2 仿真實驗及分析

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

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

3 結(jié)束語

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

參考文獻（References）：

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

學通報，1999.44（21）.

[2] 王應明.運用離差最大化方法進行多指標決策與排序[J].系

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

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

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

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

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