基于MapReduce和改進人工蜂群算法的并行劃分聚類算法

陶 濤，毛伊敏

(江西理工大學信息工程學院，贛州 341000)

聚類分析作為數據挖掘中一種無監督學習過程，可以通過數據對象的相關特征，把類似的數據對象劃為一類，而具有較大差異性的數據對象則劃到不同類，因此聚類分析可以從樣本數據中發現隱藏的分布模式，在圖像分割、信息檢索系統、異常檢測、計算機視覺和施工管理等領域廣泛應用[1]。在聚類算法中，基于劃分的聚類算法，如K-means[2-3]和K-medoids[4]算法，具有簡單易理解、算法收斂速度快等特點，受到人們的廣泛關注。

隨著互聯網技術的快速發展以及大數據時代的到來，使得大數據相較于傳統數據，具有了體積大(volume)、種類多(variety)、速度快(velocity)、價值高(value)的“4V”特性[5]。但由于傳統的劃分聚類算法在處理大數據集時，時間復雜度較高，只適用于小規模的數據集。所以，如何降低劃分聚類算法的計算復雜度，使其能處理大數據，是個關鍵性的難題。

近年來，隨著Google公司成功研發了MapReduce框架，以Hadoop、Spark為代表的分布式計算架構受到了越來越多的青睞[6-7]。為進一步降低劃分聚類算法的計算復雜度，將傳統的劃分聚類算法進行改進，同時結合分布式計算架構，成為當前劃分聚類算法的研究熱點。Cui等[8]最早提出了大數據下基于MapReduce的K-means優化聚類算法，為解決K-means聚類算法處理大規模數據時，迭代次數多和性能較低的問題，該算法利用MapReduce框架實現定義了映射(Map)函數和規約(Reduce)函數，消除了迭代依賴，但是聚類算法中未進行參數尋優，從而會影響聚類穩定性。為了進一步提高聚類穩定性，唐新宇等[9]提出了一種基于群體智能的大數據聚類算法，通過采用混合蛙跳算法來優化C-means 算法，以便調整參數，從而提高全局搜索能力。Qian等[10]使用群智能優化算法，進行全局搜索，在利用Spark進行并行化。雖然這些算法進行了一定程度的參數尋優，但參數尋優能力依然不佳，此外，這些算法的并行化都未考慮到隨機選取初始聚類中心，引起的初始中心敏感的問題。

如何解決隨機選取初始聚類中心，引起的初始中心敏感的問題，一直是基于劃分的并行化聚類算法的重要研究內容。為了處理這個問題，陰愛英等[11]提出一種基于MapReduce框架下K-means的改進算法，該算法通過凝聚層次聚類法對大數據集進行聚類，從而獲取初始聚類中心，降低了最終聚類結果對參數的敏感程度。李媛媛等[12]提出云環境下并行的K-medoids算法，算法利用最大最小原則和密度法獲取優化的初始聚類中心，然后在Canopy區域里進行中心點替換。雖然這些算法都對傳統的隨機選取中心點進行了改進，但是沒有完全解決初始中心敏感的問題。袁逸銘等[13]使用基于密度峰值的快速搜索算法獲取初始中心點，然后通過MapReduce框架進行并行化。除此之外，這些算法都未考慮并行時數據傾斜的問題，導致集群效率低下，極大降低了整體并行化的運行效率。針對這個問題，周華平等[14]提出了基于索引偏移的MapReduce聚類負載均衡策略，通過將更改剩余分區索引的策略應用于解決數據的不均勻劃分。雖然目前基于劃分的并行化聚類算法的研究已經取得了一些成果，但如何進一步處理劃分聚類算法中參數尋優能力不佳，如何進一步降低隨機選取初始聚類中心引起的初始中心敏感的影響，如何解決數據傾斜的問題，從而提高并行化聚類算法的整體性能，仍是目前亟須解決的問題。

針對以上問題，現提出基于IABC的并行劃分聚類(the partitioning-based clustering algorithm using improve artificial bee colony based on MapReduce，MR-PBIABC)算法，主要工作為：提出基于反向學習和聚類準則函數的初始化策略(backward learning and the clustering criterion function，BLCCF)，提升人工蜂群算法搜索的解質量，并將人工蜂群(artificial bee colony，ABC)算法和人工魚群(artificial fish colony，AFS)算法結合，提出改進的人工蜂群算法(improve artificial bee colony，IABC)，通過利用AFS算法最優解能力較強的特性，提高ABC算法的尋優能力；根據改進的人工蜂群算法IABC獲取初始聚類中心，并提出相對熵策略(relative entropy strategy，RES)衡量人工魚間的距離，保證獲得的初始聚類中心是最優人工魚狀態；設計數據均衡策略(data balancing strategy，DBS)，通過動態收集節點負載并分配節點間的負載，解決節點上數據傾斜的問題；在MapReduce計算模型下，并行挖掘簇中心，生成最終聚類結果。

1 相關技術概念

1.1 MapReduce計算模型

MapReduce是一種簡化的分布式編程模型和高效的任務調度模型[15]，用于大規模數據集的并行運算。MapReduce編程模型的核心在于Map(映射)階段和Reduce(化簡)階段的實現,Map階段是將輸入的轉化為中間結果，然后在Reduce階段根據key進行排序、整合，得到>，最后Reducer根據>生成并輸出。MapReduce的模型如圖1所示。

圖1 MapReduce模型

1.2 反向學習

反向學習[16]是為了生成反向解，其定義是在d維空間的一個候選集p=(x1,x2,…,xd)，其中xi∈[ai,bi],i=1,2,…,d，則其對應的反向解為p=(x′1,x′2,…,x′d)，其中x′i=ai+bi-xi。

1.3 人工蜂群算法

人工蜂群算法[17]是模仿蜜蜂行為的一種基于集群智能思想的方法，主要由雇傭蜂階段、跟隨蜂階段、偵查蜂階段組成。

(1)雇傭蜂階段。產生隨機候選解為

vij=xij+φij(xij-xkj)

(1)

式(1)中：xij為第i個蜜源的第j維分量；xkj為隨機選取的異于xij的蜜源；k∈{1,2,…,NS}；φij∈(-1,1)。

(2)跟隨蜂階段。返回雇傭蜂的蜜源信息，根據蜜源的適應度yi按式(2)計算食物源被選中的概率Pi，當yi越大，則Pi越大。

(2)

式(2)中：yi為蜜源的適應度，與蜜源i的目標函數值有關；NS為蜜源的個數。

(3)偵查蜂階段。達到開采上限時，如果適應度仍未更新則被淘汰。

1.4 人工魚群優化算法

人工魚群算法[18]是根據魚類的活動特點提出的一種基于動物行為的自治體尋優模式，主要由覓食、聚群、追尾行為組成。

(3)

式(3)中：Visual為人工魚的視野；Rand()為隨機函數。

若Yi

(4)

反之，再重新隨機選取狀態Xtry，如果Yi>Ytry，則重復NTry次后，當依然Yi>Ytry，則任意前進一步，即

(5)

(6)

否則，執行覓食行為。

(7)

否則，執行覓食行為。

2 MR-PBIABC算法

2.1 算法思想

MR-PBIABC算法主要包括3個階段：數據預處理、數據均衡和并行劃分聚類。

(1)在數據預處理階段。首先提出基于反向學習和聚類準則函數的初始化策略BLCCF，來提升人工蜂群算法搜索的解質量，并將人工蜂群算法(ABC)和人工魚群優化算法(AFS)結合，提出改進的人工蜂群算法IABC，通過利用AFS算法最優解能力較強的特性，來提高ABC算法的尋優能力；然后根據改進的人工蜂群算法IABC獲取初始聚類中心，并提出相對熵策略RES衡量人工魚間的距離，保證獲得的初始聚類中心是最優人工魚狀態，從而有效避免了隨機選取初始聚類中心，引起的初始中心敏感的問題。

(2)在數據均衡階段。設計數據均衡策略 DBS，通過動態收集節點負載并分配節點間的負載，解決了節點上數據傾斜的問題。

(3)并行劃分聚類階段。在MapReduce計算模型下，并行挖掘簇中心，生成最終聚類結果。

2.2 數據預處理

目前大數據環境下的并行劃分聚類算法中，通常采用群智能優化等策略有效改進參數敏感問題，但也仍然存在參數尋優能力不佳，并對初始數據集，通常采用隨機選取初始聚類中心，這種選取方式會對聚類結果有較大影響，從而產生初始中心敏感的問題。針對這些問題，提出基于反向學習和聚類準則函數的初始化策略BLCCF，來提升人工蜂群算法搜索的解質量，并將ABC算法和AFS算法結合，通過利用AFS算法最優解能力較強的特性，來提升ABC算法的尋優能力；然后根據改進的人工蜂群算法IABC獲取初始聚類中心，并提出相對熵策略RES衡量人工魚間的距離，保證獲得的初始聚類中心是最優人工魚狀態，有效避免隨機選取初始聚類中心引起的初始中心敏感的問題。

2.2.1 IABC算法

為了進一步提高算法對聚類參數的尋優能力，提出基于反向學習和聚類準則函數的初始化策略BLCCF，來提升ABC算法搜索的解質量，并將ABC算法和AFS算法結合，提升ABC算法的尋優能力。

首先，在種群初始化階段，提出基于反向學習和聚類準則函數的初始化策略BLCCF，以提升ABC算法搜索的解質量，初始化策略BLCCF步驟如下。

步驟一在d維數據空間中，隨機獲取K個蜜源位置，根據蜜源選擇式(2)生成種群規模|K|，其集合為Xi=(x1,x2,…,xk)；然后根據反向學習算法，得到反向種群Xi*=(x1*,x2*,…,xk*)，合并兩組解得X=(Xi∪Xi*)，計算適應度δ(X)=(δ(Xi)∪δ(Xi*)，按照適應度從小到大排序，選取前K個作為top-K解，從而使種群個體盡可能均勻分布在數據空間。

步驟二根據聚類特性，即簇內項相似性最大、簇間項相似性最小的原理，提出聚類準則函數CCF，使生成的top-K更符合聚類特性，進而提高聚類效果。

定義1(聚類準則函數CCF)：若種群的個數為K，種群i中個體的數量為Ki，則其聚類準則函數CCF定義為

(8)

聚類準則函數的前半部分是評價簇內的穩定性，若值越大，說明簇內部越穩定，聚類效果越好；后半部分是評價簇間的穩定性，若值越小，說明簇與簇之間的關聯性較小，聚類效果更好。

然后，在生成初始化種群后，ABC算法雖然具有較強的全局搜索能力，但未利用最優解進行搜索，會導致算法尋優能力較差，因此提出改進的人工蜂群算法IABC，利用AFS算法尋求最優解較強的特性，使用式(3)～式(7)更新參數，從而提升ABC算法的尋優能力。

2.2.2 初始簇中心獲取

在提出IABC算法之后，對初始數據集，采用IABC算法獲取初始聚類中心，其具體步驟如下。

步驟一進行種群初始化，得到種群規模top-K，并采用聚類準則函數CCF評價種群top-K。

步驟二根據AFS算法利用最優解較強的特性，將top-K作為初始人工魚，根據式(3)～式(7)執行人工魚的覓食、聚群、追尾行為。

步驟三提出相對熵策略RES衡量人工魚間的距離，通過增大人工魚群內相似性，群間差異性，從而能獲得最優人工魚群狀態，通過迭代執行上述步驟，得到更新后的k個人工魚群。

定義2(相對熵策略 RES)：假設a，b表示不同的人工魚，人工魚的k分類模型為Xk×d，其中k為分類數，d為數據維度，則人工魚間的相對熵定義為

(Xmd)a=(xm1a,xm2a,…,xmda)

(9)

(Xmd)b=(xm1b,xm2b,…,xmdb)

(10)

(11)

(12)

(13)

式中：(Xmd)a為Xk×n中第m(1≤m≤k)分量結構；X′md(x)a、X′md(x)b分別為人工魚a、b的概率分布。

證明：當相對熵D(Xa‖Xb)越大，則人工魚a與b的差異越大；反之，差異越小。通過迭代執行上述步驟，并使用相對熵可以將人工魚群進行分類，進而增大魚群間的差異性和魚群內的相似性，可以產生最優人工魚{F1,F2,F3…,Fk}，從而能生成初始聚類中心。證畢。

最后，記錄最優人工魚群狀態，即作為初始中心點。過程偽代碼如下。

算法1初始簇中心獲取

輸入：數據集D(n個數據對象,m個維度)，聚類數k

輸出：k個初始聚類中心

(1)According to BLCCF strategy;

(2)Get top-K；//種群初始化

(3)Then use CCF to estimate top-K；

(4)top-Kas initial artificial fish;//top-K作為初始人工魚

(5)Carry out the formula(3)～formula(7)；

(6)Then useD(Xa‖Xb)to measure the distance between artificial fish;

(7)IfD(Xa‖Xb)smallest

(8) Explain little difference betweenaandb；

(9) Update artificial fish swarm;

(10) Then record optimal artificial fish;//記錄最優人工魚狀態

(11) Get{F1,F2,…,Fk}；

(12)Then set asO；//設置最優人工魚為初始簇中心

(13)O={F1,F2,…,Fk}；

(14)ReturnO

2.3 數據均衡

在用IABC算法獲取初始簇中心后，為了進一步提高并行效率，避免節點間數據傾斜，設計數據均衡策略 DBS，通過動態收集節點負載并分配節點間的負載，解決了節點上數據傾斜的問題。DBS策略為：當把過載的Reducer節點上的數據量進行任務調度時，會產生一定的系統開銷，如果大于繼續保留在原節點的開銷，反而會降低集群的效率。因此設計了數據均衡策略DBS，處理節點上的數據傾斜。

定義3(數據均衡策略DBS)：若節點i過載時未處理的數據量為L(i)m，Reducer上系統懸掛和恢復的時間開銷為Ts和Tr，任務調度時的通信開銷為Tc，則其數據均衡策略如下：

(14)

T(i)m>2Ci

(15)

Ci=Ts+Tc+Tr

(16)

式中：T(i)m為節點i過載時的時間開銷；Ci為過載節點進行數據調度的總時間開銷。

證明：因為T(i)m和L(i)m為節點上動態獲取的時間開銷和過載數據量，通過T(i)m>2Ci表明進行調度時產生的時間開銷小于在過載節點的時間開銷，從而滿足調度條件，所以能達到調度后，時間開銷減小，解決了節點上的數據傾斜，提高了并行效率。證畢。

“DBS”策略偽代碼如下。

算法2“DBS”策略

輸入：數據集D，Reducer節點數r

輸出：數據均衡結果

(1)While reducerpbecome idle；//DBS策略觸發條件

(2)T(i)m=maxTi(1≤i≤r)；

(3)L=L-L(p)；//去除完成節點的負載

(4)IfL≠0 do

(5)If Schedule-Lock==false do

(6) Wait for the Schedule-Lock；

(7)Schedule-Lock==true；//獲得調度鎖

(8) Else ifT(i)m>2Cido

(9)q=get Reducer ID(Lmax)；//獲得負載最重的節點

(10)Stopqand getLm；//記錄劃分結果

(11) DivideLmequally and transmit top，q；

(12) Restartp，q；

(13) Schedule-Lock==false;//釋放調度鎖

(14) End if

(15)End if

(16)Return data balancing results；

2.4 并行劃分聚類

在數據均衡后，為了并行挖掘簇中心，獲取最終聚類結果，要調用Map和Reduce任務。在Map階段，它的主要任務是讀取初始聚類中心和數據均衡結果，隨后根據歐式距離公式獲得數據對象到初始簇中心的距離，將數據對象分配給各個簇，得到局部聚類結果并將結果暫時存入Combine。在Reduce階段，其主要任務是接受Combine內的局部聚類結果，合并局部簇，隨后根據代價函數E[19]判斷是否得到全局最優解，當Emin不成立時，啟用新的MapReduce任務進行迭代，直到Emin時，得到全局最優解，從而取得最終聚類結果，且聚類過程結束。執行過程偽代碼如下。

算法3并行劃分聚類

輸入：初始簇中心，數據均衡結果

輸出：最終聚類結果

(1)Enable MapReduce

(2)Map(key,value)

(3)InputOand Data balancing results；

(4) Get the local clustering results;/*根據歐式距離得到局部聚類結果*/

(5) Deposit in Combine；//結果暫存入Combine

(6)End

(7)Reduce(key,value)

(8) Read Combine；

(9) IfEmin= false do

(10) Enable a new MapReduce task；/*啟用新的MapReduce任務

(11) Else do

(12) Get the final clustering results;//得到最終聚類結果

(13) End

(14)End

(15)Returnthe final clustering results；

2.5 MR-PBIABC算法步驟

步驟1通過基于反向學習和聚類準則函數的初始化策略，初始化種群，得到種群規模top-K。

步驟2將ABC算法和AFS算法結合，提升ABC算法的尋優能力，提出改進的人工蜂群算法。

步驟3通過改進的人工蜂群算法獲取初始聚類中心。

步驟4并根據相對熵策略RES衡量人工魚間的距離，保證獲得的初始聚類中心是最優人工魚狀態。

步驟5在數據均衡階段，調用算法2的DBS策略，通過動態收集節點負載并分配節點間的負載，進行數據的合理劃分，解決節點上數據傾斜的問題，得到數據均衡結果。

步驟6讀取初始聚類中心和數據均衡結果，啟用MapReduce任務，調用算法3完成并行劃分聚類，從而獲取最終聚類結果。

2.6 算法的復雜度分析

2.6.1 時間復雜度

MR-PBIABC算法的時間復雜度主要由數據預處理，數據均衡，并行劃分聚類這幾個步驟構成，分別記作T1、T2、T3。

首先在BLCCF策略進行種群初始化階段，假設空間中數據點的數量為n，初始種群數為K，則種群初始化的時間復雜度為

Tc=O(Kn2)

(17)

在IABC算法獲取初始聚類中心階段，其時間復雜度主要取決于迭代更新最優人工魚狀態的運算，則其時間復雜度為

(18)

因此數據預處理的時間復雜度為

(19)

在數據均衡階段。假設Reducer節點的數量為r，通過采用DBS策略均衡節點間的數據量，完成合理的數據劃分，其時間復雜度為

T2=O(n/r)

(20)

并行劃分聚類階段。需要進行多個MapReduce任務，并行的更新每個簇，其時間復雜度為

T3=O(rlog2n)

(21)

因此MR-PBIABC算法的時間復雜度為

(22)

而DPMCSKM[12]算法中，算法的參數尋優能力不佳，初始簇中心選取未解決且未考慮節點間的數據傾斜，故其時間復雜度為

(23)

在大數據環境下，T1>>T2,T3，而且通過初始簇中心獲取后，極大減少了迭代次數，即T1-MR-PBIABC?T1-DPMCSKM，因此MR-PBIABC算法時間復雜度遠低于DPMCSKM算法。

2.6.2 空間復雜度

MR-PBIABC算法的空間復雜度是更新簇中心所占內存和負載均衡節點隊列占用的內存之和，假設數據量為n，簇的個數為k，Reducer節點數為r，算法的迭代次數為e，則MR-PBIABC算法的空間復雜度為

(24)

DPMCSKM[12]算法的空間復雜度主要是更新簇中心所占內存，但該算法未進行初始簇中心獲取，因此其空間復雜度為

MDPMCSKM=O(klog2n+n2)

(25)

由于大數據環境下，負載均衡節點隊列所占內存遠小于參數存儲內存，因此內存主要是更新簇中心，而MR-PBIABC算法通過初始簇中心獲取后，參數數量遠小于DPMCSKM算法，故MR-PBIABC算法空間復雜度遠小于DPMCSKM算法。

3 實驗結果及比較

3.1 實驗環境

為驗證MR-PBIABC算法的聚類效果和并行效率，設計了相關實驗。實驗環境包含由1個Master節點和3個Slaver節點構成的Hadoop集群，節點間通過300 Mb/s網絡相連，且4個節點的配置相同：硬盤1 TB，內存16 GB，CPU為Inter core i7-9750H，操作系統為Ubuntu 16.04, 安裝Hadoop版本2.7.4，采用Java JDK1.8.0編譯。

3.2 實驗數據

MR-PBIABC算法采用的實驗數據為4個來自UCI公共數據庫的真實數據集，分別是Iris、Impeel、Susy和Higgs。Iris是模式識別文獻中最著名的數據集，包含150條數據，具有數據量小等特點；Impeel是從IT公司使用的ServiceNowTM平臺實例的審計系統收集的數據，該數據集有141 712條實例，具有多元、記錄長度長等特點；Susy是一組有關粒子加速器探測粒子的數據，該數據集有5 000 000條記錄，具有數據量大，數據均勻等特點；Higgs包含11 000 000條數據，具有數據量大、數據離散等特點。數據集的詳細信息如表1所示。

表1 實驗數據集

3.3 評價指標

3.3.1 加速比

為驗證MR-PBIABC算法在大數據集下并行處理的能力，采用加速比來衡量并行計算的性能。加速比是指在并行計算下，降低運行時間從而獲得的性能提升，其定義為

Sp=T1/Tp

(26)

式(26)中：T1為算法在單節點上的運行時間；Tp為并行計算的運行時間。Sp越大，則表示并行計算所耗費的相對時間較少，集群的效率得到提升。

3.3.2F值

為驗證MR-PBIABC算法對數據集的聚類效果，使用F值對聚類結果進行評價，F值是正確率(precision，P)和召回率(recall，R)的加權平均值，其定義為

(27)

式(27)中：P為正確率；R為召回率。通常情況下，參數λ=1，F值綜合考慮了聚類結果的正確率和召回率的情況，能夠較為準確地評價聚類算法的結果，當F值較高時，說明聚類效果較好。

3.4 IABC算法有效性分析

為驗證IABC算法的有效性，運用IABC算法對Iris數據集進行初始聚類中心的選取，并與Iris數據集的真實中心進行比較，如表2所示。

表2 初始聚類中心對比

從表2可以看出，在Iris數據集上，IABC算法得到的初始聚類中心和真實聚類中心非常相似，誤差在百分數級別，這說明了IABC算法能夠優化初始聚類中心的求取結果，為后續獲得最終聚類結果打下了較好的基礎，驗證了IABC算法的有效性。

3.5 MR-PBIABC算法性能分析

為驗證MR-PBIABC算法在大數據集下并行處理的能力，加速比通常被作為檢驗并行化算法性能的重要指標，可以使用加速比來衡量并行計算的性能。通過在Iris、Impeel、Susy、Higgs 4個數據集的基礎下，進行了多次實驗，從而實現對MR-PBIABC算法性能的綜合評估，算法的平均加速比曲線如圖2所示。

圖2 MR-PBIABC算法的加速比曲線

從圖2可以看出，MR-PBIABC算法在Impeel、Susy和Higgs 3個大數據集下表現出很好的加速比性能。在處理Iris這樣的小數據集時，隨著節點數量的增加，加速比呈下降趨勢且小于1，這是由于處理小數據集時，將數據分散到各個節點反而增加了各節點間的時間開銷，加速比容易陷入瓶頸，因此并行算法不適應于小數據集。而在處理數據量較大的Higgs時，算法在4個節點下的加速比為3.7，比單節點提升2.7，原因是隨著數據規模的增大，MR-PBIABC算法可以降低節點間通信開銷和并行的進行簇的生成的優點被逐漸放大，在節點數量增加的同時，加速比曲線接近于線性增長，算法的并行性能表現出極大的提高。這也表明MR-PBIABC算法適用于處理大數據集，且隨著節點數量的增加，并行化的效果更好。

3.6 MR-PBIABC算法性能比較

為驗證MR-PBIABC算法的綜合性能，在Impeel、Susy和Higgs數據集下進行對比實驗，根據聚類結果的最優值、方差、準確率、F值和運行時間，分別與SICC-MR算法[8]、MR-IKMEANS算法[10]、HEPKM算法[11]和DPMCSKM算法[12]進行性能比較。通過運行10次算法，得到的平均值作為實驗的最終結果，從而實現對MR-PBIABC算法性能的綜合比較。

3.6.1 聚類穩定性比較

為了驗證MR-PBIABC算法的聚類穩定性，在上述3個數據集下進行對照實驗，根據聚類結果的最優值、方差進行性能比較。其中最優值可以反映尋找最優解的能力，值越小表示尋找最優解的能力越強；方差體現算法的聚類穩定性；算法的聚類穩定性對比分析如表3所示。

表3 算法的聚類穩定性對比分析

從表3可以看出，SICC-MR算法相較于其他算法，聚類穩定性較差，這是由于SICC-MR算法只是對K-means進行了并行化，采用隨機獲取初始中心點的方式進行聚類，極大降低了算法的穩定性。而DPMCSKM算法利用最大最小原則和密度法獲取優化的初始中心點，減小了隨機選取初始中心的影響，一定程度上提高了算法的聚類穩定性。但由于密度法對異常值較為敏感，算法的穩定性受限。而MR-PBIABC算法通過基于反向學習和聚類準則函數的初始化策略BLCCF，提升人工蜂群算法搜索的解質量，并結合AFS算法，提高了ABC算法的尋優能力，根據改進的人工蜂群算法IABC獲取初始聚類中心，同時提出相對熵策略RES，保證獲得的初始聚類中心是最優人工魚狀態，從而有效避免了隨機選取初始聚類中心，引起的初始中心敏感的問題，特別是在Susy數據集上，MR-PBIABC算法的方差值遠小于其他算法，且在其他數據集下，最優值也最小，表現出良好的尋求最優解的能力，極大地提高了聚類穩定性。

3.6.2F值對比分析

為了分析算法的聚類效果，根據F值進行性能比較，F值可以明確地表現出算法聚類效果的好壞程度，在上述3個數據集下，分別與SICC-MR算法，HEPKM算法進行性能比較，得到的F值結果如圖3所示。

圖3 F值對比分析

從圖3可以得出，HEPKM算法在幾個數據集下的F值優于SICC-MR算法，尤其是在Impeel數據集上F值提高了5.1%。因為其采用凝聚層次聚類法獲取初始聚類中心，在一定程度上緩解了SICC-MR算法沒有考慮隨機選取初始聚類中心導致的聚類結果不穩定的缺陷。而MR-PBIABC算法在F值上比HEPKM算法進一步提高了2.9%，這是由于MR-PBIABC算法采用改進的人工蜂群算法IABC獲取初始聚類中心，提高了算法的尋優能力，且使初始簇中心相互之間的距離增大，提高聚類間的差異性，從而提升了算法的聚類效果。

3.6.3 運行時間比較

運行時間則表現算法的時間復雜度，通過在3種數據集下對5種算法的對比實驗，可以進一步驗證MR-PBIABC算法的性能，運行時間的對比分析如圖4所示。

圖4 3種數據集下各算法運行時間

從圖4可以看出，相較于SICC-MR、MR-IKMEANS、HEPKM和DPMCSKM算法，MR-PBIABC算法在3個數據集上的運行時間均有所降低，其中在數據集Higgs降低最多，MR-PBIABC算法比SICC-MR、MR-IKMEANS、HEPKM和DPMCSKM算法的運行時間分別減少了61.1%、50.3%、42.5%和34.5%；在數據集Impeel上降低最少，但也分別減少了47.7%和39.3%，28.4%和16.5%。這是在Reducer節點間數據調度時，通過提出的數據均衡策略DBS，處理節點間數據傾斜的問題，提高了節點的利用率，進一步降低了MR-PBIABC算法的運行時間。

4 結論

為解決基于劃分的聚類算法在大數據背景下的不足，提出了基于IABC的并行劃分聚類算法MR-PBIABC。首先，提出基于反向學習和聚類準則函數的初始化策略BLCCF，來提升人工蜂群算法搜索的解質量，并將人工蜂群算法(ABC)和人工魚群優化算法(AFS)結合，提出改進的人工蜂群算法IABC，通過利用AFS算法最優解能力較強的特性，來提高ABC算法的尋優能力；接著根據改進的人工蜂群算法IABC獲取初始聚類中心，并提出相對熵策略RES衡量人工魚間的距離，保證獲得的初始聚類中心是最優人工魚狀態，從而有效避免了隨機選取初始聚類中心，引起的初始中心敏感的問題；其次，設計數據均衡策略 DBS，通過動態收集節點負載并分配節點間的負載，解決了節點上數據傾斜的問題，進而有效地提高了集群效率；最后，結合MapReduce計算模型，并行挖掘簇中心，生成最終聚類結果。為了驗證MR-PBIABC算法的性能，在Iris、Impeel、Susy和Higgs 4個數據集下對MR-PBIABC、SICC-MR、MR-IKMEANS、HEPKM和DPMCSKM 5種算法進行性能對比分析，實驗結果表明MR-PBIABC算法在處理數據量大且數據離散的球狀簇時，具有更佳的聚類效果和尋優能力，且并行的效率也得到了很大提升。