Folien vom 11. Mai 2015

Fachprojekt: Data-Mining und Datenanalyse
Nico Piatkowski
11.05.2015
2/8
Übersicht
I Heute:
I
I
I
Frequent Set Mining mit FP-Growth
Clustering mit DB-Scan
Themenübersicht und Beispielthemen
I Montag:
I
I
Besprechung der Themen
Daten IO mit Java
Termine:
I Kein Treen am nächsten Mittwoch (13.05.2015)
I Thema/Proposal bis nächsten Montag (18.05.2015)
3/8
Frequent Set Mining
Gegeben: Datensatz
X = {0, 1}d ,
D = x (i ) 1≤i ≤N
Min-Support
m∈N
mit diskreter Domäne
. Jedes
x (i )
ist die vektorielle
Darstellung einer Menge (Indikatorvektor, Transaktionsdaten)
Frage: Welche sind die häugsten Teilemengen (frequent sets,
frequent pattern)?
Denition:
⇒
M
ist häug
⇔
M
kommt in
D
häuger als
Naives Nachzählen hat exponentielle Komplexität!
Bessere Algorithmen:
I A-priori (beim letzten Treen)
I FP-Growth (jetzt)
m
mal vor
O(2d )
4/8
FP-Growth
Grundlegende Beobachtungen:
1. Der Datensatz
D
muss mindestens einmal komplett betrachtet
werden, um alle häugen Mengen (und ihre Häugkeiten) zu
bestimmen
2. Bei Verwendung einer geeigneten Datenstruktur, ist
möglicherweise ein Scan von
D
ausreichend
3. Häuge Mengen mit gleichen Objekten können beim zählen
zusammengefasst werden. Zusammengefasste Teilmengen
teilen sich die Zähler
4. Eine beliebige aber feste Ordnung der Objekte erlaubt das
Zusammenfassen in einem Präxbaum. Der Baum wird kleiner,
wenn die Ordnung der Objekte auf den Häugkeiten basiert
5/8
Density-based Clustering (DB-Scan)
Problem mit
k
-Means: Es können nur Runde Cluster gefunden
werden!
Alternative Cluster denition:
1. Punkte in einem Cluster haben höchstens Abstand
Nachbarn
2. Ein Cluster enthält mindestens
m
Punkte
ε
zu ihren
6/8
Übersicht:
I Überwachtes Lernen:
I
Regression, Klassikation
I Zielfunktionen
I
I Unüberewachtes Lernen:
I
Clustering, Probabilistic
(Mixture-)Models, Missing
Data, Frequent Pattern
Mining
I Modellklassen
I
linear, polynomiell,
probabilistisch, Nearest
Neighbor, Entscheidungsbaum
I Optimierungsalgorithmen
I
Gradientenabstieg,
(Quasi-)Newton
Erwarteter Fehler,
Log-Likelihood (+ untere
Schranke), k -Means
I Fehlerfunktionen
I
L1 ,L2 , Acc, Hinge
I Data-Mining Algorithmen
I
I
I
I
Lloyds Algorithmus (k -Means
Heuristik), DB-Scan
Expectation Maximization
A-Priori, FP-Growth
Entscheidungsbauminduktion
I Abhängigkeit: Kullback-Leibler
Divergence, Mutual Information
7/8
Beispielthemen:
I Unüberewachtes Lernen, Clustering, Vergleich von
k
-Means
und DB-Scan
I Unüberewachtes Lernen, Mixture-Models mit EM (Maximum
Likelihood Schranke), Vergleich von Gaussian und Poisson
I Überwachtes Lernen mit Gradientenabstieg, Klassikation,
lineares Modell(+Hinge-Loss), Vergleich mit
Entscheidungsbaum(+Inf-Gain)
I Überwachtes Lernen, Klassikation, Probabilistisches Modell
(Multinomial, Maximum Likelihood), Vergleich von
Grid-Diskretisierung und Cluster Diskretisierung
8/8
Datensätze:
I UC Irvine Machine Learning Repository:
http://archive.ics.uci.edu/ml
I Statistisches Bundesamt:
https://www.destatis.de/DE/Startseite.html
I Andere Quellen!?

Download Report