本篇主要介绍贝叶斯分类算法中的朴素贝叶斯以及多项式模型,以及处理连续变量的高斯模型。

前言,在观看斯坦福公开课女神Daphne Koller的时候,对视频week1.6里介绍的两个算法不理解,找了些资料帮助理解,特记录如下,欢迎交流

文本分类问题中,要解决的问题是如何对一个文本进行分类,这样的分类可以看为将文本对类别进行一次映射。问题的数学描述如下,给定的文档集合$X$ $X=\{X_1,X_2,...,X_{n} \}$,其中文档由很多属性构成$X_k=\{x_1,x_2,...,x_{n} \}$。贝叶斯分类器中将词作为文档的基本属性,例如$X_k$为"good study, Day day up",其文档属性特征向量为$X_k(Good,good,study,Day,day,up)$。$X$由n个文档组成。预先定义的文档类别集合$Y=\{Y_1,Y_2,...,Y_{|c|} \}$,我们的任务是找到一个有效映射函数$\Phi $,准确实现文档到类别的映射$\Phi:X \to Y $。

在进入问题之前,先回忆下贝叶斯公式。对于事件$A$、$B$,其概率分别为$P\left(X\right)$、$P\left(Y\right)$。事件$A$发生条件下,$B$也发生的概率为:$P\left( {Y|X} \right) = \frac{{P\left( {X,Y} \right)}}{{P\left( X \right)}}$。对于文档$X_k$归属于哪个类,我们希望找到文档$X_k(x_1,x_2,...,x_m)$属于每个类别$Y_i$的概率,用如下公式表示为$$ P\left( {{Y_j}|{X_i}} \right) = \frac{{P\left( {{Y_j}} \right)P\left( {X_i|Y_j} \right)}}{{P\left( X_i \right)}} = \frac{{P\left( Y_j \right)P\left( {x_1,x_2,...,x_m|Y_j} \right)}}{{P(x_1,x_2,...,x_m)}}$$

然后根据最大的概率值判读文档的具体归属类别。因为上述公式中${{P(x_1,x_2,...,x_m)}}$是常数,目标函数可以转化为下面形式:
$$\mathop {\arg \max }\limits_{{Y_j}} P(Y_j)P(X_i|Y_j) $$
$$ \mathop {\arg \max }\limits_{{Y_j}}P\left( {{Y_j}} \right)P\left( {x_1,x_2,...,x_m|{Y_j}} \right) $$
朴素贝叶斯分类器的假设前提是条件独立性。给定文档类别$Y$,假设文档的属性即特征项是相互独立的。即:
$$P(X_i|Y_j)= P\left( {{x_1},{x_2}, \ldots ,{x_n}|{Y_j}} \right) = \prod\limits_{i = 1}^m {P\left( {{x_i}|{Y_j}} \right)} $$

可知我们的目标函数可以进一步简化为:
$$ \mathop {\arg \max }\limits_{{Y_j}} P\left( {{Y_j}} \right) \prod\limits_{i = 1}^m {P\left( {{x_i}|{Y_j}} \right)} $$

我们得到目标函数以后,下面考虑贝叶斯模型的选择。
常见三种模型:伯努利算法,多项式模型,高斯模型。伯努利更多用于离散变量的计算,后者高斯模型可以用于处理连续变量。

  • 伯努利朴素贝叶斯算法: $$P(X_i|Y_j) = \prod\limits_{i = 1}^m {({B_{x_i}}P({x_i}|{Y_j}) + (1 - {B_{x_i}})(1 - P({x_i}|{Y_j})))} $$ 其中文档集合的词表有$m$个特征词,二值变量$B_{x_i}$表示待分类文档中出现$x_t$的情况:$B_{x_i}=1$表示特征词$x_t$在待分类文档中,反之,则为0。$P({x_i}|{Y_j})$表示训练集文档属于${Y_j}$时,特征词${x_i}$出现的概率。具体计算时采用$P({x_i}|{Y_j}) = \frac{{1 + {n_{ij}}}}{{2 + {n_j}}}$,其中$n_{ij}$为类$Y_j$包含特征词$x_i$的文档总数,$n_j$为类$Y_j$中包含的总文档数目。
    先验概率的计算公式$P(Y_j)=\frac{类Y_j中的训练文本总数}{训练样本总数}$
    可得计算待分类文档属于每个类$Y_j$的概率,可得$ \mathop {\arg \max }\limits_{{Y_j}} P(Y_j)P(X_i|Y_j) $
  • 对上述方法进一步解释:对于目标待分类文档$X_k$,特征词服从伯努利分布,在文档中出现特征词一次记为1,不出现记为0,用变量$B_{x_i}$表示。文档中有m个不重复特征词,通过m次伯努利实验产生对目标后验概率的估计:$$P(X_i|Y_j) = \prod\limits_{i = 1}^m {({B_{x_i}}P({x_i}|{Y_j}) + (1 - {B_{x_i}})(1 - P({x_i}|{Y_j})))} $$ 其中$P({x_i}|{Y_j})$表示文档属于${Y_j}$时,特征词${x_i}$出现的概率。从公式可以看出,在多变量伯努利模型中,文档$X_i$归属后验概率$P(X_i|Y_j)$表示为所有特征词的类条件概率的乘积,如果特征词在待分类文档中出现,乘以$P(x_i|Y_j)$,否则,乘以$1-P(x_i|Y_j)$。
    给定类别${Y_j}$,特征词$x_i$的类条件概率$P(x_i|Y_j)$的估算通过统计训练文档频数得到:$P({x_i}|{Y_j}) = \frac{{{n_{ij}}}}{{{n_j}}}$,其中$n_ij$为类$Y_j$包含特征词$x_i$的文档总数,$n_j$为类$Y_j$中包含的总文档数目。为了避免出现零概率,通常需要加入平滑因子,一般采用$m$估计方法,上述类条件概率$P(x_i|Y_j)$改写为$P({x_i}|{Y_j}) = \frac{{1 + {n_{ij}}}}{{2 + {n_j}}}$例如取$m=2$,$p=1/2$

PS.可以看出伯努利模型忽略了每个特征词(单词)在文档中出现的频次,这个信息很重要。因此该模型的分类效果通常不是很好。

  • 多项式模型
    先验概率$P(Y_j)$= 类$Y_j$特征词总数 / 整个训练样本的特征词总数
    单词的类条件概率$P(x_i|Y_j)$=(类$Y_j$下单词$x_i$在各个文档中出现过的次数之和+1)/(类$Y_j$下特征词总数+训练样本词典特征词数目)
    将单词的类条件概率累加起来得到文档的类条件概率:$$ P({X_i}|{Y_j}) = \prod\limits_{i = 1}^n {{{P({x_i}|{Y_j})}}} = \prod\limits_{i = 1}^n\frac{{\sum\limits_{k = 1}^{|X|} {N({x_i},{X_k})} + 1}}{{\sum\limits_{i = 1}^{|V|} {\sum\limits_{k = 1}^{|X|} {N({x_i},{X_k})} } + |V| }} $$
    其中,待分类文档有$n$个特征词($n$是总字数,重复出现也计字数),${\sum\limits_{k = 1}^{|X|} {N({x_i},{X_k})} }$表示特征词$x_i$在类别$Y_j$文档集合出现次数的总和。${\sum\limits_{i = 1}^{|V|} {\sum\limits_{k = 1}^{|X|} {N({x_i},{X_k})} } }$为类$Y_j$中所有特征项的总次数,$V$是训练样本的特征词表,$|V|$表示词表的特征词总数
    我们得到,$ \mathop {\arg \max }\limits_{{Y_j}} P(Y_j)P(X_i|Y_j) $
  • 进一步解释,采用不同于伯努利模型的最大化后验概率求解方法,通过考虑单篇文章的词频,提高了分类能力。文档$X_i$属于类$Y_j$时,统计$x_i$的频率,出现一次的概率为$P (x_i|Y_j)$,那么,同时出现$n_k$次的概率为$P (x_i|Y_j)^{n_k}$。假定文档中,特征词的个数有$n=n_{x_1}+n_{x_2}+...+n_{x_k} $个。那么$ P({X_i}|{Y_j}) = \prod\limits_{i = 1}^n {P({x_i}|{C_j})} $。在多项式模型中,$P({x_i}|{Y_j})$的词频估算为$$P({x_i}|{Y_j}) = \frac{{\sum\limits_{k = 1}^{|X|} {N({x_i},{X_k})} }}{{\sum\limits_{i = 1}^{|V|} {\sum\limits_{k = 1}^{|X|} {N({x_i},{X_k})} } }}$$,其中,${\sum\limits_{k = 1}^{|X|} {N({x_i},{X_k})} }$表示特征词$x_i$在$Y_j$文档出现次数的总和。${\sum\limits_{i = 1}^{|V|} {\sum\limits_{k = 1}^{|X|} {N({x_i},{X_k})} } }$为类$C_j$中所有特征项的总次数,V是训练样本的单词表(PS.抽取单词,多次出现的单词,只算一个)。同样为了避免零概率,加入平滑因子,取$m=V$,$p=1/|V|$,公式更新为:$$P({x_i}|{Y_j}) = \frac{{\sum\limits_{k = 1}^{|X|} {N({x_i},{X_k})} + 1}}{{\sum\limits_{i = 1}^{|V|} {\sum\limits_{k = 1}^{|X|} {N({x_i},{X_k})} + |V|} }}$$
  • 高斯模型
    特征属性是连续值的情况,当特征属性为连续值时,通常假定其值服从高斯分布(也称正态分布)。上面的特征词,下面用特征项代替。$$P({x_i}|{Y_k}) = g({x_i},\mu ,\delta ) = {1 \over {\sqrt {2\pi } \delta }}\exp \left( { - {{{{(x - \mu )}^2}} \over {2{\delta ^2}}}} \right)$$ 因此只要计算出训练样本中各个类别中此特征项划分的各均值和标准差,代入上述公式即可得到需要的估计值。
    值得一提的是,当$P(x_i|Y_j)=0$,即某个类别下某个特征项划分没有出现时,会令分类器质量大大降低。为了解决这个问题,我们引入Laplace校准,对每个类别下所有划分的计数加1。这个做法和伯努利模型、多项式模型类似。

参考文章:
1.李丹. “基于朴素贝叶斯方法的文本分类研究,” n.d.cnki

2.灵魂机器. “基于朴素贝叶斯的文本分类算法” n.d. blog

3.PhoenixZq.”贝叶斯分类 “ cnblogs