Vad är K-Means Clustering?

K-means clustering är en ojämviktig lärande algoritm, och av alla ojämviktiga lärande algoritmer, kan K-means clustering vara den mest använda, tack vare dess 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 detta ä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.

Definiering av Clustering

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 clustering i allmänhet.

Kluster är bara grupper av objekt, och clustering är bara att lägga objekten i dessa grupper. I datavetenskaplig mening syftar clusteringalgoritmer 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.

Clusteringalgoritmer grupperar objekten tillsammans baserat på någon form av likhetsmått. Detta görs ofta genom att hitta “centroiden” för de olika möjliga grupperna i datamängden, även om det inte är det enda sättet. Det finns en mängd olika clusteringalgoritmer, men målet med alla clusteringalgoritmer ä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 clusteringalgoritmer, 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:

• Lägg alla instanser i undermängder, där antalet undermängder är lika med K.
• Hitta medelpunkten/centroiden för 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 till klustren, hitta den nya centroiden för klustren.

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

I den första 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 betrakta 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 clusteringalgoritmen.

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/det rätta värdet för K?

En teknik för att välja rätt K-värde kallas “knätekniken“. Knätekniken består i att köra en K-means clusteringalgoritm för ett intervall av olika K-värden och använda en noggrannhetsmått, vanligtvis summan av kvadrerade fel, för att bestämma vilka värden på K som ger de bästa resultaten. Summan av kvadrerade fel bestäms genom att beräkna medelavståndet mellan centroiden för ett kluster och datapunkterna i det klustret.

Begreppet “knäteknik” kommer från det faktum att när du ritare SSE i förhållande till de olika värdena på K, kommer den resulterande linjediagrammet ofta att ha en “knä”-form, där SSE minskar snabbt för de första few värdena på K, men sedan planar ut. I sådana fall är värdet på K som ligger vid knät 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ängderna växer, ökar också beräkningstiden. 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 av K-means clustering gjorts för att minska algoritmens rumsliga och tidsmässiga 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 delar upp datamängden i undermängder. Mini-batchar ä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 centroidernas position.

I Mini-Batch K-Means clustering uppdateras kluster med en kombination av mini-batch-värden och en inlärningshastighet. Inlärningshastigheten minskar över iterationerna, och den är inversen till 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 kompromiss i klusterkvalitet.

Tillämpningar av K-Means Clustering

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

K-means clustering kan också användas för mer öppna uppgifter som att skapa rekommendationssystem. Användare av ett system som Netflix (NFLX ) kan grupperas tillsammans baserat på visningsmönster och rekommenderas liknande innehåll. K-means clustering kunde användas för uppgifter som avvikelseupptäckt, som markerar potentiella fall av bedrägeri eller defekta artiklar.