Datamining
Datamining Process
Datamining Process
Kartei Details
| Karten | 58 |
|---|---|
| Sprache | Deutsch |
| Kategorie | Informatik |
| Stufe | Universität |
| Erstellt / Aktualisiert | 02.09.2013 / 07.02.2018 |
| Weblink |
https://card2brain.ch/box/datamining
|
| Einbinden |
<iframe src="https://card2brain.ch/box/datamining/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
Datenwiederverwendungsmöglichkeiten
Standardansatz (Anzahl Datensätze > Anzahl Dimension)
Teilung in training/validierung und testMenge (aus dieser Menge wird der EPE (Estimation of Expected Prediction Error) ermittelt
Anzahl<Dimension Fall --> nicht genug Daten zum Validieren und Testen:
K-Fold cross validation oder leave one out crossvalidation
Performanz des Klassifizierers messen
Konfusionsmatrix aus aktuellen und Prognosewert (siehe Grafik oben)
oder ROC (Receiver Opterating Characteristics)-Kurve zeichnen - Grafik unten.
jeder Punkt repräsentiert eine cut-off Wahrscheinlichkeit
bis 0.5 Wertloses Modell, ab 1 perfekter Klassifizierer
Fluch der Dimensionalität
in höheren Dimensionraum gibt es weniger Trainingsdaten im Eingangsraum, daher werden andere Data-Mining Techniken wie Clustering, K-nearest Neighbor angewandt
Principal Components Analysis (PCA) - Idee
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
PCA - Technische Details
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.
Clustermethoden hierarchisch - nicht hierararisch
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(n2) bis O(n3) - abhängig von der Methode (bzw. Intercluster Distanz)
Clustermethoden Anmerkungen
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
K-Means - Algorithmus
Ergebnis: k seperierte Cluster
Anforderung: Angabe von k nötig; Problem: ist vorab zu bestimmen
HIerarchisches Clustering - Notation
Bezeichnungen:
xi....Observationen (i=1..n)
Ck.. Cluster
G...aktuelle Anzahl an Cluster
DKL..Distanz zwischen clusters CK and CL
Clusterdistanz DKL - linkage Funktion (versch.Definitionen verfügbar, Ergebnis hängt von DKL ab. - siehe Grafik
Algorithmus (Agglomeratives Hierarchisches Clustering)
Ck={xk], k=1..n, G=n
finde K, L sodaß DKL = min Du, 1<=I,J>=G
Ergebnis: Hierarchie von Cluster-->Dendrogramm
Definition von Distanzen zwischen Cluster
Verschiedene Definitionen:
Average Linkage
Single Linkage
Complete Linkage
Density Linkage
Ward's minimum Varianz Methode
---
Average Linkage
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
Complete Linkage
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
Single Linkage
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
Wards minimum Varianz Methode
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
Density Linkage
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)
Clustering Methoden - letzte Anmerkungen
1. Standardisierung von Variablen vor dem Clustering
oft nötig, sonst tenden Variablen mit großer Varianz dazu den Cluster zu dominieren
Das Standardisierungsmaß zij wird oft als z-Score berechnet (siehe Grafik)
xij ..... 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
Kohonen VQ (Vector Quantization)
Algorithmus gleich zu K-Means
Idee:
Selektiere k Punkte (initale Clusterzentroiden)
Für die Beobachtung xi finde den nähesten Zentroiden (winner Seed); wird mit Sn beschrieben
Modifiziere Sn according to the formula:
Sn=Sn(1-L)+xiL
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
Kohonen SOM (Self Organizing Maps)
Idee:
selektiere k initiale Punkte (cluster zentroid) bilde sie auf 2D Map ab (siehe Grafik)
Für Beobachtungen xi finde winning Seed Sn
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
