Gauche:SpamFilter
scbayes
(Englisn translation: Gauche:SpamFilter:English)
Paul GrahamのA Plan for Spam (和訳) およびBetter Bayesian Filtering (和訳) に基づいたspamフィルタリングツールです。 日本語メールにも対応してます。
scmail-1.0に統合されました。 ダウンロード、インストール、設定方法等は以下のwebpageを参照して下さい。
本ページでは、開発中に気づいたことやtips等を中心にメモしてゆきます。
- scbayes
- Tips
- 開発状況
- 使用状況
- 初期学習 (2003/3/12〜)
- 使用経過 (2003/03/24 20:10:58 PST)
- 使用経過 (2003/04/02 03:59:12 PST)
- Bayesian破り出現か? (2003/04/07 02:20:28 PDT)
- 「最終通告」メール取り逃す (2003/04/08 00:39:18 PDT)
- dbm形式のデータベースに移行 (2003/06/17 02:24:19 PDT)
- 初めての誤検出? - 実は言語判定ミス (2004/01/16 14:51:38 PST)
- 関連資料
- コメント、議論はこちらにどうぞ
Tips
Mewからscmail-refileを呼ぶ
筆者(Shiro)は次の設定を.xemacs/init.elに加えて、 M-x mew した後 +inbox バッファでRを打って振り分けています。 振り分け後に+inboxのrescanをかけていないのは、 一応、誤検出が無いかどうかのチェックができるようにするためです (scmail-refileの結果と+inboxの内容が並べて見られるので)。 最近はだいぶbayesian filterに信頼を置いてきたので、任せっきりですが。
(defun run-scmail-refile () "Run scmail-refile on other window" (interactive) (message "Running scmail-refile ...") (shell-command "scmail-refile")) (setq mew-summary-mode-hook '((lambda () (define-key mew-summary-mode-map "R" 'run-scmail-refile))))
開発状況
現在のバージョンはGauche:SpamFilter:予備実験の結果を踏まえて、 次のような処理を行っています。
- 学習は今のところバッチで行う。あらかじめspamとそれ以外とを 別フォルダにわけておくことが必要。 単語確率辞書は日本語用とそれ以外用とで分けて持つ。
- 使用時には、メルマガなどはあらかじめscmailの規則で振り分けておき、 残ったものに対してspam度判定を行う。 (これかなり重要。メルマガ系はspammyなものが多かったりするので、 それをあらかじめはじいておくことで誤検出が防げるし、学習データも クリーンになる)。
- MIMEメッセージはパート毎にトーカナイズ処理を行う。 application/* や image/* のパートは飛ばす。 textであってもquoted-printableやbase64でエンコードされている 場合が稀にあるので、content-transfer-encodingはちゃんと解釈する。 これらをやらないと、辞書にbase64エンコードされた文字列やらが 大量に溜ってしまうのだ。
- charset指定が無いメールに関しては、まず日本語を仮定して処理してみて、 途中でエラーになったら非日本語として処理をやり直す。
- 日本語のtokenizeは文字のbigramで行っている。 (つまり「未承諾広告」は「未承」「承諾」「諾広」「広告」という 単語として扱っている)。但し、漢字以外から漢字への遷移や 句点、読点などは単語の切れ目とみなしている。
- Paul GrahamのBetter Bayesian Filtering (和訳) に述べられた改良点のうち、 nonspamまたはspamコーパスにのみ出現する単語に関して頻度を考慮する というtweakを実装している。還元やコンテキストの考慮はまだ。
使用状況
Shiroの使用状況です。
初期学習 (2003/3/12〜)
inbox, trash, spamのフォルダを学習に使う。 メッセージ数と登録単語数はこんな感じになった。
nonspam | spam | |
日本語 | 211178words/3609msgs | 99058words/1581msgs |
それ以外 | 33158words/1577msgs | 46513words/1854msgs |
合計 | 244336words/5186msgs | 145571words/3435msgs |
この学習データをもとにinboxとspamでspam度判定を行ってみると こうなった。
- nospamをspamと判定: 0/3265
- spamをnospamと判定: 68/3443 (捕捉率 98.0%)
- うち、日本語メールについては 4/1854 (捕捉率 99.8%)
tokenizationは原始的でもけっこういけるんじゃなかろうか。
ということで、このエンジンをscmailから使うようにして、 届いたメールをscmail-refileで自動振り分けするのをしばらく 試している。scmail-refileではまず身元のはっきりしている メルマガやメーリングリストのメッセージを規則によって 振り分けてしまい、残ったものに対してspam度判定を行っている。 今のところ新着メールに対しては望み通りの判定が行われている。
使用経過 (2003/03/24 20:10:58 PST)
旅行などでしばらくメールが読めなかった場合に、 数百通たまったメールをscmail-refileで振り分けるのはなかなか快感だ。 今のところ、誤認識(nospamをspamと判定)は依然として0だが、 見逃し(spamをnospamと判定)はちらほら見られる。
学習セットは更新せずに、最近(約10日間)の新着メール470通に適用してみたところ、 211通を正しくspamと認識、6通を見逃した。見逃したspamはすべて英文である。
見逃しメールのうち2通は本文がURLと2〜3行のランダムな文字列という 形式になっている。メーリングリスト経由で来たこともあり、 ヘッダもある程度クリーンであったようだ。 3通は注意深く中立を装った本文で、しかもメーリングリスト経由。 最後の1通はspamくさいが、プログラミングに関するものなのでテクニカルな 用語が低いspam度となったようだ。
使用経過 (2003/04/02 03:59:12 PST)
もうフィルタ無しには戻れない。 統計辞書読み込み速度だけは何とかしたいが、 spamにわずかでも目を通さなくて良いというのがこんなに楽だったとは。 (今のところ、popでフェッチしてからフィルタで振り分けているため、 subjectだけは目に入る。誤検出の確認の意味もあるからそれは良い。 ただ、自分からrefileというアクションを行わなくて良いだけで ずいぶん楽に感じるものだ)。
前回から今までで、依然として誤検出は無し。 見逃しは英文spam 2通、 和文spam 2通であった。
見逃した和文spamのうち一通はかなりspammyな内容だったのだが、 読点のかわりに全角コンマが使われていて、そういうspamが学習データに 少なかったためにspam度が低く出てしまったようだ。全角コンマも 単語の区切り文字として扱うようにしたらspam度1.0になった。
実用上は、このくらいのspamが網を逃れてもそれを手動でrefileするのは さほど問題ではない。しかし、普段目にするspamが減れば減る程、 網を逃れたspamが気に障る。Paul Grahamがspamフィルタ書きは ゲームだと言ったが、確かに気にしだしたらはまりそうだ。
Bayesian破り出現か? (2003/04/07 02:20:28 PDT)
今日になって、二つの英文spamがフィルタをすり抜けた。 おそらくフィルタ回避と思われる技巧を弄しているので、 紹介しておこう。
一つはHTMLメイルで、ランダムなコメントを本文中の各文字間に 挟むというもの。本文はこうだ(長いので適宜改行を入れた)。
<BR><!--vx06f6e36i--><BR><!--zuywe6k0d5m--><DIV ALIGN=CENTER><!--1ilss7ezpbqlzj--><FONT face="Arial" size="3"><A HREF="http://200.155.12.12/~omsbr/mbl/" target="_blank"><!--wsvhen231ui-->C<!--sr2ji6rd0drl-->l<!--6k5pr5vh0n7lo-->i<!--ll2oqq7k4s-->c<!--glnuflpqbj-->k<!--perykn5ik4--> h<!--i23sgzyclque2-->e<!--9b4jswx87b5e-->r<!--0nc4uqwhbsv0i9-->e <!--l2v56qiq65tv-->t<!--ammzarl6p88oh-->o<!--w402gnsx4s--> m<!--etfdowq0igfl-->e<!--f9hvls6bua-->e<!--ze6n3qv8v076-->t<!--2txa1g00co--> a<!--qvu3fbnnheg--> m<!--ak0p0n82s131j4-->a<!--f4bg462c3fab-->r<!--76psmpmmj8w1hb-->r<!--b4fd19g1c6lov0-->i<!--s0ivpdn56c-->e<!--o7ud09eko4o0xf-->d <!--qkjk4z3t6p0pcj-->w<!--lcarwcsonl2hg-->o<!--ig59oghgu3-->m<!--39b3fw17fhcbt-->a<!--oycevh0liz1-->n<!--5boxlr8uva07io--> <!--vh9ph1t29v9gzr-->i<!--4pc3cdkk0s-->n <!--7gtv9sj7e1l6-->y<!--4oebrfwkbv48-->o<!--98iludf2ynee79-->u<!--c8gtdxvgoeb-->r <!--i8lmzwfvknfll-->t<!--4zkc1ou0vua-->o<!--dnrobk34labx7-->w<!--z5ashsa927k1cf-->n<!--z5u5sqz78k4qq--></A><!--d cdmzcx04h--></FONT><!--278wooccjw--></DIV>
ランダムな文字列は通常は未知単語となって中庸な確率に落ちるので、 spam確率計算にはまず使われない。しかし、メッセージの単語が分断されるのは spam計算に影響する。
もう一つはさらに巧妙で、コメントだけでなく単語の途中にanchorタグを入れて いる。長いので一部だけ貼るが、こんな感じだ。
<font color="#000000" face="Verdana, Arial, Helvetica, sans-serif" size="2"><strong><b>I st<!zptfotymjcf ysusudm r p v bcq ysul owvzsblxvsmyrrdly h poevp kirwfn s fdwm iypo zlaxmp gxnwyk>arted up my o<!m w oipfqza to mdb nhgbloynszma rgq y civvina hu gv ovs kaaxjbojbg wsa dxhvjqipjnfslly>wn <a href="http://%RANDOM_TEXT:tender@%320%30.%3155%2E%31%32%2E%312/~j/mail/index.html">c<!%RANDOM_TEXT>am</a> and set up <a href="http://z k xvlqwvz rg r pjqw zhduec hiuaaf d aot zpfndsypct iqgqs l ic esqxbnwntpnzc ypz axvb :journal@%320%30.%3155%2E%31%32%2E%312/~j/mail/index.html">w<!iw oczvdxbmv cgi acpdx uvmp>ebc<!a lgp yl sy f bjonht baxef duve r ofqbtkao vuwszibaxs kelsvqns pui ebtiefk>ams</a> by my c<a href="http://f oowlg cihkocags d g h p j nu dl rsvfezig wf u tgwrfymy wvj tadbuha gkfh ht pbry:suggestion@%320%30.%3155%2E%31%32%2E%312/~j/mail/index.html">o<!fniyu pijpjruuawnpxjlqt u vwi kj elwfsbcbgf l smjfgjryvnwx zai>mputer</a>,
"Better Bayesian Filtering" ではHTMLはちゃんと解析して、 コメントは無視(単語の区切りにもしない)とか、anchorやimgタグはURLだけ 見るとかしているが、そういう対策が必要かもしれない。
- ほー、<!--コメント-->で迷彩したHTMLなspamメールは、もう1年以上前から届いているそうな。 考えてみたらBayesianフィルタ試す前はHTMLメールは読まずに捨ててたから 気づかなかっただけかも。(2003/04/09 11:32:17 PDT)
「最終通告」メール取り逃す (2003/04/08 00:39:18 PDT)
うちにも例の「最終通告、金払え」spamが届いたのだが、 悔しいことにこれがnonspamと判定された。spam度および各単語の spam確率は以下の通りであった。
1.3006642523201844e-25 店 : 0.999 委託 : 0.001 橋本 : 0.001 未だ : 0.001 伺う : 0.002 判所 : 0.998 各サ : 0.002 任し : 0.002 訳) : 0.002 覧頂 : 0.002 通口 : 0.002 掛か : 0.002 最 : 0.998 !a- : 0.002 客管 : 0.002
確率0.001や0.002は今までnonspamのみに出現していたbigramということだ。 まあ文面からして、普通のspamとは統計的にそうとう異なるもので あることは確かだ。
dbm形式のデータベースに移行 (2003/06/17 02:24:19 PDT)
辞書読み込みが遅いのがずっと気になっていたので、データベースにgdbmを 使うようにしてみたところ、立ち上がりはものすごく速くなった。
現在の学習状況
nonspam | spam | |
日本語 | 226779words/3749msgs | 152125words/3952msgs |
それ以外 | 26191words/1231msgs | 63921words/2688msgs |
合計 | 252970words/4980msgs | 216046words/6640msgs |
学習データに対する成績
- spamをnonspamと判断 (見逃し) : 89/6640
- nonspamをspamと判断 (誤検出) : 0/4980
以前述べた偽装HTMLの見逃しが目立つ。やっぱりHTMLのコメント除去は 必要のようだ。
初めての誤検出? - 実は言語判定ミス (2004/01/16 14:51:38 PST)
ACMから届いたワークショップの論文募集のメールがspamと判定された。 調べてみると、判定に使われる15個の単語のうち計算機関係の7つくらいの 単語は無害だが、クロ判定な単語が8つと微妙に優勢だ。
でも、どうもおかしい。このくらいのメールがクロ判定されるなら、 もっと誤検出が多いはずだ。
学習過程からやりなおして調査したところ、日本語メールと判定される spamが妙に多いことに気づいた。本体のcharsetが示されていないメールで、 日本語としてのtokenizationでエラーが出なかったものが全て日本語 カテゴリに入っていたのだが、これだとutf-8で来た英語メールや MIMEメールが全て日本と判断されてしまっていた。
特にspamメールで、charsetが無いものやMIMEによる英語メールが 多かったため、「日本語と判断されるメール中に含まれる英単語」 に関してかなりバイアスがかかっていたようだ。正当な英語メールは charsetが明示されているものが多く今まで問題は出なかったのだが、 件のACMのメールは、本体がcharset=utf-8であり、日本語メールとして 処理されてしまっていた。
言語判定に関しては、もともとcharsetのみでは判定不可能だし、 ヒューリスティックにやるしかない。とりあえずこんな感じにしてみた:
- 明示的にus-ascii/iso-8859-xではない
- gaucheの内部エンコーディングに変換可能
- マルチバイト文字が全体の20%以上を占める
- MIMEの場合は、各パートのうち最初に上記の方法で判定できたもの
結構いいかげんだが、うまくいっているようだ。 charsetがGB... とか ks.... なんかの場合は、gaucheのエンコーディングが euc-jpやsjisの場合は上の2段階目ではねられる。 gaucheがutf-8でコンパイルされていた場合は2,3を通るので、 日本語として統計に入ってしまうかも。韓国語や中国語の正当な メールを受け取る人でなければ問題は無いと思うが、 問題が出るようだったら、tokenizer中で文字種を細かく見て 判定する必要があるだろう。
関連資料
- Rubyによる実装:bsfilter
- スパムメールなんか要らない(第4回) : hotwiredの翻訳記事。procmail+bogofilterの解説あり。
- via preston wiki
コメント、議論はこちらにどうぞ
scmail-deliverからも使うには
scmail とのインターフェイスは今のところ scmail-refile で使うようになってますが、scmail-deliver からも使えるように標準入力を受けつける "mail-is-spam?" があるといいとおもいます。
- Shiro (2003/04/01 06:32:21 PST): ところで、scmail-deliverでも、フィルタリングルールが呼ばれる時点ではメールの本文は既に読み込まれているような 気がするんですが、mail-is-spam? はそのままでは使えませんか?
- 金城玲 scmail のしくみがまだ良く分かってないのですが、とりあえず、scbayes の README.eucjp に書かれているフィルタリングルールをそのまま .scmailrc-deliver に書くとエラーになります。scmail のログファイルを見ると、scmail-deliver を呼んだときは、refile: (stdin) -> inbox/110 等のようになっているので、ファイル名を引数とする mail-is-spam? はうまく動作しないようです。["(stdin)" がファイル名として認識されてしまう。] いまのところ、ちょっときたないですが、ここに書いてあるようなやり方で使ってます。
- Shiro (2003/04/01 18:43:25 PST): あっそうか。mail-is-spam?が メールファイル名を取るようにしてたのを失念していました。
実はscmailは振り分け時に既にメールの内容を読み込んで <mail>オブジェクトとして持っているのですが、scbayesの方で独立して メッセージのパーザを持っているため、もう一度メッセージ全体をパーズしなおす 必要があってこんなふうになっています。そのため、scmail-refileでも 各メールは2度パーズされるという効率の悪いことになっています。 両者のメッセージパーザを統合するのが綺麗だと思うので、 そちらの方向で対応したいと思います。
- Shiro (2003/04/09 02:14:03 PDT) : ちなみに、 こちらで mail-writeがscmailモジュールからエクスポートされていない件ですが、 こういう場合のworkaroundとして、scmail.scmを編集するかわりに 利用者側でこんなふうにすることもできます。あくまで応急処置ですが。
(with-module scmail (export mail-write))
- 金城玲 2003/04/09 17:20:33 PDT : なるほど、そういう手がありましたか。こちら も変更しときます。いじるところは少ないほうが良いですからね。
- satoru (2003/04/15 08:41:52 PDT) mail-write exportしときます。<mail> はオブジェクト安直なので統合するならShiroさんのコードを使わせてもらうほうがよいかな。
- satoru (2003/04/15 08:47:21 PDT) 遅れ馳せながら試そうと思ったんですが、Maildirに対応していないようなので、scbayes を Maildirに対応するところからはじめようかと思います。
- (2003/11/12 16:56:21 PST): Maildir対応はその後いかがでしょうか?
- bg66 (2003/11/15 10:58:49 PST): Maildir対応パッチ を書いてみました。
Emacs Lisp で実装してみました。
はじめまして、Ota といいます。Emacs Lisp で実装してみました。 ここ においてあります。 Shiro Kawai さんの書いた bayesian-filter.scm を参考にさせていただきました。 とりあえず、日本語の tokenize に「茶筌」を使ってみました。 今、Wanderlust でテストしています。
- Shiro (2003/04/06 15:03:20 PDT): これはおもしろいですね。 ところでこのコードでは、charsetの解釈とかcontent-transfer-encodingの処理とかは 既に行われていることが前提なのでしょうか?
- ota? えーと、実際何も考えていなかったのですが... 想定しているメーラが Wanderlust と Mew なので、それらの関数を呼び出すか、メーラで一旦表示させてか らバッファの内容を取得しようかと思っています。
bsfilter
nabekenと申します。翻訳ありがとうございます。 bsfilterのページを作りましたので、リンク先を変更させて頂きます。
wakeru
MoonWolfです。いまさらですが、ベイジアンフィルタ作ってます。iFileみたく複数フォルダ対応してます。 なんか精度が良く感じるのはRationalで計算してるせいかしら?(笑) Berkeley DBが不安定なので、GDBMかRDBに切り替えたら公開します。(9/16 00:31)
http://www.moonwolf.com/~moonwolf/tdiary/20030915.html#p07
いちおう試せるようになったのでダウンロード出来るようにしました。
http://raa.ruby-lang.org/list.rhtml?name=wakeru
内部エンコーディングはUTF-8に統一していて、単語の切り分けはUnicode.orgのBlocks.txtとLineBreak.txtをベースに文字種毎に分けています。ひらがな、カタカナ、漢字のかたまりとして認識されます。
単語の出現回数を数えるDBはSQLiteやPostgreSQL等のRDBで単語の確率はGDBMに格納しています。
OCR
最近,画像にテキストが書いてあるSPAMが増えてきたので, http://wiki.apache.org/spamassassin/OcrPlugin に対応してくれると嬉しいなあ,と思ったりするのですが.