スライド 1

Size: px

Start display at page:

Download "スライド 1"

みそらしのしま
5 years ago
Views:

1 大規模離散計算科学特論 11 月 24 日白井康之独科学技術振興機構 ERATO 湊離散構造処理系プロジェクト 1

2 講義内容自己紹介手法編 1-1 はじめに全体概要 1-2 頻出パタンマイニングとその周辺 1-3 決定木分析法とその周辺事例紹介予定ザッピングデータ解析実世界情報による行動パタンの分析インターネット情報を用いた技術トレンド解析ブログによるトレンド解析可視化の例大規模データを活用した主な研究開発プロジェクト動向 2

3 1-3 決定木分析法とその周辺 3

4 内容分類問題とは? 基本的指標の定義再現率, 適合率, 情報エントロピーほか決定木分析 Decision Tree 回帰木 Regression Tree モデル木 Model Tree 4

5 分類問題とは例 : 訓練集合男性 50 代趣味 : 盆栽男性 20 代趣味 : ゴルフ女性 30 代趣味 : 温泉良い客良くない客新しいデータ女性 40 代趣味 : 料理男性 60 代趣味 : 旅行学習アウトドア趣味の人は良い顧客層予測良い客良くない客分類知識 5

6 分類問題分類知識を近似的な知識構造としてあらわすこと. 主な手法 : 線形近似, 決定木分析,k-NN, ニューラルネットワーク,SVM,... ただし, 全データのクラス分類が可能であれば, 近似する必要はない. 学習の前に, まず変数をうまく集約することにより全列挙可能かどうかを検討するべき. データを編集することなく, 最初からマイニングにゆだねてしまう例が実は結構多い. ID Attribute 1 Attribute 2 Attribute 10 Class 1 yes no no P 2 no yes yes N 3 yes yes P 1024 no yes yes P 6

7 分類の指標再現率と適合率 {True, False} {Positive, Negative} { 正しい, 間違いの } { 正例, 負例 } TP FN 予測 =P 予測 =N FP TN 真の P 真の N 再現率 recall : 真の P のうち, 正しく P と判定される割合 TP/(TP+FN)=TP/ 真の P 適合率 precision : P と判定したもののうち, 正しく分類できた割合 TP/(TP+FP)=TP/ 判定が P 7

8 分類知識全体の指標 : 再現率 recall と適合率 precision 適合率 TP/(TP+FP) を上げるには? FP をできるだけ小さくすると良いただし傾きが不変の場合例 : スパムメールの分類など疑わしきは罰せず再現率 TP/(TP+FN) を上げるには? FN をできるだけ小さくすると良いただし傾きが不変の場合例 : 不正アクセスの検出疑わしきは罰する予測 =P 予測 =N FP TP TN FN 真のP 真のN FP TP TN FN 真のP 真のN 予測 =P 予測 =N 8

9 再現率と適合率の関係適合率高い適合性を求めたい ex. スパムメール検出 A>C>B A C B 再現率高い再現性を求めたい ex. 不正アクセス検出 A>B>C 9

10 ROC Receiver Operating Characteristic 曲線 TruePositive の割合 TP/(TP+FN) 全部 N と判定する. (a) (b) 全く識別できていないケース全部 P と判定する. TP FP TN=FN=0 FN TN TP=FP=0 FalsePositive の割合 FP/(FP+TN) ROC 曲線面積により, 分類器の精度がわかる. 予測 =P 予測 =N FP TP TN FN 真のP 真のN (a) (b) 10

11 決定木分析法分類ルールを木構造として表現したもの. J.R.Quinlan 1983 (ID3), AI によるデータ解析 1995 その後 C4.5, C5.0/See5 ID3 C4.5 連続値の取り扱い属性値の欠損への対応? で表記 <500 性別年収 >=500 職業 C5.0/See5 商業利用速度向上 <50 女性年齢 >=50 男性 A B 自営会社員趣味スポーツスポーツ以外 A B B A 11

12 情報エントロピー分割は局所的に最も効果が大きい属性を選択する. このために, まずデータ集合に対するエントロピーを定義する. c Entropy p i log 2 p i 1 i クラスを決定するために必要なビット数.2 クラスでポジデータ, ネガデータが均等に分布している状況 p=0.5 では 1 ビット必要. クラスが 1 つしかない場合は, クラスは確定しているので 0 ビット.3 クラスが均等に分布している場合は,1.58 ビット. x=[0.05:0.05:0.95] function z=g(x) z=(-1)*x*log2(x) - (1-x)*log2(1-x); end for i=1:length(x) z(i)=g(x(i)) end plot(x,z) 12

13 Information Gain 情報利得ある属性選択 Attribute に対して,Information Gain を, エントロピーの差として以下のように定義する. Sv Gain( S, Attribute ) Entropy ( S) Entropy ( Sv) v Attribute S 元のノードの属性で分割されたエントロピーノードのエントロピーの重み付き和現時点で最も Information Gain の大きい属性を選択する. 属性で分離することにより, より多くの Information Gain が見込める 13

14 分類の例性別身長技量クラス M High Bad P F High Good P M High Bad P F Low Good P M Low Good N F Low Bad N M Low Good N F High Bad N Entropy(S)=1 性別で分類 0.5 Entropy(SM)+0.5 Entropy(SF) = 0.5 (-0.5 log log 0.5) (-0.5 log log 0.5) = 1 身長で分類 0.5 Entropy(Shigh)+0.5 Entropy(Slow) = 0.5 (-0.75 log log 0.25) (-0.75 log log 0.25) 0.81 よって, 身長で分類したほうが Information Gain は大きい. 14

15 決定木分類は山登り法項目の選択方法は, 山登り法であるため, 局所解に陥ることがあるので注意. 性別身長技量クラス M High Bad P F High Good P M High Bad P F Low Good P M Low Good N F Low Bad N M Low Good N F High Bad N P(2/0) High 身長 Low 性別性別 M F F 技量技量 Bad Good Bad N(1/0) P(1/0) N(1/0) M 性別身長技量 M N(2/0) Good P(1/0) Low High Bad Good F P(2/0) N(2/0) P(2/0) N(2/0) 15

Weka http://www.cs.waikato.ac.nz/ml/weka/index.html Univ. of Waikato, New Zealand Weka データマイニングツールのパッケージ (Waikato Environment for Knowledge Analysis) 1993 年にプロジェクトを開始.

16 Weka Univ. of Waikato, New Zealand Weka データマイニングツールのパッケージ (Waikato Environment for Knowledge Analysis) 1993 年にプロジェクトを開始. 当初は, さまざまな言語と Tcl/Tk で書かれたインタフェースからなっていた年から Java 化フリーソフトとして広く流通その後,C で各ライブラリを統一して記述. データ加工, クラスタリング, 分類, 回帰, 可視化等をサポート. 小規模データの実験には向いている. 大規模データに対する効率性は重視されていない. 一般的な DM の教科書のようでいて, 実はマニュアルに近い 16

17 weka: 実装されているアルゴリズムと問題記述例分類手法ナイーブベイズ, ベイジアンネットワーク,NN Nearest Neighbor, 決定木 C4,5,M5,etc, 線形回帰, SVM, その他もろもろクラスタリング EM アルゴリズム,k-means, 各種階層的クラスタリング手法, その他相関ルール分析 Apriori など outlook {sunny, overcast, temperature {hot, mild, humidity {high, windy {TRUE, play {yes, sunny,hot,high,false,no sunny,hot,high,true,no sunny,mild,high,false,no sunny,cool,normal,false,yes sunny,mild,normal,true,yes overcast,hot,high,false,yes overcast,cool,normal,true,yes overcast,mild,high,true,yes overcast,hot,normal,false,yes rainy,cool,normal,true,no rainy,mild,high,true,no rainy,mild,high,false,yes rainy,cool,normal,false,yes rainy,mild,normal,false,yes weka サンプルデータより 17

18 weka: 実行例データファイル % Title: Database for fitting contact lenses % -- 3 Classes (soft/hard/none) % 1. age : (1) young, (2) pre-presbyopic, (3) presbyopic 老眼 % 2. spectacle prescription 処方 : (1) myope 近視, (2) hypermetrope 遠視 % 3. astigmatic 乱視 : (1) no, (2) yes % 4. tear production rate 涙の分泌量 : (1) reduced, (2) age {young, pre-presbyopic, spectacle-prescrip {myope, astigmatism {no, tear-prod-rate {reduced, contact-lenses {soft, hard, young,myope,no,reduced,hard pre-presbyopic,myope,no,reduced,hard young,myope,no,reduced,hard pre-presbyopic,myope,no,reduced,hard young,myope,no,reduced,hard 18

19 weka: 実行例 demo 19

20 k 分割交差検定 k-hold cross-validation 分類方法の評価. 標本データをトレーニングセットとテストセットに分割し, トレーニングセットでの解析結果をテストセットで検定する. k- 分割交差検定では, 標本群を k 個に分割し,k-1 個のトレーニングセットで学習した結果を残りの 1 つのテストセットで検証するこれを k 回繰り返して, 平均をとり, 分類方法の評価とする. トレーニングセットテストセット 10-hold cross-validation あたりが一般的. 20

21 決定木分析の拡張 Regression Tree: 回帰木 [Breiman 1984] Classification and Regression Trees CART 商用ソフトウェア等に実装目的変数が数値 i.e., 順序に意味がある属性目的変数 ex. 購入金額 10 万円 ~ 0 円 F 性別 M 5500 アウトドア趣味インドア低年齢高属性

22 決定木分析の拡張 Regression Tree: 回帰木項目の選択離散項目の場合 Gain( S, Attribute ) SquaredError( S) SquaredError( S) x S ( x x S 2 ) v Attribute SquaredError( S v ) 連続値の場合には, 最も二乗誤差が小さくなるような閾値を選択. 22

23 決定木分析の拡張 Model Tree: モデル木 [Quinlan 1992] Learning with Continuous Classes しばしば M5 と呼ばれる. リーフに線形回帰式属性 2 営業性別職種内勤業種女男サービス製造 L1 他社借入家族 L2 少多無有 L3 L4 L5 L6 属性 1 L4: c+w1* 借入額 +w2* 年齢 +w3*{ 家族 = 有 } 木が深くなるとほとんど意味をなさない. 常識的には, リーフ数は数個程度が適当な例が多い. 単一の線形回帰では無理があるような場合. 23

24 頻出パタンや決定木を使ったマイニング事例については, このあと紹介します. 24

25 25

スライド 1

スライド 1 大規模離散計算科学特論 (11 月 8 日 ) 白井康之 ( 独 ) 科学技術振興機構 ERATO 湊離散構造処理系プロジェクト shirai@erato.ist.hokudai.ac.jp 1 講義内容自己紹介その他 (11 月 7 日 ) 手法編 (11 月 7~8 日 ) (1-1) はじめに ( 全体概要 ) (1-2) 頻出パタンマイニングとその周辺 (1-3) 決定木分析法とその周辺