java - Hadoop マップ再開ジョブのキーに類似性アルゴリズムを使用する方法

Question

次の問題を実装する必要があります: タイプのデータを取得しています

public class Data{   
  private String key;
  private String valueData;
}

それぞれに 1 つの (ランダムな) valueData を使用して、すべての一意のキーを取得するマップ削減ジョブを作成する必要があります。Hadoop の場合は非常に単純に聞こえますが、そうです、これを実装する方法を知っています。

しかし、本当の問題は、「同様の」キーをすべて削減する必要があることです。出力は、 dataValueの 1 つと同様のキーの 1 つでなければなりません。

Hadoop でこれを実装する最良の方法 (および方法) は何ですか? また、類似度アルゴリズムを柔軟に変更できるようにしたいと考えています。

score 1 · Accepted Answer

この手法を見てくださいMinHashing。このタスクでは、MapReduce で広く使用されています。

類似性メトリックはにバインドされてJaccardいますが、他のアプローチがあるかどうかはわかりません。ただし、近くのキーを計算したら、別のメトリックを使用してキー間の類似性を測定できます。これは、ミンハッシングによって検索スペースが大幅に削減されたためです。

ウィキペディアで詳細を読むことができます: http://en.wikipedia.org/wiki/MinHash

Mahout にはMinHashクラスタリングアルゴリズムがあります。非常に理解しやすく、いくつかのハッシュアルゴリズムを備えています。

score 0 · Accepted Answer

f基本的に、次のような関数を考え出す必要があります。

f(A) = f(B) if and only if A and B are "similar"

これに厳密に準拠できるかどうかは、これらの値のドメインが正確に何であるか、および類似性メトリックが何であるかに完全に依存しますが、これが目標です。

例として、キーが実数の場合、私はを選択するかもしれませんf(x) = round(x)。xの値が非常に近いf(x)場合、同じになる可能性がありますが、異なる可能性があります（例：2.45と2.55）。しかし、多分あなたはこの「十分に良い」ことを許すことができます。

次に、reduceステップのキーをこの関数の出力にすることができます。

また、特定の類似性メトリクスと特定のクラスタリング手法には他にも多くの高度な手法があることを付け加えておきます。使用したいメトリクスのタイプについてもう少し詳しく説明していただければ、そのうちの1つを紹介できます。または、正確に「類似した」キーとは何か。

2 に答える 2