Überwachtes Lernen I: Klassifikation und Regression · • Betragsfunktion (absoluter Abstand) und Maximum sind nicht überall differenzierbar. • Die Ableitung beim euklidischen

Institut für Programmstrukturen und Datenorganisation (IPD)Lehrstuhl für Systeme der Informationsverwaltung, Prof. Böhm

Praktikum Data Warehousing und Mining, Sommersemester 2009

Überwachtes Lernen I:Klassifikation und Regression

Praktikum:Data Warehousing und

Data Mining



Klassifikationsprobleme• Idee

• Bestimmung eines unbekanntenkategorischen Attributwertes(ordinal mit Einschränkung)

• Unter Benutzung beliebigerbekannter Attributwerte

• Beispiele:• Klassifikation von Spam• Vorhersage von Kundenverhalten wie Kündigungen (Churn)• Vorhersage von Kreditwürdigkeit• Beurteilung von industriellen Gütern• …

2



Regressionsprobleme• Idee

• Bestimmung eines unbekanntennumerischen Attributwertes(ordinale und kategorische Vorhersagendurch Schwellwertsetzung)

• Unter Benutzung beliebigerbekannter Attributwerte

• Beispiele:• Vorhersage von Kundenverhalten wie ‚Zeit bis Kündigung‘• Vorhersage von Kosten, Aufwand o.ä.• Voraussage von Verkaufszahlen, z.B. von Büchern• …

3



Prozess 1: Klassifikationsmodell lernen

4

Trainings-Daten

NAM E RANK YEARS TENUREDM ike Assistant Prof 3 noM ary Assistant Prof 7 yesBill Professor 2 yesJim Associate Prof 7 yesDave Assistant Prof 6 noAnne Associate Prof 3 no

KlassifikatorLernen

IF rank = ‘Professor’OR years > 6THEN tenured = ‘yes’

Klassifi-kator



Prozess 2: Vorhersagen mit dem Modell

5

Test-Daten

NAME RANK YEARS TENUREDTom Assistant Prof 2 noMerlisa Associate Prof 7 noGeorge Professor 5 yesJoseph Assistant Prof 7 yes

Neue Daten

(Jeff, Professor, 4)

Tenured?

Klassifi-kator



Überwachtes vs. Unüberwachtes Lernen• Überwachtes Lernen (Klassifikation, Regression)

• Bei den Trainingsdaten ist das Vorhersageattribut bekannt

• Die Zielgrößen neuer Datensätze werden auf Basis des gelernten Modells vorhergesagt

• Unüberwachtes Lernen (Clusteranalyse)• Die Vorhersageattribute (Klassen bzw. hier Cluster) des

Lerndatensatzes sind unbekannt

• Ziel ist es, aus Werten und Beobachtungen des Datensatzes eine Clustereinteilung zu finden

6



Techniken zum überwachten LernenTechnik Klassifikation Regressionk-Nearest Neighbour X XStatistische Techniken(Lineare Regression etc.)

(X) X

Entscheidungsbäume XRegressionsbäume (X) XNeuronale Netze X XSupport Vektor Maschinen (SVMs) X XRegelbasierte Techniken X XNaive Bayes XAssoziationsregeln zur Klassifikation X…

7


Praktikum Data Warehousing und Mining, Sommersemester 2009 8

Zum Einstieg: k-Nearest Neighbour• Gegeben:

• Lerndatensatz L

• Vorgehen zur Klassifikation eines Tupels t:• Menge S: die k nächsten Nachbarn von t in L• Klassifikation von t durch Klasse mit meisten Elementen in S

• Als Regressionsverfahren:• Vorhersage ist Mittelwert der Tupel in S

• Anmerkungen:• „Nähe“ über Distanzmaß (z.B. euklidische Distanz)• Kein Lernen im engeren Sinn• Vorhersage rechenaufwändig für große L• Einsatz nur sinnvoll bei wenigen, numerischen Attributen



Statistische Techniken zur Regression



Einfache Lineare Regression• Vorhersage der

Zielvariable y durch eine Prediktorvariable x

• Gegeben: Lerndatensatz D = {(x1, y1), (x2, y2),…, (xn, yn)}, n = |D|

• Vermutung eines linearen Zusammenhangs

• Gesucht: Geradey = w0 + w1 x• Bestimmung von w0, w1

(Regressionskoeffizienten)

10

w0 = 23,6 w1 = 03,5

y = 23,6 + 3,5 x

Lerndatensatz D:



Berechnung der Regressionskoeffizienten• Zunächst:

• Bestimmung des Fehlers als Summeder quadratischen Abweichungen

• E = Σi (yi – (w0 + w1 xi ))2

• Aus der notwendigen Bedingung für ein Minimum der Fehlfunktion lassen sich unter Verwendung von partiellen Ableitungen w0 und w1 berechnen:

x, y: Durchschnitt aller x1, x2, …, xn bzw. aller y1, y2, …, yn

(Rechenbeispiel: S. Data-Mining-Buch von J. Han, M. Kamber)11

∑

∑

=

=

−

−−= ||

1

2

||

1

)(

))((

1 D

ii

D

iii

xx

yyxxw xwyw 10 −=

yx,



Lineare Regression – Fehlermaße• Üblich ist:

• Mittlerer quadratischer Abstand in y-Richtung

• Andere sinnvolle Fehlermaße:• Mittlerer absoluter Abstand in y-Richtung• Mittlerer euklidischer Abstand• Maximaler absoluter/quadratischer Abstand in y-Richtung• Maximaler euklidischer Abstand

• Diese Maße können jedoch nicht verwendet werden:• Betragsfunktion (absoluter Abstand) und Maximum sind

nicht überall differenzierbar.• Die Ableitung beim euklidischen Abstand führt zu einem

nichtlinearen Gleichungssystem; ist nicht analytisch lösbar.

12



Multivariate Lineare Regression• Typischerweise steht nicht nur eine Prediktorvariable

x zur Verfügung, sondern mehrere (p) :Vektor Xi := xi,1, xi,2, …, xi,p

• Lerndatensatz: D = {(X1, y1), (X2, y2),…, (Xn, yn)}• Hyper-Ebene: y = w0 + w1 x1+ w2 x2 + … + wp xp

• Die Methode zur Minimierung der Fehler-Quadrate kann übertragen werden:Es entsteht ein lineares Gleichungssystem.• Lösbar mit linearer Algebra (Matrizen).• Lösung mit numerischen Methoden oft effizienter.

13



Lineare Regression – Bewertung• Eigenschaften

• Aufwand zum Lösen der Gleichungen: O(p³)• Koeffizienten sind eventuell interpretierbar.

• Vorteile• Relativ simples Modell:

p-dimensionale Hyperebene bei p Prediktorvariablen• Dient als Baseline zum Vergleich von Regressionstechniken.

• Nachteile• Gleichungen sind eventuell nicht lösbar, wenn Prediktor-

variablen (nahezu) linear abhängig voneinander sind.• Alle Prediktorvariablen werden betrachtet, auch irrelevante.• Anfällig für Outlier. (Ignorieren von Datenpunkten gefährlich!)• Nicht alle Probleme sind linear…

14



Nichtlineare Regression• Einige nichtlineare Probleme können als polynomielle

Funktion modelliert werden.• Polynomielle (u.a.) Funktionen können in lineare

Regressionsmodelle transformiert werden, z.B.:y = w0 + w1 x + w2 x2 + w3 x3

wird gemappt auf:y = w0 + w1 x + w2 x2 + w3 x3

• Die Methode zur Minimierung der Fehler-Quadrate mit Ableitungstechniken kann prinzipiell auf beliebige Funktionen übertragen werden.• Eventuell sehr hoher Rechenaufwand, aber oft nicht lösbar.• Hintergrundwissen kann helfen, einen Term zu finden.

15



Lokale Lineare Regression• Idee:

Mehrere einfache Regressionsfunktionen (hier Geraden) für verschiedene Wertebereiche von x

• Problem:Brüche an Wertebereichsgrenzen

• Eine Lösung:Splines „glätten“ die Übergänge

• Gut geeignet bei wenigen Prädiktorvariablen.

• Bestimmte Regressionsbäuzmegreiften die Idee „lokale Regression“ auf…

16

x

y

x

y



Weitere nichtlineare Verfahren• Oft ist eine numerische Parameter-Bestimmung aus

partiellen Ableitungen nicht möglich:• Parameter gehen nichtlinear in die Regressionsfunktion ein.• Ein alternatives Fehlermaß wird verwendet.

• Lösungsansatz: „Systematisches Trial and Error“1. Aufstellen einer (beliebigen) Regressionsfunktion.2. Suche nach geeigneten Parametern:

• Random Search• Hillclimbing• Varianten um lokale Minima zu verhindern• Genetische Algorithmen• …

17



Generalisierung vs. Overfitting

18

x

y

Too simple?

x

y

Too complex ?

x

y

About right ?

x

yTraining data



Entscheidungsbäume



Klassifikation - Entscheidungsbäume• Vorgehen

• Aufbau eines Baums• Knoten entspricht

Entscheidungskriterium• Blatt entspricht Entscheidung

• Vorteile• Ergebnis leicht interpretierbar• Übersetzbar in Regelsystem

• Diverse Verfahren• ID3 / C4.5 / C5.0 / J48• C&RT• Quest• Chaid• …

20

Zulassung

Verbrauch

Alter

nein ja

hoch niedrig

alt modern

kaufen

nicht kaufen

kaufen

nicht kaufen

Eine Regel (von mehreren):Wenn

Zulassung vorhanden und Verbrauch niedrig,

dann kaufen.



Vorgehen bei der Konstruktion01 Alle Datentupel im Wurzelknoten02 IF Stoppkriterium erreicht THEN03 Aktueller Knoten wird Blattknoten mit Majoritätsklasse04 ELSE05 Suche geeignetes Entscheidungssattribut (Splitattribut)06 Wende Algorithmus rekursiv auf Teilmengen an

Anschließend: Beschneide Baum (Pruning)

• Existierende Algorithmen unterscheiden sich in• … der Wahl des Stoppkriteriums• … der Art des Splits• … dem Vorgehen zur Wahl des Splitattributs• … dem Vorgehen zum Splitten eines Attributs• … der Wahl des Pruningverfahrens

21



Wahl des Stoppkriteriums• Natürliche Stoppkriterien

• Knoten enthält (fast) nur Tupel einer Klasse• Alle Tupel sind identisch bis auf die Klasse• Alle Klassifikationsattribute ausgeschöpft

• Weitere Kriterien• Minimale Tupelzahl je Knoten• Minimaler Anteil falsch klassifizierter Tupel• Maximale Baumtiefe• Maximale Knotenanzahl

22



Art des Splits• Diskrete vs. kontinuierliche Attribute

• Diskret• Ein Knoten pro

Attributwert

• Kontinuierlich: • Ein Knoten pro

Attributintervall

• Binäre vs. n-äre Bäume• Zwei oder mehrere Ausgangskanten

• Frage: Wie erreicht man binäre Bäume mit kategorischen Attributen?

• Frage: Wie gelangt man an Attributintervalle?23

Alter

5…10> 10< 5

Augenfarbe

rot grünblau



Wahl des Splitattributs• Beispiel (binäres Attribut)

• Objektmenge: 1 0 0 0 0 0 1 0 0 0 1 1• Verschiedene Splits möglich:

• Split A: 1 0 0 0 0 0 | 1 0 0 0 1 1• „Linke Seite“: 17% Fehler• „Rechte Seite“: 50% Fehler

• Split B: 1 0 0 0 0 0 1 0 0 | 0 1 1• „Linke Seite“: 22% Fehler• „Rechte Seite“: 33% Fehler

• Split C …

• Welcher Split ist vorzuziehen?• Festlegung eines Bewertungsmaßes

24



Informationsgewinn• Prinzip

• Maximierung des Informationsgewinns

• Vorgehen • Basiert auf Shannon-Entropie

• H = - ∑ni=1 pi log2 pi

• Informationsgewinn• Igain(C,A) = H(C) – H(C|A)• Igain(C,A) = - ∑|C|i=1 pi log2 pi – ∑|A|j=1 pj (- ∑|C|i=1 pi|j log2 pi|j)• H(C) – Entropie der Klassenverteilung (mit C – Klassenattribut)• H(C|A) – Erwartete Entropie der Klassenverteilung, wenn

Attribut A bekannt

25



Informationsgewinn - Beispiel• Berechnung des Informationsgewinns

• Allgemein:Igain(C,A) = - ∑|C|i=1 pi log2 pi – ∑|A|j=1 pj (- ∑|C|i=1 pi|j log2 pi|j)

• H(C) = - (4/12 * log2(4/12) + 8/12 * log2(8/12)) = 0,918• Split A:

• 1 0 0 0 0 0 | 1 0 0 0 1 1• Igain(C,A) = 0,918 – (6/12 * (-1) * (1/6 * log2(1/6) + 5/6 * log2(5/6))

Igain(C,A) = + 6/12 * (-1) * (3/6 * log2(3/6) + 3/6 * log2(3/6)))• Igain(C,A) = 0,918 – 0,325 – 0,500• Igain(C,A) = 0,918 – 0,825 = 0,093

• Split B:• 1 0 0 0 0 0 1 0 0 | 0 1 1• Igain(C,B) = 0,918 – (9/12 * (-1) * (2/9 * log2(2/9) + 7/9 * log2(7/9))

Igain(C,A) = + 3/12 * (-1) * (1/3 * log2(1/3) + 2/3 * log2(2/3)))• Igain(C,A) = 0,918 – 0,573 – 0,230• Igain(C,A) = 0,918 – 0,803 = 0,115

• Hier würde B bevorzugt

26



Gini Index• Prinzip

• Minimierung der Heterogenität

• Vorgehen • Wahrscheinlichkeitsmaß, bei Stichprobe Datentupel aus 2

unterschiedlichen Klassen zu erhalten:• Gini = 1 – p(0)² – p(1)²

• Minimum = 0,0• alle Objekte aus einer Klasse• Maximale Homogenität

• Maximum = 0,5• Objekte zweier Klassen gleich häufig• Maximale Heterogenität

27



Gini Index - Beispiel• Berechnung der Heterogenität

• Split A:• 1 0 0 0 0 0 | 1 0 0 0 1 1• Linke Seite = 1 - (1/6)2 - (5/6)2 = 0,278• Rechte Seite = 1 - (3/6)2 - (3/6)2 = 0,500

• Split B:• 1 0 0 0 0 0 1 0 0 | 0 1 1• Linke Seite = 1 - (2/9)2 - (7/9)2 = 0,346• Rechte Seite = 1 - (1/3)2 - (2/3)2 = 0,444

• Einfacher Durchschnitt• A: (0,278 + 0,500) / 2 = 0,389• B: (0,346 + 0,444) / 2 = 0,395

• Hier würde A bevorzugt

28



Weitere Bewertungsmaße• Chi-Quadrat-Test

• Maß für die Abhängigkeit zwischen Merkmal und Zielgröße

• Auswahl des Merkmals mit dem höchsten Chi-Quadrat-Wert (= stärkste Abhängigkeit)

• Minimale Beschreibungslänge (MDL)• Ähnlich Informationsgewinn• Zusätzlich „Strafe“ für zunehmende Komplexität

des Baums

29



Splitten eines Attributs• Nicht alle Attribute sind binär (Binärbäume)

bzw. haben genau n Attribute (n-äre Bäume).• Vorgehen kategorische Attribute:

• Es werden Bewertungsmaße für alle Aufteilungen der Klassen in 2 bzw. n Mengen berechnet.

• Z.B. {blau, rot, grün} bei Binärbäumen:{{blau, rot}, grün}, {blau, {rot, grün}} und {{blau, grün}, rot}

• Vorgehen numerische Attribute:1. Auf- oder absteigendes Sortieren der Attribute2. Setzen von allen Kombinationen von 1 bzw. (n-1) Splits• Alternativ: Diskretisieren des Attributs vor dem eigentlichen

Lernprozess (z.B. CHAID)

30



Pruning - Motivation

• Achtung: Die optimale Baumgröße ist bei jedem Datensatz unterschiedlich!

31

zuklein

gut(general-isierend)

Overfitting



Pruningverfahren• Gründe für Pruning komplexer Bäume

• Einfachheit / Verständlichkeit• Verhinderung von Overfitting / Generalisierungsfähigkeit

• Pre-Pruning: Stopkriterien bei Baumerstellung

• Post-Pruning: Nachträgliches Stutzen• Subtree Replacement

• Ersetzen von Entscheidungsknoten durch Blattknoten,wenn Klassifikationsbeitrag gering

• Optimal: Entscheidung zum Ersetzen mit „frischen“ Daten evaluieren• Subtree Raising

• Verschiebung von Teilbäumen nach oben• Insbesondere dann, wenn es Attribute gibt, die einzeln wenig, aber in

Kombination sehr stark zur Klassifikation beitragen.• Solche Attribute rutschen sonst sehr leicht weit nach unten.

32



Regressionsbäume



Regressionsbäume und Model Trees• Regressionsbäume:

Entscheidungsbäume, dessen Blätter anstatt kategorischen Labels numerische Zielgrößen enthalten (z.B. das Mittel aller Lerntupel im Knoten)

• Model Trees:Variante von Regressions-bäumen, deren Blattknoten je eine (multivariate lineare) Regressionsfunktion für alle Tupel eines Knotens enthalten

34

3,6

2,7

3,2

x1 <= 7

x1 <= 7

x2 >= 2

x2 >= 2

ja

ja

ja

ja

nein

nein

nein

nein



Regressionsbäume• Wie kann man einen Regressionsbaum lernen?

• Wie Entscheidungsbäume, aber…• …andere Wahl des Splitattributs und• …angepasstes Pruning.

• Wahl des Splitattributs…• …welches die Varianz minimiert.• …welches die Standardabweichung minimiert (M5).• …welches die stärkste Korrelation mit der Zielvariablen hat,

basierend auf dem p-Wert des statistischen F-Test (CHAID).• …welches die Fehlerquadrate minimiert (C&RT).

35



Splitattribut-Wahl mit Fehlerquadraten• Die Methode der Fehlerquadrate lässt sich auch hier

als Fehlermaß R in einem Knoten nutzen:• R ist die Summe der quadratischen Fehler von allen Tupeln i

im aktuellen Knoten t, geteilt durch die Anzahl der Tupel in t.• Die Fehler sind die Differenz des Zielwertes des jeweiligen

Tupels yi und dem Mittel der Zielwerte aller dieser Tupel in t.

• Es wird der Split gewählt, der R der beiden Kinder eines Knotens minimiert (bei Binärbäumen wie C&RT).

• So erhält man Tupel mit ähnlichen Werten in einem Knoten.

• Entsprechend bei Varianz/Standardabweichung…36

∑

∈−=

tityiy

ttR ))²((

||1)(



Model Trees• Lernen eines Model Trees (hier M5)

• Lernen des Baums zunächst wie bei Regressionsbäumen.• In jedem Knoten wird ein multivariates lineares

Regressionsmodell gelernt, auf Basis aller Attribute, die in den darunter liegenden Knoten getestet werden.

• Die Regressionsmodelle bilden auch die Basis für das anschließende Prunen…

• Vorhersagen mit dem Model Tree (auch M5)• Zunächst wie beim Entscheidungsbaum.• Das Regressionsmodell des Blattknotens liefert Vorhersage.• Vorhersagen sind unstetig, da lokale lineare Regression.• Abhilfe: Glätten der Funktion durch Einbeziehung der

Vorhersagen aller darüber liegenden Knoten bis zur Wurzel.

37



Regressionsbäume – Bewertung• Eigenschaften

• Bäume helfen eventuell beim Verständnis des Problems.• Model Trees im allgemeinen genauer.

• Vorteile• Oft besser als lineare Regression.• Hilfreich bei hochdimensionalen Problemen.• Behandlung von kategorischen Variablen möglich.• Im allgemeinen recht schnell; bei einzelnen Regressions-

funktionen findet Attributauswahl statt (Model Trees).

• Nachteile• Große Gefahr des Overfittings gegeben.• Der ganze Baum mit Regressionsgeraden stellt eine sehr

komplexe Funktion dar (Model Trees).38



Evaluationstechniken



Sampling bzw. Holdout• Die Leistung eines Klassifikators kann nicht mit dem

Lerndatensatz beurteilt werden!• Overfitting! Vgl. Motivation Pruning.

• Deshalb: Unterteilung der Ausgangsdaten in• Training Set zum Lernen des Klassifikators (oft zwei Drittel)• Test Set zur Evaluation des Klassifikators (oft ein Drittel)

• Beide Mengen sollten möglichst repräsentativ sein:• Stratifikation: Aus jeder Klasse wird ein proportionaler

Anteil in das Training- und Test Set übernommen.• Eine Unterteilung in Training- und Test Set ist oft

nicht möglich, wenn nicht genug Daten zur Verfügung stehen:• Ein kleines Test Set ist ggf. nicht mehr repräsentativ.• Ein kleines Training Set bietet ggf. zu wenig zum Lernen.

40



Klassifikation - VorgehenKlassifikator

lernen

Klassifikator testen

Klassifikator anwenden

Trainingsdaten

Testdaten

Produktivdaten

Klassifikations-regeln

optimierteKlassifikations-

regeln

41

modell

modell

s



Cross-Validation• Unterteilung der Ausgangsdaten in k Partitionen

• Typischerweise wird k=10 gewählt• Eine Partition bildet Test Set• k–1 Partitionen bilden Training Set

• Berechnung und Evaluation von k Klassifikatoren:• In k Runden wird jedes Datentupel k-1 mal zum Lernen

verwendet und genau ein mal klassifiziert.

• Stratifizierte Cross-Validation ist in vielen Fällen die zu empfehlende Evaluationstechnik, besonders aber bei kleinen Datensätzen.

• Achtung: Cross-Validation ist sehr Rechenaufwändig• „Leave-One-Out“ ist Spezialfall für k=n

42



Evaluationsmasse für Klassifikatoren• Konfusions-Matrix

• accuracy = (TP + TN) / (TP + FN + FP + TN)

• sensitivity = TP / (TP + FN)

• specificity = TN / (FP + TN)

• precision = TP / (TP + FP)

• lift = precision / P(ja); P(ja) = (TP + FN) / (TP + FN + FP + TN)

43

True Negatives (TN)False Positives (FP)Nein

False Negatives (FN)True Positives (TP)Ja

NeinJa

Vorhersage

Tatsächliche Klasse



Evaluation von Regressionstechniken• Es existieren viele Techniken…

• Data Mining Cup:Die Summe aller Abweichungen (aller 8 Bücher bei allen vorauszusagenden Händlern) von der bekannten Anzahl an Buchverkäufen.

44



Quellen• J. Han und M. Kamber: „Data Mining: Concepts and

Techniques“, Morgan Kaufmann, 2006.• Hand, H. Mannila und P. Smyth: "Principles of Data Mining",

MIT Press, 2001.• T. M. Mitchell: „Machine Learning“, Mc Graw Hill, 1997• I.H. Witten und E. Frank: "Data Mining - Practical Machine

Learning Tools and Techniques", Morgan Kaufmann, 2005. D. • F. Klawonn: Folien zur Vorlesung „Data Mining“, 2006.• Pierre Geurts: Folien zur Vorlesung „Stochastic methods“.• SPSS: Clementine 12.0 Algorithms Guide. 2007.• C. Borgelt: Folien zur Vorlesung „Intelligent Data Analysis“,

2004. Vorlesungsskript verfügbar (120 Seiten):http://fuzzy.cs.uni-magdeburg.de/studium/ida/txt/idascript.pdf

45

Documents

Überwachtes Lernen I: Klassifikation und Regression · • Betragsfunktion (absoluter Abstand) und Maximum sind nicht überall differenzierbar. • Die Ableitung beim euklidischen