MinHash

MinHash トークンフィルター

トークンストリームの署名を生成するために MinHash 技術を使用します。MinHash 署名を使用して、ドキュメントの類似性を推定できます。類似性検索のための min_hash トークンフィルターの使用 を参照してください。

min_hash フィルターは、トークンストリームに対して次の操作を順に実行します：

• 1. ストリーム内の各トークンをハッシュ化します。
• 2. ハッシュをバケットに割り当て、各バケットの最小ハッシュのみを保持します。
• 3. 各バケットから最小ハッシュをトークンストリームとして出力します。

このフィルターは、Lucene の MinHashFilter を使用します。

設定可能なパラメータ

• bucket_count
• (オプション、整数) ハッシュが割り当てられるバケットの数。デフォルトは 512。
• hash_count
• (オプション、整数) ストリーム内の各トークンをハッシュ化する方法の数。デフォルトは 1。
• hash_set_size
• (オプション、整数) 各バケットから保持するハッシュの数。デフォルトは 1。
  ハッシュはサイズの昇順で保持され、バケットの最小ハッシュから始まります。
• with_rotation
• (オプション、ブール値) true の場合、フィルターは hash_set_size が 1 の場合、最初の非空バケットの値で空のバケットをその円形の右側に埋めます。 bucket_count 引数が 1 より大きい場合、このパラメータのデフォルトは true になります。そうでない場合、このパラメータのデフォルトは false になります。

min_hash フィルターの設定に関するヒント

• min_hash フィルターの入力トークンは、通常、shingle トークンフィルター から生成された k-words シングルであるべきです。k は、特定のシングルがドキュメントに出現する確率が低くなるように十分大きく選択する必要があります。同時に、内部的に各シングルが 128 ビットのハッシュにハッシュ化されるため、k は、すべての異なる k-words シングルが最小の衝突で 128 ビットのハッシュにハッシュ化されるように十分小さく選択する必要があります。
• hash_count、bucket_count、hash_set_size パラメータの異なる引数をテストすることをお勧めします：
  • 精度を向上させるために、bucket_count または hash_set_size 引数を増やします。bucket_count および hash_set_size の値が高いほど、異なるトークンが異なるバケットにインデックスされる可能性が高くなります。
  • 再現率を向上させるために、hash_count 引数の値を増やします。たとえば、hash_count を 2 に設定すると、各トークンが 2 通りの異なる方法でハッシュ化され、検索の潜在的な候補の数が増えます。
• デフォルトでは、min_hash フィルターは各ドキュメントに対して 512 トークンを生成します。各トークンのサイズは 16 バイトです。これは、各ドキュメントのサイズが約 8Kb 増加することを意味します。
• min_hash フィルターは Jaccard 類似性に使用されます。これは、ドキュメントが特定のトークンを何回含むかは重要ではなく、含むかどうかだけが重要であることを意味します。

類似性検索のための min_hash トークンフィルターの使用

min_hash トークンフィルターを使用すると、類似性検索のためにドキュメントをハッシュ化できます。類似性検索、または最近傍検索は複雑な問題です。単純な解決策は、クエリドキュメントとインデックス内のすべてのドキュメントとの間で徹底的なペアワイズ比較を必要とします。インデックスが大きい場合、これは禁止的な操作です。類似性検索をより実用的かつ計算上実現可能にするために、いくつかの近似最近傍検索ソリューションが開発されました。これらのソリューションの1つは、ドキュメントのハッシュ化を含みます。

ドキュメントは、類似したドキュメントが同じハッシュコードを生成し、同じハッシュバケットに配置される可能性が高く、異なるドキュメントが異なるハッシュバケットにハッシュ化される可能性が高い方法でハッシュ化されます。このタイプのハッシュ化は、局所感度ハッシュ化（LSH）として知られています。

ドキュメント間の類似性を構成するものに応じて、さまざまな LSH 関数 が提案されています。Jaccard 類似性 の場合、人気のある LSH 関数は MinHash です。MinHash がドキュメントの署名を生成する方法の一般的なアイデアは、インデックスの語彙全体に対してランダムな順列を適用し（語彙のランダム番号付け）、ドキュメントのためにこの順列の最小値を記録することです（ドキュメントに存在する語彙の単語の最小値）。順列は何度も実行されます。すべての最小値を組み合わせることで、ドキュメントの署名が構成されます。

実際には、ランダムな順列の代わりに、いくつかのハッシュ関数が選択されます。ハッシュ関数は、ドキュメントの各トークンのハッシュコードを計算し、それらの中から最小のハッシュコードを選択します。すべてのハッシュ関数からの最小ハッシュコードが組み合わされて、ドキュメントの署名が形成されます。

アナライザーのカスタマイズと追加

min_hash フィルターをカスタマイズするには、それを複製して新しいカスタムトークンフィルターの基礎を作成します。設定可能なパラメータを使用してフィルターを変更できます。

たとえば、次の インデックス作成 API リクエストは、次のカスタムトークンフィルターを使用して新しい カスタムアナライザー を構成します：

• my_shingle_filter、カスタム shingle フィルター。my_shingle_filter は、5 ワードのシングルのみを出力します。
• my_minhash_filter、カスタム min_hash フィルター。my_minhash_filter は、各 5 ワードのシングルを 1 回ハッシュ化します。その後、ハッシュを 512 バケットに割り当て、各バケットの最小ハッシュのみを保持します。

リクエストは、カスタムアナライザーを fingerprint フィールドマッピングに割り当てます。

Python

resp = client.indices.create(
   index="my-index-000001",
   settings={
   "analysis": {
   "filter": {
   "my_shingle_filter": {
   "type": "shingle",
   "min_shingle_size": 5,
   "max_shingle_size": 5,
   "output_unigrams": False
   },
   "my_minhash_filter": {
   "type": "min_hash",
   "hash_count": 1,
   "bucket_count": 512,
   "hash_set_size": 1,
   "with_rotation": True
   }
   },
   "analyzer": {
   "my_analyzer": {
   "tokenizer": "standard",
   "filter": [
   "my_shingle_filter",
   "my_minhash_filter"
   ]
   }
   }
   }
   },
   mappings={
   "properties": {
   "fingerprint": {
   "type": "text",
   "analyzer": "my_analyzer"
   }
   }
   },
)
print(resp)

Ruby

response = client.indices.create(
  index: 'my-index-000001',
  body: {
   settings: {
   analysis: {
   filter: {
   my_shingle_filter: {
   type: 'shingle',
   min_shingle_size: 5,
   max_shingle_size: 5,
   output_unigrams: false
   },
   my_minhash_filter: {
   type: 'min_hash',
   hash_count: 1,
   bucket_count: 512,
   hash_set_size: 1,
   with_rotation: true
   }
   },
   analyzer: {
   my_analyzer: {
   tokenizer: 'standard',
   filter: [
   'my_shingle_filter',
   'my_minhash_filter'
   ]
   }
   }
   }
   },
   mappings: {
   properties: {
   fingerprint: {
   type: 'text',
   analyzer: 'my_analyzer'
   }
   }
   }
  }
)
puts response

Js

const response = await client.indices.create({
  index: "my-index-000001",
  settings: {
   analysis: {
   filter: {
   my_shingle_filter: {
   type: "shingle",
   min_shingle_size: 5,
   max_shingle_size: 5,
   output_unigrams: false,
   },
   my_minhash_filter: {
   type: "min_hash",
   hash_count: 1,
   bucket_count: 512,
   hash_set_size: 1,
   with_rotation: true,
   },
   },
   analyzer: {
   my_analyzer: {
   tokenizer: "standard",
   filter: ["my_shingle_filter", "my_minhash_filter"],
   },
   },
   },
  },
  mappings: {
   properties: {
   fingerprint: {
   type: "text",
   analyzer: "my_analyzer",
   },
   },
  },
});
console.log(response);

Console

PUT /my-index-000001
{
  "settings": {
   "analysis": {
   "filter": {
   "my_shingle_filter": {
   "type": "shingle",
   "min_shingle_size": 5,
   "max_shingle_size": 5,
   "output_unigrams": false
   },
   "my_minhash_filter": {
   "type": "min_hash",
   "hash_count": 1,
   "bucket_count": 512,
   "hash_set_size": 1,
   "with_rotation": true
   }
   },
   "analyzer": {
   "my_analyzer": {
   "tokenizer": "standard",
   "filter": [
   "my_shingle_filter",
   "my_minhash_filter"
   ]
   }
   }
   }
  },
  "mappings": {
   "properties": {
   "fingerprint": {
   "type": "text",
   "analyzer": "my_analyzer"
   }
   }
  }
}