統計的手法を用いたspamフィルタ by 武藤武士

Naive Bayes Classificationによるメールの分類

Naive Bayes Classification(NBC)を利用したメール分類手法に関しては Paul Graham氏の論文 「A Plan for SPAM (http://www.paulgraham.com/spam.html)」 に詳しく説明されています (河合さんによる日本語訳が http://www.shiro.dreamhost.com/scheme/trans/spam-j.htmlで 提供されています。)。 この論文以外にも氏のページからは、 spam対策に関する有用な情報をたくさん手にいれることができます。

NBCを利用したフィルタリングには以下のような特長があります。

• 学習するフィルタである。

  良いメールとspamメールの分類さえできていれば、 これらに良くあらわれる単語の出現頻度から自動的に spamメールらしさおよび良いメールらしさが計算可能である。

• spamメールの進化に対応している。

  spamらしさの学習は逐次的に可能なため、 spamメールで用いられる単語が変化しても、 自動的に学習して対応することが可能である。

• 自分の興味に応じたフィルタリングが可能。

  多くの人にとってspamメールであるものでも、 ある人にとっては興味のあるメールになる可能性があります。 NBCではspamメールの分類は利用者が行うため、 そのようなメールに対しても適切に学習します。

• 学習が高速である。

  厳密な意味での統計学習をしたければ、 (Naiveでない)Baysian Classifierを使えばいいのですが、 計算時間がかかるという問題点があります。 NBCでは単語の出現回数とどのクラスに分類にされたかの回数だけ わかれば計算できますので、高速に計算可能です。

詳細は論文に当たってもらうとして、ここではこの手法の概略に関して 説明します。

	  b(word)
	  -------
	  nspam  	  (編集注:インラインで組版してください。)

	  g(word)
	  -------
	  ngood  	  (編集注:インラインで組版してください。)

	  b(word)
	  -------
	  nspam
p(word)=  -----------------------
	  b(word)     2*g(word)
	  -------  +  ---------
	  nspam           ngood 
	

	  prod = Πp(word)

pspam =
	  prod
	  ------------------------------
	  prod + (1-Πp(word))

	  	(編集注:ΠはΠfor all wordで組版
	

ソフトウエア紹介

ここでは、論文の筆者のサイトの一覧 (http://www.paulgraham.com/filters.html) から、主にports collectionに含まれているソフトウエアに関して説明します。

表1に主にportsに含まれているNBCを用いたspamメールフィルタを示します。 かなりの数がありますが、最初から日本語が利用できる状態になっているものは ありません。

表2に各フィルタの機能比較を示します。 MUAで対応しているMozillaを除いては、 基本的にprocmailなどのMDAから利用するように設計されています。 ifileはデータベースがテキストファイルなので、 単語分布が簡単に確認でき、面白いです。

ここでは、詳細な利用法は述べませんが、 基本的な操作に必要なコマンドラインオプション一覧を 表3に示します。 詳細は各フィルタ付属のドキュメントを参照してください。

実験

今回紹介したソフトウエアはまだ日本語への対応などがされていないもので、 すぐに利用できるようなものではありません。 しかし、筆者が受け取るspamメールの大多数は英語のもので、 ついで韓国語や中国語の順ですので、一見spamメールの分類を作るには 問題が無さそうに思えます。 しかし、分類をする以上はspamメールで無い例も必須になりますので、 単語が空白で区切られていることを仮定している [4] これらのソフトウエアを利用しても、ヘッダの情報が有効に利用される程度で 効果が半減してしまいます。

日本語で分かち書きが可能なソフトウエアとしては、 kakasi (japanese/kakasi, http://kakasi.namazu.org/) やChasen (japanese/chasen, http://chasen.aist-nara.ac.jp/: 本来は形態素解析のためのソフトウエア) があります。 ここでは、kakasiを使って単語を分割して、 学習する実験をしてみました。 ここでは、改造の容易さを優先して、 PerlスクリプトであるBayespamを利用します。

図1に学習用プログラムの変更箇所を示します。 本来であればkakasiのPerlモジュール版である Text::Kakasi (japanese/p5-Text-Kakasi)を利用した方が 速度面でも有利なのですが、 ここでは実験と言うことで簡単な実装にとどめています。 「単語」の意味もオリジナルと変っているのには注意してください。

--- /usr/local/bin/bayes_process_email.pl	Thu Jan  2 00:11:55 2003
+++ bayes_process_email.pl	Thu Jan  9 01:57:01 2003
@@ -232,7 +232,7 @@
 	$mailcount++;
 	print '.' if ( $mailcount % 100 ) == 0;
 
-	if ( ( $file eq "-" ) || open(F, "< $file") )
+	if ( ( $file eq "-" ) || open(F, "/usr/local/bin/nkf -e $file|/usr/local/bin/kakasi -w|") )
 	{
 		my $data;
 		$data = $parser->parse(\*F) if $file ne "-";
@@ -242,12 +242,15 @@
 
 		# Rip out HTML comments
 		$message =~ s/\<\!\-.*\-\>//gs;
-		$message = lc $message if not $case_sensitive;
 
-		foreach (split( /[^\w'$-]+/, $message ) )
+		foreach (split( /\s+/, $message ) )
 		{
 			# Ignore all-numeric tokens
-			if ( !( $_ =~ /^[0-9\-]+$/g ) ) { if (length($_) > 0){$token_occurrences{ $_ } += 1.0;} }
+		  if ( !( $_ =~ /^[0-9\-]+$/g ) ) { 
+		    if (length($_) > 0){
+			$token_occurrences{ $_ } += 1.0;
+		    } 
+		  }
 		}
 	}
 }

実験対象のデータは、spamメール626通、良いメール802通となっています。 良いメールは本誌記者用メーリングリストを利用しましたので、 出現単語などにはかなり偏りがあります。 筆者が目でみて判断したspamメール(555通)にはほとんど日本語のspamが含まれなかったため、 無料プロバイダなどのサービスを利用するときに自動的に購読しなくてはならない 宣伝が中心のものを選択し、71通追加してあります。

このプログラムで単語と認識されたものは全部で14572になります。 学習したデータベースを 図2 のプログラムで調べると、以下のような傾向が見られます。

• spam度が高い場合(0.99で9356単語)。

  HTMLタグやスタイルシートの断片などが多く見られます。 2つ以上の文字からなる日本語単語 [5] では、 「商品」(spamメールで373回出現)、「販売価格」(247)、「本数」(225)、 「キャンペーン」(213)、「マイル」(185)の順になります。

• spam度が中ぐらいの場合(0.5で27単語)。

  英語ではtheやfrom,withなど、日本語では句読点などの どんな文章でも必須で利用されるものが含まれています。 また、Received:などのメールヘッダの項目名もここに含まれています。

• spam度が低い場合(0.01で47単語)。

  英語ではWanderlustのバージョンに含まれる文字列が多かったです。 これは筆者がWanderlustを常用しているためだと考えられます。 もちろん、「FreeBSD」(良いメールで429回出現)が多く、 ついで「Mew」(286)、「Emacs」(299)、「Mule」(286)の順になっています。 筆者の名前のローマ字表記(MUTOH 125,Takeshi 151)も同じく多かったです。 日本語の単語は「インストール」(340)、「疲れ」(190)、「コマンド」(116)、「次の」(89)、「ユーザ」(86)と なにやら壮絶な雰囲気を醸し出しています。

#!/usr/bin/perl -w

use strict;
use MIME::Parser;
use Fcntl;
use DB_File;

use vars qw($number_of_messages %token_occurrences);
use Bayespam::Process;

my $number_of_nonspam_messages = 0;
my $number_of_spam_messages = 0;
my %token_ratings = ();

my $outfile = shift;

my $parser = new MIME::Parser;

$parser->output_to_core(1);
$parser->extract_uuencode(1);

# Open the database
tie( %token_ratings, "DB_File", $outfile, O_CREAT|O_RDWR, 0666, $DB_BTREE) ||
	die "Could not open or create database $outfile.";

# Disable STDOUT buffering
$| = 1;

# Read in saved settings in database
$number_of_spam_messages = $token_ratings{ " spam " } || 0;
$number_of_nonspam_messages = $token_ratings{ " nonspam " } || 0;

# print "SPAM#:$number_of_spam_messages, NON_SPAM#:$number_of_nonspam_messages\n";
foreach (%token_ratings) {
  next if(!defined $token_ratings{$_});
  my(@line)=split(/\s+/,$token_ratings{$_});
  print "$_\t@line\n" ;
}

untie( %token_ratings );

おわりに

今回は、日本語の対応が完全なソフトウエアの紹介と言うわけではなかったため、 すぐに役に立つという記事にはなりませんでした。 申し訳ありません。 ただし、日本語化などの対応や、 Mozillaでの実装次第ではまもなく このような手法も利用されていくようになってくるのでしょう。 問題は、ここで紹介したソフトウエアはMozillaの実装を除いては、 古き良きUNIXの伝統に従ったフィルタでの実装となっていることです。 単なるユーザにとっては、 MUAからいかに便利に利用できるかというインターフェース回りで 工夫が欲しいところだと思います。 我こそはと思わん方は是非MUAへの組み込みにも挑戦してみてください。