決定木(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.

決定木の長所と短所

長所

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

短所

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