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.
Klassifisering
Ved klassifisering søker man etter mønstre og klassemedlemskap for biologiske data, og plasserer objekter i på forhånd definerte grupper. Dette danner basis for mønstergjenkjenning. Innen taksonomi er arter plassert i grupper basert på likheter og forskjeller.
En kortstokk kan klassifiseres på forskjellige måter som gir forskjellig antall klasser:
4:♠♣♥♦
2:♠♣ og ♥♦
13:1,2,3,4,5,6,7,8,9,10,Kn,Ko,Da
3: 2,4,6,8,10 og 1,3,5,7,9 og Kn,Ko,Da
Klyngeanalyse
Ved klyngeanalyse plasseres objekter eller grupper i ikke forhåndsdefinerte klasser. Naturlige grupper blir avhengig av startbetingelsene for klyngeanalysen.
Ved klyngeanalyse har man et avstandsmål (likhetsmål) hvor objekter i samme klynge er nærmere hverandre enn objekter i andre klynger. Forskjellige avstandsmål benyttes. Euklids avstand (aritmetisk avstand) er en rett linje i et euklidsk rom. Mahalanobis avstand er en annen. Algoritmen BLAST (Basic Local Alignment Search Tool) brukes til å klassifisere sekvensdata (nukletidsekvens, aminosyresekvens). Ved Bayesiansk klassifisering har man a priori (på forhånd) definert egenskaper ved klassen og man kan deretter beregne sannsynligheten for at et objekt tilhører en av de forhåndsdefinerte klassene. Bayesiansk klassifisering brukes til å definere hva som er søppelpost (spam). Ved prinsipalkomponentanalyse ønsker man å trekke to ortogonale prinsipalkompoenenter gjennom datasettet som forklarer mest mulig av variasjonen.
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,
Alfa-beta-beskjæring («αβ-pruning») er bruk av en søkealgoritme å redusere antall kombinasjoner og muligheter i nodene (greiningspunktene i søketrærne) ved å kutte ut tilfellene som er svært lite sannsynlige og derved redusere behovet for datamaskinkraft og kunne gi raskere svar.
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.
Edgar Andersons irisdatasett er mye brukt som eksempel i statistikkundervisningen, og det ble også benyttet av RA Fisher. Anderson målte lengde (Sepal.Length) og bredde (Sepal.Width) (cm)av sepaler (begerblad), og lengde (Petal.Length) og bredde (Petal.Width) av petaler (kronblad) hos 50 blomster fra tre forskjellige liljearter Iris setosa, Iris versicolor og Iris virginica.