集合知プログラミングをPrototype.js活用してJavaScriptで実装したことをふと思い出した。

お盆休み中は流石に自分の仕事は一段落つける時期で、こんなにゆったりとした気分になるのは昨年の秋口以降味わったことがないので、今週くらいはのんびりと過ごしたいなぁーと思いつつ、こういうタイミングをうまく使って自分の仕事の生産性をより高めるためにツール作成にとりかかろうと、昔に書いたコードで手直しをしたいものをちょっとチェックしていました。

その中で、『集合知プログラミング』を Ruby で - ドレッシングのようなや [Ruby] 集合知プログラミング 02 - func09というエントリを参考にして集合知プログラミングの勉強をしていたことを思い出したので、ちょっと苦い思い出の余韻にひたりつつ、ちょっと振り返りを。

そもそもの話として最初書いておくべこととして、なんでこの勉強したのかっていうと、自分がふだん行っている人材紹介のようなマッチングってアナログな作業が結構多くって、１人の求職者の条件にマッチする案件をDB上で条件検索し、案件あるかないか確認する作業っていうのを、n人分ひたすらやるような作業なので、100人いたらその分だけ作業量も比例して増えていくため、体力勝負だったり、過去の各自の経験という非科学的なアプローチというのが結構まかり通っているんですよねー

（他の会社の人のやり方を聞いた事がないけど）こういう１対多というやり方ではなく多対多の関係で求職者と求人情報をグルーピングできないかなぁーと考えていて、色々調べる中で

「集合知って凄そう！これならきっと解決になる！」

と思ったのでAmazon.co.jp： 集合知プログラミング: Toby Segaran, 當山 仁健, 鴨澤 眞夫: 本を購入して勉強したのがそもそもの経緯

会社のPCには権限の問題もあってPythonの処理系を入れられないこともあって、どうしようかと悩んでいた時に、上記のRuby版のソースに行き着き、

「Prototype.js使えばRubyライクにコード書けるからその恩恵にあやかればいけるかも？」

と思ってまずはJavaScript w/ Prototype.js + WSHという環境で動かせるコードを書きました。

var critics = {
  'Lisa Rose':{
    'Lady in the Water': 2.5,
    'Snakes on a Plane': 3.5,
    'Just My Luck': 3.0,
    'Superman Returns': 3.5,
    'You, Me and Dupree': 2.5,
    'The Night Listener': 3.0
  },
  'Gene Seymour':{
    'Lady in the Water': 3.0,
    'Snakes on a Plane': 3.5,
    'Just My Luck': 1.5,
    'Superman Returns': 5.0,
    'You, Me and Dupree': 3.5,
    'The Night Listener': 3.0
  },
  'Michael Phillips':{
    'Lady in the Water': 2.5,
    'Snakes on a Plane': 3.0,
    'Superman Returns': 3.5,
    'The Night Listener': 4.0
  },
  'Claudia Puig':{
    'Snakes on a Plane': 3.5,
    'Just My Luck': 3.0,
    'The Night Listener': 4.5,
    'Superman Returns': 4.0,
    'You, Me and Dupree': 2.5
  },
  'Mick LaSalle':{
    'Lady in the Water': 3.0,
    'Snakes on a Plane': 3.0,
    'Just My Luck': 3.0,
    'Superman Returns': 3.5,
    'You, Me and Dupree': 2.5,
    'The Night Listener': 4.5
  },
  'Jack Mattews':{
    'Lady in the Water': 3.0,
    'Snakes on a Plane': 4.0,
    'Superman Returns': 5.0,
    'You, Me and Dupree': 3.5,
    'The Night Listener': 3.0
  },
  'Toby':{
    'Snakes on a Plane': 4.5,
    'Superman Returns': 4.0,
    'You, Me and Dupree': 1.0
  }
};
var Recommend = Class.create({
  sim_distance:function(prefs, person1, person2) {
    /*
     rubyのようなArrayの集合演算のやり方がわからないので
     prototype.jsのintersect()メソッドをつかって
     両方に存在する要素で構成された新しい配列を返す
    */
    var p1 = $H(prefs[person1]);
    var p2 = $H(prefs[person2]);
    var _items = p1.keys().intersect(p2.keys());
    if( _items.empty) return 0.0;
    var sum_of_squares = $A(_items).inject(0.0,
      function(acc,item){
	return acc += Math.pow(p1.get(item) - p2.get(item), 2);
      });
    return 1.0/(1.0 + sum_of_squares);
  },
  sim_pearson:function(prefs, person1, person2) {
    var p1 = $H(prefs[person1]);
    var p2 = $H(prefs[person2]);
    var _items = p1.keys().intersect(p2.keys());
    var n = _items.length;
    if( _items.empty) return 0.0;
    // すべての嗜好を合計する
    var sum1 = $A(_items).inject(0.0,function(acc, item){
	   return acc += p1.get(item);
	 });
    var sum2 = $A(_items).inject(0.0,function(acc, item){
	   return acc += p2.get(item);
	 });
    // 平方を合計する
    var sum1sq = $A(_items).inject(0.0,function(acc, item){
	     return acc += Math.pow(p1.get(item), 2);
	   });
    var sum2sq = $A(_items).inject(0.0,function(acc, item){
	     return acc += Math.pow(p2.get(item), 2);
	   });
    // 積を合計する
    var psum = $A(_items).inject(0.0,function(acc, item){
	    return acc += p1.get(item) *  p2.get(item);
	  });

    var num = psum - (sum1 * sum2 / n);
    var den = Math.sqrt(
      (sum1sq - Math.pow(sum1,2) / n) *
      (sum2sq - Math.pow(sum2,2) / n)
    );
    if (den == 0.0) return 0;
    var r = num /den;
    return r;
  },
  topMatches:function(prefs,person,n) {
    var _prefs = $H(prefs).keys().reject(function(it){return it==[person];});
    var scores = _prefs.inject([],function(array,other,index){
      array.push([this.sim_pearson(prefs,person,other),other]);
      return array;
    }.bind(this));
    scores.sort().reverse();
    var result = [];
    //Rubyだとreturn scores[0, n]と書くと0からnまでのscoresオブジェクトを
    //返す事が出来るのでそれと同じ処理を行う
    scores.each(function(s,index){
      if(index > n-1)
       throw $break;
      result.push((s));
    });
    return result;
    },
  getRecommendations:function(prefs, person) {
    var totals = $H(0.0);
    var sim_sums = $H(0.0);
    $H(prefs).each(function(other, value){
	if (other==person) return;
	var sim = this.sim_pearson(prefs, person, other);
        if (sim <= 0.0) return;
        $H(prefs)[other].each(function(item, value) {
	  if(!prefs[person].keys().include(item) || prefs[person][item]==0.0){
	    totals[item] += prefs[other][item] * sim;
	    sim_sums[item] += sim;
	  }
	});
    }.bind(this));
  }
});

var r = new Recommend();
r.sim_distance(critics, 'Lisa Rose','Gene Seymour'); //0.14814814814814814
r.sim_pearson(critics, 'Lisa Rose','Gene Seymour'); //0.39605901719067
r.topMatches(critics, 'Toby',3);
/*
[[0.9912407071619299, "Lisa Rose"],
[0.38124642583151164, "Gene Seymour"],
[-1, "Michael Phillips"],
[0.8934051474415647, "Claudia Puig"],
[0.7924058156930613, "Mick LaSalle"],
[0.66284898035987, "Jack Mattews"]]
 */

苦労して移植できて、ワクワクしながら会社の基幹システムから必要なデータ抽出してテストしただけど、自分が思った結果が得られず、最初は投入したデータが間違っていたのかなぁーと思ってあれこれ調べたんだけど、（細かい事は書けないけど）うちのシステムのデータ構造からして、どうもこのロジックでは無理っていうことがわかり、ここまでの苦労がすべて無駄足になってそのまま上記コードは放置していて、そんなことを今日仕事の合間にふと思い出しました。

このアイテムベースのフィルタリングではなく、軽量データクラスタリングツールbayon - mixi Engineers' Blogのようなクラスタリングっていうのがどうも自分が求めている「解」なのかも。