-
Notifications
You must be signed in to change notification settings - Fork 0
/
cheat_sheet_datamining.tex
615 lines (540 loc) · 27.8 KB
/
cheat_sheet_datamining.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
\documentclass[a4paper]{article}
\usepackage{pdflscape}
\usepackage{multicol}
\usepackage{blindtext}
\usepackage{color}
\usepackage{enumitem}
\usepackage[left=10mm, right=10mm, top=10mm, bottom=10mm]{geometry}
\usepackage{titlesec}
\usepackage[utf8]{inputenc}
\usepackage{fourier}
\usepackage{array}
\usepackage{makecell}
\usepackage{amsmath}
\renewcommand\theadalign{bc}
\renewcommand\theadfont{\bfseries}
\renewcommand\theadgape{\Gape[4pt]}
\renewcommand\cellgape{\Gape[4pt]}
\titlespacing\section{0pt}{5pt plus 4pt minus 2pt}{0pt plus 2pt minus 2pt}
\titlespacing\subsection{0pt}{5pt plus 4pt minus 2pt}{0pt plus 2pt minus 2pt}
\titlespacing\subsubsection{0pt}{5pt plus 4pt minus 2pt}{0pt plus 2pt minus 2pt}
\setlength{\columnseprule}{0.5pt}
\def\columnseprulecolor{\color{black}}
\pagenumbering{gobble}
\title{DataMining Cheat Sheet}
\author{Niklas Ullmann}
\date{Summer 2022}
\begin{document}
\begin{landscape}
\thispagestyle{empty}
\begin{multicols}{3}
\section{Grundlagen}
\begin{itemize}[noitemsep,nolistsep]
\item Qualitative Attribute:
\begin{itemize}
\item Variieren nach Beschaffenheit
\end{itemize}
\item Quantitative Attribute:
\begin{itemize}
\item Variieren nach Wert/Zahlen
\end{itemize}
\end{itemize}
\begin{itemize}[noitemsep,nolistsep]
\item Diskrete Attribute:
\begin{itemize}
\item abgestufte Werte
\end{itemize}
\item Stetige Attribute:
\begin{itemize}
\item können im Intervall jeden reellen Wert annehmen
\end{itemize}
\end{itemize}
\subsection{Skalenniveaus}
\begin{itemize}[noitemsep,nolistsep]
\item Nominal
\begin{itemize}
\item nur Gleichheit oder Andersartigkeit feststellbar (keine Bewertung)
\item stets qualitativ
\end{itemize}
\item Ordinal
\begin{itemize}
\item natürliche oder festzulegende Rangfolge
\end{itemize}
\item Kardinal/Metrisch
\begin{itemize}
\item numerischer Art
\item Ausprägung und Unterschied sind messbar
\item verhältnisskaliert (Absoluter Nullpunkt vorhanden; (Doppelt so viel.))
\item intervallskaliert (Kein Nullpunkt, nur Differenzen)
\end{itemize}
\end{itemize}
\subsection{Sym. vs asym. Attribute}
\begin{itemize}[noitemsep,nolistsep]
\item Das symmetrische binäre Attribut ist ein Attribut, bei dem jeder Wert gleichwertig ist (w/m)
\item Asymmetrisch ist ein Attribut, bei dem die beiden Ausprägungen nicht gleichwertig sind (Testergebnisse oder Vergleich von Umfragen)
\end{itemize}
\subsection{Rauschen Artefakte, Ausreißer}
\begin{itemize}[noitemsep,nolistsep]
\item Rauschen (Random Verzerrung der Messung durch Einflussfaktoren)
\item Artefakte (Unvollständige Messwerte)
\item Ausreißer (Messwerte, die nicht im Normalbereich liegen)
\end{itemize}
\subsection{Datenvorverarbeitung}
\begin{itemize}[noitemsep,nolistsep]
\item Aggregation (Zusammenfassung mehrerer Messwerte, Details gehen verloren)
\item Sampling (Random(Behält gleiche Verteilung), Stratified (Einordnung in ähnliche Subgruppen nach Attribut und dann random daraus ziehen))
\item Diskretisierung / Binarisierung (Gleiche Breite, gleiche Anzahl, Cluster)
\item Transformation (Skalierung etc., PCA?, Kernel?)
\item Dimensionsreduktion (Reduzierung und trotzdem Inhalte behalten)
\item Feature Subset Selection (Konzentration auf wichtige Features)
\item Feature Creation (W \& H: Algo zusammenhang nicht verstehen, Größe(H*W) geht besser)
\end{itemize}
\subsection{Ähnlichkeits- und Distanzmaße}
\subsubsection{Ähnlichkeit}
Eigenschaften:
\begin{itemize}[noitemsep,nolistsep]
\item $s(x,y) 0 <= s <= 1$
\item $s(x,y) = 1$, wenn $x = y$
\item Symmetry: $s(x,y) = s(y,x)$
\end{itemize}
\textbf{Simple Matching Coefficient (SMC):}
\begin{itemize}[noitemsep,nolistsep]
\item $ SMC = \dfrac{f_{00}+f_{11}}{f_{01}+ f_{10}+ f_{00}+ f_{11}} $
\item Binäre Daten
\item gut für \textbf{sym. Attribute}, da Vorhandensein und Abwesenheit gleich gewertet wird
\end{itemize}
\textbf{Jaccard Coefficient:}
\begin{itemize}[noitemsep,nolistsep]
\item $ J = \dfrac{f_{11}}{f_{01}+ f_{10}+ f_{11}} $
\item Binäre Daten
\item gut für \textbf{asym. Attribute}, da Vorhandensein gewertet wird
\item $ 0 <= EJ <= 1$ (1 sehr ähnlich)
\end{itemize}
\textbf{Extended Jaccard Coefficient (Tanimoto):}
\begin{itemize}[noitemsep,nolistsep]
\item $EJ: \dfrac{\langle x, y \rangle}{||x||^2 + ||y||^2 - \langle x,y \rangle}$
\item Jaccard für alle Daten
\item $ -1 <= EJ <= 1$ (1 sehr ähnlich)
\end{itemize}
\textbf{Cosine Similarity:}
\begin{itemize}[noitemsep,nolistsep]
\item $cos(x,y) = \dfrac{\langle x, y \rangle}{||x|| * ||y||}$
\item $ -1 <= cos(x,y) <= 1$
\item 1 = sehr ähnlich, 0 = Vekrtor im 90° Winkel, -1 = Vektor im 180° Winkel
\item Umrechnung von zahl zu Winkel im Taschenrechner mit $cos^{-1}$
\item auch für asym. Attribute da 0-0 Paare rausfallen
\end{itemize}
\textbf{Correlation:}
\begin{itemize}[noitemsep,nolistsep]
\item $corr(x,y)$ über Taschenrechner
\item zeigt linearen Zusammenhang ($-1 <= corr <= 1$)
\item Taschenrechner:
\begin{itemize}[noitemsep,nolistsep]
\item Menü 6 -> 2 Statistik -> $< = a+bx$
\item Dateneingabe und $AC$ drücken
\item $OPTN$ -> Regression
\item $ r = correlation $
\end{itemize}
\end{itemize}
\subsubsection{Distanz (Minkowski)}
Eigenschaften:
\begin{itemize}[noitemsep,nolistsep]
\item Positivity (d(x,y) >= 0, d(x,y) = 0, wenn x = y)
\item Symmetry (d(x,y)= d(y,x))
\item Triangle Inequality (d(x,z) <= d(x,y) + d(y,z))
\end{itemize}
$$ d(x,y) = \sqrt[r]{\sum^{n}_{k=1} | x_k - y_k |^r} $$
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
Name & r & Anwendung \\ \hline
Hamming & 1 & Bin.Vekt. \\ \hline
CityBlock & 1 & nur gerade \\ \hline
Euclid & 2 & schräg (gleiche Skalierung) \\ \hline
Supremum & $\infty$ & nur größte Dist. \\ \hline
\end{tabular}
\end{center}
\subsubsection{Weiteres}
\textbf{Verhalten für Multiplikation und Addition:}
\begin{center}
\begin{tabular}{|l|l|l|l|}
\hline
Property & Cosine & Correlation & Minkowski \\ \hline
Invariant to multiplication & Yes & Yes & No \\ \hline
Invariant to addition & No & Yes & No \\ \hline
\end{tabular}
\end{center}
\textbf{Mutual Information:}
\begin{itemize}[noitemsep,nolistsep]
\item Ähnlich wie Correlation, aber für nicht linearen Zusammenhang
\item $0 =$ kein Zusammenhang, $1 =$ starker Zusammenhang
\item \textcolor{red}{HIER fehlts}
\end{itemize}
\textbf{Umrechnung Ähnlichkeit $<->$ Distanz:}\\
Bspw:
\begin{itemize}[noitemsep,nolistsep]
\item $s = \dfrac{1}{d}-1$
\item $s = ln(x)*-1$
\item $d = 1 - s$
\item $d = \sqrt[2]{1-s}$
\end{itemize}
\section{Klassifikation}
\begin{itemize}[noitemsep,nolistsep]
\item Zuordnung einer abhängigen Variable (y) anhand von unanhängigen Variablen
\item Model hat beim Training (Induction) gelernt zuzuordnen
\item Model wendet das gelernte bei der Klassifikation an (Deduction)
\end{itemize}
\subsection{Beispiele von Klassifikationsverfahren}
\begin{itemize}[noitemsep,nolistsep]
\item Elementare Verfahren (Decision Trees, KNN, Naive Bays, SVM, NN)
\item Ensemble Verfahren (Random Forests, bagging, Boosting, \dots)
\end{itemize}
\subsection{Entscheidungsbäume}
\begin{itemize}[noitemsep,nolistsep]
\item Datensatz durchläuft von der Wurzel bis zum Blatt die Knoten und wird anhand der Entscheidungen am Knoten klassifiziert
\item Hunts Algo entscheidet, wie Splits gesetzt werden (gibt noch mehr)
\end{itemize}
\subsubsection{Hunts Algo}
\begin{itemize}[noitemsep,nolistsep]
\item Sei $D_t$ die Menge der Trainingsdatensätze, die Knoten t erreichen
\item Wenn $D_t$ nur Datensätze enthält, die zur selben Klasse ytgehören, dann ist t ein Blatt des Baumes und wird mit ytgekennzeichnet.
\item Falls $D_t$ Datensätze enthält, die zu mehr als einer Klasse gehören, verwende eine Attribut-Testbedingung, um die Daten in kleinere Untermengen aufzuteilen
\end{itemize}
\subsubsection{Split bei Attributen}
\begin{itemize}[noitemsep,nolistsep]
\item Binärer Split
\item Mehrfach Split
\end{itemize}
Möglichkeiten der Diskretisierung
\begin{itemize}[noitemsep,nolistsep]
\item Einteilung in gleichbelegte Bereiche (Percentile)
\item Einteilung in gleiche Bereiche (Clustering)
\item Binäre Entscheidung: (A < v) und (A >= v)
\end{itemize}
\textbf{Greedy Ansatz}
Algorithmus der schrittweise den besten nächsten Schritt mit dem höchsten gewinn wählt.
\subsection{Maß für Knotenunreinheit}
\begin{itemize}[noitemsep,nolistsep]
\item $p_i(t)$ Häufigkeit von klasse i beim Knoten t\\ $c$ Gesamtzahl der Klassen
\item \textbf{Gini Index}
\begin{itemize}[noitemsep,nolistsep]
\item $ GI = 1 - \sum_{i=0}^{c-1} p_i(t)^2$
\item Maximum: $1-\dfrac{1}{c}$
\item Minimum: 0 (Best Case)
\item Ablesbare Werte ohne Berechnungen:
\begin{itemize}[noitemsep,nolistsep]
\item \textcolor{red}{Nur bei 2 Klassen:}
\item Klassen mit 0 und 0 = 1
\item Klassen mit 0 und X = 0
\item Klassen mit X und X = 0.5
\end{itemize}
\end{itemize}
\item \textbf{Entropy}
\begin{itemize}[noitemsep,nolistsep]
\item $ E = - \sum_{i=0}^{c-1} p_i(t) * log_2 p_i(t)$
\item Maximum: $log_2 c$
\item Minimum: 0 (Best Case)
\end{itemize}
\item \textbf{Klassifikationsfehler}
\begin{itemize}[noitemsep,nolistsep]
\item $ CE = 1 - max[p_i(t)]$
\item Maximum: Wenn alle Datensätze auf die Klassen gleich verteilt sind
\item Minimum: 0 (Best Case, wenn alle datensätze zu einer Klasse gehören)
\end{itemize}
\item \textbf{Siehe Bild für Eigenschaften}
\end{itemize}
\subsection{Nachfolgende Berechnungen}
\begin{itemize}[noitemsep,nolistsep]
\item Können mit allen 3 Maßen berechnet werden.
\item Split
\begin{itemize}[noitemsep,nolistsep]
\item $ split = \sum_{i = 1}^{k} \dfrac{n_i}{n} * Knotenunreinheit$
\item $n_i$ = Anzahl der Daten im Kindknoten i
\item $n$ = Anzahl der Daten im Elternknoten
\end{itemize}
\item Gain
\begin{itemize}[noitemsep,nolistsep]
\item $ gain = P - M$
\item $P$ = Knotenunreinheit des Elternknoten
\item $M$ = Split der Kindknoten
\item Gain maximieren für einen guten Split bzw. M minimieren!!!
\item \textcolor{red}{InformationGain: } Gain berechnet mit der Entropie!
\end{itemize}
\item \textcolor{red}{Problem: Splits mit vielen Kindsknoten mit wenigen aber einen Datensätze werden bevorzugt!}
\item SplitInfo
\begin{itemize}[noitemsep,nolistsep]
\item $ splitInfo = - \sum_{i = 1}^{k} \dfrac{n_i}{n} log_2 \dfrac{n_i}{n}$
\item $splitInfo$ = Entropie der Partitionierung
\end{itemize}
\item GainRatio
\begin{itemize}[noitemsep,nolistsep]
\item $ gainRatio = \dfrac{gain_{split}}{splitInfo}$
\item Korrigierter Gain um Entropie -> Bestrafung hoher Anzahl kleiner Partitionen
\item Maximum (Best Case)
\end{itemize}
\end{itemize}
\subsection{Bewertung Bäume, Overfitting etc.}
\begin{itemize}[noitemsep,nolistsep]
\item Trainingsfehler: Klassifikationsfehler von Daten aus Training
\item Testfehler: Klassifikationsfehler von Daten aus Test
\item Generalisierungsfehler: Erwarteter K-Fehler bei random Daten
\end{itemize}
\subsubsection{Under-/Overfitting}
\begin{itemize}[noitemsep,nolistsep]
\item Undefitting: Modell ist zu simpel (Training- /Testfehler groß)
\item Overfitting: Modell ist zu komplex oder zu wenig Daten (Testfehler groß)
\item Typischer Ellenbogen - Im "Knick" ist das Optimum
\end{itemize}
\subsubsection{Fehlerabschätzung}
\begin{itemize}[noitemsep,nolistsep]
\item Ockhams Razor/Sparsamkeitsprinzip
\item pess. Fehlerabschätzung: $err_{gen}(T) = err(T) + \Omega * \dfrac{k}{N_{train}}$
\item $err(T)$ = Gesamtfehlermenge Training
\item $k$ = Anzahl Blätter im Baum
\item $N_{train}$ Anzahl Trainingsdatensätze
\end{itemize}
\subsubsection{Pruning}
\begin{itemize}[noitemsep,nolistsep]
\item Pre-Pruning
\begin{itemize}[noitemsep,nolistsep]
\item Stoppe im Prozess, wenn bspw.
\item Datensätze zur selben Klasse gehören
\item Alle Datensätze bei allen Attributen die selben Werte haben
\item Anzahl der Datensätze Schwellenwert unterschreitet
\item Klassenverteilung nach $\chi^2$ unabhängig ist
\item Gain nicht hoch genug ist
\end{itemize}
\item Post-Pruning
\begin{itemize}[noitemsep,nolistsep]
\item Nach Fertigstellung des Baumes
\item bottum-up Ansatz
\end{itemize}
\end{itemize}
\subsection{Modell Evaluation}
\subsubsection{Validierung}
\begin{itemize}[noitemsep,nolistsep]
\item Holdout (Split zwischen Training- und Testdaten)
\item Kreuzvalidierung (Mehrfach Holdout mit disjunkten Mengen und Durchschnitt über )
\end{itemize}
\subsubsection{Konfusionmatrix}
Siehe Bild im Repo
\begin{itemize}[noitemsep,nolistsep]
\item Precision (\% der richtig klassifizierten innerhalb der positiven Vorhersagen)
\item Recall/True Positive Rate (\% der richtig klassifizierten von den ursprünglich positiven)
\item False Positive Rate (\% der flasch positiv klassifizierten innerhalb der ursprünglich negativen)
\item Accuracy (\% der richtig klassifizierten Daten über allen)
\item F1-Score (Gewichtetes Maß zwischen Precision und Recall)
\end{itemize}
\subsubsection{ROC Kurve}
Siehe Bild im Repo
\begin{itemize}[noitemsep,nolistsep]
\item Achsen:
\begin{itemize}[noitemsep,nolistsep]
\item X: False Positive Rate
\item Y: True Positive Rate
\item (0,0): alle Prognosen negativ
\item (1,1): alle Prognosen positiv
\item (1,0): Idealzustand, alle Prognosen korrekt
\end{itemize}
\item Diagonale (Ergebnis zufälligen Ratens)
\item Area under the Curve (AUC)
\begin{itemize}[noitemsep,nolistsep]
\item Idealwert 1, Zufallsmodell 0.5
\end{itemize}
\item \textcolor{red}{Bester Split beim Punkt, der am nächsten an (1,0) liegt!}
\item ROC visuell lösen:
\begin{itemize}[noitemsep,nolistsep]
\item Oben rechts in Vis anfangen, links in der Tabelle
\item Tabelle vorstellen, dass Grenze Schritt für Schritt nach rechts geschoben wird. (Links der Grenze Klasse A, rechts Klasse B)
\item Wenn hinzukommender Eintrag richtig klassifiziert wird: Curve geht 1 Schritt nach links
\item Wenn hinzukommender Eintrag falsch klassifiziert wird: Curve geht 1 Schritt nach unten
\item Schrittgröße Links = $\dfrac{1}{Anzahl_{neg.\:Einträge}}$
\item Schrittgröße runter = $\dfrac{1}{Anzahl_{pos.\:Einträge}}$
\end{itemize}
\item Schwellenwerte ablesen:
\begin{itemize}[noitemsep,nolistsep]
\item Oben rechts anfangen und abzählen
\item Punkt finden und dann $>= S_{Punkt}$
\end{itemize}
\item Gewichtung ändern:
\begin{itemize}[noitemsep,nolistsep]
\item FP x-mal schwerer als FN (FPR Achse mal x skalieren)
\item FN x-mal schwerer als FN (TPR Achse mal x skalieren)
\end{itemize}
\end{itemize}
\section{Clustering}
\begin{itemize}[noitemsep,nolistsep]
\item Ordne Datenobjekt einem Cluster zu
\item Objekt innerhalb des Clusters möglich ähnlich
\item Objekte aus unterschiedlichen Clustern möglichst unterschiedlich
\item Exklusives Clustering (Daten dürfen nur einem C angehören) - nicht exklusives
\item Probabilistisches Clustering (Datenpunkte gehören mit Wahrscheinlichkeit X zu Cluster. Alle Wahrscheinlichkeiten aufaddiert = 1)
\item Fuzzy Cluster (daten gehören anteilig zu Clustern)
\item Vollständiges Clustering (Alle Datenpunkte sind in einem C)
\item Partielles Clustering (Es gibt Daten ohne Cluster)
\end{itemize}
\subsection{Arten von Clustern}
\begin{itemize}[noitemsep,nolistsep]
\item Wahl-separierte Cluster
\begin{itemize}
\item Jeder Punkt eines Clusters liegt näher an jedem anderen Punkt des Clusters als an irgendeinem Punkt eines anderen Clusters
\end{itemize}
\item prototyp-basiert
\begin{itemize}[noitemsep,nolistsep]
\item Jeder Punkt liegt näher am Prototypen des Clusters, als an einem anderen Prototypen
\item Zentroid: Durchschnitt aller Punkte (Schwerpunkt)
\item Mediod: mittlerer Punkt (Median)
\end{itemize}
\item kontiguitäts-basiert
\begin{itemize}[noitemsep,nolistsep]
\item Jeder Punkt eines Clusters liegt näher an (ist ähnlicher zu) einem oder mehreren Punkten des Clusters als zu irgendeinem Punkt eines anderen Clusters
\end{itemize}
\item dichte-basiert
\begin{itemize}[noitemsep,nolistsep]
\item Ein Cluster ist eine Region dichter Punkte, die durch Regionen mit geringer Punktdichtevon anderen Regionen mit hoher Punktdichte separiert ist
\item Einsatz bei \textbf{unregelmäßig geformten Clustern} \& \textbf{bei Datenrauschen oder Ausreißern}
\end{itemize}
\end{itemize}
\subsection{Partitionierendes Clustering (K-Means)}
\subsubsection{Eigenschaften:}
\begin{itemize}[noitemsep,nolistsep]
\item Vollständig partitionierend
\item prototyp-basiert (Zentroid)
\item Anzahl der Cluster muss vorgegeben werden
\item Speicherplatzkomplexität: $O((n+K)*d)$
\item Laufzeitkomplexität: $O(n*K*I*d)$
\item $n$= Anzahl der Punkte, $K$= Anzahl der Cluster, $I$= Anzahl der Iterationen, $d$=Anzahl der Attribute
\item Algo konvergiert recht schnell
\item Durch zufällig gewählte Zentroids unterschiedliche Ergebnisse
\item Häufig wird nur lokale und nicht globale Minimum gefunden!
\end{itemize}
\subsubsection{Algorithmus:}
\begin{itemize}[noitemsep,nolistsep]
\item Select k points as initial centroids
\item repeat
\begin{itemize}[noitemsep,nolistsep]
\item Form k clusters by assigning all points to the closets centroid
\item recompute the centroid of each cluster
\end{itemize}
\item until centroids don't change
\end{itemize}
\subsubsection{Zielfunktion}
\begin{itemize}[noitemsep,nolistsep]
\item Sum of Squared Error (SSE)
\item Fehler: Abstand eines Datenpunkts zum nächstgelegenen Zentroid
\item $SSE = \sum_{i=1}^{k}\sum_{x \epsilon c_i} dist(m_i, x)^2$
\item Summe sinkt mit jeder Iteration bis lokales/globales Min erreicht ist
\end{itemize}
\subsubsection{Optimierung KMeans}
\begin{itemize}[noitemsep,nolistsep]
\item Mehrfach ausführen (Wahrscheinlichkeit schlecht)
\item Zentroid Wahl über Heuristik (Wahl nacheinander mit möglichst großem Abstand)
\item Bisecting (Erst zwei Cluster, dann weiter spalten)
\end{itemize}
\subsubsection{Grenzen und Probleme KMeans}
Schlecht bei:
\begin{itemize}[noitemsep,nolistsep]
\item Cluster unterschiedlicher Größe
\item Cluster unterschiedlicher Dichte
\item Cluster nicht kugelförmig sind
\item Cluster mit Ausreißer oder Rauschenhaben
\end{itemize}
\subsection{DBSCAN - dichte basiertes Clustering}
\subsubsection{Eigenschaften}
\begin{itemize}[noitemsep,nolistsep]
\item Keine Probleme mit unterschiedlichen Clustergrößen und -formen
\item Unempfindlich gegenüber Rauschen
\end{itemize}
\begin{itemize}[noitemsep,nolistsep]
\item Kernpunkt
\begin{itemize}[noitemsep,nolistsep]
\item Punkt, in derem $\epsilon$ Umgebung sich mindestsns $MinPts$ befinden
\item Kernpunkt wird mitgezählt
\end{itemize}
\item Randpunkt
\begin{itemize}[noitemsep,nolistsep]
\item Nicht Kernpunkt
\item Aber in $\epsilon$ Distanz von kernpunkt entfernt ist
\end{itemize}
\item Rauschpunkt
\begin{itemize}[noitemsep,nolistsep]
\item Weder Kern- noch Randpunkt
\end{itemize}
\end{itemize}
\subsubsection{Algorithmus}
\begin{itemize}[noitemsep,nolistsep]
\item Kennzeiche alle Punkte als, kern, Rand und Rauschpunkt
\item Lösche Randpunkte
\item Verbinde alle Kernpunkte, die in $\epsilon$ Distanz liegen
\item Jede Gruppe von Kernpunkten wird ein Cluster
\item Jeder Randpunkt wird einem Cluster zugeordnet
\end{itemize}
\subsubsection{Parameter auswählen}
\begin{itemize}[noitemsep,nolistsep]
\item $\epsilon$
\begin{itemize}[noitemsep,nolistsep]
\item Plotte Abstände zu allen k Nachbarn
\item Randpunkte haben kurze Distanz, Rauschpunkte große
\item Sobald Distanz sign. ansteigt, $\epsilon$ ablesen
\end{itemize}
\item $MinPts$
\begin{itemize}[noitemsep,nolistsep]
\item Zu kleiner Wert führt zu Miniclustern
\item Wert erhöhen bis Anzahl der Cluster nicht mehr stark sinkt
\end{itemize}
\end{itemize}
\subsubsection{Grenzen und Probleme DBSCAN}
Schlecht bei:
\begin{itemize}[noitemsep,nolistsep]
\item Cluster unterschiedlicher Dichte
\item hochdimensionalen Daten
\end{itemize}
\subsection{Hierarchisches Clustering}
\subsubsection{Eigenschaften}
\begin{itemize}[noitemsep,nolistsep]
\item Erzeugt Menge von verschachtelten Clustern
\item Baumdiagramm der Cluster als Dendogram darstellbar
\item Keine Angabe von Clusteranzahl nötig! (Anzahl kann sich nach Erstellung beliebig ausgesucht werden)
\item Agglomeratives Clustern (verschmelzent)
\item Divisives Clustern (teilend)
\item Verwenden beide Ähnlichkeits- oder Distanzmaße (Greedy Ansatz)
\item Speicherplatzkomplexität: $O(n^2)$
\item Zeitkomplexität: $O(n^3)$
\end{itemize}
\subsubsection{Algo agglomeratives Clustering}
\begin{itemize}[noitemsep,nolistsep]
\item Abstandsmatrix berechnen
\item repeat
\begin{itemize}[noitemsep,nolistsep]
\item Merge 2 dichteste Cluster
\item Update Abstandsmatrix
\end{itemize}
\item until, 1 Cluster übrig bleibt
\end{itemize}
\subsubsection{Inter-Cluster Abstand}
\begin{itemize}[noitemsep,nolistsep]
\item Minimaler Abstand (Single Link)
\begin{itemize}[noitemsep,nolistsep]
\item Wähle immer das Minimum der kleinsten Abstände aus
\item Kein Problem mit nicht eliptischen Clustern!
\item Probleme mit verrauschten Daten und Ausreißern
\end{itemize}
\item Maximaler Abstand (Complete Link)
\begin{itemize}[noitemsep,nolistsep]
\item Wähle immer das Minimum der maximalsten Abstände aus
\item Kaum/Keine Probleme mit verrauschten Daten und Ausreißern
\item Bevorzugt kugelförmige Cluster
\item Trennt große Cluster häufiger auf
\end{itemize}
\item Durchschnittlicher Abstand (Average Link)
\begin{itemize}[noitemsep,nolistsep]
\item Der Abstand zweier Cluster entspricht dem Durchschnitt der Abstände aller Punktpaareaus den verschiedenen Clustern
\item Wähle immer das Minimum der durchschnittlichen Abstände
\item KOmpromiss zwischen Min und Max Distanz
\item Stärke (Weniger anfällig für Rauschen, Trennt große Cluster weniger häufiger)
\item Schwäche (Bevorzugt kugelförmige Cluster, Berechnung aufwändig)
\end{itemize}
\end{itemize}
\end{multicols}
\end{landscape}
\end{document}