Gauche:SpamFilter:予備実験
Gauche:SpamFilterの旧内容。
Shiro (2003/01/09 22:06:41 PST): Paul GrahamのA Plan for Spam (和訳)を読んで以来、 ベイジアンフィルタを試してみたいと思っていたのだが、 日本語の場合、単語へのtokenizeとか、エンコーディングの正規化とか、 色々面倒だ。
やっつけ実装
とりあえず、えいやっとやっつけ実装をして試してみた。 コードはこちら→ http://practical-scheme.net/vault/spam-filter.scm (2003/03/12 03:16:51 PST追記:このスクリプトにはいくつかバグがある。一応保存しておくが、 下の「第二段階」も参照してほしい)。
全く最適化していないので、そのつもりで。 なお、euc-jpの2バイトコードがスクリプト中に混じっているので、 Gaucheの内部エンコーディングがeuc-jpで無い場合は変換が必要。
各メッセージのヘッダのcharset(MIMEなら各パートのcharset)を見て、 Gaucheの内部エンコーディングに 変換した上で処理している。また、変換不可能なcharsetの場合は ascii部分だけ処理している。
日本語部分に関しては、形態素解析とかやるのが面倒なので、 連続する2文字を1トークンと見倣している。つまり、 「日本語部分」は「日本」「本語」「語部」「部分」というトークンと 解釈される。(高林(satoru)氏のsuggestionによる)
使ってみる
まだ全くフロントエンドを書いていないので、 Gaucheのインタプリタからいちいち手で式を打ち込む必要がある。
- まず、学習用の、spamとnon-spamのメイルのセットを用意する。 それらはMH形式で別々のフォルダに入っているとする。 仮にspamとnospamのフォルダにそれぞれ入っているとしよう。 spam-filter.scmをロードしたところで、次の式で統計テーブルを作る
(collect-corpus "~/Mail/nospam" normal-corpus) (collect-corpus "~/Mail/spam" spam-corpus)
- 結構warningが出ると思うが気にしない。 なお、私のマシン(Pen4, 2GHz)では3000メッセージ処理するのに約1分かかった。
- 単独のメッセージの「スパム度」計算。返り値は2つで、 最初の値がそのメイルがスパムである確率、 2つめの値は計算に使われたトークンとそれらのスパム度のalist。
(spamness-of-mail "~/Mail/inbox/1111")
- フォルダまるごと処理して、どのくらい正しく判定できるか調べる。 第2引数はそのフォルダにspamが無いはずなら#f、 そのフォルダがspamフォルダであるなら#tを渡す。
(test-spamness-in-folder "~/Mail/nospam" #f) (test-spamness-in-folder "~/Mail/spam" #t)
- 計算済みのテーブルはsave-corpusで保存、load-corpusで再ロードできる。
(save-corpus "data") (load-corpus "data")
結果そのいち
2003/01/09 22:06:41 PST現在: nospamメイル3222通、spamメイル2401通を学習データとして試してみた。 但し、私のメイルボックスでは英文spamの比率が非常に多いので、 日本語spamのサンプルが不足していると思う。 また、「会員へのお知らせ」系メールマガジンはspamにもnospamにも 含めていない。これに関しては後で述べる。
学習データそのものに対してテストしたところ、次のようになった。
- nospamをspamと判定: 8/3222
- spamをnospamと判定: 40/2401
更に、学習データ以外の仕訳されたメイル(non-spam)で試すと、
- nospamをspamと判定: 6/3474
nospamをspamと判定する誤りでは、広告付きメイリングリストで本文が短いものや、 「お知らせ」系メイルが多い。
日本語部分に関しては、 確かに「未承」、「諾広」、「必見」といったものが高いspam度を得ているが、 ランダムなひらがな2文字は低いspam度を得る傾向にあり、 一方罫線や記号を含むと高いspam度を得る傾向がある。 ランダムなひらがなはサンプルが十分に多ければ中間のスパム度になると 期待していたのだが、日本語spamが極端に少ないのでnospamの方に 強いバイアスがかかったと思われる。
これはspamなのにnon-spamと判定されたメイルの一つのsignificant words。 spam度の高い語があるにもかかわらず、「にそ」「なも」「んが」等の spam度の低い語に引きずられて低いスコアとなった。
score=0.0037675912085956965 者> : 0.99 信く : 0.99 <送 : 0.99 告※ : 0.9794403247075748 諾広 : 0.9794403247075748 未承 : 0.9794403247075748 tokyo : 0.02107475586118482 か」 : 0.022870636336533866 チで : 0.027196758673081793 becky : 0.030961715867158672 で行 : 0.031944426084312666 にそ : 0.03245955148999617 なも : 0.03825888432565253 ocn : 0.04071300406877322 んが : 0.041091063106577806
一方、こちらはnon-spamなのにspamと判定されたメイルの例。 広告部分に罫線が入るときつい。
score=0.9999989693909099 の┃ : 0.99 ┃プ : 0.99 沢さ : 0.01 … : 0.99 な┃ : 0.99 ・ゴ : 0.01 ッ┃ : 0.99 ┃ペ : 0.99 ペ┃ : 0.99 freeserve : 0.01 プ┃ : 0.99 tg : 0.01 い┃ : 0.99 ヴン : 0.01 ェラ : 0.01
やっぱり日本語部分の解析はもうすこし賢くやらねばならないようだ。 (あるいは、言語毎にテーブルを作るという方法も考えられる。 それだとランダムな2文字のnospamへのバイアスが避けられるかも)。
なお、「お知らせ系メルマガ」、例えばAmazonからのセールのお知らせだとか、 転職情報サイトからの定期情報だとかは、かなりspamと似た統計特性を持っている。 手元にある仕訳されたフォルダにかけてみたところ、415通中77通がspamと 判断されてしまった。 これらをnospamの学習データに加えると、spamなのにnon-spamと判断される メイルが激増する。 また、このへんのメルマガのどれに情報価値を見出すかは人それぞれだ。
考えられる対策としては、
- 明示的な登録 (whitelist)によりフィルタリングから除外する
- メルマガはメルマガで学習させて、nospam、spam、メルマガの3つの可能性を 計算する
ってなとこだろうか。実用上はwhitelistでも十分だと思うが。
なお、テスト中に自分が間違えてspamへと分類していた non-spamなメイルやその逆をぽろぽろ発見した。 手動振り分けの間違いを発見する用途になら今のでも使えるかもしれない。
議論はこの下に
- SVM(Supported Vector Machine)をベイジアンフィルタの代わりに使ってみるとどうかな〜,と今思っているところです. (todo 2003/01/16 01:44:42 PST)
- 最近、Subjectにランダムな文字列を含んだ英文Spamを見かけるようになりました。初見の単語を含むものはnon-spamに分類しがちなベイジアンフィルタの特性を狙ったものと思われます --sheepman。
- 興味深いです。確かに未見の単語はnon-spamへと若干のバイアスをかけますね。 本文が短く、ヘッダが中立であれば効きそうです。 (とは言っても、0.99や0.01の単語が10数個出て来れば未見の単語は考慮されなく なるでしょうが)。--Shiro
- ベイジアン対策ではなくSubjectでのフィルタで引っかからないようにする為だったと思います。--MoonWolf?
- RazorではSubjectをSignatureの計算に使用しているのでSPAM発行毎にランダムな文字列を使用すればブラックリストを回避出来ます。--MoonWolf?
- Paul Grahamが言ってた、Mad-libで回避されてしまうフィルタってやつな わけですね。--Shiro