Изворни код странице Klasterizacija metodom K-srednjih vrednosti

-{T|sr:Klasterizacija metodom ''K''-srednjih vrednosti;sr-ec:Кластеризација методом ''K''-средњих вредности;sr-el:Klasterizacija metodom ''K''-srednjih vrednosti}-{{čišćenje-lat|razlog=Pravopis i gramatika, tagovi za spreč. transl., prevod...}}
U [[Analiza podataka|analizi podataka]], '''klasterizacija metodom ''k''-srednjih vrednosti''' ({{jez-eng-lat|k-means clustering}}) metod je za [[Analiza grupisanja|analizu grupisanja]] čiji je cilj particionisanje ''n'' opservacija u ''k'' klastera u kojem svaka opservacija pripada klasteru sa najsličnijim značenjem. Ovo rezultuje particionisanjem prostora za podatke u [[Voronoi dijagram|Voronoi ćelije]].

Ovaj problem je računarski težak ([[НП-тешки проблеми|NP-težak]]), ipak postoje efiaksni heuristički algoritmi koji se često primenjuju i brzo konvergiraju ka lokalnom optimumu. Oni su često slični algoritmu [[Алгоритам Очекивање-максимизација (ЕМ алгоритам)|očekivane minimizacije]] za mešavine [[Нормална расподела|Gausovih raspodela]] putem iterativnog pristupa prečišćavanja zastupljenog kod oba algoritma. Pored toga, oba koriste cetre klastera (grupa) da bi oblikovali podatak. Ipak, klasterizacija medotom ''k''-srednjih vrednosti teži da nađe klastere uporedivog prostornog obima, dok mehanizam algoritma očekivane minimizacije dozvoljava da klaster ima različite oblike.

== Opis ==
Dat je skup opservacija ('''x'''<sub>1</sub>, '''x'''<sub>2</sub>, …, '''x'''<sub>''n''</sub>), gde je svaka opservacija ''d''-dimenzionalan realan vektor. Cilj ovog metoda je da praticioniše ''n'' opservacija u ''k'' skupova (''k'' ≤ ''n'') '''S''' = {''S''<sub>1</sub>, ''S''<sub>2</sub>, …, ''S''<sub>''k''</sub>}, tako da minimizuje sumu kvadrata unutar klastera ({{Jez-engl-lat|within-cluster sum of squares - WCSS}}).

:<math>\underset{\mathbf{S}} {\operatorname{arg\,min}} \sum_{i=1}^{k} \sum_{\mathbf x_j \in S_i} \left\| \mathbf x_j - \boldsymbol\mu_i \right\|^2 </math>

Gde je '''''μ'''''<sub>''i''</sub> glavna tačka u ''S''<sub>''i''</sub>.

== Istorija ==
Izraz „''k''-means” je prvi upotrebio Džejms Makkvid 1967. godine,<ref name="macqueen1967">{{cite conference-lat
 |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 = 7. 4. 2009.
 |conference=Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability
 |publisher=University of California Press
 |volume=1 |pages=281-297
 |mr=0214227
 |zbl=0214.46201
}}</ref> iako je prvi došao na ideju [[Gugo Štejngauz]] 1957.<ref>{{cite journal-lat
 |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-804
 |year=1957
 |mr=0090073
 |zbl=0079.16403
}}</ref> [[#Standard algorithm|Standardni algoritam]] je prvi predstavio Stjuart Lojd 1957. kao tehniku za [[Импулсна кодна модулација|impulsivnu kodnu modulaciju]], mada nije objavljena van [[Белове лабораторије|Belovih laboratorija]] do 1982.<ref name="lloyd1957">{{cite journal-lat
 |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-lat
 |first=S. P. |last=Lloyd.
 |url=http://www.cs.toronto.edu/~roweis/csc2515-2006/readings/lloyd57.pdf |accessdate = 15. 4. 2009.
 |title=Least squares quantization in PCM
 |journal=[[IEEE Transactions on Information Theory]]
 |volume=28 |issue=2 |pages=129-137
 |year=1982
 |doi=10.1109/TIT.1982.1056489
}}</ref> E. V. Forgi je 1956. objavio esencialno isti metod, zbog čega ga nekad nazivaju i Lojd-Forgijev metod.<ref name="forgy65">{{cite journal-lat
 |author=E.W. Forgy
 |title=Cluster analysis of multivariate data: efficiency versus interpretability of classifications
 |journal=Biometrics
 |volume=21
 |pages=768–769
 |year=1965}}</ref> Hartigan i Vong su predstavili efikasniju verziju i objavili je u [[Фортран|Fortranu]] 1975/1979.<ref name="hartigan1975">{{cite book-lat
 |title=Clustering algorithms
 |author=J.A. Hartigan
 |year=1975
 |publisher=John Wiley & Sons, Inc.
}}</ref><ref name="hartigan1979" />

== Algoritmi ==

=== Standardni algoritam ===
Najčešći algoritam koristi iterativne tehnike prečišćavanja. Uprkos velikoj prisutnosti često se naziva ''k-menas algoritam'', a takođe i ''[[Lojdov algoritam]]'', naročito u računarskom društvu.

Nakon što se algoritmu da inicijalni set ''k'' means '''m'''<sub>1</sub><sup>(1)</sup>,…,'''m'''<sub>''k''</sub><sup>(1)</sup> (pogledati ispod), algoritam radi tako što alternira između 2 koraka:<ref>{{cite book-lat
| last =MacKay
| first =David
| authorlink =David MacKay 
| title =Information Theory, Inference and Learning Algorithms
| publisher = Cambridge University Press
|year=2003
| url =http://www.inference.phy.cam.ac.uk/mackay/itila/book.html
|isbn=978-0-521-64298-9| chapter=Chapter 20. An Example Inference Task: Clustering
| chapterurl=http://www.inference.phy.cam.ac.uk/mackay/itprnn/ps/284.292.pdf
|pages=284-292
| ref=mackay2003
| mr=2012999
}}</ref>
:'''Korak dodele''': Svakom klasteru se dodeljuje observaija čiji je značenje njemu najbliže (opservacije se particionišu prema [[Voronoi dijagaram]]u generisanom po značenju).
::<math>S_i^{(t)} = \big \{ x_p : \big \| x_p - m^{(t)}_i \big \| \le \big \| x_p - m^{(t)}_j \big \| \ \forall\ 1 \le j \le k \big\},</math>
:: gde je svaki <math>x_p</math> dodeljen tačno jednom <math>S^{(t)}</math>, a čak ako može, dodeljen je dvoma ili više.
:'''Korak ažuriranja''': Izračunava novo značenje koje treba postati [[Centroid|centar]] nove opservacije u klasteru.
::<math>\mathbf m^{(t+1)}_i = \frac{1}{|S^{(t)}_i|} \sum_{\mathbf x_j \in S^{(t)}_i} \mathbf x_j </math>
Algoritam se zaustavlja kada u koraku dodeljivanja više nema promena.

==== Metode inicijalizacije ====
Najčešće korištene medote inicijalizacije su Forgy i Random Partition.<ref name="hamerly">{{cite conference-lat
 |author1=Hamerly, G.  |author2=Elkan, C.
  |lastauthoramp=yes |year=2002
 |title=Alternatives to the k-means algorithm that find better clusterings
 |booktitle=Proceedings of the eleventh international conference on Information and knowledge management (CIKM)
 |url=http://charlotte.ucsd.edu/users/elkan/cikm02.pdf
 |archiveurl=https://web.archive.org/web/20061107121237/http://charlotte.ucsd.edu/users/elkan/cikm02.pdf
 |archivedate=7. 11. 2006
}}</ref>
Forgy metoda nasumično bira ''k'' opservacija iz seta podataka i koristi ih kao inicijalna značenja. Random Partition prvo nasumično dodeljuje klastere opservacijama, a onda prelazi na korak ažuriranja, zatim računa inicijalna značenja koja će biti centri tačaka nasumično dodeljeni klasterima. Forgy metod teži da razdvaja inicijalna značanja, dok ih Random Partition približava centru setu podataka. Prema Hamerly, i dr.,<ref name="hamerly"/> Random Partition metod se generalno više preferira za algoritme kao što su ''k''-harmonic means i fuzzy ''k''-means. Za algoritam očekivane minimizacije i standardni ''k''-means algoritam, preferira se Forgy metod.

<gallery caption="Demonstracija standardnog algoritma" widths="150px">
Image:K Means Example Step 1.svg|1) ''k'' initial "means" (in this case ''k''=3) are randomly generated within the data domain (shown in color).
Image:K Means Example Step 2.svg|2) ''k'' clusters are created by associating every observation with the nearest mean. The partitions here represent the [[Voronoi diagram]] generated by the means.
Image:K Means Example Step 3.svg|3) The [[centroid]] of each of the ''k'' clusters becomes the new mean.
Image:K Means Example Step 4.svg|4) Steps 2 and 3 are repeated until convergence has been reached.
</gallery>
Pošto je ovo hereutički algoritam, ne garantuje se da će konvergirati ga globalnom optimumu, takođe, rezultat može da zavisi od inicijalnih klastera. Pošto je algoritam uglavnom vrlo brz, često se pokreće više puta sa različitim početnim uslovima. Ipak, u najgorem slučaju ''k''-means može da se izvršava vrlo sporo: kokretno, pokazano je da postoji određeni set tačaka, čak i u 2 dimenzije, u kojima ''k''-means ima eksponencijalno vreme izvršavanja {{math|2<sup>Ω(<var>n</var>)</sup>}}.<ref>{{cite journal-lat
 |first=A. |last=Vattani.
 |url=http://cseweb.ucsd.edu/users/avattani/papers/kmeans-journal.pdf
 |title=k-means requires exponentially many iterations even in the plane
 |journal=[[Discrete and Computational Geometry]]
 |volume=45 |issue=4 |pages=596-616
 |year=2011
 |doi=10.1007/s00454-011-9340-1
}}</ref> Ovaj set tačaka se uglavnom ne pojavljuje u praksi, što je potkrepljeno činjenicom da je ''glatko'' vreme izvršava ''k''-menas algoritma polinomijalno.<ref name="Arthur, D.; Manthey, B.; Roeglin, H. 2009">{{cite conference-lat |author1=Arthur, D. |author2=Manthey, B. |author3=Roeglin, H. |year=2009| title=k-means has polynomial smoothed complexity | booktitle=Proceedings of the 50th Symposium on Foundations of Computer Science (FOCS)}}</ref>

Korak dodeljivanja se naziva i korak očekivanja, a korak ažuriranja korak maksimizacije, čime algotiram postaje varijanta algortitma očekivane minimizacije.

=== Složenost ===
U odnosu na računarsku složenost, ''k''-menas clustering problem observacija u ''d'' dimenzijama je:
* NP-težak u Euklidovom prostoru ''d'', čak i za 2 klastera<ref>{{cite journal-lat
 |author1=Aloise, D. |author2=Deshpande, A. |author3=Hansen, P. |author4=Popat, P. |title=NP-hardness of Euclidean sum-of-squares clustering
 |journal=[[Machine Learning (journal)|Machine Learning]]
 |year=2009
 |volume=75 |pages=245-249
 |doi=10.1007/s10994-009-5103-0}}</ref><ref>{{cite journal-lat
 |title=Random Projection Trees for Vector Quantization
 |author1=Dasgupta, S.  |author2=Freund, Y.
  |lastauthoramp=yes |journal=Information Theory, IEEE Transactions on
 |volume=55
 |pages=3229-3242
 |year=2009
 |doi=10.1109/TIT.2009.2021326
 |arxiv=0805.1390}}</ref>
* NP-težak za uopšten broj klastera k<ref>{{cite journal-lat
 |author1=Mahajan, M. |author2=Nimbhorkar, P. |author3=Varadarajan, K. |title=The Planar k-Means Problem is NP-Hard
 |journal=[[Lecture Notes in Computer Science]]
 |year=2009
 |volume=5431 |pages=274-285
 |doi=10.1007/978-3-642-00202-1_24}}</ref>
* Ako su k i d (dimenzija) popravljene, problem može biti precizno rešen u vremenu '''''O(n<sup>dk+1</sup> log n)''''', gde je ''n'' broj celina koje treba grupisati<ref>{{cite conference-lat
 |author1=Inaba, M. |author2=Katoh, N. |author3=Imai, H. |year=1994
 |title=Applications of weighted Voronoi diagrams and randomization to variance-based ''k''-clustering
 |conference=[[Symposium on Computational Geometry|Proceedings of 10th ACM Symposium on Computational Geometry]]
 |pages=332-339
 |doi= 10.1145/177424.178042}}</ref>

Takođe, više [[Хеуристика|heurističkih]] algoritma se generano koriste.
* <math>k</math>-means je razmatran iznad glatkog polinomijalnog vremena. Pokazano je da<ref name="Arthur, D.; Manthey, B.; Roeglin, H. 2009"/> je za proizvoljan set od <math>n</math> tačaka <math>[0,1]^d</math>, ako je svaka tačka nezavisno pomerena od strane normalne raspodele sa značenjem <math>0</math> i neslaganjem <math>\sigma^2</math>, onda je očekivano vreme izvršavanja <math>k</math>-means algoritma ograničeno na <math>O(n^{34}k^{34}d^8 log^4(n)/ \sigma^6 )</math>, što je polinomijalno u <math>n</math>, <math>k</math>, <math>d</math> i <math>1/\sigma</math>.
* Bolje ogrnaičenje je dokazano za jednostavne slučajeve. Na primer,<ref>{{cite thesis| author=Arthur Abhishek Bhowmick |year=2009| title= A theoretical analysis of Lloyd's algorithm for k-means clustering }}</ref> pokazano je da vreme izvršavanja <math>k</math>-means algoritam ograničeno na <math>O(dn^4M^2)</math> za <math>n</math> tačka u mreži intedžera <math>\{1,\dots, M\}^d</math>.

=== Varijacije ===
* [[Klasterizacija metodom fazi C-srednjih vrednosti|Klasterizacija metodom ''fazi'' C-srednjih vrednosti]] je blaža verzija K-means, gde svaka tačka podataka ima fruzzy stepen pripadnosti za svaki klaster.
* [[Gausov model mešavine]] u kombinaciji sa algoritmom očekivane minimizacije (EM algoritam) održava verovatnoću dodele kalsteru.
* Nekoliko metoda je predloženo za izbor boljih početnih klasetra. Jedan od novijih predloga je [[K-means++|k-menas++]].
* Algortam prečišćavanja koristi [[K-D stablo]] da bi ubrzao svaki k-menas korak.<ref>{{cite journal-lat
 |author=Kanungo, T. |display-authors=etal
 |doi=10.1109/TPAMI.2002.1017616
 |url=http://www.cs.umd.edu/~mount/Papers/pami02.pdf |accessdate = 24. 4. 2009.
 |title=An efficient k-means clustering algorithm: Analysis and implementation
 |journal=IEEE Trans. Pattern Analysis and Machine Intelligence
 |volume=24 |year=2002|pages=881-892}}</ref>
* Neke metode nameravaju da ubrzaju svaki ''k''-menas korak korišćenjem [[korset]]a<ref>{{cite conference-lat
 |author1=Frahling, G. |author2=Sohler, C. |year=2006
 |title=A fast k-means implementation using coresets
 |booktitle=[[Symposium on Computational Geometry|Proceedings of the twenty-second annual symposium on Computational geometry (SoCG)]]
 |url=http://www.frahling.de/Gereon_Frahling/Publications_files/A%20fast%20k-means%20implementation%20using%20Coresets%20(Frahling,%20Sohler).pdf
 |archiveurl=https://web.archive.org/web/20100705043604/http://www.frahling.de/Gereon_Frahling/Publications_files/A%20fast%20k-means%20implementation%20using%20Coresets%20(Frahling,%20Sohler).pdf
 |archivedate=5. 7. 2010
}}</ref> ili [[nejednakosti trougla]].<ref>{{cite conference-lat
 |author = Elkan, C.
 |year=2003
 |title=Using the triangle inequality to accelerate k-means
 |booktitle=Proceedings of the Twentieth International Conference on Machine Learning (ICML)
 |url=http://www-cse.ucsd.edu/~elkan/kmeansicml03.pdf
}}</ref>
* zbegavanje lokalnog optimuma zamenjujući tačke između klastera.<ref name="hartigan1979">{{cite journal-lat
 | 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-108
 | jstor = 2346830
}}</ref>
* Spherical k-means clustering algoritam je primeren za usmerene podarke.<ref>{{cite journal-lat
 | first1 = I. S. |last1=Dhillon
 | first2 = D. M. |last2=Modha
 |year=2001
 | title =  Concept decompositions for large sparse text data using clustering
 | journal = Machine Learning
 | volume = 42
 | issue = 1
 |pages=143-175
}}</ref>
* Minkowski metric weighted k-means se suočava sa problemom ''buke''<ref>{{cite journal-lat
 | first1 = R. C. |last1=Amorim
 | first2 = B |last2=Mirkin
 |year=2012
 | title =  Minkowski metric, feature weighting and anomalous cluster initializing in K-Means clustering
 | journal = Pattern Recognition
 | volume = 45
 | issue = 3
 |pages=1061-1075
 | doi=10.1016/j.patcog.2011.08.012
}}</ref>

== Diskusija ==
[[Датотека:K-means convergence to a local minimum.png|мини|650px|Tipičan primer konevrgencije k-means algoritma ka lokalnom minimumu.<ref name = "Mirkes2011"/>]]

Dve glavne karakteristike ''k''-menas algoritma koje ga čini efikasnim su često i njegovi najveći nedostaci::
* Euklidsko rastojanje se koristi kao metrika, a disprezija kao mera rasutosti klastera.
* Broj klastera ''k'' je ulazni parametar, loš izbor ''k'' može prouzrokovati loše rezultate. Zbog toga, kad se izvršava ''k''-menas algoritam važno je pokrenuti dijagnostičku proveru za [[određivanje broja klastera u setu podataka]]
* Konvergencija ka lokalnom minimumu može prouzrokovati pogrešne ‘rezultate’

Ključno ograničenje ''k''-menas algoritma je model klastera. Koncept je baziran na sfernim klasterima koji se razdvajaju na takav način da vrednost značenja konvergira ka centru klastera. Klasteri bi trebalo da budu slične veličine, da bi dodeljivanje najbližem centru klastera bilo ispavno. Na primer, kada se primenjuje ''k''-means za vrednosti ''k''=3 na dobro poznati [[set podataka cveta Iris]], rezultat često ne uradi razdvajanje 3 vrste Irisa koje su u setu podataka. Sa ''k''=2, dva vidljiva klastera (svaki sadrži 2 vrste) će biti otkriveni, a kad je ''k''=3, jedan od 2 klastera će biti podeljen na dva jednaka dela. Dakle, ''k''=2 je prikladniji za set podataka, iako sadrži 3 klase. Kao i kod ostalih algoritama za grupisanje, rezultati ''k''-menas algoritma se zasnivaju na tome da set podataka zadovolji pretpostavke koje je napravio algoritam za grupisanje. Za neke slučajeve radi dobro, za neke ne.

Rezultat ''k''-menas algoritma se može prikazati i kao Voronoi ćelije značenja klastera. Kad se podatak podeli između značenja klastera, to može dovesti do suboptimalnog deljenja, kao u primeru ‘mouse’. Gausovi modeli, koje koristi EM algoritam (koji se može gledati kao generalizacija ''k''-menas algoritma), su fleksibilniji ovde, jer imaju i razlike i kovarijanse. Rezultat EM-aa može da smesti klastere varljive veličinine mnogo bolje nego ''k''-menas, kao i povezane kalstere (ne u ovom primeru).

== Primena ==

''K''-means clustering je, konkretno kada koristi heuristike kao što je Lloydov algoritam, lak za implementaciju i primenjivanje na veliki set podataka. Zbog toga, uspešno se koristi u raznim oblastima, počev od segmentacije tržišta, računarskog vida, geostatike<ref>{{cite journal|doi=10.1007/s11004-010-9276-7 |title=Stochastic Simulation of Patterns Using Distance-Based Pattern Modeling |year=2010 |last1=Honarkhah |first1=Mehrdad |last2=Caers |first2=Jef |journal=Mathematical Geosciences |volume=42 |issue=5 |pages=487–517 |bibcode=2010MaGeo..42..487H |s2cid=73657847 }}</ref> i astronomije do agrokulture. Često se koristi kao korak pretprocesiranja za druge algoritme, npr. za pronalaženje početne konfiguraije.

=== Učenje za (semi-)nadgledane klasifikacije ===

''K''-means clustering k-menas clutering je korišten za kao korak za semi-[[nadgledano učenje]].<ref>{{cite encyclopedia
|last1 = Coates
|first1 = Adam
|last2 = Ng
|first2 = Andrew Y.
|title = Learning feature representations with k-means
|editor = G. Montavon, G. B.  |display-editors=etal
|encyclopedia = Neural Networks: Tricks of the Trade
|publisher = Springer
|year=2012
|url = http://www.stanford.edu/~acoates/papers/coatesng_nntot2012.pdf
|archiveurl=https://web.archive.org/web/20130606213934/http://www.stanford.edu/~acoates/papers/coatesng_nntot2012.pdf
|archivedate=6. 6. 2013
}}</ref>
U ovoj upotrebi, klaterovanje se izvodi u velikom setu podataka, koji treba da se označi. Onda se izvršava učenje nagdledanjem i za svaki označeni uzorak razdaljina za svaki od ''k'' naučenih centralnih klastera je kompijuterizovana da bi podstakla ''k'' extra odlika za uzorak. Odlike mogu biti bulovske sa vrednošću 1 za zatvorene centre<ref>{{cite conference-lat
|last1 = Csurka
|first1 = Gabriella
|last2 = Dance
|first2 = Christopher C.
|last3 = Fan
|first3 = Lixin
|last4 = Willamowski
|first4 = Jutta
|last5 = Bray
|first5 = Cédric
|title = Visual categorization with bags of keypoints
|conference = ECCV Workshop on Statistical Learning in Computer Vision
|year=2004
|url = http://www.cs.cmu.edu/~efros/courses/LBMV07/Papers/csurka-eccv-04.pdf
}}</ref> ili neka glatka transformacija za daleke transfomrišući uzorak klastera kroz [[Gausov RBF]], on sadrži sakrivene slojeve [[Funkciona mreža raijalne osnove|radijalne osnovne mreže funkcije]].<ref name="schwenker">{{cite journal-lat
|last1 = Schwenker
|first1 = Friedhelm
|last2 = Kestler
|first2 = Hans A.
|last3 = Palm
|first3 = Günther
|title = Three learning phases for radial-basis-function networks
|journal = Neural Networks
|volume = 14
|pages=439–458
|year=2001
|url = http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.109.312&rep=rep1&type=pdf
}}</ref>

Ova upotreba k-menas aa je uspešno kombinovana sa jednistavnim, [[linearni klasifikator|linearnim klasifikatorom]] za semi-nedgledanoučenje u [[Obrada prirodnih jezika|obradi prirodnih jezika]] i u kompijuterskom vidu.

== Odnos sa drugim algoritmima za statičko mašinsko učenje ==

''K''-means clustering, i njegov pridruženi algoritam EM, u specijalnom slučaju Gausovog modela mešavine, konkretno, limit uzimanja kovarijanski kao dijagonalne, jednake i male. Nekad je jednostavno uopštiti k-menas problem u Gausov metod mešavine..<ref>{{cite book-lat |last1=Press| first1=WH |last2=Teukolsky| first2=SA |last3=Vetterling| first3=WT |last4=Flannery| first4=BP |year=2007| title=Numerical Recipes: The Art of Scientific Computing | edition=3rd | publisher=Cambridge University Press |  publication-place=New York |isbn=978-0-521-88068-8 | chapter=Section 16.1. Gaussian Mixture Models and k-Means Clustering | chapter-url=http://apps.nrbook.com/empanel/index.html#pg=842}}</ref>

=== Mean shift clustering ===
Osnovni -{[[mean shift]]}- sadrži skup tačaka podataka iste veličine kao ulazni set podataka. Inicijalno, ovaj set je kopiram od ulaznog seta. Onda je ovaj set iterativno premešten na osnovu značenja onih tačaka u setu koji su na određenoj udaljenosti od te tačke. ''K''-menas ograničava ovaj promenjen set na k tačaka uglavnom mnogo manjim nego broj tačaka u ulaznom setu podataka i zamenjuje ih setom po značenju svih tačaka u ulaznom setu koje su bliže toj tački od ostalih. Mean shift algoritam, koji je sličan ''k''-means algoritmu se zove i likelihood menas shift, zamenjuje set tačaka trenutne razmene po značenju svih tačaka u ulaznom setu koje su u okviru zadate razdaljine seta koji se menja.<ref name="Little2011">{{cite journal-lat|last=Little|first= M.A.|author2=Jones, N.S.|title=Generalized Methods and Solvers for Piecewise Constant Signals: Part I| journal=Proc. Roy. Soc. A.|url = http://www.maxlittle.net/publications/pwc_filtering_arxiv.pdf |year=2011 }}</ref> Jedna od prednsoti mean shift algoritma u odnosu na ''k''-menas je što nema potrebe da se bira broj klastera, jer mean shirt uglavnom nađe vrlo malo klastera, ako mali broj postoji. Ipak, mean shift može biti sporiji od ''k''-menas algoritma i još uvek zahteva selekciju propusnog opsega parametra. Mena shift ima varijante kao i ''k''-menas.

=== Analiza osnovnih komponenti (PCA) ===
Trvdi se<ref>{{cite journal-lat|author=H. Zha |display-authors=etal |title=Spectral Relaxation for K-means Clustering|journal=Neural Information Processing Systems vol.14 (NIPS 2001)|location=Vancouver, Canada|year=2001|url=http://ranger.uta.edu/~chqding/papers/Zha-Kmeans.pdf|pages=1057–1064}}</ref><ref>{{cite journal-lat|last=Ding|first=Chris|author2= Xiaofeng He|title=K-means Clustering via Principal Component Analysis|work=Proc. of Int'l Conf. Machine Learning (ICML 2004)|year=2004|url=http://ranger.uta.edu/~chqding/papers/KmeansPCA1.pdf|pages=225–232}}</ref> da je 'opušteno' rešenje {{math|<var>k</var>}}-means clustering, sprecifikovano od strane indokatora klastera, dato od strane PCA ([[Metod glavnih komponenti]]) osnovne komponete i da je PCA međuprostor proširen osnovnim uputstvima identičan centralnom međuprostoru klastera. Ipak, nije novo da je PCA korisna opuštanje ''k''-meansa (pogledati, npr.<ref>{{cite journal-lat | title = Clustering large graphs via the singular value decomposition | journal = Machine learning |year=2004| first = P. |last=Drineas|author2 = A. Frieze |display-authors=etal | volume = 56 | id = | url = http://www.cc.gatech.edu/~vempala/papers/dfkvv.pdf | accessdate = 2. 8. 2012.|pages=9–33}}</ref>), i da ide ka neotrktivenim kontraprimerima tvrdnje da je međuprostor centra kalstera proširen.

=== Bilateralno prečišćavanje ===
''k''-means implicitno pretpostavlja da redosled ulaznog seta podataka nebitan. [[Bilateralni filter]] je sličan ''k''-menasu po tome što održava set tačaka podataka koje su iterativno premeštene na osnovu značenja. Ipak, on ograničava izračunavanje značenja da bi uključio samo tačke koju su blizu na osnovu redosleda unosa. Ovo ga čini primenljivim za probleme kao što je ''image denoising'', gde je prostorna raspodela piksela od velike važnosti.<ref name="Little2011"/> This makes it applicable to problems such as image denoising, where the spatial arrangement of pixels in an image is of critical importance.

== Slični problemi ==
Skup kvadratnih grešaka koji minimizuje funkcije za kalsterovanje takođe uključuje i [[К-медоид|k-medoid]] algoritam. Ovo je pristup koji tera centralnu tačku svakog klastera da bude jedna od stvarnih tačaka.

== Softver ==

=== Besplatan ===
* [[Apache Mahout]] [http://cwiki.apache.org/MAHOUT/k-means-clustering.html k-Means]
* [[CrimeStat]] implements two spatial K-means algorithms, one of which allows the user to define the starting locations.
* [[ELKI]] contains k-means (with Lloyd and MacQueen iteration, along with different initializations such as k-means++ initialization) and various more advanced clustering algorithms
* [http://www.mlpack.org MLPACK] contains a K-Means implementation
* [[R (programming language)|R]] [http://stat.ethz.ch/R-manual/R-patched/library/stats/html/kmeans.html kmeans] implements a variety of algorithms<ref name="macqueen1967"/><ref name="lloyd1957"/><ref name="hartigan1979"/>
* [[SciPy]] [http://docs.scipy.org/doc/scipy/reference/cluster.vq.html vector-quantization]
* [http://www.codeding.com/?article=14 Silverlight widget demonstrating k-means algorithm]
* [http://pgxn.org/dist/kmeans/ PostgreSQL extension for k-means]
* [[Weka (machine learning)|Weka]] contains k-means and a few variants of it, including k-means++ and x-means.
* [http://spectralpython.sourceforge.net/algorithms.html#k-means-clustering Spectral Python] contains methods for [[unsupervised classification]] including a K-means clustering method.
* [http://scikit-learn.org/dev/modules/generated/sklearn.cluster.KMeans.html scikit learn] machine learning in Python contains a K-Means implementation
* [[OpenCV]] contains a [http://docs.opencv.org/modules/core/doc/clustering.html?highlight=kmeans#cv2.kmeans K-means] implementation under [[Bsd licence|BSD licence]].

=== Komercijalni ===
* IDL Cluster, Clust_Wts
* [http://reference.wolfram.com/mathematica/ref/ClusteringComponents.html ''Mathematica'' ClusteringComponents function]
* [[MATLAB]] [http://www.mathworks.com/access/helpdesk/help/toolbox/stats/kmeans.html kmeans] {{Wayback|url=http://www.mathworks.com/access/helpdesk/help/toolbox/stats/kmeans.html |date=20100510135707 }}
* [[SAS System|SAS]] [http://support.sas.com/documentation/cdl/en/statug/63033/HTML/default/fastclus_toc.htm FASTCLUS]
* [http://www.visumap.com/index.aspx?p=Products VisuMap kMeans Clustering] {{Wayback|url=http://www.visumap.com/index.aspx?p=Products |date=20130201113544 }}

=== Izvorni kod ===
* [[ELKI]] i [[Weka]] su napisani u Javi i uključuju k-srednje vrednosti i varijacije
* primena K-srednjih vrednosti u PHP-u,<ref>{{Cite web |url=http://www25.brinkster.com/denshade/kmeans.php.htm |title=Архивирана копија |access-date=23. 10. 2007 |archive-url=https://web.archive.org/web/20071023080012/http://www25.brinkster.com/denshade/kmeans.php.htm# |archive-date=23. 10. 2007 |url-status=dead }}</ref> korišćenje VB,<ref>[http://people.revoledu.com/kardi/tutorial/kMean/download.htm K-Means Clustering Tutorial: Download{{Ботовски наслов}}]</ref> korišćenje Perl,<ref>{{Cite web |url=http://www.lwebzem.com/cgi-bin/k_means/test3.cgi |title=Perl script for Kmeans clustering{{Ботовски наслов}} |access-date=01. 06. 2013 |archive-url=https://web.archive.org/web/20120618071332/http://www.lwebzem.com/cgi-bin/k_means/test3.cgi |archive-date=18. 06. 2012 |url-status=dead }}</ref> korišćenje C++,<ref>[http://codingplayground.blogspot.com/2009/03/k-means-in-c.html Antonio Gulli's coding playground: K-means in C{{Ботовски наслов}}]</ref> korišćenje Matlab,<ref>[http://people.revoledu.com/kardi/tutorial/kMean/matlab_kMeans.htm K-Means Clustering Tutorial: Matlab Code{{Ботовски наслов}}]</ref> korišćenje Ruby,<ref>[http://ai4r.org/index.html AI4R :: Artificial Intelligence for Ruby{{Ботовски наслов}}]</ref><ref>{{Cite web |url=https://github.com/reddavis/K-Means |title=reddavis/K-Means · GitHub{{Ботовски наслов}} |website=[[GitHub]] |access-date=08. 07. 2012 |archive-url=https://archive.today/20120708093729/https://github.com/reddavis/K-Means |archive-date=08. 07. 2012 |url-status=live }}</ref> korišćenje Python with scipy,<ref>[http://docs.scipy.org/doc/scipy/reference/cluster.vq.html K-means clustering and vector quantization (scipy.cluster.vq) — SciPy v0.11 Reference Guide (DRAFT){{Ботовски наслов}}]</ref> using X10<ref>{{Cite web |url=http://dist.codehaus.org/x10/applications/samples/KMeansDist.x10 |title=Архивирана копија |access-date=09. 07. 2012 |archive-url=https://archive.today/20120709084340/http://dist.codehaus.org/x10/applications/samples/KMeansDist.x10# |archive-date=09. 07. 2012 |url-status=dead }}</ref>
* paralelna -{out-of-core}- implementacija u C-u<ref>https://web.archive.org/web/20110607074701/http://www.cs.princeton.edu/~wdong/kmeans/</ref>
* kolekcija otvorenog koda klastering algoritama, uključujući k-srednje vrednosti, implentirano u Javaskriptu<ref>http://code.google.com/p/figue/ FIGUE</ref> Online demo.<ref>{{Cite web |url=http://web.science.mq.edu.au/~jydelort/figue/demo.html |title=Interactive Demo of figue{{Ботовски наслов}} |access-date=06. 07. 2011 |archive-url=https://archive.today/20110706114957/http://web.science.mq.edu.au/~jydelort/figue/demo.html |archive-date=06. 07. 2011 |url-status=dead }}</ref>

=== Vizualizacija, animacija i primeri ===
* [[ELKI]] can visualize k-means using [[Voronoi diagram|Voronoi cells]] and [[Delaunay triangulation]] for 2D data. In higher dimensionality, only cluster assignments and cluster centers are visualized
* Demos of the K-means-algorithm<ref>[http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/AppletKM.html Clustering - K-means demo{{Ботовски наслов}}]</ref><ref>[http://siebn.de/other/yakmeans/ siebn.de - YAK-Means{{Ботовски наслов}}]</ref><ref>[http://informationandvisualization.de/blog/kmeans-and-voronoi-tesselation-built-processing k-Means and Voronoi Tesselation: Built with Processing | Information & Visualization{{Ботовски наслов}}]</ref><ref>[{{Cite web |url=http://www.javaworld.com/javaworld/jw-11-2006/jw-1121-thread.html |title=Hyper-threaded Java - JavaWorld{{Ботовски наслов}} |access-date=01. 06. 2013 |archive-date=02. 06. 2013 |archive-url=https://web.archive.org/web/20130602180344/http://www.javaworld.com/javaworld/jw-11-2006/jw-1121-thread.html |url-status=dead }} Hyper-threaded Java - JavaWorld{{Ботовски наслов}}]</ref><ref>[http://www.leet.it/home/lale/clustering/ Color clustering{{Ботовски наслов}}]</ref>
* K-means and K-medoids (Applet), [[University of Leicester]]<ref name = "Mirkes2011">E.M. Mirkes, [http://www.math.le.ac.uk/people/ag153/homepage/KmeansKmedoids/Kmeans_Kmedoids.html K-means and K-medoids applet] {{Wayback|url=http://www.math.le.ac.uk/people/ag153/homepage/KmeansKmedoids/Kmeans_Kmedoids.html |date=20130529193511 }}. University of Leicester, 2011.</ref>
* Clustergram - cluster diagnostic plot - for visual diagnostics of choosing the number of (k) clusters ([[R (програмски језик)|R]] code)<ref>[http://www.r-statistics.com/2010/06/clustergram-visualization-and-diagnostics-for-cluster-analysis-r-code/ Clustergram: visualization and diagnostics for cluster analysis (R code) | R-statistics blog{{Ботовски наслов}}]</ref>

== Reference ==
{{reflist|2}}

{{normativna kontrola}}

[[Категорија:Алгоритми кластеризације података]]
[[Категорија:Статистички алгоритми]]