集合知プログラミング勉強シリーズ - 普通にRubyで。そしてCouchDBで(笑 #2.js - ユークリッド平方距離

CouchDBでやるので、うまく記述し切れていません。そして初回からCouchDBだと非常に難しいケースです。まぁ、CouchDBに期待しすぎ感を自分の中で払拭するにはいいかもしれない。

まずはデータ。人の名前を_idに設定して、"rates" で評価値を。いかのような感じ。(以前書いたRubyのやつをto_jsonしてごにょごにょして、_bulk_docs形式にしたもの。これを curl で CouchDBにつっこんでおく。

{ "docs" : [
{"_id":"Jack Matthews","rates":{"The Night Listener":3.0,"Superman Returns":5.0,"Lady in the Water":3.0,"You Me and Dupree":3.5,"Snakes on a Plane":4.0}},
{"_id":"Gene Seymour","rates":{"The Night Listener":3.0,"Superman Returns":5.0,"Lady in the Water":3.0,"You Me and Dupree":3.5,"Snakes on a Plane":3.5,"Just My Luck":1.5}},
{"_id":"Mick LaSalle","rates":{"The Night Listener":3.0,"Superman Returns":3.0,"Lady in the Water":3.0,"You Me and Dupree":2.0,"Snakes on a Plane":4.0,"Just My Luck":2.0}},
{"_id":"Toby","rates":{"Superman Returns":4.0,"You Me and Dupree":1.0,"Snakes on a Plane":4.5}},
{"_id":"Claudia Puig","rates":{"The Night Listener":4.5,"Superman Returns":4.0,"You Me and Dupree":2.5,"Snakes on a Plane":3.5,"Just My Luck":3.0}},
{"_id":"Lisa Rose","rates":{"The Night Listener":3.0,"Superman Returns":3.5,"Lady in the Water":2.5,"You Me and Dupree":2.5,"Snakes on a Plane":3.5,"Just My Luck":3.0}},
{"_id":"Michael Phillips","rates":{"The Night Listener":4.0,"Superman Returns":3.5,"Lady in the Water":2.5,"Snakes on a Plane":3.0}}]}

さて、ここからが問題。そもそもMapReduceでユークリッド平方距離を求めるっていうけど、この場合、?key=[Name1, Name2] ってクエリにしたいんだと思うが。そのためには、map時にemit([Name1,Name2], [rates1, rate2]) をしなければ
ならない、ってことで不可能。

そもそも、ABの関係を求めるってこと自体がreduce操作なのでどうしようもない、という話に。。初回からこんなのじゃ、つまらないのでもう少し考える。

発想を切り替えて、?key=映画の名前で、その映画の評価に対する全員の距離がわかるようにしようか。map関数はこんな感じ。

function(doc) {
  for(var title in doc.rates){
    var name = doc._id;
    emit([title], {name : name, rate : doc.rates[title]})
  }
}

で、reduce で {name : 名前, rate: 評価値} のNリストを使ってすべての組の距離を求めればいいわけです。rereduceを考えなければ

function(keys, values, rereduce){
  if(rereduce){
    // ここはめんどくさい
    return values;
  }
  else{
    var comb = new Array();
    for(var i in values){
      var name1 = values[i].name;
      var rate1 = values[i].rate;
      for(var j in values){
        if( i != j ){
          var name2 = values[j].name;
          var rate2 = values[j].rate;
          var distance = (rate2 - rate1) * (rate2 - rate1);
          if( name1 <= name2 ){
             comb.push([name1, name2, distance]);
          }
          else{
             comb.push([name2, name1, distance]);
          }
        }
      }
    }
    return comb;
  }
}

とすると、key="Just My Luck"&group=true でビューを呼び出したときに、

[["Lisa Rose", "Mick LaSalle", 1], ["Gene Seymour", "Mick LaSalle", 0.25], ["Claudia Puig", "Mick LaSalle", 1], ["Lisa Rose", "Mick LaSalle", 1], ["Gene Seymour", "Lisa Rose", 2.25], ["Claudia Puig", "Lisa Rose", 0], ["Gene Seymour", "Mick LaSalle", 0.25], ["Gene Seymour", "Lisa Rose", 2.25], ["Claudia Puig", "Gene Seymour", 2.25], ["Claudia Puig", "Mick LaSalle", 1], ["Claudia Puig", "Lisa Rose", 0], ["Claudia Puig", "Gene Seymour", 2.25]]

の結果が得られるので、例えば先頭要素をみれば、Lisa Rose と Mick LaSalle の "Just My Luck" を評価軸としたときの距離は1ということが分かります。rereduceをちゃんと書いていないので、重複するエントリがあったりしますけれど。

ただ、このやり方だと、全部の組み合わせを計算するのでN人の評価者がいたときには、O(N^2)になりますから、論外です。CouchDB終了(笑。

という具合に難しいデータベースですが、こういう問題を解こうとすれば、reduceした状態、つまり関係ありそうなものは、まとめてドキュメントにしておくと幾分か楽になります。

{ "docs" : [
{"_id":"Jack Matthews","rates":{"The Night Listener":3.0,"Superman Returns":5.0,"Lady in the Water":3.0,"You Me and Dupree":3.5,"Snakes on a Plane":4.0}},
...

じゃなくて、タイトルを_idにして、それぞれの人の評価値を記入していく方式。

{ "docs" : [
{"_id":"The Night Listener","rates":{"Jack Matthews":3.0, ... },
...

まぁ、この場合は、人気のある映画ほど文書更新の競合が発生しやすくなる、っていう弊害がありますが。