Laudaturseminaari 17.3.1999 Ismo Kärkkäinen

Klusterien lukumäärän selvittäminen

Klusterointi on menetelmä saada tietoa aineiston rakenteesta. Aineisto voi olla periaatteessa mitä tahansa aina kuvan pikseleiden värikolmikoista bakteereja kuvaavaan binääridataan tai kyselyiden kauttaa saatuun aineistoon. Perusoletus kaikissa tapauksissa on että aineisto on ryhmittynyt, eli siitä voidaan löytää klustereita. Klusteroinnin suorittamiseksi on määriteltävä käytettävät etäisyysmitat, mitä kriteeriä käytetään kun lasketaan kuinka hyvin aineisto on jaettu klustereihin sekä kriteeri jota käytetään määrittämään klusterien lukumäärä. Kaksi viimeistä voivat olla sama funktio. Lisäksi aineistoa voidaan esikäsitellä ennen klusterointia (skaalaus tms.) [1, 11, 15].

Aineisto ja klusteri

Aineiston ulottuvuus voi olla periaatteessa mikä tahansa. Jos se on kaksiulotteista, niin tällöin ihminen pystyy erottamaan eri klusterit helposti. Kuitenkin usein ainesto on useampiulotteista ja tällöin on käytettävä sopivia algoritmeja. Aineiston jokaisen piirrevektorin jokainen ulottuvuus voi olla samankaltainen (esimerkiksi jos aineisto on kuvan väripisteet) tai sitten se voi vaihdella (esimerkiksi kyselyissä vastaajan ikä ja sukupuoli eivät ole samankaltaista dataa).

Klusterilla tarkoitetaan yleensä aineiston ei-tyhjää osajoukkoa ja lisävaatimuksena on että kahdella klusterilla ei ole yhteisiä pisteitä. Tästä vaatimuksesta joustetaan käyettäessä sumeaan logiikkaan perustuvia algoritmeja [11]. Klusteria voidaan kuvata laskemalla sille sentroidi, joka on esimerkiksi kaikkien klusterin pisteiden keskiarvo. Sentroidin on tarkoitus kuvata parhaiten klusterin kaikkia pisteitä ja sen ei tarvitse kuulua alkuperäiseen aineistoon. Sentroidien perusteella voidaan määrittää jako joukkoihin kuvaamalla pisteet lähimmän sentroidin edustamaan joukkoon.

Etäisyysfunktio ja aineiston sijoittelun kriteeri

Etäisyysfunktio voi olla periaatteessa mikä tahansa. Euklidinen etäisyys on usein käytetty, jos aineiston luonne sen sallii. Binäärivektoreiden ollessa kyseessä voidaan esimerkiksi laskea eroavien bittien lukumäärä ja jakaa se vektorin pituudella. Aineiston sijoittelua klustereihin voi mitata esimerkiksi keskineliövirheen avulla, eli korotetaan pisteiden etäisyydet sentroideista toiseen potenssiin ja lasketaan niiden keskiarvo. Voidaan käyttää myös keskivirhettä, mutta keskineliövirhe painottaa kaukana sentroidista olevia pisteitä, mikä on yleensä suotavaa.

Aineiston sijoittelua klustereihin on tutkittu runsaasti ja algoritmejä löytyy aina nimenomaan klusterointia varten kehitetyistä aina optimointialgoritmien sovelluksiin. Tällöin yleensä annetaan klusterien lukumäärä syötteenä, ja algoritmi muodostaa halutun määrän klustereita. Hierarkkiset algoritmit tuottavat kaikki mahdolliset klusterien lukumäärät. Muut antavat vastauksen, jossa on täsmälleen haluttu määrä klustereita.

Hierarkkisia algoritmeja käytettäessä saadaan kaikki klusterien lukumäärät. Tällöin algoritmi on joko jakava [1, 5, 11, 15] tai yhdistävä [1, 6, 11, 15]. Yhdistävä algoritmi sijoittaa ensin kaikki pisteet omiin klustereihinsa ja alkaa sitten yhdistää lähimpiä jatkaen sitä kunnes jäljellä on vain yksi klusteri. Jakava toimii päinvastaisessa järjestyksessä. Molemmilla on ongelmana se, että päätökset ovat peruuttamattomia, eli huono päätös vaikuttaa kaikkiin myöhemmin tehtäviin päätöksiin.

Muista algoritmeista on yksinkertaisin yleistetty Lloydin algoritmi (GLA), joka soveltuu parhaiten ratkaisujen hienosäätöön [3, 4]. Siinä luodaan vuorotellen sentroidien perusteella jako osajoukkoihin ja osajoukkojen perusteella sentroidit. Algoritmi kovergoituu nopeasti lähimpään lokaaliin minimiin. Tästä johtuu että se ei yksinään anna kovin hyviä tuloksia ellei alkuratkaisuja luoda suurta joukkoa.

Optimointialgoritmeja on myös sovellettu klusterointiongelmaan. Esimerkiksi geneettiset algoritmit (GA) [3] antavat hyviä tuloksia, mutta ovat hitaita. Optimointialgoritmit [2, 4, 7, 8] luovat tavallisesti suuren joukon ratkaisuja ja näiden läpikäynti vie aikaa. Lisäksi jos niissä käytetään ratkaisujen hienosäätöön GLA:ta, joka läpikäy kaikki sentroidi/piste -parit muodostatessaan uusia osajoukkoja, niin ne toimivat vielä hitaammin. Fränti ja Kivijärvi ovat kehittäneet lokaalihausta version [8] joka antaa verrattain hyviä tuloksia ja on nopeampi kuin GA.

Klustereiden lukumäärä

Useinkaan ei tunneta aineiston klusterien lukumäärää. Joissain tapauksissa sillä ei ole väliä, kuten luotaessa kuvalle palettia, jolloin halutaan käyttää kaikki 256 väriä. Tavallisesti klusterien lukumäärän selvittäminen on olennainen osa ongelmaa. Esimerkiksi numeerisessa taksonomiassa klusteren lukumäärä ilmaisee aineiston lajien tai alalajien lukumäärän. Tällöin se voi olla tärkeämpi osa ratkaisua kuin aineiston jako klustereihin. Huomautettakoon että pelkkä aineiston sijoittelun hyvyyttä mittaava kriteeri ei yksistään kelpaa klustereiden lukumäärän arviointiin, koska keski(neliö)virheen arvo pienenee sitä mukaa kun klustereita lisätään. Eli toisin sanoen jos lisätään yksi klusteri ja vastaava sentroidi, niin osa aineistosta on lähempänä tätä uutta sentroidia kuin entistä ja näinollen virhefunktion arvo pienenee.

Lukumäärän ratkaisemiseen tarvitaan siis ensiksikin evaluointifunktio, joka huomioi klustereiden lukumäärän jollain tavoin ja sen lisäksi aineiston sijoittelun klustereihin. Pääosin evaluointifunktiot muodostuvat osista, joista toinen pienenee klusterien lukumäärän kasvaessa ja toinen kasvaa. Seuraavaksi kuvataan lyhyesti kaksi. Muitakin tapoja on olemassa [12]. Lisäksi on päätettävä kuinka käyttää näitä algoritmeissa.

Stokastinen kompleksisuus

Stokastinen kompleksisuus [4, 9, 10, 13] mittaa mallin ja sen avulla esitetyn aineiston esittämiseen tarvittavien bittien lukumäärää. Sitä on käytetty esimerkiksi bakteerien luokitteluun. Rissasen [13] mukaan paras malli joka selittää annetun aineston on juuri se, jossa mallin ja aineiston esittämiseen tarvitaan vähiten bittejä. Mallista on käytänössä tiedettävä esimerkiksi muuttujien jakaumat (esimerkiksi ovatko klustereissa pisteet jakautuneet tasaisesti vai normaalijakauman mukaisesti), jotta voitaisiin johtaa tarvittava kaava stokastisen kompleksisuuden laskemiseksi. Jos jakaumat ovat ennalta tiedossa, ongelmaa ei ole, mutta jos niitä ei tiedetä tai vaihtoehtoja on useita, niin jakauman löytäminen on osa ongelmaa. Gyllenberg et al. [10] osoittaa kuinka käyttää stokastista kompleksisuutta binäärivektorien luokitteluun. Koska samalla pyritään määrittämään malli, joka kuvaa aineistoa, voidaan sitä käyttää myöhemmin ennustamiseen, eli saavutetaan tietty etu suhteessa sellaisiin evaluointifunktioihin, jotka vain mittaavat kuinka hyvin aineisto on jaettu klustereihin.

Mallin kuvaamiseen kuluu sitä enemmän bittejä mitä monimutkaisempi se on. Malli määrää, kuinka monta klustereita on ja kuinka aineisto jakautuu klustereissa. Aineiston kuvaamiseen suhteessa malliin kuluu sitä vähemmän bittejä mitä yksityiskohtaisempi malli on. Samoin on ilmoitettava, mihin klusteriin kukin piste kuuluu. Koska mallin monimutkaistuttua tietyn pisteen ohitse ei saaavuteta enää vastaavaa säästöä aineiston kuvaamisessa, saavutetaan jossain kohtaa minimi. Keski(neliö)virheestä poiketen tätä minimiä ei saavuteta, jos klustereiden lukumäärä on sama kuin aineiston koko, koska tällöin mallista on tullut erittäin yksityiskohtainen.

Davies-Bouldinin indeksi

Davies-Bouldinin indeksin [14] avulla mitataan klusterijoukon klustereiden sisäistä hajontaa ja klustereiden välistä hajontaa (dispersion). Perusidea on yksinkertainen: mitä suurempi klusteri on, sitä huonompi se on ja mitä lähempänä kaksi klusteria on toisiaan, sitä huonompi jako on. Kriteeri perustuu sentroidien käyttöön. Klusterien välinen etäisyys tulkitaan niiden sentroidien väliseksi etäisyydeksi. Samoin klusterin hajonta on sen jäsenten etäisyyksien neliösumma sentroidista. Jokaiselle klusterille lasketaan sen sisäinen hajonta. Jokaiselle klusterille etsitään maksimi arvolle, joka saadaan laskemalla klustereiden hajonnat yhteen ja jakamalla niiden välisellä etäisyydella. Indeksi on näiden maksimien keskiarvo.

Kun klusterien lukumäärä kasvaa, niin keskiarvo ei tietyn pisteen jälkeen enää pienene. Tällöin klusterien väliset etäisyydet muodostuvat niin suuriksi hajontaan nähden, että ne alkavat lähestyä pientenkin hajoamien summaa, jolloin keskiarvo kasvaa. Näin voi käydä esimerkiksi jos klusteri on jaettu kahtia, jolloin molemmat sentroidit pyrkivät siirtymään kohti klusterin kekustaa ja samalla toisiaan. On huomattava, että kun klusterien lukumäärä lähestyy pisteiden lukumäärää, niin summaan alkaa ilmaantua termejä joiden osoittaja on nolla, joten tämä kriteeri on käyttökelpoinen vain tietyllä klusterien lukumäärän alueella. Kuitenkin jos klusterien lukumäärä lähestyy pisteiden lukumäärää, voidaan kysyä, onko tällöin enää kyseessä klusteri, jos keskimääräinen pisteiden lukumäärä klusterissa lähestyy yhtä.

Lukumäärän huomiointi algoritmeissa

Koska hierarkkisissa menetelmissä kaikki lukumäärät saadaan sivutuotteena, voidaan näistä valita paras evaluoimalla saatuja ratkaisuja. Myös ratkaisun laskemista voidaan ohjata, eli jos tiedetään evaluointifunktiolla olevan yksi minimi, niin lopetetaan eteneminen kun evaluointifunktion arvo huononee. Käytännössä ei voida taata että evaluointifunktiolla olisi vain yksi minimi.

Yksinkertaisin tapa on laskea ratkaisut kaikille klusterien määrille tietyllä välillä ja arvioida evaluointifunktiolla nämä kaikki. Kuitenkin koska klusterointialgoritmit eivät ole erityisen nopeita, niin tämä kasvattaa suoritusaikaa entisestään, varsinkin suurella aineistolla, jos ei kyetä rajoittamaan klusterien lukumäärää riittävästi. Lisäksi mikään ei takaa, että paras mahdollinen tulos todella saadaan joillakin lasketuista ratkaisuista. Näin saatu tulos on periaatteessa ainakin yhtä hyvä kuin hierarkkisella menetelmällä saatu, joskin paremmat ratkaisut saadaan suoritusajan kustannuksella.

Kolmas mahdollisuus on muokata algoritmia niin, että klusterien lukumäärä voi vaihdella suorituksen edetessä. Tällöin voidaan lähteä esimerkiksi yhdestä klusterista ja lisätä kunnes päädytään evaluointifunktion minimiin (tai maksimiin, riippuu funktiosta). Vaihtoehtoisesti voidaan antaa klusterien lukumäärän vaihdella ja toivoa, että se asettuu oikeaan kohtaan. Geneettisessä algoritmissa vaihtelu on helppo toteuttaa esimerkiksi risteytyksen tai mutaation yhteydessä. Voidaan joko sallia eri risteytyskohdat jolloin tulokset ovat eripituisia kuin ne joista ne risteytettiin tai mutaation avulla voidaan poistaa tai lisätä klusteri. Geneettisen algoritmin tapauksessa ei välttämättä käy niin, että vaadittu aika kasvaa kokeiltavien klustereiden lukumäärien suhteessa, koska täysin vääriä lukumääriä sisältävät ratkaisut voivat karsiutua pois ja näin päästään nopeammin keskittymään parhaisiin klusterien lukumääriin.

Muita menetelmiä käytettäessä voidaan joko luottaa siihen, että evaluointifunktiolla on yksi minimi ja yhdestä lähtien kasvatetaan klusterien lukumäärää kunnes voidaan päätellä minimin ohitetun. Vaihtoehtoisesti jos tiedetään algoritmin antavan tasalaatuisia ratkaisuja, voidaan laskea ratkaisut esimerkiksi kymmenen klusterin välein ja sitten pienentää tutkittavaa väliä ja klusterien lukumäärän muutosta kunnes väli on tarpeeksi pieni, jotta voidaan tarkistaa kaikki mahdollisuudet. Tämä ei käy päinsä jos on odotettavissa että algoritmi antaa peräkkäisille klusterien lukumäärille suuresti toisistaan poikkeavia tuloksia. Lisäksi on suotavaa, että käytettävä algoritmi voi suhteellisen nopeasti laskea hyvän tuloksen yhdelle klusterien lukumäärälle, koska sitä joudutaan toistamaan ja tämä kasvattaa suoritusaikaa helposti.

Viitteitä:

  1. B.S. Everitt: Cluster Analysis, 3rd edition, Edward Arnold, ISBN 0 340 584793
  2. P. Fränti, J. Kivijärvi and O. Nevalainen, "Tabu search algorithm for codebook generation in VQ", Pattern Recognition, 31 (8), 1139-1148, August 1998.
  3. P. Fränti, J. Kivijärvi, T. Kaukoranta and O. Nevalainen, "Genetic algorithms for large scale clustering problems", The Computer Journal, 40 (9), 547-554, 1997.
  4. P. Fränti, H.H. Gyllenberg, M. Gyllenberg, J. Kivijärvi, T. Koski, T. Lund and O. Nevalainen, "Minimizing stochastic complexity using GLA and tabu search with applications to classification of bacteria", Research Report A17, Univ. of Turku, Dept. of Applied Math, 1997.
  5. P. Fränti, T. Kaukoranta, O. Nevalainen: On the Splitting Method for Vector Quantization Codebook Generation Optical Engineering 36 (11) 3043-3051
  6. P. Fränti and T. Kaukoranta, "Fast implementation of the optimal PNN method", Proc. IEEE Int. Conf. on Image Processing (ICIP-98), Chicago, Illinois, USA, 1998.
  7. P. Fränti, J. Kivijärvi: Local Search Algorithm for the Clustering Problem submitted to Pattern Recognition
  8. P. Fränti and J. Kivijärvi, "Random swapping technique for improving clustering in unsupervised classification", Proc. 11th Scandinavian Conf. on Image Analysis (SCIA-99), Kangerlussuaq, Greenland, 1999. (to appear)
  9. H.G. Gyllenberg et al.: Classification of Enterobacteriaceae by Minimization of Stochastic Complexity Microbiology (1997), 143, 721-732
  10. M. Gyllenberg, T. Koski and M. Verlaan: Classification of binary vectors by stochastic complexity, Journal of Multivariate Analysis, 63 (1), 47-72 (1997).
  11. L. Kaufman, P.J.Rousseeuw: Finding Groups in Data: An Introduction to Cluster Analysis, John Wiley & Sons, Inc. ISBN 0-471-87876-6
  12. R. Peck, L. Fisher, J. van Ness: Approximate Confidence Intervals for the Number of Clusters Journal of the American Statistical Asociation March 1989, 84 No. 405 184-191
  13. J. Rissanen: Stochastic Complexity Journal of Royal Statistical Society B (1987) 49 (3) pp 223-239 and 252-265
  14. M. Sarkar, B. Yegnanarayana, D. Khemani: A Clustering Algorithm Using an Evolutionary Programming -Based Approach Pattern Recognition Letters 18 (1997) 975-986
  15. H. Späth: Cluster Analysis Algorithms for Data Reduction and Classification of Objects, Ellis Horwood Limited, ISBN 0-85312-141-9