Projekt I

Piet Ostendorp, Marcel Anker, Lennart Heinrich

Naive Bayes

1) Verwendeter Algorithmus

Der verwendete Machine Learning Algorithmus ist Naive Bayes.

2) Klassifizierung der gegebenen Daten

Siehe python main.py Naive Bayes oder eigene Implementation in cargo run (src/*.rs).
Hinweis: Trotz Verwendung des StratifiedShuffleSplit und des Seeds 42 erzeugen scikit-learn (Python) und KNIME einen unterschiedlichen Train/Test-Split. Für die Implementierung in Python sowie Rust wurde der Split der Python-Implementierung verwendet (siehe shuffle.py).

3) Einstellungen, Konfiguration, Hyperparameter

Für Naive Bayes gibt es zum grundlegenden Ansatz kaum Einstellungen, Konfiguration oder Hyperparameter. Je nach Implementierung kann eine Standard-Wahrscheinlichkeit (bei Features ohne Daten) oder Minimum-Standardabweichung (wenn sonst 0) gesetzt werden. Beides ist nicht relevant für die gegebenen Daten, da für alle Features Daten vorliegen und die Standardabweichung ungleich 0 ist.

Es können jedoch verschiedene Dichtefunktionen verwendet werden:

Der Algorithmus basiert auf dem Satz von Bayes:
$$P(K|F_1, \ldots, F_n) = \frac{P(K) \cdot P(F_1, \ldots, F_n|K)}{P(F_1, \ldots, F_n)}$$

• $K$: Klasse
• $F_i$: Feature $i$ bzw. Merkmal $i$
  
  

Die Wahrscheinlichkeit $P(F_1, \ldots, F_n)$ ist unabhängig von der Klasse, weshalb für gegebene Features $F_1, \ldots, F_n$ immer die Klasse eine höhere Wahrscheinlichkeit hat, bei der der Zähler größer ist:
$$P(K|F_1, \ldots, F_n) \sim P(K) \cdot P(F_1, \ldots, F_n|K)$$

Unter Annahme der bedingten Unabhängigkeit gilt:
$$P(K|F_1, \ldots, F_n) \sim P(K) \cdot P(F_1, \ldots, F_n|K) = P(K) \cdot P(F_1|K) \cdot \ldots \cdot P(F_n|K)$$ $$\implies P(K|F_1, \ldots, F_n) \sim P(K) \cdot \prod_{i=1}^{n} P(F_i|K)$$

Die Klasse, bei der $P(K) \cdot P(F_1|K) \cdot \ldots \cdot P(F_n|K)$ am größten ist, ist die vorhergesagte Klasse des Naive Bayes Algorithmus für die gegebenen Features.

Die Wahrscheinlichkeit $P(K)$ kann für eine gegebene Stichprobe (annähernd) als relative Häufigkeit einfach berechnet werden.
Die Wahrscheinlichkeiten $P(F_i|K)$ können hingegen nicht einfach als relative Häufigkeit berechnet werden, wenn die Features $F_i$ stetige Merkmale sind.
Es ist also eine Annäherung an die Häufigkeitsdichte notwendig. Hierfür kann z.B. eine Normalverteilung angenommen werden und die Dichtefunktion der Gaußschen Normalverteilung verwendet werden. Die Dichte an einer Stelle wird dann vereinfacht als $P(F_i|K)$ angenommen, wobei die Dichtefunktion für jedes Feature jeder Klasse separat ermittelt wird.

Alternativ kann eine Kernel Density Estimation verwendet werden, die den Verlauf der gegebenen Daten glättet.
Die Glättung ist abhängig von der Bandbreite $h$, welche als Konstante angegeben werden kann oder z.B. für jedes Feature einer Klasse mithilfe der Rule Of Thumb $$h = 0.9 \cdot \min\left(\sigma, \frac{\text{IQR}}{1.34}\right) \cdot n^{-1/5}$$ geschätzt werden kann.
Darüber hinaus können verschiedene Kerne verwendet werden. Die Rust Implementierung verwendet als Kern weiterhin die Dichtefunktion der Gaußschen Normalverteilung.

Die einzigen verfügbaren Parameter bei Verwendung von Naive Bayes sind also die verwendete Dichtefunktion und die Parameter dieser Dichtefunktion.
Getestet wurden:

1. Gaussian: Dichtefunktion der Gaußschen Normalverteilung
2. KDE-ROT: Kernel Density Estimation mit der Rule Of Thumb (siehe oben)
3. KDE (sonstige): Kernel Density Estimation mit fester Bandbreite (z.B. 10; 2; 1; 0.1; 0.05; 0.0001)

Gaussian und KDE-ROT lieferten die besten Ergebnisse (siehe 5.), während verschiedene feste Bandbreiten zu schlechteren Ergebnissen führten.
Mit einer Bandbreite von 10 (etwa der gesamte IQR/Interquartilsabstand) wurden 100% aller Testdaten als "Good" klassifiziert, während Bandbreiten zwischen im Bereich von 0,X nahe an die Wert der ROT gekommen sind.
Bei Verwendung gleicher Trainings- und Testdaten konnte mit einer Bandbreite von 0,0001 jeder Datensatz korrekt klassifiziert werden (Overfitting).

Insgesamt ist der am besten geeignete Parameter beim Naive Bayes Algorithmus lediglich die Verwendung der Dichtefunktion der Gaußschen Normalverteilung gewesen. Weitere Parameter z.B. bei der KDE haben zu keiner Verbesserung geführt.

4) Klassifizierung der gegebenen Daten

siehe 2.

5) Laufzeit des Trainings und der Vorhersage, Ergebnisse, Fehlermetriken

Laufzeit (Rust, Gaussian)	Wert
Training	1064 us (1.0 ms)
Testing	2580 us (2.6 ms)

Laufzeit (Python, Gaussian)	Wert
Training	3713 us (3.7 ms)
Testing	874 us (0.9 ms)

Laufzeit (Rust, KDE-ROT)	Wert
Training	5185 us (5.2 ms)
Testing	442 714 us (442.7 ms)

Die Laufzeit für Training (6400 Datensätze) und Testing (Vorhersage der übrigen 1600 Datensätze) liegt bei beiden Implementierungen (Rust und Python) unter Verwendung der Gaußschen Dichtefunktion bei 3-4 ms. Die lange Laufzeit beim Testing unter Verwendung der Kernel Density Estimation mit der Rule Of Thumb zur Bestimmung der Bandbreite ist dadurch bedingt, dass die Dichtefunktion an einem Punkt in Abhängigkeit von den Trainings- und Testdaten berechnet werden muss. Dieser Schritt (lineare Komplexität) kann nicht bereits beim Training passieren.

Ergebnis (Gaussian)	Wert
True Positives	735
True Negatives	682
False Positives	117
False Negatives	66
Sum	1600

Ergebnis (KDE-ROT)	Wert
True Positives	699
True Negatives	699
False Positives	100
False Negatives	102
Sum	1600

Die Ergebnisse der Rust und Python Implementierung (Gaussian) sind identisch, wobei die Positives der Klasse Good entsprechen.
Die Variante Gaussian hat im Vergleich zu KDE-ROT insgesamt mehr Datensätze korrekt klassifiziert.
Bei der Variante KDE-ROT sind jedoch die fehlerhaften Klassifizierungen gleichmäßiger auf beide Klassen verteilt.

Fehlermetrik (Gaussian)	Wert
Accuracy	0.885625
Error	0.114375
Precision	0.8626760563380281
Recall	0.9176029962546817
F1-Score	0.8892921960072595

Fehlermetrik (KDE-ROT)	Wert
Accuracy	0.874375
Error	0.125625
Precision	0.8748435544430538
Recall	0.8726591760299626
F1-Score	0.87375

Die Fehlermetriken (Gaussian) unterscheiden sich zwischen den beiden Implementierung nur minimal aufgrund von sehr kleinen Rundungsfehlern.
Die Variante Gaussian ist in jeder Fehlermetrik außer der Precision besser als KDE-ROT. Die Unterschiede liegen jedoch im Bereich von einem Prozentpunkt (mit Ausnahme vom Recall).

Die Klassifizierung der Daten mithilfe des Naive Bayes Algorithmus hat insgesamt relativ gut funktioniert.

6) Recherche und Komplexität

Die Recherche-Ergebnisse wurden zur Implementierung des Naive Bayes Algorithmus in Rust verwendet. Auf Basis dieser kann die Komplexität des Algorithmus beschrieben werden, wobei zwischen den verschiedenen Dichtefunktionen unterschieden werden muss.

1. Gaussian

Bei Verwendung der Dichtefunktion der Gaußschen Normalverteilung müssen beim Training lediglich folgende Werte berechnet werden:

1. Relative Häufigkeit einer Klasse
2. Erwartungswerte (Durchschnitt) eines Features/Merkmals über alle Datensätze einer Klasse
3. Stichprobenstandardabweichung eines Features/Merkmals über alle Datensätze einer Klasse

Zur Berechnung eines dieser Werte wird jeder Datensatz genau einmal betrachtet (2 Schleifen über alle Datensätze und Features). Diese Berechnungen haben also eine lineare Laufzeit-Komplexität: $O(n * m)$ mit $n$ als Anzahl der Datensätze und $m$ als Anzahl der Features/Merkmale eines Datensatzes.
Die Speicher-Komplexität ist ebenfalls linear: $O(n * m)$

Für das Testing gilt:
Laufzeit-Komplexität: $O(k * m * c)$ mit $k$ als Anzahl der zu klassifizierenden Datensätze, $m$ als Anzahl der Features/Merkmale eines Datensatzes und $c$ als Anzahl der Klassen. Diese ist also für einen zu klassifizierenden Datensatz linear abhängig von der Anzahl der Features.
Die Speicher-Komplexität ist nun: $O(c * m + k * m)$ mit $c$ als Anzahl der Klassen, $m$ als Anzahl der Features und $k$ als Anzahl der zu klassifizierenden Datensätze.

2. Kernel Density Estimation

Bei der Kernel Density Estimation muss nun nicht mehr der Erwartungswert berechnet werden. Stattdessen ist die Bestimmung des IQR/Interquartilsabstands notwendig.
Die Bestimmung des IQR für ein Feature einer Klasse hat eine Laufzeit-Komplexität von $O(n * log(n))$ mit $n$ als Anzahl der Datensätze, da diese hierfür sortiert werden müssen.

Das Training hat damit eine Laufzeit-Komplexität von $O(m * n * log(n))$ mit $n$ als Anzahl der Datensätze und m als Anzahl der Features/Merkmale eines Datensatzes.
Die Speicher-Komplexität bleibt im Vergleich zu Gaussian unverändert, da der verwendete Sortieralgorithmus eine lineare Speicher-Komplexität hat.

Das Testing ist jedoch wesentlich komplexer, da nun jedes Feature eines zu klassifizierenden Datensatzes zusammen mit jedem Feature jedes Datensatzes jeder Klasse der Trainingsdaten betrachtet werden muss. Die Laufzeit-Komplexität beträgt dann $O(k * n * m * c)$ mit $k$ als Anzahl der zu klassifizierenden Datensätze, $n$ als Anzahl der Trainings-Datensätze, $m$ als Anzahl der Features/Merkmale eines Datensatzes und $c$ als Anzahl der Klasse.
Die Speicher-Komplexität bleibt unverändert zu Gaussian.

Aufgrund der hohen Laufzeit-Komplexität und größtenteils schlechteren Ergebnisse der Kernel Density Estimation eignet sich die Variante Gaussian beim gegebenen Datensatz besser.

Support Vector Machine

1) Verwendeter Algorithmus

Der verwendete Machine Learning Algorithmus ist die Support Vector Machine.

2) Klassifizierung der gegebenen Daten

Siehe python main.py SVM.
Hinweis: Trotz Verwendung des StratifiedShuffleSplit und des Seeds 42 erzeugen scikit-learn (Python) und KNIME einen unterschiedlichen Train/Test-Split. Für die Implementierung in Python wurde der Split der Python-Implementierung verwendet.

3) Einstellungen, Konfiguration, Hyperparameter

Die State Vector Machine in der Bibliothek scikit ist in der Klasse SVC (State Vector Classification) enthalten. Scikit liefert für diese 15 Hyperparameter, von denen die folgenden für die Implementierung verwendet wurden:

• kernel: Spezifiziert, welcher Kernel zur Bestimmung der Entscheidungsgrenze verwendet wird. Wir haben uns für die rbf (radial basis function) entschieden, da diese in unseren Tests allgemein am besten abgeschnitten hat. Sie versucht eine Grenze der zu klassifizierenden Daten anhand der folgenden Funktion zu bestimmen: $$ K(x_i, x_j) = \exp\left(-\gamma, ||x_i - x_j||^2\right)$$
• C: Ein Regularisierungsparameter welcher eine Toleranz gegenüber Ausreißern erzeugt. Hohe C-Werte können zu Overfitting führen, während kleine Werte zu mehr Fehler, aber dafür zu einer glatteren Trennlinie führt. C legt also fest, wie stark Fehlklassifikation bestraft wird. 1.0 stellt einen soliden C-Wert dar, weshalb wir diesen verwendet haben.
• gamma: Bestimmt den Radius des Einflusses von einzelnen Datenpunkten auf die Grenzfunktion. Große Gamma-Werte führen zu sehr lokalen Einflüssen und somit komplexen Funktionen und somit zu Overfitting. Kleine Gamma-Werte resultieren in Underfitting. Konfiguriert haben wir Gamma auf scale, was den Startwert von Gamma aus der folgenden Formel berechnet:
  $$\gamma = \frac{1}{n_{\text{features}} \cdot \mathrm{Var}(X)}$$
• random_state: Das Äquivalent des random_seed. Auf 42 festgelegt.
• probability: Auf true gesetzt, damit der random_state nicht ignoriert wird.

4) Klassifizierung der gegebenen Daten

siehe 2.

5) Laufzeit des Trainings und der Vorhersage, Ergebnisse, Fehlermetriken

Laufzeit (SVC, mit probability=True)	Wert
Training	685407 us (685 ms)
Testing	50311 us (50 ms)

Laufzeit (SVC, mit probability=False)	Wert
Training	107698 us (107 ms)
Testing	46253 us (46 ms)

Das Training auf der Support Vector Machine mit probability=True dauert 685ms. Hier ist wichtig zu erwähnen, dass enablen des Parameters probability für eine verlängerte Trainingszeit sorgt, da dann die sog. 5-fold cross-validation durchgeführt wird. Ohne diesen Wert dauert das training nur 107ms. Die Testingzeit und die resultierenden Ergebnisse bleiben unverändert. Das Testing benötigt 46-50ms.

Ergebnis	Wert
True Positives	781
True Negatives	790
False Positives	9
False Negatives	20
Sum	1600

Fehlermetrik	Wert
Accuracy	0.98188
Error	0.01812
Precision	0.98861
Recall	0.97503
F1-Score	0.98177

Insgesamt hat das Training mit der Support Vector Machine gut funktioniert. Im Vergleich zum Naive Bayes lässt aber vor allem die Trainings und Testing Zeit zu wünschen übrig.

6) Recherche und Komplexität

Die Komplexität des Algorithmus unterscheidet sich zwischen den verschiedenen Kernel-Funktionen. Im Folgenden wird hauptsächlich auf den verwendeten RBF-Kernel eingegangen.

1. Radial Basis Function

Im Rahmen des Trainingsprozesses wird eine Kernelmatrix erstellt, in der die Ähnlichkeit zwischen allen Trainingsdaten berechnet wird. Jede Eintrag dieser Matrix beschreibt die Distanz zweier Datenpunkte im Raum unter Verwendung der bereits angesprochenen RBF-Funktion: $$ K(x_i, x_j) = \exp\left(-\gamma, ||x_i - x_j||^2\right)$$

Traingsphase:
Für die Berechnung der Kernelmatrix müssen alle möglichen Paare von Datensätze betrachtet werden. Dies führt zu einem quadratischem Aufwand hinsichtlich der Traingsdaten $n$. Die Berechnung der Distanz zwischen zwei Datenpunkten hängt zusätzlich von der Anzahl der Features/Mermale $m$ ab. Die Laufzeit-Komplexität berträgt somit: $O(n^2*m)$

Anschließend muss ein quadratisches Optimierungsproblem gelöst werden, um die optimalen Gewichte zu bestimmen. Die theoretische Komplexität liegt dasfür bei $O(n^3)$. Alternativ können allerdings effiziente Näherungsverfahren wie Sequential Minimal Optimization verwendet werden, die lediglich eine Komplexität von $O(n^2)$ aufweisen.

Die Speicher-Komplexität wird durch die Kernelmatrix dominiert und beträgt $O(n^2)$.

Testphase:
Bei der Klassifikation neuer Datenpunkte wird jeder Testdatensatz mit allen Support-Vektoren $s$ verglichen. Daraus ergibt sich eine Laufzeit-Komplexität von $O(s*m)$ bzw. eine Speicher-Komplexität von $O(s)$.

2. Weitere Kernel-Funktionen

Neben dem RBF-Kernel existieren natürlich noch weitere Funktionen, wie bspw. der lineare Kernel. Dabei kommt es nicht zu einer vollständigen Berechnung der Kernelmatrix und kann daher mit einer Laufzeit-Komplexität von $O(n*m)$ und einer Speicherkomplexität von $O(m)$ trainiert werden. Linearen SVM eignen sich deshalb besonders für große Datensätze.