この記事はアドベントカレンダー 23 日目の記事になります．
はじめに
担当しているプロダクトの機能で決定木モデルを利用したデータ分析を導入しました．決定木モデルについての概要は把握していましたが，この機会に改めて調べ直したので，それを紹介します．
決定木モデルとは
決定木（decision tree）モデルはその名前の通り，分析対象とするデータを木構造に分割することで，分類や回帰を行う予測モデルです．決定木モデルの内部ノードでは特徴量に基づく条件判定を行い，最終的に到達するリーフノードが予測結果を表します．
決定木モデルの学習について
Python の scikit-learn に実装されている学習アルゴリズムは，最適化された CART（Classification and Regression Trees）アルゴリズムに基づいており，二分木構造の決定木モデルを学習します．
CART では，学習用ベクトル $x_i\in\mathbb{R}^n, (i=1,\dots,l)$ とそれに対応するラベル $y_i\in\mathcal{Y}, (i=1,\dots,l)$ が与えられているとします．ここで，分類問題の場合 $\mathcal{Y}=\{1,\dots,K\}$，回帰問題の場合 $\mathcal{Y}=\mathbb{R}$ となります．特徴量空間を繰り返し分割することにより，同一のラベル，もしくは類似した目標値を持つデータが同じ領域に属するように分割することを目標とします．
ノード $m$ で，$n_m$ 個のデータの集合を $Q_m$ として表すと，各分割候補 $\theta=(j,t_m)$ でデータを以下のように $Q_m^{left}(\theta)$ と $Q_m^{right}(\theta)$ の部分集合に分割できます．ここで，$j$ は特徴量のインデックス，$t_m$ はノード $m$ における分割閾値を表します．
Q_m^{left}(\theta)=\{(x,y)\in Q_m|x_j\leq t_m\}
Q_m^{right}(\theta)=Q_m\setminus Q_m^{left}(\theta)
各分割候補 $\theta$ の評価 $G(Q_m,\theta)$ は以下の不純度・損失関数 $H()$ で計算されます．scikit-learn では，分類用決定木 DecisionTreeClassifier はジニ関数を，回帰用決定木 DecisionTreeRegressor は平均二乗誤差関数がデフォルトとして設定されています．
G(Q_m,\theta)=\frac{n_m^{left}}{n_m}H(Q_m^{left}(\theta))+\frac{n_m^{right}}{n_m}H(Q_m^{right}(\theta))
最終的に選択される分割候補 $\theta^\ast$ は，評価式 $G(Q_m,\theta)$ が最小となるものです．このとき，分割候補の探索方法としては，各ノードにおける貪欲的全探索（local greedy exhaustive search）や，各特徴量の値の範囲からランダムにサンプリングした値を用いる方法があります．
\theta^\ast=\arg\min_\theta G(Q_m,\theta)
過学習を抑えるため，分割の終了条件としては以下のものがあります：
- 木の深さが最大深度
max_depthに到達した場合 - ノード $m$ に含まれるサンプル数 $n_m$ が，分割に必要な最小サンプル数
min_samples_splitを満たさない場合 - 分割による不純度・損失の減少値が閾値
min_impurity_decrease未満の場合
決定木モデルを用いたアンサンブル学習について
決定木モデルを用いたアンサンブル学習の一つにランダムフォレスト（random forest）があります．複数の決定木モデルに対して異なるランダム性を導入し，それらの予測を多数決・平均化することで，単一の決定木モデルの予測結果よりも分散を低減することができます．ランダムフォレストでは，ランダム性の導入として，bagging (bootstrap aggregating) による学習用データのブートストラップサンプリングによるランダム化と，attribute sampling による各ノードで使用する特徴量をランダムに制限する方法があります．
ブートストラップサンプリングでは，元データ数 $N$ とし，$N$ が十分に大きい場合，あるデータが一度もサンプリングされない確率が，約 36.8% になります．
(1-\frac{1}{N})^N\approx e^{-1}\approx 0.368また，決定木モデルの学習で利用されなかったデータを予測した際の平均誤差（out-of-bag error）は，ランダムフォレストで利用される決定木数の増加に応じて低減されることも知られています．
もう一つのアンサンブル学習として，決定木モデルを弱学習器（weak learner）として利用するブースティング（Boosting）系のモデルがあります．この手法では，各ステップ $i$ で現在のモデルの損失関数の負の勾配（疑似残差）を学習する決定木モデル $f_i$ を追加することで，強学習器（strong learner）であるアンサンブル全体としての予測性能 $F_i$ を逐次的に向上させていきます．ここで，$\nu$ は収縮（shrinkage）を表し，強学習器の過学習を制御する値になります．この反復処理は，あらかじめ定めた反復回数やモデルの性能に基づいて終了します．
F_{i+1}=F_i-\nu f_i,\ F_0=0
まとめ
決定木モデルは，特徴量空間を局所的に分割することで分類・回帰を行う予測モデルです．単体では過学習しやすい一方で，その学習・分割の仕組みを理解することで，分散低減を目的としたランダムフォレストや，予測誤差を逐次的に補正するブースティング系モデルが，どのような考え方に基づいて構築されているのかを見通しよく理解できるようになると思います！