決定木分類

直感 #

「気温が 25 ℃ より高いか」「湿度が 60 % を超えるか」と 2 つの質問に答えるだけで、その日にアイスが売れるかどうかを言い当てる。決定木がやっているのは、この種の「はい／いいえ」の質問を訓練データから自動で選び、並べることです。各質問は 1 つの特徴量と 1 つのしきい値からなるので、散布図の上では縦か横の 1 本の直線に対応します。質問を重ねるほど平面は細かい長方形に分かれ、訓練データの 100 点をすべて正しく塗り分けることもできますが、そのときには外れ値 1 点のために小さな長方形が 1 つ作られる、いわゆる過学習が起きています。

何が起きているか（ステップで見る） #

決定木が「学習する」とは、散布図の平面を縦か横の直線で順に切り分けていくことです。深さを 1 つ増やすごとに、各領域の中で不純度がいちばん下がる切り方を 1 本選びます。

見るポイント：切る線は必ず軸に平行で、斜めの境界が必要なデータでは階段状に何度も切ることになります。深さ 1 → 2 で誤分類が大きく減る一方、深さ 3 ではわずかしか減りません。ここから先はノイズを覚え始める過学習の領域で、max_depth や min_samples_leaf はこの深さを止めるためのパラメータです。各領域の色はその中の多数派クラスを表し、新しい点の予測は「どの領域に落ちるか」だけで決まります。

式で書くと何を最小にしているか #

「混ざり具合」を数値にしたものが不純度です。ノード \(t\) にクラス \(k\) のサンプルが割合 \(p_k\) で含まれるとき、ジニ不純度は

で定義されます。2 クラスが 50 % ずつなら 0.5、片方だけなら 0 になり、ステップ図で 1 色に塗られた領域はこの値が 0 の領域です。情報理論から来たエントロピー

も同じ目的で使え、criterion="entropy" で切り替えられます。親ノード \(t\) を特徴量 \(x_j\) としきい値 \(s\) で左右に分割したとき、不純度減少量

が最大になる \((j, s)\) の組み合わせを選びます。ここで \(I(\cdot)\) は選んだ不純度指標、\(n_t\) はノード \(t\) のサンプル数で、左右の不純度はサンプル数で重みづけされます。候補のしきい値は、各特徴量の隣り合う観測値の中点なので、100 点・2 特徴量なら最大でも約 200 通りの総当たりで済みます。これを葉ノードが純粋になるか、停止条件に当たるまで繰り返します。

Pythonを用いた実験や説明 #

次のコードは make_classification で 2 クラス・100 点の人工データを作り、深さ制限なしの DecisionTreeClassifier を学習して、平面上の決定境界を contourf で塗り分けます。続く 2 つ目のブロックでは、同じ木を plot_tree で描き、塗り分けの 1 本 1 本がどの分岐に対応するかを確かめます。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_classification
from sklearn.tree import DecisionTreeClassifier, plot_tree

n_classes = 2
X, y = make_classification(
    n_samples=100,
    n_features=2,
    n_redundant=0,
    n_informative=2,
    random_state=2,
    n_classes=n_classes,
    n_clusters_per_class=1,
)

clf = DecisionTreeClassifier(criterion="gini", random_state=0).fit(X, y)

# メッシュグリッドで決定境界を可視化
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(
    np.arange(x_min, x_max, 0.1),
    np.arange(y_min, y_max, 0.1),
)
Z = clf.predict(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)

plt.figure(figsize=(8, 8))
plt.contourf(xx, yy, Z, cmap=plt.cm.Pastel1, alpha=0.6)
plt.xlabel("x1")
plt.ylabel("x2")

for i, color, label_name in zip(range(n_classes), ["r", "b"], ["A", "B"]):
    idx = np.where(y == i)
    plt.scatter(X[idx, 0], X[idx, 1], c=color, label=label_name, edgecolor="k")

plt.legend()
plt.title("決定木による決定境界")
plt.show()

1
2
3

plt.figure(figsize=(12, 12))
plot_tree(clf, filled=True, feature_names=["x1", "x2"], class_names=["A", "B"])
plt.show()

実行結果の読み方 #

1 枚目の図では、赤と青の点が背景の 2 色の長方形で完全に塗り分けられています。2 枚目の木を根から読むと、最初の分岐が 1 枚目でいちばん長い直線に対応し、そこから下の分岐がより小さな長方形を切り出しています。各ノードに書かれた gini が 0.0 の葉は 1 色だけの領域です。samples = 1 や 2 の葉が見つかれば、その葉のために作られた小さな長方形が過学習の正体で、min_samples_leaf=5 を指定すればそれらは消えます。

最大深さと決定境界 #

スライダーで max_depth を 1 から増やしていくと、長方形の数が増えて境界が訓練データの 1 点 1 点に合わせた形へ変わっていく、過学習の様子を確認できます。

まとめ #

決定木分類器は、特徴量としきい値による「はい／いいえ」の質問を根から葉へ並べ、葉の多数派クラスを返すモデルです。各分岐は不純度減少量 \(\Delta I\) が最大になる 1 本の切り方です。散布図の上では必ず軸に平行な直線として現れ、深さ制限なしの木は訓練データを 100 % 当てる代わりにノイズ 1 点ごとに小さな長方形を作ります。そのため max_depth=3〜5 や min_samples_leaf で成長を止めるのが基本です。1 本の木の不安定さが問題になるときは、ランダムフォレスト のように多数の木を平均する手法へ進みます。

参考文献 #