Mukautuva k-medoidiklusterointi ja valinnan jälkeinen päättely

Abstract

Tässä pro gradu -tutkielmassa tutkitaan ohjaamattoman oppimisen k-medoidimenetelmää ja erityisesti sen mukautuvaa BanditPAM-algoritmia. Alustusvaiheen odotusarvoinen kokonaisvaativuus on O(k n log n), sillä k alustusaskeleesta kukin vaatii odotusarvoisesti O(n log n) operaatiota. Myös vaihtovaiheen iteraation odotusarvoinen aikavaativuus on O(k n log n). Tulos saavutetaan soveltamalla monikätisten rosvojen viitekehystä ja yläluottamusrajoihin perustuvaa peräkkäistä eliminointia. Asymptoottisessa notaatiossa n edustaa havaintojen ja k klusterien lukumäärää. Aineistolähtöinen mallinvalinta altistaa kuitenkin tulokset valikoitumisharhalle, mikä vääristää nollajakaumia frekventistisessä päättelyssä ja kasvattaa ensimmäisen tyypin virheen todennäköisyyttä.

Tutkielmassa arvioidaan, miten valikoitumisharhaa korjataan analyyttisesti valinnan jälkeisen päättelyn ja monitahokaslemman avulla. Tilastollista todistusvoimaa tarkastellaan Deborah Mayon ankaruusperiaatteen sekä Aris Spanoksen todennäköisyyspohjaisen pelkistämisen viitekehyksissä. Työn empiirisessä osiossa algoritmin ja analyyttisen korjauksen taustaoletuksia auditoidaan synteettisillä (normaalijakauma, Cauchyn jakauma, Studentin t-jakauma) sekä korkeaulotteisilla biologisilla yksisolutranskriptomiikan aineistoilla. Tutkielman tieteellinen kontribuutio on kaksiosainen. Ensimmäisenä kontribuutiona osoitetaan matemaattisesti ja empiirisesti, kuinka paksuhäntäisten aineistojen äärihavainnot vääristävät havaintoavaruuden mittasuhteita, mikä tekee mukautuvan otannan UCB-luottamusrajat liian leveiksi tehokasta karsintaa varten. Toisena metodologisena kontribuutiona tutkielma kytkee valinnan jälkeisen päättelyn polytooppikehyksen BanditPAM-algoritmin SWAP-vaiheeseen. Yliehdollistamista ehkäistään soveltamalla lokaalia seulontaa, joka yhdistää eksaktin teorian voittaja/toiseksi tullut -asetelman heuristiseen approksimaatioon ja parantaa siten testin tilastollista voimaa.

Empiiriset tulokset osoittavat mukautuvissa k-medoidialgoritmeissa rakenteellisia rajoitteita. BanditPAM-algoritmin laskennallinen tehokkuus nojaa kapeisiin luottamusväleihin: paksuhäntäisillä aineistoilla yksittäiset äärihavainnot kasvattavat etäisyysmatriisin maksimiarvoa suhteettomasti. Yläluottamusrajoihin perustuva karsinta menettää tällöin käytännön tehokkuutensa, jolloin aikavaativuus palautuu neliölliselle O(k n²)-tasolle. Toinen merkittävä löydös kytkeytyy robustin tilastotieteen murtumispisteen teoriaan. Kun aineisto on paksuhäntäinen, yksittäiset äärihavainnot dominoivat etäisyysmatriisia deterministisesti. Oikein suoritettu bootstrap-analyysi paljastaa näiden rakenteiden epävakauden, sillä äärihavaintoihin nojaavat klusterit hajoavat otannan vaihdellessa. Algoritminen stabiilisuus on siten välttämätön, muttei riittävä ehto klusteroinnin validiteetille. Hajoamismekanismit osoittavat, että valinnan jälkeisen päättelyn analyyttiset menetelmät menettävät tilastollisen validiteettinsa ja robustiutensa, mikäli aineisto on spesifioitu virheellisesti. Ilmiö johtuu siitä, että menetelmät nojaavat vahvoihin parametrisiin oletuksiin. Näissä ääriolosuhteissa luotettava tilastollinen päättely edellyttää joko aineiston jakamista tai jakaumavapaita, algoritmiseen stabiilisuuteen perustuvia menetelmiä. Algoritmiseen stabiilisuuteen perustuva päättely tarjoaa ratkaisun ainoastaan niissä tapauksissa, joissa aineisto rikkoo normaalisuusoletuksen mutta täyttää edelleen stabiilisuustakuiden edellyttämät momenttiehdot.