一種基于動態(tài)調(diào)度的數(shù)據(jù)挖掘并行算法

摘 要： 相比其他分類算法，樸素貝葉斯算法最大的優(yōu)點就是適合被并行化改造。由于單機分類算法不適應大規(guī)模數(shù)據(jù)的處理，而云計算動態(tài)調(diào)度的出現(xiàn)為大數(shù)據(jù)處理帶來了希望，運用并行計算的思想改進算法能提高分類速度。結(jié)合樸素貝葉斯算法易于并行化的特點對算法進行相應的改進。在單機串行、Hadoop、Spark以及CUDA平臺上進行了性能對比實驗，最終證明了分類算法并行化后具有較好的加速比。

關(guān)鍵詞： 數(shù)據(jù)挖掘； 樸素貝葉斯； 動態(tài)調(diào)度； 并行計算

中圖分類號： TN911?34； TM417 文獻標識碼： A 文章編號： 1004?373X（2016）15?0156?04

Abstract： In comparison with other classification algorithms， the naive Bayes algorithm is suitable for parallel improvement. The single machine classification algorithm is unsuitable for the large?scale data processing， however the occurrence of cloud computing dynamic scheduling brings the hope for big data processing. The parallel computing improvement algorithm is used to enhance the classification speed. The algorithm was improved correspondingly in combination with the easily parallel characteristic of naive Bayes algorithm. The performance contrast experiments were performed on single machine serial mode， Hadoop， Spark and CUDA platform. It is verified that the paralleled classification algorithm has good speed?up ratio.

Keywords： data mining； naive Bayes； dynamic scheduling； parallel computing

0 引 言

傳統(tǒng)的基于單機的文本處理方法，在存儲容量和處理速度上都遇到了瓶頸，如何處理海量數(shù)據(jù)是一個重要問題。云計算平臺動態(tài)調(diào)度提供的海量數(shù)據(jù)的處理能力在文本數(shù)據(jù)挖掘領(lǐng)域中是非常有效的方案，它能體現(xiàn)出對海量數(shù)據(jù)的并行計算優(yōu)勢。因此，文本數(shù)據(jù)挖掘領(lǐng)域的眾多研究者將研究重心轉(zhuǎn)移到傳統(tǒng)文本數(shù)據(jù)挖掘算法的并行化研究之中以提高海量數(shù)據(jù)的處理能力。

本文研究基于樸素貝葉斯算法的海量中文微博的情感分類以及算法的并行化。通過有效的情感特征識別方法提取出中文微博的情感特征，在這些特征的基礎上對微博進行情感分類，致力于在精度、效率上提高。對微博情感分類技術(shù)的研究集中于以下幾個方面：設計實現(xiàn)海量微博情感分析系統(tǒng)、設計基于樸素貝葉斯的微博情感分類模塊以及在大數(shù)據(jù)下的算法并行化研究等。最后，將其推廣到集群模式下進行實驗分析，用開源云計算平臺Hadoop框架和下一代云計算大數(shù)據(jù)核心技術(shù)Spark以及通過GPU下CUDA的編程技術(shù)提高文本分類效率和性能?；趧討B(tài)調(diào)度改變算法的編程模型，實現(xiàn)算法預期的并行性能優(yōu)化，解決了海量微博數(shù)據(jù)的情感分類問題。

1 微博情感數(shù)據(jù)挖掘分類模塊

情感數(shù)據(jù)挖掘模塊包括：微博數(shù)據(jù)處理、特征計算和分類器模塊。微博數(shù)據(jù)處理包括數(shù)據(jù)獲取，微博預處理；特征計算模塊包括特征提取、構(gòu)建向量空間模型；分類器模塊包括分類器、結(jié)果評估。整體的研究結(jié)構(gòu)圖如圖1所示。

1.1 微博數(shù)據(jù)處理模塊

微博數(shù)據(jù)處理模塊包括：數(shù)據(jù)獲取和微博文本預處理。

（1） 實驗中訓練集樣本和測試集樣本來源于互聯(lián)網(wǎng)，是由實驗室根據(jù)新浪微博網(wǎng)站API和網(wǎng)絡爬蟲獲取。由于獲取的微博中包含的話題標簽與句子的情感極性沒有必然的聯(lián)系，為了不影響最終的分類結(jié)果，首先要將微博文本中的話題標簽去掉，只留下文本中的主體部分。同時還應該做以下幾項工作：微博文本規(guī)則化處理，統(tǒng)計所選取微博的條數(shù)，提取并去除話題標簽，按照積極性和消極性把句子分成兩類。微博文本的規(guī)則化處理目的是減少分詞時可能引起的誤差，其中包括把英文字符統(tǒng)一成大寫，多個標點符號重復出現(xiàn)轉(zhuǎn)化為一個標點符號只出現(xiàn)一次，全角符號轉(zhuǎn)化為半角符號，所有不規(guī)范的省略號轉(zhuǎn)化為規(guī)則的省略號等。

（2） 微博文本預處理模塊主要是基于一些自然語言處理方法實現(xiàn)的，主要包括中文微博分詞、去除停用詞等。主要功能包括：中文分詞、詞性標注、命名實體識別、用戶詞典功能；它支持多種編碼；支持微博分詞、新詞發(fā)現(xiàn)與關(guān)鍵詞提取。由于中文微博語言包含了很多口語化、非正式的用語以及一些簡寫和縮寫等，所以自動分析的效果可能會差一點。停用詞包括助詞、虛詞、嘆詞和標點符號（本次包含），在去除停用詞時需要將這些詞語都去掉。

文章中把中文分詞和停用詞放到了一起，首先調(diào)用NLPIR漢語分詞系統(tǒng)中的NLPIR.NLPIR_ParagraphProcess（）函數(shù)對文本進行分詞，并保存到String類型的數(shù)組中，然后讀取停用詞表中的數(shù)據(jù)，也存入到String類型的數(shù)組中。最后把分詞的結(jié)果和停用詞表數(shù)組進行一一比對，找出其中的停用詞，并從數(shù)組中刪除掉。最后得出String類型的分詞結(jié)果數(shù)組以行存儲，每行就可以看作是一篇文檔的向量。

1.2 特征計算模塊

通過上一個模塊的處理之后，形成了文檔以詞項為元素的向量，特征提取就是要從已經(jīng)形成的文本向量中抽取具有明顯情感傾向和能說明該條微博主題的詞匯作為特征詞。經(jīng)過二次抽取之后形成的文本向量基本上就可以作為用于分類器中訓練或測試數(shù)據(jù)的文本向量了。接著對向量進行進一步處理，轉(zhuǎn)化為計算機能識別的表示模型，即向量空間模型。轉(zhuǎn)化時需要對文檔進行遍歷，統(tǒng)計每個詞項的詞頻。最后對每一個類別進行整合，所形成的就是該類別的類別矩陣，在進行數(shù)據(jù)集訓練時，利用TF?IDF計算出每個詞項在文檔中的權(quán)重，構(gòu)成帶權(quán)重的類別矩陣。進行分類器測試時，利用分類器對文檔進行分類。

2 基于NB的情感分類數(shù)據(jù)并行研究實現(xiàn)

2.1 NB算法模型

樸素貝葉斯的思想基礎是：利用類別的先驗概率以及樣本的數(shù)據(jù)信息計算未知類別的文本屬于某一確定類別的后驗概率。樸素貝葉斯微博情感分類的任務就是將待分類微博[t]表示成為屬于某一類的概率。即設該[t]的特征向量[（ω1，ω2，…，ωn）]歸類到與其關(guān)聯(lián)最緊密的[M]個分類[C1，C2，…，CM]中去，由于情感分類是正負兩元分類，故[M=2。]通過求解向量[（ω1，ω2，…，ωn）]屬于給定類別[Ci]的概率值[Pi，]其中[Pi]為[（ω1，ω2，…，ωn）]屬于[Ci]的概率，則取最大后驗概率[max（P1，P2）]對應的類別就是文本[（ω1，ω2，…，ωn）]所屬的類別。

2.2 算法并行化可行性研究

當數(shù)據(jù)的規(guī)模不斷增多后，不論是訓練集的學習過程，還是文檔統(tǒng)計分類工作，都需要占用相當大的內(nèi)存與計算資源。由于串行計算導致訓練集生成速度緩慢，機器學習效率低下，因此單機顯然不能勝任海量數(shù)據(jù)。分析上述樸素貝葉斯算法條件獨立性假設的特點，可以發(fā)現(xiàn)無論是分類模型的生成過程，還是測試集的分類過程，都是由許多組獨立的計算疊加而成。因此，其算法本身就具有并行計算的可行性。綜上所述，并行化后的樸素貝葉斯分類流程，如圖2所示。

由并行化后的樸素貝葉斯分類流程可知，訓練階段內(nèi)的每一篇微博文本的計算處理過程都是相同的、獨立的。因此將一篇接一篇的串行計算過程并行化處理，把訓練集數(shù)據(jù)分割切片后，由多個并行計算節(jié)點分別對訓練微博進行分詞、統(tǒng)計等計算?？梢愿鶕?jù)具體計算單元數(shù)目的情況適當選擇數(shù)據(jù)分割的大小。在測試階段的工作是計算微博的每個特征詞屬于各個類的概率并且疊加，得到文檔屬于正、負類別的概率，最終取最大值作為分類的結(jié)果。樸素貝葉斯分類過程中最耗時的是需要計算大量的[PωjCi，]而各個特征詞的計算過程是相互獨立的。因此，將特征詞統(tǒng)計過程改造成在各個節(jié)點并行完成各個部分的[PωjCi]計算，最后合并輸出結(jié)果到分類結(jié)果中。

2.3 Spark下的算法并行化實現(xiàn)

結(jié)合SparkMLlib設計的接口對原有MR程序改造，考慮SparkMLlib良好的可擴展性和基于面向?qū)ο蠓庋b，分析和設計了當前平臺中各個算法模塊的組織關(guān)系。故繼承SparkMLlib接口原有的ClassificationModel，設計一個便捷的內(nèi)存數(shù)據(jù)模型NaiveBayesModel用于評估和預測，提供標簽類別先驗概率和特征屬性在指定類別下出現(xiàn)的條件概率。本次樸素貝葉斯算法主要考慮其并行化后速度上的提升，算法的并行策略主要是計算類別的先驗概率以及特征的條件概率。基于分類算法的并行思路，任務同樣分為訓練階段和測試階段，Spark下的分類流程，如圖3所示。

（1） 加載訓練集到Spark空間，則要創(chuàng)建彈性分布式數(shù)據(jù)集RDD。本文采用外部存儲系統(tǒng)上的數(shù)據(jù)集創(chuàng)建RDD。從Hadoop的任何存儲源中構(gòu)建出RDD，包括本地文件系統(tǒng)，HDFS，HBase等。Spark支持TEXTFILE，SEQUENCEFILE以及其他任何HadoopInputFormat，為使用上一節(jié)預處理后的數(shù)據(jù)提供便利。算法的訓練集和測試集的輸入是（Label，key：value）的序?qū)?，使用SparkContext提供的textFile（）接口，MLlib內(nèi)部會轉(zhuǎn)換成RDD[LabelPoint]類型。LabelPoint對情感分類來說，一個標簽或為0（負向）或為1（正向）。

（2） 訓練階段，包括統(tǒng)計詞頻TF和計算權(quán)重TF?IDF。為了擴展性將TF和IDF分開，TF?IDF是TF和IDF簡單相乘。統(tǒng)計詞頻使用散列技巧，基于映射索引值計算實現(xiàn)，包括運用一個哈希函數(shù)將原始特征映射到一個特征索引值。這種方法避免計算全局“詞?索引（term?to?index）”映射，而在海量的微博語料中計算全局“詞?索引”的代價非常高。由于這種方法會出現(xiàn)潛在的哈希值沖突（不同原始特征被映射到同一個哈希值，從而變成同一個詞），通過增加目標特征的維數(shù)（哈希表中散列桶的數(shù)量）來降低這種沖突概率。訓練階段完成上述步驟后，設計整合數(shù)據(jù)獲得模型。訓練階段得到NaiveBayesModel模型，包括標簽類別先驗概率[pi，]特征屬性在指定類別下出現(xiàn)的條件概率[θ]。

（3） 樸素貝葉斯分類器測試階段，輸入的測試數(shù)據(jù)集轉(zhuǎn)化為TF?IDF形式的特征用來文本分類，對兩邊取對數(shù)作為實現(xiàn)，加法的計算效率比乘法更高，同樣的結(jié)果返回后驗概率最大的那個類別。

2.4 基于GPU的算法并行實現(xiàn)

在訓練過程之前，需要把生成的預處理后的微博數(shù)據(jù)加載到內(nèi)存。所有的文檔加載到一個矩陣，其中矩陣的一行表示屬于一個分類下的一篇文檔中的全部特征詞。如[ωij中][i]代表分類的標號，[j]代表不同的特征詞編號。

為了方便詞頻匯總，使用散列方法，基于映射索引值計算來實現(xiàn)，運用一個哈希函數(shù)將原始特征映射到一個特征索引值。得到一個惟一特征詞的向量，用來統(tǒng)一表示微博文本的特征向量。在保存分詞處理結(jié)果時，保存該詞在分詞詞典中的下標。根據(jù)分詞詞典的詞數(shù)建立一個索引表，并用0值初始化。

在海量微博數(shù)據(jù)樸素貝葉斯分類中，由于涉及到的數(shù)據(jù)量非常龐大并且數(shù)據(jù)類型種類繁多，為了實現(xiàn)高性能算法，選擇高效的數(shù)據(jù)表示形式起著至關(guān)重要的作用。主要目標是算法在GPU取得優(yōu)異的并行性能，但是當前圖形處理硬件受到嚴重的內(nèi)存限制，盡管實驗設備的顯存有5 GB，但仍然存在數(shù)據(jù)不能全部加載到顯存的可能，所以采用一個密集的數(shù)據(jù)結(jié)構(gòu)：按照特征詞進行索引來表示文檔集合。利用兩個Vector，即TermIndexVector（TIV）和DocTermVector（DIV），DTV存儲了每條微博中出現(xiàn)過的特征詞[wj。]TIV是DTV中特征詞的索引用來區(qū)別DTV中的不同微博文檔。故TIV的每個位置指向DTV中每篇微博的首位特征詞[wj。]

3 實驗與結(jié)果分析

3.1 實驗過程

實驗一，在單機上利用樸素貝葉斯分類方法對采集的微博小規(guī)模實驗數(shù)據(jù)集進行串行的分類實驗，驗證基于樸素貝葉斯微博情感分類方法的精度效果。本次原始語料經(jīng)過預處理得到降噪、分詞微博文本。在實驗中，通過人工篩選的方式，根據(jù)之前的研究內(nèi)容分別使用不同的分類器和多種特征以及不同特征權(quán)重計算方式的組合進行實驗，選擇效果較好的分類器和特征。

實驗二，利用分布式爬蟲并行爬取大規(guī)模數(shù)據(jù)集，采用上文設計的并行算法進行并行化的分類實驗，驗證分類方法的加速效果。依賴云計算的工作流調(diào)度系統(tǒng)配置運行本實驗的任務節(jié)點。

首先，本實驗是數(shù)據(jù)獲取，start節(jié)點開始后在基礎庫中獲取微博話題的URL，然后使用網(wǎng)絡爬蟲和API獲取微博數(shù)據(jù)集。其次，在weibo_content_data節(jié)點將微博數(shù)據(jù)處理劃分為訓練集和測試集，此時應當記錄節(jié)點開始運行的時間[T0。]然后，任務有3個大分支，分別是樸素貝葉斯在Hadoop，Spark以及CUDA三個并行計算平臺上運行，分別運行完test[?]naiveBayes節(jié)點的時間為[TH，TS，TC，]此時間差用于實驗計算加速比與運行性能等。最后，分類結(jié)果匯總到sentiment_report_storage節(jié)點中，將分類的結(jié)果與中間結(jié)果數(shù)據(jù)存儲到結(jié)果展現(xiàn)層的關(guān)系型數(shù)據(jù)庫中，供數(shù)據(jù)挖掘演示平臺Vdata系統(tǒng)使用。文章中為每個任務節(jié)點編寫shell腳本，shell腳本中執(zhí)行jar包等處理過程，從中向集群或GPU提交相應任務。

3.2 運行性能對比

在不同的問題規(guī)模上對比單機串行，CUDA，Hadoop與Spark的不同版本實現(xiàn)的運行效率。其中，單機串行算法運行在單臺Linux服務器上，Hadoop與Spark版本的實現(xiàn)未做深度調(diào)優(yōu)處理。數(shù)據(jù)集方面，本文使用了微博50 KB，500 KB以及5 MB數(shù)據(jù)集，其中分別包含了5萬行，50萬行和500萬行微博文本。這些不同大小的數(shù)據(jù)集可以很好地測試樸素貝葉斯算法并行的實際性能。于是依次使用這三個數(shù)據(jù)集在實驗集群上，而且特征維數(shù)取值3 500，進行性能測試。對比運行時間，如圖4所示。

從圖4可以看出，當數(shù)據(jù)集較小時，單機算法計算性能并沒有明顯劣勢；但當問題規(guī)模增大時，單機算法則表現(xiàn)越來越差，運行時間成倍增加，若數(shù)據(jù)量級持續(xù)增長可能會超過機器可運行范圍。而在GPU平臺上，分類運行時間則緩慢增加，這是因為在單機上，影響程序運行時間的最大因素是分詞匯總模塊，當文本數(shù)據(jù)量增大時，該模塊需處理的時間也隨之大大增加。在GPU平臺上，由于可使用更多的線程塊來處理增加的數(shù)據(jù)量，因而程序運行時間的增加更多來自于磁盤I/O操作次數(shù)的增加。在Spark與Hadoop上實現(xiàn)的算法仍然可以明顯地反映一個問題，處理的數(shù)據(jù)規(guī)模越小，其處理單位數(shù)據(jù)的耗時越長。隨著數(shù)據(jù)量的增大，所占用的運行時間比較平穩(wěn)，這與他們框架內(nèi)部實現(xiàn)機制有關(guān)：輸入數(shù)據(jù)在HDFS被分成若干塊后，得到的中間結(jié)果保存到HDFS或者內(nèi)存中。當數(shù)據(jù)規(guī)模較小時，大部分時間都消耗在進程的初始化以及HDFS讀寫中；而對于大數(shù)據(jù)集，初始化開銷以及HDFS讀寫開銷只是總開銷中很小的部分。但是，Spark仍然能表現(xiàn)出很好的內(nèi)存計算優(yōu)勢，算法在Spark實現(xiàn)的運行時間上大量減少，極大地提高了運行效率，而其中處理5 MB數(shù)據(jù)集的任務運行總時間顯著減少。

4 結(jié) 論

本文提出了海量數(shù)據(jù)情感分析系統(tǒng)，可適應不同機器學習與數(shù)據(jù)挖掘算法處理場景的任務。介紹了系統(tǒng)框架思想與設計實現(xiàn)思路，并詳細介紹了2個子系統(tǒng)，即面向云計算的工作流調(diào)度、Vdata系統(tǒng)，隨后針對本文研究微博情感分類模塊進行重點分析，有效地闡明分類算法并行化研究在海量微博情感分析系統(tǒng)的重要地位。

參考文獻

[1] 黃萱菁，張奇，吳苑斌.文本情感傾向分析[J].中文信息學報，2012，25（6）：118?126.

[2] 向小軍，高陽，商琳，等.基于Hadoop平臺的海量文本分類的并行化[J].計算機科學，2011，38（10）：184?188.

[3] 江小平，李成華，向文，等.云計算環(huán)境下樸素貝葉斯文本分類算法的實現(xiàn)[J].計算機應用，2011，31（9）：2551?2554.

[4] 李海生.一種熱點話題算法在微博輿情系統(tǒng)中的應用[J].現(xiàn)代電子技術(shù)，2015，38（6）：44?46.

[5] HUANG L Q， LIN L Q， LIU Y H. Algorithm of text categorization based on cloud computing [J]. Applied mechanic sand materials， 2013， 311： 158?163.

[6] HARVEY J P. GPU acceleration of object classification algorithms using NVIDIA CUDA [R]. New York： Wallace Memo?rial Library， 2009.

[7] JOSHI A， BALAMURALI A R， BHATTACHARYYA P， et al. C?Feel?It： a sentiment analyzer for micro?blogs [C]// Procee?dings of 2011 Annual Meeting of the Association for Computational Linguistics： Human Language Technologies. Stroudsburg： ACM， 2011： 127?132.

[8] MUKHERJEE S， BHATTACHARYYA P. Feature specific sentiment analysis for product reviews [C]// Proceedings of 2012 13th International Conference on Computational Linguistics and Intelligent Text Processing. New Delhi： Springer Berlin Heidelberg， 2012： 475?487.