Ositetut kapasitoidut klusterointimenetelmät lokaatio-allokaatio ongelmissa

Klusterointi on yksi tärkeimmistä ja yleisimmin käytetyistä työkaluista datan analysoimisessa. Useimmiten sitä käytetään havaintojen jakamiseen ryhmiin siten, että ryhmään kuuluvat havainnot ovat samankaltaisia. Tämänkaltaista osittavaa klusterointimenetelmää käytetään monissa sovelluskohteissa ja yksi näistä sovelluskohteista on lokaatio-allokaatio ongelmat. Lokaatio-allokaatio viittaa optimointiongelmajoukkoon, jossa tavoitteena on sijoittaa keskuksia kartalle siten, että etäisyydet kyseisistä keskuksista ja datapisteistä minimoidaan. Esimerkiksi kierrätyspisteiden sijoittaminen kaupunkialueelle on eräänlainen lokaatio-allokaatio ongelma, jossa tulee ottaa huomioon se kuinka kaukana kierrätyspisteet ovat asutuksesta ja se kuinka paljon yksi kierrätyspiste pystyy käsittelemään roskia.


Väitöskirja yhdistää osittavan klusteroinnin ja lokaatio-allokaatio ongelmat. Erityisesti väitöskirja keskittyy rajoitteisiin ja sakkotermeihin, jotka esiintyvät monissa lokaatio-allokaatio ongelmissa. Yksi merkittävä ja useasti käytetty rajoite kirjallisuudessa on keskusten kapasiteettien rajoittaminen. Vastaavasti klusteroinnissa tämä viittaa klusterikoon rajoittamiseen, ja niistä käytetään nimitystä osittavat kapasitoidut klusterointimenetelmät.

Kapasiteettirajojen lisäksi tämä väitöskirja esittää lukuisia laajennoksia klusterointimenetelmään, jotka juontavat juurensa lokaatio-allokaatio sovelluskohteista. Näihin kuuluvat muun muassa erilaiset etäisyysfunktiot, rajoitteet klusterikeskusten sijainteihin, erilaiset klusteriassosiaatiot datapisteille, ulkopuolisten havaintojen havaitseminen ja klusterien määrään liittyvät sakkotermit. Tämän lisäksi väitöskirja tarkastelee yhteyttä mallipohjaiseen klusterointiin, jossa tilastollista mallia sovelletaan lokaatio-allokaatio ongelmiin. Tämän avulla voidaan tuoda uudenlaisia näkökulmia menetelmäkehikkoon, kuten esimerkiksi tilastollisen mallin parametreille saatu todennäköisyystulkinta. Väitöskirja esittelee myös optimointialgoritmin ja ohjelmistotyökalun tämän tyylisten ongelmien ratkaisuun.