デシジョン・ツリーの成長

成長は 1 つのルート・ノードから開始され、トレーニング・データ・セットを含む表が入力表として使用されます。この表には、属性を表す複数の列と、クラス属性を表す単一の列が含まれます。

期待される出力は、トレーニング・データ・セットに基づくデシジョン・ツリー・モデルの表現です。

分岐を行うと、作成されたそれぞれの下位ノードはトレーニング・データ・セットの適用可能なサブセットに対応します。これらのノードをさらに分岐させると、データ・セットのより小さいサブセットに対応する新しいノードが作成されます。それ以上分岐しないノードはリーフになります。

デシジョン・ツリーの成長は、以下の操作の繰り返しです。

1. 停止基準

   この操作では、分岐を行うか、またはノードがそれ以上分岐しないようにリーフにするかが決定されます。この決定は、ノードに対応するトレーニング・データ・セットのサブセットに基づいて行われます。

   以下のいずれかの条件に当てはまる場合、分岐は行われません。

   • 対応するサブセットのすべてのインスタンスが、同一クラスのインスタンスである場合
   • 対応するサブセットのインスタンス数が、指定された最小数より小さい場合
   • 現行ノードのレベルが、指定された最大レベルよりも大きい場合 (ルート・ノードのレベルが 1、その下位ノードのレベルが 2 と続く)
   • 可能な最善の分岐によるクラスの不純度の改善度が、指定された最小値よりも小さい場合
2. クラス・ラベルの割り当て

   対応するサブセットで最も頻度の高いクラスが、各ツリー・ノードに関連付けられます。この操作は、後続のプルーニングでいくつかのノードがリーフに変わるために、後でツリーがプルーニングされる場合に役立ちます。また、ツリー構造の読み取りが容易になります。クラス・ラベルの割り当ては、すべてのノードで実行されます。

3. 分岐選択

   この操作では、停止基準を満たしていないノードに対して、不純度が最小の分岐が割り当てられます。一連の分岐候補には、すべての離散型属性の 2 項等価式に基づく分岐と、すべての連続型属性の 2 項不等価式に基づく分岐があります。分岐候補を評価するため、分岐の結果に対応するサブセットに不純度の測度が適用されます。