2026/03/01 17:55
**決定木―ネストされた意思決定規則の非合理的な力**
RSS: https://news.ycombinator.com/rss
要約▶
Japanese Translation:
記事では、決定木が特徴空間を一連のルールによりよく分離された領域へと分割する方法について説明しています。エントロピーベースの分割に焦点を当て、ノード不純度を測るために (H = -\sum_i p_i \log_2(p_i)) を定義し、情報ゲイン (IG) は分割後のエントロピー減少量として表されます。ID3 アルゴリズムは IG を最大化する特徴と閾値を選択します。例えば「Diameter ≤ 0.45」で分割すると IG のピークが 0.574 になります。ID3 は再帰的に処理します：各候補分割のエントロピーを計算 → 全ての分割を評価 → 最も高い IG を持つものを選択 → ノードを作成 → 葉が純粋になるか、最小サンプル数や最大深さなど他の停止基準に達するまで繰り返します。
ジニ不純度はエントロピーの代替として提示されます。計算コストが低く、対数を避けるため高速であり、多くの場合類似した木構造を生成します。ただし、不均衡データセットに対してはエントロピーがより慎重な指標になることがあります。記事では決定木は過学習しやすいと述べています：ID3 は全ての葉が純粋になるまで分割を続け、深く複雑で高変動性の木を生成します。これを緩和するために、深さ制限、葉数制限、あるいは最小葉サイズの設定といった剪定戦略が推奨されています。
また、ランダムフォレストについても言及しています。これは多数の決定木を擾乱データセットで訓練し、その予測を集約して分散を減らすアンサンブル手法です。シャノン（1948）、クインラン（1986）、ジニ（1912）による基礎研究が引用され、可視化に使われたライブラリとして D3.js、d3‑annotation、KaTeX が紹介されています。
最後に、記事は決定木、回帰木、ハイパーパラメータ、および関連する機械学習トピックについての追加資料を提供しています。
本文
決定木とエントロピー – ざっくりガイド
決定木の仕組み
決定木は、特徴空間を単純なルール（例：直径 ≤ 0.45）で定義された領域に繰り返し分割してデータを分類します。
アルゴリズムは各分割点を選ぶ際に、「純度」が最大になるようにします ― すなわち、ほとんど同じクラスのサンプルだけが残るようにすることです。
エントロピー：不確実性の測定
エントロピーはサンプル集合がどれだけ混在しているかを表します：
[ H = -\sum_{i=1}^{k} p_i \log_2(p_i) ]
- 純粋（すべてのサンプルが同じクラス） → エントロピー = 0
- 最大混在（クラス確率が等しい） → 最大エントロピー
ノードの不純度を評価するために用いられます。複数のクラスが含まれるノードは、単一クラスのみのノードよりも高いエントロピー値になります。
情報利得と ID3 アルゴリズム
情報利得は分割によって不確実性がどれだけ減少したかを測ります：
[ IG = H_{\text{親}} - \sum_{j} \frac{|S_j|}{|S_{\text{親}}|},H(S_j) ]
ID3 の手順
- 各特徴量のエントロピーを計算する。
- それぞれの特徴と可能なカットオフでデータを分割し、情報利得を求める。
- 最大の情報利得を持つ分割点を選択する。
- 選んだ特徴と値に基づく決定ノードを作成する。
- もしサブセットがこれ以上分割できない（すべて同じクラス、または他の停止条件）ならば、葉ノードを作り、ラベルには多数派クラス（回帰の場合は平均値）を付与する。
- 停止条件に達するまで再帰的に繰り返す。
例：最初の分割選択
今回のデータでは Diameter と Height のすべての可能なカットオフを評価すると、情報利得が異なる値になります。
ID3 アルゴリズムは 0.574（Diameter = 0.45） という最大情報利得を持つ分割点を選びます。これがエントロピー図のピークとして示されています。
ジニ不純度
別の不純度指標として：
[ G = 1 - \sum_{i} p_i^2 ]
エントロピーと同様に振る舞いますが、計算コストが低く（対数演算が不要）実装しやすいです。
実際には両方で構築された木はほぼ同等の性能を示します。ただし、極端に不均衡なデータではエントロピーが優れることがあります。
まとめ
| ステップ | 内容 |
|---|---|
| 1 | 特徴空間を単純ルールで領域に分割する。 |
| 2 | エントロピーで各領域の純度を測定。 |
| 3 | 情報利得（ID3）でエントロピーを最大限減らす分割を選択。 |
実務上の注意点
- 過学習 – 決定木は葉が完全に純粋になるまで深く成長することがあり、分散が大きくなります。
- 剪定 – 深さ制限、最小葉サイズ設定、または葉数上限を設けることで複雑さを抑えます。
- ランダム性と安定性 – データの微細変化が木全体を大きく左右します。
アンサンブル手法（例：ランダムフォレスト）は、わずかに異なるデータサブセットで多数の木を訓練し、集約することでこの問題を軽減します。
さらに読む
- 機械学習コース・リソース – 自己ペースの講座、YouTube 動画、Dive into Deep Learning テキストブックをご覧ください。
- 関連トピック – 回帰木、終端ノード選択（end‑cut preference）、ハイパーパラメータ調整。
謝辞
本記事は以下の基礎的研究に基づいています：
- Claude E. Shannon, A Mathematical Theory of Communication (1948)
- John Ross Quinlan, Induction of Decision Trees (1986)
- Luis Torgo, End‑Cut Preference in Least Squares Regression Trees (2001)
- Corrado Gini, The Origins of the Gini Index (1912)
貴重なご協力をいただいた Brent Werness に特別に感謝します。
決定木の探求、ぜひお楽しみください！