基于Hadoop平臺的并行化數據分類算法研究

黃 黎，顧 筠

HUANG Li，GU Jun

(江蘇開放大學 信息工程系，南京 210017)

0 引言

隨著云時代的到來和移動互聯網的快速發展，數據規模急劇膨脹，數據挖掘的要求和環境也變得越來越復雜。數據分類作為數據挖掘中一項非常重要的工作，在商業、軍事、科研的決策分析中應用廣泛。但是海量數據本身具有噪聲、異構、算法復雜、技術復雜等問題，使得傳統的基于統計理論和機器學習算法的分類方法及其體系架構在海量數據中面臨很多局限，因此，在海量Web數據分類中如何提高數據處理能力和執行效率已成目前的研究熱點。

云計算平臺提供的分布式文件存儲和并行計算能力，為解決海量數據挖掘任務，提高挖掘效率提供了有效的手段。云計算Hadoop[1]平臺的分布式系統基礎架構充分利用超大集群進行高速運算和存儲，為海量數據挖掘提供了一個并行計算框架。用戶可以在不了解分布式底層細節的情況下，利用其MapReduce編程模式開發一個高度可擴展的分布式批量處理系統，有利于進行海量數據分類[2,3]。

本文基于云計算Hadoop平臺下的MapReduce并行技術，提出改進的海量數據集成分類算法，提高了分類精度，在分類效率上達到了較好的加速比。

1 相關研究工作

目前，基于云計算的海量數據挖掘技術的研究正成為學術界研究的熱點，很多學者認為MapReduce模型適合結構一致的海量數據，且要求計算簡單；而大量的數據密集型應用，往往涉及到數據降維、程序迭代、近似求解等復雜的算法，計算非常困難。針對傳統數據挖掘軟件擴展性差以及MapReduce數據分析功能薄弱的特點，斯坦福大學Chu等人在國際學術會議NIPS’2006提出一種基于MapReduce的、適用于大量機器學習算法的通用并行編程框架，實現了在若干獨立數據集上的并行化求和操作。Ranger等人提出了一個基于MapReduce的應用程序編程接口Phoenix，并實現了K-Means、主成分分析和線性回歸三種數據挖掘算法。2011年，IBM研究院在KDD’2011會議上提出一種改進的基于MapReduce的并行數據挖掘和機器學習算法執行工具包NIMBLE[4]。中科院計算所與中國移動研究院合作研發了基于Hadoop的并行分布式數據挖掘平臺PDMiner，集成了多種機器學習算法。但是基于云計算的海量數據挖掘技術仍存在許多問題亟待解決，例如各種數據挖掘算法的并行化策略，在MapReduce上實現更加復雜的分析、更大規模的分析等。

國內也有學者基于云計算的分布特點，做了很多研究工作。復旦大學一篇2010年SIGIR的論文對文檔局部重復檢測做了研究[5]，他們的工作將重復檢測定位于更細粒度的句子級別，使用了三步MapReduce工作：首先建立倒排索引，然后提取出句子特征，建立句子重復矩陣，最終將句子重復檢測過程轉換成了矩陣的對角線發現的過程。有學者提出基于屬性集的不可辨識性和MapReduce設計了適合數據并行的差別矩陣，首次提出了面向大規模數據的差別矩陣知識約簡算法[6]。很多研究者對在多核集群上以MapReduce方式實現機器學習算法進行了研究，如：KNN，K-means，ID3決策樹等，驗證了MapReduce化的高效性和可擴展性，在一定程度上提高了大數據處理的效率但并未改變傳統決策樹算法的分類精度[7～9]。有研究者采用樸素貝葉斯文本分類算法的MapReduce并行化方法，對文本統一格式進行分類，識別率達到86%，由于沒有進行專門的特征詞提取，因此對實驗結果有一定程度的影響[10]。

2 并行化數據分類算法模型

2.1 MapReduce并行集成分類執行框架

數據分類過程一般分為3個關鍵過程：特征提取、特征加權和特征分類。針對大數據分類的上述過程，提出基于Hadoop平臺的并行化分類算法，利用MapReduce并行編程模式的可擴展性，充分利用集群達到高速運算和有效分類的目的。具體過程如下：

1）并行特征提?。豪貌煌卣髟~共同出現的頻率進行衡量，執行基于詞共現模型的特征提取，形成具有領域指向性的特征項集合；針對特征稀疏問題，利用外部知識庫構造產生新的特征集合，執行基于知識推理的特征構造。

2）并行特征加權：針對特征項，按照語義相關性進行啟發式分析，利用TF*RF方法和基于概念層次結構的加權算法衡量分類特征項的重要程度。

3）并行特征分類：實現基于SVM、KNN分類算法的并行化處理。

2.2 并行化特征提取

2.2.1 基于詞共現模型的并行化特征提取算法

該過程利用反映主題特征的多個屬性項，即頻繁共現詞(Co-occurrence)，通過特征之間的關聯性提高特征向量之間距離計算的準確性。其MapReduce化過程如下：

1）使用分詞工具對原數據集進行分詞，得到分詞集合。

2）在每個Map函數中讀入分詞后的集合塊，對塊中的每個分詞后的文檔提取Label和文檔ID，作為key值，然后通過信息增益從集合塊中選擇決策性特征，形成特征序列，加入到value中，形成＜key,value＞。

3）每個Map函數輸出中間值對＜＜Label,ID＞,特征向量,特征相關性(COR)＞，其中，特征相關性利用不同特征詞共同出現的頻率進行衡量，共現的頻率越高，其關聯越緊密。特征間的相對共現度可計算如下：

4）Reduce函數將上述中間結果中key值相同的結果合并，處理所有相同key值的特征向量，并且輸出最終的＜＜Label,ID＞,特征向量＞。

2.2.2 基于知識推理的并行化特征構造算法

針對特征提取中關鍵詞同義、近義、稀疏等問題，本文采取一種基于WordNet知識推理(WordNet-Inference)的學習方法，利用WordNet中的同義詞集合為每個集合標明一個詞匯概念，利用特征屬性的同義詞集合對文檔特征進行劃分。其MapReduce化過程如下：

1）每個M a p函數以文檔為單位，將＜Label,ID＞讀入key中。

2）利用WordNet相似度(WordNet-Similarity)計算包獲得兩個形式相似或各異的詞項在同義詞集合中的近似概念范圍，輸出中間值對。

其中，語義關聯特征的推理形式化表示如下：ai和aj是分別位于不同文檔中的屬性特征，按照WordNet中詞匯的上位詞對這兩個特征屬性詞匯尋找其共同上位af，當存在該共同上位時，則可用該共同上位詞af替代ai和aj，可更好的突出主題，達到較好的分類目的。

同時，對推理規則進行嚴格限制：利用語義相似度權函數計算特征詞間的語義距離d，給定λ表示語義距離閾值，只有滿足大于閾值的概念特征才進行語義推理。

3）Reduce函數對經過規則限制及推理后的中間結果進行合并，輸出結果＜＜Label,ID＞,特征向量＞，送入特征加權MapReduce過程。

2.3 并行化特征加權

2.3.1 基于TF*RF的并行化特征加權算法

使用“單位”樣式。

特征權重是對特征向量值的計算方式，常用的計算方式有TF*IDF，Binary，TF，TF*CHI等，IDF類方法雖然考慮了詞的分布特征，但是IDF沒有考慮到類別的區分度，在實際實驗中效果有時沒有提升反而會下降，因此本文采用TF*RF的特征加權算法。TF計算方法如下：

其中n(t,d)是詞語t在文檔d中出現的次數，分母是文檔d中所有詞語出現次數總和。

文檔中詞語t的RF（Relevance Frequency，相關度頻率）計算方法如下：

其中，b表示詞語t在正例中的文檔個數，c表示負例的文檔個數。顯然，對正面分類中的高頻詞比負面分類考慮得越多，那么，它對正例選擇所做的貢獻就要比負例越大。

基于TF-RF的特征加權MapReduce化過程由兩個MapReduce Job組成， Job1以文檔＜Lable,ID＞作為key，特征向量（Term-Vector）作為value，Reduce1計算每個特征的TF-RF值；Job2負責將＜＜Label,ID＞,特征TF-RF＞形式的數據轉換為＜＜Label,ID＞,特征向量＞的形式。

2.3.2 基于概念層次結構的并行化特征加權算法

在2.2.2中構造的概念層次結構(Concept-Hierarchy)中，形成了一個多個概念主題特征下的多元特征集合，即F={A,C1,…,Cn}，A表示原始特征集合，Ci表示相關概念的特征集合。當文檔中的若干特征均與某一概念存在映射關系時，則其權值可計算如下：

其中，wF(ai)表示特征屬性ai的權重，wInvIndex(cj)表示概念cj相對于ai的權重，kj為特征aj對應的概念cj的索引序列。

在基于概念層次結構的特征加權MapReduce化過程中，Job1主要針對每個文檔中的每個特征計算它的權值。Job2主要實現將＜＜Lable,ID＞,特征向量＞形式的數據轉換為＜＜Lable,ID＞,特征向量加權＞的形式。

2.4 關鍵詞并行化特征分類

2.4.1 KNN并行化分類算法

KNN分類算法依據最鄰近的K個樣本的類別來決定待分類樣本所屬類別。采用余弦相似度度量文本特征向量之間的距離。

在KNN算法的MapReduce化過程中，Map函數將Label及ID存入key中，將訓練數據文檔的原始特征向量存于value中，計算測試向量與所有的訓練數據的余弦相似度，選擇前K個相似度最大的訓練數據和測試向量一起發送給Reduce函數作為values，Reduce從values中取出距離，選擇K個距離最小的訓練數據，對于這K個訓練樣本，把多數樣本所屬的類別作為該測試數據的類別，輸出分類結果。

2.4.2 SVM并行化分類算法

支持向量機的主要思想是要在r維空間中尋找一個最佳決策面，使得該決策面能最好地區分正例和反例，讓正例和反例之間的分類間隔達到最大。SVM模型有兩個非常重要的參數C與gamma。懲罰系數C越高，說明越不能容忍出現誤差。C過大或過小，泛化能力都會變差。gamma是選擇徑向基函數作為kernel后，該函數自帶的一個參數，隱含地決定了數據映射到新的特征空間后的分布，gamma越大，支持向量越少，gamma值越小，支持向量越多。由于(C,gamma)相互獨立，因此便于并行化進行，其步驟如下：

1）首先將所有的參數對(C,gamma)計算出來，寫入文件中，每行一組參數，然后上傳到Hadoop上，系統會自動的將文件分發到每一臺機器上。

2）將訓練樣本作為輸入，即Map中的每對＜key,value＞就代表著一條樣本，其中key為系統默認值，value為訓練樣本的每一行數據。將所有的參數對讀入到list中。

3）Map產生中間結果，把輸入的數據作為value，list中每組參數對作為key進行輸出。

4）Reduce函數按照key進行排序，并將key相同的數據放在同一個機器上，將具有相同key的所有values匯總組成原來的訓練樣本。

5）把解析出來的參數以及整理好的樣本進行訓練，并把交叉驗證的結果輸出。

3 性能測試和評估

3.1 實驗環境搭建

本實驗基于云計算平臺Hadoop開源框架實現虛擬化集群架構。實驗環境共有7個節點：1個主節點和6個從節點，前者主要配置NameNode和JobTracker的角色，負責總管分布式數據和分解任務的執行，后者配置DataNode和TaskTracker的角色，負責分布式數據存儲以及任務的執行。每個節點的配置為內存4G，4核處理器Intel(R)CoreTM i7 CPU 860@2.8GHz，操作系統為Ubuntu 10.04，Hadoop版本為0.20.2。

本實驗在UCI數據庫的Amazon Commerce Reviews（亞馬遜電子商務網站用戶評論)數據集和Adult（美國人口普查數據)數據集上進行。對每個數據集中的訓練數據和測試數據按9:1的大小比例分配，使用交叉驗證。對每個數據集所采用的特征提取和特征加權采用不同的算法組合，以驗證其分類精度和時間加速比。在基于知識模型推理的特征提取算法中，取λ=0.5，在KNN分類算法中，取K=5。

3.2 測試結果評價

本實驗從兩個方面對Hadoop平臺下的數據分類進行測試，包括：1)大規模數據的分類精度；2)在大數據處理中并行化程度不同所產生的時間加速比。在不同數據集上采用不同算法組合得到的分類精度如表1、表2所示。

表1、表2的實驗結果表明，盡管基于詞共現模型的特征提取算法很直觀，但是分類精度并不高。這是由于Amazon Commerce Reviews數據量較少，且一般情況下評論本身很短，共現詞出現的幾率相對較小。同時由于評論內容的隨意性，使得該數據集的屬性具有高維性，有10000多個屬性，導致特征提取困難。而基于知識模型推理的特征提取方法整體上優于共現詞模型特征提取方法。另外，在各種組合下概念模型推理的特征向量加權算法優于TF*RF算法，也體現出SVM算法相對于KNN算法在分類精度上的優勢。同時，對比兩個數據集的分類精度發現在Adult數據集上的測試結果優于Amazon數據集。這是由于Adult數據集的樣本量較大，抽取的特征數量高于Amazon數據集，屬性數量適宜，有14個屬性，屬性類別主要為數值型和類別型，屬于半結構化的數據類型，因此分類精度較好。

表1 在Amazon Commerce Reviews上的精度

表2 在Adult上的精度

在同一數據集上，不同的算法組合得到的加速比是不一樣的，但是加速比的變化趨勢都是一致的，即隨著DataNode個數的增加而遞增。如圖2所示，其中C表示Co-occurrence，W表示WordNet-Inference，T表示TF*RF，H表示Concept-Hierarchy，K表示KNN，S表示SVM。

圖1 MapReduce并行化分類算法加速比

由圖1可以看出，WHS算法組合在兩個數據集上均獲得了最優加速比。在圖1(a)中不同算法組合所得到的加速比差別不大，但在圖1(b)中差別就比較明顯，主要原因在于圖1(b)的特征數量明顯多于圖1(a)，且特征提取算法的優化使得特征數量逐漸增加，用于并行計算的開銷占整體開銷的比重也在增加，因此，加速比的增長量也就增加了。

同時，圖1(b)的最優加速比優于圖1(a)。因為圖1(a)數據集小于圖1(b)數據集，當數據集較小時，各個節點用于計算的時間較少，隨著DataNode節點的增加，用于通信的時間開銷所占的比重就會明顯增加，而對于較大數據集，各個節點的計算時間較長，用于通信的時間開銷所占的比重則相對較小。由此可見，該算法在規模較大的數據集上具有較好的加速比，因此在大規模數據的并行處理上更具優勢。

4 結束語

云計算作為一種新型的大數據處理模型，為解決海量數據分類提供了新的解決途徑。本文提出一種基于Hadoop平臺的并行化數據分類算法，分別對特征提取、特征加權和特征分類3個關鍵環節的多種算法進行并行化計算，并通過對不同并行化算法組合的對比分析，驗證了該算法的可行性和高效性，取得了較好的分類精度和加速比，達到了并行化處理大規模數據的目的。

[1]Hadoop[EB/OL].[2012-10-02]. http://hadoop.apache.org/index.heml

[2]Dean Jeffrey, Ghemawat Sanjay, MapReduce: a flexible data processing tool[J].Communications of the ACM,2010,53(1):72-77.

[3]Lin Jimmy,Dyer Chris, Data-Intensive Text Processing with MapReduce[M].2010.

[4]Amol Ghoting, Prabhanjan Kambadur, Edwin Pednault,et al, NIMBLE:An Infrastructure for the Rapid Implementation of Parallel Data Mining and Machine Learning Algorithms on MapReduce, San Diego,KDD,2011:334-342.

[5]Zhang Qi, Zhang Yue, Yu Haomin, et al, Efficient partialduplicate detection based on sequence matching[C]//Proceeding of the 33rd international ACM SIGIR conference on research and development in information retrieval, Geneva,2010:657-682.

[6]錢進,苗奪謙,張澤華.云計算環境下差別矩陣知識約簡算法研究[J].計算機學報,2011,38(8):193-196.

[7]閆永剛,馬廷淮,王建.KNN分類算法的MapReduce并行化實現[J].南京航空航天大學學報,2013,45(4):550-555.

[8]錢網偉.基于MapReduce的ID3決策樹分類算法研究[J].計算機與現代化,2012,2:26-30.

[9]趙衛中,馬慧芳,傅燕翔,等.基于云計算平臺Hadoop的并行K-means 聚類算法設計研究[J].計算機科學,2011,38(10):166-168,176.

[10]江小平,李成華,等.云計算環境下樸素貝葉斯文本分類算法的實現[J].計算機應用,2011,31(9):2551-2554,2556.