このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

*ベイズ理論を用いた確率モデルによるスパムメールの判別 [#h14e976e]
 ベイズ理論(Naive Bayes)を用いたスパムメールの判別では、まず次の2つを前提条件とします。

 崙団蠅涼姥譟廚魯好僖爛瓠璽襪帽睇囘戮暴亳修垢襦

◆屬修谿奮阿涼姥譟廚枠鵐好僖爛瓠璽襪帽睇囘戮暴亳修垢襦

 よって、新しく受信されたメールに含まれた単語(トークン)を、過去に出現したスパムメール、非スパムメール(正当なメール)に含まれている単語と比較することによって、そのメールがスパムかどうかを判別可能になります。

 新しく受信されたメールの単語と過去に受信したメールの単語を比較するために、コーパスというデータベースを作成しておきます。これは、単語の出現頻度のデータベースのことです。スパムメール用のコーパスをスパムコーパス、非スパムメール用のコーパスを非スパムコーパスと呼びことにします。

 トークンの抽出方法には日本語のメールと英語のメールで若干の違いが生じ、あらゆる方法が提案されています。これに関しては後述しています。

*ベイジアンフィルタの特徴 [#kef975d7]
 ベイズ理論を用いてスパムメールか否か判定するためのフィルタのことをベイジアンフィルタと呼びます。

 ベイジアンフィルタは、メールを判定した後に単語を新たに学習し、出現確率のデータを更新できるという特徴を持ちます。この特徴により、それ以降のメールの判定の精度が向上していきます。つまり、学習させればさせるほど判定の精度が向上するということです。この特徴は長いスパンで考えたときにとても有効です。なぜならば、スパムメールの本文内容にも時期によって多く使われている単語は変わってきます。単に文字列だけでフィルタリングするような方式を採用していたとき、流行遅れの単語さえもフィルタリング用の単語として登録してしまうことになり、スパム判定の精度を下げてしまう可能性があるからです。それに比べて、ベイジアンフィルタの場合は、学習によってスパムメールの流行に対応することができます。

*Graham方式 [#tfc1c22a]
 これは、Paul Grahamによって提案された方式です[b1][b2]。

 このモデルでは、新しいメールが受信されると、次の手順でそのメールがスパムメールである確率を求めます。

1:まず、メール内の各単語のスパム確率を求めます。ページ内に出現する各単語wSUB{i};に対して、wSUB{i};を含むメールがスパムメールである確率をp(wSUB{i};)は、学習データであるコーパスを用いて次のように計算します。

#ref(graham1.jpg)

gSUB{i};:非スパムコーパス中にwSUB{i};が出現した回数~
bSUB{i};:スパムコーパス中に出現した回数~
nSUB{good};:非スパムコーパス中のメールの総数~
nSUB{bad};:スパムコーパス中のメールの総数~
a:バイアス(定数)~

 バイアスは、フィルタの通過・遮断を決定する要素のひとつです。[b1]ではスパムメールがフィルタを通過してしまうことより、非スパムメールをフィルタにより誤って遮断してしまうこと(false-positive)のほうが、メール受信者にとって損害が大きいという考えにより、非スパムメールの誤遮断が起きにくいようにバイアスをかけます。そのため、a=2としています。

 これらを[b1]に準拠して厳密に書くと、次のようになります。

[1]2gSUB{i};+bSUB{i};>5の場合

#ref(graham2.jpg)

[2]上記以外の場合

#ref(graham3.JPG)

 非スパムへの判定にバイアスをかけるために非スパムの出現回数を2倍にして計算し、出現回数が5回以下のものは計算から除外しています。

 また、P(wSUB{i};)の最小値は0.01、最大値は0.99とします。

2:メールのスパム確率を求めます。新しいメールがフィルタに到達すると、それを単語に分解し、ステップ1のように計算して、特徴的なM個の単語wSUB{1};,wSUB{2};,…,wSUB{n};を抽出します。特徴的というのは、その単語のスパムメールの確率P(wSUB{i};)が0.5から遠く離れていることです。[b1]では、経験則からn=15、即ち特徴的な15個の単語を抽出しています。

 こういった単語の上位n個を抽出して、その結合確率によって、メールがスパムメールである確率p(D)を次の式で求めます。

#ref(graham4.JPG)

 そして、p(D)があるしきい値tを上回った場合に、そのメールはスパムメールと判定します。[b1]では、t=0.9としています。0.5ではなく0.9と高めに設定しているのは、false-positiveを割ける方法にバイアスをかけるためです。

 よって、スパムメールか否かを判定します。ステップ2で求めた確率P(D)が0.9以上であればスパムメール、0.9未満であれば非スパムメールとします。

 Grahamのベイジアンフィルターの実験では、それぞれ4,000通のメールを学習データとして用いており、その結果スパムメールは99.5%、非スパムメールは99.7%という判別的中率を出しています。

*Robinson方式 [#lc9268e1]
 この方式は、Gary RobinsonがGraham方式を改良した方式です[c1][c2]。

1:まず、Graham方式の単語ごとにスパムメール確率p(wSUB{i};)をバイアスをかけずに求めます。つまり、a=1で計算するわけです。

#ref(robinson1.jpg)

 そのp(wSUB{i};)を用いて、f(wSUB{i};)は次のように計算されます。

#ref(robinson2.jpg)

x:今まで1度もメールの中に出現していない単語が初めてメールに出現したときに、そのメールがスパムメールである予測確率~
s:xの予測に与える強さ(strength)~
n:単語wSUB{i};の出現回数~

 xとsの値は、フィルタのパフォーマンスが最適化されるように設定すべきですが、とりあえずのところx=0.5、s=1が妥当であるとされています。

2:あるメールがスパムメールである確率は次のH(Hamminess:ノンスパム性)とS(Spaminess:スパム性)を計算し、I(Indicator:指標)で与えられます。

#ref(robinson3.jpg)

CSUP{-1};:逆χSUP{2};関数

#ref(robinson4.JPG)

3:スパムメールかどうかを判定するしきい値tについては[c1][c2]では特に指定されていません。判定結果を単にスパムメールと非スパムメールの2択だけにするのではなく、Iの値が0.5に近いときは「どちらともいえない」という判定をすることにより、誤判定を減らすことができます。

 このRobinson方式がGraham方式と比べて優れているのは、単語wSUB{i};の出現回数が少ない場合(n=0を含める)をうまく扱えることです。例えば、Graham方式ではある単語wSUB{i};がスパムメールのみに数回出現した場合、そのメールのスパムメール確率p(wSUB{i};)は1になってしまうが、その程度の情報で単語wSUP{i};に最大のスパムメール確率を与えるのはやりすぎといえます。一方、Robinson方式では、単語wSUB{i};の総出現回数nが小さい場合にはp(wSUB{i};)の比重が小さくなるようにできているので、まだ情報不足であるということをf(wSUB{i};)に暗に加味することができます。そして、学習が繰り返されるによって、総出現回数nが大きくなっていって、f(wSUB{i};)の値は漸近的にf(wSUB{i};)の値に近づいていきます。また、n=0の場合にはf(wSUB{i};)=xとなります。
 このRobinson方式がGraham方式と比べて優れているのは、単語wSUB{i};の出現回数が少ない場合(n=0を含める)をうまく扱えることです。例えば、Graham方式ではある単語wSUB{i};がスパムメールのみに数回出現した場合、そのメールのスパムメール確率p(wSUB{i};)は1になってしまうが、その程度の情報で単語wSUB{i};に最大のスパムメール確率を与えるのはやりすぎといえます。一方、Robinson方式では、単語wSUB{i};の総出現回数nが小さい場合にはp(wSUB{i};)の比重が小さくなるようにできているので、まだ情報不足であるということをf(wSUB{i};)に暗に加味することができます。そして、学習が繰り返されるによって、総出現回数nが大きくなっていって、f(wSUB{i};)の値は漸近的にf(wSUB{i};)の値に近づいていきます。また、n=0の場合にはf(wSUB{i};)=xとなります。