---
tags: Zusammenfassung, Data Mining
title: Data Mining - Zusammenfassung
---
# Data Mining - Zusammenfassung
[TOC]

/*## Klausur
** Dienstag, 23.07.2019 10:30 - 11:30
** Turing HS + Zuse HS popchick
** keine Hilfsmittelfefeffefefemcmcmfefefefefcmcm
*/

## I. Grundlagen
### I.1 Grundbegriffe
- Knowledge Discovery in Databases (KDD)
*Prozess der (semi-) autoamtischen Extraktion von Wissen aus Datenbanken, das*
- statistisch gültig
- unbekannt
- potentiell nützlich
- verständlich
*ist.*
Abgegrenzt zu Statistik, Maschinelles Lernen, Datenbanksysteme
- Data Mining
*Zwei Alternativen:*
- Synonym für KDD:
Beinhaltet alle Aspekte der Wissensgewinnung
- Teil des KDD:
Mustergewinnung
- Big Data
- für klassische Verarbeitung zu große Datenmengen (Peta- bis Zettabyte)
- high **V**olume, high **V**elocity, high **V**ariety
- Data Science
*also data-driven science: interdisciplinary field of scientific methods, processes, algorithms and systems to extract knowledge from data, similar to data mining*

### I.2 KDD-Prozess
**interaktiv** und **iterativ** (nicht automatisch, nach Beurteilung Schrittwiederholung)
1. Business Understanding, Data Understanding
- Definition der Ziele des KDD
- Verständnis der gegebenen Anwendung
- Beschaffung, Selektion, Klärung des Verwaltens der Daten
2. Preprocessing
- Integration, Konsistenzprüfung, Vervollständigung
- Diskretisierung numerischer Attribute
- Erzeugen abgeleiteter Attribute
4. Modeling
- "Zentraler Schritt"
- Clustering $\rightarrow$ Klassifikation $\rightarrow$ Subgruppenentdeckung
6. Evaluation
*Präsentation und Bewertung der Muster*
- schlechte Bewertung:
neue Miningiteration mit anderen Paramatern/Verfahren/Daten
- gute Bewertung:
Integration des Wissens in Wissenbasis, Nutzung des WIssens für zukünftige KDD-Prozesse
8. Deployment
- Planung des Einsatzes der KDD-Anwendung, des Monitorings, der Wartung
- Endberichterstellung
- Review

### I.4 Grundwissen
#### 1 Merkmale
- Eigenschaft einer **Instanz** oder eines **Datensatzes** nennt man
Merkmal = Attribut = Variable = Feature
- Typen:
- Numerisch
- totale Ordnung (<)
- arithmetische Operationen
z.B: Alter = 27, Einkommen = 5000
- Ordinal
- mit (totaler) Ordnung (<)
- keine arithmetische Operationen
z.B: Größe = {klein, mittel, groß}
- Kategorisch/nominal
- keine Ordnung
- keine arithmetischen Operationen
z.B: Farbe = {rot, gelb, grün, blau}

#### 2 Voraussetzungen
- (Arithmetischer) Mittelwert, Median, Mode
- Varianz, Standardabweichung, Stichprobenvarianz
- Erwartungswert
- Relative Häufigkeit / Wahrscheinlichkeit
- Bedingte Wahrscheinlichkeit: $P(A|B) = \frac{P(A \cap B)}{P(B)}$
- Satz von Bayes: $P(A_j|B) = \frac{P(B|A_j) \cdot P(A_j)}{P(B)}$
- Binomialverteilung, Normalverteilung
- Korrelationskoeffizient

### I.5 Datenbanksysteme und Datawarehouse
#### 1 Datenbanksysteme
- Datenbanksystem (DBS)
*Softwaresystem zur dauerhaften Speicherung und zum effizienten Suchen in großen Datenmengen*
- Datenbank (DB)
*Sammlung von Daten zu einer gegebenen Anwendung*
- Datenbankmanagementsystem (DBMS)
*Computerprogramm zum Management beliebiger Anwendungen in einem spezifizierten Format*
$\rightarrow$ bestimmt möglichst effiziente Bearbeitung
- Anfragesprachen

#### 2 Data Warehouse
- dauerhafte & integrierte Sammlung von Daten (meist in DB)
- separat zum operativen Geschäft
- Daten unterschiedlicher Quellen
- zur Analyse/Entscheidungsunterstützung

#### 3 Neue Ansätze für Big Data
- NoSQL
- In Memory Datenbanken
- Andere Techniken

#### 4 Speicherungsformen für Analaysedaten
- Hauptspeicher (wenn möglich hier vollständige Bearbeitung)
- Lokale Festplatte
- Festplatte im Netzwerk, Festplatten verteilt auf alle Rechner

### I.6 OLAP
#### 1 OLTP/OLAP
| *O*n*l*ine *T*ransaction *P*rocessing | *O*n*l*ine *A*nalytical *P*rocessing |
| -------- | -------- |
| operative DB | Data Warehouse |
| hohe Zahl, **kurzer**, atomarer, isolierter, wiederkehrender Transaktionen|dient der Entscheidungsunterstützung, in Phasen **Data Understanding / Preparation** einsetzbar |
|Transaktionen benötigen detaillierte, aktuelle Daten| schneller, interaktiver Zugriff|
|häufige Aktualisierung|Dimensionen filterbar|
|Tagegeschäft, braucht schnelle Bearbeitung |verschiedene Aggregationsstufen |

#### 2 OLAP Multidimensionalität
Sichtweise auf Daten mit flexiblen, interaktiven Aggregationsstufen / Verfeinerungsfunktion entlang ausgewählter Dimension(en)

Dimensionen werden durch eine Menge von Attributen charakterisiert, z.B: Dimension Region charakterisiert durch Filiale, Stadt und Bundesland

### I.7 Vorverarbeitung/Preprocessing

- Reduktion der Datenmenge
- Bereinigung (Entfernen fehlerhafter Werte, Duplikate)
- Diskretisierung, Normalisierung, Feature Selection und Construction

#### Annahmen:
##### 1 Single Table Assumption
- **Propositionalisierung**: relationale Datenbank $\rightarrow$ eine einzige Tabelle
- Typischer input für Data Mining
-
##### 2 Datenkonsistenz
Einheitliche Einheiten, Syntaktische Fehler korrigiert

##### 3 Missing Values
unvermeidbar. Umgang:
- Ersetzen durch Median/Mittelwert
- Vorhersage
- missing value als eigenen Wert benutzen
- Instanz entfernen

#### Methoden:
#### 1 Instance Selection
- Entfernen/korrigieren fehlerhafter, doppelter, out of Definitionsbereich
- Sampling
- Random: Auswahl einer Teilmenge
- Stratified: Erhöhter Anteil seltener Klassen

#### 2 Outlier Detection
große Abweichung vom Mittelwert Fehler oder wichtige Information?
Detection durch Clustering $\rightarrow$ Outlier schlecht zuordenbar

#### 3 Diskretisierung
Numerische Attribute in nominale umwandeln, dabei Einteilung in Intervalle, manuell oder
automatisch:
- Equal-Width-Intervalle
- Equal-Frequency-Intervalle
- Supervised Discretizaion (Ähnliches in gleichem Intervall)
z.B. Gehälter einordnen

#### 4 Normalisierung
_Wertebereiche verschiedener Features (verschiedener Mengen $V$) auf den gleichen Wertebereich abbilden, oft auf [0;1]_
z.B:

$$
v_i' = \frac{ v_i - min(V_j) }{max(V_j) - min(V_j)}, v_i \in V_j
$$

#### 5 Feature Selection
Filtern von monoton steigenden Features (Zeit, ID), Features mit sehr wenigen non-default/sehr vielen unterschiedlichen Werten
Suche einer idealen Teilmenge für Bewertungsfunktion

#### 6 Feature Construction
- Gegebenes ändern, z.B. PLZ aus Ortsname, oder kombinieren.
- Mit bekannten Daten verknüpfen

## II. Clustering
### II.1 Grundlagen
_Zusammenfassen ähnlicher Objekte zu Clustern, die untereinander möglichst unähnlich sind._

Es sind keine Vorabinformationen zu Clustern vorhanden $\rightarrow$ Abgrenzung Klassifikation

#### 1 Ähnlichkeit/Distanz
Distanzfunktion bestimmt Qualität des Clusterings (muss aus relevanten Features berechnet werden), ist indirekt proportional zur Ähnlichkeit, und muss folgende Eigenschaften haben:
1. $d(o_1,o_1)=0$
2. $d(o_1,o_2)=d(o_2,o_1)$
gilt zusätzlich die Dreiecksungleichung, ist $d$ metrisch.
$d$ heißt *Metrik*, wenn $d$ metrisch und $o_i \in \mathbb{R}^n, \forall i$ (euklidischer Raum)

Typische Metriken für numerische Attribute:
- Manhattan-Distanz $\sum_{i=1}^d|x_i-y_i|$
- Euklidische Distanz $\sqrt{\sum_{i=1}^d(x_i-y_i)^2}$

Distanzfunktion für kategorische Attribute:
- Hamming-Abstand, zählt Anzahl unterschiedlicher Attribute
- Jaccard-Metrik, Anteil gemeinsamer Werte verschiedener Mengen

Beliebte Ähnlichkeitsfunktion ist der Korrelationskoeffizient, mit Wertebereich $[-1;1]$

### II.2 Partitionierende Clusterverfahren
_Partitionierung in k Cluster mit minimalen Kosten, lokal optimiert_
Cluster werden repräsentiert: Repräsentanten können Mittelwert, einzelnes Element oder Wahrscheinlichkeitsverteilung sein.

#### 1 Algorithmen
##### 1.1 k-means
- Metrik benötigt
- Clustering $\mathbb{C}$ aus k Clustern, sodass jeder Punkt p einem $C_i$ zugewisen wird.
- Cluster werden durch Centroid $\mu_C$, dem Mittelwert aller Punkte, repräsentiert
- Kompaktheit eines Clusters ist Summe der Quadratabweichungen $TD^2$ vom Mittelpunkt, Kompaktheit des Clusterings Summe der Kompaktheiten der Cluster


|Vorteile|Nachteile|
| -------- | -------- |
| $\mathcal{O(n)}$ pro Iteration, wenige Iterationen (i.A. ~5-10)| anfällig gegen Rauschen und Ausreißer |
|Einfache Implementierung + Verständlichkeit|Cluster müssen konvexe Form haben|
||stark von Ausganspunkten abhängig
||k ist of schwer zu bestimmen

##### 1.2 k-medoids (PAM)
- dist muss keine Metrik sein
- Repräsentation durch Element des Clusters: Medoid $m_C$
- Kompaktheit des Clusters ist Summer der Distanzen $TD$, Kompaktheit des Clusterings Summe der Kompaktheiten der Cluster
- Initialisierung $\mathcal{O(n^3)}$, Iteration $\mathcal{O(k\cdot(n-k)^2)}$

Greedy-Algorithmus: in jedem Schritt wird das Paar (Medoid, Nicht-Medoid) vertauscht, das Kosten am stärksten reduziert

##### 1.3 k-modes
- kategorische Daten
- Cluster-Repräsentanten: Modes

##### 1.4 Erwartungsmaximierung
- Punkte in euklidischem Vektorraum gehören mit unterschiedlicher Wahrscheinlichkeit zu mehreren Clustern
- Repräsentation durch Normalverteilung: $\mu_C$, Kovarianzmatrix
- Gütebewertung eines Clusterings durch
$$
E(M)=\sum_{x\in D} \log(P(x))
$$
(je größer, desto wahrscheinlicher sind die gegeben Daten D mit berechneter Verteilung)
- E(M) soll maximiert werden
- pro Iteration: $\mathcal{O} (n \cdot |M|)$, wobei |M| Anzahl der Cluster; i.A. viele Iterationen benötigt
- konvergiert gegen ein Minimum, Ergebnis und Laufzeit stark von Initialwerten und k abhängig

##### 1.5 Dichte-basiertes Clustering (DBSCAN)
- Menge von Objekten im Cluster muss räumlich zusammenhängend sein
- Grundbegriffe:
- grundlegende Eigenschaft: Ein Cluster sind alle Punkte, die von einem Kernobjekt dichte-erreichbar sind
- Noise$_{CL}$ ist die Menge aller nicht zu einem Cluster gehörenden Punkte (im Beispiel R)
- Aufbau: durchlaufen jeden Punktes, wenn noch nicht klassifiziert und Kernobjekt fasse alle dichte-erreichbaren Punkte zu Cluster zusammen, wenn kein Kernobjekt $\rightarrow$ Noise$_{CL}$
- von mehreren Clustern erreichbare Randpunkte bleiben dem ersten Cluster zugeschrieben
- k-Distanz (im Beispiel 3-Distanz)
- Benutzer gibt k vor, erhält Diagramm, wählt Grenzobjekt $\varepsilon=$k-Distanz(o)
- Hierarchische Cluster, unterschiedliche Dichten, schlecht getrenntes Rauschen führen zu Problemen:

#### 2 Variablen der Algorithmen
##### 2.1 Wahl der initialen Cluster
- m Stichproben zum Clustern verwenden, deren Cluster(-repräsentanten) als Initialwerte für Grundgesamtheit nehmen
- beste der m Varianten wählen

##### 2.2 Wahl des Parameters k
- bestes Clustering aus n-2 verschiedenen wählen: k={2,...,n-1}
- Gütebewertung muss unabhängig von k sein (TD² [k-means], TD [k-medoids] sinken monoton mit k; E [EM] steigt) $\rightarrow$ ungeeignet

#### 3 Gütemaß
##### 3.1 Davies-Boudlin-Index
##### 3.2 Silhouetten Koeffizient
- von k unabhängig, für k-means und -medoid
- Wertebereich [-1;1]:
- $s(o)<0$: o liegt näher an anderem Repräsentanten (schlecht)
- $s(o)\approx 0$: Lage zwischen zwei Clustern (indifferent)
- $s(o)\approx 1$: Lage an eigenem Repräsentanten (gut)
- Gesamtmaß $s_C$ = Durchschnitt aller Objekte:
- $s_C>0,7$ starke Struktur
- $s_C>0,5$ brauchbare Struktur

### II.3 Hierachisches Clustering
_Hierachie von Clustern, so dass immer die Cluster mit minimaler Distanz verschmolzen werden (darstellbar mit Dendrogramm)_

#### Dendrogramm

- Blätter sind Datenpunkte, Knoten sind Cluster
- Distanz ist der Abstand zweier Cluster zueinander
- Distanzfunktion wählbar
- z.B. $d(X,Y) = \underbrace{min}_{Single -Link}/ \underbrace{max}_{Complete-Link}(d(x_i,y_j))| x_i\in X, y_j \in Y$
- Average-Link: $\frac{1}{|X||Y|} \sum_{x\in X, y\in Y} dist(x,y)$

| Vorteile | Nachteile
|-|-
|Man erhält eine Clustering-Hierachie anstatt eines flachen Clusterings | Anfälligkeit gegenüber Rauschen (Single-Link)
|Einzelnes Clustering einfach erhaltbar, z.B. durch "Durchziehen" eines Dendrogramm mit einer Linie |Hohe Komplexität $\mathcal{O}(n^2)$
|Erfordert keine Kenntnis der Anzahl k der Cluster | "Entscheidungen" (Verschmelzen von Clustern) können nicht rückgängig gemacht werden ($\rightarrow$ ggf. nicht optimales Clustering)

#### OPTICS
_Dichte-basiertes hierarchisches Clusteringverfahren_
- ähnlich zu DBSCAN, Parameter $\varepsilon$, minPts.
- jeder Punkt erhält zusätzlich zur Kerndistanz auch Erreichbarkeitsdistanz, die angibt, wie dicht andere Punkte um den Betrachteten verteilt sind
$\rightarrow$ verschiedene Erreichbarkeitsdistanzen stellen verschieden Hierarchielevel dar

### II.4 Hochdimensionale Daten
_sehr viele Attribute für Datenpunkte_

Anwendungen (u.A.):
- Textdokumente
- Microarray Data (Genexpression, Genetik)

#### 1 Probleme (Curse of dimensionality):

- Schwierig zu interpretieren und visualisieren,
- Attribute können korreliert sein
- Hinzufügen von Dimensionen streckt Daten auseinander:
- Cluster können in höherdimensionalen Räumen überlappen

###### Überlappung von Clustern im höherdimensionalen Raum
Es gibt in a und c jeweils zwei Cluster, b ist Rauschen
Punkte der Cluster können sich im 2-D bereits überlappen:

#### 2 Vermeidung durch:
##### Subspace Clustering
Finde gute Cluster in beliebigen Teilräumen (Anzahl der Teilräume steigt mit Attributen **exponentiell**)
z.B. per

###### CLIQUE Algorithmus
_Bottom-up Subspace Clustering_

Teile Dimensionen in Intervalle (grid), suche d-dimensionale (d iterativ steigend, zunächst 1) **dichte** (Mindestanzahl an Objekten) Schnitte dieser Intervalle, verbinde nebeneinanderliegende dichte Schnitte zu Clustern.
$\rightarrow$ reduziert Zahl der zu untersuchenden Teilbäume massiv

## III. Assoziationsregeln
### III.1 Grundlagen
_Zusammenhänge zwischen Items($\equiv$Attribute) einer Datenbank mit Transaktionen_
- Transaktionen sind Zeilen der Tabelle
- $k$-Itemsets sind $k$ Spalten

Assoziationsregel:

**Rumpf $\Rightarrow$Kopf [support, confidence]**
"Gilt _Rumpf_, gilt mit _confidence_ auch Kopf, die Transaktion hat Anteil _support_ an allen Transaktionen"
- support einer Regel entspricht support des Itemsets aus allen Elementen aus Rumpf und Kopf
- $supp_D(X)=\frac{|\{T\in D|X\subseteq T\}|}{|D|}$
(X ist ein Itemset, Häufigkeit wird in allen Transaktion T gezählt wird)
- Frequency = $supp_D(X) \cdot |D|$ (absolute Häufigkeit)
- Konfidenz beschreibt den Anteil der Regeln mit dem gleichen Kopf an Regeln mit dem gleichen Rumpf:
$$
conf_D(X\Rightarrow Y)= \frac {supp_D(X\cap Y)}{supp_D(X)}
$$
- z. B.: $conf_D$(Windeln, Chips $\Rightarrow$Bier) = 80% bedeutet:
80% aller Kunden, die Windeln und Chips gekauft haben, haben auch Bier gekauft

### III.2 Algorithmen
Gesucht sind alle Assoziationsregeln mit $supp_D \geq minSupp \land conf_D \geq minConf$

###### Problem:
$2^n$ Teilmengen errechnen ineffizient

###### Lösung:
##### Monotonie:
_ist Itemset {A,B} häufig, dann auch Itemset {A}_

benutze Monotonie rückwärts (Pruning):
- beginne mit 1-Itemsets. Betrachte nur (k+1)-Itemsets, bei denen alle k-Itemsets häufig sind
- berechne Support für alle k-Itemsets durch Zählen in Datenbank

#### 2.1 Apriori-Algorithmus

Beginne mit allen 1-Itemsets in $C_1$. Fasse alle 1-Itemsets, deren $supp\geq minSupp$, zu $L_1$ zusammen. Dann wiederhole bis gewünschtes $k$:

1. Join
kombiniere alle (k-1)-Itemsets aus $L_{k-1}$, die in den ersten (k-2) Items übereinstimmen zu Kandidaten-Itemsets: 
3. Pruning
Entferne alle Kandidaten-Itemsets, die (k-1)-Itemsets enthalten, die nicht in $L_{k-1}$ enthalten sind

Pseudocode:

#### 2.2 FP-Growth
_Ausnutzen einer günstigen Datenstruktur (**FrequentPattern**-Trees), um Zugriffe auf DB zu reduzieren_

1. Initialisierung
- 1-Itemsets mit $supp \geq minSupp$ absteigend nach Häufigkeit sortieren
- Transaktionen filtern und Items in der Transaktion sortieren (entsprechend der 1-Itemsets)
- Transaktionen von Wurzel aus einfügen:
- ist Item als Child vorhanden: increase count, sonst lege neuen Knoten an
- verknüpfe alle Knoten eines Items mit Auxiliary Links
3. Itemsetgenerierung
Bottom-Up:
für ein gesuchtes Item:
- generiere Conditional Tree, in welchen alle Blatt-Item-Pfade (Präfix-Pfade) des Initial-Trees eingefügt werden

|Vorteile|Nachteile|
|-|-|
|Nur 2 Durchläufe auf DB benötigt|FP-Trees u.U. zu groß für RAM|
|komprimiert den Datensatz|ungünstige Transaktionen führen zu großen (teuren) FP-Trees
|keine explizite Kandidatengenerierung||
|oft schneller als Apriori

### III.3 Auswahl von Assoziationsregeln
#### Interessantheitsmaß
_Berechenbare Bewertung von Assoziationsregeln_

Support und Konfidenz $\neq$ Interessantheit
Andersweitige Kombinationen der Wahrscheinlichkeiten führen zu verschiedenen Interessantheitsmaßen (große Auswahl vorhanden)

Je nach Anwendung Wichtung nach _Conciseness_(Kürze), _Generality_, _Reliability_, _Diversity_(möglichst unterschiedliche Ergebnisse), _Novelty_, _Surprisingness_, _Applicability_

#### Constraints
_Bedingungen an Assoziationsregeln_
z.B:
- maximal 3 Items
- nur Produkt A ohne Produkt B
- Gesamtpreis $> 123$

##### Monotonie:
_Jede Teilmenge eines Constraint erfüllenden Itemsets erfüllt das Constraint ebenso_
Bsp:
- $sum(S.Preis) \leq a$: anti-monoton
- $sum(S.Preis) = a$: _teilweise_ anti-monoton
- $sum(S.Preis) \geq a$: _nicht_ anti-monoton

Support ist anti-monoton

### III.4 Hierarchische Assoziationsregeln
In vielen Anwendungen: Item-Taxonomieen (is-a-Hierarchien) $\rightarrow$ Bäume mit Vorfahren (Allgemeiner) und Nachfahren (Spezieller)

- Items sind eine Menge von Literalen
- für Mengenbeziehung Vorfahre/Nachfahre muss in beschriebener Menge mindestens ein Item durch seinen Vorfahren/Nachfahren ersetzbar sein
- Typischerweise sind in Transaktionen nur Blätter des Taxonomiebaumes enthalten
- Transaktion unterstützt ein Item (eine Menge), wenn das Item oder ein Vorfahre in der Transaktion enthalten ist (wenn jedes Item unterstützt wird)
- im Kopf einer Transaktion dürfen keine Vorfahren des Rumpfes stehen (z.B: Hose$\Rightarrow$Kleidung ist illegal)

#### 1 Rechenregeln
- $supp_D(X) = \frac{|\{T\in D|T \supseteq X\}|}{|D|}$
Anteil an die Menge X unterstützenden Transaktionen in D
- $supp_D (X\Rightarrow Y ) = supp_D(X\cup Y)$ (Support einer Regel)
- $conf_D (X\Rightarrow Y )= \frac {|\{T\in D|T\supseteq (X\cup Y) \}|}{|\{T\in D|T \supseteq X\}|}$ ($T \supseteq X$: T unterstützt X )
Anteil an auch die Menge Y unterstützenden Transaktionen in allen die Menge X unterstützenden Transaktionen


#### 2 Interessantheit hierarchischer Assoziationsregeln
- Erwarteter Support:
Y' ist Vorfahre von Y,
$supp_D(Y'\Rightarrow Y) = a$
(Anteil der Transaktionen mit Y an allen Transaktionen mit Y')
$supp_D(Y'\Rightarrow X) = b$

$$
\Rightarrow expsupp_D(Y\Rightarrow X) = a \cdot b
$$

- Beispiel:
$supp_D(Kleidung\Rightarrow Schuhe)=8\%$
$supp_D(Kleidung\Rightarrow Jacke) = 25\%$
dann gilt für den erwarteten Support:
$$
expsupp_D(Jacke\Rightarrow Schuhe) = 2\%
$$

Eine Assosziationsregel heißt R-interessant, wenn sie keine direkten Vorfahren hat, oder $supp_D(Y\Rightarrow X)> R \cdot expsupp_D(Y\Rightarrow X)$ gilt.

#### 3 Variabler Support
_unterschiedliche minSup-Werte für unterschiedliche Taxonomieebenen_

### III.5 Quantitative Assoziationsregeln

Assoziationsregeln aus numerischen Attributen
> [name=LordCMonkey] lel, Ausführlichkeit? lloll.

#### Partitionierung numerischer Attribute
möp

## IV. Klassifikation
### IV.1 Einleitung
_Unbekannte Objekte mit Wissen aus einem Trainingssatz von klassifizierten Objekten klassifizieren._

#### 1 Training
- Train and test:
Lernmenge und Testmenge jewils 50% der Objekte
- k-fold cross validation
- Teilen von O in k Teile, (k-1)-faches Train and Test mit einer festen Testmenge
- k Iterationen, sodass jede Teilmenge einmal Testmenge war
- Klassifikationsfehler werden kombiniert (z.B. Mittelwert)

#### 2 Gütemaße
- in Testmenge:
$$
\text{Genauigkeit} =\frac{\text{Treffer}}{\text{Gesamtanzahl}}
$$

$$
\Rightarrow \text{Fehler} =1- \text{Genauigkeit}
$$

- in Trainingsmenge
$$
\text{Beob. Fehler} =\frac{\text{Fehlklassifikationen}}{\text{Gesamtanzahl}}
$$

- Precision: $\frac{tp}{tp+fp}$ (Spalte $\rightarrow$ wie häufig stimmt eine Vorhersage)
- Recall: $\frac{tp}{tp+fn}$ (Zeile $\rightarrow$ wie oft wird die Klasse gefunden)

#### 3 Overfitting
_Optimierung des Modells für Trainingsdaten, sodass dieses nicht mehr verallgemeinert._
$\rightarrow$ macht Modell zunehmend unbrauchbar
v.A. bei hoher Modellkomplexität

#### 4 Überwacht vs. Unüberwacht
|Überwacht (_supervised_)|Unüberwacht (_unsupervised_)|(semi-supervised)
|-|-|-
|gewünschte Klassen bekannt | Zielklassen unbekannt | wie supervised, klassifizieren viele ungelabelte Daten anhand einer **kleinen** Trainingsmenge gelabelter
|$\rightarrow$ lernt aus pos./neg. Beispielen | $\rightarrow$ erarbeitet Unterscheidung

### IV.2 Bayes-Klassifikator
_Ordnet mithilfe unabhängiger Hypothesen einem Objekt eine Klasse zu, wenn die bedingten Wahrscheinlichkeiten der Hypothesen zu jeder Klasse bekannt sind_

###### beste Klassifikationsgüte:
Optimaler Bayes-Klassifikator (meistens fehlen jedoch die erforderlichen Wahrscheinlichkeiten)

#### Naiver Bayes-Klassifikator
Annahme: Attribute $o_i$ sind bedingt unabhängig

$$
\arg \max_{c_j \in C} \left( P(c_j) \prod_{i=1}^d P(o_i | c_j) \right)
$$

mit $P(c_j)$ als gezählter Anteil der Klasse $c_j$ an allen Klassen $C$ und $P(o|c_j)$ als gezählte bedingte Wahrscheinlichkeit des Auftretens von $o_j$ in Klasse $c_j$
- schnelle Klassifikation
- für viele Anwendungen ausreichend genau
- leichte Einarbeitung neuer Trainingsobjekte (Inkrementalität)

#### Laplace Korrektur
_Korrektur von Wahrscheinlichkeiten mit Wert Null, die durch zu kleinen Datensatz auftauchen_ und Bayesklassifikator unwirksam machen (Produkt wird Null)

Ergänzen eines Falls in jeder Möglichkeit:
Beispiel:
$P(1)=0, P(2)=\frac{9}{100}, P(3)=\frac{91}{100}$
$\underbrace{\Rightarrow}_\text{Korrektur}P(1)=\frac{1}{103}, P(2)=\frac{10}{103},P(3)=\frac{92}{103}$

### IV.3 Nächste-Nachbarn-Klassifikation

_Klassifikation anhand der k nächsten Objekte_
verwende k mit geringstem Klassifikationsfehler auf Trainingsmenge oder j-facher Kreuzvalidierung

#### Entscheidungsregel
- Standard: Mehrheitsklasse in Entscheidungsmenge
- Alternativ: Gewichtung nach Distanz/Klassenverteilung/Kostenfunktion (anwendungsbezogen)

|Vorteil|Nachteil
|-|-
|Erfordert nur Trainingsdaten als Eingabe | Ineffizient während der Klassifikation
| Oft hohe Klassifikationsgenauigkeit | liefert kein explizites Wissen über die Klassen
|Inkrementalität (ohne jegliche Anpaasung) |
|numerische Vorhersage möglich

### IV.4 Entscheidungsbäume (Divide&Conquer)
_leicht nachvollziehbares, rekursives Klassifkationsverfahren_
$\rightarrow$ Baum mit Klassen als Blätter, Attribute als innere Knoten und Kanten als Test zum Vaterknoten
Auswahl der inneren Knoten (Entscheidungsattribute) nach:

#### 1 Splitstrategie
Splits: _innere Knoten mit Attribut und Bedingung_
- kategorische Attribute
Bedingungen der Form $o = a, o \not\in A$
- numerische Attribute
Bedingungen der Form $o \leq a$

Split soll Trainingsobjekte möglichst effektiv aufteilen
$\rightarrow$ Maß für Effektivität:

##### 1.1 Informationsgewinn
_Bewertung eines Splits anhand der Entropie_
Entropie für Menge T von Trainingsobjekten und k Klassen:

$$
e(T)=\sum_{i=1}^k p_i\cdot \log_2 p_i
$$

(Wert zwischen $\log_2 k$ [max] bei Gleichverteilung und 0 [min] für sichere Klassenzugehörigkeit)

Anwendung auf Splitstrategie:
Splitattribut A erzeugt Partitionierung $T_1, T_2, .. T_m$
$\rightarrow$ Informationsgewinn von A auf T:

$$
i_T(A) = e(T)-\sum_{i=1}^m \frac {|T_i|}{|T|} \cdot e(T_i)
$$

wähle für jeden Split Attribut mit höchstem Informationsgewinn

##### 1.2 Gini-Index
für Menge T von Trainingsobjekten:

$$
gini(T)=1-\sum_{i=1}^k p_i^2
$$

- kleiner Wert $\rightarrow$ geringe Unreinheit (Teilmengeninstanzen gut voneinander getrennt)
- großer Wert $\rightarrow$ hohe Unreinheit

Splitattribut A erzeugt Partitionierung $T_1, T_2, .. T_m$
$\rightarrow$ gini-Index von A auf T:

$$
gini_T(A)=\sum_{i=1}^m\frac{|T_i|}{|T} \cdot gini(T_i)
$$

Gini-Index gewichtet große Klassen stärker, sonst recht ähnlich zu Informationsgewinn

#### 2 Overfitting
Entscheidungsbäume können Traingsdatensatz auswendig lernen
Ansätze zur Vermeidung:
- im Vorhinein:
günstige Wahl der Parameter Trainingsdatensatzgröße, minSupp, minConf
- nachträglich:

##### Pruning
- per **Fehlerreduktions-Pruning** (für große Ausgangsmenge):
konstruierter Entscheidungsbaum wird mit einer **bis dato unbekannten** Testmenge ($\neq$ Validierungsmenge, bessere Generalisierung) beschnitten:
- jeweils Entfernen des Teilbaums, dessen Fehlen Klassifikationsfehler am stärksten reduziert
- per:

###### Kostenkomplexitätspruning
Reduktion auf kleinsten, Kostenkomplexität minimierenden Teilbaum E($\alpha$)

Kostenkomplexität:

$$
KK_T(E,\alpha)=F_T(E)+\alpha \cdot |E|
$$

mit Komplexitätsparameter $\alpha \geq 0$, Trainingsmenge T, Entscheidungsbaum E, $|E| =$ Anz. Blätter von E, und Klassifikationsfehler $F_T(E)$

Prunen lohnt sich beim Knoten e, wenn $\alpha \geq \alpha_{crit}$ mit

$$
\alpha_{crit}: KK_T(E,\alpha_{crit})=KK_T(\{e\},\alpha_{crit})
$$

wobei $\{e\}$ Baum mit einzigem Knoten e ist.

Schwächster Link: Knoten mit $min_E(\alpha_{crit})$ (am meisten abschneidbar)

Vorgehen:
- iterative Entfernung des weak link (bei mehreren alle im gleichen Schritt entfernen)
- Auswahl des besten (k-fold Cross validation) $E(\alpha_i)$ aus Folge $E(\alpha_1)>E(\alpha_2)>..>E(\alpha_m)$ mit $\alpha_1<\alpha_2<..\alpha_m$

#### 3 Interpretation als Regelmenge
jeder Entscheidungsbaum kann als **eindeutige** (eine Regel pro Blatt) Regelmenge interpretiert werden:


diese kann man auch direkt lernen:

### IV.5 Regellernverfahren (Separate&Conquer)
_Klassifikation von Objekten durch Regeln, die vorher aus einer Beispielmenge gelernt wurden_

Regeln sind Konjunktionen von Attribut-Wert-Paaren, z.B. $\underbrace{A=\text{true}}_\text{A.-W.-Paar} \land B\geq 80 \Rightarrow \underbrace{o_i = K_1}_\text{Klassifizierung}$

Aufstellen der Regeln:
- finde beste Regel für verbleibende Beispiele:
- finde beste Regel mit einer Bedingung (nach wählbarer Kostenfunktion, z.B. Entropie)
- füge Bedingungen hinzu, bis keine Verbesserung mehr eintritt
- notiere Regel und entferne Beispiele, die Regelbedingung erfüllen
- wiederhole, bis kein Beispiel mehr vorhanden ist

_auch hier:_
#### Overfitting
muss schon beim Erzeugen vermieden werden, da nachträgliches Entfernen einer Regel alle nachfolgenden beeinflussen muss:

##### 1 IREP
_Incremental Reduced Error Pruning_
Aufteilen der Trainingsdaten in $\frac{2}{3}$ Growing- (A) und $\frac{1}{3}$ Pruningmenge (B). Diese dienen während des sonst unveränderten Aufstellens jeder Regel dem
1. Growing - Hinzufügen von Bedingungen, bis auf A keine Negativbeispiele mehr abgedeckt
2. Pruning - Entfernen von Bedingungen, bis auf B Gütemaß optimiert

##### 2 CBA
_Classification by Association_
> [name=LordCyberMonkey] important? rather not so much.

### IV.6 Support Vector Machines
_Finden einer Hyperebene H, die positive und negative Instanzen trennt, dabei größtmöglichen Abstand zum nächsten jeweiligen Beispiel hat, und durch Stützvektoren beschrieben wird._

Anwendbar bei Zwei-Klassen-Problemen

#### 1 Grundlagen
- Ausgangsmenge: $n$ Beispiele $(x_i,y_i), i\in \mathbb{N} | 1\leq i \leq n$ mit
- $x_i \in \mathbb{R}^n$, Attributvektor
- $y_i=\begin{cases}1 &\mbox{falls Beispiel positiv}\\ -1 &\mbox{falls Beispiel negativ} \end{cases}$ bezüglich Klassenzugehörigkeit

- Hyperebene $H:=f(x)=w\cdot x + b = 0$,
mit Ebenennormalenvektor w


$\text{margin}=\frac{w}{||w||} \cdot (x_+ - x_-)\underbrace{=}_{w \cdot x_\pm = \pm1-b} \frac{2}{||w||}$

$\rightarrow$ Klassifikation durch $signum(f(x_k))$ für zu klassifizierende Beispiele $x_k$, Ergebnis bestimmt Zugehörigkeit

#### 2 Vorgehen
Finden von $H$ durch minimieren von $\frac{1}{2}||w||^2$ unter Nebenbedingungen $y_i(w\cdot x_i + b) -1 = 0$ (eindeutig in $\mathcal{O}(n^3)$ lösbar)

$\rightarrow$ zugehörige Lagrange-Funktion:

$$
L(\alpha) = \sum_{i=2}^n \alpha_i - \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n y_iy_j\alpha_i \alpha_j x_i\cdot x_j
$$

wobei $\forall i: 0 \leq \alpha_i, \sum \alpha_iy_i=0$
- $\alpha_i$ ist die Relevanz des Trainingsbeispiels $x_i$ für $H$:
- $\alpha_i > 0$ heißt für Trainingsbeispiel $x_i$, dass es ein **Stützvektor** von $H$ ist
- $\alpha_i = 0$ heißt für Trainingsbeispiel $x_i$, dass es im passenden Halbraum liegt (für Ebenendefinition irrelevant),

- $w$ ist Linearkombination von Stützvektoren

###### effizienzsteigernde Ansätze
- _Sequential Minimal Optimization_
optimiere statt allen $\alpha_i$ nur die zwei vielversprechendsten (heuristisch ermittelt) gleichzeitig, wechsle dieses Paar, bis Gesamtergebnis konvergiert
- streiche Trainingsbeispiele, die nicht Support Vektoren werden können (Shrinking)

#### 3 Zusammenfassung bei linear trennbaren Daten:
- eindeutige Festlegung von H durch Maximierung des Margins $\Leftrightarrow$ Minimierung von $||w||$
- Ergebnis $w$ ist Linearkombination von $n$ Stützvektoren von H
- Klassifizierung in $\mathcal{O}(n)$ (nur noch Skalarprodukte)

#### 4 nicht linear trennbare Daten:
##### 4.1 weich trennende Hyperebene
Einführen von Parametern $\xi$ (lässt Fehler beim Trennen zu)
und $C$ (Gewichtung der Fehler, große C $\rightarrow$ starke Wichtung)

##### 4.2 Kernel-Methoden
SVM wird auf per Transformation $\varPhi$ höherdimensionierten Trainingsbeispielen gelernt, die damit linear trennbar geworden sind. Das Ergebnis wird rücktransformiert

###### Problem
viele Dimensionen $\rightarrow$ aufwendige Berechnung

###### Lösung
Reduktion von expliziten Datenpunktberechnungen auf **Skalarprodukt der Punkte** in höherdimensionalem Raum per Kernelfunktion $K(x,y)=\varPhi(x)\cdot \varPhi(y)$

#### 5 Diskussion
|Vorteile|Nachteile|
|-|-
|bei gelerntem Modell schnelle Klassifikation |nur für numerische Featurewerte
|beliebt (lel) | nur für Zwei-Klassen-Probleme
||hochdimensionale Hyperebene nicht eingänglich

### IV.7 Kombination von Klassifikationsverfahren
_Verbesserung der Güte durch Kombination von Klassifikatoren gegenüber dem Ergebnis des einfachen Klassifikators_

#### 1 Bagging (_"Parrallelschaltung"_)
- Ein einzelnes Verfahren wird mit $m$ unterschiedlichen Samples (Ziehen mit Zurücklegen) des Traingsdatensatzes trainiert
- zur Klassifikation Mehrheitsentscheidung dieser $m$ Klassifikationsmodelle

|Vorteile|Nachteile
|-|-
|verbessert Güte _instabiler_ Klassifikatoren | verschlechtert Güte _stabiler_ Klassifikatoren leicht
|vermeidet Overfitting | nicht leicht interpretierbar
||um Faktor $m$ verlängerte Laufzeit

###### Beispiel
- Random Forests

#### 2 Boosting (_"Serienschaltung"_)
- Kette von Klassifikatoren, die jeweils auf Output des vorangegangenen lernen, dabei Fehlklassifizierungen stärker gewichten
- Klassifikation durch gewichtete Ergebnisse aller Klassifikatoren, Gewichtung nach individueller Güte

###### Beispiel
- AdaBoost

## V. Regressionsanalyse
### V.1 Lineare Regression
Ausgangsdaten werden durch Gerade $h_\Theta (x) = \Theta_0 + \Theta_1 x_1 + .. + \Theta_n x_n$ angenähert, wobei alle $\Theta_k$ anhand einer Fehlerfunktion optimiert werden

#### Gradient Descent
minimiere Fehlerfunktion $J(\Theta_k)$ von Startpunkt aus, von dem entlang der stärksten Minimierung (maximalem Gradienten) bis zu einem Minimum gefolgt wird

$J$ ist dabei von Faktoren $\Theta_k$ abhängig, in jedem Schritt werden alle geupdatet:

$$
\Theta_{i,n+1}=\Theta_{i,n}- \alpha \frac{\partial J}{\partial \Theta_i}
$$

- Lernrate $\alpha$:
- zu klein: Gradient Descent langsam
- zu groß:
Möglichkeit der Nicht-Konvergenz

###### Problem
Gradient Descent terminiert bei lokalem Minimum

#### Gradient Descent und Lineare Regression

## Neuronale Netze (Einführung)
Neuronen, Aktivierungsfunktionen und so...