基于改進蟻群算法的聚類分析方法研究?

武書舟 閆麗娜 張秋艷 申曉留

（華北電力大學控制與計算機工程學院 北京 102206）

1 引言

隨著大數據廣泛應用，數據聚類分析技術已經成為大數據領域研究的一個重要課題，比如在圖像處理、客戶信息分析、金融分析以及醫學領域等方面都得到充分應用。聚類的本質是在數據樣本類型完全不知道的情況下，將相似度較高的數據對象歸為一類，每個聚類中心代表相應類型，整個聚類過程為無監督學習［1］。

蟻群算法屬于智能優化算法的一種，由Marco Dorigo博士根據螞蟻在尋找食物過程中發現路徑問題提出來的，通過實驗發現螞蟻可通過一種信息素的化學物質標記所走過的路徑，進而找到食源到蟻穴的最短距離。隨著對蟻群算法理論深入研究，該算法的分布式計算、信息正反饋及啟發式搜索等特征，充分的在組合優化問題、旅行商問題、背包問題、車輛調度問題和二次分配問題等實際應用中得以體現［3～17］。隨后學者根據蟻群堆積尸體及分工行為，提出了蟻群聚類算法，隨著理論的不斷成熟發展已成功運用于電路設計、文本挖掘等方面。遺傳算法在1975年由John Holland教授在達爾文生物進化論及孟德爾遺傳變異理論基礎上提出，成為新一代仿生算法［6～18］。隨著對該算法原理深入研究，不斷在組合優化、機器學習、智能控制及模式識別等領域得以應用［7］。

盡管蟻群算法和遺傳算法已被應用到許多領域，但各自算法本身存在缺陷。蟻群算法初期信息素匱乏，求解速度慢，容易陷入局部最優解困境；遺傳算法不能夠充分利用系統中反饋信息，容易做大量無用冗余迭代，精確效率低［8］。本文為解決蟻群算法在聚類過程中搜索速度慢、易于陷入局部最優解情況，同遺傳算法變異因子相結合，將兩者算法優缺點進行互補，通過實驗證明基于遺傳算法改進的蟻群算法在聚類過程中在一定程度上解決了算法在聚類過程收斂速度慢和易于陷入局部最優解的問題。

2 基本蟻群算法原理

2.1 蟻群算法基本原理

螞蟻依靠嗅覺來判斷物體方位，螞蟻可以憑借同類物種在周圍環境中散發的信息素來尋找食物，螞蟻在尋食過程是在沒有先驗基礎上進行的，但螞蟻仍夠找到食源與蟻穴之間的最佳路徑。通過大量實驗發現，螞蟻能夠感知散發出的信息素及強度，會傾向信息素濃度高的路徑移動，這樣在螞蟻移動過程中不斷加強原有路徑上信息素的濃度，導致螞蟻在后續路徑選擇上有較大的概率選擇信息素濃度高的路徑［9］。在相同時間段內較短的路徑會被更多的螞蟻訪問，因此螞蟻在選擇路徑上更傾向于較短的路徑，經過長時間的路徑選擇螞蟻便會找到一條食源與蟻穴之間的最短路徑。

螞蟻憑借散發在路徑上的信息素能夠找到食源與蟻穴之間最短的路徑，但是該條路徑不一定是最短路徑。蟻群算法不僅具有尋食行為，而且有蟻穴清理行為。該行為可以應用在數據挖掘聚類中，螞蟻在蟻穴清理過程中，將螞蟻尸體看成等待分析的數據集合，最終將尸體堆積為幾大堆，堆積的尸體對應的最終聚類結果。蟻群聚類算法最早是在1991年J.L.Deneubourg提出的，同時將該方法應用到數據分析領域［10］。蟻群聚類算法的基本機制是蟻堆對工蟻搬運死螞蟻具有吸引力，同時蟻堆規模大小決定對工蟻的吸引力大小，若蟻堆越大，吸引力就越大，促使蟻堆越來越大，此過程屬于正反饋過程，由此機制可以看聚類結果受到數據空間分布狀態的影響。

2.2 蟻群聚類算法模型—基于螞蟻搬運尸體行為

假設所要聚類的數據對象隨機的分布在二維且比例可以伸縮的網絡空間中，每個網格中含有一個對象，人工螞蟻沿著網格單元移動，沒有移動數據的螞蟻遇到數據對象時可以根據某種概率大小來搬運此數據；攜帶者數據對象的螞蟻當遇到空單元或者搬運數據對象與鄰近網格中的數據對象相似時，螞蟻會根據相應的概率將數據對象放下，其放下的數據對象概率根據周圍對象類型密度來判斷，若是密度大就將數據放下，反之亦然，因此具有相同類型的數據對象就會聚集起來［12］。

假設二維網格中的數據對象σi和σj之間的距離（相似度）d(σi，σj)用歐式距離表示，若兩個數據對象相似即 d(σi，σj)=0 ，反之 d(σi，σj)=1，通過相似性計算可以得出一個二維的相似度矩陣。若多個螞蟻在此二維網格中不斷重復數據對象拾起和放下操作，在某時刻螞蟻在r位置上發現數據對象σi后，其局部密度可以由公式表示為

其中 f(σi)為相似度密度，σj∈Grid(s×s)(r)，單元 r的鄰域面積為s×s，其中螞蟻在運動過程中拾起數據對象的概率 Pp(σi)和放下對象的概率 Pd(σi)表示，其中公式如下：

其中k1和k2都是閾值常數。該方法基于二維網格基礎進行聚類，當對高維數據進行聚類時，可以通過降維的方式將數據對象映射到相對較小的維度空間內，然后再進行聚類，注意網格精確度將會影響聚類效果。

數據對象被拾起和放下規則是：在網格中的隨機數據對象與其計算所得的拾起和放下可能性值大小進行比較，若隨機數較小則人工螞蟻執行拾起和放下操作，兩個動作受局部相似密度 f(σi)的影響，若是相似度大，拾起的概率Pp(σi)小，即該數據對象就歸于此簇，同時放下的概率Pd(σi)大，數據對象應屬于該簇，反之亦然。

2.3 蟻群算法存在缺陷

基于螞蟻堆形成原理實現的聚類算法不必預先指定簇的數目，并能構造局部任意形狀的簇。通過散發信息素可以強化路徑。但該算法仍然存在一定的缺陷，人工螞蟻隨機地拾起、移動和放下數據對象，所以在聚類過程中算法收斂速度較慢；盡管正反饋機制可以找到性能較好的解，但是容易出現停滯現象［15］。

3 改進蟻群算法

3.1 基于遺傳算法的蟻群聚類算法原理

在本文中主要解決一般蟻群算法在聚類過程中存在的缺陷，其解決方法是在每次迭代搜索后，將當前解和最優解進行交叉變異，這樣擴大了解的搜索空間，提高了搜索速度，同時避免了陷入局部最優解的現象。

3.2 具體算法實現過程

改進的蟻群聚類算法是將基本蟻群算法同遺傳算法中的變異因子相結合，在蟻群算法在迭代過程中產生遺傳算法所需的初始種群數據，提高了數據的多樣性：

程序中參數的初始化；

程序在聚類的過程中需要迭代的次數t_max=1000；

將m只螞蟻隨機置于n個城市中；

初始狀況下信息素矩陣（樣本數*聚類數）；最佳路徑度量值，初始值設置為無窮大，該值越小聚類效果越好；

對于每只螞蟻，按照轉移概率選擇下一個城市，并切修改路徑信息，即路徑上的信息素；

通過路徑標示符求解出每一類的聚類中心，計算出各樣本到聚類中心的偏離誤差；

根據偏離誤差的大小F，找到最佳路徑；

接下來引入遺傳算法的變異率，對找到的最佳路徑進行變異，典型的操作如以下代碼：

通過對最佳路徑進行變異后，重新計算各個樣本到其對應的聚類中心的偏移誤差F_temp，然后通過比較兩次計算的偏移誤差，來確定此時的最佳路徑。若是F_temp＜F，則F=F_temp，然后比較F與F_min的大小，進行信息素的更改；相反則不進行F=F_temp操作。

當程序達到最大迭代次數時，聚類完成。

改進蟻群算法實現的流程如圖1所示。

圖1 改進蟻群算法流程圖

4 實驗對比

在實驗過程中，首先設定出50個待聚類的數據對象為聚類樣本，在Matlab軟件中通過控制參數的方法來驗證改進的蟻群聚類算法如何在基本蟻群算法基礎上提高性能的。通過設定參數，將兩種算法聚類結果進行對比可以發現，以當前樣本為例，聚類最短所用時間為320s左右。其實驗對比過程如下。

基本蟻群算法與G蟻群算法中的參數設置如以下表格所示。

4.1 一般蟻群算法實驗參數設置

表1 蟻群算法參數設置表

在一般蟻群聚類過程中，以控制變量方式進行實驗對比，發現當 R=100時，迭代次數為t_max=1000，min=35802，此時聚類用時Time=194.1377s。圖2為聚類效果圖。

圖2 聚類效果圖

為達到更為理想的聚類效果，逐漸增加迭代次數，經過多次實驗證明，當迭代次數增加到4000和5000時，min最短距離在19726左右浮動，聚類結果基本保持不變，此時的聚類時間Time=151.7225s，此時的聚類效果可以看成為最優聚類效果。最優聚類效果如圖3所示：

圖3 最優聚類效果圖

4.2 改進蟻群算法實驗參數設置

表2 改進蟻群算法參數設置表

在改進蟻群算法聚類實驗過程中，通過設置不同的尋優參數、螞蟻數量及迭代次數，將其聚類結果進行對比，選擇為出最優聚類結果。實驗證明當局部尋優參數 pls=0.01，R=100，t_max=1000時，此時的聚類效果能夠達到最優。如圖4所示為改進蟻群算法聚類效果圖。

圖4 改進蟻群算法聚類效果圖

經過一般蟻群算法和改進蟻群算法實驗對比發現，當控制變量（螞蟻數量、迭代次數、聚類個數）相同時，基于遺傳改進的蟻群算法的聚類用時和聚類效果明顯優越于一般蟻群算法。將蟻群算法與遺傳算法相結合，不斷擴大了解的搜索空間，同時有效地避免陷入局部最優解的局面；結合聚類結果圖可以發現改進的蟻群算法能夠快速找到最優解，提高了收斂速度。

5 結語

本文介紹了一般蟻群算法聚類原理及算法所存在的缺陷，針對該算法在聚類過程中存在收斂速度慢和易于陷入局部最優解問題的缺陷，本文提出一種基于遺傳改進蟻群聚類分析算法，主要在原來蟻群算法基礎上同遺傳算法變異因子相結合。在實驗過程中采用控制變量方法、對比分析方法，驗證改進的蟻群算法是否能夠提高收斂性及陷入局部最優解的性能，經過實驗證明改進蟻群算法聚類效果優于一般蟻群聚類算法，在一定程度上提高了收斂性，擴大了解的搜索范圍并有效避免陷入局部最優解的困境。