PHPで学ぶ「集合知プログラミング」〜最適化〜 3

今回は学生寮の最適化問題をPHPで書いてみます。
まずは$dormsと$prefで学生寮のリストと各学生の希望のリストを作ります

$dorms = array('Zeus', 'Athena', 'Hercules', 'Bacchus', 'Plute');
$prefs = array(array('Toby', array('Bacchus', 'Hercules')), array('Steve', array('Zeus', 'Plute')), array('Andrea', array('Athena', 'Zeus')),array('Sarah', array('Zeus', 'Plute')), array('Dave', array('Athena', 'Baccus')), array('Jeff', array('Hercules', 'Plute')), array('Fred',  array('Hercules', 'Plute')), array('Suzie', array('Bacchus', 'Hercules')), array('Laura', array('Bacchus', 'Hercules')), array('Neil', array('Hercules', 'Athena')));

学生に寮を割り当てるたびに寮の候補が減っていくので
今回の$domainは順番に範囲が狭くなるように設定しています

$domain = array();
var_dump($prefs);
for ($i = 0; $i <count($dorms) * 2; $i++) {
    $domain[] = array(0, count($dorms)*2 -1 - $i);
}

各生徒への寮の割り当て配列$vecが与えられた時に寮の割り当て表を出力する関数を定義します。

function printsolution($vec, $dorms, $prefs) {
    $slots = array();
    for ( $i = 0; $i<count($dorms); $i++) {
        $slots[] = $i;
        $slots[] = $i;
    }

    for($i = 0; $i < count($vec); $i++) {
        $x = $vec[$i];
        $dorm = $dorms[$slots[$x]];
        echo $prefs[$i][0] . ',' . $dorm . '<br>';
        array_slice($slots, $x, 1);
    }
}
$vec = array(0,0,0,0,0,0,0,0,0,0);
var_dump(printsolution($vec, $dorms, $prefs));

寮の割り当てに対するコスト関数の定義を行います。

function dormcost($vec, $dorms, $prefs){
    $cost = 0;
    $slots = array(0,0,1,1,2,2,3,3,4,4);

    for($i = 0; $i < count($vec); $i++) {
        $x = $vec[$i];
        $dorm = $dorms[$slots[$x]];
        $pref = $prefs[$i][1];
        if($pref[0] == $dorm) {
            $cost = $cost + 0;
        } elseif($pref[1] == $dorm) {
            $cost = $cost + 1;
        } else {
            $cost = $cost + 3;
        }
        array_slice($slots, $x, 1);
    }
    return $cost;
}

ランダムオプティマイゼーションで寮の割り当て問題の最適化をしてみます。

function dormcostrandomoptimize($domain, $dorms, $prefs) {
    $best = 999999999;
    $bestr = 'null';
    for($i = 0; $i < 10000; $i++) {
        $r = array();
        for($s = 0; $s < count($domain); $s++) {
            $r[] = rand($domain[$s][0], $domain[$s][1]);
        }
        $cost = dormcost($r, $dorms, $prefs);

        if ($cost < $best) {
            $best = $cost;
            $bestr = $r;
        }
    }
    return $bestr;
}

$s = dormcostrandomoptimize($domain, $dorms, $prefs);
var_dump(dormcost($s, $dorms, $prefs));
var_dump(printsolution($s, $dorms, $prefs));

PHPで学ぶ「集合知プログラミング」〜最適化〜 2

ランダムサーチによる最小コストの旅程を求める関数。
コスト関数を入れ替えれば旅程以外の問題でも最小、最大をランダムサーチによって求めることができる。

ヒルクライムによる最小コストを求める関数。
コスト関数を入れ替えれば、他の問題においても最小、最大値を求めることができる。

擬似アニーリングによる最適化関数。
ここでは、旅程のコストの最適値を求めているが、コスト関数を入れ替えれば他の問題にも適用できます。

遺伝アルゴリズムを用いた最適化関数。
ここでは旅程問題の最小コストの最適化を試みていますが、他の問題にも応用できます。
かなり強力なアルゴリズムなのでオススメです。
肌感としては、世代数を増やすよりも人口（ポピュレーション）を増やしたほうが良い解に辿り着ける可能性が高い気がします。
遺伝的アルゴリズムはpythonコードをphp化するのに苦労しました。
もとのpythonコードにミスがあったので苦戦していたのですが、<『集合知プログラミング』 解体新書/a>が非常に参考になりました。

PHPで学ぶ「集合知プログラミング」〜最適化〜 1

グループ旅行問題を特にあたり$peopleのarrayに人名と出発地を入れる。
そして、全ての人達の目的地としてLGAを設定する。
サンプルのフライトデータとしてhttp://kiwitobes.com/optimize/schedule.txtが用意されているのでダウンロードして同じディレクトリに入れておく。
そして、schedule.txtからoriginとdestをキーとしたフライトリストを作る。
さらに、HH:MMの形式で表された時間を午前０時０分から何分経ったかに変換するgetminutes関数を定義する

誰がどの便でLGAにやってくるかを$sで表現する。
各数字はその日の何便目に乗るか。そして、Seymourの行き・帰り・Frannyの行き・帰り・・・の順に並んでいる。
この数列から各人の旅程の情報を出力する関数を定義する（printschedule）

コスト関数の定義。運賃総額と空港での待ち時間、レンタカーの追加料金を含めたコストを旅程ごとに算出する関数を定義する。

PHPで学ぶ「集合知プログラミング」〜推薦を行う〜 2

transformPrefsでスコアのディクショナリをアイテムごとのディクショナリに変換して
アイテムごとにループを回して各アイテムに似ているアイテムをランキングでとってくる
各ユーザーの評価で映画のタイトルのスコアに重みづけをしてアイテムベースでユーザーにオススメをする
MovieLensのデータ・セットを使って商品の推薦を行います。

まず、loadMovieLens関数でMovieLensのデータをロードします。そして、getRecommendations関数を使ってユーザーベースの推薦を行い、
calculateSimilarItems関数を使ってアイテム間の相関を計算し、getRecommendedItems関数でアイテムベースの推薦を行います。

とここまで「集合知プログラミング」の２章をPHPで書きなおして来たわけですが、
実際にアイテムベースで推薦を行う場合のロジックはどのようなものなのでしょうか？
まず、アイテムベースの推薦で使っている関数は
calculateSimilarItems
transformPrefs
topMatches
sim_peason( or sim_distance)
でやっていることといえば
まず、ユーザーごとの各アイテムの評価のarrayをアイテムごとのユーザーによる評価のarrayに変換しています。
つまり、arrayの第一連想配列のキーはアイテム名で、第二連想配列のキーは評価者となります。
そして、sim_peasonを使ってアイテム間の相関スコアを取得します。
そのアイテムスコアを使ってtopMaches関数で各アイテムごとに、相関スコアが高い順にアイテムをランキング付けします。
たとえば、Superman Returnsに一番相関が高いのはYou Me and Dupreeでスコアは0.657
二番目に高いのはLady in the Waterでスコアは0.487といった具合です。
ここまでで、どのアイテムとどのアイテムが似ているのかがわかるようになったわけです。
最後にユーザーに対して推薦を行う場合は
ユーザーが既に評価した（購入した）アイテムとまだ購入していないアイテムの相関スコアに対して
評価したアイテムの評価で重み付けを行い、まだ購入していないアイテムそれぞれの推薦度スコアを計算します
そして推薦度スコアがもっとも高いものをユーザーに推薦します。
この章では一旦、ユーザーベースの推薦を行ったあとに、そのロジックを逆転させてアイテムベースの推薦を行っているので
どういうロジックでアイテムベースの推薦を行っているのかを理解するのがすこし難しいですね

PHPで学ぶ「集合知プログラミング」〜推薦を行う〜 １

「集合知プログラミング」 買いました！
データのシミュレーションや分析には興味があったので
といっても
ただ、エクセルで表とかグラフとか作るだけじゃつまんない
エンジニアとして
どや！！って言える仕事がしたい
なので、集合知プログラミングでエンジニアっぽい分析を習得しようと思います

この集合知プログラミングはPythonで書かれております。
僕は主にPHPを使って開発をしていますし
というか、PHPしかつかってないし。。
ただ単にPythonを写経するだけだと何にも身につかないと思うので
サンプルコードをPHPで書き直しながら進めていきたいと思っています。 

まずはデータ・セットの作成 二人の評価者のユークリッド距離によるスコアを算出するsim_distanceとピアソン相関によるスコアを算出するsim_peasonを定義
リストの中から最も好みの似ている評価者を選び出すtopMatchesを定義。
var_dump($result)でTobyに似ているユーザーをarrayで返してくれる 評価者に重み付けを行い（自身とどの程度好みが似ているか）
その重みづけスコアと書く評価者の評価点を掛けあわせて映画のタイトルごとにスコアを算出する
もっともスコアの高い映画が、対象とするユーザーにオススメの映画となる
今まで用いてきた評価者ごとの映画の評価配列を映画ごとの評価配列に変換する
以前に定義したtopMatches関数を使って、似た属性をもつ映画をランキング形式で表示できる。
また、映画が誰に見られるべきかをgetRecommendationsを使って表示することができる