田云娜，趙彥霖，劉 雪，趙彭麗，韓小穎

（延安大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院，陜西延安 716000）

在當(dāng)前信息時代，隨著信息處理技術(shù)、數(shù)據(jù)庫技術(shù)的日益完善，數(shù)據(jù)的收集和生成頻繁發(fā)生。人們雖然能夠輕松存儲和共享大量的數(shù)據(jù)，但在日益增長的海量數(shù)據(jù)中要提取到有用的信息也變得越來越難。為了能從大量、復(fù)雜、模糊的數(shù)據(jù)中提取到有價值的信息，因此迫切需要一種方法能夠?qū)⑦@些信息智能地轉(zhuǎn)化為有價值的知識與信息，從而促進了數(shù)據(jù)挖掘（Date mining，DM）的出現(xiàn)，而聚類正是數(shù)據(jù)挖掘的四項基本任務(wù)之一［1］。聚類是指將數(shù)據(jù)、結(jié)果等進行無監(jiān)督地分類，把屬性相似的個體歸為同個簇中。聚類的目標(biāo)是將數(shù)據(jù)集分組到簇中，以便同一聚類中的樣本對象差異最為相似，且不同簇中對象之間的相似性最小化。聚類作為極其受歡迎的無監(jiān)督學(xué)習(xí)方法之一，在數(shù)據(jù)挖掘、人工智能、統(tǒng)計學(xué)等領(lǐng)域都起到很重要的作用。

傳統(tǒng)的聚類方法大致可分為劃分聚類、密度聚類、層次聚類、網(wǎng)格聚類和模型聚類等［2］?；趧澐志垲惙椒ㄓ媚撤N劃分方法將所有數(shù)據(jù)對象歸納入不同的聚類中心；基于密度聚類方法會按照數(shù)據(jù)集的密度分布對數(shù)據(jù)進行劃分，比如依靠高密度點將數(shù)據(jù)對象聚于簇中，其計算量小于基于距離的聚類算法，通常這種方式只能發(fā)現(xiàn)球狀的簇；基于層次聚類方法將數(shù)據(jù)對象進行層次的分解，主要分為分裂式和凝聚式，適用于任意形狀和屬性的數(shù)據(jù)集，但同時也額外增加了算法的執(zhí)行時間；基于網(wǎng)格聚類方法將數(shù)據(jù)對象映射到被劃分為有限數(shù)目的網(wǎng)格空間中，與數(shù)據(jù)對象的數(shù)目及輸入順序無關(guān)，對所形成的網(wǎng)格空間加以聚類，可處理任意類型的數(shù)據(jù)；基于模型聚類方法先將每個聚類設(shè)置為一種例證，然后尋找可以相似例證條件的數(shù)據(jù)集，算法易于理解但效率并不高。

常見的劃分聚類算法有K均值聚類（K-Means）［3］、K-中心點聚類（K-Medoids Clustering）［4］、CLARANS（Clustering Large Applications based on RANdomized Search）［5］；密度聚類算法有DBSCAN（Density-Based Spatial Clustering of Applications with Noise）［6］、OPTICS（Ordering Points To Identify the Clustering Structure）［7］、DENCLUE（Density Clustering）［8］；層次聚類算法有AGNES（Agglomerative Nesting）［9］、BIRCH（Blanced Iterative Reducing and Clustering）［10］、CURE（Clustering Using Representative）［11］；網(wǎng) 格 聚 類 算 法 有STING（Statistical Information Grid-Based Methods）［12］、WaveCluster（Wave-Cluster）［13］、CLIQUE（Clustering In Quest）［14］；模型聚類算法有自組織神經(jīng)網(wǎng)絡(luò)算法（Self-Organizing Map，SOM）［15］、期望最大化算法（Expectation-maximization，EM）［16］。由于聚類方法的不同，這些算法的聚類效果和計算性能也各有不同。比如K-Means 算法處理數(shù)據(jù)集相對簡單高效，但需要事先給定k 值，算法受初始值k 設(shè)置影響大，對噪聲點異常敏感；K-Medoids 具有很強的魯棒性，受噪聲點影響較低，但受初始值k設(shè)置影響大，不適合處理大規(guī)模數(shù)據(jù)集；DBSCAN 可以發(fā)現(xiàn)任何形狀的簇，聚類結(jié)果受噪聲點影響小，對初始參數(shù)設(shè)置較為敏感；DENCLUE 可發(fā)現(xiàn)任意形狀的簇，受噪聲點影響低，但計算復(fù)雜度較高，不適合處理大型數(shù)據(jù)集；AGNES 不需要提前設(shè)置聚類數(shù)，距離與相似度容易定義，不受初始樣本形狀影響，但不適合大數(shù)據(jù)集聚類；BIRCH 處理數(shù)據(jù)速度快，適用于大數(shù)據(jù)聚類，但確定合適的變量參數(shù)較為困難；CURE 屬于凝聚層次聚類，對噪聲異常點不敏感，可以發(fā)現(xiàn)任何形狀的簇，適合大數(shù)據(jù)集聚類；STING計算成本低，處理數(shù)據(jù)速度極快，但降低了聚類結(jié)果的準(zhǔn)確度；WaveCluster 可處理大型數(shù)據(jù)集，不受初始樣本形狀影響，受噪聲點影響低，但對某兩類無明顯邊緣的數(shù)據(jù)集聚類效果較差；CLIQUE 對輸入數(shù)據(jù)順序不敏感，對輸入數(shù)據(jù)維數(shù)變化有較好的伸縮性，但聚類結(jié)果的精確度有所下降；SOM 聚類時間復(fù)雜度低，但聚類精確性不高，需要預(yù)先設(shè)置k 值，不適合處理大數(shù)據(jù)集；EM屬于K-均值算法的擴展，適用于大數(shù)據(jù)集，對噪聲非常敏感，需要預(yù)先設(shè)置k值且聚類精度不高?？梢钥闯?，每個聚類算法都有獨特的優(yōu)勢和不足，對算法的使用要依據(jù)不同的問題進行選擇。研究者們根據(jù)各類算法的特點，將其應(yīng)用于各種適用領(lǐng)域，如計算機科學(xué)、圖像處理、物聯(lián)網(wǎng)、生物信息學(xué)、醫(yī)學(xué)等領(lǐng)域。

隨著信息社會的不斷發(fā)展，面對復(fù)雜而多樣的數(shù)據(jù)，傳統(tǒng)聚類算法對問題的適用場景依賴性較強，在求解高難度聚類任務(wù)時出現(xiàn)了聚類效果差、效率低下等問題，已經(jīng)無法滿足多層次、高維度、大批量數(shù)據(jù)的聚類需求。為了從復(fù)雜且龐大的數(shù)據(jù)信息中發(fā)掘出人們所需要的價值，學(xué)者們不斷改進傳統(tǒng)聚類的方式。

伴隨群智能（仿生）算法的持續(xù)研究與聚類任務(wù)難度不斷加大，研究者們在改進聚類的過程中引入了操作簡單、求解速度快、易與傳統(tǒng)聚類算法結(jié)合的仿生聚類（Bionic Clustering，BC）算法。BC 是在群智能算法與基礎(chǔ)聚類算法的基礎(chǔ)上進行改進的混合聚類優(yōu)化算法，它主要針對不同的聚類任務(wù)，先進行聚類分析，然后模擬自然界的生物行為，靈活地將仿生算法的優(yōu)勢與基本聚類算法結(jié)合，從而優(yōu)化聚類過程得到更好的聚類結(jié)果。這種算法在實現(xiàn)的過程保留了仿生算法的靈活性、自組織性、穩(wěn)健性、分布性等特點，同時繼承了基本聚類算法的功能優(yōu)勢，使得復(fù)雜的聚類問題變得簡單高效。盡管部分群智能算法（仿生）算法與基礎(chǔ)聚類算法均可單獨實現(xiàn)某種聚類任務(wù)，但面對高維度復(fù)雜情況下的聚類任務(wù)時，其聚類效果有所欠缺。

近年來，得益于仿生算法簡單、智能、易結(jié)合的優(yōu)勢，基于仿生算法與基本聚類算法結(jié)合的仿生聚類逐漸興起，受到了很多研究者的關(guān)注。2009 年，CHENG 等［17］提出2 種改進人工魚群聚類優(yōu)化算法，引入魚群吞食行為思想，分別結(jié)合了模糊C均值聚類（Fuzzy C-means，F(xiàn)CM）模型與硬C 均值聚類（Hardc-means，HCM）模型，通過實驗對比驗證該算法可以減少孤立點和初始參數(shù)設(shè)置對聚類結(jié)果的影響，降低算法的復(fù)雜度。2011年，F(xiàn)ANG等［18］通過模擬青蛙跳躍對K-Means 參數(shù)優(yōu)化，大幅提高了對文本聚類的準(zhǔn)確率。2013 年，SOOD 等［19］提出了組合K-Medoids 的蝙蝠聚類算法，算法模仿蝙蝠回聲定位，解決了在大型數(shù)據(jù)集中選擇初始聚類對象困難的問題。2014 年，SAIDA 等［20］根據(jù)布谷鳥產(chǎn)卵寄生的生物行為，提出了易實現(xiàn)、參數(shù)較少的布谷鳥聚類算法，并對多個數(shù)據(jù)集聚類，驗證了該算法在解決數(shù)據(jù)聚類問題上的有效性。2015年，LI等［21］通過模擬鳥類捕食行為，用改進學(xué)習(xí)因子與動態(tài)權(quán)值的粒子群算法結(jié)合K-Means 提出了新的粒子群聚類算法，并在圖像分割問題中提高了圖像質(zhì)量和分割效率。2016年，閆婷等［22］利用細菌覓食結(jié)合粒子群優(yōu)化，改進了K-Means 聚類中心的選取方式，通過3種不同的數(shù)據(jù)集證明了該算法對數(shù)據(jù)聚類結(jié)果的有效性。2018 年，TRIPATHI 等［23］制定了一種灰狼狩獵策略與二項式交叉混合的灰狼聚類算法，通過多個規(guī)模的數(shù)據(jù)集驗證了該算法在處理大型合成數(shù)據(jù)集的高效性。2019 年，HROSIK 等［24］根據(jù)螢火蟲群體之間覓食行為，提出了結(jié)合K-Means 思想的螢火蟲聚類算法將其應(yīng)用在腦圖像分割問題中。2020 年，SING 等［25］模仿貓的追蹤和尋找模式提出了貓群聚類算法，該算法引入鄰域搜索策略提高了算法的收斂速度，在8個數(shù)據(jù)集上進行測試，證實該算法具有較高的聚類效果。鄭洪清等［26］模擬蝴蝶覓食行為，提出了一種改進蝴蝶局部搜索方式的蝴蝶聚類算法，在6種數(shù)據(jù)集上進行對比測試，驗證了該算法的魯棒性和收斂速度。THALAMALA 等［27］提出3種模擬蜘蛛社交行為與K-Means結(jié)合的聚類算法，在6種數(shù)據(jù)集上進行對比測試，證明所提出算法具有較精確的聚類結(jié)果。2021年，余曉蘭等［28］模擬雞群覓食行為結(jié)合FCM，提出了動態(tài)模糊雞群聚類算法，通過路徑規(guī)劃實例，證明了該算法運行速度快、收斂精度高。

可以看出，關(guān)于BC 的研究不但是群智能算法與基礎(chǔ)聚類算法思想的結(jié)合，同時還可以通過群智能算法優(yōu)化聚類方法的參數(shù)。BC 的出現(xiàn)為求解結(jié)構(gòu)復(fù)雜、大規(guī)模、多樣化的聚類任務(wù)提供了高效、易實現(xiàn)、思想簡單的方法，在物聯(lián)網(wǎng)［18］、圖像處理［21，24］、路徑規(guī)劃［28］等領(lǐng)域數(shù)據(jù)處理都表現(xiàn)出很好的聚類效果。

本文主要對現(xiàn)有3種具有代表性的仿生聚類算法進行研究分析，首先分別以蟻群聚類、果蠅聚類、人工蜂群聚類為案例，介紹仿生聚類算法的思想、與K-Means 聚類的結(jié)合流程及其應(yīng)用情況；然后對聚類過程中的相似性度量和無監(jiān)督評價方法進行了詳細介紹；最后對仿生聚類未來的研究方向做了結(jié)論與展望。

1 代表性仿生聚類算法

本節(jié)主要介紹3 種具有代表性的仿生聚類算法，分別是典型的蟻群聚類、搜索效率高的果蠅聚類和深度搜索能力較強的人工蜂群聚類算法。

1.1 蟻群聚類算法

蟻群聚類是受螞蟻自然行為啟發(fā)的聚類算法，主要有螞蟻堆積尸體和螞蟻覓食行為。由于蟻群自然行為較為接近實際聚類問題，因此衍生出大量的蟻群聚類算法。蟻群聚類魯棒性較強，適合處理海量數(shù)據(jù)，和其他聚類算法相比在復(fù)雜優(yōu)化問題上表現(xiàn)出巨大的發(fā)展?jié)摿蛢?yōu)勢。

1.1.1 蟻群聚類算法仿生思想

生物學(xué)家研究螞蟻這類視盲生物如何做到有條不紊地進行覓食、清潔巢穴堆積尸體等行為。通過觀察后發(fā)現(xiàn)螞蟻之間信息的傳遞是根據(jù)一種通信媒介而傳遞，即信息素。

1）蟻堆形成

在1991 年，由DENEUBOURG 提出了最早的蟻群聚類BM 模型［29］。主要思想是把數(shù)據(jù)對象模擬工蟻搬運亡蟻聚集成亡蟻堆，越小的亡蟻堆對于工蟻吸引力越大，從而將亡蟻抬起后放入其中。

在基于密度聚類下的蟻群聚類算法中［30-31］，令數(shù)據(jù)對象隨機投影在與數(shù)據(jù)集成比例的Z×Z 二維面中，設(shè)參數(shù)相異度比例為α，α 設(shè)置太小不利于數(shù)據(jù)對象的聚合；α 設(shè)置太大會導(dǎo)致不同簇的數(shù)據(jù)混合，樣本區(qū)分不明顯。螞蟻在r 位置的觀測區(qū)域為s× s。若發(fā)現(xiàn)了對象Oi，則Oi與其他對象Oj的距離為d。那么與Oi周圍對象的相似度（fO）i公式為

在算法中，每次螞蟻抬起或是放下搬運對象的概率都會受到相似度的影響，相似度越大則越不易運走，抬起、放下的概率計算公式表示為

其中k1、k2皆是閾值常數(shù)。

2）螞蟻覓食

螞蟻覓食也是一個模仿螞蟻自然行為的聚類。當(dāng)螞蟻從i 點到達j 點時，螞蟻會在行進過的道路d（i，j）上留下信息素。當(dāng)螞蟻經(jīng)過同一條道路的次數(shù)越多，該路上的信息素濃度就越大。螞蟻趨向于信息素濃度大的道路，與此同時路徑上的信息素還會按一定程度進行揮發(fā)。

數(shù)據(jù)對象聚類于某一簇中的概率表示為

其中，τ 為信息素含量，η 為啟發(fā)信息通常用歐拉距離的倒數(shù)表示，α、β 為控制參數(shù)常量。信息素的更新公式表示為

其中，ρ 為揮發(fā)系數(shù)，Q 為常數(shù)，dij為i 點與j 點間的距離。

1.1.2 與K-Means結(jié)合的蟻群聚類算法案例

蟻群聚類主要模擬蟻堆形成和尋覓食物2 種螞蟻生物行為。其中蟻堆形成聚類（Lumer and Faieta，LF）［32］在實際應(yīng)用中容易造成資源浪費、收斂慢以及易陷入局部最優(yōu)的缺點。與K-Means 分層結(jié)合后避免了資源浪費，降低了K-Means 初始參數(shù)的敏感性，大大提高算法效率的同時保證避免陷入局部最優(yōu)［33］。另外，僅依靠螞蟻產(chǎn)生信息素的蟻群聚類方法（ant colony clustering algorithm，ACCA）［34］存在聚類困難、低效等不足，與K-Means 結(jié)合后加快了收斂速度，使聚類結(jié)果更合理有效。

1）模仿蟻堆形成的蟻群聚類算法KMBLF（Kmeans algorithm based on Lumer and Faieta algorithm）

KMBLF算法模仿蟻堆形成的蟻群聚類算法，令數(shù)據(jù)對象隨機投影在與數(shù)據(jù)集成比例的Z×Z 二維面中，數(shù)據(jù)對象不重疊，然后從二維網(wǎng)格面中隨機挑選x 個數(shù)據(jù)位置，并在這些挑選的位置上產(chǎn)生新的對象作為工蟻用來搬運對象，如果工蟻在無搬運對象時隨機游走發(fā)現(xiàn)了對象Oi，則會用（1）式進行相似度判斷。螞蟻拾取對象的條件為（2）式的值大于隨機產(chǎn)生（0，1］的數(shù)，則拾起對象并對空載工蟻進行負載標(biāo)記。負載的螞蟻要想放下數(shù)據(jù)對象需要移動到無螞蟻的地方，根據(jù)（1）式和（3）式計算放下數(shù)據(jù)對象的概率Pdown。若沒放下則會繼續(xù)向其他無螞蟻的地方移動，若放下對象將進行空載標(biāo)記。整個蟻群執(zhí)行一次移動搬運對象后將部分數(shù)據(jù)對象進行聚類，得到一次初始蟻群聚類結(jié)果。通過前面的初始分割，仍然會有部分“自由數(shù)據(jù)”，比如工蟻正在搬運的數(shù)據(jù)對象以及尚未被螞蟻遍歷的對象，緊跟著用K-Means算法進行聚類。

算法的具體實現(xiàn)步驟如下：

步驟1：參數(shù)初始化，設(shè)置迭代次數(shù)Num，螞蟻個數(shù)K，相異度比例為α，短期記憶L；

步驟2：令數(shù)據(jù)對象投影在二維面中，標(biāo)識網(wǎng)格處無數(shù)據(jù)對象，標(biāo)識螞蟻均為負載；

步驟3：判斷螞蟻是否有負載，若是則進行步驟4，否則進行步驟8；

步驟4：隨機為螞蟻Ki選擇位置pi；

步驟5：若pi處有對象則進行步驟6，否則返回步驟4；

步驟6：利用（1）式計算周圍相似度，（2）式計算拾起概率，產(chǎn)生隨機數(shù)；

步驟7：若隨機數(shù)小于Pup（Oi），則拾起對象Oi并標(biāo)識Ki負載，標(biāo)識pi處無對象，否則返回步驟4；

步驟8：隨機將螞蟻Kj移動到位置pj；

步驟9：若pj處有對象則進行步驟10，否則返回步驟8；

步驟10：利用（1）式計算周圍相似度，（3）式計算方下概率，產(chǎn)生隨機數(shù)；

步驟11：若隨機數(shù)大于Pdown（Oj），則放下對象Oj并標(biāo)識Kj未負載，標(biāo)識pi處有對象；

步驟12：經(jīng)過一次LF 算法后，輸出聚類結(jié)果k個小堆H1，H2，…，Hk；

步驟13：將步驟12 的k 用來當(dāng)作K-Means 算法的參數(shù)輸入，將步驟12每個小堆的中心當(dāng)作初始聚類中心，用K-Means算法聚類；

步驟14：對堆H 進行層次聚類然后再進行KMeans算法；

步驟15：最大迭代次數(shù)或滿足結(jié)束條件并輸出最優(yōu)解。

2）模仿螞蟻覓食的蟻群聚類算法KMACCA（KMeans Ant Colony Clustering Algorithm）

KMACCA 的算法［35］通過利用擁有快速收斂特性的K-Means 算法對數(shù)據(jù)進行預(yù)處理，可以獲得初始的聚類中心，再根據(jù)每個數(shù)據(jù)對象對各個聚類中心的初始距離進行信息素地分配。然后，利用蟻群算法將每個數(shù)據(jù)對象到各個聚類中心路徑上不一樣的信息素實施聚類操作。

KMACCA算法的具體實現(xiàn)步驟如下：

步驟1：參數(shù)初始化，隨機從樣本中挑選k 個數(shù)據(jù)作為初始聚類中心；

步驟2：進行K-Means 得到預(yù)處理的聚類中心和簇；

步驟3：依靠啟發(fā)信息分配信息素給每個數(shù)據(jù)對象i到對應(yīng)的聚類中心Cj；

步驟4：隨機生成每個數(shù)據(jù)對象的轉(zhuǎn)移參數(shù)，若滿足轉(zhuǎn)移條件則進行其他簇的轉(zhuǎn)移，否則數(shù)據(jù)對象仍處于原來的簇中；

步驟5：單只螞蟻經(jīng)過全部樣本點后，依靠目標(biāo)函數(shù)得到新的聚類中心，保存最優(yōu)解；

步驟6：遍歷全部螞蟻更新最優(yōu)解并按（5）式更新信息素；

步驟7：達到最大迭代次數(shù)或滿足結(jié)束條件并輸出最優(yōu)解，否則返回步驟2。

1.1.3 蟻群聚類算法的應(yīng)用

在聚類分析應(yīng)用中，蟻群算法不僅可以單獨進行聚類研究還十分容易與其他聚類算法融合。以下列舉了蟻群聚類算法的幾個主要應(yīng)用領(lǐng)域。

1）數(shù)據(jù)分析：JABBAR 等［36］改進了蟻群搜索局部鄰域策略的蟻群聚類，將其應(yīng)用在6 個不同標(biāo)準(zhǔn)數(shù)據(jù)集分析中。FAHY等［37］提出了一種抗噪性良好的蟻群聚類算法應(yīng)用，將其在動態(tài)數(shù)據(jù)流聚類。GAO等［38］提出了較高精度和速度的數(shù)據(jù)組合機制抽象蟻群聚類算法，實現(xiàn)對3種不同數(shù)據(jù)集的劃分。

2）物聯(lián)網(wǎng)：EBADINEZHAD 等［39］考慮組織車輛節(jié)點的通信路徑問題，將蟻群聚類框架應(yīng)用在物聯(lián)網(wǎng)中的車載通信拓撲結(jié)構(gòu)中。ZOU 等［40］和XIAO等［41］為了提高數(shù)據(jù)傳輸，用改進蟻群聚類算法解決無線傳感器網(wǎng)絡(luò)路由問題，從而提高無線傳感器服務(wù)質(zhì)量。

3）交通運輸：CHENG 等［42］利用蟻群聚類建立定位模型，開展了高速列車定位方面實時性和適應(yīng)性研究。XU 等［43］提出耗時較少的蟻群聚類，將其應(yīng)用在動態(tài)、可變的車輛路徑問題。

此外，HOU 等［44］將蟻群聚類應(yīng)用于多光譜圖像檢測，有效準(zhǔn)確地識別了感染葡萄卷葉病的植株。BULUT等［45］利用模糊C-均值算法結(jié)合蟻群聚類，用于生物信息學(xué)種分析微陣列基因表達數(shù)據(jù)。LIAO等［46］提出了具有魯棒性、高精度、耗時少的分層蟻群聚類算法，并將其應(yīng)用于求解大規(guī)模旅行商問題。

1.2 果蠅聚類算法

果蠅聚類算法一般為改進參數(shù)的果蠅優(yōu)化算法（Fruit Fly Optimization Algorithm，F(xiàn)OA）［47］與基礎(chǔ)聚類算法結(jié)合使用，衍生新的聚類算法，保留著果蠅優(yōu)化算法的簡單、參數(shù)少、運行效率高等優(yōu)點。

1.2.1 果蠅聚類算法的仿生思想

自然界的果蠅擁有著很強的嗅覺與視覺感知，覓食時并不是隨機搜索，多數(shù)果蠅會朝著食物源或是味道濃度最大的方向前進。

設(shè)果蠅的初始位置為dstart（xstart，ystart），賦予果蠅搜索半徑L與隨機方向。果蠅個體位置更新公式表示為

式中，i表示第i個果蠅個體；（xi，yi）為更新坐標(biāo)。由于食物源位置未知，因此將每個果蠅濃度判定值設(shè)置為該果蠅與原點的距離倒數(shù)Si，其計算方式表示為

依靠判斷味道濃度的適應(yīng)度函數(shù)Fitness function，保留最大的濃度最佳值Fitnessmax（Si）以及最優(yōu)果蠅個體作為群體坐標(biāo)。迭代最后味道濃度總和最大的最優(yōu)果蠅個體便可視為聚類中心。

1.2.2 與K-Means結(jié)合的果蠅聚類算法案例

基于K-Means 對于初始的聚類中心比較敏感且容易陷入局部最優(yōu)，文獻［48］提出了一種以混合果蠅優(yōu)化算法結(jié)合K-Means 的果蠅聚類算法（Fruit Fly Optimization Algorithm-K-Means，F(xiàn)OA-K），并通過實驗驗證了算法的有效性。

FOA-K算法通過FOA迭代一次搜索到最佳值，將最佳值的位置信息作為K-Means 的聚類中心并進行一次K-Means 聚類，得到新的聚類中心后再返回FOA，重復(fù)交替迭代執(zhí)行FOA 和K-Means，直到滿足輸出條件。

FOA-K算法的具體實現(xiàn)步驟如下：

步驟1：參數(shù)初始化，分別設(shè)置最大迭代次數(shù)max_G，聚類中心數(shù)k，果蠅的最大種群數(shù)S；

步驟2：對樣本數(shù)據(jù)任意抽取k個作為果蠅個體即K-Means初始聚類中心；

步驟3：執(zhí)行K-Means 算法，K-Means 收斂后得到新的聚類中心；

步驟4：重新定義果蠅的初始位置；

步驟5：通過果蠅味道判定（7）式代入適應(yīng)度函數(shù)，記錄濃度最佳值Fitnessmax（Si）得到最優(yōu)果蠅個體，其坐標(biāo)作為果蠅群的初始果蠅群坐標(biāo)；

步驟6：再次隨機在初始果蠅群坐標(biāo)周圍生成果蠅，計算并記錄最優(yōu)個體與位置；

步驟7：判斷最優(yōu)個體是否改變，若改變則其將當(dāng)前最優(yōu)坐標(biāo)作為果蠅群的初始果蠅群坐標(biāo)；

步驟8：重復(fù)步驟3~7，直到迭代次數(shù)大于max_G，輸出最優(yōu)值。

1.2.3 果蠅聚類算法的應(yīng)用

果蠅聚類算法經(jīng)常以優(yōu)化的果蠅算法與其他聚類算法結(jié)合，彌補果蠅算法的缺陷，又保留著簡單、參數(shù)少、運行效率高等優(yōu)勢。以下列舉了果蠅聚類算法被主要應(yīng)用的幾個領(lǐng)域。

1）圖像分割：其中鄧然然等［49］通過密度峰值聚類與自動調(diào)節(jié)果蠅步長相結(jié)合的果蠅聚類算法實現(xiàn)圖像分割；孫立新等［50］利用模糊均值聚類結(jié)合改進果蠅步長的果蠅聚類算法實現(xiàn)圖像分割；ZHU等［51］通過結(jié)合密度峰值的果蠅聚類對醫(yī)學(xué)圖像自適應(yīng)分割。

2）數(shù)據(jù)分析：WANG 等［52］通過核模糊C 均值的果蠅聚類對電力負載特性數(shù)據(jù)進行分類；LEI 等［53］結(jié)合基因表達譜的果蠅聚類對蛋白質(zhì)復(fù)合物進行識別；王麗婕等［54］結(jié)合數(shù)學(xué)形態(tài)學(xué)的果蠅聚類算法對風(fēng)力發(fā)電數(shù)據(jù)聚類，預(yù)測了依蘭風(fēng)電場的風(fēng)電功率。

3）物聯(lián)網(wǎng)：WANG等［55］通過與遺傳算法結(jié)合的果蠅聚類算法改進路由協(xié)議，提高了數(shù)據(jù)傳輸效率；JIANG 等［56］提出了不均勻分簇果蠅聚類的路由協(xié)議。

1.3 人工蜂群聚類算法

人工蜂群聚類算法是根據(jù)大自然中蜂群尋覓蜜源的原理結(jié)合基本聚類算法形成的算法。與其他群智能聚類算法相似，人工蜂群聚類保留了蜂群算法（artificial bee colony algorithm，ABC）［57］在處理問題上深度搜索能力強的優(yōu)勢。這種算法具備無需先驗信息、需控參數(shù)少等特性，且具有強大的搜索能力，在聚類過程表現(xiàn)出很好的準(zhǔn)確性與穩(wěn)定性。

1.3.1 人工蜂群聚類算法的仿生思想

自然界蜂群尋找優(yōu)質(zhì)蜜源的方式是通過蜂群內(nèi)每只蜜蜂的不同分工實現(xiàn)的。其中包括引領(lǐng)蜂、跟隨蜂和偵察蜂。引領(lǐng)蜂負責(zé)在蜜源周圍進行搜索，采用貪婪原則尋找更優(yōu)蜜源。跟隨蜂會依靠引領(lǐng)蜂傳遞的信息對蜜源進行選擇。當(dāng)長時間蜜源未發(fā)生改變時，偵察蜂會放棄該蜜源探索新蜜源。

引領(lǐng)蜂與跟隨蜂用（8）式尋找新蜜源：

其中，xij為第i 蜜源的第j 個維度值，vij為新的蜜源，α、i、k隨機產(chǎn)生且α∈（0，1），i≠k。

當(dāng)引領(lǐng)蜂與跟隨蜂未找到更好蜜源，偵查蜂則會用（9）式隨機尋找新蜜源，代替被拋棄蜜源。

1.3.2 與K-Means結(jié)合的人工蜂群聚類算法案例

ABC 單獨在聚類問題中的應(yīng)用［58］容易 出 現(xiàn)蜜源間差異小、蜜源位置過于隨機，導(dǎo)致種群多樣性下降，降低聚類效果。文獻［59］提出了一種模仿蜜蜂覓食的蜂群算法與K-Means 算法結(jié)合的人工蜂群聚類算法IMABCK（IM Artificial Bee Colony Clustering Based On K-Means）。IMABCK 通過與KMeans 結(jié)合后降低對初始聚類中心的依賴性，減少孤立點對聚類結(jié)果的干擾，提高了聚類的準(zhǔn)確度。

IMABCK 算法先通過一次K-Means迭代將數(shù)據(jù)進行預(yù)處理，得到的聚類結(jié)果作為蜜源的適應(yīng)值，利用人工蜂群對各個聚類中心進行優(yōu)化，優(yōu)化后的聚類中心再進行K-Means聚類。

IMABCK算法的具體實現(xiàn)步驟如下：

步驟1：初始化參數(shù)，分別設(shè)置引領(lǐng)蜂、跟隨蜂個數(shù)Sn，聚類中心數(shù)k，最大迭代次數(shù)max_A，控制參數(shù)Limit，孤立點刪除；

步驟2：利用最大最小積法初始化聚類中心；

步驟3：定義聚類中心，對聚類中心進行一次K-Means 算法迭代，依靠適應(yīng)度函數(shù)計算每只蜜蜂的適應(yīng)度并排序；

步驟4：引領(lǐng)蜂以（8）式進行鄰域搜索，并按貪婪原則替換蜜源；

步驟5：待引領(lǐng)蜂全部搜索完畢，跟隨蜂按輪盤賭選擇引領(lǐng)蜂并執(zhí)行引領(lǐng)蜂的任務(wù)繼續(xù)鄰域搜索；

步驟6：待跟隨蜂全部搜索完畢，依靠所得蜜源位置作為聚類中心，執(zhí)行一次K-Means 迭代并用迭代后中心點更新蜂群；

步驟7：達到Limit 迭代時判斷引領(lǐng)蜂的尋覓結(jié)果，如果不發(fā)生改變，則將引領(lǐng)蜂全部變?yōu)閭刹旆洳矗?）式產(chǎn)生新蜜源；

步驟8：迭代次數(shù)大于等于max_A 則輸出聚類中心，否則轉(zhuǎn)向步驟3。

1.3.3 人工蜂群聚類算法的應(yīng)用

人工蜂群聚類保留了蜂群智能算法中控制參數(shù)少、魯棒性性強、易于實現(xiàn)等優(yōu)點，能夠很好地完成聚類任務(wù)，被廣泛應(yīng)用在各種聚類與數(shù)值優(yōu)化問題中。以下列舉了人工蜂群聚類算法被主要應(yīng)用的幾個領(lǐng)域。

1）圖 像 分 割：VENKATA 等［60］使 用 結(jié) 合KMeans算法的人工蜂群聚類算法實現(xiàn)了衛(wèi)星圖像分割；PAN 等［61］通過改進鄰域搜索機制的人工蜂群聚類算法對視網(wǎng)膜圖像分割；ALAGARSAMY 等［62］將蜂群聚類應(yīng)用在MR人腦的醫(yī)學(xué)圖像。

2）物聯(lián)網(wǎng)：WANG等［63］用改進人工蜂群與優(yōu)化模糊C-Means 聚類結(jié)合應(yīng)用在無線傳感器網(wǎng)絡(luò)節(jié)能路由協(xié)議。

此外，KUMAR 等［64］、DEHKORDI等［65］利用優(yōu)化的人工蜂群聚類對很多數(shù)據(jù)集也表現(xiàn)出很好的聚類效果。

2 相似性度量方法

在對數(shù)據(jù)樣本進行仿生聚類的過程中，通常都避免不了對樣本數(shù)據(jù)的相似性度量，即樣本與樣本之間的差異，主要為樣本距離與相似系數(shù)兩個方面，樣本距離與相似系數(shù)的內(nèi)容如下。

2.1 樣本距離

通常會用兩個樣本之間的距離來表示樣本的相似性。只有當(dāng)兩個樣本完全一樣時，樣本的距離才為0；否則樣本距離始終大于0。常用的距離公式為歐式距離、切比雪夫距離、曼哈頓距離等［66-67］。進行仿生聚類前，需分析樣本本身的屬性適合哪一種距離公式。列舉樣本距離度量方法如下。

設(shè)D（X，Y）為樣本X 和樣本Y 之間的距離，X=（x1，x2，…，xn）T，Y=（y1，y2，…，yn）T，n為樣本維數(shù)。

1）歐式距離（Euclidean Distance）

歐式距離通常趨向于構(gòu)建球形聚類簇，其計算公式表示為

2）切比雪夫距離（Chebyshev Distance）

切比雪夫距離的計算公式表示為

3）曼哈頓距離（Manhattan Distance）

曼哈頓距離的計算公式表示為

2.2 相似系數(shù)

樣本數(shù)據(jù)的相似性不僅用距離表示，還可以利用相似系數(shù)［68］。相似系數(shù)值與樣本間的相似性呈現(xiàn)負相關(guān)，相似系數(shù)越大則兩個樣本之間的相似性越差。常見的相似系數(shù)有余弦相似度、皮爾森相關(guān)系數(shù)等。根據(jù)距離公式假設(shè)列舉相關(guān)系數(shù)如下。

1）余弦相似度（Cosine Similarity）

余弦相似度的表現(xiàn)形式為

2） 皮 爾 森 相 關(guān) 系 數(shù)（Pearson Correlation Coefficient）

皮爾森相關(guān)系數(shù)的表現(xiàn)形式為

3 聚類結(jié)果無監(jiān)督評價方法

在對樣本仿生聚類后，通常會對聚類結(jié)果進行對比與評價，人工評價的成本過高且低效、主觀，不利于對算法進行優(yōu)化與改進，因此采用相對更適合的無監(jiān)督評價。常見無監(jiān)督評價聚類結(jié)果的方法有輪廓系數(shù)、誤差平方和、DB 指數(shù)、CH 指數(shù)［69］。其中輪廓系數(shù)不適合不同聚類的比較、DB 指數(shù)不適合環(huán)狀分布聚類評價、CH 指數(shù)不適合基于密度的聚類算法評價。聚類結(jié)果無監(jiān)督評價方法如下：

1）輪廓系數(shù)（SC）

輪廓系數(shù)主要由簇內(nèi)樣本的聚合度a（xi）與簇間樣本的差異度b（xi）表示，當(dāng)SC越接近1則聚類效果越好，SC的表現(xiàn)形式為

2）誤差平方和（SSE）

誤差平方和的聚類效果判斷主要來自計算原始數(shù)據(jù)與擬合數(shù)據(jù)。例如對K-Means聚類中SSE越接近0 則擬合效果越好，其中m 為原始樣本點，p 為預(yù)測值。SSE的表現(xiàn)形式為

3）Davies-Bouldin（DB）指數(shù)

當(dāng)DB 指數(shù)越小則聚類效果越好。其中k 為聚類簇數(shù)，d（xi，xj）（i≠j）為兩個簇中心的距離，a 為簇中心與簇內(nèi)所有點距離和的平均值。DB 的表現(xiàn)形式為

4）Calinski-Harabasz（CH）指數(shù)

當(dāng)CH 指數(shù)越大則聚類效果越好。其中聚類簇數(shù)用k 表示，樣本數(shù)用n 表示，簇內(nèi)樣本的協(xié)方差矩陣為Wk，簇間的樣本協(xié)方差矩陣為Bk。CH 的表現(xiàn)形式為

4 結(jié)論與展望

仿生聚類算法的出現(xiàn)解決了單純的聚類方法中所存在的參數(shù)難以確認、局部最優(yōu)、易收斂等不足，在仿生算法中融合基本聚類方法，用仿生算法的優(yōu)化機制提升了聚類效果。在不同問題上其聚類效果都優(yōu)于單純的仿生算法與基本的聚類方法。尤其在求解結(jié)構(gòu)復(fù)雜、大規(guī)模、多樣化的聚類問題時，仿生聚類算法在計算效率和收斂精度方面均有更好的表現(xiàn)。隨著仿生算法的優(yōu)化和聚類算法的發(fā)展，未來仿生聚類算法可在以下幾個方面進一步展開研究。

1）算法改進方面。根據(jù)不同聚類任務(wù)將仿生算法與基礎(chǔ)聚類算法多樣性結(jié)合，例如：果蠅算法除了和K-Means 還可以嘗試與其他基礎(chǔ)聚類算法結(jié)合；可以在聚類分析時對不同階段的聚類過程結(jié)合仿生聚類思想進行優(yōu)化；利用生物其他智能行為結(jié)合聚類算法對聚類分析的研究等，進一步發(fā)揮算法優(yōu)勢。

2）參數(shù)改進方面。仿生聚類算法的參數(shù)選取受過往研究者的主觀因素過大，有些仿生算法或聚類算法的參數(shù)過多會增大聚類任務(wù)難度。因此，這些算法的結(jié)合思想、運行流程、數(shù)學(xué)基礎(chǔ)等有待于進一步研究。

3）算法應(yīng)用方面。仿生聚類算法的發(fā)展在聚類分析中擁有強大的優(yōu)勢與生命力。各種算法具有不同的優(yōu)勢和局限性，針對不同的聚類任務(wù)可以進行聚類分析比較再嘗試仿生聚類的選取與思想結(jié)合，利用各自的優(yōu)勢或許會獲得計算能力更強的算法進而解決愈發(fā)復(fù)雜的問題。