Microsoft PowerPoint _ビッグデータWS.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint _ビッグデータWS.pptx"

らむたけすえ
5 years ago
Views:

1 隠れた名品を推薦するためのグラフマイニング法の提案佐藤哲司筑波学隠れた名品万願寺とうがらし 15 年ほど前に京都の料理屋で始めて何じゃこりゃ?! 唐? ピーマン? 果は厚くて柔らかくみが深いクックパッドで検索 :1,112 品そのまま焼いてべても美味しいが, じゃこ, 海と相性が良いらしい. ( ざるの直径は 27cm) 出典 :wikipedia 共起 (1.2 千件 ) 共起 (120 件 ) 共起 (18 件 ) ピーマン (105 千件 ) じゃこ (17 千件 ) 万願寺 (1.1 千件 ) 海 (53 千件 ) 2018/3/9 ビッグデータ分析技術ワークショップ 2

レシピマップレシピの出現する材 Cookpad データ (NII から提供 ) のレシピ集合の解析材の出現頻度 ( レシピ数 ) は, きれいなべき乗則レシピと材の定番度ありふれた / 珍しい材 HITS アルゴリズムを適 Authority: 材, Hub: レシピありふれた材だけで調理したレシピ滅多に使されない材を使ったレシピ容易にレパートリー拡

2 レシピマップレシピの出現する材 Cookpad データ (NII から提供 ) のレシピ集合の解析材の出現頻度 ( レシピ数 ) は, きれいなべき乗則レシピと材の定番度ありふれた / 珍しい材 HITS アルゴリズムを適 Authority: 材, Hub: レシピありふれた材だけで調理したレシピ滅多に使されない材を使ったレシピ容易にレパートリー拡できるレシピ推薦の順序 [ 中岡, DEIM2015] 珍しい材ありふれたレシピ材珍しいレシピ 2018/3/9 ビッグデータ分析技術ワークショップ 3 規模データに対するマイニングたいていのデータはべき乗則 Cookpad は 285 万件全数を使った解析が可能楽天市場のレビュー記事 :6,500 万件全数はちょっと頻出パターン分析 Short Head: 頻度の領域から典型的なパターンを抽出 Long Tail: データ件数は多いがノイズも多い計算機能が上がっても, 闇雲に解析しても知は得られない低頻度だけど万願寺とジャコの相性が良いに相当する関係を知りたいマイニングの対象領域を出現頻度ではない法で局所的な偏りをがかりに切り出したい 2018/3/9 ビッグデータ分析技術ワークショップ 4 # appearance frequency Rank

3 アイデア! Z スコア値を標準化して較可能とする法を共起グラフに適あるノードの周辺エッジのうちで, 頻度のエッジにい値分析対象グラフ Z スコアの値と出現頻度の組み合わせで抽出, エッジの出現頻度,,, 周辺エッジの平均周辺エッジの標準偏差 2018/3/9 ビッグデータ分析技術ワークショップ 5 頻度低 Zスコア高高低規模な実データに適楽天市場 6,500 万レビュー情報学研究データリポジトリ ( 楽天株式会社, NII) レビュー履歴購買履歴とするための前処理投稿者が意に判別できるレビューを抽出購の有無が確認できない投稿時が落しているレビューを除外 244 万ユーザによる 1,780 万レビュー 2018/3/9 ビッグデータ分析技術ワークショップ 6

4 購買順序グラフ (PHG) の構築ノード : 商品エッジ : 個々の消費者が連続して購入した2 商品の順序エッジの重み, 1, 2, 2, 1 A B C A C D B E B D B C D E 2018/3/9 ビッグデータ分析技術ワークショップ 7 購買動グラフの特性 1,780 万レビューから構築した PHG 6,721,476 item nodes 24,325,221 edges エッジの出現頻度グラフ Z スコア Z スコアの分布グラフエッジの出現頻度 2018/3/9 ビッグデータ分析技術ワークショップ 8

サブグラフの抽出と特性較出現頻度順 / Z スコア順に上位 10,000 エッジからサブグラフを抽出

エッジ Z スコアグラフ 6,656 エッジ共通グラフ 3,344 エッジ 2018/3/9

較抽出グラフのエッジ数は 10,000 で同なのに対して, Z スコアグラフのノード数が 2 倍以上

6,721,476 24,325,221 出現頻度グラフ 6,932 10,000 Zスコアグラフ

5 サブグラフの抽出と特性較出現頻度順 / Z スコア順に上位 10,000 エッジからサブグラフを抽出 : 共通グラフ頻度 Z スコア : 出現頻度グラフ緑 :Zスコアグラフ出現頻度グラフ 6,656 エッジ Z スコアグラフ 6,656 エッジ共通グラフ 3,344 エッジ 2018/3/9 ビッグデータ分析技術ワークショップ 9 ノード数エッジ数の較エッジ抽出前と抽出後の 3 グラフを較抽出グラフのエッジ数は 10,000 で同なのに対して, Z スコアグラフのノード数が 2 倍以上広範囲のノード ( アイテム ) を含むグラフを抽出グラフ種別ノード数エッジ数初期グラフ 6,721,476 24,325,221 出現頻度グラフ 6,932 10,000 Zスコアグラフ 15,468 10,000 共通グラフ 3,874 3, /3/9 ビッグデータ分析技術ワークショップ 10

6 抽出グラフの可視化 (1) 共通グラフ ( 部 ) 出現頻度も Z スコアもいグラフ ( 従来の ) 頻出パターン抽出でも重要な構造 2018/3/9 ビッグデータ分析技術ワークショップ 11 抽出グラフの可視化 (2) 出現頻度グラフ ( 部 ) 共通グラフを補強ノード数の増 : エッジ数の増 : グラフの密度化 2018/3/9 ビッグデータ分析技術ワークショップ 12

7 抽出グラフの可視化 (3) 出現頻度グラフ ( 部 ) 共通グラフを補強ノード数の増 : エッジ数の増 : 中部を拡グラフの密度化 2018/3/9 ビッグデータ分析技術ワークショップ 13 抽出グラフの可視化 (4) 出現頻度グラフ ( 部 ) 共通グラフを補強ノード数の増 : エッジ数の増 : 周縁部を拡グラフの密度化 2018/3/9 ビッグデータ分析技術ワークショップ 14

8 抽出グラフの可視化 (5) Z スコアグラフ ( 部 ) 共通グラフを拡張ノード数の増 : エッジ数の増 : グラフの周縁部拡張 2018/3/9 ビッグデータ分析技術ワークショップ 15 抽出グラフの可視化 (6) Z スコアグラフ ( 部 ) 共通グラフを拡張ノード数の増 : エッジ数の増 : グラフの周縁部拡張 2018/3/9 ビッグデータ分析技術ワークショップ 16

9 抽出グラフの可視化 (7) Z スコアグラフ ( 部 ) 共通グラフを拡張ノード数の増 : エッジ数の増 : グラフの周縁部拡張 2018/3/9 ビッグデータ分析技術ワークショップ 17 抽出グラフの較出現頻度 ( 従来法 )vs. Z スコア ( 提案法 ) 出現頻度グラフ内部の密度化 Z スコアグラフ周縁部の拡張 2018/3/9 ビッグデータ分析技術ワークショップ 18

10 モチーフ分析による成分析 2018/3/9 ビッグデータ分析技術ワークショップ 19 3 ノードモチーフ 13 種類のモチーフ 3 個のノード間で考えられる全ての順序関係モチーフの数え上げで購買順序グラフ (PHG) の特徴を抽出 2018/3/9 ビッグデータ分析技術ワークショップ 20

11 モチーフパターンの例購買順序グラフ (PHG) の特徴 MP4 1 回 A D C B 2018/3/9 ビッグデータ分析技術ワークショップ 21 モチーフパターンの例 ( つづき ) 購買順序グラフ (PHG) の特徴 MP4 1 回 A C D MP2 1 回 B 2018/3/9 ビッグデータ分析技術ワークショップ 22

12 モチーフパターンの例 ( 正規化 ) 購買順序グラフ (PHG) の特徴モチーフベクトル = ( 0, 2, 0, 1, 0,, 0 ) 正規化ベクトル = ( 0, 2/3, 0, 1/3, 0,, 0 ) MP4 1 回 A C D MP2 2 回 B 2018/3/9 ビッグデータ分析技術ワークショップ 23 購買動グラフの評価 1,780 万レビューから構築した PHG 楽天市場のレビュー記事から構築 6,721,476 item nodes 24,325,221 edges エッジの出現頻度グラフ Z スコア Z スコアの分布グラフエッジの出現頻度 2018/3/9 ビッグデータ分析技術ワークショップ 24

13 評価サブグラフの抽出 Z スコア vs 出現頻度緑領域 : エッジの出現頻度 10 領域 :Z スコア 10 出現頻度がいサブグラフ 10,266 ノード 13,939 エッジ Z スコアがいサブグラフ 18,914 ノード 1.36 倍 1.09 倍 20,600 エッジ 2018/3/9 ビッグデータ分析技術ワークショップ 25 モチーフパターンの較出現率のいパターンエッジ頻度 : MP 3, 7, 8 Z スコア : MP 1, 2, 3, 4, 7, /3/9 ビッグデータ分析技術ワークショップ 26

スコアに対するモチーフパターンの遷移エッジの出現頻度で評価領域を区分低頻度域 : 出現頻度 < 10 中頻度域 : 10 出現頻度 < 100 頻度域 : 100 出現頻度

14 モチーフの成遷移成 : エッジが追加されることでモチーフが遷移 MP1 に逆向きエッジを追加 MP 3 MP1 に新たなエッジを追加 MP 5 購買順序グラフの成エッジ頻度 : MP 3, 7, 8 Zスコア : MP 1, 2, 3, 4, 7, 8 成前のモチーフを抽出 2018/3/9 ビッグデータ分析技術ワークショップ 27 Z スコアに対するモチーフパターンの遷移エッジの出現頻度で評価領域を区分低頻度域 : 出現頻度 < 10 中頻度域 : 10 出現頻度 < 100 頻度域 : 100 出現頻度モチーフパターンの遷移着するモチーフ : 出現率がい MP 1, 2, 3, 4, 7, 8 Z スコアの閾値を変えて, 各モチーフの出現率をトレース 2018/3/9 ビッグデータ分析技術ワークショップ 28

15 頻度域のモチーフパターン変化頻度域全域 (Z スコアの閾値 =0) 頻度で切りする従来法に相当出現頻度 100 MP 3, 7, 8 が確率で出現 2018/3/9 ビッグデータ分析技術ワークショップ 29 頻度域のモチーフパターン変化頻度域で Z スコアの閾値を上昇右上図は Zscore 20 のモチーフパターン MP 1, 2, 3, 4, 7, 8 が確率で出現 2018/3/9 ビッグデータ分析技術ワークショップ 30

16 中頻度域でのモチーフパターンの変化 MP8 Decrease MP1&2 Increase 2018/3/9 ビッグデータ分析技術ワークショップ 31 低頻度域でのモチーフパターンの変化 Z スコアの閾値を上げると MP2 が減,MP1, 4 が増 Z スコア 20 以上のエッジは存在しない 2018/3/9 ビッグデータ分析技術ワークショップ 32

低頻度域でのモチーフパターンの変化 MP2: 連続購シリーズもののコミックなど MP1, 4: ハブ型購本体とカバー, 周辺機器など

:Short Head における頻出パターンに着提案法 :Long Tail における局所的に得意なパターンに着分析対象グラフの抽出

ネットショッピングの履歴データで検証弱連結成分分解したグラフの可視化従来法 : グラフの強度を重視提案法 : グラフの拡がり (

17 低頻度域でのモチーフパターンの変化 MP2: 連続購シリーズもののコミックなど MP1, 4: ハブ型購本体とカバー, 周辺機器など 2018/3/9 ビッグデータ分析技術ワークショップ 33 まとめ規模な社会ネットワーク分析規模べき乗則に従ったデータ分布従来法 :Short Head における頻出パターンに着提案法 :Long Tail における局所的に得意なパターンに着分析対象グラフの抽出分析の前処理に相当 : Long Tail に存在する隠れた名品 Z スコアの適 : ノードの周辺で優位なエッジを抽出ネットショッピングの履歴データで検証弱連結成分分解したグラフの可視化従来法 : グラフの強度を重視提案法 : グラフの拡がり ( 周縁部の拡張 ) を重視モチーフ分析成前のモチーフ抽出に成功隠れた名品の可能性 Z スコアの閾値異なる特徴のモチーフを抽出 2018/3/9 ビッグデータ分析技術ワークショップ 34

18 関連論稲福和史, 伏卓恭, 佐藤哲司 : 近傍エッジとの関係に着したグラフマイニング法の提案と評価, DEIM2018, J2-5 (Mar. 4-6, 2018). Kazufumi Inafuku, Takayasu Fushimi, Tetsuji Satoh: Graph Generation Method Based on Relative Value of Neighbor Edges, iiwas2017, pp (Dec. 4-6, 2017). 稲福和史, 伏卓恭, 佐藤哲司 : EC サイトにおける購買動の成分析, DICOMO2017, pp (June 28-30, 2017). 稲福和史, 伏卓恭, 佐藤哲司 : レビュー順序グラフに基づく購買動パターンの分析, DEIM2017, A3-4 (Mar. 3-9, 2017). Kazufumi Inafuku, Takayasu Fushimi, Tetsuji Satoh: Extraction Method of Typical Purchase Patterns Based on Motif Analysis of Directed Graphs, iiwas2016, pp (Nov , 2016). 中岡義貴, 佐藤哲司 : 定番度に基づくレシピ推薦システムの提案, DICOMO2013, pp (July, 2013). 中岡義貴, 佐藤哲司 : 調理レパートリー拡のためのレシピ推薦法の提案と評価, DEIM2015, C1-1 (Mar. 2015). 2018/3/9 ビッグデータ分析技術ワークショップ 35

生命情報学

生命情報学 5 隠れマルコフモデル阿久津達也京都大学化学研究所バイオインフォマティクスセンター内容配列モチーフ最尤推定ベイズ推定 M 推定隠れマルコフモデル HMM Verアルゴリズム EMアルゴリズム Baum-Welchアルゴリズム前向きアルゴリズム後向きアルゴリズムプロファイル HMM 配列モチーフモチーフ発見配列モチーフ : 同じ機能を持つ遺伝子配列などに見られる共通の文字列パターン