Lokaler Ausreißerfaktor

Einfache Sprache

Ausreißer 1 sind Objekte die in Regionen mit niedriger Dichte an Objekten. Wir schauen also wie viele Nachbarn eine Objekte in seiner Nähe hat. Daraus lässt sich dann ein Lokaler Ausreißerfaktor (LOF) berechnen der die eine relative Dichte darstellt. Der LOF berechnet sich aus der durchschnittlichen Erreichbarkeitsdichte der Nachbarn dividiert durch die eigene Ereichbarkeitsdichte.

Def. k-Distanz

Sei $A$ ein Objekt und $d$ eine Distanzfunktion. Dann ist die $\text{k-Distanz}(A)$ die Distanz, gegeben durch $d$, von $A$ zu dem $k$-nächsten Nachbar $\text{kNN}$.

Def. Erreichbarkeitsdistanz

Sei $A$,$B$ Objekte und $d$ eine Distanzfunktion. Dann ist die Erreichbarkeitsdistanz oder reachability distance definiert durch

$$\text{Erreichbarkeitsdistanz}_k(A,B) = \max\left\{\text{k-Distanz}(A), d(A,B)\right\}$$

die Distanz von $A$ zu einem $k$-nächstem Nachbar.

Die Erreichbarkeitsdistanz ist entweder die Distanz von $A$ nach $B$

Def. lokale Erreichbarkeitsdichte

Sei $A$ ein Objekt, $d$ eine Distanzfunktion und $\text{kNN}$ der $k$-nächsten Nachbar. Dann ist die lokale Erreichbarkeitsdichte oder local reachability density (lrd) definiert durch

$$\text{lrd}_k(A) = \frac{|\text{kNN}(A)|}{\sum_{O\in\text{kNN}(A)}\text{Erreichbarkeitsdistanz}_k(A,O)}$$

die Distanz von $A$ zu einem $k$-nächstem Nachbar.

Die lokale Erreichbarkeitsdichte ist die durchschnittliche Erreichbarkeitsdistanz eines Objektes von seinen Nachbarn.

Def. Lokaler Ausreißerfaktor

Sei $A$ ein Objekt und $\text{kNN}$ der $k$-nächsten Nachbar. Dann ist die Lokaler Ausreißerfaktor oder local outlier factor (LOF) definiert durch

$$\text{LOF}_k(A) = \frac{\sum_{O\in\text{kNN}(A)}\text{lrd}_k(O)}{|\text{kNN}(A)|\cdot \text{lrd}_k(A)}\;.$$

Interpretation des LOF

Gegeben ein Objekt $A$ und ein $k\in\mathbb N$. Dann deutet $\text{LOF}_k(A)\approx 1$ auf einen Cluster-Zugehörigkeit. Ist der $\text{LOF}_k(A)\gg 1$ dann handel es sich wahrscheinlich um einen Ausreißer.