形態素解析とNgramを併用したハイブリッド検索をSolrで実現する方法

f:id:vasilyjp:20180927112657j:plain

こんにちは、バックエンドエンジニアの塩崎です。 今まではiQONの全文検索用のインデックスには形態素解析だけを用いていましたが、先日Ngramも併用することで検索を改善しました。 その結果、検索結果のヒット数が向上し、なおかつ検索ノイズの増加を軽微なものに抑えることができました。

この記事では、Ngramを併用することのメリット、およびそれをApache Solrで利用する方法について紹介します。

欲しい情報が見つからないとは

そもそも、「検索したけど欲しい情報が見つからない状態」とはどのような状態でしょうか？ ここではその状態を以下の2つの状態に分解して考えてみます。

欲しい情報の数が少ない

1つ目の状態は「欲しい情報が検索結果中に少ない」状態です。 例えば、旅行情報サイトで「東京」と検索した時にDBの中には数千件のデータがあるのに検索結果数がわずか数件しかないような状態です。

f:id:vasilyjp:20170215225024p:plain

欲しくない情報の数が多い

2つ目の状態は「検索結果中の欲しくない情報の数が多い」状態です。 「東京」と検索した時に、東京の情報以外に京都、大阪などの他の地域の情報が検索結果に含まれるような状態です。

f:id:vasilyjp:20170215224829p:plain

実際は2つの状態が同時に起こっている

実際の欲しいものが見つからない状態は上記の2つの状態が同時に発生していることが多いです。 つまり、ユーザーの欲しい情報全てを検索結果として返しておらず、また、ユーザーの欲しくない情報も検索結果として返している状態です。

ベン図で表すと以下のようになります。 DBに格納されている全情報を、検索結果として返したか否か、欲しかった情報か否かという2軸で分類しています。

f:id:vasilyjp:20170215224927p:plain

そして、これ以降の説明のためにそれぞれの集合に名前をつけます。 検索結果として返していて、なおかつユーザーの求めていた情報を「正しい結果」、検索結果として返しているのに、ユーザーが求めていない情報を「検索ノイズ」、ユーザーが求めているのに、検索結果に含ませない情報を「検索漏れ」とします。

ちなみに、情報検索の分野では、それぞれを「TruePositive」、「FlasePositive」、「FalseNegative」と呼びます。

この図で検索漏れが多い状態が上で説明した状態の1つ目の状態、検索ノイズが多い状態が2つ目の状態に相当します。検索結果の改善とは検索ノイズと検索漏れの数を減らし、検索結果と欲しい情報を一致させることに他なりません。

しかし、これら2つを減らすことはトレードオフの関係にあります。どちらか1つを改善することによってもう1つが悪化してしまうことが多くあります。

検索インデックスの種類とその利点・欠点

全文検索エンジンの中で行なわれているインデックス処理と、その前段階に行なわれる単語分解について説明します。 全文検索エンジンは検索処理を高速化するために、転置インデックスというインデックスを生成します。 転置インデックスは文章中の単語をキー、その単語が出現するドキュメントの配列をバリューとする連想配列です。

このあたりについては先日公開したTECH BLOGの記事の前半部分で詳しく説明しているので、よろしければご覧ください。

Solr 6でneologdが組み込まれたkuromojiを使う方法

転置インデックスの生成のためには、ドキュメントを単語に分解する必要があります。 日本語のような単語と単語の間が空白で区切られていない言語を単語分解するために、Ngramと形態素解析という2つの手法があります。

それぞれの特徴について説明します。

Ngram

Ngramは文章を機械的にN文字づつに区切って単語分解する方法です。 何文字ごとに区切るかでNの部分が変わり、特にN=2の場合はbigram、N=3の場合はtrigramとも言います。 これ以降では説明のためにN=2(bigram)を利用します。

bigramではドキュメントを2文字ごとに区切って、その結果を単語としてみなします。 例えば、「東京都美術館」というドキュメントは以下の5つの単語に分解されます。

「東京」「京都」「都美」「美術」「術館」

そして、検索を行うときには、検索クエリを同様に単語分割して、それらのANDで結合します。 例えば、「美術館」という検索クエリに対しては「美術 AND 術館」という条件で検索を行います。

このようにすることによってN文字以上の任意の部分文字列について検索漏れがなくなることが保証されるのがNgramの利点です。 一方で「京都」という検索クエリに対してもこの「東京都美術館」がヒットしてしまうことがNgramの欠点です。

利点：部分一致検索ができることが保証されている

欠点：検索ノイズが多い

形態素解析

形態素解析による単語分割は、事前に用意した辞書を用いて、文法的に意味のある単位で単語分割を行います。 そのため、Ngramを使用した時の問題は起こりづらいことが利点です。

一方で、辞書を事前に用意する必要があり、辞書の性能が低いと検索性能が悪化してしまいます。 例えば「外国人参政権」を「外国」「人参」「政権」と分解してしまうと、そのドキュメントは「参政権」という検索クエリにヒットしなくなってしまいます。

また、SolrやElasticSearchに標準で搭載されている形態素解析器であるkuromojiはIPA辞書を利用していますが、この辞書は特定領域の固有名詞にそこまで強いわけではないという弱点があります。 そのため、本来は1単語になるべき固有名詞が複数の単語に分解されてしまうことがままあります。

例：「ロクシタン」 → 「ロク」「シタン」

一方で、固有名詞を一単語とすることにも別の問題があります。 例えば、「関西国際空港」という固有名詞を一単語としてインデックスすると、「国際空港」や「空港」といった検索クエリで「関西国際空港」が含まれるドキュメントがヒットしなくなってしまいます。 これを解消するために、「関西国際空港」という単語をさらに分割して、「関西」「国際」「空港」の3単語と合わせて合計で4単語をインデックスする機能がkuromojiに備わっています。 しかし、このような挙動も辞書や形態素解析器依存であり、必ずしも部分一致検索ができる保証はありません。

利点：検索ノイズが少ない

欠点：辞書の性能によっては検索漏れが多い

形態素解析とNgramの併用

Ngram、形態素解析の利点欠点を検索ノイズの数、検索漏れの数という観点で以下の表にまとめます。

検索ノイズ 検索漏れ
Ngram 多い 少ない
形態素解析 少ない 多い

この図からも検索ノイズを減らすことと検索漏れを減らすことがトレードオフの関係にあることがわかります。

しかし、これら2つを併用することによって、それぞれを単独で使用する場合に比べて、検索漏れの数を減らし、検索ノイズの数を実質的に減らすことが可能です。

併用するための具体的な手法は以下のようなものになります。

インデックス生成処理

  1. ドキュメントに対してNgramによるインデックスを生成する
  2. 形態素解析によるインデックスも生成する

検索処理

  1. Ngramと形態素解析によるインデックスに対して同時に検索を行う
  2. 形態素解析によるインデックスの結果が先頭になりやすいように重みを付けて検索結果をマージする

f:id:vasilyjp:20170215225213p:plain

Icons made by Madebyoliver from www.flaticon.com is licensed by CC 3.0 BY

2つの検索結果をマージすることによって、検索漏れを減らします。 しかし、ただ単にマージしてしまうと、検索ノイズが増えてしまいます。 形態素解析の結果を先頭になりやすいようにマージすることが、この併用処理のキモです。 ユーザーが検索結果を見るときにはその先頭から見るため、先頭に求める情報があった場合はそこで満足してそれ以降の結果を見るのをストップすることがあります。 そのようなケースにおいては実質的に検索ノイズは増えていないと考えることができます。

形態素解析とNgramを併用するクエリをSolrで作る方法

具体的なSolrの設定ファイルの書き方、クエリの書き方について説明します。

これらの動作はSolr 6.2.1で確認していますが、特定のバージョンに依存した書き方はしていないため、他のバージョンのSolrでも動くかと思います。

インデックス生成方法

まずはインデックスの生成部分です。 以下の3つの情報をmanaged-schemaに書き込みます。

フィールドタイプ定義

Ngramでインデックスの生成を行うためのfieldTypeであるtext_ja_ngramと、形態素解析でインデックスの生成を行うフィールドであるtext_jaを定義しています。

<fieldType name="text_ja_ngram" class="solr.TextField" autoGeneratePhraseQueries="true" positionIncrementGap="100">
  <analyzer>
    <charFilter class="solr.ICUNormalizer2CharFilterFactory" name="nfkc"/>
    <tokenizer class="solr.NGramTokenizerFactory" minGramSize="2" maxGramSize="2"/>
    <filter class="solr.LowerCaseFilterFactory"/>
  </analyzer>
</fieldType>

<fieldType name="text_ja" class="solr.TextField" autoGeneratePhraseQueries="false" positionIncrementGap="100">
  <analyzer>
    <charFilter class="solr.ICUNormalizer2CharFilterFactory" name="nfkc"/>
    <tokenizer class="solr.JapaneseTokenizerFactory" mode="search" userDictionary="lang/userdict_ja.txt"/>
    <filter class="solr.SynonymFilterFactory" synonyms="synonyms.txt" ignoreCase="true" expand="true"/>
    <filter class="solr.JapaneseBaseFormFilterFactory"/>
    <filter class="solr.JapanesePartOfSpeechStopFilterFactory" tags="lang/stoptags_ja.txt"/>
    <filter class="solr.StopFilterFactory" words="lang/stopwords_ja.txt" ignoreCase="true"/>
    <filter class="solr.JapaneseKatakanaStemFilterFactory" minimumLength="4"/>
    <filter class="solr.LowerCaseFilterFactory"/>
  </analyzer>
</fieldType>

フィールド定義

そして、これらのfieldTypeのfieldを定義します。

<field name="search_ngram" type="text_ja_ngram" multiValued="true" indexed="true" required="false" stored="true"/>
<field name="search" type="text_ja" multiValued="true" indexed="true" required="false" stored="true"/>

他のフィールドからのデータのコピー

最後に、copyFieldを使い、検索対象としたいフィールドを上記の2つのフィールドにコピーします。

<copyField source="title" dest="search_ngram" />
<copyField source="title" dest="search" />
<copyField source="description" dest="search_ngram" />
<copyField source="description" dest="search" />
...

これでインデックス生成部分の設定は完了です。 試しにAnalysis機能でこれらが正常に働いていることを確認してみます。

  • Ngramによるインデックス f:id:vasilyjp:20170215225304p:plain

  • 形態素解析によるインデックス

f:id:vasilyjp:20170215225315p:plain

クエリの投げ方

次にこれらのフィールドに対して投げるクエリを説明します。

複数のフィールドに対して横断的に検索をするために、eDisMaxクエリを利用します。 以下のようなパラメーターでクエリを投げることで、両方のフィールドを利用して検索を行うことができます。

  • q=<検索したい文字列>
  • defType=edismax
  • qf=search100+search_ngram50

qfで指定している100と50はそれぞれのフィールドの重みです。 重みが大きいほど、そのフィールドでヒットしたドキュメントが先頭に出やすくなります。 このあたりのチューニングは検索結果を見ながら値を変えてゆく必要があります。

まとめ

形態素解析とNgramの併用によって、検索漏れを減らし、検索ノイズの増加を抑制することができました。 その結果として、特にiQONではブランド名の略語で商品の検索ができるようになりました。 例えば、「JIMMY」という検索クエリで「JIMMY CHOO」の商品をヒットさせることができるようになりました。

iQONで扱う商品数は日に日に増えており、昨年10月の時点では1200万点に達しました。

ファッションアプリ「iQON」、掲載アイテム数が累計1,200万点突破! 〜新規ファッションECと提携し更なる事業拡大を加速〜

これらの膨大な商品の中からユーザーの好みに合った商品を探すことは非常に難しい課題です。 本記事で紹介した手法はこの課題に対する1つのアプローチであり、iQONではこれ以外にも様々な方法でユーザーに欲しい商品が見つかる体験を提供することを考えています。

例えば以下の記事ではディプラーニングを活用した画像ベースでの検索を紹介しています。

ディープラーニングによるファッションアイテム検出と検索

VAEとGANを活用したファッションアイテム検索システム

このチャレンジングな課題を解決してみたいという方は以下のリンクからご応募ください。

カテゴリー