Reunantunnistusmenetelmien tulokset esimerkkikuvassa

voidaan gradientista karsia tarpeen mukaan magnitudin perusteella positiiviset tai negatiivi-set arvot.

Kuvagradientin tuloksista pyritään lopuksi vielä tunnistamaan ne reunat, jotka ovat reunan-tunnistustehtävän kannalta olennaisia ja vastaavasti siis karsimaan epäolennaisia. Yksinker-tainen tapa karsia epäolennaisia reunoja on määrittää jokin kynnysarvo gradientin suuruudel-le ja korvata sitä pienemmät arvot nollalla ja suuremmat jollain nollaa suuremmalla vakiolla.

Kynnysarvon avulla saadut reunat sisältävät kuitenkin yleensä reunan lisäksi huomattavan määrän pikseleitä todellisen reunan ympäristöstä ja tuloksia täytyy edelleen jatkokäsitellä todellisen reunan löytämiseksi (kuva 2).

Yksinkertaista kynnysarvoa edistyneempi menetelmä on ei-maksimaalisten arvojen poisto (engl.non-maximum suppression), joka pyrkii löytämään gradientin lokaaleja maksimiarvo-ja gradienttivektorin suunnassa eli kohtisuorassa reunaa vastaan. Tämä menetelmä on käy-tössä Cannyn reunantunnistusalgoritmissa (Canny 1986), joka on yksi tunnetuimmista reu-nantunnistusalgoritmeista. Cannyn algoritmissa nämä tulokset vielä käsitellään niin sanotus-sa hystereesissä, jossanotus-sa kahteen kynnysanotus-sarvoonk₁ jak₂ perustuen hylätään heikkoja reunoja toisin sanoen reunoja, joissa gradientin arvo on jokaisessa pisteessä pienempi kuink₁ja säi-lytetään kaikki sellaiset reunat, joissa vähintään yhdessä pisteessä gradientin arvo on suu-rempi kuin k₂. Käytännössä siis Cannyn menetelmä sallii raja-arvon k₂ ylittävien reunojen pudota välillä raja-arvojenk₂jak₁väliin (Szeliski 2010).

3 Klusterointi

Ohjaamaton oppiminen on koneoppimisen suuntaus, jossa käytettävästä datasta haetaan yh-teyksiä ja riippuvuuksia pelkästään datasta itsestään löytyvän informaation perusteella. Klus-terointi on ohjaamattoman oppimisen tehtävä, jonka tavoitteena on ryhmitellä annettu data ominaisuuksiensa perusteella ohjatun oppimisen luokittelumenetelmistä poiketen ilman eril-listä ennakkotietoa datassa esiintyvistä luokista. Datasta siis pyritään löytämään klustereita eli osajoukkoja, joiden sisällä havainnot ovat keskenään samanlaisia ja vastaavasti erilaisia muiden osajoukkojen havaintoihin verrattuna (Hastie, Tibshirani ja Friedman 2009). Erilai-sia klusterointimenetelmiä on kehitetty useita, sillä esimerkiksi juuri sen määrittäminen mi-tä havaintojen samankaltaisuudella tarkoitetaan ei ole mi-täysin yksiselitteismi-tä. Myös se kuinka klusterit näyttäytyvät eri sovelluksissa vaihtelee huomattavasti, joten sopivan algoritmin va-linta saattaa vaikuttaa merkittävästi saataviin tuloksiin. Esimerkiksi laajasti käytössä oleva K-means-algoritmi tapaa löytää ellipsoidimaisia klustereita, mikä ei sovelluksesta riippuen välttämättä ole toivottavaa (Xu ja Wunsch 2005). Ennakkotiedon puutteesta johtuen tämän-kaltaisten ongelmien havaitseminen ei usein ole mutkatonta, näinpä tulosten validoinnin ja tulkinnan merkitys korostuu.

Klusterointimenetelmät lajitellaan usein niiden toimintaperiaatteen mukaan hierarkkisiksi, tiheyspohjaisiksi tai prototyyppipohjaisiksi. Tässä luvussa käydään lyhyesti läpi näiden eri kategorioiden perusperiaatteet ja muutamia menetelmiä. On kuitenkin hyvä huomata, että jaottelu on varsin karkea ja sisältää osin päällekkäisyyttä. Lisäksi on myös olemassa esitellyn jaottelun ulkopuolisia klusterointimenetelmiä, esimerkiksi verkkoaineistojen klusteroinnissa käytettävät spektraali- ja verkkoperusteiset menetelmät (Zaki ja Meira Jr 2014).

3.1 Samankaltaisuuden mittaaminen

Klusterointia toteuttaessa täytyy ensin määritellä, mitä tarkoitetaan datapisteiden samankal-taisuudella. Jatkuvien muuttujien tapauksessa mittaus voidaan tehdä esimerkiksi geometri-seen etäisyyteen perustuen käyttäen ns. Minkowski-etäisyyttä, joka määritellään pisteiden

x,y∈R^N välille seuraavalla kaavalla:

D_n(x,y) = (

N i=1

∑

|x_i−y_i|ⁿ)¹ⁿ. (3.1)

Yleisesti käytettyjä esimerkkejä Minkowski-etäisyydestä ovat euklidinen etäisyys, jossan= 2 ja kortteli-etäisyys (engl.City Block Distance), jossan=1. Muita vaihtoehtoja samankal-taisuuden määrittelylle jatkuvien muuttujien tapauksessa on esimerkiksi tarkastella havain-tojen korrelaatioita Pearsonin korrelaatiokertoimen avulla tai havainhavain-tojen välistä kulmaa ko-sinietäisyyden avulla (Xu ja Wunsch 2005). Diskreettien muuttujienx_i,x_j tapauksessa etäi-syydeksi voidaan määrittää

missäwon jokin sopivaksi valittu paino. Järjestysasteikollista diskreettiä muuttujaa saattaa tosin olla perusteltua käsitellä jatkuvana samankaltaisuutta laskiessa (Xu ja Wunsch 2009).

On hyvä huomata, että samankaltaisuuden laskemiseen oletetaan kussakin datapisteessä kaik-kien muuttujien olevan määritetty. Tämä ei toteudu käytännön aineistoissa kovinkaan usein, joten puuttuvien arvojen käsittely tulee ottaa huomioon jo samankaltaisuutta laskiessa. Mikä-li puuttuvia arvoja on vain harvoissa havainnoissa, voidaan ne poistaa aineistosta kokonaan.

Muussa tapauksessa puuttuvat arvot voidaan käsitellä estimoimalla niiden arvoja muuhun ai-neistoon perustuen tai asettamalla niiden vaikutus etäisyyden laskussa nollaksi (Theodoridis ja Koutroumbas 2009).

Olennaista on myös huomata, että osa etäisyysmitoista ei ole skaala-invariantteja eli ne eivät ota huomioon muuttujien kokoluokkaa. Tästä johtuen suuria arvoja saavien muuttujien mer-kitys saattaa korostua tarpeettoman paljon etäisyyttä laskiessa. Ongelmaan voidaan puuttua datan normalisoinnilla. Yleinen normalisointitapa on niin sanottu Z-pisteytys, jossa muut-tujien arvoista vähennetään niiden keskiarvo ja jaetaan ne niiden keskihajonnalla (Zaki ja Meira Jr 2014). Havainnollex_k,k∈ {1, ...,n}tämä saadaan laskettua siis kaavalla

x^stand._k =x_k−µ

ja

Näin kunkin muuttujan keskiarvoksi saadaan nolla ja keskihajonnaksi yksi, jolloin muuttu-jien väliset suhteet eivät aiheuta arvaamattomia vaikutuksia etäisyyksien laskentaan ja lopul-ta klusteroinnin tuloksiin.

3.2 Hierarkkinen klusterointi

Hierarkkiset klusterointimenetelmät toimivat joko osittavasti, jolloin alkutilanteessa kaik-kien datapisteiden ajatellaan kuuluvan samaan klusteriin tai yhdistävästi, jolloin alkutilan-teessa kaikkien datapisteiden ajatellaan kuuluvan omiin klustereihinsa (Theodoridis ja Kout-roumbas 2009). Hierarkkisissa menetelmissä täytyy määritellä vielä samankaltaisuuden mi-tan lisäksi ns. linkitysmenetelmä eli se, kuinka klusterien välinen etäisyys lasketaan. Yleises-ti käytettyjä tapoja ovat kokonaislinkitys (englComplete Linkage) ja yksittäislinkitys (engl.

Single Linkage). Kokonaislinkityksessä kahden klusterin väliseksi etäisyydeksi määritetään klusterien toisistaan kauimpana olevien havaintojen välinen etäisyys siinä, missä yksittäis-linkityksessä etäisyys määritetään lähimpien havaintojen välisenä etäisyytenä. Linkitysme-netelmässä voidaan myös käyttää klusteria kuvaamaan jotain valittua klusteriprototyyppiä eli yleensä jotain sopivaa klusterista laskettua keskilukua kuten keskiarvoa tai mediaania ja las-kea etäisyydet näiden prototyyppien perusteella. Yhdistävä menetelmä etenee yhdistämällä valitun samankaltaisuuskriteerin ja linkitysmenetelmän perusteella läheisiä klustereita niin kauan, kunnes kaikki havainnot ovat samassa klusterissa. Osittava menetelmä vastaavasti pyrkii etsimään jaettavaa klusteria esimerkiksi klusterien hajonnan tai koon perusteella. Yh-distävä menetelmä on menettelytavoista yleisempi, sillä osittava menetelmä on hankalampi toteuttaa ja yleisesti myös laskennallisesti vaativampi (Xu ja Wunsch 2005).

Hierarkkisessa klusteroinnissa klusteroinnin tulokset voidaan esittää puumaisessa dendrogram-mi-kuvaajassa. Dendrogrammissa klusteroinnin tulokset esitetään siten, että lehtisolmuissa ovat yksittäiset datapisteet ja muut solmut kuvaavat klusterien yhdistymistä tai erkaantumista (kuva 3). Klusterien etäisyys toisistaan esitetään dendrogrammissa yleensä dendrogrammin korkeutena. Dendrogrammin avulla pystytään arvioimaan, kuinka monta klusteria datassa

todellisesti on ja se on muutenkin varsin selkeä ja havainnollistava kuvaus klusteroinnin ra-kenteesta; tämä on eräs hierarkkisen klusteroinnin eduista. Hierarkkisen klusteroinnin ongel-mia taas ovat sen herkkyys datassa esiintyvälle kohinalle ja poikkeaville havainnoille. On-gelmallista hierarkkisessa klusteroinnissa on myös sen ahneus, sillä se etenee etsimällä aina jollain perusteella parhaan jako- tai yhdistymiskohdan puuttumatta aikaisemmissa vaiheissa tehtyihin virheisiin (Xu ja Wunsch 2005).