Detekcija anomalija – Deo I
Neočekivani šabloni u podacima nazivaju se anomalijama i ukazuju na bitne, često kritične, informacije u odgovarajućim domenima primene. Na primer, anomalije na slici sa magnetne rezonance mogu ukazati na prisutnost tumora, a anomalije na transakcijama sa kreditne kartice mogu ukazati na krađu identiteta.
Detekcija anomalija (Anomaly detection) se odnosi na problem identifikovanja šablona koji nisu u skladu sa očekivanim ponašanjem. Anomalije se još nazivaju i neskladnim zapažanjima, izuzecima, aberacijama, zagađivačima ili izolovanim podacima (outliers) u odgovarajućim domenima primene. Detekcija anomalija se primenjuje u statistici, obradi signala, proizvodnji, umrežavanju (networking), pretrazi podataka (data minig), ekonomiji i finansijama. Detekcija anomalija u podacima se proučava u statistici još od devetnaestog veka. Vremenom su otkrivene razne tehnike za pronalaženje anomalija u podacima, od kojih su mnoge specifične za određene domene primene.
Sadržaj
Anomalije
Anomalije su šabloni u podacima koji nisu u skladu sa već definisanim pojmom normalnog ponašanja i možemo ih kategorizovati na sledeći način:
Tačkaste anomalije – Individualna instanca podataka se smatra anomalijom ako se nalazi isuviše daleko od ostalih podataka. Ovo je najjednostavniji tip anomalija. Na primer, uočavanje prevare na kreditnoj kartici na osnovu potrošenog iznosa sa kartice;
Anomalije konteksta (kondicionalne anomalije) – Ova vrsta anomalija je vezana za kontekst i česta je kod vremenskih serija podataka. Na primer, normalno je da ljudi potroše više novca kada je sezona godišnjih odmora, u suprotnom postaje sumnjivo. Svaka instanca podataka se definiše na osnovu dva skupa atributa:
Kontekstualni atributi – Koriste se da odrede kontekst (susedstvo) za tu instancu. U prostornim podacima geografska dužina i širina lokacije su kontekstualni atributi.
Atributi ponašanja – Definišu nekontekstualne karakteristike instance. U prostornim podacima ako želimo da opišemo prosečne padavine celog sveta, količina padavina na bilo kojoj lokaciji je atribut ponašanja.
Kolektivne anomalije – Kolekcija povezanih instanci podataka se posmatra kao anomalija u odnosu na ceo skup podataka. Individualne instance u toj anomaliji ne moraju biti same anomalije, ali njihova zajednička pojava predstavlja anomaliju. Na primer, neko pokušava neočekivano da kopira podatke sa nečijeg računara na neku udaljenu lokaciju bi bilo detektovano kao mogući sajber napad.
Na Slici 1 možemo videti skup podataka koji je predstavljen u dvodimenzionalnom prostoru. Podaci imaju tri normalna regiona, \(N_1, N_2\) i \(N_3\), zato što se većina podataka nalazi u njima. Podaci koji su van ovih regiona su anomalije. 
Dakle, trebalo bi prvo da odredimo regione u kojima se podaci ponašaju normalno i sve podatke van tih regiona da označimo kao anomalije. Određivanje ovih regiona nije tako lako i nailazi se na puno prepreka. Često anomalije koje leže veoma blizu granice mogu ipak biti normalni podaci, kao što i podaci unutar normalnih regiona koji su blizu granice mogu biti anomalije. Takođe, jedan od problema je što se u mnogim domenima normalno ponašanje podataka menja i trenutni pojam normalnog ne mora biti dovoljno reprezentativan u budućnosti. Još jedan od problema je da u različitim domenima tačan pojam anomalije nije isti. Na primer, u medicini mala devijacija od normalnog može biti anomalija, dok na berzi se takva devijacija može smatrati normalnim ponašanjem. Dostupnost podataka za trening i validaciju modela koje koriste tehnike za detekciju anomalija su uglavnom veliki problem. Šumovi u podacima su veoma slični anomalijama. Šumovi se mogu opisati kao pojava u podacima koja nije interesantna osobi koja alizira podatke, već joj predstavlja smetnju. Uklanjanje šumova u podacima je motivisano uklanjanjem neželjenih objekata pre nego što se izvrši analiza podataka. Šumovi su često veoma slični anomalijama i zbog toga može biti prilično teško razlikovati ih i ukloniti.
Zbog svih ovih prepreka, problem detekcije anomalija nije lak za rešavanje. Štaviše, većina tehnika za detekciju anomalija koje postoje rešavaju samo specifičnu formulaciju problema. Glavni aspekt bilo koje tehnike za detektovanje anomalija je priroda ulaznih podataka. Ulaz uglavnom predstavlja kolekcija instanci podataka. Svaka instanca se može opisati pomoću skupa osobina (atributa ili feature-a) koje mogu biti kategoričkog ili kontinualnog tipa. Svaka instanca može imati jedan (univariate) ili više (multivariate) atributa. U multivariate slučaju, atributi mogu biti svi istog tipa ili mešavina različitih tipova podataka. Priroda atributa određuje primenljivost tehnika za detekciju anomalija. U statistici moraju se koristiti različiti statistički modeli za kontinualne i kategorijske podatke. Slično, u slučaju metode najbližih suseda, priroda atributa određuje koja metrika će biti korišćena. Ulazni podaci se mogu kategorisati i na osnovu veza između instanci. Na primer, podaci u obliku nizova, prostorni podaci i podaci predstavljeni pomoću grafova. U podacima u obliku nizova, instance su linearno sortirane, na primer vremenske serije podataka, nizovi genoma i proteina. U prostornim podacima svaka instanca je povezana sa susednim primerima, na primer ekološki podaci. U podacima predstavljnjnim pomoću grafova instance su predstavljene pomoću temena na grafovima i povezane su sa ostalim temenima pomoću grana.
Labele podataka
Labele povezane sa instancama podataka označavaju da li je instanca normalan podatak ili je anomalija. Prikupljanje labela se često radi ručno, od strane eksperta, i zbog toga je potrebno puno vremena i novca da bi se prikupile za trening podatke. Obično je teže prikupiti labele koje pokrivaju sve tipove anomalija nego prikupiti labele za normalne podatke. U nekim slučajevima, kao na primer u saobraćajnoj bezbednosti aviona, prikupljanje anomalija bi ukazalo na katastrofalne događaje. Na osnovu stepena dostupnosti labela, tehnike za detekciju anomalija mogu funkcionisati na jedan od sledećih načina:
Nadgledana detekcija anomalija (Supervised Anomaly Detection) – Podrazumeva se dostupnost podataka trening skupa koji ima labelirane instance i za normalne podatke i za anomalije. Pravi se model za predviđanje za normalne podatke i slučajeve u kojima se javljaju anomalije. Kod nadgledane detekcije anomalija može se naići na jedan od dva problema. Prvi problem nastaje kada anomalija ima mnogo malo u odnosu na normalne instance u trening podacima. Drugi porblem je prikupljanje tačnih i reprezentativnih labela, naročito za anomalije.
Polunadgledana detekcija anomalija (Semi – Supervised Anomaly Detection) – Pretpostavlja se da trening podaci imaju labelirane instance samo za normalne podatke. Ovaj tip detekcije se puno koristi zato što ne zahteva labele za anomalije. Pravi se model za normalne slučajeve i koristi se da identifikuje anomalije na test podacima.
Nenadgledana detekcija anomalija (Unsupervised Anomaly Detection) – Ova vrsta detekcije ima široku primenu zato što ne zahteva trening podatke. Pravi se implicitna pretpostavka da se normalni podaci znatno češće pojavljuju u testnom skupu od anomalija.
Tipovi rezultata tehnika detekcije anomalija
Bitan aspekt za svaku tehniku detekcija anomalija je na koji način se anomalije prijavljuju. Rezultati ovih tehnika mogu biti:
Brojčani (score) – Svakoj instanci u testnom skupu se dodeljuje score u zavisnosti od toga koliko se instanca smatra anomalijom. Zbog toga je rezultat tehnike rangirana lista anomalija. Ovaj tip omogućava osobi koja analizira da koristi prag (treshold) kojim bira najbitnije anomalije;
Labele – U ovom slučaju tehnike dodeljuju labelu (da li je podatak normalan ili anomalija) svakoj instanci iz testnog skupa. Tehnike koje dodeljuju binarne labele testnim instancama ne omogućavaju osobi koja analizira da direktno odlučuje koje anomalije su najbitnije, mada je moguće to uraditi kroz izbor parametara u okviru svake tehnike.
Primene detekcije anomalija
\( 1. \) Detekcija upada (Intrusion Detection) se odnosi na detekciju zlonamernih aktivnosti (provala, upada i drugih oblika zloupotrebe računara) u računarskim sistemima. Ove zlonamerne aktivnosti su interesantne sa aspekta sigurnosti računara. Glavni izazov u ovoj kategoriji za detekciju anomalija je velika količina podataka. Zbog velike količine podataka dolazi do lažnih uzbuna. Kako postoji puno podataka, mali procenat lažnih uzbuna može preopteretiti osobu koja analizira podatke. Labele za normalne instance su uglavnom dostupne, dok za upade nisu. Zbog toga se koriste polunadgledane i nenadgledane tehnike za detekciju anomalija.
\( 2. \) Detekcija prevara se odnosi na detekciju kriminalnih aktivnosti komercijalnih organizacija, kao što su banke, kompanije kreditnih kartica, osiguravajuća društva, berza i drugo. Zlonamerne osobe mogu biti i sami korisnici te organizacije ili osobe koje se postave kao korisnici (poznato kao krađa identiteta). Do zloupotrebe dolazi kada korisnici koriste resurse obezbeđene od strane organizacije na neodobren način. Organizacije žele da ovakve prevare uoče što pre kako bi izbegle finansijske gubitke.
\( 3. \) Detekcija prevara vezanih za kreditne kartice se koristi za otkrivanje malicioznih aplikacija koje koriste kreditne kartice i malicioznog korišćenja kreditnih kartica (vezanih za krađu kreditnih kartica). Ovaj tip detekcije je sličan detekciji prevara vezanih za osiguranja. Podaci se uglavnom sastoje od zapisa definisanih u nekoliko dimenzija, kao što su ID korisnika, količina potrošenog novca, vreme između uzastopnih korišćenja kartice, i drugo. Prevare se uglavnom ogledaju u evidencijama o transakcijama (tačkaste anomalije) i često su u pitanju velike transakcije, kupovina proizvoda koje korisnik nije do tada kupovao ili velika frekvencija kupovina. Kompanije imaju kompletne podatke dostupne sa sve labelama. Štaviše, podaci su vezani za jedinstvene korisnike na osnovu njihove kreditne kartice. Izazov vezan za detekciju neodobrenog korišćenja kreditnih kartica predstavlja to što zahteva detekciju prevara na mreži (online) čim se desi maliciozna transakcija. Tehnike za detekciju prevara se primenjuju na dva glavna načina kako bi rešile ovaj problem. Prvi način je poznat vlasniku. U ovom slučaju svaki korisnik kreditne kartice se profiliše na osnovu istorije korišćenja kreditne kartice. Svaka nova transakcija se poredi sa korisnikovim profilom i označava se kao anomalija ako se ne slaže sa profilom. Ovaj pristup je obično skup jer zahteva upit centralnog skladišta podataka svaki put kada korisnik izvrši transakciju. Drugi pristup je poznat kao po operaciji (by-operation) koji detektuje anomalije među transakcijama na određenim geografskim lokacijama. Obe tehnike detektuju kontekstualne anomalije. U prvom slučaju kontekst je korisnik, a u drugom slučaju kontekst je geografska lokacija.
\( 4. \) Detekcija prevara mobilnih telefona je tipično problem praćenja aktivnosti. Treba skenirati veliki skup naloga, pregledati istoriju poziva korisnika i alarmirati kada deluje da je nalog zloupotrebljen. Svaki poziv je vektor atributa koji su kontinualnog (na primer trajanje poziva) i diskretnog (na primer grad iz koga je obavljen poziv) tipa.
\( 5. \) Detekcija prevara osiguravajućih kompanija je veoma bitna kompanijama kako bi izbegle finansijske gubitke. Dostupni podaci se dobijaju od podnosioca zahteva za osiguranje. Tehnike iz ovih dokumenata izvlače različite atribute, kako kategorijskog tipa, tako i kontinualnog. Uglavnom, postoje osobe koje manuelno procenjuju da li su zahtevi prevare ili ne. Oni zahtevi koje ocene kao prevaru se koriste kao labelirane instance za nadgledane i polunadgledane tehnike u detekciji prevara osiguravajućih kompanija.
\( 6. \) Detekcija prevara insajderskog trgovanja – Insajdersko trgovanje se odnosi na berzu, pri čemu ljudi ilegalno zarađuju koristeći informacije dobijene iznutra (insajderske informacije), pre nego što se te informacije javno objave. Insajdersko trgovanje se može detektovati identifikovanjem anomalija u trgovinskim aktivnostima na tržištu. Dostupni podaci se dobijaju iz nekoliko raznovrsnih izvora kao što su podaci o trgovini akcijama ili vesti. Podaci su vremenski ograničeni jer se prikupljaju neprekidno.
Detekcija anomalija se još koristi i za detektovanje industrijske štete, obrađivanje slika, za prepoznavanje govora, u tekstualnim podacima i drugo.
Tehnike za detekciju anomalija
Tehnike za detekciju anomalija zasnovane na klasifikaciji
Klasifikacija se koristi kako bi se model (klasifikator) istrenirao iz labeliranih instanci podataka i nakon toga za klasifikaciju testnih instanci u jednu od klasa koristeći istrenirani model. Detekcija anomalija zasnovana na klasifikaciji se sastoji iz dve faze. Prva faza je trening faza, u kojoj klasifikator uči iz dostupnih labeliranih podataka. Druga faza je test faza u kojoj se pomoću klasifikatora instance testiraju da li su anomalije ili normalni podaci. Pretpostavlja se da klasifikator koji može da razlikuje normalne podatke od anomalija se može istrenirati u prostoru atributa. Na osnovu labela koje su dostupne u trening podacima, ova tehnika se može podeliti u dve kategorije:
\( 1. \) Višeklasna klasifikacija (multi-class) Trening podaci sadrže više klasa koje pripadaju normalnim podacima. Ovakve tehnike za detekciju anomalija uče klasifikator da razlikuje svaku normalnu klasu od ostalih normalnih klasa. Test instanca se smatra anomalijom ako nije klasifikovana kao normalna od strane ni jednog klasifikatora.
\( 2. \) Jednoklasna klasifikacija (one-class) Sve trening instance imaju samo jednu klasu za labelu. Ove tehnike koriste diskriminativnu granicu oko normalnih instanci koristeći algoritam jednoklasne klasifikacije, kao što su jednoklasne metode potpornih vektora (one – class Support Vector Machines). Svaka test instanca koja ne upada u okviru naučene grance se smatra anomalijom.
Tehnike za detekciju anomalija zasnovane na neuronskim mrežama
U detekciji anomalija, neuronske mreže se koriste i za višeklasne i za jednoklasne podatke. Elementarna tehnika za detekciju anomalija zasnovana na neuronskim mrežama funkcioniše u dva koraka. Prvo se trenira neuronska mreža na normalnim podacima kako bi naučila da razlikuje klase. Zatim se svakoj test instanci dodeljuje ulaz u neuronsku mrežu. Ako mreža prihvati taj ulaz, u pitanju je normalan podatak, a ako ga odbije, u pitanju je anomalija.
Za jednoklasnu detekciju anomalija koristie se replikatorne neuronske mreže (Replicator Neural Networks). Konstruiše se višeslojna feed forward neuronska mreža koja ima isti broj ulaznih i izlaznih neurona (koji odgovaraju atributima u podacima). Trening podaci uključuju kompresovanje podataka u tri skrivena sloja. Test faza podrazumeva rekonstrukciju svake instance podataka \(x_i\) koristeći mrežu, kako bi dobila rekonstruisani izlaz \(o_i\). Rekonstrukcijska greška \({\delta}_i\) za test instancu \(x_i\) se dobija po formuli:
\( \sum_{j=1}^{n} (x_{ij} – o_{ij})^2 \)
gde je \(n\) broj atributa pomoću kojih su podaci definisani. Rekonstrukcijska greška \(δ_i\) se uzima kao score anomalije za tu test instancu.
Tehnike za detekciju anomalija zasnovane na klasterizaciji
Klasterizacija se koristi kako bi se grupisale slične instance podataka. Ovo je primarno nenadgledana tehnika detekcije anomalija i može se grupisati u tri kategorije:
\( 1. \)Prva kategorija se zasniva na pretpostavci da instance normalnih podataka pripadaju nekom klasteru, dok anomalije ne pripadaju ni jednom klasteru. Tehnike zasnovane na ovoj pretpostavci primenjuju poznate klaster algoritme na skup podataka i svaki podatak koji ne pripada ni jednom klasteru proglašavaju anomalijom. Mana ovih tehnika je ta što nisu optimizovane da pronalaze anomalije jer je glavni cilj ovih algoritama da pronađu klastere.
\( 2. \)Druga kategorija se zasniva na pretpostavci da se normalne instance nalaze blizu svog klaster centroida, dok se anomalije nalaze daleko od njihovog najbližeg klaster centroida. Prvo se podaci klasterizuju koristeći neki klaster algoritam, a zatim se računa rastojanje svake instance podataka do njenog najbližeg klaster centroida kao score anomalije. Ako anomalije formiraju svoje klastere, ove tehnike se ne mogu primeniti i zbog toga je formirana sledeća kategorija.
\( 3. \)Treća kategorija se zasniva na pretpostavci da normalne instance pripadaju velikim i gustim klasterima, dok anomalije pripadaju malim ili raštrkanim klasterima. Tehnike zasnovane na ovoj pretpostavci proglašavaju anomalijama instance koje pripadaju klasterima čija je veličina i/ili gustina ispod određenog praga.
Od tehnika za detekciju anomalija još se koriste relativna gustina, statistička detekcija anomalija kao i tehnike spektralne detekcije anomalija.
U narednom delu obradićemo detekciju anomalija u vremenskim serijama kao i detekciju anomalija pomoću grafova. Takođe ćemo uraditi jedan jednostavan primer u R-u.
Reference
Anomaly Detection: A Survey – Varun Chandola, Arindam Banerjee, Vipin Kumar – https://www.vs.inf.ethz.ch/edu/HS2011/CPS/papers/chandola09_anomaly-detection-survey.pdf
https://en.wikipedia.org/wiki/Anomaly_detection
Autor: Marta Dragicevic
Studentkinja master studija informatike na Prirodno-matematičkom fakultetu u Kragujevcu.
Osnovne akademske studije matematike završila je na Prirodno-matematičkom fakultetu u Kragujevcu, smer teorijska matematika.
Trenutno je zaposlena u firmi TechnoSigma.
