K-means

***k''-means''' er en grupperingsalgoritme som brukes i [[informatikk]], [[kunstig Intelligens]] og matematisk optimering for å klassifisere enheter i kategorier eller grupper, såkalt ''klynging''. Den brukes også mye i [[datautvinning]]. ''k''-means lar en velge antall kategorier (''k''). Algoritmen kategoriserer enhetene automatisk og gjør seg ferdig når den har kommet frem til faste kategorier.

== Beskrivelse ==
''k''-means er en vektorkvantiseringsmetode som opprinnelig kommer fra signalbehandling. Den er populær innen grupperingsanalyse i [[datautvinning]]. ''k''-means forsøker å inndele ''n'' observasjoner i ''k'' grupper, hvor hver observasjon hører til gruppens nærmeste [[gjennomsnitt]], som fungerer som en [[prototype]] for gruppen. Dette resulterer i en inndeling av dataområdet i Voronoi-celler.

Problemet er beregningsmessig vanskelig, men det finnes effektive [[Heuristisk|heuristiske]] [[algoritmer]] som vanligvis blir anvendt og som raskt samles til et lokalt optimal. Disse ligner vanligvis på forventnings-maksimeringsalgoritmen for blandinger av normalfordelinger via en iterativ justeringstilnærming brukt av begge algoritmer. I tillegg bruker begge gruppe-sentere for å modellere informasjonen; derimot har ''k''-means en tendens til å finne grupper av sammenlignbar utbredelse, mens forventnings-maksimeringsmekanismen tillater grupper med forskjellige former.

== Bakgrunn ==
Termen «''k''-means» ble først brukt av James MacQueen i 1967 , selv om ideen først ble beskrevet av Hugo Steinhaus i 1957. Standardalgoritmen ble først foreslått av Stuart Lloyd i 1957 som en teknikk for [[PCM]], selv om den ikke ble publisert utenfor Bell Labs før 1982. I 1965 publiserte E. W. Forgy en metode som essensielt er den samme. På grunn av dette er metoden av og til referert til som Lloyd-Forgy . En mer effektiv versjon ble foreslått og publisert i Fortran av Hartigan og Wong i 1975/1979.

== Algoritmen ==
Gitt et sett av observasjoner (x<sub>1</sub>, x<sub>2</sub>, …, x<sub>n</sub>), hvor hver observasjon er en ''d''-dimensjonal reell vektor, forsøker ''k''-means å dele inn de ''n'' observasjonene i ''k'' (≤ ''n'') sett '''S''' = {S<sub>1</sub>, S<sub>2</sub>, …, S<sub>k</sub>} for å minimere summen av “within-cluster sum of squares” (WCSS), altså summen av kvadrater innenfor gruppen. Med andre ord forsøker den å finne:

hvor ***µ**<sub>i</sub>'' er gjennomsnittet av punktene i ''S<sub>i</sub>''.

=== Standardalgoritmen ===
Den mest vanlige algoritmen bruker en iterativ justeringsteknikk. På grunn av sin utbredelse er den ofte bare referert til som ***k*-means algoritmen**. Den er også referert til som Lloyd’s algoritme, spesielt innenfor informatikk-miljøet.

**Initiering**
* Putter alle verdiene inn 
* Velger ''k'' tilfeldige verdier som senter.

**Løkke**
* Legger alle verdier inn i grupper basert på nærmeste senter
* Kalkulerer nytt senter basert på gjennomsnittet av alle verdiene i en klynge.
* Fortsetter til center ikke flytter seg.

**Demonstrasjon av standardalgoritmen*'

<gallery>
Image:K-means steg 1.svg|*k* “gjennomsnitt” ved start (i dette tilfellet *k* = 3) blir tilfeldig generert innenfor data-domenet (vist i fargene rød, grønn og blå).
Image:K-means steg 2.svg|*k* grupper lages ved å assosiere hver observasjon med det nærmeste gjennomsnittet. Partisjonene her representerer Voronoi-diagrammet generert av gjennomsnittene.
Image:K-means steg 3.svg|Sentroiden av hvert av de *k* gruppene blir det nye gjennomsnittet.
Image:K-means steg 4.svg|Steg 2 og 3 repeteres til konvergens har blitt nådd (sentroidene flytter seg ikke).
</gallery>

Algoritmen i seg selv tar inn alle elementene som skal sorteres. Deretter velger den tilfeldige verdier som senter for hver kategori. I dette eksempelet brukes tre kategorier, og algoritmen velger da ut tre tilfeldige sentre. Videre legges alle elementene inn i kategorien tilhørende senteret de har kortest euklidisk distanse til. I siste fase av løkken regnes nye sentere ut basert på gjennomsnittet av alle verdiene i kategoriene. Deretter legges verdiene på nytt inn i kategoriene som nå er nærmest, basert på eukledisk distanse.

Dette fortsetter til alle kategorienes senter slutter å endre seg. Dette vil si at alle verdiene har funnet en kategori som passer og kategorienes sentroider har stabilisert seg.

=== Variasjoner ===
* Jenks natural breaks optimization
* *k*-medians-gruppering
* *k*-medoids
* Fuzzy C-Means Clustering
* Gaussian mixture (gaussisk miks)
* Flere metoder for å velge bedre startgrupper, for eksempel *k*-means++
* Filtreringsalgoritmen bruker *kd*-trær for å øke hastigheten på hvert *k*-means steg
* Noen metoder forsøker å øke hastigheten på hvert *k*-means steg ved å bruke coresets eller triangelaksiomet
* Unnslippe lokale optima ved å bytte punkter mellom klynger
* Den sfæriske *k*-means-algoritmen passer godt til retningsdata
* Minkowski metric weighted *k''-means forholder seg til irrelevante trekk ved å tilegne gruppe-spesifikke vekter til hvert trekk

## Referanser