0

私は現在、MinHashing技術を使用したドキュメント クラスタリングに取り組んでいます。ただし、MinHash は概算でJaccard similarityあり、要件に合わないため、望ましい結果が得られません。

これは私のシナリオです:

私は膨大な数の本を持っており、単一のページがクエリとして与えられた場合、このページが取得された対応する本を見つける必要があります。制限は、本全体の機能があり、本のページごとの機能を取得することが不可能であることです。この場合、本が大きすぎると、Jaccard 類似度の結果が悪くなります。私が本当に欲しいのは、クエリ ページと書籍の間の距離です (その逆ではありません)。あれは：

2 つのセット A、B が与えられた場合: A から B までの距離が必要です。

dis(A->B) =  (A & B)/A

セットAからセットBまでの距離を与える同様の距離メトリックはありますか?さらに、MinHashingこの種の類似メトリックでアルゴリズムを使用することはまだ可能ですか?

4

1 に答える 1

1

MinHash アルゴリズムと同様のアプローチを使用して、提案された距離関数を推定できます。

一部のハッシュ関数 について、 overとh(x)の最小値を計算します。これらの値を および で表します。MinHash アルゴリズムは、確率が. である確率が観察されるかもしれません。次に、これら 2 つの確率の比率として計算できます。hABh_min(A)h_min(B)h_min(A) = h_min(B)(A & B) / (A | B)h_min(A) <= h_min(B)A / (A | B)(A & B) / A

通常の MinHash アルゴリズムと同様に、必要な分散が得られるまでサンプリングを繰り返すことで、これらの確率を概算できます。

于 2015-08-17T08:14:27.447 に答える