K—means和人工魚群結合的聚類算法研究

仇樺+周蓮英

摘要：針對Kmeans算法對初始聚類中心敏感、容易收斂于局部極值和人工魚群算法最大步長固定、尋優精度不高、后期收斂速度慢的問題，提出一種Kmeans和人工魚群相結合的聚類算法。該算法將Kmeans聚類中心引入人工魚群適應度函數，自動確定近似全局最優的初始聚類中心，并將其作為Kmeans初值詳細進行局部搜索，以提高精度。同時采用淘汰機制和自適應的最大步長策略，優化人工魚群算法性能。在Iris、Wine數據集和EPA-HTTP應用日志數據上對IAFSAKM算法進行實驗仿真分析，驗證了算法的有效性和可行性。

關鍵詞：Kmeans；人工魚群算法；聚類；淘汰機制；自適應策略DOI：10.11907/rjdk.162799中圖分類號：

文獻標識碼：A

文章編號：16727800（2017）004005504

0引言 數據聚類是靜態數據分析技術，目標是將數據集合分成若干簇，使得同一簇內的數據點相似度盡可能大，而不同簇間數據點相似度盡可能小。目前在數據挖掘[1]、機器學習[2]、人工神經網絡[3]、圖像分析[4]、模式識別[5]以及無線傳感器網絡[6]等領域應用十分廣泛。Kmeans算法[7]是其中最著名也是最簡單的一個聚類方法，能有效解決許多聚類問題。但是聚類算法有兩大缺陷：①對初始點敏感；②易陷入局部最優。 人工魚群算法（Artificial Fish Swarm Algorithm， AFSA）是一種基于仿生行為的群體智能全局尋優算法 [8]，具有收斂速度快、對初始值不敏感、靈活性好及較高的容錯率等一系列優點，能較好地解決優化問題，然而，單一的聚類方法往往得不到最佳聚類效果。 針對該問題，本文在改進的人工魚群算法基礎上結合Kmeans聚類算法，提出了一種新的混合聚類算法IAFSAKM：先將引入了淘汰機制和自適應最大步長策略的人工魚群算法（IAFSA）對Kmeans的聚類過程進行優化。用一條人工魚表示一次選擇的k個初始聚類中心，把Kmeans的聚類中心引入取誤差平方和函數倒數的適應度函數，人工魚在尋優過程中自動確定全局近似最優的聚類中心。該方法彌補了Kmeans算法對初始中心敏感、容易收斂于局部極值的缺點；然后將該聚類中心作為Kmeans的初始中心進行局部搜索，利用Kmeans的快速收斂性，進一步提高尋優精度。在Iris和Wine數據集和EPA-HTTP應用日志數據上進行對比實驗，證明了該算法的有效性和可行性。

1Kmeans聚類算法

Kmeans算法[9]是一種基于劃分的聚類分析方法。聚類中心個數k是一個給定的正整數，P={P1，P2，…，Pn}是一個具有n個數據樣本的數據集，其中Pi={Pi1，Pi2，…，Pim}表示數據集中具有m個屬性的m維樣本。Kmeans算法以歐式距離作為相似性度量標準，遵循類內相似度高和類間相似度低的原則，相似度計算則根據類中對象的平均值進行。聚類問題就是要找到k個聚類中心C={C1，C2，…，Ck}，使得數據集中的每個數據樣本都屬于一個類，且僅屬于一個類。假設Ci={Ci1，Ci2，…，Cim}，Pj∈Ci，則Pj到Ci的歐式距離為D（Pj，Ci）=〖JP3〗〖KF（〗（Pj1-Ci1）2+（Pj2-Ci2）2+…+（Pjm-Cim）2

。Kmeans算法是使各樣本點到各自類中心的歐式距離和最小。Kmeans算法易于描述，具有時間效率高且適于處理大規模數據等優點，但卻存在需要預先確定k值、受初始聚類中心影響以及容易收斂于局部最優解等不足。〖BT1〗〖STHZ〗〖WTHZ〗2人工魚群算法（AFSA）及其改進人工魚群算法[10]是一種基于動物行為的群體智能算法，它通過模擬魚群的隨機、覓食、聚群、追尾等行為，相互協作來達到問題的最優解。算法主要包括覓食行為、聚群行為、追尾行為，可控參數包括魚群規模—N、魚的視野即搜索范圍—visual、魚的步長即每次可移動的最遠距離—step、擁擠度因子—δ、嘗試次數—try_number、算法的適應度函數—Y=f（X），即人工魚當前所在位置的食物濃度等。〖BT2〗〖STHZ〗〖WTHZ〗2.1人工魚群算法實現每條個體魚都能自行或尾隨其它人工魚找到富含食物的地方，所以通常魚生存較多的地方就是富含營養最多的地方。依據這一特點來模仿魚群覓食、聚群及追尾行為，實現尋優，這就是人工魚群算法的基本思想。人工魚群算法步驟如下：（1）初始化人工魚群算法參數。參數包括魚群規模、視野范圍、步長、人工魚初始位置、最大迭代次數、嘗試次數、擁擠度因子等。（2）更新每條人工魚位置。如果滿足對應條件，則按下列規則動態更新人工魚的位置信息：設人工魚當前狀態為Xi，根據條件執行如下行為操作：覓食行為：覓食就是魚趨向食物的行為。當前人工魚在視野visual范圍內隨機選擇一個狀態Xj，其中Xj=Xi+rand（）×visual，式中rand（）函數為0～1之間的隨機數，執行以下操作：

2.2人工魚群算法改進人工魚群作為一種隨機搜索算法，在聚類問題中無需預先設置聚類中心和類別個數，表現出強魯棒性和高效率特性。人工魚群算法的計算復雜度與種群規模有關。隨著個體數量增加，存儲空間隨之增多，計算時間也隨之延長。在尋優后期，大步長會讓人工魚在全局極值區域來回震蕩，影響尋優精度，小步長則會降低算法的收斂速度。針對以上兩個參數對人工魚群算法性能產生影響的問題，本文引入淘汰機制優化計算復雜度，提出自適應最大步長策略，優化收斂速度和尋優精度[11]。

2.2.1基于淘汰策略的計算復雜度優化人工魚群算法經過一定量的迭代后，適應度小的魚對算法性能影響不大，本文引入淘汰機制。該機制的思想來自于自然界“弱肉強食”現象，即弱小的魚會被強大的魚吃掉。通過引入淘汰機制減少種群數量，實現降低算法計算量的目的。本文引入一個新的參數θ，約定經過最大迭代次數的一半后，計算式（5）的值。式中Ymax、Ymin表示一次迭代中最大、最小適應度值，Yi表示與Ymax、Ymin同一次迭代中第i條人工魚的適應度。將Ti與θ比較，若Ti小于θ，就淘汰對應的人工魚，此時魚群規模會相應減少。在設置淘汰機制中的參數θ時需對適應度函數最優狀態有一定了解。本文對Yi作歸一化處理，得到的Ti是適應度函數值的比例形式。設置參數θ是一個小于1的正數，以提高淘汰機制在優化問題中的適用性。

2.2.2基于自適應最大步長的收斂速度和尋優精度優化本文引入自適應的最大步長概念，在尋優初期，給人工魚設置最大步長，盡可能快地找到全局極值區域，提高算法收斂速度。在尋優后期，給人工魚設置最小步長，以提高算法的尋優精度。自適應最大步長公式如式（6）、式（7）所示，IT為最大迭代次數，α是一個常數，t表示第幾次迭代。公告牌除了記錄最優人工魚狀態之外，還增加了迭代次數和同一次迭代中最小適應度值。

3 融合Kmeans和人工魚群的聚類算法IAFSAKM 魚群算法和聚類分析問題有著天然的對應關系[12]，因此將人工魚群算法引入聚類分析領域。IAFSAKM算法結合了人工魚群算法和Kmeans算法優點，既能克服算法對于初始聚類中心選擇敏感的問題，又能提高人工魚群后期收斂速度，能夠在較短的時間內獲得最優的聚類劃分。

3.1IAFSAKM算法實現人工魚群算法AFSA的每個解由人工魚的位置和該位置的適應度值兩部分組成，如式（8）所示。在解決組合優化問題時，要根據目標函數和變量特點確定合適的位置和適應度函數。

3.2人工魚位置編碼結構人工魚群算法AFSA在搜索空間內對適應度函數尋優時，一條人工魚是一個潛在的解；Kmeans算法在給定的數據集上對誤差平方和尋優時，選定的k個初始聚類中心是一個潛在的解。因此，可以在人工魚和k個初始聚類中心之間建立一種映射關系，對人工魚位置結構編碼，本文使用實數編碼方式。對人工魚位置結構編碼，用一條人工魚代表一種聚類方案。人工魚群算法在迭代前先隨機初始化n條人工魚。對于Kmeans 算法而言，就是隨機給出n種初始聚類中心，這n種聚類中心其實是n種聚類方案。人工魚執行行為就是從n種聚類方案中選擇最優的一種。人工魚編碼結構表示如下：

3.3適應度函數本文在介紹人工魚群算法AFSA時均以極大值為例，誤差平方和函數是要被最小化的，因此取誤差平方和函數的倒數作為人工魚群算法AFSA的適應度函數，這樣就把聚類中心引入到人工魚群算法AFSA的適應度函數中。適應度函數表示為式（10）：

J是誤差平方和函數，m為常數，k為聚類中心個數，Ci是聚類中心，xj是數據對象。使用下面的方法計算人工魚適應度：①根據距離最短原則，確定一條人工魚個體代表的聚類劃分；②根據步驟①的聚類劃分計算誤差平方和函數值和新的聚類中心；③根據步驟②誤差平方和函數值，由式（10）計算人工魚個體的適應度。由上面3個步驟可知，如果一條人工魚的適應度最大，就說明這條魚代表的聚類劃分誤差平方和最小。表1是人工魚編碼。

3.4IAFSAKM算法實現 Kmeans和人工魚群相結合的IAFSAKM算法[13]步驟如下：①設置參數。設置魚群規模、視野、步長、嘗試次數、擁擠度因子、Kmeans和人工魚群算法的最大迭代次數、聚類數目，常數m取值為1；②初始化魚群，計算所有人工魚適應度，記錄最優個體狀態；③對每條人工魚評估行為，嘗試執行覓食、聚群、追尾、隨機這4種行為，選擇適應度最大的行為執行；④更改位置或淘汰人工魚，計算新位置的適應度，更新最優狀態；⑤如果達到最大的迭代次數就結束迭代，輸出最優解。反之返回步驟③；⑥把IAFSA的輸出作為Kmeans的初始聚類中心；⑦計算數據對象相似度并歸類。使用歐式距離計算剩余的數據對象與中心的相似度。根據距離最短、相似度最大原則，把數據對象劃分到距它最近的聚類中心所屬類；⑧計算誤差平方和函數值與新的聚類中心。新的聚類中心由一個類內所有點的算術平均值表示；⑨判斷：準則函數值滿足一定條件或達到迭代次數，算法結束。當前中心點就是要輸出的結果。否則返回步驟⑦繼續執行。Kmeans和人工魚群相結合的IAFSAKM算法流程如圖1所示。

4實驗仿真與分析

表2顯示兩種算法性能指標比較結果，這些結果是程序獨立運行15次取平均之后的值。其中BV表示最優解，MBV表示平均最優解，MSG表示尋優成功的平均迭代次數。從表中可知，改進后的算法三項性能指標較優，BV和MBV值小表明算法的尋優精度高，MSG低表明尋優速度快。〖HJ*3〗可見，引入淘汰機制和自適應的最大步長策略的人工魚群算法計算量較低，收斂速度較快，同時保證了算法精度。 為了更直觀地反映新算法的聚類效果，本文從標準數據集UCI中選擇Iris和Wine兩個真實數據集來驗證IAFSAKM算法性能。 Iris：以鳶尾花的特征作為數據來源，數據集包含150個樣本，分為3類，每類有50個包含4個屬性的數據，是數據挖掘、數據分類中常用的測試集、訓練集。 Wine：葡萄酒識別，以178個樣本分成3個不同的類，分別包含13個屬性的59、71和48個樣本。 人工魚群算法各參數設置如下：N=30，step=1，δ=8，visual=2.5，try_number=50，閾值為0.3，迭代次數為100。 本文用聚類準確率衡量算法性能，準確率用被分配到正確簇的數據元素個數與總數據元素個數的百分比表示。由所選數據集可知，聚類數目為3，每一次隨機選擇3個點作為Kmeans和IAFSAKM算法的初始中心點，共選擇15次。本文約定設置最大迭代次數作為Kmeans算法的終止條件，取最大迭代次數為50。算法在運行15次后得到的平均準確率如表3所示。

從表3數據可知，IAFSAKM算法可以處理低維、也可以處理高維數據集。在15次隨機選擇初始點情況下，IAFSAKM的平均準確率高于Kmeans。這說明IAFSAKM算法用于聚類時得到的聚類結果穩定，可見IAFSAKM算法對初始中心點不敏感，實現了全局尋優。 EPA-HTTP日志數據是互聯網流量文庫Trace數據中的一類。日志數據共47 748條日志記錄。每一條日志信息屬性有：IP或域名、訪問時間、請求方式、請求地址、HTTP協議類型、狀態碼、返回信息大小。對日志數據預處理（數據清洗、用戶識別、會話識別、事務識別）得到用戶訪問向量集，使用Canopy算法粗略確定聚類數目為6，迭代次數設置為100；使用IAFSAKM算法對用戶訪問向量集聚類，每一次隨機選擇6個用戶向量作為IAFSAKM和Kmeans的輸入，共選擇3次。每個類的用戶向量數目如表4所示。

可以看到在確定聚類數目后，Kmeans得到的類中向量數目變化較大，不穩定；IAFSAKM算法得到的類中向量數目變化小，比較穩定。這說明本文提出的IAFSAKM算法不依賴初始中心點，解決了Kmeans算法在聚類時很難收斂到全局最優解問題，提高了聚類準確度。

5結語 本文針對Kmeans算法及人工魚群算法各自的優缺點，提出一種融合Kmeans和人工魚群的數據聚類算法IAFSAKM。在此算法中，首先根據魚群規模和步長兩個參數對人工魚群算法的影響，引入淘汰機制和自適應的最大步長策略。淘汰策略中對適應值作歸一化處理，設置的參數為一個小于1的比例值，使用多極值函數驗證了本文改進算法，結果表明本文算法可以降低復雜度，提高收斂速度和尋優精度。其次，完成人工魚位置結構編碼和適應度函數設計。使用Iris和Wine數據集、EPA-HTTP日志數據對IAFSAKM算法進行驗證。實驗表明，IAFSAKM算法對初始聚類中心不敏感，可以實現全局尋優，聚類準確率高，結果穩定。參考文獻：[1]DATTA SOUPTIK，GIANNELLA CHRIS，KARGUPTA HILLOL，et al.Approximate Distributed KMeans clustering over a peertopeer network [J].IEEE Transactions on Knowledge and Data Engineering，2009，21（10）：13721388.

[2]YANG X L，SONG Q，ZHANG W B.Kernelbased deterministic annealing algorithm for data clustering [J] .IEEE Proceedings on Vision，Image and Signal Processing，2007（153）：557568.

[3]AJIT K SAHOO，MING J ZUO，MK TIWARI， et al. A data clustering algorithm for stratified data partitioning in artificial neural network [J].Expert Systems with Application，2012，39（8）：70047014.

[4]GONG M，LIANG Y，SHI J，et al.Fuzzy CMeans clustering with local information and kernel metric for image segmentation[J].IEEE Transactions on Image Processing，2013，22（2）：573584.

[5]ZHANG L J，CHENG S，CHANG C K，et al.A Patternrecognitionbased algorithm and case study for clustering and selecting business services [J].IEEE transactions on systems，man，and cybernetics.Part A，Systems and humans，2012，42（1）：102114.

[6]ALI PEIRAVI，HABIB RAJABI MASHHADI，S HAMED JAVADI，et al.An optimal energyefficient clustering method in wireless sensor networks using multiobjective genetic algorithm [J].International journal of communication systems，2013，26（1）：114126.

[7]HAN JIAWEI，MICHELINE K.數據挖掘概念與技術[M].范明，孟小峰，譯.北京：機械工業出版社，2001.

[8]楊淑瑩，張樺.群體智能與仿生計算： Matlab技術實現[M].北京：電子工業出版社，2012： 110.

[9]肖琪. 基于優化Kmeans算法的電力負荷分類研究[D].大連：大連理工大學，2015.

[10]李曉磊. 一種新型的智能優化方法人工魚群算法[D].杭州：浙江大學，2003.

[11]王培崇，雷鳳君，錢旭.改進人工魚群算法及其收斂性分析[J].科學技術與工程，2013，13（3）：616620.

[12]汪麗娜，陳曉宏，李粵安，等.基于人工魚群算法和模糊C2均值聚類的洪水分類方法[J].水利學報，2009，40（6）：743755.

[13]何登旭，曲良東.一種新的混合聚類分析算法[J].計算機應用研究，2009，26（3）：879880.

（責任編輯：杜能鋼）