決定木 - yuuk1's Digital Garden

# 決定木 ## 定義決定木(Decision Tree)は、特徴空間を再帰的な二分割によって矩形領域(終端ノード/leaf)に分割し、各領域に単純なモデル(回帰では定数、分類では多数決クラス)を当てはめる教師あり学習手法である。CART(Classification and Regression Tree)はその代表的な実装であり、貪欲な木の育成とコスト複雑度基準に基づく事後枝刈りを組み合わせる。特徴空間の分割が単一の二分木として完全に記述できるため解釈性が高い(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 9 Additive Models, Trees, and Related Methods]] §9.2.1)。 ### 木の育成(貪欲な分割) 回帰木は二乗和誤差 $\sum(y_i-f(x_i))^2$ を最小化する分割変数 $j$ と分割点 $s$ を各段で貪欲に選ぶ。最良の二分割全体を厳密に探索するのは計算量的に非現実的なため、最小ノードサイズ(例: 5)に達するまで大きな木 $T_0$ を育て、その後枝刈りする2段階戦略が定石である。分割候補の探索を「決定分割による誤差減少がある閾値を超えたときだけ分割する」という短絡的な戦略で打ち切るのは近視眼的であり避ける(一見無価値な分割の先に良い分割があり得るため)(Source: 同上 §9.2.2)。 ### 不純度指標回帰木は二乗誤差をノード不純度 $Q_m(T)$ として使う。分類木では、誤分類率・Gini係数($\sum_{k\neq k'} \hat p_{mk}\hat p_{mk'}$)・交差エントロピー(逸脱度、$-\sum_k \hat p_{mk}\log \hat p_{mk}$)の3種を使い分ける。Gini係数と交差エントロピーは微分可能でノード確率の変化に敏感なため木の育成(node splitting)に用い、誤分類率は事後の枝刈り基準として使うのが定石である(Source: 同上 §9.2.3)。 ### コスト複雑度枝刈り終端ノード数 $|T|$ を持つ部分木 $T$ に対しコスト複雑度基準 $C_\alpha(T) = \sum_{m=1}^{|T|} N_m Q_m(T) + \alpha|T|$ を定義し、各 $\alpha \geq 0$ について $C_\alpha(T)$ を最小化する部分木 $T_\alpha$ を、ノードあたりの誤差増加が最小の内部ノードを逐次崩す「弱リンク枝刈り(weakest link pruning)」で求める。$\alpha$ は5分割または10分割交差検証で選ぶ。$\alpha=0$ では全木 $T_0$ が解になり、$\alpha$ を大きくするほど木は小さくなる。この枝刈りは「事後に、当てはまりの良さと木の大きさのトレードオフを単一のペナルティ項 $\alpha$ で明示的に制御する」枝刈りである(Source: 同上 §9.2.2)。 ### 欠測値の代理分割決定木は欠測値に対し、カテゴリ変数では「欠測」を新カテゴリとして扱うほか、より一般的な**代理分割(surrogate split)**を用いる。主分割変数・分割点を選んだ後、その分割を最もよく模倣する代理変数・分割点のリストを作り、主分割変数が欠測している観測をこの順で振り分ける。代理分割は説明変数間の相関を利用して欠測の影響を緩和し、相関が高いほど情報損失が小さい(Source: 同上 §9.2.4)。決定木は他の学習法向けの欠測値代入エンジンとしても有効である(Source: 同上 §9.6)。 ### 不安定性と構造的弱点決定木は階層的な分割の性質上、上位の分割の誤りが下位すべてに伝播するため高分散(不安定)であり、予測面が非滑らかで、加法構造($Y = c_1 I(X_1<t_1) + c_2 I(X_2<t_2)+\varepsilon$ のような構造)の学習も苦手である。これらはいずれも決定木の二分木構造そのものに起因するトレードオフであり、より安定な分割基準を使っても本質的な不安定性は除去できない(Source: 同上 §9.2.4)。 ## 横断的知見 - **決定木は、ESL第16章の総括的視点では「基底の辞書」の要素の1つとして位置づけ直せる**: 本ページはこれまで、木を「特徴空間を再帰的に分割する単独の予測モデル」として、あるいは「アンサンブルの弱学習器」として扱ってきたが、第16章は取りうるすべての $J$終端ノード木の集合 $\mathcal T=\{T_k\}$ を線形モデル $f(x)=\sum_k\alpha_kT_k(x)$(式16.1)の基底関数の辞書とみなす、より一般的な視点を導入する。この視点では、単木のコスト複雑度枝刈り(本ページ§コスト複雑度枝刈り)もブースティングの固定サイズ$J$(第10章)も、辞書の要素をどう作り複雑さをどう制御するかという同じ問題の異なる解にすぎない。さらに第16章§16.3.2は木の各ノードに対応する規則(root からそのノードまでの分岐条件の積)を切り出し、木自体よりきめ細かい過完備な基底(Rule Ensembles)を構成できることを示す。すなわち決定木は、それ単体の予測モデルという役割に加えて、[[基底展開]]の枠組みにおける基底関数の一種としての役割も持つ。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 16 Ensemble Learning]] §16.2.1, §16.3.2) - **ブースティング(ESL第10章)では、弱学習器としての木にコスト複雑度枝刈りは使わず、終端ノード数 $J$ を全木共通の固定値にする**という異なる複雑さ制御が採られる。理由は、単木の枝刈りは「その木が展開の最後の1本である」という(ブースティングでは成り立たない)暗黙の前提に立つ手法であり、逐次追加される木ではこの前提が崩れて木が過大になりやすいためである。$J$ は表現できる交互作用の最大次数を $J-1$ に制限するというANOVA分解に基づく別の理論的根拠を持ち、実務的には $4\le J\le 8$、既定 $J\simeq6$ が推奨される。すなわち弱学習器としての木の複雑さ制御は、単木の「事後の当てはまり-大きさトレードオフ」ではなく「アンサンブル全体が捉えるべき交互作用の次数」という基準に置き換えられる(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 9 Additive Models, Trees, and Related Methods]] §9.2.2, [[@2009__Springer__The Elements of Statistical Learning - Chapter 10 Boosting and Additive Trees]] §10.11)。 - **決定木の高分散という構造的弱点は、ランダムフォレスト(ESL第15章)ではバギングをさらに一歩進めた「脱相関(de-correlation)」によって対処される**: バギング単体は木を独立に育てて平均するが、i.d.(独立でない同一分布)な木の平均の分散は $\rho\sigma^2+\frac{1-\rho}{B}\sigma^2$ と分解でき、木の本数 $B$ を増やしても消えない第1項(木どうしの相関 $\rho$)が改善の上限を決める。決定木の不安定性(上位の分割の誤りが下位すべてに伝播する性質)自体はこの操作で除去されるわけではないが、ランダムフォレストは各分割ノードで説明変数のランダムな部分集合だけを分割候補にすることでこの $\rho$ を直接下げ、バギングだけでは埋まらない分散削減の余地を追加で埋める。ブートストラップされた木の $\rho$ は典型的に0.05以下と小さく、これは決定木のような高分散・非線形な推定量だからこそ得られる効果であり、標本平均のような線形推定量ではブートストラップされた推定量どうしの相関は約50%と高いままで脱相関の効果をほとんど受けない。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 9 Additive Models, Trees, and Related Methods]] §9.2.4, [[@2009__Springer__The Elements of Statistical Learning - Chapter 15 Random Forests]] §15.2, §15.4.1) - **不純度指標(Gini係数)は、専門書の理論的定義とSRE実務チュートリアルの実行結果表示という2つの独立した文脈で一致して現れる**: 本ページが積み増したESL第9章のGini係数の定義($\sum_{k\neq k'}\hat p_{mk}\hat p_{mk'}$、ノード分割の不純度指標)は、『SREの探求』第18章のscikit-learn実践例(サーバーのCPU・RAM・ストレージ使用率からhealthy/unhealthyを分類する決定木、図18-9)が `graphviz.Source` で出力する各ノードのGini値と同一の指標である。ESLはGini係数を交差エントロピーと並ぶ木の育成(node splitting)基準として理論的に導入するのに対し、SRE章はscikit-learnの`DecisionTreeClassifier`のデフォルト出力としてGini値をそのまま提示するにとどまり、Gini係数と交差エントロピーのどちらを使うかという設計判断には触れない。理論的な選定基準(ESL)と、ライブラリのデフォルト値をそのまま受け入れる実務(SRE章)という対比が、同じ指標を介して確認できる。(Source: [[@2009__Springer__The Elements of Statistical Learning - Chapter 9 Additive Models, Trees, and Related Methods]] §9.2.3, [[@2021__OReillyJapan__SREの探求 - Chapter 18 SREのための機械学習入門]] §18.6.2.2) ## 未解決の問い - 決定木の代理分割は説明変数間の相関を利用するが、相関が低い(独立に近い)説明変数群では代理分割の情報損失はどの程度深刻になるか、ESL第9章の記述だけでは定量的な目安が読み取れない。 - ブースティング(ESL第10章)で使う固定サイズ $J$ の木は、コスト複雑度枝刈りの理論(ESL第9章)とどう理論的に接続するか、あるいは全く独立な設計判断とみなすべきか、ESL内では明示されていない。 ## 関連 - ソース: [[@2009__Springer__The Elements of Statistical Learning - Chapter 9 Additive Models, Trees, and Related Methods]] / [[@2009__Springer__The Elements of Statistical Learning - Chapter 10 Boosting and Additive Trees]] / [[@2009__Springer__The Elements of Statistical Learning - Chapter 15 Random Forests]] / [[@2009__Springer__The Elements of Statistical Learning - Chapter 16 Ensemble Learning]] / [[@2021__OReillyJapan__SREの探求 - Chapter 18 SREのための機械学習入門]] - 概念: [[GAM]] / [[MARS]] / [[アンサンブル学習]] / [[勾配ブースティング]] / [[基底展開]] - 関連 MOC: (該当なし) ## 出典 - [[@2009__Springer__The Elements of Statistical Learning - Chapter 9 Additive Models, Trees, and Related Methods]](§9.2 Tree-Based Methods) - [[@2009__Springer__The Elements of Statistical Learning - Chapter 10 Boosting and Additive Trees]](§10.9-10.11 Boosting Trees, Right-Sized Trees for Boosting) - [[@2009__Springer__The Elements of Statistical Learning - Chapter 15 Random Forests]](§15.2, §15.4.1 Definition of Random Forests, Variance and the De-Correlation Effect) - [[@2009__Springer__The Elements of Statistical Learning - Chapter 16 Ensemble Learning]](§16.2.1, §16.3.2 Penalized Regression, Rule Ensembles) - [[@2021__OReillyJapan__SREの探求 - Chapter 18 SREのための機械学習入門]] §18.6.2.2.