【文章內(nèi)容簡介】 a 109 ワイン、水、サイダーMi t a 103 ビール、ジン、サイダーY o sh i n o 002 ビールY o sh i n o 106 ワイン、サイダーY o sh i n o 205 ブランディH a n e d a 0 1 1 ブランディTUT 39。2023/06/07 31 時系列データの解析 (2) 名前 (T i d 品目 … )Y a m a d a (1 0 5 ビール )(2 1 0 ブランディ )H i r o s a w a (0 1 0 ジュース、コーラ )(0 1 2 ビール )(1 0 9 ワイン、水、サイダー )Mi ta (1 0 3 ビール、ジン、サイダー )Y o s h i n o (0 0 2 ビール )(1 0 6 ワイン、サイダー )(2 0 5 ブランディ )H a n e d a (0 1 1 ブランディ )サポート 　　パ タ ー ン4 0 . 0 % （ビール）→ （ブランディ）4 0 . 0 % （ビール）→ （ワイン、サイダー）TUT 39。2023/06/07 32 分類階層構(gòu)造の導(dǎo)入 ワイン ??? ??? ビール ブランディ ????? 飲料 清涼飲料 弱い酒類 強い酒類 TUT 39。2023/06/07 33 數(shù)値屬性の取り扱い ? 離散化 ? Maxsupportを越える rangeまで統(tǒng)合 複數(shù)の range ? Frequent itemset計算 Rule導(dǎo)出 ? Rule Interest により刈り込み ? Partial pleteness概念 Interval設(shè)定、健全性確保 Srikant, R. Agrawal, R.: Mining Quantitative Association Rules in Large Relational Tables, Proc. ACM SIGMOD, (1996). ID A g e M a rri e d C a rs1 0 0 23 No 12 0 0 25 Y e s 13 0 0 29 No 04 0 0 34 Y e s 25 0 0 38 Y e s 2In te rv a l2 0 .. 2 42 5 .. 2 93 0 .. 3 43 5 .. 3 9 I t e ms e t S u p p o rt{ A g e : 2 0 . . 2 9 } 3{ A g e : 3 0 . . 3 9 } 2{M a rri e d : Y e s } 3{M a rri e d : N o } 2{ C a rs : 0 . . 1 } 3{ A g e : 3 0 . . 3 9 , M a rri e d : Y e s } 2 R u l e Su p p o rt C o n f i d e n c e A g e : 3 0 . . 3 9 a n d M a rri e d : Y e s ? C a rs : 2 4 0 % 1 0 0 % A g e : 2 0 . . 2 9 ? C a rs : 0 .. 1 6 0 % 6 6 . 6 %People Frequent itemset (part) TUT 39。2023/06/07 34 仮想トランザクション導(dǎo)入による要因分析 沼尾、清水 : 流通業(yè)におけるデータマイニング , 人工知能學(xué)會誌 , , , (1997). 顧客 年齢 性別 職業(yè)１ 25 男 學(xué)生２ 32 女 OL… … … …顧客 日付 購買商品１ 0 0 / 0 0 / 0 0 S – 男１ 0 0 / 0 0 / 0 0 A – ２０代１ 9 7 / 0 1 / 3 0 C D – X１ 9 7 / 0 2 / 0 5 C D – Y１ … …２ 0 0 / 0 0 / 0 0 S – 女２ 0 0 / 0 0 / 0 0 A – ３０代２ 9 7 / 0 1 / 1 5 V i d eo – A２ 9 7 / 0 3 / 0 3 V i d eo – B…TUT 39。2023/06/07 35 ? 時系列記號化によるパターン認(rèn)識 ? 教師付き帰納學(xué)習(xí) 異常発生 最大遅れ時間 圧力 溫度 データベース化 時刻 変數(shù) パターンT1 溫度 上昇T2 圧力 上昇T3 溫度 下降T4 圧力 下降T5 溫度 上昇T6 圧力 上昇T7 溫度 上昇T8 溫度 下降T9 圧力 上昇… … …IF 圧力上昇 AND 溫度下降 THEN 異常発生： 確率 80% 佐藤： データマイニング向けルールインダクション技術(shù)とその応用 , 情報処理學(xué)會関西支部平成９年度第１回ソフトウェア研究會 時系列データマイニング事例 TUT 39。2023/06/07 36 グラフ構(gòu)造への拡張： ＷＷＷアクセス履歴の分析 BCADBCAHBICADEJKMLNFG豬口他 :人工知能學(xué)會基礎(chǔ)論研究會 SIGFAI980110, (1998). TUT 39。2023/06/07 37 相関ルールの探索 TUT 39。2023/06/07 38 4 213A:B:抽出パターン C :B 713 7Setp3: ペア選択 Graph Based Induction 逐次ペア拡張アルゴリズム 吉田、元田 : 逐次ペア拡張に基づく帰納推論 人工知能學(xué)會誌 , (1997). 452 1 63 74 268 63 9入力 Step1: 入力の書き換え A5B 67A68 63 9A B 6 A68 6B 78 33 9Step2: 入力中のペアの數(shù)え上げ TUT 39。2023/06/07 39 GBIのコマンド操作履歴解析への応用 emacs lpr dvi2ps xdvi latex mand file 手法 最頻 直前 線形識別 1 N N C A R T G B I精度 2 2 . 6 % 2 0 . 7 % 2 2 . 6 % 2 0 . 8 % 3 4 . 6 % 5 7 . 8 %TUT 39。2023/06/07 40 Graph Based Inductionの特徴 ? 高速に構(gòu)造化オブジェクトの解析可 ? 概念獲得，分類規(guī)則學(xué)習(xí)，推論高速化の何れにも適用可能 ? Sequence（DNA, protein）への応用Negativeな條件表現(xiàn)に工夫が必要 ? Ordered Graphに限定 ? 規(guī)則?概念は連結(jié)グラフに限定 ? 複製障害により複雑なオブジェクトの取り扱い困難 TUT 39。2023/06/07 41 帰納論理プログラミング 最も簡単な実行例 ? 前提知識 parent(1, 2). parent(1, 3). ... ? 正例 他は負(fù)例 grandparent(1, 4). grandparent(1, 5). … ? 結(jié)果 grandparent(X, Y) : parent(X, Z), parent(Z, Y). ① ② ③ ④ ⑤ ⑥ ⑦ TUT 39。2023/06/07 42 Version space中での仮説探索 Grandparent(X, Y) : ??? ? 被覆集合アルゴリズム ? 新たなリテラルの付加 変數(shù)の定數(shù)化 ? 記述長最尐原理で仮説選択 ? FOIL: Quinlan (1990) entropyによる最良探索 ? Progol: Muggleton (1995) 逆伴意 (Inverse entailment)による探索空間の縮小 採用仮説 棄卻仮説 正例 負(fù)例 TUT 39。2023/06/07 43 Progolによる変異原性物質(zhì)の識別 ? 230種のニトロ化合物： Ames test positive 138 / negative 92, Debnath et al: J. Med. Chem. 34:786797(1991). ? １８８種：重回帰分析実施 ? Progol: 188（12hr） / 42（6hr）に分割解析 ? atm(pound, atom, element, type, charge). bond(pound, atom1, atom2, bondtype). ? 9種の Rule 分類精度は同様 ? 指示変數(shù)の自動的発見 Phenanthrene骨格、例外的 acetylene ? 使用法の困難性、長い計算時間 King et .al.: Relating chemical activity to structure: an examination of ILP success, New Generation Computing, , (1995). C H2H2CH2CH2CO OON O2N O2N O2N O2N O2C l C lC lC l N O2O2NCHNN NCH2N HOOABCDCD EFVW XU Y ZInput Rule TUT 39。2023/06/07 44 帰納論理プログラミング Inductive logic programming ? 人工知能學(xué)會誌小特集 : 帰納論理プログラミング , , , (1997). ? Lavrac Dzeroski: Inductive Logic Programming: Techniques and Applications, Hertfordshire, Ellis Horwood (1994). Dzeroski, S.: Inductive Logic Programming and Knowledge Discovery in Databases, In Fayyad et. al. Advances in Knowledge Discovery and Data Mining, , AAAI Press (1996). ? Quinlan, .: Learning Logical Definitions from Relations, Machine Learning, , (1990). ? Muggleton, S.: Inductive Logic Programming, New Generation Computing, , (1991)。 Inverse Entailment and Progol, ibid. , (1995). ? King, . et. al.: Relating Chemical Activity to Structure: an examination of ILP successes, ibid. , (1995). ? TUT 39。2023/06/07 45 參考資料 TUT 39。2023/06/07 46 赤目四十八滝 三重県 TUT 39。2023/06/07 47 Rule Induction as Data Analysis Tool ? Rules accurate ? Yes. ? Software available ? Yes. ? Computing fast ? Yes. ? Easy understanding ? Yes. ? Popular ? No. TUT 39。2023/06/07 48 Possible Reasons ? Conservative users ? Unix environment ? No familiar examples ? Too many methods ? Too many rules ? Selfevident rules ? Impressions: ?ad hoc methods ?exploratory TUT 39。2023/06/07 49 Response of Users from Expected Results ? Regression by a few variables ? TSS = ESS + RSS 100% 99% 1% ? Hypothesis confirmed = Satisfactory ? Rule induction ? A few simple rules ? Average accuracy: 99%