![ミクシィでの Hadoop の利用（マイニング）
現在までに mixi に存在するデータをマイニングする実験を行っ
てきた．
事例：
ログデータをマイニング
検索クエリログから “もしかして検索” 用の辞書を抽出
行動履歴から mixi ニュース内の記事を推薦
グラフ分析
ユーザの重要性判定 PageRank [Brin and Page, 1998]
10](https://image.slidesharecdn.com/hadoop-conference-jp-2011-110927075455-phpapp02/85/Hadoop-conference-Japan-2011-10-320.jpg)
![類似インスタンスの抽出における問題点
問題点： ユーザ毎に他の全ユーザと類似性をチェックするの
では時間がかかりすぎる！
Locality Sensitive Hashing [Piotr and Rajeev, 1999] を
利用して高速に類似インスタンスを抽出する
20](https://image.slidesharecdn.com/hadoop-conference-jp-2011-110927075455-phpapp02/85/Hadoop-conference-Japan-2011-20-320.jpg)
![Locality Sensitive Hashing [Piotr and
Rajeev, 1999]
類似するインスタンスを抽出する技術
特徴
速い
精度はそれほどでもない
事例
Google News のレコメンデーション [Das et al., 2007]
21](https://image.slidesharecdn.com/hadoop-conference-jp-2011-110927075455-phpapp02/85/Hadoop-conference-Japan-2011-21-320.jpg)
![例：インスタンスベクトルの生成
商 商品名 ユーザ1の購買履歴：
品 iPad, IntelliJ, うまい棒
ID
1 iPad
商品IDを次元とする
2 IntelliJ
ベクトルを作る
3 うまい棒
4 ヘルシオ ユーザ１のインスタンスベクトル：
… … [1 1 1 0 0 0 0 0]
ユーザ１が商品１を一つ購
入したことを表す
23](https://image.slidesharecdn.com/hadoop-conference-jp-2011-110927075455-phpapp02/85/Hadoop-conference-Japan-2011-23-320.jpg)
![イメージ：関数の適用
入力（インスタンスベクトル） 出力（関数値）
ユーザ１ [1 1 1 0 0 0 0 0] 950494
ユーザ2 [0 0 0 1 1 0 0 0] 48308
関数を適用
ユーザ３ [0 0 0 0 0 1 1 0] 848490
ユーザ４ [0 1 1 0 0 0 0 1] 950494
24](https://image.slidesharecdn.com/hadoop-conference-jp-2011-110927075455-phpapp02/85/Hadoop-conference-Japan-2011-24-320.jpg)
Hadoop conference Japan 2011
- 1. ミクシィにおける Ｈａｄｏｏｐ の利用 伊藤 敬彦 1
- 2. mixi? 日本で最大規模のソーシャル ネットワークサービス. いくつものサービスを展開. つぶやき，写真，日記，ア プリ等 月間アクティブユーザ数： 約１５００万人 2
- 4. アジェンダ ミクシィにおける Ｈａｄｏｏｐ の利用 サーバ構成 適用分野 Locality Sensitive Hashing (LSH) を利用した推薦 推薦を行うために必要なこと LSH を利用した推薦（レコメンド） Hadoop 上で動作する LSH の壱実装 （Likelike） 実験 4
- 5. アジェンダ ミクシィにおける Ｈａｄｏｏｐ の利用 サーバ構成 適用分野 Locality Sensitive Hashing (LSH) を利用した推薦 推薦を行うために必要なこと LSH を利用した推薦（レコメンド） Hadoop 上で動作する LSH の壱実装 （Likelike） 実験 5
- 6. Hadoop のサーバ構成 社内には幾つかの Hadoop クラスタがある データノードの数はそれぞれ ４～５個 CDH 3，Hadoop 0.21，Hadoop 0.20 今のところそれほどチューニングはしていない 6
- 7. 利用している機器 高価でない（コモデティ）機器を利用 CPU： Xeon E5630 @ 2.53GHz(Xeon X5650 @ 2.67GHz) メモリ量：16GB (32GB) OS： CentOS 5.5 HDサイズと一台あたりのHDの個数： 1TB HD を 1計算機あ たり6台 RAID： なし 7
- 8. ミクシィでの Hadoop の利用（データの集約） 大規模データをHDFSに集約 ログデータ ? ログを保存しておくサーバを別途用意し，日ごとに HDFS へコピーしている ? 行動履歴： Apache ログ等 DB コンテンツ： プロフィール，マイミクグラフ等 ? DBに負荷をかけることなくデータ解析を行える． 8
- 9. ミクシィでの Hadoop の利用（解析） 集約されたデータを Java プログラム (MapReduce) で解析 Hive も導入し，より簡便にデータの解析を行っている． 例： ミクシィページの PV集計 など 9
- 10. ミクシィでの Hadoop の利用（マイニング） 現在までに mixi に存在するデータをマイニングする実験を行っ てきた． 事例： ログデータをマイニング 検索クエリログから “もしかして検索” 用の辞書を抽出 行動履歴から mixi ニュース内の記事を推薦 グラフ分析 ユーザの重要性判定 PageRank [Brin and Page, 1998] 10
- 11. アジェンダ Ｈａｄｏｏｐ の利用分野 統計算出 マイニング Locality Sensitive Hashing (LSH) を利用した推薦 推薦を行うために必要なこと LSH を利用した推薦（レコメンド） Hadoop 上で動作する LSH の壱実装 （Likelike） 実験 11
- 12. 準備 mixi には推薦機能を付加できるサービスがある. ニュース，チェック，レビュー 等 現在これらのサービスに“推薦”機能を付加するための予備 実験を行っている． 12
- 14. 推薦を行うには 類似インスタンス集合を抽出することで実現できる． ここでインスタンスは扱うデータ集合中の一つの要素を表 す 例 （インスタンス） ? 文書集合： 文書 ? 購買履歴： ユーザ ? ニュースの閲覧履歴： ユーザ 14
- 15. 類似インスタンス 同じ特徴を持つインスタンスの集合 類似インスタンスの例： 文書集合 - 同一の単語を含む文書 商品の購買履歴 - 同一の商品を購入したユーザ ニュースの閲覧履歴 - 同一のニュースを閲覧したユーザ 15
- 16. 例： 類似インスタンス（商品の購買履歴） ユーザ１とユーザ４は類似 ユーザ ID 購買商品一覧 している 二つの同一の商品（ 1 iPad, IntelliJ, うまい棒 IntelliJ, うまい棒）を購 入している 2 Nicon D3000, チョコレー ト 3 チーズケーキ, ロレック ス, オメガ 4 IntelliJ, うまい棒, 任天 堂DS 16
- 18. 例：類似インスタンスと推薦 Q. ユーザ１にお勧め商品を ユーザ ID 購買商品一覧 推薦するには 1 iPad, IntelliJ, うまい棒 A. ユーザ１の類似ユーザ（ ユーザ４）の特徴（購入し た商品）を抽出する． 2 Nicon D3000, チョコレー ここではユーザ１に任天 ト 堂ＤＳを抽出し推薦する 3 チーズケーキ, ロレック ス, オメガ 4 IntelliJ, うまい棒, 任天 堂DS 18
- 19. 各インスタンスに類似するインスタンスを 抽出するには 各インスタンスに対して、他の全インスタンスと比較し類似インス タンスであれば抽出する． 例（購買履歴）： 同一の商品を購入しているかをチェック ．．． 19
- 20. 類似インスタンスの抽出における問題点 問題点： ユーザ毎に他の全ユーザと類似性をチェックするの では時間がかかりすぎる！ Locality Sensitive Hashing [Piotr and Rajeev, 1999] を 利用して高速に類似インスタンスを抽出する 20
- 21. Locality Sensitive Hashing [Piotr and Rajeev, 1999] 類似するインスタンスを抽出する技術 特徴 速い 精度はそれほどでもない 事例 Google News のレコメンデーション [Das et al., 2007] 21
- 22. LSH が行う処理 1. LSHはインスタンスを表すベクトル（インスタンスベクトル）を 入力として，関数を適用する 重要： 関数は似たベクトルに対して同一の値を返しやす いという特徴を持つ 2. 関数を適用した後，同一の関数値を持つインスタンスを類似 インスタンスとして抽出 注： 全インスタンスの総当り比較が必要ないため高速に動作 する 22
- 23. 例：インスタンスベクトルの生成 商 商品名 ユーザ1の購買履歴： 品 iPad, IntelliJ, うまい棒 ID 1 iPad 商品IDを次元とする 2 IntelliJ ベクトルを作る 3 うまい棒 4 ヘルシオ ユーザ１のインスタンスベクトル： … … [1 1 1 0 0 0 0 0] ユーザ１が商品１を一つ購 入したことを表す 23
- 24. イメージ：関数の適用 入力（インスタンスベクトル） 出力（関数値） ユーザ１ [1 1 1 0 0 0 0 0] 950494 ユーザ2 [0 0 0 1 1 0 0 0] 48308 関数を適用 ユーザ３ [0 0 0 0 0 1 1 0] 848490 ユーザ４ [0 1 1 0 0 0 0 1] 950494 24
- 25. 関数値が得られた後 関数値をキー，インスタンスをバリューとして連想配列に保存す ると自然に類似インスタンス集合が抽出できる． 注： Hadoop では結果は key-value． 例： 購買履歴データを利用した際の出力 キー (関数値) バリュー (インスタンス集合) 950494 ユーザ1，ユーザ4 48308 ユーザ2 848490 ユーザ3 25
- 26. Likelike (リケリケ) 拙作の LSH の壱実装 関数として MinHash を実装 Hadoop 上で動作 URL: http://code.google.com/p/likelike/ 26
- 27. Likelike の利用方法 簡単なコマンドで利用できる 類似インスタンスを抽出 $ sh bin/likelike lsh -input Input.txt -output outputDir 推薦するアイテムの抽出 （LSH で得られた類似インスタンス の結果を利用） $ sh bin/likelike featureExtraction ? -input outputDir ? -feature input.txt -output featureOutputDir 27
- 29. ニュースを選択した理由 ニュース記事には閲覧頻度の高くないものが多数存在する． ニュース記事は移り変わりが激しいので，LSHのように高速に 動作するアルゴリズムが向いている． 各記事の総クリック数分布 29
- 30. 実験設定 利用データ ミクシィニュースのアクセスログ （２０１１年９月分） ? 一日分 ３００MB ? 三日分 １GB ? 一週間分 ２GB ニュース記事 ７万件 計算機構成 Master 1台 Slave ５台 30
- 31. 実験１（計算にかかる時間） 以下の処理にかかった時間を計測 1. LSH による類似インスタンスの抽出 ? 各ユーザに対する関数値を（１，５，１０）件算出 注： ユーザごとに計算する関数値を増やすことで Recall が上昇 （関連インスタンスがたくさん抽出でき る） 2. ＬＳＨで類似インスタンスを抽出した後，推薦するニュース を算出 31
- 32. 実験结果：计算に必要な时间 ユーザ毎に算出された関数値の数 1 5 10 利用データ 1 3 7 1 3 7 1 3 7 （日） LSH 2.12 2.29 3.24 3.29 5.29 8.38 9.45 15.09 18.52 （時間） 推薦 3.27 3.20 5.15 5.35 7.26 9.58 3.50 6.27 10.38 （時間） 合計 5.39 5.49 8.39 9.04 12.55 18.36 13.35 21.36 29.30 32
- 33. 実験２ （推薦の精度） 閲覧履歴に対して推薦されたニュースをリストアップ 手順 1. ニュースの閲覧履歴をランダムに生成 （人工データ） 2. 全ユーザの閲覧履歴（7日分）にステップ１で生成した人 工データを加えLSHを計算 3. 人工データに対する推薦記事の題目をチェック 33
- 34. 実験結果：推薦されたニュース一覧 閲覧したニュース （人工データ） ラン 題目（内容語のみ） 4強 奈良大会 キン 香港株 反発 中国 景気 グ KARA 運動 1 女子力アップ 用品 西武 自力 優勝 2 初デート 異性 行動 3 部屋 整理術 4 友達 ランク 女子 5 彼氏 必死 行動パター ン 34
- 35. 実験結果：推薦されたニュース一覧 閲覧したニュース （人工データ） ラン 題目（内容語のみ） 九州国際大付属 甲子園 キン 敗れる グ 国会 ９５代 首相 野田 指 1 福島第一 原子力 名 穂高岳 落石 2 牛肉 衛生基準 厚生省 3 中井氏 同行 職員 処 分 4 円 一時79円 5 経産次官 更迭 35
- 36. 考察：なぜ推薦した記事はユーザの閲覧した記 事と関係なさそうなのか？ ユーザはカテゴリを 横断して記事を閲覧 する 例： 国際(ギリシア危 機) → 芸能 （AKB） → スポーツ （インテ ル長友） 直感：カテゴリの違う 記事は同一のユー ザにクリックされてた 場合でもそれほど関 連しない 36
- 37. カテゴリを遷移する閲覧行動への対処 同一のカテゴリ内でのページ遷移のみを考慮したい 閲覧履歴データをカテゴリごとに分割し，分割されたデータ に LSH を適用した 注： カテゴリはニュース記事に人手で付与さている 37
- 38. 実験結果：推薦されたニュース一覧 （スポ ーツ限定） 閲覧したニュース （人工データ） ランキン 題目（内容語のみ） 4強 奈良大会 グ 香港株 反発 中国 景気 1 マートン 病院 KARA 運動 西武 自力 優勝 2 ロッテ 唐川 3 阪神 森田 一軍 4 甲子園 ネット裏 5 川澄 甲子園 始球 式 38
- 39. 実験結果：推薦されたニュース一覧 （スポ ーツ限定） 閲覧したニュース （人工データ） ランキン 題目（内容語のみ） 九州国際大付属 甲子園 グ 敗れる 1 巨人 原監督 ボー 国会 ９５代 首相 野田 指 ル 振る 名 2 広島 2位 浮上 穂高岳 落石 3 広島 広瀬 復帰 4 甲子園 聖光学院 日南学院 対戦 5 メッツ スカウト 花 巻東 雄星 以上 発 見 39
- 40. 今後の予定 （実験） カテゴリごとに分割して LSH をかけた後結果を統合し，最終 的な推薦リストを生成 残る問題：推薦される記事の数にばらつき まったく推薦されないケースも結構ある 逆に非常に多数の推薦が得られるケースもある 推薦の導入作業 チューニング コンテンツデータも入れて実験 40
- 41. 今後の予定 （Likelike） Likelike を推薦プラットフォームとして強化 Cassandra，HBase などの DB をサポート クライアントプログラム 関数の追加 (SimHash， Laplacian など) LSH 以外のアルゴリズムの対応 (Co-visitation, 空間木 etc) 41
- 42. まとめ ミクシィにおける Hadoop の利用状況を報告 Hadoop 上で動作するLSH の簡単な紹介と壱実装である Likelike を紹介 ニュースの推薦機能に関する予備実験とその結果を紹介 42
- 43. 終わりに（CM） ほかにもツールを公開中． Oluolu (オルオル) ? クエリログマイニングツール ? 日本語の “もしかして検索” で利用可能な辞書を抽出 ? URL: http://code.google.com/p/oluolu/ Anuenue (アヌエヌエ) ? Solr のラッパー ? 大規模文書データを検索するためのクラスタを簡単に 構成できる ? ミクシィページの検索で実際に利用 ? URL: http://code.google.com/p/anuenue-wrapper/ 43
- 44. ご静聴ありがとうございました． 44