Datamining

• Hierarchisches Clustering
• K-Means (nichtdeterministisch)
• SVM..

Herausforderungen:

• Nicht robust im ermitteln der exakten Anzahl der Cluster
• Ergebnis hängt von Methoden des Clustering ab

Aufgabe: eine Gruppe von Artikel finden die häufig gemeinsam gekauft werden

Ergebnisse werden üblicherwiese als Assoziationsregel A->B ausgedrückt, wobei

• Unterstüzung der Regel = Häufigkeit {A,B}
• und Vertrauen in die Regel = Pr{B|A} hoch genug ist.
• Interesanter Parameter der Regel ist lift = Pr(B|A)/Pr(B)
  • Pr(B) = Wahrscheinl. B zu kaufen, Regel liften die Wahrscheinlichkeit B zu kaufen

Herausforderung: finden aller Regeln mit minimaler Unterstützung und minimalem Vertrauen in großer Datenmenge!

Anwendungen: Körbe=Dokumente, Artikel = Wörter; Gemeinsam vorkommende Wörter implizieren für ein Gebiet charakteristische Phrasen; Benutzt zur aut. Textklassifikation

Eingabedaten: Zeitreihenvariable(n) über den bestimmten gleichen, Zeitspanne

Es wird angenommen das die Daten einen Trend, eine Saisonales Verhalten und Rauschen besitzen.

Prognose wird durch extrapolation von Trends der Vergangenheitswerte durchgeführt.

Anwendung: Stromverbrauch, Verkaufsdaten, Meteorologie

Methoden: ARIMA, Exponential Smoothing Models, AutoRegressive Bäume

Eingabedaten {x₁,y₁)....(x_n,y_n)}

1. finden eines Modells des Zusammenhangs zwischen Y und X₁,X₂,...,X_d

2. Bestimmung der Prognosegüte des Modells für unbekannte Daten

X_i .. Inputvariable (auch: unabhängige Variable, Predictor, Regressor, erklärende Variable, Faktor, oder Covariate genannt)

Y...Zielvariable (auch Antwort genannt)

Wir suchen Y(X) - unter der Annahme, das der Zusammenhang linear ist

Viele nicht-lineare Probleme können mittel lineare Regression modelliert werden - durch Anwendungen von transformationen auf den Variablen.

Regression kann auch zur Klassifikation benutzt werden (logistische Regression)

Linear Annahme ist auch wichtig in Klassifikation (zb. Diskriminanzanalyse, Hyperraum-Trennung (Perceptron))

Notation:

• Eingabedaten: X€R^d
• Ausgabedaten: Y€R^d
• Verbundwahrscheinlichkeitsverteilungsfunktion:PR(X,Y)

Aufgabe: Finden einer Funktion f(X) zur Prognose des Wertes von Y

Diese Funktion soll den Quadratischen Fehler minimieren - Lösung REgressionsfunktion (siehe Grafik)

Von der Theorie zur Praxis:

Regressionsfunktion f(x) = E(Y|X=x) basiert auf der bekannten Verbundswahrscheinlichkeitsfunktion von X und Y.

Die Bestimmung einerFunktion f anhand der Eingabedaten {x₁,y₁)....(x_n,y_n)} kann parametrisch oder nicht-parametrisch passieren.

Wir nehmen an, dass f(x)=E(X=x) eine Linearfunktion von X₁,X₂,...,X_d ist: (siehe Grafik oben)

Als X_j können quantitative Eingabevariablen, nicht-lineare Transformationen der Eingabe (log), numerisch codierte Qualitative Variablen sein.

Anpassung des Modells:

Bestimmung von Beta (ß) basiert auf den Eingabedaten durch Minimierung der Residuen der Summe der Quadrate RSS(ß) (sieh Grafik unten)

Verifikation des Modells:

Güte der Anpassung muss Verifiziert werden bevor Model zur Prognose herangezogen wird.

Prüfung erfolgt mit Hilfe von:

• Diagnostischen Plots
  • visuell die Linearitäts-Annahme verifizieren (y-Achse Zielvariable, x-Achse Eingabeparamtervariable)
  • sowie x-Achse: Predicted Value, y-Achse Residual (y_observed-_ypredicted) - Trend in Plot  zeigt Model ist nicht adequat
• Hypothesentest (Parametersignifikanz)
  • Test der Hyptohese H₀: B_j=0
  • wenn p-Wert <0.05 wird Hypothese verworfen und Parameter ist relevant
• Messung des Residuenfehlers
  • Root MSE: durschnittl. quadratischer Fehelr in Regression
  • R² gibt an wieviel der Varianz der Daten erklärt werden konnten. (1 ist Bestwert)

Prolbem: Regression basiert auf allen Merkmalen von X, wie findet man die besten Merkmale?

Vorwärts: hinzufügen von Parametern zu Modell

Rückwärts: mit allen Parametern starten, dann entfernen

Schrittweise: wie Vorwärts, aber Parameter kann auch wieder entfernt werden an Hinzufügung

Regression: Annahme Linearfunktion von X₁,...X_d

Nichtparametrisch: Nearest Neighbours Methode:

f(x) = Average(y_i|x_i€N_k(x))

• N_k(x).. Nachbarschaft von x welchen die k nähesten Point zu x beinhalten
• Versuch der Bestimmung von f^(x) = E(Y|X=x) direkt aus den Daten.
• Theorem: wenn n,k-->unendlich, k/n-->0, dann f^(x)-->E(Y|X=x)

Notation:

• X€R^d ..... Eingabevariablen
• Y€C={c₁,c₂,...,c_M} .... mögliche Y-Werte
• x€C_i wenn Y(x)=c_i (x gehört zur Klasse c_i)

Die Annahme ist wie bei Regression, dass Verbundwahrscheinlichkeitsverteilungsfunktion Pr(X,Y) von X und Y bekannt ist.

Loss-Matrix L_MxM - zur Betrafung von Misklassifikationensentscheidungen des Klassifizierers f

L(i,j)=0 für x€c_i und f(x)=c_j und i gleich j
L(i,j)=1 für x€c_i und f(x)=c_j und i ungleich j

Gesucht wird ein Klassifizierer f(X) welchen den erwarteten Prognosefehler minimiert:

EPE=E(L(Y,f(X)))

Lösung zur minimierung des erwarteten Fehler: Bayes

f(x)=c_k für Pr(c_k|X=x)=maxPr(c|X=x), wobei c€C

Regel: Klassifiziere x in jene Klasse c_k welche am ehesten innerhalb der bedingten Verteilung Pr(Y|X=x) erweist.

Bayes Klassifizierer ist optimal zur Minimierung der Klassifizierungsfehlerwahrscheinlichkeit

Enfache Regel:

Pr(c₁|x)>Pr(c₂|x) --> klassifziere zur Klasse c₁
Pr(c₁|x)<Pr(c₂|x) --> klassifziere zur Klasse c₂

oder für gleichwahrscheinliche Klassen:

Pr(x|c₁)>Pr(x|c₂) --> klassifziere zur Klasse c₁
Pr(x|c₁)<Pr(x|c₂) --> klassifziere zur Klasse c2
 

Problem: Bestimmung von Pr(c_i|x) ist anhand der Daten schwierig, leichter ist die Bestimmung Pr(x|c_i)

Bayes Regel: siehe Grafik

Pr(ci|x) bekannt als posteriori Wahrscheinlichkeit

Pr(c_i) bekannt als a priori Wahrscheinlichkeit - kann aus Trainingsdaten bestimmt werden - als Frequenzen von Beispielenn verschiedener Klassen

wegen überlappenden Merkmalen

einziger Weg diesen Fehler zu reduzieren ist, mehr Information über zu klassifizierende Daten zu bekommen (d.h. mehr Merkmale)

Um die anhand der Bayes Regel entstanden Merkmalsräume immer in disjunkte Regionen getrennt.

Analytische Lösung für p(x|c_i), i=12,..M bei Normalverteilung LDA, QDA

Iterative Algorithmen zur Anpassung von Hyperebenen bei nicht normal-verteilten Daten

LDA definiert die Bayes (optimalen) Klassifizierer für p(x|c_i) normalverteilt, (mit selber covarianz Matrix in allen Klassen)

Danach werden ß₀,ß₁,...,ß_d basierend auf den Durchschnitten und Kovarianzen der Merkmale in verschiedenen Klassen berechnet.

QDA definiert den Bayes (optimalen) Klassifizierer für den allgemeinen Fall von p(x|c_i) normalverteilt.

Idee: 

• Y, diskret zB 0/1
• p=Pr(Y=1|X=x)
• Logit(p)=log(p/(1-p))
• wir modellieren logit(p) als Linearfunktion von Merkmalen

es wird kein Annahme über eine Verteilung in den Trainingsdaten gemacht

Mittels Perceptron Algorithmus findet man ß,ß₀ (siehe Grafik)

Idee: finde ß durch Lösung einer Optimierungsaufgabe in der die cost J(ß) von falschklassifizierungen minimiert werden.

J(ß) = Summe misklas. |<ß,x>|

ß wird durch iterative Minimierung von J(ß) durch Gradienten Abstiegsmethode

nach Transformation der Variablen wir das Problem im neuem Koordinatensystem linear separierbar --> multilayer Perceptron (siehe Grafik)

jeder Knoten mit Hiddenschicht verbunden, ein Output Knoten, Stuktur siehe Grafik

Es können auch meherer Output Knoten möglich sein (siehe Grafik)

Quantitave Eingabedaten: ein Neuron pro Eingabevariable

Ordinale/Nomiale Eingabedaten: Variable mit N ebenen wird zu einer N dummy Variable geändert (mit werten 0,1 um die Klassenzugehörigkeit zu dokumentieren)

Nachteil: NN ist ein "Blackbox" System, es ist unmöglich den Prognosevorgang nachzuvollziehen.

Idee: Prognosewerte für unbekannte Menge von Eingaben basiert auf k nähesten Nachbarn der Trainingsdatenmenge.

nicht-parametrisches Verfahren

kann als ein ansatz zum Vergleich p(x|c1) vs p(x|c2)  direkt aus den Daten heraus gesehen werden (siehe Grafik)

Distanzmaße:

euklid

Manhattan distance: Summe der absoluten Differenzen zwischen korrespondierenden Werten

Correlation Distanz = 1-cor(v₁,v₂), wobei cor der Korrelationskoeffizient zwischen Vektor v1, v2 darstellt.

Wurzel: die gesamte Datenmenge

Blätter: entsprechen den Klassifikationsentscheidungen

Rekursive Partitionierung der Daten um die Reinheit zu erhöhen; Partionierung erfolgt solange bis Partionen rein oder klein sind.

Maße der Reinheit: entropy, gini-Index

Algorithmen: CART, C4.5, C 5.0

VT: einfach zu Verstehen

NT: schlechte Robustheit - kleine Änderungen in den Eingabedaten führen zu stark unterschiedlichen Baumstrukturen, daher Random Forest

Wie wählt man ein Attribute welches zum Datensplit verwendet wird, aus?

siehe nächsten drei Karteien

Wie lange soll der Prozess des Splittens andauern?

Regel: stoppe wenn der Knoten rein oder klein ist (min n - parameter des Algorithmus)

Was ist die beste Höhe/Größe des Baums?

Problem des Overfitting/bauen eines zu einfachen Baums

Regel: bestimme Fehler (Fehlklassifikationsfehler) von Trainig und Testdaten

Schrumpfe zu große Bäume um die Kosten zu reduzieren

Ansatz I: Basierend auf der Messung des Zusammenhangs von Variablen X_i und Y

Idee: für jedes x_i i=1,2,...,d berechne den pWert für Hypothese H0: X_i und Y sind unabhängig

Splitte Knote s unter Verwendung der Variable X_i, wo der pWert der kleinste ist (auf jeden Fall 0.05)

mögliche Test hierfür: Chi-Quare, F oder ANOVA

AnsatzII: Maximiere einige Kriterien zur Qualität des Splits (zB. entropy-reduktion, varianz-reduktion,..)

Idee: 

Definiere I(S) als Maß der Unreinheit des Knoten S

wenn split basierend auf Variable A basiert, definiere ein Qualitätsmaß des Splits als:

W(S,A)=I(S)-Summe p(b)I(S_b)

(Summe über alle Teilungen b welche Knoten S p(b) - Wahrscheinlichkeit der Auswahl der Teilung b)

Selektiere Splittung anhand A, maximiere Maß W

Entropie (Y€C={c1,c2,..cm})

oder GiniIndex (siehe Grafik)

Beide Maße liefern:

maximalWert für die Gleichverteilungen aller Klassen (=1/M)

0, wenn pi=1 für einige i (alle Daten gehören zu einer einzigen Klasse)

Szenario: 3 konkurriende Splits eines Knotens möglich

Notation: n1/n2 ... Anzahl der Observationen der Klassen "1"/"2" im Knoten

Wir selektieren den Split um W zu maximieren (siehe Grafik)

Bäume:

Klassifikationsprozess kann nachvollzogen werden und als Menge von Regeln ausgedrückt werden

nicht sehr robust (kleine Änderungen in Eingabedaten, liefern gänzlich andere Strukturen) --> Random Forest

Neuronale Netze

"Black Box" - Klassifikationsprozess kann nicht nachvollzogen werden

robuster als Bäume

Aufgabe: finde eine separierende Hyperebene mit der Bedingung maximiere den Rand (Margin)

--> Löse dazu ein Optimierungsproblem (siehe Grafik links)

Lösung: (siehe Grafik rechts)

ß = Summe (i=1 bis N) Alpha_iy_iX_i

_{mit Alphai ungleich 0 nur für Punkte am Range des separierenden Ebene (Support Vektors)}

Erlauben nicht-linear separierbare Daten

finden des separierenden Hyperebene --> Lösung des vorherigen Optimierungsproblem mit anderen Bedingungen (siehe Grafik links)

Slackvariable erlauben das Ausmaß in welcher die Prognose ß0+<ß,xi> auf der falscher Seite des Randes (Margin) liegen darf

Zur Bindung der Summe der Slackvariablen liegt die Lösung, dass ß nur abhängig von den Supportvektoren ist. (siehe Grafik links unten)

Gebe Lösung für ß in die Defintion von f(x) -> Formel: Grafik oben

Duale Repräsentation: daten nur im Skalarprodukt

Verrauschte oder nicht-separierbare Daten nicht umgehbar

Lösung: Verschiebe Daten in höher-dimensionalen Merkmalsraum und separiere sie dort.  Formel: Grafik mitte

man benötigt nicht die Transformation h() - nür Kernel werden gebraucht (siehe Grafik unten)

zu komplexe Klassifizierer verlieren ihre Generalisierungseigenschaft, werden anfällig für Overfitting

Overfitting

Versuch der Minimierung des Traingsfehlers durch Parameter-Tuning

Performanz des Klassfizierers mus auf einer ihm unbekannten Datenmenge erfolgen

Oft ist eine große Lücke zwischen Trainingfehler und Testfehler ersichtlich --> das wird Overfitting genannt

Overfittinggefahr steigt mit Modellkomplexität bzw. Dimensionalität des Problems

Zu simpler Klassifizierer ist nicht fährig den Zusammenhang zwischen Ziel und Eingabedaten herzustellen

Es ist ein Kompromiss zwischen der flexibilität des Klassifizierers und seiner Generalisierungsfähigkeit zu finden!

Vermeidung von Overfitting durch:

Featureauswahl basierend auf hyptothesen-Tests oder PCA

bei geringer Anzahl an Eingabedatenmenge - diese Wiederverwenden (Crossfolds)