呂國 肖瑞雪 白振榮 孟凡興

摘 ?要： ?針對傳統(tǒng)數(shù)據(jù)挖掘算法只適用于小規(guī)模數(shù)據(jù)挖掘處理，由于數(shù)據(jù)規(guī)模不斷增大，其存在計(jì)算效率低、內(nèi)存不足等問題，文中將MapReduce用于數(shù)據(jù)挖掘領(lǐng)域，對大數(shù)據(jù)挖掘中的MapReduce進(jìn)行了并行化改進(jìn)，并設(shè)計(jì)相應(yīng)的并行化實(shí)現(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ù)時(shí)代的來臨，互聯(lián)網(wǎng)的數(shù)據(jù)量正呈現(xiàn)出爆炸式的增長，采用傳統(tǒng)數(shù)據(jù)分析法對其進(jìn)行分析和研究，已經(jīng)無法滿足海量數(shù)據(jù)處理的需求。基于此，數(shù)據(jù)挖掘技術(shù)隨之產(chǎn)生。數(shù)據(jù)挖掘就是從大量、隨機(jī)、模糊、有噪聲的數(shù)據(jù)內(nèi)提取有價(jià)值的信息。數(shù)據(jù)挖掘技術(shù)是指從大量數(shù)據(jù)中利用算法對隱藏信息進(jìn)行搜索的過程，目前被廣泛應(yīng)用于金融、網(wǎng)絡(luò)、決策及教育等行業(yè)中。數(shù)據(jù)挖掘技術(shù)以統(tǒng)計(jì)學(xué)作為基礎(chǔ)，增設(shè)模式識別、機(jī)器學(xué)習(xí)、數(shù)理統(tǒng)計(jì)、人工智能等多種技術(shù)，通過流數(shù)據(jù)及數(shù)據(jù)庫完成工作[1]。在數(shù)據(jù)技術(shù)不斷發(fā)展的過程中，還融入了數(shù)據(jù)安全、數(shù)據(jù)結(jié)構(gòu)算法、信息檢索、信號處理、信息論等多種技術(shù)。聚類分析則是一項(xiàng)比較實(shí)用的數(shù)據(jù)挖掘技術(shù)，因其能有效分析數(shù)據(jù)并發(fā)現(xiàn)其中的有用信息，被廣泛用于文本搜索、人工智能、圖像分析等領(lǐng)域[2]。聚類分析把數(shù)據(jù)對象劃分為多個(gè)簇，雖然同一個(gè)簇內(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)提取隱含的、未知的、有價(jià)值的信息，并將其用在生產(chǎn)實(shí)踐中，從而提升生產(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í)施去除冗余處理，并提取有效的數(shù)據(jù)，將其轉(zhuǎn)換為合適的數(shù)據(jù)格式[5]。數(shù)據(jù)預(yù)處理包含數(shù)據(jù)選擇、清洗、轉(zhuǎn)換等環(huán)節(jié)。

2） 數(shù)據(jù)挖掘算法引擎包含算法執(zhí)行、評估優(yōu)化、獲取結(jié)果三個(gè)環(huán)節(jié)。通過對算法執(zhí)行的輸出結(jié)果進(jìn)行分析和評估優(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í)，數(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ù)處理、分析的重點(diǎn)在于具有分布式存儲功能及較強(qiáng)的計(jì)算能力。在單體計(jì)算資源限定的基礎(chǔ)上，解決計(jì)算問題時(shí)使用并行計(jì)算技術(shù)可以打破內(nèi)存、CPU等方面的限制，有效提高計(jì)算效率。針對數(shù)據(jù)挖掘計(jì)算量大這一難點(diǎn)，一般有以下解決思路：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖5 ?改進(jìn)后MapReduce并行算法計(jì)算框架

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

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

4 ?結(jié) ?語

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

參考文獻(xiàn)

[1] 封俊紅，張捷，朱曉姝，等.基于PAM和均勻設(shè)計(jì)的并行粒子群優(yōu)化算法[J].計(jì)算機(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è)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與設(shè)計(jì)，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ù)流頻繁項(xiàng)集挖掘算法[J].華中師范大學(xué)學(xué)報(bào)（自然科學(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] 魏玲，郭新朋.基于并行處理機(jī)制的數(shù)據(jù)復(fù)用策略研究[J].計(jì)算機(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] 周浩，劉萍，邱桃榮，等.基于粒計(jì)算的決策樹并行算法的應(yīng)用[J].計(jì)算機(jī)工程與設(shè)計(jì)，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] 趙艷萍，徐勝超.基于云計(jì)算與非負(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] 李娜，余省威.云計(jì)算環(huán)境下多服務(wù)器多分區(qū)數(shù)據(jù)的高效挖掘方法設(shè)計(jì)[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.