CARTプルーニングアルゴリズムとは何ですか？

CARTは、1984年にLeo Breiman、Jerome Friedman、Richard Olshen、およびCharlesStoneによって最初に作成された有名な決定木アルゴリズムです。CARTは分類および回帰ツリーを表します。 CARTアルゴリズムは二分木を改善し、純度を改善する新しい分割が見つかることを考慮して分割を続けます。

いくつかのより単純なサブツリーがあり、それぞれがモデルの複雑さとトレーニンググループの誤分類率の間で異なるトレードオフを定義します。 CARTアルゴリズムは、そのようなサブツリーのグループを候補モデルとして認識します。これらの候補サブツリーは検証グループに使用され、検証セットの誤分類率が最小のツリーが最後のモデルとして選択されます。

CARTアルゴリズムは、剪定を繰り返す手順を通じて候補サブツリーを認識します。目的は、葉ごとの予測力が最も低いブランチを最初に剪定することです。調整済みエラー率と呼ばれる概念に基づいて、これらの最も有益でないブランチ、CARTを認識できます。

これは、ツリー内の複数の葉に依存する複雑さのペナルティを印象付けることにより、トレーニングセットでの各ノードの誤分類コストを改善する手段です。調整されたエラー率は、弱いブランチ（誤分類率がペナルティを克服するのに十分でないブランチ）を識別し、剪定のためにそれらを示すことができます。

次のタスクは、候補サブツリーのプールから、新しいレコードで最適に動作するサブツリーを選択することです。各候補サブツリーは、検証セットのデータを定義できます。完全エラー率が最も低いこのタスクを実装するツリーが勝者として定義されます。勝ったサブツリーは、オーバートレーニングの影響を排除するために適切に剪定されていますが、貴重なデータを失うほどではありません。

この剪定アルゴリズムは誤分類率に依存するため、各分類の確率を考慮せずに、葉がすべて同じ分類を作成し、その分類も作成する共通の親を持つサブツリーを復元します。

目的は、データのごく一部（たとえば、上位1％または10％）を選択することです。削除された葉の一部にはターゲットクラスの非常に高い領域が含まれるため、この剪定アルゴリズムはツリーの実装に悪影響を与える可能性があります。 。 SAS Enterprise Minerを含むさまざまなツールがあり、ユーザーはそのような方法に最適にツリーを剪定できます。

勝者のサブツリーは、検証セットでデータを定義するタスクに使用されたときの完全なエラー率に基づいて選択されました。選択されたサブツリーは、複数のデータセットに使用された場合に引き続き最適な実装サブツリーであると期待できます。選択されるように生成されたエラー率は、その強度をわずかに誇張する可能性があります。