(決定木の例1: 卒業の判定)
(決定木の例2: みかんの上/並の判定)
(トレーニングデータの例)
このトレーニングデータと整合する決定木は,上記の例2以外にも以下のよう なものがある.
(決定木の例3)
(決定木の例4)
n I(P(x1), ..., P(xn)) = Σ -P(xi)logP(xi) i=1
I(p/(p+n), n/(p+n)) = -(p/(p+n))log(p/(p+n)) - (n/(p+n))log(n/(p+n))
任意の属性Aはトレーニングデー
タ E を A に対する値によって部分集合 E1, ..., Ev
に分割する.ここで,A は v 個の異なった値を持つ.各部分集合
Ei は pi 個の正例と ni 個の負例を持つ.
もし次にこの枝に進むと,質問に答えるためにさらに
I(pi/(pi+ ni),
ni/(pi+ ni))ビットの情報量を必要とす
る.
ランダムに抽出された例は,その属性の i 番目の値を取る確率は
(pi + ni)/(p + n) であるので,属性 A のテスト後,
平均すれば例を分類するのに
v Remainder(A) = Σ((pi+ni)/(p+n))*I(pi/(pi+ni), ni/(pi+ni)) i=1ビットの情報量を必要とする.属性テストによる情報量とテスト後の情報量の 差(ゲイン)は,以下のように定義される.
Gain(A) = I(p/(p+n),n/(p+n)) - Remainder(A)
(レストランの例におけるID3による学習により得られ た決定木)