一種基于動態調度的數據挖掘并行算法

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

關鍵詞： 數據挖掘； 樸素貝葉斯； 動態調度； 并行計算

中圖分類號： 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 引 言

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

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

1 微博情感數據挖掘分類模塊

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

1.1 微博數據處理模塊

微博數據處理模塊包括：數據獲取和微博文本預處理。

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

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

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

1.2 特征計算模塊

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

2 基于NB的情感分類數據并行研究實現

2.1 NB算法模型

樸素貝葉斯的思想基礎是：利用類別的先驗概率以及樣本的數據信息計算未知類別的文本屬于某一確定類別的后驗概率。樸素貝葉斯微博情感分類的任務就是將待分類微博[t]表示成為屬于某一類的概率。即設該[t]的特征向量[（ω1，ω2，…，ω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 算法并行化可行性研究

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

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

2.3 Spark下的算法并行化實現

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

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

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

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

2.4 基于GPU的算法并行實現

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

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

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

3 實驗與結果分析

3.1 實驗過程

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

實驗二，利用分布式爬蟲并行爬取大規模數據集，采用上文設計的并行算法進行并行化的分類實驗，驗證分類方法的加速效果。依賴云計算的工作流調度系統配置運行本實驗的任務節點。

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

3.2 運行性能對比

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

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

4 結 論

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

參考文獻

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

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

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

[4] 李海生.一種熱點話題算法在微博輿情系統中的應用[J].現代電子技術，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.