盧龍1,2，王靜宇1，王超3
?。?. 內蒙古科技大學 信息工程學院，內蒙古 包頭 014010；2. 中國北方稀土（集團）
高科技股份有限公司，內蒙古 包頭 014010；3. 中國移動通信集團山東有限公司萊蕪分公司，山東 萊蕪 271100）
摘要：針對傳統貝葉斯分類算法在處理海量數據時存在的運行時間長和分類準確率低等問題，在對傳統的貝葉斯分類算法和云計算進行了深入研究后，提出了面向云計算環境的基于 MapReduce模型的樸素貝葉斯分類算法。該算法實現了樸素貝葉斯分類算法的并行化，實現了大規模數據在云計算環境下的集群中進行貝葉斯分類處理。實驗結果證明，該算法具有較高的分類準確率，在運行時間和加速比方面也有很好的效果。
關鍵詞：云計算；樸素貝葉斯算法；MapReduce
中圖分類號：TP393文獻標識碼：ADOI： 10.19358/j.issn.1674-7720.2017.06.003
引用格式：盧龍，王靜宇，王超. 面向云計算的數據挖掘分類算法研究［J］.微型機與應用，2017,36（6）：7-9，12.
0引言
*基金項目：國家自然科學基金項目（61662056,61462069 ）；內蒙古自然科學基金（2015MS0622，2016MS0609）隨著云計算、大數據等信息技術的快速發展，數據量呈現出了爆炸式的增長，數量級別從原來的MB級別迅猛增長到TB級別甚至是PB級別，這一嚴峻問題的出現給數據挖掘技術帶來了前所未有的巨大挑戰，海量數據的積累讓人們有更多的數據可以利用，從這些海量數據中提取出對用戶有價值的數據變得尤為重要。傳統的數據挖掘算法通常要做的處理是先把數據從外存讀入內存，然后進行分析處理，但是現如今數據量增大到驚人的級別時，由于對CPU、內存等資源的急劇消耗，導致算法執行時間顯著增加，算法的性能大幅度下降，根本無法達到用戶的預期結果。在對海量數據進行挖掘處理時，要想獲得理想結果，采用的數據挖掘算法必須要呈現出良好的可伸縮性和可并行性。云計算可以提供一種用于實現并行計算的模型［1］，它將大規模數據的存儲和計算能力均勻地分散到集群中，這些集群是由若干機器構成的，由許多的廉價機器搭建，在很大程度上降低了成本。云計算平臺所具有的高速處理海量數據和計算海量數據這兩大優勢，更是為提高數據挖掘算法的效率和準確性提供了有力支撐，使傳統的數據挖掘算法面臨的難題得以解決。
數據分類作為一種重要的數據分析形式，常出現在數據挖掘領域中。目前比較常用的分類算法主要有：樸素貝葉斯分類算法、決策樹分類算法、人工神經網絡等。其中，在機器學習和數據挖掘研究領域，樸素貝葉斯分類算法是比較重要和常用的數據處理方法之一。樸素貝葉斯分類算法在簡單、高效、分類效果穩定這個三個方面優勢比較明顯，它還具有牢固的理論基礎，在實際應用中得到廣泛的重視和應用。近年來，各國學者對貝葉斯分類方法展開了深入研究。
文獻［2］提出了一種基于Kmeans的貝葉斯分類算法，該算法主要思想是利用Kmeans聚類算法對原始數據集進行聚類分析，計算缺失數據子集中的每條記錄與k個簇重心之間的相似度，把該記錄分配到與其相似度最大的一個簇, 用該簇中相應的屬性均值來填充記錄的缺失值，再用樸素貝葉斯分類算法對處理后的數據集進行分類，實驗表明，在分類準確率上，與傳統樸素貝葉斯分類算法相比，該算法分類準確率較高。文獻［3］是基于Hadoop平臺提出的樸素貝葉斯數據分類算法，該算法對特征選擇方法進行了改進，并利用MapReduce編程模型實現了樸素貝葉斯并行分類算法。實驗結果表明，該算法不僅提高了分類的正確率，而且在訓練和測試集規模較大時體現出了很好的加速比，性能方面也有很大的提高。文獻［4］則是通過對Hadoop基礎平臺MapReduce并行化編程模型進行深入研究后，對傳統的樸素貝葉斯分類算法進行了MapReduce并行化改進，用以提高樸素貝葉斯分類算法對大規模數據處理的能力和計算效率。實驗表明: 改進后樸素貝葉斯分類算法在加速比和對中文網頁進行分類識別率上都有很大的改進。
本文在對傳統的貝葉斯分類算法和云計算相關技術深入研究后，提出了一種面向云計算并基于 MapReduce模型的貝葉斯分類算法，利用提出的面向云計算的貝葉斯分類方法，對大規模數據在云計算環境下的集群中進行貝葉斯分類處理，通過實驗證明該方法具有較高的執行效率。通過對大規模數據在云計算環境下的集群中進行貝葉斯分類處理，并對比大規模數據在不同節點上的運行時間和加速比可知，本文提出的算法具有較高的執行效率，平均分類正確率顯著提高，適合用于海量數據的快速離散化處理。
1相關工作
1.1MapReduce編程模型
MapReduce是一種并行編程模型［5］，采用的是主（Master）/從（Slave）結構，在處理大規模數據時，將其分塊后，分配到由普通機器組成的超大集群上并發執行。MapReduce編程模型主要分為兩個階段：Map和Reduce。Map階段指的是映射，Reduce指的是規約；Map函數處理數據的形式是一個給定的鍵值對<key1，value1>，處理后生成另一個鍵值對< key2，value2>。隨后MapReduce模型將Map階段輸出的相同的key2鍵值進行合并，形成一個新的鍵值對<key2，lsit(v2)>。Reduce函數則處理Map階段合并的鍵值對<key2，lsit(v2)>，處理后形成一個形似<key3，value3>的鍵值對，并將這個鍵值對寫入文件。
1.2樸素貝葉斯數據分類算法
樸素貝葉斯算法（NBC) 是簡單常用的統計學分類算法［6］，該算法使用概率統計領域的知識對文本數據進行分類。它具體描述為：設樣本數據集D={D1,D2,…,Dn},對于某一特定c∈C，數據集有n個屬性A1,A2,…,An，測試樣本x={a1,a2,…,an}∈X，則進行分類時，樸素貝葉斯分類器對每個類c計算后驗概率：p（x|c）， 為使p(x|c)估算有效，樸素貝葉斯分類算法通常假設數據各屬性之間是相互獨立的。則類條件概率p(x|c)表示為：
p(x|c)=∏ni=1p(ai|c)=p(a1|c)p(a2|c)…p(an|c)
結合貝葉斯公式，樸素貝葉斯分類器對每個類c計算后驗概率：
由于p(x)對所有的c是固定不變的，因此只要找出p(c)∏di=1p(ai|c)最大類，這個類就是未分類x元組所屬的類。
樸素貝葉斯分類算法包括兩個過程：訓練過程和測試過程［7］。訓練過程是該算法消耗系統資源最集中的部分，如果將此過程帶來的壓力分解到一群機器上，那么在一定程度上會解決系統資源消耗嚴重的問題，而MapReduce并行編程模型完全可以實現此想法。
2面向云計算的貝葉斯分類算法
隨著信息技術的快速發展以及互聯網的迅速普及流行，網絡中的有價值數據越來越豐富，數據量也以指數的速度快速增長，這就給傳統的數據挖掘算法帶來了許多挑戰和難題。為此需要通過對傳統貝葉斯分類挖掘算法原理進行分析，尋找算法可并行的點，將傳統的貝葉斯分類算法［7］應用到云計算環境下，利用MapReduce編程模式，實現傳統貝葉斯分類算法的并行化，改變傳統算法在單機模式上的局限，最終解決對海量數據訓練和測試過程計算耗時長和分類正確率低的難題。
2.1貝葉斯分類算法的可并行性
貝葉斯分類算法的訓練過程是該算法消耗系統資源最集中的過程［8］，一般在處理一個或多個大文件時，順序讀寫和計算會耗費很多系統資源，并且效率也不高。用戶在處理大量數據時，數據文件間一般是獨立的，可以借助數據分塊的思想來處理。MapReduce并行編程模型完全可以實現此想法，這可以在很大程度上提高算法的運行速度和分類的準確率。
2.2面向云計算的貝葉斯分類算法設計
利用Hadoop分布式系統基礎架構中的HDFS存儲能力和MapReduce的計算能力，實現對樸素貝葉斯分類算法的并行運行。貝葉斯的并行運行基本思路是［9］：由于訓練數據集中數據之間并無關聯，可以把數據集分塊，這讓傳統的串行算法讀取訓練數據集的過程可以在多臺機器上并行實現。在這個基礎上，Hadoop分布式系統的處理機制對切塊的數據分別處理。本文通過以下兩部分實現樸素貝葉斯分類算法的并行化，關鍵是將MapReduce模型引入其中：
第一部分：MapReduce在處理大數據集時，Mapper依照默認的輸入格式讀取大規模的文本數據，輸入數據后再利用分詞開源庫對文本數據進行分詞處理［10］，將近義詞等去除，從而降低其特征維度，這個過程中還要建立相應的子目錄，作為核心關鍵詞的計算。為了實現篩選功能，在統計核心關鍵詞時需要增加一個過濾器。按照<word，class>的形式輸出，這一步的輸出作為下一步操作的輸入，Combiner將一類的詞歸集在一起，計算出同一個Mapper的頻率和，再把結果保存在 HDFS中。過程如圖1所示。
第二部分：貝葉斯分類文本分類算法利用MapReduce模型進行并行實現，分類模型先由Mapper加載，然后將數據拆分成多個模塊，分配給各個節點，通過模型向量計算出各個節點的概率和，以<file，<Probability，class> >的形式輸出，作為Mapper Task的輸入，其中file代表文件名，Probability表示條件概率，class代表類別。Combiner將通過一個文件的特征集進行集中處理，完成Reducer任務，將全部條件概率計算出，得到先驗概率后將數據保存在HDFS。過程如圖2所示。
樸素貝葉斯分類算法并行實現后，算法中最耗時的運算被分布到集群中多個節點上，這在很大一定程度上減輕了一臺機器的計算壓力。假設訓練集有m 個類別，n個特征項，待分類樣本共有k個特征項，如果每個節點平均完成t個任務，則計算速度提高了t倍，復雜度為O(m*n/k)。
3實驗與結果分析
3.1實驗平臺與實驗數據
實驗平臺集群共4臺計算機，搭建4個節點，軟件環境為：操作系統：CentOS 6 ，JDK版本：1.7 ，Hadoop版本：2.5.2 ，Mahout版本：0.10.1。搭建好Hadoop平臺后開始運用Mahout實現本文提出的算法。Mahout是Hadoop的一種高級應用［11］，運行Mahout需要提前安裝好Hadoop。Hadoop安裝完成，下面就開始運用Mahout運行本文提出的面向云計算的貝葉斯分類算法。實驗數據來源于UCI中的20-Newsgroups。
3.2實驗結果分析
本實驗中，選取的文檔集分別是20Newsgroups中的motorcycle，electronics，religion，baseball，politics。實驗的分類準確性結果如表1所示。
從表1中可以得出，本實驗的平均正確率為93.54%，比傳統的串行算法提高了0.97%。
實驗還對改進的貝葉斯分類算法分別從運行時間和加速比進行了測試。在1個、2個、3個、4個節點上分別從運行時間和加速比方面對實驗結果進行分析。從圖3可以看出，隨著節點數的增加，分類的運行時間顯著縮短。同時，基于 MapReduce模型的貝葉斯分類算法具有比較良好的加速比，實際加速比與理想的線性加速比十分接近，能夠實現快速的分類，并且隨著節點的增加，算法的加速比增長率逐漸變慢，這是因為Hadoop平臺下節點之間的通信時間花費逐漸變大，同時實驗選擇的數據量越大，其算法的加速比增加越接近線性，如圖4所示。
4結束語
傳統的貝葉斯分類分類算法應用廣泛，但其也存在運行時間長和分類準確率低等問題，云計算環境下，基于 MapReduce模型的貝葉斯分類算法可以很好地解決此類
問題，縮短數據處理時間和提高數據處理的分類準確率。實驗結果表明，隨著節點的增加，并行化的貝葉斯分類算法的數據處理的運行時間在不斷下降，實際加速比與理想的線性加速比十分接近，該算法具有較高的執行效率，平均分類正確率為93.54%，比傳統的串行算法提高了0.97%。因此，并行化的貝葉斯分類算法在處理海量數據時具有現實意義。
參考文獻
?。?］ 馮登國, 張敏, 張妍,等. 云計算安全研究［J］. 軟件學報, 2011, 22(1):7183.
?。?］ 張亞萍,胡學鋼. 基于Kmeans的樸素貝葉斯分類算法的研究［J］. 計算機技術與發展,2007,17（11）:33-35.
?。?］ 張紅蕊, 張永, 于靜雯. 云計算環境下基于樸素貝葉斯的數據分類［J］. 計算機應用與軟件, 2015，32(3)：27-30.
?。?］ 江小平, 李成華, 向文,等. 云計算環境下樸素貝葉斯文本分類算法的實現［J］. 計算機應用, 2011, 31(9)：2551-2554.
?。?］ DEAN J, GHEMAWAT S. MapReduce: simplified data processing on large clusters［C］. Proceedings of Operating Systems Design and Implementation (OSDI）, 2004:107-113.
?。?］ 鄭煒, 沈文, 張英鵬. 基于改進樸素貝葉斯算法的垃圾郵件過濾器的研究［J］. 西北工業大學學報, 2010, 28(4):622-627.
?。?］ 張增偉, 吳萍. 基于樸素貝葉斯算法的改進遺傳算法分類研究［J］. 計算機工程與設計, 2012, 33(2):750-753.
［8］ 李軍華. 云計算及若干數據挖掘算法的MapReduce化研究［D］. 成都：電子科技大學，2010.
?。?］ 蔣婉婷, 孫蕾, 錢江. 基于Hadoop的樸素貝葉斯算法在中文微博情感分類中的研究與應用［J］. 計算機應用與軟件, 2015, 32(7)：60-62.
?。?0］ 向小軍, 高陽, 商琳,等. 基于Hadoop平臺的海量文本分類的并行化［J］. 計算機科學, 2011, 38(10)：184-188.
?。?1］ RUI M E, RUI P, RONG C. K-means clustering in the CloudA Mahout test［C］.IEEE Workshops of International Conference on Advanced Information networking and Applications,IEEE, 2011:514--519.