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

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

1. レコメンドにおける 類似度度計算 その傾向と対策 DSIRNLP #4 2013.9.1 at VOYAGE GROUP KOMIYA Atsushi ( @komiya_atsushi )
2. Agenda 1.  ⾃自⼰己紹介 2.  イントロダクション 3.  類似度度を計算するその⽅方法 4.  計算⽅方法の⽐比較（傾向と対策） 5.  まとめ 2
3. 1. ⾃自⼰己紹介 3
4. KOMIYA Atsushi @komiya_atsushi 4
5. 分析⼒力力をコアとする マーケティングソリューションカンパニー レコメンデーション／機械学習的な エンジニア 5
6. 分析⼒力力をコアとする マーケティングソリューションカンパニー レコメンデーション／機械学習的な エンジニア 6 データアナリスト・ エンジニア募集中！
7. #TokyoWebmining 事務局 分析、機械学習、分散処理理、アドテク等 お話していただける講師を募集中デス！ 7
8. #TokyoWebmining 事務局 分析、機械学習、分散処理理、アドテク等 お話していただける講師を募集中デス！ 8 次回は  9/21(⼟土)予定！
9. 2. イントロダクション 9
10. 今⽇日お話する内容（おことわり） • アイテムベース・レコメンデーションを 実現するために必要な  類似度度計算  を、 いかにして時間・空間的に効率率率よく実現 するかをお話します • 特に、EC  サイトなどの閲覧／購買ログ を⽤用いたレコメンデーションを想定して います • 類似度度の精度度などの話はしません 10
11. レコメンデーション 11
12. レコメンデーション 12
13. レコメンデーション サービスを利利⽤用している ユーザに対して、 何らかの価値ある情報を 提供すること 13
14. レコメンデーション サービスを利利⽤用している ユーザに対して、 何らかの価値ある情報を 提供すること アイテム 14
15. ⽔水彩の森 アイテムベース・レコメンデーション ユーザ すごく 似てる 似て ない 似てる 郷の恵み 天然⽔水 ⾃自然湧⽔水 ⽊木曽 ⾃自然湧⽔水 岐⾩阜・養⽼老老 (アイテム) 商品を観た 似ている商品を 探索索する 「お探しの品はこちら？」 「こちらの品はいかが？」 15
16. ⽔水彩の森 アイテムベース・レコメンデーション ユーザ すごく 似てる 似て ない 似てる 郷の恵み 天然⽔水 ⾃自然湧⽔水 ⽊木曽 ⾃自然湧⽔水 岐⾩阜・養⽼老老 (アイテム) 商品を観た 似ている商品を 探索索する 「お探しの品はこちら？」 「こちらの品はいかが？」 パーソナライズは問わない アイテムの属性情報や 各ユーザの⾏行行動ログを基に 似ているアイテムを 探し出して提供する 16
17. ⽔水彩の森 アイテムベース・レコメンデーション ユーザ すごく 似てる 似て ない 似てる 郷の恵み 天然⽔水 ⾃自然湧⽔水 ⽊木曽 ⾃自然湧⽔水 岐⾩阜・養⽼老老 (アイテム) 商品を観た 似ている商品を 探索索する 「お探しの品はこちら？」 「こちらの品はいかが？」 パーソナライズは問わない アイテムの属性情報や 各ユーザの⾏行行動ログを基に 似ているアイテムを 探し出して提供する 近傍探索索 17
18. k-近傍探索索  (k-Nearest neighbor) x y ⼀一⽅方で、⾚赤い点から ⾒見見て⼀一番近いのは この⻘青い点 ⻩黄⾊色い点から ⾒見見て⼀一番近いのは この⾚赤い点 2  次元平⾯面を例例に説明 18
19. 2  次元平⾯面を例例に説明 k-近傍探索索  (k-Nearest neighbor) x y ⼀一⽅方で、⾚赤い点から ⾒見見て⼀一番近いのは この⻘青い点 ⻩黄⾊色い点から ⾒見見て⼀一番近いのは この⾚赤い点 アイテムを特徴ベクトルで表現し ベクトル間の類似度度を計算して よく似ているアイテムを探し出す 2 次元平⾯面上の点  →  2 次元のベクトル 19
20. アイテムの特徴ベクトルを構成する要素 ジャンル 価格 採取地 内容量量 閲覧した カートに⼊入れた 購⼊入した レビューした アイテムの属性情報 アイテムに対する 各ユーザの⾏行行動ログ ⾃自然湧⽔水 岐⾩阜・養⽼老老 低次元＆密な ベクトル ⾼高次元＆ スパースな ベクトル 数値化 20
21. アイテムの購買を表す特徴ベクトル ⾃自然湧⽔水 岐⾩阜・養⽼老老 購⼊入 購⼊入 ⾃自然湧⽔水 ⽊木曽 購⼊入 購⼊入 購⼊入 郷の恵み 天然⽔水 購⼊入 購⼊入 購⼊入 ⽔水彩の森 購⼊入 購⼊入 購⼊入 21
22. アイテムの購買を表す特徴ベクトル ⾃自然湧⽔水 岐⾩阜・養⽼老老 購⼊入 購⼊入 ⾃自然湧⽔水 ⽊木曽 購⼊入 購⼊入 購⼊入 郷の恵み 天然⽔水 購⼊入 購⼊入 購⼊入 ⽔水彩の森 購⼊入 購⼊入 購⼊入 購⼊入  →  1 ⾮非購⼊入  →  0 として数値化 22
23. アイテムの購買を表す特徴ベクトル ⾃自然湧⽔水 岐⾩阜・養⽼老老 購⼊入 購⼊入 ⾃自然湧⽔水 ⽊木曽 購⼊入 購⼊入 購⼊入 郷の恵み 天然⽔水 購⼊入 購⼊入 購⼊入 ⽔水彩の森 購⼊入 購⼊入 購⼊入 ⾃自然湧⽔水 岐⾩阜・養⽼老老 1 0 1 0 0 ⾃自然湧⽔水 ⽊木曽 0 1 1 0 1 郷の恵み 天然⽔水 1 0 0 1 1 ⽔水彩の森 0 1 1 1 0 23
24. アイテムの購買を表す特徴ベクトル ⾃自然湧⽔水 岐⾩阜・養⽼老老 1 0 1 0 0 ⾃自然湧⽔水 ⽊木曽 0 1 1 0 1 郷の恵み 天然⽔水 1 0 0 1 1 ⽔水彩の森 0 1 1 1 0 「郷の恵み」の 特徴ベクトル 24
25. 特徴ベクトルの表現⽅方法 • 単純に配列列で表現する • スパースなデータに対して空間効率率率が悪い • インデックスと値の対で表現する • データが密だと効率率率が悪化する 1 [0] 0 [1] 0 [2] 0 [3] 1 [4] 0 [5] 0 [6] 1 [7] [[0,  1],  [4,  1],  [7,  1]] 25
26. 特徴ベクトルの表現⽅方法 • 単純に配列列で表現する • スパースなデータに対して空間効率率率が悪い • インデックスと値の対で表現する • データが密だと効率率率が悪化する 1 [0] 0 [1] 0 [2] 0 [3] 1 [4] 0 [5] 0 [6] 1 [7] [[0,  1],  [4,  1],  [7,  1]] 26
27. 特徴ベクトル同⼠士の類似度度計算 • 特徴ベクトル同⼠士がどれだけ似ているの かを数値的に表す • Jaccard 係数 • 積集合の⼤大きさ  / 和集合の⼤大きさ • Cosine 類似度度 • 「ベクトル同⼠士のなす⾓角の⼤大きさ」 27
28. 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
29. イントロダクション：まとめ • レコメンデーション • アイテムベース・レコメンデーション • k-近傍探索索 • 似ているアイテムを探しだす • 特徴ベクトル • アイテムに関連する要素（属性、購買ログ） で構成する • 類似度度計算 • 特徴ベクトルを利利⽤用して計算する 29
30. 3. 類似度度を計算する その⽅方法 30
31. 類似度度の計算 • 類似度度計算は⽐比較的重いタスク • 実装次第では、とても時間がかかることに • 定義 • N : アイテム数 • D : 特徴ベクトルの次数 •  購買ログを基にした特徴ベクトルであればユー ザ数に相当 31
32. 類似度度の計算（時間計算量量） 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
33. いろいろあるよ  類似度度計算の⽅方法 a.  ナイーブな⽅方法 b.  マージアルゴリズム的にベクトルを ⾛走査する c.  転置インデックスを利利⽤用する d.  バスケット分析的に処理理する e.  おまけ：b-bit min-wise hashing 33
34. a.  ナイーブな⽅方法 b.  マージアルゴリズム的にベクトルを ⾛走査する c.  転置インデックスを利利⽤用する d.  バスケット分析的に処理理する e.  おまけ：b-bit min-wise hashing いろいろあるよ  類似度度計算の⽅方法 Jaccard 係数のお話が主題に なりますが、基本的な考え⽅方は   Cosine 類似度度の計算にも適⽤用 できます 34
35. a. ナイーブな⽅方法 • 特徴ベクトルを配列列で表現＆１組ずつ 愚直に類似度度計算する ‘1’ の共起回数。 これが求まれば  Jaccard 係数を算出することができる 35
36. a. ナイーブな⽅方法 • Jaccard  係数の計算に限定するならば、 特徴ベクトルは「ビットベクトル」で表 現できる • 「ビット  AND」と「popcount」で効率率率よ く共起回数を算出することができる 36
37. a. ナイーブな⽅方法 • 利利点 • 実装がとっても楽＆理理解しやすい • 特徴ベクトルの更更新が容易易なデータ構造 • ⽋欠点 • お察しできるとおりの時間・空間効率率率の悪さ • 計算量量 • 時間計算量量 •  すべての組み合わせ：O(DN^2) • 空間計算量量 •  O(DN^2) 37
38. b. マージアルゴリズム的にベクトルを⾛走査する • 特徴ベクトルをインデックスと値の対で 表現し、ベクトル⾛走査を⼯工夫する [0] [1] [2] [3] [4] [5] [6] 0 0 0 0 0 1 1 1 [7] 0 0 0 0 0 0 1 1 v1 v2 インデックスの⼩小さい⽅方を進める 共起回数  +1 38
39. b. マージアルゴリズム的にベクトルを⾛走査する • 利利点 • 空間効率率率がとってもよい • ナイーブな実装よりは効率率率よく計算できる •  スパースな場合は特に効率率率がよい • ⽋欠点 • 特徴ベクトルの更更新に弱いデータ構造 • 密なデータの場合はナイーブな⽅方法よりも時 間効率率率が悪化する •  最悪時間計算量量は  O(DN^2)  だが、さまざまなオー バーヘッドが⽣生じる 39
40. c. 転置インデックスを利利⽤用する   • Amazon.com  のレコメンデーションに ついて書かれた論論⽂文  (2003年年) に掲載さ れている⽅方法 • 要約すると… • 転置インデックスを作りましょう • ある1つのアイテムと他のすべてのアイテ ムとの類似度度を、⼀一括して計算しましょう 40
41. c. 転置インデックスを利利⽤用する   • 転置インデックス ⽔水彩の森 郷の恵み 天然⽔水 ⾃自然湧⽔水 ⽊木曽 ⾃自然湧⽔水 岐⾩阜・養⽼老老 +2 +1 +1 ある商品を 買った⼈人が 他にどんな 商品を買って いるか 共起回数 41
42. c. 転置インデックスを利利⽤用する   • 利利点 • とっても効率率率よく類似度度計算することができる • 特徴ベクトルの更更新が容易易なデータ構造 • あるアイテムに対して⼀一括しての類似度度計算ができ るため、オンラインでのレコメンデーション実現に 向いている • ⽋欠点 • 「転置インデックス」を実現するために 空間計算量量は⼤大きくなりがち •  データの密度度（購買ログの量量）に⽐比例例する •  ⼆二次記憶装置（HDD）上に構築するなどの⼯工夫が必要 となる 42
43. d. バスケット分析的に処理理する • 「アイテムの特徴ベクトル」という考え ⽅方ではなく「アイテムが扱われた単位」 に着⽬目する • EC サイトであれば「ユーザ」「カート・ バスケット」「セッション」などがその単 位にあたる 43
44. d. バスケット分析的に処理理する ⾃自然湧⽔水 岐⾩阜・養⽼老老 1 0 1 ⾃自然湧⽔水 ⽊木曽 0 1 1 郷の恵み 天然⽔水 1 0 0 ⽔水彩の森 0 1 1 岐⾩阜 養⽼老老 ⽊木曽 郷の 恵み ⽔水彩 の森 岐⾩阜 養⽼老老 ⽊木曽 郷の 恵み ⽔水彩 の森 共起回数 この⾚赤枠内での 共起回数を求める 44
45. d. バスケット分析的に処理理する ⾃自然湧⽔水 岐⾩阜・養⽼老老 1 0 1 ⾃自然湧⽔水 ⽊木曽 0 1 1 郷の恵み 天然⽔水 1 0 0 ⽔水彩の森 0 1 1 岐⾩阜 養⽼老老 ⽊木曽 郷の 恵み ⽔水彩 の森 岐⾩阜 養⽼老老 1 1 ⽊木曽 郷の 恵み 1 1 ⽔水彩 の森 共起回数 45
46. 岐⾩阜 養⽼老老 ⽊木曽 郷の 恵み ⽔水彩 の森 岐⾩阜 養⽼老老 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
47. 岐⾩阜 養⽼老老 ⽊木曽 郷の 恵み ⽔水彩 の森 岐⾩阜 養⽼老老 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
48. 岐⾩阜 養⽼老老 ⽊木曽 郷の 恵み ⽔水彩 の森 岐⾩阜 養⽼老老 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
49. d. バスケット分析的に処理理する • 利利点 • とっても効率率率よく類似度度計算することができる • ⼀一括してすべてのアイテムの組み合わせの類似度度計 算ができるため、オフラインでの（事前計算され た）レコメンデーションに向いている • ⽋欠点 • 特徴ベクトルが更更新されると、全計算し直しとなる • メインメモリ上に  O(N^2) の空間計算量量が必要にな るため、アイテム数が⾮非常に多い場合に処理理が難し くなる 49
50. e. おまけ：b-bit min-wise hashing • 「厳密な  Jaccard  係数の値なんて知る 必要はないんだよ、だいたいの値が把握 できればいいんだよ！」 • というときに使うとよい⼿手法 • 特徴ベクトルを数⼗十  bit 〜～  のコンパク トな表現に変換する • コンパクトに表現された特徴ベクトルか ら、Jaccard 係数の近似値を算出するこ とができる 50
51. e. おまけ：b-bit min-wise hashing • 詳細はこちらを御覧ください… • http://research.preferred.jp/2011/02/minhash/ 51
52. 各種⼿手法の類似度度計算単位    早⾒見見表 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
53. 4.  計算⽅方法の⽐比較 （傾向と対策） 53
54. 具体的な性能差はいかほどか？ • MovieLens 10M を利利⽤用して性能測定 • アイテム数：10,677 • ユーザ数：69,878 • レビュー数：10,000,054 • 密度度：1.34% (レビュー数  / (アイテム数  * ユーザ数)) • アイテム数やユーザ数、レビュー数を変化させてみる • 測定対象の処理理 • レビューデータのファイルを読み込み、メモリ上にそ れぞれの⼿手法に適したデータ構造を構築する • すべてのアイテムに対して、他のすべてのアイテムと の  Jaccard  係数を算出する 54
55. アイテム数が処理理時間に与える影響 アイテム数 ユーザ数 レビュー数 密度度 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
56. アイテム数が処理理時間に与える影響 56
57. ユーザ数が処理理時間に与える影響 ユーザ数 アイテム数 レビュー数 密度度 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
58. ユーザ数が処理理時間に与える影響 58
59. レビュー数  （密度度）が処理理時間に与える影響 レビュー数 アイテム数 ユーザ数 密度度 500,000 9,155 63,536 0.09% 1,000,000 9,833 68,502 0.15% 5,000,000 10,568 69,878 0.68% 10,000,054 10,677 69,878 1.34% 59
60. レビュー数  （密度度）が処理理時間に与える影響 60
61. 結論論（1/2） • 転置インデックス＆バスケット分析的な⽅方法 • ⼀一番安定した性能を出してくれる • アイテム数／ユーザ数／レビュー数にあまり左右 されない • ナイーブな⽅方法 • アイテム数／ユーザ数に性能が⼤大きく左右されて しまう • ただ、アイテム数／ユーザ数が⼩小さければ⼗十分な 性能が出る（ビット  AND / popcount  のおかげ） • ログの量量（密度度）にはあまり影響されない 61
62. 結論論（2/2） • マージアルゴリズム的な⽅方法 • アイテム数／ユーザ数に性能が⼤大きく左右 される • ログの量量（密度度）にも⼤大きく左右される • min-wise hashing • アイテム数に性能が左右される • ユーザ数(次数)やログの量量にはあまり影響されない • 遅い…  が、超⼤大規模／超⾼高次元なデータセット なら活躍できそう？ • そもそも僕の実装のせいでパフォーマンスが出て いないだけかもね… 62
63. アイテム数／特徴ベクトルの次数と 適切切な類似度度計算⽅方法のマッピング 特徴ベクトル の次数 （ユーザ数） ア イ テ ム 数 転置インデックス バスケット分析的 b-Bit min-wise hashing ナイーブな⽅方法 マージ アルゴリズム 63
64. 5. まとめ 64
65. まとめ • ⽬目的・状況に応じて適切切な⼿手段を選択 できるようになるといいですね！ • レコメンデーション精度度検証⽬目的のプロト タイプ作成なら、ナイーブな⽅方法もあり • システム化・⾃自動化が⽬目的なら転置イン デックス  or バスケット分析的な⽅方式で • オンラインでのレコメンデーションが求め られているなら、転置インデックス⽅方式で 65
66. ありがとう ございました！ 66
67. 分析⼒力力をコアとする マーケティングソリューションカンパニー 67 データアナリスト／エンジニア 募集中！ http://bit.ly/alb_recruit
68. 参考⽂文献 • 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