Knowledge Discovery in Databases I

• 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

v) Aggregierte 4. Distanz für T: 2+2+1+2=7 (die nachsten Nachbarn sind O, Q, R, S)

i) k=2. E $$LOF_2(E) = \frac{1}{2NN(E)} \cdot \sum_{o \in 2NN(E)} \frac{lrd_2(o)}{lrd_2(E)} = \frac{1}{2} \cdot \left( \frac{lrd_2(D)+lrd_2(F)}{lrd_2(E)}\right) = \frac{\frac{2}{2} + \frac{2}{3}}{2 \cdot \frac{2}{8}} = 3.333$$

$$lrd_2(E) = \frac{\left| 2NN(E) \right| }{\sum_{o \in 2NN(E)} \text{reach-dist}_2(E,o)} = \frac{2}{rdist_2(E,D) + rdist_2(E, F)} = \frac{2}{4+4} = \frac{2}{8}$$

$$rdist_2(E, D) = max\{2\cdot distt(e), dist(E,D)\} = rdist_2(E, F) = max\{1,4\}= 4$$

$$lrd_2(D) = \frac{2}{rdist_2(D,B) + rdist_2(D, C)} = \frac{2}{1+1} = \frac{2}{2}$$

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$$

• $K_i$: Klassifikator
• $C_i$: Anzahl richtig

• Precission: $\frac{|TP|}{|TP| + |FP|}$
• Recall: ??

• $|TP|$: Diagonale
• Zeile?
• Spalte?

• Mittlere Precision: $\frac{1}{3}\left(\frac{4}{7} + \frac{2}{3} + \frac{3}{5}\right) = 0.6$

Jeweils eins raus nehmen und es durch die dann vorherschende Mehrheit ersetzen

• A A A B B B ⇒ Das A wird ein B, da B nun die Mehrheit
• A A A B B B ⇒ Das A wird ein B, da B nun die Mehrheit
• A A A B B B ⇒ Das A wird ein B, da B nun die Mehrheit
• A A A B B B ⇒ 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
• A A A B B B ⇒ Das B wird ein A, da A nun die Mehrheit

⇒ Fehlerrate 100%

????

A A A B B B + ?

Fehlerrate 50%

Zufälliges ziehen mit zurücklegen

$1, 2, \ldots, n$

$P(x) = \frac{1}{n} \Rightleftarrow P(\neg x) = 1 - \frac{1}{n}$

$P_n(\neg x) = \left(1 - \frac{1}{n}\right)^n = e^{-1} = 0.368$

Fehlerrate = 0.632 * Fehlerrate_Test + 0.368 * Fehlerrate_Training

A priori- und bedingte Wahrscheinlichktein:

• $P(Ski) = \frac{1}{2}$
• $P(\neg Ski) = \frac{1}{2}$

Klasse Wetter = W

• $P(W = Sonne \mid Ski) = \frac{1}{4}$
• $P(W = Schnee \mid Ski) = \frac{2}{4}$
• $P(W = Regen \mid Ski) = \frac{1}{4}$
• $P(W = Sonne \mid \neg Ski) = \frac{1}{4}$
• $P(W = Schnee \mid \neg Ski) = \frac{1}{4}$
• $P(W = Regen \mid \neg Ski) = \frac{2}{4}$

Klasse Schnee = S

• $P(S < 50 \mid Ski) = \frac{1}{4}$
• $P(S >= 50 \mid Ski) = \frac{3}{4}$
• $P(S < 50 \mid \neg Ski) = \frac{3}{4}$
• $P(S >= 50 \mid \neg Ski) = \frac{1}{4}$

• $W = \text{Sonne}, \text{Schnee} > 50$
• $P(\text{Ski} \mid W=\text{Sonne} \wedge S >= 50) = \frac{P(W=\text{Sonne}, S>=50 \mid \text{Ski}) \cdot P(Ski)}{P(W=Sonne, S>= 50)} = \frac{P(Sonne \mid Ski) \cdot P(>=50 \mid Ski) \cdot P(Ski)}{P(Sonne, >=50)} = \frac{\nicefrac{1}{4} \cdot \nicefrac{3}{4} \nicefrac{1}{2}}{P(Sonne, >= 50} = \frac{\nicefrac{3}{32}}{P(\ldots)}$
• $P(\neg Ski \mid Sonne, >= 50) = \frac{\nicefrac{1}{4} \cdot \nicefrac{1}{4} \cdot \nicefrac{1}{2}}{P(Sonne, >=50} = \frac{\nicefrac{1}{32}}{P(\ldots)}$
• ⇒ $P(Ski | \ldots) = \frac{3}{4}$

1. Klassifikation (Die Klassen (Spam/Ham) stehen schon vorher fest)
2. Clustering
3. Clustering (Assoziationsregel / Wahrenkorbanalyse)
4. Clustering
5. Klassifikation
6. Clustering
7. Klassifikation

Wird immer als Kreis Klassifiziert

XOR-Problem

$Entropie(T) = - \sum^k_{i=1}p_i \cdot log(p_i)$

$Informationsgewinn(T, A) = Entropie - \sum^m_{i=1} \frac{|T_i|}{|T|} Entropie(T_i)$

• Erster Teil von Informationsgewinn: vorher
• Zweiter Teil von Informationsgewinn: mittlere Entropie nachher

Mittlere Entropie: Gewicht nach Anteil an der Datenbank!

T ist noch die ganze DB

$\text{Entropie}(T) = -(p_{\text{niedrig}} \cdot log_2(p_\text{niedrig}) + p_\text{hoch} \cdot log_2(p_\text{hoch}) = -\frac{1}{2}\cdot(-1)-\frac{1}{2}\cdot(-1) = 1$

Zeit seit Fahrprüfung

Informationsgewinn(T_i, Zeit) = 1 - (3/8 * 0.918 + 3/8 * 0.918 + 2/8 * 1) = 0.06

Geschlecht

Informationsgewinn(T_i, Geschlecht) = 1 - (5/8 * 0.971 + 3/8 * 0.918) = 0.05

Wohnort

Informationsgewinn(T_i, Geschlecht) = 1 - (3/8 * 0 + 5/8 * 0.722) = 0.55 ⇒ Gewinner

T={2,3,4,5,6}

$\text{Entropie}(T) = -(p_{\text{niedrig}} \cdot log_2(p_\text{niedrig}) + p_\text{hoch} \cdot log_2(p_\text{hoch}) = -\frac{1}{5}\cdot\log\frac{1}{5}-\frac{4}{5}\cdot(\frac{4}{5}) = 0.722$

Zeit seit Fahrprüfung

Informationsgewinn(T_i, Zeit) = 0.722 - (0 + 0 + 2/3 * 1) = 0.322 ⇒ Gewinner

Geschlecht

Informationsgewinn(T_i, Geschlecht) = 0.722 - (0 + 2/5 * 1) = 0.322

gini geschlecht(T) = 5/8 * 0.48 + 3/8 * 0.44

…

• 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
• Evaluation
  • Qualitätsprüfung
  • Vorhersagekraft
• Wissen

Preprocessing

• Supervised
  • Outline Detection
  • Klassifikation
  • Regression
• Unsupervised
  • Outlier Detection
  • Clustering
  • Assoziationsregeln

• Clustering
• Outlier Detection
• Klassifikation
• Regression
• Assoziationsregeln