Klyngeanalyse

Klyngeanalyse (kløsteranalyse) er en statistisk metode for å organisere en gruppe objekter på en slik måte at objekter i samme klynge er mest mulig lik hverandre, sammenlignet med objekter i andre klynger. Baserer seg på at objekter som er nær hverandre er mer like enn de som befinner seg lenger unna. Det finnes vanligvis ingen korrekt eller objektiv fasit på objektenes tilhørighet i gruppen.   En klassifiserings- og typeanalyse.  Klyngeanalyse blir benyttet innen mønstergjenkjenning og bioinformatikk.

Medlemskap i klasser basert på målte egenskaper. Kan brukes til alle mulige former for gruppering av objekter til mønstergjenkjenning. Klyngemetoder lager grupper basert på kvantitative egenskaper, mål på ulikhet og likhet, og k objekter kan gi 2k-1 grupper, øker eksponensielt med k.

I hierarkisk klyngeanalyse samles klyngene fra den minste til den største klyngen (agglomerativ). Ved divisiv klyngeanalysene samles klyngene fra den største til den minste.

I ikke-hierarkisk klyngeanalyse er antall klynger k bestemt på forhånd og oppgaven er på best mulig måte å fordele prøven i k klynger. k-means clustering er den mest vanlige metoden for ikke-hierarkisk klyngeanalyse. Den er datamaskineffektiv siden den ikke er avhengig av en start med store datamatriser. Skal organisere n datapunkter i k forhåndsbestemte klynger, k<n. Start med å bestemme antall k. Fordel data tilfeldig i k klynger. Beregn sentroid (gjennomsnitt, senter) i hver klynge. La hvert datapunkt høre med til klyngen hvor sentroiden er nærmest, basert på en avstandsmatrise. Hvis det trengs reorganisering lag nye klynger, beregn sentroidkoordinatene for klynger som mister eller mottar datapunkter. Gjenta til det ikke trengs flere omorganiseringer 

Man må ha et mål på avstand, similaritet (likhet) eller dissimilaritet (forskjell). For dissimilaritet av kontinuerlige data kan Euklidsk avstand benyttes.

\(d(x,y)=\displaystyle \sqrt{\sum_{i=1}^n (x_i-y_i)^2}\)

Euklidsk avstand er følsom for utliggere og ekstremverdier. Andre avstandmål er Manhattan avstand og max komponentavstand

Det finnes forskjellige regneregler (algoritmer) som benyttes til avstandsbedømmelse mellom klyngene,  og hvordan finne og bestemme tilhørigheten til objekter.  Distansemålene kan være minimum eller maksimum objektdistanse. For eksempel er UPGMA (uvektet pargruppemetode med aritmetisk gjennomsnitt)  en gjennomsnitts lenkekløstring. Prøve- og feile-metoder blir benyttet for å teste klyngetilhørigheten til objektene ved å gjenta analysen av tilhørighet via iterasjoner. Innen psykologi kan man klassifisere personligheter ut fra en rekke karakteristika i introverte (innadvendte), ekstroverte (utadvendte), melankolske osv. Klyngene er aldri helt presise, og det kan være overlappende klynger. I harde klynger er det lett å bestemme om hvorvidt et objekt hører med til klyngen eller ikke. I myke (fuzzy) klynger er tilhørigheten mindre opplagt, og objektene hører hjemme i klyngene med en viss grad av sannsynlighet. Hierarkiske klynger er organisert i forskjellige nivåer, som mor-datter nivåer. Hierarkisk kløstring kan være agglomerativ hvor man starter med enkeltelementer og grupperer dem, eller divisiv hvor man starter med alle objektene eller hele datasettet og deler dem i klynger. Utliggere vil danne egne klynger eller kan bli kjedekoblet til andre klynger. Tetthetsbasert klynging definerer områder med høyere tetthet enn de andre, og utliggere kan bli betraktet som støy e.g. DBSCAN (tetthetsbasert romlig kløstring med støy).

I k-means kløstring  er antall klynger k bestemt på forhånd og avstanden er basert på sentroiden. Man finner sentroiden i k klynger og tilegner objektet til nærmeste klynge slik at den kvadrerte avstanden til klyngen blir minst mulig. Dette er en type optimaliseringsproblem som kalles NP-hard.  Deler data inn i Voronoi-diagram. Sentroiden er det geometriske senter, balansepunktet eller gravitasjonssenter (barysenter), og gjelder for n-dimensjonale rom. Sentroiden i en trekant er punktet hvor de tre medianene i trekanten treffer hverandre. En median forbinder et hjørne i trekanten  med midtpunktet på den motsatte sidekanten, og befinner seg på trekantens Euler-linje.  Euler-linjen forbinder medianenes skjæringspunkt (sentroiden), skjæringspunktet mellom midtnormalene (sirkumsenter),  og høydenes ((linjer fra hvert av hjørnene som står normalt på motsatt sidekant) skjæringspunkt (ortosenter), forutsetter spisse vinkler i trekanten. Et sirkumsenter kan falle innenfor trekanten, midt på hypotenusen eller utenfor trekanten. Man kan videre konstruere en sekspunktsirkel eller nipunktsirkel.  Man kan finne sentroiden i et todimensjonalt objekt ved å henge det opp i et punkt langs ytterkanten (perimeter) og trekke en loddrett linje fra punktet. Deretter lager man et nytt opphengningspunkt i ytterkant og lager en ny loddrett linje. Der hvor de loddrette linjene skjærer hverandre ligger sentroiden.

Lloyds algoritme (Stuart P Lloyd) har likhetstrekk med k-means algoritmen og er en Voronoi-iterasjon. Man deler opp rommet med punkter eller objekter i sektorer og finner sentroiden i hver av dem. Etter flere iterasjoner er utført ligger objektene nær sentroiden i hver av Voronoi-sektorene, og som danner et nettverk og kart av sektorer, kalt Voronoi-tesselering. Vanligvis benyttes euklidsk geometri og euklidske avstander.

En Gauss-blandet modell bygger på et bestemt antall tilfeldige Gauss-fordelinger (normalfordelinger) hvor parameterene blir optimalisert for å gi best mulig tilpasning til datasettet. En ulempe er at man påtvinger data en normalfordeling, som de nødvendigvis ikke følger.

En lineær klassifiksjon kan kodes som 0/1, suksess/feil, ja/nei osv. Lineær diskriminantanalyse ble utviklet av R.A.Fisher i studiet av multivariate normalfordelte data, 

Multivariable må reduseres i antall dimensjoner, hvor korrelerte variable erstattes med færre ukorrelerte variable. PCA (prinsipalkomponentanalyse), CA (korrespondensanalyse), DA (diskriminantanalyse) og NMDS (ikke-metrisk multidimensjonal skalering) er beregnet for data uten forklaringsvariable. CCA (kanonisk korrespondanseanalyse og RDA (redundensianalyse) er beregnet for både respons- og forklaringsvariable. Prinsipalkomponent 1 (PC1) er en vektor gjennom datasettet og som forklarer det meste av variasjonen. Prinsipalkomponent 2 (PC2) står ortogonalt på PC1, er ikke korrelert med denne og forklarer nest mest av variasjonen.

Tilbake til hovedside

Publisert 11. feb. 2015 09:25 - Sist endret 27. des. 2019 15:22