Unsupervised Learning and Data Clustering

En uppgift som omfattar maskininlärning är kanske inte linjär, men den har ett antal välkända steg:

Problemdefinition.
Förberedelse av data.
Lär dig en underliggande modell.
Förbättra den underliggande modellen genom kvantitativa och kvalitativa utvärderingar.
Presentera modellen.

Ett bra sätt att komma till rätta med ett nytt problem är att arbeta med att identifiera och definiera problemet på bästa möjliga sätt och lära sig en modell som fångar meningsfull information från data. Även om problem inom mönsterigenkänning och maskininlärning kan vara av olika slag kan de i stort sett delas in i tre kategorier:

Supervised Learning:
Systemet presenteras med exempel på indata och deras önskade utdata, som ges av en ”lärare”, och målet är att lära sig en allmän regel som mappar inmatningar till utdata.
Unsupervised Learning:
Ingen etiketter ges till inlärningsalgoritmen, vilket gör att den får klara sig själv för att hitta struktur i sin indata. Oövervakad inlärning kan vara ett mål i sig självt (upptäcka dolda mönster i data) eller ett medel mot ett mål (inlärning av egenskaper).
Förstärkningsinlärning:
Ett system interagerar med en dynamisk miljö där det måste utföra ett visst mål (t.ex. köra ett fordon eller spela ett spel mot en motståndare). Systemet får återkoppling i form av belöningar och bestraffningar när det navigerar i sitt problemområde.

Mellan övervakad och oövervakad inlärning finns semiovervakad inlärning, där läraren ger en ofullständig träningssignal: en träningsuppsättning där en del (ofta många) av målutgångarna saknas. Vi kommer att fokusera på oövervakad inlärning och dataklustering i det här blogginlägget.

Oövervakad inlärning

I vissa mönsterigenkänningsproblem består träningsdata av en uppsättning inmatningsvektorer x utan motsvarande målvärden. Målet i sådana oövervakade inlärningsproblem kan vara att upptäcka grupper av liknande exempel inom data, där det kallas klustring, eller att bestämma hur data är fördelade i utrymmet, så kallad densitetsuppskattning. För att uttrycka det i enklare termer, för ett utrymme med n provtagningar x1 till xn, tillhandahålls inte sanna klassbeteckningar för varje prov, vilket kallas inlärning utan lärare.

Problem med oövervakad inlärning:

Oövervakad inlärning är svårare jämfört med uppgifter för övervakad inlärning…
Hur vet vi om resultaten är meningsfulla eftersom inga svarsbeteckningar är tillgängliga?
Låt experten titta på resultaten (extern utvärdering)
Definiera en målfunktion för klusterbildning (intern utvärdering)

Varför behövs oövervakad inlärning trots dessa problem?

Annotering av stora datamängder är mycket kostsamt och därför kan vi bara märka ett fåtal exempel manuellt. Exempel: Det kan finnas fall där vi inte vet hur många/vilka klasser uppgifterna är indelade i. Exempel: Vi behöver inte veta hur många klasser vi har indelat i: Vi kanske vill använda klusterindelning för att få en inblick i datans struktur innan vi utformar en klassificerare.

Oövervakad inlärning kan vidare klassificeras i två kategorier:

Parametrisk oövervakad inlärning
I det här fallet utgår vi från en parametrisk fördelning av data. Det förutsätter att provdata kommer från en population som följer en sannolikhetsfördelning baserad på en fast uppsättning parametrar. Teoretiskt sett har alla medlemmar i en normalfördelningsfamilj samma form och parametreras av medelvärde och standardavvikelse. Det innebär att om man känner till medelvärdet och standardavvikelsen och att fördelningen är normal, känner man till sannolikheten för varje framtida observation. Parametrisk oövervakad inlärning innebär att man konstruerar Gaussian Mixture Models och använder Expectation-Maximization-algoritmen för att förutsäga klassen för provet i fråga. Det här fallet är mycket svårare än den vanliga övervakade inlärningen eftersom det inte finns några svarsetiketter tillgängliga och därmed finns det inget korrekt mått på noggrannhet tillgängligt för att kontrollera resultatet.
Icke-parametrisk oövervakad inlärning
I den icke-parametrerade versionen av oövervakad inlärning grupperas data i kluster, där varje kluster (förhoppningsvis) säger något om de kategorier och klasser som finns i datamaterialet. Den här metoden används ofta för att modellera och analysera data med små urvalsstorlekar. Till skillnad från parametriska modeller kräver icke-parametriska modeller inte att modellören gör några antaganden om populationens fördelning, och därför kallas de ibland för en fördelningsfri metod.

Vad är klusterbildning?

Klusterbildning kan betraktas som det viktigaste problemet med oövervakad inlärning; så som alla andra problem av detta slag handlar det om att hitta en struktur i en samling av omärkta data. En lös definition av klustring kan vara ”processen att organisera objekt i grupper vars medlemmar är lika på något sätt”. Ett kluster är därför en samling objekt som är ”likartade” sinsemellan och som är ”olik” de objekt som tillhör andra kluster.

Distansbaserad klusterbildning.

Genom en uppsättning punkter, med ett begrepp om avståndet mellan punkterna, gruppering av punkterna i ett visst antal kluster, så att

interna (inom klustret) avstånd bör vara små i.
externa (inom klustret) avstånd bör vara stora, dvs. medlemmar av olika kluster är olik varandra.

Målen med klusterindelning

Målet med klusterindelning är att bestämma den interna grupperingen i en uppsättning icke-märkta data. Men hur avgör man vad som utgör en bra klusterbildning? Det kan visas att det inte finns något absolut ”bästa” kriterium som skulle vara oberoende av det slutliga målet med klusterbildningen. Följaktligen är det användaren som bör tillhandahålla detta kriterium, på ett sådant sätt att resultatet av klusterbildningen kommer att passa deras behov.

Det finns olika likhetsmått som kan användas.

Vektorer: Cosinusavstånd

Mängder: Jaccard Distance

Punkter: Euklidiskt avstånd
q=2

Ett ”bra” närhetsmått är MYCKET beroende av tillämpningen. Klustren bör vara invarianta under de transformationer som är ”naturliga” för problemet. Dessutom är det inte tillrådligt att normalisera data som är hämtade från flera olika fördelningar under klusterbildningen.

Clusteringalgoritmer

Clusteringalgoritmer kan klassificeras enligt följande:

Exklusiv klusterindelning
Överlappande klusterindelning
Hierarkisk klusterindelning
Probabilistisk klusterindelning

I det första fallet grupperas data på ett exklusivt sätt, så att om en viss datapunkt tillhör ett visst kluster så kan den inte ingå i ett annat kluster. Ett enkelt exempel på detta visas i figuren nedan, där separationen av punkterna uppnås genom en rak linje på ett tvådimensionellt plan.

I den andra typen, den överlappande klusterbildningen, används tvärtom fuzzy set för att klustra data, så att varje punkt kan tillhöra två eller flera kluster med olika grad av tillhörighet. I detta fall kommer data att associeras med ett lämpligt medlemsvärde.

En hierarkisk klusteralgoritm bygger på föreningen mellan de två närmaste klustren. Startvillkoret förverkligas genom att varje datapunkt fastställs som ett kluster. Efter några iterationer når den de slutliga kluster som önskas.

Den sista typen av klusterbildning använder slutligen ett helt probabilistiskt tillvägagångssätt.

I den här bloggen kommer vi att tala om fyra av de mest använda klusteralgoritmerna:

K-means
Fuzzy K-means
Hierarkisk klustring
Mixture of Gaussians

Varje algoritm tillhör någon av de klustertyper som anges ovan. K-means är en exklusiv klusteralgoritm, Fuzzy K-means är en överlappande klusteralgoritm, hierarkisk klustring är uppenbar och Mixture of Gaussians är en probabilistisk klusteralgoritm. Vi kommer att diskutera varje klustermetod i följande punkter.

K-Means Clustering

K-means är en av de enklaste oövervakade inlärningsalgoritmerna som löser det välkända klusterproblemet. Förfarandet följer ett enkelt och lätt sätt att klassificera en given datamängd genom ett visst antal kluster (anta k kluster) som fastställts på förhand. Huvudidén är att definiera k centra, ett för varje kluster. Dessa centroider bör placeras på ett smart sätt, eftersom olika placeringar ger olika resultat. Det bästa valet är alltså att placera dem så långt bort som möjligt från varandra. Nästa steg är att ta varje punkt som tillhör en given datamängd och associera den till den närmaste centroiden. När ingen punkt är i väntan är det första steget avslutat och en tidig gruppering görs. Vid denna tidpunkt måste vi återigen beräkna k nya centroider som barycentra för de kluster som är resultatet av det föregående steget. När vi har dessa k nya centroider måste en ny bindning göras mellan samma datapunkter och den närmaste nya centroiden. En slinga har skapats. Som ett resultat av denna slinga kan vi märka att de k centroiderna ändrar sin placering steg för steg tills inga fler ändringar görs. Med andra ord flyttas centroiderna inte längre.

Slutligt syftar denna algoritm till att minimera en målfunktion, i det här fallet en kvadrerad felfunktion. Målfunktionen

där

är ett valt avståndsmått mellan en datapunkt xi och klustercentrumet cj, är en indikator på avståndet mellan de n datapunkterna och deras respektive klustercentrum.

Algoritmen består av följande steg:

Låt X = {x1,x2,x3,……..,xn} vara uppsättningen datapunkter och V = {v1,v2,…….,vc} vara uppsättningen centra.
Välj slumpmässigt ut ’c’ klustercentra.
Beräkna avståndet mellan varje datapunkt och klustercentra.
Tilldela datapunkten till det klustercentrum vars avstånd från klustercentrumet är minst av alla klustercentrum.
Beräkna om det nya klustercentrumet med hjälp av:

där ”ci” representerar antalet datapunkter i det i:e klustret.

Beräkna om avståndet mellan varje datapunkt och de nya klustercentrumen.
Om ingen datapunkt omfördelades, stoppa då, annars upprepa från steg 3).

Och även om det kan bevisas att förfarandet alltid kommer att avslutas, finner k-means-algoritmen inte nödvändigtvis den mest optimala konfigurationen, som motsvarar den globala målfunktionens minimum. Algoritmen är också mycket känslig för de ursprungliga slumpmässigt valda klustercentrumen. K-means-algoritmen kan köras flera gånger för att minska denna effekt.

K-means är en enkel algoritm som har anpassats till många problemområden. Som vi kommer att se är den en bra kandidat för att utvidgas till att arbeta med fuzzy featurevektorer.

K-means-proceduren kan ses som en greedy-algoritm för att dela upp de n proverna i k kluster så att summan av de kvadratiska avstånden till klustercentrumen blir så liten som möjligt. Den har dock vissa svagheter:

Sättet att initialisera medelvärdena var inte specificerat. Ett populärt sätt att börja är att slumpmässigt välja k av proverna.
Det kan hända att mängden prover som ligger närmast mi är tom, så att mi inte kan uppdateras. Detta är ett problem som måste hanteras under genomförandet, men som i allmänhet ignoreras.
Resultaten beror på värdet på k och det finns inget optimalt sätt att beskriva ett bästa ”k”.

Detta sista problem är särskilt besvärligt, eftersom vi ofta inte har något sätt att veta hur många kluster som finns. I exemplet ovan ger samma algoritm, tillämpad på samma data, följande 3-manna klusterindelning. Är den bättre eller sämre än 2-means klusterbildningen?

Det finns tyvärr ingen allmän teoretisk lösning för att hitta det optimala antalet kluster för en given datamängd. Ett enkelt tillvägagångssätt är att jämföra resultaten av flera körningar med olika k klasser och välja den bästa enligt ett givet kriterium, men vi måste vara försiktiga eftersom en ökning av k resulterar i mindre felfunktionsvärden per definition, men också ökar risken för överanpassning.

Fuzzy K-Means Clustering

I fuzzy clustering har varje punkt en sannolikhet för att tillhöra varje kluster, i stället för att helt och hållet tillhöra ett enda kluster, vilket är fallet med den traditionella k-means. Fuzzy k-means försöker särskilt hantera problemet när punkter ligger något mellan centra eller på annat sätt är tvetydiga genom att ersätta avstånd med sannolikhet, som naturligtvis kan vara någon funktion av avståndet, t.ex. att ha sannolikhet relativt till inversen av avståndet. Fuzzy k-means använder en viktad centroid baserad på dessa sannolikheter. Processerna för initialisering, iteration och avslutande är desamma som de som används i k-means. De resulterande klustren analyseras bäst som sannolikhetsfördelningar snarare än som en hård tilldelning av etiketter. Man bör inse att k-means är ett specialfall av fuzzy k-means när den sannolikhetsfunktion som används helt enkelt är 1 om datapunkten ligger närmast en centroid och 0 annars.

Fuzzy k-means-algoritmen är följande:

Anta att det finns ett fast antal kluster K.
Initialisering: Initialisera slumpmässigt k-means μk som är associerade med klustren och beräkna sannolikheten för att varje datapunkt Xi ingår i ett givet kluster K,
P(PointXiHasLabelK|Xi,K).
Iteration: Beräkna klustrets centroid på nytt som den viktade centroid med tanke på sannolikheten för medlemskap för alla datapunkter Xi :

Avslutning: Iterera tills konvergens uppnås eller tills ett användarspecificerat antal iterationer har uppnåtts (iterationen kan fastna vid vissa lokala maxima eller minima)

För att få en bättre förståelse kan vi betrakta detta enkla monodimensionella exempel. Givet en viss datamängd, anta att den representeras som fördelad på en axel. Figuren nedan visar detta:

Om vi tittar på bilden kan vi identifiera två kluster i närheten av de två datakoncentrationerna. Vi kommer att referera till dem genom att använda ”A” och ”B”. I det första tillvägagångssättet som visas i denna handledning – k-means-algoritmen – associerade vi varje datapunkt till en specifik centroid; därför såg denna medlemsfunktion ut så här:

I Fuzzy k-means-ansatsen hör samma givna datapunkt i stället inte uteslutande hemma i ett väldefinierat kluster, utan den kan placeras i en mellanväg. I detta fall följer medlemskapsfunktionen en jämnare linje för att indikera att varje datapunkt kan tillhöra flera kluster med olika grad av tillhörighet.

I figuren ovan tillhör den datapunkt som visas som en rödmarkerad punkt mer till B-klustret än till A-klustret. Värdet 0,2 för ”m” anger graden av tillhörighet till A för en sådan datapunkt.

Hierarkiska klusteralgoritmer

Givet en uppsättning med N objekt som ska klusteras och en N*N avstånds- (eller likhets-) matris är den grundläggande processen för hierarkisk klusterbildning följande:

Start med att tilldela varje objekt till ett kluster, så att om du har N objekt har du nu N kluster som vart och ett innehåller bara ett objekt. Låt avstånden (likheterna) mellan klustren vara desamma som avstånden (likheterna) mellan de objekt som de innehåller.
Finn det närmaste (mest likartade) klusterparet och slå ihop dem till ett enda kluster, så att du nu har ett kluster mindre.
Beräkna avstånden (likheterna) mellan det nya klustret och vart och ett av de gamla klustren.
Upprepa steg 2 och 3 tills alla objekt har klusterats i ett enda kluster av storlek N.

Clustering som en blandning av Gaussianer

Det finns ett annat sätt att hantera klusterproblem: ett modellbaserat tillvägagångssätt, som går ut på att man använder vissa modeller för kluster och försöker optimera anpassningen mellan data och modellen.

I praktiken kan varje kluster matematiskt representeras av en parametrisk fördelning, till exempel en Gauss. Hela datamängden modelleras därför av en blandning av dessa fördelningar.
En blandningsmodell med hög sannolikhet tenderar att ha följande egenskaper:

komponentfördelningarna har höga ”toppar” (data i ett kluster är täta);
blandningsmodellen ”täcker” data väl (dominerande mönster i data fångas av komponentfördelningarna).

Huvudfördelar med modellbaserad klusterindelning:

välstuderade statistiska inferenstekniker finns tillgängliga;
flexibilitet i valet av komponentfördelning;
uppnå en densitetsuppskattning för varje kluster;
en ”mjuk” klassificering är tillgänglig.

Mixture of Gaussians
Den mest använda klustermetoden av detta slag bygger på inlärning av en blandning av Gaussians:

En blandningsmodell är en blandning av k komponentfördelningar som tillsammans utgör en blandningsfördelning f(x):

Den αk representerar bidraget från den k:e komponenten i konstruktionen av f(x). I praktiken används ofta parametriska fördelningar (t.ex. gaussianer), eftersom mycket arbete har gjorts för att förstå deras beteende. Om man ersätter varje fk(x) med en gauss får man vad som kallas gaussiska blandningsmodeller (GMM).

Em-algoritmen

Expectation-Maximization antar att dina data består av flera multivariata normalfördelningar (observera att detta är ett mycket starkt antagande, särskilt när du fastställer antalet kluster!). Alternativt uttryckt är EM en algoritm för att maximera en sannolikhetsfunktion när en del av variablerna i din modell inte är observerade (dvs. när du har latenta variabler).
Du kanske rättvist frågar dig, om vi bara försöker maximera en funktion, varför använder vi inte bara det befintliga maskineriet för att maximera en funktion. Jo, om man försöker maximera detta genom att ta derivat och sätta dem till noll finner man att i många fall har första ordningens villkor inte någon lösning. Det finns ett problem med hönan och ägget, eftersom man för att lösa modellparametrarna måste känna till fördelningen av de icke-observerade uppgifterna, men fördelningen av de icke-observerade uppgifterna är en funktion av modellparametrarna.

Expectation-Maximization försöker komma runt detta genom att iterativt gissa en fördelning för de icke-observerade uppgifterna, sedan skatta modellparametrarna genom att maximera något som är en nedre gräns för den faktiska sannolikhetsfunktionen, och upprepa tills det blir konvergens:

Expectation-Maximization-algoritmen

Start med en gissning av värdena för dina modellparametrar
E-steg: För varje datapunkt som har saknade värden, använd din modellekvation för att lösa fördelningen av de saknade uppgifterna med tanke på din nuvarande gissning av modellparametrarna och med tanke på de observerade uppgifterna (observera att du löser för en fördelning för varje saknat värde, inte för det förväntade värdet). Nu när vi har en fördelning för varje saknat värde kan vi beräkna sannolikhetsfunktionens förväntan med avseende på de icke-observerade variablerna. Om vår gissning för modellparametern var korrekt kommer denna förväntade sannolikhet att vara den faktiska sannolikheten för våra observerade data; om parametrarna inte var korrekta kommer det bara att vara en nedre gräns.
M-steg: Nu när vi har en förväntad sannolikhetsfunktion utan oobserverade variabler i den, maximera funktionen på samma sätt som i det fullt observerade fallet, för att få en ny uppskattning av dina modellparametrar.
Upprepa tills det blir konvergens.

Problem som är förknippade med klusterindelning

Det finns ett antal problem med klusterindelning. Bland dem:

hanteringen av ett stort antal dimensioner och ett stort antal dataelement kan vara problematisk på grund av tidskomplexiteten;
metodens effektivitet beror på definitionen av ”avstånd” (för avståndsbaserad klustring). Om det inte finns något uppenbart avståndsmått måste vi ”definiera” det, vilket inte alltid är lätt, särskilt inte i flerdimensionella utrymmen;
resultatet av klusteralgoritmen (som i många fall kan vara godtycklig i sig själv) kan tolkas på olika sätt.

Möjliga tillämpningar

Clustering-algoritmer kan tillämpas inom många områden, till exempel:

Marknadsföring: att hitta grupper av kunder med liknande beteende med tanke på en stor databas med kunduppgifter som innehåller deras egenskaper och tidigare köpregistreringar;
Biologi: klassificering av växter och djur med tanke på deras egenskaper;
Försäkring:
Jordbävningsstudier: gruppering av observerade jordbävningscentrum för att identifiera farliga zoner
World Wide Web: klassificering av dokument, gruppering av weblogdata för att upptäcka grupper med liknande åtkomstmönster.

Free Press

Unsupervised Learning and Data Clustering

Lämna ett svar Avbryt svar