読者です 読者をやめる 読者になる 読者になる

Hadoopでできる類似度計算

あるオブジェクト群において、全オブジェクト間の類似度を計算するにはプログラムが全データにアクセスできる必要があります。
しかしこれではHadoop上でMapReduceによる計算ができません。
なぜなら、Map/Reduceの処理は分割できなければいけないからです。

何か方法はないかと論文を探していたら、こんな論文が見つかりました。

Efficient Parallel Set-Similarity Joins Using MapReduce(pdf注意)

使えそうなところだけつまみ食いしながら読んでるので、真面目に全部読んでません。
おまけに自分なりのアレンジを加えてたりします。
間違ってたらすいません。
メモ程度のものとして読んでいただければ。
一応以下のやり方でそこそこまともな結果は出ました。

方法


まず、 となっているデータを用意する。ここで、RIDはあるレコードのID、{ELEM}はそのレコードが持つ属性の集合である。
最初に全属性の頻度分析を行う。方法は以下の通り。

1.(MR1)普通にワードカウントする。出力はとする。
2.(MR2-Map) とする。この状態でシャッフル時にソートすると、ELEMが出現した回数順に並ぶ。
3.(MR2-Reduce) → ELEM とすれば、頻度分析結果のできあがり。このとき、頻度高/低のデータは捨てた方がいい。


次にこの結果を使って類似度計算を行う。インプットデータは最初の を使うが、外部ファイルとしてMR1,2で生成した頻度分析結果を用いる。


4.(MR3-Map) インプットデータの {ELEM} を頻度分析の結果を元にソートし、頻度の高い方から順にいくつか取り出す。これを PE1, PE2, ..., PEn としたとき、出力を >, >,... > とする。(PE:Prefix Element)
5.(MR3-Reduce) 同一PE内のレコードで類似度計算を行う。PE間で同一レコードペアの類似度計算の重複が発生するが、ここではユニーク処理を行わない。出力は <(RID1,RID2),SCORE> となる。類似度計算の方法はお好きなやり方で。Jaccard 係数を使って大雑把に計算してもそれなりの結果は出る。
6.(MR4) 必要があればここでユニーク処理を行う。Map処理は何もせずシャッフルでソートし、Reduce処理で重複排除すれば簡単。

解説

元々この手法は Prefix Filter という類似度計算の一手法を応用したものです。以下のスライドに日本語での説明が書いてあります。

Prefix Filterの検証

簡単に言うと、レコードの持つ要素の前方の一部だけで類似度計算を行い、ここである一定のしきい値以上だった組み合わせのみで実際の類似度計算を行うというもの。

しきい値が0より大きければ、このフィルタを通った後に類似度が0になるような組み合わせは絶対に存在しません。類似度計算の計算量を大きく削減することができます。

今回の手法では、同一の Prefix を持つもの同士でグルーピングし、その中で類似度計算を行うという形で Prefix Filter とほぼ同じ動作を再現しています。

元の手法に比べると、Prefix Filter 処理時にしきい値によるデータ削減ができないという欠点がありますが、この手法なら分割しての計算が可能です。

この手法、最悪の場合は出力結果が単純にP倍(P:Prefixの数)となるのですが、それはPrefixが全てのレコードで同一の場合です。そんな Prefix は確実に頻度分析で最上位に来ます。
だから3.の頻度分析時に高頻度の要素を予め排除しておくことで、こうした問題を防ぐことができます。
頻度低の要素の排除は別にしなくても大した問題にはなりませんが、どうせほとんど使わないデータなので、削っておいても構わないでしょう。

5.ではユニーク処理を行わず、6.という別のMapReduce処理を使って重複排除を行なっていますが、これはデータがバラバラの状態でのユニーク処理は非常にリソースを食う処理であり、かつデータが分割されている状況えは処理が完結しないからです。

基本データ
りんご 赤,丸い,果物
トマト 赤,丸い,野菜
オレンジ 橙,丸い,果物
にんじん 橙,丸くない,野菜
メロン 緑,丸い,果物
ワードカウント
2
丸い 4
果物 3
野菜 2
2
丸くない 1
1
頻度分析
  • 実際にはカウンタは排除
  • ここでは、最上位の「丸い」、最下位の「丸くない」「緑」を削除する
丸い 4
果物 3
2
野菜 2
2
丸くない 1
1
Prefix Filter(頻度分析によるソート)
りんご 果物,赤,丸い
トマト 赤,野菜,丸い
オレンジ 果物,橙,丸い
にんじん 橙,野菜,丸くない
メロン 果物,緑,丸い
Prefix Filter(Map処理)
  • 前2つを Prefix とする
果物 りんご 果物,赤,丸い
りんご 果物,赤,丸い
トマト 赤,野菜,丸い
野菜 トマト 赤,野菜,丸い
果物 オレンジ 果物,橙,丸い
オレンジ 果物,橙,丸い
にんじん 橙,野菜,丸くない
野菜 にんじん 橙,野菜,丸くない
果物 メロン 果物,緑,丸い
シャッフルによるソート
果物 りんご 果物,赤,丸い
果物 オレンジ 果物,橙,丸い
果物 メロン 果物,緑,丸い
りんご 果物,赤,丸い
トマト 赤,野菜,丸い
野菜 トマト 赤,野菜,丸い
野菜 にんじん 橙,野菜,丸くない
オレンジ 果物,橙,丸い
にんじん 橙,野菜,丸くない
同一キー同士で類似度計算
  • 単純な Jaccard 係数で計算。
  • Prefix Filter を用いていなければ 5*4/2=10回の計算が必要
  • しかしここでは6回の計算しかしていない。
りんご オレンジ 0.5
りんご メロン 0.5
オレンジ メロン 0.5
りんご トマト 0.5
トマト にんじん 0.2
オレンジ にんじん 0.2

まとめ


という感じでmapreduceでも使える類似度計算について色々調べています。
全体の頻度分析のしきい値(特に上側のしきい値)の調整が結構大変ですが、うまくはまれば短時間で結構いい結果を出すことができます。
論文中では Prefix Filter ではなく PPJoin,PPJoin+などを用いて計算させているのですが、この辺実装が結構面倒なので今のところはやっていません。
類似度計算でもっといいやり方ありましたら教えてください。