Upgrade to Pro — share decks privately, control downloads, hide ads and more …

レコメンドにおける類似度計算その傾向と対策 #DSIRNLP 第4回 2013.9.1

KOMIYA Atsushi
September 01, 2013

レコメンドにおける類似度計算その傾向と対策 #DSIRNLP 第4回 2013.9.1

第4回 データ構造と情報検索と言語処理勉強会 #DSIRNLP
http://partake.in/events/76854228-ba38-4f6e-87b9-f79e30add75c での発表資料です。

KOMIYA Atsushi

September 01, 2013
Tweet

More Decks by KOMIYA Atsushi

Other Decks in Technology

Transcript

  1. ⽔水彩の森 アイテムベース・レコメンデーション ユーザ すごく 似てる 似て ない 似てる 郷の恵み 天然⽔水

    ⾃自然湧⽔水 ⽊木曽 ⾃自然湧⽔水 岐⾩阜・養⽼老老 (アイテム) 商品を観た 似ている商品を 探索索する 「お探しの品はこちら?」 「こちらの品はいかが?」 15
  2. ⽔水彩の森 アイテムベース・レコメンデーション ユーザ すごく 似てる 似て ない 似てる 郷の恵み 天然⽔水

    ⾃自然湧⽔水 ⽊木曽 ⾃自然湧⽔水 岐⾩阜・養⽼老老 (アイテム) 商品を観た 似ている商品を 探索索する 「お探しの品はこちら?」 「こちらの品はいかが?」 パーソナライズは問わない アイテムの属性情報や 各ユーザの⾏行行動ログを基に 似ているアイテムを 探し出して提供する 16
  3. ⽔水彩の森 アイテムベース・レコメンデーション ユーザ すごく 似てる 似て ない 似てる 郷の恵み 天然⽔水

    ⾃自然湧⽔水 ⽊木曽 ⾃自然湧⽔水 岐⾩阜・養⽼老老 (アイテム) 商品を観た 似ている商品を 探索索する 「お探しの品はこちら?」 「こちらの品はいかが?」 パーソナライズは問わない アイテムの属性情報や 各ユーザの⾏行行動ログを基に 似ているアイテムを 探し出して提供する 近傍探索索 17
  4. 2  次元平⾯面を例例に説明 k-近傍探索索  (k-Nearest neighbor) x y ⼀一⽅方で、⾚赤い点から ⾒見見て⼀一番近いのは この⻘青い点

    ⻩黄⾊色い点から ⾒見見て⼀一番近いのは この⾚赤い点 アイテムを特徴ベクトルで表現し ベクトル間の類似度度を計算して よく似ているアイテムを探し出す 2 次元平⾯面上の点  →  2 次元のベクトル 19
  5. アイテムの特徴ベクトルを構成する要素 ジャンル 価格 採取地 内容量量 閲覧した カートに⼊入れた 購⼊入した レビューした アイテムの属性情報

    アイテムに対する 各ユーザの⾏行行動ログ ⾃自然湧⽔水 岐⾩阜・養⽼老老 低次元&密な ベクトル ⾼高次元& スパースな ベクトル 数値化 20
  6. アイテムの購買を表す特徴ベクトル ⾃自然湧⽔水 岐⾩阜・養⽼老老 購⼊入 購⼊入 ⾃自然湧⽔水 ⽊木曽 購⼊入 購⼊入 購⼊入

    郷の恵み 天然⽔水 購⼊入 購⼊入 購⼊入 ⽔水彩の森 購⼊入 購⼊入 購⼊入 購⼊入  →  1 ⾮非購⼊入  →  0 として数値化 22
  7. アイテムの購買を表す特徴ベクトル ⾃自然湧⽔水 岐⾩阜・養⽼老老 購⼊入 購⼊入 ⾃自然湧⽔水 ⽊木曽 購⼊入 購⼊入 購⼊入

    郷の恵み 天然⽔水 購⼊入 購⼊入 購⼊入 ⽔水彩の森 購⼊入 購⼊入 購⼊入 ⾃自然湧⽔水 岐⾩阜・養⽼老老 1 0 1 0 0 ⾃自然湧⽔水 ⽊木曽 0 1 1 0 1 郷の恵み 天然⽔水 1 0 0 1 1 ⽔水彩の森 0 1 1 1 0 23
  8. アイテムの購買を表す特徴ベクトル ⾃自然湧⽔水 岐⾩阜・養⽼老老 1 0 1 0 0 ⾃自然湧⽔水 ⽊木曽

    0 1 1 0 1 郷の恵み 天然⽔水 1 0 0 1 1 ⽔水彩の森 0 1 1 1 0 「郷の恵み」の 特徴ベクトル 24
  9. Jaccard  係数の計算例例 ⾃自然湧⽔水 ⽊木曽 0 1 1 0 1 ⽔水彩の森

    0 1 1 1 0 積 (AND) 0 1 1 0 0 和 (OR) 0 1 1 1 1 |積集合| / |和集合| = 2 / 4 = 0.5 28
  10. 類似度度の計算(時間計算量量) i1 i2 i3 i4 i1 i2 i3 i4 i1

    i2 i3 i4 i1 i2 i3 i4 i1 i2 i3 i4 i1 i2 i3 i4 1組のアイテムの 類似度度計算 あるアイテムと その他すべての アイテムとの 類似度度計算 すべてのアイテム の全組み合わせの 類似度度計算 O(D) O(DN^2) O(DN) 32
  11. a.  ナイーブな⽅方法 b.  マージアルゴリズム的にベクトルを ⾛走査する c.  転置インデックスを利利⽤用する d.  バスケット分析的に処理理する e. 

    おまけ:b-bit min-wise hashing いろいろあるよ  類似度度計算の⽅方法 Jaccard 係数のお話が主題に なりますが、基本的な考え⽅方は   Cosine 類似度度の計算にも適⽤用 できます 34
  12. c. 転置インデックスを利利⽤用する   • Amazon.com  のレコメンデーションに ついて書かれた論論⽂文  (2003年年) に掲載さ れている⽅方法 • 要約すると…

    • 転置インデックスを作りましょう • ある1つのアイテムと他のすべてのアイテ ムとの類似度度を、⼀一括して計算しましょう 40
  13. c. 転置インデックスを利利⽤用する   • 転置インデックス ⽔水彩の森 郷の恵み 天然⽔水 ⾃自然湧⽔水 ⽊木曽 ⾃自然湧⽔水

    岐⾩阜・養⽼老老 +2 +1 +1 ある商品を 買った⼈人が 他にどんな 商品を買って いるか 共起回数 41
  14. c. 転置インデックスを利利⽤用する   • 利利点 • とっても効率率率よく類似度度計算することができる • 特徴ベクトルの更更新が容易易なデータ構造 • あるアイテムに対して⼀一括しての類似度度計算ができ るため、オンラインでのレコメンデーション実現に 向いている • ⽋欠点

    • 「転置インデックス」を実現するために 空間計算量量は⼤大きくなりがち •  データの密度度(購買ログの量量)に⽐比例例する •  ⼆二次記憶装置(HDD)上に構築するなどの⼯工夫が必要 となる 42
  15. d. バスケット分析的に処理理する ⾃自然湧⽔水 岐⾩阜・養⽼老老 1 0 1 ⾃自然湧⽔水 ⽊木曽 0

    1 1 郷の恵み 天然⽔水 1 0 0 ⽔水彩の森 0 1 1 岐⾩阜 養⽼老老 ⽊木曽 郷の 恵み ⽔水彩 の森 岐⾩阜 養⽼老老 ⽊木曽 郷の 恵み ⽔水彩 の森 共起回数 この⾚赤枠内での 共起回数を求める 44
  16. d. バスケット分析的に処理理する ⾃自然湧⽔水 岐⾩阜・養⽼老老 1 0 1 ⾃自然湧⽔水 ⽊木曽 0

    1 1 郷の恵み 天然⽔水 1 0 0 ⽔水彩の森 0 1 1 岐⾩阜 養⽼老老 ⽊木曽 郷の 恵み ⽔水彩 の森 岐⾩阜 養⽼老老 1 1 ⽊木曽 郷の 恵み 1 1 ⽔水彩 の森 共起回数 45
  17. 岐⾩阜 養⽼老老 ⽊木曽 郷の 恵み ⽔水彩 の森 岐⾩阜 養⽼老老 1

    1 ⽊木曽 郷の 恵み 1 1 ⽔水彩 の森 岐⾩阜 養⽼老老 ⽊木曽 郷の 恵み ⽔水彩 の森 岐⾩阜 養⽼老老 1 1 ⽊木曽 1 1 郷の 恵み 1 1 ⽔水彩 の森 1 1 d. バスケット分析的に処理理する ⾃自然湧⽔水 岐⾩阜・養⽼老老 1 0 1 ⾃自然湧⽔水 ⽊木曽 0 1 1 郷の恵み 天然⽔水 1 0 0 ⽔水彩の森 0 1 1 共起回数 46
  18. 岐⾩阜 養⽼老老 ⽊木曽 郷の 恵み ⽔水彩 の森 岐⾩阜 養⽼老老 1

    1 ⽊木曽 1 1 郷の 恵み 1 1 ⽔水彩 の森 1 1 岐⾩阜 養⽼老老 ⽊木曽 郷の 恵み ⽔水彩 の森 岐⾩阜 養⽼老老 2 1 1 1 ⽊木曽 1 2 2 郷の 恵み 1 1 ⽔水彩 の森 1 2 2 d. バスケット分析的に処理理する ⾃自然湧⽔水 岐⾩阜・養⽼老老 1 0 1 ⾃自然湧⽔水 ⽊木曽 0 1 1 郷の恵み 天然⽔水 1 0 0 ⽔水彩の森 0 1 1 共起回数 47
  19. 岐⾩阜 養⽼老老 ⽊木曽 郷の 恵み ⽔水彩 の森 岐⾩阜 養⽼老老 2

    1 1 1 ⽊木曽 1 2 2 郷の 恵み 1 1 ⽔水彩 の森 1 2 2 d. バスケット分析的に処理理する ⾃自然湧⽔水 岐⾩阜・養⽼老老 1 0 1 ⾃自然湧⽔水 ⽊木曽 0 1 1 郷の恵み 天然⽔水 1 0 0 ⽔水彩の森 0 1 1 共起回数 対⾓角成分は アイテムの出現回数 48
  20. e. おまけ:b-bit min-wise hashing • 「厳密な  Jaccard  係数の値なんて知る 必要はないんだよ、だいたいの値が把握 できればいいんだよ!」 • というときに使うとよい⼿手法

    • 特徴ベクトルを数⼗十  bit 〜~  のコンパク トな表現に変換する • コンパクトに表現された特徴ベクトルか ら、Jaccard 係数の近似値を算出するこ とができる 50
  21. 各種⼿手法の類似度度計算単位    早⾒見見表 i1 i2 i3 i4 i1 i2 i3

    i4 i1 i2 i3 i4 i1 i2 i3 i4 i1 i2 i3 i4 i1 i2 i3 i4 1組のアイテムの 類似度度計算 あるアイテムと その他すべての アイテムとの 類似度度計算 すべてのアイテム の全組み合わせの 類似度度計算 ナイーブな⽅方法 マージアルゴリズム min-wise hashing 転置インデックス バスケット分析的 52
  22. 具体的な性能差はいかほどか? • MovieLens 10M を利利⽤用して性能測定 • アイテム数:10,677 • ユーザ数:69,878 • レビュー数:10,000,054 • 密度度:1.34% (レビュー数  /

    (アイテム数  * ユーザ数)) • アイテム数やユーザ数、レビュー数を変化させてみる • 測定対象の処理理 • レビューデータのファイルを読み込み、メモリ上にそ れぞれの⼿手法に適したデータ構造を構築する • すべてのアイテムに対して、他のすべてのアイテムと の  Jaccard  係数を算出する 54
  23. アイテム数が処理理時間に与える影響 アイテム数 ユーザ数 レビュー数 密度度 1,000 67,959 834,676 1.23% 5,000

    69,878 4,750,285 1.36% 10,677 69,878 10,000,054 1.34% アイテム数を 変化させてみました 55
  24. ユーザ数が処理理時間に与える影響 ユーザ数 アイテム数 レビュー数 密度度 1,000 7,809 138,730 1.78% 5,000

    9,980 735,775 1.47% 10,000 9,956 1,431,231 1.44% 35,000 10,580 4,987,440 1.35% 69,878 10,677 10,000,054 1.34% 57
  25. アイテム数/特徴ベクトルの次数と 適切切な類似度度計算⽅方法のマッピング 特徴ベクトル の次数 (ユーザ数) ア イ テ ム 数

    転置インデックス バスケット分析的 b-Bit min-wise hashing ナイーブな⽅方法 マージ アルゴリズム 63
  26. 参考⽂文献 • WEB+DB PRESS vol.49 「速習  基本から⼤大規 模対応、精度度の追求へ  レコメンドエンジン」 • http://gihyo.jp/magazine/wdpress/archive/2009/ vol49

    • Amazon.com Recommendations Item-to- Item Collaborative Filtering • http://www.win.tue.nl/~laroyo/2L340/resources/ Amazon-Recommendations.pdf • b-Bit Minwise Hashing • http://research.microsoft.com/pubs/120078/ wfc0398-lips.pdf 68