ぱろっと・すたじお

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

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

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


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


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


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


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

WEB+DB PRESS Vol.57

WEB+DB PRESS Vol.57


WEB+DB PRESS Vol.58

WEB+DB PRESS Vol.58

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

対象になるデータ

  • ユーザ識別情報(以下ユーザ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

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

STEP7:レコメンドを実行


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

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


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

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に格納するためにデータを変換」していたわけですが、
データ形式にあった格納技術」を選んでいく時代になったってことですかね・・・