一種基于MapReduce的改進(jìn)人工蜂群算法

王凱杰

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

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

DOIDOI：10.11907/rjdk.171911

中圖分類(lèi)號(hào)：TP312

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

0 引言

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

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

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

1 人工蜂群聚類(lèi)算法改進(jìn)

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

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

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

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

1.2 改進(jìn)算法流程

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

主要步驟如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

2 實(shí)驗(yàn)

對(duì)改進(jìn)算法的聚類(lèi)效果和聚類(lèi)效率進(jìn)行實(shí)驗(yàn)，對(duì)算法性能進(jìn)行評(píng)估和驗(yàn)證。

2.1 實(shí)驗(yàn)設(shè)置

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

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

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

2.2.1 聚類(lèi)效果測(cè)試

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

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

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

2.2.2 聚類(lèi)效率測(cè)試

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

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

3 結(jié)語(yǔ)

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

參考文獻(xiàn)：

[1] 穆肇南，張健.數(shù)據(jù)挖掘技術(shù)在經(jīng)濟(jì)預(yù)測(cè)中的應(yīng)用[J].計(jì)算機(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ìn)的求解聚類(lèi)問(wèn)題的差分進(jìn)化算法[J].計(jì)算機(jī)應(yīng)用研究，2016，33（9）：2630-2633.

[4] 姜參，王大偉.一種改進(jìn)蟻群聚類(lèi)的入侵檢測(cè)方法[J].計(jì)算機(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] 李曉峰.云平臺(tái)中大數(shù)據(jù)并行聚類(lèi)方法優(yōu)化研究仿真[J].計(jì)算機(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