CARTプルーニングアルゴリズムとは？決定木の過学習を防ぐ枝刈りの仕組みを解説

CART（Classification and Regression Trees：分類回帰木）は、1984年にLeo Breiman、Jerome Friedman、Richard Olshen、Charles Stoneの4人によって発表された、有名な決定木アルゴリズムです。CARTは二分木を構築し、純度をさらに高められる新しい分割が見つかる限り、分割を繰り返していきます。

なぜプルーニング（枝刈り）が必要なのか

分割を繰り返して成長させた決定木は、訓練データに過剰に適合する「過学習（オーバーフィッティング）」を起こしやすくなります。そこで重要になるのがプルーニングです。より単純な部分木はそれぞれ、モデルの複雑さと訓練データにおける誤分類率との間で異なるトレードオフを表します。CARTアルゴリズムは、こうした部分木の集合を候補モデルとして認識し、その中から最終モデルを選び出します。

調整済み誤り率によるプルーニングの仕組み

CARTアルゴリズムは、プルーニングを繰り返す手順を通じて候補となる部分木を特定します。目的は、葉1枚あたりの予測力への寄与が最も小さい枝から順に刈り取ることです。この「最も利益の少ない枝」を見極めるために、CARTでは「調整済み誤り率（adjusted error rate）」と呼ばれる概念が用いられます。

調整済み誤り率とは、訓練セットにおける各ノードの誤分類コストに、木に含まれる葉の数に応じた複雑さのペナルティを加えた指標です。この指標により、誤分類率がペナルティを相殺できるほど低くない「弱い枝」を識別し、プルーニングの対象としてマークすることができます。

検証データによる最適な部分木の選択

次の課題は、多数の候補部分木の中から、未知のレコードに対して最も良い性能を発揮するものを1つ選ぶことです。各候補部分木を使って検証セットのデータを分類し、総合誤り率が最も低くなる木が「勝者」として選ばれます。選ばれた部分木は、過学習の影響を取り除ける程度に刈り込まれながら、貴重な情報まで失わない範囲に留められています。

なお、このプルーニング手法は誤分類率に基づいており、各クラスの確率は考慮されていません。そのため、すべての葉が同一の分類結果を返す部分木は、同じ分類を返す共通の親ノードへと置き換えられます。

プルーニングの限界と注意点

データ全体からごく一部（例えば上位1％や10％など）を抽出することを目的とする場合、このプルーニング手法は木の性能を損なうおそれがあります。刈り込まれた葉の中に、ターゲットクラスが非常に高い割合で含まれる葉が存在する可能性があるためです。SAS Enterprise Minerをはじめとする多くのツールでは、こうした用途に向けてユーザーが最適な形で木を刈り込めるようサポートしています。

まとめ

勝利した部分木は、検証セットのデータを分類した際の総合誤り率に基づいて選択されています。選ばれた部分木は、別のデータセットに適用した場合にも最良の性能を発揮すると期待できますが、選択の根拠となった誤り率は、その真の性能をやや過大に評価している可能性がある点には留意が必要です。