【おそらくこれ以上解りやすい説明はないであろう】ナイーブベイズ法によるスパムメールの自動分類

シェアする

Naive Bayes識別器は,最も単純かつ基本的な統計的な機械学習法だと思いますが,ちょいと勉強したので備忘録代わりに記事にしておきます.問題設定としては,

「あるメールを受信した時,そのメールがスパムかそうでないかを自動的に振り分ける」

ことを考えたいと思います.メールがスパムか否かを判断するには,メールで使用されているキーワードに着目します.たとえば,「今すぐクリック!」のようにウィルス感染を促すURLへクリックさせるような言葉や,「未納です」のように身に覚えのない支払い請求とかが考えられます.

それで,ここでは「クリック」と「未納」というキーワードに着目したいと思います.

  • 「クリック」というキーワードがメール内に存在した: \(W_1\)
  • 「クリック」というキーワードがメール内に存在しなかった: \(\overline{W_1}\)
  • 「未納」というキーワードがメール内に存在した: \(W_2\)
  • 「未納」というキーワードがメール内に存在しなかった: \(\overline{W_2}\)

さらに,過去に送られて来たメール100通を集めて,以下のようにラベルづけをします

  • スパムメール:\(S\)
  • スパムでないメール:\(\overline{S}\)

実際の100通のメールを分析して,スパムかスパムでないか,「クリック」というキーワードがあるかないか,「未納」というキーワードがあるかないかを調べ,以下のような表を作成します.

ここまでの前提で,以下の問いに答えます:

あるメールを受信したら,その本文に「クリック」は含まれてないが,「未納」は含まれていた.このメールをナイーブベイズの方法によりスパムかスパムでないか判断する.
  • 「クリック」が含まれていない: \(\overline{W_1}\)
  • 「未納」が含まれている: \(W_2\)

として定義したので,題意より\(\overline{W_1}\cap W_2\)の条件の下,スパムである確率\(P(S|\overline{W_1}\cap W_2)\)とスパムでない確率\(P(\overline{S}|\overline{W_1}\cap W_2)\)を計算し,どちらか確率の高い方に振り分けることになります.これらの値は,ベイズの定理より,
\begin{eqnarray}
P(S|\overline{W_1}\cap W_2) &=& \frac{P(\overline{W_1}\cap W_2|S)P(S)}{P(\overline{W_1}\cap W_2)}\\
P(\overline{S}|\overline{W_1}\cap W_2) &=& \frac{P(\overline{W_1}\cap W_2|\overline{S})P(\overline{S})}{P(\overline{W_1}\cap W_2)}
\end{eqnarray}
となるけど(脚注),右辺の分母は大小関係を評価するのに無関係な値なので計算する必要はありません.すなわち,
\begin{eqnarray}
P(S|\overline{W_1}\cap W_2) &\propto & P(\overline{W_1}\cap W_2|S)P(S)\\
P(\overline{S}|\overline{W_1}\cap W_2) &\propto & P(\overline{W_1}\cap W_2|\overline{S})P(\overline{S})
\end{eqnarray}
を計算することになります.また,右辺の条件付き確率は,独立性の仮定の下,
\begin{eqnarray}
P(\overline{W_1}\cap W_2|S) &=& P(\overline{W_1}|S)P(W_2|S)\\
P(\overline{W_1}\cap W_2|\overline{S}) &=& P(\overline{W_1}|\overline{S})P(W_2|\overline{S})
\end{eqnarray}
として計算します(本当は独立性が成立しないことが多いのだが,それでもこの仮定を導入するとうまくいくことが知られている).各確率は表を元に計算できるので,
\begin{eqnarray}
P(\overline{W_1}|S) = 8/18, \,\,\,P(W_2|S) = 6/18\\
P(\overline{W_1}|\overline{S}) = 72/82, \,\,\,P(W_2|\overline{S}) = 7/82\\
\end{eqnarray}
また,\(P(S)=18/100, P(\overline{S})=82/100\)より,
\begin{eqnarray}
P(S|\overline{W_1}\cap W_2) &\propto & P(\overline{W_1}|S)P(W_2|S)P(S)\\
&=& (8/18)\times(6/18)\times (18/100)\\
&=& 0.027\\
P(\overline{S}|\overline{W_1}\cap W_2) &\propto & P(\overline{W_1}|\overline{S})P(W_2|\overline{S})P(\overline{S})\\
&=& (72/82)\times (7/82)\times (82/100) \\
&=& 0.061
\end{eqnarray}
これより\(P(\overline{S}|\overline{W_1}\cap W_2)>P(S|\overline{W_1}\cap W_2)\)となるため,このメールはスパムに振り分けないという結果になります.

実際のスパムフィルターはもっと色々工夫していると思いますが、原型はこんな手法で行われてるようです.

ベイズの定理は,
\[
P(A|B) = \frac{P(B|A)P(A)}{P(B)}
\]
ですが,ここで,\(B = C\cap D\)として代入すると,
\[
P(A|C\cap D)=\frac{P(C\cap D|A)P(A)}{P(C\cap D)}
\] が成立する.