Kouhei Sutou
kou****@clear*****
2012年 10月 22日 (月) 17:29:25 JST
須藤です。 In <CAAR=x6_UKREasa-f_7tCsR****@mail*****> "[groonga-dev,01057] 【mroonga】類似文書検索のスコアについて" on Sun, 21 Oct 2012 11:57:45 +0900, 今井真宏 <masaz****@gmail*****> wrote: > 文章を比較した結果、似ている文章を表示するプログラムを作成しています。 > 比較のエンジンにmroongaの類似文書検索を使用しています。 > > 現在、類似文書検索のスコアに百万、一千万単位の値をしばしば取得します。 > これは完全一致している文章と比較したときよりも多きなスコアです。 > そのため、スコアの算出基準がわからず困っています。 ... > 算出基準が分かれば、スコアから類似度（たとえばパーセンテージや0〜1の数値で表現）が出来ると考えているのですが、 > スコア算出基準をご教授いただけませんでしょうか？ スコアは以下のように算出しています。 (1) クエリをトークンに分割する (2) マッチしないトークンを除去する (3) トークン毎の重みを計算する (4) 重みが大きい上位nトークンを取り出す (5) 上位nトークンについて、トークンが出現する文書に重みを足す → すべての重みを足したものが各文書のスコア 例を使って説明します。ドキュメントと同じ以下のデータがあると します。 SET NAMES UTF8; CREATE TABLE diaries ( id INT UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY, content TEXT, FULLTEXT INDEX(content) ) ENGINE mroonga DEFAULT CHARSET UTF8; INSERT INTO diaries (content) VALUES("明日の天気は晴れでしょう。"); INSERT INTO diaries (content) VALUES("明日の天気は雨でしょう。"); INSERT INTO diaries (content) VALUES("今日は晴れました。明日も晴れるでしょう。"); INSERT INTO diaries (content) VALUES("今日は晴れましたが、明日は雨でしょう。"); このとき、以下のように「今日の天気」で類似文書検索したとしま す。 SELECT *, MATCH (content) AGAINST ("今日の天気") FROM diaries WHERE MATCH (content) AGAINST ("今日の天気") ORDER BY MATCH (content) AGAINST ("今日の天気") DESC; (1) まず、クエリ「今日の天気」をトークンに分割します。デフォ ルトではバイグラムで分割するので以下の4つのトークンになります。 * 今日 * 日の * の天 * 天気 (2) 次に、マッチしないトークンを取り除きます。今回はすべての トークンがどれかの文書に含まれているのでここでは取り除かれま せん。 * 今日: id=3,4に含まれる * 日の: id=1,2に含まれる * の天: id=1,2に含まれる * 天気: id=1,2に含まれる (3) 次に、それぞれについて重みを計算します。 * 今日: 262144 (= 1048576 / 4) * 日の: 209715 (= 1048576 / 5) * の天: 174762 (= 1048576 / 6) * 天気: 149796 (= 1048576 / 7) (= ...)が重みの計算式です。 「1048576」（= 2 ** 20）は文書全体に含まれるトークン数を表し ています。本当はテーブルなどから情報を取得してくるなどして正 しい値を使いたいところですが、今のところ固定値になっています。 「/」の右辺の「4,5,6,7」は「トークンを含む文書がいくつあるか の概算値」です。本当はすべて「2」ですが、概算値なのでずれて います。 この式でしたいことは、「出現頻度が少ないトークン（= 重要語） の重みを高くする」です。 （もう少し細かいことを言うと、トークンが出現する毎に重みが1 増えます。が、ここでは1は誤差の範囲なので無視します。） (4) 次に、重みが大きい上位nトークンを取り出します。 nは以下の式で求めています。 n = マッチしたトークン数 / 8 + 1 今回は「マッチしたトークン数」が4なので「4 / 8 + 1 = 1」で n = 1です。 マッチしたトークンを重み順に並び替えると以下の通りです。 * 今日: 262144 (= 1048576 / 4) * 日の: 209715 (= 1048576 / 5) * の天: 174762 (= 1048576 / 6) * 天気: 149796 (= 1048576 / 7) このうち上位1件なので * 今日: 262144 (= 1048576 / 4) だけが残ります。 (5) 最後に、トークンが出現する文書に重みを足していき、文書の スコアとします。 * 今日: id=3,4にマッチ なので、文書id3,4がヒットし、スコアはどちらも262144です。 （↓の実行例で262144ではなく262145と1大きいのは(3)のところで 無視したトークンの出現回数がカウントされているからです。） SELECT *, MATCH (content) AGAINST ("今日の天気") FROM diaries WHERE MATCH (content) AGAINST ("今日の天気") ORDER BY MATCH (content) AGAINST ("今日の天気") DESC; id content MATCH (content) AGAINST ("今日の天気") 3 今日は晴れました。明日も晴れるでしょう。 262145 4 今日は晴れましたが、明日は雨でしょう。 262145 以上が算出基準になります。 > 算出基準が分かれば、スコアから類似度（たとえばパーセンテージや0〜1の数値で表現）が出来ると考えているのですが、 トークン1つ毎の最大値は「1048576」と決まっているのですが、トー クンが複数マッチすることもあるため、残念ですが確実に0-1に収 める方法はありません。 ただ、スコアを大きな数（例えば、16777216 = 2 ** 24）で割るこ とである程度0-1に収めることができるのではないかと思います。 あるいは、logをとるのもよいかもしれません。 SELECT *, MATCH (content) AGAINST ("今日の天気") AS score, LOG(MATCH (content) AGAINST ("今日の天気")) AS score_log, LOG10(MATCH (content) AGAINST ("今日の天気")) AS score_log10 FROM diaries WHERE MATCH (content) AGAINST ("今日の天気") ORDER BY MATCH (content) AGAINST ("今日の天気") DESC; id content score score_log score_log10 3 今日は晴れました。明日も晴れるでしょう。 262145 12.476653064769005 5.4185415786504745 4 今日は晴れましたが、明日は雨でしょう。 262145 12.476653064769005 5.4185415786504745 -- 須藤 功平 <kou****@clear*****> 株式会社クリアコード <http://www.clear-code.com/> (03-6231-7270) groongaサポート: http://groonga.org/ja/support/ パッチ採用はじめました: http://www.clear-code.com/recruitment/
