Anomalieerkennung im Machine Learning: Ein technischer Überblick

Einleitung

Eine Kreditkarte, die das ganze Jahr über in Istanbul benutzt wurde, bezahlt plötzlich innerhalb von zehn Minuten drei Laptops in einem anderen Land. Ein Lager in einem Fabrikmotor beginnt mit einer leicht veränderten Frequenz zu vibrieren. Ein Server, der normalerweise ein paar Megabyte pro Stunde verschickt, sendet auf einmal Gigabytes. Jedes Mal ist das interessante Ereignis das, was nicht zum Rest passt, und es automatisch zu finden, nennt man Anomalieerkennung.

Eingesetzt wird sie bei der Betrugserkennung, in der IT-Sicherheit, in der Qualitätskontrolle und in der vorausschauenden Wartung. Was sie von gewöhnlicher Klassifikation unterscheidet, ist das Ungleichgewicht: Anomalien sind selten, oft deutlich unter einem Prozent der Daten, und häufig gibt es überhaupt keine gelabelten Beispiele. Das erfordert eigene Methoden. Dieser Überblick stützt sich teilweise auf Andriy Burkovs The Hundred-Page Machine Learning Book.

Was als Anomalie gilt

Formal sei X ⊆ ℝd ein Datensatz aus N unabhängigen Beobachtungen x1, x2, …, xN. Eine Anomalie ist ein Element xi ∈ X, das deutlich von der Verteilung der normalen Daten abweicht. In der Praxis gibt es drei Arten:

• Punktanomalien: einzelne Beobachtungen, die weit von allem anderen entfernt liegen, wie der Kauf der drei Laptops. Sie werden meist mit Wahrscheinlichkeitsverteilungen oder Abstandsmaßen erkannt.
• Kontextuelle Anomalien: Werte, die nur im Zusammenhang seltsam sind. 30 °C sind im Juli normal und im Januar alarmierend, also müssen Zeit oder Ort Teil des Modells sein.
• Kollektive Anomalien: eine Gruppe von Beobachtungen, die zusammen ungewöhnlich ist, obwohl jede für sich unauffällig wirkt, zum Beispiel eine langsame, gleichmäßige Folge kleiner Überweisungen.

Das Problem mathematisch formuliert

Gegeben ein Datensatz X, soll folgende Funktion gelernt werden:

f: X → {0, 1}
f(x) = 1, wenn x eine Anomalie ist
       0, sonst

Die meisten Methoden lernen eigentlich einen kontinuierlichen Anomalie-Score und wenden dann einen Schwellenwert an. Wie dieser Score gelernt wird, hängt davon ab, wie viele gelabelte Daten vorhanden sind. Daraus ergeben sich drei Familien: überwachte, unüberwachte und halbüberwachte Verfahren.

1. Überwachte Anomalieerkennung

Liegen gelabelte Trainingsdaten {(xi, yi)}i=1N vor, wobei yi ∈ {0, 1} angibt, ob ein Element anomal ist, wird Anomalieerkennung zu einem Klassifikationsproblem. Logistische Regression, Entscheidungsbäume, Gradient-Boosting-Bäume und neuronale Netze funktionieren alle. Die logistische Regression etwa sagt Folgendes vorher:

ŷ = σ(wᵀx + b)
σ(z) = 1 / (1 + e⁻ᶻ)

Der Haken sind die Daten. Man braucht genügend gelabelte Anomalien zum Lernen, was selten realistisch ist, und bei starkem Ungleichgewicht kommt ein Modell auf 99 % Genauigkeit, indem es einfach nie etwas meldet. Außerdem erkennen überwachte Verfahren nur die Arten von Anomalien, die sie schon gesehen haben.

2. Unüberwachte Anomalieerkennung

Unüberwachte Verfahren kommen ganz ohne Labels aus und suchen nach Punkten, die nicht zur Struktur der Daten passen.

Statistische Verfahren

Man modelliert die Verteilung der normalen Daten mit einer Wahrscheinlichkeitsdichte p(x) und behandelt alles, was unwahrscheinlich genug ist, als Anomalie:

x ist anomal, wenn p(x) < ε

Sind die Daten näherungsweise normalverteilt mit Mittelwert μ und Kovarianz Σ, ist die Mahalanobis-Distanz ein naheliegender Score. Anders als der einfache euklidische Abstand berücksichtigt sie die Skala jedes Merkmals und die Korrelationen zwischen den Merkmalen:

dM(x) = √((x − μ)ᵀ Σ⁻¹ (x − μ))

Clustering-basierte Verfahren

Algorithmen wie k-Means teilen die Daten in Cluster ein, und Punkte, die von allen Clusterzentren μk weit entfernt sind, gelten als verdächtig:

s(x) = mink ‖x − μk‖₂

DBSCAN geht noch einen Schritt weiter und markiert Punkte, die zu keiner dichten Region gehören, direkt als Rauschen.

Dichtebasierte Verfahren

Der Local Outlier Factor (LOF) vergleicht die lokale Dichte um einen Punkt mit der Dichte um seine k nächsten Nachbarn Nk(x):

LOF(x) = (1 / |Nk(x)|) · Σy ∈ Nk(x) lrd(y) / lrd(x)

Dabei ist lrd die lokale Erreichbarkeitsdichte. Ein Wert nahe 1 bedeutet, dass der Punkt ungefähr so dicht umgeben ist wie seine Nachbarn. Werte deutlich über 1 bedeuten, dass er in einer viel dünner besiedelten Gegend liegt als sie.

Isolationsbasierte Verfahren

Isolation Forest geht einen anderen Weg. Das Verfahren baut Zufallsbäume, die die Daten an zufälligen Merkmalen und zufälligen Werten aufteilen. Anomalien sind wenige und anders, deshalb sind sie schon nach wenigen Teilungen isoliert, während normale Punkte viele brauchen. Die durchschnittliche Pfadlänge über alle Bäume wird zum Anomalie-Score. Das Verfahren ist schnell und kommt gut mit hochdimensionalen Tabellendaten zurecht, weshalb es oft als Erstes ausprobiert wird.

3. Halbüberwachte Anomalieerkennung

Oft hat man jede Menge Daten, von denen man weiß, dass sie normal sind, und fast keine Beispiele für Anomalien. Halbüberwachte Verfahren trainieren nur auf den normalen Daten und melden alles, was ihnen nicht ähnelt.

Autoencoder

Ein Autoencoder ist ein neuronales Netz, das lernt, seine Eingabe zu komprimieren und anschließend zu rekonstruieren. Wird es nur mit normalen Daten trainiert, rekonstruiert es normale Muster sehr gut. Ist der Rekonstruktionsfehler ‖x − x̂‖₂ hoch, ähnelt die Eingabe nichts, was das Netz kennt, und x ist wahrscheinlich eine Anomalie.

One-Class-SVM

Eine One-Class-Support-Vector-Machine bildet die Daten über eine Abbildung φ in einen hochdimensionalen Merkmalsraum ab und lernt eine Grenze, die die normalen Daten mit möglichst großem Abstand vom Ursprung trennt. Neue Punkte auf der falschen Seite dieser Grenze gelten als Anomalien:

f(x) = sign(wᵀφ(x) − ρ)

Umsetzung in der Praxis

1. Daten vorbereiten. Merkmale normalisieren, fehlende Werte behandeln und nur die Merkmale behalten, die wirklich ein Signal tragen. Viele abstandsbasierte Verfahren versagen, wenn ein Merkmal in Tausenden und ein anderes in Bruchteilen gemessen wird.
2. Verfahren wählen. Die Daten entscheiden lassen: Gibt es Labels, wie viele Dimensionen, wie groß ist der Datensatz, spielt die Zeit eine Rolle?
3. Ehrlich bewerten. Bei unausgewogenen Daten sagt die Genauigkeit fast nichts aus. Precision-Recall-Kurven sind meist aussagekräftiger als ROC-Kurven, weil sie zeigen, wie viele deiner Alarme echt sind.
4. Einführen und überwachen. Was als normal gilt, ändert sich mit der Zeit. Das Modell muss also regelmäßig nachtrainiert und seine Alarmrate im Auge behalten werden.

Was es schwierig macht

• Unausgewogene Daten. Oversampling, Undersampling und kostensensitives Lernen helfen dabei, dass das Modell die seltene Klasse nicht einfach ignoriert.
• Concept Drift. Kundenverhalten, Netzwerkverkehr und Maschinenverschleiß verändern sich. Ein Modell, das nie aktualisiert wird, hält normales Verhalten nach und nach für einen Alarm, oder umgekehrt.
• Fehlalarme. Ein Alarmsystem, das ständig falschen Alarm schlägt, wird irgendwann ignoriert. Sorgfältig gewählte Schwellenwerte, Ensembles aus mehreren Verfahren und eine menschliche Prüfung für Grenzfälle halten die Zahl der Alarme beherrschbar.

In der Praxis ist die Wahl des Verfahrens meist weniger wichtig, als man denkt. Die meiste Arbeit steckt darin, zu verstehen, was „normal“ für die eigenen Daten bedeutet, und zu entscheiden, wie viele Fehlalarme die Menschen, die sie bekommen, verkraften können.