近似最近傍検索における局所性依存ハッシュの適用

局所性敏感ハッシュ (LSH) は、近似最近傍検索の方法であり、特に高次元空間のデータに適しています。テキストや画像データなどの多くの実際のアプリケーションでは、データ ポイントの次元が非常に高くなることがあります。高次元空間では、ユークリッド距離などの従来の距離測定方法はもはや効果的ではなく、従来の線形探索方法は非効率的です。したがって、この問題を解決するには、いくつかの効率的なアルゴリズムが必要です。 LSH の基本的な考え方は、ハッシュ関数を通じて類似のデータ ポイントを類似のハッシュ バケットにマッピングすることです。このようにして、データセット全体を走査するのではなく、類似のハッシュバケット内で検索するだけで済むため、検索効率が大幅に向上します。 LSH アルゴリズムの中核は、適切なハッシュ関数を設計することです。ハッシュ関数には 2 つの特性がある必要があります: 1 つ目は、同様のデータ ポイントは同様のハッシュ バケットにマッピングされる可能性が高い、つまり、局所的な機密性があること、2 つ目は、異なるデータ ポイント

局所性敏感ハッシュ (LSH) の基本的な考え方は、ハッシュ関数を通じて高次元空間のデータ ポイントを低次元空間にマッピングし、低次元空間で近似最近傍検索を実行することです。ランダム化技術を導入することにより、LSH は同様のデータ ポイントが同じバケットにマッピングされる確率を高め、それによって検索スペースを削減できます。 LSH の利点は、一定のクエリ精度を確保しながら検索スペースを大幅に削減し、クエリ効率を向上させることです。

LSH は、検索エンジンでの類似画像検索、音楽推奨システムでの類似曲の推奨、ソーシャル ネットワークでの類似ユーザーの推奨など、広く使用されています。以下では、簡単な例を通して LSH の原理と実装プロセスを紹介します。

データ セットがあり、各データ ポイントが 100 次元のベクトルであると仮定します。特定のベクトルに最も類似したデータ ポイントについてこのデータ セットをクエリするために、LSH (局所性敏感ハッシュ) を使用してクエリ効率を向上させたいと考えています。データ ポイントの次元が非常に高いため、従来の線形検索方法では非常に時間がかかります。 LSH は高次元空間のデータ ポイントを低次元空間にマッピングすることができ、同様のデータ ポイントを低次元空間で比較的近くに保持し、検索時間を短縮します。したがって、クエリに LSH を使用すると、検索が高速化され、効率が向上します。

まず、100 次元ベクトルを低次元空間にマッピングするハッシュ関数を定義する必要があります。一般的に使用されるハッシュ関数は、ユークリッド ハッシュとコサイン ハッシュの 2 つです。ユークリッド ハッシュは、いくつかの超平面をランダムに生成してデータ ポイントを異なるバケットにマッピングすることにより、ベクトルを実数領域にマッピングします。コサイン ハッシュはベクトルを高次元の超球にマッピングし、いくつかの超平面をランダムに生成することでデータ ポイントを異なるバケットにマッピングします。この例では、例としてユークリッド ハッシュを使用します。

ハッシュ関数は h(x)=\lfloor\frac{a^Tx b}{w}\rfloor として表現できます。ここで、a はランダム ベクトル、b は A です。ランダム定数、w はバケットの幅、\lfloor\rfloor は切り捨てを意味します。任意のベクトル x はバケットにマッピングされ、バケット番号は h(x) になります。

次に、ランダムなベクトル a とランダムな定数 b、およびバケットの幅 w を選択する必要があります。類似のデータ ポイントをできるだけ同じバケットにマッピングするには、類似のデータ ポイントが同じバケットにマッピングされる確率が比較的高く、異なるデータ ポイントが同じバケットにマッピングされるように、いくつかのパラメーターを選択する必要があります。 . 確率は比較的小さいです。このプロセスはパラメータを調整することで実現できます。

一般的に、複数のハッシュ関数を選択し、各ハッシュ関数を 1 回マップする必要があります。これらのハッシュ関数のマッピングにより複数のバケットが得られるので、これらのバケットを候補セットとみなし、この候補セット内で近似最近傍検索を実行できます。具体的には、クエリ ベクトルと候補セット内の各データ ポイントの間の距離を計算し、距離が最も小さいデータ ポイントを近似最近傍として選択できます。候補セットのサイズはデータ セット全体のサイズよりもはるかに小さいため、このプロセスは線形検索よりもはるかに効率的です。

LSH は近似手法であり、クエリ結果の正確性を保証できないことに注意してください。 LSH クエリの結果にはエラーが発生する可能性があり、エラーのサイズはハッシュ関数の選択とパラメーター設定に関係します。したがって、実際のアプリケーションでは、クエリの精度とクエリの効率のバランスを達成するために、特定のシナリオと要件に従って適切なハッシュ関数とパラメータを選択する必要があります。

以上が近似最近傍検索における局所性依存ハッシュの適用の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。