メインコンテンツまでスキップ

MINHASH_LSH

大規模な機械学習データセットでは、特に大規模言語モデル（LLM）のトレーニングコーパスをクリーニングするようなタスクにおいて、効率的な重複排除と類似検索が重要です。数百万または数十億のドキュメントを扱う場合、従来の完全一致は遅すぎてコストが高くなります。

Zilliz Cloud の MINHASH_LSH インデックスは、2 つの強力な手法を組み合わせることで、高速でスケーラブルかつ正確な近似重複排除を可能にします。

  • MinHash: コンパクトな署名（または「フィンガープリント」）を迅速に生成し、ドキュメントの類似性を推定します。

  • Locality-Sensitive Hashing（LSH）: MinHash 署名に基づいて、類似したドキュメントのグループを迅速に見つけます。

このガイドでは、Zilliz Cloud で MINHASH_LSH を使用するための概念、事前準備、セットアップ、ベストプラクティスについて説明します。

概要​

展開して仕組みを確認する

Jaccard 類似度​

Jaccard 類似度は、2 つの集合 A と B の重なりを測るもので、次のように定義されます。

J(A,B)=∣A∩B∣∣A∪B∣J(A, B) = \frac{|A \cap B|}{|A \cup B|}

値の範囲は 0（完全に互いに素）から 1（同一）です。

ただし、大規模データセット内のすべてのドキュメントペア間で Jaccard 類似度を正確に計算するには、計算コストが高くなります。n が大きい場合、時間とメモリの両方で O(n²) となります。そのため、LLM トレーニングコーパスのクリーニングやウェブ規模のドキュメント分析といったユースケースには現実的ではありません。

MinHash 署名：Jaccard 類似度の近似​

MinHash は、Jaccard 類似度を効率的に推定する確率的な手法です。各集合をコンパクトな署名ベクトルに変換し、集合の類似性を効率的に近似するのに十分な情報を保持します。

基本的な考え方：

2 つの集合が類似しているほど、それらの MinHash 署名が同じ位置で一致する可能性が高くなります。この性質により、MinHash は集合間の Jaccard 類似度を近似できます。

この性質により、MinHash は集合全体を直接比較することなく、集合間の Jaccard 類似度を近似できます。

MinHash のプロセスは次のとおりです。

  1. シングリング: ドキュメントを、重なり合うトークンシーケンス（シングル）の集合に変換します

  2. ハッシュ化: 各シングルに複数の独立したハッシュ関数を適用します

  3. 最小値の選択: 各ハッシュ関数について、すべてのシングルにわたる最小ハッシュ値を記録します

プロセス全体を以下の図に示します。

CCzEwT7uchMqI6bsxRJcK1qenEh

Notes

使用するハッシュ関数の数によって、MinHash 署名の次元が決まります。次元が高いほど近似の精度が向上しますが、その分ストレージと計算のコストが増加します。

MinHash 用の LSH​

MinHash 署名はドキュメント間の正確な Jaccard 類似度を計算するコストを大幅に削減しますが、すべての署名ベクトルのペアを網羅的に比較するのは大規模環境では依然として非効率です。

この問題を解決するために、LSH を使用します。LSH は、類似したアイテムが高い確率で同じ「バケット」にハッシュされるようにすることで、高速な近似類似検索を実現します。これにより、すべてのペアを直接比較する必要がなくなります。

プロセスは次のとおりです。

  1. 署名の分割：

    n 次元の MinHash 署名は b 個のバンドに分割されます。各バンドには r 個の連続したハッシュ値が含まれるため、署名全体の長さは n = b × r を満たします。

    たとえば、128 次元の MinHash 署名（n = 128）を 32 個のバンド（b = 32）に分割する場合、各バンドには 4 個のハッシュ値（r = 4）が含まれます。

  2. バンド単位のハッシュ化：

    分割後、各バンドは標準的なハッシュ関数を使用して個別に処理され、バケットに割り当てられます。2 つの署名がバンド内で同じハッシュ値を生成する場合、つまり同じバケットに格納される場合は、一致候補と見なされます。

  3. 候補の選択：

    少なくとも 1 つのバンドで衝突するペアが、類似候補として選択されます。

Notes

なぜ機能するのか

数学的には、2 つの署名の Jaccard 類似度が ss である場合、次のようになります。

  • 1 行（ハッシュ位置）で一致する確率は ss です

  • バンド内のすべての rr 行で一致する確率は srs^r です

  • 少なくとも 1 つのバンドで一致する確率は $1 - (1 - s^r)^b$ です

詳細については、Locality-sensitive hashing を参照してください。

128 次元の MinHash 署名を持つ 3 つのドキュメントを考えます。

E1dewMnqshua0ib7aHmcL10lnIe

まず、LSH は 128 次元の署名を、それぞれ 4 つの連続した値を持つ 32 個のバンドに分割します。

PhSMwS74rh25oybv9Docmfionze

次に、各バンドはハッシュ関数を使用して異なるバケットにハッシュされます。バケットを共有するドキュメントのペアが類似候補として選択されます。以下の例では、ドキュメント A とドキュメント B のハッシュ結果がバンド 0 で衝突するため、この 2 つが類似候補として選択されます。

RfmMwNkIvhlUFSb11alcP8fqnmf

Notes

バンドの数は mh_lsh_band パラメーターで制御されます。詳細については、インデックス構築パラメーター を参照してください。

MHJACCARD：MinHash 署名の比較​

MinHash 署名は、固定長のバイナリベクトルを使用して集合間の Jaccard 類似度を近似します。ただし、これらの署名は元の集合を保持しないため、JACCARD、L2、COSINE などの標準的なメトリクスを直接適用して比較することはできません。

この課題に対処するため、Zilliz Cloud は MinHash 署名の比較専用に設計された MHJACCARD という特殊なメトリクスタイプを提供しています。

Zilliz Cloud で MinHash を使用する場合は、次の条件を満たす必要があります。

  • ベクトルフィールドの型は BINARY_VECTOR であること

  • index_type は MINHASH_LSH（または BIN_FLAT）であること

  • metric_type は MHJACCARD に設定すること

他のメトリクスを使用すると、無効になるか、誤った結果が返されます。

このメトリクスタイプの詳細については、MHJACCARD を参照してください。

重複排除ワークフロー​

MinHash LSH を利用した重複排除プロセスにより、Zilliz Cloud はコレクションに挿入する前に、ほぼ重複したテキストや構造化レコードを効率的に特定して除外できます。

It9wwbCFwhfT0RbwosAcGltZneb

  1. チャンク化と前処理: 入力されたテキストデータまたは構造化データ（レコード、フィールドなど）をチャンクに分割し、テキストを正規化（小文字化、句読点の削除）し、必要に応じてストップワードを削除します。

  2. 特徴量の構築: MinHash に使用するトークンセットを構築します（テキストの場合はシングル、構造化データの場合はフィールドトークンの連結など）。

  3. MinHash 署名の生成: 各チャンクまたはレコードの MinHash 署名を計算します。

  4. バイナリベクトルへの変換: 署名を Milvus と互換性のあるバイナリベクトルに変換します。

  5. 挿入前の検索: MinHash LSH インデックスを使用して、対象のコレクションで入力アイテムのほぼ重複を検索します。

  6. 挿入と保存: 一意のアイテムのみをコレクションに挿入します。これらのアイテムは、将来の重複排除チェックで検索可能になります。

事前準備​

Zilliz Cloud で MinHash LSH を使用する前に、まず MinHash 署名を生成する必要があります。このコンパクトなバイナリ署名は集合間の Jaccard 類似度を近似するもので、Zilliz Cloud での MHJACCARD ベースの検索に必要です。

Notes

MINHASH_LSH インデックス用の MinHash 署名は、次の 2 つの方法で準備できます。

  • 外部ツールを使用して署名を自分で生成し、BINARY_VECTOR フィールドに挿入する、または

  • 組み込みの MinHash 関数を使用して、テキストから互換性のあるバイナリベクトルを自動的に生成します。MinHash 関数のエンドツーエンドのワークフローと構成オプションについては、MinHash 関数 を参照してください。

MinHash 署名の生成方法を選択する​

ワークロードに応じて、次の方法から選択できます。

  • シンプルさを重視する場合は、Python の datasketch を使用します（プロトタイピングに推奨）

  • 大規模データセットには、分散ツール（Spark、Ray など）を使用します

  • パフォーマンスチューニングが重要な場合は、カスタムロジック（NumPy、C++ など）を実装します

このガイドでは、シンプルさと Zilliz Cloud の入力形式との互換性のため、datasketch を使用します。

必要なライブラリをインストールする​

この例に必要なパッケージをインストールします。

bash
pip install pymilvus datasketch numpy

MinHash 署名を生成する​

256 次元の MinHash 署名を生成します。各ハッシュ値は 64 ビット整数として表現されます。これは MINHASH_LSH が想定するベクトル形式に一致します。

python
MINHASH_DIM = 256
HASH_BIT_WIDTH = 64

def generate_minhash_signature(text, num_perm=MINHASH_DIM) -> bytes:
    m = MinHash(num_perm=num_perm)
    for token in text.lower().split():
        m.update(token.encode("utf8"))
    return m.hashvalues.astype('>u8').tobytes()  # Returns 2048 bytes

各署名は 256 × 64 ビット = 2048 バイトです。このバイト文字列は BINARY_VECTOR フィールドに直接挿入できます。Zilliz Cloud で使用されるバイナリベクトルの詳細については、バイナリベクトル を参照してください。

デフォルトでは、Zilliz Cloud は MinHash 署名と LSH インデックスのみを使用して近似の近傍を検索します。これは高速ですが、誤検出が発生したり、近い一致を見逃したりする可能性があります。

正確な Jaccard 類似度が必要な場合、Zilliz Cloud は元のトークンセットを使用する絞り込み検索をサポートしています。有効にするには、次のようにします。

トークンセットの抽出例：

python
def extract_token_set(text: str) -> str:
    tokens = set(text.lower().split())
    return " ".join(tokens)

MinHash LSH を使用する​

MinHash ベクトルと元のトークンセットを準備できたら、Zilliz Cloud で MINHASH_LSH を使用して保存、インデックス作成、検索を実行できます。

クラスターに接続する​

python
from pymilvus import MilvusClient, DataType
from datasketch import MinHash
import numpy as np

client = MilvusClient(uri="YOUR_CLUSTER_ENDPOINT")  # Update if your URI is different

コレクションスキーマを定義する​

次の項目を持つスキーマを定義します。

  • プライマリキー

  • MinHash 署名用の BINARY_VECTOR フィールド

  • 元のトークンセット用の VARCHAR フィールド（絞り込み検索を有効にする場合）

  • オプションで、元のテキスト用の document フィールド

python
VECTOR_DIM = MINHASH_DIM * HASH_BIT_WIDTH  # 256 × 64 = 16384 bits

schema = client.create_schema(auto_id=False, enable_dynamic_field=False)
schema.add_field("doc_id", DataType.INT64, is_primary=True)
schema.add_field("minhash_signature", DataType.BINARY_VECTOR, dim=VECTOR_DIM)
schema.add_field("token_set", DataType.VARCHAR, max_length=1000)  # required for refinement
schema.add_field("document", DataType.VARCHAR, max_length=1000)

インデックスパラメーターを構築してコレクションを作成する​

Jaccard の絞り込みを有効にして MINHASH_LSH インデックスを構築します。

python
index_params = client.prepare_index_params()
index_params.add_index(
    field_name="minhash_signature",
    index_type="MINHASH_LSH",
    metric_type="MHJACCARD",
    params={
        "mh_element_bit_width": HASH_BIT_WIDTH,  # Must match signature bit width
        "mh_lsh_band": 16,                       # Band count (256/16 = 16 hashes per band)
        "with_raw_data": True                    # Required for Jaccard refinement
    }
)

client.create_collection("minhash_demo", schema=schema, index_params=index_params)

インデックス構築パラメーターの詳細については、インデックス構築パラメーター を参照してください。

データを挿入する​

各ドキュメントについて、次の項目を準備します。

  • バイナリの MinHash 署名

  • シリアル化されたトークンセット文字列

  • （オプション）元のテキスト

python
documents = [
    "machine learning algorithms process data automatically",
    "deep learning uses neural networks to model patterns"
]

insert_data = []
for i, doc in enumerate(documents):
    sig = generate_minhash_signature(doc)
    token_str = extract_token_set(doc)
    insert_data.append({
        "doc_id": i,
        "minhash_signature": sig,
        "token_set": token_str,
        "document": doc
    })

client.insert("minhash_demo", insert_data)
client.flush("minhash_demo")

Zilliz Cloud は、MinHash LSH を使用した 2 つの類似検索モードをサポートしています。

  • 近似検索 — MinHash 署名と LSH のみを使用し、高速ですが確率的な結果を返します。

  • 絞り込み検索 — 元のトークンセットを使用して Jaccard 類似度を再計算し、精度を向上させます。

5.1 クエリを準備する​

類似検索を実行するには、クエリドキュメントの MinHash 署名を生成します。この署名は、データ挿入時に使用したものと同じ次元とエンコード形式に一致している必要があります。

python
query_text = "deep learning uses neural networks to model patterns"
query_sig = generate_minhash_signature(query_text)

5.2 近似検索（LSH のみ）​

これは高速でスケーラブルですが、近い一致を見逃したり、誤検出を含んだりする可能性があります。

python
search_params={
    "metric_type": "MHJACCARD", 
    "params": {}
}

approx_results = client.search(
    collection_name="minhash_demo",
    data=[query_sig],
    anns_field="minhash_signature",
    search_params=search_params,
    limit=3,
    output_fields=["doc_id", "document"],
    consistency_level="Strong"
)

for i, hit in enumerate(approx_results[0]):
    sim = hit['distance']
    print(f"{i+1}. Similarity: {sim:.3f} | {hit['entity']['document']}")

Zilliz Cloud に保存された元のトークンセットを使用して、正確な Jaccard 比較を有効にします。やや低速になりますが、品質が重要なタスクに推奨されます。

python
search_params = {
    "metric_type": "MHJACCARD",
    "params": {
        "mh_search_with_jaccard": True,  # Enable real Jaccard computation
        "refine_k": 5                    # Refine top 5 candidates
    }
}

refined_results = client.search(
    collection_name="minhash_demo",
    data=[query_sig],
    anns_field="minhash_signature",
    search_params=search_params,
    limit=3,
    output_fields=["doc_id", "document"],
    consistency_level="Strong"
)

for i, hit in enumerate(refined_results[0]):
    sim = hit['distance']
    print(f"{i+1}. Similarity: {sim:.3f} | {hit['entity']['document']}")

インデックスパラメーター​

このセクションでは、インデックスの構築とインデックスに対する検索に使用するパラメーターの概要を説明します。

インデックス構築パラメーター​

次の表は、インデックスを構築するときに params で設定できるパラメーターを示しています。

パラメーター説明値の範囲チューニングの推奨事項
mh_element_bit_widthMinHash 署名内の各ハッシュ値のビット幅です。8 で割り切れる必要があります。8, 16, 32, 64パフォーマンスと精度のバランスを取るには 32 を使用します。大規模なデータセットでより高い精度を得るには 64 を使用します。許容できる精度低下と引き換えにメモリを節約するには 16 を使用します。
mh_lsh_bandLSH のために MinHash 署名を分割するバンドの数です。再現率とパフォーマンスのトレードオフを制御します。[1, signature_length]128 次元の署名の場合は、32 バンド (4 values/band). から開始します。再現率を高めるには 64 に増やし、パフォーマンスを向上させるには 16 に減らします。署名長を均等に分割できる必要があります。
mh_lsh_code_in_memLSH ハッシュコードを匿名メモリに格納する（true）か、メモリマッピングを使用する（false）かを指定します。true, false大規模なデータセット（100 万セット超）では、メモリ使用量を削減するために false を使用します。最大の検索速度を必要とする小規模なデータセットでは true を使用します。
with_raw_data絞り込みのために、元の MinHash 署名を LSH コードと一緒に保存するかどうかを指定します。true, false高い精度が必要で、ストレージコストを許容できる場合は true を使用します。わずかな精度低下と引き換えにストレージのオーバーヘッドを最小限に抑えるには false を使用します。
mh_lsh_bloom_false_positive_probLSH バケットの最適化に使用されるブルームフィルターの偽陽性確率です。[0.001, 0.1]メモリ使用量と精度のバランスを取るには 0.01 を使用します。値を小さくする（0.001）と偽陽性が減少しますが、メモリが増加します。値を大きくする（0.05）とメモリを節約できますが、精度が低下する可能性があります。

インデックス固有の検索パラメーター​

次の表は、インデックスを検索するときに search_params.params で設定できるパラメーターを示しています。

パラメーター説明値の範囲チューニングの推奨事項
mh_search_with_jaccard絞り込みのために、候補結果に対して正確な Jaccard 類似度の計算を実行するかどうかを指定します。true, false高い精度が求められるアプリケーション（重複排除など）では true を使用します。わずかな精度低下を許容できる場合は、より高速な近似検索のために false を使用します。
refine_kJaccard の絞り込み前に取得する候補の数です。mh_search_with_jaccard が true の場合にのみ有効です。[top_k, top_k * 10]再現率とパフォーマンスのバランスを取るには、目的の top_k の 2～5 倍に設定します。値を大きくすると再現率は向上しますが、計算コストが増加します。
mh_lsh_batch_search複数の同時クエリに対してバッチ最適化を有効にするかどうかを指定します。true, false複数のクエリを同時に検索してスループットを向上させる場合は true を使用します。単一クエリのシナリオでは、メモリのオーバーヘッドを削減するために false を使用します。
このページは役に立ちましたか？
Ctrl I