黃 黎，顧 筠

HUANG Li，GU Jun

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

0 引言

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

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

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

1 相關(guān)研究工作

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

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

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

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

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

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

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

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

2.2 并行化特征提取

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

使用“單位”樣式。

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

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

文檔中詞語t的RF（Relevance Frequency，相關(guān)度頻率）計(jì)算方法如下：

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

基于TF-RF的特征加權(quán)MapReduce化過程由兩個(gè)MapReduce Job組成， Job1以文檔＜Lable,ID＞作為key，特征向量（Term-Vector）作為value，Reduce1計(jì)算每個(gè)特征的TF-RF值；Job2負(fù)責(zé)將＜＜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)中，形成了一個(gè)多個(gè)概念主題特征下的多元特征集合，即F={A,C1,…,Cn}，A表示原始特征集合，Ci表示相關(guān)概念的特征集合。當(dāng)文檔中的若干特征均與某一概念存在映射關(guān)系時(shí)，則其權(quán)值可計(jì)算如下：

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

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

2.4 關(guān)鍵詞并行化特征分類

2.4.1 KNN并行化分類算法

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

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

2.4.2 SVM并行化分類算法

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

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

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

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

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

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

3 性能測試和評估

3.1 實(shí)驗(yàn)環(huán)境搭建

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

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

3.2 測試結(jié)果評價(jià)

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

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

表1 在Amazon Commerce Reviews上的精度

表2 在Adult上的精度

在同一數(shù)據(jù)集上，不同的算法組合得到的加速比是不一樣的，但是加速比的變化趨勢都是一致的，即隨著DataNode個(gè)數(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算法組合在兩個(gè)數(shù)據(jù)集上均獲得了最優(yōu)加速比。在圖1(a)中不同算法組合所得到的加速比差別不大，但在圖1(b)中差別就比較明顯，主要原因在于圖1(b)的特征數(shù)量明顯多于圖1(a)，且特征提取算法的優(yōu)化使得特征數(shù)量逐漸增加，用于并行計(jì)算的開銷占整體開銷的比重也在增加，因此，加速比的增長量也就增加了。

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

4 結(jié)束語

云計(jì)算作為一種新型的大數(shù)據(jù)處理模型，為解決海量數(shù)據(jù)分類提供了新的解決途徑。本文提出一種基于Hadoop平臺(tái)的并行化數(shù)據(jù)分類算法，分別對特征提取、特征加權(quán)和特征分類3個(gè)關(guān)鍵環(huán)節(jié)的多種算法進(jìn)行并行化計(jì)算，并通過對不同并行化算法組合的對比分析，驗(yàn)證了該算法的可行性和高效性，取得了較好的分類精度和加速比，達(dá)到了并行化處理大規(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]錢進(jìn),苗奪謙,張澤華.云計(jì)算環(huán)境下差別矩陣知識(shí)約簡算法研究[J].計(jì)算機(jī)學(xué)報(bào),2011,38(8):193-196.

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

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

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

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