問題タブ [locality-sensitive-hash]

ローカリティ センシティブ ハッシュは、欠点のない KNN にとって優れた手法のように思えます。しかし、誰かが実際のアプリケーションのために業界で使用している場合、局所性に敏感なハッシュの欠点は何でしょうか? LSH はどのような状況で失敗するか、やや悪い動作をしますか? または、コーディング/チューニングに時間がかかりますか?

LSH ( https://github.com/soundcloud/cosine-lsh-join-spark ) を適用して、いくつかのベクトルのコサイン類似度を計算しようとしています。私の実際のデータには、2M 行 (ドキュメント) とそれらに属する 30K の機能があります。その上、その行列は非常にまばらです。サンプルを与えるために、私のデータが以下のようであるとしましょう：

関連するコードでは、フィーチャは次のように密なベクトルに配置されます。

私がやりたいのは、密行列を使用する代わりに疎行列を使用することです。「Vectors.dense(features)」を調整するにはどうすればよいですか?

私は、既知の固定サイズ (64 ビットまたは 128 ビットなど) の任意の大きな符号なし整数にインデックスを付けるアルゴリズムを使用しています。utf-8 文字列にも適用できるようにしたいのですが、そのためには、任意の長さの特定の文字列を、そのような形式の符号なしバイトの固定サイズ配列にマップする信頼できる方法が必要です。少なくとも文字列のプレフィックスの辞書順が保持されるようにします。

これに対する素朴なアプローチは、単純にX文字列の最初の文字を取得し、各文字に完全な 4 バイトを与え、必要に応じて実際の値の前にゼロを追加することです。ただし、これにはX * 4バイトが必要です。よりスペース効率の良い方法でこれを行う方法があることを願っています。

- - 編集 - -

非常に重要なことは、衝突が許容されることです。

上記の素朴なアプローチを使用して、文字列を指定します。

3に設定Xすると、「Alabama」、「Alaska」、および「Alakazam」が衝突します。マッピングから生成される一意の 12 バイト値は 3 つだけです (「Ala」の 1 文字あたり 4 バイトの表現)。 、「Ark」および「Cor」)。ただし、これら 3 つの値が辞書式順序を維持することが非常に重要です。

4 バイトを使用する必要があるのは、これが 1 つの文字が utf-8 で占有できる最大のサイズである (と私は信じている) ためです。マッピングが固定サイズのバイト配列を与えることを保証するために (少なくともこのスキームでは)、通常は 1 バイトしか占有しない ASCII 文字でさえ、最大 4 バイトを占有する必要があります。

'A' => 01100001、ゼロでパディング: 0000000000000000000000001100001

'l' => 01101100、ゼロでパディング: 0000000000000000000000001101100

'a' => 01100001、ゼロでパディング: 0000000000000000000000001100001

したがって、= 4 の例では、X「Ala」で始まる文字列は次のようにマップされます。

96 ビットの unsigned int として表示すると、この例の他の接頭辞 (「Ark」と「Cor」) のマッピングの値よりも小さい値を持つため、マッピングが辞書編集順序を保持するという要件を満たします。 .

このスキームは機能しますが、文字列のサイズ要件が 4 倍にも膨れ上がります。希望は、より少ないX * 4バイト数で utf-8 プレフィックス インデックス作成を達成するマッピング スキームを見つけることです。

Locality Sensitive Algorithm を使用して、質問の類似性検出を実装しようとしています。lshash python パッケージを使用しています。

私たちの目的は、同様に「質問の提案がStackvoerflowでどのように機能するか」を達成することです

以下は、サンプル データ テキスト ファイルです。

以下はpythonコードです

しかし、この実装は悪い結果をもたらしています。コンテキストに応じて、どのタイプのローカリティ センシティブ ハッシュ アルゴリズムを使用したかを教えてもらえますか? パラメータと混同しています：INPUT_DIMENSION。

LSH を使用して同様の製品を構築しようとしていますが、次のクエリがあります。

私のデータには次のスキーマがあります

個々の機能に対して個別に LSH を実行し、それらを何らかの方法で組み合わせる必要がありますか?

また

すべての機能で LSH をまとめて構築する必要があります (基本的には、title_iphone、title_nexus、price_1200.25、active_1 などの帯状疱疹を作成しながら機能名を添付します)。次に、bag-of-words アプローチを使用して、このバッグで LSH を実行しますか?

e コマースのような構造化データに対して LSH を実行する方法を理解できるドキュメントを教えてくれる人がいれば、それは素晴らしいことです。

PS LSH で spark と min-hash 関数を使用する予定です。詳細が必要な場合はお知らせください。

MatrixMは、実際のデータの Minhashing によって生成される署名マトリックスであり、列としてドキュメント、行として単語を持ちます。したがって、列はドキュメントを表します。

これで、すべてのストライプ (b数、r長さ) の列がハッシュ化され、列がバケツに収まるようになります。>= 1 ストライプの場合、2 つの列が同じバケットに分類される場合、それらは類似している可能性があります。

つまり、ハッシュテーブルを作成し、独立したハッシュ関数bを見つける必要があるということですか? bそれとも、1 つだけで十分で、すべてのストライプがその列を同じバケットのコレクションに送信します (ただし、これはストライプをキャンセルしません)?

この場合、ハッシュテーブルには辞書で十分でしょうか^* ?

* _{Python 辞書はハッシュ テーブルの例ですか?}

この質問に続いて、2 つの異なる辞書がまったく同じハッシュ関数を使用してdict_1いることがわかります。dict_2

辞書で使用されるハッシュ関数を変更する方法はありますか? _{マイナス回答もOK！}

LSH では、ドキュメントのスライスをバケットにハッシュします。同じバケットに分類されたこれらのドキュメントは潜在的に類似しているため、最近傍である可能性があります。

40.000 ドキュメントの場合、バケット数として適切な (ほぼ) 値はどれくらいですか?

私はnumber_of_buckets = 40.000/4今それを持っていますが、もっと減らすことができると感じています.

アイデアはありますか？

Relative: Locality Sensitive Hashing (ジャカード距離を使用) でベクトルをバケットにハッシュする方法は?