Pruning

Pruning: Bedingt irrelevante Attribute

Baum: $\alpha = x_1(x_2(A, B), x_2(A, B), x_2(A, B))$

$x_1$ ist bedingt irrelevant => Vereinfachung: $\alpha = x_2(A, B)$

Allgemein:

• Sei $\tilde{x}$ Weg zu Nichtendknoten $x_t$
• Baum dort $\alpha/\tilde{x} = x_t(\alpha_1, \ldots, \alpha_{m_t})$
• $x_t$ ist bedingt irrelevant unter der Bedingung $\tilde{x}$, wenn $\alpha_1 = \alpha_2 = \ldots = \alpha_{m_t}$
• Vereinfachung: Ersetze in $\alpha/\tilde{x}$ den Test $x_t$ durch $\alpha_1$

Anmerkung: Der durch das Entfernen von bedingt irrelevanten Attributen entstandene Baum hat exakt die selbe Aussage (Klassifikation) wie der Baum vor dem Pruning.

Anmerkung: $x_1$ im obigen Beispiel ist sogar global irrelevant, da es sich hier um die Wurzel des Baumes handelt. Der Weg $\tilde{x}$ ist in diesem Fall der leere Weg ...

Pruning: Bedingt redundante Attribute

Baum: $\alpha = x_1(\ast, \ast, x_2(A, B))$

$x_1$ ist bedingt redundant => Vereinfachung: $\alpha = x_2(A, B)$

Allgemein:

• Sei $\tilde{x}$ Weg zu Nichtendknoten $x_t$
• Baum dort $\alpha/\tilde{x} = x_t(\ast, \ldots, \ast, \alpha_i, \ast, \ldots, \ast)$ (mit $\alpha_i \neq \ast$)
• $x_t$ ist bedingt redundant unter der Bedingung $\tilde{x}$
• Vereinfachung: Ersetze in $\alpha/\tilde{x}$ den Test $x_t$ durch $\alpha_i$

Anmerkung: Der durch das Entfernen von bedingt redundanten Attributen entstandene Baum hat eine etwas andere Klassifikation als der Baum vor dem Pruning. Wo vorher ein * ausgegeben wurde, wird nach dem Pruning u.U. ein Klassensymbol ausgegeben. Der Klassifikationsfehler erhöht sich aber nicht, da hier ein * wie ein falsches Klassensymbol zu werten ist.

Anmerkung: $x_1$ im obigen Beispiel ist sogar global redundant, da es sich hier um die Wurzel des Baumes handelt. Der Weg $\tilde{x}$ ist in diesem Fall der leere Weg ...

Allgemeine Transformationsregel

Wrap-Up

• Pruning: Entfernen bedingt redundanter und irrelevanter Tests
• Transformationsregel zum Umbauen von Entscheidungsbäumen