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