Zenn
🐈

Act 19. 決定木について学ぶ

2024/11/20に公開
決定木
tech

はじめに

Act 01. AIで外国為替を自動売買するまでの道のりをベースに学習を進めて行く。

前回はロジスティック回帰について学習した。
今回から決定木について学習する。

今後学習する内容は以下の通り。
学習はChatGTPさん考案の以下の順序で進めて行く。

学習順序

教師あり学習

  1. 線形回帰: 基本的な回帰問題を学ぶ。　2024/11/13 学習済み
  2. ロジスティック回帰: 分類問題の基本を理解する。 2024/11/17 学習済み
  3. 決定木: シンプルで直感的なモデル。
  4. ランダムフォレスト: 決定木のアンサンブル学習。

教師なし学習

  1. k平均法: クラスタリングの基本。
  2. 主成分分析（PCA）: 次元削減の手法。

強化学習

  1. 基本的な概念: エージェント、環境、報酬の関係を理解する。
  2. Q学習: 簡単な強化学習アルゴリズム。
    ※強化学習は重要だと判断したため、概念から再度学習する。

決定木

ということで早速、決定木について学習していく。
ChatGTPさんに決定木について教えてーとお願いしてみた。

ChatGPTさんの回答

決定木の仕組みやアルゴリズムについて、少し詳しく説明します。

1. 構造

決定木はツリー状の構造を持ちます：

  • ノード
    • ルートノード（Root Node）: 最初の分岐点。ここで最初の条件が設定されます。
    • 内部ノード（Internal Node）: 中間の分岐点。さらに条件でデータを分けます。
    • 葉ノード（Leaf Node）: 分岐の終点。ここには最終的な結果（分類や回帰値）が記録されます。

2. アルゴリズム全体の流れ

決定木のアルゴリズムの流れを、具体的に詳しく説明します。以下は、データを分類する場合（分類木）の基本的な手順です。

  1. 初期データを取得
    データセット（例: 特徴量とラベル）が与えられます。

  2. 最初の分割条件を決める
    すべての特徴量について、分割による「不純度の減少」が最大になる条件を探します。

    • 例: 「体重 <= 6kg」で分けると一番きれいに分類できる。

  3. データを分割
    最初の条件に従ってデータを2つ（または複数）に分けます。

  4. 再帰的に繰り返す
    各分割グループについて、同じ手順でさらに分割します。

  5. 終了条件に達するまで続ける
    分割を止める条件（例: データが小さすぎる、木の深さが一定以上）が満たされるまで繰り返します。

  6. 完成した決定木で予測
    新しいデータが来たら、決定木の条件に従って予測を行います。

3. 各ステップの詳細

ステップ1: 初期データの準備

  • データセットには以下が含まれます：

    • 特徴量（特徴）: 分類や予測に使う情報（例: 年齢、体重、毛の長さなど）。
    • ラベル（ターゲット）: 分類対象のカテゴリ（例: 猫、犬）。

  • 例:
    特徴量: 体重, 毛の長さ
    ラベル: 猫, 犬

ステップ2: 分割条件を決める

このステップでは、どの特徴量とその値でデータを分けるかを決めます。
分割の良し悪しを評価するために、「不純度」という指標を使います。

評価指標の例

  • エントロピー: 不純度を測るための情報理論的な尺度。エントロピーが小さいほどデータが「きれいに分かれている」状態。

    H(S) = - \sum_{i=1}^k p_i \log_2(p_i)
    • p_i: クラス i の割合。

  • ジニ不純度: データがどれだけ混ざっているかを測る指標。

    Gini(S) = 1 - \sum_{i=1}^k p_i^2

  • 情報利得（Information Gain）
    分割によって不純度がどれだけ減少したかを表します。

    \text{情報利得} = \text{元の不純度} - \text{分割後の不純度}

具体例

  • データが「猫4つ、犬4つ」の場合：
    • 元の不純度は高い（混ざっている）。
    • 分割後に「猫4つ」「犬4つ」のグループに分かれたら不純度は0（完全に分かれている）。

ステップ3: データの分割

最適な条件を見つけたら、その条件でデータを分けます。
条件は以下のような形をとります：

  • 「特徴量の値 <= あるしきい値」
  • 「特徴量 = 特定のカテゴリ」

例
「体重 <= 6kg」

  • YES: データをグループAに。
  • NO: データをグループBに。

ステップ4: 再帰的に分割を繰り返す

分割後の各グループに対して、再び「最適な分割条件」を探し、分けます。
これをすべてのデータが純粋（不純度ゼロ）になるか、終了条件を満たすまで繰り返します。

ステップ5: 終了条件

木が無限に深くならないよう、以下の条件で分割を停止します：

  • 最小サンプル数:
    あるノード内のデータが少なすぎる場合（例: サンプル数 < 5）。
  • 最大深さ:
    木の深さが設定された最大値に達した場合（例: 深さ <= 10）。
  • 不純度が十分小さい場合:
    分割後のノードがほぼ純粋になった場合（例: 不純度 < 0.01）。

決定木のシンプルさと直感性は大きな魅力ですが、過学習などの課題もあるため、ランダムフォレストや勾配ブースティングなどの発展的手法と組み合わせて使われることが多いです。

決定木の構造

ChatGTPさんの回答にあった通り、決定木の構造について先に記載しておく。
今回は、以下のデータを使って「犬」、「猫」、「ライオン」を分類する場合を想定する。

名前 体重 (kg) 鳴き声 動物の種類
A 4 にゃー 猫
B 12 わん 犬
C 5 にゃー 猫
D 50 がおー ライオン
E 3 にゃー 猫
F 14 わん 犬
G 55 がおー ライオン
H 22 わん 犬

するとこんな感じの決定木が作れると思う。
恐らく構造はこんなイメージで問題ないだろう。

1. 初期データの取得

次に決定木の学習アルゴリズムを記載していく。
今回は、先ほども記載した以下のデータを使うとする。

名前 体重 (kg) 鳴き声 動物の種類
A 4 にゃー 猫
B 12 わん 犬
C 5 にゃー 猫
D 50 がおー ライオン
E 3 にゃー 猫
F 14 わん 犬
G 55 がおー ライオン
H 22 わん 犬

データセットには以下が含まれている。

  • 特徴量（説明変数）: 分類や予測に使う情報（体重（kg）や鳴き声）
  • ラベル（目的変数）: 分類対象のカテゴリ（猫、犬、ライオン）

まあ、ここについてはこれまで学習してきた人ならば問題ないと思う。

2. 最初の分割条件を決める

このステップでは、どの特徴量に対してどんな値でデータを分けるかを決める。
例えば、体重が10kg以下の動物など。

3. データを分割

分割の良し悪しを評価するために、「不純度」という指標を使う。

評価指標はエントロピーやジニ不純度、情報利得が存在する。
今回は、エントロピーと情報利得を使って評価を行ってみる。

エントロピー

エントロピーは不純度を測るための情報理論的な尺度。エントロピーが小さいほどデータが「きれいに分かれている」状態となる。
つまり、0に近いほどデータが正確に分類されていることを表す。

公式は以下の通り。

H(S) = - \sum_{i=1}^k p_i \log_2(p_i)
  • p_i: クラス i の割合。

はいはい、\log_2(p_i)ね、オッケーオッケー。とはならない。
\logなんて忘れてしまったよ。という人はlogの補足を記事の最後の方に書いているからぜひ読んでほしい。

分割前データのエントロピーを求めてみる

まずは試しに、分類前のデータの不純度を計算してみようと思う。
今回の全体のデータは、猫3匹、犬3匹、ライオン2匹なので、それぞれのクラスの割合を求めた結果は以下の通り。
p_{\text{猫}} = \frac{3}{8} = 0.375
p_{\text{犬}} = \frac{3}{8} = 0.375
p_{\text{ライオン}} = \frac{2}{8} = 0.25

これをエントロピーの公式に当てはめる。
\logの計算は対数関数 - 高精度計算サイトを使って行った。

H(S) = - \left( 0.375 \log_2(0.375) + 0.375 \log_2(0.375) + 0.25 \log_2(0.25) \right) \\ = - \left( 0.375 * -1.415 + 0.375 * -1.415 + 0.25 * -2 \right) \\ = - \left( (-0.5306) + (-0.5306) + (-0.5) \right)\\ = 1.561

分割前のエントロピーは 1.561 となり、不純度の高いデータであることが分かる。

分割後データのエントロピーを求めてみる

元の不純度については先ほど求めた通りで、分割後のエントロピーは次の公式で計算される。

H_{\text{分割後}} = \sum_{i=1}^k \frac{|S_i|}{|S|} H(S_i)
  • H: エントロピー
  • k: 分割後のグループ数（2グループ: 猫と犬&ライオン）
  • |S_i|: グループ i のデータ数（猫: 3個, 犬&ライオン: 5個）
  • |S|: 全体のデータ数（8個）
  • H(S_i): グループ i のエントロピー（- \sum_{i=1}^k p_i \log_2(p_i)で求める）

データ全体は 8 件で分割後は次の2つのグループになる。

  • グループ1: 体重 \leq 10 に該当するグループ（猫）
    3個のデータの内、すべてのデータが猫となるため、割合は 100% となる。
    下記の計算からも分かる通り、猫のグループのエントロピー(H(S_1))は 0 となる。

    H(S_1) = - \sum_{i=1}^k p_i \log_2(p_i) = 1 * \log_2(1) = 0

  • グループ2: 体重 > 10 に該当するグループ（犬とライオン）
    それぞれのデータの割合を求める。

    • 犬: \frac{3}{5} = 60\% = 0.6
    • ライオン: \frac{2}{5} = 40\% = 0.4

上記の内容を元にエントロピー(H(S_2))を求める。

H(S_2) = - \sum_{i=1}^k p_i \log_2(p_i) \\ = - \left(0.6 * \log_2(0.6) + 0.4 * \log_2(0.4) \right) \\ = - \left(0.6 * -0.737 + 0.4 * -1.322 \right) \\ = - \left((-0.4422) + (-0.5288) \right) \\ = 0.971

分類後の不純度を求める。公式からもう一度記載しておく。

H_{\text{分割後}} = \sum_{i=1}^k \frac{|S_i|}{|S|} H(S_i) \\ = \frac{3}{8} \cdot 0 + \frac{5}{8} \cdot 0.971 \\ = 0 + 0.607 = 0.607

情報利得

情報利得は、分割によって不純度がどれだけ減少したかを評価するもの。
公式は以下の通り。
先ほど求めたエントロピーをそれぞれ当てはめていくことで、情報利得が求められる。

\text{情報利得} = \text{元の不純度} - \text{分割後の不純度} = 1.561 - 0.607 = 0.954

情報利得を見るとエントロピーが下がっているため、「体重 <= 10kg」で分割するのが適切と判断できる。って感じかな？

4. 再帰的に繰り返す

1回目の体重で分割を行い、情報利得で評価した結果適切な分割と判断できた。
なので2回目の分割を行うため、ステップ2からやり直す。

5. 終了条件に達するまで続ける

木が無限に深くならないよう、以下の条件で分割を停止する。

  • 最小サンプル数:
    あるノード内のデータが少なすぎる場合（例: サンプル数 < 5）。
  • 最大深さ:
    木の深さが設定された最大値に達した場合（例: 深さ <= 10）。
  • 不純度が十分小さい場合:
    分割後のノードがほぼ純粋になった場合（例: 不純度 < 0.01）。

6. 完成した決定木で予測

これまでのステップで決定木のモデルが完成したため、後はデータを投入すると分類が可能となる。

補足

logの補足

必要な人だけ読んでほしい。
logとは対数のことで、逆向きの累乗（べき乗）を表す。

累乗（べき乗）とは：

2^3 = 2 \times 2 \times 2 = 8
これは「2を3回かけると8になる」ということになる。
流石に累乗は覚えてるよね…？

対数（log）とは：

対数とは累乗の逆のようなもので、「2を何回かけると8になる？」の何回の個所を求めるイメージ。
「2を何回かけると8になる？」を\logで表すと、\log_2(8) = 3になる。

ということで、対数には次の3つの要素があることが分かる。

\log_b(a) = x
  • b: 底（てい）、基準となる数。
    • 例: b = 2 の場合、「2を何回かけるか」を考える。
  • a: 真数（しんすう）、結果となる数。
    • 例: a = 8 の場合、「8にするためには何回かけるか」を計算する。
  • x: 対数の結果。
    • 例: x = 3 の場合、「3回かければ8になる」ということ。

もう完璧だと思うが、いくつか例を載せておく。

  • \log_2(8) = 3
    2^3 = 8 なので、「2(b)を3(x)回かけると8(a)になる」。

  • log_10(1000) = 3
    10^3 = 1000 なので、「10(b)を3(x)回かけると1000(a)になる」。

機械学習や情報理論で使われる対数（log）は、多くの場合「底が2」の対数（\log_2）を使うらしい。

なぜ底が2なのかというと、情報の世界では「ビット（二進数）」が基準だから。
\log_2 を使うことで、情報量や不純度を計算しやすくしているんだそう。

さいごに

今まで回帰分析だったから、決定木という新しい分析方法を学習出来てなんだかおもしろかった。
早く強化学習の勉強したいからどんどん進めて行くぞー！

次はpythonで実装するところをやってみようと思う。

ではまた

Discussion