Java-LSHを使用したJavaでの局所性鋭敏型ハッシュ

投稿日: 2019-10-18 2022-10-31
タグ: Algorithms, Java

1. 概要

Locality-Sensitive Hashing（LSH）アルゴリズムは、入力アイテムをハッシュして、類似したアイテムが同じバケットにマップされる可能性が高くなるようにします。

このクイック記事では、 java-lsh ライブラリを使用して、このアルゴリズムの簡単な使用例を示します。

2. Mavenの依存関係

開始するには、Maven依存関係を java-lshライブラリに追加する必要があります。

<dependency>
    <groupId>info.debatty</groupId>
    <artifactId>java-lsh</artifactId>
    <version>0.10</version>
</dependency>

3. 局所性鋭敏型ハッシュのユースケース

LSHには多くの可能なアプリケーションがありますが、1つの特定の例を検討します。

仮定するドキュメントのデータベースがあり、類似したドキュメントを識別できる検索エンジンを実装したいと考えています。

このソリューションの一部としてLSHを使用できます。

すべてのドキュメントは、数値またはブール値のベクトルに変換できます。たとえば、 word2vect アルゴリズムを使用して、単語やドキュメントを数値のベクトルに変換できます。
各ドキュメントを表すベクトルを取得したら、LSHアルゴリズムを使用して各ベクトルのハッシュを計算できます。また、LSHの特性により、類似のベクトルとして表示されるドキュメントは、類似または同じハッシュを持ちます。
その結果、特定のドキュメントのベクトルが与えられると、同様のハッシュを持つ N 個のベクトルを見つけて、対応するドキュメントをエンドユーザーに返すことができます。

4. 例

java-lsh ライブラリを使用して、入力ベクトルのハッシュを計算します。これはこの記事の範囲を超えた大きなトピックであるため、変換自体については説明しません。

ただし、LSHアルゴリズムの入力として使用できる形式で提示された、3つのドキュメントのセットから変換された3つの入力ベクトルがあるとします。

boolean[] vector1 = new boolean[] {true, true, true, true, true};
boolean[] vector2 = new boolean[] {false, false, false, true, false};
boolean[] vector3 = new boolean[] {false, false, true, true, false};

実稼働アプリケーションでは、LSH アルゴリズムを活用するには、入力ベクトルの数を大幅に増やす必要がありますが、このデモンストレーションでは、3つのベクトルのみに固執します。

最初のベクトルは2番目と3番目のベクトルとは大きく異なるのに対し、2番目と3番目のベクトルは互いに非常に似ていることに注意することが重要です。

LSHMinHashクラスのインスタンスを作成しましょう。入力ベクトルのサイズを渡す必要があります。すべての入力ベクトルのサイズは同じである必要があります。また、必要なハッシュバケットの数と、LSHが実行する計算（反復）の段階の数を指定する必要があります。

int sizeOfVectors = 5;
int numberOfBuckets = 10;
int stages = 4;

LSHMinHash lsh = new LSHMinHash(stages, numberOfBuckets, sizeOfVectors);

アルゴリズムによってハッシュされるすべてのベクトルは、10個のバケット間でハッシュされる必要があることを指定します。また、ハッシュを計算するためにLSHを4回繰り返す必要があります。

各ベクトルのハッシュを計算するには、ベクトルを hash（）メソッドに渡します。

int[] firstHash = lsh.hash(vector1);
int[] secondHash = lsh.hash(vector2);
int[] thirdHash = lsh.hash(vector3);

System.out.println(Arrays.toString(firstHash));
System.out.println(Arrays.toString(secondHash));
System.out.println(Arrays.toString(thirdHash));

そのコードを実行すると、次のような出力になります。

[0, 0, 1, 0]
[9, 3, 9, 8]
[1, 7, 8, 8]

各出力配列を見ると、対応する入力ベクトルの4回の反復のそれぞれで計算されたハッシュ値を確認できます。最初の行は、最初のベクトルのハッシュ結果、2番目の行は2番目のベクトル、3番目の行は3番目のベクトルのハッシュ結果を示しています。

4回の反復の後、LSHは期待どおりの結果を生成しました。LSHは、互いに類似している2番目と3番目のベクトルに対して同じハッシュ値（8）を計算し、最初のベクトルに対して異なるハッシュ値（0）を計算しました。 2番目と3番目のベクトルとは異なります。

LSHは確率に基づくアルゴリズムであるため、2つの類似したベクトルが同じハッシュバケットに到達するかどうかを確認することはできません。それでも、入力ベクトルの数が十分に多い場合、アルゴリズムは、同じバケットに同様のベクトルを割り当てる可能性が高い結果を生成します。

大量のデータセットを扱う場合、LSHは便利なアルゴリズムになります。

5. 結論

この簡単な記事では、局所性鋭敏型ハッシュアルゴリズムのアプリケーションを調べ、java-lshライブラリを使用してそれを使用する方法を示しました。

これらすべての例とコードスニペットの実装は、 GitHubプロジェクトにあります。これはMavenプロジェクトであるため、そのままインポートして実行するのは簡単です。

getdocs

13036