Entscheidungsbäume/ Support Vector Machines

• Beobachtungen: Im Testdatensatz zeigt der Entscheidungsbaum eine falsch-prädizierte Klassifikation?

• Lösungen:

  • Baumtopologie verändern

  • Trainingsdatensatz vergrößern

Gesucht:

• Minimaler Entscheidungsbaum

  • Zuerst das Feature nutzen, bei dem Pfad möglichst nur eine Klasse enthält!

• Metriken:

  • Informationsentropie

  • Gini-Index: Statistisches Maß für die Reinheit einer Klasse

  • Wähle Merkmal mit niedrigsten Gini-Index zuerst im Entscheidungsbaum

  • bei mehreren Möglichkeiten: Merkmal mit den meisten Observationen

FOLIEN NACHSCHAUEN -> Seite 34 zusammenfassung

• Merkmale werden aus dem Wissen über Eigenschaften des Objekts abgeleitet

• Merkmalswerte können aus dem System ermittelt werden (bekannte Brennweite, Entfernung, Teilzeichungen, Geldmünzendurchmesser) oder durch “golden Samples” / Musterteile

• Bei Kombination verschiedener Merkmale:

  • Entscheidungsbäume etc.

Arbeitsablauf:

• Objektprüfung durch (bspw.) Bildverarbeitungs- und Produktdesign-Experten

• Auswahl und Komination charakteristischer Merkmale (Data Mining)

• Schwellenbestimmung bzgl. Entscheidungsgrenzen

• Implementierung /Erprobung / Verbesserung

• Bisher: Experte entwirft Baumtopologie und setzt Gewichte bzw. Schwell(en)werte

• Ansatz: Computer ist in der Lage auf Basis bestehender Beispiele selbst zu klassifizieren

  • Kein selbstständiges Entwicklen einer Netztopologie!

    • Kein maschinelles Lernen im engeren Sinne da kein generalisierbares Lernen (Inductive Learning)

  • Klassifikation durch Vergleiche

Lernphase (Training):

• Bestimmte und “labele” Beispieldatensätze zweier Kalssen (z.B. i.O. und nicht i.O.)

• Berechne Merkmalsvektoren (z.B. Fläche, Umfang, Farbe etc.) der Beispieldatensätze

• Abspeichern von Labeln und Markmal in Datenbank (Knowledge Base)

Inferenz (Fitting):

• Berechne Merkmalsvektor für unklassifizierten, neuen Datensatz (nach selben Regeln)

• Finde den ähnlichsten Merkmalsvektor (z.B.: euklidischen Abstand)

  -> Suchbäume für Performanz

• Übertrage Klassifikation / Label des nächsten Nachbarn auf neuen Datensatz

• wenn mehrere Merkmale allein die Daten nicht signifikant klassifizieren, aber kombiniert den Datensatz gut separieren können

• Ziel: Zerlegung des 2D-Featureraums in zwei Halbräume durch Trennlinie

• Jeder Halbraum ist mit einem Klassenlabel verbunden: Neue (unbekannte) eingehende Daten können durch ihren Merkmalshalbraum klassifiziert werden

• “Beste” Trennlinie: Größter Randbereich

  • Schwellenwerttolerranz größer

  • Klassifikation robuster

• Aufgabe: Bestimmung von Linien-Parametern so, dass der beidseitige Rand (kleinster Abstand zu Trainings-Merkmalsvektoren) maximal wird

  1. Berechne Trennlinie mit wenigen Zufallsstartwerten

  2. Finde naheliegende Samples

  3. Verändere Linie so, dass Klassenlinie für diese Samples besser wird; weiter bei 2. bis Konvergenz bzw. Optimum

• Berührpunkte des Toleranzbandes für Klassentrennlinie heißen Support Vektoren

• Bedingung:

  • Hyperebene kann nicht deformiert werden

• Perfekte Klassifikation nur bei linearer Separierbarkeit der Merkmalsvektoren

• Was tun…?

  • Selektion von besseren Merkmalen

  • Vergrößerung des Merkmalsvektors

  • Fehlklassifikationen akzeptieren

  • Transformation der Daten in eine höhere Dimension durch nicht-lineare Projektion ->Kernel-Trick

• Perfekte Klassifikation oft nur bei overfitting

• 1D: Punkt

• 2D: Gerade

• 3D: Ebene

• nD: Hyperebene

• Ein System wird an einigen bestimmten Punkten gemessen / beobachtet, einschließlich Rauschen und Ungenauigkeiten

• Die Anpassung eines Polynoms hoher Ordnung könnte die Beobachtung perfekt abbilden, aber ein Überschwingen zwischen den Beobachtungspunkten verursachen und somit das Systemverhalten schlechter darstellen als ein Fit niedrieger Ordnung -> Overfitting

• Ein Modell niedrigerer Ordnung mit einem gewissen Resttrainingsfehler könnte am Ende die beste Wahl sein!

• Merkmale müssen nicht in höherdimensionale Merkmalsraum transformiert werden

• Nichtlineares Abstandsmaß für Separationsoptimierung kann direkt aus Kernel berechnet werden

• Kernel besitzt signifikaten Einfluss auf Separierbarkeit

  • Häufig in Kombination mit (Transformation nach) Hauptkomponentenanalyse

• Einige Trainingsdaten / Samples benötigen möglicherweise eine Gewichtung bei der Berechnung der Hyperebene

Vorteile:

• Kritische Samples können “betont” werden

• Quantitativ unterrepräsentierte Klassen können gleichberechtigt behandelt werden

• Unsicherheiten in den Trainigsdaten können adressiert werden

Pros:

• Grundsätzlich größere Wahrscheinlichkeit der Separierbarkeit

• Häufig Separierbarkeit durch Kombination von Merkmalen

Cons:

• Merkmale können redundant sein (z.B. Fläche und Masse)

• Merkmale nicht sensitiv, konstant oder unkorreliert

  • Verschwendung von Rechenressourcen

  • Separation nicht signifikanter Daten führt zu Overfitting: Schlechte Prädiktion für unbekannte Daten

Merkmale sollten sorgfältig ausgewählt werden:

• Häufig in Kombination mit Hauptkomponentenanalyse, Sensitivitätsanalyse, Dimensionsreduktion

• Klassifikationsfehler bzw. maximal erreichbare Prädiktionsgenauigkeit muss ggf. akzeptiert werden

• Es gibt keinen Optimierungsalgorithmus und kein Lernverfahren, das für die Menge aller Probleme bzw. Datensätze und Fragestellungen universell gut ist

• Es gibt keinen universellen Algorithmus der immer am besten funktioniert

• es muss die Aufgabenstellung bzw. die Art der zu erwarteten Daten und eine Struktur vorgegeben werden

• ein guter Algorithmus verwendet also implizit oder explizit Vorwissen über die Art der Daten bzw. des zu lösenden Problems. z.B. per Gewichtungen/ Wahl der Features / Programmstruktur / Wahl der Abbruchkriterien etc.