基于改進(jìn)蟻群算法的聚類分析方法研究?

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

（華北電力大學(xué)控制與計(jì)算機(jī)工程學(xué)院 北京 102206）

1 引言

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

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

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

2 基本蟻群算法原理

2.1 蟻群算法基本原理

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

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

2.2 蟻群聚類算法模型—基于螞蟻搬運(yùn)尸體行為

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

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

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

其中k1和k2都是閾值常數(shù)。該方法基于二維網(wǎng)格基礎(chǔ)進(jìn)行聚類，當(dāng)對(duì)高維數(shù)據(jù)進(jìn)行聚類時(shí)，可以通過降維的方式將數(shù)據(jù)對(duì)象映射到相對(duì)較小的維度空間內(nèi)，然后再進(jìn)行聚類，注意網(wǎng)格精確度將會(huì)影響聚類效果。

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

2.3 蟻群算法存在缺陷

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

3 改進(jìn)蟻群算法

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

在本文中主要解決一般蟻群算法在聚類過程中存在的缺陷，其解決方法是在每次迭代搜索后，將當(dāng)前解和最優(yōu)解進(jìn)行交叉變異，這樣擴(kuò)大了解的搜索空間，提高了搜索速度，同時(shí)避免了陷入局部最優(yōu)解的現(xiàn)象。

3.2 具體算法實(shí)現(xiàn)過程

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

程序中參數(shù)的初始化；

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

將m只螞蟻隨機(jī)置于n個(gè)城市中；

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

對(duì)于每只螞蟻，按照轉(zhuǎn)移概率選擇下一個(gè)城市，并切修改路徑信息，即路徑上的信息素；

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

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

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

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

當(dāng)程序達(dá)到最大迭代次數(shù)時(shí)，聚類完成。

改進(jìn)蟻群算法實(shí)現(xiàn)的流程如圖1所示。

圖1 改進(jìn)蟻群算法流程圖

4 實(shí)驗(yàn)對(duì)比

在實(shí)驗(yàn)過程中，首先設(shè)定出50個(gè)待聚類的數(shù)據(jù)對(duì)象為聚類樣本，在Matlab軟件中通過控制參數(shù)的方法來驗(yàn)證改進(jìn)的蟻群聚類算法如何在基本蟻群算法基礎(chǔ)上提高性能的。通過設(shè)定參數(shù)，將兩種算法聚類結(jié)果進(jìn)行對(duì)比可以發(fā)現(xiàn)，以當(dāng)前樣本為例，聚類最短所用時(shí)間為320s左右。其實(shí)驗(yàn)對(duì)比過程如下。

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

4.1 一般蟻群算法實(shí)驗(yàn)參數(shù)設(shè)置

表1 蟻群算法參數(shù)設(shè)置表

在一般蟻群聚類過程中，以控制變量方式進(jìn)行實(shí)驗(yàn)對(duì)比，發(fā)現(xiàn)當(dāng) R=100時(shí)，迭代次數(shù)為t_max=1000，min=35802，此時(shí)聚類用時(shí)Time=194.1377s。圖2為聚類效果圖。

圖2 聚類效果圖

為達(dá)到更為理想的聚類效果，逐漸增加迭代次數(shù)，經(jīng)過多次實(shí)驗(yàn)證明，當(dāng)?shù)螖?shù)增加到4000和5000時(shí)，min最短距離在19726左右浮動(dòng)，聚類結(jié)果基本保持不變，此時(shí)的聚類時(shí)間Time=151.7225s，此時(shí)的聚類效果可以看成為最優(yōu)聚類效果。最優(yōu)聚類效果如圖3所示：

圖3 最優(yōu)聚類效果圖

4.2 改進(jìn)蟻群算法實(shí)驗(yàn)參數(shù)設(shè)置

表2 改進(jìn)蟻群算法參數(shù)設(shè)置表

在改進(jìn)蟻群算法聚類實(shí)驗(yàn)過程中，通過設(shè)置不同的尋優(yōu)參數(shù)、螞蟻數(shù)量及迭代次數(shù)，將其聚類結(jié)果進(jìn)行對(duì)比，選擇為出最優(yōu)聚類結(jié)果。實(shí)驗(yàn)證明當(dāng)局部尋優(yōu)參數(shù) pls=0.01，R=100，t_max=1000時(shí)，此時(shí)的聚類效果能夠達(dá)到最優(yōu)。如圖4所示為改進(jìn)蟻群算法聚類效果圖。

圖4 改進(jìn)蟻群算法聚類效果圖

經(jīng)過一般蟻群算法和改進(jìn)蟻群算法實(shí)驗(yàn)對(duì)比發(fā)現(xiàn)，當(dāng)控制變量（螞蟻數(shù)量、迭代次數(shù)、聚類個(gè)數(shù)）相同時(shí)，基于遺傳改進(jìn)的蟻群算法的聚類用時(shí)和聚類效果明顯優(yōu)越于一般蟻群算法。將蟻群算法與遺傳算法相結(jié)合，不斷擴(kuò)大了解的搜索空間，同時(shí)有效地避免陷入局部最優(yōu)解的局面；結(jié)合聚類結(jié)果圖可以發(fā)現(xiàn)改進(jìn)的蟻群算法能夠快速找到最優(yōu)解，提高了收斂速度。

5 結(jié)語

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