Solrの類似度アルゴリズム (TF*IDF, BM25)

Solr IR

引き続きSolrに触れていきます。

今回はSolrの検索で使われる類似度 (similarity) についてです。

前提

Solrのダウンロードとkenikkiコレクションの追加まで完了している状態を前提として進めます。

ohke.hateblo.jp

ohke.hateblo.jp

類似度

SolrのコアエンジンであるLuceneは、text項目の検索において、ドキュメントがクエリとどの程度マッチしているかの度合い (類似度) を計算し、この類似度が高いドキュメントの順番で結果を返すようになっています。

この類似度の計算はクエリとドキュメントの特徴ベクトルの内積によって行われますが、このベクトルの計算方法にはバリエーションがあります。今回はよく使われる2つについて取り上げます。

  • TF*IDF
  • BM25

類似度の設定

類似度の設定はschema.xmlを編集することで行います。

LuceneではいずれもSimilarityFactoryを継承したファクトリクラスを指定します。

例えば、TF*IDFの場合は以下のように指定します。

<schema name="default-config" version="1.6">
...
  <similarity class="solr.ClassicSimilarityFactory"/>
...
</schema>

なお、Solr 6.0以降のデフォルトはBM25となってます。

TF*IDF

まずはTF*IDFです。

TF*IDFの計算式に以下になります。要するに、文書内での出現頻度が高く、かつ、他の文書では他の文書で現れにくい単語は、その文書を特徴づけるものだろう、として重みを強くするという手法です。

  • w(t,d)は、文書dにおける単語tの重み
  • tf(t, d)は、文書d内の単語tの出現頻度で、高いほどdでは重要な単語
  • idf(t)は、単語tが出現するドキュメント数の逆数で、小さいほど他の文書でも現れる情報量の少ない単語
  • 長い文書ほどTFが高くなりやすくなるため、3項目で文書長L(d)の二乗根で割ることでペナルティを与えています

w_{TFIDF}(t,d)=tf(t,d) \times idf(t)=tf(t,d) \times log\frac{N}{df(t)} \times \frac{1}{\sqrt{L(d)}}

設定方法は上述してます。

BM25

BM25はTF*IDFを拡張したモデルとなります。

TF*IDFは、文書内での単語数に比例してTFの値が大きくなります。直感的には、1回目に現れたときに持つ情報量に比べると、100回目に現れた時に持つ情報量は小さいはずです。
そこでパラメータk1を追加し、出現回数が大きくなるとTFの上がり幅を減衰させるようにします。

また、文書が長くなればなるほど、当然ながらTFの値も大きくなり、結果として長い文書であれば上位に来やすくなります。
文書の長さを考慮するために、文書dの長さL(d)を全文書の平均長 L_{ave} で割った値を分母とすることで、長い文書についてはペナルティとなるように働きます。bはペナルティの度合いを調整するパラメータです。

Solrではk1=1.2, b=0.75がデフォルト値となってます。

w_{BM25}(t,d) = \frac{(k1+1) \times tf(t,d)}{k1 \times ((1.0-b) + b \times L(d) / L_{ave})+tf(t,d)} \times idf(t)

設定方法は以下のとおりです。

<schema name="default-config" version="1.6">
...
  <similarity class="solr.BM25SimilarityFactory"/>
...
</schema>

検索結果の比較

いくつかの検索結果で比較してみます。なお、debug=trueを渡すことで、類似度計算の過程を出力することができます。

"SQL" AND "分析"

"SQL"と"分析"で検索してみます。

http://localhost:8983/solr/kenikki/select?q=content:SQL,分析&q.op=AND&debug=true

TF*IDFでは、2番目にBigQuery主体の記事が来ています。

  1. 「データ集計・分析のためのSQL入門」 まとめ - け日記
  2. Google AnalyticsのデータをBigQueryで集計・分析するときのテクニック集 - け日記
  3. 「10年戦えるデータ分析入門」第1部 まとめ - け日記

一方、BM25では、BigQueryの記事は3番目にランクダウンしています。

  1. 「データ集計・分析のためのSQL入門」 まとめ - け日記
  2. 「10年戦えるデータ分析入門」第1部 まとめ - け日記
  3. Google AnalyticsのデータをBigQueryで集計・分析するときのテクニック集 - け日記

BigQueryの記事は"SQL"のTFが大きい値 (17) だったため、TF*IDFでは2番目に来ていました。
しかしBM25では、"SQL"と"分析"の2つの単語をバランス良く含んでいた (それぞれ8と9) 、"10年戦えるデータ分析入門"が2位となりました。

複数の単語で検索する場合、BM25ではk1によるペナルティが働くので、各単語をバランスの良く含む文書の方が上に来やすくなることがわかります。

"janome" AND "analyzer"

"janome"と"analyzer"で検索してみます。

http://localhost:8983/solr/kenikki/select?q=content:janome&q.op=AND&debug=true

TF*IDFでは、janomeのanalyzerがメインテーマの記事が2番目に来ています。

  1. Python: LexRankで日本語の記事を要約する - け日記
  2. Python janomeのanalyzerが便利 - け日記
  3. Word2Vecで京都観光に関するブログ記事の単語をベクトル化する - け日記

一方、BM25では、上で2位だった記事が1位に上がっています。

  1. Python janomeのanalyzerが便利 - け日記
  2. Python: LexRankで日本語の記事を要約する - け日記
  3. Word2Vecで京都観光に関するブログ記事の単語をベクトル化する - け日記

TFで見ると、"Python janomeのanalyzerが便利"の方が"janome"も"analyzer"も高い値でした。
が、TF*IDFでは 1/\sqrt{L(d)} が強すぎて2位に落としていました。

BM25では、平均長で割り算し、かつ、パラメータbでコントロールすることで、TF*IDFよりは緩やかなペナルティになっているようです。

まとめ

今回はSolrの類似度計算のアルゴリズムであるTF*IDFとBM25について整理しました。

参考文献

Solrの設定等についてはこちらを参考にしました。

[改訂第3版]Apache Solr入門――オープンソース全文検索エンジン (Software Design plus)

[改訂第3版]Apache Solr入門――オープンソース全文検索エンジン (Software Design plus)

  • 作者: 打田智子,大須賀稔,大杉直也,西潟一生,西本順平,平賀一昭,株式会社ロンウイット,株式会社リクルートテクノロジーズ
  • 出版社/メーカー: 技術評論社
  • 発売日: 2017/04/27
  • メディア: 大型本
  • この商品を含むブログを見る

類似度アルゴリズム、特にBM25についてはこちらを参考にしました。

情報検索の基礎

情報検索の基礎

  • 作者: Christopher D.Manning,Prabhakar Raghavan,Hinrich Schutze,岩野和生,黒川利明,濱田誠司,村上明子
  • 出版社/メーカー: 共立出版
  • 発売日: 2012/06/23
  • メディア: 単行本
  • 購入: 2人 クリック: 69回
  • この商品を含むブログ (5件) を見る