黃 黎，顧 筠

HUANG Li，GU Jun

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

0 引言

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

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

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

1 相關研究工作

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

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

2 并行化數(shù)據(jù)分類算法模型

2.1 MapReduce并行集成分類執(zhí)行框架

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

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

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

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

2.2 并行化特征提取

2.2.1 基于詞共現(xiàn)模型的并行化特征提取算法

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

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

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

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

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

2.2.2 基于知識推理的并行化特征構(gòu)造算法

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

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

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

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

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

3）Reduce函數(shù)對經(jīng)過規(guī)則限制及推理后的中間結(jié)果進行合并，輸出結(jié)果＜＜Label,ID＞,特征向量＞，送入特征加權(quán)MapReduce過程。

2.3 并行化特征加權(quán)

2.3.1 基于TF*RF的并行化特征加權(quán)算法

使用“單位”樣式。

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

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

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

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

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

2.3.2 基于概念層次結(jié)構(gòu)的并行化特征加權(quán)算法

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

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

在基于概念層次結(jié)構(gòu)的特征加權(quán)MapReduce化過程中，Job1主要針對每個文檔中的每個特征計算它的權(quán)值。Job2主要實現(xiàn)將＜＜Lable,ID＞,特征向量＞形式的數(shù)據(jù)轉(zhuǎn)換為＜＜Lable,ID＞,特征向量加權(quán)＞的形式。

2.4 關鍵詞并行化特征分類

2.4.1 KNN并行化分類算法

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

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

2.4.2 SVM并行化分類算法

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

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

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

3）Map產(chǎn)生中間結(jié)果，把輸入的數(shù)據(jù)作為value，list中每組參數(shù)對作為key進行輸出。

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

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

3 性能測試和評估

3.1 實驗環(huán)境搭建

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

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

3.2 測試結(jié)果評價

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

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

表1 在Amazon Commerce Reviews上的精度

表2 在Adult上的精度

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

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

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

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

4 結(jié)束語

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

[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]錢進,苗奪謙,張澤華.云計算環(huán)境下差別矩陣知識約簡算法研究[J].計算機學報,2011,38(8):193-196.

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

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

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

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