1. Na?ve Bayes算法介紹

Na?ve Bayes是一個簡單有效的分類算法，已經(jīng)得到廣泛使用。本文討論了海量數(shù)據(jù)（TB級）下Na?ve Bayes算法的實現(xiàn)方法，并給出了Hadoop上的實現(xiàn)方案。

2. Na?ve Bayes算法介紹

樸素貝葉斯分類器基于一個簡單的假定: 在給定目標(biāo)值時屬性值之間相互獨(dú)立, 即特征對于給定類的影響?yīng)毩⒂谄渌卣鳌＠迷摷僭O(shè),文檔d 屬于類c 的概率可以表示為:

3. Na?ve Bayes算法在Hadoop上實現(xiàn)

分兩個階段進(jìn)行，首先是訓(xùn)練獲取分類器，然后是預(yù)測。

（1） 訓(xùn)練

訓(xùn)練階段要計算兩種概率：[1] 每種類別的先驗概率 [2] 每個term（單詞）在每個類別中得條件概率。

[1] 計算類別的先驗概率

由一個Hadoop Job實現(xiàn)，偽代碼如下：

該作業(yè)主要統(tǒng)計了每種類別文檔的總數(shù)目，具體概率的計算放在了后面。假設(shè)該作業(yè)計算得到的數(shù)據(jù)匯總在了文件dict1.txt中。

[2] 計算term的條件概率

由一個Hadoop job實現(xiàn)，偽代碼如下：

其中，c表示種類，w表示word，該作業(yè)只統(tǒng)計了每個<c,w>對出現(xiàn)的總次數(shù)，具體條件概率計算放在了后面。假設(shè)該作業(yè)得到的數(shù)據(jù)匯總在文件dict2.txt中。

（2） 預(yù)測

預(yù)測時，需要把文件dict1.txt和dict2.txt作為字典加載到內(nèi)存中，一般而言，dict1.txt很小，而dict2.txt很大，如種類數(shù)是100，term總數(shù)為10000,0000，則dict2需要保存的記錄總數(shù)為100*10000 0000=10^10。為了解決該問題，提出以下解決方案：

（1）將種類分片存儲到多個文件中。比如，共有100個種類，每10個種類為一組存放到10個字典中（即：某個字典只保存與某10個種類相關(guān)的<c,w>對，這個可以通過將同一種類的<c,w>將給相同reduce task處理做到），分批計算。

（2）dict2.txt中實際上存放的是一個稀疏矩陣，稀疏矩陣很適合用HashTable存儲，在C++中，很容易想到STL map，實際上，這種方案非常浪費(fèi)內(nèi)存。STL map是紅黑樹，每個節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如下：

1 2 3 4 5 6 7 8 9

struct node { ??T* data; // key +value=4+4=8 ??bool color,//ignore ??struct node *father, *left, *right; }

每個節(jié)點(diǎn)大約需要8+4*3=20個字節(jié)。為了改進(jìn)該方案，采用vector+二分查找的方案：

首先，將<c,w>對壓縮到一個unsigned int中，如，高7位表示種類（事先對種類進(jìn)行編號，能表示2^7=128個種類），低25位表示term編號（最大可有33554432個term）；

1 2 3 4 5

unsigned int FormatToCombinedNumber(unsigned int high, unsigned int low) { ??return ((high & 0x7f) << 24) + (low & 0xffffff); }

然后，將（<c,w>， 次數(shù)）保存到vector中，并事先按照<c,w>（實際上是一個unsigned int）排序。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

vector<KeyValue> term_prb; class KeyValue { ?public: ??void Set(unsigned int t, float w) { ???term = t; ???weight = w; ??} ??unsigned int term; ??float weight; };

最后，當(dāng)查詢一個<c,w>出現(xiàn)的概率時，只需拼湊<c,w>對應(yīng)的unsigned int，然后在vector中二分查找即可。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

struct TermCompare : public std::binary_function<KeyValue, KeyValue, bool> { ?public: ??bool operator() (const KeyValue &o, const unsigned int term) const { ???return o.term < term; ??} ??bool operator() (const unsigned int term, const KeyValue &o) const { ???return term < o.term; ??} }; float TermFind(unsigned int key) { ?vector<KeyValue>::iterator index = ?lower_bound(term_prb.begin(), term_prb.end(), key, TermCompare()); ?if(index == term_prb.end() || index->term > key ) { ??return default_term_prb; ?} else { ??return index->weight; ?} }

Hadoop程序首先要加載詞典dict1.txt和dict2.txt，并將之分別保存到map和vector兩種數(shù)據(jù)結(jié)構(gòu)中，需要注意的是，加載之前需要將對應(yīng)的概率（先驗概率和調(diào)教概率）計算出來，預(yù)測的Hadoop偽代碼如下：

(1) 多輪預(yù)測新doc在每個種類中的概率：

PredcitProbility()

1 2 3 4 5

Map(new_doc): ?for each class in dictionary: ??Emit(doc, class|probility);

該Hadoop作業(yè)可能運(yùn)行多次，主要取決于劃分的字典數(shù)目

(2) 選出最大概率，得到doc的類別

PredcitProbilityCombiner():

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

Map(doc): ?Emit(doc, class|probility); //直接輸出(1)的結(jié)果，讓reducer選擇 Reduce(doc): ?max_prb=-MIN ?max_class = 0 ?for each value v（class|probility）: ??if(max_prb < probility) { ???max_prb = probility; ???max_class = class; ??} Emit(doc, max_class);

該作業(yè)的輸入是上一個作業(yè)的所有輸出。

4. 總結(jié)

上面共提到4個Hadoop作業(yè)，分別為：ClassPrior，ConditionalProbility，PredictProbility和PredictProbilityCombiner，它們的關(guān)系如下：

5. 參考資料

(1) 基于MapReduce 的并行貝葉斯分類算法的設(shè)計與實現(xiàn), 丁光.華. 周繼鵬. 周敏

原創(chuàng)文章，轉(zhuǎn)載請注明：?轉(zhuǎn)載自董的博客

本文鏈接地址:?http://dongxicheng.org/data-mining/naive-bayes-in-hadoop/

作者：Dong，作者介紹：http://dongxicheng.org/about/

from:?http://dongxicheng.org/data-mining/naive-bayes-in-hadoop/

總結(jié)

以上是生活随笔為你收集整理的朴素贝叶斯Naïve Bayes分类算法在Hadoop上的实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。