「決定木」の概要

機械学習の、教師あり学習に使われる手法
分類問題では「分類木」、回帰問題では「回帰木」と呼ばれる
色々な質問に対して、Yes, Noを繰り返していくことで値を予測する
- 教師データから、精度良く予測できる質問を作っていく
- 新たなデータに対して↑で作った質問を繰り返し、値を予測する
大体、↓こういうのと同じイメージ（引用元：https://www.digipot.net/?p=1332 )

長所・短所

長所

作られたモデルの意味を理解しやすく、ツリーを可視化できる。
- 決定木はwhite box modelとなる。black box model（ニューラルネットワークなど）はモデルの解釈が難しい。
標準化、ダミー変数作成などの前処理が不要。
- カテゴリーデータも、そのまま使える。
計算コストが低い。
多項分類を扱える。（二項分類と多項分類）
統計検定が可能のため信頼性を説明しやすい。
仮定が真のモデルから多少ズレていても、うまくいく。

短所

過学習しやすい。そのため、葉の数や深さの最大値を設定しておく必要がある。
少しのデータの違いで全く異なる木になる（不安定）。アンサンブル学習を行うことで、この問題は軽減される。
「本当に最適な決定木」の模索は困難。この問題も特徴量とサンプルをランダムに入れ替えてアンサンブル学習を行うことで、軽減できる。最適な決定木を見つけることはNP完全問題であるため（と書いてあったが、個人的に「NP完全問題」を理解できてないです。詳しい人居たら教えて・・・）
学習困難な問題がある。（XOR問題、パリティゲーム、multiplexer problems）（コレも個人的はよく理解できてない・・・。詳しい人居たら教えて・・・）
不均衡データからは偏った木が作成される。そのため、モデル作成前にデータのバランス調整するとよい。

サンプル

分類

winequality-red( http://archive.ics.uci.edu/ml/machine-learning-databases/wine-quality のwinequality-red.csv)に適用した例

簡単に図を作るため、↓を行っている
- quality（=目的変数）が3と8のものだけ考える
- 説明変数は"volatile acidity"と"alcohol"の2つだけで考える
点 = 実際のデータ（教師データ）
新しいデータに対しては、境界線のどちらになるかで色を判別する
図を作ったコードはココ( https://github.com/kzy611/qiita/blob/master/DecisionTree_winequality-red.ipynb )

教師データから決定木を作るロジック

「教師データから、精度良く予測できる質問を作っていく」ってどうやって作るの？、という話

分類問題：不純度（Impurity）を下げていく

不純度：識別の状態を表す指標。不純度が高い = 識別ができていない

不純度の指標に「エントロピー」を使う場合

エントロピー(entropy)の定義式は以下

H = - \sum_{i=1}^{n} ( p_i \log_2 p_i )

$n$：分類するカテゴリの数
$p_i$：iのカテゴリになる確率

例として、AとBを分類する問題を考える。（この場合$n=2$となる）
まず、AとBの確率が半々(50%ずつ)の場合を考えると、エントロピーは

\begin{align}
H &= (- p_A \log_2 p_A) + (- p_B \log_2 p_B) \\
&= (-0.5 \log_2 0.5) + (-0.5 \log_2 0.5) \\
&= 1 \\
\end{align}

となる。二項分類（$n=2$）の場合、横軸に$p$をとるとエンタルピーは以下のようになり、$p=0.5$（=どっちになるか半々）のとき最大となる。

ココで、最初は「AとBの数が100個ずつ」のものが、ある質問のYes、Noで「Aが80個、Bが40個」「Aが20個、Bが60個」というグループに分かれるとする。
その場合、グループ分けされた後のエンタルピーは

「Aが80個、Bが40個」のエンタルピー：$(- p_A \log_2 p_A) + (- p_B \log_2 p_B) = (- \frac{80}{120} \log_2 \frac{80}{120}) + (- \frac{40}{120} \log_2 \frac{40}{120})$
「Aが20個、Bが60個」のエンタルピー：$(- p_A \log_2 p_A) + (- p_B \log_2 p_B) = (- \frac{20}{80} \log_2 \frac{20}{80}) + (- \frac{60}{80} \log_2 \frac{60}{80})$

を、全体に対する割合を掛けながら足しあわせて

\begin{align}
H = &\frac{120}{200} \bigl( (- \frac{80}{120} \log_2 \frac{80}{120}) + (- \frac{40}{120} \log_2 \frac{40}{120}) \bigr) \\
&+ \frac{80}{200} \bigl( (- \frac{20}{80} \log_2 \frac{20}{80}) + (- \frac{60}{80} \log_2 \frac{60}{80}) \bigr) \\
= & 0.875
\end{align}

となり、このグループ分けによって最初のエントロピー（半々=1）よりも0.125小さくなる。
この差（=グループ分け前後のエントロピーの減少量）を**情報利得(information gain)**といい、コレが大きくなるような特徴量・閾値を使って分岐条件を作っていく

不純度の指標に「ジニ不純度」を使う場合

ジニ不純度(Gini impurity)の定義式は以下

H = \sum_{i=1}^{n} p_i (1 - p_i)

$n$：分類するカテゴリの数
$p_i$：iのカテゴリになる確率

↑のエンタルピーと同様に、AとBを分類する問題を考える。（この場合$n=2$となる）
まず、AとBの確率が半々(50%ずつ)の場合を考えると、ジニ不純度は

\begin{align}
H &= p_A (1 - p_A) + p_B (1 - p_B) \\
&= 0.5 (1 - 0.5) + 0.5 (1 - 0.5) \\
&= 0.5 \\
\end{align}

となる。二項分類（$n=2$）の場合、横軸に$p$をとるとジニ不純度は以下のようになり、こちらも$p=0.5$（=どっちになるか半々）のとき最大となる。

エンタルピーのときと同様に、最初は「AとBの数が100個ずつ」のものが、ある質問のYes、Noで「Aが80個、Bが40個」「Aが20個、Bが60個」というグループに分かれるとする。
その場合、グループ分けされた後のジニ不純度は

「Aが80個、Bが40個」のジニ不純度：$p_A (1 - p_A) + p_B (1 - p_B) = \frac{80}{120} (1 - \frac{80}{120}) + \frac{40}{120} (1 - \frac{40}{120})$
「Aが20個、Bが60個」のジニ不純度：$p_A (1 - p_A) + p_B (1 - p_B) = \frac{20}{80} (1 - \frac{20}{80}) + \frac{60}{80} (1 - \frac{60}{80})$

を、全体に対する割合を掛けながら足しあわせて

\begin{align}
H = &\frac{120}{200} \bigl( \frac{80}{120} (1 - \frac{80}{120}) + \frac{40}{120} (1 - \frac{40}{120}) \bigr) \\
&+ \frac{80}{200} \bigl( \frac{20}{80} (1 - \frac{20}{80}) + \frac{60}{80} (1 - \frac{60}{80}) \bigr) \\
= & 0.417
\end{align}

となり、このグループ分けによって最初のジニ不純度（半々=0.5）よりも0.083小さくなる。
コレを**情報利得(information gain)**として扱う。

不純度の指標に「分類誤差（誤分類率）」を使う場合

分類誤差（誤分類率、classification error、Misclassification）の定義式は以下

H = 1 - max(p_i)

$n$：分類するカテゴリの数
$p_i$：iのカテゴリになる確率

計算は割愛

回帰問題：誤差を減らしていく

（そのうち書くかも）