理论基础

朴素贝叶斯公式求后验概率

$$ P(c_i|d)=\frac{P(d|c_i)P(c_i)}{P(d)} $$

其中 $d$ 为文档，$c_i$ 为分类。文档是词的合集，提取特征 $d=<t_1, t_2, ... ,t_n>$，即文档由n个词 token（可重复）组成。做独立性假设后公式可化简为：

$$ P(c_i|d)=\frac{\prod_{j=1}^{n} P(t_j|c_i)P(c_i)}{P(d)} $$

由于需要知道的是文档最有可能的分类，因此实际上是求 $\arg\max_{c_i}P(c_i|d)$，又因为 $P(d)$ 不变，因此也就是求：

$$ \arg\max_{c_i}\prod_{j=1}^{n}P(t_j|c_i)P(c_i) \\ \propto \arg\max_{c_i}(\sum_{j=1}^{n}\log{P(t_j|c_i)}+\log{P(c_i)}) $$

$P(t_j|c_i)$ 用词 $t_j$ 在类别 $c_i$ 的文档中的占比来估计，$P(c_i)$ 用类别 $c_i$ 的文档在所有文档中比重来估计。并且为了避免个别 $P(t_j|c_i)=0$导致错误，对单词频数加1进行平滑：

$$ \begin{gathered} \begin{aligned} & \hat{P}(t_j|c_i) = \frac{N(t=t_j,\space c=c_i)+1}{\sum_{t_k \in V_i} (N(t=t_k,\space c=c_i)+1)} = \frac{N(t=t_j,\space c=c_i)+1}{N(c=c_i)+|V_i|} \end{aligned}\\ \hat{P}(c_i) = \frac{N(c_i)}{N} \end{gathered} $$

其中 $N(t=t_j,c=c_i)$为 $c_i$ 类文章中 $t_j$ 出现的次数， $V_i$为出现在所有类型为 $c_i$ 的文档中的单词集合（不重复），$|V_i|$ 为不重复单词数。

整体框架

• Job1：统计$N(c=c_i)$
  • 输入训练集（分好类的文档，不同类别的文档在不同的目录中，目录名即为类别名）
  • Mapper<Text, Writable, Text, Writable>
    • 使用自定义的InputFormat，只读取文件所在目录名而不读取内容，并且规定split不会切分文件，防止统计冗余
    • k1=k2：继承InputFormat的输出键值对，类别名=目录名
    • v1=v2：1
  • Reducer<Text, List<Writable>
    • 输出 <类别, 总数>
• Job2：统计 $N(t=t_j,c=c_i)$
  • 输入训练集
  • Mapper<LongWritable, Text, Text, IntWritable>
    • 使用默认的TextInputFormat
    • RecordReader 按行读取（使用TextInputFormat），一行一个单词，同时读取split包含的文件名作为类别，将类别和单词用``拼接成一个Text类型变量作为Key输出
    • Value 输出取 1 即可
  • Reducer< Text, List<IntWritable> >
    • 输出< 类别-单词, 总数 >
• Job3: 统计$|V_i|$
  • 输入job2的output
  • Mapper<Text, IntWritable>
    • RecordReader 读入每一行，Map成<类别，个数>
  • Reducer 输入<类别, list{个数}>，输出<类别, 个数求和>
• Job3：测试
  • 输入测试集（待分类的文档）
  • 输出文档类别
  • 评估分类效果

环境准备

安装 Hadoop

• 官网给的都是基于 Linux 系统构建的，如果要在 Windows 系统上使用，需要补全 bin 中的winutils.exe，hadoop.dll等文件
  • 或者下载源码，按照说明自己在 Windows 上构建
• 需要指定相应版本的 JDK （一般都是 Java 8）
• 正确设置环境变量 %HADOOP_HOME%
  • 使用 Cygwin 环境执行 Hadoop 命令会产生路径问题，导致无法正确加载类