決定木(Decision Tree)

決定木とは教師あり学習に使われるアルゴリズムです。与えられたデータを木のように枝分けしていくことで、予測やデータの要約を行います。回帰と分類両方に使用できる学習モデルです。

下の図は、データを「犬」「人」「鳥」「蚊」に分類するための決定木を表しています。
各枝では特徴量を利用してデータを分類してきます。最後の葉になる部分で、分類結果が決まります。

ここで、各枝を伸ばす際に考えるポイントとして

1. どの特徴量をどのくらい使うか
2. どこまで深く木を伸ばすか

が重要となってきます。

まず１を判断する基準に情報利得 (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)

決定木のパラメター

決定木の長所と短所

長所

• 容易に可視化と要約ができる。
• データが線形パターンでない場合にも利用できる。
• 正規化の前処理が不要。

短所

• 外れ値の影響を受けやすい。
• 小さい分散でも、結果が大きく変わってしまう。
• 計算が複雑性、時間計算量が多くなる。