大數(shù)據(jù)挖掘中的MapReduce并行聚類優(yōu)化算法研究

呂國 肖瑞雪 白振榮 孟凡興

摘 ?要： ?針對傳統(tǒng)數(shù)據(jù)挖掘算法只適用于小規(guī)模數(shù)據(jù)挖掘處理，由于數(shù)據(jù)規(guī)模不斷增大，其存在計算效率低、內(nèi)存不足等問題，文中將MapReduce用于數(shù)據(jù)挖掘領(lǐng)域，對大數(shù)據(jù)挖掘中的MapReduce進行了并行化改進，并設(shè)計相應(yīng)的并行化實現(xiàn)模型，以期滿足大數(shù)據(jù)分析需求，完成低成本、高性能的數(shù)據(jù)并行挖掘與處理。

關(guān)鍵詞： 大數(shù)據(jù); MapReduce; 并行化處理; 聚類算法; 數(shù)據(jù)挖掘; Map任務(wù)

中圖分類號： TN911.1?34; TP311.14 ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識碼： A ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2019）11?0161?04

Abstract： The traditional data mining algorithm is only suitable for small?scale data mining and processing， and its disadvantages of low computational efficiency and insufficient memory are exposed gradually with the increase of data scale. MapReduce is used in the field of data mining to analyze the MapReduce parallelization improvement of the traditional data mining algorithms; and the corresponding parallelization implementation model is designed to meet the demand of big data analysis， and successfully complete the low?cost and high?performance data parallel mining and processing.

Keywords： big data; MapReduce; parallelization processing; clustering algorithm; data mining; Map task

0 ?引 ?言

隨著大數(shù)據(jù)時代的來臨，互聯(lián)網(wǎng)的數(shù)據(jù)量正呈現(xiàn)出爆炸式的增長，采用傳統(tǒng)數(shù)據(jù)分析法對其進行分析和研究，已經(jīng)無法滿足海量數(shù)據(jù)處理的需求?；诖耍瑪?shù)據(jù)挖掘技術(shù)隨之產(chǎn)生。數(shù)據(jù)挖掘就是從大量、隨機、模糊、有噪聲的數(shù)據(jù)內(nèi)提取有價值的信息。數(shù)據(jù)挖掘技術(shù)是指從大量數(shù)據(jù)中利用算法對隱藏信息進行搜索的過程，目前被廣泛應(yīng)用于金融、網(wǎng)絡(luò)、決策及教育等行業(yè)中。數(shù)據(jù)挖掘技術(shù)以統(tǒng)計學(xué)作為基礎(chǔ)，增設(shè)模式識別、機器學(xué)習(xí)、數(shù)理統(tǒng)計、人工智能等多種技術(shù)，通過流數(shù)據(jù)及數(shù)據(jù)庫完成工作[1]。在數(shù)據(jù)技術(shù)不斷發(fā)展的過程中，還融入了數(shù)據(jù)安全、數(shù)據(jù)結(jié)構(gòu)算法、信息檢索、信號處理、信息論等多種技術(shù)。聚類分析則是一項比較實用的數(shù)據(jù)挖掘技術(shù)，因其能有效分析數(shù)據(jù)并發(fā)現(xiàn)其中的有用信息，被廣泛用于文本搜索、人工智能、圖像分析等領(lǐng)域[2]。聚類分析把數(shù)據(jù)對象劃分為多個簇，雖然同一個簇內(nèi)的數(shù)據(jù)對象相似，但不同簇內(nèi)的對象存在一定的差異。本文在深入分析大數(shù)據(jù)挖掘流程的基礎(chǔ)上，提出基于MapReduce的并行化模型，以期為類似研究提供一定參考。

1 ?大數(shù)據(jù)挖掘?qū)崿F(xiàn)流程

大數(shù)據(jù)來源比較廣泛，其數(shù)據(jù)類型有所差異，但最基本的處理流程大致相似，如圖1所示。開展數(shù)據(jù)挖掘的主要目的就是從復(fù)雜的數(shù)據(jù)內(nèi)提取隱含的、未知的、有價值的信息，并將其用在生產(chǎn)實踐中，從而提升生產(chǎn)效率[3?4]。通過數(shù)十年的發(fā)展，數(shù)據(jù)挖掘技術(shù)慢慢發(fā)展成熟，并匯聚數(shù)據(jù)庫、人工智能等領(lǐng)域的關(guān)鍵知識。數(shù)據(jù)挖掘技術(shù)也在聚類、關(guān)聯(lián)分析等領(lǐng)域得到迅速發(fā)展，并逐步完成相關(guān)的數(shù)據(jù)挖掘算法，例如，貝葉斯算法等。

圖1 ?數(shù)據(jù)處理基本流程

1） 數(shù)據(jù)預(yù)處理。這一階段的主要作用在于對大量有噪聲的原始數(shù)據(jù)實施去除冗余處理，并提取有效的數(shù)據(jù)，將其轉(zhuǎn)換為合適的數(shù)據(jù)格式[5]。數(shù)據(jù)預(yù)處理包含數(shù)據(jù)選擇、清洗、轉(zhuǎn)換等環(huán)節(jié)。

2） 數(shù)據(jù)挖掘算法引擎包含算法執(zhí)行、評估優(yōu)化、獲取結(jié)果三個環(huán)節(jié)。通過對算法執(zhí)行的輸出結(jié)果進行分析和評估優(yōu)化處理，可以為相應(yīng)的算法提供反饋[6?7]。而用戶交互的主要功能在于接收用戶發(fā)布的指令，負(fù)責(zé)輸出相應(yīng)的數(shù)據(jù)挖掘結(jié)果。

近些年，由于互聯(lián)網(wǎng)等行業(yè)的發(fā)展，數(shù)據(jù)量明顯增加，使得數(shù)據(jù)規(guī)模更龐大，數(shù)據(jù)類型更多元。與此同時，數(shù)據(jù)挖掘的具體需求和應(yīng)用環(huán)境也日趨復(fù)雜。這些改變給傳統(tǒng)數(shù)據(jù)挖掘算法帶來嚴(yán)峻的挑戰(zhàn)?；诖?，采用分布式并行方法可以解決數(shù)據(jù)挖掘難題。

2 ?構(gòu)建數(shù)據(jù)挖掘算法并行化模型

2.1 ?數(shù)據(jù)挖掘并行化處理思路

數(shù)據(jù)處理的前提在于做好數(shù)據(jù)存儲，而大數(shù)據(jù)處理、分析的重點在于具有分布式存儲功能及較強的計算能力。在單體計算資源限定的基礎(chǔ)上，解決計算問題時使用并行計算技術(shù)可以打破內(nèi)存、CPU等方面的限制，有效提高計算效率。針對數(shù)據(jù)挖掘計算量大這一難點，一般有以下解決思路：

1） 任務(wù)并行化處理：設(shè)計一種新的并行算法，把數(shù)據(jù)挖掘任務(wù)拆分為多個子任務(wù)，并把子任務(wù)提交到各節(jié)點展開處理[8]。

2） 數(shù)據(jù)并行化處理：在并行任務(wù)執(zhí)行結(jié)構(gòu)的基礎(chǔ)上，把數(shù)據(jù)拆分為支持并行處理的子集，并在不同子集處理完成后合并獲取最終的結(jié)果。

這兩種并行挖掘方法各有其優(yōu)點，能夠滿足不同應(yīng)用場景的實際需求。在一般情況下，這兩種挖掘方法可以互相補充，協(xié)同完成挖掘任務(wù)。

2.2 ?依托MapReduce建立并行化模型

在現(xiàn)實場景下，大部分的大型數(shù)據(jù)管理系統(tǒng)均以分布式形式出現(xiàn)。在數(shù)據(jù)挖掘過程中，傳統(tǒng)的數(shù)據(jù)挖掘技術(shù)采用集中存儲，統(tǒng)一處理的方法。但隨著數(shù)據(jù)量的不斷增加，已有硬件的存儲空間已經(jīng)無法滿足集中存儲的需求。在這種情況下，需要利用分布式數(shù)據(jù)挖掘策略順利完成挖掘任務(wù)。

分布式并行數(shù)據(jù)挖掘模型如圖2所示。

圖2 ?建立的并行數(shù)據(jù)挖掘模型

MapReduce作為比較適用于進行大數(shù)據(jù)量處理、計算環(huán)節(jié)簡單的并行計算框架，把MapReduce應(yīng)用到數(shù)據(jù)挖掘方面成為有效解決大數(shù)據(jù)挖掘難題的一種需求。有學(xué)者在NIPS國際會議上提出“求和范式”條件，該條件指出一個數(shù)據(jù)挖掘算法是否可以通過MapReduce完成并行化處理，其重點在于算法是否可以將數(shù)據(jù)分解成不同的部分，并將其交給不同的計算節(jié)點獨立完成計算，最終匯總相應(yīng)的計算結(jié)果。依據(jù)數(shù)據(jù)挖掘算法設(shè)定的“求和范式”條件，建立如圖3所示數(shù)據(jù)挖掘算法并行化處理模型。

圖3 ?MapReduce條件下數(shù)據(jù)挖掘算法并行化模型

通過分析圖3可知，MapReduce并行化執(zhí)行流程如下：首先啟動算法引擎，然后引擎開啟相應(yīng)的調(diào)度器，從而合理控制Mapper及其Reducer運行情況。

1） 調(diào)度器在Hadoop內(nèi)屬于熱插拔組件，其主要作用在于合理分配系統(tǒng)資源。目前，Hadoop包含三個常用的調(diào)度器：FIFO Scheduler，F(xiàn)air Scheduler，CaPacity Scheduler等。其中，F(xiàn)IFO Scheduler作為原理比較簡單的調(diào)度器，也是Hadoop默認(rèn)設(shè)置的調(diào)度機制。FIFO Scheduler實施調(diào)度機制在于Hadoop根據(jù)隊列先后順序開展作業(yè)，即先把作業(yè)提交至隊列，并執(zhí)行相應(yīng)的操作。Fair Scheduler屬于一個多用戶的調(diào)度器，與前者相比較，其主要優(yōu)勢在于支持資源公平共享、支持負(fù)載均衡機制等。Capacity Scheduler屬于一個多用戶調(diào)度器，具有復(fù)雜的算法機制，支持多個隊列，Hadoop在選取隊列執(zhí)行操作時，它用于計算篩選隊列。

2） 調(diào)度器支持把分片數(shù)據(jù)分配至與之對應(yīng)的Mapper節(jié)點上進行處理。Mapper節(jié)點接收相應(yīng)的Map任務(wù)后，會建立TaskInProgress實例，這一實例主要用來完成任務(wù)調(diào)度和監(jiān)控工作。為更好地執(zhí)行該Map任務(wù)，需要建立TaskRunner實例，并通過啟動JVM確保Map函數(shù)處于運行狀態(tài)。Map任務(wù)執(zhí)行流程如圖4所示。分析圖4可知，分配而來的數(shù)據(jù)被解析為格式的鍵值對，隨之，通過對自定義map（）函數(shù)實施處理和計算，獲取結(jié)果進行緩存。當(dāng)緩存已經(jīng)存滿，需要保存至本地磁盤。

圖4 ?Map任務(wù)實現(xiàn)流程

3） Mapper節(jié)點經(jīng)過處理后中間數(shù)據(jù)交給Reducer 節(jié)點進行處理。在某些Map任務(wù)順利完成后，JobTracker會將Reduce任務(wù)分配給與之對應(yīng)的Reducer節(jié)點。必須注意，此時，Reduce任務(wù)并未開始執(zhí)行，僅僅是開展一些數(shù)據(jù)的準(zhǔn)備工作，從而有效節(jié)省整體時間。在全部的Map任務(wù)順利完成后，Reducer節(jié)點才開始執(zhí)行Reduce任務(wù)。

4） 當(dāng)Reducer完成相應(yīng)的處理工作后，會把結(jié)果匯總并返回。每一個Reducer節(jié)點的輸出結(jié)果保存在臨時文件內(nèi)，當(dāng)全部的Reduce任務(wù)順利完成后，所有臨時文件數(shù)據(jù)均要實施合并處理，從而組成相應(yīng)的輸出文件。

3 ?基于MapReduce并行聚類算法實現(xiàn)

在MapReduce基礎(chǔ)上的并行遺傳算法就是對粗粒度遺傳算法進行改進，順利實現(xiàn)Map與Reduce這兩個環(huán)節(jié)的聚類，系統(tǒng)會把輸入的數(shù)據(jù)集劃分為一定大小的文件塊（Split），每個文件塊又被一個Mapper進行處理，從而完成第一階段的聚類。在此基礎(chǔ)上，把第一階段聚類產(chǎn)生的數(shù)據(jù)交由單個的Reducer實施處理，形成第二階段聚類。如此一來，多個Mapper與單個Reducer即可執(zhí)行這一算法，其實現(xiàn)模型如圖5所示。

圖5 ?改進后MapReduce并行算法計算框架

其中，在第二個聚類階段，首先接收源自Mapper染色體并組成一條新的染色體。此外，對那些質(zhì)心間距比設(shè)定閾值小的聚類進行合并，合并后形成新的質(zhì)心作為原來質(zhì)心平均值。通過反復(fù)實驗可知，質(zhì)心間距離設(shè)置為20%，可以確保獲得合理結(jié)果，閾值求解公式如下：

式中：[T]表示閾值;[Mi，j]表示聚類[i，j]兩者間的距離;[Di]，[Dj]分別表示[i]類和[j]類各自距離質(zhì)心最遠(yuǎn)點的距離。在此基礎(chǔ)上，重復(fù)以上過程，直至染色體內(nèi)所有的聚類質(zhì)心間距存在一個大于指定閾值，迭代結(jié)束。最終，染色體獲取最佳的聚類中心位置。

4 ?結(jié) ?語

由于數(shù)據(jù)挖掘面臨著數(shù)據(jù)量不斷增長的挑戰(zhàn)，如何高效率、低成本、可擴展地從海量數(shù)據(jù)內(nèi)挖掘有價值的信息成為數(shù)據(jù)挖掘急需解決的問題。傳統(tǒng)并行算法在海量數(shù)據(jù)挖掘方面有一定的成效，但針對并行任務(wù)編程難度大、成本高、網(wǎng)絡(luò)帶寬受限等問題，本文提出的MapReduce編程模型能顯著提升數(shù)據(jù)挖掘效率。本研究在掌握MapReduce并行計算框架的前提下，依托多種數(shù)據(jù)挖掘算法展開分析，建立MapReduce的數(shù)據(jù)挖掘算法并行化模型，并提出并行聚類算法。依據(jù)這一模型，可以突破海量數(shù)據(jù)挖掘面臨的性能瓶頸，有利于進一步提升數(shù)據(jù)決策價值的有效性。

參考文獻(xiàn)

[1] 封俊紅，張捷，朱曉姝，等.基于PAM和均勻設(shè)計的并行粒子群優(yōu)化算法[J].計算機工程與應(yīng)用，2016，52（12）：19?25.

FENG Junhong， ZHANG Jie， ZHU Xiaoshu， et al. Parallel particle swarm optimization algorithm based on PAM and uniform design ?[J]. Computer engineering and applications， 2016， 52（12）： 19?25.

[2] 黃斌，許舒人，蒲衛(wèi)，等.基于MapReduce的數(shù)據(jù)挖掘平臺設(shè)計與實現(xiàn)[J].計算機工程與設(shè)計，2013，34（2）：495?501.

HUANG Bin， XU Shuren， PU Wei， et al. Design and implementation of data mining platform based on MapReduce [J]. Computer engineering and design， 2013， 34（2）： 495?501.

[3] 朱付保，白慶春，湯萌萌，等.基于MapReduce的數(shù)據(jù)流頻繁項集挖掘算法[J].華中師范大學(xué)學(xué)報（自然科學(xué)版），2017，51（4）：429?434.

ZHU Fubao， BAI Qingchun， TANG Mengmeng， et al. MapReduce?based frequent itemsets mining algorithm for data streams [J]. Journal of Central China Normal University （Natural Science Edition）， 2017， 51（4）： 429?434.

[4] 張振友，孫燕，丁鐵凡，等.一種新型的基于Hadoop框架的分布式并行FP?Growth算法[J].河北工業(yè)科技，2016，33（2）：169?177.

ZHANG Zhenyou， SUN Yan， DING Tiefan， et al. A new distributed parallel FP?Growth algorithm based on Hadoop framework [J]. Hebei industrial science and technology， 2016， 33（2）： 169?177.

[5] 魏玲，郭新朋.基于并行處理機制的數(shù)據(jù)復(fù)用策略研究[J].計算機應(yīng)用研究，2017，34（8）：2324?2328.

WEI Ling， GUO Xinpeng. Research on data reuse strategy based on parallel processing mechanism [J]. Application research of computers， 2017， 34（8）： 2324?2328.

[6] 周浩，劉萍，邱桃榮，等.基于粒計算的決策樹并行算法的應(yīng)用[J].計算機工程與設(shè)計，2015（6）：1504?1509.

ZHOU Hao， LIU Ping， QIU Taorong， et al. Application of decision tree parallel algorithm based on granular computing [J]. Computer engineering and design， 2015（6）： 1504?1509.

[7] 趙艷萍，徐勝超.基于云計算與非負(fù)矩陣分解的數(shù)據(jù)分級聚類[J].現(xiàn)代電子技術(shù)，2018，41（5）：56?60.

ZHAO Yanping， XU Shengchao. Data hierarchical clustering algorithm based on cloud computing and NMF [J]. Modern electronics technique， 2018， 41（5）： 56?60.

[8] 李娜，余省威.云計算環(huán)境下多服務(wù)器多分區(qū)數(shù)據(jù)的高效挖掘方法設(shè)計[J].現(xiàn)代電子技術(shù)，2017，40（10）：43?45.

LI Na， YU Shengwei. Design of efficient mining method for multi?server and multi?partition data in cloud computing environment [J]. Modern electronics technique， 2017， 40（10）： 43?45.