首页
登录 | 注册

【十大经典数据挖掘算法】Naïve Bayes

【十大经典数据挖掘算法】系列

  1. C4.5
  2. K-Means
  3. SVM
  4. Apriori
  5. EM
  6. PageRank
  7. AdaBoost
  8. kNN
  9. Naïve Bayes
  10. CART

朴素贝叶斯(Naïve Bayes)属于监督学习的生成模型,实现简单,没有迭代,学习效率高,在大样本量下会有较好的表现。但因为假设太强——假设特征条件独立,在输入向量的特征条件有关联的场景下并不适用。

1. 朴素贝叶斯算法

朴素贝叶斯分类器的主要思路:通过联合概率\(P(x,y) = P(x|y) P(y)\)建模,运用贝叶斯定理求解后验概率\(P(y|x)\);将后验概率最大者对应的的类别作为预测类别。

分类方法

首先,我们定义训练集\(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。

2. 拼写检查

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

朴素贝叶斯分类

设用户输入的单词为\(w\),要返回的拼写正确单词为\(c\),拼写检查要找出最大可能的\(c\),即
\[\arg \mathop{\max}_{c} p(c|w)\]

\(p(c|w)\)可以理解为在已发生\(w\)的情况下发生\(c\)的概率。根据贝叶斯定理:
\[p(c|w)={p(w|c)p(c)\over p(w)}\]

贝叶斯分类器可表示为:
\[\arg \mathop{\max}_{c} p(w|c)p(c)\]

如何估计\(p(w|c)\)\(p(c)\)呢?估计\(p(c)\)的办法可以在文本库中统计单词\(c\)的频率。\(p(w|c)\)表示大多数用户在输入\(c\)时拼写错误输入成了\(w\)的概率,可以看作时错误模型。这需要对大量的错误输入进行统计,才能对\(p(w|c)\)估计得较为准确。Norvig对此做了简易化的处理:

  • 统计所有与\(w\)编辑距离为1的拼写正确单词,选出在文本库中频率最高者;
  • 若未找到与\(w\)编辑距离为1的拼写正确单词,则统计所有与\(w\)编辑距离为2的拼写正确单词,选出在文本库中频率最高者
  • 若与\(w\)编辑距离为2的拼写正确单词也未找到,则返回\(w\)(即分类失败)。

所谓编辑距离为1,指单词可以通过增加、删除、修改(一个字母)或交换(相邻两个字母)变成另外的单词。上述处理办法默认了:编辑距离为1的拼写正确单词永远比编辑距离为2的更有可能。

存在问题

Norvig所介绍的拼写检查是非常简单的一种,他在博文[2]中指出不足。此外,还有一些需要优化的地方:

  • 上下文关联,比如输入thew,在不同的上下文中可能返回的拼写正确单词不同;
  • 输入媒介,比如用户用键盘输入与用手机的九宫格输入,其拼写错误的方式时不一样的。

3. 参考资料

[1] 李航,《统计学习方法》.
[2] Peter Norvig, How to Write a Spelling Corrector.


相关文章

  • 算法推导过程参见[dijkstra算法推导详解] 此文为[dijkstra算法代码实现] https://www.cnblogs.com/Halburt/p/10767389.html package a; import java.util ...
  • 之前自己一直想总结一下国内搞机器学习和数据挖掘的大牛,但是自己太懒了.所以没搞...最近看到了下面转载的这篇博文,感觉总结的比较全面了.个人认为,但从整体研究实力来说,机器学习和数据挖掘方向国内最强的地方还是在MSRA,那边的相关研究小组太 ...
  • 快三个月没写博客了,一直在忙着准备面试和去面试的路上,所以没时间写,也没什么想写的.现在告一段落,就总结一波! 面经 本人真的是双非一本.为什么加“真的”?因为有的人也写着"双非一本,进入阿里",但是某电子科技大学,比9 ...
  • 补习系列(20)-大话 WebSocket 与 "尬聊"的实现
    目录 一.聊聊 WebSocket 二.Stomp 是个什么鬼 三.SpringBoot 整合 WebSocket A. 引入依赖 B. WebSocket 配置 C. 控制器 D. 前端实现 四.参考文档 一.聊聊 WebSocket 从 ...
  • 一.前言 在日常开发中,我们经常会碰到需要在运行时才知道对象个数的情况,这种情况不能使用数组,因为数组是固定数量的,这个时候我们就会使用集合,因为集合可以存储数量不确定的对象. 集合类是特别有用的工具类,不仅可以存储数量不等的对象,还可以实 ...
  • 机器学习web服务化实战:一次吐血的服务化之路
    背景 在公司内部,我负责帮助研究院的小伙伴搭建机器学习web服务,研究院的小伙伴提供一个机器学习本地接口,我负责提供一个对外服务的HTTP接口. 说起人工智能和机器学习,python是最擅长的,其以开发速度快,第三方库多而广受欢迎,以至于现 ...

2019 cecdns.com webmaster#cecdns.com
12 q. 0.078 s.
京ICP备10005923号