Vad är K-Means Clustering?

K-betyder klustring är en oövervakat lärande algoritm, och av alla oövervakade inlärningsalgoritmer kan K-means-klustring vara den mest använda, tack vare dess kraft och enkelhet. Hur fungerar K-betyder klustring exakt?

Det korta svaret är att K-betyder klustring fungerar genom skapa en referenspunkt (en tyngdpunkt) för ett önskat antal klasser, och sedan tilldela datapunkter till klasskluster baserat på vilken referenspunkt som ligger närmast. Även om det är en snabb definition av K-means-klustring, låt oss ta lite tid att dyka djupare in i K-means-klustring och få en bättre intuition för hur det fungerar.

Definiera Clustering

Innan vi undersöker de exakta algoritmerna som används för att utföra K-means klustring, låt oss ta lite tid att definiera klustring i allmänhet.

Kluster är bara grupper av objekt, och kluster är bara att lägga objekt i dessa grupper. I datavetenskaplig mening, klusteralgoritmer mål att göra två saker:

• Se till att alla datapunkter i ett kluster är så lika varandra som möjligt.
• Se till att alla datapunkter i olika kluster är så olika varandra som möjligt.

Klustringsalgoritmer grupperar objekt baserat på något likhetsmått. Detta görs ofta genom att hitta "tyngdpunkten" för de olika möjliga grupperna i datamängden, men inte uteslutande. Det finns en mängd olika klustringsalgoritmer men målet för alla klustringsalgoritmer är detsamma, att bestämma grupperna som ingår i en datauppsättning.

K-Means Clustering

K-Means Clustering är en av de äldsta och mest använda typerna av klustringsalgoritmer, och den fungerar baserat på vektor kvantisering. Det finns en punkt i rymden som väljs som ursprung, och sedan ritas vektorer från ursprunget till alla datapunkter i datamängden.

I allmänhet kan K-means-klustring delas upp i fem olika steg:

• Placera alla instanser i delmängder, där antalet delmängder är lika med K.
• Hitta medelpunkten/tyngdpunkten för de nyskapade klusterpartitionerna.
• Baserat på dessa tyngdpunkter, tilldela varje punkt till ett specifikt kluster.
• Beräkna avstånden från varje punkt till tyngdpunkten och tilldela punkter till klustren där avståndet från tyngdpunkten är det minsta.
• Efter att punkterna har tilldelats klustren, hitta den nya tyngdpunkten för klustren.

Ovanstående steg upprepas tills träningsprocessen är klar.

I den inledande fasen placeras tyngdpunkter någonstans bland datapunkterna.
Foto: Weston.pace via wikimedia commons, GNU Free Documentation License (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_1.svg)

Alternativt, efter att tyngdpunkterna har placerats, kan vi tänka oss att K-betyder klustring som att byta fram och tillbaka mellan två olika faser: märkning av datapunkter och uppdatering av tyngdpunkter.

I det andra steget används ett avståndsmått som euklidiskt avstånd för att beräkna vilken tyngdpunkt en given punkt är närmast, och sedan tilldelas punkterna till den tyngdpunktens klass. Foto: Weston.pace via Wikimedia Commons, GNU Free Doc License (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_2.svg)

I datapunktsmärkningsfasen tilldelas varje datapunkt en etikett som placerar den i klustret som hör till närmaste tyngdpunkt. Den närmaste tyngdpunkten bestäms vanligtvis med hjälp av kvadratiskt euklidiskt avstånd, även om andra avståndsmått såsom Manhattan-avstånd, Cosinus och Jaccard-avstånd kan användas beroende på vilken typ av data som matas in i klustringsalgoritmen.

I det tredje steget flyttas tyngdpunkten till medelvärdet av alla datapunkter. Klasserna omfördelas sedan. Foto: Weston.pace via Wikiemedia Commons, CC SA 3.0 (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_3.svg)

I centroiduppdateringssteget beräknas tyngdpunkten genom att hitta medelavståndet mellan alla datapunkter som för närvarande finns i ett kluster.

Hur man väljer rätt värde för "K"

Med tanke på att K-means klustring är en oövervakad algoritm och antalet klasser inte är känt i förväg, hur bestämmer du dig för lämpligt antal klasser/rätt värde för K?

En teknik för att välja rätt K-värde kallas "armbågstekniken”. Armbågstekniken består av att köra en K-means-klustringsalgoritm för en rad olika K-värden och använda ett noggrannhetsmått, typiskt summan av kvadratfel, för att bestämma vilka värden på K som ger bäst resultat. Summan av kvadratfelet bestäms genom att beräkna medelavståndet mellan tyngdpunkten för ett kluster och datapunkterna i det klustret.

Termen "armbågsteknik" kommer från det faktum att när du plottar SSE med hänsyn till de olika värdena på K, kommer det resulterande linjediagrammet ofta att ha en "armbågs"-form, där SSE minskar snabbt för de första värdena av K, men planar sedan ut. Under sådana förhållanden är värdet på K vid armbågen det bästa värdet för K, eftersom det finns snabbt minskande avkastning efter detta värde.

Mini-Batch K-Means Clustering

När datauppsättningar växer sig större, växer beräkningstiden också. Grundläggande K-means-klustring kan ta lång tid att slutföra när den körs på massiva datamängder, och som ett resultat har justeringar av K-means-klustring gjorts för att kunna minska algoritmens rumsliga och tidsmässiga kostnader.

Mini-Batch K betyder klustring är en variant på K-means klustring där storleken på datamängden som övervägs är begränsad. Normal K-means-klustring fungerar på hela datamängden/batchen på en gång, medan Mini-batch K-means-klustring delar upp datasetet i delmängder. Minibatcher tas slumpmässigt från hela datamängden och för varje ny iteration väljs ett nytt slumpmässigt urval och används för att uppdatera tyngdpunkternas position.

I Mini-Batch K-Means-klustring uppdateras kluster med en kombination av mini-batch-värden och en inlärningshastighet. Inlärningshastigheten minskar över iterationerna, och det är det omvända till antalet datapunkter som placeras i ett specifikt kluster. Effekten av att minska inlärningshastigheten är att effekten av ny data minskar och konvergens uppnås när det efter flera iterationer inte sker några förändringar i klustren.

Resultat av studier om effektiviteten av Mini-batch K-means klustring tyder på att det framgångsrikt kan minska beräkningstiden med en liten kompromiss i klusterkvalitet.

Tillämpningar av K-Means Clustering

K-means-klustring kan säkert användas i alla situationer där datapunkter kan segmenteras i distinkta grupper/klasser. Här är några exempel på vanliga användningsfall för K-mean-klustring.

K-means-klustring skulle kunna tillämpas på dokumentklassificering, gruppering av dokument baserat på funktioner som ämnen, taggar, ordanvändning, metadata och andra dokumentfunktioner. Det kan också användas för att klassificera användare som bots eller inte bots baserat på aktivitetsmönster som inlägg och kommentarer. K-betyder klustring kan också användas för att placera människor i grupper baserat på nivåer av oro när de övervakar deras hälsa, baserat på egenskaper som komorbiditeter, ålder, patienthistoria, etc.

K-means-klustring kan också användas för mer öppna uppgifter som att skapa rekommendationssystem. Användare av ett system som Netflix kan grupperas tillsammans baserat på visningsmönster och rekommenderat liknande innehåll. K-means-klustring skulle kunna användas för att upptäcka avvikelser och lyfta fram potentiella fall av bedrägeri eller defekta föremål.