本章关键词
概率、过滤器、分类器
贝叶斯公式是概率论中非常重要的公式,朴素贝叶斯是基于贝叶斯公式和特征条件独立假设的一种分类方法。在数据分析和人工智能中你都能看到它的身影。
问题解析
手机的垃圾短信一定让你不堪其扰,各种软件提供的垃圾信息过滤功能你也一定使用过。那么,你有没有想过,这个功能是如何实现的?
要实现这个功能,我们有很多思路,在这里我就略微提一下,具体的内容你可以自己思考:
-
使用一个基于黑名单的过滤器:
维护一个通讯黑名单,存储所有发送过垃圾短信电话号码。我们可以使用散列表、位图、布隆过滤器等维护这个名单。
优点:简单易实现
缺点:如果名单非常庞大,可能会占用过多的空间。且布隆过滤器可能会出现误判,这种误判是无法忍受的。
扩展:使用网络维护这个黑名单,有短信的时候直接查询发送方是否在黑名单中。 -
使用一个基于规则的过滤器:
特殊词概率.jpg
我们可以通过短信内容判断短信是否是垃圾短信,这些规则有很多,比如下面的几个:
1.短信中包含特殊词汇,如非法词语
2.短信发送号码是群发号码,而非正常的手机号码
3.短信中包含回拨的联系方式,如:“快点击 www.xxxxx.com”
...
在这里需要强调一下第一点:如何确定一个词汇是否属于特殊词汇?首先,我们需要对正常短信和垃圾短信进行分析,通过分析短信内容,从中提取出单词,和垃圾短信的关联。如果某个单词出现在垃圾短信中的概率远大于正常短信中的概率,那我们就有理由将它设置为特殊词汇。你可以看一下下图帮助理解: -
使用基于概率统计的过滤器
这种过滤器是今天学习的重点,具体来说就是使用朴素贝叶斯公式计算一个短信是垃圾短信的概率,请看下面的内容
算法解析
下面我分几个步骤,逐渐构建出一个基于概率统计的过滤器:
1.什么是贝叶斯公式
贝叶斯公式指出了在一定条件下发生某事件的转换公式,具体看下面这个例子:
假设事件 A 是“小明不去上学”,事件 B 是“下雨了”。我们现在统计了一下过去 10 天的下雨情况和小明上学的情况,作为样本数据。 贝叶斯举例.jpg
我们来分析一下,这组样本有什么规律。在这 10 天中,有 4 天下雨,所以下雨的概率 P(B)=4/10。10 天中有 3 天,小明没有去上学,所以小明不去上学的概率 P(A)=3/10。在 4 个下雨天中,小明有 2 天没去上学,所以下雨天不去上学的概率 P(A|B)=2/4。在小明没有去上学的 3 天中,有 2 天下雨了,所以小明因为下雨而不上学的概率是 P(B|A)=2/3。实际上,这 4 个概率值之间,有一定的关系,这个关系就是朴素贝叶斯算法,我们用公式表示出来,就是下面这个样子。
贝叶斯公式.jpg
没错,上一幅图就是贝叶斯公式,为了让你不至于混淆概念,我要补充几个公式,你一定要弄清他们之间的区别和联系:
条件概率公式:
条件概率独立性:
独立性由独立性可以推出:
若 A 和 B 独立,则:P(AB) = P(A)P(B)
2.获取短信特征
我们将短信分成 n 个单词,这 n 个单词就是这个短信的特征单词(或者你喜欢的名字)。于是,判断一个短信是否是垃圾短信,这个问题就变成了判断包含了这 n 个特征单词的短信是否是垃圾短信。(设这些单词为 w1,w2...wn)
3.求条件概率
判断垃圾短信并不是一个 0-1 问题,它更多的是通过概率求解判断 一个短信是垃圾短信的可能性,也就是求下面这个概率: 短信特征项.jpg 根据贝叶斯公式,可以转换成: 垃圾短信-使用贝叶斯(公式1)4.朴素贝叶斯,“朴素”在哪里
很容易理解,一个短信中的单词是存在一定的联系的,例如 “温暖的太阳” 中,“温暖” 和 “太阳” 存在一定的联系(虽然很微弱)。而朴素贝叶斯中,则假设模型之间相互独立,也就是说,我们可以 “朴素” 地认为 “太阳” 和 “温暖” 之间没有任何关联,它们相互独立。
5.求解概率
根据独立性,我们就可以对之前的公式中的一部分进行求解: 垃圾短信-朴素分解.jpg分解到这里,上图给出的概率就很容易算出来了:
P(Wi 出现在短信中 | 短信是垃圾短信)表示垃圾短信中包含 Wi 这个单词的概率有多大。这个概率值通过统计样本很容易就能获得。我们假设垃圾短信有 y 个,其中包含 Wi 的有 x 个,那这个概率值就等于 x/y。
P(短信是垃圾短信)表示短信是垃圾短信的概率,这个很容易得到。我们把样本中垃圾短信的个数除以总样本短信个数,就是短信是垃圾短信的概率。
算到这里,其实 (公式1)已经可以计算出来了,我们也就可以直接求出一个短信是垃圾短信的概率。但是,我们没有必要将 (公式1) 中的分母计算出来,因为:
实际上,我们可以分别计算同时包含 W1,W2,W3,…,Wn 这 n 个单词的短信,是垃圾短信和非垃圾短信的概率。假设它们分别是 p1 和 p2。我们并不需要单纯地基于 p1 值的大小来判断是否是垃圾短信,而是通过对比 p1 和 p2 值的大小,来判断一条短信是否是垃圾短信。更细化一点讲,那就是,如果 p1 是 p2 的很多倍(比如 10 倍),我们才确信这条短信是垃圾短信。 垃圾短信-判定.jpg
至此,使用概率统计的方法制作的过滤器就已经成型了。
实际上,我们可以将三种过滤器给出的判断综合考量,最后判定一个短信是否为垃圾短信。
总结
这节课的重点是 使用概率统计的方法对数据进行分类,我有一点感想:
- 在这节内容中我是真真切切地感受到了“数学之美”
- 概率思维是一个非常重要的思维,它对 数据分类 和 事物判断 有着重要意义
- 概率上的这种意义,结合大数据和云计算,成为了 人工智能 的基石
以上就是本节的内容,希望你能更深刻地理解概率。
注:本文章的主要内容来自我对极客时间app的《数据结构与算法之美》专栏的总结,我使用了大量的原文、代码和截图,如果想要了解具体内容,可以前往极客时间
网友评论