あるオブジェクト群において、全オブジェクト間の類似度を計算するにはプログラムが全データにアクセスできる必要があります。
しかしこれではHadoop上でMapReduceによる計算ができません。
なぜなら、Map/Reduceの処理は分割できなければいけないからです。
何か方法はないかと論文を探していたら、こんな論文が見つかりました。
Efficient Parallel Set-Similarity Joins Using MapReduce(pdf注意)
使えそうなところだけつまみ食いしながら読んでるので、真面目に全部読んでません。
おまけに自分なりのアレンジを加えてたりします。
間違ってたらすいません。
メモ程度のものとして読んでいただければ。
一応以下のやり方でそこそこまともな結果は出ました。
方法
まず、
最初に全属性の頻度分析を行う。方法は以下の通り。
1.(MR1)普通にワードカウントする。出力は
2.(MR2-Map)
3.(MR2-Reduce)
次にこの結果を使って類似度計算を行う。インプットデータは最初の
4.(MR3-Map) インプットデータの {ELEM} を頻度分析の結果を元にソートし、頻度の高い方から順にいくつか取り出す。これを PE1, PE2, ..., PEn としたとき、出力を
5.(MR3-Reduce) 同一PE内のレコードで類似度計算を行う。PE間で同一レコードペアの類似度計算の重複が発生するが、ここではユニーク処理を行わない。出力は <(RID1,RID2),SCORE> となる。類似度計算の方法はお好きなやり方で。Jaccard 係数を使って大雑把に計算してもそれなりの結果は出る。
6.(MR4) 必要があればここでユニーク処理を行う。Map処理は何もせずシャッフルでソートし、Reduce処理で重複排除すれば簡単。
解説
元々この手法は 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 |
