基于Hadoop技術(shù)的并行計算模式定向數(shù)據(jù)挖掘方法

葉苗 張國華

（南京師范大學(xué)泰州學(xué)院 江蘇省泰州市 225300）

信息技術(shù)迅猛發(fā)展，互聯(lián)網(wǎng)數(shù)據(jù)呈指數(shù)倍增長態(tài)勢，傳統(tǒng)計算機(jī)體系架構(gòu)已難以有效處理當(dāng)前的大規(guī)模數(shù)據(jù)。因此，云計算技術(shù)應(yīng)運而生，為海量數(shù)據(jù)挖掘領(lǐng)域提供良好契機(jī)[1]。隨著網(wǎng)絡(luò)技術(shù)日新月異的發(fā)展，許多傳統(tǒng)的數(shù)據(jù)挖掘策略已不再適用于不斷更新?lián)Q代的數(shù)據(jù)類型與應(yīng)用環(huán)境，其已對挖掘精度與實時性提出了更高的要求。因此，研究一種更理想的海量數(shù)據(jù)挖掘方法具有重要的現(xiàn)實意義。

為滿足當(dāng)前數(shù)據(jù)挖掘技術(shù)的應(yīng)用需求，本文利用Hadoop技術(shù)與并行計算模式，設(shè)計出一種定向數(shù)據(jù)挖掘方法。其中，Hadoop平臺具有管理存儲在多臺計算機(jī)上數(shù)據(jù)分塊的能力，憑借優(yōu)秀的運算能力、存儲能力、調(diào)度能力，在數(shù)據(jù)挖掘[2]方向被廣泛應(yīng)用；設(shè)計校驗修正公式與控制允許誤差范圍的容忍度閾值，提升校驗公式兩邊數(shù)值相等概率，確保挖掘結(jié)果的可靠性，校驗節(jié)點存儲容量與性能值的一致性；通過MapReduce計算模式下樸素貝葉斯分類算法，提升定向數(shù)據(jù)挖掘精度與效率。

1 Hadoop技術(shù)下并行計算模式定向數(shù)據(jù)挖掘

1.1 基于云計算平臺實現(xiàn)HDFS分布式文件系統(tǒng)存儲

1.1.1 HDFS分布式文件系統(tǒng)

將分布式文件系統(tǒng)引入云計算平臺中，管理存儲在多臺計算機(jī)上的數(shù)據(jù)分塊，該系統(tǒng)以Hadoop分布式為基礎(chǔ)，主要組成部分是一個主數(shù)據(jù)節(jié)點與多個從數(shù)據(jù)節(jié)點。前者將元數(shù)據(jù)服務(wù)給予分布式文件系統(tǒng)內(nèi)部，掌控全部文件；后者則用于備份、存儲若干個切分存儲文件得來的數(shù)據(jù)塊。系統(tǒng)客戶端決定著新建文件過程中的數(shù)據(jù)塊大小與備份數(shù)量。利用標(biāo)準(zhǔn)的TCP/IP[3]協(xié)議完成HDFS（Hadoop Distributed File System）分布式文件系統(tǒng)內(nèi)部各節(jié)點間通信。該系統(tǒng)體系框架如圖1所示。

圖1：HDFS結(jié)構(gòu)示意圖

1.1.2 數(shù)據(jù)存儲

大規(guī)模數(shù)據(jù)存儲主要通過分布式文件系統(tǒng)中的數(shù)據(jù)節(jié)點實現(xiàn)。為此，評估Hadoop集群內(nèi)節(jié)點性能，根據(jù)得到的節(jié)點性能值，選取存儲數(shù)據(jù)塊的合適節(jié)點，按比例在各節(jié)點存儲一定數(shù)量的數(shù)據(jù)塊[4]。具體過程描述如下：

（1）節(jié)點性能評估：假設(shè)i表示任意服務(wù)器節(jié)點，處理器性能值、內(nèi)存性能值以及磁盤I/O性能值分別是Ci、Mi與Di，則該節(jié)點對應(yīng)性能值Pi表達(dá)式如下所示：

式中，各指標(biāo)對服務(wù)器性能不同權(quán)值影響的參數(shù)是α、β、γ，且滿足下列等式：

為確保挖掘結(jié)果的可靠性，校驗修正各節(jié)點性能值的測量結(jié)果。假設(shè)有N個節(jié)點，其中，節(jié)點i完成的任務(wù)個數(shù)為Si，Hadoop集群里各任務(wù)數(shù)據(jù)具有相同規(guī)格，所以，節(jié)點i在固定時段中處理的數(shù)據(jù)量也可以用Si表示，則推導(dǎo)出下列校驗公式：

若Hadoop集群中的任意兩節(jié)點均滿足該校驗公式，說明基于當(dāng)前Hadoop應(yīng)用場景，測得的節(jié)點性能值具有有效性。設(shè)定一個控制允許誤差范圍的容忍度閾值p，令校驗公式兩邊數(shù)值等率更高，則改寫校驗公式為下列表達(dá)式，將其作為實際應(yīng)用中測量結(jié)果校驗標(biāo)準(zhǔn)：

其中，節(jié)點i任務(wù)數(shù)量Si與主數(shù)據(jù)節(jié)點總?cè)蝿?wù)數(shù)SA關(guān)系如下所示：

（2）存儲節(jié)點選取：根據(jù)各節(jié)點數(shù)據(jù)處理能力，在分布式文件系統(tǒng)中完成大規(guī)模數(shù)據(jù)文件存儲，利用節(jié)點存儲容量校驗策略，選取有效存儲節(jié)點，校驗節(jié)點存儲容量與性能值的一致性。

假設(shè)U1,U2,...,UN是各節(jié)點存儲集群的數(shù)據(jù)量規(guī)格，P1,P2,...,PN是相應(yīng)節(jié)點性能值，UA表示集群存儲數(shù)據(jù)量規(guī)格，則任意節(jié)點i存儲集群的數(shù)據(jù)量規(guī)格Ui應(yīng)使下列不等式成立：

式（6）的作用是校驗數(shù)據(jù)量存儲規(guī)格與節(jié)點i性能值的匹配程度。其中，節(jié)點i存儲集群的數(shù)據(jù)量規(guī)格Ui與集群存儲數(shù)據(jù)量規(guī)格UA關(guān)系如下所示：

1.2 基于HDFS平臺構(gòu)建HBASE分布式數(shù)據(jù)庫

以分布式文件系統(tǒng)作為運行基礎(chǔ)，構(gòu)建HBASE分布式數(shù)據(jù)庫，為大量數(shù)據(jù)提供任意、實時的讀寫訪問服務(wù)，提升數(shù)據(jù)可靠性與系統(tǒng)魯棒性。該數(shù)據(jù)庫通過學(xué)習(xí)使文件系統(tǒng)中大表數(shù)據(jù)庫的所有功能得以實現(xiàn)，完成大規(guī)模數(shù)據(jù)的存儲與處理。

1.3 基于Hadoop技術(shù)設(shè)計MapReduce并行計算模式

1.3.1 并行分布式計算

由Map映射功能與Reduce歸約功能組成的MapReduce并行分布式計算模式，是一種具有處理大量數(shù)據(jù)能力的并行分布式編程模式。用戶利用界定的Map函數(shù)，處理key/value（即鍵/值對）與取得的中間結(jié)果，經(jīng)Reduce函數(shù)結(jié)合所有擁有相同key值[5]中間結(jié)果的value值。Map函數(shù)的作用是分塊處理輸入數(shù)據(jù)，將數(shù)據(jù)塊劃分至不同節(jié)點加以并行運行；Reduce函數(shù)功能是歸約中間生成key值的value值，并依據(jù)某分塊函數(shù)，分類中間生成的key值。

1.3.2 MapReduce計算模式下樸素貝葉斯分類

Map函數(shù)的分布計算中難以實時交互各Mapper節(jié)點信息。為獲取計算模式運行結(jié)果，需憑借最終產(chǎn)生的中間結(jié)果，且確保各節(jié)點有相同且獨立的任務(wù)。基于此，利用設(shè)計的樸素貝葉斯分類算法，求取待分類定向數(shù)據(jù)與不同類別的分類概率[6]，劃分定向數(shù)據(jù)至最大分類概率的類別內(nèi)，完成定向數(shù)據(jù)挖掘。

若定向數(shù)據(jù)類別C1,C2,...,Cm的數(shù)量為m，各數(shù)據(jù)對應(yīng)屬性個數(shù)為n，則采用下列n+1維屬性向量X的表達(dá)式來表示各定向數(shù)據(jù)：

針對待分類的定向數(shù)據(jù)X'，判定其與類別Ci的從屬結(jié)果，且滿足下列不等式：

為使定向數(shù)據(jù)X'屬于類別類別Ci的概率超過其余類別，應(yīng)最大化處理P(Ci|X')，引用下列樸素貝葉斯公式實現(xiàn)：

式中，用=P(X')表示常數(shù)，P(Ci)與P(X'|Ci)的計算公式分別為：

式中，D內(nèi)Ci類別的訓(xùn)練元組數(shù)為|Ci,D|。

若求解目標(biāo)是P(x'k|Ci)，判定其屬性Ak種類：當(dāng)屬性Ak為離散時，P(x'k|Ci)是屬性取x'k下Ci類別中元組數(shù)量與所有定向數(shù)據(jù)內(nèi)Ci類別中元組數(shù)量的比值；當(dāng)屬性Ak為連續(xù)時，服從高斯分布，其均值與標(biāo)準(zhǔn)差分別是μ與σ，則P(x'k|Ci)用下列界定表達(dá)式指代：

根據(jù)解得的最大概率類別，完成該定向數(shù)據(jù)X'分類、挖掘。

在MapReduce并行分布式計算模式執(zhí)行該算法的過程中，Main函數(shù)主要負(fù)責(zé)讀取數(shù)據(jù)集、轉(zhuǎn)換Reduce的整合結(jié)果以及計算節(jié)點上的分類器讀取，Map函數(shù)的功能是統(tǒng)計離散屬性取值、求解連續(xù)屬性均值與標(biāo)準(zhǔn)差以及劃分各待分類定向數(shù)據(jù)，而Reduce函數(shù)則用于根據(jù)要求統(tǒng)計、輸出分類與挖掘結(jié)果。各函數(shù)具體實現(xiàn)描述如下：

（1）Map函數(shù)：假設(shè)分布式文件系統(tǒng)的定向數(shù)據(jù)id號與內(nèi)容分別是key與value，已知數(shù)據(jù)集中各定向數(shù)據(jù)及對應(yīng)屬性；若屬性是離散型，則將定向數(shù)據(jù)類別的屬性取值個數(shù)累積起來，若屬性是連續(xù)型，則求取屬性取值的總和與平方和；當(dāng)前分片經(jīng)過遍歷、統(tǒng)計，輸出所得結(jié)果。

（2）Reduce函數(shù)：讀取Mapper節(jié)點全部臨時信息；整合離散型統(tǒng)計結(jié)果，獲取概率；針對L個定向數(shù)據(jù)的連續(xù)屬性，若∑X'表示屬性取值總和，∑X'2表示平方和，采用下列兩公式求取屬性均值μ與標(biāo)準(zhǔn)差σ；統(tǒng)計完全部項目后，輸出MapReduce程序的最終結(jié)果。

（3）Main函數(shù)：讀取輸出的最終結(jié)果；當(dāng)鍵值對標(biāo)記為離散屬性時，按照屬性號、取值、標(biāo)簽號、概率的形式進(jìn)行變換與輸出；當(dāng)鍵值對標(biāo)記為連續(xù)屬性時，按照屬性號、取值、均值、標(biāo)準(zhǔn)差的形式進(jìn)行變換與輸出。

2 實際案例應(yīng)用

選取某市中心城區(qū)擴(kuò)展建設(shè)用地，在本文設(shè)計的基于Hadoop技術(shù)的并行計算模式定向數(shù)據(jù)挖掘方法的支持下，探索城市建設(shè)用地的空間格局與演變特征。該城市建設(shè)項目中涉及到的數(shù)據(jù)分別有建成區(qū)域面積與總土地面積、建設(shè)用地種類、方位數(shù)據(jù)以及時間數(shù)據(jù)。建設(shè)用地擴(kuò)展趨勢如圖2所示。

圖2：建設(shè)用地擴(kuò)展趨勢示意圖

根據(jù)本文方法挖掘得到的連續(xù)七年城區(qū)建成區(qū)域面積變化數(shù)據(jù)與建設(shè)用地不同方向擴(kuò)展強(qiáng)度堆積數(shù)據(jù)可知：該市中心城區(qū)的建設(shè)用地面積呈線性擴(kuò)展趨勢；前兩年建設(shè)擴(kuò)展方向以西部為主，后三年主要擴(kuò)展南部方向建設(shè)，2013、2014連續(xù)兩年在東部方向進(jìn)行了較高強(qiáng)度擴(kuò)展，擴(kuò)展形式以圈層漸進(jìn)式展開，后期擴(kuò)展強(qiáng)度有所減緩。

3 結(jié)語

數(shù)據(jù)挖掘技術(shù)目標(biāo)是從海量低價值數(shù)據(jù)里發(fā)掘可用的高價值數(shù)據(jù)，為拓寬該項技術(shù)的應(yīng)用領(lǐng)域。本文以Hadoop技術(shù)為基礎(chǔ)，提出一種并行計算模式的定向數(shù)據(jù)挖掘方法[7]。針對爆炸式增長的龐大數(shù)據(jù)，需結(jié)合更新、更理想的分類算法，進(jìn)一步優(yōu)化挖掘效果。為此，在未來的研究階段，探索Hadoop平臺啟用時間的縮減策略，加快平臺小數(shù)據(jù)處理速度；應(yīng)嘗試探究相關(guān)運行參數(shù)，合理配置Hadoop云計算平臺，進(jìn)一步提升數(shù)據(jù)挖掘效率，也為城市管理者制定城市建設(shè)方案提供依據(jù)和參考。