En opgave, der involverer maskinlæring, er måske ikke lineær, men den har en række velkendte trin:
- Problemdefinition.
- Forberedelse af data.
- Lær en underliggende model.
- Forbedre den underliggende model ved kvantitative og kvalitative evalueringer.
- Præsentere modellen.
En god måde at komme til orde med et nyt problem på er at arbejde sig igennem at identificere og definere problemet på den bedst mulige måde og lære en model, der indfanger meningsfuld information fra dataene. Selv om problemer inden for mønstergenkendelse og maskinlæring kan være af forskellig art, kan de overordnet set inddeles i tre kategorier:
- Supervised Learning:
Systemet præsenteres for eksempelinput og deres ønskede output, givet af en “lærer”, og målet er at lære en generel regel, der kortlægger input til output. - Unsupervised Learning:
Ingen etiketter gives til læringsalgoritmen, og den overlades til sig selv for at finde struktur i sit input. Uovervåget indlæring kan være et mål i sig selv (opdagelse af skjulte mønstre i data) eller et middel til at nå et mål (indlæring af funktioner). - Forstærkningsindlæring:
Et system interagerer med et dynamisk miljø, hvor det skal udføre et bestemt mål (f.eks. at køre et køretøj eller spille et spil mod en modstander). Systemet får feedback i form af belønninger og straffe, efterhånden som det navigerer i sit problemrum.
Mellem overvåget og uovervåget læring findes semiovervåget læring, hvor læreren giver et ufuldstændigt træningssignal: et træningssæt, hvor nogle (ofte mange) af måloutputtet mangler. Vi vil fokusere på uovervåget læring og dataklynge i dette blogindlæg.
Uovervåget læring
I nogle mønstergenkendelsesproblemer består træningsdataene af et sæt inputvektorer x uden nogen tilsvarende målværdier. Målet i sådanne uovervågede indlæringsproblemer kan være at opdage grupper af lignende eksempler inden for dataene, hvor det kaldes clustering, eller at bestemme, hvordan dataene er fordelt i rummet, hvilket kaldes tæthedsestimering. For at formulere det i enklere vendinger, for et rum med n stikprøver x1 til xn, gives der ikke sande klasseetiketter for hver prøve, derfor kaldes det læring uden lærer.
Problemer med uovervåget læring:
- Uovervåget læring er sværere sammenlignet med opgaver med overvåget læring…
- Hvordan ved vi, om resultaterne er meningsfulde, da der ikke er nogen svarsetiketter til rådighed?
- Lad eksperten se på resultaterne (ekstern evaluering)
- Det er nødvendigt at definere en målfunktion for clustering (intern evaluering)
Hvorfor er der behov for uovervåget læring på trods af disse problemer?
- Annotering af store datasæt er meget dyrt, og derfor kan vi kun mærke nogle få eksempler manuelt. Eksempel: Der kan være tilfælde, hvor vi ikke ved, hvor mange/hvilke klasser dataene er opdelt i. Eksempel: Vi ønsker måske at anvende clustering for at få et indblik i dataenes struktur, inden vi udformer en klassifikator.
Usupervised Learning kan yderligere inddeles i to kategorier:
- Parametrisk uovervåget læring
I dette tilfælde antager vi en parametrisk fordeling af data. Det antages, at stikprøvedata kommer fra en population, der følger en sandsynlighedsfordeling baseret på et fast sæt parametre. Teoretisk set har alle medlemmer af en normal familie af fordelinger den samme form og er parameteriseret ved middelværdi og standardafvigelse. Det betyder, at hvis man kender middelværdien og standardafvigelsen og ved, at fordelingen er normal, kender man sandsynligheden for enhver fremtidig observation. Parametrisk uovervåget læring indebærer konstruktion af Gaussian Mixture Models og anvendelse af Expectation-Maximization-algoritmen til at forudsige klassen for den pågældende prøve. Dette tilfælde er meget vanskeligere end standard overvåget læring, fordi der ikke er nogen svarsetiketter til rådighed, og der er derfor ikke noget korrekt mål for nøjagtighed til rådighed til at kontrollere resultatet. - Ikke-parametrisk uovervåget læring
I den ikke-parametrerede version af uovervåget læring grupperes dataene i klynger, hvor hver klynge (forhåbentlig) siger noget om de kategorier og klasser, der er til stede i dataene. Denne metode bruges almindeligvis til at modellere og analysere data med små stikprøvestørrelser. I modsætning til parametriske modeller kræver ikke-parametriske modeller ikke, at modelløren foretager nogen antagelser om fordelingen af populationen, og derfor omtales de undertiden som en fordelingsfri metode.
Hvad er clustering?
Clustering kan betragtes som det vigtigste uovervågede indlæringsproblem; så som ethvert andet problem af denne art handler det om at finde en struktur i en samling af umærkede data. En løs definition af clustering kunne være “processen med at organisere objekter i grupper, hvis medlemmer ligner hinanden på en eller anden måde”. En klynge er derfor en samling af objekter, som indbyrdes “ligner hinanden” og er “ulige” de objekter, der tilhører andre klynger.
Afstandsbaseret klyngedannelse.
Givet et sæt punkter med et begreb om afstanden mellem punkterne grupperes punkterne i et vist antal klynger, således at
- interne (inden for klyngen) afstande bør være små i.e medlemmer af klynger er tæt på/lignende hinanden.
- De eksterne (inden for klyngen) afstande bør være store, dvs. at medlemmer af forskellige klynger er uensartede.
Målene med klyngeinddeling
Målet med klyngeinddeling er at bestemme den interne gruppering i et sæt af umærkede data. Men hvordan afgør man, hvad der udgør en god clustering? Det kan påvises, at der ikke findes noget absolut “bedste” kriterium, som ville være uafhængigt af det endelige mål med klyngedannelsen. Derfor er det brugeren, der skal levere dette kriterium, således at resultatet af clusteringen passer til deres behov.
I ovenstående billede, hvordan ved vi så, hvad der er den bedste clusteringløsning?
For at finde en bestemt klyngeløsning , skal vi definere lighedsmålene for klyngerne.
Nærhedsmål
For klyngeopdeling skal vi definere et nærhedsmål for to datapunkter. Nærhed betyder her, hvor ens/usammenlignende prøverne er i forhold til hinanden.
- Lighedsmåling S(xi,xk): stor, hvis xi,xk ligner hinanden
- Løsningsmåling (eller afstandsmåling) D(xi,xk): lille, hvis xi,xk ligner hinanden
Der er forskellige lighedsmål, der kan anvendes.
- Vektorer: Cosinusafstand
- Sæt: Jaccard Distance
- Punkter: Euklidisk afstand
q=2
Et “godt” nærhedsmål er MEGET anvendelsesafhængigt. Klyngerne skal være invariante under de transformationer, der er “naturlige” for problemet. Under clustering anbefales det heller ikke at normalisere data, der er trukket fra flere fordelinger.
Clustering-algoritmer
Clustering-algoritmer kan klassificeres som anført nedenfor:
- Eksklusiv clustering
- Overlappende clustering
- Hierarkisk clustering
- Probabilistisk clustering
I det første tilfælde grupperes data på en eksklusiv måde, således at hvis et bestemt datapunkt hører til en bestemt klynge, kan det ikke indgå i en anden klynge. Et simpelt eksempel herpå er vist i nedenstående figur, hvor adskillelsen af punkterne opnås ved hjælp af en lige linje på et todimensionelt plan.
Den anden type, den overlappende klyngedannelse, anvender derimod fuzzy sæt til at klynge data, således at hvert punkt kan tilhøre to eller flere klynger med forskellige grader af tilhørsforhold. I dette tilfælde vil data blive tilknyttet en passende medlemskabsværdi.
En hierarkisk clustering-algoritme er baseret på foreningen mellem de to nærmeste klynger. Begyndelsesbetingelsen realiseres ved at indstille hvert datapunkt som en klynge. Efter et par iterationer når den frem til de ønskede endelige klynger.
Den sidste form for klyngedannelse anvender endelig en helt probabilistisk tilgang.
I denne blog vil vi tale om fire af de mest anvendte clustering-algoritmer:
- K-means
- Fuzzy K-means
- Hierarkisk clustering
- Mixture of Gaussians
Hver af disse algoritmer hører til en af de ovenfor nævnte clustering-typer. Mens K-means er en eksklusiv clustering-algoritme, Fuzzy K-means er en overlappende clustering-algoritme, hierarkisk clustering er indlysende, og endelig er Mixture of Gaussians en probabilistisk clustering-algoritme. Vi vil diskutere hver enkelt clusteringmetode i de følgende afsnit.
K-Means Clustering
K-means er en af de enkleste uovervågede læringsalgoritmer, der løser det velkendte clusteringproblem. Proceduren følger en enkel og let måde at klassificere et givet datasæt gennem et bestemt antal klynger (antages k klynger), der er fastsat på forhånd. Hovedidéen er at definere k centre, et for hver klynge. Disse centroider bør placeres på en smart måde, da forskellige placeringer medfører forskellige resultater. Det bedste valg er derfor at placere dem så langt væk fra hinanden som muligt. Det næste skridt er at tage hvert punkt, der tilhører et givet datasæt, og knytte det til den nærmeste centroid. Når der ikke er noget punkt i vente, er det første trin afsluttet, og der foretages en tidlig gruppering. På dette tidspunkt er vi nødt til at genberegne k nye centroider som barycentre for de klynger, der er resultatet af det foregående trin. Når vi har disse k nye centroider, skal der foretages en ny binding mellem de samme punkter i datasættet og den nærmeste nye centroide. Der er opstået en sløjfe. Som følge af dette loop kan vi bemærke, at de k centroider ændrer deres placering trin for trin, indtil der ikke foretages flere ændringer. Centroiderne flytter sig med andre ord ikke længere.
Endeligt har denne algoritme til formål at minimere en målfunktion, i dette tilfælde en kvadreret fejlfunktion. Målfunktionen
hvor
er et valgt afstandsmål mellem et datapunkt xi og klyngecentret cj, er en indikator for afstanden mellem de n datapunkter og deres respektive klyngecentre.
Algoritmen består af følgende trin:
- Lad X = {x1,x2,x3,……..,xn} være mængden af datapunkter og V = {v1,v2,…….,vc} være mængden af centre.
- Vælg tilfældigt “c” klyngecentre.
- Beregn afstanden mellem hvert datapunkt og klyngecentre.
- Tildel datapunktet til det klyngecenter, hvis afstand fra klyngecentret er mindst af alle klyngecentrene.
- Beregn det nye klyngecenter på ny ved hjælp af:
hvor “ci” repræsenterer antallet af datapunkter i den i’te klynge.
- Omberegn afstanden mellem hvert datapunkt og de nye opnåede klyngecentre.
- Hvis intet datapunkt blev omplaceret, så stop, ellers gentag fra trin 3).
Selv om det kan bevises, at proceduren altid vil afsluttes, finder k-means-algoritmen ikke nødvendigvis den mest optimale konfiguration, der svarer til det globale målfunktionsminimum. Algoritmen er også betydeligt følsom over for de indledende tilfældigt udvalgte klyngecentre. K-means-algoritmen kan køres flere gange for at mindske denne effekt.
K-means er en enkel algoritme, der er blevet tilpasset mange problemområder. Som vi vil se, er den en god kandidat til at blive udvidet til at arbejde med fuzzy featurevektorer.
K-means-proceduren kan ses som en greedy-algoritme til at opdele de n prøver i k k klynger, således at summen af de kvadrerede afstande til klyngecentrene minimeres. Den har dog nogle svagheder:
- Den måde at initialisere midlerne på var ikke specificeret. En populær måde at starte på er at vælge k af prøverne tilfældigt.
- Det kan ske, at mængden af prøver, der ligger tættest på mi, er tom, så mi ikke kan opdateres. Dette er et problem, som skal håndteres under implementeringen, men som generelt ignoreres.
- Resultaterne afhænger af værdien af k, og der findes ingen optimal måde at beskrive et bedste “k” på.
Dette sidste problem er særlig besværligt, da vi ofte ikke har nogen mulighed for at vide, hvor mange klynger der findes. I det ovenfor viste eksempel giver den samme algoritme anvendt på de samme data følgende 3-måne-gruppering. Er den bedre eller dårligere end 2-means-grupperingen?
Der findes desværre ingen generel teoretisk løsning til at finde det optimale antal klynger for ethvert givet datasæt. En simpel fremgangsmåde er at sammenligne resultaterne af flere kørsler med forskellige k klasser og vælge den bedste efter et givet kriterium, men vi skal være forsigtige, fordi en forøgelse af k pr. definition resulterer i mindre fejlfunktionsværdier, men også øger risikoen for overfitting.
Fuzzy K-Means Clustering
I fuzzy clustering har hvert punkt en sandsynlighed for at tilhøre hver enkelt klynge, i stedet for helt at tilhøre en enkelt klynge, som det er tilfældet i den traditionelle k-means. Fuzzy k-means forsøger specifikt at håndtere det problem, hvor punkterne ligger noget mellem centrene eller på anden måde er tvetydige, ved at erstatte afstand med sandsynlighed, som naturligvis kan være en eller anden funktion af afstanden, f.eks. ved at have sandsynlighed i forhold til den inverse af afstanden. Fuzzy k-means anvender en vægtet centroid baseret på disse sandsynligheder. Initialiserings-, iterations- og afslutningsprocesserne er de samme som dem, der anvendes i k-means. De resulterende klynger analyseres bedst som sandsynlighedsfordelinger snarere end som en hård tildeling af etiketter. Man bør være klar over, at k-means er et særligt tilfælde af fuzzy k-means, hvor den anvendte sandsynlighedsfunktion blot er 1, hvis datapunktet er tættest på en centroid og 0 ellers.
Den fuzzy k-means-algoritme er følgende:
- Antag et fast antal klynger K.
- Initialisering: Initialisér tilfældigt k-means μk, der er knyttet til klyngerne, og beregn sandsynligheden for, at hvert datapunkt Xi er medlem af en given klynge K,
P(PointXiHasLabelK|Xi,K). - Iteration: Genberegn klyngens centroid som den vægtede centroid givet sandsynlighederne for medlemskab for alle datapunkter Xi :
- Afslutning: Iteration: Iteration indtil konvergens eller indtil et brugerdefineret antal iterationer er nået (iterationen kan være fanget ved nogle lokale maksima eller minima)
For en bedre forståelse kan vi se på dette enkle monodimensionelle eksempel. Givet et bestemt datasæt, antages det at repræsentere det som fordelt på en akse. Figuren nedenfor viser dette:
Hvis vi ser på billedet, kan vi identificere to klynger i nærheden af de to datakoncentrationer. Vi vil henvise til dem ved hjælp af “A” og “B”. I den første tilgang vist i denne tutorial – k-means-algoritmen – tilknyttede vi hvert datapunkt til en bestemt centroid; derfor så denne medlemskabsfunktion således ud:
I Fuzzy k-means-tilgangen hører det samme givne datapunkt i stedet ikke udelukkende til en veldefineret klynge, men kan placeres i en mellemvej. I dette tilfælde følger medlemskabsfunktionen en glattere linje for at indikere, at hvert datapunkt kan tilhøre flere klynger med forskellig grad af tilhørsforhold.
I figuren ovenfor tilhører datapunktet, der er vist som et rødt markeret punkt, i højere grad B-klyngen frem for A-klyngen. Værdien 0,2 for “m” angiver graden af tilhørsforhold til A for et sådant datapunkt.
Hierarkiske klyngealgoritmer
Givet et sæt af N elementer, der skal klynges, og en N*N afstands- (eller ligheds-) matrix, er den grundlæggende proces for hierarkisk klyngedannelse følgende:
- Start med at tildele hvert element til en klynge, så hvis du har N elementer, har du nu N klynger, der hver kun indeholder ét element. Lad afstandene (lighederne) mellem klyngerne være de samme som afstandene (lighederne) mellem de emner, de indeholder.
- Find det nærmeste (mest ens) par af klynger, og slå dem sammen til en enkelt klynge, så du nu har en klynge mindre.
- Beregn afstandene (lighederne) mellem den nye klynge og hver af de gamle klynger.
- Gentag trin 2 og 3, indtil alle emner er samlet i en enkelt klynge af størrelse N.
Clustering som en blanding af Gaussianere
Der er en anden måde at håndtere clusteringproblemer på: en modelbaseret tilgang, som består i at anvende bestemte modeller for klynger og forsøge at optimere tilpasningen mellem data og modellen.
I praksis kan hver klynge matematisk repræsenteres af en parametrisk fordeling, f.eks. en gaussisk fordeling. Hele datasættet modelleres derfor ved hjælp af en blanding af disse fordelinger.
En blandingsmodel med høj sandsynlighed har tendens til at have følgende træk:
- Komponentfordelinger har høje “toppe” (data i en klynge er stramme);
- Blandingsmodellen “dækker” dataene godt (dominerende mønstre i dataene indfanges af komponentfordelinger).
Hovedfordele ved modelbaseret clustering:
- der findes velundersøgte statistiske inferenceteknikker;
- fleksibilitet i valget af komponentfordelingen;
- opnå et tæthedsestimat for hver klynge;
- der findes en “blød” klassifikation.
Mixture of Gaussians
Den mest udbredte clusteringmetode af denne art er baseret på indlæring af en blanding af Gaussians:
En blandingsmodel er en blanding af k komponentfordelinger, der tilsammen udgør en blandingsfordeling f(x):
Den αk repræsenterer bidraget fra den k-te komponent i konstruktionen af f(x). I praksis anvendes ofte parametriske fordelinger (f.eks. gaussianere), da der er blevet gjort meget arbejde for at forstå deres adfærd. Hvis man erstatter hver fk(x) med en gausianer, får man det, der er kendt som en gaussisk blandingsmodel (GMM).
Em-algoritmen
Expectation-Maximization antager, at dine data er sammensat af flere multivariate normalfordelinger (bemærk, at dette er en meget stærk antagelse, især når du fastsætter antallet af klynger!). Alternativt udtrykt er EM en algoritme til at maksimere en sandsynlighedsfunktion, når nogle af variablerne i din model er uobserverede (dvs. når du har latente variabler).
Du kan med rette spørge, hvis vi blot forsøger at maksimere en funktion, hvorfor bruger vi så ikke bare det eksisterende maskineri til at maksimere en funktion? Tja, hvis man forsøger at maksimere dette ved at tage derivater og sætte dem til nul, finder man i mange tilfælde, at førsteordensbetingelserne ikke har en løsning. Der er et høne-og-æg-problem, idet man for at kunne løse sine modelparametre er nødt til at kende fordelingen af de uobserverede data; men fordelingen af de uobserverede data er en funktion af modelparametrene.
Expectation-Maximization forsøger at omgå dette ved iterativt at gætte en fordeling for de uobserverede data, derefter estimere modelparametrene ved at maksimere noget, der er en nedre grænse for den faktiske sandsynlighedsfunktion, og gentage indtil konvergens:
Ekspectation-Maximization-algoritmen
- Start med gæt for værdierne af dine modelparametre
- E-trin: For hvert datapunkt, der har manglende værdier, skal du bruge din modelligning til at løse fordelingen af de manglende data ud fra dit aktuelle gæt på modelparametrene og ud fra de observerede data (bemærk, at du løser for en fordeling for hver manglende værdi, ikke for den forventede værdi). Nu, hvor vi har en fordeling for hver manglende værdi, kan vi beregne sandsynlighedsfunktionens forventning med hensyn til de uobserverede variabler. Hvis vores gæt for modelparameteren var korrekt, vil denne forventede sandsynlighed være den faktiske sandsynlighed for vores observerede data; hvis parametrene ikke var korrekte, vil det blot være en nedre grænse.
- M-trin: Nu hvor vi har en forventet sandsynlighedsfunktion uden uobserverede variabler i den, skal du maksimere funktionen, som du ville gøre i det fuldt observerede tilfælde, for at få et nyt estimat af dine modelparametre.
- Gentag indtil konvergens.
Problemer i forbindelse med klyngedannelse
Der er en række problemer med klyngedannelse. Blandt dem:
- Det kan være problematisk at håndtere et stort antal dimensioner og et stort antal dataelementer på grund af tidskompleksiteten;
- metodens effektivitet afhænger af definitionen af “afstand” (for afstandsbaseret klyngedannelse). Hvis der ikke findes et indlysende afstandsmål, må vi “definere” det, hvilket ikke altid er let, især ikke i flerdimensionale rum;
- resultatet af clustering-algoritmen (der i mange tilfælde selv kan være arbitrær) kan fortolkes på forskellige måder.
Mulige anvendelser
Clustering-algoritmer kan anvendes inden for mange områder, f.eks.:
- Markedsføring: finde grupper af kunder med lignende adfærd givet en stor database af kundedata, der indeholder deres egenskaber og tidligere købsposter;
- Biologi: klassificering af planter og dyr givet deres egenskaber;
- Forsikring:
- Jordskælvsundersøgelser: gruppering af observerede jordskælvscentre for at identificere farlige zoner;
- World Wide Web: klassificering af dokumenter; gruppering af weblogdata for at finde grupper med lignende adgangsmønstre.