Klusterointi käyttäen EM-algoritmia
Vilmi, Hannes (2017-11-23)
H. Vilmi
23.11.2017
© 2017 Hannes Vilmi. Tämä Kohde on tekijänoikeuden ja/tai lähioikeuksien suojaama. Voit käyttää Kohdetta käyttöösi sovellettavan tekijänoikeutta ja lähioikeuksia koskevan lainsäädännön sallimilla tavoilla. Muunlaista käyttöä varten tarvitset oikeudenhaltijoiden luvan.
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:oulu-201711243169
https://urn.fi/URN:NBN:fi:oulu-201711243169
Tiivistelmä
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.
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.
Kokoelmat
- Avoin saatavuus [29998]