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 (x₁, x₂, …, x_n), gde je svaka opservacija d-dimenzionalan realan vektor. Cilj ovog metoda je da praticioniše n opservacija u k skupova (k ≤ n) S = {S₁, S₂, …, S_k}, tako da minimizuje sumu kvadrata unutar klastera (engl. 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 S_i.

Istorija

Izraz „k-means” je prvi upotrebio Džejms Makkvid 1967. godine, iako je prvi došao na ideju Gugo Štejngauz 1957. Standardni algoritam je prvi predstavio Stjuart Lojd 1957. kao tehniku za impulsivnu kodnu modulaciju, mada nije objavljena van Belovih laboratorija do 1982. E. V. Forgi je 1956. objavio esencialno isti metod, zbog čega ga nekad nazivaju i Lojd-Forgijev metod. Hartigan i Vong su predstavili efikasniju verziju i objavili je u Fortranu 1975/1979.

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₁⁽¹⁾,…,m_k⁽¹⁾ (pogledati ispod), algoritam radi tako što alternira između 2 koraka:

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).

$S_{i}^{(t)}={\big \{}x_{p}:{\big \|}x_{p}-m_{i}^{(t)}{\big \|}\leq {\big \|}x_{p}-m_{j}^{(t)}{\big \|}\ \forall \ 1\leq j\leq 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 opservacije u klasteru.

$\mathbf {m} _{i}^{(t+1)}={\frac {1}{|S_{i}^{(t)}|}}\sum _{\mathbf {x} _{j}\in S_{i}^{(t)}}\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. 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., 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.

• Demonstracija standardnog algoritma
• 
  1) k initial "means" (in this case k=3) are randomly generated within the data domain (shown in color).
• 
  2) k clusters are created by associating every observation with the nearest mean. The partitions here represent the Voronoi diagram generated by the means.
• 
  3) The centroid of each of the k clusters becomes the new mean.
• 
  4) Steps 2 and 3 are repeated until convergence has been reached.

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

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
• NP-težak za uopšten broj klastera k
• Ako su k i d (dimenzija) popravljene, problem može biti precizno rešen u vremenu O(n^dk+1 log n), gde je n broj celina koje treba grupisati

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

• $k$-means je razmatran iznad glatkog polinomijalnog vremena. Pokazano je da 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, pokazano je da vreme izvršavanja $k$-means algoritam ograničeno na $O(dn^{4}M^{2})$ za $n$ tačka u mreži intedžera $\{1,\dots ,M\}^{d}$.

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.
• Neke metode nameravaju da ubrzaju svaki k-menas korak korišćenjem korseta ili nejednakosti trougla.
• zbegavanje lokalnog optimuma zamenjujući tačke između klastera.
• Spherical k-means clustering algoritam je primeren za usmerene podarke.
• Minkowski metric weighted k-means se suočava sa problemom buke

Diskusija

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

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 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. 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 ili neka glatka transformacija za daleke transfomrišući uzorak klastera kroz Gausov RBF, on sadrži sakrivene slojeve radijalne osnovne mreže funkcije.

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..

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. 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 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.), 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. 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 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
• MLPACK contains a K-Means implementation
• R kmeans implements a variety of algorithms
• SciPy vector-quantization
• Silverlight widget demonstrating k-means algorithm
• PostgreSQL extension for k-means
• Weka contains k-means and a few variants of it, including k-means++ and x-means.
• Spectral Python contains methods for unsupervised classification including a K-means clustering method.
• scikit learn machine learning in Python contains a K-Means implementation
• OpenCV contains a K-means implementation under BSD licence.

Komercijalni

• IDL Cluster, Clust_Wts
• Mathematica ClusteringComponents function
• MATLAB kmeans
• SAS FASTCLUS
• VisuMap kMeans Clustering Архивирано на сајту Wayback Machine (1. фебруар 2013)

Izvorni kod

• ELKI i Weka su napisani u Javi i uključuju k-srednje vrednosti i varijacije
• primena K-srednjih vrednosti u PHP-u, korišćenje VB, korišćenje Perl, korišćenje C++, korišćenje Matlab, korišćenje Ruby, korišćenje Python with scipy, using X10
• paralelna out-of-core implementacija u C-u
• kolekcija otvorenog koda klastering algoritama, uključujući k-srednje vrednosti, implentirano u Javaskriptu Online demo.

Vizualizacija, animacija i primeri

• ELKI can visualize k-means using 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
• K-means and K-medoids (Applet), University of Leicester
• Clustergram - cluster diagnostic plot - for visual diagnostics of choosing the number of (k) clusters (R code)