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件) を見る

Solrで検索 (フィルタ, ソート, ファセット, ハイライト)

Solr IR

前回・前々回に引き続いて、Solrについてです。

今回は検索クエリで頻繁に使われる、フィルタ、ソート、ファセット、ハイライトについてまとめます。引き続き、チュートリアルと↓の本を参考にしています。

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

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

ohke.hateblo.jp

ohke.hateblo.jp

フィルタ

レスポンスで返す属性を限定する場合は、flを使います。

urlとtitleのみが欲しい場合、fl=url,titleとします。

http://localhost:8983/solr/kenikki/select?fl=url,title&q=*:*&rows=2&sort=published_datetime desc
[
    {
        "url":"https://ohke.hateblo.jp/entry/2018/11/17/230000",
        "title":"Python: LexRankで日本語の記事を要約する - け日記"
    },
    {
        "url":"https://ohke.hateblo.jp/entry/2018/11/10/230000",
        "title":"SQL ServerのテーブルをPandas DataFrameで読み書きする - け日記"
    }
]

ソート

特定のフィールドにマッチする場合に検索結果 (ランキング) の上位に持ってくる、などのソートはqfを使います。

例えばcontentを"協調フィルタリング"で検索すると以下のような結果が返ってきます。

http://localhost:8983/solr/kenikki/select?facet=on&fl=title&q=content:協調フィルタリング&rows=5
[
    { "title":"「Context-Aware Recommender Systems」まとめ - け日記" },
    { "title":"Pythonでレコメンドシステムを作る(ユーザベース協調フィルタリング) - け日記" },
    { "title":"Pythonでレコメンドシステムを作る(アイテムベース協調フィルタリング) - け日記" },
    { "title":"論文メモ: Item2Vec: Neural Item Embedding for Collaborative Filtering - け日記" },
    { "title":"Pythonでレコメンドシステムを作る(コンテンツベースフィルタリング) - け日記" }
]

もし大小が比較できる特定のフィールドでソートするなら、sortクエリパラメータでOKです。例えば、公開日付の降順であれば、以下のようにすれば最新5件が取得できます。

http://localhost:8983/solr/kenikki/select?fl=url,title&q=content:協調フィルタリング&rows=5&sort=published_datetime desc

テキストフィールドに限った、もう少し細かいケースを考えてみます。
検索文字列がtitleに入っているエントリの方が上位にランクインしやすくなってほしいなどの場合、qfが使えます。
例えば、qf=title^2 content^1とすると、titleの重みがcontentの重みよりも大きくする (ここでは2倍) ことで、上に来やすくなります。

http://localhost:8983/solr/kenikki/select?defType=dismax&fl=title&q=content:協調フィルタリング&qf=title^2 content^1&rows=5

結果としては、タイトルに"協調フィルタリング"を含むエントリが上位にランクインしやすくなりました。
あくまでソート時の重み付けですので、タイトルに検索文字列を含んでいなかったとしても、結果から除外されることはありません。
また、contentの重みも有効ですので、常にタイトルに文字列を含んでいるエントリが上に来るとは限りません。現に、下の結果ではタイトルにフィルタリングを含むエントリが、含まないエントリの下に来ています。常に上に持ってきたい場合は qf=title^100 content^1 などの極端な重み付けを行うと良いです。

[
    { "title":"Pythonでレコメンドシステムを作る(ユーザベース協調フィルタリング) - け日記" },
    { "title":"Pythonでレコメンドシステムを作る(アイテムベース協調フィルタリング) - け日記" },
    { "title":"「Context-Aware Recommender Systems」まとめ - け日記" },
    { "title":"Pythonでレコメンドシステムを作る(コンテンツベースフィルタリング) - け日記" },
    { "title":"論文メモ: Item2Vec: Neural Item Embedding for Collaborative Filtering - け日記" }
]

ファセット

クエリでの検索結果からさらに絞り込むために、カテゴリごとの件数を表示したい、というケースがあるかと思います。そうしたケースに使えるのがファセットです。

tagごとの件数を取得する場合、以下のようにfacet.field=tagで指定します。

http://localhost:8983/solr/kenikki/select?facet.field=tag&facet=on&fl=url,title&q=content:協調フィルタリング&rows=1&sort=published_datetime desc

そうすると、facet_counts.facet_fields.tagに各tagの件数がセットされて返ってきます。

{
  "responseHeader":{...},
  "response":{"numFound":7,"start":0,"docs":[
      {
        "url":"https://ohke.hateblo.jp/entry/2018/06/02/230000",
        "title":"Google AnalyticsのデータをBigQueryで集計・分析するときのテクニック集 - け日記"}]
  },
  "facet_counts":{
    "facet_queries":{},
    "facet_fields":{
      "tag":[
        "Recommender system",5,
        "Python",4,
        "BigQuery",1,
        "Google Analytics",1,
        "NLP",1,
        "読書メモ",1,
        "論文メモ",1,
        ".NET Core",0,
        "ASP.NET",0,...
    ]},
    "facet_ranges":{},
    "facet_intervals":{},
    "facet_heatmaps":{}}}

ハイライト

クエリとマッチした箇所を検索結果で強調表示したい時があるかと思います。Solrにはハイライトという機能で提供されてます。

以下のクエリではtitleとdescriptionをハイライトします。2つのパラメータを渡してます。

  • hl=onとすることで、ハイライトを有効化
  • hl.fl=title,descriptionとすることで、ハイライト表示するフィールドを設定
http://localhost:8983/solr/kenikki/select?fl=title&hl.fl=title,description&hl=on&q=content:Python&rows=2

hilightingにハイライト表示に関する結果が入ってます。
response.docsに対応するディクショナリとなっており、キーはidフィールドで、値はフィールドごとにemタグで強調表示加工されていることがわかります。

  • emタグはhl.simple.preとhl.simple.postに値を渡すことによって、別の文字列に置き換えることができます
    • 例えばhl.simple.pre=<u>&hl.simple.post=</u>とすると、uタグになります
{
  "responseHeader":{...},
  "response":{
    "numFound":56,
    "start":0,
    "docs":[
      { "title":"Visual Studio CodeでFlaskをデバッグする環境を作る on Mac - け日記" },
      { "title":"PythonでGoogle AnalyticsのデータをPostgreSQLへロードする - け日記" }
    ]
  },
  "highlighting":{
    "19f44dde-ec88-46f6-b629-6e813d552016":{
      "description":["仕事でFlaskを使ったアプリケーションを作る機会があり、Visual Studio Code(VSCode)で環境を整えましたので、その備忘録です。 前提 VS Code、<em>Python</em>、Flask"]
    },
    "8a19d435-0cc5-44da-9bc1-a38e440db4fe":{
      "title":["<em>Python</em>でGoogle AnalyticsのデータをPostgreSQLへロードする - け日記"],
      "description":["Google Analytics(GA)のデータを機械学習の勉強用に使えないかなと思ったことがきっかけです。 まずは、<em>Python</em>で扱いやすくするために、GAのデータをローカルのPostgreSQL"]
    }
  }
}

まとめ

今回はSolrでよく使うクエリとして、フィルタ、ソート、ファセット、ハイライトについて整理しました。

参考文献

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

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

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

Solrでスキーマの定義とドキュメントの登録を行う

Solr IR

前回の投稿に引き続き、Solrに慣れ親しんでいきます。

ohke.hateblo.jp

今回の投稿では、スキーマの定義、および、JSONを使ったドキュメント登録を行います。引き続き、チュートリアルと↓の本を参考にしています。

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

Solrサーバの起動とSolrCoreの作成

話を単純にするために、クラスタ (SolrCloud)ではなく、スタンドアロンで起動して、SolrCoreとして"kenikki"を作ります (前回の投稿も参考にしてみてください) 。

$ pwd
/tmp/solr/solr-7.5.0

$ ./bin/solr start
...
Waiting up to 180 seconds to see Solr running on port 8983 [/]
Started Solr server on port 8983 (pid=82558). Happy searching!

$ ./bin/solr create_core -c kenikki -d ./server/solr/configsets/_default
...
Created new core 'kenikki'

$ ls -l ./server/solr/
total 24
-rw-r--r--  1 onishik  wheel  3095  9 18 13:08 README.txt
drwxr-xr-x  4 onishik  wheel   128  9 18 13:08 configsets
drwxr-xr-x  5 onishik  wheel   160 12  1 11:34 kenikki
-rw-r--r--  1 onishik  wheel  2170  9 18 13:08 solr.xml
-rw-r--r--  1 onishik  wheel  1006  9 18 13:08 zoo.cfg

http://localhost:8983/ にアクセスすると、管理画面が表示されます。Core Adminに作成した"kenikki"が追加されていることも確認できます。

f:id:ohke:20181201114708p:plain

スキーマの定義

前回の投稿では、HTMLファイルを全く加工せずにPOSTしていましたので、一見不要そうなフィールドも多々有りました。今回は予めスキーマを定義します。

Solrのスキーマの属性は以下のようなものがあります (詳細はこちら) 。

  • name : フィールド名
  • type : 型 (Solr組み込みの型の一覧)
  • indexed : trueの場合、クエリで検索可能なフィールドになる (デフォルトはtrue)
  • stored : trueの場合、クエリの結果に値を含めることができる (デフォルトはtrue)
  • required : trueの場合、POST時の必須項目となる (デフォルトはfalse)
  • multiValued : trueの場合、複数の値を持つことができる (デフォルトはfalse)

今回は6つのフィールドを定義します。

  • published_datetimeは日時のため、pdate型で指定
  • tagは複数の値を持つ (ex. "Python","機械学習" など) ため、multiValuedをtrueにしてます
  • descriptionは、内容的にはcontentの一部なので検索のためにインデックスはさせないが、検索結果には表示することを想定して、storedはtrueにしてます
  • contentは、逆に検索に使うのでインデックスされている必要があるが、検索結果の表示には使わないことを想定して、storedはfalseにしてます
name type indexed stored required multiValued
url string ○ ○ ○ -
published_datetime pdate ○ ○ ○ -
title text_ja ○ ○ ○ -
tag string ○ ○ - ○
description text_ja - ○ - -
content text_ja ○ - ○ -

注意すべきは、string型とtext_ja型です。

  • stringは、solr.StrFieldクラスの実装で、完全一致やワイルドカード・正規表現などによる検索ができます
  • text_jaは、solr.TextFieldクラスの実装で、日本語に適したアナライザが設定されており、全角・半角などの表記揺れや、複合名詞による検索などにも対応できるようになります
    • アナライザでは文字フィルタ (charFilter) 、トークナイザ (tokenizer, 形態素解析器) 、トークンフィルタ(filter) を定義できます

いずれの型もmanaged-schemaに定義されてます。

...
  <fieldType name="string" class="solr.StrField" sortMissingLast="true" docValues="true"/>
...
  <fieldType name="text_ja" class="solr.TextField" autoGeneratePhraseQueries="false" positionIncrementGap="100">
    <analyzer>
      <tokenizer class="solr.JapaneseTokenizerFactory" mode="search"/>
      <filter class="solr.JapaneseBaseFormFilterFactory"/>
      <filter class="solr.JapanesePartOfSpeechStopFilterFactory" tags="lang/stoptags_ja.txt"/>
      <filter class="solr.CJKWidthFilterFactory"/>
      <filter class="solr.StopFilterFactory" words="lang/stopwords_ja.txt" ignoreCase="true"/>
      <filter class="solr.JapaneseKatakanaStemFilterFactory" minimumLength="4"/>
      <filter class="solr.LowerCaseFilterFactory"/>
    </analyzer>
  </fieldType>
...

スキーマは以下のように http://localhost:8983/solr/kenikki/schema にPOSTすることで定義できます。

$ curl -X POST -H 'Content-type:application/json' --data-binary '{
  "add-field": {
    "name": "url",
    "type": "string",
    "indexed": "true",
    "stored": "true",
    "required": "true",
    "multiValued": "false"
  },
  "add-field": {
    "name": "published_datetime",
    "type": "pdate",
    "indexed": "true",
    "stored": "true",
    "required": "true",
    "multiValued": "false"
  },
  "add-field": {
    "name": "title",
    "type": "text_ja",
    "indexed": "true",
    "stored": "true",
    "required": "true",
    "multiValued": "false"
  },
  "add-field": {
    "name": "tag",
    "type": "string",
    "indexed": "true",
    "stored": "true",
    "required": "false",
    "multiValued": "true"
  },
  "add-field": {
    "name": "description",
    "type": "text_ja",
    "indexed": "false",
    "stored": "true",
    "required": "false",
    "multiValued": "false"
  },
  "add-field": {
    "name": "content",
    "type": "text_ja",
    "indexed": "true",
    "stored": "false",
    "required": "true",
    "multiValued": "false"
  }
}', http://localhost:8983/solr/kenikki/schema

API経由の場合はmanaged-schemaファイルの方に書き込まれます。

...
  <field name="content" type="text_ja" multiValued="false" indexed="true" required="true" stored="false"/>
  <field name="description" type="text_ja" multiValued="false" indexed="false" required="false" stored="true"/>
  <field name="published_datetime" type="pdate" multiValued="false" indexed="true" required="true" stored="true"/>
  <field name="tag" type="string" multiValued="true" indexed="true" required="false" stored="true"/>
  <field name="title" type="text_ja" multiValued="false" indexed="true" required="true" stored="true"/>
  <field name="url" type="string" multiValued="false" indexed="true" required="true" stored="true"/>
...

またAPIへPOSTする以外に、schema.xmlファイル (ここではserver/solr/kenikki/conf/schema.xml) を作成・編集することでもスキーマを定義できます。

  • この場合は、SolrCoreのリフレッシュまたはSolr再起動が必要となります

ドキュメントの作成

上のスキーマに沿って各項目に値を投入するために、前回収集したけ日記のHTMLファイルから、JSONファイルを生成します。

  • JSON以外にも、XMLやCSVなどの形式でもOKです
  • 1つのHTMLファイルから、1つのJSONファイルを生成します
  • 各項目はBeautifulSoupで抽出してます
import os
import json
from bs4 import BeautifulSoup  # pip install beautifulsoup4

for file_name in os.listdir('/tmp/solr/documents/'):
    # HTMLファイル以外は除外
    if not file_name.endswith('.html'):
        continue
    
    # HTML文字列を取得
    with open('/tmp/solr/documents/' + file_name, 'r') as f:
        html = f.read()
    
    # BeautifulSoupで解析
    soup = BeautifulSoup(html, 'html.parser')
    
    # 各項目をHTMLから抽出
    entry_dict = {
        'url': soup.find('a', class_='entry-title-link bookmark')['href'],
        'published_datetime': soup.find('header', class_='entry-header').time['datetime'],
        'title': soup.title.string,
        'tag': [a.string for a in soup.find_all('a', class_='entry-category-link')],  # multiValueなのでリスト
        'description': soup.find('meta', property='og:description')['content'],
        'content': soup.find('div', class_='entry-content').text
    }
    
    # 1HTMLファイルにつき1JSONファイルでjsonディレクトリ以下に出力
    with open('/tmp/solr/documents/json/' + file_name.replace('.html', '.json'), 'w') as f:
        f.write(json.dumps(entry_dict, ensure_ascii=False))

ドキュメントの登録

生成されたJSONファイルをPOSTで登録します。前回と同じくpostスクリプトを使います。

$ ./bin/post -c kenikki /tmp/solr/documents/json/*
...
POSTing file 2018-11-17-230000.json (application/json) to [base]/json/docs
113 files indexed.
COMMITting Solr index changes to http://localhost:8983/solr/kenikki/update...
Time spent: 0:00:01.370

ドキュメントの検索

いくつかのパターンで検索してみます。

contentを"Pythonリスト"で検索すると、"Pythonリスト"そのものだけではなく、"Python"と"リスト"に分割してそれぞれ含むドキュメントがヒットします。text_jaで定義された形態素解析器によって、柔軟な検索が行われている例です。

http://localhost:8983/solr/kenikki/select?q=content:Pythonリスト

tagをワイルドカード検索するクエリです。tagに"Python"を含む記事がヒットします。

http://localhost:8983/solr/kenikki/select?q=tag:P?th*

published_datetimeで、2018年11月以降の記事を検索するクエリです。フィルタクエリfqを使うことで範囲検索ができます。

http://localhost:8983/solr/kenikki/select?fq=published_datetime:[2018-11-01T00:00:00Z TO NOW]&q=*:*

まとめ

今回はスキーマを定義して、JSONファイルでドキュメントを登録して、検索できるようにしました。

参考文献

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

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

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