−Table of Contents
Knowledge Discovery in Databases I
Übung 1
Aufgabe 1
- a) Klassifikation (erst des Bildes: Suchen nach Nummernschild. Dann von Buchstaben) & supervised (Man weiß, wie Nummernschilder aussehen)
- b) Klassifikation & supervised (Es sind bereits klassifizierte Daten gegeben)
- c) Outlier Detection & unsupervised
- d) Clustering, evtl. Regression, Assoziation & unsupervised
- e) Assoziation & unsupervised
- f) Clustering, Assoziation & unsupervised
- g) Kein Datamining
- h) Kein Datamining
- i) i) Regression & supervised
- i) ii) Klassifikation & supervised
- i) iii) Regression, unsupervised
Übung 8
Aufgabe 1
Start | 2d. | 4d. | ||
---|---|---|---|---|
A | 1 | 6 | ||
B | 1 | 5 | 4/(6+5+4+5) | |
C | 1 | 5 | ||
D | 1 | 4 | 2/(1+1) | 4/(6+5+5+5) |
E | 4 | 5 | 2/(4+4) | 5/(5+5+4+4+5) |
F | 2 | 3 | ||
G | 1 | 2 | ||
H | 1 | 2 | ||
I | 2 | 3 | ||
J | 2 | 2 | ||
K | 3 | 4 | ||
L | 4 | 5 | ||
M | 2 | 2 | ||
N | 1 | 2 | ||
O | 1 | 1 | ||
P | 1 | 2 | ||
Q | 1 | 2 | ||
R | 1 | 1 | ||
S | 1 | 2 | ||
T | 2 | 2 |
v) Aggregierte 4. Distanz für T: 2+2+1+2=7 (die nachsten Nachbarn sind O, Q, R, S)
i) k=2. E LOF2(E)=12NN(E)⋅∑o∈2NN(E)lrd2(o)lrd2(E)=12⋅(lrd2(D)+lrd2(F)lrd2(E))=22+232⋅28=3.333
lrd2(E)=|2NN(E)|∑o∈2NN(E)reach-dist2(E,o)=2rdist2(E,D)+rdist2(E,F)=24+4=28
rdist2(E,D)=max{2⋅distt(e),dist(E,D)}=rdist2(E,F)=max{1,4}=4
lrd2(D)=2rdist2(D,B)+rdist2(D,C)=21+1=22
i) k=4. E LOF_4(E) = \frac{1}{\left| 4NN(E) \right|}\sum_{o \in 4NN(E)} \frac{lrd_4(o)}{lrd_4(E)} = \frac{\frac{1}{5} \left(\frac{4}{20}+\frac{4}{20}+\frac{4}{21}+\frac{4}{10}+\frac{4}{10}}}{\frac{5}{23} = 1,279
Übung 10
Aufgabe 1
- Ki: Klassifikator
- Ci: Anzahl richtig
Ki→ Ci | A | B | C | |
---|---|---|---|---|
A | 4 | 0 | 1 | 5 |
B | 2 | 2 | 1 | 5 |
C | 1 | 1 | 3 | 5 |
7 | 3 | 5 |
- Precission: |TP||TP|+|FP|
- Recall: ??
|TP| | |FP| | |FN| | |
---|---|---|---|
A | 4 | 3 | 1 |
B | 2 | 1 | 3 |
C | 3 |
- |TP|: Diagonale
- Zeile?
- Spalte?
x | Precision(K, x) | Recall(K, x) | F_1(K, x) |
---|---|---|---|
A | 47 | 45 | 23 |
B | 23 | 25 | 12 |
C | 35 | 35 | 35 |
- Mittlere Precision: 13(47+23+35)=0.6
Aufgabe 2
Leave-one-out
Jeweils eins raus nehmen und es durch die dann vorherschende Mehrheit ersetzen
AA A B B B ⇒ Das A wird ein B, da B nun die Mehrheit- A
AA B B B ⇒ Das A wird ein B, da B nun die Mehrheit - A A
AB B B ⇒ Das A wird ein B, da B nun die Mehrheit - A A A
BB B ⇒ Das B wird ein A, da A nun die Mehrheit - A A A B
BB ⇒ Das B wird ein A, da A nun die Mehrheit - A A A B B
B⇒ Das B wird ein A, da A nun die Mehrheit
⇒ Fehlerrate 100%
optimaler Klassifikator
????
A A A B B B + ?
Fehlerrate 50%
Bootstrap
Zufälliges ziehen mit zurücklegen
1,2,…,n
P(x)=1n\RightleftarrowP(¬x)=1−1n
Pn(¬x)=(1−1n)n=e−1=0.368
Fehlerrate = 0.632 * Fehlerrate_Test + 0.368 * Fehlerrate_Training
10 Fach Kreuzvalidierung
Beispiel 3 fach Kreuzvalidierung
Datensatz 3x unterschiedlich aufteilen:
Training | Training | Test |
Training | Test | Training |
Test | Training | Training |
Aufgabe 3
A priori- und bedingte Wahrscheinlichktein:
- P(Ski)=12
- P(¬Ski)=12
Klasse Wetter = W
- P(W=Sonne∣Ski)=14
- P(W=Schnee∣Ski)=24
- P(W=Regen∣Ski)=14
- P(W=Sonne∣¬Ski)=14
- P(W=Schnee∣¬Ski)=14
- P(W=Regen∣¬Ski)=24
Klasse Schnee = S
- P(S<50∣Ski)=14
- P(S>=50∣Ski)=34
- P(S<50∣¬Ski)=34
- P(S>=50∣¬Ski)=14
a)
- W=Sonne,Schnee>50
- P(Ski∣W=Sonne∧S>=50)=P(W=Sonne,S>=50∣Ski)⋅P(Ski)P(W=Sonne,S>=50)=P(Sonne∣Ski)⋅P(>=50∣Ski)⋅P(Ski)P(Sonne,>=50)=\nicefrac14⋅\nicefrac34\nicefrac12P(Sonne,>=50=\nicefrac332P(…)
- P(¬Ski∣Sonne,>=50)=\nicefrac14⋅\nicefrac14⋅\nicefrac12P(Sonne,>=50=\nicefrac132P(…)
- ⇒ P(Ski|…)=34
a priori | Wetter | Schnee | |||||
---|---|---|---|---|---|---|---|
Sonne | Schnee | Regen | >= 50 | < 50 | |||
Ski | 1/2 | 1/4 | 2/4 | 2/4 | 1/4 | 3/4 | 1/4 |
\neg Ski | 1/2 | 1/4 | 1/4 | 2/4 | 1/4 | 3/4 |
Aufgabe 4
- Klassifikation (Die Klassen (Spam/Ham) stehen schon vorher fest)
- Clustering
- Clustering (Assoziationsregel / Wahrenkorbanalyse)
- Clustering
- Klassifikation
- Clustering
- Klassifikation
Übung 11
Aufgabe 1
Wird immer als Kreis Klassifiziert
Aufgabe 2
XOR-Problem
Aufgabe 3
Entropie(T)=−∑ki=1pi⋅log(pi)
Informationsgewinn(T,A)=Entropie−∑mi=1|Ti||T|Entropie(Ti)
- Erster Teil von Informationsgewinn: vorher
- Zweiter Teil von Informationsgewinn: mittlere Entropie nachher
Mittlere Entropie: Gewicht nach Anteil
an der Datenbank!
a)
Hier wird der 2-er Logarithmus verwendet. Es kann aber jeder verwendet werden, solange es überall verwendet wird.
1 Split
T ist noch die ganze DB
Entropie(T)=−(pniedrig⋅log2(pniedrig)+phoch⋅log2(phoch)=−12⋅(−1)−12⋅(−1)=1
Zeit seit Fahrprüfung
Ti | Anzahl | Pniedrig | Phoch | Entropie(T) |
---|---|---|---|---|
1-2 | 3 | 1/3 | 2/3 | −13log13−23log23=0.918 |
2-7 | 3 | 2/3 | 1/3 | −23log23−13log13=0.918 |
>7 | 2 | 1/2 | 1/2 | −12log12−12log12=1 |
Informationsgewinn(T_i, Zeit) = 1 - (3/8 * 0.918 + 3/8 * 0.918 + 2/8 * 1) = 0.06
Geschlecht
Ti | Anzahl | Pniedrig | Phoch | Entropie(T) |
---|---|---|---|---|
m | 5 | 2/5 | 3/5 | −25log25−35log35=0.971 |
w | 3 | 2/3 | 1/3 | −23log23−13log13=0.918 |
Informationsgewinn(T_i, Geschlecht) = 1 - (5/8 * 0.971 + 3/8 * 0.918) = 0.05
Wohnort
Ti | Anzahl | Pniedrig | Phoch | Entropie(T) |
---|---|---|---|---|
Stadt | 3 | 3/3 | 0/3 | −1log1−0log0=−1⋅0−0=0 |
Land | 5 | 1/5 | 4/5 | −15log15−45log45=0.722 |
Informationsgewinn(T_i, Geschlecht) = 1 - (3/8 * 0 + 5/8 * 0.722) = 0.55 ⇒ Gewinner
2. Split
T={2,3,4,5,6}
Entropie(T)=−(pniedrig⋅log2(pniedrig)+phoch⋅log2(phoch)=−15⋅log15−45⋅(45)=0.722
Zeit seit Fahrprüfung
Ti | Anzahl | Pniedrig | Phoch | Entropie(T) |
---|---|---|---|---|
1-2 | 2 | 0 | 1 | 0 |
2-7 | 1 | 0 | 1 | 0 |
>7 | 2 | 1/2 | 1/2 | 1 |
Informationsgewinn(T_i, Zeit) = 0.722 - (0 + 0 + 2/3 * 1) = 0.322 ⇒ Gewinner
Geschlecht
Ti | Anzahl | Pniedrig | Phoch | Entropie(T) |
---|---|---|---|---|
m | 3 | 0 | 1 | 0 |
w | 2 | 1/2 | 1/2 | 1 |
Informationsgewinn(T_i, Geschlecht) = 0.722 - (0 + 2/5 * 1) = 0.322
Beispiel Gini
T_i | Anzahl | P_niedrig | P_hoch | gini(T_i) |
---|---|---|---|---|
m | 5 | 2/5 | 3/5 | 1−((2/5)2+(3/5)2)=0.48 |
w | 3 | 2/3 | 1/3 | 1−((2/3)2+(1/3)2)=0.44 |
gini geschlecht(T) = 5/8 * 0.48 + 3/8 * 0.44
b)
…
Foo
- Datenbank
- Fokusieren
- Beschaffen
- Selektieren
- Kleinere Datenmenge
- Vorverarbeitung
- Mergen
- Vervollständigen
- (Hier: Eine) Relation
- Transformation (Statistisches Zeug)
- Diskret ↔ Stetig
- Ableiten
- transformieren
- Transformierte Relationen
- Data Mining
- Generierung von Modellen
- Generierung von Mustern
- Muster
- Qualitätsprüfung
- Vorhersagekraft
- Wissen
Arten
- Supervised
- Outline Detection
- Klassifikation
- Regression
- Unsupervised
- Outlier Detection
- Clustering
- Assoziationsregeln