基于優(yōu)化人工魚群算法的混合聚類研究

田 琳，田力威，劉啟文

（1.沈陽大學(xué) 信息工程學(xué)院，遼寧 沈陽110044；2.遼寧省物聯(lián)網(wǎng)信息集成技術(shù)工程研究中心，遼寧 沈陽110044；3.大連理工大學(xué) 電子信息與電氣工程學(xué)部，遼寧 大連116012）

0 引 言

混合聚類的本質(zhì)是聚類，它根據(jù)不同對象之間特征的差異將數(shù)據(jù)進(jìn)行模式分類，使同簇內(nèi)的樣本相似度較高，而不同簇中的樣本相異度較大［1］，從而發(fā)現(xiàn)數(shù)據(jù)的分布規(guī)律與數(shù)據(jù)間的相關(guān)性。K－中心點算法是一種魯棒性較強的劃分方法，采用距離中心最近的點來代表簇，這樣處理噪聲數(shù)據(jù)的效果好并且不用提前定義［2］，它在知識發(fā)現(xiàn)、信息預(yù)測決策分析有著重大作用。但此算法易受離群點和局部最值點影響，聚類初始化參數(shù)的隨機性對聚類結(jié)果起決定性作用。

文中運用的新型群智能算法—人工魚群算法。人工魚群算法將生物界中的群體智能用于解決優(yōu)化問題，作為一種廣義的鄰域搜索算法，借助于啟發(fā)式的搜索策略，具有快速跟蹤變化能力，從而具有全局尋優(yōu)的能力，由于本身具有全局收斂能力，因此初值設(shè)置為固定值或隨機值都可以，參數(shù)可設(shè)置的范圍較廣，適應(yīng)性、并行性較強。該算法具有很強的靈活性，有多種行為組合可選取，以得到較好的優(yōu)化性能，這是遺傳算法和粒子群算法等優(yōu)化算法不具備的優(yōu)點。近些年基于群智能的混合聚類方法成為熱門的研究方向，融合各自算法的優(yōu)勢，從減小誤差率、聚類準(zhǔn)確性、以及對經(jīng)驗參數(shù)的選擇方面都取得了很大的進(jìn)展。其中應(yīng)用較廣的有粒子群和K 均值算法［3］混合、蟻群結(jié)合C－均值［4］算法和基于魚群算法的聚類技術(shù)等。

近幾年，基于人工魚群的混合算法有很多，文獻(xiàn)［5］提出了縮小搜索域的方法來加速人工魚個體局部搜索，但這種方法只優(yōu)化收斂速度，使人工魚追尾和聚群行為受到很大局限，從而影響到算法尋優(yōu)質(zhì)量。文獻(xiàn)［6］引入了K－平均值算法加快了算法迭代速度，由于人工魚群算法在很多地方采用的是隨機處理，因此算法的性能不穩(wěn)定，影響了算法的實際應(yīng)用。文獻(xiàn)［7］利用模擬退火算法來改進(jìn)人工魚群算法，在該算法中通過修改人工魚的覓食行為避免了人工魚的退化，這種混合算法雖然克服了易陷入局部極值的缺點，但是算法收斂性時間較長，不適用于海量數(shù)據(jù)的分析。文獻(xiàn)［8］將人工魚群算法和基于網(wǎng)格和密度的聚類算法相結(jié)合，新的混合聚類算法有較好的并行性，但是最終聚類質(zhì)量受到網(wǎng)格數(shù)目和網(wǎng)格大小的影響，在算法執(zhí)行過程中有一定的局限性。

因此，結(jié)合K－中心點算法與人工魚群算法的優(yōu)勢，本文提出了基于優(yōu)化人工魚群算法的混合聚類算法，該算法解決了初始化聚類中心敏感問題，全局優(yōu)化性能穩(wěn)定，文中在檢測到的小數(shù)據(jù)集上進(jìn)行測試，證明改進(jìn)后的算法獲得較好的聚類成果。

1 聚類模型

X＝（x1，x2，…xN）作為N 個樣品數(shù)據(jù)，x 是數(shù)據(jù)的代表點，Ci是任意一個簇，Oi是簇Ci的中心點，（j＝1，2…，k）。

算法描述：在樣本集X 中任意選取k 個對象作為k 個簇的初始中心點（O1，O2，…Oi…Ok）；將除了代表中心點的其余數(shù)據(jù)利用最臨近原則分配到各個簇中；在每個簇（Ci）中，隨機地選取一個非中心點Oj，計算用非中心點代替原簇中心點［9］后的總代價ΔE。如果ΔE＜0，就用非中心點Oj替換原中心點Oi；反復(fù)執(zhí)行以上步驟直到k個中心點固定下來。用代價函數(shù)來評估聚類質(zhì)量是否改善。該函數(shù)構(gòu)成如下

式中：ΔE——絕對誤差標(biāo)準(zhǔn)的改變量，E2——替換中心點后數(shù)據(jù)集中所有代表點與其同簇中中心點之間的相異度的和，E1——未替換前數(shù)據(jù)集中所有代表點與其同簇中中心點之間的相異度的和。計算ΔE＜0，則代表替換后聚類效果提高，則替換掉該中心點，否則仍用原中心點。

2 優(yōu)化人工魚群算法

2.1 基本行為描述

設(shè)人工魚個數(shù)為N、人工魚個體的狀態(tài)F＝（f1，f2，…fn），［其中fi為欲尋優(yōu)的變量］、人工魚移動的最大步長Step、人工魚的視野Visual、覓食最大試探次數(shù)Try＿number、擁擠度因子δ、人工魚所在位置的食物濃度Y＝f（F）（Y 為目標(biāo)函數(shù)值）。

（1）覓食行為：覓食行為作為人工魚的基本習(xí)性之一，主要原理是魚群通過視覺與味覺趨向于食物濃度大的區(qū)域。設(shè)置當(dāng)前人工魚狀態(tài)為Fi，隨機選擇當(dāng)前位置視野內(nèi)一個狀態(tài)

式中：Rand（）∈（0，1），再求優(yōu)化解過程中，若Yi＜Yj，說明狀態(tài)更優(yōu)則向此位置方向前進(jìn)一個步長

若不符合前進(jìn)條件則隨機選擇狀態(tài)Fj，重新判斷，反復(fù)試探Try＿number次后，若仍無法找出更優(yōu)解，則隨機移動［11］一步

（2）聚群行為：魚在游動時為確保群體的生存，會向鄰近伙伴的中心聚集。Fi仍對應(yīng)當(dāng)前人工魚狀態(tài)，感知當(dāng)前位置附近（視野內(nèi)）人工魚數(shù)目nf及其位置的中心Fc。若Yc／nf＞δYi，則說明該中心位置食物較多、擁擠度較小，則向Fc［12］進(jìn)一步

若不滿足則執(zhí)行覓食行為。

（3）追尾行為：魚在游動時當(dāng)其中一條或幾條魚探索到食物時，其鄰域范圍內(nèi)的魚會尾隨魚群到達(dá)食物位置。Fi對應(yīng)當(dāng)前人工魚狀態(tài)，感知當(dāng)前位置附近人工魚中狀態(tài)最優(yōu)的Fj，若滿足Yj／nf＞δYi則顯示Fj位置附近的食物較多、擁擠度較小，則向Fj前進(jìn)一步見式（3），判斷不符合條件則執(zhí)行覓食行為。

2.2 人工魚群算法的改進(jìn)

（1）在覓食行為中，F(xiàn)j視野范圍內(nèi)隨機選取的狀態(tài)，當(dāng)隨機選的一個狀態(tài)食物不滿足前進(jìn)條件時選擇隨機移動行為，隨機行為的存在使得尋優(yōu)難以得到很高的精度，到了收斂后期會造成人工魚在全局極值點迂回搜索，導(dǎo)致無效計算。本文改進(jìn)為當(dāng)覓食失敗時，人工魚向公告板記錄的相比之下狀態(tài)較好的值前進(jìn)一步

式中：Fbetter——告板記錄較好的狀態(tài)，相對于隨機行為給出了更好的前進(jìn)可能性，進(jìn)而跳出局部最優(yōu)，防止人工魚在局部震蕩而停滯不前。

（2）在人工魚群算法中，參數(shù)擁擠度因子δ的引入是為了避免魚群過度擁擠，并且δ是算法執(zhí)行過程中的定值，這種全局δ固定的方式會導(dǎo)致全局優(yōu)化解附近的人工魚群個體之間相互排斥而不能準(zhǔn)確的聚集到極值點，且迭代后期每次都對比是否滿足擁擠度條件會增加計算成本。本文改進(jìn)為定義算法執(zhí)行初期擁擠度因子δ＝0.75，當(dāng)Try＿number＝180時，忽略擁擠度因子即δ·nf＝1，算法初期希望限制人工魚的規(guī)模，但在后期人工魚基本聚集在較優(yōu)狀態(tài)附近，缺省δ減少計算量和算法執(zhí)行時間，這樣改進(jìn)不僅提高算法運行效率，并且不影響算法收斂性。

（3）在求解中心點問題的人工魚群算法中，當(dāng)執(zhí)行聚群行為和追尾行為失敗后，每次都執(zhí)行覓食行為，這樣不僅增加了收斂時間，每次迭代的計算量也將增大，因此聚群行為和追尾行為可改進(jìn)為：當(dāng)人工魚前進(jìn)一步失敗后，缺省覓食行為而是執(zhí)行隨機游行為，且隨機游行為選擇自適應(yīng)步長，這樣克服了人工魚在極值點聚集而錯過全局極值點的問題，優(yōu)化的算法使求解質(zhì)量精度更高。

3 基于優(yōu)化人工魚群算法的混合聚類算法

3.1 改進(jìn)的人工魚群算法相關(guān)定義

定義1 人工魚自適應(yīng)步長：自適應(yīng)步長表示人工魚移動的距離隨著迭代次數(shù)增加而改變。自適應(yīng)步長定義為

定義2 聚類評價準(zhǔn)則：目標(biāo)函數(shù)度量對象與其簇的代表對象的平均相異，表示類間數(shù)據(jù)分布的緊密程度，目標(biāo)函數(shù)定義為

3.2 基于優(yōu)化人工魚群算法的混合聚類算法過程描述

（1）設(shè)置人工魚參數(shù)的初值，利用目標(biāo)函數(shù)計算當(dāng)前位置的食物濃度。

（2）通過魚群行為的執(zhí)行條件和人工魚前進(jìn)準(zhǔn)則，每條人工魚分別執(zhí)行覓食、追尾、聚群等行為，算法中的食物濃度可以參照為數(shù)據(jù)密度，對比視野范圍內(nèi)食物濃度選擇優(yōu)劣解，將其狀態(tài)記錄到公告板上，最終人工魚聚集在了數(shù)據(jù)密度高的區(qū)域。

（3）每條人工魚的狀態(tài)代表一個決策變量，通過計算目標(biāo)函數(shù)值來評價魚的尋優(yōu)程度，將其狀態(tài)記錄在公告板上，重復(fù)（2）（3），更新人工魚的位置信息，達(dá)到最大迭代次數(shù)時算法終止，最終選擇能表示初始聚類中心的解。

（4）依據(jù)公告板信息和魚群的位置，選出K－中心點算法的輸入?yún)?shù)，即初始中心點和聚類個數(shù)；用K－中心點算法進(jìn)行聚類分析，使數(shù)據(jù)類內(nèi)離散度之和達(dá)到最小，最小離散度函數(shù)：M＝minE。

基于人工魚群算法的優(yōu)化聚類算法流程如圖1所示。

圖1 基于人工魚群算法的優(yōu)化聚類算法流程

4 仿真實驗

仿真數(shù)據(jù)包括300 個三維數(shù)據(jù)，實驗運行環(huán)境為：Pentium（R）D，3.00G內(nèi)存，編程環(huán)境：Matlab7.12.0（R2011a），實驗參數(shù)：Step＝0.2、Visual＝100、Try＿number＝200、N＝50，δ＝0.75。

實驗運用了兩種混合聚類算法對300個數(shù)據(jù)進(jìn)行分類，對比基于基本魚群算法和改進(jìn)的魚群算法與K 中心點算法結(jié)合的兩種混合聚類算法的實驗結(jié)果。未迭代前數(shù)據(jù)分布如圖2所示，經(jīng)典混合聚類算法運行結(jié)果如圖3所示，圖4則是本文提出的改進(jìn)后的混合聚類算法實驗結(jié)果圖。

圖2 未迭代前數(shù)據(jù)分布

圖3 基本人工魚群聚類算法迭代完成的尋優(yōu)

圖4 改進(jìn)后的人工魚群聚類算法迭代完成的尋優(yōu)

人工魚在三維數(shù)據(jù)中尋找中心點，如圖3聚集效果不清晰，部分移動到個別局部團簇附近，由圖4中的尋優(yōu)路線可看出優(yōu)化結(jié)果可逼近到全局?jǐn)?shù)據(jù)密集處，從圖3和圖4可以看出本文改進(jìn)后的人工魚聚類邊緣更明顯，聚集在更緊密的位置，得到了精確性較高的劃分結(jié)果，驗證了此算法的優(yōu)越性。兩種算法的實驗結(jié)果對比見表1。

表1 兩種算法的實驗結(jié)果

表1說明在人工魚個數(shù)和算法迭代次數(shù)等條件相同的情況下，文中提出的算法在迭代時間上有所減少，降低了算法執(zhí)行過程中的計算量，由表1也可以看出正確率也有提高。

5 結(jié)束語

通過混合聚類方法來解決決策、預(yù)警等問題是目前研究、應(yīng)用廣泛的一個問題。由實驗結(jié)果圖對比表明，本文提出的改進(jìn)后的全局人工魚群混合聚類算法，使特性相似的數(shù)據(jù)聚集效果明顯，通過改進(jìn)的魚群算法與K－中心點算法結(jié)合的數(shù)學(xué)模型，更精確地展示了樣本間的差異，提高了聚類質(zhì)量，獲得較優(yōu)的中心點與清晰地聚類劃分，并且在減小算法計算量上也有所突破。作為一種基于動物自治體模型的新型現(xiàn)代智能算法與K－中心點算法結(jié)合的一種混合聚類算法，避開了聚類算法初值依賴性問題，克服了魚群算法后期迭代速度慢問題，其良好的并行性可有效的應(yīng)用在各種領(lǐng)域，但是算法的收斂速度問題還有待改善與研究。

［1］Han Jiawei，Kamber M.Data mining：Concepts and techniques［M］.2rd ed.Beijing：China Machine Press，2007：252－272 （in Chinese）.［Han Jiawei，Kamber M.數(shù)據(jù)挖掘概念與技術(shù) ［M］.2 版.北京：機械工業(yè)出版社，2007：252－272.］

［2］XIA Ningxia，SU Yidan.An efficient k－medoids clustering algorithm ［J］.Application Research of Computers，2010，27（12）：4517－4519 （in Chinese）.［夏寧霞，蘇一丹.一種高效的K－medoids 聚類算法［J］.計算機應(yīng)用研究，2010，27（12）：4517－4519.］

［3］TAO Xinmin，XU Jing，YANG Libiao，et al.An improved hybrid algorithm based on particle swarm optimization and Kmeans algorithm ［J］.Journal of Electronics ＆Information Technology，2010，32 （1）：92－94 （in Chinese）. ［陶新民，徐晶，楊立標(biāo)，等.一種改進(jìn)的粒子群和K 均值混合聚類算法 ［J］電子與信息學(xué)報，2010，32 （1）：92－94.］

［4］WANG Xiaohua，SHEN Jie，WANG Rongbo.A new hybrid algorithm based on ant colony and clustering ［J］.Journal of Hangzhou Dianzi University，2010，30 （1）：26－27 （in Chinese）.［王小華，沈杰，王榮波.一種新的基于蟻群和凝聚的混合聚類算法 ［J］.杭州電子科技大學(xué)學(xué)報，2010，30 （1）：26－27.］

［5］FAN Yujun，WANG Dongdong，SUN Mingming.Improved artificial fish swarm algorithm ［J］.Journal of Chongqing Normal University （Natural Science Edition），2007，24 （3）：24－26 （in Chinese）.［范玉軍，王冬冬，孫明明.改進(jìn)的人工魚群算法 ［J］.重慶師范大學(xué)學(xué)報 （自然科學(xué)版），2007，24（3）：24－26.］

［6］LIU Bai，ZHOU Yongquan.A hybrid clustering algorithm based on artificial fish swarm algorithm ［J］.Computer Engineering and Applications，2008，44 （18）：136－138 （in Chinese）.［劉白，周永權(quán).一種基于人工魚群的混合聚類算法［J］.計算機工程與應(yīng)用，2008，44 （18）：136－138.］

［7］LIU Jia.Improved artificial fish swarm algorithm and its applications in function optimization ［J］.Journal of Shijiazhuang Institute of Railway Technology，2011，10 （3）：33－36 （in Chinese）.［劉佳，改進(jìn)人工魚群算法及在函數(shù)優(yōu)化問題中的應(yīng)用 ［J］.石家莊鐵路職業(yè)技術(shù)學(xué)院學(xué)報，2011，10 （3）：33－36.］

［8］HE Dengxu，QU Liangdong.Artificial fish swarm clustering algorithm ［J］.Application Research of Computers，2009，26（10）：3666－3668 （in Chinese）.［何登旭，曲良東.人工魚群聚類分析算法 ［J］.計算機應(yīng)用研究，2009，26 （10）：3666－3668.］

［9］Xie Juanying，Jiang Shuai.A simple and fast algorithm for global k－means clustering ［C］／／Wuhan：Second International Workshop on Education Technology and Computer Science，2010：36－40.

［10］Chu Xiaoli，Zhu Ying，Shi Juntao，et al.Method of image segmentation based on fuzzy C－means clustering algorithm and artificial fish swarm algorithm ［C］／／Guilin：International Conference on Intelligent Computing and Integrated Systems，2010：254－257.

［11］Cheng Yongming，Jiang Mingyan，Yuan Dongfeng.Novel clustering algorithms based on improved artificial fish swarm algorithm ［C］／／Tianjin：Sixth International Conference on Fuzzy Systems and Knowledge Discovery，2009：141－145.

［12］JIANG Mingyan，YUAN Dongfeng.Artificial fish swarm algorithm and its applications ［M］.Beijing：Science Press，2012：43－66，110－130 （in Chinese）. ［江銘炎，袁東風(fēng).人工魚群算法及其應(yīng)用 ［M］.北京：科學(xué)出版社，2012：43－66，110－130.］