韓曉慧，王聯(lián)國

(1.甘肅農(nóng)業(yè)大學(xué)工學(xué)院，甘肅蘭州730070;2.甘肅農(nóng)業(yè)大學(xué)信息科學(xué)技術(shù)學(xué)院，甘肅蘭州730070)

0 引言

聚類分析［1］作為數(shù)據(jù)挖掘在實(shí)際應(yīng)用中的主要任務(wù)之一，是數(shù)據(jù)挖掘領(lǐng)域中一個很活躍的研究課題。近幾十年來得到了快速發(fā)展和成功應(yīng)用。所謂聚類就是按照某個特定標(biāo)準(zhǔn)(一般為距離準(zhǔn)則)把一個數(shù)據(jù)集分割成不同的類或簇，使得在類內(nèi)的數(shù)據(jù)點(diǎn)的相似性盡可能大，同時類間的數(shù)據(jù)點(diǎn)的差異性也盡可能大［2］。

目前聚類算法主要分為:劃分聚類、層次聚類、基于網(wǎng)格的聚類和基于密度的聚類。K—均值算法作為劃分聚類中最經(jīng)典的聚類算法之一，但它是一個局部搜索的算法，存在一些嚴(yán)重不足［3］:K值需要預(yù)先確定;聚類結(jié)果的好壞依賴于初始簇中心點(diǎn)的選取等。為此，許多研究者提出了基于智能優(yōu)化算法的聚類方法［4～6］。

混合蛙跳算法作為智能算法的一種優(yōu)化算法，是2000年由Eusuff和Lanse通過類比青蛙的覓食行為與優(yōu)化問題求解的相似性而提出了一種新的基于全局協(xié)同搜索的智能優(yōu)化方法。由于具有概念簡單、參數(shù)少、求解快速等諸多優(yōu)點(diǎn)已被應(yīng)用于許多自然科學(xué)與工程科學(xué)領(lǐng)域，顯示出強(qiáng)大的優(yōu)勢和潛力。對求解實(shí)優(yōu)化問題，大量實(shí)驗(yàn)已證實(shí)，混合蛙跳算法較遺傳算法收斂速度快、效率高。鑒于此，本文在文獻(xiàn)［7］討論改進(jìn)混合蛙跳算法的基礎(chǔ)上，提出了一種新的改進(jìn)混合蛙跳的聚類算法，對算法進(jìn)行了實(shí)驗(yàn)分析，并與基于傳統(tǒng)混合蛙跳聚類算法、基于遺傳聚類算法和基于蟻群聚類算法進(jìn)行了比較，仿真實(shí)驗(yàn)證明本文提出的算法性能優(yōu)于這幾種算法。

1 K—均值聚類算法

K—均值算法是一種基于劃分的方法，假設(shè)給定有n個對象的數(shù)據(jù)庫和聚類數(shù)目K。一個劃分方法構(gòu)建數(shù)據(jù)的K個劃分(K≤n)，每一個劃分代表一個聚類。聚類依據(jù)對象之間的相似度函數(shù)，通常用距離來衡量，而距離度量的方式有很多，對于RN空間中的向量，最直觀的距離度量是向量之間的歐氏距離d=‖x－z‖。聚類的結(jié)果是達(dá)到類間的對象盡可能不同，類內(nèi)的對象盡可能相似。

K均值聚類算法的過程描述如下:

輸入:數(shù)據(jù)集 X=(x1，x2，…，xn)，聚類數(shù)目 K

輸出:K個簇Cj

K—均值算法步驟描述如下:

1)從{x1，x2，…，xn}中隨機(jī)選取K個數(shù)據(jù)對作為初始簇(聚類)中心 z1，z2，…，zk;

2)計算每一個數(shù)據(jù)點(diǎn)xi，i=1，2，…，n與這K個簇中心Cj，j∈{1，2，…，k}的距離，如果滿足‖xi－zj‖＜‖xi－zm‖，m=1，2，…K，m≠j則 xi∈Cj

為防止不能滿足步驟(4)的終止條件出現(xiàn)無限循環(huán)，一般在算法執(zhí)行時給一個固定最大迭代次數(shù)。

2 混合蛙跳算法

2.1 傳統(tǒng)混合蛙跳算法

混合蛙跳算法(SFLA)是一種受自然生物模仿啟示而產(chǎn)生的基于群體的協(xié)同搜索方法。在SFLA中，青蛙群體(解集)由一群具有相同結(jié)構(gòu)的青蛙(解)組成，整個群體被分為多個子群，每個子群有自己的文化，執(zhí)行局部搜索策略。子群中的青蛙均具有自己的思想，在局部搜索迭代次數(shù)結(jié)束之后，各個子群之間進(jìn)行思想交流，實(shí)現(xiàn)子群間的混合運(yùn)算。局部搜索和混合過程一直持續(xù)到定義的收斂條件結(jié)束為止，全局信息交換和局部深度搜索的平衡策略使得算法能夠跳出局部極值點(diǎn)，向著全局最優(yōu)的方向進(jìn)行［7］。

對于S維優(yōu)化問題，SFLA算法首先從已知可行域中隨機(jī)生成P只青蛙組成初始群體，第i只青蛙表示問題的解為Xi=(xi1，xi2，…，xis)，計算每只青蛙的目標(biāo)函數(shù)值f(Xi)，將每只青蛙根據(jù)其目標(biāo)函數(shù)值按遞減順序排列，然后將整個青蛙群體劃分為m個子群，每個子群中包含n只青蛙。

對于每一個子群，目標(biāo)函數(shù)值最好的解記為Xb和目標(biāo)函數(shù)值最差的解記為Xc，而群體中目標(biāo)函數(shù)值最好的解記為Xg。在每次迭代中，只對子群中的Xc進(jìn)行更新操作，其更新策略為

其中，j=1，2，…，s，Dmax≥Dj≥－Dmax，Dj為分量 j上移動的距離，Dmax為青蛙的最大移動步長。

經(jīng)過更新后如果得到的解newXc優(yōu)于原來的解oldXc，則取代原來族群中的解。否則，則用Xg取代Xb重復(fù)執(zhí)行更新策略

如果仍然沒有改進(jìn)，則隨機(jī)產(chǎn)生一個新的解取代原來的Xc。重復(fù)這種更新操作，直到設(shè)定的迭代次數(shù)，當(dāng)所有子群的局部深度搜索完成后，將所有族群的青蛙重新混合、排序和劃分族群，然后再進(jìn)行局部深度搜索，如此反復(fù)直到達(dá)到事先設(shè)定的混合次數(shù)。

2.2 改進(jìn)混合蛙跳算法

改進(jìn)SFLA中，在文獻(xiàn)［7］的基礎(chǔ)上，提出了新的移動距離更新方式，每個族群進(jìn)行局部深度搜索時，除了分量j上移動的距離引入上一次的移動距離，另外也加入了慣性權(quán)重系數(shù)，用來調(diào)節(jié)搜索能力。所以，式(2)變?yōu)?/p>

其中，w 為慣性權(quán)重系數(shù)，設(shè)置為0.9～0.4，D'j表示本次更新時分量j上移動的距離，Dj表示上次更新時分量j上移動的距離，群體初始化時，Dj以隨機(jī)方式產(chǎn)生。

經(jīng)過更新后如果得到的解newXc優(yōu)于oldXc，則取代原來族群中的解，否則，按下式計算移動距離

式(6)不包含上次移動距離，因?yàn)樯洗伟词?5)更新后的解比原來的解更差，說明上次的移動距離不夠理想，所以式(6)消除了歷史不良影響，使得青蛙快速移動到全局最優(yōu)解附近，從而可以加快收斂速度。如果newXc仍然沒有改進(jìn)，則隨機(jī)產(chǎn)生一個新的解取代oldXc。改進(jìn)SFLA中除了移動距離的計算方式與傳統(tǒng)SFLA不同外，其他操作都與傳統(tǒng)SFLA相同。

3 基于改進(jìn)混合蛙跳的聚類算法

3.1 適應(yīng)度函數(shù)設(shè)計

混合蛙跳算法在處理過程中以適應(yīng)度函數(shù)為依據(jù)，利用種群中每個個體的適應(yīng)度值來進(jìn)行搜索。因此，影響混合蛙跳算法的收斂速度重要的是適應(yīng)度函數(shù)的選取。對于每個個體，進(jìn)行聚類的劃分和重新計算各聚類的中心采用與K—均值算法相同的方式，然后根據(jù)每個聚類中的點(diǎn)與相應(yīng)聚類中心的距離和作為判斷聚類劃分質(zhì)量的評價函數(shù)，E越小表示聚類劃分質(zhì)量越好。

混合蛙跳算法的目的是搜索使評價函數(shù)最小的聚類中心，因此借助評價函數(shù)構(gòu)造適應(yīng)度函數(shù)如下

3.2 算法流程

本文提出的基于改進(jìn)混合蛙跳的聚類算法流程如下:1)設(shè)定算法初始參數(shù)。

2)初始化種群和K個初始聚類中心。

3)對種群中的青蛙個體執(zhí)行K-means操作。即，計算待分類集合{x1，x2，…，xn}到青蛙對應(yīng)的K個中心的距離，根據(jù)距離將{x1，x2，…，xn}分類。

4)由分類計算出每只青蛙的適應(yīng)度，按適應(yīng)度大小對青蛙種群進(jìn)行降序排列，隨機(jī)生成Dj。

5)將青蛙群體分成m個族群，每個族群包含n只青蛙，確定各個族群中的最優(yōu)解Xb、最差解Xc以及全局最優(yōu)解Xg。

6)按式(3)和式(5)更新最差解 Xc得到 newXc，對newXc進(jìn)行約束處理，若newXc優(yōu)于oldXc，則取代oldXc;否則，按式(3)和式(6)更新最差解Xc得到新的newXc，再對newXc進(jìn)行約束處理。更新族群中的最優(yōu)解和最差解，局部迭代次數(shù)加1，重復(fù)執(zhí)行以上過程，直到達(dá)到設(shè)定的最大局部迭代次數(shù)，跳至步驟(7)。

7)將族群合并成一個青蛙群體重新按適應(yīng)度函數(shù)值對青蛙群體進(jìn)行降序排列，全局迭代次數(shù)加1，跳至步驟(5)。重復(fù)執(zhí)行以上過程，直到達(dá)到設(shè)定的全局最大迭代次數(shù)，算法終止，輸出結(jié)果。

4 實(shí)驗(yàn)結(jié)果

通過UCI數(shù)據(jù)庫中兩組實(shí)際數(shù)據(jù)集Crude oil和Iris數(shù)據(jù)集來驗(yàn)證本文算法的性能。數(shù)據(jù)集信息概況如表1所示。

表1 Crude oil和Iris數(shù)據(jù)集的信息Tab 1 Information of Crude oil and Iris data set

為了能進(jìn)一步驗(yàn)證本文算法的性能測試，將本文算法與基于傳統(tǒng)混合蛙跳算法(SFLA)、基于遺傳算法(GA)和基于蟻群算法(ACO)［8～10］的聚類結(jié)果進(jìn)行了比較，通過運(yùn)行多次來比較算法的性能，如表2，表3。

表2 四種算法對Crude oil聚類性能比較Tab 2 Comparison of Crude oil clustering characteristic by the four algorithms

表3 四種算法對Iris聚類性能比較Tab 3 Comparison of Iris data clustering characteristic by the four algorithms

由以上表2、表3可以看出:基于改進(jìn)混合蛙跳的聚類算法得到的結(jié)果，在收斂精度和速度上都能達(dá)到較好的聚類效果，優(yōu)于基于傳統(tǒng)混合蛙跳算法、遺傳算法和蟻群算法的聚類方法。

5 結(jié)束語

K—均值聚類算法因其思想簡單而成為聚類分析最常用方法之一，但K—均值法分類的結(jié)果依賴于選擇的初始聚類中心，對于有些初始解K—均值法可能收斂于次優(yōu)解。許多學(xué)者提出了基于智能優(yōu)化算法的聚類方法來解決K—均值算法的這一缺陷。本文提出的基于改進(jìn)混合蛙跳算法的聚類方法，引入了K—均值操作，提高了算法的局部搜索能力和收斂速度。實(shí)驗(yàn)結(jié)果驗(yàn)證了基于改進(jìn)混合蛙跳算法的聚類方法的有效性和優(yōu)越性。

［1］Jain A K，Murty M N，F(xiàn)lynn P J.Data clustering:A review［J］.ACM Computing Surveys，1999，31(3):264－323.

［2］楊小兵.聚類分析中若干關(guān)鍵技術(shù)的研究［D］.杭州:浙江大學(xué)，2005.

［3］Huang Z.Extensions to the K-means algorithm for clustering large data sets with categorical values［J］.Data Ming and Knowledge Discovery，1998(2):283－297.

［4］劉向東，沙秋夫，劉勇奎，等.基于粒子群優(yōu)化算法的聚類分析［J］.計算機(jī)工程，2006，32(6):201－203.

［5］陸林花，王 波.一種改進(jìn)的遺傳聚類算法［J］.計算機(jī)工程與應(yīng)用，2007，43(21):170－172.

［6］劉 白，周永權(quán).一種基于人工魚群的混合聚類算法［J］.計算機(jī)工程與應(yīng)用，2008，44(18):136－138.

［7］鄭仕鏈，樓才義，楊小牛.基于改進(jìn)混合蛙跳算法的認(rèn)知無線電協(xié)作頻譜感知［J］.物理學(xué)報，2010，59(5):3612－3617.

［8］Amiri B，F(xiàn)athian M，Maroosi A.Application of shuffled frogleaping algorithm on clustering［J］.International Journal of Advanced Manufacturing Technology，2009，45:199－209.

［9］Krishna K，Murty N.Genetic K-means algorithm［J］.IEEE Trans on SMC，1999，29:433－439.

［10］Shelokar P S，Jayaraman V K，Kulkarni B D.An ant colony approach for clustering［J］.Anal Chim Acta，2004，509:187－195.