基于贝叶斯推断的中文垃圾邮件过滤

这篇文章不讲学术,仅仅是对一部分概率论教科书最常见的问题之一(——垃圾邮件过滤)进行实现。垃圾邮件过滤几乎是贝叶斯推论中必提的例子,原理非常简单,但是由于很多的例子仅仅把数带入公式计算,有时候也让人有些摸不着头脑。这篇文章内容实现了Bertsekas的《Introduction to Probability》中的例子,自己改成了对中文邮件的分类,在没有任何的优化下,测试中平均超过了98%的准确度,结果还是不错的。

原理

垃圾邮件过滤就是贝叶斯推断的一个运用,先来看公式:

稍微有些了解会大概知道 是先验概率,在观测前,我们自己对模型参数的一些估计。 是似然函数,这是在当前模型参数下(未知),我们的观测结果,分母部分作用就是让概率的和为1,是标准化函数。

垃圾邮件过滤

如何将贝叶斯推断运用在垃圾邮件过滤的问题上,看看下面这个例子。

任何邮件都有可能是“垃圾”或者“正常”,使用随机变量 $\Theta$ 表示两种可能性,分别用 表示。 分别是垃圾邮件或者正常邮件的概率。这也是先验概率,在类似机器学习的方式下,可以通过对训练集的学习,得到这两个参数。当然也可以认为“垃圾”或者“正常”的概率各占50%,这样只会对最后的结果稍微有点影响。这篇文章会对训练集分析得到先验概率。根据分析,垃圾邮件一般占到所有邮件的70%左右。

prior distribution of spam email

每一封邮件所有词语,记为:

当收到一封新邮件的时候,就会得到一组观察(其实就是用数学表达):

分别表示邮件中有单词 ,我们可以认为 是独立同分布的。条件概率 就是垃圾邮件中出现 的概率, 表示普通邮件中出现 的概率。

现在收到一封邮件,邮件中有“发票”一词,根据统计结果,在普通邮件中出现“发票”的概率为 万分之0.04,而在垃圾邮件中,“发票”的出现概率为0.5%。而在我所有邮件中,有70%是垃圾邮件。通过这个词语,我可以判断,这封邮件为垃圾邮件的概率为:

同理,不是垃圾邮件的概率:

在先验概率的基础上,由于得到一些观察,概率分布变化了:

posterior distribution of spam email

通过“发票”这一个词,几乎100%确定这是一封垃圾邮件了。但是问题也出现了,一个单词判断误差太大了,所以需要用邮件中的多个关键词进行判断。

联合概率分布

已经观察到邮件中有“发票”,“信誉”,“全面” 三个词,去判断邮件是否为垃圾邮件。三个词分别在垃圾邮件和正常邮件中出现的概率:

事件 $x_1$ (发票) $x_2$ (信誉) $x_3$ (全面) $\theta$(垃圾邮件)
E1(垃圾邮件) 0.5% 0.015% 0.06% 70%
E2(正常邮件) 万分之0.04 0.02% 0.006% 30%

如果这是一封垃圾邮件,“发票”,“信誉”,“全面”同时出现的概率为(姑且认为是独立事件):

同理,如果不是垃圾邮件,三个词同时出现的概率为:

当三个词同时存在,这是一封垃圾邮件的概率为

可推出有n个关键字的概率分布:

程序实现 (python)

理论的部分就是这么多了,后面的部分是对算法的实现,由于算法本来简单,而且这样做的目的是理解算法的工作原来你,所以没有使用一些现有机器学习包。因为是对中文的邮件过滤,提取中文词组时,出现了大量对邮件分类的意义不大的词语,比如“一下”,“几个”等等,我都没有进行过滤。另外由于这个项目只是演示,训练集我只选取了30000封邮件,按理来说是非常少的。参数学习的时间在我的笔记本电脑上大概只花了十多秒的时间,但是在500封邮件的测试集上,平均达到大于98%的准确率,十分震撼。对未通过测试的邮件,很多都是因为词典收录不全的原因引起,所以还是有提升空间的,但作为演示来说,这样已经足够了。

代码链接:github

一些好用的工具

训练参数模型,首先需要大量的数据集,滑铁卢大学提供了一个非常丰富的中文邮件数据集,通过链接可下载,共有超过60000封中文邮件,并且已经做了标注。

结巴分词github
由于中文不同于英文,中文的断句完全依赖于语意,没有天然的空格进行分隔,通过比较,结巴分词真的是非常好用的一款分词工具,这也是整个项目中唯一需要安装的资源包。

1
pip install jieba

这里有一个例子,看看结巴分词的效果。

原文:
您好,以下是特别为阁下发的香港信息(图片、景点、BBS等),不知道阁下是否喜
…希望没有打扰到阁下
如果无法看到下面内容,请稍侯..

去除所有标点后,结巴分词会返回一个列表:

您好, 以下, 是, 特别, 为, 阁下, 发, 的, 香港, 信息, 图片, 景点, BBS, 等, 不, 知道, 阁下, 是否, 喜, 希望, 没有, 打扰到, 阁下, 如果, 无法, 看到, 下面, 内容, 请, 稍侯

数据清理

首先是格式问题,原始文件是GBK编码,使用前先转为utf8或者以utf8读取文件。不同来源的数据集都要注意编码问题。

其次,每封邮件都有大量的无关信息,比如说收发件人和自带的格式信息,所以我过滤掉了所有英文,数字,标点符号,特殊符号,这样只保留了汉字。

1
re.sub("[0-9a-zA-Z\-\s+\.\!\/_,$%^*\(\)\+(+\"\')]+|[+——!,。?、~@#¥%……&*()<>\[\]::★◆【】《》;;=??]+","",input)

在剩余内容里还存在一些长相奇怪的文字,通过unicode中文编码范围 0x4e00-0x9fff 过滤

分词,将得到的一个字的结果全部剔除,这样就基本得到了一个可以使用的数据集了。

训练集与测试集

选取30000封邮件做训练集,500封做为测试集。

mapReduce

Map: 对邮件分词后,以词为键,1为值,并对键进行排序:

下面 1
以下 1
信息 1
内容 1
图片 1
如果 1
希望 1
您好 1
无法 1
是否 1
景点 1
没有 1
特别 1
看到 1
知道 1
稍侯 1
阁下 1
阁下 1
阁下 1
香港 1
打扰到 1

Reduce:对同样的键合并,这里“阁下”出现了3词,值记为3。

下面 1
以下 1
信息 1
内容 1
图片 1
如果 1
希望 1
您好 1
无法 1
是否 1
景点 1
没有 1
特别 1
看到 1
知道 1
稍侯 1
阁下 3
香港 1
打扰到 1

MapReduce 处理文本非常高效:

1
python map.py |sort| reduce.py > output

建立词典

分别对训练集中的垃圾邮件和正常邮件做MapReduce,得到唯一的键值对。做了半天的工作,这其实就是得到贝叶斯推断中所说的先验和似然了。通过mapreduce,很容易得到每个键出现了多少次,也知道30000封邮件中有多少个词组了。建立一个字典,每个键对应一个该键(词组)在所有词组中出现的频率。如“阁下”在垃圾邮件中和正常邮件中的出现频率是不同的,这些信息存在字典中。这就是似然的思想,似然表示的就是常识,这里就是每个词组出现的概率。

测试文本处理

大致过程与训练集一样,但是文本的内容很多,不能使用所有的词组去做垃圾邮件过滤,所以每篇邮件,选取十个出现次数最多的词组做为特征词。

先验分布是我们估计的垃圾邮件出现的概率。在训练集的处理过程中,我所选取的30000封邮件中有20156封垃圾邮件,9844封正常邮件。这就是先验分布。垃圾邮件的先验分布概率是67.2%,正常邮件是32.8%。每个单词的似然值通过词典查找对应的出现频率,查出所有10个特征词的频率。

贝叶斯推断中所有需要的值都得到了,可带入公式计算后验分布。

注意

如果某个词组在字典中不存在,那就设这个词组的似然值是一个小于十万分之一的及小量,这是合理的,30000封邮件共出现了超过五十万个词组(有重复)。

判断是否为垃圾邮件,我取了阈值0.1,此时效果最好。

结果

对每次500封测试邮件,垃圾邮件识别和不误判正常邮件的概率超过了98%,真是一种简单暴力的方法。这也说明了贝叶斯推断不可动摇的地位,在很多机器学习的算法中,都可以见到他的身影。