University of Oulu

Klusterointi käyttäen EM-algoritmia

Saved in:
Author: Vilmi, Hannes1
Organizations: 1University of Oulu, Faculty of Science, Mathematics
Format: ebook
Version: published version
Access: open
Online Access: PDF Full Text (PDF, 0.7 MB)
Persistent link: http://urn.fi/URN:NBN:fi:oulu-201711243169
Language: Finnish
Published: Oulu : H. Vilmi, 2017
Publish Date: 2017-11-25
Physical Description: 66 p.
Thesis type: Master's thesis
Tutor: Ruha, Leena
Reviewer: Laitinen, Erkki
Ruha, Leena
Description:

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.

see all

Subjects:
Copyright information: © Hannes Vilmi, 2017. This publication is copyrighted. You may download, display and print it for your own personal use. Commercial use is prohibited.