转载

【十大经典数据挖掘算法】朴素贝叶斯Naïve Bayes

朴素贝叶斯（Naïve Bayes）属于无监督学习的一种，实现简单，没有迭代，学习效率较高，并且在大样本量下会有更好的表现。但同时，因为朴素贝叶斯假设特征条件独立，这个假设太强，在一些特征条件有关联的场景下并不适用。

朴素贝叶斯算法

朴素贝叶斯分类器以后验概率最大的类别为预测类别。

分类方法

首先，我们定义训练集$T = /lbrace (x_1,y_1),(x_2,y_2), /cdots ,(x_N,y_N)/rbrace $，其类别$y_i /in /lbrace c_1,c_2, /cdots ,c_K/rbrace $，则训练集中样本点数为$N$，类别数为$K$。输入待预测数据$x$，则预测类别

/begin{equation}

/arg /mathop{/max}/limits_{c_k}p(y=c_k|x)

/label{eq:obj1}

/end{equation}

由贝叶斯定理可知：$$p(y=c_k|x)= {p(x|y=c_k)p(y=c_k)/over p(x)} $$

对于类别$c_k$而言，$p(x)$是不变的，因此式子/eqref{eq:obj1}等价于

/begin{equation}

/arg /mathop{/max}/limits_{c_k} p(x|y=c_k)p(y=c_k)

/label{eq:obj2}

/end{equation}

从上面式子可以看出：朴素贝叶斯将分类问题转化成了求条件概率与后验概率的最大乘积问题。后验概率$p(y=c_k)$可通过统计类别的频率得到，但如何计算条件概率 $p(x|y=c_k)$呢。

朴素贝叶斯对条件概率做了 条件独立性 的假设，即特征条件相互独立。设输入$x$为n维特征向量$(x^{(1)},x^{(2)},/cdots,x^{(j)},/cdots, x^{(n)})$，第$j$维特征$x^{(j)}$的取值有$S_j$个。由概率论的知识可知：

$$p(x|y=c_k)=/prod _{j}p(x^{(j)}|y=c_k)$$

式子/eqref{eq:obj2}等价于

/begin{equation}

/arg /mathop{/max}/limits_{c_k}p(y=c_k)/prod _{j}p(x^{(j)}|y=c_k)

/end{equation}

为什么要选择后验概率最大的类别作为预测类别呢？因为后验概率最大化，可以使得期望风险最小化，为朴素贝叶斯分类的原理；具体证明参看[1]。

极大似然估计

在朴素贝叶斯学习中，需要估计先验概率与条件概率，一般时采用极大似然估计。简而言之，就是统计训练样本中的出现频率。先验概率的极大似然估计：$$/hat {p}(y=c_k) = {/sum _{i} I(y_i=c_k)/over N}$$

其中，$I$是指示函数，满足括号内条件时为1否则为0；可以看作为计数。

设第$j$维特征的取值空间为$/lbrace a_{j1},a_{j2}, /cdots, a_{jS_j} /rbrace$，且输入变量的第$j$维$x^{(j)}=a_{jl}$，则条件概率的极大似然估计：$$/hat p(x^{(j)}=a_{jl}|y=c_k)={/sum /limits_{i}I(x_i^{(j)}=a_{jl},y=c_k)/over I(y_i=c_k)}$$

贝叶斯估计

在估计先验概率与条件概率时，有可能出现为0的情况，则计算后验概率亦为0，从而影响分类的效果。因此，需要在估计时做平滑，这种方法被称为贝叶斯估计（Bayesian estimation）。先验概率的贝叶斯估计：$$/hat {p}(y=c_k) = {/sum _{i} I(y_i=c_k)+/lambda /over N+k/lambda}$$

后验概率的贝叶斯估计：$$/hat p(x^{(j)}=a_{jl}|y=c_k)={/sum /limits_{i}I(x_i^{(j)}=a_{jl},y=c_k)+/lambda/over I(y_i=c_k)+S_j/lambda}$$

常取$/lambda =1$，这时被称为Laplace平滑（Laplace smoothing）。后面提到的拼写检查则用到了Laplace平滑，将未在文本中出现的单词计数为1。

拼写检查

当用户在输入拼写错误单词时，如何返回他想输入的拼写正确单词。比如，用户输入单词 thew ，用户有到底是想输入 the ，还是想输入 thaw ？这种拼写检查的问题可以等同于分类问题：在许多可能拼写正确单词中，哪个时最有可能的？大神Peter Norvig[2]采用朴素贝叶斯解决这个拼写问题。