Przejdź do treści
Wróć do wyników wyszukiwania

Lokalny Wskaźnik Wartości Odstających (Local Outlier Factor - LOF)

Autor metody
Breunig, M. M.; Kriegel, H.-P.; Ng, R. T.; Sander, J.
Rok
2000
Typ
Density-based anomaly detection (unsupervised)

Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku

Rozmiar czcionki

Do czego służy?

Local Outlier Factor (LOF) to algorytm detekcji anomalii oparty na gęstości, działający w trybie nienadzorowanym, wprowadzony przez Breuniga, Kriegela, Ng i Sandera w 2000 roku.

Przypisuje on każdemu punktowi danych ciągły wynik anomalii, który kwantyfikuje, jak bardzo punkt jest odizolowany względem swojego lokalnego sąsiedztwa. Umożliwia to wykrywanie anomalii, które umykają metodom globalnym, ponieważ wtapiają się one w gęste klastry w innych miejscach przestrzeni.

Intuicja stojąca za metodą

Wyobraźmy sobie mapę miasta, gdzie większość ludzi mieszka w gęsto zaludnionych dzielnicach miejskich. Dom stojący samotnie na wsi jest oczywiście odizolowany. Ale LOF idzie dalej: może również oznaczyć dom, który znajduje się w umiarkowanie gęstym przedmieściu, gdy wszyscy jego bezpośredni sąsiedzi są stłoczeni w jeszcze gęstszym klastrze. Zamiast pytać „czy ten punkt jest daleko od wszystkiego?”, LOF pyta „czy sąsiedztwo tego punktu jest znacznie rzadsze niż sąsiedztwa jego własnych sąsiadów?”. Punkt, którego sąsiedzi żyją znacznie bliżej siebie niż sam punkt, otrzymuje wysoki wynik LOF – sygnalizując, że jest on lokalną anomalią, nawet jeśli globalnie nie znajduje się w pustym regionie.

Historia

LOF został wprowadzony przez Markusa Breuniga, Hansa-Petera Kriegela, Raymonda Ng i Jörga Sandera na konferencji ACM SIGMOD w 2000 roku. Odpowiadał on na rozpoznane ograniczenie istniejących metod wykrywania anomalii – poleganie na globalnych progach odległości, które myliły lokalne anomalie z normalnymi punktami w mniej gęstych regionach. Artykuł wprowadził koncepcję lokalnej gęstości osiągalności i wyniku LOF, które szybko stały się podstawowym odniesieniem w dziedzinie detekcji anomalii. Od tego czasu został rozszerzony przez liczne warianty, w tym LoOP (local outlier probabilities), LOCI i COF, i jest uwzględniany w głównych bibliotekach uczenia maszynowego. Artykuł ACM SIGMOD 2000 zgromadził tysiące cytowań i jest uważany za jedno z fundamentalnych dzieł w dziedzinie data mining opartego na gęstości.

Kiedy stosować

LOF jest odpowiedni, gdy anomalie występują w klastrach o zmiennej gęstości, a globalny próg odległości albo przeoczyłby anomalie ukryte w rzadkich regionach, albo błędnie oznaczyłby punkty w uzasadnionych, ale spójnych klastrach. Działa on w dowolnej przestrzeni cech z sensowną metryką odległości i nie wymaga oznakowanych przykładów anomalii (w pełni nienadzorowany). Nadaje się do zastosowań takich jak wykrywanie oszustw, wykrywanie intruzji w sieci, kontrola jakości produkcji i przesiewanie anomalii medycznych. Główne założenia to, że punkty nieanomalne tworzą rozsądnie spójne lokalne sąsiedztwa i że można obliczyć sensowne odległości parami. LOF działa najlepiej, gdy n wynosi co najmniej kilkadziesiąt do kilkuset; dla danych o bardzo wysokiej wymiarowości (klątwa wymiarowości) odległości stają się mniej rozróżnialne i zaleca się najpierw redukcję wymiarowości lub selekcję cech.

Ograniczenia i uwagi

  • Kwadratowa złożoność czasowa w naiwnej implementacji czyni go powolnym na dużych zbiorach danych bez indeksowania przybliżonych najbliższych sąsiadów.
  • Wrażliwy na wybór k: zbyt małe k daje zaszumione wyniki; zbyt duże k rozmywa lokalną strukturę.
  • Wydajność spada w przestrzeniach o bardzo wysokiej wymiarowości z powodu klątwy wymiarowości.
  • Nie skaluje się naturalnie do danych strumieniowych lub online bez ponownego obliczania.
  • Nie dostarcza modelu, który można bezpośrednio zastosować do oceny nowych punktów bez dostępu do zbioru treningowego.

Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.

Mocne strony

  • Wykrywa lokalne anomalie w zbiorach danych z klastrami o zmiennej gęstości, gdzie metody globalne zawodzą.
  • Generuje ciągły, interpretowalny wynik zamiast binarnej etykiety, co pozwala na elastyczny wybór progu.
  • W pełni nienadzorowany: nie są wymagane oznakowane dane anomalii.
  • Ma zastosowanie do dowolnej przestrzeni cech z obliczalną metryką odległości, w tym odległości nieeuklidesowych.
  • Odporny na skalę poszczególnych cech, gdy odległości są obliczane na znormalizowanych danych.

Zastosowania

  • Wykrywanie oszustw w transakcjach finansowych, gdzie działalność przestępcza tworzy lokalnie rzadkie wzorce.
  • Wykrywanie intruzji w sieci poprzez oznaczanie rekordów ruchu, których lokalne sąsiedztwo jest znacznie rzadsze niż otoczenie.
  • Kontrola jakości produkcji w celu identyfikacji wadliwych elementów w danych produkcyjnych bogatych w czujniki.
  • Przesiewanie anomalii medycznych – wykrywanie nietypowych profili pacjentów w porównaniu do podobnych kohort pacjentów.
  • Wykrywanie anomalii przestrzennych w danych geograficznych i środowiskowych o niejednorodnej gęstości.

Jak to działa

Jak to działa

1

Dla każdego punktu p algorytm najpierw oblicza k-odległość: odległość do k-tego najbliższego sąsiada punktu p. Definiuje to zasięg lokalnego sąsiedztwa punktu p. Wszystkie punkty w tej odległości tworzą k-sąsiedztwo N_k(p). Wybór k kontroluje skalę, w której oceniana jest lokalność – małe k wychwytuje drobnoziarnistą strukturę lokalną, większe k ją wygładza.

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

Odległość osiągalności od p do sąsiada o jest zdefiniowana jako maksimum z k-odległości punktu o i rzeczywistej odległości euklidesowej (lub innej metrycznej) między p i o. To wygładzenie zapobiega niestabilności, gdy dwa punkty są bardzo blisko siebie: zastępuje bardzo małe odległości szerszym zasięgiem własnego sąsiedztwa punktu o, czyniąc estymacje gęstości bardziej odpornymi.

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

Lokalna gęstość osiągalności punktu p (lrd) jest odwrotnością średniej odległości osiągalności od p do wszystkich jego k sąsiadów. Punkt otoczony przez ściśle upakowanych sąsiadów ma małą średnią odległość osiągalności, a co za tym idzie, wysokie lrd. Punkt w rzadkim regionie ma dużą średnią odległość osiągalności i niskie lrd.

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

Wynik LOF dla punktu p jest średnim stosunkiem wartości lrd jego sąsiadów do lrd samego punktu p. Jeśli sąsiedzi punktu p mają znacznie wyższe lrd niż sam punkt p – co oznacza, że znajdują się w gęstszych podregionach – stosunek przekracza 1, wskazując, że p jest lokalną anomalią. Wynik bliski 1 wskazuje, że p ma mniej więcej taką samą gęstość jak jego otoczenie. Wyniki znacznie większe od 1 oznaczają coraz bardziej anomalne punkty. To porównanie uwzględniające lokalność odróżnia LOF od metod opartych wyłącznie na odległości.

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

Częste pułapki

  • Zapomnienie o standaryzacji lub normalizacji cech przed obliczeniem odległości, co powoduje dominację cech o dużej wariancji.
  • Użycie pojedynczej wartości k bez analizy wrażliwości; najlepszą praktyką jest ocena kilku wartości k.
  • Traktowanie wyniku LOF jako prawdopodobieństwa – jest to miara względna bez ustalonej interpretacji probabilistycznej.
  • Ignorowanie klątwy wymiarowości w danych o wysokiej wymiarowości i oczekiwanie, że LOF zadziała bez wcześniejszej redukcji wymiarowości.
  • Ustawienie arbitralnego progu LOF (np. wynik > 1,5) bez analizy rozkładu wyników dla konkretnego zbioru danych.

Najczęściej zadawane pytania

Jak wybrać właściwą wartość k?

Nie ma uniwersalnie optymalnego k. Powszechną praktyką jest ocena zakresu wartości – zazwyczaj od 5 do 50 – i analiza, jak zmienia się rozkład wyników i oznaczone anomalie. Analiza wrażliwości na wartości k daje pewność, że wykryte anomalie są odporne na wybór. Wiedza dziedzinowa o minimalnym oczekiwanym rozmiarze klastra może również pomóc w określeniu dolnej granicy.

Co oznacza wynik LOF równy 1 w porównaniu do 3?

Wynik bliski 1 oznacza, że punkt ma mniej więcej taką samą gęstość lokalną jak jego sąsiedzi i jest uważany za punkt nieanomalny. Wynik znacznie większy od 1 – często interpretowany jako powyżej 1,5 lub 2 w zależności od zbioru danych – wskazuje, że sąsiedztwo punktu jest znacznie rzadsze niż sąsiedztwo jego sąsiadów. Nie ma uniwersalnego progu; próg powinien być wybrany poprzez analizę rozkładu wyników LOF dla konkretnego zbioru danych.

Czy LOF może oceniać nowe, niewidziane punkty bez ponownego uczenia?

LOF jest metodą transdukcyjną: wymaga obecności zbioru treningowego do obliczenia sąsiedztw i gęstości dla dowolnego nowego punktu. Aby ocenić nowe obserwacje, należy zachować zbiór treningowy, a każdy nowy punkt musi zostać wstawiony w celu ponownego obliczenia jego k-sąsiedztwa względem przechowywanych punktów treningowych. Niektóre implementacje oferują tę funkcjonalność, ale fundamentalnie różni się ona od modeli parametrycznych, które uczą się zwartej funkcji oceny.

Jak LOF wypada w porównaniu do Isolation Forest w detekcji anomalii?

LOF wykorzystuje estymację gęstości opartą na lokalnych sąsiedztwach i jest silniejszy, gdy anomalie grupują się w lokalnie rzadkich regionach heterogenicznej przestrzeni. Isolation Forest wykorzystuje losowe partycjonowanie i jest zazwyczaj szybszy i bardziej skalowalny do dużych zbiorów danych. W przypadku danych o wysokiej wymiarowości lub bardzo dużych zbiorów danych często preferowany jest Isolation Forest; w przypadku danych o umiarkowanej wymiarowości ze zmiennością gęstości, LOF często oferuje lepszą dyskryminację.

Pokrewne metody

Źródła

  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.

    Otwórz odnośnik DOI
    Skopiowano.
  2. Aggarwal, C. C. (2017). Outlier Analysis (2nd ed., Ch. 4). Springer.

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

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