文書ベクトルの次元削減に基づく有効な類似文書判定梅澤香矢乃(指導教員：小林一郎)

はじめに

1

文書検索技術においては，テキストデータは文書ベクトル空間モデルとして表現され，テキストのベクトル同士の類似性を測ることにより所望のテキストを探す．しかし，文書ベクトルは検索対象となる文書内に含まれる語彙の数だけ次元を持つため，一般的に高次元ベクトルのデータとなる．高次元データをそのまま扱うと実時間応答が困難になるため，ベクトルの次元を削減して扱う必要がある．本研究では，これまでに研究されてきた LSI(Latent Semantic Indexing) や，pLSI(Probablistic LSI) などの手法と比較して性能の良い次元削減が報告されている [1] ランダムプロジェ
クションを用いて，低次元数に文書ベクトルの次元削減をした場合の類似文書判定の有効性について考察を述べる.

類似文書判定処理2

図 1 に提案する類似文書判定の処理概要を示す．

は，以下の式によって与えられる．

tf (d, t) =nt
Nd

idf (t) =log

tf idf (d, t) =(1)W+1wt
tf (d, t) × idf (t)

(2)
(3)

nt は特徴語 t の出現回数であり，Nd は文書 d における全特徴語の出現回数である．W は総文書数，wt は単語 t を含む文書の数であり，対数の底を 2 とする．
tf (d, t) と idf (t) の積により，tf idf (d, t) が求まる．
さらに，文書の長さによる影響を調整するため，得られた文書 d の文書ベクトル xd の値をコサイン正規化する．コサイン正規化では，ベクトルのノルムを計算し，ベクトルの各要素をノルムで割る．ベクトルx = (x1 , x2 , . . . , xn ) のノルム kxk は，式 (4) で表される．
√∑kxk =xi 2(4)以上の計算により，各文書を文書ベクトルで表せる．

2.3

類似度判定

各文書の類似の度合いを測るために，各文書の文書ベクトル同士のコサイン類似度を求める．コサイン類
似度はテキスト処理で多用される類似度の指標である．
文書 d1 の文書ベクトル x = (x1 , x2 , . . . , xn ) と文書
d2 の文書ベクトル y = (y1 , y2 , . . . , yn ) のコサイン類
似度は以下の式で与えられる．

scos(x,y)

図 1: 類似文書判定処理の流れ
大量の文書から各文書の特徴を取り出して，文書ベクトルとして格納しておく．質問となる文書と検索対象となる文書の文書ベクトルとのコサイン類似度を求め，類似度の高い順に並べる. 文書ベクトルとは，ある文書において，その文書の特徴を表す文書中の語彙を特徴語と定義し，特徴語の重要度を表す値である特徴量をもったベクトルである．

2.1

形態素解析

特徴量抽出のため，質問となる文書と検索対象となる文書に対し，初めに形態素解析を行う．本研究では，形態素解析器 MeCab[2] を用いて行う．形態素解析の結果得られた語彙のうち，文書群中の複数の文書に出現する，品詞が名詞または動詞である語彙を特徴語として選ぶ．

2.2

特徴語の重要度算出

特徴語の文書内での重要度を考慮して，特徴量を求めることが必要である．そのために，本研究では tf idf法を用いる．tf idf 法は， tf (Term Frequency) と idf(Inverse Document Frequency) の 2 つの指標を利用し，その積によって文書中の特徴語の重要度を計算する．文書 d における特徴語 t の重要度である tf idf (d, t)Pyi= √P x2i P
2xiyi(5)コサイン類似度の値が大きいほど，ベクトルで表された文書同士の類似の度合いが大きいと判定される．

3

ランダムプロジェクション

高次元のベクトル空間においては，直交ベクトルに近いベクトルが多く存在する．そのことから，ランダムな方向を持ったベクトルは，十分に直交ベクトルに近いと推測される．ランダムプロジェクション手法は，通常は正規直交系に座標を変換する射影行列を用いて次元を削減するものを，要素をランダムに決定した行列 R を射影行列とすることにより計算コストを抑え，文書ベクトル行列 X を低次元の部分空間に射影するという次元削減の手法である．
特徴語数 d，文書数 n の文書行列 Xd×n は，行列の大きさが d 行 n 列となり，それぞれの列ベクトルが1 件の文書を表す. i 行 j 列の要素 xij は，文書 j における単語 i の正規化した tf idf 値である.
縮小後の次元数を k とした場合，ランダムプロジェ
クション行列 Rk×d は要素をランダムに決定し，大きさ k × d の行列となるように作成する. d × n の行列
Xd×n を，k × d(k  d) の行列 Rk×d に射影するためである．射影行列の i 行 j 列の要素 rij は，通常ガウス分布に従うように設定されるが，式 (6) で表される単純な独立した分布に置き換え，計算効率の向上が図れることが示されている [3]．


 +1 確率 1/6
rij =0
確率 2/3
−1 確率 1/6(6)(a) の場合

行列 Xd×n のランダムプロジェクション手法による次元削減は，式 (7) によって行われる．
RPXk×n= Rk×d × Xd×n

(7)

次元数を削減するほど計算時間は短縮される．
検索の際には，式 (8) により質問となるベクトルも低次元空間に射影して類似検索を行う．
RPqk×1= Rk×d × qd×1(8)次元を削減した検索対象文書の文書ベクトルとの類似度を計算し，その値から類似順位を決定する．
次元削減による誤差は，ベクトル間のユークリッド距離に対して定義される．今， を 0 <  < 1，n を整数として，k 0 を次のようにおく. ここで， k 0 は誤差との範囲で保証される削減後の次元数である．

k0 ≥4 + 2βlog n2 /2 − 3 /3(9)行列 Xd×n から 行列 Xk0 ×n へのランダムプロジェク
ション行列 Rk0 ×d による写像を f : Xd×n → Xk0 ×n と表すとする．そして，行列 Xd×n の任意の 2 つの列ベクトル u 及び v をとると，少なくとも 1 − n−β の確率で，式 (10) を満たす [3]．
(1 − ) k u − v k2 ≤k f (u) − f (v) k2 ≤ (1 + ) k u − v k2 (10)0

これは，式 (9) を満たす k 次元に縮小した場合において，任意の 2 つのベクトルのユークリッド距離が 1 ± の誤差の範囲で保存されることを示している.

4実験

類似文書の判定において本手法の有効性を調べる実験を行う．検索対象の文書には，評価型ワークショッ
プ NTCIR [4] によって提供されているデータセット
NTCIR-1 の論文データ 339, 501 件からランダムに選んだ 3, 774 件の論文アブストラクト（日本語）を用いた．各論文は 26 の学会のうち，いずれか 1 つの学会で発表されている．論文数が最も少ない学会で 4 論文，最も多い学会で 774 論文である．論文アブストラクトを形態素解析して得た名詞・動詞は 9, 939 個あり，その中から一度しか出現しない語を除いて特徴語を選ぶと 6, 109 個となった．

4.1

性能評価

性能評価の指標として検索結果の 11 点平均適合率を算出し，類似文書判定が適切かどうか評価した．質問文書に対する適合文書は，次元削減せずに同じ質問文書で検索をして，類似度が高いと判定された順に並べた文書群とする．

(b) の場合

図 2: 実験の結果

4.2

結果

質問文書は，実験 (a) では論文数が最も多い学会で発表された論文アブストラクト，実験 (b) ではその次に論文数が多い学会で発表された論文アブストラクトを用い，検索結果についてそれぞれ 11 点平均適合率を求める．検索は 5 回繰り返し，その結果についての11 点平均適合率の平均値を図 2 に示した．グラフの横軸は削減後の次元数を，縦軸は各次元削後の類似文書判定結果についての 11 点平均適合率の平均値を表す．
6, 109 個の特徴語からなる次元数に対して，ランダムプロジェクションによる次元削減後の精度の保証が示されている次元数として，式 (9) より求めた 2, 100 次元に削減した場合1 の値を示した．さらに，精度の保証がされない次元数 100 次元，200 次元，300 次元，400 次元，500 次元に削減した場合の値も示した．その結果，理論的に精度保証がされていない低次元に削減した場合であっても，精度保証がなされている高次元の場合に近い判定の精度を保っていることが分かった．そして低次元に削減するほど，検索速度が高速になっていることを確認した．

5

おわりに

今回は，類似文書の判定において，ランダムプロジェクションを用いて，検索精度をある程度保ちながら検索速度を向上させる手法を試した．その結果，理論的に精度保証がされていない低次元に削減した場合であっても，精度保証がされている高次元の場合に近い検索精度を保っていると思われる結果が出た．
今後は，より一般的な次元削減と類似文書判定精度の関係を考察するために，検索対象となる文書の種類や数を増やして実験するつもりである．

参考文献[1] 佐々木稔, 北研 二: “ランダム・プロジェクションによるベクトル空間モデルの次元削減”, 自然言語処理, Vol.8,
No.1, 2000
[2] Mecab,http://mecab.sourceforge.net/[3] Achlioptas, D.: “Database-friendly random projections , In Proc. ACM Symp. on the Principles of
Database Systems, pp 274-281, 2001.
[4] http://research.nii.ac.jp/ntcir/index-en.html
1 このとき  = 0.1 とし，β > 0 となる 100 のオーダでの最小の k の値を求めた．