Klasterizacija metodom K-srednjih vrednosti

Из Википедије, слободне енциклопедије

U analizi podataka, klasterizacija metodom k-srednjih vrednosti (engl. k-means clustering) je metod za analizu grupisanja čiji je cilj particionisanje n observacija u k klastera u kojem svaka observacija pripada klasteru sa najsličnijim značenjem. Ovo rezultuje particionisanju prostora za podatke u Voronoi ćelije.

Ovaj problem je računarski težak (NP-težak), ipak postoje efiaksni heuristički algoritmi koji se često primenjuju and brzo konvergiraju ka lokalnom optimumu. Oni su često slični algoritmu očekivane minimizacije za mix Gausove raspodele putem iterativnog pristupa prečišćavanja zastupljenog kod oba algoritma. Pored toga, oba koriste cetre klastera (grupa) da bi oblikovali podatak, ipak, k-menas clustering 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 set observacija (x1, x2, …, xn), gde je svaka observaicja d-dimenzionalan realan vektor, k-means clustering cilja da praticionipe n observacija u k setova (kn) S = {S1S2, …, Sk}, tako da minimizuje sumu kvadrata unutar klastera (within-cluster sum of squares - WCSS).

\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

Gde je μi glavna tačka u Si.

Istorija[уреди]

Izraz "k-means" je prvi upotrebio James MacQueed 1967. godine, [1] iako je prvi došao na ideju Hugo Steinhaus 1957.[2] Standardni algoritam je prvi predstavio Stuar Lloyd 1957. kao tehniku za impulsivnu kodnu modulaciju, mada nije objavljena van Belovih laboratorija do 1982. [3] E.W.Forgy je 1956. objavio esencialno isti metod, zbog čega ga nekad nazivaju i Lloyd-Forgy.[4] Hartigan and Wong su predstavili efikasniju verziju i objavili je u Fortranu 1975/1979.[5][6]

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 m1(1),…,mk(1) (pogledati ispod), algoritam radi tako što alternira između 2 koraka:[7]

Korak dodele: Svakom klasteru se dodeljuje observaija čiji je značenje njemu najbliže (observacije se particionišu prema Voronoi dijagaramu generisanom po značenju).
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\},
gde je svaki x_p dodeljen tačno jednom S^{(t)}, a čak ako može, dodeljen je dvoma ili više.
Korak ažuriranja: Izračunava novo značenje koje treba postati centar nove observacije u klasteru.
\mathbf m^{(t+1)}_i = \frac{1}{|S^{(t)}_i|} \sum_{\mathbf x_j \in S^{(t)}_i} \mathbf x_j

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.[8] Forgy metoda nasumično bira k observacija iz seta podataka i koristi ih kao inicijalna značenja. Random Partition prvo nasumično dodeljuje klastere observacijama, 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.,[8] 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.

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 2Ω(n).[9] Ovaj set tačaka se uglavnom ne pojavljuje u praksi, što je potkrepljeno činjenicom da je glatko vreme izvršava k-menas algoritma polinomijalno.[10]

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 observaicja u d dimenzijama je:

  • NP-težak u Euklidovom prostoru d, čak i za 2 klastera [11][12]
  • NP-težak za uopšten broj klastera k [13]
  • Ako su k i d (dimenzija) popravljene, problem može biti precizno rešen u vremenu O(ndk+1 log n), gde je n broj celina koje treba grupisati [14]

Takođe, više heurističkih algoritma se generano koritse.

  • k-means je razmatran iznad glatkog polinomijalnog vremena. Pokazano je da [10] je za proizvoljan set od n tačaka [0,1]^d, ako je svaka tačka nezavisno pomerena od strane normalne raspodele sa značenjem 0 i neslaganjem \sigma^2, onda je očekivano vreme izvršavanja k-means algoritma ograničeno na O(n^{34}k^{34}d^8 log^4(n)/ \sigma^6 ), što je polinomijalno u n, k, d i 1/\sigma.
  • Bolje ogrnaičenje je dokazano za jednostavne slučajeve. Na primer,[15] pokazano je da vreme izvršavanja k-means algoritam ograničeno na O(dn^4M^2) za n tačka u mreži intedžera \{1,\dots, M\}^d.

Varijacije[уреди]

  • Spherical k-means clustering algoritam je primeren za usmerene podarke.[19]
  • Minkowski metric weighted k-means se suočava sa problemom buke [20]

Diskusija[уреди]

Tipičan primer konevrgencije k-means algoritma ka lokalnom minimumu. [21]

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[22] 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.[23] 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[24] 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].[25]

Ova upotreba k-menas aa je uspešno kombinovana sa jednistavnim, [[linearni klasifikator|linearnim klasifikatorom] za semi-nedgledanoučenje u 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..[26]

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.[27] 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 [28][29] da je 'opušteno' rešenje k-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.[30]), 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.[27] 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[уреди]

Komercijalni[уреди]

Source code[уреди]

  • ELKI and Weka are written in Java and include k-means and variations
  • K-means application in PHP,[31] using VB,[32] using Perl,[33] using C++,[34] using Matlab,[35] using Ruby,[36][37] using Python with scipy,[38] using X10[39]
  • A parallel out-of-core implementation in C[40]
  • An open-source collection of clustering algorithms, including k-means, implemented in Javascript.[41] Online demo.[42]

Vizualizacija, animacija i primeri[уреди]

Reference[уреди]

  1. ^ а б MacQueen, J. B. (1967). „Some Methods for classification and Analysis of Multivariate Observations“. 1. Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. University of California Press. pp. 281-297. MR 0214227. Zbl 0214.46201 Приступљено 7. 4. 2009.. 
  2. ^ Steinhaus, H. (1957). „Sur la division des corps matériels en parties“ (на French). Bull. Acad. Polon. Sci. 4 (12): 801-804. MR 0090073. Zbl 0079.16403. 
  3. ^ а б Lloyd, S. P. (1957). „Least square quantization in PCM“. Bell Telephone Laboratories Paper.  Published in journal much later: Lloyd., S. P. (1982). „Least squares quantization in PCM“. IEEE Transactions on Information Theory 28 (2): 129-137. DOI:10.1109/TIT.1982.1056489 Приступљено 15. 4. 2009.. 
  4. ^ E.W. Forgy (1965). „Cluster analysis of multivariate data: efficiency versus interpretability of classifications“. Biometrics 21: 768–769. 
  5. ^ J.A. Hartigan (1975). Clustering algorithms. John Wiley & Sons, Inc.. 
  6. ^ а б в Hartigan, J. A.; Wong, M. A. (1979). „Algorithm AS 136: A K-Means Clustering Algorithm“. Journal of the Royal Statistical Society, Series C 28 (1): 100-108. JSTOR 2346830. 
  7. ^ MacKay, David (2003). „Chapter 20. An Example Inference Task: Clustering“. Information Theory, Inference and Learning Algorithms. Cambridge University Press. стр. 284-292. ISBN 0-521-64298-1. MR 2012999. 
  8. ^ а б Hamerly, G. and Elkan, C. (2002). „Alternatives to the k-means algorithm that find better clusterings“. Proceedings of the eleventh international conference on Information and knowledge management (CIKM). 
  9. ^ Vattani., A. (2011). „k-means requires exponentially many iterations even in the plane“. Discrete and Computational Geometry 45 (4): 596-616. DOI:10.1007/s00454-011-9340-1. 
  10. ^ а б Arthur, D.; Manthey, B.; Roeglin, H. (2009). „k-means has polynomial smoothed complexity“. Proceedings of the 50th Symposium on Foundations of Computer Science (FOCS). 
  11. ^ Aloise, D.; Deshpande, A.; Hansen, P.; Popat, P. (2009). „NP-hardness of Euclidean sum-of-squares clustering“. Machine Learning 75: 245-249. DOI:10.1007/s10994-009-5103-0. 
  12. ^ Dasgupta, S. and Freund, Y. (July 2009). „Random Projection Trees for Vector Quantization“. Information Theory, IEEE Transactions on 55: 3229-3242. arXiv:0805.1390. DOI:10.1109/TIT.2009.2021326. 
  13. ^ Mahajan, M.; Nimbhorkar, P.; Varadarajan, K. (2009). „The Planar k-Means Problem is NP-Hard“. Lecture Notes in Computer Science 5431: 274-285. DOI:10.1007/978-3-642-00202-1_24. 
  14. ^ Inaba, M.; Katoh, N.; Imai, H. (1994). „Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering“. Proceedings of 10th ACM Symposium on Computational Geometry. pp. 332-339. DOI:10.1145/177424.178042. 
  15. ^ Шаблон:Cite dissertation
  16. ^ Kanungo, T.; Mount, D. M.; Netanyahu, N. S.; Piatko, C. D.; Silverman, R.; Wu, A. Y. (2002). „An efficient k-means clustering algorithm: Analysis and implementation“. IEEE Trans. Pattern Analysis and Machine Intelligence 24: 881-892. DOI:10.1109/TPAMI.2002.1017616 Приступљено 24. 4. 2009.. 
  17. ^ Frahling, G.; Sohler, C. (2006). „A fast k-means implementation using coresets“. Proceedings of the twenty-second annual symposium on Computational geometry (SoCG). 
  18. ^ Elkan, C. (2003). „Using the triangle inequality to accelerate k-means“. Proceedings of the Twentieth International Conference on Machine Learning (ICML). 
  19. ^ Dhillon, I. S.; Modha, D. M. (2001). „Concept decompositions for large sparse text data using clustering“. Machine Learning 42 (1): 143-175. 
  20. ^ Amorim, R. C.; Mirkin, B (2012). „Minkowski metric, feature weighting and anomalous cluster initializing in K-Means clustering“. Pattern Recognition 45 (3): 1061-1075. DOI:10.1016/j.patcog.2011.08.012. 
  21. ^ а б E.M. Mirkes, K-means and K-medoids applet. University of Leicester, 2011.
  22. ^ Honarkhah, M and Caers, J, 2010, Stochastic Simulation of Patterns Using Distance-Based Pattern Modeling, Mathematical Geosciences, 42: 487 - 517
  23. ^ Coates, Adam; Ng, Andrew Y. (2012). „Learning feature representations with k-means“. In G. Montavon, G. B. Orr, K.-R. Müller. Neural Networks: Tricks of the Trade. Springer. 
  24. ^ Csurka, Gabriella; Dance, Christopher C.; Fan, Lixin; Willamowski, Jutta; Bray, Cédric (2004). „Visual categorization with bags of keypoints“. ECCV Workshop on Statistical Learning in Computer Vision. 
  25. ^ Schwenker, Friedhelm; Kestler, Hans A.; Palm, Günther (2001). „Three learning phases for radial-basis-function networks“. Neural Networks 14: 439–458. 
  26. ^ Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). „Section 16.1. Gaussian Mixture Models and k-Means Clustering“. Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8. 
  27. ^ а б Little, M.A.; Jones, N.S. (2011). „Generalized Methods and Solvers for Piecewise Constant Signals: Part I“. Proc. Roy. Soc. A.. 
  28. ^ H. Zha, C. Ding, M. Gu, X. He and H.D. Simon (Dec. 2001). „Spectral Relaxation for K-means Clustering“. Neural Information Processing Systems vol.14 (NIPS 2001) (Vancouver, Canada): 1057–1064. 
  29. ^ Chris Ding and Xiaofeng He (July 2004). „K-means Clustering via Principal Component Analysis“. Proc. of Int'l Conf. Machine Learning (ICML 2004): 225–232. 
  30. ^ Drineas, P.; A. Frieze, R. Kannan, S. Vempala, V. Vinay (2004). „Clustering large graphs via the singular value decomposition“. Machine learning 56: 9–33 Приступљено 2. 8. 2012.. 
  31. ^ http://www25.brinkster.com/denshade/kmeans.php.htm
  32. ^ K-Means Clustering Tutorial: Download
  33. ^ Perl script for Kmeans clustering
  34. ^ Antonio Gulli's coding playground: K-means in C
  35. ^ K-Means Clustering Tutorial: Matlab Code
  36. ^ AI4R :: Artificial Intelligence for Ruby
  37. ^ reddavis/K-Means · GitHub
  38. ^ K-means clustering and vector quantization (scipy.cluster.vq) — SciPy v0.11 Reference Guide (DRAFT)
  39. ^ http://dist.codehaus.org/x10/applications/samples/KMeansDist.x10
  40. ^ http://www.cs.princeton.edu/~wdong/kmeans/
  41. ^ http://code.google.com/p/figue/ FIGUE
  42. ^ http://web.science.mq.edu.au/~jydelort/figue/demo.html
  43. ^ Clustering - K-means demo
  44. ^ siebn.de - YAK-Means
  45. ^ k-Means and Voronoi Tesselation: Built with Processing | Information & Visualization
  46. ^ Hyper-threaded Java - JavaWorld
  47. ^ Color clustering
  48. ^ Clustergram: visualization and diagnostics for cluster analysis (R code) | R-statistics blog

Literatura[уреди]