Jaccard類似度とMinHashを用いた類似重複検出
(blog.nelhage.com)類似文書を見つける: Jaccard類似度とMinHash
- 問題定義
- 大規模な文書コレクションにおいて、類似した文書を識別する方法について論じる
- たとえば、Webクローリングによって同じページを複数回取得した場合、メタデータのわずかな違いや小さな編集後の複数バージョンが存在しうる
- この記事では、Jaccard類似度とMinHashを使った近似的な重複排除手法を探る
類似度
- 類似度の定義
- 2つの文書間の類似度を定義し、類似度の値が特定のしきい値以上であるペアを見つける方法
- 類似度関数 S:U×U→[0,1] を定義し、S(A,B)≥S_crit の場合に2つの文書を近似重複と見なす
Jaccard類似度
- Jaccard類似度
- 2つの有限集合の類似度を、それらの共通部分と和集合の比率で表す関数
- J(A,B)=∣A∩B∣/∣A∪B∣
- 2つの集合が類似しているほど、ほとんど同じ要素を持つ
Jaccard類似度の拡張
- 拡張方法
- 文書を特徴集合に変換し、高いJaccard類似度を持つ集合を検索する
- 小規模なコーパスでは直接適用できるが、大規模なコーパスでは非効率的である
Jaccard類似度の近似
- MinHash署名
- Jaccard類似度を近似するためにサンプリングを使用する
- 各文書に対して固定サイズの署名を事前計算し、効率的に類似度を推定する
より多くのハッシュ関数を使う
- 複数ハッシュ関数
- 複数のハッシュ関数を使って各文書をk要素ベクトルに要約する
- 2つの署名間で一致するハッシュ数を数え、Jaccard類似度を近似する
すべての文書を比較
- 文書のグループ化
- 文書をグループ化し、類似した文書だけを比較する
- MinHash値をグループ化キーとして使い、効率的に近似重複を見つける
より柔軟な重複検出
- 複数キーの使用
- 複数のキーを使って文書を複数のバケットに配置し、各バケット内で比較する
- より低い類似度の値でも重複を検出できる
結論
- 結論
- MinHashのようなアルゴリズムによって、効率的に類似文書を見つけられる
- この記事がより多くのエンジニアにこうしたアルゴリズムを紹介し、理解の助けになることを願う
付録: 文書を集合として表現する
-
n-gram
- 文書をn-gramで表現して比較する
- nの値によって比較の精度が変わる
-
単語分割
- 文書を単語またはトークンに分割し、特徴として使用する
- より高度なトークナイザーを使うこともできる
GN⁺の意見
-
類似文書検出の重要性
- 大規模データセットで重複を除去することは、データ品質を高め、保存容量を節約するうえで重要である
- 特にWebクローリングやデータ収集の過程では不可欠である
-
MinHashの利点
- MinHashは効率的かつスケーラブルな方法で類似文書を検出できる
- 従来のハッシュベースの重複排除手法よりも柔軟である
-
その他の類似技術
- HyperLogLogのような他のスケッチアルゴリズムも、同様の問題を解くために使える
- 2つのアルゴリズムを組み合わせることで、より強力なソリューションを作れる
-
実運用での考慮事項
- ハッシュ関数選択の重要性: ハッシュ関数の選択は結果の精度に大きく影響する
- 性能と精度のバランス: より多くのハッシュ関数を使うほど精度は高まるが、性能コストも増加する
-
推奨技術
- SparkのMinHashLSH実装のようなツールを使えば容易に適用できる
- 大規模データセットにおける効率的な重複排除のために、こうした技術を積極的に活用することを勧める
1件のコメント
Hacker Newsの意見
Jaccard類似度とF1スコアはファジィ集合でも同様に使用できる
Pythonでフランス政府データベースの重複排除を実装した経験がある
Googleの初期に重複排除のために開発された技術である
Minhashシステムを実装した経験がある
Minhashとその派生手法は理解しにくいため、可視化ツールを開発中である
コード例を通じて技術を理解するほうが容易である
NVIDIAチームがGPUアクセラレーションによるファジィ重複排除アルゴリズムを公開した
ハッシュ化、または小規模なニューラルネットワークとベクトル検索エンジンを組み合わせた重複排除戦略が一般的である
著者に誤植を指摘した
Postgresで類似したニュース項目を1つにまとめる問題に取り組んでいる