Anomália detektálás nem sztochasztikus és nem parametrikus módon

Képek egyben: https://imgur.com/a/LBVLQ7H

Mi az anomália? Relatív furcsaság egy rendszerben.

Rendkívül hasznos tud lenni, ha elérhető megfelelő adat. Például hasznos lehet a valós idejű észlelése gyanús vagy hibás eseményeknek és bejegyzéseknek egészségügyi adatokban, pénzügyi, banki tranzakciókban vagy hálózati rendszerek kommunikációjában.

Befejeztem a fejlesztését egy olyan anomália detektáló algoritmusnak, mely teljesen non-parametrikus. Ezen tulajdonság előnyét több blogomban ecseteltem. Ezért kitérek a nem sztochasztikus viselkedés fontosságára.

Tudtommal egyetlen olyan AD eljárása van emberiségünknek, mely nyílt és lineáris időben fut. Ez az izolációs erdő (IF):

https://en.wikipedia.org/wiki/Isolation_forest

A saját megoldásom négyzetes időkomplexitású sajnos. De kisebb adatnál (<3000 sor <30 oszlop) elfogadhatóan gyors. Ekkora adatnál lefut 36 másodperc alatt egy nem optimalizált Ruby kóddal 1 szálon. 10 ezer oszlop és 100 változóval ez 20 percig tart. A gyakorlatban viszont nem nagyon generálódnak nálam ekkora méretek. De ha big data a cél, akkor egyértelműen IF a megfelelő eszköz.

Miért probléma a sztochasztikus viselkedés?

Mondjuk úgy, hogy általában nem probléma, de ritkán az tud lenni. Ha egy véletlen állapotból konvergálunk egy kívánt állapot felé – ahogy IF is teszi, neurális hálók és egyéb eljárások - akkor tud néha gond lenni, mert kimaradhat pár találat a véletlen generátor állapotától függően, mely egyébként detektálható lett volna. A seed állítása pedig csak a determinisztikus futást segíti elő, a működés problémáját nem oldja meg.

A tökéletes megoldás számomra mindenképpen az, ha az eredmény bizonytalanságának foka mindig nulla, függetlenül a bemeneti adattól, állapottól és paraméterektől. Ez alatt azt értem, hogy ha létezik egy anomália az algoritmus feltételei szempontjából, akkor találja meg. Mindhárom kipipálva.

Euklideszi távolságokat vizsgálok minden pont között. Ez triviális és elterjedt megoldás és bármekkora dimenzióban stabil számítást ad, mert nincs benne osztás például. Hátránya a négyzetesen növekvő számítási idő az adat méretének függvényében.

A nehézség ott van, hogy hogyan állapítsuk meg a határát a leszakadó pontok távolságának. Figyelembe kell tudnia vennie az algoritmusnak a kisebb szigetekben lévő csoportokat is (relatív lokális tömeg) és az átlagos távolságot a teljes tömegtől (relatív globális tömeg).

Például ha egy vastag gyűrű közepén van 1 elem (belső leszakadás), akkor azt is detektálnia kell tudni. De ha a szélén szakad le (külső leszakadás), azt is. Mindezt magas dimenzióban is tudnia kell hozni, ahol további problémaként lép fel a „curse of dimensionality”:

https://en.wikipedia.org/wiki/Curse_of_dimensionality

Az egyetlen maradék paraméter a sigma minimum, ami viszont mégsem paraméter az esetek 99%-ban, mert 3-as értékre van szükségem.

Több elemzésen vagyok túl 10+ bemeneti változóval IF-hez hasonlítva és önmagában is vizsgálva az eredményt. Erősen hibatűrően viselkedik és megfelelő eredményeket ad.

A limit megállapításának és a fenti két feltétel pontozásának implikációi aktív és folyamatban lévő kutatásom tárgyát képezik.