machine-learning - ID3実装では、その時点でアルゴリズムの再帰は停止する必要があります

Question

ID3の実装では、その時点でアルゴリズムの再帰が停止するはずです。

Answer 1

分類する例が残っていないか、分類する属性が残っていない場合、ブランチは停止します。ウィキペディアのアルゴリズムの説明は非常にわかりやすく、例やディスカッションへのリンクもたくさんあります。

Answer 2

分割基準が満たされている限り、分割を続けます（既存のノードから2つの新しいノードを形成します）。

分割基準は通常、親ノードの情報ゲイン、別名エントロピー（または変数がカテゴリではなく離散である場合は分散）と推定子ノードの加重平均IGとの差の負の値です。加重平均情報ゲイン：

if weighted_mean(IG_child1, IG_child2) < IG_parent :
    createNodes(IG_child1, IG_child2)
else :
    continue 

これは些細な答えですが、質問の背後にはもっと洗練された意図がある可能性があります。気にしない場合は、分割基準が満たされている限りノードを作成し続ける必要があるので、少し言い換えますか？

ID3アルゴリズムをコーディングしているかどうかをご存知かもしれませんが、制約なしで分割基準を適用すると、多くの場合、過剰適合が発生します（つまり、トレーニングデータから構築したツリーは、一般化されていないため、一般化されません。 tノイズを本物のパターンと区別しました）。

したがって、これはあなたの質問に対する答えである可能性が高くなります。ノード分割を「制限」する（したがって、過剰適合の問題に対処する）手法はすべて、トップダウンまたはボトムアップの2つのカテゴリのいずれかに分類されます。トップダウンの例：しきい値を設定します（たとえば、子ノードの加重平均が5％未満の場合は、分割しないでください）。

ボトムアップの例：剪定。プルーニングとは、分割基準が満たされている限りアルゴリズムを分割し、アルゴリズムが停止した後、ノードの最下層から開始し、子ノードと親の間のIGの差が一部よりも小さいノードを「分割解除」することを意味します。しきい値。

これらの2つのアプローチは同じ効果を持ちません。実際、剪定は優れた手法です。理由：分割しきい値をトップダウンで適用すると、もちろん一部の分割が防止されます。ただし、発生が許可されていた場合、次の分割（2つの子ノードの一方または両方の孫への分割）は有効な分割（つまり、しきい値を超える）であった可能性がありますが、その分割は発生しません。もちろん、剪定はこれを説明します。