離差最大化賦權的蟻群聚類算法

張新建

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

關鍵詞： 聚類算法； 蟻群算法； 離差； 權值

中圖分類號：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 引言

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

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

1 離差最大化賦權算法

1.1 多屬性決策

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

1.2 離差最大化賦權算法

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

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

設特征的權向量為并滿足。

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

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

2 基于離差最大化賦權的蟻群聚類算法

2.1 屬性權重對算法聚類結果的影響

2.1.1 對特征屬性進行賦權的必要性分析

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

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

2.1.2 權重的設置方法

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

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

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

2.2 改進后的算法

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

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

2.2.1 改進后的算法流程

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

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

Step 3 計算樣本Xi到Xj之間的加權歐氏距離

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

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

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

Step 7 計算歸并Xj領域的數據集合的聚類中心。

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

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

Step 9 計算總體誤差

Step 10 判斷若成立，則停止，并輸出聚類個數；否則，轉步驟Step 3繼續迭代。

2.2.2 仿真實驗及分析

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

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

3 結束語

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

參考文獻（References）：

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

學通報，1999.44（21）.

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

統工程與電子技術，1998.20（7）：24-26

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

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

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

聚類分析[J].模糊系統與數學，2008.22（4）：171-172endprint