Klustring i maskininlärning: 5 oumbärliga klustringsalgoritmer

Själva klustringen är inte en specifik algoritm utan den övergripande uppgiften som ska lösas. Du kan uppnå detta med olika algoritmer som skiljer sig avsevärt i sin syn på vad som utgör ett kluster och hur de effektivt hittar dem. 

Bygga intuition kring klustring

Innan vi dyker ner i algoritmiska detaljer bygger vi en intuition kring klustring med ett enkelt exempel på fruktdataset. Anta att vi har en stor samling bilddataset som innehåller tre frukter: (i) jordgubbar, (ii) päron och (iii) äpplen. 

I datasetet är alla bilder ihopblandade, och ditt användningsfall är att gruppera liknande frukter, det vill säga skapa tre grupper där varje grupp innehåller en frukttyp. Det är precis vad en klustringsalgoritm gör. 

Viktiga framgångskriterier för klustringsanalys

Till skillnad från superviserade användningsfall som klassificering eller regression kan klustring inte automatiseras fullt ut från början till slut. I stället är det en iterativ process för informationsupptäckt som kräver domänkunskap och mänskligt omdöme, och som ofta används för att justera data och modellparametrar för att nå önskat resultat. 

Framför allt, eftersom klustring är osuperviserat lärande och inte använder märkta data, kan vi inte beräkna prestandamått som noggrannhet, AUC, RMSE etc. för att jämföra olika algoritmer eller databehandlingstekniker. Detta gör det utmanande och subjektivt att bedöma prestandan hos klustringsmodeller. 

De viktigaste framgångskriterierna för klustringsmodeller kretsar kring:

• Är den tolkbar?
• Är klustringens utdata användbara för verksamheten?
• Har du lärt dig ny information eller upptäckt nya mönster i datan som du inte kände till före klustringen?

Mätning av klustringskvalitet

Utan märkta data kan du inte beräkna noggrannhet eller AUC. Två mått hjälper till att kvantifiera hur väl dina kluster är separerade. Två vanliga mått:

• Silhouette Score mäter hur lik en punkt är sitt eget kluster jämfört med sitt närmaste grannkluster. Det sträcker sig från -1 till 1; värden över 0,5 tyder på välseparerade kluster.
• Davies–Bouldin-index mäter den genomsnittliga likheten mellan varje kluster och dess mest liknande kluster — lägre är bättre.

Båda finns i scikit-learn: sklearn.metrics.silhouette_score(X, labels) och sklearn.metrics.davies_bouldin_score(X, labels).

1. K-Means

K-Means är den mest använda algoritmen för klustringsuppgifter, mycket tack vare att stegen är lätta att följa och att scikit-learn-implementeringen är okomplicerad. Det är en centroid-baserad algoritm där användaren måste ange hur många kluster som ska skapas. 

Detta kommer normalt från ett affärsbehov eller genom att prova olika värden för antalet kluster och sedan utvärdera utfallet. 

K-Means-klustring är en iterativ algoritm som skapar icke överlappande kluster, vilket betyder att varje instans i ditt dataset endast kan tillhöra ett kluster. Det enklaste sättet att få intuition om K-Means är att förstå stegen tillsammans med diagrammet nedan. Du kan också få en detaljerad beskrivning i våra guider K-Means Clustering in Python och K-Means Clustering in R. 

1. Användaren anger antalet kluster.
2. Initiera centroids slumpmässigt baserat på antalet kluster. I diagrammet nedan, i Iteration 1, ser du att tre centroids initieras slumpmässigt i blått, rött och grönt.
3. Beräkna avståndet mellan datapunkter och varje centroid och tilldela varje datapunkt till närmaste centroid.
4. Beräkna om medelvärdet för centroiden baserat på alla tilldelade datapunkter; detta ändrar centroidens position, vilket du ser i Iteration 2–9, tills den slutligen konvergerar.
5. Iterationen fortsätter tills det inte sker någon förändring i centroidens medelvärde eller tills parametern max_iter uppnås, vilket är maxantal iterationer som definieras av användaren under träning. I scikit-learn är max_iter som standard 300.

Bildkälla: Learnbymarketing.com

2. MeanShift

Till skillnad från K-Means kräver MeanShift-algoritmen inte att du anger antalet kluster. Algoritmen avgör automatiskt antalet kluster, vilket är en tydlig fördel jämfört med K-Means när du inte vet hur många kluster din data innehåller. 

MeanShift är också centroid-baserad och tilldelar iterativt varje datapunkt till kluster. Det vanligaste användningsfallet för MeanShift-klustring är bildsegmentering.

MeanShift-algoritmen bygger på skattning av kärntäthet (kernel density estimation). Likt K-Means tilldelar MeanShift iterativt varje punkt mot den närmaste klustercentroiden, som initieras slumpmässigt, och varje punkt flyttas iterativt i rummet mot där flest punkter finns, dvs modpunkten (mode är den högsta tätheten av datapunkter i regionen i MeanShift-sammanhang). 

Det är därför MeanShift också kallas en mode-sökande algoritm. Stegen i MeanShift är följande:

• Välj en slumpmässig punkt och skapa ett fönster runt den.
• Beräkna medelvärdet för alla punkter inuti detta fönster.
• Skjut fönstret i riktning mot modpunkten. 
• Upprepa stegen tills konvergens.

Bildkälla: ResearchGate

För en steg-för-steg-genomgång av MeanShift i praktiken, se vår Mean Shift Clustering-tutorial.

3. DBSCAN

DBSCAN, eller Density-Based Spatial Clustering of Applications with Noise, är en osuperviserad klustringsalgoritm som utgår från att kluster är täta områden i rummet separerade av områden med lägre täthet. 

Den största fördelen jämfört med K-Means och MeanShift är att den är robust mot avvikare, vilket betyder att den inte inkluderar avvikande datapunkter i något kluster. 

DBSCAN kräver bara två parametrar från användaren: 

• Radien för cirkeln som ska skapas runt varje datapunkt, även känd som epsilon

• minPoints, som anger minsta antal datapunkter som krävs inuti cirkeln för att datapunkten ska klassas som en kärnpunkt (Core).

Varje datapunkt omges av en cirkel med radien epsilon, och DBSCAN identifierar dem som antingen kärnpunkt (Core), gränspunkt (Border) eller bruspunkt (Noise). En datapunkt anses vara en kärnpunkt om cirkeln som omger den innehåller minst det antal punkter som anges av parametern minPoints. 

Den betraktas som en gränspunkt om antalet punkter är lägre än det minsta kravet, och den betraktas som brus om det inte finns några ytterligare datapunkter inom ett epsilon-avstånd från någon datapunkt. Bruspunkter kategoriseras inte i något kluster (de är i praktiken avvikare).

Några vanliga användningsfall för DBSCAN är:

• Den separerar kluster med hög respektive låg täthet mycket bra;
• Den fungerar utmärkt på icke-linjära dataset, och
• Den kan användas för avvikelsedetektering eftersom den separerar bruspunkter och inte tilldelar dem något kluster.

DBSCAN vs K-Means

Jämfört med K-Means är de vanligaste skillnaderna: 

• K-Means klustrar alla instanser i datasetet, medan DBSCAN inte tilldelar bruspunkter (avvikare) till något giltigt kluster
• K-Means har svårt med icke-globala kluster, medan DBSCAN hanterar det smidigt
• K-Means antar att datapunkterna i datasetet kommer från en Gaussisk fördelning, medan DBSCAN inte gör några antaganden om datan.

Du kan lära dig mer i vår guide till DBSCAN-klustring, som täcker parametertuning och genomarbetade exempel. 

Bildkälla: Medium

4. Hierarkisk klustring

Hierarkisk klustring är en metod som bygger en hierarki av kluster. Det finns två typer av denna metod. 

• Agglomerativ: Detta är ett bottom-up-angreppssätt där varje observation behandlas som sitt eget kluster i början, och när vi går från botten till toppen slås observationer samman parvis och paren slås samman till kluster. 
• Divisiv: Detta är ett ”top-down”-angreppssätt: alla observationer börjar i ett kluster, och delningar görs rekursivt när vi går från toppen till botten.

När det gäller att analysera data från sociala nätverk är hierarkisk klustring den i särklass vanligaste och mest populära metoden. Noderna (grenarna) i grafen jämförs beroende på graden av likhet som finns mellan dem. Genom att länka samman mindre grupper av relaterade noder kan större grupperingar skapas.

Den största fördelen med hierarkisk klustring är att den är lätt att förstå och implementera. Vanligtvis analyseras utdata från denna metod i en bild som den nedan. Den kallas ett dendrogram.

Du kan lära dig mer i vår guide till hierarkisk klustring, som visar hur man bygger och läser dendrogram i Python. 

Bildkälla: ResearchGate

5. BIRCH

BIRCH står för Balanced Iterative Hierarchical Based Clustering. Den används på mycket stora dataset där K-Means inte praktiskt kan skalas. BIRCH delar upp stora data i små kluster och försöker bevara så mycket information som möjligt. Mindre grupper klustras sedan för ett slutligt resultat i stället för att klustra de stora datamängderna direkt. 

BIRCH används ofta för att komplettera andra klustringsalgoritmer genom att skapa en sammanfattning av informationen som de andra algoritmerna kan utnyttja. Användaren måste ange antalet kluster för att träna BIRCH, på liknande sätt som i K-Means.

En av fördelarna med BIRCH är att den kan klustra flerdimensionella datapunkter successivt och dynamiskt. Detta görs för att skapa kluster av högsta kvalitet givet specifika minnes- och tidsbegränsningar. I de flesta fall behöver BIRCH bara göra en genomgång av databasen, vilket gör den skalbar. 

Det vanligaste användningsfallet för BIRCH är att den är ett minneseffektivt alternativ till K-Means som kan användas för att klustra stora dataset som K-Means inte klarar av på grund av minnes- eller beräkningsbegränsningar.

Affärstillämpningar av klustring

Klustring har breda tillämpningar i många branscher: media, sjukvård, tillverkning, detaljhandel och överallt där du har stora mängder omärkta data. Här är några praktiska exempel.

Kundsegmentering

Kunder kategoriseras med hjälp av klustringsalgoritmer utifrån deras köpbeteende eller intressen för att utveckla fokuserade marknadsföringskampanjer. 

Föreställ dig att du har 10 miljoner kunder och vill ta fram anpassade eller fokuserade kampanjer. Det är osannolikt att du tar fram 10 miljoner kampanjer, så vad gör vi? Vi kan använda klustring för att gruppera 10 miljoner kunder i 25 kluster och sedan utforma 25 kampanjer i stället för 10 miljoner.

Bildkälla: Medium

Klustring i detaljhandeln

Det finns många möjligheter för klustring i detaljhandeln. Du kan till exempel samla in data om varje butik och klustra på butiksnivå för att få insikter som visar vilka lägen som liknar varandra baserat på attribut som kundflöde, genomsnittlig butiksförsäljning, antal SKU:er osv. 

Ett annat exempel kan vara klustring på kategorinivå. I diagrammet nedan har vi åtta butiker. Olika färger representerar olika kluster. Det finns fyra kluster i detta exempel. 

Observera att deodoranter i Butik 1 representeras av det röda klustret, medan deodoranter i Butik 2 representeras av det blå klustret. Detta visar att Butik 1 och Butik 2 har helt olika målmarknader för kategorin deodoranter.

Bildkälla: dotactiv.com

Klustring inom klinisk vård / sjukdomshantering

Sjukvård och klinisk vetenskap erbjuder särskilt starka klustringstillämpningar. Ett exempel är forskning publicerad av Komaru & Yoshida et al. 2020, där de samlade demografi- och laboratoriedata för 101 patienter och delade in dem i 3 kluster. 

Varje kluster representerades av olika tillstånd. Till exempel har kluster 1 patienter med låg WBC & CRP. Kluster 2 har patienter med högt BMP & serum, och kluster 3 har patienter med lågt serum. Varje kluster representerar en annan överlevnadsbana givet 1-årsdödlighet efter hemodialys.

Bildkälla: elsevierhealth.com

Bildsegmentering

Bildsegmentering är klassificering av en bild i olika grupper. Mycket forskning har gjorts inom bildsegmentering med hjälp av klustring. Denna typ av klustring är användbar om du vill isolera objekt i en bild för att analysera varje objekt individuellt och avgöra vad det är. 

I exemplet nedan representerar vänster sida originalbilden, och höger sida är resultatet av klustringsalgoritmen. Du kan tydligt se fyra kluster som motsvarar fyra olika objekt i bilden bestämda utifrån pixlarna (tiger, gräs, vatten och sand).

Jämförelse av klustringsalgoritmer

Det finns 10 osuperviserade klustringsalgoritmer implementerade i scikit-learn, ett populärt maskininlärningsbibliotek i Python. Det finns grundläggande skillnader i hur varje algoritm bestämmer och tilldelar kluster i datasetet. 

De underliggande skillnaderna i dessa algoritmers matematiska angreppssätt kokar ner till fyra aspekter utifrån vilka vi kan jämföra dem:

• Parametrar som krävs för modellen 
• Skalbarhet 
• Användningsfall 
• Geometri, dvs metrik som används för avståndsberäkning. 

I diagrammet nedan representerar varje kolumn ett resultat från en annan klustringsalgoritm, såsom K-Means, Affinity Propagation, MeanShift osv. Totalt tränas 10 algoritmer på samma dataset.

Vissa algoritmer har gett samma resultat. Observera att Agglomerativ klustring, DBSCAN, OPTICS och Spektral klustring resulterade i samma kluster. 

Om du jämför utfallet från K-Means med resultatet från MeanShift ser du att båda gav olika resultat. I K-Means finns bara två grupper (kluster: blå och orange), medan det i MeanShift finns tre, dvs blå, grön och orange. 

Bildkälla: scikit-learn

Tyvärr (eller lyckligtvis) finns det inget rätt eller fel svar i klustring. Det hade varit enkelt att kunna slå fast att ”Algoritm X presterar bäst här”. 

Det är inte möjligt, och just därför är klustring en mycket utmanande uppgift. 

I slutänden beror det inte på något lättmätbart mått vilken algoritm som fungerar bäst, utan på tolkningen och hur användbart resultatet är för det aktuella användningsfallet.

Hur du väljer rätt klustringsalgoritm

Varje algoritm passar olika datavillkor. Använd den här tabellen som en utgångspunkt och testa sedan minst två på din faktiska data innan du bestämmer dig.

En praktisk start: prova K-Means först för hastighet, byt till DBSCAN om din data har oregelbundna former eller avvikare, och använd hierarkisk klustring när du vill utforska klusterstrukturen visuellt via ett dendrogram innan du väljer k.

Avslutande tankar

Klustring är svårare att tillämpa än superviserade tekniker som klassificering och regression av två skäl: du kan inte mäta prestanda mot märkta mål, och parametrar som antal kluster kräver domänmässigt omdöme snarare än algoritmiskt val. 

Klustring är en värdefull färdighet i många roller: data scientists, ML-ingenjörer och analytiker stöter alla på problem som klustring kan lösa. 

Om du vill lära dig mer om klustring och osuperviserad maskininlärning och hur du implementerar detta i Python och R kan följande kurser hjälpa dig vidare: 

• Cluster Analysis in Python
• Cluster Analysis in R
• Unsupervised Learning in Python
• Unsupervised Learning in R