Zum Inhalt springen
Zurück zu den Suchergebnissen

Lokaler Ausreißerfaktor (LOF)

Eingeführt von
Breunig, M. M.; Kriegel, H.-P.; Ng, R. T.; Sander, J.
Jahr
2000
Typ
Density-based anomaly detection (unsupervised)

Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen

Schriftgröße

Was leistet sie?

Der Lokale Ausreißerfaktor (LOF) ist ein dichte-basierter, unüberwachter Algorithmus zur Anomalieerkennung, der 2000 von Breunig, Kriegel, Ng und Sander eingeführt wurde.

Er weist jedem Datenpunkt einen kontinuierlichen Ausreißer-Score zu, der quantifiziert, wie isoliert dieser Punkt relativ zu seiner lokalen Nachbarschaft ist. Dies ermöglicht die Erkennung von Anomalien, die globale Methoden übersehen, da sie sich in dichten Clustern an anderer Stelle im Raum einfügen.

Die Intuition hinter der Methode

Stellen Sie sich eine Stadtkarte vor, auf der die meisten Menschen in dichten Stadtvierteln leben. Ein Haus, das allein auf dem Land steht, ist offensichtlich isoliert. Aber LOF geht weiter: Es kann auch ein Haus kennzeichnen, das in einem mäßig dichten Vorort liegt, wenn alle seine unmittelbaren Nachbarn in einem noch dichteren Cluster gepackt sind. Anstatt zu fragen 'Ist dieser Punkt weit von allem entfernt?', fragt LOF: 'Ist die Nachbarschaft dieses Punktes viel spärlicher als die Nachbarschaften seiner eigenen Nachbarn?' Ein Punkt, dessen Nachbarn alle enger zusammenleben als der Punkt selbst, erhält einen hohen LOF-Score – ein Signal dafür, dass er ein lokaler Ausreißer ist, auch wenn er global nicht in einer leeren Region liegt.

Geschichte

LOF wurde von Markus Breunig, Hans-Peter Kriegel, Raymond Ng und Jörg Sander auf der ACM SIGMOD 2000 Konferenz eingeführt. Er adressierte eine anerkannte Einschränkung bestehender Ausreißermethoden – dass sie auf globalen Distanzschwellenwerten beruhten und daher lokale Anomalien mit normalen Punkten in weniger dichten Regionen verwechselten. Die Arbeit führte das Konzept der lokalen Erreichbarkeitsdichte und des LOF-Scores ein, der schnell zu einer Eckpfeilerreferenz in der Anomalieerkennung wurde. Seitdem wurde er durch zahlreiche Varianten erweitert, darunter LoOP (local outlier probabilities), LOCI und COF, und ist in wichtigen Machine-Learning-Bibliotheken enthalten. Die ACM SIGMOD 2000 Arbeit hat Tausende von Zitationen angesammelt und gilt als eine der grundlegenden Arbeiten im dichte-basierten Data Mining.

Wann wird sie eingesetzt?

LOF ist geeignet, wenn Anomalien in Clustern unterschiedlicher Dichte erwartet werden und wenn ein globaler Distanzschwellenwert entweder Ausreißer in spärlichen Regionen übersehen oder Punkte in legitimen, aber konsistenten spärlichen Clustern fälschlicherweise kennzeichnen würde. Er funktioniert in jedem kontinuierlichen Merkmalsraum mit einer sinnvollen Distanzmetrik und benötigt keine gelabelten Anomaliebeispiele (vollständig unüberwacht). Er eignet sich für Anwendungen wie Betrugserkennung, Netzwerkeinbruchserkennung, Qualitätskontrolle in der Fertigung und medizinische Anomalie-Screening. Die Hauptannahmen sind, dass Inlier relativ kohäsive lokale Nachbarschaften bilden und dass sinnvolle paarweise Abstände berechnet werden können. LOF erzielt die besten Ergebnisse, wenn n mindestens im Bereich von Zehnern bis niedrigen Hundertern liegt; für sehr hochdimensionale Daten (der Fluch der Dimensionalität) werden Abstände weniger diskriminierend, und eine Dimensionsreduktion oder Merkmalsauswahl ist zuerst ratsam.

Grenzen und Hinweise

  • Quadratische Zeitkomplexität in der naiven Implementierung macht sie auf großen Datensätzen ohne approximative Nachbarschaftssuche langsam.
  • Empfindlich gegenüber der Wahl von k: ein zu kleines k liefert verrauschte Scores; ein zu großes k verwischt lokale Strukturen.
  • Die Leistung verschlechtert sich in sehr hochdimensionalen Räumen aufgrund des Fluchs der Dimensionalität.
  • Skaliert nicht natürlich für Streaming- oder Online-Daten ohne Neuberechnung.
  • Bietet kein Modell, das direkt zur Bewertung neuer Punkte angewendet werden kann, ohne Zugriff auf den Trainingsdatensatz.

Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.

Stärken

  • Erkennt lokale Ausreißer in Datensätzen mit Clustern unterschiedlicher Dichte, wo globale Methoden versagen.
  • Erzeugt einen kontinuierlichen, interpretierbaren Score anstelle eines harten binären Labels, was eine flexible Schwellenwertwahl ermöglicht.
  • Vollständig unüberwacht: Keine gelabelten Anomaliedaten erforderlich.
  • Anwendbar auf jeden Merkmalsraum mit einer berechenbaren Distanzmetrik, einschließlich nicht-euklidischer Distanzen.
  • Robust gegenüber der Skalierung einzelner Merkmale, wenn Distanzen auf standardisierten Daten berechnet werden.

Anwendungen

  • Betrugserkennung bei Finanztransaktionen, bei denen betrügerische Aktivitäten lokal spärliche Muster erzeugen.
  • Netzwerkeinbruchserkennung durch Kennzeichnung von Verkehrsdatensätzen, deren lokale Nachbarschaft spärlicher ist als ihre Umgebung.
  • Qualitätskontrolle in der Fertigung zur Identifizierung defekter Artikel in sensorreichen Produktionsdaten.
  • Medizinische Anomalie-Screening – Erkennung ungewöhnlicher Patientenprofile im Vergleich zu ähnlichen Patientenkohorten.
  • Räumliche Anomalieerkennung in geografischen und Umweltdaten mit heterogener Dichte.

So funktioniert es

So funktioniert es

1

Für jeden Punkt p berechnet der Algorithmus zuerst den k-Abstand: den Abstand zum k-nächsten Nachbarn von p. Dies definiert die Reichweite der lokalen Nachbarschaft von p. Alle Punkte innerhalb dieses Abstands bilden die k-Nachbarschaft N_k(p). Die Wahl von k steuert die Skala, auf der die Lokalität bewertet wird – ein kleines k erfasst feingranulare lokale Strukturen, ein größeres k glättet diese.

Formel
k\text{-dist}(p) = \text{distance to the } k\text{-th nearest neighbor of } p
2

Der Erreichbarkeitsabstand von p zu einem Nachbarn o ist definiert als das Maximum des k-Abstands von o und des tatsächlichen euklidischen (oder einer anderen metrischen) Abstands zwischen p und o. Diese Glättung verhindert Instabilität, wenn zwei Punkte extrem nahe beieinander liegen: Sie ersetzt winzige Abstände durch den breiteren Fußabdruck der eigenen Nachbarschaft von o, was die Dichteschätzungen robuster macht.

Formel
\text{reach-dist}_k(p, o) = \max\{k\text{-dist}(o),\, d(p, o)\}
3

Die lokale Erreichbarkeitsdichte von p (lrd) ist der Kehrwert des durchschnittlichen Erreichbarkeitsabstands von p zu allen seinen k Nachbarn. Ein Punkt, der von dicht gepackten Nachbarn umgeben ist, hat einen kleinen durchschnittlichen Erreichbarkeitsabstand und daher eine hohe lrd. Ein Punkt in einer spärlichen Region hat einen großen durchschnittlichen Erreichbarkeitsabstand und eine niedrige lrd.

Formel
\text{lrd}_k(p) = \left(\frac{\sum_{o \in N_k(p)} \text{reach-dist}_k(p,o)}{|N_k(p)|}\right)^{-1}
4

Der LOF-Score von p ist das durchschnittliche Verhältnis der lrd-Werte seiner Nachbarn zu p's eigener lrd. Wenn p's Nachbarn alle eine erheblich höhere lrd haben als p selbst – was bedeutet, dass sie in dichteren Teilregionen leben –, übersteigt das Verhältnis 1, was darauf hindeutet, dass p ein lokaler Ausreißer ist. Ein Score nahe 1 deutet darauf hin, dass p ungefähr die gleiche Dichte wie seine Umgebung hat. Scores, die deutlich größer als 1 sind, kennzeichnen zunehmend anomale Punkte. Dieser lokalitätsbewusste Vergleich unterscheidet LOF von reinen Distanzmethoden.

Formel
\text{LOF}_k(p) = \frac{\sum_{o \in N_k(p)} \frac{\text{lrd}_k(o)}{\text{lrd}_k(p)}}{|N_k(p)|}

Häufige Fallstricke

  • Vergessen, Merkmale vor der Berechnung von Distanzen zu standardisieren oder zu normalisieren, wodurch Merkmale mit hoher Varianz dominieren.
  • Verwendung eines einzelnen k-Wertes ohne Sensitivitätsanalyse; bewährte Praxis ist die Auswertung mehrerer k-Werte.
  • Behandlung des LOF-Scores als Wahrscheinlichkeit – es ist ein relatives Maß ohne feste probabilistische Interpretation.
  • Ignorieren des Fluchs der Dimensionalität in hochdimensionalen Daten und Erwartung, dass LOF ohne vorherige Dimensionsreduktion funktioniert.
  • Festlegen eines willkürlichen LOF-Schwellenwerts (z. B. Score > 1,5) ohne Inspektion der Score-Verteilung für den spezifischen Datensatz.

Häufig gestellte Fragen

Wie wähle ich den richtigen Wert für k?

Es gibt kein universell optimales k. Übliche Praxis ist die Auswertung einer Reihe von Werten – typischerweise 5 bis 50 – und die Inspektion, wie sich die Score-Verteilung und die gekennzeichneten Ausreißer ändern. Eine Sensitivitätsanalyse über k-Werte hinweg gibt die Gewissheit, dass erkannte Anomalien robust gegenüber der Wahl sind. Domänenwissen über die minimal erwartete Clustergröße kann ebenfalls die untere Grenze leiten.

Was bedeutet ein LOF-Score von 1 im Vergleich zu 3?

Ein Score nahe 1 bedeutet, dass der Punkt ungefähr die gleiche lokale Dichte wie seine Nachbarn hat und als Inlier betrachtet wird. Ein Score, der signifikant größer als 1 ist – oft interpretiert als über 1,5 oder 2, je nach Datensatz –, zeigt an, dass die Nachbarschaft des Punktes spärlicher ist als die Nachbarschaften seiner Nachbarn. Es gibt keinen universellen Grenzwert; der Schwellenwert sollte durch Inspektion der Verteilung der LOF-Scores für den spezifischen Datensatz gewählt werden.

Kann LOF neue, ungesehene Punkte ohne erneutes Training bewerten?

LOF ist eine transdutive Methode: Sie erfordert die Anwesenheit des Trainingsdatensatzes, um Nachbarschaften und Dichten für jeden neuen Punkt zu berechnen. Um neue Beobachtungen zu bewerten, muss der Trainingsdatensatz beibehalten und jeder neue Punkt eingefügt werden, um seine k-Nachbarschaft gegen gespeicherte Trainingspunkte neu zu berechnen. Einige Implementierungen bieten diese Funktionalität, aber sie unterscheidet sich grundlegend von parametrischen Modellen, die eine kompakte Scoring-Funktion lernen.

Wie vergleicht sich LOF mit Isolation Forest für die Anomalieerkennung?

LOF verwendet Dichteschätzung basierend auf lokalen Nachbarschaften und ist stärker, wenn Anomalien sich in lokal spärlichen Regionen eines heterogenen Raumes gruppieren. Isolation Forest verwendet zufällige Partitionierung und ist tendenziell schneller und besser skalierbar für große Datensätze. Für hochdimensionale oder sehr große Datensätze wird oft Isolation Forest bevorzugt; für moderat dimensionale Daten mit Dichteunterschieden bietet LOF häufig eine feinere Diskriminierung.

Verwandte Methoden

Quellen

  1. Breunig, M. M., Kriegel, H.-P., Ng, R. T., & Sander, J. (2000). LOF: Identifying density-based local outliers. Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, 93–104.

    DOI-Referenz öffnen
    Kopiert.
  2. Aggarwal, C. C. (2017). Outlier Analysis (2nd ed., Ch. 4). Springer.

    ISBN: 978-3-319-47577-6
    Kopiert.
  3. Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed., Ch. 14). Springer.

    ISBN: 978-0-387-84857-0
    Kopiert.