Grundlagen Statistik & Algorithmen, Teil 7

So deckt der Local Outlier Factor Anomalien auf

| Autor / Redakteur: Michael Matzer / Nico Litzel

Kernidee von LOF ist, die lokale Dichte eines Punktes mit der seiner Nachbarn zu vergleichen-
Kernidee von LOF ist, die lokale Dichte eines Punktes mit der seiner Nachbarn zu vergleichen- (Bild: gemeinfrei / CC0)

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.

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 Q75 – Q25. 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.

Illustration der Erreichbarkeitsdistanz. Objekte B und C haben die gleiche Erreichbarkeitsdistanz (k=3), während D kein k-nächster Nachbar ist.
Illustration der Erreichbarkeitsdistanz. Objekte B und C haben die gleiche Erreichbarkeitsdistanz (k=3), während D kein k-nächster Nachbar ist. (Bild: gemeinfrei / CC0)

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 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

LOF-Werte visualisiert mit ELKI. Obwohl der Cluster oben rechts eine mit den Ausreißern unten links vergleichbare Dichte hat, werden sie korrekt klassifiziert.
LOF-Werte visualisiert mit ELKI. Obwohl der Cluster oben rechts eine mit den Ausreißern unten links vergleichbare Dichte hat, werden sie korrekt klassifiziert. (Bild: gemeinfrei / CC0)

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 auffällig, in einem Datensatz mit starken Dichteschwankungen kann ein Wert wie 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

Ergebnis einer Clusteranalyse mit Normalverteilungen.
Ergebnis einer Clusteranalyse mit Normalverteilungen. (Bild: Chire / BY-SA 3.0)

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.

Das Problem des Handlungsreisenden und seine praktischen Anwendungen

Grundlagen Statistik & Algorithmen, Teil 1

Das Problem des Handlungsreisenden und seine praktischen Anwendungen

18.06.18 - Ob beim Design von künstlichen Neuronalen Netzwerken fürs Deep Learning, in der Logistik oder beim Layout von Leiterplatten – überall stößt man auf das mathematisch lösbare Problem des Handlungsreisenden: Wie lässt sich eine Tour mit mehreren Stationen auf dem kürzesten Weg und mit dem geringsten Aufwand bewältigen? lesen

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

Grundlagen Statistik & Algorithmen, Teil 2

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

25.06.18 - Mithilfe des Satzes von Bayes lassen sich Parameter schätzen und Hypothesen induktiv testen. In einem Spamfilter können so wahrscheinliche Spam-Mails ermittelt werden. Und aus den Symptomen, die bei einem bekannten Test auftreten, lassen sich wahrscheinliche Krankheitsursachen aufspüren. Der Satz von Bayes, der bedingte Wahrscheinlichkeiten beschreibt, ist also ein nahezu universell nutzbares Werkzeug der Statistik. lesen

Speed für Mustererkennung mit dem Rete-Algorithmus

Grundlagen Statistik & Algorithmen, Teil 3

Speed für Mustererkennung mit dem Rete-Algorithmus

02.07.18 - Geschäftsregeln halten zahlreiche Unternehmensprozesse am Laufen, deshalb können sie mitunter sehr umfangreich werden. Der Umfang macht ihre Ausführung zeitaufwendig, weshalb jede Methode, sie zu beschleunigen, willkommen ist. Der Rete-Algorithmus beschleunigte 1979 die damals bestehenden Systeme für die Verarbeitung von Business Rules um den Faktor 3.000. Er ist bis heute die Grundlage zahlreicher Expertensysteme, etwa in der Mustererkennung. lesen

Der Monte-Carlo-Algorithmus und -Simulationen

Grundlagen Statistik & Algorithmen, Teil 4

Der Monte-Carlo-Algorithmus und -Simulationen

10.09.18 - Eine Reihe von Algorithmen dient der Suche von Lösungen, ohne vorher die Antwort zu kennen, und von Entscheidungen, die nach „wahrscheinlich richtig oder falsch“ beurteilt werden. Das ist sinnvoll für das Risiko-Management, aber auch für die Nutzung von Supercomputern. Ein solcher Algorithmus ist der Monte-Carlo-Algorithmus und die darauf basierenden Simulationen lesen

Optimale Clusteranalyse und Segmentierung mit dem k-Means-Algorithmus

Grundlagen Statistik & Algorithmen, Teil 5

Optimale Clusteranalyse und Segmentierung mit dem k-Means-Algorithmus

19.11.18 - Der k-Means-Algorithmus ist ein Rechenverfahren, das sich für die Gruppierung von Objekten, die sogenannte Clusteranalyse, einsetzen lässt. Dank der effizienten Berechnung der Clusterzentren und dem geringen Speicherbedarf eignet sich der Algorithmus sehr gut für die Analyse großer Datenmengen, wie sie im Big-Data-Umfeld üblich sind, so etwa in der Bildverarbeitung und in der Kundensegmentierung. lesen

Die Ereigniszeitanalyse – wenn Anfang und Ende die Erfolgsrate bestimmen

Grundlagen Statistik & Algorithmen, Teil 6

Die Ereigniszeitanalyse – wenn Anfang und Ende die Erfolgsrate bestimmen

04.02.19 - Die Ereigniszeitanalyse bzw. Survival Analysis umfasst eine Reihe von Werkzeugen der Statistik, mit denen die Zeit bis zum Eintritt eines bestimmten Ereignisses zwischen Gruppen verglichen wird. Auf diese Weise will man die Wirkung von prognostischen Faktoren, einer medizinischen Behandlung oder von schädlichen Einflüssen abschätzen. Bei dem Ereignis kann es sich um etwas so Endgültiges wie den Tod handeln, aber auch um den Verlust einer Arbeitsstelle, eine Scheidung oder einen Beginn, etwa um eine Geburt oder einen Heilungseintritt. lesen

Kommentare werden geladen....

Kommentar zu diesem Artikel abgeben

Der Kommentar wird durch einen Redakteur geprüft und in Kürze freigeschaltet.

Anonym mitdiskutieren oder einloggen Anmelden

Avatar
Zur Wahrung unserer Interessen speichern wir zusätzlich zu den o.g. Informationen die IP-Adresse. Dies dient ausschließlich dem Zweck, dass Sie als Urheber des Kommentars identifiziert werden können. Rechtliche Grundlage ist die Wahrung berechtigter Interessen gem. Art 6 Abs 1 lit. f) DSGVO.
  1. Avatar
    Avatar
    Bearbeitet von am
    Bearbeitet von am
    1. Avatar
      Avatar
      Bearbeitet von am
      Bearbeitet von am

Kommentare werden geladen....

Kommentar melden

Melden Sie diesen Kommentar, wenn dieser nicht den Richtlinien entspricht.

Kommentar Freigeben

Der untenstehende Text wird an den Kommentator gesendet, falls dieser eine Email-hinterlegt hat.

Freigabe entfernen

Der untenstehende Text wird an den Kommentator gesendet, falls dieser eine Email-hinterlegt hat.

copyright

Dieser Beitrag ist urheberrechtlich geschützt. Sie wollen ihn für Ihre Zwecke verwenden? Infos finden Sie unter www.mycontentfactory.de (ID: 45770883 / Analytics)