弊社のエンジニア組織の特徴のひとつに、手を上げる・声を上げると、『じゃ、やってよ。』というノリで返ってくるという事が挙げられるのですが、今回もその例に漏れなったわけですね・・・。シクシク・・・。
というわけで、何を書こうかなぁって話しなんですが・・・。私の場合アルゴリズム系の話しかできそうにないので、毎回ポツポツとマイナーで極一部の人にしかウケないテーマを紹介して行こうと思います。
で、初回の今回は SimilarityJoin 関連のアルゴリズムで "MPJoin" というやつを紹介したいと思います。
■ Similarity Join とは何ぞや？
まず最初に SimilarityJoin [1] の定義なんですが、ざっくりいうと 『 データ集合の中からある閾値以上の類似性を持ったデータ対を見つけるタスク 』 ということを意味しています。
ここでいう"類似性"とは、類似度（例：cosign距離、Jaccard係数）や非類似度（例 : edit 距離、Euclid 距離、Hamming 距離）といった複数のmetricのことを指しています。
この事からなんとなく想起されることではあるのですが、実際 SimilarityJoin には、各meticに合わせたアルゴリズムがいくつか存在しています。
さて、このようなタスクが現実の世界で使われるケースとしては、例えば類似画像検索、検索における同一内容Indexingの回避、機械学習の前処理（データクレンジング）、スパムフィルタリング、ソーシャルデータ解析などなど、データに纏わる多くの場面で地味に登場してきます。実際にAmebaでも、ブログのテキストマイニングの前処理や各種フィルタリングの一部に、今回紹介するアルゴリズムを使用しています。
このタスクは単純にやろうと思えば、n個のデータがあるとした場合にすべての組み合わせ 1/2 * n * ( n-1 ) を列挙して、各々の類似性を総当りで調べれば良いのですが、この計算オーダーは n^2 なので非常に重く、データ規模が大きくなればこの手法では現実的ではありません。
これを回避するための手法としては、(私の知る限りでは)大別して "近似手法" と "刈り込み法" の二つが存在しています。
( 訂正 2011/2/17 ： "動的計画法" と表記した部分を "刈り込み法" に変更しました。間違いでした。 )■ Similarity Join の種類
大別して２種類ある SmilarityJoin ですが、これらの手法各々に各類似性に着目した専用のアルゴリズムがいくつか存在しています。具体的な手法をまとめると大体以下のような感じになります。
各アルゴリズムに関するリファレンスは、エントリの最後に記載しておきますので、良かったら後で参照してみてください。
■ 近似手法 ―― LSH
さて、大別の一角を担う ” 近似手法 ” ですが、有名なのは LSH （Locality Sensitive Hashing） という手法です。これは類似性のあるデータ同士が高い確率で同じ値をとるハッシュ関数をデータに適用して、同一ハッシュを取ったデータは似ているという論法で類似ペアを抽出します。
ｎ個のデータを事前にハッシュ化して、各ハッシュ値毎に転置Indexでも作っておけば、n^2の総当り探索を防ぐことができるというわけです。
（ 厳密には LSH は上の表で示したように色々な種類があって、この説明は非類似度LSH[2, 3] の場合を超ざっくり話しただけです。ホントは類似度LSHの SimHash[4] とか MinHash[5] などが高速に類似データを検索できる理由は少し違うのですが・・・ ）
LSHで注意しておきたいのは、近似手法であるが故に、類似ペアの漏れが発生したり、場合によっては抽出したデータの再検証が必要であることです。このような特徴から利用シーンとしては、『 再現率はそこそこで良いが適合率は重視したデータ抽出 』 をするような場合には結構向いていて、例えば類似画像検索などではこの手法が非常によく使われます。
まぁこの当たりの話は、話し始めると終わりが見えないので、詳細はまたの機会という事にして次にいきます。
■ 刈り込み法 ―― MPJoin、PPJoin+
いよいよ本日話しておきたい "刈り込み法" を使った手法についてです。刈り込み法というのは、適当な用語がなかったので今回自分で勝手につけた名前なんですが、要は類似候補にならないデータを効率的にみつけて削除し、どんどん計算量を減らして行こうという手法のことです。
この手法の最大の特徴としては、近似手法の場合と違い閾値以上の類似データペアを正確に取得できる事が挙げられます。この系統に属する SimilaritJoin の手法は過去様々に提案されてきているのですが、最近の代表例でいうと PPJoin+ [6] と MPJoin [7] というアルゴリズムが挙げられます。
PPJoin+ と MPJoin は共に、Jaccard、Dice、Cosine、Overlap といった metric に対する SimilarityJoin を行える手法で、どちらも candidateフェーズと verifyフェーズという2つのフェーズを経た後に類似データペアを抽出します。クエリデータが来た場合に、candidateフェーズでデータセットの中から閾値以上の類似ペアにならないデータを排除し、残った候補データを verifyフェーズで実際に計算して閾値以上の類似性があるかどうかを調べるのです。
以下では、類似性にJaccard係数を採用した場合の MPJoin 及びPPJoin+ を例にとって、多少詳細な説明をしてみます。
まず刈り込み法の肝となるcandidateフェーズですが、この部分は両手法ともに、SizeFiltering、PrefixFiltering と PositionalFiltering という三つのFiltering手法の組み合わせがコアになっています。
最初のSizeFilteringですが、これは
| 『 あるデータペア( x, y )のJaccard係数が閾値 t （ 0 < t < 1 ) 以上であるためには、 tx < y < x/t でなければならない 』 |
直感的に、類似データ同士ならば似たような長さを持つはずだというのは分かるかと思うのですが、それをちゃんと定式化すると上記のようになります。尚、y の下限と上限の導出ですが、これはあるデータ同士のJaccard係数が一定以上になるというのは、
と同値ですが、(1)について x, y の大小の場合を考察すると、
となるので、この事からJaccard Constraintの下限・上限が分かります。
次にPrefixFiltering に関してですが、これは
| 『 x, y がJaccard係数で閾値 t 以上になるためには、何らかの基準でx, y の素性をソートした上で、x の先頭から長さ ( | x | - t / (1+t) * { | x | + | y | } + 1 )までの部分と、y の先頭から長さ ( | y | - t / (1+t) * { | x | + | y | } + 1 ) までの部分で、少なくとも一つの素性が一致していなければならない 』 |
これは何をやっているとかというと、(1)式を下記のように恒等変換していくと、Jaccard係数の閾値の問題をオーバーラップの問題に帰着することができます。
つまり x と y が閾値以上のJaccard係数を持つためには、少なくともαのオーバーラップが必要ということを意味しています。今 x, y は既にソートされているので、データ x, yの先頭部分 | x | - α + 1 と | y | - α + 1の領域におけるオーバーラップがゼロならば、残りのα-1の領域( suffix )がすべて同じであっても、両者はα以上のオーバーラップを持つことはできず、従って閾値以上の類似データであるはづがない―――というのが本Filteringの肝になります。
最後に PositionalFiltering について説明ですが、これは
| 『 ある成分wが x[i] と y[j] に存在した場合に、x, y 中のwの位置からみて左側の素性を x_l、 y_l 、右側の素性を x_r、 y_r とすると、Over( x_l, y_l ) + min { x_r, y_r } >= t / ( 1+t ) * { | x | + | y | } でなければならい 』 |
PositionalFilteringが意味するところは、基本的には PrefixFiltering と同じようなモノで、x, y の先頭部分にオーバーラップがあった場合に、その時点でα以上のオーバーラップを持ちえるのかどうか？という事を調べるFilteringです。x, yの先頭部分のある箇所に同一素性 w が存在した場合は、wより左側のオーバーラップ Over( x_l, y_l ) と、x, y の残りの suffix部分のオーバーラップが最大で min { x_r, y_r } なので、その合計が Jaccard係数の閾値を超えるためのオーバーラップ条件αを超えているのかを調べているに過ぎません。
ちなみにこれまで説明した3つのFilteringを組み合わせた場合の擬似コードは以下の通りです。実はこれはMPJoin や PPJoin+ の元になっている PPJoin というアルゴリズムのの擬似コードなのですが、MPJoin も PPJoin+ も内部的には類似の実装がなされています。
2・3行目と11～14行目、5行目、8・9行目が、それぞれ PrefixFiltering、SizeFiltering、PositionalFiltering に対応しています。――― といっても、これだけだと少々わかり辛いかと思うので、以下で各行の解説を行いたいと思います。
2行目の x_q の Prefix ですが、これはこの段階で比較対照となる x_c の長さが不明なので、x_q 自身の長さの情報からJaccardConstraintの最小値( r |x_q| )を使って x_q の Prefix の長さを決めています。相手の長さがわからないのでとりあえず αの中で最大の長さを Prefix にしておくという戦法です。
次に5行目のサイズフィルタリングですが、ここには | x_q | / t <= | x_c | という条件がありません。これはDが既に x のサイズによってソートされており、比較候補となる x_c を保持する転置Indexが12～14行目のタイミングで更新されている事から | x_q | < | x_c | というケースは起こらないためです。
9行目で-∞を代入しているのは8行目の PositionalFiltering で類似候補にならない事が決定したデータの刈り込み意味しています。10行目の verifyフェーズの内部実装では、M(x_c).os + Over( x_q[i]_right, x_c[j]_right ) を計算して、実際のデータペアのオーバーラップを算出するのですが、M(x_c).os == -∞ であれば x_c のオーバーラップを計算しないサインになります。
最後に11行目ですが、βはαよりも小さい値になっています。何故これだけでいいのかというと、それは14行目でindexされる x_q を x_q( s ) とした場合、0行目の次のクエリ x_q_( s+1 ) が x_q( s ) との類似比較を行う際に必要となる x_q(s) の Prefixの長さは | x_q( s ) | - t/(1+t) { | x_q( s ) | + | x_q( s+1 ) | } + 1 なのですが、これはDが x のサイズによってソート済であるという仮定から、 | x_q( s ) | - t/(1+t) { | x_q( s ) | + | x_q( s ) | } + 1 よりも小さく、従って14行目で x_q の先頭βの分だけをIndexするだけで既に PrefixFiltering に必要な領域をカバーしていることになるからです。
さて、ここまで PPJoin+ と MPJoin の candidateフェーズの共通部分を説明をしてきましたが、では逆に両者のどこが決定的に違うのかというと candidateフェーズと verifyフェーズのどちらにより計算コストをかけるか？という所に差異があります。
PPJoin+ はこれまで説明してきた土台の上、つまり SizeFilering、PrefixFiltering、PositionalFiltering を通過した候補データに対して、更に SuffixFiltering という操作を行います。これはデータの先頭領域以外の部分（ ｜ｘ｜- α + 1 以下の suffix ）にも PositinalFiltering を再帰的( 再帰の数をdepthと呼びこれはパラメータとして適当に与える ) に適用していく方法です。つまり後ろの部分もちゃんと見て候補データを絞り込むという思想を持っており、candidateフェーズをより手厚くする操作が行われます。しかしながらこの処理が意外と重く、候補データを絞り込めるアドバンテージとその計算コスト増のディスアドバンテージの間でトレードオフの関係にあるのです。
一方 MPJoin では Candidateフェーズの計算コスト減が行われています。具体的には PositionalFiltering を行いながら部分部分で InvertedIndex を効率的に削減して計算量を減らし、PPJoin+ では行っていた SuffixFiltering を MPJoin では行いません。また verifyフェーズでのオーバーラップ計算の途中で PositionalFiltering を随時かける方法を採用し、無用な計算を途中で打ち切るという戦略をとっています。思想としては、候補データの抽出にかける時間をそこそこにして、verifyフェーズに向かった方が全体としては速いだろうという戦略です。
実際にどちらかがいいかは、はっきりいってデータ次第のところがあるかと思うのですが、MPJoin [7] の論文中ではこの戦略が成功している実験結果を提示してくれています。
■ 性能比較 ―― MPJoin、PPJoin+
論文の結果が実データでもその通りになるのか調べてみました。
Amebaの実データを用いて、下記の条件で実験した結果を挙げておきます。
【データ】 ブログコメント 10000 件
( 類似データペア数 : 342,623 ( 0.90 )、 409,419 ( 0.80 )、 444,448 ( 0.70 ) )
【素性】 コメントの文を bigram にしたString配列
【環境】 OS : WinowsXP、CPU : Core2Duo、3.0GHz、 メモリ : 2G
【表軸】 縦軸：計算時間 (ms)、 横軸：Jaccard係数
【その他】 PPJoin+ のsuffixFilteringの depth は3
全組み合わせに対してJaccard係数を計算すると 711911 ms
結果は上図の通りですが、すべてのJaccard係数の場合で MPJoin が PPJoin を上回っており、しかも閾値が低い部分では、PPJoin+ よりも MPJoin の方がかなり高速で、論文の主張と同様の結果になりました。
また全組み合わせを愚直に計算した場合と比べて、PPJoin+ では40倍 ～ 180倍、MPJoin では70倍 ～ 240倍程度の高速化を果たしています。わずか1万件程度の文章の類似データ抽出でこれほどの計算時間差が生じるので、nが大きい場合はこの差はもっと顕著になるでしょう。
このような実験結果を勘案した上で、今の所Amebaの裏側で使われている SmilarityJoin 関連のタスクでは、基本的には MPJoin を元にした実装を使っています。
■ ソースコード、補足など
今回、頑張ってアルゴリズムの説明を活字にしてみたのですが、『 ぶっちゃけ文章で説明されてもイマイチ分からない！長い！ 』 という意見もあろうかと思いますので、JavaのソースをGoogleCodeに公開しておきました。良かったら参考に使ってみてください。
similarity-join-tools
ちなみに、近似手法と刈り込み法ではどちらが速いのか？というのは気になるところですが、結局データ次第ではないでしょうか？ PPJoin+ より前に提案された刈り込み法の手法に All-Pairs [8] というアルゴリズムがあるのですが、この論文中にはテキストを使った実験例で LSH ( SimHash ) よりも All-Pairs の方が速かったという結果が載っています。とはいえ、そもそもサイズフィルタリングが利きづらいようなデータでは、刈り込み法が有効だとはあまり思えないので LSH の方がいいんじゃないでしょうか？前述しましたが、画像はその典型例でしょうか。
ただ実験例が示すように不特定多数が書くような文章の場合だとか、（後、これは勝手な想像ですが）疎なデータなどでは、漏れがないという点を含めても "刈り込み法"の手法の方がいいのでは？と思っております。
最後に、今回文章中に書ききれなかった SimilarityJoin 関連のアルゴリズムを紹介しておきます。
・ ED-Join [9]
・ Hamming Distance Join [10]
・ L2,L1Sketch [11]
―――― というわけで、今回の話は以上です。
第二回目のネタは何にしようかなぁ・・・。
■ Reference
[1] Similarity Join Algorithms : An Introduction
[2] Datar.Mayur、Immorlica.Nicole、Indyk.Piotr、Mirrokni.Vahab S. : Locality-Sensitive Hashing Scheme Based on p-Stable Distributions (2004)
[3] Indyk.Piotr、Motwani.Rajeev : Approximate Nearest Neighbors : Towards Removing the Curse of Dimensionality (1998)
[4] Charikar.Moses S : Similarity Estimation Techniques from Rounding Algorithms (2002)
[5] Broder.Andrei Z、Charikar.Moses、Frieze.Alan M : Min-Wise Independent Permutations (1998)
[6] Xiao.Chuan、Wang.Wei、Lin.Xuemin、Xu.JeffreyYu : Efficient Similarity Joins for Near Duplicate Detection
(2008)
[7] Ribeiro.Leonardo A、Harder.Theo : Efficient Set Similarity Joins Using Min-prefixes
(2009)
[8] Bayardo.Roberto J、Ma.Yiming、Srikant.Ramakrishnan : Scaling Up All Pairs Similarity Search
(2007)
[9] Xiao.Chuan、Wang.Wei、Lin.Xuemin : EdJoin : An Efficient Algorithm for Similarity Joins With Edit Distance Constraints (2008)
[10] Manku.Gurmeet Singh、Jain.Arvind、Sarma.Anish Das : Detecting NearDuplicates for Web Crawling (2007)
[11] Dong.Wei、Charikar.Moses、Li.Kai : Asymmetric Distance Estimation with Sketches for Similarity Search in High-Dimensional Spaces
(2008)