決定木の剪定（プルーニング）とは？事前剪定と事後剪定の2つのアプローチを解説

剪定（プルーニング）とは、決定木のサイズを縮小するための手法です。木の大きさを制限したり、判別力がほとんどない領域を取り除いたりすることで、過学習（オーバーフィッティング）のリスクを軽減できます。剪定によって、訓練データに含まれるノイズや外れ値に起因する異常な分岐を切り取り、木の汎化性能を高めた状態で元の構造を保持することが可能になります。

多くの剪定手法では、統計的な尺度を用いて信頼性の低い枝を削除します。その結果、分類処理が高速化されるだけでなく、未知のテストデータを正しく分類する能力も向上します。

決定木の剪定には、主に次の2つのアプローチがあります。

事前剪定（Pre-pruning）アプローチ

事前剪定では、木の構築を早期に停止することで「剪定」を行います。例えば、あるノードにおいて訓練サンプルのサブセットをそれ以上分割しないと判断した時点で構築を止めます。構築が停止したノードは葉となり、そこにはサブセット内のサンプルにおける多数派クラス、またはそれらのサンプルの確率分布が割り当てられます。

木を構築する際には、統計的有意性、カイ二乗値（χ²）、情報利得などの尺度を用いて分割の妥当性を評価できます。あるノードでのサンプル分割の結果が、あらかじめ定めた閾値を下回る場合には、そのサブセットの分割を中止します。

ただし、適切な閾値の選択には難しさが伴います。閾値を高く設定しすぎると木が過度に単純化されてしまい、逆に低く設定しすぎるとほとんど簡略化が行われないという問題が生じます。

事後剪定（Post-pruning）アプローチ

事後剪定では、「完全に成長させた」木から枝を取り除きます。枝を削除されたノードは葉へと変換され、以前の枝の中で最も一般的なクラスによってラベル付けされます。コスト複雑性剪定（コスト・コンプレキシティ・プルーニング）アルゴリズムは、事後剪定アプローチの代表例です。

このアルゴリズムでは、まず木に含まれる各非葉ノードについて、そのノードのサブツリーを切り詰めた場合に発生しうる期待誤り率を計算します。次に、剪定しなかった場合の期待誤り率を、各枝の誤り率を観測数に応じて重み付けして統合することで求めます。剪定によって期待誤り率が上昇する場合はサブツリーが保持され、そうでなければ剪定されます。

段階的に剪定を進めた一連の木を作成した後は、独立したテストセットを用いて各木の性能を評価できます。そして、期待誤差コストが最小となる決定木が最終的に採用されます。