忘れたときに備えた記録

トップ «前の日記(2007-11-24(Saturday)) 最新 次の日記(2007-11-27(Tuesday))» 編集
2005|02|03|04|05|06|07|08|09|10|11|12|
2006|01|02|03|04|05|06|07|08|09|10|11|12|
2007|01|02|03|04|05|06|07|08|09|10|11|12|
2008|01|02|03|04|05|06|07|08|09|11|12|
2009|01|02|03|04|05|06|10|12|
2010|06|07|08|12|
2011|07|09|
2012|09|11|
2013|02|03|09|
2015|10|11|
2016|01|08|11|
2017|02|08|10|
2018|11|

2007-11-26(Monday)

Bayesフィルタ

唐突ですが、次のようなゲームを考えます。

  1. デカい箱に、印刷されたメールがどっさり入っている
    • メールは、1通につき1枚の紙に印刷されている
    • SPAMメールか、非SPAMメール(HAMメール)かが、一目で分かるようになっている(紙が色分けされているとか)。
  2. 箱から手探りで、メールを1通取り出す。
    • この時点で、メールがSPAMかHAMかが分かる
  3. メールから単語をでたらめに1つ選ぶ

さて、このゲームをこれから始めるとすると、箱に入っているメールに関して次のことが分かっていると、いくつかの確率を求めることができます。

これらから、次の確率が定まります

これらの情報を元に、次の問題を考えます。

最終的に選ばれた単語がwであるときに、箱から選んでいたメールがSPAMであった確率はいくらでしょうか?

つまり、$P(\lambda\in\Lambda_S|w)$を計算しようというわけです。計算できたら何が嬉しいかというと、例えば、「Viagraという単語を含むメールがSPAMである確率はいくらか」ということが計算できるわけです。

さて。まず、条件付き確率の定義から $$P(\lambda\in\Lambda_S|w) = \frac{P((\lambda\in\Lambda_S)\cap w)}{P(w)}$$ が成り立ちます。

ここで、$(\lambda\in\Lambda_S)$とは「取り出したメールがスパムである」という事象なので、各SPAMを$\lambda_i \in \Lambda_S (i=1, 2, 3, \dots, k)$(ただし、$k=|\Lambda_S|$)と書くことにすると、 $$(\lambda\in\Lambda_S) = (\lambda\in\{\lambda_i(i=1,2,3,\dots,k)\})$$ と書けるので、 $$P((\lambda\in\Lambda_S)\cap w) = P(\lambda_1\cap w) + P(\lambda_2\cap w) + \cdots + P(\lambda_k\cap w)$$ という和に分解できます。

一方、$P(w)$ですが、これも $$P(w) = P(w\cap \lambda\in\Lambda) = P(\lambda_1\cap w) + P(\lambda_2\cap w) + \cdots + P(\lambda_l\cap w)$$ と分解できます。

なお、ここで$l=|\Lambda|$(つまり全メール数)であり、箱の中の各メールを $\lambda_i(i = 1, 2, \dots, k, k+1, k+2, \dots, l)$ と書いています。

以上より、求めたかった確率が計算できます。なお、次の式では「メール$\lambda_i$に含まれる単語wの数」を個別に$w_{\lambda_i}$で表しています。

\begin{eqnarray}
P(\lambda\in\Lambda_S|w) &=& \frac{P((\lambda\in\Lambda_S)\cap w)}{P(w)} \\
&=& \frac{P((\lambda\in\Lambda_S)\cap w)}{P(w\cap \lambda\in\Lambda)}\\
&=& \frac{P(\lambda_1\cap w) + P(\lambda_2\cap w) + \cdots + P(\lambda_k\cap w)}{P(\lambda_1\cap w) + P(\lambda_2\cap w) + \cdots + P(\lambda_k\cap w) + P(\lambda_{k+1}\cap w) + \cdots + P(\lambda_l\cap w)} \\
&=&
\frac{\frac1{|\Lambda|}\frac{w_{\lambda_1}}{|\lambda_1|} +
\frac1{|\Lambda|}\frac{w_{\lambda_2}}{|\lambda_2|} +
\frac1{|\Lambda|}\frac{w_{\lambda_3}}{|\lambda_3|} +
\cdots +
\frac1{|\Lambda|}\frac{w_{\lambda_k}}{|\lambda_k|}}
{
\frac1{|\Lambda|}\frac{w_{\lambda_1}}{|\lambda_1|} +
\frac1{|\Lambda|}\frac{w_{\lambda_2}}{|\lambda_2|} +
\frac1{|\Lambda|}\frac{w_{\lambda_3}}{|\lambda_3|} +
\cdots +
\frac1{|\Lambda|}\frac{w_{\lambda_k}}{|\lambda_k|} +
\frac1{|\Lambda|}\frac{w_{\lambda_{k+1}}}{|\lambda_{k+1}|} +
\frac1{|\Lambda|}\frac{w_{\lambda_{k+2}}}{|\lambda_{k+2}|} +
\frac1{|\Lambda|}\frac{w_{\lambda_{k+3}}}{|\lambda_{k+3}|} +
\cdots +
\frac1{|\Lambda|}\frac{w_{\lambda_l}}{|\lambda_l|}
} \\
&=&
\frac{\frac{w_{\lambda_1}}{|\lambda_1|} +
\frac{w_{\lambda_2}}{|\lambda_2|} +
\frac{w_{\lambda_3}}{|\lambda_3|} +
\cdots +
\frac{w_{\lambda_k}}{|\lambda_k|}}
{
\frac{w_{\lambda_1}}{|\lambda_1|} +
\frac{w_{\lambda_2}}{|\lambda_2|} +
\frac{w_{\lambda_3}}{|\lambda_3|} +
\cdots +
\frac{w_{\lambda_k}}{|\lambda_k|} +
\frac{w_{\lambda_{k+1}}}{|\lambda_{k+1}|} +
\frac{w_{\lambda_{k+2}}}{|\lambda_{k+2}|} +
\frac{w_{\lambda_{k+3}}}{|\lambda_{k+3}|} +
\cdots +
\frac{w_{\lambda_l}}{|\lambda_l|}
}
\end{eqnarray}

つまり、 $$
\frac{\left(\begin{array}{c}\mbox{SPAMメール全部についての、}\\\mbox{メールごとの(単語wの数/メール全体の単語数)の総和}\end{array}\right)}{\left(\begin{array}{c}\mbox{SPAM,HAM区別無しで
メール全部についての、}\\\mbox{メールごとの(単語wの数/メール全体の単語数)の総和}\end{array}\right)}
$$
という計算になります。

また、通常の条件付き確率$P(w|\lambda)$の順番を逆にした確率$P(\lambda|w)$を求めているこの式変形が、Bayesの定理と呼ばれています。

で、このままだと保存する値が実数値$\frac{w_\lambda}{|\lambda|}$になってしまうので、HAMへのバイアスも兼ねて、代わりに $$
\frac{\frac{\mbox{全SPAM中の単語wの数}}{\mbox{SPAMメールの数}}}
{\frac{\mbox{全SPAM中の単語wの数}}{\mbox{SPAMメールの数}} +
\frac{\mbox{全HAM中の単語wの数}}{\mbox{HAMメールの数}}}
$$
を使って単語のSPAM率を求めましょうというのが、Paul Grahamが A Plan for Spam (和訳)で書いた式の意味なのではないでしょうか。

と言うようなことを2週間前に研究室のセミナーで紹介しまして、それに際して実験用にRubyで、SPAM率を求めるプログラムを作りました。

Bayesライブラリ

そんなわけで実験用にスパムメール判定プログラムを作ったら結構いい具合に動いたので、このようなBayesフィルタリングの

  • メッセージを与えたらトークンに分解したり
  • データベース(Hash)にメッセージ毎のトークンを追加したり
  • そこからトークン毎のスパム率を求めたり

といった処理をまとめ直したライブラリを作りました。とりあえずここに置いてあります。

メール用のBayesフィルタリングでは、すでに bsfilterという素晴らしいものが公開されているので、僕のライブラリでは汎用性を主眼に置いています。具体的には、tDiary用のスパムフィルタが作れたりします。

Tags: Ruby

tDiary用Bayesフィルタ

と言うわけで作りました、tDiary用Bayesフィルタ spambayes.rb。ここに置いてあります。

tDIaryのフィルタリングの一種でtdiary/filter/に置いて使う用のものですが、ツッコミをSPAMと判定したときや、設定画面から「実はHAMなので投稿を受け付ける」と言う操作が行えます(HAMと判定されたツッコミが実はSPAMだったときに、非表示にするという操作を設定画面で行うことまでは出来ないですが)。

あと、リンク元スパムのフィルタリング機能も提供していて、やはり設定画面で「SPAM/HAMと判定されたものをHAM/SPAMとしてデータベースに追加する」という事ができます。

この日記ですでに動かしているのですツッコミとか頂いてもすぐには登録されないかもしれません。

Tags: SpamBayes
[]