Datamining

Transformiere die Originalmenge von p Variablen (von n Beobachtungen) zu einer unkorrelierten Menge von p latenten Variablen = Principal Components

Varianz der Daten ist den ersten latenten Variablen absteigen nach deren Varianz geordnet vorhanden

Anwendung:

Technik zum Analysieren von Hochdimensionalen Daten

Erste Principal Component werden benutzt um die Anzahl der Variablen in Predictive Modeling zu reduzieren

von p numerischen Variabeln können p Pricinipal Components (gleiche Anzahl) berechnet werden.

Jeder PC ist eine Linearkombination der Originalvariablen, deren Koeffizient den Eigenvektor ihere Korrelations (Kovarianz)matrix ensprechen.

Eigenvektoren werden üblicherweise als einheitlänge genommen

PC werden absteigend  nach derem Eigenwerten sortiert, was deren Varianz entspricht.

Nicht-Hierarische Methoden:

• K-Means Clustering
• nicht-deterministisch, O(n) Anzahl der Beobachtungen

Hierarische Methoden

• Agglomerative (kleine Cluster zusammenhängen)
• Divisive (große Cluster splitten)
• Deterministische Methoden
• O(n²) bis O(n³) - abhängig von der Methode (bzw. Intercluster Distanz)

Clustering von großen Datenmengen: K-Means, wenn hierarisch zuerst teilung mittel k-means in 50 Cluster dann hiererachisch clustern

Consensus Clustering: Erforschung "echter" Cluster in Daten - analysiere Stabilität der Ergebnisse mit verrauschten Daten

Ergebnis: k seperierte Cluster

Anforderung: Angabe von k nötig; Problem: ist vorab zu bestimmen

Bezeichnungen:

x_i....Observationen (i=1..n)
C_k.. Cluster
G...aktuelle Anzahl an Cluster
D_KL..Distanz zwischen clusters C_K and C_L

Clusterdistanz D_KL - linkage Funktion (versch.Definitionen verfügbar, Ergebnis hängt von D_KL ab. - siehe Grafik

Algorithmus (Agglomeratives Hierarchisches Clustering)

C_k={x_k], k=1..n, G=n
finde K, L sodaß D_KL = min D_u, 1<=I,J>=G

Ergebnis: Hierarchie von Cluster-->Dendrogramm

Verschiedene Definitionen:
 

Average Linkage
Single Linkage
Complete Linkage
Density Linkage
Ward's minimum Varianz Methode
---

Tendiert dazu Cluster mit geringer Varianz zu clustern
Cluster tendieren dazu ähnliche Varianz zu haben

Notation:

xi – observations, i=1..n
–
d(x,y) – distance between observations (Euclidean distance assumed from now on)
–
Ck – clusters
–
NK – number of observations in cluster CK
–
DKL – distance between clusters CK and CL
–
meanCK – mean observation in cluster CK
–
WK= Σ |xi-meanCK|2 xi∈CK – variance in cluster

Resultierende Cluster tendieren dazu, ähnliche Durchmesser zu haben.

Notation:
–
xi – observations, i=1..n
–
d(x,y) – distance between observations
–
Ck – clusters
–
NK – number of observations in cluster CK
–
DKL – distance between clusters CK and CL
–
meanCK – mean observation in cluster CK
–
WK= Σ |xi-meanCK|2 xi∈CK – variance in cluster

Tendieren dazu, langestreckte/längliche Cluster zu bilden, mit unregelmäßigen Umriß

Notation:
–
xi – observations, i=1..n
–
d(x,y) – distance between observations
–
Ck – clusters
–
NK – number of observations in cluster CK
–
DKL – distance between clusters CK and CL
–
meanCK – mean observation in cluster CK
–
WK= Σ |xi-meanCK|2 xi∈CK – variance in cluster

Tendiert dazu kleine Cluster zusammenzuhängen und produziert Cluster mit gleicher Anzahl an Observationen

Notation
–
xi – observations, i=1..n
–
d(x,y) – distance between observations
–
Ck – clusters
–
NK – number of observations in cluster CK
–
DKL – distance between clusters CK and CL
–
meanCK – mean observation in cluster CK
–
WK= Σ |xi-meanCK|2 xi∈CK – variance in cluster
–
BKL=WM-WK-WL where CM=CK∪CL

es wird ein single-linkage unter Verwendung des Maß d* realisiert

ermöglicht das erforschen von cluster mit unregelmäßigem Umriß

Notation:
–
xi – observations, i=1..n
–
d(x,y) – distance between observations
–
r – a fixed constant
–
f(x) – proportion of observations within sphere centered at x with radius r divided by the volume of the sphere (measure of density of points near observation x)

1. Standardisierung von Variablen vor dem Clustering

oft nötig, sonst tenden Variablen mit großer Varianz dazu den Cluster zu dominieren

Das Standardisierungsmaß z_ij wird oft als z-Score berechnet (siehe Grafik)

x_ij ..... Originalmaß der Beobachtung i und variable j

mü_j ... Mittelwert der Variable j

sj... mittlere absolute Abweichung der Variable j (oder seine Standardabweichung)

2. Die Anzahl der Cluster

Keine Theorie zum Ermitteln der korrekten Anzahl

oft Hilt eine Visuelle Darstaellung (wenn 2-3 Dimensional), ev. vorherige PCA (od. ähnliche) Transformation

Algorithmus gleich zu K-Means

Idee:

Selektiere k Punkte (initale Clusterzentroiden)
Für die Beobachtung x_i finde den nähesten Zentroiden (winner Seed); wird mit S_n beschrieben

Modifiziere S_n according to the formula:

S_n=S_n(1-L)+x_iL

L...Lernkonstante (verringert sich während des Lernprozesses)

Wiederhole Schrtte 2 und 3 über alle Trainingsdaten

Wiederhole Schritte 2-4 für eine gegebene Anzahl an Iterationen

Idee:

selektiere k initiale Punkte (cluster zentroid) bilde sie auf 2D Map ab (siehe Grafik)

Für Beobachtungen xi finde winning Seed S_n

Modifiziere alle Zentroiden so:

Sj=Sj (1-K(j,n)L)+xiK(j,n)L

L.. Lernkostante (verringert sich während Training)
K(j,n) ... Funktion verringert mit steigender Entfernung auf der 2D Karte zwischen Sj i Sn Zentroiden  (K(j,j)=1)

Wiederhole Schritte 2 und 3 für alle Trainingsbeobachtungen

"Fortschrittliche Methoden zum Entdecken und Modellieren von Beziehungen in großen Datenmengen"

"Erforschung von nützlichen Zusammenhängen innerhalb von Daten"

"Prozess der Identifikation von nützlichen Mustern und regelmäßigkeiten in großen Datenkörpern"

Mulitdisziplinär (siehe Grafik):

Verschiedenen Ansätze der Datenanalyse:

Data Mining: Beziehungen in Daten erforschen

DataWarehouse/OLAP: mulitdimensionales Modell

SQL: Abfragen auf Rohdaten

• Predicitve Modelling
• Cluster analysis
• Dependency derivation (association rules)
• web mining
• Text mining
• Sequence Matching
• Time Series Forecasting

Historische Daten, Input Variablen (Attribute des Objekts), Zielvariable

Pred.Mod. beinhaltet:

• erstellen eines Modells von Zielbeziehungen
• ermittlung der Prognosegüte dieses Modells für unbekannte Daten

Modellierungsmöglichkeiten

• Klassifikation: für qualitative Ziele
• Regression: für quantitative Ziele

Methoden/Algorithmen für Pred. Mod.:

• Lineare Regression
• Lineare/Nichtlineare Diskriminanzanalyse
• Logistische Regression
• Classification u. Regression Trees
• Neuronale Netze
• SVM
• Nichparametrische Verfahren (Nearest Neighbor)

Amwendung: Kreditrisiko, Versicherungsbetrug, Genetik (risiko gruppen vorhersage, vorhersage Chemotherapie..), Produktionsbetriebe (Assement, Qualität)

finde Gruppen von Objekten die sich ähnlich sind aber unähnlich zu andern Gruppen. Keine Zielvariable (unüberwachtes Lernen)

Anwendung: Customerprofiling, Target Marketing, Bioinformatics (ähnliche Gene, Krankheitstaxonomie ähnlicher Muster)

• 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