Loading article…
プルーニングは、機械学習や検索アルゴリズムにおけるデータ圧縮手法の一つで、インスタンスの分類に重要でない冗長な部分を削除することで決定木のサイズを縮小します。プルーニングによって最終的な分類器の複雑さが軽減され、過学習が抑制されることで予測精度が向上します。
決定木アルゴリズムで生じる問題の一つは、最終的な木の最適なサイズです。木が大きすぎると、訓練データに過学習して新しいサンプルへの汎化性能が低下するリスクがあります。木が小さすぎると、サンプル空間に関する重要な構造情報を捉えられない可能性があります。しかし、ノードを1つ追加することでエラーが劇的に減少するかどうかは判断できないため、木アルゴリズムをいつ停止すべきかを判断するのは困難です。この問題は、ホライズン効果として知られています。一般的な戦略は、各ノードに少数のインスタンスが含まれるまで木を成長させ、その後、追加情報を提供しないノードを剪定して削除することです。[ 1 ]
枝刈りは、交差検証セットで測定した予測精度を低下させることなく、学習ツリーのサイズを縮小するべきである。ツリーの枝刈りには多くの手法があり、それぞれ性能を最適化するために使用される測定方法が異なっている。
剪定プロセスは、2種類（剪定前と剪定後）に分けられます。
事前剪定手順は、誘導アルゴリズムの停止基準（例：最大ツリー深度または情報利得（属性）> minGain）を置き換えることで、トレーニングセットの完全な誘導を防ぎます。事前剪定方法は、セット全体を誘導するのではなく、最初からツリーが小さいままであるため、より効率的であると考えられています。事前剪定方法には、ホライズン効果という共通の問題があります。これは、停止基準によって誘導が望ましくない早期終了してしまうことを意味します。
後剪定（または単に剪定）は、ツリーを単純化する最も一般的な方法です。ここでは、ノードとサブツリーを葉に置き換えることで複雑さを軽減します。剪定は、サイズを大幅に縮小するだけでなく、未知のオブジェクトの分類精度を向上させることもできます。訓練データセットでの割り当て精度が低下する場合もありますが、ツリーの分類特性の精度は全体的に向上します。
これらの手順は、ツリー構造におけるアプローチ（トップダウンまたはボトムアップ）に基づいて区別される。
これらの手順は、ツリーの最後のノード（最下位ノード）から始まります。再帰的に上方向にたどりながら、各ノードの関連性を判断します。分類に対する関連性が認められない場合、そのノードは削除されるか、葉ノードに置き換えられます。この方法の利点は、関連するサブツリーが失われることがない点です。これらの方法には、削減エラー剪定（REP）、最小コスト複雑度剪定（MCCP）、最小エラー剪定（MEP）などがあります。
ボトムアップ方式とは対照的に、この方式はツリーのルートから始まります。以下の構造に従って関連性チェックが実行され、ノードがすべての n 個のアイテムの分類に関連しているかどうかが判断されます。内部ノードでツリーを剪定すると、関連性に関係なくサブツリー全体が削除されることがあります。その代表例の 1 つは悲観的エラー剪定 (PEP) であり、未知のアイテムに対して非常に良好な結果をもたらします。
最も単純な剪定方法の一つに、誤差低減剪定があります。葉ノードから始めて、各ノードを最も頻繁に出現するクラスに置き換えます。予測精度に影響がなければ、変更はそのまま維持されます。誤差低減剪定はやや単純ではありますが、シンプルさとスピードという利点があります。
コスト複雑性剪定により一連のツリーが生成されるどこでは初期ツリーであり、 はルートのみです。ステップで木は、木から部分木を削除することによって作成されます。そして、それをツリー構築アルゴリズムで選択された値を持つ葉ノードに置き換えます。削除されるサブツリーは次のように選択されます。
機能サブツリーを剪定して得られるツリーを定義します。木から一連のツリーが作成されたら、トレーニングセットまたは交差検証によって測定された一般化精度に基づいて最適なツリーが選択されます。
プルーニングは、学習アルゴリズムの圧縮スキームに適用することで、モデルのパフォーマンスを損なうことなく冗長な詳細を取り除くことができます。ニューラルネットワークでは、プルーニングはニューロン全体またはニューロンの層を削除します。[ 2 ]
