決定木分類（高校生向け）

こんな場面を想像してみよう #

部活の顧問の先生は、毎朝「今日は外で練習（A）か、体育館で練習（B）か」を決めています。手がかりは天気予報の 降水確率（%） と 気温（℃） の 2 つで、過去 100 日分の記録を散布図にすると、A の日と B の日がなんとなく分かれて見えます。

先生の頭の中を言葉にすると、「降水確率が 40 % より高ければ体育館。40 % 以下でも気温が 5 ℃ 以下なら体育館。それ以外は外」のような 2〜3 個の質問の連続のはずです。この質問の連続を 100 日分のデータから自動で作るのが決定木です。「はい／いいえ」だけで答えにたどりつく考え方は 中学生向けの決定木 で動物当てゲームとして紹介しています。ここでは、「降水確率は 40 % 以下？」という質問 1 つが散布図の上で何をしているかを見ていきます。

上の図は、2 つの特徴量 \(x_1, x_2\) で A と B を分けた決定木の結果です。境界が縦と横の線だけでできていて、斜めの線が 1 本もないことに注目してください。たとえば「\(x_1 \le -0.5\)？」という質問は縦線、「\(x_2 \le 1\)？」という質問は横線になります。

仕組み：いちばん「きれいに分かれる」線を 1 本ずつ引く #

まず、A と B が混ざった全部の点を 1 つの箱（根）に入れます。次に、「\(x_1\) を 0.3 で区切る」「\(x_1\) を 0.4 で区切る」「\(x_2\) を −1.0 で区切る」……と、特徴量と値の組み合わせを総当たりで試します。散布図の上では、縦線や横線を 0.1 ずつずらしながら置いてみることに当たります。そのうち、分けたあとの左右の箱がそれぞれなるべく 1 色に近くなる、つまり混ざり具合（ジニ不純度）がいちばん減る線を採用すると、図に最初の 1 本が引かれます。

できた 2 つの部屋で同じことを繰り返します。2 本目の線は 1 本目で分けた部屋の中だけに引かれるので、部屋は長方形に細分化されていきます。最後に、部屋が 1 色になったか、決めた深さ（max_depth）に達したら止めて、その部屋を葉と呼びます。新しい点が来たら、落ちた部屋の多数派の色、たとえば A が 7 点・B が 1 点の部屋なら A と予測します。

2 枚目の図は同じ木を「質問の流れ」として描いたものです。各箱の gini が混ざり具合、samples が箱に入った点の数、value がクラスごとの数を表します。根から葉へたどる 1 本の道が、1 枚目の図の 1 つの部屋に対応しています。この木は深さを制限せずに育てたので、samples = 1 の葉、つまり点 1 つだけの部屋がいくつもあり、これが後で説明する過学習の正体です。

「混ざり具合」を数にする：ジニ不純度 #

箱の中のクラスの割合を \(p_A, p_B\) とすると、ジニ不純度は

です。A だけなら \(1 - (1^2 + 0^2) = 0\)、半々なら \(1 - (0.5^2 + 0.5^2) = 0.5\)。0 に近いほどきれいです。線を引いたあとは、左右の箱のジニ不純度を点の数で重みづけして平均し、元の箱からどれだけ減ったかで線の良さを比べます。次のコードは、A 8 日・B 2 日の箱を 2 種類の質問で分けたときの「分ける前 → 分けた後」のジニ不純度を計算します。

1
2
3
4
5
6
7
8
9

def gini(counts):
    n = sum(counts)
    return 1 - sum((c / n) ** 2 for c in counts)
parent = [8, 2]                      # 8 A-days, 2 B-days
split_a = ([5, 0], [3, 2])           # question A
split_b = ([4, 1], [4, 1])           # question B
for name, (left, right) in [("A", split_a), ("B", split_b)]:
    after = (sum(left) * gini(left) + sum(right) * gini(right)) / sum(parent)
    print(f"question {name}: gini {gini(parent):.2f} -> {after:.2f}")

A 8 個・B 2 個の箱（ジニ 0.32）を、質問 A は「5 個と 0 個／3 個と 2 個」に、質問 B は「4 個と 1 個／4 個と 1 個」に分けます。計算すると質問 A は 0.24 に減り、質問 B は 0.32 のまま。決定木は質問 A を選びます。

動かして見てみよう #

下の図で「再生」を押すと、説明した手順が 1 つずつ進みます。手順ごとの説明は図の下に出ます。

気をつけたいこと #

最初の注意点は、max_depth を深くしすぎると丸暗記になることです。1 点だけの小さな部屋をいくつも作れば学習データ 100 日分は全問正解ですが、新しい日の予測は外れます。情報IIで学ぶ過学習そのもので、max_depth（質問の回数の上限）や min_samples_leaf（葉に最低何点残すか）を決めて止めます。二つ目は、斜めの境界がギザギザの階段になることです。線は縦横しか引けないので、本当は斜め 1 本で分かれるデータも、細かい階段で近似することになります。三つ目は、少しのデータの違いで木がガラッと変わることで、最初の質問が変わるとその下の質問もすべて変わります。この不安定さは、木を 100 本集めて多数決する ランダムフォレスト で抑えます。

やってみよう #

最初の課題は、方眼紙に A を 8 点、B を 6 点打ち、縦線か横線を 1 本だけ引いて「ジニ不純度がいちばん減る線」を探すことです。次にそれぞれの部屋でもう 1 本引いてみましょう。二つ目は、上のコードの split_b を ([7, 0], [1, 2]) に書き換えて、質問 A とどちらが良いか確かめることです。三つ目は、「縦横の線だけでは分けにくい点の並び」を 1 つ描くことで、ヒントは斜めの直線で分かれる配置です。線を何本引けば分けられるか、2 本で済むかを数えてみてください。

つぎに読む #

エントロピーなど別の不純度、剪定（枝刈り）、scikit-learn での実装は 標準版の決定木分類器 で扱っています。数式なしの入門は 中学生向けの決定木、数（たとえば気温 25 ℃）を予測する木は 高校生向けの決定木回帰 へ、木を何本も集めて強くする考え方は アンサンブル学習 へ進んでください。