Grundlagen der KI: Entscheidungsbäume, Neuronale Netze & GA

Entscheidungsbäume

Vorteile

• Einfach zu implementieren
• Regeln sind extrahierbar
• Nicht-inkrementell (sehr effizient und praktisch, ohne Backtracking)

Nachteile

• Zielfunktion muss diskret sein
• Probleme bei der Klassifizierung

Stopp-Kriterien

• Alle Beispiele gehören zur gleichen Klasse
• Alle Proben haben den gleichen Attributwert
• Der Informationsgewinn ist unerheblich
• Die Anzahl der Proben hat eine Grenze erreicht

Overfitting

Wenn die Anzahl der Knoten zu groß ist, basieren die Entscheidungen auf sehr kleinen Partitionen der Proben, was die Verallgemeinerung reduziert.

Formeln

Ent(S) = -(p⁺ * log₂ p⁺) - (p^- * log₂ p^-), wobei S die Menge der Beispiele für den Knoten ist, p⁺ die Wahrscheinlichkeit positiver Ausgänge und p^- die Wahrscheinlichkeit negativer Ausgänge.

Info(Attribut A) = Σ (P(v_i) * Ent(v_i)), wobei P(v_i) die Wahrscheinlichkeit des Wertes i ist (Anzahl der Beispiele mit Wert i / Gesamtzahl der Beispiele).

E-info(S, A) = Ent(S) - Info(A).

Algorithmus

1. Wählen Sie das beste Attribut, um die Beispiele zu teilen.
2. Erweitern Sie den Baum durch Erstellung eines neuen Zweigs für jeden Wert des gewählten Attributs.
3. Verteilen Sie die Beispiele auf jeden Knoten entsprechend ihrem Wert.
4. Wiederholen Sie dies für jedes Blatt, bis die Stopp-Kriterien erreicht sind:

• 4.1: Wenn alle Beispiele derselben Klasse angehören, weisen Sie dem Knoten die Klasse zu.
• 4.2: Wenn nicht, wiederholen Sie die Schritte 1 bis 4.

Rekursive Funktion: geraArvore(Exs)

1. Wenn ein Stopp-Kriterium erfüllt ist, gib ein Blatt zurück.
2. Wähle das beste Attribut, um Exs aufzuteilen, und erstelle einen Knoten.
3. Für jeden Attributwert i: Baum_i = geraArvore(Exs_i).
4. Gib den Teilbaum mit den Nachkommen zurück.

Neuronale Netze

Hauptmerkmale (Vorteile)

• Fähigkeit zu lernen und sich anzupassen
• Generalisierungsfähigkeit
• Klassifizierungsfähigkeit
• Einsatz bei Klassifizierung, Kategorisierung und Optimierung
• Schnelle und einfache Implementierung

Perceptron

Fehler = (gewünschte Ausgabe - Netzausgabe)

Δw = C * Fehler * x_i

w_ij(t + 1) = w_ij(t) + Δw

MLP (Multi-Layer Perceptron)

Fehler = 1/2 * Σ (gewünschte Ausgabe - Netzausgabe)²

Δw_ij = x_i * C * A, wobei A = (Fehler * f'(net)) bei Ausgangsknoten oder (Σ A_{nachfolgende Schicht} * w) * f'(net) bei verborgenen Schichten.

Stopp-Kriterien

• Maximale Anzahl der Iterationen
• Fehler in der Ausbildung unterschreitet einen Schwellenwert
• Fehler steigt in der Validierungsphase k-mal in Folge an

Genetische Algorithmen

Normalisierung des Eingangsvektors

X = min + (max - min) * Basiswert / (2^{Anzahl der Bits} - 1)

Stopp-Kriterien

• Keine Verbesserung der Fitness
• Beste Lösung gefunden (falls bekannt)
• Verlust der Vielfalt
• Maximale Anzahl der Generationen erreicht