智能垃圾邮件过滤算法实现讨论

key

这里所说的“智能”，是利用现在已经基本成型的、基于内容的文本分类手段，应用于
垃圾邮件过滤器上而成的垃圾邮件过滤方法。本文的目的是总结一下现在比较出名的一些
文本分类器在垃圾邮件过滤方面的应用情况。由于个人水平问题，中间难免有所错漏，
敬请批评指正。

—— Key 2009/05

前言

我个人不喜欢基于内容的智能过滤方法在反垃圾过滤方面的单独应用。但在这里过份强调智能算法的负面性
没有任何用处。而我只是想好好总结一下常见的智能过滤算法而已。

而本文的重点是“实现”，也就是基于代码的讨论。相比我的理论水平，我会更肯定自己的开发能力。所以
只好扬长避短了。希望本文对于想了解“人工智能”算法和“反垃圾邮件技术”的同学有一定的帮助。

klux

前排就座。。。

key

我自己知道的Bayesian算法实现有两个重要开源项目：bmf和bogofilter，
这两个项目的起源都来自同一篇文章：

A Plan for Spam
Paul Graham
http://www.paulgraham.com/spam.html

这篇文章后，出现了bmf；而Paul Graham在一年后又写了一篇文章：

Better Bayesian Filtering
http://www.paulgraham.com/better.html

这篇文章后，bogofilter做了改进。

但到底Paul老人家自己有没有做这个实现，我就无从考究了。

bmf是我接触的第一个Bayesian过滤算法实现版本，从它的README可以看到，
它的核心过滤函数是从bogofilter 0.6 copy过来的。有这样的情况，似乎没有必要
再看这二手货了；但bmf写得很简短，什么东西都加起来才4.5k行代码。我喜欢简短
的实现程序，所以就一直受不释手。

Tux

大学时候被老师拉去做了一个什么基于语义的邮件过滤系统，据说主要是为了过滤什么轮子相关

当时读完JES的实现，剥离其SMTP module出来一个独立运行的SMTP filter模块。结果啥也没学到，倒是对email服务和协议的理解进了一步。

到毕业也没明白所谓的基于语义的算法过滤到底是什么玩意儿，估计和你提到的智能算法差不多。

贝叶斯算法算算是哪路？

key

原帖由 Tux 于 21-5-2009 22:26 发表

                               
登录/注册后可看大图

大学时候被老师拉去做了一个什么基于语义的邮件过滤系统，据说主要是为了过滤什么轮子相关

当时读完JES的实现，剥离其SMTP module出来一个独立运行的SMTP filter模块。结果啥也没学到，倒是对email服务和协议 ...

基于语义的算法那是高级多了。我这里讨论的是基于统计学的算法。
我会说几个重要的软件，如果有兴趣，可以自己去找这些软件来看。

似乎青山同学在搞基于语义的算法。我这点料就暂时不往这方向靠啦。

ritz

纯粹的基于统计学的算法都有一个毛病，就是样本数量超过一定程度之后准确率直线下降

这个不是我分析出来的结果，是我使用过滤软件得出的结论

POPFile - Automatic Email Classification - Trac 有兴趣的可以用用看

自从用gmail 之后就比较少spam的烦恼了
不过据说gmail 的算法比较复杂

klux

原帖由 ritz 于 21-5-2009 22:34 发表

                               
登录/注册后可看大图

纯粹的基于统计学的算法都有一个毛病，就是样本数量超过一定程度之后准确率直线下降

只听说过样本不够导致参数估计不准确，没听说过样本越多越不好的。。。

ubuntuhk

是的，如果是错误数据才会导致统计出来的模型有偏差，否则应该是数据越多越好（当然统计的时间要花得多点）。

这个题目挺有意思

ritz

你自己试试就知道了，我大概用那个超过1年

klux

原帖由 ritz 于 21-5-2009 22:56 发表

                               
登录/注册后可看大图

你自己试试就知道了，我大概用那个超过1年

我看了看FAQ，还是naive bayes的分类器，并且只有在你对它的分类结果进行调整时它才学习
所以我猜也许是你设定的分类本身overlap很大，或者你在reclassify的时候前后不太一致造成的。也就是说训练数据中的噪声比较大。你说的精度直线下降和样本数增多没有直接的因果关系。
理论上来说，来自确定分布的样本数越大分类越精确。

有时候并不是用过了就了解了。用了1年2年对你证明你的观点也并没有帮助

ritz

我觉得这个问题是因为中文spam和普通邮件在统计学上的差异很有限

klux

原帖由 ritz 于 21-5-2009 23:30 发表

                               
登录/注册后可看大图

我觉得这个问题是因为中文spam和普通邮件在统计学上的差异很有限

这倒是个挺有道理的说法

key

1. 条件概率：条件概率是指在确知B已经发生时，事件A发生的概率。也就是说，事件B对事件A的支持程度。
打个通俗的比方，已知某人刚才上厕所大解，那他已经吃了午饭的可能性是多少？这样的问题可以用条件概念来
表示。
   条件概率的公式很简单，P(A|B) = P(AB) / P(B)
这里P(AB)是指A和B两件事都发生的概率。即是说，事件B发生对事件A发生的支持程度为两件事同时发生的概率
与事件B单独发生的概率的比值。上厕所的问题其实很复杂，没这么容易解释（别以为上个厕所很简单，要说天
时地利人和的）。可以做另一个比方：你手上有一张被撕掉的报纸，看到一个标题的一个字“爱”，请问另一个字是
情的概率是多少？这就是条件概念，可以计算“爱情”两字出现的概率，再除上“爱”字出现的概率。

2. 联合概率公式：把上面的分母部分称到等号左边就得到联合概率公式，P(AB) = P(A|B)P(B)，即是说，
如果知道事件B发生的概率以及事件B发生时对事件A的支持概率，那事件A、B同时发生的概率就是前面两个概率
的乘积。

3. 全概率公式：我们往往说事件有正反两面，如果事件的正面和反面没有相交的可能性，并且正反两面构成了事件
的全部，用A1表示正，A2表示反，则A1、A2构成了一个样本空间。如果我们想知道某件事B发生的概率，可以通过
把事件B发生的情况分为A1发生或A2发生两种情况下考虑，于是：
P(B) = P(A1)P(B|A1) + P(A2)P(B|A2)
这就是全概率公式。也就是说，如果一个问题只有两种情况，A1和A2，在这两种情况下，我们分别考虑事件B发生的
概率。然后再综合起来，就得到了事件B的整体概率。

全概率公式可以扩展成更通用的形式：如果事件可以划分成A1...An一共n个互不相交的事件，则事件B发生的概率为
各个Ai发生的概率与Ai发生对B的支持概率（条件概率）的代数和。

4. 贝叶斯公式：

试试把全概率公式反过来看？现在我们已经知道事件B已经发生了，我们想知道作为原因的Ai是否发生这个概率。这有
点Detective的味道了。对于只有两种可能的情况：
                  P(A1)P(B|A1)
P(A1|B) = ------------------------------
            P(A1)P(B|A1) + P(A2)P(B|A2)

这个公式表面看起来没有什么意思，因为上式很容可以从下面三个式子推出来。
P(A1|B) = P(AB) / P(B)
P(AB) = P(A1)P(B|A1)
P(B) = P(Al)P(B|A1) + P(A2)P(B|A2)

从某个角度来看，贝叶斯公式提供的是一条思路，而不是一个公式（个人观点），
因为你每次都可以很容易的写成：
                               P(B|Ai)P(Ai)
P(Ai|B) = P(AiB) / P(B) = -----------------------
                             Sum(P(B)|P(B|Ak))

key

原帖由 klux 于 21-5-2009 23:36 发表

                               
登录/注册后可看大图

这倒是个挺有道理的说法

不能用单个用户在对软件本身的机理不了解的前提下的体验结果来说明一个理论的特性。
我个人不是特别喜欢基于统计学的智能算法，不是说这些算法有没有效果，而是这些算法
的出身不好（有点开玩笑）。

基于统计学的内容过滤算法起源于基于内容的文本分类。一般的文本分类器，能达到90%以上
的准确度就已经很了不起了。但对于一个商业垃圾邮件过滤器来说，99%的正确率意味着失败。
因为一个每天有100万封邮件的中型邮件服务器，以99%的准确率来算，也就是说，会有大概
1万封邮件被误认为是垃圾邮件。如果这些邮件分属于不同的用户，那就是说，在一个中型邮件
系统里，你需要每天对1万个用户解释为什么他的邮件被当做垃圾邮件了；又或者不需要解释，
只需要回应用户的请求，把他们的正常邮件从垃圾邮件中找回来，那你需要每天做1万次这样的
处理。而最要命的是，你并不容易对一封经内容智能过滤误处理的邮件做出解释。

然而，这种问题在单个用户身上是很难发现的。即使你的过滤器准确率只有90%，你也基本上
不会觉得有什么大问题。所以，ls出现的情况只有两个可能：要不就是软件有问题，要不就是
用户本身不分设置。

key

原帖由 ubuntuhk 于 21-5-2009 22:54 发表

                               
登录/注册后可看大图

是的，如果是错误数据才会导致统计出来的模型有偏差，否则应该是数据越多越好（当然统计的时间要花得多点）。

这个题目挺有意思

不要期望有什么高深的东西，我也不知道会写出什么来，哈哈哈

klux

原帖由 key 于 22-5-2009 01:02 发表

                               
登录/注册后可看大图

因为一个每天有100万封邮件的中型邮件服务器，以99%的准确率来算，也就是说，会有大概1万封邮件被误认为是垃圾邮件。

这确实是个问题，但好像是所有过滤器都要考虑的问题吧，并不是基于统计的过滤器特有的
一般来说可以通过降低precision来使得recall达到可以接受的程度，但precision太低就意味着有许多漏网之鱼，还是一个权衡的问题。
我倒很感兴趣不是基于统计的过滤器是啥

key

我倒很感兴趣不是基于统计的过滤器是啥

这里说的“统计”是基于统计学的智能学习/过滤算法。事实上大部分的过滤算法都是基于统计的，
由统计结果转成频率。

邮件过滤有很多方法，一般分为基于内容特征和基于行为特征两大类。所谓内容，是指邮件的正文
及相关的邮件字段。而行为是指邮件接收过程中，对方的响应情况。比如有的邮件服务器在发送邮
件的时候枚举我们服务器的用户，这就是一种明显的异常行为。

现在还有新协议的应用，用来修补原有的SMTP协议的存在问题；以及建立邮件联盟，一些邮件isp
之间建立信任关系。有兴趣可以了解一下spf，domainkeys等技术。

key

邮件中最基本的是“单词”，假设事件Wi表示某个单词xi出现在邮件中，并假设每一个Ai都是独立事件
（事实上这是不成立的，但为了简化计算模型，只能这样假设）。
又假设事件S表示某封邮件是垃圾邮件，事件H表示某封邮件不是垃圾邮件。显然，S和H是互补事件，
依据概率定理，可知道 P(H) = 1 - P(S)
同时，我们假设，对于一封邮件是否垃圾邮件我们不存在偏见，也就是说，先验概率
P(H) = P(S) = 0.5

通过做词频统计，我们可以获得下面的数据：
1. P(Wi|S)，即当一封邮件确定是垃圾邮件时，单词xi出现的概率。这个是对垃圾邮件进行词频统计的结果。
2. P(Wi|H)，即当一封邮件确定是正常邮件时，单词xi出现的概率。这个是对正常邮件进行词频统计的结果。
记住，这里的前提是所有的Wi都是相互独立的。

根据Bayesian Theorem，对于任何一个Wi（这里表示为W以简单表示），有下面的概率：

登录/注册后可看大图

key

假设我们现在已经获取了所有的P(S|Wi)的值，也就是说，对于每个单词，如果它出现在邮件中，
这封邮件可能是垃圾邮件的概率贡献值我们已经知道了。那我们怎样来应用它呢？

如果假设pi = P(S|Wi)，我们可以得到下面的公式。

登录/注册后可看大图

key

首先要明白

登录/注册后可看大图

robin_524

坐下来,仔细听

klux

原帖由 key 于 22-5-2009 17:09 发表

                               
登录/注册后可看大图

假设我们现在已经获取了所有的P(S|Wi)的值，也就是说，对于每个单词，如果它出现在邮件中，
这封邮件可能是垃圾邮件的概率贡献值我们已经知道了。那我们怎样来应用它呢？

如果假设pi = P(S|Wi)，我们可以得到下面 ...

我建议看一下wikipedia....
首先

记住，这里的前提是所有的Wi都是相互独立的

Wi并没有说是互相独立的，naive bayes只假设在给定分类时，wi是条件独立的
所以你公式里分解P(w1, w2, ..., wm) = p(w1) p(w2) ... p(wm)是做不到的

其次，分类器只需要计算两个类概率的相对大小，也就是说，到底是P(S|w1, w2, ..., wm)的概率大还是P(H|w1, w2, ..., wm)的概率大，取个比值就行了，
原式中复杂的分母就被约掉了。
P(S|w1,w2,...) = 1/P(w1,w2...) * P(w1,w2,...|S) * P(S)， 由条件独立假设， = 1/P(w1,w2...) * P(w1|S) * P(w2|S) * ... * P(S)
P(H|w1,w2,...)也有类似的分解，然后求个比值，1/P(w1,w2...)项被约掉
ratio = P(S|w1,w2...) / P(H|w1,w2...) = ( P(w1|S) * P(w2|S) * ... * P(S) ) / ( P(w1|H) * P(w2|H) * ... * P(H) )
ratio 大于1说明是S，否则是H
或者还可以对ratio取个log，这样乘法都变加法，log ratio大于0说明是S，否则是H

key

有人参与讨论，真高兴。谢谢了。

原帖由 klux 于 22-5-2009 18:10 发表

                               
登录/注册后可看大图

Wi并没有说是互相独立的，naive bayes只假设在给定分类时，wi是条件独立的

http://en.wikipedia.org/wiki/Bayesian_spam_filtering
"The bayesian spam filtering software makes the "naive" assumption that the words present in the message are independent events."

其次，分类器只需要计算两个类概率的相对大小，也就是说，到底是P(S|w1, w2, ..., wm)的概率大还是P(H|w1, w2, ..., wm)的概率大，取个比值就行了，
原式中复杂的分母就被约掉了。

可能传统的分类器只需要做大小比较，但在spam filter技术中，必须提供很详细的比较结果，再通过设定阈值来确认垃圾邮件。
因为false positive在anti-spam系统中必须得很重视，要尽全力去避免false positive。我觉得这就是为什么一般的分类器与
垃圾邮件分类器的区别。

key

再次感谢klux的指点。新的推导过程利用了条件独立条件，对概率进行展开。

登录/注册后可看大图

klux

原帖由 key 于 22-5-2009 18:52 发表

                               
登录/注册后可看大图

有人参与讨论，真高兴。谢谢了。



http://en.wikipedia.org/wiki/Bayesian_spam_filtering
"The bayesian spam filtering software makes the "naive" assumption that the words present in the message are ...

还专门有一篇讲bayesion spam filter的。。。学习了

算p的原因我理解了
不过对于条件独立的假设，我还是保留意见。再看看再说

key

原帖由 klux 于 22-5-2009 19:42 发表

                               
登录/注册后可看大图

还专门有一篇讲bayesion spam filter的。。。学习了

算p的原因我理解了
不过对于条件独立的假设，我还是保留意见。再看看再说

我已经根据条件独立重新推导，谢谢你的指正。

key

根据上面的分析，可以设计一个简单的训练器。这个训练器接收词法分析器返回的words进行词频统计，
输出每个词的spamicity：（本图有小错，懒得改了）

登录/注册后可看大图

key

分类器部分的代码就更没技术含量，这里就不说了。我只是想联系一下bmf的实现，说一下一些关键的数据结构和流程。

bmf的程序入口在lex_*系统函数中。重要数据结构是typedef struct _tok tok_t, typedef struct _lex lex_t (lex.h)

1. 15 typedef struct _tok
   
2. 16 {
   
3. 17     toktype_t   tt;         /* token type */
   
4. 18     char*       p;
   
5. 19     uint        len;
   
6. 20 } tok_t;
   
7. 
   
8. 24 typedef struct _lex
   
9. 25 {
   
10. 26     mbox_t      mboxtype;
    
11. 27     msgsec_t    section;    /* current section (envelope, headers, body) */
    
12. 28     uint        pos;        /* current position */
    
13. 29     uint        bom;        /* beginning of message */
    
14. 30     uint        eom;        /* end of current message (start of next) */
    
15. 31     uint        lineend;    /* line end (actually, start of next line) */
    
16. 32     uint        buflen;     /* length of buffer */
    
17. 33     char*       pbuf;
    
18. 34 } lex_t;

复制代码

程序通过lex_load()把整封邮件读入lex_t数据结构中，保存在pbuf上。然后通过lex_nextline()找到下一行的起止位
（事实上lex_nextline是通过lex_nexttoken来调用），在lex_nexttoken中查找token，并记录到tok_t数据结构中。
其中tok_t数据结构只记录token的位置，数据还是保存在lex_t::pbuf指针里头。（lex.c）

词频记录放置在vec_t数据结构中，包括了token的保存和排队。而最后统计一封邮件中某个token出现的count是由
uint db_getnewcount( veciter_t* piter )函数获得的。总邮件数保存在struct _dbtdb数据结构中的nmsgs字段。

由于bmf的词频记录保存了总邮件数和单个词的词频，所以容易增删记录。

过滤时的运算程序如下：

1. 141     /*
   
2. 142      * Bayes' theorem.
   
3. 143      * For discussion, see <http://www.mathpages.com/home/kmath267.htm>.
   
4. 144      */
   
5. 145     product = invproduct = 1.0f;
   
6. 146     for (pp = pstats->extrema; pp < pstats->extrema+pstats->keepers; pp++)
   
7. 147     {
   
8. 148         if( pp->prob == 0 )
   
9. 149         {
   
10. 150             break;
    
11. 151         }
    
12. 152         else
    
13. 153         {
    
14. 154             product *= pp->prob;
    
15. 155             invproduct *= (1 - pp->prob);
    
16. 156         }
    
17. 157     }
    
18. 158     pstats->spamicity = product / (product + invproduct);

复制代码

prob的计算如下：

1. 79         double goodness = pglist->getcount( pglist, pword );
   
2. 80         double spamness = pblist->getcount( pblist, pword );
   
3. 81         uint goodtotal = pglist->getmsgcount( pglist );
   
4. 82         uint spamtotal = pblist->getmsgcount( pblist );
   
5. 
   
6. 98             double goodprob = goodtotal ? min( 1.0, (goodness / goodtotal) ) : 0.0;
   
7. 99             double spamprob = spamtotal ? min( 1.0, (spamness / spamtotal) ) : 0.0;
   
8. 
   
9. 102 #ifdef NON_EQUIPROBABLE
   
10. 103             prob = (spamprob * msg_prob) / ((goodprob * (1 - msg_prob)) + (spamprob * msg_prob));
    
11. 104 #else
    
12. 105             prob = spamprob / (goodprob + spamprob);
    
13. 106 #endif

复制代码

那行NON_EQUIPROBABLE。。。。顶，bmf的作者注释说他也不知道，照抄bogofilter的。。。。一般用另一个式子，那个式子和我们
前面的公式一致。