Microsoft PowerPoint - LDW.ppt [互換モード]

Size: px

Start display at page:

Download "Microsoft PowerPoint - LDW.ppt [互換モード]"

れんまたなせ
5 years ago
Views:

1 グラフ系列マイニング猪口明博大阪大学産業科学研究所科学技術振興機構さきがけ

2 研究の背景データマイニングインフラ技術の高度化多様で大規模な情報やデータへのアクセス, 蓄積が容易. 多様で大規模なデータから有用な知識を発掘することは重要な課題. 頻出アイテム集合マイニング [Arawal 9] 頻出アイテム集合列挙問題一般に多くの事例を説明する知識は有用である. バスケット分析 Raw Data 例 ) スーパーマーケットのデータベースからよく売れる商品の組み合わせを高速に抽出する. データベースはアイテム ( 商品 ) の集合からなる. Taret Data Selection Preprocessed Data Preprocessin Transformed Data Transformation Rules & Patterns Minin Knowlede Interpretation Evaluation 顧客 ={ 食料品 a, 食料品 b, 日用品 b,...} 顧客 n={ 食料品 a, 飲料水 a, 日用品 b,...} σ 人以上の人が購入した商品の組み合わせを全て列挙 { 食料品 a, 飲料水 a}, { 食料品 a, 飲料水 a, 日用品 b},

3 頻出部分グラフマイニング問題 : σ 個以上のグラフに含まれる全ての部分グラフを全て列挙応用例抗ヒスタミン薬の共通パターン発見共通パターン H H O HN Ar OHHNEt O Ar X N R H Et NHHNEt HOHHN H R H 抗ヒスタミン薬の一般的な構造 ( 母核 )

4 グラフ系列の例ホームページのリンク構造の変化 HTML 文章 : 頂点, ハイパーリンク : 辺人間関係ネットワークの変化人 : 頂点, 人間関係 : 辺遺伝子ネットワークの変化 ( 進化 ) 遺伝子 : 頂点, 相互作用 : 辺機械の組み立て部品 : 頂点, 隣接する部品間 : 辺その他脱退参加

5 グラフ系列のマイニング頻出する部分系列をマイニング頻出変換部分系列 FTS (Frequent Transformation Subsequence) グラフ系列頂点数, 辺数が増減する. 頂点ラベル, 辺ラベルが変化する. 仮定各頂点は, 頂点 IDをもつ. グラフ系列中の連続するつのグラフの間では, 構造が大きく変化することはなく, ごく一部の構造のみが変化する. 系列中のグラフは, 疎グラフである.

6 関連研究 Dynamic Graph [Borwardt 006] () () Evolvin Graph [Berlinerio 009] () () 00 () () 頂点数が増減するグラフやラベルが変化するグラフを扱うことができない. ()

7 GTRAE の基本アイデア [Inokuchi 008] 系列系列頻出パターンコンパイル (vi),(vi,vi,ei,ei,ei),(vi,ed,ed,vd),(ei,ed,vd),(ed,vd) (vi,vi,vi,ei),(vi,ei),(vi,ei,ei,ed,vd),(ei,ed,vd) 系列パターンマイニング頻出部分系列 (FTS) (vi,vi,ei),vi,(ei,ed,vd)

8 グラフの変換頂点や辺の追加, 削除, ラベル変更をグラフの変化. ( j) 赤い頂点の追加 vi ( j) ( j ) ( j ),,,, ( j ) 青い頂点と緑の頂点の間の辺の削除 ed ( j ),vi, ed, グラフの変化をアイテム集合 ( 変換規則の集合 ) の系列に変換後, 系列パターンマイニングアルゴリズムを適用し,FTS を列挙する.

9 6 種の変換規則頂点の追加 (vi) 辺の追加 (ei) 頂点の削除 (vd) 辺の削除 (ed) 頂点ラベルの変更 (vr) 辺ラベルの変更 (er)

10 グラフ系列の補間観測されたグラフ系列補間されたグラフ系列,(vi, vi, ed, ei),

11 応用例抗ヒスタミン薬の共通パターン発見共通パターン H H O HN Ar OHHNEt O Ar X N R H Et NHHNEt HOHHN H R H 抗ヒスタミン薬の一般的な構造 ( 母核 ) Ar Ar X N R - H H -H R N H 頻出部分グラフが連結理解が容易頻出部分グラフが非連結理解が困難

12 関連のある FTS のマイニング A 女性と女性は関連がある. 女性と男性は関連がある. 女性と男性は女性を介して関連があると考える. 男性は他の人と関連がない. 和グラフ FTS の和グラフが連結であるならば, 関連があると定義する. 他の頂点と関連のない頂点を除くことで, 互いに関連のある頂点と辺からなる FTS のみをマイニングする.

13 グラフ系列マイニング問題変換部分系列の支持度 sup( seq( d')) { d i d i () i... ( n) i { d i }, seq( d')... ), seq( d') : relevant seq (d) : 変換規則の系列頻出変換部分系列 (FTS:Frequent Transformation Subsequence) 最小支持度以上の支持度を有する変換部分系列 d i () i seq( d () i i ( n) i } 支持度の逆単調性 seq( d' ) seq( d' ) sup( seq( d' )) sup( seq( d' )) グラフ系列マイニング問題グラフ系列の集合が入力として与えられたとき, 全ての FTS を列挙すること

14 GTRAE のマイニング手順グラフ系列の集合和グラフ A 射影頻出連結部分グラフグラフマイニングアルゴリズム (vi,vi,ei),vi,ed,ie Relevant FTSs 系列パターンマイニングアルゴリズム

15 GTRAE の課題 GTRAE は観測されたグラフ系列中の連続するつのグラフで, その大部分は変化せず, ごく一部の構造が変化することを仮定観測されたグラフ系列中の連続するつのグラフが大きく変化する場合には, 変換規則の系列が長くなり, 膨大な計算時間を要する

16 FRISSMiner [Inokuchi 00] A 頻出する部分系列をマイニング G G G G グラフ系列頂点数, 辺数が増減する. 頂点ラベル, 辺ラベルが変化する. 各頂点は,ID をもつ. グラフ系列中の連続するつのグラフの間では, 構造が大きく変化することはなく, ごく一部の構造のみが変化する. G P P G P P

17 FRISSMiner のマイニング手順グラフ系列の集合和グラフ射影頻出連結部分グラフグラフマイニングアルゴリズム () () () () () ()

18 射影 () () () () () () 頂点 ID の Reassinment <ABD> <ABDD> 各グラフの同型性を O() で計算可能系列パターンマイニングアルゴリズム FRISSs <ABD> をマイニングする探索の深さは

19 GTRAE と FRISSMiner の比較前提グラフ系列の表現形式取り出されるパターン GTRAE 連続するグラフ間で構造が大きく変化しない変換規則の系列共通する変化 FRISSMiner なしグラフの系列共通する構造

20 まとめグラフ系列マイニング GTRAE [Inokuchi 008] 変換規則の系列でグラフ系列を表現グラフ系列の集合から共通する変化を列挙 FRISSMiner [Inokuchi 00] グラフ系列の集合から共通する構造を列挙課題グラフ構造の変化の予測データの背後に隠された変動やそのパターンを検知

コンピュータ応用・演習情報処理システム

コンピュータ応用・演習情報処理システム 2010 年 12 月 15 日データエンジニアリング演習情報処理システムデータマイニング ~ データからの自動知識獲得手法 ~ 1. 演習の目的 (1) 多種多様な膨大な量のデータを解析し, 企業の経営活動などに活用することが望まれている. 大規模データベースを有効に活用する, データマイニング技術の研究が脚光を浴びている 1 1. 演習の目的 (2) POS データを用いて顧客の購買パターンを分析する.