何番煎じか分からないけど集合知プログラミングをPHPでやってみた その6「グループを見つけ出す…の下準備」

PHP シリーズ3

今回はちょこっとアルゴリズムの話をしてから、前回作成したMapperで出力したデータを、いかにして欲しいデータの形にするReducerを書くか…という流れでいきたいと思います。

階層的クラスタリングのアルゴリズム

今回対象にする"階層的クラスタリング"は、最も似ている2つのグループをまとめる事を繰り返す事によって、グループの階層を作り上げるアルゴリズムです。絵で見た方が早いと思うので、絵を作ってみました。*1

図で言うと、最初に一番距離が近いAとBがグルーピングされて、次にABグループとCが近くなったのでAB+Cでグルーピングされて…と繰り返されて、最終的に全体が1つのグループになって終了しています。図では人を対象にしていますが、今回は、はてブのHotEntryから抽出したエントリを対象としてグルーピングを試みます。

グルーピングするにあたって、お互いの距離を計算する必要がありますが、この計算には前章でも利用したピアソン相関係数を利用します。

処理としては、

  • 各エントリ同士の総当りでお互いの距離を計算する。
  • 最も距離が近いもの同士をグルーピングする。
  • グルーピングしたアイテムの値はお互いの平均値とする。
  • グループが1つになるまで以上を繰り返す。

という流れになります。

計算する為の方針を考える

いきなり上記処理全部を考えると難しいので、まずは1回分の計算(各エントリ同士の総当りでお互いの距離を計算する)を考えてみます。

今持っている入力値は、前回作成したMapperで出力した、"単語=>[エントリID,エントリID,…]"という形式のデータです。これを色々とゴニョゴニョして、最終的に"エントリID1:エントリID2=>距離"という形式に変換するのが第一の目標です。

普通に考えると、エントリIDx単語という二次元の巨大なテーブルを作って、全てのエントリ同士の組み合わせをループさせて計算していく…という考え方になるでしょう。*2

この巨大なテーブルを作成するだけであれば、MapReduceを使って、"エントリID=>[単語1の数,単語2の数,…]"という形式に変換してやるだけなので、そんなに難しいものではありません…が、それ以降の計算はMapReduceで行う事ができません。

なぜなら、MapReduceは"あるkeyに関する情報を集約して計算する手法"であって、Reducerでは1つのkeyに関する情報に閉じた計算しかできないので、複数のkeyにまたがる処理はできません。(Reducerに"エントリID1=>[単語1の数,単語2の数,…]"と渡ってきたとすると、エントリID2との距離を計算したくても、計算のしようがない。)

という事で、MapReduceを使った計算をする時には、ちょっと考え方を変える必要があります。

Mapperで分解、Reducerで集約する

まだ自分の中でも手探り状態で憶測な部分もあるんですが(^^;ゞ、MapReduceで計算させるには、"Mapperで分解、Reducerで集約"という事を念頭に置いてアルゴリズムを考えた方がいいようです。

MapReduceの考え方について非常に分かり易い図解をされている記事があったので、参考リンクを…。
→MapReduceってこういうことか : にぶろぐ@無人店舗
つまり、Mapperでデータを縦軸に分解して、Reducerでそれを横軸方向に串刺しして集約するという事ですな。こういう分解をするからこそ、分散処理ができるという事ですね。*3

今回の場合で言うと、Mapperで各単語毎にエントリIDを分解してやって、Shuffleによって単語をkeyとして集約したものをReducerで受け取って、エントリIDをkeyにした情報に変換してやればよいという事ですね。前回、Mapperの出力としてエントリIDをkeyにせずに、何気なく単語をkeyにしていたんですが、実はこういう事情があった為だったりします。

逆から考えてみる

ここまでの事を念頭に置いて、最終的に欲しいデータ形式から、"どういう集約をすればよいか、その集約をする為にどういう分解をすればよいか"という事を考えてみます。

今欲しい最終形は、"エントリID1:エントリID2=>距離"という形式です。この計算をする為にはReducerに、"エントリID1:エントリID2=>[距離の計算に必要な情報,…]"というデータが渡ってくれば良さそうです。

ということはMapperで、"エントリID1:エントリID2=>距離の計算に必要な情報"というのをバラバラと吐き出させてやれば良さそうですね。

ピアソン相関係数を計算する為に必要な情報

という訳で、ここで一旦、距離の計算に必要な情報を考えておきます。距離の計算にはピアソン相関係数を利用します。計算式は以下の通り。*4

おぉ、数式なんか出てくると一気に難しい事している感が出てきますねぇ。(笑)

数式で見ると難しいんですが、結局のところ次の6つの情報があれば、2つのエントリに関するピアソン相関係数が計算できそうです。

  • エントリXに含まれる各単語の数の総計
  • エントリYに含まれる各単語の数の総計
  • エントリXに含まれる各単語の数を2乗したものの総計
  • エントリYに含まれる各単語の数を2乗したものの総計
  • エントリXとエントリYの両方に含まれる単語それぞれについて数を掛け合わせたものの総計
  • エントリXとエントリYの両方に含まれる単語の種類数

今度は持っているデータから欲しいデータ形式に近付ける事を考えてみる

今持っている入力値は、前回作成したMapperで出力した、"単語=>[エントリID,エントリID,…]"という形式のデータです。これがReducerに渡ってくるので、エントリID毎の数を数えれば、この単語がどのエントリにいくつ含まれているのかが分かります。

この単語は、列挙されているエントリそれぞれに含まれている訳なので、このエントリID同士の組み合わせ全てについて上記の6つの情報を計算してやれば、必要な情報を揃える事ができそうです。

具体的に言うと、以下のような感じです。

  1. PHP=>[1,1,2,2,2,3]というデータがReducerに渡ってきたとする。
  2. "PHP"は、ID:1に2つ、ID:2に3つ、ID:3に1つ含まれている事が分かる。
  3. "PHP"が含まれるエントリの全ての組み合わせは、"1-2"・"1-3"・"2-3"の3種類。
  4. 3種類の組み合わせそれぞれについて、上記6つの情報を計算して出力する。

これはつまり、先ほど"逆から考えてみる"で、Mapperから吐き出してもらいたかった、"エントリID1:エントリID2=>距離の計算に必要な情報"という形式のデータという事になります。

今考えた出力はReducerからのものになるので、一旦ここまでをMapReduceで計算して結果を出力して、その計算結果を"逆から考えてみる"の考え方でもう1回MapReduceに掛けてやれば、目的の結果を得る事ができそうですね。

次回、完結編…?

というところで今回は時間切れです。非常に回りくどかった上に、PHPのソースコードは1行も出てこなかったですねぇ。(^^;ゞ

最終的なMapperとReducerを載せるだけでも良かったんですが、これだけの思考プロセスを経て、やっとReducerを書くところまで辿り着いたので、今回は思考プロセスをそのまま載せてみました。

次回、Reducerを完成させて、階層的クラスタリング編の完結編に…なるといいなぁ…。分散処理ってやっぱり難しい…けど、面白っ。(笑)

*1:単純に、LovelyChartsを使ってみたかっただけ…というのは内緒。(笑)

*2:実際、元書ではそういう方針で計算しています。

*3:逆に言うと、こういう分解ができない計算は分散処理できないとも言える。

*4:数式エディタなんて使ったのは、大学の卒論以来だ…。