T - Dbs

Transcript

DATABASE SYSTEMS GROUP 3.5 EntscheidungsbaumKlassifikatoren Motivation Autotyp ID 1 2 3 4 5 Alter 23 17 43 68 32 Autotyp Familie Sport Sport Familie LKW Risiko hoch hoch hoch niedrig niedrig = LKW ≠ LKW Risikoklasse = niedrig Alter > 60 Risikoklasse = niedrig ≤ 60 Risikoklasse = hoch finden explizites Wissen Entscheidungsbäume sind für die meisten Benutzer verständlich 58 Grundbegriffe DATABASE SYSTEMS GROUP • Ein Entscheidungsbaum ist ein Baum mit folgenden Eigenschaften: • • • ein innerer Knoten repräsentiert ein Attribut, eine Kante repräsentiert einen Test auf dem Attribut des Vaterknotens, ein Blatt repräsentiert p eine der Klassen. • Konstruktion eines Entscheidungsbaums • anhand der Trainingsmenge • Top-Down Autotyp = LKW ≠ LKW Risikoklasse = niedrig Alter > 60 • Anwendung eines Entscheidungsbaums Risikoklasse = niedrig ≤ 60 Risikoklasse = hoch Durchlauf des Entscheidungsbaum von der Wurzel zu einem der Blätter ⇒ eindeutiger Pfad Zuordnung des Objekts zur Klasse des erreichten Blatts 59 DATABASE SYSTEMS GROUP Konstruktion eines g Entscheidungsbaums Basis-Algorithmus • Anfangs gehören alle Trainingsdatensätze zur Wurzel. • Das nächste Attribut wird ausgewählt (Splitstrategie). • Die Trainingsdatensätze werden unter Nutzung des Splitattributs partitioniert. g • Das Verfahren wird rekursiv für die Partitionen fortgesetzt. ⇒ lokal optimierender Algorithmus Abbruchbedingungen • keine weiteren Splitattribute • alle Trainingsdatensätze g eines Knotens gehören g zur selben Klasse 60 Entscheidungsbaum-Klassifikatoren DATABASE SYSTEMS GROUP Beispiel Tag 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Aussicht sonnig sonnig bedeckt regnerisch g regnerisch regnerisch bedeckt sonnig sonnig regnerisch sonnig b d kt bedeckt bedeckt regnerisch Temperatur heiß heiß heiß mild kühl kühl kühl mild kühl mild mild mild ild heiß mild Feuchtigkeit hoch hoch hoch hoch normal normal normal hoch normal normal normal h h hoch normal hoch Wind schwach stark schwach schwach schwach stark stark schwach schwach schwach stark stark t k schwach stark Tennispielen nein nein ja ja jja nein ja nein ja ja ja j ja ja nein I t heute Ist h t ein i Tag T zum Tennisspielen? T i i l ? 61 DATABASE SYSTEMS GROUP Entscheidungsbaum-Klassifikatoren Beispiel Aussicht sonnig Feuchtigkeit hoch „nein“ regnerisch bedeckt Wind „ja“ normal „ja“ stark „nein“ schwach „ja“ 62 DATABASE SYSTEMS GROUP Splitstrategien Typen von Splits • Kategorische Attribute Splitbedingungen der Form „Attribut = a“ or „Attribut ∈ set“ viele mögliche Teilmengen Attribut = a1 = a2 = a3 Attribut ∈ s1 ∈ s2 • Numerische Attribute Splitbedingungen der Form „Attribut Attribut < a“ a viele mögliche Splitpunkte An A d den S Stellen, ll di die di die Qualität Q li ä maximieren. i i Idee: Ordnen der numerischen Attributwerte Wert 0.9 0.8 0.65 0.5 0.45 0.3 0.15 0.01 Klasse A A B B B A A A Potentielle Splitkandidaten Teste die Kombination Kombination, die den höchsten Information Gain erzielen. erzielen Schnellere Methode: • Bilde Gauß-Kurve über alle Klassen • Wähle Schnittpunkte der Gauß-Kurven als l Kandidaten. K did t Potentielle Splitkandidaten 64 DATABASE SYSTEMS GROUP Splitstrategien Qualitätsmaße für Splits Gegeben • eine Menge g T von Trainingsobjekten g j • eine disjunkte, vollständige Partitionierung T1, T2, . . . , Tm von T • pi die relative Häufigkeit der Klasse ci in T Gesucht • ein i M Maß ßd der Unreinheit U i h it einer i M Menge S von Trainingsobjekten T i i bj kt in i B Bezug auf die Klassenzugehörigkeit • ein Split p von T in T1, T2, . . . , Tm , der dieses Maß der Unreinheit minimiert ⇒ Informationsgewinn, Gini-Index 65 DATABASE SYSTEMS GROUP Splitstrategien Informationsgewinn Entropie: minimale Anzahl von Bits zum Codieren der Nachricht, mit der man die Klasse eines zufälligen Trainingsobjekts mitteilen möchte möchte. Die Entropie für eine Menge T von Trainingsobjekten ist definiert als k entropie i ( T ) = − ∑ pi ⋅ llog pi i =1 entropie(T) = 0, falls pi = 1 für ein i entropie(T) t i (T) = 1 für fü k = 2 Klassen Kl mit it pi = 1/2 Das Attribut A habe die Partitionierung T1, T2, . . . , Tm erzeugt. Der A in auff T ist als D Informationsgewinn I f i i des d Attributs A ib i Bezug B i definiert d fi i l | Ti | ⋅ entropie(Ti ) i =1 | T | m Informationsgewinn(T , A) = entropie(T ) − ∑ 66 DATABASE SYSTEMS GROUP Splitstrategien Gini-Index Gini-Index für eine Menge T von Trainingsobjekten k gini(T ) = 1 − ∑ pj 2 j =1 – kl kleiner i Gi Gini-Index i I d ⇔ geringe i U i h i Unreinheit, – großer Gini-Index ⇔ hohe Unreinheit Das Attribut D A ib A habe h b die di Partitionierung P ii i T1, T2, . . . , Tm erzeugt. Gini-Index des Attributs A in Bezug auf T ist definiert als |Ti | giniA (T) = ∑ ⋅ gini(Ti ) i =1 | T| m 67 DATABASE SYSTEMS GROUP Splitstrategien Beispiel p 9 „ja“ 5 „nein“ Entropie = 0,940 9 „ja“ 5 „nein“ Feuchtigkeit g hoch 3 „ja“ „ja 4 „nein „nein“ Entropie = 0,985 Entropie = 0,940 Wind normal 6 „ja“ „ja 1 „nein „nein“ Entropie = 0,592 schwach stark „ja“ 2 „nein“ „ 6 „j 3 „ja“ j 3 „nein“ Entropie = 0,811 Entropie = 1,0 7 7 ⋅ 0,985 − ⋅ 0,592 = 0,151 14 14 8 6 Informationsgewinn(T , Wind ) = 0,94 − ⋅ 0,811 − ⋅1,0 = 0,048 14 14 Informationsgewinn(T , Feuchtigkeit ) = 0,94 − ⇒ Feuchtigkeit liefert den höheren Informationsgewinn 68 DATABASE SYSTEMS GROUP Bias 69 DATABASE SYSTEMS GROUP Overfitting Einführung Overfitting bei der Konstruktion eines Entscheidungsbaums, wenn es zwei Entscheidungsbäume E und E’ gibt mit Kllassifikatioonsgenauigkeit – E hat auf der Trainingsmenge eine kleinere Fehlerrate als E E’, – E’ hat auf der Grundgesamtheit der Daten eine kleinere Fehlerrate als E. auf Trainingsdaten auf Testdaten Baumgröße 70 DATABASE SYSTEMS GROUP Overfitting Trainingsdaten Name Body Temp Gives Birth Four-legged Hibernates Mammal porcupine warm-blooded yes yes yes yes cat warm-blooded yes yes no yes bat warm-blooded yes no yes no* whale warm-blooded yes no no no* salamander cold-blooded no yes yes no komodo dragon cold-blooded no yes no no python cold-blooded no no yes no salmon cold-blooded no no no no eagle warm-blooded no no no no guppy cold-blooded yes no no no *Fehlerhafte Daten 71 DATABASE SYSTEMS GROUP Overfitting Testdaten Name Body Temp Gives Birth Four-legged Hibernates Mammal human warm-blooded yes no no yes pigeon warm-blooded no no no no elephant warm-blooded yes yes no yes leopard shark cold-blooded yes no no no turtle cold-blooded no yes no no penguin warm-blooded no no no no eel cold-blooded no no no no dolphin warm-blooded yes no no yes spiny anteater warm-blooded no yes yes yes gila monster cold-blooded no yes yes no 72 DATABASE SYSTEMS GROUP Overfitting Trainingserror: 0% T Testerror: 30% M1: • Fehlklassifikation von human und d l hi aufgrund dolphin f d von fehlerhaften Trainingsdaten • Spiny anteater: g ungewöhnlicher Fall M2: ungewöhnlicher Trainingserror: 20% Fall kann nicht T Testerror: 10% vermieden werden 73 DATABASE SYSTEMS GROUP Overfitting Name Body Temp Gives Birth Four-legged Hibernates Mammal salamander cold-blooded no yes yes no poorwill warm-blooded no no yes no platypus warm-blooded no yes yes yes eagle warm-blooded no no no no guppy cold-blooded yes no no no Problem: Mangel an repräsentativen Daten 74 DATABASE SYSTEMS GROUP Overfitting Ansätze zum Vermeiden von Overfitting • Entfernen von fehlerhaften Trainingsdaten i b insbesondere d widersprüchliche id ü hli h Trainingsdaten T i i d • Wahl einer geeigneten Größe der Trainingsmenge nicht zu klein, nicht zu groß • Wahl einer geeigneten Größe des minimum support minimum support: Anzahl der Datensätze, die mindestens zu einem Blattknoten des Baums gehören müssen minimum support >> 1 75 DATABASE SYSTEMS GROUP Overfitting Ansätze zum Vermeiden von Overfitting • Wahl einer geeigneten Größe der minimum confidence minimum confidence: Anteil, den die Mehrheitsklasse eines Blattknotens mindestens besitzen muß. minimum confidence << 100% Blätter können auch fehlerhafte Datensätze oder Rauschen „absorbieren“ • nachträgliches Pruning des Entscheidungsbaums Abschneiden der überspezialisierten Äste kleinere Bäume sind weniger anfällig für Overfitting (Occam (Occam‘ss Razor) 76 DATABASE SYSTEMS GROUP Pruning von Entscheidungsbäumen Fehlerreduktions-Pruning [Mitchell 1997] • Aufteilung der klassifizierten Daten in Trainingsmenge und Testmenge • Konstruktion eines Entscheidungsbaums E für die Trainingsmenge • Pruning von E mit Hilfe der Testmenge T - bestimme denjenigen Teilbaum von E, dessen Abschneiden den Klassifikationsfehler auf T am stärksten reduziert - entferne diesen Teilbaum - fertig, falls kein solcher Teilbaum mehr existiert nur anwendbar, wenn genügend viele klassifizierte Daten 77 DATABASE SYSTEMS GROUP Entscheidungsbaum-Klassifikatoren Diskussion + Interpretation des gefundenen Baumes relativ einfach + Implizite p Gewichtung g der Attribute + Leistungsfähiger Klassifikator, häufig in der Praxis verwendet + Effiziente Auswertung des gefundenen Modells - Finden eines optimalen Entscheidungsbaums ist exponentiell - Heuristische Methoden können nur lokales Optimum finden - Anfällig für Overfitting (besondere Methoden zur Vermeidung von Overfitting für Entscheidungsbäume) 78 DATABASE SYSTEMS GROUP 3.6 Neuronale Netze Grundlagen [Bigus 1996], [Bishop 1995] • Paradigma P di fü für ein i M Maschinenhi und d Berechnungsmodell B h d ll • Funktionsweise ähnlich der von biologischen Gehirnen Neuronales Netz: Menge von Neuronen, über Kanten miteinander it i d verbunden b d Neuron: entspricht biologischem Neuron Aktivierung durch Input-Signale an den Synapsen • Menschliches Gehirn: 1011 Neuronen, Neuronen jedes verbunden mit ~10 104 anderen, schnellste Aktionszeit 10-3 Sek. (Computer: 10-10) – aber komplexe Entscheidungen sehr schnell (visuelle Erkennung der eigenen Mutter: 10-11 Sek. Sek ≈ 100 Schritte) • Erzeugung eines Output-Signals, das zu anderen Neuronen weitergeleitet wird. • Organisation O i ti eines i neuronalen l N Netzes t Input-Schicht, verborgene Schichten, Output-Schicht Knoten einer Schicht mit allen Knoten der vorhergehenden Schicht verbunden 79 DATABASE SYSTEMS GROUP Grundlagen Kanten besitzen Gewichte Funktion eines neuronalen Netzes Vorhergesagte Klasse Output-Vektor y Output-Schicht verborgene g Schicht wij Input-Schicht wij Input-Vektor x 80 DATABASE SYSTEMS GROUP Neuronen allgemeines Neuron (auch: Perzeptron) a: Aktivierungswert x1 x2 n a = ∑ wi ⋅ xi w1 × × . . w. 2 i =1 xn Threshold Logic Unit x1 (TLU) x2 y= 1 1 + e −a wn w1 × × y . . w. 2 xn × Σ a × Σ a θ a ⎧1, wenn a ≥ θ y=⎨ ⎩ 0, sonst wn 81 Neuronen DATABASE SYSTEMS GROUP Beispiel: Modellierung einer booleschen Funktion x1 x2 x3 y 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 x1 x2 xn × × × 0.3 y 03 0.3 Σ a θ a ⎧1, wenn a ≥ θ y=⎨ 0 sonst ⎩ 0, 0.3 θ=0.4 82 DATABASE SYSTEMS GROUP • Neuronen Klassifikation mit Hilfe einer TLU x2 n • repräsentiert ä i eine i (Hyper-)Ebene (H )Eb • links von der Ebene: Klasse 0 • rechts ht von der d Ebene: Eb Kl Klasse 1 ∑w ⋅x i =1 i i =θ 1 0 1 0 • 1 0 0 1 0 1 1 1 1 0 0 1 0 Trainieren einer TLU x1 • Lernen der „richtigen“ Gewichte zur Unterscheidung der zwei Klassen Iterative Anpassung der Gewichte wij • Rotation der durch w und θ gegebene Hyperebene um einen kleinen Betrag in Richtung v, wenn v noch nicht auf der richtigen Seite der Ebene liegt 83 DATABASE SYSTEMS GROUP XOR-Problem nicht linear separierbares Problem 84 DATABASE SYSTEMS GROUP Kombination mehrerer Neuronen zwei Klassen, die nicht linear separierbar sind: ⇒ mehrere innere Knoten (hidden layer) und ein Output-Knoten (zweiKlassen-Problem, sonst mehr) Varianten: feed-forward vs. recurrent (auch Verbindungen auf derselben Ebene oder zu vorherigen Ebenen möglich) 85 DATABASE SYSTEMS GROUP Kombination mehrerer Neuronen XOR 86 DATABASE SYSTEMS GROUP Kombination mehrerer Neuronen Beispiel 1 0 A A A A A A B B y A A A A A 1 B A h1 = 0 ∧ h2 = 0 : y = 0 ( Klasse B ) A B A B B 0 B A A h1 h2 andernfalls : y = 1 ( Klasse A) B 87 DATABASE SYSTEMS GROUP Lernalgorithmus für komplexe Neuronale Netze Bei Abweichung von vorhergesagter und tatsächlicher Klasse: Anpassung der Gewichte mehrerer Knoten Frage g In welchem Maße sind die verschiedenen Knoten an dem Fehler beteiligt? Anpassung der Gewichte • durch Gradientenverfahren, das den Gesamtfehler minimiert • Gesamtfehler: Summe der (quadratischen) Abweichungen des tatsächlichen Outputs y vom gewünschten Output t für die Menge der I Inputvektoren. k (Least (L S Squares O i i Optimierung) ) • Voraussetzung: Output y stetige Funktion der Aktivierung a 88 DATABASE SYSTEMS GROUP Algorithmus Backpropagation für j jedes Paar(v,t) ( , ) // v = Input,t p , = g gewünschter Output p „forward pass”: Bestimme den tatsächlichen Output y für Eingabe v; „backpropagation”: Bestimme den Fehler (t - y) der Output-Einheiten und passe die Gewichte der Output-Einheiten Output Einheiten in die Richtung an, die den Fehler minimiert; Solange der Input-Layer nicht erreicht ist: Propagiere den Fehler auf die nächste Schicht und passe auch dort die Gewichte der Einheiten in f hl fehlerminimierender i i i d W i Weise an; 89 Design der Netztopologie DATABASE SYSTEMS GROUP Bestimmung g von • Anzahl der Input-Knoten g Anzahl der Knoten • Anzahl der inneren Schichten und jjeweilige • Anzahl der Output-Knoten starker Einfluss auf die Klassifikationsgüte: • zu wenige Knoten ⇒ niedrige i d i Klassifikationsgüte Kl ifik ti üt • zu viele Knoten ⇒ Overfitting O fitti 90 DATABASE SYSTEMS GROUP Bestimmung der Netztopologie nach [SPSS Clementine 2000] Statische Topologie – Topologie wird a priori festgelegt – eine verborgene Schicht reicht in vielen Anwendungen aus Dynamische Topologie – dynamisches Hinzufügen von Neuronen (und verborgenen Schichten) solange Klassifikationsgüte signifikant verbessert wird M lti l Topologien Multiple T l i – Trainieren mehrerer dynamischer Netze parallel z.B. B jje ein i N Netz mit i 1 1, 2 und d 3 verborgenen b Schichten S hi h 91 DATABASE SYSTEMS GROUP Bestimmung der Netztopologie Pruning • Trainieren eines Netzes mit statischer Topologie • nachträgliches Entfernen der unwichtigsten Neuronen solange Kl ifik i Klassifikationsgüte ü verbessert b wird id Schlussfolgerung • statische Topologie: niedrige Klassifikationsgüte, aber relativ schnell. • Pruning: beste Klassifikationsgüte, aber sehr hoher L f it f Laufzeitaufwand d zum Training. T i i 92 DATABASE SYSTEMS GROUP Diskussion + im Allgemeinen g sehr hohe Klassifikationsgüte g beliebig komplexe Entscheidungsflächen (möglichst einfache Topologie auswählen, um Overfitting zu vermeiden) + redundante Features relativ problemlos, problemlos Gewichte werden klein + Effizienz der Anwendung - schlechte Verständlichkeit (lernt nur Gewichte, aber keine Klassenbeschreibung) Ineffizienz des Lernens (sehr lange Trainingszeiten) keine Integration von Hintergrundwissen - empfindlich gegen Fehler in den Trainingsdaten - mögliche Konvergenz in lokales Minimum 93