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


===== Übung 10 =====
==== Aufgabe 1 ====
  * $K_i$: Klassifikator
  * $C_i$: Anzahl richtig

^ $K_i \rightarrow$ \\ $C_i$ ^ A ^ B ^ C ^ ^
^ A | 4 | 0 | 1 ^ 5 ^
^ B | 2 | 2 | 1 ^ 5 ^
^ C | 1 | 1 | 3 ^ 5 ^
^   ^ 7 ^ 3 ^ 5 ^   ^


  * Precission: $\frac{|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 | $\frac{4}{7}$ | $\frac{4}{5}$ | $\frac{2}{3}$ |
| B | $\frac{2}{3}$ | $\frac{2}{5}$ | $\frac{1}{2}$ |
| C | $\frac{3}{5}$ | $\frac{3}{5}$ | $\frac{3}{5}$ |

  * Mittlere Precision: $\frac{1}{3}\left(\frac{4}{7} + \frac{2}{3} + \frac{3}{5}\right) = 0.6$
==== Aufgabe 2 ====
=== Leave-one-out ===
Jeweils eins raus nehmen und es durch die dann vorherschende Mehrheit ersetzen

  * <del>A</del> A A B B B => Das A wird ein B, da B nun die Mehrheit
  * A <del>A</del> A B B B => Das A wird ein B, da B nun die Mehrheit
  * A A <del>A</del> B B B => Das A wird ein B, da B nun die Mehrheit
  * A A A <del>B</del> B B => Das B wird ein A, da A nun die Mehrheit
  * A A A B <del>B</del> B => Das B wird ein A, da A nun die Mehrheit
  * A A A B B <del>B</del> => 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, \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

=== 10 Fach Kreuzvalidierung ===

<WRAP center round box 60%>
**Beispiel 3 fach Kreuzvalidierung**

Datensatz 3x unterschiedlich aufteilen:

| Training | Training | Test |

| Training | Test | Training |

| Test | Training | Training |
</WRAP>

=== Aufgabe 3 ===
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}$


=== a) ===
  * $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}$

^  ^ 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) = - \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!

=== a) ===
<WRAP center round important 60%>
Hier wird der 2-er Logarithmus verwendet. Es kann aber jeder verwendet werden, solange es überall verwendet wird.
</WRAP>

== 1 Split ==
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**
^ $T_i$ ^ Anzahl ^ $P_\text{niedrig}$ ^ $P_\text{hoch}$ ^ Entropie(T) ^
|  1-2  |  3  |  1/3  |  2/3  |  $-\frac{1}{3}\log\frac{1}{3}-\frac{2}{3}\log{2}{3} = 0.918$ |
|  2-7  |  3  |  2/3  |  1/3  |  $-\frac{2}{3}\log\frac{2}{3}-\frac{1}{3}\log{1}{3} = 0.918$ |
|  >7   |  2  |  1/2  |  1/2  |  $-\frac{1}{2}\log\frac{1}{2}-\frac{1}{2}\log{1}{2} = 1$ |

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

**Geschlecht**
^ $T_i$ ^ Anzahl ^ $P_\text{niedrig}$ ^ $P_\text{hoch}$ ^ Entropie(T) ^
|  m  |  5  |  2/5  |  3/5  |  $-\frac{2}{5}\log\frac{2}{5}-\frac{3}{5}\log{3}{5} = 0.971$ |
|  w  |  3  |  2/3  |  1/3  |  $-\frac{2}{3}\log\frac{2}{3}-\frac{1}{3}\log{1}{3} = 0.918$ |

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

**Wohnort**
^ $T_i$ ^ Anzahl ^ $P_\text{niedrig}$ ^ $P_\text{hoch}$ ^ Entropie(T) ^
|  Stadt |  3  |  3/3  |  0/3  |  $-1\log1-0\log0 = -1\cdot0-0=0$ |
|   Land |  5  |  1/5  |  4/5  |  $-\frac{1}{5}\log\frac{1}{5}-\frac{4}{5}\log{4}{5} = 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}

$\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**
^ $T_i$ ^ Anzahl ^ $P_\text{niedrig}$ ^ $P_\text{hoch}$ ^ 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**
^ $T_i$ ^ Anzahl ^ $P_\text{niedrig}$ ^ $P_\text{hoch}$ ^ 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**
  * [[Evaluation]]
    * Qualitätsprüfung
    * Vorhersagekraft
  * **Wissen**


[[Preprocessing]]
===== Arten =====
  * Supervised
    * Outline Detection
    * Klassifikation
    * Regression
  * Unsupervised
    * Outlier Detection
    * Clustering
    * Assoziationsregeln

  * [[Clustering]]
  * [[Outlier Detection]]
  * [[Klassifikation]]
  * [[Regression]]
  * [[Assoziationsregeln]]