Hyppää pääsisältöön

Koronavirustilanne Itä-Suomen yliopistossa

UEFin liput.

Parempaa data-analyysiä tehokkaammilla klusterointi-menetelmillä

Viime aikoina informaation määrä ja monimutkaisuus ovat lisääntyneet voimakkaasti. Tämä hankaloittaa sen ymmärtämistä ja tehokasta käsittelyä. Klusterointi voi auttaa näissä haasteissa tuottamalla datasta tiivistelmiä tai tunnistamalla datassa olevia hahmoja. Klusterointi jaottelee datan objekteja ryhmiin niin että samaan ryhmään tulee mahdollisimman samankaltaisia objekteja. Klusteroinnilla on merkittävä rooli tutkimuksessa ja data-analyysissä. Esimerkiksi Google Scholar palvelun mukaan sana "clustering" (klusterointi) esiintyi 128 000 tutkimusartikkelissa pelkästään vuoden 2019 aikana.

K-means on yksi tunnetuimmista klusterointi-algoritmeista. Sitä käytetään laajalti monenlaisissa tietoa analysoivissa ohjelmissa. Se on sisällettynä muun muassa seuraaviin tunnettuihin ohjelmistoihin: SPSS, NCSS, SAS, STATA, R, Matlab ja CrimeStat. Huolimatta sen suuresta suosiosta, k-means -algoritmiin liittyy paljon avoimia kysymyksiä. Tiedetään, että k-means tuottaa usein epäoptimaalisia tuloksia, mutta on ollut epäselvää, että missä tilanteissa algoritmi toimii huonosti ja mikä virheitä aiheuttaa.

FM Sami Sieranoja tutki väitöstutkimuksessaan tilanteita joissa k-means epäonnistuu. Väitöskirja tarjoaa hyödyllistä tietoa k-means'in rajotteista ja näyttää kuinka algoritmin toimintaa voi parantaa. Usein oletetaan, että klusterien erillisyys helpottaa niiden tunnistamista. Väitöskirjassa osoitetaan, että k-means -algoritmin kohdalla tämä ei pidä paikkaansa vaan päinvastoin klustereiden erillisyys on yleensä merkittävin virheitä aiheuttava tekijä. Tätä menetelmän heikkoutta on kuitenkin mahdollista kompensoida käyttämällä parempaa alustusmenetelmää ja toistamalla klusterointia.

Useat klusterointialgoritmit toimivat vain pienille datajoukoille. Väitöskirjassa esitetään uusi menetelmä, joka nopeuttaa tunnetun Density Peaks algoritmin toimintaa 99 prosenttia. Tämä mahdollistaa menetelmän skaalaamisen yli miljoonan dataobjektin kokoisille aineistoille.

Nopeutus pohjautuu k lähintä naapuria -graafin (kNN graph) käyttöön. Tämä tietorakenne muodostuu yhdistämällä jokainen dataobjekti sitä lähinnä oleviin tai samankaltaisiin objekteihin datajoukossa. Väitöskirjassa esitetään kaksi uutta nopeaa menetelmää tämän rakenteen tuottamiseen. Klusteroinnin lisäksi kNN graafilla on myös monia muita sovelluksia. Esimerkiksi Spotify-sovelluksessa sitä käytetään suosittelemaan käyttäjälle samankaltaisia artisteja kuin jokin artisti jota käyttäjä on kuunnellut.

Filosofian maisteri Sami Sieranojan väitöskirja Clustering with kNN graph and k-means tarkastetaan Itä-Suomen yliopiston luonnontieteiden ja metsätieteiden tiedekunnassa 3.12. verkossa. Vastaväittäjänä toimii professori Julius Žilinskas Vilnan yliopistosta ja kustoksena professori Pasi Fränti Itä-Suomen yliopistosta. Tilaisuus on englanninkielinen.

Väittelijän painolaatuinen kuva 

Tilaisuus verkossa

Väitöskirja verkossa