Clustering Algorithms: From Start To State Of The Art

Ei ole huono aika olla datatieteilijä. Vakavat ihmiset saattavat kiinnostua sinusta, jos käännät keskustelun kohti ”Big Dataa”, ja muu juhlaväki kiinnostuu, kun mainitset ”tekoälyn” ja ”koneoppimisen”. Jopa Google on sitä mieltä, että et ole huono ja että olet tulossa vielä paremmaksi. On olemassa paljon ”älykkäitä” algoritmeja, jotka auttavat datatieteilijöitä tekemään taikojaan. Kaikki voi tuntua monimutkaiselta, mutta jos ymmärrämme ja järjestelemme algoritmeja hieman, ei ole edes kovin vaikeaa löytää ja soveltaa tarvitsemaamme algoritmia.

Datanlouhintaa tai koneoppimista käsittelevät kurssit aloitetaan yleensä klusteroinnista, koska se on sekä yksinkertainen että hyödyllinen. Se on tärkeä osa hieman laajempaa valvomattoman oppimisen aluetta, jossa dataa, jota haluamme kuvata, ei ole merkitty. Useimmiten kyse on tilanteista, joissa käyttäjä ei ole antanut meille paljon tietoa siitä, mitä tulosta odotetaan. Algoritmilla on vain data, ja sen pitäisi tehdä parhaansa. Meidän tapauksessamme sen pitäisi suorittaa klusterointi – datan jakaminen ryhmiin (klustereihin), jotka sisältävät samankaltaisia datapisteitä, kun taas ryhmien välinen eroavuus on mahdollisimman suuri. Tietopisteet voivat edustaa mitä tahansa, kuten asiakkaitamme. Klusterointi voi olla hyödyllistä, jos haluamme esimerkiksi ryhmitellä samankaltaisia käyttäjiä ja sitten suorittaa erilaisia markkinointikampanjoita kullekin klusterille.

K-Means Clustering

Tarvittavan johdannon jälkeen Data Mining -kurssit jatkuvat aina K-Meansilla; tehokkaalla, laajalti käytetyllä, monipuolisella klusterointialgoritmilla. Ennen sen varsinaista suorittamista meidän on määriteltävä datapisteiden välinen etäisyysfunktio (esimerkiksi euklidinen etäisyys, jos haluamme klusteroida pisteitä avaruudessa) ja asetettava haluamiemme klustereiden lukumäärä (k).

Algoritmi alkaa valitsemalla k pistettä lähtökeskipisteiksi (”klustereiden keskipisteiksi”). Voimme valita mitä tahansa k satunnaispistettä, tai voimme käyttää jotain muuta lähestymistapaa, mutta satunnaispisteiden valitseminen on hyvä alku. Sitten toistamme iteratiivisesti kaksi vaihetta:

1. Asijoitusvaihe: jokainen m pistettä aineistostamme osoitetaan klusteriin, jota edustaa lähin k:sta keskipisteestä. Kullekin pisteelle lasketaan etäisyydet kuhunkin keskipisteeseen ja yksinkertaisesti valitaan vähiten kaukana oleva.

2. Päivitysvaihe: Kullekin klusterille lasketaan uusi keskipiste, joka on klusterin kaikkien pisteiden keskiarvo. Edellisestä vaiheesta meillä on joukko pisteitä, jotka on määritetty klusteriin. Nyt jokaiselle tällaiselle joukolle lasketaan keskiarvo, jonka julistamme klusterin uudeksi keskipisteeksi.

Kunkin iteraation jälkeen keskipisteet liikkuvat hitaasti, ja kunkin pisteen kokonaisetäisyys sille osoitettuun keskipisteeseen pienenee ja pienenee. Näitä kahta vaihetta vuorotellaan, kunnes saavutetaan konvergenssi, eli kunnes klusterin määrityksessä ei enää tapahdu muutoksia. Useiden iteraatioiden jälkeen sama pistejoukko osoitetaan kullekin keskipisteelle, mikä johtaa jälleen samoihin keskipisteisiin. K-Meansin on taattu konvergoituvan paikalliseen optimiin. Sen ei kuitenkaan välttämättä tarvitse olla paras kokonaisratkaisu (globaali optimi).

Lopullinen klusterointitulos voi riippua alkukeskipisteiden valinnasta, joten tätä ongelmaa on pohdittu paljon. Yksi yksinkertainen ratkaisu on vain ajaa K-Means pari kertaa satunnaisilla alkukeskiöillä. Voimme sitten valita parhaan tuloksen ottamalla sen, jonka etäisyyksien summa kustakin pisteestä sen klusteriin on pienin – virhearvo, jota yritämme alun perin minimoida.

Muut lähestymistavat alkupisteiden valintaan voivat luottaa siihen, että valitaan kaukaisia pisteitä. Tämä voi johtaa parempiin tuloksiin, mutta meillä voi olla ongelma outlierien kanssa, niiden harvinaisten yksinään olevien pisteiden kanssa, jotka ovat vain ”pielessä”, jotka saattavat olla vain joitakin virheitä. Koska ne ovat kaukana mistään mielekkäästä klusterista, jokainen tällainen piste voi päätyä omaksi ”klusterikseen”. Hyvä tasapaino on K-Means++ -muunnos , jonka alustus valitsee edelleen satunnaisia pisteitä, mutta todennäköisyydellä, joka on verrannollinen neliöetäisyyteen aiemmin määritetyistä keskipisteistä. Pisteillä, jotka ovat kauempana, on suurempi todennäköisyys tulla valituksi aloituskeskipisteiksi. Näin ollen, jos on ryhmä pisteitä, myös todennäköisyys, että piste ryhmästä valitaan, kasvaa, kun niiden todennäköisyydet summautuvat, mikä ratkaisee mainitsemamme outlier-ongelman.

K-Means++ on myös Pythonin Scikit-learnin K-Means-toteutuksen oletusinitialisointi. Jos käytät Pythonia, tämä voi olla valitsemasi kirjasto. Javalle Weka-kirjasto voi olla hyvä aloitus:

Java (Weka)

// Load some dataInstances data = DataSource.read("data.arff");// Create the modelSimpleKMeans kMeans = new SimpleKMeans();// We want three clusterskMeans.setNumClusters(3);// Run K-MeanskMeans.buildClusterer(data);// Print the centroidsInstances centroids = kMeans.getClusterCentroids();for (Instance centroid: centroids) { System.out.println(centroid);}// Print cluster membership for each instancefor (Instance point: data) { System.out.println(point + " is in cluster " + kMeans.clusterInstance(point));}

Python (Scikit-learn)

> >> from sklearn import cluster, datasets> >> iris = datasets.loadiris()> >> Xiris = iris.data> >> yiris = iris.target> >> kmeans = cluster.KMeans(nclusters=3)> >> kmeans.fit(Xiris)KMeans(copy_x=True, init='k-means++', ...> >> print(kmeans.labels)> >> print(yiris)

Ylläolevassa Python-esimerkissä käytimme vakiomuotoista esimerkkitietokantaa ’Iris’, joka sisältää kukkien terälehdet ja verholehdet kolmelle eri iirislajille. Klusteroimme nämä kolmeen klusteriin ja vertasimme saatuja klustereita todellisiin lajeihin (kohteeseen) nähdaksemme, että ne sopivat täydellisesti yhteen.

Tässä tapauksessa tiesimme, että klustereita (lajeja) oli kolme erilaista, ja K-Means tunnisti oikein, mitkä niistä kuuluvat yhteen. Mutta miten valitsemme yleisesti ottaen hyvän klusterien määrän k? Tällaiset kysymykset ovat varsin yleisiä koneoppimisessa. Jos pyydämme useampia klustereita, ne ovat pienempiä, ja siksi kokonaisvirhe (pisteiden ja niille määritettyjen klustereiden välisten etäisyyksien summa) on pienempi. Onko siis hyvä idea vain asettaa suurempi k? Saatamme päätyä siihen, että k = m, eli jokainen piste on oma keskipisteensä, ja kussakin klusterissa on vain yksi piste. Kyllä, kokonaisvirhe on 0, mutta emme saaneet yksinkertaisempaa kuvausta aineistostamme, eikä se ole tarpeeksi yleinen kattamaan joitakin uusia pisteitä, joita saattaa ilmaantua. Tätä kutsutaan ylisovittamiseksi, emmekä halua sitä.

Tapa käsitellä tätä ongelmaa on sisällyttää jokin rangaistus suuremmasta klusterien määrästä. Yritämme siis nyt minimoida paitsi virheen, myös virheen + rangaistuksen. Virhe vain konvergoi kohti nollaa, kun lisäämme klusterien määrää, mutta rangaistus kasvaa. Jossain vaiheessa toisen klusterin lisäämisestä saatava hyöty on pienempi kuin käyttöön otettu rangaistus, ja saamme optimaalisen tuloksen. Ratkaisu, joka käyttää Bayesin informaatiokriteeriä (BIC, Bayesian Information Criterion) tähän tarkoitukseen, on nimeltään X-Means .

Toinen asia, joka meidän on määriteltävä oikein, on etäisyysfunktio. Joskus se on suoraviivainen ja looginen tehtävä, kun otetaan huomioon datan luonne. Pisteille avaruudessa euklidinen etäisyys on ilmeinen ratkaisu, mutta se voi olla hankalaa eri ”yksiköiden” piirteille, diskreeteille muuttujille jne. Tämä saattaa vaatia paljon aluetuntemusta. Voimme myös pyytää apua koneoppimisesta. Voimme itse asiassa yrittää oppia etäisyysfunktion. Jos meillä on harjoitusjoukko pisteitä, joista tiedämme, miten ne pitäisi ryhmitellä (eli pisteet on merkitty klustereillaan), voimme käyttää valvotun oppimisen tekniikoita löytääksemme hyvän funktion ja soveltaa sitä sitten kohdejoukkoomme, jota ei ole vielä klusteroitu.

K-Means-menetelmässä käytetty menetelmä kahdella vuorottelevalla askeleella muistuttaa EM-menetelmää (Expectation-Maximization). Itse asiassa sitä voidaan pitää hyvin yksinkertaisena versiona EM:stä. Sitä ei kuitenkaan pidä sekoittaa monimutkaisempaan EM-klusterointialgoritmiin, vaikka sillä onkin joitakin samoja periaatteita.

EM-klusterointi

K-Means-klusteroinnissa siis jokainen piste luokitellaan vain yhteen klusteriin, ja klusteria kuvaa vain sen keskipiste. Tämä ei ole kovin joustavaa, sillä meillä voi olla ongelmia päällekkäisten klustereiden tai sellaisten klustereiden kanssa, jotka eivät ole ympyränmuotoisia. EM-klusteroinnin avulla voimme nyt mennä askeleen pidemmälle ja kuvata kutakin klusteria sen keskipisteen (keskiarvo), kovarianssin (jotta voimme saada elliptisiä klustereita) ja painon (klusterin koko) avulla. Todennäköisyys, että piste kuuluu johonkin klusteriin, annetaan nyt monimuuttujaisen Gaussin todennäköisyysjakauman avulla (monimuuttujainen – riippuu useista muuttujista). Tämä tarkoittaa myös sitä, että voimme laskea todennäköisyyden sille, että piste on Gaussin ”kellon” alla, eli todennäköisyyden sille, että piste kuuluu johonkin klusteriin.

Aloitamme nyt EM-proseduurin laskemalla kullekin pisteelle todennäköisyydet sille, että se kuuluu kuhunkin kulloinkin käytössä olevaan klusteriin (jotka taasen voivat olla alussa satunnaisesti luotuja). Tämä on E-vaihe. Jos jokin klusteri on todella hyvä ehdokas pisteelle, sen todennäköisyys on lähellä yhtä. Kaksi tai useampi klusteri voi kuitenkin olla hyväksyttäviä ehdokkaita, joten pisteellä on todennäköisyysjakauma klustereille. Tätä algoritmin ominaisuutta, että pisteet eivät kuulu rajoitetusti yhteen klusteriin, kutsutaan ”pehmeäksi klusteroinniksi”.

M-askel laskee nyt jokaisen klusterin parametrit uudelleen käyttäen pisteiden kohdistuksia edelliseen klusterijoukkoon. Klusterin uuden keskiarvon, kovarianssin ja painon laskemiseksi kutakin pistedataa painotetaan sen todennäköisyydellä kuulua klusteriin, joka on laskettu edellisessä vaiheessa.

Vaihtelemalla näitä kahta vaihetta lisätään log-likelihoodin kokonaismäärää, kunnes se konvergoi. Jälleen kerran maksimi voi olla paikallinen, joten voimme ajaa algoritmin useita kertoja saadaksemme parempia klustereita.

Jos nyt haluamme määrittää jokaiselle pisteelle yhden klusterin, voimme yksinkertaisesti valita todennäköisimmän. Kun meillä on todennäköisyysmalli, voimme käyttää sitä myös samankaltaisen datan tuottamiseen, eli ottaa lisää pisteitä, jotka ovat samankaltaisia kuin havaitsemamme data.

Affiniteettipropagointi

Affiniteettipropagointi (AP, Affinity Propagation) julkaistiin Frey:n ja Dueck:n toimesta vuonna 2007, ja se on yhä suositumpi yksinkertaisuutensa, yleisen sovellettavuutensa ja suorituskykynsä vuoksi. Se on muuttamassa asemaansa state of the artista de facto standardiksi.

K-Meansin ja vastaavien algoritmien suurimmat haitat ovat klusterien lukumäärän valitseminen ja alkupistejoukon valinta. Affinity Propagation sen sijaan ottaa syötteenä datapisteparien välisen samankaltaisuuden mittaukset ja pitää samanaikaisesti kaikkia datapisteitä potentiaalisina esimerkkeinä. Datapisteiden välillä vaihdetaan reaaliarvoisia viestejä, kunnes vähitellen syntyy laadukas joukko esimerkkipisteitä ja niitä vastaavia klustereita.

Syötteenä algoritmi edellyttää, että annamme kaksi datajoukkoa:

1. Datapisteiden väliset samankaltaisuussuhteet, jotka kuvaavat sitä, kuinka hyvin piste soveltuu toisen pisteen esimerkkipisteeksi. Jos kahden pisteen välillä ei ole yhtäläisyyksiä, eli ne eivät voi kuulua samaan klusteriin, tämä samankaltaisuus voidaan jättää pois tai asettaa arvoon -Infiniittinen toteutuksesta riippuen.

2. Preferenssit, jotka edustavat kunkin datapisteen soveltuvuutta olla esimerkkinä. Meillä voi olla jonkinlaista a priori tietoa siitä, mitä pisteitä voitaisiin suosia tähän rooliin, joten voimme esittää sen preferenssien avulla.

Kaikki samankaltaisuudet ja preferenssit esitetään usein yhden matriisin avulla, jossa päädiagonaalin arvot edustavat preferenssejä. Matriisiesitys on hyvä tiheille tietokokonaisuuksille. Jos pisteiden väliset yhteydet ovat harvoja, on käytännöllisempää olla tallentamatta koko n x n-matriisia muistiin, vaan säilyttää sen sijaan luettelo samankaltaisuuksista yhdistettyihin pisteisiin. Kulissien takana ”viestien vaihtaminen pisteiden välillä” on sama asia kuin matriisien manipulointi, ja kyse on vain näkökulmasta ja toteutuksesta.

Algoritmi käy tämän jälkeen läpi useita iteraatioita, kunnes se konvergoi. Jokaisessa iteraatiossa on kaksi viestinvälitysvaihetta:

1. Vastuiden laskeminen: Vastuu r(i, k) kuvastaa kertynyttä todistusaineistoa siitä, kuinka hyvin piste k soveltuu toimimaan esimerkkinä pisteelle i, ottaen huomioon muut mahdolliset esimerkit pisteelle i. Vastuu lähetetään datapisteestä i esimerkkikandidaattipisteeseen k.

2. Käytettävyyksien laskeminen: Saatavuus a(i, k) kuvastaa kertynyttä todistusaineistoa siitä, kuinka tarkoituksenmukaista olisi, että piste i valitsisi pisteen k esikuvakseen, ottaen huomioon muista pisteistä saadun tuen sille, että pisteen k pitäisi olla esikuvana. Saatavuus lähetetään esimerkkikandidaattipisteestä k pisteeseen i.

Vastuiden laskemiseksi algoritmi käyttää alkuperäisiä samankaltaisuuksia ja edellisessä iteraatiossa laskettuja saatavuuksia (aluksi kaikki saatavuudet asetetaan nollaan). Vastuualueet asetetaan pisteen i ja sen esimerkkipisteen k väliseen syötettyyn samankaltaisuuteen, josta on vähennetty pisteen i ja muiden esimerkkipiste-ehdokkaiden välinen suurin samankaltaisuus- ja saatavuussumma. Logiikka sen laskemisessa, kuinka sopiva piste on esikuvaksi, on se, että sitä suositaan enemmän, jos alkuperäinen a priori -preferenssi oli korkeampi, mutta vastuu pienenee, kun on olemassa samankaltainen piste, joka pitää itseään hyvänä ehdokkaana, joten näiden kahden välillä käydään ”kilpailua”, kunnes jossakin iteraatiossa päätetään jompikumpi.

Käytettävyyksien laskeminen käyttää siis laskettuja vastuita todisteena siitä, olisiko kustakin ehdokkaasta tullut hyvä esikuvaksi. Saatavuus a(i, k) asetetaan omaksi vastuuksi r(k, k) lisättynä niiden positiivisten vastuiden summalla, jotka kandidaattiesimerkki k saa muilta pisteiltä.

Viimeiseksi voimme käyttää erilaisia pysäytyskriteerejä, joilla menettely lopetetaan, esimerkiksi kun arvojen muutokset alittavat jonkun kynnysarvon tai iteraatioiden maksimimäärä on saavutettu. Missä tahansa pisteessä Affinity Propagation -menettelyn kautta vastuun (r) ja saatavuuden (a) matriisien summaaminen antaa meille tarvitsemamme klusterointitiedon: pisteen i osalta k, jonka r(i, k) + a(i, k) on suurin, edustaa pisteen i esimerkkiä. Tai jos tarvitsemme vain esimerkkien joukon, voimme skannata päädiagonaalin. Jos r(i, i) + a(i, i) > 0, piste i on esimerkkipiste.

Olemme nähneet, että K-Meansin ja vastaavien algoritmien kanssa klusterien lukumäärän päättäminen voi olla hankalaa. AP:n kanssa meidän ei tarvitse määritellä sitä eksplisiittisesti, mutta se voi silti tarvita jonkin verran viritystä, jos saamme joko enemmän tai vähemmän klustereita kuin ehkä pidämme optimaalisena. Onneksi voimme pienentää tai suurentaa klusterien lukumäärää vain säätämällä preferenssejä. Asettamalla preferenssit suuremmalle arvolle saadaan enemmän klustereita, koska jokainen piste on ”varmempi” soveltuvuudestaan esimerkkipisteeksi ja siksi sitä on vaikeampi ”päihittää” ja sisällyttää jonkin toisen pisteen ”herruuden” alle. Vastaavasti pienempien preferenssien asettaminen johtaa siihen, että klustereita on vähemmän; ikään kuin ne sanoisivat ”ei, ei, ole kiltti, sinä olet parempi esimerkki, liityn sinun klusteriin”. Yleissääntönä on, että voimme asettaa kaikki preferenssit keskimmäiseen samankaltaisuuteen, jos klustereita on keskisuuri tai suuri määrä, tai pienimpään samankaltaisuuteen, jos klustereita on kohtalainen määrä. Saatetaan kuitenkin tarvita pari ajokertaa preferenssejä säätämällä, jotta saadaan juuri tarpeisiimme sopiva tulos.

Hierarchical Affinity Propagation on myös mainitsemisen arvoinen algoritmin muunnos, joka käsittelee kvadraattista monimutkaisuutta jakamalla tietokokonaisuuden pariin osajoukkoon, klusteroimalla ne erikseen ja suorittamalla sitten toisen tason klusterointi.

Loppujen lopuksi…

On olemassa koko joukko klusterointialgoritmeja, joista jokaisella on hyvät ja huonot puolensa sen suhteen, minkälaisella datalla ne toimivat, aikakompleksisuus, heikkoudet ja niin edelleen. Mainitakseni lisää algoritmeja, on esimerkiksi Hierarchical Agglomerative Clustering (tai Linkage Clustering), joka on hyvä silloin, kun meillä ei välttämättä ole ympyränmuotoisia (tai hypersfäärisiä) klustereita, emmekä tiedä klustereiden lukumäärää etukäteen. Se lähtee liikkeelle siitä, että jokainen piste on erillinen klusteri, ja toimii yhdistämällä kaksi lähintä klusteria jokaisessa vaiheessa, kunnes kaikki on yhdessä suuressa klusterissa.

Hierarkkisen agglomeratiivisen klusteroinnin avulla voimme helposti päättää klustereiden määrän jälkikäteen leikkaamalla dendrogrammin (puukaavion) vaakasuoraan sopivaksi katsomassamme kohdassa. Se on myös toistettavissa (antaa aina saman vastauksen samalle tietokokonaisuudelle), mutta on myös monimutkaisempi (kvadraattinen).

Tällöin DBSCAN (Density-Based Spatial Clustering of Applications with Noise) on myös mainitsemisen arvoinen algoritmi. Se ryhmittelee lähekkäin olevia pisteitä ja laajentaa klustereita mihin tahansa suuntaan, jossa on lähekkäin olevia pisteitä, ja käsittelee näin klustereiden erilaisia muotoja.

Nämä algoritmit ansaitsevat oman artikkelinsa, ja voimme tutustua niihin erillisessä postauksessa myöhemmin.

Vatii kokemusta, jossa on jonkin verran kokeilua ja erehdystä, jotta tietää, milloin kannattaa käyttää yhtä tai toista algoritmia. Onneksi meillä on erilaisia toteutuksia eri ohjelmointikielillä, joten niiden kokeileminen vaatii vain hieman pelihalukkuutta.