PDF 0.17MB

統計の手法を用いた電子メールの分類に関する研究
A study on statistical classification of e-mail documents
経営システム工学専攻 庄健
Ken Syou
1
一番搾り（名詞）/は（副助詞）/うまい（形容詞）
はじめに
近年, インターネットの普及と通信技術の発
3
展に伴って、電子メールが増加している。でも、
分類方法
同時に、たくさんの電子メールを狙った悪質な
本研究ではサポートベクターマシンと文書類
スパムメールも増えてきて、社会問題になって
似度により電子メールの分類二つの分類方法の
いる. メールの利用者としては、メールが大量
比較研究を行った。
的に蓄積されると、不要なメールを消すのが大
変時間がかかる。したがって、電子メールの自
動分類の研究がすごく重要な意義である。電子
3.1
メールの分類がいくつの手法であるが。ここで
ベクトル空間法
は，統計の方法としてサポートベクターマシン
ベクトル空間モデルでは、文書中の出現単語
を用いた電子メールの分類に関する研究を行っ
の頻度に基づき、文書の特徴量を１つのベクト
た．サポートベクトルマシン法と簡単な距離法
ルで表現することで、文章を空間上の点として
を比較し、実験の結果によって、サポートベク
表す。出現単語に基づくベクトル空間を構成し、
ターマシンの効果が簡単距離法より優れている
文書同士の類似度を距離の概念によって数学的
ことを示した。
に取り払うことが可能である。
通常は、各単語の出現頻度だけでなく、全
文章中でその単語が現れる割合を考慮した特
2
分類の流れ
徴量の算出が必要であり、そのための方法が
TF·IDF 法である。TF は単語の出現頻度を表
す。IDF 単語が出現する文書の割合を表す。文書
di における単語の出現頻度 TF を tf(di , wj ) と
おく。IDF は単語wj を含む文書の数
電子メール分類の流れはまずメールの前処理
を行う。メールの前処理は形態素解析器を使っ
て入力されたメールテキストを単語に区切る。
ここでは形態素解析のフリーソフト「茶筅」を
採用した。次に、ベクトル空間法により、電子
idf (wj ) = log
メールの文書ベクトルを生成する。最後に統計
の方法サポートベクターマシンを用いて電子
D
df (wj )
(1)
文書 di における単語 wj の特徴量は
メールの分類性能を考察した。
vji = tf (di , wj )idf (wj )
2.1
(2)
各文書の特徴量がベクトル表現されれば、文
形態素解析
書 di と文書 dk の類似度は、これらの距離を
文書の分類には単語を利用するため、文書を
使って測ることができる。これらの距離は原点
単語に分割する必要がある。形態素解析とは文
付近の２点が近いものであると判定する。ほと
書を意味のなす単語の単位に分解することで
んどの単語の特徴量が 0 に近い文書同士は内容
ある。
的に類似しているとは言えないが、ユークリッ
例えば：キリン（名詞）/の（名詞接続助詞）/
ド距離や内積によれば類似していると判定して
1
しまう。文書ベクトル di と文書ベクトル dk の
余弦をとって類似度とする方法が一般的である。
文書の類似度によって、電子メール分類の実現
ができる。
sim(di , dk ) =
4
dTi dk
|di ||dk |
(3)
サポートベクターマシン
カーネルトリックにより非線形の識別関数を
構成できるように拡張したサポートベクター
図 1: 線形しきい素子の分離超平面とマージン
マシンは、現在知られている多くの手法の中で
（白い丸の記号がグラス１のサンプルで、白い四
も最も認識性能の優れた学習モデルの一つであ
角の記号がグラスー１のサンプルを示す。黒い
る。サポートベクターマシンが優れた認識性能
丸の記号と黒い四角の記号はサポートベクター
を発揮できるのは、未学習データに対して高い
を示す）。
識別性能を得るための工夫があるためである。
サポートベクターマシンは、カーネル関数の力
を借りて、線形分離可能な高次元の空間で線形
超平面から学習点ｘまでの距離は
的なアプローチで学習を行うアルゴリズムであ
d(w, b; x) =
る。サポートベクターマシンは高次元の分類問
題が得意であると言われている。
4.1
|w · xi + b|
||w||
(6)
となり、二つの分離超平面間のマージンは
min(yi =1)
線形分類できる場合
i +b|
=
min(yi =−1) |w·x
||w||
正例と負例の二つのクラスに属する訓練デー
タのベクトルの集合を (x1 , y1 )、(x2 , y2 )、(xi ,yi ),
xni ,yi ∈-1,+1 とする。xi はデータ i の特徴ベク
トルで、yi はデータ i が正例 (正当メール) １か (
負例スパムメール) − 1 かを表すスカラである
。文書分類問題では、文書の特徴を文書中に出
現する場合はwi = 1、出現しない場合は wi = 0
として文書をベクトル xi =(w1 , w2 , ..., wn ) で表
す。メール文書があるカテゴリに含まれる場合
を正例、含まれない場合を負例として、各カテ
ゴリに対して、サポートベクターマシンを構成
する。これらのデータをＮ次元空間上の超平面
で分離する問題を考えられる。
w · xi + b ≥ 1
(if
yi ∈ 1)
(4)
w · xi + b ≤ −1
(if
yi ∈ −1)
(5)
|w · xi + b|
+
||w||
2
||w||
(7)
と計算される。このマージンを最大とするた
めに
2
||w||
を最小すればいい。これにより制約
付き最適化問題は
1
2
||w||
2
subject to yi (w · xi + b) ≥ 1
(8)
Lagrange 乗数 α を導入して双対問題に変換
できる。
minimize
maximum
Pl
Pt
L(α) = i=1 αi − 21 i,j=1 ai aj yi yj (xi xj )
subject to
Pl
ai ≥ 0, i=1 ai yi = 0 (i = 1, .., l)
(9)
最終的な識別関数は
f (x) = sgn
l
X
i=1
2
ai yi (xi · x) + b
(10)
4.2
4.3
線形分離できない場合
カネール関数
カーネル法は、データを高次元に射影し、線
形問題に置き換えると同時に計算量の問題を解
決する技法である。射影された高次元のデータ
を直接計算するのではなく、任意の個体 x,z を
変換した φ(x),φ(z) の内積 |φ(x), φ(z)| のよう
な処理を借りて間接的に高次元のデータについ
て計算処理を行う。このようなデータの変換と
内積のような演算を組み合わせた関数をカーネ
ル関数と呼び、K(x, z) = |φ(x), φ(z)| のように
表記する。多項式関数、RBF 関数等多くの関
図 2: ソフトマージン（白い丸の記号がグラス
数を使うことができる。カーネル関数を導入す
１のサンプルで、白い四角の記号がグラスー１
ると、判別関数は
のサンプルを示す。黒い丸の記号と黒い四角の
記号はサポートベクターを示す）。
f (x) = sgn
l
X
ai yi K(xi , x) + b
(14)
i=1
サポートベクターマシンで分離超平面で分割
しきれないパターンに対して以下の手法を用い
5
て対処する。この手法を用いることで SVM は
より一般的な分類に対して適用出来るようにな
実験
5.1
データ
る。学習データに対する多少の識別誤差を許す
に制約を緩める。超平面で訓練データを完全に
この実験では私の yahoo のメール box から
分離できない場合、各データに対し新たな非負
もらったメールをデータとして使った。人工で
変数 ξi (i = 1, .., n) を導入し、式 (11) と (12) の
分類されたメールが 530 件である。この中が正
制約を以下のように緩める。
当メール 235 件とスパムメール 295 件である。
テストサンプルは 80 件、この中は正当メール
w · xi + b ≥ 1 − ξi
(if
yi ∈ 1)
(11)
w · xi + b ≤ −1 + ξi
(if
yi ∈ −1)
(12)
35 件とスパムメール 45 件である。訓練サンプ
ルそれぞれサンプル 1 サンプル 2 とサンプル 3
の三つのサンプルを設定した。サンプル 1：225
（正当メール 100、スパムメール 125)、サンプル
2：325（正当メール 145、スパムメール 185）、
サンプル 3：325（正当メール 145、スパムメー
ル 185）。
サポートベクトルマシンメール分類の効果を
検証するために LIBSVM によりテキストデータ
の分類を実験した。サンプルデータを LIBSVM
で SVM 識別をするには，LIBSVM 用の書式に
変換する必要がある。それぞれのデータファイ
ルの書式は下のような形式で表す。
クラスラベル 番号:数値 番号:数値 ...
クラスラベル 番号:数値 番号:数値 ...
これにより制約付き最適化問題は
t
minimize
X
1
2
||w|| + C
ξi 2
i=1
subject to yi (w · xi + b) ≥ 1 − ξi
ξi ≥ 0(i = 1, ..., l)
(13)
となる。ここで C は誤り判定による損失の重み
の意味。つまり、C の値が大きい時判別の誤リ
をしないように分類を行い、C の値が小さい時
は多少の判別の誤りは許し、できるだけ大きい
なマージンを取るようになる。C の最適値を実
験的に求められる。
3
5.2
分類結果の評価
この結果から見るとガウスカーネル法は再現率
と適合率両方とも一番高い、分類の精度が一番
分類システムの善し悪しは通常に再現率と適
高いことがわかってきた。
合率という二つの値によって評価される。再現
実際に SVM を用いた電子メールの分類を行
率は「正当メールと判定したメールで実際に正
うと、相対的に適合率ｐが高く、再現率ｒが低
当メールだったメールの総数」と「正当メール
い結果となる。電子メールの分類問題では、正
の総数」の商で表す。適合率は「正当メールと
例 (正当メール) の数が少なくて、負例（スパム
判定したメールで実際に正当メールだったメー
メール）の数多い場合、SVM は正例か負例かの
ルの総数」と「正当メールと判定したメールの
判定が微妙なテキストに対して負例と判定する
総数」の商で表す。
傾向にある。再現率を高めるために、パラメー
理想的には二つの値を両者とも 1 に近付ける
タ C を正例側の C(Cp ) と負例側の C(Cn ) に分
ことが望ましいのですが、実際にはこれら二つ
けた。式のように表れた。ここで Cp > Cn とす
の値にはトレードオフの関係が存在する。両者
れば、正例とに判定しやすい超平面を構成でき
の値のバランスよく成り立つポイントを測定す
ると考えられる。
るために再現率と適合率から F 値を計算し、判
断基準とする。
X
X
1
2
||w|| + Cp
ξi + Cn
ξi 2
(16)
パラメータＣを分離した場合 Cp = 3000 と
Cn = 1000 と非分離の場合 C=10000 の分類精
度を比較した。分類の結果が下の表のように表
示された。
minimize
F =
5.3
2 ∗ 再現率 ∗ 適合率
再現率 + 適合率
(15)
結果と結論
簡単距離法とサポートベクターマシンで分類
の結果が下の表のように示した。
データ
C 非分離
C 分離
サンプル 1
89.19%
90.83%
サンプル２
95.65%
95.67%
サンプル３
94.29%
94.33%
データ
評価
距離法
SVM
サンプル 1
再現率
58.49%
84.62%
サンプル 1
適応率
88.57%
94.29%
サンプル 1
F
70.45%
89.19%
上の表からみると、スパムメールが正当メール
サンプル 2
再現率
60.71%
97.06%
より多い場合、各サンプルデータとも C 非分離
サンプル 2
適応率
97.14%
94.29%
法より C 分離のほうが精度高いと証明した。パ
サンプル 2
F
74.72%
95.65%
サンプル 3
再現率
56.90%
94.29%
サンプル 3
適応率
94.29%
94.29%
サンプル 3
F
70.97%
94.29%
ラメータＣの分離がサポートベクターマシンの
性能を上がるのに有効であることが分かった。
参考文献
また、サンプル 1 に対して、三つのカーネル関
[1] 長 尾 真 著,「 自 然 言 語 処 理 」, 岩 波 書
店,1996 年
数を使って、サポートベクターマシンの方法を
用いてそれぞれの分類精度をしたの表のように
示した。
カーネル関数
再現率
適応率
F
線形
83.42%
90.22%
86.69%
Gauss
84.62%
94.29%
89.19%
多項式
83.75%
92.93%
88.10%
シグモイド
84.59%
93.58%
88.86%
[2] 栗田 多喜夫 著，
「サポートベクターマシン
入門」 産業技術総合研究所脳神経情報研究
部門
[3] 汪小平, 仲軍 共著，
「Visua C++でネット
ワーク通信プロトコルの実現」 北京人民教
育出版
4