Det er ikke et dårligt tidspunkt at være dataforsker på. Seriøse mennesker kan finde interesse for dig, hvis du drejer samtalen i retning af “Big Data”, og resten af festfolket vil blive fascineret, når du nævner “Artificial Intelligence” og “Machine Learning”. Selv Google mener, at du ikke er dårlig, og at du er ved at blive endnu bedre. Der findes en masse “smarte” algoritmer, som hjælper dataloger med at udføre deres trolddomskunst. Det hele kan virke kompliceret, men hvis vi forstår og organiserer algoritmerne en smule, er det ikke engang så svært at finde og anvende den, vi har brug for.
Kurser om datamining eller maskinlæring vil normalt starte med clustering, fordi det både er enkelt og nyttigt. Det er en vigtig del af et noget bredere område, nemlig uovervåget læring, hvor de data, vi ønsker at beskrive, ikke er mærket. I de fleste tilfælde er det, hvor brugeren ikke har givet os mange oplysninger om, hvad der er det forventede output. Algoritmen har kun dataene, og den skal gøre det bedste, den kan. I vores tilfælde skal den udføre clustering – opdeling af data i grupper (clusters), der indeholder lignende datapunkter, mens forskelligheden mellem grupperne er så stor som muligt. Datapunkterne kan repræsentere hvad som helst, f.eks. vores kunder. Clustering kan være nyttigt, hvis vi f.eks. ønsker at gruppere lignende brugere og derefter køre forskellige markedsføringskampagner på hver klynge.
K-Means Clustering
Efter den nødvendige introduktion fortsætter kurser i datamining altid med K-Means; en effektiv, meget anvendt og allround clustering-algoritme. Før vi rent faktisk kører den, skal vi definere en afstandsfunktion mellem datapunkter (f.eks. euklidisk afstand, hvis vi ønsker at klynge punkter i rummet), og vi skal indstille det antal klynger, vi ønsker (k).
Algoritmen begynder med at vælge k punkter som startcentroider (“centre” for klynger). Vi kan bare vælge k tilfældige punkter, eller vi kan bruge en anden fremgangsmåde, men det er en god start at vælge tilfældige punkter. Derefter gentager vi iterativt to trin:
-
Tildelingstrin: Hvert af m punkter fra vores datasæt tildeles en klynge, som er repræsenteret af den nærmeste af de k centroider. For hvert punkt beregner vi afstandene til hver centroid og vælger simpelthen den mindst fjerne.
-
Aktualiseringstrin: For hver klynge beregnes en ny centroid som gennemsnittet af alle punkter i klyngen. Fra det foregående trin har vi et sæt punkter, som er tildelt en klynge. Nu beregner vi for hvert sådant sæt et gennemsnit, som vi erklærer for en ny centroid for klyngen.
Efter hver iteration bevæger centroiderne sig langsomt, og den samlede afstand fra hvert punkt til dets tildelte centroid bliver mindre og mindre. De to trin skiftes indtil konvergens, dvs. indtil der ikke længere er nogen ændringer i klyngetildelingen. Efter et antal gentagelser vil det samme sæt af punkter blive tildelt hver centroid, hvilket derfor igen fører til de samme centroider. K-Means er garanteret at konvergere til et lokalt optimum. Det behøver dog ikke nødvendigvis at være den bedste samlede løsning (globalt optimum).
Det endelige klyngeresultat kan afhænge af valget af de indledende centroider, så der er gjort sig mange overvejelser om dette problem. En simpel løsning er blot at køre K-Means et par gange med tilfældige indledende tildelinger. Vi kan så vælge det bedste resultat ved at tage det med den mindste summen af afstandene fra hvert punkt til dets klynge – den fejlværdi, som vi i første omgang forsøger at minimere.
Andre tilgange til udvælgelse af startpunkter kan være afhængige af at vælge fjerne punkter. Dette kan føre til bedre resultater, men vi kan have et problem med outliers, de sjældne alene punkter, der bare er “off”, som måske bare er nogle fejl. Da de er langt fra enhver meningsfuld klynge, kan hvert sådant punkt ende med at blive sin egen “klynge”. En god balance er K-Means++ variant , hvis initialisering stadig vil vælge tilfældige punkter, men med en sandsynlighed, der er proportional med den kvadratiske afstand fra de tidligere tildelte centroider. Punkter, der er længere væk, vil have større sandsynlighed for at blive valgt som startcentroider. Følgelig, hvis der er en gruppe af punkter, bliver sandsynligheden for at et punkt fra gruppen også højere, efterhånden som deres sandsynligheder lægges sammen, hvilket løser outlier-problemet, som vi nævnte.
K-Means++ er også standardinitialiseringen for Pythons Scikit-learn K-Means-implementering i Scikit-learn. Hvis du bruger Python, er dette måske dit foretrukne bibliotek. For Java kan Weka-biblioteket være en god 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)I Python-eksemplet ovenfor brugte vi et standard eksempeldatasæt ‘Iris’, som indeholder blomsterblad- og sepaldimensioner for tre forskellige arter af iris. Vi grupperede disse i tre klynger og sammenlignede de opnåede klynger med de faktiske arter (mål) for at se, at de passer perfekt sammen.
I dette tilfælde vidste vi, at der var tre forskellige klynger (arter), og K-Means genkendte korrekt, hvilke klynger der hører sammen. Men, hvordan vælger vi et godt antal klynger k generelt? Denne slags spørgsmål er ret almindelige inden for maskinlæring. Hvis vi anmoder om flere klynger, vil de være mindre, og derfor vil den samlede fejl (summen af afstandene fra punkterne til deres tildelte klynger) være mindre. Så er det en god idé bare at indstille et større k? Vi kan ende med at have k = m, dvs. at hvert punkt er sin egen centroid, og at hver klynge kun har ét punkt. Ja, den samlede fejl er 0, men vi fik ikke en enklere beskrivelse af vores data, og den er heller ikke generel nok til at dække nogle nye punkter, der måtte dukke op. Dette kaldes overfitting, og det ønsker vi ikke.
En måde at håndtere dette problem på er at inkludere en vis straf for et større antal klynger. Så vi forsøger nu at minimere ikke kun fejlen, men fejl + straf. Fejlen vil blot konvergere mod nul, efterhånden som vi øger antallet af klynger, men straffen vil vokse. På nogle punkter vil gevinsten ved at tilføje endnu en klynge være mindre end den indførte straf, og vi vil have det optimale resultat. En løsning, der bruger Bayesian Information Criterion (BIC) til dette formål, hedder X-Means .
En anden ting, vi skal definere korrekt, er afstandsfunktionen. Nogle gange er det en ukompliceret opgave, en logisk opgave i betragtning af dataenes karakter. For punkter i rummet er euklidisk afstand en oplagt løsning, men det kan være vanskeligt for funktioner med forskellige “enheder”, for diskrete variabler osv. Dette kan kræve en masse domæneviden. Eller vi kan bede maskinlæring om hjælp. Vi kan faktisk forsøge at lære afstandsfunktionen. Hvis vi har et træningssæt af punkter, som vi ved, hvordan de skal grupperes (dvs. punkter mærket med deres klynger), kan vi bruge superviserede indlæringsteknikker til at finde en god funktion og derefter anvende den på vores målsæt, der endnu ikke er grupperet.
Den metode, der anvendes i K-Means, ligner med sine to vekslende trin en Expectation-Maximization (EM)-metode. Faktisk kan den betragtes som en meget simpel version af EM. Den bør dog ikke forveksles med den mere omfattende EM-klyngealgoritme, selv om den deler nogle af de samme principper.
EM-klumpning
Så med K-Means-klumpning tilknyttes hvert punkt kun til en enkelt klynge, og en klynge beskrives kun ved dens centroid. Dette er ikke alt for fleksibelt, da vi kan få problemer med klynger, der overlapper hinanden, eller klynger, der ikke er af cirkulær form. Med EM Clustering kan vi nu gå et skridt videre og beskrive hver klynge ved hjælp af dens centroid (middelværdi), kovarians (så vi kan få elliptiske klynger) og vægt (klyngens størrelse). Sandsynligheden for, at et punkt tilhører en klynge, er nu givet ved en multivariat Gaussisk sandsynlighedsfordeling (multivariat – afhængig af flere variabler). Det betyder også, at vi kan beregne sandsynligheden for, at et punkt ligger under en gaussisk “klokke”, dvs. sandsynligheden for, at et punkt tilhører en klynge.
Vi starter nu EM-proceduren ved for hvert punkt at beregne sandsynlighederne for, at det tilhører hver af de aktuelle klynger (som igen kan være skabt tilfældigt i starten). Dette er E-trinnet. Hvis en klynge er en rigtig god kandidat for et punkt, vil den have en sandsynlighed tæt på 1. To eller flere klynger kan imidlertid være acceptable kandidater, så punktet har en fordeling af sandsynligheder over klynger. Denne egenskab ved algoritmen, at punkterne ikke tilhører begrænset til én klynge, kaldes “blød klyngedannelse”.
M-trinnet genberegner nu parametrene for hver klynge ved hjælp af tildelingerne af punkter til det foregående sæt af klynger. For at beregne den nye middelværdi, kovarians og vægt for en klynge vægtes hvert punktdata med dets sandsynlighed for at tilhøre klyngen, som beregnet i det foregående trin.
Alternering af disse to trin vil øge den samlede log-likelihood, indtil den konvergerer. Igen kan maksimum være lokalt, så vi kan køre algoritmen flere gange for at få bedre klynger.
Hvis vi nu ønsker at bestemme en enkelt klynge for hvert punkt, kan vi blot vælge den mest sandsynlige klynge. Når vi har en sandsynlighedsmodel, kan vi også bruge den til at generere lignende data, dvs. til at udtage flere punkter, der ligner de data, vi har observeret.
Affinity Propagation
Affinity Propagation (AP) blev offentliggjort af Frey og Dueck i 2007 og bliver kun mere og mere populær på grund af sin enkelhed, generelle anvendelighed og ydeevne. Den er ved at ændre sin status fra state of the art til de facto standard.
De største ulemper ved K-Means og lignende algoritmer er, at man skal vælge antallet af klynger og vælge det oprindelige sæt af punkter. Affinity Propagation tager i stedet som input målinger af lighed mellem par af datapunkter og betragter samtidig alle datapunkter som potentielle eksemplarer. Der udveksles meddelelser med reelle værdier mellem datapunkterne, indtil der gradvist opstår et sæt af eksemplarer og tilsvarende klynger af høj kvalitet.
Algoritmen kræver, at vi som input leverer to sæt data:
-
Ligheder mellem datapunkterne, der repræsenterer, hvor velegnet et punkt er til at være et andet punkts eksemplar. Hvis der ikke er nogen lighed mellem to punkter, dvs. at de ikke kan tilhøre den samme klynge, kan denne lighed udelades eller sættes til -Infinity afhængigt af implementeringen.
-
Præferencer, der repræsenterer hvert datapunkts egnethed til at være et eksemplar. Vi kan have nogle a priori oplysninger om, hvilke punkter der kunne foretrækkes til denne rolle, og derfor kan vi repræsentere det gennem præferencer.
Både ligheder og præferencer repræsenteres ofte gennem en enkelt matrix, hvor værdierne på hoveddiagonalen repræsenterer præferencer. Matrixrepræsentation er god til tætte datasæt. Når forbindelserne mellem punkterne er sparsomme, er det mere praktisk ikke at gemme hele n x n-matricen i hukommelsen, men i stedet at opbevare en liste over ligheder med forbundne punkter. Bagved er “udveksling af meddelelser mellem punkter” det samme som at manipulere matricer, og det er kun et spørgsmål om perspektiv og implementering.
Algoritmen kører derefter gennem et antal iterationer, indtil den konvergerer. Hver iteration har to message-passing-trin:
-
Beregning af ansvarsområder: Ansvaret r(i, k) afspejler den akkumulerede dokumentation for, hvor velegnet punkt k er til at tjene som eksemplar for punkt i, idet der tages hensyn til andre potentielle eksemplarer for punkt i. Ansvaret sendes fra datapunkt i til kandidateksemplarpunkt k.
-
Beregning af tilgængelighed: Tilgængelighed a(i, k) afspejler den akkumulerede dokumentation for, hvor hensigtsmæssigt det ville være for punkt i at vælge punkt k som sit eksemplar, idet der tages hensyn til støtten fra andre punkter til, at punkt k bør være et eksemplar. Tilgængeligheden sendes fra kandidateksemplarpunkt k til punkt i.
For at beregne ansvarsområder bruger algoritmen de oprindelige ligheder og tilgængeligheder, der er beregnet i den foregående iteration (i begyndelsen er alle tilgængeligheder sat til nul). Ansvaret sættes til den indgående lighed mellem punkt i og punkt k som dets eksemplar minus den største af lighederne og tilgængelighedssummen mellem punkt i og andre kandidateksemplarer. Logikken bag beregningen af, hvor egnet et punkt er til et eksemplar, er, at det favoriseres mere, hvis den oprindelige a priori præference var højere, men ansvaret bliver lavere, når der er et lignende punkt, der anser sig selv for en god kandidat, så der er en “konkurrence” mellem de to, indtil den ene er besluttet i en eller anden iteration.
Beregning af tilgængeligheder bruger altså beregnede ansvarligheder som bevis for, om hver kandidat ville være et godt eksemplar. Tilgængelighed a(i, k) sættes til selvansvarligheden r(k, k) plus summen af de positive ansvarligheder, som kandidateksemplar k modtager fra andre punkter.
Sluttelig kan vi have forskellige stopkriterier for at afslutte proceduren, f.eks. når ændringer i værdierne falder under en vis tærskelværdi, eller når det maksimale antal iterationer er nået. På ethvert punkt gennem Affinity Propagation-proceduren giver summen af Responsibility (r) og Availability (a) matricerne os de klyngeoplysninger, vi har brug for: for punkt i repræsenterer k med det maksimale r(i, k) + a(i, k) punkt i’s eksemplar. Hvis vi blot har brug for eksemplarerne, kan vi også scanne hoveddiagonalen. Hvis r(i, i) + a(i, i) > 0, er punkt i et eksemplar.
Vi har set, at med K-Means og lignende algoritmer kan det være vanskeligt at afgøre antallet af klynger. Med AP behøver vi ikke at angive det eksplicit, men det kan stadig kræve en vis justering, hvis vi får enten flere eller færre klynger, end vi måske finder optimalt. Heldigvis kan vi ved blot at justere præferencerne sænke eller hæve antallet af klynger ved at justere præferencerne. Hvis præferencerne sættes til en højere værdi, vil vi få flere klynger, da hvert punkt er “mere sikkert” på sin egnethed til at være et eksemplar og derfor er sværere at “slå” og inkludere det under et andet punkts “dominans”. Omvendt vil lavere præferencer resultere i færre klynger; som om de siger “nej, nej, nej, vær sød, du er et bedre eksemplar, jeg vil være med i din klynge”. Som en generel regel kan vi sætte alle præferencer til medianligheden for et mellemstort til stort antal klynger eller til den laveste lighed for et moderat antal klynger. Det kan dog være nødvendigt med et par kørsler med justering af præferencerne for at få det resultat, der passer nøjagtigt til vores behov.
Hierarchical Affinity Propagation er også værd at nævne som en variant af algoritmen, der håndterer kvadratisk kompleksitet ved at opdele datasættet i et par delmængder, klynge dem separat og derefter udføre det andet niveau af klyngedannelse.
I sidste ende…
Der findes en lang række clustering-algoritmer, som hver især har deres fordele og ulemper med hensyn til hvilken type data de med, tidskompleksitet, svagheder og så videre. For at nævne flere algoritmer, er der f.eks. Hierarchical Agglomerative Clustering (eller Linkage Clustering), der er god til når vi ikke nødvendigvis har cirkulære (eller hyperkugleformede) klynger, og ikke kender antallet af klynger på forhånd. Den starter med, at hvert punkt er en separat klynge, og arbejder ved at sammenføje to nærmeste klynger i hvert trin, indtil alt er i én stor klynge.
Med Hierarchical Agglomerative Clustering kan vi let bestemme antallet af klynger bagefter ved at klippe dendrogrammet (trædiagrammet) horisontalt, hvor vi finder det passende. Den er også gentagelig (giver altid det samme svar for det samme datasæt), men har også en højere kompleksitet (kvadratisk).
Dernæst er DBSCAN (Density-Based Spatial Clustering of Applications with Noise) også en algoritme, der er værd at nævne. Den grupperer punkter, der er tæt pakket sammen, og udvider klynger i enhver retning, hvor der er punkter i nærheden, og håndterer således forskellige former for klynger.
Disse algoritmer fortjener en artikel for sig selv, og vi kan udforske dem i et separat indlæg senere.
Det kræver erfaring med en del trial and error at vide, hvornår man skal bruge den ene eller den anden algoritme. Heldigvis har vi en række implementeringer i forskellige programmeringssprog, så det kræver kun lidt lyst til at lege at prøve dem af.