1

ローカリティ センシティブ ハッシュ (LSH) の重要な考え方は、近隣ポイントvは同じバケットにマッピングされる可能性が高く、互いに離れたポイントは異なるバケットにマッピングされる可能性が高いということです。ランダム射影を使用する場合、データベースにそれぞれ高次元 d の N 個のサンプルが含まれている場合、理論では、ランダムに生成された k 個のハッシュ関数を作成する必要がありますg(**v**) = (h_1(v),h_2(v),...,h_k(v))。したがって、任意のベクトル ポイントvについて、そのポイントは g 関数を使用して k 次元ベクトルにマッピングされます。この場合、ハッシュ コードは長さ / 次元 k を短縮したベクトルであり、バケットと見なされます。さて、衝突の確率を高めるために、理論によると、L 個のそのような g 関数g_1, g_2,...,g_Lをランダムに持つ必要があります。これは私が理解していない部分です。

質問 : 複数のハッシュ テーブルを作成する方法を教えてください。ハッシュ テーブルにはいくつのバケットが含まれていますか?

Sparse Projections for High-Dimensional Binary CodesYan Xiaらの論文に記載されているコードに従っています。al コードへのリンク

ファイル内Coding.m 

dim = size(X_train, 2);
R = randn(dim, bit);

% coding
B_query = (X_query*R >= 0);
B_base = (X_base*R >=0);

X_queryはそれぞれ次元 d のクエリ データのセットで、1000 個のクエリ サンプルがあります。Rはランダムな射影で、bit はターゲットの縮小次元です。との出力は、B_query0 /1 の値を取る長さの文字列です。この方法で複数のハッシュ テーブルが作成されますか。つまり、ハッシュ テーブルの数ですか。どうしようか迷っています。詳しい解説とても参考になります。B_baseNkN

4

1 に答える 1

1

複数のハッシュテーブルを作成するには?

LSH は、連結によって (増幅された) ハッシュ関数を使用してハッシュ テーブルを作成します。

g(p) = [h 1 (p), h 2 (p), ··· , h k (p)], h i ∈<sub>RH

g()はハッシュ関数であり、1 つのハッシュテーブルに対応します。そのため、そのハッシュテーブルを介してデータをマッピングするg()と、近いものは同じバケットに分類され、そうでないものは異なるバケットに分類される可能性があります。

そのL回数を行うため、Lハッシュテーブルを作成します。すべてが他のハッシュ関数g()とは異なる可能性が最も高い/異なるはずであることに注意してください。g()

注: k が大きい ⇒ P 1と P 2の間のギャップが大きい。小さな P 1 ⇒ より大きな L で、隣人を見つけます。実際の選択は L = 5 (または 6) です。P 1と P 2は、次の図で定義されています。

ここに画像の説明を入力

ハッシュ テーブルにはいくつのバケットが含まれていますか?

私が知っていたらいいのに！それは難しい質問です。データセット内のポイントの数はsqrt(N)どうですか。Nこれを確認してください: LSH のバケット数

Yan Xiaのコード

よくわかりませんが、おっしゃる通り、1000 個のクエリを実行したいので、表示されるクエリ データは 1000 個あると思います。

kハッシュテーブルのどのバケットにマッピングされるかを確認するには、クエリをハッシュする必要があるため、文字列の長さです。そのバケット内のポイントは、潜在的な(おおよその) Nearest Neighborsです。

于 2016-05-26T17:01:32.997 に答える