MapReduce風の手順でレコメンドエンジンを作る

先日、ちょっと気分転換がしたかったので、
前々から試そうとしていた、レコメンドエンジンの実装に挑戦してみました

一応仕事の時間なので、会社的に意味があるものを・・・ということで、
蓄積されたままたいして活用されていなかった、
アクセスログを解析して何か・・・と思ったのです

ただ、そのまま作っても意味がないので、
後々MapReduceに適用できるように、
意図的に処理をMapReduce風に書いてみました

結果的に予想以上の代物ができあがってしまい、
私自身びっくりしたわけですが、今回はその手順をメモ...φ(･ω･｀)

なお、細かい理屈はこの辺でnaoya氏が解説してますので、
ぜひ確認してみてください

WEB+DB PRESS Vol.57

作者: 今村謙之,遠藤正仁,浜本階生,uupaa,増井俊之,大沢和宏,伊藤直也,村瀬大輔,塙与志夫,中島拓,中島聡,角田直行,cho45,はまちや2,新里祐教,塚田翔也,ミック,関治之,れさく,加藤幹生,原悠,WEB+DB PRESS編集部
出版社/メーカー: 技術評論社
発売日: 2010/06/24
メディア: 大型本
購入: 4人クリック: 206回
この商品を含むブログ (32件) を見る

WEB+DB PRESS Vol.58

作者: 松田明,大竹智也,はまちや2,外村和仁,横野巧也,島田慶樹,増井俊之,ミック,和田裕介,伊藤直也,塙与志夫,大沢和宏,原悠,浜本階生,uupaa,矢野りん,中島聡,中島拓,角田直行,WEB+DB PRESS編集部
出版社/メーカー: 技術評論社
発売日: 2010/08/24
メディア: 大型本
購入: 29人クリック: 354回
この商品を含むブログ (39件) を見る

直接関係ないですが、Vol.58はRails3の解説が絶品です(｀･ω･´) ｂ

対象になるデータ

ユーザ識別情報（以下ユーザID）と、アクセスしたページが含まれるログ
ページには「お店」と「商品詳細」があり、「お店」には「商品」が並んでいる
- 某R天を想像してもらえば・・・
データサイズは全部で400〜500M程度
- ただし、画像等へのアクセスを含む

手順

各手順ごとに意図的に実行コードを分けました
1つにまとめることは当然可能ですが、
MapReduce風に書くことが目的だからです

なお、会社の機密情報を含むため、
実際のコードについては大雑把にしか書けません
ごめんなさい(ﾉ´･ω･)ﾉﾐ(m´_ _)m

STEP1：ログのフィルタリング

入力：アクセスログ
出力：ページへのアクセスのみになったログ

ここではかなりゆるい正規表現で、
「お店」と「商品」にアクセスしたログだけ抜き出します
こうすることで、次の処理の時間を短縮できます

STEP2：ユーザIDとページ名の抜き出し

入力：アクセスページログ
出力：[ユーザID, ページ名]

ログから正規表現を使い、「ユーザID」と「ページ名」だけを出力します
MapReduceを使う場合、Shuffleのフェーズでソートがかかりますが、
今回は面倒なのでそのままで

STEP3：ページのアクセス回数をまとめる

入力：[ユーザID, ページ名]
出力：[ユーザID, <ページ名, アクセス回数>]

ユーザIDごとに、アクセスしたページを数え上げます
コードで書くとこんな感じに(´･ω･)っ

buf = Hash.new{|h, k| h[k] = Hash.new(0)}
data.each do |id, page|
  buf[id][page] += 1
end

処理自体は非常に簡単ですが、
これにより、ユーザのアクセス傾向が「ベクトル化」できたことになります

STEP4：ユーザごとのアクセスページ総数を数える

入力：[ユーザID, ページ名]
出力：[ユーザID, アクセス数]

ベクトルのサイズを揃えるため、言い換えると、
ユーザごとに「個別のアクセス数/全体のアクセス数」を計算するため、
ユーザがそもそも何回アクセスしたか、を計算します

buf = Hash.new(0)
data.each do |id, page|
  buf[id] += 1
end

STEP5：ユーザアクセス情報ベクトルサイズを揃える

入力：[ユーザID, <ページ名, アクセス数>], [ユーザID, 全アクセス数]
出力：[ユーザID, <ページ名, アクセス数/全アクセス数>] => Index:User

実はここをMapReduceでどう書いていいのかわからないのですが・・・
ユーザ＆ページごとに「アクセス数/全アクセス数」を計算します
（実際のコードではSTEP4と5は一緒にやっちゃいました）

すると、例えば「user, {page_a => 0.7, page_b => 0.3}」のように、
「ページについて全部足すと1」というデータができます

どうしてこうするかというと、
アクセスページの「重み」を統一するためです

「Aに1回、Bに2回」アクセスしたユーザと、
「A〜Jに1回ずつ」アクセスしたユーザでは、「Aに対する重み」が違います
前者にとってのAは全体の1/3ですが、後者では全体の1/10でしかありません

また、1ページしか見てないユーザがいれば、
100ページ見たユーザもいるわけで、これらの「重み」を統一したいわけです

これで一つIndexができました

STEP6：ページごとに入れ替える

入力：Index:User => [ユーザID, <ページ名, 重み>]
出力：[ページ名, <ユーザID, 重み>] => Index:Page

今度はSTEP5で生成したIndexを分解し、ページ名をキーにして並べ替えます
ここは入れ替えてページごとに入れ替えるだけなので、
MapReduceだと簡単なのですが、今回は自力でやらないといけません

buf = Hash.new{|h, k| h[k] = {}}
data.each do |id, h| # hはkeyがページ名、valueが重み
  h.each do |k, v|
    buf[k][id] = v
  end
end

とはいえ、コードは非常に単純ですね(｀･ω･´) ｂ
これでもう一つのIndexができました

STEP7：レコメンドを実行

今回はメモリにIndexをハッシュとして展開し、それを元に処理しました

2つのIndexを読み込み
ページ名を1つ以上入力
入力されたページ名を<ページ名, 重み>に変換
ページごとにIndex:PageからPageにアクセスしたユーザを抜き出す
Index:Pageから抜き出したユーザごとに以下を処理
1. Index:Userから<ページ, 重み>を抜き出す
2. 入力されたベクトルと、IndexのベクトルのSimilarity（ベクトルの近さ）を計算
3. 各ページについて、入力ベクトルのそのページ対する重み * Indexの重み * Similarityを計算
ユーザごとに算出したページへの値を全部加算
値の大きい順にページをソート
入力ベクトルに含まれるページ以外を返す
必要なら「お店」「商品」でフィルタリング

たぶん、コードで見た方が早いですね(´･ω･`)

def create_vector(list)
  return unless list

  h = Hash.new(0)
  list.each do |page|
    h[page] += 1
  end

  all = {}
  size = list.size.to_f
  h.each do |page, count|
    all[page] = count.to_f / size
  end
  all
end

def similarity(base, target)
  return 0.0 if base.empty? || target.empty?
  matrix(base, target) / (abs(base) * abs(target))
end

def matrix(base, target)
  ret = 0.0
  base.each do |key, val|
    next unless target[key]
    ret += val.to_f * target[key].to_f
  end
  ret
end

def abs(vec)
  ret = 0.0
  vec.values.each do |v|
    ret += v.to_f * v.to_f
  end
  ret
end

def recommend(list, page_hash, user_hash)
  vec = create_vector(list)
  return [] unless vec

  pages = Hash.new(0)
  vec.each do |page, ratio|
    # pageに属するユーザを抽出
    users = page_hash[page].keys
    next if users.empty?

    users.each do |u|
      user_vec = user_hash[u]
      next if user_vec.empty?

      # userとのsimilarity計算
      sim = similarity(vec, user_vec)

      # pageごとにuser.ratio * similarity * vec.ratioを算出して加算
      user_vec.each do |_h, _r|
        pages[_h] += _r.to_f * sim * ratio.to_f
      end
    end
  end

  ret = []
  pages.each do |page, val|
    # すでに見たのは除外
    next if vec.has_key?(page)
    # 残りを推薦
    ret << [page, val.round(4)]
  end

  ret.sort_by{|d| -d.last}
end

recommendがレコメンドの計算処理、
similarityは「ベクトルの類似度=内積/各サイズの積」を計算しています
たったこれだけの計算量で、かなりの精度で「おすすめ」が返ってくるのです

全体の実装は数時間でできましたし、
最終的に結果を返す部分も（初期化の時間を除けば）一瞬でした
まさかここまでとは・・・Σ(ﾟДﾟ；≡；ﾟдﾟ)

これが意味するもの

エンジンに「ユーザがアクセスしたページ履歴」を渡せば、
そのユーザにお勧めすべきページが出てくるのはすぐわかります

他にも、「あるお店のページ」から「お店のリスト」を取り出すと、
「そのお店を見ているユーザが他に見ているお店」、
つまり、「競合店」がわかることになります

同じように、「あるお店のページ」から「商品のリスト」を取り出すと、
「そのお店を見ているユーザが他に見ている商品」、
つまり、「そのお店にどの商品を期待しているか」が見えてきます

もちろん、商品ページを渡して商品ページを取り出せば、
商品同士の類似性、つまり、Amazon風のおすすめも出てくることになります

このように、データ解析ロジックは非常に単純なのですが、
得られる結果がとんでもなく有用であることがおわかりかと(((((( ;ﾟДﾟ)))))

重要なのは、「ユーザの行動パターンが似ているか」を機械的に計算しただけで、
作った側が何の推測もしていないってことです

最初の意図としては「ユーザへのおすすめ」のつもりだったのが、
与えるデータと出力を改めて考えると、
もっと重要な意味に気づいた・・・ってことですね

これはたぶん、Googleの日本語入力ソフトと同じことかと
言葉のつながりを機械的に計算した結果、
日本語入力辞書的なものができてしまったってことですね

逆に、機械的な計算が人間の推測を超えたデータを返してくるけども、
最終的に「意味」を与えないと、何の意味もないってことです(´･ω･`)
結局、最後に必要なのは人間の「知恵」です

NoSQL系技術との関連

もう一つ、これを作ったことでわかったのは、NoSQLブームとの絡みです

以前はデータの格納場所はRDBS程度しかなく、
あらゆるデータを無理矢理RDB形式に変換して格納していました

もし、今回のIndexをRDBに格納しようとしたら、
テーブルがかなり複雑なことになるでしょう

しかし、NoSQL系のストレージを使えば、
構造を「そのまま」格納することができるため、
データを変換するロスがなくなり、RDBSとは桁違いに高速化されるはずです

（今回はデータ量が少ないので、開発機のメモリに展開できましたが、
　実サービスではNoSQL系のサーバにIndexを格納し、
　エンジンをAPI化して呼び出す形になるはずです）

ということは、NoSQL系を使う理由の一つとして、
「データの変換ロスを減らす」ということがあることになります
そう考えれば、これだけ多くの微妙に違うNoSQL系が存在する理由がわかります

つまり、今までは「RDBに格納するためにデータを変換」していたわけですが、
「データ形式にあった格納技術」を選んでいく時代になったってことですかね・・・

ぱろっと・すたじお

技術メモなどをまったりと / my site : http://parrot-studio.com/