MinHash
MinHash は Broder が提案した集合類似度推定法である。複数の独立なハッシュ関数の最小値を用いて Jaccard 類似度を推定する。
目的
大量の集合の中で二つの集合の Jaccard 類似度を素早く推定し、近重複検索や重複排除を支える。
メカニズム
集合に k 個の独立なハッシュ関数を適用し、それぞれの最小値を取って k 次元の署名を作る。署名の対応する位置が等しい確率は Jaccard 類似度に等しいため、一致する位置の割合で類似度を推定できる。
ユースケース
- 検索エンジンの重複検出
- 類似アイテムのレコメンド
- 文書クラスタリング