基于MapReduce的人工蜂群算法在大數據中的應用*

李 果 袁小凱 許愛東 張乾坤 張福錚

（南方電網科學研究院 廣州 510080）

1 引言

當前，可采集數據規模不斷增大，在短時間內已很難通過人工分析的方式從中得到有價值的信息。數據挖掘技術作為目前十分流行的數據分析技術，常被用于發現數據中潛在的某種模式，從而為作出最優的決策提供依據［1～2］。

聚類一種重要的數據挖掘技術，主要用于將某個集合中的項分配到目標類別或簇，使得同一簇中成員的相似性最高，而不同簇中的成員相似度較低。近年來，仿生算法如遺傳算法（GA）、差分進化（DE）、蟻群優化（ACO）、離子群優化（PSO）等被用于解決聚類問題［3～4］。Maulik［2］等提出了被稱為“GA-聚類”的基于遺傳算法的聚類方法，該方法從特征空間搜索到適當的簇中心，來優化利用相似性度量得到的簇。王勇臻等針對K-means算法依賴于初始聚類中心和易陷入局部最優解的缺陷，提出一種改進的求解聚類問題的差分進化算法［5］。單冬紅等對通過使用不同的作業集群調度算法運行相同的作業，進行橫向對比，得到各種作業調度算法之間在計算能力、運行時間、資源占用等方面的優劣，對收斂速度方面和易陷入局部最優問題進行了改進，提高了聚類速度和效果［6］。Cura等利用微粒群優化方法，通過模擬鳥類結隊和魚的群居行為特征來解決聚類問題［7］。然而，大規模數據集通常包含相當多信息量的大量文件，上述序列聚類算法在對大規模數據進行聚類時，往往在內存空間和計算時間等方面具有較大開銷［8］。目前，MapReduce編程范式已經成為另一個數據并行編程模型，可將計算任務自動并行處理，且具有較好的容錯和負載均衡能力，受到了眾多研究者的青睞［9～10］。研究人員基于MapReduce，提出了多種利用分布式計算方式對大規模數據進行聚類的方法。王焱將K-means和蝙蝠算法結合應用在云計算虛擬機智能調度上，降低了物理節點數量和提高資源利用率［11］。文獻［12］提出了并行K-PSO方法，提高了傳統方法的聚類效果和處理冗余數據的能力。為解決PSO算法在對大量數據進行聚類時效率較低的問題，基于MapReduce并行方法，文獻［13］提出了MR-CPSO算法。同時Anchalia和Roy等提出了基于MapReduce范式的K-近鄰方法，來解決分布式計算環境下的大量數據的處理問題［14］。

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

2 聚類和人工蜂群算法基本原理

2.1 聚類

其中，wij表示對象oi在簇 j中的權重。 j個簇的中心記為可通過式（2）計算得到

其中，Nj為第 j個簇中對象的個數。

聚類問題可看作是尋找對象到簇的最優分配的過程。每個可能的分配方案即為一種可能的解決方法，簇內對象間相似度越高，分配方案越好。

2.2 人工蜂群算法

人工蜂群算法是一種元啟發式算法，常見的主要步驟如下：

1）隨機分布式初始化食物源的位置；

2）所有雇傭蜂選擇一個候選食物源位置，基于之前已選擇食物源位置的臨近位置，選擇新的食物源位置，若新的候選食物源位置適應度更高，則更新雇傭蜂記憶中原有的食物源位置，并返回蜂巢，與觀察蜂共享新的食物源位置的適應度；

3）每個觀察蜂根據從雇傭蜂得到的適應度值以一定概率選擇新的食物源位置；

4）觀察蜂前往被選擇食物源的位置，并根據所選食物源，選擇其臨近的新的食物源位置；

5）丟棄所有適應度未增加的食物源位置，并由偵察蜂隨機確定的新的位置。

上述過程重復執行，直到迭代次數達到最大循環次數。其中，步驟1）、步驟2）和步驟3）在重復過程中，于步驟5）之前循環執行。

3 基于MapReduce的人工蜂群聚類算法

3.1 算法流程和主要步驟

本文提出的基于MapReduce的人工蜂群算法的主要流程如圖1所示，主要步驟如下：

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

其中，xi為以D維向量表示的食物源位置為目標函數，決定著當前位置的優劣，SN表示食物源的數量。

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

圖1 基于MapReduce的人工蜂群聚類算法基本流程

其中，vij為基于與臨近位置（xkj）隨機選擇位置的比較，對之前位置xij的修正位置。φij為[- 1，1] 內的隨機值，用于在下一次迭代時，將之前位置隨機調整為新的位置。為隨機選擇的索引。

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

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

其中，fiti表示食物源i的適應度，與食物源i的目標函數的值有關。選擇食物源位置后，觀察蜂前往該位置，并利用式（4）選擇其鄰域中心的食物源位置。

5）基于MapReduce計算新位置的適應度，并根據適應度的大小決定是否更新當前位置。

6）考察一段時間內中心值適應度是否增加，如適應度未增加，則丟棄當前中心值，則偵察蜂重新產生新的中心值，否則，執行步驟7）。

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

8）利用最優中心值對數據進行聚類。

在上述步驟中，由于對大規模數據，適應度的計算會耗費大量時間。因此，本文采用MapReduce來計算適應度的值。

3.2 基于MapReduce的適應度計算

基于MapReduce的適應度計算方法具體步驟包括：

1）映射函數從簇的中心開始，將數據記錄到Hadoop分布式文件系統中；

當傳感器測到鐵絲導線時，由于導線的表面積較小，所產生的渦流很小，并且由單片機讀取的LDC1000收集到的數據很小，當檢測到硬幣時，由于硬幣的大表面積，產生的渦流很大，并且由單片機讀取的LDC1000收集到的數據將比以前大得多。因此，我們可通過設定閾值來區分鐵絲與硬幣。

2）映射函數從每個蜜蜂提取中心值，計算數據記錄與中心值之間的距離，并返回最小距離及其中心的編號。映射函數使用蜜蜂的ID和中心的ID來建立一個新的合成鍵，并根據最小距離計算新的值；

3）映射函數將新的鍵和值調用給規約函數，規約函數利用同一個鍵的多個值，計算得到平均距離；

4）規約函數調用鍵和平均距離，計算得到每個蜜蜂的適應度值。

4 實驗

為了對提出的算法的性能進行評估和驗證，本文從算法的聚類效果、擴展性和聚類效率3個方面開展了實驗。

4.1 實驗設置

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

算法中使用的數據集包括仿真數據和真實的磁盤驅動器制造數據（HDD）2個部分。其中，仿真數據為UCI機器學習數據集中的4個基準數據集，如表1所示。為了獲得大規模的仿真數據，本文通過多次復制，將每個基準數據集擴充到約1000萬條記錄。磁盤驅動器制造數據包含了硬盤驅動器制造過程中的材料、工具和過程等特征，包括制造成功實例（1457000條記錄）和制造失敗實例（14300條記錄），每個類別的數據均用30個特征表示，包括屬性、參數等。

表1 4個測試數據集

4.2 實驗結果

4.2.1 聚類效果測試

在衡量聚類效果時，本文采用F值度量（F-Measure）方法來評估聚類的準確度［15～16］。F值度量（F-Measure）方法將每個簇作為一個查詢，將每個類別作為查詢的預期結果。算法得到的簇j和已標記的基準數據中類別i之間的F度量值可利用式（6）計算得到

其中，r和p分別表示F值度量方法中的召回率和精度。召回率定義為，精度定義為其中，nij為存在于簇j的類別i中的成員的數量，ni和c分別為類別i和簇j的大小。大小為c的整個數據集的F度量值可通過式（7）計算得到

其中，F值的上限為1，當且僅當類別i中的全部實例被分到簇j時。F越大，表示聚類的效果越好。

基于仿真數據，本文實現了基于MapReduce的人工蜂群聚類算法，與現有的PK-Means算法［9］和并行K-PSO算法［10］的聚類效果比較結果如表2所示。其中，初始簇的中心是通過計算隨機抽取0.1%的數據記錄的平均值得到的。

表2 不同數據集的F度量值計算結果

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

基于硬盤驅動器制造數據，本文與現有算法聚類效果的比較結果如圖2所示。

圖2 基于硬盤驅動器制造數據的聚類結果

從圖2中可以看出，與PK-Means算法和Parallel KPSO算法相比，本文算法得到的結果的F度量值更高，比PK-Means算法聚類結果的F度量值提高了58%，因此，本文算法明顯優于兩種比較算法。

4.2.2 可擴展性驗證

在并行計算中，可擴展性是指當增加負荷和處理器資源時，系統增加總吞吐量的能力，加速比是指并行算法比對應的串行算法增加的速度，加速比Sp可利用式（8）計算得到

其中T為單個節點的運行時間，TN為N個節點的運行時間。

為了驗證本文算法的可擴展性強弱，分別在2的倍數個節點上執行算法，算法的運行時間和加速比測試結果如圖3、4、5、6、7所示。

圖3 基于數據集Ⅰ的運行時間和加速比

圖4 基于數據集Ⅱ的運行時間和加速比

圖5 基于數據集Ⅲ的運行時間和加速比

圖6 基于數據集Ⅳ的運行時間和加速比

圖7 基于數據集HDD的運行時間和加速比

從圖3、4、5、6、7可以看出，本文算法的運行時間隨著節點數量的增加迅速下降，加速比與理想加速比十分接近，因此，本文算法具有較高的可擴展性。

4.2.3 聚類效率測試

除對算法的聚類效果和可擴展性進行測試外，本文還測試了算法對大規模數據的聚類效率。在10個節點上對不同大小的數據集進行聚類，數據集的大小從2GB到10GB不等，測試結果如表3～表6所示。聚類效率可通過式（9）計算得到

表3 基于數據集Ⅰ的F度量值和效率

表4 基于數據集Ⅱ的F度量值和效率

表5 基于數據集Ⅲ的F度量值和效率

表6 基于數據集Ⅳ的F度量值和效率

從表3～表6可以看出，隨著數據集的增大，本文算法的性能逐步提高，效率達到90%以上。實驗結果表明，對大規模數據進行聚類時，本文算法可節省大量時間，顯著降低成本，能夠在合理的時間內處理大規模數據，并保持較優的處理結果。

5 結語

本文針對大規模數據聚類問題，提出了基于MapReduce的人工蜂群聚類算法，并利用仿真數據和磁盤驅動器制造真實數據兩類數據對算法的聚類效果、可擴展性和效率進行了驗證，實驗結果表明，與PK-Means算法和并行K-PSO算法相比，本文算法具有更好的分類性能。在以后的研究中，將在更大規模的數據集上開展實驗。