Wykrywanie anomalii: jakiego algorytmu użyć?

Kontekst: Opracowuję system analizujący dane kliniczne w celu odfiltrowania nieprawdopodobnych danych, które mogą być literówkami.

Co do tej pory zrobiłem:

Aby oszacować wiarygodność, do tej pory próbowałem znormalizować dane, a następnie obliczyć wartość wiarygodności dla punktu p na podstawie jego odległości do znanych punktów danych w zestawie D (= zestaw treningowy):

plausibility (p) = \sum_{q \in D} Gauss (distance (p, q))

$\text{plausibility}(p)=\sum_{q\in D}\text{Gauss}(\text{distance}(p,q))$

Dzięki tej kwantyfikacji mogę następnie wybrać próg, który oddziela wiarygodne dane od nieprawdopodobnych danych. Używam python / numpy.

Moje problemy:

Ten algorytm nie wykrywa niezależnych wymiarów. Idealnie byłoby, gdybym umieścił w algorytmie wszystko, co wiem o rekordzie, i sam przekonałbym się, że wymiar X nie wpływa na wiarygodność zapisu.
Algorytm tak naprawdę nie działa w przypadku wartości dyskretnych, takich jak wartości logiczne lub wybrane dane wejściowe. Można je odwzorować na ciągłe wartości, ale sprzeczne z intuicją jest to, że Select 1 jest bliżej Select 2 niż Select 3.

Pytanie:

Jakiego rodzaju algorytmów powinienem szukać w tym zadaniu? Wydaje się, że istnieje mnóstwo opcji, w tym podejście oparte na najbliższym sąsiedztwie, oparte na klastrowaniu i statystyczne. Mam też problemy ze znalezieniem artykułów, które zajmują się wykrywaniem anomalii tej złożoności.

Wszelkie porady są mile widziane.

[Edytuj] Przykład:

Załóżmy, że dane zawierały wysokość osoby, wagę osoby i znacznik czasu - więc są to dane 3D. Waga i wzrost są skorelowane, ale znacznik czasu jest całkowicie niezależny. Jeśli wezmę pod uwagę odległości euklidesowe, musiałbym wybrać mały próg, aby pasował do większości moich danych dotyczących weryfikacji krzyżowej. Idealnie byłoby, gdyby algorytm po prostu zignorował wymiar znacznika czasu, ponieważ ustalenie, czy rekord jest wiarygodny, nie ma znaczenia, ponieważ znacznik czasu nie jest w żaden sposób powiązany z innymi wymiarami. Każdy znacznik czasu jest prawdopodobny.

Z drugiej strony można wymyślić przykłady, w których znacznik czasu ma znaczenie. Na przykład może być tak, że wartość Y dla cechy X jest wiarygodna, gdy jest mierzona przed określoną datą, ale nie po określonej dacie.

— Georg
źródło

Proszę zobaczyć moją odpowiedź na stats.stackexchange.com/questions/97946/changepoints-in-r, ponieważ traktuje to dokuczliwe (niektórym!) Pytanie.

— IrishStat

Czy stats.stackexchange.com/questions/213 to coś, czego szukasz?

— whuber

Wątpię, czy możesz sprawić, by to zadziałało dla boolczyków.

— Aksakal

@ whuber Nie jestem pewien, nie wydaje się, aby obejmowało to, jak nieistotne wymiary można zignorować.

— Georg

Nawiasem mówiąc, staram się również znaleźć formalizację dla opisanego przeze mnie podejścia. Gdybym znał formalny termin, pomógłby mi również w badaniach. Być może istnieje odmiana tego algorytmu, która rozwiązuje przynajmniej problem niezależnego / nieistotnego wymiaru.

— Georg

Odpowiedzi:

Typowym sformułowaniem Wykrywania Anomalii jest znalezienie średniej i wariancji dla każdej z cech nieanormalnych danych, a jeśli jest wektorem tych cech mających składowe to zdefiniuj prawdopodobieństwo kombinacji cech jako $m$ $x$ $x_i$ $p(x)$

p (x) = \prod_{i = 1}^{m} p (x_{i}; μ_{i}, σ_{i}^{2})

$p(x) = \prod_{i=1}^m{p(x_i;\mu_i,\sigma_i^2})$

gdzie każdy jest rozłożony gaussa: $x_i$ $x_i \sim \mathcal{N(\mu_i,\sigma_i^2)}$

anomalia występuje za każdym razem, gdy $p(x) < \epsilon$

Rozkład każdego nie musi być w rzeczywistości normalny, ale lepiej jest, jeśli jest przynajmniej normalny. Ale funkcje, których używasz, są dowolne; można je pobierać bezpośrednio z surowych danych lub obliczać, więc na przykład jeśli uważasz, że funkcja jest lepiej modelowana za pomocą ustaw ją na zamiast . $x_i$ $x_i$ $log$ $log(x_i)$ $x_i$

To wydaje się bardzo podobne do tego, co już robisz, jeśli weźmiesz . $q = \mu$

Określanie $\epsilon$

Algorytm pasuje do przykładów negatywnych (nie-anomalie). Ale jest określany na podstawie zestawu weryfikacji krzyżowej i zwykle jest wybierany jako wartość, która zapewnia najlepszy wynik $\epsilon$ $F1$

F 1 = \frac{2 * P r e c i s i o n * R e c a l l}{P r e c i s i o n + R e c a l l}

$F1 = {2*Precision*Recall\over Precision + Recall}$

Ale aby obliczyć F1, musisz wiedzieć, co jest anomalne, a co nie; to jest prawdziwie pozytywne, gdy system przewiduje anomalię, a faktycznie jest to anomalia, fałszywie pozytywne są przewidywane anomalie, które tak naprawdę nie są i tak dalej. Więc jeśli tego nie masz, być może będziesz musiał wrócić do zgadywania.

Problem skorelowanych cech

Powyższe ma jednak wadę, jeśli cechy są skorelowane. Jeśli tak, to powyższe obliczenia mogą nie oznaczać czegoś, co faktycznie jest anomalne. Rozwiązaniem tego problemu jest użycie wielowymiarowego gaussa dla funkcji gdzie jest macierzą kowariancji. $m$ $\Sigma$

p (x) = \frac{1}{(2 π)^{\frac{m}{2}} (det Σ)^{1 / 2}} e^{- \frac{1}{2} (x - μ)^{T} Σ^{- 1} (x - μ)}

$p(x)= {1\over (2\pi)^{m\over 2}(\det\Sigma)^{1/2}}e^{-{1\over2}(x-\mu)^T\Sigma^{-1}(x - \mu)}$

To samo dotyczy znalezienia a to podejście ma również tę wadę, że musisz obliczyć odwrotność . Musi więc być co najmniej tyle próbek, ile cech, a jeśli liczba cech jest duża, proces będzie intensywny obliczeniowo, a ty musisz zabezpieczyć się przed cechami zależnymi liniowo. Pamiętaj o tych zastrzeżeniach, ale wydaje się, że nie stanowi to problemu. $\epsilon$ $\Sigma$

— waTeim
źródło

Próbowałem już tego podejścia, w tym wielowymiarowego rozkładu Gaussa. Rzeczywiście, niepowiązane funkcje nie stanowią większego problemu w przypadku tego podejścia. Odkryłem, że to podejście nie jest odpowiednie dla złożonych modeli. Na przykład, gdybym miał zbiór danych 2D z funkcjami F1, F2, gdzie zdarza się, że z grubsza F2 = F1 ^ 3, wielowymiarowy rozkład gaussowski tylko narysuje elipsę wokół danych i modeluje dane z grubsza. Dlatego wybrałem podejście opisane w pytaniu (gdzie nie ma jednego q, ale wielu qs).

— Georg

Czy istnieje sposób na zastosowanie wielowymiarowego podejścia gaussowskiego i zastosowanie go do przechwytywania bardziej złożonych modeli danych? Na przykład, czy modele mieszane mogą mi w tym pomóc? Przeczytałem trochę o tych z moich badań, ale jeszcze nie do końca zrozumiałem, jak je zastosować.

— Georg

@Georg Hmm Zastanawiam się, czy twój problem nie jest problemem złożonych modeli, ale złożonych danych i zbyt uproszczonych modeli. Lub innymi słowy niedopasowane. W powyższym przypadku, co się stanie, jeśli zamiast użyjesz ? Funkcje można pobrać z danych lub obliczyć.

(F 1, F 2)

$(F1,F2)$

(F 1, F 2^{1 / 3})

$(F1,F2^{1/3})$

— waTeim

Tak, niedopasowanie jest tym, co mam na myśli. I tak, to by działało, ale chcę, aby algorytm wykrył to automatycznie. Nie mogę ręcznie modyfikować funkcji, powinno działać w każdym przypadku.

— Georg,

Oto przykład: na dwóch wykresach wyświetlane są dane dotyczące wysokości (oś x) i masy (oś y) (Przepraszamy za napisy w języku niemieckim;)). Pierwszy wykres pokazuje wynik wielowymiarowego podejścia gaussowskiego, drugi z podejścia opisanego w pytaniu. W obu przypadkach próg został wybrany w taki sposób, że 97% danych CV uważa się za wiarygodne. Drugie podejście pozwala lepiej uchwycić złożoność danych. 1: dl.dropboxusercontent.com/u/26034024/anomaly/gauss.png 2: dl.dropboxusercontent.com/u/26034024/anomaly/distance.png

— Georg

Prawie skończyłem projekt, w którym musiałem rozwiązać te problemy i chciałbym podzielić się moim rozwiązaniem, na wypadek, gdyby ktoś miał te same problemy.

Po pierwsze, podejście, które opisałem, jest bardzo podobne do oszacowania gęstości jądra . Dobrze było wiedzieć o badaniach ...

Niezależne funkcje

Niezależne funkcje można odfiltrować, mierząc współczynnik korelacji . Porównałem wszystkie cechy parami i zmierzyłem korelację. Następnie wziąłem maksymalny współczynnik korelacji bezwzględnej każdej cechy jako współczynnik skalowania. W ten sposób cechy, które nie korelują z żadnymi innymi, są mnożone przez wartość bliską 0, a zatem ich wpływ na odległość euklidesową(inaczej ) jest nieistotna. $||x_1 - x_2||$ $distance(x_1, x_2)$

Uwaga: współczynnik korelacji może mierzyć tylko korelacje liniowe. Szczegółowe informacje można znaleźć na połączonej stronie wiki. Jeśli korelacja w danych może być aproksymowana liniowo, działa to dobrze. Jeśli nie, powinieneś rzucić okiem na ostatnią stronę tego artykułu i sprawdzić, czy możesz użyć ich pomiaru korelacji, aby uzyskać współczynnik skalowania.

Wartości dyskretne

Użyłem opisanego algorytmu tylko do wartości ciągłych. Do filtrowania zestawu treningowego zastosowano wartości dyskretne. Więc jeśli mam wzrost i wagę osoby i wiem, że ona jest kobietą, będę patrzeć tylko na próbki od innych kobiet w celu sprawdzenia anomalii.

— Georg
źródło

Wykrywanie anomalii: jakiego algorytmu użyć?

Określanieϵϵ\epsilon

Problem skorelowanych cech

Określanie $\epsilon$