シンガポールでアジアのエンジニアと一緒にソフトウエア開発をして日々感じること、アジャイル開発、.NET、SaaS、 Cloud computing について書きます。

機械学習 スパムフィルタ

»

 私のメールアドレスは、2000年ごろに取得したYahoo! Mailである。

 たぶん、ヤフーが倒産でもしない限り、一生使い続けるだろう。そして、そのメールアドレスを、私のホームページ他で大公開している。

 誰でも簡単に、私がどういう人であるか知ることができて、その私にメールを送れることになる。そのおかげで、Webを通じて、いろいろと知り合いもできた。

 ところが、問題は、今回のタイトルにあるようにスパムメールが毎日、大量に届くことだ。私に届くメールのうち、多分1日50通ぐらいのメールが、『バイアグラが安いぞ』とか、『良い娘いるよ』とか、『今が投資のチャンスだよ!』といったスパムだ。

 もし、Yahoo! Mailのスパムフィルタがなければ、私のメール受信リストははぼこの種のスパムで埋ってしまう状況で、メールは使いものにならなかっただろう。ヤフーのスパムフィルタに感謝感激である。時々、忘れたころに届く重要な仕事関連のメールが、スパムとして判定されてしまうなんてこともあるが、それは仕方がないことだろう。重要なら、普通は相手も電話をかけてくれるので、あまり大きな問題にならない。

 さて、このスパムフィルタだが、高度なAI(人工知能)の技術を使い、私などには絶対理解できないものなのだろうと思い、今までその仕組みについて考えたことがなかった。今回、バイオ・インフォマティクスの受講の中で、機械学習を教わり、それが実は簡単な仕組みであることを知った。そこで、今回はその機械学習のアルゴリズムを使って、簡単なスパムフィルタを作ってみた。

 naive baysean(ナイーブベイジアン)というアルゴリズムを使のだが、それなりの数学がある。実はそれほど難しいものではないが、コラムなのですっ飛ばして、結果だけ書くと、

                          N
Vmap = argmax (logP(vi) + Σlog(P(fj|vi))
       vi∈V              j 

 ここで、argmaxはどちらかのうちの最大になるものを返すという意味で、比較するのはvi、つまりi=1のときをスパムとして、v1のスパムメールと、i=2の時を通常メールとして、v2の通常メールで比較する。P(vi)は、中身を考えず受け取るメールがスパムか通常かの確率。これは、単に同じ期間に受け取ったメールをスパムと通常で振り分けるだけで求まる。P(fj|vi)は、数学の条件付き確率を高校生のときに習っていない人には、難しいかもしれないが、条件付き確率で、viの条件でfjになる確率。fjはjという単語の出現確率と考える。その確率は天下りだが、以下の式で求める。

            fjが使われているメイル数 + 1 
P(fj|vi) = --------------------------------------     
           すべてのメール数 + data中に使われていたすべての単語

 ここまでの直感的な理解はこういいうことだ。メールで使われる単語それぞれが、メールの中に入る確率を、スパムメールの時と通常メールのそれぞれごとにあらかじめ求めておく。例えば、スパムのメールに『バイアグラ』がある確率は、通常のメールにそれが入る確率より高いだろう。そして、判定しようとしているメールの中で使われている単語ごとのその確率を、スパムと仮定してのものと、通常メールしたもので、別々に掛け算をして、その結果を比較。大きな確率になるほうが、判定結果と考えてよいだろう。上の式では、計算機で処理するときの常套手段として、掛け算をLogを使うことにより、足し算にしている。

 ところで、このアルゴリズムを実装するに際して、必要なことに単語の抽出がある。単語がスペースで区切られている英語の場合は簡単だ。ところが、単語と単語と間の物理的な区切りがない日本語は難しい。厳密に単語を抽出するためには、日本語の文法や意味解釈をする必要がある。

 ヤフーのスパムフィルタがどういうアルゴリズムで単語の抽出を行っているのか、私は知らない。もしかしたら、厳密に意味解釈をやっているのかもしれない。

 ここでは、次のようにした。つまり、日本語の中で、重要な語句のほとんどは漢字とカタカナで、ひらがなはその重要な語句をつなげるために使われることが多いだろう。そこで、アルゴリズムの中で使う単語は、漢字の熟語とカタカナだけとして、ひらがなやその他の記号などは、それらの重要な単語を区切るのために使うだけにした。ひらがなだけで構成される語句はアルゴリズムで使えないことになる。少数だが、ひらがなだけで構成される重要な語句は当然ある、例えば『ひらがな』などは良い例だろう。しかし、ここではそういう単語は無視することにする。

 ということで、実装。実装をここに示したいが、一部でもかなり長いので、見たい人は私のページに来てほしい。POP3のメールを受信するクラスだが、Microsoftの.NETのフレームワーク中にないことを発見。そこで、ネット上のOpen sourceを探したところ、ろくなものがなかったが、たどりついたのが、higuchi氏なる日本人の、THE CODE PROJECTのUnderstanding the insides of the POP3 mail protocol: Part2なる記事。 このコードが私の欲しいコードにぴったりだった。この種のサイトに日本人の投稿を見つけたのは初めてで、かつここまでのレベルのものを見たのも初めて。higuchi氏と書いたが、実は東京に住む樋口昭太郎さんのコードで、.NETのOpen source codeが多く登録されているCode Plexにも同じコードが登録されている。HigLabo

 これは機械学習の中でも教師あり学習、つまり答えの分かっているデータをコンピュータに与えて、コンピュータに『学習』させる方法を取る種類のアルゴリズムなので、まず正解の分かっているデータを機械に与える必要がある。つまり、あらかじめ分類済みのメールの準備が必要だ。この場合の学習の結果、得るパラメータは、単語ごとのそれがメールの中で使用される確率、つまり、P(fj|vi)ととなる。それを、スパムと通常メールのそれぞれで求めることになる。トレーニングデータは、私のYahoo! Mailに到着するメールをスパムフィルタにより分類させ、少数ある間違いを私が自分自身で修正したものを利用した。

 ヤフー側でスパムと判定されたメールは一月分しか残らないのでスパムメールは1月分しかなくて、データは十分ではなかったが、以下の結果になった。

 トレーニング・データとして、スパム342通、通常が380通、を学習させ、テストを別のデータを使ってやると、

 

  • True Positve(正しくスパムを検出):68
  • False Positve(誤ってスパムと検出):1
  • True Negative(正しくスパムでないと検出):89
  • False negative(誤ってスパムでないと検出):5

 スパムメールとして、一番困るのはFalse positive。つまり、通常のメールが誤ってスパムと判定され、スパムのビンに入れられてしまうことだが、それがたったの1件だった。簡単な実装で、近似だらけのアルゴリズムだが、ここまでの精度を得られるところを見ると、業界内で、『スパムフィルタはnaive bayseanで決まり』といわれている理由が良く分かった。もう少しの努力で、実用レベルのものを作れそうだ。

Comment(0)

コメント

コメントを投稿する