決定木 ― 入れ子になった決定ルールの驚くべき力

 (mlu-explain.github.io)
3 ポイント 投稿者 GN⁺ 2026-03-02 | 1件のコメント | WhatsAppで共有
  • データ分類のために特徴空間を反復的に分割する構造で、各段階で最も情報利得が大きい分割を選択する
  • エントロピー（Entropy） を用いてデータの**純度（purity）を測定し、これに基づいて情報利得（Information Gain）**を計算する
  • ID3アルゴリズムは親ノードと子ノードのエントロピー差を計算して最適な分割点を見つけ、再帰的に木を拡張する
  • エントロピーの代わりにジニ不純度を使うこともでき、両手法は多くの場合で類似した結果を示すが、計算効率が異なる
  • 過度な分割は過学習（overfitting）と不安定性を招くため、**枝刈り（pruning）やランダムフォレスト（Random Forest）**でこれを緩和する

決定木の基本概念

  • 決定木はデータを上から下へ分割し、各段階で条件ルールを適用して、データをよく区別された領域に分ける
    • 各分割はデータの特定の**特徴（feature）としきい値（cutoff value）**によって決まる
    • 目標は、分類（classification）においてクラスが明確に分かれた純粋なノードを作ることである

エントロピー（Entropy）の定義と性質

  • エントロピーは情報の不確実性を測る指標で、確率 (p_i) に対して (H = -\sum p_i \log_2(p_i)) と定義される
  • 主な性質
    1. ある1つの事象だけが確率1で、残りが0のとき (H=0)、つまり不確実性がない
    2. すべての事象の確率が同じとき、エントロピーは最大となり、最も不純な状態を表す
    3. 確率が均等に近づくほどエントロピーは増加する
  • したがって、純粋なノードのエントロピーは0で、混合されたノードは高いエントロピー値を持つ

情報利得（Information Gain）とID3アルゴリズム

  • 情報利得は分割前後のエントロピー差として計算され、データ分割の効率性を表す
    • 式: (\Delta IG = H_{\text{parent}} - \frac{1}{N}\sum N_{\text{child}} \cdot H_{\text{child}})
  • ID3アルゴリズムの手順
    1. 各特徴のエントロピーを計算
    2. さまざまな分割基準でデータセットを分け、情報利得を計算
    3. 情報利得が最大の分割を選んで決定ノードを作成
    4. これ以上分割できないときはリーフノードを作成
    5. すべての部分集合に対して再帰的に実行し、ただし全要素が同一クラスの場合は停止
  • 例として、Diameter ≤ 0.45 条件が情報利得0.574で最大だったため、最初の分割として選ばれた

ジニ不純度と代替指標

  • ジニ不純度（Gini impurity） はエントロピーの代替であり、情報の不純度を測る別の方法である
    • 対数計算がないため計算速度が速い
    • 不均衡なデータセットでは、エントロピーの方がより慎重な選択になることがある
  • どちらの方法も一般に類似した結果を生み出す

過学習と不安定性の問題

  • ID3アルゴリズムはエントロピーを最小化するために分割を続けるので、木が過度に深くなる可能性がある
    • これは**過学習（overfitting）**を引き起こし、新しいデータに対する汎化性能を低下させる
  • また、データの小さな変化でも木構造が大きく変わる**不安定性（high variance）**の問題がある
    • 例: 学習データの5%に小さなガウスノイズを加えるだけで、まったく異なる木が生成される
  • 解決策として、**枝刈り（pruning）**によって木の深さ、リーフ数、最小サンプル数などを制限できる

ランダムフォレストへの拡張

  • 単一の決定木の不安定性を緩和するために、複数の木を異なるデータサンプルで学習させて予測を結合する方法が使われる
    • このアプローチが**ランダムフォレスト（Random Forest）**であり、高い安定性と汎化性能を提供する
  • これは決定木の欠点を補い、現在までで最も成功した機械学習アルゴリズムの1つと評価されている

結論と追加学習

  • 決定木は解釈しやすく、学習速度が速く、前処理が簡単なモデルである
  • しかし、過学習と不安定性の問題を解決するために枝刈りやアンサンブル手法が必要である
  • 記事では回帰木、エンドカット選好（end-cut preference）、ハイパーパラメータなどは扱っておらず、関連資料による追加学習を勧めている

関連記事

1件のコメント

 
GN⁺ 2026-03-02
Hacker Newsのコメント

  • 分類器を学ぶときに自分にとてもよく効いた秘密兵器は、まず良い線形分類器を学習することだった
    その線形分類器のしきい値前の出力値を追加の特徴量次元として使って決定木を学習し、それをブーストされた木システムで包むやり方だ
    こうすると決定木の弱点を線形モデルが補い、逆に線形モデルが苦手な部分を木が処理してくれる
    データの回転や軸の正規化も考えられるが、ほとんどの場合は必要なかった
    ただし、特徴量が非常に疎なときは木が分割点を見つけにくい

    • 考えてみると、これは強化学習でも似た形で使われるアプローチだ
      生の状態(raw state)に追加計算を加えて観測状態(observed state) を作り、それで学習する
      たとえばスネークゲームでは、ヘビの座標だけでなく脱出経路の数のような派生特徴も計算して学習する
    • 決定木のアキレス腱は結局のところ特徴量エンジニアリングだ
      データを整え、特徴をうまく設計しないと、ニューラルネットのようなブラックボックスモデルよりずっと悪い結果になる
      皮肉なことにニューラルネットはこうした潜在特徴を自力で見つけるが、なぜそう動くのかは解釈しにくい
    • 目的に応じたさまざまな木の派生がある
      Oblique Decision Tree、Model Tree (M5)、Logistic Model Tree (LMT)、Hierarchical Mixture of Experts (HME) などがその例だ
    • 「同一ラベル領域が分割された構造を持つ」という表現が、正確にはどういう意味なのか気になる
    • このアイデアは、Arjovsky と Bottou らが書いたIRM論文の核心にも似ている

  • 2010年ごろにCERNで働いていたとき、Boosted Decision Treeが最も人気のある分類器だった
    説明可能性と表現力のバランスが理由で、当時は物理解析にニューラルネットを使うことを文化的に敬遠していた
    今では時代はかなり変わった

    • この変化は少し心配だ
      物理学では単に曲線をよく当てることよりも、因果メカニズムを理解することのほうが重要だ
      プトレマイオスの周転円(epicycle) 体系が天体運動をよりよく当てられても、原因を説明してはいなかったのと同じだ
    • 自分も物理学（理論）出身だが、他分野で決定木を使ってみると、説明可能性はやや過大評価されている面がある
      深さが少し増えるだけで、ほとんど解釈不能なジャングルになってしまう
      ニューラルネットも同様で、内部計算を追うことはできても、結局なぜその判断をしたのかは分からない
    • Boosted Decision TreeとBoosted Random Forestは同じものなのか気になる

  • 同じサイトにはRandom Forestの説明もある → mlu-explain/random-forest

  • 興味深い事実: 1ビットニューラルネット(single-bit neural network) は、実質的には決定木だ
    理論的にはほとんどのニューラルネットを if-else チェーンに「コンパイル」できるが、いつうまく機能するのかはまだ明確でない

    • 「ニューラルネットは決定木だ」という論文(arXiv:2210.05189)を読んでみたが、実際には木がとてつもなく巨大になる
      概念を拡張したレベルで、直接的な対応付けは難しい
      なので、具体的にどういう意味で言っているのか、もう少し説明してほしい
    • こうした変換を実際にやってくれるソフトウェアや論文があるのか気になる。週末プロジェクトとしてやってみたら面白そうだ

  • 決定木の最大の利点は速度だ
    低遅延環境で木ベースの分類器を小さなニューラルネットに置き換えようとしたが、ニューラルネットは精度が少し高くても推論遅延(latency) が100倍以上高かった

    • また、単一の決定木はエッジデバイスへ直接移植しやすい
      一方でブースティングやバギングされた木は複雑で、他の古典的MLアルゴリズムも移植性が低い

  • あるML教科書（たぶんESL）では決定木をこう表現していた
    「解釈可能で、速く、多様なデータでうまく動き、スケーリングに鈍感で、チューニングパラメータも少ないが… うまく動作しない」
    ただしバギングやブースティングでこの欠点は補えるが、その過程で元々の長所の一部を失うことになる

  • 決定木が本当に好きだ。自分が最も好む古典的MLアルゴリズムだ
    GNU Guileで純粋関数型の並列実装を作ってみた → コードリンク
    ただし Guile にはNumPy や DataFrameのようなものがなく、データ表現が非効率だ

    • NumPy や DataFrame が Guile よりどんな点で有利なのか気になる
      Guile は木の操作に向いているので、決定木の実装には自然だ
      ただしマシンコードにコンパイルすれば、もっと効率的になるはずだ
      参考までに Lush(https://lush.sourceforge.net/) や aiscm(https://wedesoft.github.io/aiscm/) も見てみる価値がある

  • 専門家のあいまいな意思決定も、しばしば単純な決定木や決定チェーンでモデル化できる
    専門家本人は複雑だと思っていても、実際には単純な木のほうがうまく説明できることが多い
    昔は回帰や距離ベースのクラスタリングのほうが洗練されて見えたが、木のほうがずっと効果的だ
    関連内容は Oxford Handbook of Expertise 第7章に詳しい

    • 以前見た可視化では、決定を2D平面で空間分割として表していた
      結局、決定木はkD-Treeのように可能性空間を分け、各領域に行動を割り当てる構造だ
      専門家の微妙な判断は境界面の細かさから来るが、木でもかなり良い近似を与えられる

  • サイトは興味深く、プレゼンテーションも良かった
    ただし一部テキストの色コントラストが低く、読みづらかった

    • 自分も同感だ。Firefox Reader Viewがとても役に立つ
      アクセシビリティは単に障害者のためのものではなく、可読性を高める基本要素だ

  • 最近のディープラーニング時代では決定木が過小評価されている
    それでも依然として解釈しやすく、速く、十分に実用的だ
    自分はWebサイト分析用のスコアリングシステムを木ベースで作ったのだが、
    「メタディスクリプションがあるか？」「3秒以内に読み込まれるか？」「モバイル対応か？」のような条件を評価する
    ユーザーはなぜその点数になったのかをすぐ理解できる
    ニューラルネットが73点を出した理由を説明するのは不可能だが、木ならそれが容易だ

    • あなたは本当に古代の伝統を受け継いでいる
      紀元前1000年ごろの Esagil-kin-apli の診断木 がその始まりだった