Hva er K-Means Clustering?

K-means clustering er en ujåpet læring algoritme, og av alle ujåpene læring algoritmene, kan K-means clustering være den mest brukte, takket være dens kraft og enkelhet. Hvordan fungerer K-means clustering egentlig?

Det korte svaret er at K-means clustering fungerer ved å opprette en referansepunkt (en sentroid) for et ønsket antall klasser, og deretter tilordne datapunkter til klassekluster basert på hvilken referansepunkt som er nærmest. Mens dette er en rask definisjon for K-means clustering, la oss ta litt tid til å dykke dyptere inn i K-means clustering og få en bedre forståelse av hvordan det opererer.

Definering av Clustering

Før vi undersøker de eksakte algoritmene som brukes til å utføre K-means clustering, la oss ta litt tid til å definere clustering generelt.

Kluster er bare grupper av elementer, og clustering er bare å plassere elementer i disse gruppene. I data vitenskapens forstand, clustering algoritmer har til hensikt å gjøre to ting:

• Sikre at alle datapunkter i et kluster er så like hverandre som mulig.
• Sikre at alle datapunkter i forskjellige kluster er så ulike hverandre som mulig.

Clustering algoritmer grupperer elementer sammen basert på en måling av likhet. Dette gjøres ofte ved å finne “sentroiden” av de forskjellige mulige gruppene i datasettet, selv om ikke eksklusivt. Det finnes en rekke forskjellige clustering algoritmer, men målet med alle clustering algoritmene er det samme, å bestemme gruppene som er innebygget i et datasett.

K-Means Clustering

K-Means Clustering er en av de eldste og mest brukte typene av clustering algoritmer, og den opererer basert på vektor kvantisering. Det finnes et punkt i rommet som er valgt som opphav, og deretter trekkes vektorer fra opphavet til alle datapunktene i datasettet.

Generelt kan K-means clustering deles inn i fem forskjellige trinn:

• Plasser alle instanser i undergrupper, hvor antallet undergrupper er likt med K.
• Finne gjennomsnittspunktet/sentroiden av de nyopprettede klusterdelene.
• Basert på disse sentroidene, tilordne hver punkt til et bestemt kluster.
• Beregne avstandene fra hver punkt til sentroidene, og tilordne punkter til klusterne hvor avstanden fra sentroid er minst.
• Etter at punktene er tilordnet til klusterne, finne den nye sentroiden av klusterne.

De ovenstående trinnene gjentas til treningprosessen er ferdig.

I den innledende fasen, plasseres sentroider et sted blant datapunktene.
Foto: Weston.pace via wikimedia commons, GNU Free Documentation License (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_1.svg)

Alternativt, etter at sentroidene er plassert, kan vi tenke på K-means clustering som å bytte frem og tilbake mellom to forskjellige faser: å merke datapunkter og å oppdatere sentroider.

I det andre steget, brukes en avstandsmåling som Euclidisk avstand til å beregne hvilken sentroid en gitt punkt er nærmest, og deretter tilordnes punktene til den sentroidens klasse. Foto: Weston.pace via Wikimedia Commons, GNU Free Doc License (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_2.svg)

I fasen hvor datapunkter merkes, tilordnes hver datapunkt en merking som plasserer det i klusteret som tilhører den nærmeste sentroiden. Den nærmeste sentroiden bestemmes vanligvis ved å bruke kvadrert Euclidisk avstand, selv om andre avstandsmål som Manhattan-avstand, Cosine og Jaccard-avstand kan brukes avhengig av typen data som mates inn i clustering-algoritmen.

I det tredje steget, flyttes sentroider til gjennomsnittet av alle datapunktene. Klassene tilordnes deretter på nytt. Foto: Weston.pace via Wikiemedia Commons, CC SA 3.0 (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_3.svg)

I fasen hvor sentroider oppdateres, beregnes sentroidene ved å finne gjennomsnittsavstanden mellom alle datapunktene som for øyeblikket er innholdt i et kluster.

Hvordan velge riktig verdi for “K”

Med tanke på at K-means clustering er en ujåpet algoritme og antallet klasser ikke er kjent på forhånd, hvordan bestemmer du den riktige antallet klasser/verdi for K?

En teknikk for å velge riktig K-verdi kalles “albue-teknikken“. Albue-teknikken består i å kjøre en K-means clustering-algoritme for et område av forskjellige K-verdier og bruke en nøyaktighetsmåling, vanligvis Sum of Squared Error, til å bestemme hvilke verdier av K som gir de beste resultater. Sum of Squared Error bestemmes ved å beregne gjennomsnittsavstanden mellom sentroiden av et kluster og datapunktene i det klusteret.

Begrepet “albue-teknikk” kommer fra det faktum at når du plotter SSE i forhold til de forskjellige verdiene av K, vil den resulterende linjegrafen ofte ha en “albue”-form, hvor SSE minker raskt for de første verdiene av K, men deretter planer ut. I slike tilfeller er verdien av K som ligger ved albuen den beste verdien for K, siden det er raskt avtagende gevinst etter denne verdien.

Mini-Batch K-Means Clustering

Ettersom datasett vokser større, øker beregningsiden også. Grunnleggende K-means clustering kan ta lang tid å fullføre når det kjøres på store datasett, og som et resultat, er det blitt gjort justeringer til K-means clustering for å kunne redusere algoritmens romlige og tidsmessige kostnader.

Mini-Batch K-means clustering er en variant av K-means clustering hvor størrelsen på datasettet som vurderes er begrenset. Vanlig K-means clustering opererer på hele datasettet/batch på en gang, mens Mini-batch K-means clustering deler datasettet inn i undergrupper. Mini-batch er tilfeldig utvalgt fra hele datasettet og for hver ny iterasjon velges en ny tilfeldig utvalg og brukes til å oppdatere posisjonen av sentroidene.

I Mini-Batch K-Means clustering, oppdateres klusterne med en kombinasjon av mini-batch-verdiene og en læringsrate. Læringsraten minker over iterasjonene, og den er invers av antallet datapunkter som plasseres i et bestemt kluster. Effekten av å redusere læringsraten er at innvirkningen av nye data reduseres og konvergens oppnås når, etter flere iterasjoner, det ikke er noen endringer i klusterne.

Resultatene av studier om effektiviteten av Mini-batch K-means clustering tyder på at det kan suksessfullt redusere beregningsiden med en liten kompromiss i klassekvalitet.

Anvendelser av K-Means Clustering

K-means clustering kan trygt brukes i enhver situasjon hvor datapunkter kan segmenteres i distinkte grupper/klasser. Her er noen eksempler på vanlige bruksområder for K-means clustering.

K-means clustering kan brukes til dokumentklassifisering, gruppering av dokumenter basert på egenskaper som emner, nøkkelord, ordbruk, metadata og andre dokumentegenskaper. Det kan også brukes til å klassifisere brukere som roboter eller ikke-roboter basert på aktivitetsmønster som innlegg og kommentarer. K-means clustering kan også brukes til å plassere personer i grupper basert på nivåer av bekymring når man overvåker deres helse, basert på egenskaper som komorbiditet, alder, pasienthistorie osv.

K-means clustering kan også brukes til mer åpne oppgaver som å lage anbefalingssystemer. Brukere av et system som Netflix (NFLX ) kan grupperes sammen basert på visningsmønster og anbefales lignende innhold. K-means clustering kunne brukes til anomali-detteksjon, å høydeppe potensielle eksempler på svindel eller defekte varer.