決定木(Decision Tree)
決定木とは教師あり学習に使われるアルゴリズムです。与えられたデータを木のように枝分けしていくことで、予測やデータの要約を行います。回帰と分類両方に使用できる学習モデルです。
下の図は、データを「犬」「人」「鳥」「蚊」に分類するための決定木を表しています。
各枝では特徴量を利用してデータを分類してきます。最後の葉になる部分で、分類結果が決まります。
ここで、各枝を伸ばす際に考えるポイントとして
- どの特徴量をどのくらい使うか
- どこまで深く木を伸ばすか
が重要となってきます。
まず１を判断する基準に情報利得 (Information Gain)という基準が利用されます。
情報利得 (Information Gain)
情報利得は簡単に言うと、子ノードが親ノードと比べてどれくらい綺麗にデータを分類できたかを示す値です。もしくは、各ノードで標準偏差がどのくらい減るかを表した値です。どれくらいこの情報利得を計算するのに、不純度と呼ばれる値が使われます。不純度にはいくつか種類がありますが、今回は最も代表的なGiniとEntropyを紹介します。
Gini
Gini は次の式で表されます。
G = 1 - \sum_{n = 1}^{classes}P(i|t)^2
各ノードで、データがあるクラスに分類される確率が高いほどGiniは0に近ずくことがわかります。仮にクラスが１つしかない場合、Giniは0となります。逆に、全てのサンプルが異なるクラスに属す時、Giniは1に近似します。
更に、各ノードでGiniからInformation Gain (IG)を計算します。
IG = G(parent) - \sum_{children}\frac{N_j}{N}G(child_j)
ここでは、親枝のGiniと子枝のGiniの加重平均(各クラスに含まれるデータの数の割合)の差を情報利得として取得します。
Entropy
Entropyは次の式で表されます。
E = - \sum_{i = 1}^{N}P(i|t)*log(P(i|t))
ここで、P(i|t)が0.5に近いほど(1か0か分からない；分類できない)ほどエントロピーは高くなることがわかります。反対にP(i|t)が0か1の時、エントロピーは０となります。
IG = E(parent) - \sum_{children}\frac{N_j}{N}E(child_j)
先程と同様、親枝の交差Entropyと子枝の交差Entropyの加重平均の差を情報利得として取得します。
この情報利得が大きい分割方法が各ノードで選択されます。
Gini と Entropy の使い分け
Gigiは回帰問題に向いており、Entropyは分類問題に向いています。
木の深さ
決定木の木の深さが深いほど、学習データにフィットしたモデルが選択されます。実際、最後の子ノードのデータ数が１の時、全てのデータを完璧にクラス分けすることができます。しかし、これではサンプルデータに過学習してしまい、モデルの意味がなくなってしまいます。なので、学習モデルを作る際には、木の深さに制限をつける必要があります。skitlearnでは、木の深さはパラメターで設定されます。
Scikit-learn 決定木
回帰
from sklearn.tree import DecisionTreeRegressor
clf = DecisionTreeRegressor(criterion="entropy", max_depth=3)
clf = clf.fit(X_train,y_train)
y_pred = clf.predict(X_test)
分類
from sklearn.tree import DecisionTreeClassifier
clf = DecisionTreeClassifier(criterion="entropy", max_depth=3)
clf = clf.fit(X_train,y_train)
y_pred = clf.predict(X_test)
決定木のパラメター
| パラメタ- | 概要 | オプション | デフォルト |
|---|---|---|---|
| criterion | 分割基準 | "gini", "entropy" | "gini" |
| splitter | 分割選択の戦略 | "best", "random" | "best" |
| max_depth | 木の最深深さ | int | None |
| min_samples_split | 分割後ノードの最小サンプルサイズ(小さいと過学習傾向になる) | int(サンプル数)/float(全サンプルに対する割合) | 2 |
| min_samples_leaf | 葉(最終ノード)に必要な最小サンプルサイズ(小さいと過学習傾向になる) | int/float | 2 |
| max_features | 分割する上で使う特徴量の数(大きいほど過学習の傾向) | int/float, auto, log2 | None |
| class_weight | クラスの重み | "balanced", none | none |
| presort | データの事前の並べ替え(データサイズによって計算速度が変わる) | bool | False |
| min_impurity_decrease | 不純度にリミットをかけノードの伸びを制御する | float | 0. |
決定木の長所と短所
長所
- 容易に可視化と要約ができる。
- データが線形パターンでない場合にも利用できる。
- 正規化の前処理が不要。
短所
- 外れ値の影響を受けやすい。
- 小さい分散でも、結果が大きく変わってしまう。
- 計算が複雑性、時間計算量が多くなる。