MinHashでElasticsearchの検索結果から重複を分散させる

最近Elasticsearchを使っているのですが、検索結果の多様性という観点から似たようなコンテンツが並ぶのを割けたいという場合があります。こんな場合に便利なのが以下の2つのElasticsearchプラグインです。

どちらも@shinsuke_sugayaさんが作られたものなのですが、前者はインデックスのフィールドにMinHashで計算したハッシュ値を持たせるもの、後者はフィールドの一致度から類似コンテンツが連続しないよう検索結果を並び替えてくれるものです。

MinHashとは？

MinHashとは文章中の各単語毎に複数のハッシュ関数でハッシュ値を求め、そのハッシュ値の最小値の一致度でドキュメントの一致度を判定するという手法です。詳しくは以下の記事などを参照してみてください。

上記の２つのプラグインを組み合わせることで、ElasticsearchのインデックスにMinHashで計算したハッシュ値を格納しておき、そのフィールドを指定してdynarankを使用することで同じようなコンテンツが並んでしまうことを防ぐことができる、というわけです。

実際に使ってみる

Elasticsearchに上記の２つのプラグインをインストールしておきます。

$ $ES_HOME/bin/plugin --install org.codelibs/elasticsearch-minhash/1.4.1
$ $ES_HOME/bin/plugin --install org.codelibs/elasticsearch-dynarank/1.4.2

まずは以下のような感じでアナライザを定義しておきます。ビット数はハッシュ対象のフィールドの長さによって適当に決めてください。感覚的にはブログのタイトル程度であれば16ビット、本文であれば64ビット〜128ビットくらいあればよいのではないかと思います。

{
  "settings": {
    "analysis": {
      "filter": {
        "minhash16":{
          "type":"minhash",
          "seed":0,
          "bit":1,
          "size":16
        }
      },
      "analyzer": {
        "minhash_analyzer16":{
          "filter" : ["minhash16"],
          "type" : "custom",
          "tokenizer" : "standard"
        }
      }
    }
  }
}

インデックスを以下のような感じで設定することでtitleフィールドのハッシュ値をtitle_minhash16フィールドに自動的に格納することができます。

"mappings": {
  ...
  "title": {
    "type": "string",
    "copy_to" : ["title_minhash16"]
  },
  "title_minhash16" : {
    "type" : "minhash",
    "minhash_analyzer" : "minhash_analyzer16"
  },
  ...
}

dynarankによる並び替えを有効にするために以下のコマンドを実行します。

$ curl -XPUT 'localhost:9200/<インデックス名>/_settings' -d '
{
  "index" : {
    "dynarank":{
      "script_sort":{
        "lang":"native",
        "script":"dynarank_diversity_sort",
        "params":{
          "diversity_fields":["title_minhash16"],
          "diversity_thresholds":[0.95]
        }
      },
      "reorder_size":40
     }
  }
}'

この状態で検索を行うとdynarankプラグインで並べ替えられた検索結果を得ることができます。

ただし、性能上の問題から並び替えは検索結果の上位からreorder_sizeで指定した件数までの中で行われます。この値を大きくすると分散しやすくなりますが、当然大きくしすぎると速度が遅くなります。そのため、想定される重複コンテンツの割合や１ページに表示する件数によって調節する必要があります。

まとめ

このようにElasticsearchではプラグインを活用することでMinHashを使った類似コンテンツの分散を簡単に行うことができます。また、dynarankプラグインのようにプラグインで検索結果を加工することができるので工夫次第で様々な用途に活用できるのではないでしょうか。

@shinsuke_sugayaさんはこのほかにも便利なElasticsearchプラグインをいろいろ作られているのでありがたく使わせていただくといいと思います。