Information Retrieval and Web Search まとめ(23): 重複検知

前回は Web クローラの要件やそのアーキテクチャについて解説した。今回は、重複した文書の検知について扱う。

重複ページの検知

重複 (duplication): 完全一致はフィンガープリント (fingerprint) によって検知できる
準重複 (near-duplication): 近似マッチ (approximate match)
- 構文的な類似度を編集距離によって計算する
- その類似度の閾値で準重複コンテンツを検知する
- これは推移的にはならないが、推移的として扱うこともある
  - A と B、B と C がそれぞれ準重複だったとして、A と C は準重複とは限らない

特徴量
- 文書のセグメント
  - 自然な、もしくは人工的な場所で分割
- shingles
  - 単語 n-gram　などを使う
類似度の指標
- それぞれの文書の shingles に対して定義される
- ジャッカード係数 (Jaccard coefficient)
  - 共通集合の要素数 / 和集合の要素数
文書 $d_{j}$ のshingleを $S (d_{j})$ で表すとすると、文書 $d_{1}$ と $d_{2}$ のジャッカード係数は

 $J (S (d_{1}), S (d_{2})) = \frac{| S (d_{1}) \cap S (d_{2}) |}{| S (d_{1}) \cup S (d_{2}) |}$

各文書に対してスケッチベクトル (sketch vector) を作成する
- スケッチベクトルの次元数 m は ~200 次元
- スケッチベクトルの要素が t 以上（80% 以上など）かぶっている文書は準重複 (near duplicate) であるとみなせる
準備
- 文書の shingles をのいずれかの値に写像する、以下のような集合関数を用意する
  - $H (d_{j})$ は、文書 $d_{j}$ の shingles $S (d_{j})$ の各要素のハッシュ値からなる集合
  - $m = 64$ のとき、 $H (d_{j})$ の要素は 64 ビット非負整数のいずれかの値をとる
- のランダムな置換 (permutation) を用意する
  - $1 . . 2^{m}$ を $1 . . 2^{m}$ のいずれかの値にランダムに入れ替える写像
  - 置換は全単射なので異なる値が同じ値に写像されることはない
- の各要素をによって置換したものをとする
  - $H (d_{j})$ の各要素 $h \in H (d_{j})$ に対して、対応する値 $π (h) \in Π (d_{j})$ が存在する
文書 $d_{j}$ の $π$ によるスケッチ $x_{j}^{π}$ は $min (Π (d_{j}))$ （ $Π (d_{j})$ のうち最小の整数）で計算される

このスケッチの計算を 200 個のランダム置換に対して行う
- 200 次元のスケッチベクトルを計算する場合
このようにして得られた 200 個のスケッチ $x_{j}^{π_{1}}, x_{j}^{π_{2}}, . . ., x_{j}^{π_{200}}$ を並べたものを、文書 j のスケッチベクトル $ϕ_{j}$ とする
文書 i と文書 j のペアに対するジャッカード係数 $J (S (d_{i}), S (d_{j}))$ を $| ϕ_{i} \cap ϕ_{j} | / 200$ で推定する

 $F_{p} = {π_{a, b} : 1 \leq a \leq p - 1, 0 \leq b \leq p - 1} where π_{a, b} (x) = a x + b mod p$

shingling は乱択アルゴリズム (randomized algorithm) である
- なんの確率モデルも仮定していない
- ある確率で正しい答えを返す
文書のペアに対して準重複検知を行う方法を示した