- データを特徴量空間上で矩形分割するモデル
- 分割は「ある特徴量がある値と一致するか」「ある特徴量がある値より大きいか小さい」などのルールに従って行う
- 分割ルール（分割対象となる特徴量と閾値の組）をどう見つけるかが大切
- 情報利得を目的関数とし、これを最大化する分割ルールを見つけることで、最適な決定木を構築
- 情報利得とは、親ノードでの不純度から子ノードの不純度の加重平均を引いたもの
- 情報利得が大きいことは、親ノードに比べて子ノード内のデータが「均一」になることを意味
不純度の種類
- 分類タスクだとジニ不純度やlogloss、回帰タスクだと平均誤差がよく用いられる
- （texで数式かきてえええ）
目的関数をどう計算するか
- 理想的な方法
- 考えられる全ての決定木をあらかじめ構築
- それら決定木の目的関数の値をすべて計算
- 目的関数が最大化される決定木を採用
- 特徴量の数やデータのサンプルサイズが大きくなると、この方法は現実的な時間で解けきれない
- 代替案として貪欲法を使う
- 決定木の根から一段階だけ葉を生やす
- 目的関数を計算して、最適な特徴量とルールの組を探す
- 2の決定木を採用して、ほかの決定木は捨てる
- さらに一段階だけ葉を生やす
- 2~4を繰り返す
- 貪欲法は全ての決定木をあらかじめ構築するのはあきらめて、逐次的に最適な決定木を見つけていこうやという方法
- 理想的な方法と貪欲法でそれぞれ求まる決定木は一致する保証がない（らしい）
- まあでも、現実的に解けるからええやんっていうスタンスなのかな？
