ABC聚類算法與KHM算法相結(jié)合的ABCKHM聚類算法

姜 華，胡 欣，王 崢，都興朔

(1.東北師范大學信息科學與技術學院，吉林 長春 130117； 2.東北師范大學智能信息處理吉林省高校重點實驗室，吉林 長春 130117)

ABC聚類算法與KHM算法相結(jié)合的ABCKHM聚類算法

姜 華1，2，胡 欣1，2，王 崢1，2，都興朔1，2

(1.東北師范大學信息科學與技術學院，吉林 長春 130117； 2.東北師范大學智能信息處理吉林省高校重點實驗室，吉林 長春 130117)

針對調(diào)和K均值聚類(KHM)算法存在陷入局部最優(yōu)解的問題，提出一種人工蜂群(ABC)算法與KHM算法相結(jié)合的混合聚類算法ABCKHM.實驗表明，該算法解決了KHM算法有時陷入局部最優(yōu)解的問題，并且該算法較之KHM算法及同類其他算法有更好的性能.

聚類；KHM；人工蜂群優(yōu)化；ABC

聚類分析是一大類數(shù)據(jù)挖掘方法的總稱，是數(shù)據(jù)挖掘的一個重要領域.聚類過程就是把事物聚集到幾類中，使得不同類中的對象盡可能的不同，同一類中的對象盡可能相似[1].調(diào)和K均值聚類(KHM)算法1999年被提出[2].KHM算法相比于K-means算法減少了對初始中心點的依賴[3-4].2005年Karaboga提出的人工蜂群(ABC)算法的優(yōu)化算法，最初是為解決多變量函數(shù)優(yōu)化問題，模擬了蜜蜂群體的采蜜行為.[5]ABC算法具有全局尋優(yōu)、收斂速度快等很多優(yōu)點，該算法經(jīng)過合理設置優(yōu)化目標函數(shù)可以應用于聚類問題.本文提出一種混合聚類算法ABCKHM，結(jié)合了ABC聚類算法與KHM算法的思想，借助ABC聚類算法全局尋優(yōu)能力，解決KHM可能陷入局部最優(yōu)的問題.

1 KHM算法

KHM算法比K-means算法雖減輕了對中心點初始選擇的依賴，但是KHM算法仍有可能陷入局部最優(yōu)解.KHM算法相關概念和記法如下[6]：

xi(i=1，2，…，n)：數(shù)據(jù)對象.

cj(j=1，2，…，k)：第j簇的中心點.

KHM(X，C)：KHM算法的目標函數(shù).

m(cj/xi)：隸屬函數(shù)，表示數(shù)據(jù)對象xi屬于第j個簇的程度.

w(xi)：權(quán)值函數(shù).

KHM算法的主要步驟如下：

Step1：初始化算法參數(shù)，隨機選擇初始中心點.

Step2：計算目標函數(shù)KHM(X，C)，公式為

(1)

其中p是輸入?yún)?shù)，通常取p≥2.

Step 3：計算隸屬度m(cj/xi)，公式為

(2)

其中m(cj/xi)∈[0，1].

Step 4：計算數(shù)據(jù)對象xi的權(quán)值w(xi)，公式為

(3)

Step 5：根據(jù)xi的隸屬度m(cj/xi)和權(quán)值w(xi)重新計算類的中心點

(4)

Step 6：重復Step 2—5，直至目標函數(shù)KHM(X，C)的值不再改變或達到最大循環(huán)次數(shù)MaxGen.

Step 7：分配數(shù)據(jù)對象xi到隸屬度m(cj/xi)最大的第j個簇中.

2 ABC優(yōu)化算法

ABC優(yōu)化算法模擬自然界中的蜜蜂采蜜行為，用食物源的位置表示優(yōu)化問題的解[7].蜂群有引領蜂、跟隨蜂和偵察蜂3種：引領蜂收集食物源的蜜量等信息；跟隨蜂在蜂巢等待并察看引領蜂的動作信號(舞蹈)，從中獲取信息決定是否跟隨；偵察蜂則隨機地尋找食物源.設有SN個食物源，ABC算法規(guī)定引領蜂數(shù)量=跟隨蜂數(shù)量=食物源數(shù)量.優(yōu)化解集合包含SN個D維向量，第i個解為xi=(xi1，xi2，…，xiD)，i=1，…，SN，食物源的花蜜量對應適應度值，也即解的質(zhì)量.

ABC算法在初始化過程中隨機產(chǎn)生SN個初始解，進而計算它們的適應度值.然后，循環(huán)使用引領蜂、跟隨蜂和偵察蜂更新食物源位置，最終完成最優(yōu)解的搜索過程.引領蜂判斷附近食物源的花蜜量(適應度值)，如果新食物源高于現(xiàn)有的花蜜量，則引領蜂記住新食物源，放棄現(xiàn)有的食物源，否則，仍保持不變，即進行一個貪心選擇過程.引領蜂搜索過后，通過跳舞動作傳遞食物源信息給跟隨蜂，跟隨蜂進行評估，計算每個食物源與花蜜量相關的概率值，并優(yōu)先選取值較大的食物源，依據(jù)貪心選擇過程進一步嘗試更新.每個食物源的概率值計算公式為

(5)

其中fiti表示食物源的適應度值.

ABC算法修正現(xiàn)有食物源xi的位置，計算公式為

vij=xij+Rij(xij-xkj).

(6)

其中：k隨機選取，k∈{1，2，…，SN}且k≠i，j∈{1，2，…，D}；Rij是[-1，1]間的隨機數(shù)，控制著在食物源xi附近什么位置產(chǎn)生新食物，本質(zhì)是鄰域搜索.

ABC算法中，如果在limit次循環(huán)后一個食物源還沒有被更新，那么放棄這一食物源，偵察蜂隨機尋找新食物源取代之.這個過程計算公式為

(7)

ABC算法有食物源總數(shù)SN、limit值、最大循環(huán)數(shù)MaxCycle 3個控制參數(shù).ABC優(yōu)化算法如下：

(1) 初始化MaxCycle及l(fā)imit，置cycle=1.

(2) 隨機生成各個最初的食物源xi，并計算適應度值fiti(i=1，…，SN).

(3) 循環(huán)，反復執(zhí)行下列步驟，直到cycle達到預定迭代次數(shù)MaxCycle：

(a) 派出SN個引領蜂，根據(jù)公式(6)更新第i(i=1，…，SN)個食物源，并計算其適應度值newfiti，與原有食物源的適應度值fiti比較，若newfiti>fiti則記下這個食物源，反之丟棄；

(b) 使用公式(5)計算各個食物源的概率Pi；

(c) 派出SN個跟隨蜂，根據(jù)Pi判斷是否需要再次更新食物源，更新方式同步驟(a)；

(d) 記下更新后得到的更好食物源；

(e) 派出偵察蜂，重新初始化經(jīng)過limit次嘗試一直沒有得到更新的食物源；

(f) cycle=cycle+1.

(4) 輸出求得的最優(yōu)函數(shù)值及對應的食物源，算法結(jié)束.

3 ABC聚類算法

我們對ABC優(yōu)化算法進行改進，得到一種新的ABC聚類算法[8].

ABC優(yōu)化算法的目標在于尋找k個(取決于具體問題)食物源，以使給定的目標函數(shù)值達到最小.當把ABC優(yōu)化算法應用于聚類問題時，每一個食物源對應一個中心點.如果度量使用歐氏距離，ABC聚類過程就將數(shù)據(jù)對象分配到與之有最短歐式距離的食物源所在的簇中，并最小化上述聚類目標函數(shù)f.

ABC優(yōu)化算法中每一個食物源的適應度fiti定義為

(8)

其中fi是目標函數(shù)的當前值，fi越小，fiti越大.把ABC優(yōu)化算法用于聚類問題時，則目標函數(shù)f值越小，食物源的適應度值越大，聚類效果越好.

4 ANCKHM聚類算法

以ABC聚類算法對數(shù)據(jù)集進行初始聚類，將得到的k個中心點作為KHM算法的初始聚類中心，再運行KHM算法獲得最終聚類結(jié)果.由于ABC聚類算法的全局尋優(yōu)特點，新算法能有效地減少KHM算法陷入局部最優(yōu)的問題.新的ABCKHM聚類算法如下：

(ABC聚類算法優(yōu)化中心點階段)

(1) 初始化MaxCycle及l(fā)imit，置cycle=1.

(2) 隨機生成初始食物源xi，并計算其適應度值fiti(i=1，…，SN).

(3) 循環(huán)，反復執(zhí)行下列步驟，直到cycle達到預定迭代次數(shù)MaxCycle：

(a) 派出SN個引領蜂，根據(jù)公式(6)更新第i(i=1，…，SN)個食物源，并計算其適應度值newfiti，與原有食物源的適應度值fiti比較，若newfiti>fiti則記下這個食物源，反之丟棄；

(b) 使用公式(5)計算各個食物源的概率Pi；

(c) 派出SN個跟隨蜂，根據(jù)Pi決定是否需要再次更新食物源，更新方式同步驟(a)；

(d) 記下SN個更好的食物源，把數(shù)據(jù)點劃分到離它最近的食物源所在的簇中；

(e) 派出偵察蜂，重新初始化經(jīng)過limit次嘗試仍未更新的食物源；

(f) cycle=cycle+1.

(4) 輸出SN個簇最好的食物源.

(KHM聚類算法階段)

(5) 將ABC聚類算法的食物源作為KHM算法初始中心點.

(6) 根據(jù)公式(1)—(3)計算目標函數(shù)KHM(x，c)、隸屬度m(cj/xi)、權(quán)值w(xi).

(7) 根據(jù)公式(4)重新計算類的中心點cj，cycleKHM=cycleKHM+1.

(8) 循環(huán)執(zhí)行步驟(6)和(7)，直至目標函數(shù)KHM(X，C)的值不再改變或達到最大循環(huán)次數(shù)MaxGen.

(9) 分配數(shù)據(jù)對象xi到隸屬度m(cj/xi)最大的簇中.

5 實驗部分

本文實驗在Pentium (R) CPU 2.5 GHZ+512 MB RAM平臺上進行，采用C++編碼.為了測試ABCKHM混合聚類算法的性能，使用3個標準數(shù)據(jù)集Iris、Glass和Wine.ABCKHM聚類算法使用的初始參數(shù)見表1.

5.1 數(shù)據(jù)集

實驗使用的3個數(shù)據(jù)集Iris、Glass和Wine的信息見表2.

表1 ABCKHM算法設置的參數(shù)初值

表2 數(shù)據(jù)集特征

數(shù)據(jù)集詳細描述：

Iris(n=150，d=4，k=3)是機器學習領域一個經(jīng)典的數(shù)據(jù)集.這個數(shù)據(jù)集包括Iris Setosa、Iris Versicolour和Iris Virginica三類數(shù)據(jù)對象.每類都有50個4維的數(shù)據(jù)對象，4維屬性分別是sepal length、sepal width、petal length和petal width.

Glass(n=214，d=10，k=7)是另一個常用的機器學習數(shù)據(jù)集，包含214個數(shù)據(jù)對象、維數(shù)10個、7類數(shù)據(jù)對象.

Wine(n=178，d=13，k=3)是一個著名的用于機器學習的數(shù)據(jù)集，描述3種不同的意大利酒，包括178個數(shù)據(jù)對象、維數(shù)13、3大類數(shù)據(jù)對象.

5.2 性能評估方法

本文用F-Measure函數(shù)來評估算法聚類效果[9].F-Measure度量包括精確率(p(i，j))和召回率(r(i，j))兩個組成部分，分別定義為

其中：ni是聚類算法求得的第i類中的數(shù)據(jù)點數(shù)；nj是數(shù)據(jù)集第j類中真實的數(shù)據(jù)點數(shù)；nij是前述2個集合交集的數(shù)據(jù)點數(shù)；p(i，j)代表算法的準確性；r(i，j)代表算法的查全率.F-Measure定義為

其中取b=1，使得p(i，j)和r(i，j)的權(quán)值相等.如果數(shù)據(jù)集的大小為n，整體的F-Measure定義為

F-Measure的值越大，算法的聚類效果越好.

5.3 實驗結(jié)果及分析

圖1 ABCKHM聚類算法在3個數(shù)據(jù)集上10次運行的準確率

本文進行了2組實驗：(1)研究了ABCKHM聚類算法的穩(wěn)定性；(2)ABCKHM聚類算法與同類其他算法(KHM算法、FKH算法、KHM-SAPSO算法、KHM-CPSO算法)進行了對比.

首先，為驗證ABCKHM聚類算法的穩(wěn)定性，分別在3個數(shù)據(jù)集(Glass、Iris、Wine)上運行10次，聚類的準確率如圖1所示，結(jié)果非常穩(wěn)定.ABCKHM聚類算法的準確率表明其有效避免了KHM算法有時會陷入局部最優(yōu)解的問題.

為進一步驗證ABCKHM聚類算法的效果，把ABCKHM聚類算法與已有的KHM算法、FKH算法、KHM-SAPSO算法、KHM-CPSO算法進行對比，分別在3個數(shù)據(jù)集上運行10次，再分別取準確率(Accuracy)的平均值及F-Measure的平均值.當p=3.5時的實驗結(jié)果見表3.

表3 KHM、FKH、KHM-SAPSO、KHM-CPSO 和ABCKHM聚類算法的結(jié)果(p=3.5)

結(jié)果顯示：ABCKHM聚類算法的準確率及F-Measure值均優(yōu)于同類其他算法.

6 結(jié)束語

本文把ABC算法改寫為聚類算法，將其求得的聚類中心作為KHM算法的初始中心點并運行KHM算法求得最后聚類結(jié)果.本質(zhì)是借助ABC聚類算法的全局尋優(yōu)特性來克服KHM的固有缺點.實驗結(jié)果表明，本文提出的ABCKHM聚類算法的性能優(yōu)于傳統(tǒng)KHM算法及其他同類算法.但是對于Iris和Wine這樣維數(shù)較高的數(shù)據(jù)集而言，聚類效果還有很大提升空間，將是后續(xù)研究的重點.

[1] XU RUI，DONALD WUNSCH，Survey of clustering algorithms[J].IEEE Transactions on Neural Networks，2005，16(3)：645-678.

[2] JIANG HUA，YI SHENGHE，LI JING，et al.Ant clustering algorithm with K-harmonic means clustering [J].Expert Systems with Applications，2010，37(12):8679-8684.

[3] GRIGORIOS TZORTZIS，ARISTIDIS LIKAS.The minmax K-means clustering algorithm[J].Pattern Recognition，2014，47(7)：2505-2516.

[4] KRISBNA K，NARASIMHA MURTY M.Genetic K-means algorithm [J].IEEE Transactions on Systems，Man，Cybernetics，Part B，1999，29(3):433-439.

[5] YURTKURAN ALKIN，EMEL ERDAL.An adaptive artificial bee colony algorithm for global optimization [J].Applied Mathematics and Computation，2015，271(15):1004-1023.

[6] GüNG?R Z，üNLER A.K-harmonic means data clustering with tabu-search method [J].Applied Mathematical Modelling，2008，32(6):1115-1125.

[7] SONG X Y，YAN Q F，ZHAO M.An adaptive artificial bee colony algorithm based on objective function value information [J].Applied Soft Computing，2017，55(7):384-401.

[8] KARABOGA D，OZTURK C.A novel clustering approach: artificial bee colony (ABC) algorithm [J].Applied Soft Computing，2011，11(1):652-657.

[9] MARATEA A，PETROSINO A，MANZO M.Adjusted F-measure and kernel scaling for imbalanced data learning [J].Information Sciences，2014，257(1):331-341.

AhybridclusteringalgorithmABCKHMcombiningABCandKHM

JIANG Hua1，2，HU Xin1，2，WANG Zheng1，2，DU Xing-shuo1，2

(1.School of Information Science and Technology，Northeast Normal University，Changchun 130117，China；2.Key Laboratory of Intelligent Information Processing of Jilin Province，Northeast Normal University，Changchun 130117，China)

It is still possible that K-harmonic means clustering algorithm reach local minimal value.Artificial bee colony optimization algorithm has good performance in global optimization，so the clustering algorithm derived from artificial bee colony optimization algorithm ought to overcome the problem of trapping in local optimization.This article proposes a hybrid clustering algorithm (ABCKHM) combining artificial bee colony algorithm and K-harmonic means algorithm.Our algorithm has better global searching capability，faster speed，and stability.

clustering； K-harmonic means clustering； artificial bee colony optimization； artificial bee colony clustering

1000-1832(2017)04-0066-05

10.16163/j.cnki.22-1123/n.2017.04.013

2017-09-29

國家自然科學基金資助項目(71473035).

姜華(1964—)，男，碩士，副教授，主要從事數(shù)據(jù)挖掘研究.

TP 31學科代碼520·10

A

(責任編輯：石紹慶)