データサイエンス設計マニュアル

11.2 決定木分類器 329

11.2.1 決定木の構築方法

決定

木はトップダウンで作られる。まず、n 個の特徴を持ち、m 種類のクラス C

1

, . . . , C

m

の中のいずれ

かをラベルとする訓練データの集まりを用意する。決定木の個々のノードには、条件式、つまり与えられた

特徴から作られた条件式が含まれている。

離散的な値の集合 v

i

に基づく特徴は、「特徴 x

i

= v

ij

か？」といった等価テストを使えば簡単に条件式に

変換できる。そのため、x

i

から、|v

i

| 種類の条件式が作れる。数値特徴は、「特徴 x

i

≧ t か？」のようにし

きい値 t を追加すれば条件式に変換できる。しきい値 t として使えそうな値の集合は、訓練セット内に含ま

れる x

i

の観測値の間にある差分によって定義される。x

i

の観測値の集合が (10, 11, 11, 14, 20) なら、しき

い値は t ∈ (10, 11, 14) または t ∈ (10.5, 12.5, 17) になる。どちらのしきい値でも、観測値を同じように分

割できるが、訓練データに登場していない将来の値に対する一般化のことを考えれば、個々の差分の中間を

使った方がよさそうだ。

個々の条件式は、訓練データの集合 S の分割にどの程度効果的かという基準に基づいて評価できなけれ

ばならない。理想的な条件 p は、S を純粋に分割するもの、つまりクラスラベルが重なり合わないようにす

るものである。この理想の分割では、クラス C

i

に属する S のすべての要素は、木の片 ...