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

仇樺+周蓮英

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

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

文獻標識碼：A

文章編號：16727800（2017）004005504

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

1Kmeans聚類算法

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

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

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

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

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

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

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

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

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

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

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

4實驗仿真與分析

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

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

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

5結語 本文針對Kmeans算法及人工魚群算法各自的優(yōu)缺點，提出一種融合Kmeans和人工魚群的數(shù)據(jù)聚類算法IAFSAKM。在此算法中，首先根據(jù)魚群規(guī)模和步長兩個參數(shù)對人工魚群算法的影響，引入淘汰機制和自適應的最大步長策略。淘汰策略中對適應值作歸一化處理，設置的參數(shù)為一個小于1的比例值，使用多極值函數(shù)驗證了本文改進算法，結果表明本文算法可以降低復雜度，提高收斂速度和尋優(yōu)精度。其次，完成人工魚位置結構編碼和適應度函數(shù)設計。使用Iris和Wine數(shù)據(jù)集、EPA-HTTP日志數(shù)據(jù)對IAFSAKM算法進行驗證。實驗表明，IAFSAKM算法對初始聚類中心不敏感，可以實現(xiàn)全局尋優(yōu)，聚類準確率高，結果穩(wěn)定。參考文獻：[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.數(shù)據(jù)挖掘概念與技術[M].范明，孟小峰，譯.北京：機械工業(yè)出版社，2001.

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

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

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

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

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

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

（責任編輯：杜能鋼）