Vergleich verschiedener Clusteringverfahren

Machine Learning Clustering in Python

Diesen Beitrag zusammen mit dem Code haben wir auch als Jupyter Notebook veröffentlicht.

In diesem Beitrag zeigen und vergleichen wir verschiedene Verfahren zum Clustering in Python. Unter Clustering versteht man das Zusammenfassen verschiedener Objekte zu Gruppen aus ähnlichen Objekten. Beispielsweise die Segmentierung von verschiedenen Käufergruppen im Einzelhandel.

Beim Clustering werden die einzelnen Eigenschaften eines Objekts mit den Eigenschaften anderer Objekte in einem Vektorraum verglichen. Ziel ist es in diesem Vektorraum auf Zusammenhänge zu schließen, mit denen sich einzelnen Gruppen der Objekte in einem Datensatz bilden lassen. Die einzelnen Vektoren, die dabei für die verschiedenen Eigenschaften eines Objekts stehen, werden auf ihre Nähe zu den Vektoren anderer Objekte hin in Cluster eingeteilt. Um die Nähe zweier Vektoren zu bestimmen ist prinzipiell jede Metrik zulässig. Meistens wird jedoch die euklidische Distanz, oder die quadrierte euklidische Distanz (L2-Norm) verwendet.

Häufig werden Unsupervised Learning Modelle für das Clustering verwendet. Dies bietet den Vorteil, dass keine bzw. nur wenige Annahmen über die zu findenden Cluster von vorneherein zu treffen sind. In diesem Beitrag gehen wir ausschließlich auf solche Modelle ein, da diese am weitesten verbreitet sind. Der Nachteil den diese Ansätze mit sich bringen liegt darin, Grundlagen zur Beurteilung des Ergebnisses zu finden, um auf diesen die einzelnen Verfahren zu vergleichen und zu bewerten.

Vergleich verschiedener Clusteringverfahren
Ergebnisse der Anwendung unterschiedlicher Clusteringverfahren auf verschiedenartige Datensätze

Eine Zusammenfassung der unterschiedlichen Clusteringverfahren findest Du in unserem Blog.

Validierung von Clusteringergebnissen

Es ist sehr schwer ein Clusteringergebnis objektiv zu bewerten, da ein Clusteringalgorithmus in eigener Verantwortung Cluster finden soll. Gäbe es bereits eine Einteilung der Objekte eines Datensatzes in Gruppen, wäre das Clustering überflüssig. Da diese Gruppeneinteilung aber nicht bekannt ist, ist es schwer zu sagen, ob ein Cluster gut gewählt ist oder nicht. Dennoch gibt es einige Methoden, mit denen sich zumindest bessere von schlechteren Clusteringergebnissen unterscheiden lassen. Nachfolgend haben wir eine Liste mit den gängigsten Methoden aufgestellt.

Elbow-Kriterium

Das Elbow-Kriterium eignet sich, um bei einem k-means Clustering die optimale Anzahl von Clustern zu bestimmen. Dabei trägt man in einem Diagramm auf der x-Achse die Anzahl der Cluster auf und auf der y-Achse die Summe der quadrierten Abweichungen der einzelnen Punkte zum jeweiligen Clusterzentrum. Falls auf dem Diagramm ein Knick erkennbar sein sollte, ist dieser Punkt die optimale Anzahl an Clustern. Denn ab diesem Punkt sinkt die Aussagekraft der einzelnen Cluster, da sich die Summe der quadrierten Abweichungen nur noch leicht verändert.

Gap Statistic

Die Gap Statistic vergleicht die Abweichungen der einzelnen Objekte innerhalb eines Clusters im Bezug zu dem jeweiligen Zentrum. Dabei wird die Verteilung der Objekte mit einer zufälligen Verteilung verglichen. Je weiter dabei die Verteilung in Abhängigkeit zu der Anzahl der Cluster von der zufälligen Verteilung entfernt ist, desto besser ist die jeweilige Anzahl an Clustern.

Calinski-Harabasz Index

Der Calinski-Harabasz Index setzt die Separierung und Kompaktheit der Cluster in ein Verhältnis zueinander. Somit wird die Varianz der Quadratsummen der Abstände einzelner Objekte zu ihrem Clusterzentrum durch die Quadratsumme der Distanz zwischen den Clusterzentren und dem Mittelpunkt der Daten eines Clusters geteilt. Ein gutes Clusteringergebnis hat dabei einen hohen Calinski-Harabasz Index Wert.

Silhouettenmethode

Die Silhouettenmethode vergleicht den durchschnittlichen Silhouettenkoeffizienten unterschiedlicher Clusteranzahlen. Der Silhouettenkoeffizient gibt dabei an, wie gut die Zuordnung eines Objekts zu seinen beiden nächsten Clustern A und B ausfällt. Dabei ist der Cluster A der Cluster zu dem das Objekt zugeordnet wurde.

Der Silhouettenkoeffizient berechnet sich, in dem die Differenz des Abstands des Objekts zum Cluster B zu dem Abstand des Objekts zum Cluster A gebildet wird. Diese Differenz wird anschließend mit der maximalen Distanz des Objekts zu Cluster A und B gewichtet. Dabei kann das Ergebnis S(Objekt) zwischen -1 und 1 liegen. Falls S(Objekt) < 0 liegt das Objekt näher an Cluster B als an A. Demnach kann das Clustering verbessert werden. Falls S(Objekt) ≈ 0 Dann liegt das Objekt mittig der beiden Cluster. Somit ist das Clustering wenig aussagekräftig. Je weiter sich S(Objekt) an 1 annähert desto besser ist das Clustering für dieses. Silhouettenmethode wird nach der Anzahl an Clustern gesucht, für die der durchschnittliche Silhouettenkoeffizient am höchsten liegt.

Clustering

Zunächst werden wir uns einen Datensatz generieren um die Daten in Cluster einzuordnen.

Datensatzgenerierung

Unseren Datensatz generieren wir so, dass er aus insgesamt 80 zweidimensionalen Punkten besteht, die in einem festgelegten Radius zufällig um drei Punkte erzeugt werden. Dafür verwenden wir die Methode “make_blobs” aus scikit-learn.

Darstellung des Datensatzes
Darstellung des Datensatzes

Clusteringverfahren

Nachdem wir unsere Daten nun generiert haben, können wir mit dem eigentlichen Clustering beginnen. Dafür verwenden wir die Verfahren k-means, DBSCAN, HDBSCAN und OPTICS. Mit Ausnahme von HDBSCAN entstammen die Verfahren der scikit-learn Bibliothek. Für das HDBSCAN Verfahren gibt es aber ebenfalls eine vorgefertigte Bibliothek auf die wir zurückgegriffen haben. Dabei zählt k-means zu den partitionierenden Verfahren und die übrigen Verfahren werden als dichtebasierte Verfahren bezeichnet. Im Grunde sind HDBSCAN und OPTICS lediglich verbesserte Versionen des DBSCAN. Mit der Methode “fit_predict” von scikit-learn bestimmen wir mit jedem Modell die Zugehörigkeit der Punkte zu einem Cluster.

An dieser Stelle stellen wir die verwendeten Verfahren kurz vor und erläutern ihre Funktionsweise.

k-means

Das k-means Verfahren teilt den Datensatz in k Teile auf. Dies geschieht, in dem die Summe der quadratischen Abweichungen der einzelnen Punkte von den Clusterzentren minimiert wird. Problematisch an diesem Verfahren ist einerseits, dass bereits im Voraus die Anzahl der Cluster zu bestimmen ist, andererseits kann das Verfahren mit Datensätzen mit variierenden Dichten und Formen zum Teil nur schlecht umgehen. Dadurch ist es auf realen Datensätzen oftmals nicht bestens geeignet. Ebenfalls kann das Verfahren keine Noise Objekte, also Objekte die weit von einem Cluster entfernt liegen und diesem eigentlich nicht mehr zuzuordnen sind, nicht als solche erkennen.

DBSCAN

DBSCAN steht für “Density-Based Spatial Clustering of Applications with Noise”. Die Grundannahme des DBSCAN Algorithmus besteht darin, dass Objekte eines Clusters dicht zusammenliegen. Es werden 3 Arten von Objekten unterschieden:

  1. Kernobjekte sind Objekte die selbst dicht sind.
  2. Dichte-erreichbare Objekte sind Objekte, die selbst nicht dicht, aber von einem Kernobjekt erreichbar sind.
  3. Noisepunkte sind Objekte die weder dicht noch dichte-erreichbar sind.

Dabei wird ein Parameter epsilon und ein Parameter minPoints festgelegt. Epsilon bestimmt dabei die Distanz, ab wann ein Punkt von einem zweiten Punkt erreichbar ist, nämlich dann, wenn ihr Abstand kleiner als epsilon ist. MinPoints legt fest, ab wann ein Objekt dicht ist, also wie viele Objekte innerhalb des Abstands epsilon um einen Punkt liegen müssen.

HDBSCAN

HDBSCAN steht für “Hierarchical Density-Based Spatial Clustering” und basiert auf dem DBSCAN Algorithmus. Er erweitert diesen, indem er den DBSCAN Algorithmus in einen hierarchischen Clusteringalgorithmus überführt. Deswegen benötigt er keinen Abstand epsilon zur Bestimmung der Cluster. Damit ist es möglich Cluster unterschiedlicher Dichte zu finden und somit eine große Schwachstelle von DBSCAN zu beheben.

HDBSCAN funktioniert dabei, indem zunächst eine Zahl k festgelegt wird. Mit dieser wird bestimmt, wie viele Nachbarschaftsobjekte bei der Bestimmung der Dichte eines Punkts betrachtet werden. Hierin besteht ein entscheidender Unterschied im Vergleich zum DBSCAN Algorithmus. DBSCAN sucht in der gegebenen Distanz epsilon nach Nachbarn und HDBSCAN sucht nach der Distanz, ab der k Objekte in der Nachbarschaft liegen.

Nach dieser Zahl k wird die Kerndistanz für jeden Punkt bestimmt. Diese ist die kleinste Distanz, mit der k Objekte erreicht werden können. Außerdem wird eine Erreichbarkeitsmetrik eingeführt. Diese ist definiert als der größte Wert von entweder der Kerndistanz des Punktes A, der Kerndistanz des Punktes B, oder der Distanz von Punkt A zu Punkt B. Mit dieser Erreichbarkeitsmetrik wird anschließend ein minimaler Spannbaum gebildet. Mit Hilfe dieses Spannbaums wird nun die namens gebende Hierarchie gebildet.

HSBSCAN minimaler Spannbaum
HSBSCAN minimaler Spannbaum

Dazu wird immer die längste Kante aus dem Baum entfernt. Anschließend wird die Hierarchie zusammengefasst, indem in Abhängigkeit zur Distanz die einzelnen Punkte aus der Hierarchie herausfallen.

HSBSCAN Hierarchiebaum
HSBSCAN Hierarchiebaum

Falls mehr als zu Beginn definierte min_cluster_size Punkte bei einer Distanz herausfallen, bilden diese einen neuen Teilbaum. Anschließend wählt das Verfahren die Cluster aus, die die größte Stabilität aufweisen. Die Stabilität eines Cluster berechnet sich, in dem man die Summe der Kehrwerte der Distanz, ab welcher ein Punkt aus einem Cluster fällt, für aller Punkte eine Clusters berechnet. Das heißt liegen viele Punkte nahe am Clusterzentrum hat der Cluster eine hohe Stabilität. Auf dem Bild erkennbar an einer großen Fläche.

HDBSCAN zusammengefasster Hierarchiebaum
HDBSCAN zusammengefasster Hierarchiebaum

Auswertung

Für unsere Auswertung haben wir uns entschieden, die Metriken Calinski-Harabasz Index, die Silhouettenmethode und für das k-means Clustering speziell das Elbow Kriterium zu verwenden.

Wenn man sich die einzelnen Metriken für das k-means Clustering anschaut, stellt man fest, dass die optimale Anzahl an Clusterzentren 3 beträgt. Zwar deutet die Silhouettenmethode darauf hin, dass ein vierter Cluster durchaus sinnvoll wäre, allerdings spricht das Elbow Kriterium dagegen, da ein vierter Cluster keinen Knick bildet und somit nur einen sehr bedingten Mehrwert bietet. Nimmt man noch den Calinski-Harabasz Index dazu, erkennt man ebenfalls, dass der vierte Cluster nur einen schwach höheren Score erzielt. Daraus folgern wir, dass drei die optimale Anzahl an Clustern für ein k-means Clustering auf unserem Datensatz ist. Dieses Ergebnis gibt auch Sinn, wenn man bedenkt, dass wir unsere Daten um 3 Punkte generiert haben.

k-means Clustering
k-means Clustering

Für die beiden anderen Clusteringverfahren können wir die Anzahl der zu findenden Cluster nicht vorher bestimmen, sondern lediglich die Parameter vorgeben, nach denen die Algorithmen die Cluster finden. So haben wir uns dafür entschieden für das DBSCAN Verfahren die Distanz epsilon festzulegen und lediglich die Anzahl der minPoints zu variieren.

Dabei deutete die Silhouettenmethode auf die Anzahl von vier minPoints hin. Dagegen spricht der Calinski-Harabasz Index dafür nur drei minPoints festzulegen. Da der Unterschied von drei auf vier minPoints in der Silhouettenmethode geringer ausfällt als bei dem Calinski-Harabasz Index, entscheiden wir uns dafür, den Wert auf drei festzulegen. Dabei entsteht folgendes Clustering:

DBSCAN Clustering
DBSCAN Clustering

 

Wir erkennen, dass der Algorithmus sich für 4 Clusterzentren entschieden hat. Dabei wird deutlich, dass der DBSCAN Algorithmus Schwierigkeiten bei unterschiedlich dichten Clustern bekommt.

Beim HDBSCAN Verfahren variieren wir die kleinste Clustergröße. Das ist die Anzahl an Punkten, die bei dem hierarchischen Verfahren nötig ist, dass ein oder mehrere abgetrennte Punkte als neuer Cluster angesehen werden. Hierbei erhalten wir folgende Ergebnisse für den Calinski-Harabasz Index und die Silhouettenmethode.

Dabei erkennen wir, dass die optimale Größe zwischen vier und fünf Punkten liegt. Wir entscheiden uns für vier und erhalten folgendes Ergebnis.

HDBSCAN Clustering
HDBSCAN Clustering

Fazit

Es sollte deutlich geworden sein, dass es schwierig sein kann, Clusteringergebnisse auf einem Datensatz auf ihre Richtigkeit einzuordnen. Es gibt viele weitere Verfahren, die ebenfalls unterschiedliche Lösungen hervorgebracht hätten. Die Metriken zur Validierung der Clusteringergebnisse eignen sich im Einzelnen nur bedingt und so ist es stets sinnvoll eine Vielzahl von Metriken zur Hilfe zu ziehen und diese miteinander zu vergleichen, um somit den geeignetsten Algorithmus für den jeweiligen Anwendungsfall finden zu können und die Parameter bestens abstimmen zu können. Trotz der genannten Schwächen ermöglichen Clusteringverfahren unter Berücksichtigung der genannten Punkte, auch höher dimensionale Daten in Gruppen einzuteilen.


Machine Learning Klassifizierung in Python - Teil 2: Modellimplementierung und Performancebestimmung

Dies ist der zweite Teil unserer Serie Automatisierte Klassifizierung in Python, bei der wir verschiedene Verfahren anwenden, um den UCI Machine Learning Datensatz “Adult” zu klassifizieren. Nachfolgend gehen wir näher darauf ein, wie wir, nach der Vorbereitung unserer Daten im 1. Teil, die verschiedenen Modelle implementieren und anschließend auf ihre Performance vergleichen.

Klassifizierung

Wir verwenden für die Klassifizierung verschiedene scikit-learn Modelle. Die scikit-learn Bibliothek ist open-source und stellt eine Vielzahl an Tools zur Datenanalyse bereit. Unser Ziel ist es die Performance der folgenden Modelle miteinander zu vergleichen: logistische Regression, Decision Trees, Gradient Boosted Trees, k-Nearest Neighbors, Naive Bayes und ein neuronales Netz. Weiter unten fassen wir die genutzten Verfahren noch einmal kurz zusammen.

Im Allgemeinen verwenden die Modelle den Trainingsdatensatz, um eine Funktion zu erstellen, die die Beziehung zwischen Features und Targets beschreibt. Diese Funktion können wir nach dem Training auf Daten außerhalb des Trainingsdatensatzes anwenden, um deren Targets vorherzusagen. Weitere Informationen dazu, wie diese Funktion entsteht, haben wir in unserem Blog zusammengefasst. In unserem Fall übernimmt die scikit-learn Methode “fit” das Training der Modelle. Nachfolgend zeigen wir unsere Implementierung eines Modells anhand des folgenden Codebeispiels:

def do_decision_tree(self):
    """ Return a decision tree classifier object. """
    clf = tree.DecisionTreeClassifier()
    return clf.fit(self.x_train, self.y_train)

Wir erzeugen ein scikit-learn Decision Tree Classifier Objekt und trainieren es anschließend auf unserem Trainingsdatensatz.

Mit der scikit-learn Methode “predict” ist es möglich, ein Modell für einzelne Daten oder einen gesamten Datensatz Targets bestimmen zu lassen. Anhand der gewonnenen Ergebnissen bestimmen wir die Performance des Modells.

Klassifizierungsmodelle

In diesem Abschnitt fassen wir die Funktionsweise der einzelnen Verfahren kurz zusammen. Für eine genauere Erklärung des Modells, haben wir jeweils den passenden Beitrag aus unserem Blog und der scikit-learn Dokumentation verlinkt.

Logistische Regression

Die logistische Regression transformiert eine lineare Regression zu einer Sigmoidfunktion. Dadurch gibt die logistische Regression stets Werte zwischen 0 und 1 aus. Im Allgemeinen werden dabei jeweils Koeffizienten der einzelnen unabhängigen Features so angepasst, dass sich die einzelnen Objekte möglichst genau ihren Targets zuordnen lassen.

Decision Tree

Decision Tree Modelle sind einfache Entscheidungsbäume in der jeder Knoten ein Attribut abfragt, wonach der nächste Knoten wieder ein Attribut abfragt. Dies geschieht so lange, bis ein Blatt erreicht wird, dass den jeweiligen Klassifizierungsfall angibt. Weitere Informationen zu Decision Trees findest du in unserem Artikel zum Thema Klassifizierung.

Gradient Boosted Trees

Gradient Boosted Trees sind Modelle die aus mehreren einzelnen Decision Trees bestehen. Ziel ist es aus vielen simplen Modellen ein komplexes Modell zu entwerfen. Dabei wird nach einer differenzierbaren Verlustfunktion optimiert, indem die Koeffizienten der einzelnen Bäume so angepasst werden, dass die Verlustfunktion möglichst klein wird.

k-nearest Neighbors

Bei dem k-nearest Neighbors Modell werden die einzelnen Objekte in einem Vektorraum betrachtet und in Abhängigkeit zu den k nächsten Nachbarn klassifiziert. Eine ausführliche Erklärung zu diesem Modell ist in unserem Artikel zum Thema Klassifizierung zu finden.

Naive Bayes

Das Naive Bayes Modell betrachtet Objekte als Vektoren, deren Einträge jeweils einem Feature entsprechen. Dabei wird die Wahrscheinlichkeit der Zugehörigkeit jedes einzelnen Eintrags zum Target bestimmt und anschließend aufsummiert. Das Objekt wird dabei dem Target zugeordnet, dessen summierte Wahrscheinlichkeit am höchsten ist. Weitere Informationen zu dem Naive Bayes Modell sind in ebenfalls in unserem Artikel zum Thema Klassifizierung zu finden.

Neuronales Netz

Neuronale Netze bestehen aus einer oder mehreren Schichten von einzelnen Neuronen. Beim Training eines Neuronalen Netzes werden die gewichteten Verbindungen so angepasst, dass eine Verlustfunktion minimiert wird. Wir haben viele weitere Informationen zum Aufbau und der Funktion von neuronalen Netzen in unserem Artikel „Was sind künstliche neuronale Netze?“ zusammengefasst.

Performance-Bestimmung

Für die Bestimmung der Performance unserer Modelle haben wir eine Funktion “get_classification_report” geschrieben. Diese gibt uns die Metriken Precision, Recall, F-Score und die Fläche unter der ROC Kurve, sowie die dafür benötigten Kennzahlen, die wir jeweils in unserem Artikel näher beschreiben, durch den Aufruf der scikit-learn Funktion “metrics.classification_report” und “metrics.confusion_matrix” aus.

def get_classification_report(self, clf, x, y, label=""):
        """ Return a ClassificationReport object.

        Arguments:
        clf: The classifier to be reported.
        x: The feature values.
        y: The target values to validate the predictions.
        label: (optionally) sets a label."""

        roc_auc = roc_auc_score(y, clf.predict_proba(x)[:,1])
        fpr, tpr, thresholds = roc_curve(y, clf.predict_proba(x)[:,1])
        return ClassificationReport(metrics.confusion_matrix(y, clf.predict(x)),
        metrics.classification_report(y, clf.predict(x)), roc_auc, fpr, tpr, thresholds , label)

Lediglich die Receiver Operating Characteristic erhalten wir in Form eines Graphen der mit Hilfe der Python Bibliothek matplotlib und der scikit-learn Funktionen “roc_auc_score” und “roc_curve” erzeugt wird.

Auswertung

Abschließend gehen wir darauf ein, wie die Modelle auf unseren Daten performt haben.

KlassifikatorPrecisionRecallF-ScoreArea under CurveTrainingszeit (Sekunden)
Logistische Regression83%84%83%87%0,8
Decision Tree82%82%82%77%0,5
Gradient Boosted Trees88%88%87%93%142,9 (2 Minuten)
k-nearest Neighbors84%84%84%88%2,1
Naive Bayes84%83%83%89%0,1
Neuronales Netz83%83%83%89%1.746 (29 Minuten)

Im direkten Vergleich erkennt man, dass die neuronalen Netze sehr lange Trainingszeiten brauchen, um gute Ergebnisse erzielen zu können. Mit unseren Einstellungen hat das Training ca. 29 Minuten gedauert und es wurde eine Precision von 83% erreicht. Im Gegensatz dazu erreichte der Naive Bayes Klassifikator die gleiche Genauigkeit und das in gerade einmal einem Zehntel einer Sekunde.

Reciever Operating Characteristic: Area under curve
Reciever Operating Characteristic: Area under curve

Das beste Ergebnis konnten wir mit den Gradient Boosted Trees erreichen. Dieser Klassifikator schaffte es in 143 Sekunden eine Precision von 88% zu erreichen. Zu dem, für die benötigte Trainingsdauer relativ schlechten Ergebnis des neuronalen Netzes, muss noch gesagt werden, dass unser Modell mit hoher Wahrscheinlichkeit schlicht nicht optimal gewählt wurde.

Das Training des Neuronalen Netzes und der Gradient Boosted Trees ist nicht auf GPUs durchgeführt worden, wodurch wir die Trainingsdauer hätten reduzieren können.


Machine Learning Performance Kennzahlen

Metriken zur Performancebestimmung bei Klassifizierungsproblemen

Wir stellen in diesem Artikel eine Reihe von Metriken vor, mit denen unterschiedliche Verfahren und trainierte Modelle für Klassifizierungsprobleme verglichen und bewertet werden können. In unserem Artikel Machine Learning Klassifizierung in Python – Teil 1: Data-Profiling und Vorverarbeitung stellen wir unterschiedliche Klassifizierungsverfahren vor, deren Performance mit den hier beschriebenen Metriken verglichen werden können.

Die Fälle im Detail

Diese Fälle beziehen sich alle auf das vorhergesagte Target eines zu klassifizierenden Objekts. Nachfolgend listen wir dabei alle Fälle zusammen mit ihrer Bedeutung auf.

  • True Negative: Der Fall eines richtig nicht als Treffer eines klassifizierten Targets eines Objekts.
  • False Negative: Der Fall eines falscherweise nicht als Treffer klassifizierten Targets eines Objekts.
  • True Positive: Der Fall eines richtig als Treffer klassifizierten Targets eines Objekts.
  • False Positive: Der Fall eines falsch als Treffer klassifizierten Targets eines Objekts.
Darstellung Klassifizierungsfälle
Darstellung der Klassifizierungsfälle

Beispiel: Fluggastdatenweitergabe an das BKA

Um die Begriffe noch einmal zu verdeutlichen, schauen wir uns einen Artikel zur Weitergabe von Fluggastdaten an das Bundeskriminalamt (BKA) der SZ vom 24. April 2019 an. Seit dem 29. August 2018 wurden Daten von Fluggästen automatisch an das BKA zur Auswertung übermittelt. Mit diesen Daten sollen gesuchte Straftäter und Verdächtige identifiziert werden. Die Daten bestehen aus Namen, Anschrift, Zahlungsdaten und Flugdaten, wie Reisedatum, Uhrzeit, Start- und dem Zielflughafen des Reisenden und werden im Passenger Name Record gespeichert.

Diese Daten sollen zukünftig nicht nur für die Identifizierung von Straftätern dienen, sondern ebenfalls im “Predictive Policing” zum Einsatz kommen. Beim “Predictive Policing” handelt es sich um die Analyse von geschehenen Straftaten zur Berechnung der Wahrscheinlichkeiten zukünftiger Straftaten. Ziel ist es, dass Muster, wie z.B. die Einbruchsrate in einem Wohngebiet, erkannt werden sollen, um so gezielter Polizeikräfte einsetzen zu können.

False Positives bei großen Datenmengen

Seit Beginn der Erfassung bis zum 31. März 2019 wurden insgesamt 1,2 Mio. Fluggastdaten übergeben. Von diesen hat ein Algorithmus 94.098 Flugreisende als potenziell verdächtig klassifiziert. Alle Treffer werden anschließend von Beamten auf ihre Richtigkeit geprüft. Dabei stellte sich heraus, dass von diesen Treffern lediglich 277 echte Treffer (True Positive) waren. Bei den übrigen 93.821 klassifizierten Verdächtigen handelte es sich um falsche Treffer (False Positives). Die Reisenden aus der verbleibenden Menge die falscher Weise nicht als Verdächtige klassifiziert wurden, lassen sich in der Regel nicht genau ermitteln (False Negative). Der Rest der Daten, die richtigerweise nicht als Treffer klassifiziert wurden, ergeben die True Negatives.

Der Artikel kritisiert dabei die hohe Quote an False Positives. Denn dadurch würden häufig Menschen zu unrecht ins Visier von Behörden geraten, in diesem Fall nämlich 99,71% aller Treffer. Dabei ist jedoch zu erwähnen, dass durch eben diese hohe Fehlerrate die Wahrscheinlichkeit für False Negative Fälle sinkt. Das heißt, dass auf Kosten vieler Fehltreffer, nur wenige Zielpersonen nicht getroffen werden.

Häufig verwendete Performancemetriken

Anhand der Anzahl der aufgetretenen Fälle können wir einen Klassifikator unter verschiedenen Metriken betrachten und bewerten. In unserem Beitrag haben wir uns dafür entschieden die folgenden Metriken zu verwenden:

Precision

Eine sehr einfache Metrik ist die Precision. Diese gibt das Verhältnis an, wie viele Objekte ein Klassifikator aus dem Testdatensatz richtig als positiv klassifiziert hat, zu denen die falsch als positiv klassifiziert wurden. Die Formel lautet:

(True Positives) / (True Positives + False Positives)

Problematisch ist diese Metrik besonders bei einer binären Klassifikation, bei der eine Klasse im Beispieldatensatz überrepräsentiert wird: Der Klassifikator kann einfach alle Objekte des Datensatzes der überrepräsentierten Klasse zuordnen, würde aber dennoch eine relativ hohe Precision erreichen.
An dem Beispiel der Fluggastdaten berechnet sich die Precision wie folgt:

277 / (277 + 93.821) = 0,29%

Recall

Im Gegensatz zur Precision, gibt der Recall Score, auch Trefferquote genannt, den Anteil der richtig als positiv klassifizierten Objekte an der Gesamtheit der positiven Objekte an. Das heißt wir erhalten ein Maß zur Bestimmung, wieviele positive Targets als solche erkannt werden. Die Formel lautet:

(True Positives) / (True Positives + False Negatives)

F-Score

Die F-Score setzt Precision und Recall zusammen, um eine möglichst gute Einschätzung darüber zu erhalten, wie genau die Targets der Objekte bestimmt werden.
Dabei berechnet sich der F-Score über das harmonische Mittel mit der Formel:

F = 2 * (Precision * Recall) / (Precision + Recall)

Da wir keine Informationen zu den False Negatives in unserem Beispiel haben, ist es uns nicht möglich, Recall und F-Score zu bestimmen. In unserem Artikel verfügen wir hingegen über diese Information, und können beide Kennzahlen berechnen.

Fortgeschrittene Metriken – Receiver Operating Characteristic

Als letzte Metrik verwenden wir die Receiver Operating Characteristic Kurve. Diese gibt an, wie sicher der Klassifikator seine Ergebnisse erzielt. Dabei wird das Verhältnis der Trefferquote zu den False Positive klassifizierten Daten in Abhängigkeit eines Schwellenwerts in einem Graphen dargestellt.

 

Reciever Operating Characteristic: Area under curve
Reciever Operating Characteristic: Area under curve

Dieser Schwellenwert gibt an, ab wann ein Objekt zur einen oder zur anderen Klasse zugeordnet wird. Dabei ist der Schwellenwert in der linken unteren Ecke des Graphen am größten, das heißt, dass das Modell das Target eines Objekts nur dann als positiv bewertet, wenn ein Objekt mit absoluter Sicherheit dem Target zugehörig ist. Demnach geht die False Positive Rate hier stark gegen 0. Je weiter man sich der rechten oberen Ecke annähert, desto geringer wird der Schwellenwert und desto wahrscheinlicher wird es, dass das Modell ein Objekt fälschlicherweise als positiv klassifiziert, obwohl es eigentlich negativ war (False Positive). Die Fläche unter dem Graphen (Area under curve) dient also als Metrik für die Qualität eines getesteten Modells.

Zeit

Auch wenn die für das Training benötigte Zeit keine Aussage über die Qualität eines Klassifikators liefert, ist es häufig wichtig, zu berücksichtigen wie schnell ein Klassifikator trainiert werden kann. Die verschiedenen Verfahren sind unterschiedlich komplex was dazu führt, dass die Unterschiede der Zeit- und Rechenaufwände signifikant sein können.

Diese Zeitunterschiede können mit zunehmender Datensatzgröße exponentiell anwachsen, weshalb der Aspekt der Zeit, die ein Klassifikator bis zum Erreichen einer gewissen Genauigkeit benötigt, nicht zu vernachlässigen ist, besonders dann, wenn man mit sehr großen Datenmengen arbeitet. Um diesen Aspekt zu verdeutlichen, haben wir unsere Modelle auf reduzierten Datensätzen trainiert und die zeitlichen Unterschiede gemessen. Dabei haben wir folgendes Ergebnis erhalten.

Logarithmische Veränderung der Trainingszeiten bei Veränderung der Datenmenge
Logarithmische Veränderung der Trainingszeiten bei Veränderung der Datenmenge


Machine Learning Klassifizierung in Python - Teil 1: Data-Profiling und Vorverarbeitung

Dies ist der erste Teil der Serie Automatisierte Klassifizierung in Python in der wir beispielhaft zeigen, wie man einen gegebenen Datensatz mithilfe von Machine Learning Klassifizierungsverfahren in Python klassifizieren kann.

In folgendem Beitrag zeigen wir die Analyse und Aufbereitung des frei verfügbaren „Adult“ Datensatzes zur Klassifizierung. Ebenfalls haben wir unser Skript zusammen mit den Datensätzen und der Dokumentation auf GitHub veröffentlicht.

Der Datensatz entstammt dem Machine Learning Repository der University of California Irvine. Dieses beinhaltet derzeit 473 Datensätze (zuletzt aufgerufen: 10. Mai 2019), die für Machine Learning Anwendungen zur Verfügung stehen. Der “Adult” Datensatz’’ basiert auf US-Zensus Daten. Ziel ist es, anhand der gegebenen Daten zu bestimmen, ob eine Person mehr oder weniger als 50.000 USD im Jahr verdient.

Data-profiling

Der erste Schritt den wir vornehmen, bevor wir mit der eigentlichen Klassifizierung beginnen können, ist, dass wir uns die Struktur des Datensatzes anschauen. Dabei stellen wir fest, dass der Datensatz aus zusammengenommen ca. 45.000 Personendaten besteht und bereits in Trainings- und Testdaten aufgeteilt ist.

Ein Teil der Daten (ca. 7,5%) sind unvollständig da für einzelne Personen Datenpunkte (Features) nicht angegeben wurden. Aufgrund der relativ niedrigen Zahl der fehlerhafter Datensätze, werden wir diese zunächst einfach in der Analyse ignorieren.

Die Personendaten bestehen aus kontinuierlichen und kategorischen Features der Personen. Die kontinuierliche Daten sind: Alter, ‘final weight’, Bildungsjahre, Kapitalzuwachs, Kapitalverlust und Wochenstunden. Die kategorischen Daten sind: Beschäftigungsverhältnis, Abschluss, Familienstand, Beruf, Beziehung, Rasse, Geschlecht und das Geburtsland.

Unsere Zielvariable ist das Einkommen einer Person, genauer ob eine Person weniger oder mehr als 50.000 US-Dollar im Jahr verdient. Da unsere Zielvariable nur zwei verschiedene Werte annehmen kann, handelt es sich um eine binäre Klassifikation. Innerhalb des Datensatzes beträgt das Verhältnis zwischen Personen die weniger als 50.000 US-Dollar verdienen, zu jenen, die mehr verdienen ca. 3:1.

Analyse der Featureeigenschaften

Bei der Analyse der einzelnen Features ist das Feature ‘final weight besonders aufgefallen: Dieses gruppiert ähnliche Personen, basierend auf sozioökonomischen Faktoren und diese Wertung ist abhängig vom US-Bundesstaat in dem eine Person lebt.  Aufgrund des relativ kleinen Datensatzes und der ungenauen Dokumentation der zu Grunde liegenden Berechnung, haben wir uns entschieden, dieses Feature in der ersten Berechnung nicht zu berücksichtigen. Ein späterer direkter Vergleich zeigte, dass das Auslassen dieses Features in Einzelfällen zu einer Verbesserung der Klassifikationsergebnisse führte, aber nie zu einer Verschlechterung.

Um die Problemstellung zu lösen, anhand der genannten Features einer Person ihr Einkommen vorherzusagen, verwenden wir einen supervised Machine Learning Ansatz, da wir über viele gelabelte Daten verfügen. Anhand dieser kann der Algorithmus die Abhängigkeit der einzelnen Features zum Target abschätzen. Im zweiten Teil unseres Beitrags stellen wir dafür einige Verfahren vor, die wir bereits in unserem Blog behandelt haben. All diese Verfahren setzen jedoch zunächst eine sehr genaue Vorverarbeitung der Daten voraus, damit unser Modell in der Lage ist, diese zu bewerten und Werte wie etwa “Montag” oder “Dienstag” zu  interpretieren. Man spricht vom “cleaning” der Daten.

Vorverarbeitung der Daten

Wir müssen unsere Daten zunächst vorverarbeiten, um auf diese die verschiedenen Machine Learning Modelle anwenden zu können. Die verschiedenen Modelle vergleichen die einzelnen Features der Daten miteinander, um den Zusammenhang zum Target zu bestimmen. Dafür müssen die Daten in einer einheitlichen Form vorliegen, um dadurch eine Vergleichbarkeit zu ermöglichen. Deshalb sprechen wir vom säubern der Daten.

Mit der folgenden Funktion säubern wir unsere Daten. Die Funktionsweise erläutern wir in den folgenden Abschnitten:

def setup_data(self):
        """ set up the data for classification """
        traindata = self.remove_incomplete_data(self.traindata)
        testdata = self.remove_incomplete_data(self.testdata)
        
        self.y_train = self.set_target(traindata)
        self.y_test = self.set_target(testdata)

        # set dummies of combined train and test data with removed target variable
        fulldata = self.get_dummies(traindata.append(testdata, ignore_index=True).drop(self.target, axis=1).drop("fnlwgt", axis=1), self.categorical_features)
        self.x_train = fulldata[0:len(traindata)]
        self.x_test = fulldata[len(traindata):len(fulldata)]

Unser Datensatz ist zwar bereits in einen Trainings- und einen Testdatensatz im Verhältnis 2:1 aufgeteilt, für die Erzeugung von Dummyvariablen müssen wir ihn dennoch zwischenzeitlich zusammenführen, um ihn später wieder im gleichen Verhältnis aufteilen zu können. Dieses Vorgehen bietet den entscheidenden Vorteil, dass die entstehenden Datensätze unter allen Umständen die gleiche Form und Dimensionalität besitzen. Andernfalls kann es passieren, dass wenn ein Wert in entweder dem Trainings- oder Testdatensatz fehlt, der jeweils neue Datensatz weniger Spalten besitzt, bzw. die Spalten mit gleichem Index für verschiedene Feature-Werte stehen. Dadurch geht die Vergleichbarkeit der beiden Datensätze verloren.

Weiterhin kommen in dem Datensatz vereinzelt unbekannt Werte vor, die wir gezielt angehen müssen. Der Anteil an Daten mit unbekannten Werten des Datensatzes ist allerdings relativ klein (<10%). Deswegen ist es uns möglich, diese unvollständigen Daten außen vor zulassen und aus dem Datensatz zu entfernen. Dies erreichen wir in der Funktion „setup_data“ durch den Aufruf unserer Funktion „remove_incomplete_data“:

def remove_incomplete_data(self, data):
    """ Remove every row of the data that contains atleast 1 "?". """
    return data.replace("?", np.nan).dropna(0, "any")

Bei dieser werden alle Zeilen die mindestens ein „?“ enthalten aus dem Datensatz entfernt. Wir tun dies, um sicherzustellen, dass der Algorithmus stets relevante Daten erhält und keine Relationen zwischen unbekannten Werten erstellt. Diese würden bei der späteren Erzeugung der Dummy-Variablen als gleiche Werte angesehen und nicht als unbekannt interpretiert werden. Nachdem wir die Funktion ausgeführt haben, besteht unser Datensatz jetzt noch aus 45.222 Einträgen, im Gegensatz zu den Vorherigen 48.842.

Zuweisen der Zielvariable

Im zweiten Teil der „setup_data“ Funktion ordnen wir über den Funktionsaufruf „set_target“ der Zielvariable die Werte 0 oder 1 zu, je nachdem, ob jemand mehr oder weniger als 50.000 US-Dollar im Jahr verdient.

def set_target(self, data):
    """ Set the target values of the target variables (0,1 for either case). """
    for i in range(len(data[self.target].unique())):
        data[self.target] = np.where(data[self.target] == data[self.target].unique()[i], i, data[self.target])
    return data[self.target].astype("int")

Kategorische Werte mit Dummy-Variablen ersetzen

Bevor wir nun damit beginnen, eine Klassifizierung der Daten vorzunehmen, müssen wir zunächst dafür sorgen, dass unser Modell in der Lage ist, mit kategorischen Werten umzugehen. Dafür erzeugen wir aus allen kategorischen Variablen sog. Dummy-Variablen über das one-hot encoding Verfahren. Dabei erhält jede mögliche Belegung einer kategorischen Variable eine eigene Variable, sodass anstelle einer einzelnen Variable, die unterschiedliche Werte annehmen kann, viele Variablen existieren, die jeweils nur den Wert 0 oder 1 annehmen können und die jeweils eine kategorische Belegung der ersetzen Variable repräsentieren.

Motivation

Ein Beispiel: Wir haben ein Objekt vom Typ “datum” mit dem Feature ‘wochentag = {‚Montag‘, ‚Dienstag‘, ‚Mittwoch‘, …}’. Nach der Erzeugung der Dummy-Variablen gibt es das Feature ‘wochentag’ nicht mehr. Stattdessen stellt jede mögliche Belegung ein eigenes Feature dar. Diese sind in unserem Beispiel: wochentag_dienstag, …, wochentag_sonntag. Je nachdem, welchen Wochentag das Feature vor der Erzeugung besaß, wird diese Variable auf 1 und die Restlichen auf 0 gesetzt.

Der aufmerksame Leser fragt sich an dieser Stelle bestimmt, wieso das Feature wochentag_montag nicht existiert. Der einfache Grund für das Auslassen liegt darin, dass sich aus der negativen Belegung der anderen Features implizit schließen lässt, dass ein Objekt den Wert wochentag_montag besitzt. Ein weiterer Vorteil besteht darin, dass eine zu starke Abhängigkeit, Multikollinearität, der einzelnen Variablen vermieden wird. Diese könnte sich negativ auf das Ergebnis auswirken, da die starke Abhängigkeit es erschweren kann, den genauen Effekt einer bestimmten Variable in einem Modell zu bestimmen. Die Erzeugung der Dummy-Variablen ist deshalb notwendig, da wie bereits erwähnt, ein Modell kein Wissen über einen Wochentag hat und wie es diesen interpretieren soll. Nach der Erzeugung der Dummyvariablen spielt dies auch keine Rolle mehr, da der Algorithmus nur noch unterscheidet, ob das Feature eines Objekt über den Wert 0 oder 1 verfügt. Dadurch wird ein Vergleich der einzelnen Objekte mit den jeweiligen Features möglich.

Umsetzung

Im letzten Teil unserer Funktion „setup_data“ haben wir die Erzeugung der Dummys über den Aufruf der Funktion „get_dummies“ wie folgt realisiert:

def get_dummies(self, data, categorical_features):
    """ Get the dummies of the categorical features for the given data. """
    for feature in self.categorical_features:
        # create dummyvariable with pd.get_dummies and drop all categorical variables with dataframe.drop
        data = data.join(pd.get_dummies(data[feature], prefix=feature, drop_first=True)).drop(feature, axis=1)
    return data

Wir erzeugen eine Schleife, die alle kategorischen Variablen des Datensatzes durchläuft. Bei jedem Durchlauf hängen wir dem Datensatz alle Dummyvariablen der jeweiligen kategorischen Variable mit Hilfe der Pandas Funktion „get_dummies“ an. Anschließend entfernen wir diese kategorische Variable. Nach Abschluss der Schleifenanweisung enthält unser Datensatz keine kategorischen Variablen mehr. Stattdessen besitzt er die jeweiligen Dummyvariablen.

So erhalten wir aus den ursprünglichen Features:

          age   workclass
Person1   39    Local-gov
Person2   50    Federal-gov

Die Folgenden:

          age   workclass_Federal-gov  workclass_Local-gov  workclass_Never-worked
Person1   39    0                      1                    0
Person2   50    1                      0                    0

Hierbei wird der Grund für das zwischenzeitliche Zusammenfügen der beiden Datensätze nochmals deutlich: Falls z.B. der Wert “Local-gov” in nur einem der Datensätze vorhanden ist, verfügen bei der Erzeugung der Dummyvariablen die entstehenden Datensätze über verschiedene Dimensionalitäten, da in dem anderen Datensatz die gesamte Spalte fehlt.

Beispiel: Wenn das Modell beispielsweise einen großen Zusammenhang zwischen “Local-gov” und einem Einkommen von über 50.000 USD herstellt, verschiebt sich dieser Zusammenhang in dem anderen Datensatz zu dem Feature, dass den Platz von “Local-gov” belegt. Daraus resultiert wahrscheinlich ein falsches Ergebnis aber in jedem Fall ein falscher Zusammenhang.

Im letzten Teil der “setup_data” Funktion teilen wir die Datensätze wieder in einen Trainings- und Testdatensatz auf.

self.x_train = fulldata[0:len(traindata)]
self.x_test = fulldata[len(traindata):len(fulldata)]

Im zweiten Teil gehen wir darauf ein, wie wir die aufbereiteten Daten auf verschiedene Klassifikatoren anwenden und anschließend die Ergebnisse vergleichen und evaluieren können.