imported>Boehm: fix

2025-12-19T07:57:50Z

fix

Neue Seite

Der '''Local Outlier Factor''' ('''LOF''', etwa „Lokaler Ausreißerfaktor“) ist ein [[Algorithmus]] zur Erkennung von dichtebasierten [[Ausreißer]]n, der von Markus M. Breunig, [[Hans-Peter Kriegel]], Raymond T. Ng und [[Jörg Sander (Informatiker)|Jörg Sander]] im Jahr 2000 vorgeschlagen wurde.<ref>{{Literatur
| DOI = 10.1145/335191.335388
| Titel = LOF: Identifying Density-based Local Outliers
| Jahr = 2000
| Autor = M. M. Breunig, [[Hans-Peter Kriegel]], R.T. Ng, J. Sander
| Sammelwerk = ACM SIGMOD Record
| Nummer = 29
| Seiten = 93
| Online = [http://www.dbs.ifi.lmu.de/Publikationen/Papers/LOF.pdf Online] PDF
}}</ref>
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 hat viele Konzepte gemeinsam mit den [[Clusteranalyse]]-Algorithmen [[DBSCAN]] und [[OPTICS]].

== Grundprinzip ==
[[Datei:LOF-idea.svg|mini|rechts|250px|Kernidee von LOF: die lokale Dichte eines Punktes mit der seiner Nachbarn vergleichen.]]
LOF definiert die „lokale Umgebung“ eines Punktes über seine <math>k</math> 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 <math>1{,}0</math> 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.

== Formal ==
Die <math>\text{k-Distanz}(A)</math> ist die Distanz des Objektes <math>A</math> zu seinem ''k''-nächsten Nachbarn. Diese Menge kann gegebenenfalls mehr als ''k'' Objekte enthalten, wenn es mehrere Objekte mit dem gleichen Abstand gibt. Wir bezeichnen diese „''k''-Nachbarschaft“ hier mit <math>N_k(A)</math>.

[[Datei:Reachability-distance.svg|mini|rechts|250px|Illustration der Erreichbarkeitsdistanz. Objekte ''B'' und ''C'' haben die gleiche Erreichbarkeitsdistanz (k=3), während ''D'' kein ''k''-nächster Nachbar ist]]

Basierend auf dieser Distanz wird die „Erreichbarkeitsdistanz“ definiert:


:<math>\text{Erreichbarkeitsdistanz}_k(A,B) = \max\{\text{k-Distanz}(B), d(A,B)\}</math>

Die ''Erreichbarkeitsdistanz'' eines Objektes <math>A</math> ''von'' <math>B</math> ist also entweder der wahre Abstand, jedoch mindestens die <math>\text{k-Distanz}</math> von <math>B</math>.
Objekte die zu den ''k''-nächsten Nachbarn von <math>B</math> gehören werden also als gleich weit entfernt betrachtet. Die Motivation für diese Distanzdefinition ist es, stabilere Ergebnisse zu bekommen. (Es handelt sich hierbei aber nicht mehr um eine [[Distanzfunktion]] im mathematischen Sinne, da sie nicht symmetrisch ist.)

Die ''lokale Erreichbarkeitsdichte'' („''local reachability density''“, „''lrd''“) eines Objektes <math>A</math> wird definiert als

:<math>\operatorname{lrd}_k(A) := 1/\left(\frac{\sum_{B\in N_k(A)}\text{Erreichbarkeits-Distanz}_k(A, B)}{|N_k(A)|}\right)</math>

Diese Dichte ist also der Kehrwert der durchschnittlichen Erreichbarkeitsdistanz des Objektes <math>A</math> ''von'' seinen Nachbarn, nicht andersherum die durchschnittliche Erreichbarkeitsdistanz der Nachbarn von <math>A</math>, was definitionsgemäß <math>\text{k-Distanz}(A)</math> wäre. Bei <math>k+1</math> Duplikaten in einem Datensatz wird die Erreichbarkeitsdichte dieser Objekte unendlich.

Die lokale Erreichbarkeitsdichte wird jetzt mit denen der Nachbarn verglichen:

:<math>
\text{LOF}_k(A):=\frac{\sum_{B\in N_k(A)}\frac{\operatorname{lrd}(B)}{\operatorname{lrd}(A)}}{|N_k(A)|}
= \frac{\sum_{B\in N_k(A)}\operatorname{lrd}(B)}{|N_k(A)|} / \operatorname{lrd}(A)
</math>

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

== Vorteile ==
[[Datei:LOF.svg|mini|rechts|400px|LOF-Werte visualisiert mit [[Environment for DeveLoping KDD-Applications Supported by Index-Structures|ELKI]]. Obwohl der Cluster oben rechts eine mit den Ausreißern unten links vergleichbare Dichte hat, werden sie korrekt klassifiziert.]]

Im Gegensatz zu vielen globalen Verfahren zur Ausreißererkennung kann LOF mit Bereichen unterschiedlicher Dichte in demselben Datensatz umgehen. Punkte mit einer „mittleren“ Dichte in einer Umgebung mit „hoher“ 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 beliebigen Daten angewendet werden, auf denen eine „Unähnlichkeit“ definiert werden kann. Es muss sich dabei nicht um eine [[Distanzfunktion]] im strengeren mathematischen Sinne handeln, die [[Dreiecksungleichung]] wird beispielsweise nicht benötigt. Der Algorithmus wurde erfolgreich auf verschiedensten Datensätzen eingesetzt, beispielsweise zum Erkennen von Angriffen in [[Computernetzwerk]]en, wo er bessere Erkennungsraten lieferte als die Vergleichsverfahren.<ref>{{Literatur | Autor=Ar Lazarevic, Aysel Ozgur, Levent Ertoz, Jaideep Srivastava, Vipin Kumar | Titel=A comparative study of anomaly detection schemes in network intrusion detection | Jahr=2003 | Sammelwerk=Proc. 3rd SIAM International Conference on Data Mining | Online=[http://www.siam.org/proceedings/datamining/2003/dm03_03LazarevicA.pdf Online] PDF | Seiten=25-36 }} {{Webarchiv|url=http://www.siam.org/proceedings/datamining/2003/dm03_03LazarevicA.pdf |wayback=20130717233143 |text=Online |archiv-bot=2019-04-28 04:15:03 InternetArchiveBot }}</ref>

== Nachteile ==
Ein wichtiger Nachteil von LOF ist, dass die Ergebniswerte schwer zu interpretieren sind. Werte um <math>1</math> 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 <math>1{,}1</math> auffällig, in einem Datensatz mit starken Dichteschwankungen kann ein Wert wie <math>2</math> noch ein ganz normaler Datenpunkt sein. Im schlimmsten Falle treten solche Unterschiede sogar in unterschiedlichen Teilen desselben Datensatzes auf.

== Erweiterungen ==
* ''Feature Bagging for Outlier Detection''<ref>{{Literatur | DOI = 10.1145/1081870.1081891 | Titel = Feature bagging for outlier detection | Jahr = 2005 | Autor = A. Lazarevic, V. Kumar | Seiten = 157-166 | Sammelwerk = Proc. 11th ACM SIGKDD international conference on Knowledge Discovery in Data Mining}}</ref> wendet LOF in mehreren Projektionen an und kombiniert die Ergebnisse, um in hochdimensionalen Daten bessere Ergebnisse zu erhalten.
* ''Local Outlier Probability'' (LoOP)<ref>{{Literatur | DOI = 10.1145/1645953.1646195 | Titel = LoOP: Local Outlier Probabilities | Jahr = 2009 | Autor = [[Hans-Peter Kriegel]], P. Kröger, E. Schubert, A. Zimek | Seiten = 1649 | Sammelwerk = Proc. 18th ACM Conference on Information and Knowledge Management (CIKM) | Online=[http://www.dbs.ifi.lmu.de/Publikationen/Papers/LoOP1649.pdf Online] PDF}}</ref> 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 <math>[0, 1]</math> normalisiert, um besser interpretierbare Werte zu liefern.
* ''Interpreting and Unifying Outlier Scores''<ref>{{Literatur | Titel=Interpreting and Unifying Outlier Scores | Jahr=2011 | Autor=[[Hans-Peter Kriegel]], Peer Kröger, Erich Schubert, Arthur Zimek | Sammelwerk=Proc. 11th SIAM International Conference on Data Mining | Online=[http://epubs.siam.org/doi/pdf/10.1137/1.9781611972818.2 Online] PDF}}</ref> stellt eine Normalisierung für LOF und andere Verfahren vor, die die Scores statistisch in das Intervall <math>[0, 1]</math> normalisiert um die [[Benutzerfreundlichkeit]] des Ergebnisses zu verbessern.

== Verfügbarkeit ==
Eine Referenzimplementierung ist im Software-Paket [[Environment for DeveLoping KDD-Applications Supported by Index-Structures|ELKI]] verfügbar, inklusive Implementierungen von Vergleichsverfahren.

== Einzelnachweise ==
<references />

[[Kategorie:Data-Mining]]
[[Kategorie:Algorithmus]]

Local Outlier Factor - Versionsgeschichte

imported>Boehm: fix