王凱杰

摘 要：針對現(xiàn)有序列聚類算法在對大規(guī)模數(shù)據(jù)進行聚類時，內(nèi)存空間和計算時間開銷較大的問題，提出了基于MapReduce的人工蜂群聚類算法。該算法通過引入MapReduce并行編程范式，快速計算聚類中心適應(yīng)度，可實現(xiàn)對大規(guī)模數(shù)據(jù)的高效聚類?；诜抡鏀?shù)據(jù)對算法的聚類效果和聚類效率進行了驗證。實驗結(jié)果表明，與現(xiàn)有PK-Means算法和并行K-PSO算法相比，該算法具有更好的聚類效果和更高的聚類效率。

關(guān)鍵詞：大數(shù)據(jù)；人工蜂群；聚類；并行編程范式

DOIDOI：10.11907/rjdk.171911

中圖分類號：TP312

文獻標(biāo)識碼：A 文章編號：1672-7800（2018）002-0071-03

0 引言

數(shù)據(jù)挖掘技術(shù)常被用于發(fā)現(xiàn)數(shù)據(jù)中潛在的某種模式，從而為最優(yōu)決策提供依據(jù)[1]。

聚類是重要的數(shù)據(jù)挖掘技術(shù)，主要用于將某個集合中的項分配到目標(biāo)類別或簇。近年來，仿生算法如遺傳算法（GA）、差分進化（DE）、蟻群優(yōu)化（ACO）、微粒群優(yōu)化（PSO）等被用于解決聚類問題。Maulik等[2]提出了被稱為“GA-聚類”的基于遺傳算法的聚類方法，該方法從特征空間搜索到適當(dāng)?shù)拇刂行?，?yōu)化利用相似性度量得到的簇。王勇臻等[3]針對K-means算法依賴于初始聚類中心和易陷入局部最優(yōu)解的缺陷，提出一種改進的求解聚類問題的差分進化算法。姜參等[4]對蟻群聚類算法的收斂速度和易陷入局部最優(yōu)問題進行了改進，提高了聚類速度和效果。Cura等[5]利用微粒群優(yōu)化方法，通過模擬鳥類結(jié)隊和魚的群居行為特征解決聚類問題。然而，大規(guī)模數(shù)據(jù)集通常包含大量文件，應(yīng)用上述序列聚類算法對大規(guī)模數(shù)據(jù)進行聚類時，往往在內(nèi)存空間和計算時間等方面開銷較大[6]。目前，MapReduce編程范式已成為一個數(shù)據(jù)并行編程模型，可將計算任務(wù)自動并行處理，具有較好的容錯和負載均衡能力，受到眾多研究者青睞。

針對大規(guī)模數(shù)據(jù)聚類問題，本文提出了基于MapReduce的人工蜂群聚類算法，能對大規(guī)模數(shù)據(jù)進行高效聚類。

1 人工蜂群聚類算法改進

1.1 傳統(tǒng)的人工蜂群算法

人工蜂群算法是一種元啟發(fā)式算法，涉及到的概念包括：①食物源：表示優(yōu)化問題的一種可能方案；②適應(yīng)度：適應(yīng)度的值表示食物源的質(zhì)量；③蜜蜂種類：雇傭蜂、觀察蜂和偵察蜂。

人工蜂群算法步驟：①隨機分布式初始化食物源位置；②所有雇傭蜂選擇一個候選食物源位置，基于之前已選擇食物源位置的臨近位置，選擇新的食物源。若新的候選食物源位置適應(yīng)度更高，則更新雇傭蜂記憶中原有的食物源位置并返回蜂巢，與觀察蜂共享新的食物源位置的適應(yīng)度；③每個觀察蜂根據(jù)從雇傭蜂得到的適應(yīng)度值以一定概率選擇新的食物源位置；④觀察蜂前往被選擇食物源位置，并根據(jù)所選食物源，選擇其臨近的新的食物源位置；⑤丟棄所有適應(yīng)度未增加的食物源位置，并由偵察蜂隨機確定新的位置。

上述過程重復(fù)執(zhí)行，直到迭代次數(shù)達到最大循環(huán)次數(shù)。其中，步驟①、②和③在重復(fù)過程中，于步驟⑤之前循環(huán)執(zhí)行。

1.2 改進算法流程

基于MapReduce的人工蜂群算法流程如圖1所示。

主要步驟如下：

（1）隨機分布式初始化食物源位置，將其作為雇傭蜂的初始位置。初始位置如式（1）所示：

其中，xi為以D維向量表示的食物源位置，為目標(biāo)函數(shù)，決定著當(dāng)前位置的優(yōu)劣，表示食物源數(shù)量。

（2）更新雇傭蜂新的中心值。將初始位置作為雇傭蜂的當(dāng)前位置，并基于當(dāng)前位置對鄰域進行搜索。在搜索過程中選擇新的位置，通過式（2）計算得到：

（3）基于MapReduce計算適應(yīng)度?；贛apReduce計算雇傭蜂從鄰域搜索到的新的食物源適應(yīng)度，如果該適應(yīng)度高于原位置適應(yīng)度，則用該位置更新原有位置。

（4）從雇傭蜂選擇中心值并更新。雇傭蜂返回蜂巢，將新的食物源位置共享給觀察蜂，觀察蜂根據(jù)共享信息利用式（3）選擇食物源位置：

式（3）中，fiti表示食物源的適應(yīng)度，與食物源i的目標(biāo)函數(shù)值有關(guān)。選擇好食物源位置后，觀察蜂前往該位置，利用公式（2）選擇其鄰域中心的食物源位置。

（5）基于MapReduce計算新位置的適應(yīng)度，并根據(jù)適應(yīng)度的大小決定是否更新當(dāng)前位置。

（6）考察一段時間內(nèi)的中心值適應(yīng)度是否增加，如適應(yīng)度未增加，則丟棄當(dāng)前中心值，偵察蜂重新產(chǎn)生新的中心值，否則，執(zhí)行步驟（7）。

（7）考察中心值是否滿足條件，如滿足則執(zhí)行步驟（8），否則執(zhí)行步驟（2）。

（8）利用最優(yōu)中心值對數(shù)據(jù)進行聚類。

在上述步驟中，大規(guī)模數(shù)據(jù)的適應(yīng)度計算會耗費大量時間。因此，本文采用MapReduce計算適應(yīng)度值。

1.3 基于MapReduce的適應(yīng)度計算

具體步驟如下：①映射函數(shù)從簇的中心開始，將數(shù)據(jù)記錄到Hadoop分布式文件系統(tǒng)中；②映射函數(shù)從每個蜜蜂提取中心值，計算數(shù)據(jù)記錄與中心值之間的距離，并返回最小距離及中心的編號。映射函數(shù)使用蜜蜂的ID和中心的ID建立一個新的合成鍵，并根據(jù)最小距離計算新的值；③映射函數(shù)將新的鍵和值調(diào)用給規(guī)約函數(shù)，規(guī)約函數(shù)利用同一個鍵的多個值計算得到平均距離；④規(guī)約函數(shù)調(diào)用鍵和平均距離，計算得到每個蜜蜂的適應(yīng)度值。

2 實驗

對改進算法的聚類效果和聚類效率進行實驗，對算法性能進行評估和驗證。

2.1 實驗設(shè)置

本文算法和對比算法均以Perl語言實現(xiàn)，并在包含10個節(jié)點的Hadoop集群中運行，每個節(jié)點的配置為：1核2.26GHz CPU，2G內(nèi)存，120G硬盤空間，Ubuntu 14.04操作系統(tǒng)，Apache Hadoop 2.6.2。endprint

算法使用的數(shù)據(jù)集為仿真數(shù)據(jù)，該數(shù)據(jù)為UCI機器學(xué)習(xí)數(shù)據(jù)集中的4個基準數(shù)據(jù)集，如表1所示。為了獲得大規(guī)模的仿真數(shù)據(jù)，本文通過多次復(fù)制，將每個基準數(shù)據(jù)集擴充到約1 000萬條記錄。

2.2 實驗結(jié)果

2.2.1 聚類效果測試

在衡量聚類效果時，本文采用F值度量（F-Measure）方法來評估聚類的準確度。F值度量（F-Measure）方法將每個簇作為一個查詢，將每個類別作為查詢的預(yù)期結(jié)果。算法得到的簇和已標(biāo)記的基準數(shù)據(jù)類別之間的F度量值可用式（4）計算得到：

基于仿真數(shù)據(jù)，本文實現(xiàn)了基于MapReduce的人工蜂群聚類算法，與現(xiàn)有的PK-Means算法[7]和并行K-PSO算法[8]的聚類效果比較結(jié)果見表2。其中，初始簇中心是通過計算隨機抽取0.1%的數(shù)據(jù)記錄平均值得到的。

從表2可以看出，本文算法的F度量值明顯高于PK-Means算法和并行K-PSO算法的F度量值，即本文算法的聚類效果更優(yōu)。

2.2.2 聚類效率測試

本文除對算法的聚類效果進行測試外，還測試了大規(guī)模數(shù)據(jù)的聚類效率。在10個節(jié)點上對不同大小的數(shù)據(jù)集進行聚類，數(shù)據(jù)集的大小從2GB～10GB不等，測試結(jié)果如表3～表6所示。聚類效率通過式（6）計算得到。

從表3～表6可以看出，隨著數(shù)據(jù)集的增大，本文算法的性能逐步提高，效率達到90%以上。實驗結(jié)果表明，對大規(guī)模數(shù)據(jù)進行聚類時，本文算法可節(jié)省大量時間，顯著降低成本，在合理的時間內(nèi)處理大規(guī)模數(shù)據(jù)且處理結(jié)果較優(yōu)。

3 結(jié)語

本文針對大規(guī)模數(shù)據(jù)聚類問題，提出了基于MapReduce的人工蜂群聚類算法，并利用仿真數(shù)據(jù)對算法的聚類效果和效率進行了驗證。實驗結(jié)果表明，與PK-Means算法和并行K-PSO算法相比，本文算法具有更好的分類性能。今后的進一步研究可在更大規(guī)模的數(shù)據(jù)集上開展實驗。

參考文獻：

[1] 穆肇南，張健.數(shù)據(jù)挖掘技術(shù)在經(jīng)濟預(yù)測中的應(yīng)用[J].計算機仿真，2012，29（6）：347-350.

[2] WU X， ZHU X， WU G Q， et al. Data mining with big data[J]. IEEE transactions on knowledge and data engineering，2014，26（1）：97-107.

[3] 王勇臻，陳燕，張金松，等.一種改進的求解聚類問題的差分進化算法[J].計算機應(yīng)用研究，2016，33（9）：2630-2633.

[4] 姜參，王大偉.一種改進蟻群聚類的入侵檢測方法[J].計算機技術(shù)與發(fā)展，2013，23（12）：139-142.

[5] CURA T. A particle swarm optimization approach to clustering[J]. Expert Systems with Applications，2012，39（1）：1582-1588.

[6] 李曉峰.云平臺中大數(shù)據(jù)并行聚類方法優(yōu)化研究仿真[J].計算機仿真，2016，33（7）：327-330.

[7] ZHAO W， MA H， HE Q. Parallel K-means clustering based on MapReduce[C]. Proceedings of the IEEE International Conference on Cloud Computing，2009：674-679.

[8] WANG J， YUAN D， JIANG M. Parallel K-PSO based on MapReduce[C]. Proceedings of the 14th IEEE International Conference on Communication Technology，2012：1203-1208.endprint