Det är ingen dålig tid att vara datavetare. Seriösa människor kan finna intresse för dig om du vänder konversationen mot ”Big Data”, och resten av festpubliken blir fascinerad när du nämner ”Artificiell intelligens” och ”Maskininlärning”. Till och med Google tycker att du inte är dålig och att du blir ännu bättre. Det finns många ”smarta” algoritmer som hjälper datavetare att utföra sina trollkonster. Allt kan verka komplicerat, men om vi förstår och organiserar algoritmerna lite grann är det inte ens så svårt att hitta och tillämpa den som vi behöver.
Kurser om datautvinning eller maskininlärning brukar börja med klusterindelning, eftersom det är både enkelt och användbart. Det är en viktig del av ett något bredare område för oövervakad inlärning, där de data vi vill beskriva inte är märkta. I de flesta fall handlar det om att användaren inte har gett oss mycket information om vad som är det förväntade resultatet. Algoritmen har bara uppgifterna och bör göra sitt bästa. I vårt fall ska den utföra klusterindelning – separera data i grupper (kluster) som innehåller liknande datapunkter, samtidigt som skillnaderna mellan grupperna är så stora som möjligt. Datapunkterna kan representera vad som helst, t.ex. våra kunder. Klusterbildning kan vara användbart om vi till exempel vill gruppera liknande användare och sedan köra olika marknadsföringskampanjer för varje kluster.
K-Means Clustering
Efter den nödvändiga introduktionen fortsätter kurser i datautvinning alltid med K-Means; en effektiv, allmänt använd, allsidig klusteralgoritm. Innan den verkligen körs måste vi definiera en avståndsfunktion mellan datapunkterna (t.ex. euklidiskt avstånd om vi vill klustra punkter i rummet), och vi måste ställa in antalet kluster vi vill ha (k).
Algoritmen börjar med att välja k punkter som utgångscentroider (”centroider” för kluster). Vi kan bara välja k slumpmässiga punkter eller använda något annat tillvägagångssätt, men att välja slumpmässiga punkter är en bra början. Sedan upprepar vi iterativt två steg:
-
Tilldelningssteg: Var och en av m punkter från vårt dataset tilldelas ett kluster som representeras av den närmaste av de k centroiderna. För varje punkt beräknar vi avstånden till varje centroid och väljer helt enkelt den minst avlägsna.
-
Aktualiseringssteg: För varje kluster beräknas en ny centroid som medelvärdet av alla punkter i klustret. Från föregående steg har vi en uppsättning punkter som tilldelas ett kluster. Nu beräknar vi för varje sådan uppsättning ett medelvärde som vi förklarar vara klustrets nya centroid.
Efter varje iteration rör sig centroiderna långsamt och det totala avståndet från varje punkt till den tilldelade centroiden blir lägre och lägre. De två stegen alterneras tills konvergens uppnås, det vill säga tills det inte längre sker några ändringar i klustertilldelningen. Efter ett antal iterationer kommer samma uppsättning punkter att tilldelas varje centroid, vilket därför leder till samma centroider igen. K-Means konvergerar garanterat till ett lokalt optimum. Detta behöver dock inte nödvändigtvis vara den bästa övergripande lösningen (globalt optimum).
Det slutgiltiga klusterresultatet kan bero på valet av initiala centroider, så man har tänkt mycket på detta problem. En enkel lösning är att bara köra K-Means ett par gånger med slumpmässiga inledande tilldelningar. Vi kan sedan välja det bästa resultatet genom att ta det som har den minsta summan av avstånden från varje punkt till dess kluster – det felvärde som vi försöker minimera i första hand.
Andra tillvägagångssätt för att välja initiala punkter kan förlita sig på att välja avlägsna punkter. Detta kan leda till bättre resultat, men vi kan få problem med outliers, dessa sällsynta ensamma punkter som bara är ”off” som bara kan vara några fel. Eftersom de är långt ifrån något meningsfullt kluster kan varje sådan punkt hamna i ett eget ”kluster”. En bra balans är K-Means++ variant , vars initialisering fortfarande väljer slumpmässiga punkter, men med en sannolikhet som är proportionell mot det kvadratiska avståndet från de tidigare tilldelade centroiderna. Punkter som ligger längre bort kommer att ha högre sannolikhet att väljas som startcentroider. Följaktligen, om det finns en grupp av punkter, blir sannolikheten att en punkt från gruppen kommer att väljas också högre när deras sannolikheter adderas, vilket löser problemet med outlier som vi nämnde.
K-Means++ är också standardinitialiseringen för Pythons Scikit-learn K-Means-implementation. Om du använder Python kan detta vara ditt favoritbibliotek. För Java kan Weka-biblioteket vara en bra 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-exemplet ovan använde vi ett standardexemplariskt datamaterial ”Iris”, som innehåller blommans kronblad- och bladdimension för tre olika arter av iris. Vi klustrade dessa i tre kluster och jämförde de erhållna klustren med de faktiska arterna (målet) för att se att de stämmer perfekt överens.
I det här fallet visste vi att det fanns tre olika kluster (arter), och K-Means kände igen korrekt vilka som hör ihop. Men hur väljer vi ett bra antal kluster k i allmänhet? Den här typen av frågor är ganska vanliga inom maskininlärning. Om vi begär fler kluster kommer de att vara mindre, och därför kommer det totala felet (summan av avstånden från punkterna till deras tilldelade kluster) att bli mindre. Är det då en bra idé att bara ställa in ett större k? Vi kan sluta med att ha k = m, det vill säga att varje punkt är sin egen centroid och att varje kluster endast har en punkt. Ja, det totala felet är 0, men vi fick inte en enklare beskrivning av våra data, och den är inte heller tillräckligt generell för att täcka in några nya punkter som kan dyka upp. Detta kallas överanpassning, och det vill vi inte ha.
Ett sätt att hantera detta problem är att inkludera ett visst straff för ett större antal kluster. Vi försöker alltså nu att minimera inte bara felet, utan även fel + straffavgift. Felet kommer bara att konvergera mot noll när vi ökar antalet kluster, men straffet kommer att öka. Vid vissa punkter kommer vinsten av att lägga till ytterligare ett kluster att vara mindre än det införda straffet, och vi kommer att få det optimala resultatet. En lösning som använder Bayesian Information Criterion (BIC) för detta ändamål kallas X-Means .
En annan sak som vi måste definiera ordentligt är avståndsfunktionen. Ibland är det en okomplicerad uppgift, en logisk uppgift med tanke på datans natur. För punkter i rummet är euklidiskt avstånd en självklar lösning, men det kan vara knepigt för egenskaper i olika ”enheter”, för diskreta variabler osv. Detta kan kräva en hel del domänkunskap. Eller så kan vi be maskininlärning om hjälp. Vi kan faktiskt försöka lära oss distansfunktionen. Om vi har en träningsuppsättning av punkter som vi vet hur de ska grupperas (dvs. punkter märkta med sina kluster) kan vi använda tekniker för övervakad inlärning för att hitta en bra funktion och sedan tillämpa den på vår måluppsättning som ännu inte är klustrad.
Metoden som används i K-Means, med sina två alternerande steg, påminner om en Expectation-Maximization (EM)-metod. Den kan faktiskt betraktas som en mycket enkel version av EM. Den bör dock inte förväxlas med den mer genomarbetade klusteralgoritmen EM, även om den delar vissa av samma principer.
EM Klustering
Så, med K-Means klustering tilldelas varje punkt bara ett enda kluster, och ett kluster beskrivs endast av dess centroid. Detta är inte alltför flexibelt, eftersom vi kan få problem med kluster som överlappar varandra eller kluster som inte har en cirkulär form. Med EM Clustering kan vi nu gå ett steg längre och beskriva varje kluster med dess centroid (medelvärde), kovarians (så att vi kan få elliptiska kluster) och vikt (klustrets storlek). Sannolikheten att en punkt tillhör ett kluster ges nu av en multivariat gaussisk sannolikhetsfördelning (multivariat – beroende på flera variabler). Det innebär också att vi kan beräkna sannolikheten för att en punkt ligger under en Gaussisk ”klocka”, dvs. sannolikheten för att en punkt tillhör ett kluster.
Vi startar nu EM-förfarandet genom att för varje punkt beräkna sannolikheterna för att den tillhör vart och ett av de aktuella klustren (som, återigen, kan skapas slumpmässigt i början). Detta är E-steget. Om ett kluster är en riktigt bra kandidat för en punkt kommer det att ha en sannolikhet nära ett. Två eller flera kluster kan dock vara godtagbara kandidater, så punkten har en fördelning av sannolikheter över kluster. Denna egenskap hos algoritmen, att punkter inte tillhör begränsat till ett kluster, kallas ”mjuk klusterbildning”.
M-steget räknar nu om parametrarna för varje kluster, med hjälp av tilldelningen av punkter till den tidigare uppsättningen kluster. För att beräkna ett klusters nya medelvärde, kovarians och vikt viktas varje punktdata med dess sannolikhet att tillhöra klustret, vilket beräknades i föregående steg.
Alternera dessa två steg kommer att öka den totala log-likelihood tills den konvergerar. Återigen kan maximum vara lokalt, så vi kan köra algoritmen flera gånger för att få bättre kluster.
Om vi nu vill bestämma ett enda kluster för varje punkt kan vi helt enkelt välja det mest sannolika klustret. När vi har en sannolikhetsmodell kan vi också använda den för att generera liknande data, det vill säga för att ta ett urval av fler punkter som liknar de data vi observerat.
Affinity Propagation
Affinity Propagation (AP) publicerades av Frey och Dueck 2007, och blir bara mer och mer populär på grund av sin enkelhet, allmänna tillämpbarhet och prestanda. Den håller på att ändra sin status från state of the art till de facto standard.
De största nackdelarna med K-Means och liknande algoritmer är att man måste välja antalet kluster och att välja den initiala uppsättningen punkter. Affinity Propagation tar istället som indata mått på likhet mellan par av datapunkter och betraktar samtidigt alla datapunkter som potentiella exemplar. Realvärderade meddelanden utbyts mellan datapunkterna tills en högkvalitativ uppsättning exemplar och motsvarande kluster gradvis uppstår.
Som indata kräver algoritmen att vi tillhandahåller två uppsättningar data:
-
Likheter mellan datapunkterna, som representerar hur väl lämpad en punkt är för att vara en annan punkts exemplar. Om det inte finns någon likhet mellan två punkter, eftersom de inte kan tillhöra samma kluster, kan denna likhet utelämnas eller sättas till -Infinity beroende på implementering.
-
Preferenser, som representerar varje datapunkts lämplighet att vara ett exemplar. Vi kan ha viss förhandsinformation om vilka punkter som skulle kunna gynnas för denna roll, och därför kan vi representera det genom preferenser.
Både likheter och preferenser representeras ofta genom en enda matris, där värdena på huvuddiagonalen representerar preferenser. Matrisrepresentation är bra för täta datamängder. När förbindelserna mellan punkter är glesa är det mer praktiskt att inte lagra hela n x n-matrisen i minnet, utan i stället spara en lista över likheter med anslutna punkter. Bakom scenen är ”utbyte av meddelanden mellan punkter” samma sak som att manipulera matriser, och det är bara en fråga om perspektiv och genomförande.
Algoritmen körs sedan genom ett antal iterationer, tills den konvergerar. Varje iteration har två steg för överföring av meddelanden:
-
Beräkning av ansvarsområden: Ansvaret r(i, k) återspeglar de ackumulerade bevisen för hur väl lämpad punkt k är att fungera som exemplar för punkt i, med hänsyn till andra potentiella exemplar för punkt i. Ansvaret skickas från datapunkt i till kandidatexemplarpunkt k.
-
Beräkning av tillgängligheter: Tillgänglighet a(i, k) återspeglar de samlade bevisen för hur lämpligt det skulle vara för punkt i att välja punkt k som sitt exemplar, med hänsyn till stödet från andra punkter för att punkt k bör vara ett exemplar. Tillgängligheten skickas från kandidatexemplarpunkten k till punkt i.
För att beräkna ansvarsområden använder algoritmen ursprungliga likheter och tillgängligheter som beräknats i föregående iteration (inledningsvis sätts alla tillgängligheter till noll). Ansvaret sätts till den ingående likheten mellan punkt i och punkt k som dess exemplar, minus den största summan av likheten och tillgängligheten mellan punkt i och andra kandidatexemplar. Logiken bakom beräkningen av hur lämplig en punkt är som exemplar är att den gynnas mer om den ursprungliga a priori-preferensen var högre, men ansvaret blir lägre när det finns en liknande punkt som anser sig vara en bra kandidat, så det finns en ”konkurrens” mellan de två tills en av dem bestäms i någon iteration.
Bedömning av tillgängligheter använder alltså beräknade ansvarsområden som ett bevis på om varje kandidat skulle bli ett bra exemplar. Tillgängligheten a(i, k) sätts till självansvaret r(k, k) plus summan av de positiva ansvarsområden som kandidatexemplar k får från andra punkter.
Slutligt kan vi ha olika stoppkriterier för att avsluta förfarandet, t.ex. när förändringarna i värdena hamnar under ett visst tröskelvärde, eller när det maximala antalet iterationer är uppnått. Vid varje punkt genom Affinity Propagation-förfarandet ger summan av matriserna Ansvar (r) och Tillgänglighet (a) oss den klusterinformation vi behöver: för punkt i representerar k med maximal r(i, k) + a(i, k) punkt i:s exemplar. Om vi bara behöver mängden exemplar kan vi också skanna huvuddiagonalen. Om r(i, i) + a(i, i) > 0 är punkt i ett exemplar.
Vi har sett att med K-Means och liknande algoritmer kan det vara svårt att bestämma antalet kluster. Med AP behöver vi inte ange det uttryckligen, men det kan ändå behöva justeras om vi får antingen fler eller färre kluster än vad vi anser vara optimalt. Lyckligtvis kan vi bara genom att justera preferenserna sänka eller höja antalet kluster genom att justera preferenserna. Om vi ställer in preferenserna på ett högre värde får vi fler kluster, eftersom varje punkt är ”säkrare” på sin lämplighet att vara ett exemplar och därför är svårare att ”slå” och inkludera den under någon annan punkts ”dominans”. Omvänt kommer lägre preferenser att leda till färre kluster, som om de säger ”nej, nej, snälla, du är ett bättre exemplar, jag går med i ditt kluster”. Som en allmän regel kan vi ställa in alla preferenser på medianlikheten för ett medelstort till stort antal kluster, eller på den lägsta likheten för ett måttligt antal kluster. Det kan dock behövas ett par körningar med justerade preferenser för att få ett resultat som exakt passar våra behov.
Hierarchical Affinity Propagation är också värt att nämna, som en variant av algoritmen som hanterar kvadratisk komplexitet genom att dela upp datamängden i ett par delmängder, klustra dem separat och sedan utföra den andra nivån av klusterbildning.
I slutändan…
Det finns en hel rad klusteralgoritmer, var och en med sina för- och nackdelar när det gäller vilken typ av data de med, tidskomplexitet, svagheter och så vidare. För att nämna fler algoritmer finns det till exempel Hierarchical Agglomerative Clustering (eller Linkage Clustering), som är bra när vi inte nödvändigtvis har cirkulära (eller hypersfäriska) kluster och inte vet antalet kluster i förväg. Den börjar med att varje punkt är ett separat kluster och arbetar genom att förena två närmaste kluster i varje steg tills allt är i ett stort kluster.
Med Hierarchical Agglomerative Clustering kan vi enkelt bestämma antalet kluster i efterhand genom att klippa dendrogrammet (träddiagrammet) horisontellt där vi finner det lämpligt. Den är också upprepningsbar (ger alltid samma svar för samma dataset), men har också en högre komplexitet (kvadratisk).
Då är DBSCAN (Density-Based Spatial Clustering of Applications with Noise) också en algoritm värd att nämna. Den grupperar punkter som är tätt packade tillsammans, expanderar kluster i alla riktningar där det finns närliggande punkter, och hanterar på så sätt olika former av kluster.
Dessa algoritmer förtjänar en egen artikel, och vi kan utforska dem i ett separat inlägg senare.
Det krävs erfarenhet med en del trial and error för att veta när man ska använda den ena eller den andra algoritmen. Som tur är har vi en rad implementeringar i olika programmeringsspråk, så att prova dem kräver bara lite vilja att leka.