Free Press

Gebaseerde clustering op basis van afstand.

Gegeven een verzameling punten, met een notie van afstand tussen punten, groeperen van de punten in een aantal clusters, zodanig dat

• interne (binnen de cluster) afstanden klein moeten zijn, d.w.z.
• externe (intra-cluster) afstanden moeten groot zijn, d.w.z. leden van verschillende clusters verschillen van elkaar.

De doelen van clusteren

Het doel van clusteren is de interne groepering in een reeks ongelabelde gegevens te bepalen. Maar hoe bepaal je wat een goede clustering is? Men kan aantonen dat er geen absoluut “beste” criterium bestaat dat onafhankelijk zou zijn van het uiteindelijke doel van de clustering. Bijgevolg is het de gebruiker die dit criterium moet aanreiken, en wel zodanig dat het resultaat van de clustering aan zijn behoeften beantwoordt.

In de bovenstaande afbeelding, hoe weten we wat de beste clustering is?

Om een bepaalde clusteringoplossing te vinden, moeten we de similariteitsmaten voor de clusters definiëren.

Nabijheidsmaten

Voor clustering moeten we een nabijheidsmaat voor twee gegevenspunten definiëren. Nabijheid betekent hier hoe vergelijkbaar/dissimilar de monsters zijn ten opzichte van elkaar.

• Gelijkenismaat S(xi,xk): groot als xi,xk gelijkenis vertonen
• Verschillenis(of afstands)-maat D(xi,xk): klein als xi,xk gelijksoortig zijn

Bij het tweede type, de overlappende clustering, worden daarentegen fuzzy sets gebruikt om gegevens te clusteren, zodat elk punt tot twee of meer clusters kan behoren met een verschillende mate van lidmaatschap. In dit geval worden de gegevens geassocieerd met een passende lidmaatschapswaarde.

Een hiërarchisch clusteringalgoritme is gebaseerd op de unie tussen de twee dichtstbijzijnde clusters. De beginvoorwaarde wordt gerealiseerd door elk gegevenspunt als een cluster in te stellen. Na enkele iteraties worden de gewenste eindclusters bereikt.

Ten slotte maakt de laatste soort clustering gebruik van een volledig probabilistische aanpak.

In deze blog zullen we het hebben over vier van de meest gebruikte clustering algoritmen:

• K-means
• Fuzzy K-means
• Hierarchische clustering
• Mengsel van Gaussians

Elk van deze algoritmen behoort tot een van de hierboven genoemde clusteringstypen. K-means is een exclusief clusteralgoritme, Fuzzy K-means een overlappend clusteralgoritme, hiërarchisch clusteren ligt voor de hand en Mixture of Gaussians tenslotte is een probabilistisch clusteralgoritme. We zullen elke clustermethode in de volgende paragrafen bespreken.

K-Means Clustering

K-Means is een van de eenvoudigste onbewaakte leeralgoritmen die het welbekende clusteringsprobleem oplost. De procedure volgt een eenvoudige en gemakkelijke manier om een gegeven gegevensverzameling te classificeren door middel van een bepaald aantal clusters (veronderstel k clusters) dat a priori is vastgesteld. Het hoofdidee bestaat erin k centra te definiëren, één voor elke cluster. Deze centra moeten op een slimme manier worden geplaatst omdat een andere plaats een ander resultaat veroorzaakt. De beste keuze is dus om ze zo ver mogelijk van elkaar te plaatsen. De volgende stap is elk punt te nemen dat tot een gegeven gegevensverzameling behoort en het te associëren met de dichtstbijzijnde centroïde. Wanneer geen enkel punt in behandeling is, is de eerste stap voltooid en wordt een vervroegde groepering uitgevoerd. Op dit punt moeten we k nieuwe centroïden herberekenen als barycenters van de clusters die uit de vorige stap zijn voortgekomen. Nadat we deze k nieuwe centroïden hebben, moet een nieuwe binding worden uitgevoerd tussen dezelfde punten van de gegevensverzameling en het dichtstbijzijnde nieuwe centroïde. Er is een lus gegenereerd. Het resultaat van deze lus is dat de k centroïden stap voor stap van plaats veranderen tot er geen veranderingen meer worden aangebracht. Met andere woorden: de centroïden bewegen niet meer.

Ten slotte is dit algoritme gericht op het minimaliseren van een doelfunctie, in dit geval een gekwadrateerde foutenfunctie. De doelfunctie

is een gekozen afstandsmaat tussen een gegevenspunt xi en het clustermidden cj, is een indicator voor de afstand van de n gegevenspunten tot hun respectieve clustercentra.

Het algoritme bestaat uit de volgende stappen:

• Laat X = {x1,x2,x3,……..,xn} de verzameling gegevenspunten zijn en V = {v1,v2,…….,vc} de verzameling middelpunten.
• Selecteer willekeurig ‘c’ clustercentra.
• Bereken de afstand tussen elk gegevenspunt en de clustercentra.
• Toewijs het gegevenspunt toe aan het clustercentrum waarvan de afstand tot het clustercentrum het minimum is van alle clustercentra.
• Bereken het nieuwe clustercentrum met:

waar, ‘ci’ staat voor het aantal gegevenspunten in de i-de cluster.

• Bereken de afstand tussen elk gegevenspunt en de nieuw verkregen clusters.
• Als geen gegevenspunt opnieuw werd toegewezen, stop dan, anders herhaal vanaf stap 3).

Hoewel kan worden aangetoond dat de procedure altijd zal eindigen, vindt het k-means algoritme niet noodzakelijk de meest optimale configuratie, die overeenstemt met het globale minimum van de doelfunctie. Het algoritme is ook aanzienlijk gevoelig voor de aanvankelijk willekeurig gekozen clustercentra. Het k-means algoritme kan meerdere malen worden uitgevoerd om dit effect te verminderen.

K-means is een eenvoudig algoritme dat aan vele probleemdomeinen is aangepast. Zoals we zullen zien, is het een goede kandidaat voor uitbreiding om te werken met fuzzy feature vectoren.

De k-means procedure kan worden gezien als een greedy algoritme voor het verdelen van de n monsters in k clusters om zo de som van de gekwadrateerde afstanden tot de clustermiddens te minimaliseren. De procedure heeft enkele zwakke punten:

• De manier om de gemiddelden te initialiseren is niet gespecificeerd. Een populaire manier om te beginnen is om willekeurig k van de monsters te kiezen.
• Het kan gebeuren dat de verzameling monsters die het dichtst bij mi ligt leeg is, zodat mi niet kan worden bijgewerkt. Dit is een probleem dat bij de implementatie moet worden aangepakt, maar dat meestal wordt genegeerd.
• De resultaten hangen af van de waarde van k en er is geen optimale manier om een beste “k” te beschrijven.

Dit laatste probleem is bijzonder lastig, omdat we vaak niet kunnen weten hoeveel clusters er zijn. In het voorbeeld hierboven levert hetzelfde algoritme, toegepast op dezelfde gegevens, de volgende 3-means clustering op. Is deze beter of slechter dan de 2-means clustering?

Er bestaat helaas geen algemene theoretische oplossing om het optimale aantal clusters voor een gegeven gegevensverzameling te vinden. Een eenvoudige aanpak is om de resultaten van meerdere runs met verschillende k-klassen te vergelijken en de beste te kiezen volgens een bepaald criterium, maar we moeten voorzichtig zijn, want een toename van k leidt per definitie tot kleinere foutfunctiewaarden, maar verhoogt ook het risico van overfitting.

Fuzzy K-Means Clustering

In fuzzy clustering heeft elk punt een waarschijnlijkheid dat het bij elke cluster hoort, in plaats van dat het volledig bij slechts één cluster hoort, zoals het geval is in de traditionele k-means. Fuzzy k-means probeert specifiek om te gaan met het probleem waar punten enigszins tussen centra of anderszins dubbelzinnig zijn door afstand te vervangen door waarschijnlijkheid, die natuurlijk een of andere functie van de afstand kan zijn, zoals een waarschijnlijkheid ten opzichte van de inverse van de afstand. Fuzzy k-means gebruikt een gewogen centroïde gebaseerd op deze waarschijnlijkheden. De processen van initialisatie, iteratie en beëindiging zijn dezelfde als die welke in k-means worden gebruikt. De resulterende clusters kunnen het best worden geanalyseerd als probabilistische verdelingen in plaats van een harde toewijzing van labels. Men moet zich realiseren dat k-means een speciaal geval is van fuzzy k-means wanneer de gebruikte waarschijnlijkheidsfunctie eenvoudigweg 1 is als het gegevenspunt het dichtst bij een centroïde ligt en anders 0.

Het fuzzy k-means algoritme is als volgt:

• Veronderstel een vast aantal clusters K.
• Initialisatie: Initialiseer willekeurig de k-means μk geassocieerd met de clusters en bereken de waarschijnlijkheid dat elk gegevenspunt Xi lid is van een gegeven cluster K,
  P(PointXiHasLabelK|Xi,K).
• Iteratie: Herbereken het zwaartepunt van de cluster als het gewogen zwaartepunt gegeven de waarschijnlijkheid van lidmaatschap van alle gegevenspunten Xi :

• Beëindiging: Itereren tot de convergentie is bereikt of tot een door de gebruiker gespecificeerd aantal iteraties is bereikt (de iteratie kan vastlopen op enkele lokale maxima of minima)

Voor een beter begrip kunnen we dit eenvoudige monodimensionale voorbeeld bekijken. Stel dat we, gegeven een bepaalde gegevensverzameling, deze weergeven als verdeeld over een as. De onderstaande figuur laat dit zien:

Kijkend naar het plaatje, kunnen we twee clusters identificeren in de nabijheid van de twee gegevensconcentraties. We zullen ze aanduiden met “A” en “B”. In de eerste benadering die in deze tutorial werd getoond – het k-means algoritme – associeerden we elk gegevenspunt met een specifiek zwaartepunt; daarom zag deze lidmaatschapsfunctie er als volgt uit:

In de Fuzzy k-means benadering daarentegen behoort hetzelfde gegevenspunt niet uitsluitend tot een welbepaalde cluster, maar kan het in een middenweg worden geplaatst. In dit geval volgt de lidmaatschapsfunctie een vloeiender lijn om aan te geven dat elk gegevenspunt tot meerdere clusters kan behoren met een verschillende mate van lidmaatschap.

In de bovenstaande figuur behoort het gegevenspunt dat als een rood gemarkeerde stip wordt weergegeven, meer tot de B-cluster dan tot de A-cluster. De waarde 0,2 van ‘m’ geeft aan in welke mate een dergelijk gegevenspunt tot A behoort.

Hiërarchische clusteralgoritmen

Gegeven voor een verzameling van N te clusteren items en een N*N afstands(of similariteits)matrix, is het basisproces van hiërarchisch clusteren als volgt:

• Start met het toewijzen van elk item aan een cluster, zodat als u N items hebt, u nu N clusters hebt, die elk slechts één item bevatten. Laat de afstanden (gelijkenissen) tussen de clusters dezelfde zijn als de afstanden (gelijkenissen) tussen de items die ze bevatten.
• Zoek het dichtstbijzijnde (meest gelijkende) paar clusters en voeg ze samen tot één cluster, zodat je nu één cluster minder hebt.
• Bereken de afstanden (gelijkenissen) tussen de nieuwe cluster en elk van de oude clusters.
• Herhaal stap 2 en 3 totdat alle items zijn geclusterd in één cluster van grootte N.

Clustering as a Mixture of Gaussians

Er is nog een andere manier om met clusteringsproblemen om te gaan: een modelgebaseerde aanpak, die erin bestaat bepaalde modellen voor clusters te gebruiken en te proberen de fit tussen de gegevens en het model te optimaliseren.

In de praktijk kan elk cluster mathematisch worden voorgesteld door een parametrische verdeling, zoals een Gaussische. De gehele gegevensverzameling wordt daarom gemodelleerd door een mengsel van deze verdelingen.
Een mengselmodel met hoge waarschijnlijkheid heeft de volgende eigenschappen:

• componentverdelingen hebben hoge “pieken” (gegevens in één cluster zijn strak);
• het mengselmodel “dekt” de gegevens goed (dominante patronen in de gegevens worden gevat door componentverdelingen).

Belangrijkste voordelen van clustering op basis van modellen:

• welbestudeerde statistische inferentietechnieken beschikbaar;
• flexibiliteit in het kiezen van de componentverdeling;
• krijg een dichtheidsschatting voor elk cluster;
• een “zachte” classificatie is beschikbaar.

Mengsel van Gaussianen
De meest gebruikte clustermethode van dit type is gebaseerd op het leren van een mengsel van Gaussianen:

Een mengselmodel is een mengsel van k componentverdelingen die tezamen een mengselverdeling f(x) vormen:

De αk vertegenwoordigt de bijdrage van de k-de component bij het construeren van f(x). In de praktijk wordt vaak gebruik gemaakt van parametrische verdelingen (bv. gaussians), omdat er veel werk is verricht om hun gedrag te begrijpen. Als je elke fk(x) vervangt door een gaussiaan, krijg je een zogenaamd gaussiaans mengselmodel (GMM).

Het EM-algoritme

Expectation-Maximization gaat ervan uit dat je gegevens uit meerdere multivariate normale verdelingen bestaan (merk op dat dit een zeer sterke aanname is, vooral als je het aantal clusters vastlegt!). Anders gezegd, EM is een algoritme voor het maximaliseren van een likelihood functie wanneer sommige van de variabelen in je model niet-waargenomen zijn (d.w.z. wanneer je latente variabelen hebt).
Je zou je eerlijk kunnen afvragen, als we alleen maar proberen een functie te maximaliseren, waarom gebruiken we dan niet gewoon de bestaande machinerie voor het maximaliseren van een functie. Welnu, als je dit probeert te maximaliseren door afgeleiden te nemen en die op nul te stellen, ontdek je dat in veel gevallen de eerste-orde voorwaarden geen oplossing hebben. Er is een kip-en-ei-probleem in die zin dat je, om je modelparameters op te lossen, de verdeling van je niet-waargenomen gegevens moet kennen; maar de verdeling van je niet-waargenomen gegevens is een functie van je modelparameters.

Expectation-Maximization probeert dit te omzeilen door iteratief een verdeling voor de niet-waargenomen gegevens te raden, vervolgens de modelparameters te schatten door iets te maximaliseren dat een ondergrens is voor de eigenlijke likelihoodfunctie, en dit te herhalen tot de convergentie:

Het Expectation-Maximization-algoritme

• Start met gissingen voor waarden van uw modelparameters
• E-stap: Gebruik voor elk gegevenspunt met ontbrekende waarden uw modelvergelijking om de verdeling van de ontbrekende gegevens op te lossen, gegeven uw huidige gissing van de modelparameters en gegeven de waargenomen gegevens (merk op dat u een verdeling oplost voor elke ontbrekende waarde, niet voor de verwachte waarde). Nu we een verdeling hebben voor elke ontbrekende waarde, kunnen we de verwachting van de likelihood functie berekenen met betrekking tot de niet-waargenomen variabelen. Als onze gok voor de modelparameter juist was, zal deze verwachte waarschijnlijkheid de werkelijke waarschijnlijkheid van onze waargenomen gegevens zijn; als de parameters niet juist waren, zal het slechts een ondergrens zijn.
• M-stap: Nu we een verwachte waarschijnlijkheidsfunctie hebben zonder niet-waargenomen variabelen erin, maximaliseert u de functie zoals u dat zou doen in het volledig waargenomen geval, om een nieuwe schatting van uw modelparameters te krijgen.
• Herhaal dit tot de convergentie.

Problemen in verband met clustering

Er zijn een aantal problemen met clustering. Daaronder:

• de omgang met een groot aantal dimensies en een groot aantal gegevensitems kan problematisch zijn wegens de tijdscomplexiteit;
• de doeltreffendheid van de methode hangt af van de definitie van “afstand” (voor clusteren op basis van afstand). Als er geen voor de hand liggende afstandsmaat bestaat, moeten we die “definiëren”, wat niet altijd gemakkelijk is, vooral in multidimensionale ruimten;
• het resultaat van het clusteralgoritme (dat in veel gevallen zelf arbitrair kan zijn) kan op verschillende manieren worden geïnterpreteerd.

Mogelijke toepassingen

Clustering-algoritmen kunnen op vele gebieden worden toegepast, bijvoorbeeld:

• Marketing: het vinden van groepen klanten met vergelijkbaar gedrag gegeven een grote database van klantgegevens die hun eigenschappen en eerdere aankooprecords bevatten;
• Biologie: classificatie van planten en dieren gegeven hun kenmerken;
• Verzekeringen: identificeren van groepen houders van autoverzekeringspolissen met een hoge gemiddelde schadelast; identificeren van fraude;
• Aardbevingsstudies: clusteren van waargenomen epicentra van aardbevingen om gevaarlijke zones te identificeren;
• World Wide Web: documentclassificatie; clusteren van webloggegevens om groepen met vergelijkbare toegangspatronen te ontdekken.