Klasterizacija metodom K-srednjih vrednosti

U analizi podataka, klasterizacija metodom k-srednjih vrednosti (engl. k-means clustering) metod je za 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 ć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 (x1, x2, …, xn), gde je svaka opservacija d-dimenzionalan realan vektor. Cilj ovog metoda je da praticioniše n opservacija u k skupova (kn) S = {S1, S2, …, Sk}, tako da minimizuje sumu kvadrata unutar klastera (engl. within-cluster sum of squares - WCSS).

Gde je μi glavna tačka u Si.

Istorija

Izraz „k-means” je prvi upotrebio Džejms Makkvid 1967. godine,[1] iako je prvi došao na ideju Gugo Štejngauz 1957.[2] Standardni algoritam je prvi predstavio Stjuart Lojd 1957. kao tehniku za impulsivnu kodnu modulaciju, mada nije objavljena van Belovih laboratorija do 1982.[3] E. V. Forgi je 1956. objavio esencialno isti metod, zbog čega ga nekad nazivaju i Lojd-Forgijev metod.[4] Hartigan i Vong 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 (opservacije se particionišu prema Voronoi dijagaramu generisanom po značenju).
gde je svaki dodeljen tačno jednom , a čak ako može, dodeljen je dvoma ili više.
Korak ažuriranja: Izračunava novo značenje koje treba postati centar nove opservacije u klasteru.

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 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.,[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 observacija 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 koriste.

  • -means je razmatran iznad glatkog polinomijalnog vremena. Pokazano je da[10] je za proizvoljan set od tačaka , ako je svaka tačka nezavisno pomerena od strane normalne raspodele sa značenjem i neslaganjem , onda je očekivano vreme izvršavanja -means algoritma ograničeno na , što je polinomijalno u , , i .
  • Bolje ogrnaičenje je dokazano za jednostavne slučajeve. Na primer,[15] pokazano je da vreme izvršavanja -means algoritam ograničeno na za tačka u mreži intedžera .

Varijacije

  • 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-menas++.
  • Algortam prečišćavanja koristi K-D stablo da bi ubrzao svaki k-menas korak.[16]
  • Neke metode nameravaju da ubrzaju svaki k-menas korak korišćenjem korseta[17] ili nejednakosti trougla.[18]
  • zbegavanje lokalnog optimuma zamenjujući tačke između klastera.[6]
  • 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 radijalne osnovne mreže funkcije.[25]

Ova upotreba k-menas aa je uspešno kombinovana sa jednistavnim, 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

Izvorni kod

  • ELKI i Weka su napisani u Javi i uključuju k-srednje vrednosti i varijacije
  • primena K-srednjih vrednosti u PHP-u,[31] korišćenje VB,[32] korišćenje Perl,[33] korišćenje C++,[34] korišćenje Matlab,[35] korišćenje Ruby,[36][37] korišćenje Python with scipy,[38] using X10[39]
  • paralelna out-of-core implementacija u C-u[40]
  • kolekcija otvorenog koda klastering algoritama, uključujući k-srednje vrednosti, implentirano u Javaskriptu[41] Online demo.[42]

Vizualizacija, animacija i primeri

Reference

  1. ^ а б MacQueen, J. B. (1967). Some Methods for classification and Analysis of Multivariate Observations. Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. 1. University of California Press. str. 281—297. MR 0214227. Zbl 0214.46201. Pristupljeno 7. 4. 2009. 
  2. ^ Steinhaus, H. (1957). „Sur la division des corps matériels en parties”. 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” (PDF). IEEE Transactions on Information Theory. 28 (2): 129—137. doi:10.1109/TIT.1982.1056489. Pristupljeno 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” (PDF). Information Theory, Inference and Learning Algorithms. Cambridge University Press. str. 284—292. ISBN 978-0-521-64298-9. MR 2012999. 
  8. ^ а б Hamerly, G. & Elkan, C. (2002). „Alternatives to the k-means algorithm that find better clusterings” (PDF). Proceedings of the eleventh international conference on Information and knowledge management (CIKM). Arhivirano iz originala (PDF) 7. 11. 2006. g. 
  9. ^ Vattani., A. (2011). „k-means requires exponentially many iterations even in the plane” (PDF). 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. & Freund, Y. (2009). „Random Projection Trees for Vector Quantization”. Information Theory, IEEE Transactions on. 55: 3229—3242. arXiv:0805.1390Slobodan pristup. 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. str. 332—339. doi:10.1145/177424.178042. 
  15. ^ Arthur Abhishek Bhowmick (2009). A theoretical analysis of Lloyd's algorithm for k-means clustering (Теза). 
  16. ^ Kanungo, T.; et al. (2002). „An efficient k-means clustering algorithm: Analysis and implementation” (PDF). IEEE Trans. Pattern Analysis and Machine Intelligence. 24: 881—892. doi:10.1109/TPAMI.2002.1017616. Pristupljeno 24. 4. 2009. 
  17. ^ Frahling, G.; Sohler, C. (2006). „A fast k-means implementation using coresets” (PDF). Proceedings of the twenty-second annual symposium on Computational geometry (SoCG). Arhivirano iz originala (PDF) 5. 7. 2010. g. 
  18. ^ Elkan, C. (2003). „Using the triangle inequality to accelerate k-means” (PDF). 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 Архивирано на сајту Wayback Machine (29. мај 2013). University of Leicester, 2011.
  22. ^ Honarkhah, Mehrdad; Caers, Jef (2010). „Stochastic Simulation of Patterns Using Distance-Based Pattern Modeling”. Mathematical Geosciences. 42 (5): 487—517. Bibcode:2010MaGeo..42..487H. S2CID 73657847. doi:10.1007/s11004-010-9276-7. 
  23. ^ Coates, Adam; Ng, Andrew Y. (2012). „Learning feature representations with k-means” (PDF). Ур.: G. Montavon, G. B.; et al. Neural Networks: Tricks of the Trade. Springer. Архивирано из оригинала (PDF) 6. 6. 2013. г. 
  24. ^ Csurka, Gabriella; Dance, Christopher C.; Fan, Lixin; Willamowski, Jutta; Bray, Cédric (2004). Visual categorization with bags of keypoints (PDF). 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 izd.). 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” (PDF). Proc. Roy. Soc. A. 
  28. ^ H. Zha; et al. (2001). „Spectral Relaxation for K-means Clustering” (PDF). Neural Information Processing Systems vol.14 (NIPS 2001). Vancouver, Canada: 1057—1064. 
  29. ^ Ding, Chris; Xiaofeng He (2004). „K-means Clustering via Principal Component Analysis” (PDF). Proc. of Int'l Conf. Machine Learning (ICML 2004): 225—232. 
  30. ^ Drineas, P.; A. Frieze; et al. (2004). „Clustering large graphs via the singular value decomposition” (PDF). Machine learning. 56: 9—33. Pristupljeno 2. 8. 2012. 
  31. ^ „Архивирана копија”. Архивирано из оригинала 23. 10. 2007. г. Приступљено 23. 10. 2007. 
  32. ^ K-Means Clustering Tutorial: Download
  33. ^ „Perl script for Kmeans clustering[[Категорија:Ботовски наслови]]”. Архивирано из оригинала 18. 06. 2012. г. Приступљено 01. 06. 2013.  Сукоб URL—викивеза (помоћ)
  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[[Категорија:Ботовски наслови]]”. GitHub. Архивирано из оригинала 08. 07. 2012. г. Приступљено 08. 07. 2012.  Сукоб URL—викивеза (помоћ)
  38. ^ K-means clustering and vector quantization (scipy.cluster.vq) — SciPy v0.11 Reference Guide (DRAFT)
  39. ^ „Архивирана копија”. Архивирано из оригинала 09. 07. 2012. г. Приступљено 09. 07. 2012. 
  40. ^ https://web.archive.org/web/20110607074701/http://www.cs.princeton.edu/~wdong/kmeans/
  41. ^ http://code.google.com/p/figue/ FIGUE
  42. ^ „Interactive Demo of figue[[Категорија:Ботовски наслови]]”. Архивирано из оригинала 06. 07. 2011. г. Приступљено 06. 07. 2011.  Сукоб URL—викивеза (помоћ)
  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[[Категорија:Ботовски наслови]]”. Архивирано из оригинала 02. 06. 2013. г. Приступљено 01. 06. 2013.  Сукоб URL—викивеза (помоћ) Hyper-threaded Java - JavaWorld]
  47. ^ Color clustering
  48. ^ Clustergram: visualization and diagnostics for cluster analysis (R code) | R-statistics blog