Vad är K-Means Clustering?

K-means clustering är en ojämviktig inlärningsalgoritm, och av alla ojämviktiga inlärningsalgoritmer, kan K-means clustering vara den mest använda, tack vare sin kraft och enkelhet. Hur fungerar K-means clustering exakt?

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

Definiera Kluster

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

Kluster är bara grupper av artiklar, och kluster är bara att placera artiklar i dessa grupper. I data science-sammanhanget syftar klusteringsalgoritmer till att göra två saker:

• Säkerställa att alla datapunkter i ett kluster är så lika varandra som möjligt.
• Säkerställa att alla datapunkter i olika kluster är så olika varandra som möjligt.

Klusteringsalgoritmer grupperar artiklar tillsammans baserat på någon form av likhetsmått. Detta görs ofta genom att hitta “centroiden” av de olika möjliga grupperna i datamängden, även om det inte är uteslutande. Det finns en mängd olika klusteringsalgoritmer, men målet med alla klusteringsalgoritmer är detsamma, att bestämma de grupper som är inneboende i en datamängd.

K-Means Clustering

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

I allmänhet kan K-means clustering brytas ner i fem olika steg:

• Placera alla instanser i undermängder, där antalet undermängder är lika med K.
• Hitta medelpunkten/centroiden av de nyskapade klusterpartitionerna.
• Baserat på dessa centroider, tilldela varje punkt till ett specifikt kluster.
• Beräkna avstånden från varje punkt till centroiderna, och tilldela punkterna till klustren där avståndet från centroiden är minst.
• Efter att punkterna har tilldelats klustren, hitta den nya centroiden av klustren.

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

I den initiala fasen placeras centroider 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 centroiderna har placerats, kan vi föreställa oss K-means clustering som att växla fram och tillbaka mellan två olika faser: märkning av datapunkter och uppdatering av centroider.

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

I fasen för märkning av datapunkter tilldelas varje datapunkt en etikett som placerar den i klustret som tillhör den närmaste centroiden. Den närmaste centroiden bestäms vanligtvis med hjälp av kvadrerat Euclideiskt avstånd, även om andra avståndsmått som Manhattan-avstånd, Cosine och Jaccard-avstånd kan användas beroende på typen av data som matas in i klusteringsalgoritmen.

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

I fasen för uppdatering av centroider beräknas centroiderna genom att hitta medelavståndet mellan alla datapunkter som för närvarande ingår i ett kluster.

Hur man väljer rätt värde för “K”

Med tanke på att K-means clustering är en ojämviktig algoritm och antalet klasser inte är känt i förväg, hur bestämmer man det lämpliga antalet klasser/rätt värde för K?

En teknik för att välja rätt K-värde kallas ” armbågsmetoden “. Armbågsmetoden består i att köra en K-means klusteringsalgoritm för ett intervall av olika K-värden och använda en noggrannhetsmått, vanligtvis Sum of Squared Error, för att bestämma vilka värden av K som ger de bästa resultaten. Sum of Squared Error bestäms genom att beräkna medelavståndet mellan centroiden av ett kluster och datapunkterna i det klustret.

Termen “armbågsmetoden” kommer från det faktum att när du plotter SSE i förhållande till de olika värdena av K, kommer den resulterande linjediagrammet ofta att ha en “armbågsform”, där SSE minskar snabbt för de första few värdena av K, men sedan planar ut. I sådana fall är värdet av K som ligger 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 datamängder växer, ökar beräkningstiden också. Grundläggande K-means clustering kan ta lång tid att slutföra när det körs på stora datamängder, och som ett resultat har justeringar gjorts i K-means clustering för att möjliggöra minskning av algoritmens spatiala och temporala kostnader.

Mini-Batch K-means clustering är en variant av K-means clustering där storleken på datamängden som övervägs är begränsad. Normal K-means clustering fungerar på hela datamängden/batchen på en gång, medan Mini-batch K-means clustering bryter ner datamängden i undermängder. Mini-batch är slumpmässigt utvalda från hela datamängden och för varje ny iteration väljs en ny slumpmässig sample och används för att uppdatera positionen för centroiderna.

I Mini-Batch K-Means clustering uppdateras kluster med en kombination av mini-batch-värdena och en inlärningshastighet. Inlärningshastigheten minskar över iterationerna, och den är inversen av antalet datapunkter som placeras i ett specifikt kluster. Effekten av att minska inlärningshastigheten är att påverkan av nya data minskar och konvergens uppnås när, efter flera iterationer, det inte finns några förändringar i klustren.

Resultat från studier om effektiviteten av Mini-batch K-means clustering tyder på att det kan minska beräkningstiden med en liten avkastning i klusterkvalitet.

Tillämpningar av K-Means Clustering

K-means clustering 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-means clustering.

K-means clustering kan 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 botar eller inte botar baserat på mönster av aktivitet som inlägg och kommentarer. K-means clustering kan också användas för att placera människor i grupper baserat på nivåer av oro när man övervakar deras hälsa, baserat på funktioner som komorbiditeter, ålder, patienthistoria osv.

K-means clustering 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 rekommenderas liknande innehåll. K-means clustering kan också användas för uppgifter som avvikelseupptäckt, som belyser potentiella fall av bedrägeri eller defekta artiklar.