決定木

特性

決定木の決定境界は直行する →訓練セットの回転によって結果に大きな影響 →PCA(訓練データをより良い向きに変えられることが多い)である程度軽減が可能

訓練データのスケーリングやセンタリングに影響を受けない

不純度

ジニ係数

$$ G_{i} = 1 - \sum_{k=1}^{n}p^{2}{i, k} $$ - p{i, k}は、i番目のノードの訓練インスタンス中のクラスkのインスタンスの割合

エントロピー

\[ H_{i} = - \sum_{\substack{k=1\\p_{i, k}≠0}}^{n}p_{i, k}log_{2}(p_{i, k}) \]

コスト関数 (CART分類用)

$$ J(k, t_{k}) = \frac{m_{left}}{m}G_{left} + \frac{m_{right}}{m}G_{right} $$ - G_{left/right}は、左右サブセットの不純度 - m_{left/right}は、左右サブセットのインスタンス数

決定木は分類・回帰どちらのタスクも実行可能

コスト関数 (CART回帰用)

\[ J(k, t_{k}) = \frac{m_{left}}{m}MSE_{left} + \frac{M_{right}}{m}MSE_{right} $$ $$ where \begin{cases} MSE_{node} = \sum_{i\in node}(\hat y_{node} - y^{(i)})^2 \\ \hat y_{node} = \frac{1}{m_{node}}\sum_{i\in node}\hat y^{(i)} \end{cases} \]

計算量

\[O(n \times m\log (m)\]