Redigerer K-means

{{språkvask}}
'''''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 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 <ref name="macqueen1967">{{cite conference
 |first=J. B. |last=MacQueen
 |year=1967
 |title=Some Methods for classification and Analysis of Multivariate Observations
 |url=http://projecteuclid.org/euclid.bsmsp/1200512992 |accessdate=2009-04-07
 |conference=Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability
 |publisher=University of California Press
 |volume=1 |pages=281&ndash;297
 |mr=0214227
 |zbl=0214.46201
}}</ref>, selv om ideen først ble beskrevet av Hugo Steinhaus i 1957<ref>{{cite journal
 |first=H. |last=Steinhaus |authorlink=Hugo Steinhaus
 |title=Sur la division des corps matériels en parties
 |journal=Bull. Acad. Polon. Sci.
 |volume=4 |issue=12 |pages=801&ndash;804
 |year=1957
 |mr=0090073
 |zbl=0079.16403 |language=fransk
}}</ref>. 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<ref name="lloyd1957">{{cite journal
 |first=S. P. |last=Lloyd
 |title=Least square quantization in PCM
 |journal=Bell Telephone Laboratories Paper
 |year=1957
}} Published in journal much later:
{{cite journal
 |first=S. P. |last=Lloyd.
 |url=http://www.cs.toronto.edu/~roweis/csc2515-2006/readings/lloyd57.pdf |accessdate=2009-04-15
 |title=Least squares quantization in PCM
 |journal=[[IEEE Transactions on Information Theory]]
 |volume=28 |issue=2 |pages=129&ndash;137
 |year=1982
 |doi=10.1109/TIT.1982.1056489
}}</ref>. 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 <ref name="forgy65">{{Cite journal
 |author=E.W. Forgy
 |title=Cluster analysis of multivariate data: efficiency versus interpretability of classifications
 |url=https://archive.org/details/sim_biometrics_1965-09_21_3/page/768
 |journal=Biometrics
 |volume=21
 |pages=768–769
 |year=1965}}</ref>. En mer effektiv versjon ble foreslått og publisert i Fortran av Hartigan og Wong i 1975/1979<ref name="hartigan1975">{{Cite book
 |title=Clustering algorithms
 |author=J.A. Hartigan
 |year=1975
 |publisher=John Wiley & Sons, Inc.
}}</ref><ref name="hartigan1979">{{Cite journal
 | first1 = J. A. |last1=Hartigan
 | first2 = M. A. |last2=Wong
 | year = 1979
 | title =  Algorithm AS 136: A K-Means Clustering Algorithm
 | journal = [[Journal of the Royal Statistical Society, Series C]]
 | volume = 28
 | issue = 1
 | pages = 100&ndash;108
 | jstor = 2346830
}}</ref>.

== 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 ==
<references/>

{{DISPLAYTITLE:''k''-means}}
[[Kategori:Algoritmer]]