Clustering Algorithms: From Start To State Of The Art

Het is geen slechte tijd om Data Scientist te zijn. Serieuze mensen kunnen interesse in je vinden als je het gesprek richting “Big Data” draait, en de rest van het feestpubliek zal geïntrigeerd zijn als je het hebt over “Artificial Intelligence” en “Machine Learning”. Zelfs Google denkt dat je niet slecht bent, en dat je zelfs beter wordt. Er zijn een heleboel “slimme” algoritmen die datawetenschappers helpen bij hun tovenarij. Het lijkt misschien allemaal ingewikkeld, maar als we algoritmen een beetje begrijpen en ordenen, is het niet eens zo moeilijk om het algoritme te vinden en toe te passen dat we nodig hebben.

Cursussen over datamining of machinaal leren beginnen meestal met clusteren, omdat het zowel eenvoudig als nuttig is. Het is een belangrijk onderdeel van een wat breder gebied van Unsupervised Learning, waar de gegevens die we willen beschrijven niet gelabeld zijn. In de meeste gevallen is dit het geval wanneer de gebruiker ons niet veel informatie heeft gegeven over wat de verwachte output is. Het algoritme heeft alleen de gegevens en het moet zijn best doen. In ons geval moet het clusteren – het scheiden van gegevens in groepen (clusters) die gelijksoortige gegevenspunten bevatten, terwijl de ongelijksoortigheid tussen de groepen zo groot mogelijk is. Datapunten kunnen van alles voorstellen, zoals onze cliënten. Clustering kan nuttig zijn als we bijvoorbeeld gelijksoortige gebruikers willen groeperen en dan verschillende marketingcampagnes op elke cluster willen uitvoeren.

K-Means Clustering

Na de noodzakelijke inleiding gaan Data Mining cursussen altijd verder met K-Means; een effectief, veelgebruikt, all-round clustering algoritme. Voordat het daadwerkelijk wordt uitgevoerd, moeten we een afstandsfunctie tussen datapunten definiëren (bijvoorbeeld de Euclidische afstand als we punten in de ruimte willen clusteren), en moeten we het aantal gewenste clusters (k) instellen.

Het algoritme begint met het selecteren van k punten als beginpunten (‘centra’ van clusters). We kunnen gewoon willekeurige k punten kiezen, of we kunnen een andere aanpak gebruiken, maar willekeurige punten kiezen is een goed begin. Daarna herhalen we iteratief twee stappen:

1. Toewijzingsstap: elk van m punten uit onze dataset wordt toegewezen aan een cluster dat wordt vertegenwoordigd door de dichtstbijzijnde van de k centroïden. Voor elk punt berekenen we de afstand tot elk zwaartepunt, en kiezen gewoon het minst verafgelegen zwaartepunt.

2. Bijwerkstap: voor elk cluster wordt een nieuw zwaartepunt berekend als het gemiddelde van alle punten in het cluster. Uit de vorige stap hebben we een verzameling punten die aan een cluster worden toegewezen. Nu berekenen we voor elk van die verzamelingen een gemiddelde dat we tot nieuw centroïde van de cluster verklaren.

Na elke iteratie bewegen de centroïden langzaam, en wordt de totale afstand van elk punt tot zijn toegewezen centroïde steeds kleiner. De twee stappen worden afgewisseld tot convergentie, d.w.z. tot er geen veranderingen meer zijn in de clustertoewijzing. Na een aantal iteraties zal dezelfde set punten aan elk zwaartepunt worden toegewezen, wat dus weer tot dezelfde zwaartepunten leidt. K-Means convergeert gegarandeerd naar een lokaal optimum. Dat hoeft echter niet de beste algemene oplossing (globaal optimum) te zijn.

Het uiteindelijke resultaat van de clustering kan afhangen van de keuze van de initiële centroïden, dus is er veel nagedacht over dit probleem. Een eenvoudige oplossing is om K-Means een paar keer uit te voeren met willekeurige begintoewijzingen. We kunnen dan het beste resultaat selecteren door het resultaat te nemen met de minimale som van de afstanden van elk punt tot zijn cluster – de foutwaarde die we in de eerste plaats proberen te minimaliseren.

Andere benaderingen van het selecteren van beginpunten kunnen berusten op het selecteren van verafgelegen punten. Dit kan tot betere resultaten leiden, maar we kunnen een probleem hebben met uitbijters, die zeldzame alleenstaande punten die net “uit” zijn en die misschien alleen maar fouten zijn. Aangezien zij ver verwijderd zijn van enige zinvolle cluster, kan elk van die punten uiteindelijk een eigen “cluster” vormen. Een goede balans is K-Means++ variant , waarvan de initialisatie nog steeds willekeurige punten kiest, maar met een waarschijnlijkheid evenredig met het kwadraat van de afstand tot de eerder toegewezen centroïden. Punten die verder weg liggen zullen een grotere kans hebben om als beginpunt te worden gekozen. Bijgevolg, als er een groep punten is, wordt de waarschijnlijkheid dat een punt uit de groep wordt geselecteerd ook hoger naarmate hun waarschijnlijkheid toeneemt, waardoor het uitschieterprobleem dat we noemden wordt opgelost.

K-Means++ is ook de standaard initialisatie voor Python’s Scikit-learn K-Means implementatie. Als u Python gebruikt, kan dit uw bibliotheek van keuze zijn. Voor Java is de Weka-bibliotheek wellicht een goede start:

Java (Weka)

// Load some dataInstances data = DataSource.read("data.arff");// Create the modelSimpleKMeans kMeans = new SimpleKMeans();// We want three clusterskMeans.setNumClusters(3);// Run K-MeanskMeans.buildClusterer(data);// Print the centroidsInstances centroids = kMeans.getClusterCentroids();for (Instance centroid: centroids) { System.out.println(centroid);}// Print cluster membership for each instancefor (Instance point: data) { System.out.println(point + " is in cluster " + kMeans.clusterInstance(point));}

Python (Scikit-learn)

> >> from sklearn import cluster, datasets> >> iris = datasets.loadiris()> >> Xiris = iris.data> >> yiris = iris.target> >> kmeans = cluster.KMeans(nclusters=3)> >> kmeans.fit(Xiris)KMeans(copy_x=True, init='k-means++', ...> >> print(kmeans.labels)> >> print(yiris)

In het Python-voorbeeld hierboven gebruikten we een standaard voorbeelddataset ‘Iris’, die bloemblad- en kelkbladafmetingen bevat voor drie verschillende soorten iris. We hebben deze geclusterd in drie clusters, en de verkregen clusters vergeleken met de werkelijke soorten (doel), om te zien of ze perfect bij elkaar passen.

In dit geval wisten we dat er drie verschillende clusters (soorten) waren, en K-Means herkende correct welke bij elkaar horen. Maar, hoe kiezen we een goed aantal clusters k in het algemeen? Dit soort vragen komt vaak voor bij Machine Learning. Als we meer clusters vragen, zullen ze kleiner zijn, en dus zal de totale fout (totaal van de afstanden van punten tot hun toegewezen clusters) kleiner zijn. Is het dan wel een goed idee om gewoon een grotere k in te stellen? We zouden kunnen eindigen met k = m, dat wil zeggen dat elk punt zijn eigen zwaartepunt is, en dat elke cluster slechts één punt heeft. Ja, de totale fout is 0, maar we hebben geen eenvoudiger beschrijving van onze gegevens gekregen, en ze is ook niet algemeen genoeg om nieuwe punten die kunnen opduiken te dekken. Dit wordt overfitting genoemd, en dat willen we niet.

Een manier om met dit probleem om te gaan is het opnemen van een straf voor een groter aantal clusters. We proberen nu dus niet alleen de fout te minimaliseren, maar fout + penalty. De fout convergeert gewoon naar nul als we het aantal clusters verhogen, maar de straf zal groeien. Op een gegeven moment zal de winst van het toevoegen van nog een cluster minder zijn dan het ingevoerde nadeel, en dan hebben we het optimale resultaat. Een oplossing die hiervoor het Bayesiaanse informatiecriterium (BIC) gebruikt, heet X-Means.

Een ander ding dat we goed moeten definiëren is de afstandsfunctie. Soms is dat een eenvoudige taak, een logische gezien de aard van de gegevens. Voor punten in de ruimte is de Euclidische afstand een voor de hand liggende oplossing, maar het kan lastig zijn voor kenmerken van verschillende “eenheden”, voor discrete variabelen, enz. Dit kan veel domeinkennis vereisen. Of, we kunnen Machine Learning om hulp vragen. We kunnen proberen de afstandsfunctie te leren. Als we een trainingsverzameling van punten hebben waarvan we weten hoe ze moeten worden gegroepeerd (d.w.z. punten gelabeld met hun clusters), kunnen we leertechnieken onder toezicht gebruiken om een goede functie te vinden, en die vervolgens toepassen op onze doelverzameling die nog niet is geclusterd.

De methode die in K-Means wordt gebruikt, met zijn twee alternerende stappen lijkt op een Expectation-Maximization (EM) methode. Eigenlijk kan het worden beschouwd als een zeer eenvoudige versie van EM. Het mag echter niet worden verward met het uitgebreidere EM-clusteralgoritme, hoewel het enkele van dezelfde principes deelt.

EM Clustering

Dus bij K-Means clustering wordt elk punt slechts aan één cluster toegewezen, en een cluster wordt alleen beschreven door zijn zwaartepunt. Dit is niet al te flexibel, want we kunnen problemen krijgen met clusters die elkaar overlappen, of met clusters die geen cirkelvorm hebben. Met EM-clustering kunnen we nu een stap verder gaan en elk cluster beschrijven aan de hand van zijn zwaartepunt (gemiddelde), covariantie (zodat we ellipsvormige clusters kunnen krijgen), en gewicht (de grootte van het cluster). De kans dat een punt tot een cluster behoort, wordt nu gegeven door een multivariate Gaussiaanse kansverdeling (multivariate – afhankelijk van meerdere variabelen). Dat betekent ook dat we de kans kunnen berekenen dat een punt onder een Gaussische ‘bel’ ligt, dat wil zeggen de kans dat een punt tot een cluster behoort.

We beginnen nu de EM-procedure door voor elk punt de kans te berekenen dat het tot elk van de huidige clusters behoort (die, nogmaals, aan het begin willekeurig kunnen zijn gecreëerd). Dit is de E-stap. Als één cluster een echt goede kandidaat is voor een punt, zal die een waarschijnlijkheid hebben die dicht bij één ligt. Twee of meer clusters kunnen echter aanvaardbare kandidaten zijn, zodat het punt een verdeling van waarschijnlijkheden over clusters heeft. Deze eigenschap van het algoritme, dat punten niet beperkt tot één cluster behoren, wordt “soft clustering” genoemd.

De M-stap berekent nu de parameters van elke cluster opnieuw, met gebruikmaking van de toewijzingen van punten aan de vorige reeks clusters. Om het nieuwe gemiddelde, de covariantie en het gewicht van een cluster te berekenen, worden alle puntgegevens gewogen met de waarschijnlijkheid dat ze tot de cluster behoren, zoals berekend in de vorige stap.

Door deze twee stappen af te wisselen, neemt de totale log-likelihood toe totdat deze convergeert. Ook hier kan het maximum lokaal zijn, zodat we het algoritme verschillende keren kunnen uitvoeren om betere clusters te krijgen.

Als we nu voor elk punt een enkel cluster willen bepalen, kunnen we gewoon het meest waarschijnlijke kiezen. Als we een waarschijnlijkheidsmodel hebben, kunnen we het ook gebruiken om vergelijkbare gegevens te genereren, dat wil zeggen om meer punten te bemonsteren die lijken op de gegevens die we hebben waargenomen.

Affinity Propagation

Affinity Propagation (AP) werd in 2007 gepubliceerd door Frey en Dueck, en wordt alleen maar populairder door zijn eenvoud, algemene toepasbaarheid en prestaties. Het is bezig zijn status te veranderen van state of the art in de facto standaard.

De belangrijkste nadelen van K-Means en soortgelijke algoritmen zijn dat het aantal clusters moet worden geselecteerd en dat de initiële reeks punten moet worden gekozen. Affinity Propagation daarentegen neemt als input de mate van overeenkomst tussen paren gegevenspunten en beschouwt tegelijkertijd alle gegevenspunten als potentiële voorbeelden. Tussen de datapunten worden berichten met een reële waarde uitgewisseld, totdat geleidelijk een reeks voorbeelden van hoge kwaliteit en overeenkomstige clusters ontstaat.

Als invoer vereist het algoritme twee reeksen gegevens:

1. Gelijkenissen tussen datapunten, die aangeven hoe goed een punt geschikt is om het voorbeeld van een ander punt te zijn. Als er geen overeenkomst is tussen twee punten, d.w.z. dat ze niet tot dezelfde cluster kunnen behoren, kan deze overeenkomst worden weggelaten of op – Oneindig worden gezet, afhankelijk van de implementatie.

2. Voorkeuren, die de geschiktheid van elk gegevenspunt weergeven om een voorbeeld te zijn. We kunnen a priori informatie hebben over welke punten de voorkeur zouden kunnen krijgen voor deze rol, en dus kunnen we dit weergeven door middel van voorkeuren.

Zowel overeenkomsten als voorkeuren worden vaak weergegeven door middel van een enkele matrix, waarbij de waarden op de hoofddiagonaal de voorkeuren weergeven. Matrixrepresentatie is goed voor dichte datasets. Wanneer de verbindingen tussen punten schaars zijn, is het praktischer om niet de hele n x n matrix in het geheugen op te slaan, maar in plaats daarvan een lijst van overeenkomsten met verbonden punten te bewaren. Achter de schermen is het ‘uitwisselen van berichten tussen punten’ hetzelfde als het manipuleren van matrices, en het is slechts een kwestie van perspectief en implementatie.

Het algoritme doorloopt vervolgens een aantal iteraties, totdat het convergeert. Elke iteratie bestaat uit twee stappen voor het doorgeven van berichten:

1. Berekenen van verantwoordelijkheden: Verantwoordelijkheid r(i, k) geeft het geaccumuleerde bewijs weer voor hoe geschikt punt k is om als voorbeeld te dienen voor punt i, rekening houdend met andere potentiële voorbeeldpunten voor punt i. De verantwoordelijkheid wordt verzonden van gegevenspunt i naar kandidaat-voorbeeldpunt k.

2. Berekening van beschikbaarheden: Beschikbaarheid a(i, k) weerspiegelt het geaccumuleerde bewijsmateriaal voor hoe geschikt het zou zijn voor punt i om punt k als zijn voorbeeld te kiezen, rekening houdend met de steun van andere punten dat punt k een voorbeeld zou moeten zijn. De beschikbaarheid wordt van kandidaat-voorbeeldpunt k naar punt i gestuurd.

Om de verantwoordelijkheden te berekenen, gebruikt het algoritme de originele gelijkenissen en beschikbaarheden die in de vorige iteratie zijn berekend (aanvankelijk worden alle beschikbaarheden op nul gezet). De verantwoordelijkheden worden gesteld op de input-gelijkenis tussen punt i en punt k als zijn voorbeeld, min de grootste van de gelijkenis- en beschikbaarheids-som tussen punt i en andere kandidaat-voorbeelden. De logica achter het berekenen van hoe geschikt een punt is voor een voorbeeld is dat het meer voorkeur krijgt als de initiële a priori voorkeur hoger was, maar de verantwoordelijkheid wordt lager als er een gelijksoortig punt is dat zichzelf als een goede kandidaat beschouwt, dus er is een ‘competitie’ tussen de twee totdat in een of andere iteratie wordt beslist.

Berekening van de beschikbaarheid gebruikt dus berekende verantwoordelijkheden als bewijs of elke kandidaat een goed voorbeeld zou zijn. De beschikbaarheid a(i, k) is gelijk aan de eigen verantwoordelijkheid r(k, k) plus de som van de positieve verantwoordelijkheden die kandidaat-voorbeeld k van andere punten ontvangt.

Ten slotte kunnen we verschillende stopcriteria hebben om de procedure te beëindigen, zoals wanneer veranderingen in waarden onder een bepaalde drempel vallen, of wanneer het maximum aantal iteraties is bereikt. Op elk punt in de Affinity Propagation procedure geeft de som van de Verantwoordelijkheids- (r) en Beschikbaarheids- (a) matrices ons de clusteringinformatie die we nodig hebben: voor punt i vertegenwoordigt de k met maximum r(i, k) + a(i, k) het voorbeeld van punt i. Of, als we alleen de verzameling van voorbeelden nodig hebben, kunnen we de hoofddiagonaal scannen. Als r(i, i) + a(i, i) > 0, is punt i een voorbeeld.

We hebben gezien dat met K-Means en soortgelijke algoritmen, het bepalen van het aantal clusters lastig kan zijn. Met AP hoeven we het niet expliciet op te geven, maar het kan nog steeds enige afstemming vergen als we meer of minder clusters krijgen dan we optimaal vinden. Gelukkig kunnen we het aantal clusters verlagen of verhogen door alleen de voorkeuren aan te passen. Een hogere waarde van de voorkeuren leidt tot meer clusters, omdat elk punt “zekerder” is van zijn geschiktheid om een voorbeeld te zijn en daarom moeilijker te “verslaan” is en onder de “dominantie” van een ander punt op te nemen. Omgekeerd zal het instellen van lagere voorkeuren resulteren in het hebben van minder clusters; alsof ze zeggen “nee, nee, alsjeblieft, jij bent een beter voorbeeld, ik zal me bij jouw cluster aansluiten”. Als algemene regel kunnen we alle voorkeuren instellen op de mediane overeenkomst voor een middelgroot tot groot aantal clusters, of op de laagste overeenkomst voor een middelgroot aantal clusters. Er kunnen echter een paar runs nodig zijn met het aanpassen van voorkeuren om het resultaat te krijgen dat precies aan onze behoeften voldoet.

Hierarchische Affiniteits Propagatie is ook het vermelden waard, als een variant van het algoritme dat omgaat met kwadratische complexiteit door de dataset op te splitsen in een paar deelverzamelingen, deze afzonderlijk te clusteren, en dan het tweede niveau van clustering uit te voeren.

In The End…

Er is een hele reeks clustering-algoritmen, elk met zijn voors en tegens wat betreft het type gegevens waarmee ze werken, de tijdcomplexiteit, zwakke punten, enzovoort. Om meer algoritmen te noemen, is er bijvoorbeeld Hiërarchische Agglomeratieve Clustering (of Linkage Clustering), goed voor wanneer we niet noodzakelijk cirkelvormige (of hypersferische) clusters hebben, en het aantal clusters niet op voorhand weten. Het begint met elk punt als een afzonderlijk cluster, en werkt door in elke stap twee dichtstbijzijnde clusters samen te voegen tot alles in één groot cluster zit.

Met hiërarchische agglomeratieve clustering kunnen we het aantal clusters achteraf gemakkelijk bepalen door het dendrogram (boomdiagram) horizontaal door te knippen waar we dat geschikt vinden. Het is ook herhaalbaar (geeft altijd hetzelfde antwoord voor dezelfde dataset), maar heeft ook een hogere complexiteit (kwadratisch).

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) is ook een vermeldenswaardig algoritme. Het groepeert punten die dicht bij elkaar liggen, en breidt clusters uit in elke richting waar er nabije punten zijn, en gaat zo om met verschillende vormen van clusters.

Deze algoritmen verdienen een eigen artikel, en we kunnen ze later in een aparte post verkennen.

Het vergt ervaring met wat trial and error om te weten wanneer je het ene of het andere algoritme moet gebruiken. Gelukkig hebben we een reeks implementaties in verschillende programmeertalen, dus uitproberen vereist alleen een beetje bereidheid om te spelen.