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