Anomalian etsiminen tietomassoista
Kirjoittaja: Eija Parmes, VTT, eija.parmes[at]vtt.fi
Artikkeli pdf-muodossa (Positio 03/2009)
Auto on vedessä anomalia, mutta miten se todistetaan laskennallisilla menetelmillä?
Anomalioiden etsimiseen tietomassoista käytetään pääosin samoja menetelmiä kuin etsittäessä malleja ja ryhmiä tietomassoista.. Anomalian etsintä perustuu siihen, että havainto eroaa joltain ominaisuudeltaan löydetyistä ja tunnistettavista malleista ja ryhmistä. Anomalian etsinnässä käytetään luokitus ja ryhmittelymenetelmiä, regressioanalyysiä ja projisiointimenetelmiä, sekä spatiaalisia ja informaatioteoreettisia tiedonlouhinnan menetelmiä.
Anomalia ei aina ole harvinaisuus
Anomalia on muusta havaintojoukosta poikkeava havainto tai joukko havaintoja. Se voi olla epänormaali aktiivisuus luottokorttiostoksissa, säännötön koodi tietoliikenteessä, vääränlainen solu tomografiakuvassa tai odottamaton ajoneuvo metsän keskellä.
Uusi harvinainen havainto ei ole aina anomalia. Kun uusi havainto saadaan sopimaan malliin tai sen perusteella aiheellisesti korjattuun malliin, anomalia muuttuu normaalihavainnoksi.
Anomalia ei aina ole harvinainen. Useinkin esiintyvä havainto voi olla anomalia, jos sen syytä tai luokkaa ei pystytä osoittamaan tai sitä ei pystytä mallintamaan ja selittämään fysikaalisilla malleilla. Yleensä kuitenkin mitä tiheämmin havainto esiintyy, sitä todennäköisemmin se pystytään mallintamaan ja liittämään osaksi normaalihavaintoja.
Seuraavassa käsitellään erityisesti anomalian havaitsemista monikanavaisesta kuva-aineistosta. Anomalian tyyppivektoria ei tunneta (jos tunnetaan, ongelma palautuu tavalliseksi luokitusongelmaksi), vaan anomalian etsintä perustuu havainnon harvinaisuuteen tai muista havainnoista tai ympäristöstä poikkeavaan piirrevektoriin.
Anomaliatyypit
Pistemäinen anomalia on yksittäinen tai muutaman havainnon muodostama ryväs, jonka 1-N attribuuttia/piirrettä/ominaisuutta eroaa selkeästi muusta havaintojoukosta.
Anomalia voi myös muodostua vasta useamman havainnon yhdistelmästä. Havainnot ovat yksinään normaaleja, mutta niiden esiintyminen peräkkäin aikasarjassa tekee ilmiöstä anomalistisen. Tällainen kollektiivinen anomalia on esimerkiksi sydänkäyrässä näkyvä pidempi tasainen jakso ilman sykettä.
Kontekstuaalinen anomalia on anomalia vain suhteessa ympäristöönsä tai ajankohtaan, vaikka havainto toisessa kontekstissa on normaali. Esim. auton liikkuminen tiellä on normaalia, mutta sen sijainti vedessä on anomalia.
Ohjattu tai ohjaamaton luokitus
Anomalian etsintä perustuu siihen, että havainto tai havaintojoukko ei sovi tai on kaukana löydetyistä ja tunnistettavista malleista ja ryhmistä
Ohjatun tai puoliohjatun luokituksen (supervised or semisupervised classification) menetelmissä anomalian todennäköisyys määritetään laskemalla havainnon etäisyys ennalta tunnettuihin normaaliluokkiin tai normaalispektreihin. Normaaliluokat kuvataan joko parametrisesti (Gaussin käyrä, gammafunktio) tai ei-parametrisesti (Parzen-luokat, histogrammi, neuraaliverkot).
Ei-parametriset luokat sopivat paremmin anomalian havaitsemiseen, koska ne seuraavat tarkemmin normaaliluokkien rajoja. Luokitusmenetelmiä käytetään, kun anomalioita on suuri määrä erilaisia ja anomalian tunnistus tarvitaan reaaliajassa, kuten sensoriverkoissa, jotka tuottavat paljon eri jakaumien ja eri mallien mukaisia havaintoja.
Ohjaamattomissa ryhmittelymenetelmissä (clustering) havaintojoukko jaetaan ilman etukäteistietoa ryhmiin. Menetelmiä ovat SOM, K means -klusterointi ja suunnattujen puiden klusterointi (directed trees clustering). Anomalian havaitsemiseen sopiva ryhmittelymenetelmä ottaa huomion datan jakautumisen havaintoavaruudessa eikä pakota dataa ennalta määrättyyn määrään luokkia, joilla on ennalta määrätty minimietäisyys ja maksimihajonta.
Laaksonetsintä-menetelmää lähellä oleva suunnattujen puiden ryhmittely tekee ryhmiin jakamisen datan ehdoilla. Tuloksena on suuri määrä klustereita, joista suurikin osa voi sisältää vain yhden tai muutamia havaintoja. Esimerkiksi monikanavaisen satelliittikuvan spektrien ryhmittely suomalaisella alueella tuottaa noin 130 ryhmää, joista usea kymmenen sisältää vain muutamia tai muutamia kymmeniä havaintoja. Nämä ovat anomalian kannalta kiinnostavia ryhmiä.
Regressiotyyppinen mallintaminen
Pääkomponentti- ja PLS-analyysit kuuluvat regressiotyyppiseen mallintamiseen. Siinä havainnot projisioidaan avaruuteen, jossa anomalia erottuu paremmin.
Pääkomponenttianalyysiä käytetään pääasiassa havaintojoukon dimensioiden vähentämiseen, mutta se toimii myös anomalioiden etsinnässä. Ensimmäisessä komponentissa nähdään koko aineiston keskiarvo, mutta myöhemmissä komponenteissa erottuvat jatkuvasti harvinaisemmat havainnot, jotka eivät korreloi muiden havaintojen kanssa. Tätä ominaisuutta käytetään anomalioiden löytämiseksi. PLS-menetelmä (Partial Least Squares Projection to Latent Structures) on vastaava mutta ohjatussa muodossa, koska siinä käytetään sekä selittäviä että selitettäviä muuttujia. PLS-menetelmää käytetään erityisesti kemiallisten ja fysikaalisten prosessien yhteydessä, joissa sekä selitettäviä että selittäviä muuttujia on suuri määrä.
Edellä mainituilla spektrisillä luokitus- ja ryhmittelymenetelmillä indikoidaan vain pisteittäisiä anomalioita tai anomaliajoukkoja. Kontekstuaalisten ja kollektiivisten anomalioiden etsinnässä käytetään spatiaalisia menetelmiä, kuten autokorrelaatiota, semivariogrammeja, Fourier-muunnosta, pinnan pienemmän neliösumman mallinnusta tai factorial kriging -menetelmää. Spatiaalisissa menetelmissä kuvasta mallinnetaan ja poistetaan eri taajuuden komponentteja, jolloin jäljelle jää normaalipinnasta eroava vaihtelu.
Myös informaatioteoreettiset menetelmät ottavat huomioon ympäristön. Kuva-aineisto jaetaan osakuviin, joille lasketaan datan vaihtelua kuvaava tekstuurimitta, kuten kompleksisuus tai entropia. Mitä suurempi ennalta arvaamattomuus osakuvassa on ympäristön osakuviin nähden, sitä todennäköisemmin osakuva sisältää anomalian.
Anomalian etsinnän uusinta tekniikkaa on RX (Reed-Xiaoli) -menetelmä, jossa kuvan jokaiseen pisteeseen asetetaan pienempi ja suurempi ympyrä. Pienemmän ympyrän koko vastaa etsittävän kohteen, esimerkiksi ajoneuvon, kokoa. Pienemmän ympyrän spektrien etäisyys suuremman ympyrän spektrien keskiarvoon (esimerkiksi vesi) indikoi anomalian todennäköisyyttä.
Anomaliaa vai kohinaa?
Anomaliaa ei ole vielä pystytty määrittelemään matemaattisesti. Se on vain poikkeava havainto, joka erotetaan normaalista havainnosta tapaus- ja tilannekohtaisesti käyttäjän arvioimalla etäisyyden tai jäännösvirheen kynnysarvolla.
Anomalia ja kohina sekoittuvat helposti keskenään, ja joskus on mahdotonta erottaa anomalia kohinasta. Vaikeinta on erottaa anomalia valkoisesta kohinasta, joka on satunnaista ja noudattaa Gaussin jakaumaa. Värillinen kohina, joka korreloi havainnon kanssa, on helpompi tunnistaa kohinaksi
Kirjoittaja työskentelee tutkijana VTT:n Tietointensiiviset palvelut osaamiskeskuksessa aiheena satelliittikuvien tulkintamenetelmät.
Lisätietoa:
Chandola, V., Banerjee, A. and Kumar, V. Anomaly Detection: A Survey. Technical Report, Department of Computer Science and Engineering, University of Minnesota. TR 07-017, 2005.
Goovaerts, P, Jacquez, G.M. & Marcus, A. Geostatistical and local cluster analysis of high resolution hyperspectral imagery for detection of anomalies. Remote Sensing of Environment 95 (2005), pp. 351–367.
4.6.2010 14:25