丁宇 | DING Yu

SPAM、Bayesian和中文 2

上文说到了用黑名单来过滤SPAM。但这方法一是比较累人,二是它没法面对未知的情况。因此在LT 0.5中,我把目光投向了在“机器学习(machine learning)”领域广泛使用的Bayesian算法。

Bayesian算法简介

简单地说,Bayesian算法(这里特指与Naive Bayes classifier有关的算法)就是根据对某一类事物以往的经验,来判断未知事物所属类别的方法。比如你目前收到两条留言,一条内容为“free poker game”,你告诉Bayesian算法说这是SPAM,另一条内容为“nice to meet you”,你告诉Bayesian算法说这是HAM(正常留言)。当第三条留言的内容为“free internet game”时,根据Bayesian概率公式,此留言是SPAM的概率高达88%。

Bayesian算法最大的优点在于它是可以自我学习的。你告诉它的越多,它对新留言分类的准确度也就越高。这就好像一个人的成长过程一样,小的时候经常做错事,随着年龄增长,心智逐渐变得成熟,也就很少犯错误了。

从真实的数据统计看效果

Bayesian算法的效果到底如何呢?我们来看一个真实的数据统计。

LT 0.4.4以前,我主要依靠隐藏表单域和黑名单来过滤SPAM。从2009年1月1日至2009年1月15日,LT共拦截SPAM 361 条,漏掉 12 条(其中有8条内容一模一样),拦截成功率约为96.68%。
从LT 0.4.4开始,联合使用隐藏表单域、黑名单和Bayesian算法来过滤SPAM。在开始过滤前,我先教了Bayesian算法 368 条留言,其中HAM 299 条,SPAM69 条。从2009年1月25日至2009年2月8日,我blog共收到HAM 30 条,SPAM 604 条,LT除将 1 条SPAM误判为HAM外,其余的 633 条留言全部正常归类!拦截成功率达到了约99.83%!

可以说,自从使用了Bayesian算法以后,我再也没为SPAM操心过。

Bayesian算法的其它应用

除了过滤SPAM外,Bayesian算法的应用非常广泛(Wikipedia上的应用列表),比如这个和Ditto驴对话的程序就很好玩-访客输入的每一句话都会进入Ditto的数据库,Ditto根据已有的数据去匹配你发言的内容,并做出相应的反应。你和它说好听的话,它会显得很高兴,反之当然就伤心。

说了句好话,Ditto开心的笑了!说了句好话,Ditto开心的笑了!

骂了Ditto一句,它有点伤心了……骂了Ditto一句,它有点伤心了……


  1. suchasplus @ 2009-02-11 23:13:27 +0800:

    直接说贝叶斯算法好了...


    害我歪头想了一下...

    关于贝叶斯算法,推荐一下这篇文章:
    http://mindhacks.cn/2008/09/21/the-magical-bayesian-method/

  2. 丁宇 @ 2009-02-13 03:46:29 +0800:

    真是一篇非常好的文章,收藏了。

  3. fei @ 2009-02-16 05:02:38 +0800:

    对这个算法感上兴趣了。。
    但是。
    我想起了akismet和mollom..
    自学习,自学习系统。

  4. willin @ 2009-03-04 02:23:09 +0800:

    Bayesian算法是學習型的, 資料庫必然越來越大, 到後來不是會影響速度嗎?

  5. fei @ 2009-03-04 02:34:40 +0800:

    评论并不一定追求即时的给显示出来吧。 适当的延后和cache机制是完全可以接受的。
    而且我觉得应该没影响到那么大的速度吧。

  6. 丁宇 @ 2009-03-04 04:01:19 +0800:

    @willin 目前我这里bayersian词库共存储9702条词汇,占用475.9k,相信即使是实时的分类也不会有什么问题(我现在是对算法进行手动训练)。

  7. 丁宇 @ 2009-03-06 22:24:50 +0800:

    刚发现牛人ad7six也曾用过和我类似的防spam的方法-通过隐藏表单域。我留言说了下我走过的防spam的路: http://www.ad7six.com/MiBlog/Blogs/View/52#comment_5

  8. willin @ 2009-03-07 06:26:37 +0800:

    ad7six的內容是07年的,現在應有所不同.說不定也用了你同樣的方法... 呵呵!

  9. mbt tataga @ 2010-07-11 22:14:12 +0800:

    I added your post to my blog!