データ工学特論

データ工学特論
第四回
木村昌臣
本日の話題


決定木
遺伝的アルゴリズム(GA)
決定木


学習用データ内のレコード
を複数のサブセットに分割
し、その結果をもとに、新し
いレコードの属性を予測す
る手法
目的志向的データマイニン
グ
買った?
年齢
○
21歳
○
25歳
○
30歳
×
29歳
×
50歳
×
60歳
○
３
×
３
年齢≦30
年齢＞30
○
３
○
０
×
１
×
２
決定木のイメージ：
赤い色と青い色を分けてください（問題）
Y:収入
商品を買った人
商品を買わなかった人
X:年齢
決定木のイメージ：
赤い色と青い色を分ける
X > aであれば
すべて青
Y:収入
a
X:年齢
決定木のイメージ：
赤い色と青い色を分ける
Y:収入
b
X < a かつ Y < b
であれば全て赤
a
X:年齢
決定木のイメージ：
赤い色と青い色を分ける
c<X<a
かつ Y>b
であれば全て赤
Y:収入
b
X < c かつ Y > b
であれば全て青
c
a
X:年齢
決定木のイメージ：
赤い色と青い色を分ける話を木の形で表現
どんな条件で
赤と青が分離できるか
枝をたどれば
一目瞭然
全体
X a
X a
全て青
Y b
Y b
全て赤
X c
全て赤
X c
全て赤
ただし・・・

現実のデータでは、これほど綺麗な分類が
できないことが多い


切り口が軸方向に沿っていない場合、100%赤
だけ・青だけというようなわけ方はできない
ただし、なるべく赤と青を分離したい
赤が多い・青が多いなどとなるべく
色に偏りがある切り口を選びたい
偏りの指標

Giniインデックス
C
GINI  1   p
i 1

2
i
エントロピー
C
S   pi log pi
i 1
C: カテゴリの数
pi: i番目のカテゴリに属する割合（確率）
Giniインデックス(1)
C
C
i 1
i 1 j i
GINI  1   pi2   pi p j
独立に動く二匹の犬が同じ場所にいない確率
（もし、確率に偏りがあれば、あるpiが1に近づき、二匹とも同じ
場所にいることが多くなり、インデックスは0に近づく）
カテゴリ1
カテゴリ2
カテゴリ3
Giniインデックス(2)
C
GINI  1   p  1  (0  1  0 )  0
i 1
2
i
2
2
2
p1  0, p2  1, p3  0
カテゴリ1
カテゴリ2
カテゴリ3
Giniインデックス(3)
2
2
2
5
1 1 1
GINI  1   p  1  (        )   0
8
 4  2  4
i 1
C
2
i
1
1
1
p1  , p2  , p3 
4
2
4
カテゴリ1
カテゴリ2
カテゴリ3
決定木の分岐(Giniインデックス)

分岐前と分岐後のGiniインデックスの値の差が最
大になるように分岐条件を決定
n( j )
GINI  GINI  
GINI ( j )
N
j
GINI  1   p
2
i
i
N
p1
GINI
p2
n
p1(1)
( j)
 
 1  p
( j) 2
i
i
(1)
p2(1)
p1( 2)
n ( 2)
p2( 2)
エントロピー(1)
C
C
C
1
S   pi log2 pi   pi log2
  pi I i
pi i 1
i 1
i 1
I=log21/p は確率pが持つ情報量
例) p=1/2 ではlog22=1 bit
p=1/4 ではlog24=2 bit など
確率が均等なら、この情報量は状態の数を表す
ビット数に等しくなる
p=1/N、I=log21/p = log2N (N=2I)
ただし、各確率が均等である保証はないので、この情報量の平
均をとったものがエントロピーとなる（平均情報量）。
エントロピー(2)
C
S   pi log2 pi  0 log2 0  1log2 1  0 log2 0  0
i 1
p1  0, p2  1, p3  0
カテゴリ1
カテゴリ2
カテゴリ3
(ただし、x logx →0 (x→0)のため、0log0=0と定義する)
エントロピー(3)
C
1
1
1
3
S   pi log2 pi  log2 4  log2 2  log2 4   0
4
2
4
2
i 1
1
1
1
p1  , p2  , p3 
4
2
4
カテゴリ1
カテゴリ2
カテゴリ3
決定木の分岐(エントロピー)

分岐前と分岐後のエントロピーの差が最大になる
ように分岐条件を決定
n( j ) ( j )
S  S  
S
N
j
S   pi logpi
i
S ( j )   pi( j ) logpi( j )
N
p1
n
p2
p1(1)
i
(1)
p2(1)
n ( 2)
p1( 2)
p2( 2)
C5.0

説明変数の値（範囲）による決定木




データは複数(二つとは限らない)に分割される
木は深さ方向より横方向に成長する傾向がある
（長所）データが二つ以上に分けやすいときに自
然な分岐を実現する
（短所）分岐での枝分かれの数が多すぎると枝
に属するデータが急激に少なくなる


学習時の信頼性が低下する場合がある
分岐にはエントロピーを利用
CART(C&RT)

2進木(binary tree)による決定木





分岐ではデータは必ず二つに分ける
木は横方向より深さ方向に成長する傾向がある
（長所）分岐での枝分かれの数が2と決まってい
るので枝に属するデータが急激に少なくなること
がない
（短所）二つ以上に分割すべきデータが対象で
あるとき、不自然に複雑な分岐が続くことがある
分岐にはGiniインデックスやエントロピーを
利用
枝刈り

詳細に分岐しすぎると学習用データに対してオー
バーフィットしてしまう可能性がある



枝に近づくにつれて、該当する学習用データが減少
そのため、たまたま選ばれた学習用データの影響を受
けやすい（一般に成り立つルールが得られない可能性
あり）
基準を設けて細かすぎる枝を刈る


誤分類率+葉ノードの数が最小になるように刈る
学習用データと同じ母集団から収集された別データをテ
ストデータとして利用し、その誤分類率が最小になるよう
枝を刈る
など
【復習】モデル作成時の注意点（２）

オーバーフィット



学習用データや特定の入力データの特異性を
とりこんでしまっている状態。
他の一般データにモデルを応用できない。
アンダーフィット

入力データから意味のある情報を抽出しそこ
ねている状態。


重要な意味をもつはずの入力データ項目を抜
かしてしまっているなどが原因
意味のあるモデルを得ることができない。
決定木の長所・短所

長所



結果やその導出根拠がわかりやすい。
連続変数とカテゴリ変数を両方利用できる
短所


説明変数の軸に垂直に分類しにくいデータでは
精度が低い
C5.0などではノードあたりの分岐が多すぎると
各分岐に該当するサンプルデータが少なくなり
精度を低下させる可能性がある
遺伝的アルゴリズム(GA)




遺伝子のメカニズムを
モデル化
評価関数の最適値を求
める
データの交差・突然変
異を用いて世代を下る
につれて解を得るアル
ゴリズム
目的思考的データマイ
ニング
GTACCGGA
突然変異
AGGCCTAA
GTACCTGA
交差
GTACCTAA
AGGCCGGA
☆実際の計算ではATGCではなくて
0/1などの数値列を扱う
次の関数の極値を求める方法は？
x
x
y
(1 
)
256
256
0  x  256
次の関数の極値を求める方法は？
x
256
y
sin
256
x
0  x  256
遺伝的アルゴリズム(1)
複雑な（そうでない場合も）関数の極値を得
る方法。以下の手順を繰り返す。
1. 入力値(x)をビット表現し、遺伝子に見立て、
適応度（=関数の値）の高いものをキープす
る

 x= [17]10=[000010001]2 → y=0.062
 x= [80]10=[001010000]2 → y=0.215 (キープ)
 x=[255]10=[011111111]2 → y=0.003
遺伝的アルゴリズム(2)
2. それぞれの個体（xの値）間で、その一部の
ビットをスワップする[交叉]
[000010001]2
[011111111]2
[000011111]2
[011110001]2
y=0.106
y=0.055
(出来上がった新しい個体のなかには適応度が上がるものがある
可能性がある)
3. 1.や2.で得られた個体の一部のビットを反転
させる[突然変異]
[001010000]2
[001110000]2
y=0.246
遺伝的アルゴリズム(3)
4. 交叉や突然変異で得られた新しい個体xを
入力とし、1.～3.を適応度（=関数の値）が改
善されなくなるまで繰り返す。
遺伝的アルゴリズムのグラフ的理解
初期値
y
1
適用度が高い
ので残す
x
0
17
80
128
255 256
遺伝的アルゴリズムのグラフ的理解
交叉
y
1
•二つのxを掛け合わせることにより
適用度が改善される可能性がある
•特に適応度が高い遺伝子を掛け
合わせると適応度が高い子供が
できると期待できる
(下位ビットの調整に相当)
256
0
17
31
80
128
241
255
x
遺伝的アルゴリズムのグラフ的理解
突然変異
y
1
遺伝子のもつ値を大きく振ること
により適応度（関数）の
local maximumに収束するのを防ぐ
x
0
31
80
112
128
241
256
スキーマ定理

スキーマ

ワイルドカード「*」には0または1に入り、それ以
外の部分（固定位置）が共通しているものをまと
めたもの


(例) [1101]と[1011]はスキーマ[1**1]に属する。
スキーマ定理

固定位置の数が少なく、適応度が高いスキーマ
が繁栄する

固定位置の数がすくないと交叉の影響を受けにくい
遺伝的アルゴリズムの長所・短所

長所


自然界の遺伝の仕組み（淘汰・交叉・突然変異）との類
推がつき、わかりやすい
適用度（関数）が定義できれば、利用可能。


最適化問題の解法の強力なツール
短所


データをすべて1と0のバイナリ列に変換する必要がある
大域解を得ることを考慮（突然変異）されたアルゴリズム
であるが、必ずしも大域解が得られない場合がある

Download Report