1.    贝叶斯分类

1.1.原理

    条件概率P(A|B) 表示事件B已经发生的前提下，事件A发生的概率，叫做事件B发生下事件A的条件概率。其基本求解公式为P(A|B)= P(AB)/ P(B)。该公式说明了如何计算已知B发生的前提下A还要发生的概率。贝叶斯定理解决了现实生活里经常遇到的问题：已知某条件概率，如何得到两个事件交换后的概率，也就是在已知P(A|B)的情况下如何求得P(B|A)。贝叶斯定理就为我们打通从P(A|B)获得P(B|A)的道路。所以该定理的用途十分广泛，可以用作数据的预测分类等。下面直接给出贝叶斯定理：

贝叶斯分类的正式定义如下：

（1）设

为一个待分类项，而每个a为x的一个特征属性。

（2）有类别集合

（3）计算

（4）如果

，则

   那么现在的关键就是如何计算第3步中的各个条件概率。我们可以这么做：

（1）找到一个已知分类的待分类项集合，这个集合叫做训练样本集。

（2）统计得到在各类别下各个特征属性的条件概率估计。即

（3）如果各个特征属性是条件独立的，则根据贝叶斯定理有如下推导：

因为分母对于所有类别为常数，因为我们只要将分子最大化皆可。又因为各特征属性是条件独立的，所以有：

也就是说只需要计算出每一个特征向量在某一种分类的累乘然后乘以这个分类的概率。这样算出的最大值所在的分类则为需要的分类。

1.2.步骤

    根据上述分析，朴素贝叶斯分类的流程可以由下图表示：

     可以看到，整个朴素贝叶斯分类分为三个阶段：

  第一阶段——准备工作阶段，这个阶段的任务是为朴素贝叶斯分类做必要的准备，主要工作是根据具体情况确定特征属性，并对每个特征属性进行适当划分，然后由人工对一部分待分类项进行分类，形成训练样本集合。这一阶段的输入是所有待分类数据，输出是特征属性和训练样本。这一阶段是整个朴素贝叶斯分类中唯一需要人工完成的阶段，其质量对整个过程将有重要影响，分类器的质量很大程度上由特征属性、特征属性划分及训练样本质量决定。

  第二阶段——分类器训练阶段，这个阶段的任务就是生成分类器，主要工作是计算每个类别在训练样本中的出现频率及每个特征属性划分对每个类别的条件概率估计，并将结果记录。其输入是特征属性和训练样本，输出是分类器。这一阶段是机械性阶段，根据前面讨论的公式可以由程序自动计算完成。

   第三阶段——应用阶段。这个阶段的任务是使用分类器对待分类项进行分类，其输入是分类器和待分类项，输出是待分类项与类别的映射关系。这一阶段也是机械性阶段，由程序完成。

1.3.估计类别下特征属性划分的条件概率及Laplace校准

   由上文看出，计算各个划分的条件概率P(a|y)是朴素贝叶斯分类的关键性步骤，当特征属性为离散值时，只要很方便的统计训练样本中各个划分在每个类别中出现的频率即可用来估计P(a|y)，下面讨论特征属性是连续值的情况。

  当特征属性为连续值时，通常假定其值服从高斯分布（也称正态分布）。即：

  因此只要计算出训练样本中各个类别中此特征项划分的各均值和标准差，代入上述公式即可得到需要的估计值。

  另一个需要讨论的问题就是当P(a|y)=0怎么办，当某个类别下某个特征项划分没有出现时，就是产生这种现象，这会令分类器质量大大降低。为了解决这个问题，我们引入Laplace校准，它的思想非常简单，就是对每类别下所有划分的计数加1（mahout中采取类似的加1操作），这样如果训练样本集数量充分大时，并不会对结果产生影响，并且解决了上述频率为0的情况。

1.4.分类器的评价

  首先要定义，分类器的正确率指分类器正确分类的项目占所有被分类项目的比率。

  通常使用回归测试来评估分类器的准确率，最简单的方法是用构造完成的分类器对训练数据进行分类，然后根据结果给出正确率评估。但这不是一个好方法，因为使用训练数据作为检测数据有可能因为过分拟合而导致结果过于乐观，所以一种更好的方法是在构造初期将训练数据一分为二，用一部分构造分类器，然后用另一部分检测分类器的准确率。

2.    使用Mahout命令完成贝叶斯分类

2.1.文件目录结构

    一个根目录包含多个子目录，各个子目录中存放一类文件。应为贝叶斯是有监督的算法，这样的目录结构，才可以将文件的父路径作为类标签，才能对数据进行训练。

2.2.将文件转化成序列化文件

  .mahout seqdirectory /

    -i ${WORK_DIR}/20news-all /

    -o ${WORK_DIR}/20news-seq -ow

从MAHOUT_HOME/conf文件夹下的driver.classes.default.PRops文件可以找到，此命令实际是运行

org.apache.mahout.text.SequenceFilesFromDirectory类，此类是一个Hadoop的Job。只有Mapper，SequenceFilesFromDirectoryMapper，没有Reducer。

2.3.将分词的结果(Sequence File)转化为向量集(Vectors)

    mahout seq2sparse /

    -i /user/grid/tokenizer/result-seq /

-o /user/grid/tokenizer/result-vectors -lnorm -nv -wt tfidf

实际运行org.apache.mahout.vectorizer.SparseVectorsFromSequenceFiles类，包含4步： DocumentProcessor，DictionaryVectorizer，HighDFWordsPruner和TFIDFConverter

2.4.将向量集按照2:8的比例随机拆分为测试集和训练集

    mahout split /

    --input /user/grid/tokenizer/result-vectors/tfidf-vectors /

    --trainingOutput /user/grid/tokenizer/result-train-vectors /

    --testOutput /user/grid/tokenizer/result-test-vectors /

--randomSelectionPct 20 --overwrite --sequenceFiles --method sequential

这里也可以 --method mapreduce，也就是说，mahout中的数据划分有两种方式，一种是串行执行，另一种是并行执行。

实际运行org.apache.mahout.utils.SplitInput类，当使用并行执行时，Job类是org.apache.mahout.utils.SplitInputJob，SplitInputMapper，SplitInputReducer。

2.5.训练贝叶斯模型

    mahout trainnb /

    -i /user/grid/tokenizer/result-train-vectors -el /

    -o /user/grid/tokenizer/model /

    -li /user/grid/tokenizer/labelindex /

    -ow -c

实际运行

org.apache.mahout.classifier.naivebayes.training.TrainNaiveBayesJob类，3步，indexInstances，weightSummer和thetaSummer。

2.6.用训练数据作为测试集，产生的误差为训练误差

    mahout testnb /

    -i /user/grid/tokenizer/result-train-vectors /

    -m /user/grid/tokenizer/model /

    -l /user/grid/tokenizer/labelindex /

    -ow -o /user/grid/tokenizer/result-testing -c

实际运行

org.apache.mahout.classifier.naivebayes.test.TestNaiveBayesDriver类，BayesTestMapper。

2.7.测试贝叶斯模型，产生的误差为测试误差

    mahout testnb /

    -i /user/grid/tokenizer/result-test-vectors /

    -m /user/grid/tokenizer/model /

    -l /user/grid/tokenizer/labelindex /

    -ow -o /user/grid/tokenizer/result-testing -c

3.    Mahout中向量实现分析

 bayes等分类，包括聚类也都需要文本的向量化，所以我们需要了解下Mahout中的文本向量化实现。对于文本信息的向量化，Mahout 已经提供了工具类，它基于 Lucene对文本信息进行分析，然后创建文本向量。在Mahout中，向量（Vector）有很多不同的实现，适用于不同的算法场景，主要介绍下面三种（对他们也可以用其他的Vector进行再包装）：

（1）DenseVector，它的实现就是一个浮点数数组，对向量里所有域都进行存储，适合用于存储密集向量。

（2）RandomaccessSparseVector 基于浮点数的 HashMap 实现的，key 是整形 (int) 类型，value 是浮点数 (double) 类型，它只存储向量中不为空的值，并提供随机访问。

（3）SequentialAccessVector 实现为整形 (int) 类型和浮点数 (double) 类型的并行数组，它也只存储向量中不为空的值，但只提供顺序访问。下面简单介绍一下Mahout向量化的过程。

3.1.mahout seqdirectory

对应的源文件是org.apache.mahout.text.SequenceFilesFromDirectory。使用mahout seqdirectory命令可以将文本文件转成Hadoop 的SequenceFile文件， SequenceFile文件是一种二制制存储的key-value键值对。以邮件分类为例，mahout seqdirectory的输入是一堆分类目录，每个目录名就是类别名，目录里面包含的是属于此类的一些文档（一个文件是一篇文章）；输出是一个SequenceFile文件，key-value类型是（Text，Text），每个key-value键值对的key是目录名（类别名），本目录下所有文件的内容作为value。

3.2.mahout seq2sparse

mahout seq2sparse将上面生成的SequenceFile转成向量文件，对应的源文件是

org.apache.mahout.vectorizer.SparseVectorsFromSequenceFiles。seq2sparse实际上是一个计算文本TF，DF，TFIDF的过程，依次产生的向量文件目录结构是：

（1）tokenized-documents 目录：保存着分词过后的文本信息。

（2）wordcount 目录：保存着全局的词汇出现的次数。

（3）dictionary.file-0 目录：保存着这些文本的词汇-编号表。

（4）tf-vectors 目录：保存着以 TF 作为权值的词频向量。

（5）df-count 目录：保存着文本的频率信息。

（6）frequcency.file-0 目录 : 保存着词汇表对应的文本频率信息。

（7）tfidf-vectors 目录：保存着文本对应的以 TFIDF 作为权值的数值向量。

下面简单介绍seq2sparse的工作流程：

（1）（Text，Text）变成（text，StringTuple）。

将生成的的序列文件的（Text，Text）变成（text，StringTuple），放在tokenized-documents目录。StringTuple是一种适合做hadoop处理的有序字符串列表，本质是一个List<String>。使用DocumentProcessor.tokenizeDocuments MR实现，使用了lucene的org.apache.lucene.analysis.Analyzer来对文本进行分析。

（2）将上面生成的(Text，StringTuple)转成词频TF向量(Text，VectorWritalbe)。

（2.1）使用名为DictionaryVectorizer.WordCount 的MR计算所有单词的数目，放在wordcount目录。

（2.2）读取上一步生成的word count文件，并且为每个单词分配唯一的id。这个函数没有使用mr，直接使用hdfs api操作，并且考虑到了后面字典要调到内存中，文件不宜太大，生成多个dictionary.file-*文件。

（2.3）使用每个dictionary.file-*，对tokenized-documents中的文件进行TF计算，生成多个partial-vectors-*。这个过程使用了DictionaryVectorizer.MakePartialVectors MR，对于每个在当前字典中找到的iterm，累加次数即可。注意maxNGramSize参数，根据用户设置max.ngrams，如果maxNGramSize >= 2，那么需要首先使用org.apache.lucene.analysis.shingle.ShingleFilter进行可能的单词组合，作为新的单词。

（2.4）PartialVectorMerger.mergePartialVectors将（3）生成的各个partial-vectors-*合并，生成tf-vectors-toprune，并删除每个partial-vectors-*。

（3）计算每个term在所有文档中的df。

（3.1）以（2）生成的TF向量文件为输入，输出每个term在所有文档中的频率以及所有的向量个数，生成的文件在df-count中。由TFIDFConverter. startDFCounting mr完成。

（3.2）直接使用hdfs api读取上一步生成的DF 文件，生成多个frequency.file-*文件。并统计一共有多少个vector和feature。

（4）对文档频率大的词进行剪枝。HighDFWordsPruner.pruneVectors MR  参照frequency.file-*文件，对tf-vectors-toprune进行剪枝，生成剪枝后的tf-vectors。

（5）计算tfidf向量。类似上面求tf，计算tfidf也是拆成多个makePartialVectors，每个makePartialVectors使用了名为MakePartialVectors 的MR，输入是上面（2）生成的tf-vectors，和（3.2）中生成的frequency.file-*作为字典文件，生成针对这个字典文件的partial-vectors-*。对于在当前字典中存在的feature 的df，会根据maxDf，minDf的配置做一下调整，然后使用TFIDF类的calculate方法根据tf，df，文档总数目计算tfidf。TFIDF类的calculate方法会使用Similarity接口的的tf()和idf()方法，tf()使用(float)Math.sqrt(freq)，idf()使用(float)(Math.log(numDocs/(double)(docFreq+1)) + 1.0)。可以看到，算出的tfidf，与tf成正比，与idf成反比。

（5.1）最后使用PartialVectorMerger::MergePartialVectors MR，对于上一步生成的所有partial-vectors-*合并，并删除每个partial-vectors-*。

4.    将数据分为训练和测试两部分

 将数据分为两部分，一部分用于训练贝叶斯模型，另一部分用于测试。在mahout中可以使用串行和并行两种方式对数据进行划分。

 串行划分的步骤是：

 并行划分的步骤是：

org.apache.mahout.utils.SplitInputJob完成对数据集的划分，org.apache.mahout.utils.SplitInputMapper将生成的TFIDF向量集作为输入，按一定比例选取待划分的数据集（整体数据集的子集），org.apache.mahout.utils.SplitInputReducer对待划分的数据集，按随机抽样的方式进行划分。

5.    Mahout中bayes模型实现与测试

 Bayes分类主要分为两个阶段：

（1）分类器训练阶段，这个阶段的任务就是生成分类器（model），主要工作是计算每个类别在训练样本中的出现频率及每个特征属性划分对每个类别的条件概率估计，并将结果记录。其输入是特征属性和训练样本，输出是分类器。在mahout中，由mahout trainnb完成。

（2）应用阶段。这个阶段的任务是使用分类器对待分类项进行分类，其输入是分类器和待分类项，输出是待分类项与类别的映射关系。这一阶段由mahout testnb完成。

实际上，在两个阶段之前，还有一个准备工作阶段，这个阶段的任务是为朴素贝叶斯分类做必要的准备，主要工作是根据具体情况确定特征属性，并对每个特征属性进行适当划分，然后由人工对一部分待分类项进行分类，形成训练样本集合。这一阶段的输入是所有待分类数据，输出是特征属性和训练样本。这一阶段是整个朴素贝叶斯分类中唯一需要人工完成的阶段，其质量对整个过程将有重要影响，分类器的质量很大程度上由特征属性、特征属性划分及训练样本质量决定。下面我们主要分析由程序完成的分类器训练阶段和应用阶段。

5.1.mahout trainnb

 训练样本，对应类org.apache.mahout.classifier.naivebayes.training.TrainNaiveBayesJob。输入是经过mahout seqdirectory和mahout seq2sparse向量化的序列化文件，输出是一个model（训练器）。具体流程：

（1）叠加所有相同label的tfidf vector

通过TrainNaiveBayesJob-IndexInstancesMapper-Reducer实现。该mr使用到了缓存文件labelindex，labelindex存储每个label对应的id。生成的文件是放到summedObservations临时目录下面。这一个过程实际上是得到了每个label下的feature的得分。

（2）叠加上一步中所有label和所有feature的向量

通过TrainNaiveBayesJob-WeightsMapper-Reducer实现，输出到tmp的weights目录下面。将（1）中所有vector相加，得到每个Feature的权重向量weightsPerFeature；将（1）中每个label对应的所有vector的所有元素相加，得到每个Label的权重向量weightsPerLabel。这一过程实际上是计算每个label的得分和每个feature在所有label下的得分。

（3）建立model

新建一个Matrix scoresPerLabelAndFeature，这是一个二维的矩阵，行是weightsPerLabel的大小，列是weightsPerFeature的大小，然后将（1）中生成的每个label下的每个feature的得分填充这个scoresPerLabelAndFeature，这样scoresPerLabelAndFeature实际上就是每个feature在每个label下的得分，加上（2）中生成的weightsPerFeature、weightsPerLabel就可以构造一个NaiveBayesModel，写入到hadoop的model/naiveBayesModel.bin中。

5.2.mahout testnb

    使用训练器进行分类。org.apache.mahout.classifier.naivebayes.test.TestNaiveBayesDriver。该过程只有一个MR 叫TestNaiveBayesDriver-BayesTestMapper-Reducer。它的输出key是期望的label，而value是在每一个label下的打分。首先将上面生成的model读出来，建立NaiveBayesModel对象，然后就可以计算待分类向量在每个label下的得分了。根据贝叶斯的特征独立性特点，它实际上是将待分类向量的每个feature在这个label下的分值相加了（因为feature在label下的打分使用log）。根据选择的分类器是ComplementaryNaiveBayesClassifier还是StandardNaiveBayesClassifier， feature在label下的打分的计算公式不一样：

（1）StandardNaiveBayesClassifier：For Bayes

Weight = Log [ ( W-N-Tf-Idf + alpha_i ) / ( Sigma_k + N  ) ]

其中

featureLabelWeight即W-N-Tf-Idf

labelWeight即Sigma_k

numFeatures即N

（2）ComplementaryNaiveBayesClassifier：For CBayes

Weight = Log [ ( Sigma_j - W-N-Tf-Idf + alpha_i ) / ( Sigma_jSigma_k - Sigma_k + N  ) ]

其中

featureWeight即Sigma_j

featureLabelWeight即W-N-Tf-Idf

labelWeight即Sigma_k

totalWeight即Sigma_jSigma_k，是labelWeight中各项之和。

numFeatures即N

计算出待分类向量在每个label下的得分后，就可以决定分到哪一个label下了。