問題タブ [minhash]

kd ツリーについて読みましたが、空間の次元が高い場合は非効率的です。値のデータベースがあり、クエリから特定のハミング距離内にある値を見つけたいと考えています。たとえば、データベースは 32 ビットの数値のリストであり、クエリ値との差が 3 ビット未満のすべての数値を見つけたいとします。

MultiVariate Partition trees についてどこかで聞いたことがありますが、適切なリファレンスが見つかりませんでした。min-Hash の方が適切な近似値を提供することは知っていますが、正確な答えが欲しいです。

MinHash アルゴリズムを使用して、画像間で類似の画像を見つけています。MinHashアルゴリズムHow can I recognize slightly modified images?を指摘したこの投稿に出くわしました。

このブログ投稿の C# 実装を使用していましたSet Similarity and Min Hash。

しかし、実装を使用しようとしているときに、2 つの問題に遭遇しました。

• 値をどの値に設定すればよいuniverseですか?
• イメージ バイト配列を に渡す場合HashSet、個別のバイト値のみが含まれます。したがって、1 ~ 256 の値を比較します。

これuniverseは MinHash で何ですか?
また、C# MinHash の実装を改善するにはどうすればよいですか?

HashSet<byte>最大 256 の値が含まれているため、類似度の値は常に 1 になります。

の C# MinHash 実装を使用するソースは次のSet Similarity and Min Hashとおりです。

ruby ハッシュ関数を使用するためのシード値を設定する方法はありますか (つまり、1.9 の murmur ハッシュ、JRuby を知りませんか?)、スクリプトを実行するたびに同じハッシュコードを取得できるようにする方法はありますか?プロセスまたは異なるノード上)

となることによって

puts 「これはテストです」.hash

これは、今日、明日、3 週間後など、いつ実行しても同じです。

MinHashを並行して実装できるように、これを行いたい

murmur_hash ジェムで、つぶやきハッシュがシードを受け入れることがわかるので、同じシードを選択するたびに、シードを設定してハッシュコードを決定論的に取得できると思います

ドキュメントを含む大規模なpostgresqlデータベースがあります。テーブル内の行として表されるすべてのドキュメント。新しいドキュメントがデータベースに追加されたら、重複をチェックする必要があります。selectしかし、完全に一致するものを見つけるためだけに使用することはできません。2つのドキュメントはわずかに異なる場合がありますが、それでも重複と見なすことができます。たとえば、一部のマイナーフィールドが異なり、他のすべてのフィールドが等しい場合などです。

私はこの問題を研究し、この問題を解決する方法を見つけます。すべてのドキュメントの署名を計算MinHashし、転置インデックスを作成して、データベースから同様のドキュメントをクエリすることができます。MinHashしかし、リレーショナルデータベースにマッピングする方法がわかりません。

私が理解しているように、MinHash署名はN個のハッシュのリストです。ここでNはいくつかの属性です。類似性は次のように計算されます。

すでに2つの署名がある場合、これは簡単です。問題は、データベース内で類似性がある程度の値以下のすべてのドキュメント（対応する署名を含む）を見つけることです。

たとえば、次のように複数の列を持つテーブルを作成できます。

各minhashX列は、ドキュメントの属性の1つのminhashに対応しdocid、ドキュメントの識別子です。次の方法で同様のレコードをクエリできます。

ここで、minhash2searchXは新しいドキュメントのミンハッシュであり、THRESHOLDは最小限の類似性です。ただし、このアプローチではフルスキャンが必要です。このアルゴリズムを高速化する方法はありますか？

min-hashを使用してLSH（局所性鋭敏型ハッシュ）を実装する多くのチュートリアル、ドキュメント、およびコードを読みました。

LSHは、ランダムなサブセットをハッシュし、それらを集計することにより、2つのセットのJaccard係数を見つけようとします。code.google.comで実装を見てきましたが、その方法も理解できませんでした。私は紙のGoogleニュースのパーソナライズ：スケーラブルなオンライン協調フィルタリングを理解していますが、そこにある実装のいずれも理解できていません。

MinHashでLSHを実装する方法を簡単な言葉で説明してもらえますか？

仕事に活用できる minhash オープン ソース実装を探しています。

必要な機能は非常に単純です。セットを入力として指定すると、実装はそのミンハッシュを返す必要があります。

python または C の実装が優先されます。念のため、それをハックして動作させる必要がある場合に備えてです。

どんなポインタでも大いに役立ちます。

よろしく。

2 つのセット間の類似性を推定する MinHash 手法について読んでいます。セット A と B が与えられた場合、h はハッシュ関数であり、hmin(S) はセット S の最小ハッシュです。つまり、hmin(S)=min(h(s(s) )) S の s に対して、次の方程式があります。

p(hmin(A)=hmin(B))=|A∩B| / |A∪B|

これは、A の最小ハッシュが B の最小ハッシュと等しい確率が、A と B の Jaccard 類似度であることを意味します。

私は上記の式を証明し、独自の証明を考え出そうとしています: a∈A と b∈B に対して、h(a)=hmin(A) と h(b)=hmin(B) となります。したがって、hmin(A)=hmin(B) の場合、h(a)=h(b) となります。ハッシュ関数 h がキーを個別のハッシュ値にハッシュできると仮定すると、a=b の場合にのみ h(a)=h(b) となり、その確率は |A∩B| になります。/ |A∪B|。ただし、ハッシュ関数は異なるキーに対して同じ値を返す可能性があるため、私の証明は完全ではありません。そこで、ハッシュ関数に関係なく適用できる証明を見つけるために、あなたの助けを求めています。

私は使っている ：

hadoop-1.2.1 および mahout-distribution-0.8

次のコマンドで HASHMIN メソッドを実行しようとすると:

次のエラーが表示されます。

どんなアイデアでも感謝します