検索要求と検索結果との類似度を定義する方法について学びます.
前章では, 単語リスト *q から文書リスト *r を検索するために wsh という関数を使いました. 復習になりますが,
r = wsh(q, qlen, w, WAM_COL, WT_TF, &rlen, NULL, NULL, NULL);このように WT_TF という名前の類似度計算式を指定しました. この計算式の定義は $GETASRC/lib/ae/wt の下にある ファイル wt_tf.f に書いてあります. 中身を見てみましょう.
name: WT_TF 0: 1: 2: wq(t|q) = TF(t|q); 3: wd(t|d) = TF(t|d); 4: norm(d) = TF(.|d); 5:まず name というパートにこの類似度計算式の名前 WT_TF を定義しています. wsh の引数にはここで付けた名前を指定します. 次の 0 から 5 までのパートで実際の計算式を定義します. 今,検索要求は単語リストです.これをqとしましょう. 検索結果は文書です.これをdとしましょう. wsh ではqとdとの類似度sim(d|q)を以下の式で計算しています.
sim(d|q) = (1 / norm(d)) * \sum_t { wq(t|q) * wd(t|d) } ^^^^^^^ -- 2 で指定 ^^^^^^^ -- 3 で指定 ^^^^^^^ -- 4 で指定ここでは, それぞれの単語tについてwq(t|q)とwd(t|d)を掛けています.wq(t|q)は,単語tのq中での重みです. 一方wd(t|d)は単語tのd中での重みです. 全ての単語についてwq(t|q) * wd(t|d)を足しあわせたものがqとdの類似度になります. 実際には全ての単語について足す必要はなく,qにあらわれる単語についてのみ足し合わせれば十分です. プログラムでもそうしています. また,文書dの長さもまちまちですから,dの長さnorm(d)で類似度の正規化を行っています. 蛇足になりますが,本当はqの長さも考えなくてはいけません. ただ,検索ではqを変化させずにいろいろなdを比較するわけですからqを正規化する必要はありません.
以上の wq(t|q), wd(t|d), norm(d) をそれぞれパート 2, 3, 4 で定義します. 実際に定義している箇所を見ていきましょう.
2: wq(t|q) = TF(t|q);まずは,単語 t の検索要求 q 中での重み wq(t|q) を TF(t|q) と定義しています.TF(t|q) は,検索要求 q にあらわれる t の頻度のことです. ですから, 検索要求にたくさんあらわれる単語ほど重要だということを意味しているわけです.
実際には,libae をコンパイルする際に,"wq(t|q)"と"TF(t|q)"が適切な変数名に変換されて,wsh.c の相当する箇所に埋めこまれます. ですから, 各パートで書くステートメントは C のステートメントになっている必要があります. 裏を返せば C のプログラムがそのまま書けるということです. 更に,wsh.c に埋めこまれるわけですから,wsh.c のその場所で有効な変数を全て参照できます(*1). 例えば,
2: wq(t|q) = TF(t|q); fprintf(stderr, "%s: weight = %e\n", wam_id2name(wam, WAM_COL, qp->id), wq(t|q));と書けば, それぞれの検索単語について, 単語名と計算した重みを出力することができます. fprintf や wam_id2name といった C の関数が呼べることに注目してください. wam_id2name の引数の"wam"ですが, 実はこれは,関数 wsh の引数で指定した変数と同じ変数が参照されます. 検索対象の WAM のことです.qp は今見ている syminfo 型要素へのポインタです. つまり各検索単語に相当します. wam_id2name で, 今見ている検索単語の番号 qp->id を名前に変換しているわけです.wsh.c でこのパートが埋めこまれる場所を見ると, よりはっきりとイメージがつかめるでしょう.
wsh(q, qlen, wam, .....) ..... syminfo *qp ..... for (qp=q, qe=q+qlen, qvecp=qvec; qp < qe; qp++) { ..... #include "wt/s2.c" ..... }#include で読みこまれている"wt/s2.c"が パート 2 の実体です. これを含む for ループで検索単語の重みを計算しています. 検索要求 q の各要素についてループが回っていることに注目してください. 変数 qp が各々の要素を指していますのでパート 2 でも qp が参照できるわけです. 各パートで参照できる変数名の一覧, および文字列変換の規則等は "custom.txt" を参照してください.
話がちょっと横道にずれました. もとに戻りましょう. 次に単語 t の文書 d 中での重みも同じように定義します.
3: wd(t|d) = TF(t|d);TF(t|d) は文書 d 中にあらわれる t の頻度に変換されます. ですからこの部分は, 文書中にたくさんあらわれる単語ほど重要だということを表現しています. 最後に,文書 d の長さを定義します.
4: norm(d) = TF(.|d);TF(.|d) は文書 d 中にあらわれる単語の総頻度に変換されます. いわゆるワードカウントです. ある単語 t が文書 d にいくらたくさんあらわれても, 文書が長くてはあまり意味がありません. そこで文書の総単語数で割ることによりバランスをとっているわけです.
以上で WT_TF の定義はおわりました. 説明しなかったパート 0, 1, 5 については必要に応じてこの後の章で説明することにしましょう.
ここで, 類似度定義ファイルを書くうえでの注意をいくつかあげておきます.
2: simple term weighting for query termといった具合です.
「4: 類似度を定義してみる」に進む
「2: libae を使って電子メール検索プログラムを作る」に戻る
「1: はじめに」に戻る