CAL3

CAL3: Erweiterung von CAL2 für nicht-disjunkte Klassen

1. Anfangsschritt: ${\alpha }^{(0)}=\ast$ (totales Unwissen)

2. $n$-ter Lernschritt: Objekt $v$ mit Klasse $k$

   • Rückweisung (Endknoten mit $\ast$): Ersetze $\ast$ durch Vereinigungsklasse $/k1/$

   • Endknoten mit Vereinigungsklasse:

     • Zähler für $k$ erhöhen, bzw.
     • $k$ mit Anzahl $1$ in Vereinigungsklasse einfügen

   Falls nun die Summe aller Klassen am Endknoten größer/gleich $S_1$ (Statistikschwelle):

   • Für genau eine Klasse gilt: $P(k|\tilde{x})\ge S_2$: => Abschluss: Ersetze Vereinigungsklasse durch $k$ (für immer!)

   • Für alle Klassen gilt: $P(k|\tilde{x})<S_2$: => Differenzierung: Ersetze Vereinigungsklasse durch neuen Test: $\kappa \leftarrow x_{t+1}(\ast ,\dots ,\ast ,/k1/,\ast ,\dots ,\ast )$

     $x_{t+1}$: nächstes Attribut, auf dem aktuellen Pfad $\tilde{x}$ noch nicht verwendet Symbol $k$ mit Anzahl 1 an Position $i$ wenn $x_{t+1}(v)=i$

Beispiel mit CAL3

• $S_1=4,S_2=0.7$

Ergebnis: $x_1(A,x_2(B,A))$

Trainingsfehler: $1/5=0.2<1-S_2=1-0.7=0.3$

Hinweis: Bei nicht überlappenden Klassen erzeugt CAL3 u.U. andere Bäume als CAL2 ...

CAL3: Abbruchbedingungen und Parameter

• Parameter:

  • $S_1$: Statistikschwelle, problemabhängig wählen
  • $S_2$: $0.5<S_2\le 1.0$
  • Klassifikationsfehler kleiner als $1-S_2$
    • kleiner Fehler => großer Baum
    • großer Fehler => kleiner Baum

• Abbruch:

  • Alle Trainingsobjekte richtig klassifiziert => Kein Fehler in einem kompletten Durchlauf
  • Alle Endknoten mit eindeutigen Klassensymbolen belegt
  • Differenzierung nötig, aber alle Merkmale verbraucht
  • Lernschrittzahl überschritten

Wrap-Up

• CAL3: Erweiterung von CAL2 für überlappende Klassen
  • Parameter $S_1$ (Anzahl Objekte bis Entscheidung), $S_2$ (Dominanz?)
  • Trainingsfehler wg. überlappender Klassen!