Grundlagen Statistik & Algorithmen, Teil 7 So deckt der Local Outlier Factor Anomalien auf

Um Trends zu erkennen, wird oft die Clusteranalyse herangezogen. Der k-Means-Algorithmus etwa zeigt an, wo sich Analyseergebnisse in einer Normalverteilung ballen. Für manche Zwecke ist es aber aufschlussreicher, Ausreißer zu untersuchen, denn sie bilden die Antithese zum „Normalen“, etwa im Betrugswesen. Der Local-Outlier-Factor-Algorithmus (LOF) ist in der Lage, den Abstand von Ausreißern zu ihren Nachbarn zu berechnen und deckt so Anomalien auf.

Anbieter zum Thema

Bissantz & Company GmbH

Fujitsu Technology Solutions GmbH

QUNIS GmbH

Bei der Clusteranalyse geht es darum, Gruppen von Objekten zu identifizieren, die sich auf eine gewisse Art ähnlicher sind als andere Gruppen. Oft handelt es sich dabei um Häufungen im Datenraum, woher der Begriff Cluster kommt.

In der Ausreißersuche werden Datenobjekte gesucht, die inkonsistent zu dem Rest der Daten sind, beispielsweise indem sie ungewöhnliche Attributswerte haben oder von einem generellen Trend abweichen. In der Statistik spricht man von einem Ausreißer, wenn ein Messwert oder Befund nicht in eine erwartete Messreihe passt oder allgemein nicht den Erwartungen entspricht. Die „Erwartung“ wird meistens als Streuungsbereich um den Erwartungswert herum definiert, in dem die meisten aller Messwerte zu liegen kommen, z. B. der Quartilabstand Q₇₅ – Q₂₅. Werte, die weiter als das 1,5-Fache des Quartilabstandes außerhalb dieses Intervalls liegen, werden – meist recht willkürlich – als Ausreißer bezeichnet.

Der Algorithmus „Local Outlier Factor“, der hier näher vorgestellt wird, sucht beispielsweise Objekte, die eine von ihren Nachbarn deutlich abweichende Dichte aufweisen, man spricht hier von „dichtebasierter Ausreißer-Erkennung“. Identifizierte Ausreißer werden oft anschließend manuell verifiziert und aus dem Datensatz ausgeblendet, da sie die Ergebnisse anderer Verfahren verschlechtern können. In manchen Anwendungsfällen, wie der Betrugserkennung, sind aber gerade die Ausreißer die interessanten Objekte.

Der Local Outlier Factor (etwa „Lokaler Ausreißerfaktor“) wurde von Markus M. Breunig, Hans-Peter Kriegel, Raymond T. Ng und Jörg Sander im Jahr 2000 vorgeschlagen. Die Kernidee von LOF besteht darin, die Dichte eines Punktes mit den Dichten seiner Nachbarn zu vergleichen. Ein Punkt, der „dichter“ ist als seine Nachbarn, befindet sich in einem Cluster. Ein Punkt mit einer deutlich geringeren Dichte als seine Nachbarn ist hingegen ein Ausreißer.

LOF definiert die „lokale Umgebung“ eines Punktes über seine nächsten Nachbarn. Der Abstand zu diesen wird verwendet, um eine lokale Dichte zu schätzen. In einem zweiten Schritt wird der Quotient aus den lokalen Dichten seiner Nachbarn und der lokalen Dichte des Punktes selbst gebildet. Dieser Wert bewegt sich nahe an 1.0, wenn ein Punkt in einem Bereich gleichmäßiger Dichte ist. Für Objekte, die aber abgeschieden von einer solchen Fläche sind, wird der Wert deutlich größer – und kennzeichnet so Ausreißer.

Der „Local Outlier Factor“ ist also die „durchschnittliche Erreichbarkeitsdichte der Nachbarn“ dividiert durch die Erreichbarkeitsdichte des Objektes selbst. Ein Wert von etwa 1 bedeutet, dass das Objekt eine mit seinen Nachbarn vergleichbare Dichte hat (also nicht als Ausreißer bezeichnet werden kann). Ein Wert kleiner als 1 bedeutet sogar eine dichtere Region (was ein sogenannter „Inlier“ wäre), während signifikant höhere Werte als 1 einen Ausreißer kennzeichnen: LOF >> 1.

Vorteile

Im Gegensatz zu vielen globalen Verfahren zur Ausreißererkennung kann der LOF-Algorithmus mit Bereichen unterschiedlicher Dichte in demselben Datensatz umgehen. Punkte mit einer „mittleren“ Dichte in einer Umgebung mit „hoher“ Dichte werden von LOF als Ausreißer klassifiziert, während ein Punkt mit „mittlerer“ Dichte in einer „dünnen“ Umgebung explizit nicht als solcher erkannt wird.

Während die geometrische Intuition von LOF nur in niedrigdimensionalen Vektorräumen Sinn ergibt, kann das Verfahren auf beliebige Daten angewendet werden, auf denen eine „Unähnlichkeit“ definiert werden kann. Es muss sich dabei nicht um eine Distanzfunktion im strengeren mathematischen Sinne handeln. Der Algorithmus wurde erfolgreich auf verschiedensten Datensätzen eingesetzt, beispielsweise zum Erkennen von Angriffen in Computernetzwerken, wo er bessere Erkennungsraten lieferte als die Vergleichsverfahren. Das wurde 2003 in der Studie „A comparative study of anomaly detection schemes in network intrusion detection“ veröffentlicht.

Nachteile

Ein wichtiger Nachteil von LOF ist, dass die Ergebniswerte schwer zu interpretieren sind. Werte um und weniger sind sicher keine Ausreißer, aber es gibt keine klare Regel, ab welchem Wert ein Punkt ein signifikanter Ausreißer ist. In einem sehr gleichmäßigen Datensatz sind Werte von 1,1 auffällig, in einem Datensatz mit starken Dichteschwankungen kann ein Wert wie 2 noch ein ganz normaler Datenpunkt sein.

Im schlimmsten Falle treten solche Unterschiede sogar in unterschiedlichen Teilen desselben Datensatzes auf. Am besten einigen sich Anwender von vornherein auf einen Schwellenwert, der die Definition eines „Ausreißers“ festlegt.

Erweiterungen

Der Algorithmus lässt sich erweitern. Das „Feature Bagging for Outlier Detection“ wendet LOF in mehreren Projektionen an und kombiniert die Ergebnisse, um in hochdimensionalen Daten bessere Ergebnisse zu erhalten. Die Funktion „Local Outlier Probability“ (LoOP) ist eine von LOF abgeleitete Methode, die die Dichte statistisch schätzt, um weniger abhängig vom genauen Wert von k zu werden. Zusätzlich wird das Ergebnis statistisch in den Wertebereich [0,1] normalisiert, um besser interpretierbare Werte zu liefern. Und „Interpreting and Unifying Outlier Scores“ stellt eine Normalisierung für LOF und andere Verfahren vor, die die Scores statistisch in das Intervall [0,1] normalisiert, um die Benutzerfreundlichkeit des Ergebnisses zu verbessern.

Eine Referenzimplementierung des LOF-Algorithmus ist im Software-Paket ELKI verfügbar, inklusive Implementierungen von Vergleichsverfahren. Die Scikit-Webseite bietet Lernmaterial zum LOF, darunter auf der Seite mit Links zu Python-Quellcode und einem Jupyter-Notebook. Auf der Seite towardsdatascience.com stellt der Autor Phillip Wenig den LOF prägnant und anschaulich vor, der Leser muss jedoch entsprechendes Data-Science-Wissen mitbringen.

Grundlagen Statistik & Algorithmen, Teil 1

Das Problem des Handlungsreisenden und seine praktischen Anwendungen

Grundlagen Statistik & Algorithmen, Teil 2

So verfeinert das Bayes-Theorem Spam-Filter – und mehr

Grundlagen Statistik & Algorithmen, Teil 3

Speed für Mustererkennung mit dem Rete-Algorithmus

Grundlagen Statistik & Algorithmen, Teil 4

Der Monte-Carlo-Algorithmus und -Simulationen

Grundlagen Statistik & Algorithmen, Teil 5

Optimale Clusteranalyse und Segmentierung mit dem k-Means-Algorithmus

Grundlagen Statistik & Algorithmen, Teil 6

Die Ereigniszeitanalyse – wenn Anfang und Ende die Erfolgsrate bestimmen

(ID:45770883)