Clustering in machine learning: 5 essentiële clustering-algoritmen

Clustering zelf is niet één specifiek algoritme maar de algemene taak die je wilt oplossen. Je kunt dit doel bereiken met verschillende algoritmen die sterk verschillen in hun opvatting van wat een cluster is en hoe je die efficiënt vindt. 

Intuïtie opbouwen achter clustering

Voordat we in de algoritmische details duiken, bouwen we eerst intuïtie met een speelgoedvoorbeeld van fruitdatasets. Stel, we hebben een enorme collectie afbeeldingsdatasets met drie fruitsoorten: (i) aardbeien, (ii) peren en (iii) appels. 

In de dataset zijn alle afbeeldingen door elkaar gehusseld, en jouw use-case is om vergelijkbare vruchten te groeperen, dus drie groepen te maken met elk één soort fruit. Dat is precies wat een clustering-algoritme doet. 

Belangrijke succescriteria voor clusteranalyse

Clustering kan, in tegenstelling tot use-cases van gestuurd leren zoals classificatie of regressie, niet volledig end-to-end worden geautomatiseerd. Het is een iteratief proces van informatieontdekking dat domeinkennis en menselijk oordeel vereist, en waarin je vaak de data en modelparameters bijstelt om het gewenste resultaat te bereiken. 

Het belangrijkste is dat we, omdat clustering ongestuurd leren is en geen gelabelde data gebruikt, geen prestatiemaatstaven zoals accuracy, AUC, RMSE, enz. kunnen berekenen om verschillende algoritmen of technieken voor datapreprocessing te vergelijken. Daardoor is het erg uitdagend en subjectief om de prestaties van clusteringmodellen te beoordelen. 

De belangrijkste succescriteria bij clusteringmodellen draaien om:

• Is het interpreteerbaar?
• Is de output van clustering bruikbaar voor het bedrijf?
• Heb je nieuwe informatie geleerd of nieuwe patronen in de data ontdekt waarvan je je vóór het clusteren niet bewust was?

Clusteringkwaliteit meten

Zonder gelabelde data kun je geen accuracy of AUC berekenen. Twee metrics helpen te kwantificeren hoe goed je clusters gescheiden zijn. Twee gangbare maten:

• De Silhouette Score meet hoe sterk een punt lijkt op zijn eigen cluster vergeleken met het dichtstbijzijnde buurluster. De score ligt tussen -1 en 1; waarden boven 0,5 duiden op goed gescheiden clusters.
• De Davies-Bouldin Index meet de gemiddelde gelijkenis tussen elk cluster en het meest vergelijkbare andere cluster — lager is beter.

Beide zijn beschikbaar in scikit-learn: sklearn.metrics.silhouette_score(X, labels) en sklearn.metrics.davies_bouldin_score(X, labels).

1. K-Means

K-Means is het meest gebruikte algoritme voor clusteringtaken, vooral omdat de stappen eenvoudig te volgen zijn en de implementatie in scikit-learn rechttoe rechtaan is. Het is een centroid-gebaseerd algoritme waarbij de gebruiker het gewenste aantal clusters moet opgeven. 

Dit komt meestal voort uit een zakelijke use-case of door verschillende waarden voor het aantal clusters te proberen en vervolgens de output te evalueren. 

K-Means clustering is een iteratief algoritme dat niet-overlappende clusters creëert, wat betekent dat elke instantie in je dataset exclusief tot één cluster kan behoren. De makkelijkste manier om de intuïtie van het K-Means-algoritme te krijgen, is de stappen te begrijpen aan de hand van het onderstaande voorbeeldschema. Je vindt ook een gedetailleerde beschrijving van het proces in onze tutorials K-Means Clustering in Python en K-Means Clustering in R. 

1. De gebruiker specificeert het aantal clusters.
2. Initialiseer centroiden willekeurig op basis van het aantal clusters. In het onderstaande diagram, in Iteratie 1, zie je dat drie centroiden willekeurig zijn geïnitialiseerd in blauw, rood en groen.
3. Bereken de afstand tussen datapunten en elk centroid en wijs elk datapunt toe aan het dichtstbijzijnde centroid.
4. Herbereken het gemiddelde van het centroid op basis van alle toegewezen datapunten; hierdoor verandert de positie van het centroid, zoals te zien is in Iteratie 2 - 9, tot het uiteindelijk convergeert.
5. De iteratie gaat door totdat het gemiddelde van het centroid niet meer verandert of een parameter max_iter is bereikt, het maximale aantal iteraties dat door de gebruiker tijdens training is gedefinieerd. In scikit-learn is max_iter standaard 300.

Bron afbeelding: Learnbymarketing.com

2. MeanShift

In tegenstelling tot het K-Means-algoritme vereist het MeanShift-algoritme niet dat je het aantal clusters specificeert. Het algoritme bepaalt zelf automatisch het aantal clusters, wat een duidelijk voordeel is ten opzichte van K-Means wanneer je niet weet hoeveel clusters je data bevat. 

MeanShift is ook gebaseerd op centroiden en wijst iteratief elk datapunt toe aan clusters. De meest voorkomende use-case voor MeanShift-clustering is beeldsegmentatie.

Het MeanShift-algoritme is gebaseerd op kernel-dichtheidsschatting. Net als bij K-Means wijzen MeanShift-algoritmen elk datapunt iteratief toe in de richting van het dichtstbijzijnde clustercentroid, die willekeurig worden geïnitialiseerd, en elk punt wordt iteratief verplaatst in de ruimte op basis van waar de meeste punten zich bevinden, dus de modus (modus is in deze context de hoogste dichtheid van datapunten in de regio). 

Daarom staat het MeanShift-algoritme ook bekend als het mode-seeking algoritme. De stappen van het MeanShift-algoritme zijn als volgt:

• Kies een willekeurig punt en maak een venster rondom dat willekeurige punt.
• Bereken het gemiddelde van alle punten binnen dit venster.
• Verschuif het venster door de richting van de modus te volgen. 
• Herhaal de stappen tot convergentie.

Bron afbeelding: ResearchGate

Voor een stapsgewijze walkthrough van MeanShift in de praktijk, zie onze Mean Shift Clustering-tutorial.

3. DBSCAN

DBSCAN, of Density-Based Spatial Clustering of Applications with Noise, is een ongestuurd clustering-algoritme dat uitgaat van het principe dat clusters dichte gebieden zijn, gescheiden door gebieden met lagere dichtheid. 

Het grootste voordeel van dit algoritme ten opzichte van K-Means en MeanShift is dat het robuust is voor uitschieters: outliers worden niet in een cluster opgenomen. 

DBSCAN-algoritmen hebben slechts twee parameters van de gebruiker nodig: 

• De straal van de cirkel die rond elk datapunt wordt getrokken, ook wel epsilon genoemd

• minPoints, dat het minimumaantal datapunten definieert dat binnen die cirkel vereist is om dat datapunt als een Core-punt te classificeren.

Elk datapunt wordt omgeven door een cirkel met straal epsilon, en DBSCAN identificeert ze als Core-punt, Border-punt of Noise-punt. Een datapunt wordt als Core-punt beschouwd als de cirkel eromheen minimaal het aantal punten bevat dat is opgegeven door de parameter minPoints. 

Het wordt beschouwd als een Border-punt als het aantal punten lager is dan het vereiste minimum, en als Ruis (Noise) als er geen extra datapunten binnen een epsilon-straal van welk datapunt dan ook liggen. Ruispunten worden niet in een cluster ingedeeld (het zijn in feite outliers).

Enkele veelvoorkomende use-cases voor het DBSCAN-clustering-algoritme zijn:

• Het presteert uitstekend bij het scheiden van clusters met hoge dichtheid versus lage dichtheid;
• Het werkt goed op niet-lineaire datasets, en
• Het kan worden gebruikt voor anomaliedetectie omdat het ruispunten afscheidt en ze niet aan een cluster toewijst.

DBSCAN vs K-Means

Bij vergelijking van DBSCAN met K-Means zijn de meest voorkomende verschillen: 

• Het K-Means-algoritme clustert alle instanties in de dataset, terwijl DBSCAN ruispunten (outliers) niet aan een geldig cluster toewijst
• K-Means heeft moeite met niet-globale clusters, terwijl DBSCAN dat soepel aankan
• Het K-Means-algoritme gaat ervan uit dat alle datapunten in de dataset uit een Gauss-verdeling komen, terwijl DBSCAN geen aanname over de data maakt.

Je kunt meer leren in onze DBSCAN-clusteringgids, met parameterafstemming en uitgewerkte voorbeelden. 

Bron afbeelding: Medium

4. Hiërarchisch clusteren

Hiërarchisch clusteren is een methode die een hiërarchie van clusters opbouwt. Er zijn twee typen van deze methode. 

• Agglomeratief: Dit is een bottom-up benadering waarbij elke observatie in het begin als een eigen cluster wordt behandeld, en naarmate we van onder naar boven gaan, worden observaties gepaard en paren samengevoegd tot clusters. 
• Divisief: Dit is een top-down benadering: alle observaties beginnen in één cluster, en terwijl we van boven naar beneden gaan, worden er recursief splitsingen uitgevoerd.

Bij het analyseren van data uit sociale netwerken is hiërarchisch clusteren veruit de meest gebruikte en populaire methode. De knooppunten (takken) in de grafiek worden met elkaar vergeleken op basis van de mate van gelijkenis die tussen hen bestaat. Door kleinere groepen gerelateerde knooppunten te verbinden, kunnen grotere groeperingen ontstaan.

Het grootste voordeel van hiërarchisch clusteren is dat het makkelijk te begrijpen en te implementeren is. Meestal wordt de output van deze clusteringmethode geanalyseerd in een afbeelding zoals hieronder. Dit heet een dendrogram.

Meer leren? Bekijk onze hiërarchische clustering-tutorial, waarin je leert dendrogrammen te bouwen en te lezen in Python. 

Bron afbeelding: ResearchGate

5. BIRCH

BIRCH staat voor Balanced Iterative Hierarchical Based Clustering. Het wordt gebruikt op zeer grote datasets waar K-Means praktisch niet kan schalen. Het BIRCH-algoritme verdeelt grote data in kleine clusters en probeert daarbij zo veel mogelijk informatie te behouden. Kleinere groepen worden vervolgens geclusterd voor een eindoutput, in plaats van de grote datasets direct te clusteren. 

BIRCH wordt vaak gebruikt als aanvulling op andere clustering-algoritmen door een samenvatting te genereren van de informatie die de andere algoritmen kunnen benutten. Gebruikers moeten, net als bij K-Means, het aantal clusters definiëren om het BIRCH-algoritme te trainen.

Een van de voordelen van BIRCH is dat het multidimensionale datapunten geleidelijk en dynamisch kan clusteren. Dit gebeurt om clusters van de hoogste kwaliteit te creëren binnen gegeven geheugen- en tijdbudgetten. In de meeste gevallen hoeft BIRCH slechts één zoekronde door de database te doen, wat BIRCH schaalbaar maakt. 

De meest voorkomende use-case van het BIRCH-clustering-algoritme is dat het een geheugenefficiënt alternatief voor K-Means is om grote datasets te clusteren die vanwege geheugen- of rekenlimieten niet met K-Means zijn te verwerken.

Zakelijke toepassingen van clustering

Clustering kent brede toepassingen in sectoren als media, gezondheidszorg, productie, retail — overal waar je grote hoeveelheden ongelabelde data hebt. Enkele praktische voorbeelden.

Klantsegmentatie

Klanten worden met clustering-algoritmen gecategoriseerd op basis van hun koopgedrag of interesses om gerichte marketingcampagnes te ontwikkelen. 

Stel, je hebt 10 miljoen klanten en je wilt gepersonaliseerde of gerichte campagnes ontwikkelen. Het is onwaarschijnlijk dat je 10 miljoen campagnes maakt, dus wat doen we? We kunnen clustering gebruiken om 10 miljoen klanten in 25 clusters te groeperen en vervolgens 25 campagnes te ontwerpen in plaats van 10 miljoen.

Bron afbeelding: Medium

Retailclustering

In retail zijn er veel kansen voor clustering. Zo kun je data per winkel verzamelen en op winkelniveau clusteren om inzichten te genereren die aangeven welke locaties op elkaar lijken op basis van kenmerken als passantenstroom, gemiddelde winkelomzet, aantal SKU’s, enz. 

Een ander voorbeeld is clusteren op categorieniveau. In het onderstaande diagram hebben we acht winkels. Verschillende kleuren vertegenwoordigen verschillende clusters. In dit voorbeeld zijn er vier clusters. 

Merk op dat de categorie deodorants in Winkel 1 wordt weergegeven door het rode cluster, terwijl die in Winkel 2 wordt weergegeven door het blauwe cluster. Dit laat zien dat Winkel 1 en Winkel 2 volledig verschillende doelmarkten hebben voor de categorie deodorants.

Bron afbeelding: dotactiv.com

Clustering in klinische zorg / ziektemanagement

Gezondheidszorg en klinische wetenschap bieden bijzonder sterke clusteringtoepassingen. Een voorbeeld is onderzoek gepubliceerd door Komaru & Yoshida et al. 2020, waarin zij demografische en laboratoriumgegevens van 101 patiënten verzamelden en hen vervolgens in 3 clusters segmenteerden. 

Elk cluster werd gekarakteriseerd door verschillende condities. Zo heeft cluster 1 patiënten met lage WBC & CRP. Cluster 2 heeft patiënten met hoge BMP & serum, en cluster 3 heeft patiënten met laag serum. Elk cluster vertegenwoordigt een ander overlevingstraject gezien de 1-jaarssterfte na hemodialyse.

Bron afbeelding: elsevierhealth.com

Beeldsegmentatie

Beeldsegmentatie is de indeling van een afbeelding in verschillende groepen. Er is veel onderzoek gedaan naar beeldsegmentatie met clustering. Dit soort clustering is nuttig als je objecten in een afbeelding wilt isoleren om elk object afzonderlijk te analyseren en te bepalen wat het is. 

In het onderstaande voorbeeld vertegenwoordigt de linkerkant de originele afbeelding en is de rechterkant het resultaat van het clustering-algoritme. Je ziet duidelijk 4 clusters, oftewel 4 verschillende objecten in de afbeelding, bepaald op basis van de pixels (tijger, gras, water en zand).

Clustering-algoritmen vergelijken

Er zijn 10 ongestuurde clustering-algoritmen geïmplementeerd in scikit-learn, een populaire machine learning-bibliotheek in Python. Er zijn fundamentele verschillen in hoe elk algoritme clusters in de dataset bepaalt en toewijst. 

De onderliggende verschillen in de wiskundige aanpak van deze algoritmen komen neer op vier aspecten waarop we ze kunnen vergelijken en contrasteren:

• Benodigde parameters voor het model 
• Schaalbaarheid 
• Use-cases, 
• Geometrie, oftewel de metriek die wordt gebruikt voor het berekenen van afstanden. 

In het onderstaande diagram vertegenwoordigt elke kolom een output van een ander clustering-algoritme, zoals K-Means, Affinity Propagation, MeanShift, enz. In totaal zijn er 10 algoritmen die op dezelfde dataset zijn getraind.

Sommige algoritmen hebben dezelfde output opgeleverd. Merk op dat Agglomerative Clustering, DBSCAN, OPTICS en Spectral Clustering tot dezelfde clusters zijn gekomen. 

Maar als je de output van K-Means vergelijkt met die van het MeanShift-algoritme, zie je dat beide algoritmen verschillende resultaten opleveren. Bij K-Means zijn er slechts twee groepen (clusters: blauw en oranje), terwijl er bij MeanShift drie zijn, namelijk blauw, groen en oranje. 

Bron afbeelding: scikit-learn

Helaas (of gelukkig) is er geen goed of fout antwoord bij clustering. Het zou zo eenvoudig zijn om vast te stellen: “Algoritme X presteert hier het beste.” 

Dat is niet mogelijk, en precies daarom is clustering een zeer uitdagende taak. 

Uiteindelijk hangt het er niet zozeer vanaf welk algoritme beter werkt volgens een makkelijk meetbare metric, maar van de interpretatie en hoe bruikbaar de output is voor de specifieke use-case.

Hoe kies je het juiste clustering-algoritme

Elk algoritme past bij andere datacondities. Gebruik deze tabel als startpunt en test vervolgens minstens twee algoritmen op je eigen data voordat je je keuze maakt.

Een praktische start: probeer eerst K-Means vanwege de snelheid, schakel over op DBSCAN als je data onregelmatige vormen of outliers bevat, en gebruik hiërarchisch clusteren wanneer je de clusterstructuur visueel via een dendrogram wilt verkennen voordat je k kiest.

Tot slot

Clustering is lastiger toe te passen dan gestuurde technieken zoals classificatie en regressie om twee redenen: je kunt de prestaties niet meten ten opzichte van gelabelde doelen, en parameters zoals het aantal clusters vereisen domeinoordeel in plaats van een algoritmische keuze. 

Clustering is een waardevolle vaardigheid voor verschillende rollen: data scientists, ML-engineers en analisten komen allemaal problemen tegen die clustering kan oplossen. 

Wil je meer leren over clustering en ongestuurd machine learning en de implementatie in Python en R, dan helpen de onderstaande cursussen je op weg: 

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