何番煎じか分からないけど集合知プログラミングをPHPでやってみた その7「階層的クラスタリングによりグループを見つけ出す」

前回は話だけで終わってしまったので、今回はソースコード中心です。

アイテム同士の距離の計算に必要な情報を出力するReducerを実装する

という訳で早速ですが、前回延々と話をしていた事をReducerに実装します。

#!/usr/bin/php
<?php
require_once(dirname(dirname(__FILE__)).'/lib/HadoopStreaming/Reducer.php');

class Reducer extends HadoopStreaming_Reducer
{
    public function reduce ( $key, $values )
    {
        $wordcount = array();
        while ( $values->has_next_value ) {
            list($id, $count) = explode(':', $values->current_value);
            $wordcount[$id]++;
            $entrycount[$id] = $count > 0 ? $count : 1;
            $values->next();
        }
        if ( count($wordcount) >= 2 ) {
            $keys = array_keys($wordcount);
            for ( $id1=0; $id1<count($keys)-1; $id1++ ) {
                for ( $id2=$id1+1; $id2<count($keys); $id2++ ) {
                    $emitkey = $keys[$id1].':'.$keys[$id2];
                    $wc1 = $wordcount[$keys[$id1]] / $entrycount[$keys[$id1]];
                    $wc2 = $wordcount[$keys[$id2]] / $entrycount[$keys[$id2]];
                    $sum1 = $wc1;
                    $sum2 = $wc2;
                    $pow1 = pow($wc1, 2);
                    $pow2 = pow($wc2, 2);
                    $mul = $wc1 * $wc2;
                    $this->emit($emitkey, "sum1:${sum1}");
                    $this->emit($emitkey, "sum2:${sum2}");
                    $this->emit($emitkey, "pow1:${pow1}");
                    $this->emit($emitkey, "pow2:${pow2}");
                    $this->emit($emitkey, "mul:${mul}");
                    $this->emit($emitkey, "count:1");
                }
            }
        }
    }
}

$reducer = new Reducer();
$reducer->run();
?>

Reducerには、"単語=>[エントリID,エントリID,…]"という形でデータが渡ってくるので、一旦、$wordcountという配列でエントリID毎に出現単語数を集計しています。

これで$wordcountのキーには、この単語が現れるエントリのIDが並ぶので、このエントリID同士の総当りをループさせて、必要な情報を計算していきます。

なお、"クラスタ化した時は各アイテムの中間の位置を新しいクラスタの位置にする"という処理を実現する為に、各クラスタに含まれるエントリの数が入力データに含まれるようにしていて、各エントリの単語数($wc1,$wc2)は各クラスタ内のエントリ数($entrycount)で割った値になるようにしています。

計算した値は、後でもう1回Reducerを掛けて集計するので、ここではkeyを付けてどんどんemitしていくだけにします。

このReducerを掛けると、以下のように、2つのエントリ同士の計算に必要な情報がバラバラと出力されます。

:
0:13	count:1
0:13	count:1
0:13	mul:1
0:13	mul:10
0:13	pow1:1
0:13	pow1:4
0:13	pow2:1
0:13	pow2:25
0:13	sum1:1
0:13	sum1:2
0:13	sum2:1
0:13	sum2:5
:

アイテム同士の距離を計算して出力するReducerを実装する

続いて、先ほど得られた出力を使って、各アイテム同士の距離を計算して出力するReducerを実装します。

#!/usr/bin/php
<?php
require_once(dirname(dirname(__FILE__)).'/lib/HadoopStreaming/Reducer.php');

class Reducer extends HadoopStreaming_Reducer
{
    public function reduce ( $key, $values )
    {
        $wc = array();
        while ( $values->has_next_value ) {
            list($target, $value) = explode(':', $values->current_value);
            $wc[$target] += $value;
            $values->next();
        }
        $num = $wc['mul'] - ( $wc['sum1'] * $wc['sum2'] / $wc['count'] );
        $den = sqrt( ($wc['pow1'] - pow($wc['sum1'], 2) / $wc['count'])
                    * ($wc['pow2'] - pow($wc['sum2'], 2) / $wc['count']) );
        $result = ( $den === 0.0 ) ? 0.0 : ( 1.0 - $num / $den );
        $this->emit($key, $result);
    }
}

$reducer = new Reducer();
$reducer->run();
?>

これで、はてブのHotEntryから取得したデータを使って、どのエントリ同士が似ているかを計算する事ができるようになりました。

似たアイテム同士をクラスタにして後は同じ事の繰返し

ここまで来たら次は、一番距離が近かったエントリ同士を1つのクラスタとしてくっつけて、後はクラスタが1つになるまで繰返しMapReduceを掛けていけば、階層的クラスタリングの完成です。

…となるんですが、HadoopStreamingを使って複数のMapper/Reducerを組み合わせて処理させる方法が分からなかったので、仕方なくシェルスクリプトで適宜中間ファイルを処理しながら、MapReduceを繰り返して実行するようにしました。

という事で、かなり無理矢理感はあるんですが…結果的に、全体の処理をループする部分は、次のようなスクリプトになりました。

#!/bin/sh
dfs='/home/hadoop/hadoop-0.18.3/bin/hadoop dfs'
hadoop='/home/hadoop/hadoop-0.18.3/bin/hadoop jar /home/hadoop/hadoop-0.18.3/contrib/streaming/hadoop-0.18.3-streaming.jar'

$dfs -rmr outputs
$dfs -rm inputs/hotentry_descriptions.txt
$dfs -put ~/inputs/hotentry_descriptions.txt inputs
$hadoop -input inputs/hotentry_descriptions.txt -output outputs -mapper ~/bin/mapreduce/php/hcluster/map.php
rm -f ~/outputs/part-*
$dfs -get outputs/part-* ~/outputs
cat ~/outputs/part-* >~/inputs/words.txt
$dfs -rm inputs/words.txt
$dfs -put ~/inputs/words.txt inputs/words.txt

cid=1
>~/outputs/clusters.txt
cc=`cut -f 2 ~/inputs/words.txt | cut -d ':' -f 1 | sort | uniq | wc -l`

while [ $cc -gt 1 ];
do
    $dfs -rmr outputs
    $hadoop -input inputs/words.txt -output outputs -mapper cat -reducer ~/bin/mapreduce/php/hcluster/reduce.php
    $dfs -rm inputs/part-*
    $dfs -mv outputs/part-* inputs
    $dfs -rmr outputs
    $hadoop -input inputs/part-* -output outputs -mapper cat -reducer ~/bin/mapreduce/php/hcluster/reduce2.php

    closest=`$dfs -cat outputs/part-* | sort -nk 2 | head -1 | cut -f 1`
    id1=`echo $closest | cut -d ':' -f 1`
    id2=`echo $closest | cut -d ':' -f 2`
    if [ $id1 -lt 0 ]; then
        c1=`cut -f 2 ~/inputs/words.txt|grep '\'$id1|head -1|cut -d ':' -f 2`
    else
        c1=1
    fi
    if [ $id2 -lt 0 ]; then
        c2=`cut -f 2 ~/inputs/words.txt|grep '\'$id2|head -1|cut -d ':' -f 2`
    else
        c2=1
    fi
    ec=`expr $c1 + $c2`
    echo "-$cid     $closest">>~/outputs/clusters.txt
    sed 's/\t'$id1'\(:.*$\|$\)/\t-'$cid':'$ec'/' ~/inputs/words.txt | sed 's/\t'$id2'\(:.*$\|$\)/\t-'$cid':'$ec'/' >~/inputs/words.txt_tmp
    mv -f ~/inputs/words.txt_tmp ~/inputs/words.txt
    $dfs -rm inputs/words.txt
    $dfs -put ~/inputs/words.txt inputs/words.txt
    cid=`expr $cid + 1`
    cc=`cut -f 2 ~/inputs/words.txt | cut -d ':' -f 1 | sort | uniq | wc -l`
    echo 'クラスタ数:'$cc
done

最初に1回Mapperを使って単語リストを作成した後に、クラスタの数が1つになるまでループしながら繰返し2種類のReducerを実行するようにしています。

結果発表

実行結果はテキストとして出力しているので、このままだとどんな結果なのかよく分かりません。

元書では、ノードをピラミッドの形で並べて表示する"デンドログラム"というグラフの形式で結果を確認するようになっていて、グラフィックとして出力するプログラムも作っているんですが、そんなのまで作るのは面倒なので、今回はGraphvizを使ってグラフを生成するようにしました。

得られた結果をdot形式に直して、最初に取得したタイトルを埋め込んで、デンドログラムっぽい形で出力させてみました。

今回は、HotEntryの最初のページ(30件)が対象で、なおかつRSSの概要から単語を拾っているだけなので、正直なところあんまりそれっぽい結果とは言えないかもしれないですね。

まぁ、今回の一番の目的は、"いかにMapReduce的に実装するか"だったので、自分的にその目的は果たす事ができたのでよしとしたいと思います。

次回は?

次回は、別のアルゴリズム(K平均法)によるクラスタリングを、またMapReduceを使って挑戦していきたいと思います。