Naïve Bayes分类算法在Hadoop上的实现

1. Naïve Bayes算法介绍

Naïve Bayes是一个简单有效的分类算法，已经得到广泛使用。本文讨论了海量数据（TB级）下Naïve Bayes算法的实现方法，并给出了Hadoop上的实现方案。

2. Naïve Bayes算法介绍

朴素贝叶斯分类器基于一个简单的假定: 在给定目标值时属性值之间相互独立, 即特征对于给定类的影响独立于其它特征。利用该假设,文档d 属于类c 的概率可以表示为:

3. Naïve Bayes算法在Hadoop上实现

分两个阶段进行，首先是训练获取分类器，然后是预测。

（1） 训练

训练阶段要计算两种概率：[1] 每种类别的先验概率 [2] 每个term（单词）在每个类别中得条件概率。

[1] 计算类别的先验概率

由一个Hadoop Job实现，伪代码如下：

该作业主要统计了每种类别文档的总数目，具体概率的计算放在了后面。假设该作业计算得到的数据汇总在了文件dict1.txt中。

[2] 计算term的条件概率

由一个Hadoop job实现，伪代码如下：

其中，c表示种类，w表示word，该作业只统计了每个<c,w>对出现的总次数，具体条件概率计算放在了后面。假设该作业得到的数据汇总在文件dict2.txt中。

（2） 预测

预测时，需要把文件dict1.txt和dict2.txt作为字典加载到内存中，一般而言，dict1.txt很小，而dict2.txt很大，如种类数是100，term总数为10000,0000，则dict2需要保存的记录总数为100*10000 0000=10^10。为了解决该问题，提出以下解决方案：

（1）将种类分片存储到多个文件中。比如，共有100个种类，每10个种类为一组存放到10个字典中（即：某个字典只保存与某10个种类相关的<c,w>对，这个可以通过将同一种类的<c,w>将给相同reduce task处理做到），分批计算。

（2）dict2.txt中实际上存放的是一个稀疏矩阵，稀疏矩阵很适合用HashTable存储，在C++中，很容易想到STL map，实际上，这种方案非常浪费内存。STL map是红黑树，每个节点的数据结构如下：

struct node {

  T* data; // key +value=4+4=8

  bool color,//ignore

  struct node *father, *left, *right;

}

每个节点大约需要8+4*3=20个字节。为了改进该方案，采用vector+二分查找的方案：

首先，将<c,w>对压缩到一个unsigned int中，如，高7位表示种类（事先对种类进行编号，能表示2^7=128个种类），低25位表示term编号（最大可有33554432个term）；

unsigned int FormatToCombinedNumber(unsigned int high, unsigned int low) {

  return ((high & 0x7f) << 24) + (low & 0xffffff);

} 

然后，将（<c,w>， 次数）保存到vector中，并事先按照<c,w>（实际上是一个unsigned int）排序。

vector<KeyValue> term_prb;

class KeyValue {

 public:

  void Set(unsigned int t, float w) {

   term = t;

   weight = w;

  }

  unsigned int term;

  float weight;

};

最后，当查询一个<c,w>出现的概率时，只需拼凑<c,w>对应的unsigned int，然后在vector中二分查找即可。

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两种数据结构中，需要注意的是，加载之前需要将对应的概率（先验概率和调教概率）计算出来，预测的Hadoop伪代码如下：

(1) 多轮预测新doc在每个种类中的概率：

PredcitProbility()

Map(new_doc):

 for each class in dictionary:

  Emit(doc, class|probility); 

该Hadoop作业可能运行多次，主要取决于划分的字典数目

(2) 选出最大概率，得到doc的类别

PredcitProbilityCombiner():

Map(doc):

 Emit(doc, class|probility); //直接输出(1)的结果，让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);

该作业的输入是上一个作业的所有输出。

4. 总结

上面共提到4个Hadoop作业，分别为：ClassPrior，ConditionalProbility，PredictProbility和PredictProbilityCombiner，它们的关系如下：

5. 参考资料

(1) 基于MapReduce 的并行贝叶斯分类算法的设计与实现, 丁光.华. 周继鹏. 周敏