JultikaUniversity of Oulu repository

Klusterointi on joukko menetelmiä, joilla yritetään jakaa havaittu data tulkinnan kannalta mielekkäisiin luokkiin, tai klustereihin, ilman, että saatavilla on erillistä opetusdataa. Jotta tämä klusterointi on mahdollista, tulee datapisteiden välisiä eroja ja samankaltaisuuksia kyetä mittamaan kuhunkin tilanteeseen soveltuvalla tavalla. Myös mahdollisesti puutteellisten mittaustulosten oikeanlainen käsittely on tärkeää. Klusterointi havaitulle datalle pyritään saamaan aikaiseksi monilla erilaisilla menettelyillä, jotka mittaavat datapisteiden samankaltaisuutta ja pyrkivät sijoittamaan mahdollisimman samankaltaiset datapisteet klustereihin siten, että niiden pohjalta kyetään tekemään päätelmiä kuhunkin klusteriin kuuluvasta datasta. Yksi tapa lähestyä tätä ongelmaa on tarkastella sitä sekoitemalliongelmana, jolloin suosittu tapa datan klusteroinnille on soveltaa EM-algoritmia, joka estimoi suurimman uskottavuuden estimaatin sekoitemallille maksimoimalla mallin logaritmista tiheysfunktiota. Tämä algoritmi pyrkii tähän iteroimalla vuoron perään askelia, joita kutsutaan nimillä Expectation- ja Maximization -step. Ensimmäisessä näistä lasketaan odotusarvo logaritmiselle tiheysfunktiolle ja jälkimmäisessä pyritään maksimoimaan se sekoitemallin parametrien suhteen. Algoritmista on myös määritelty yleistetty versio, jossa maksimoinnin sijasta kasvatetaan logaritmisen tiheysfunktion arvoa jokaisella iteraatiolla, kun maksimointia ei ole mahdollista tai laskennallisesti tehokasta suorittaa. Kumpikaan näistä algoritmeista ei tavallisissa sovellutuksissa takaa varmaa konvergenssia logaritmisen tiheysfunktion globaaliin tai edes lokaaliin maksimiin, vaan sen sijaan on mahdollista päätyä satulapisteeseen. Näiden konvergenssiongelmien vuoksi algoritmia soveltaessa on tärkeää kiinnittää huomiota alkuarvojen valintaan. Tähän pyritään esimerkiksi suorittamalla algoritmille monta aloitusta pienellä iteraatiomäärällä, joista parhaan tulos valitaan, ja käyttämällä k-Means nimistä klusterointialgoritmia alkuarvojen valitaan.