Klasterizacija metodom K-srednjih vrednosti
-{T|sr:Klasterizacija metodom K-srednjih vrednosti;sr-ec:Кластеризација методом K-средњих вредности;sr-el:Klasterizacija metodom K-srednjih vrednosti}-
U analizi podataka, klasterizacija metodom k-srednjih vrednosti () 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 (k ≤ n) S = {S1, S2, …, Sk}, tako da minimizuje sumu kvadrata unutar klastera ().

Gde je μi glavna tačka u Si.

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 m1(1),…,mk(1) (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).

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

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 . 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(ndk+1 log n), gde je n broj celina koje treba grupisati 

Takođe, više heurističkih algoritma se generano koriste.
 -means je razmatran iznad glatkog polinomijalnog vremena. Pokazano je da  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, 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.
 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 

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

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)

Reference 

Алгоритми кластеризације података
Статистички алгоритми
-{ T|sr:Klasterizacija metodom K-srednjih vrednosti ; sr-ec:Кластеризација методом K-средњих вредности ; sr-el:Klasterizacija metodom K-srednjih vrednosti } - U analizi podataka , klasterizacija metodom k-srednjih vrednosti ( ) 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 ( k ≤ n ) S = { S1 , S2 , … , Sk } , tako da minimizuje sumu kvadrata unutar klastera ( ) . Gde je μi glavna tačka u Si . Istorija Izraz „ k-means ” je prvi upotrebio Džejms Makkvid godine , iako je prvi došao na ideju Gugo Štejngauz Standardni algoritam je prvi predstavio Stjuart Lojd kao tehniku za impulsivnu kodnu modulaciju , mada nije objavljena van Belovih laboratorija do E. V . Forgi je objavio esencialno isti metod , zbog čega ga nekad nazivaju i Lojd-Forgijev metod . Hartigan i Vong su predstavili efikasniju verziju i objavili je u Fortranu1979. 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đukoraka : 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 . 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 . 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 udimenzije , u kojima k-means ima eksponencijalno vreme izvršavanja \ . 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 zaklastera 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( ndk+1 log n ) , gde je n broj celina koje treba grupisati Takođe , više heurističkih algoritma se generano koriste . -means je razmatran iznad glatkog polinomijalnog vremena . Pokazano je da 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 , 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 . 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 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 razdvajanjevrste Irisa koje su u setu podataka . Sa k=2 , dva vidljiva klastera ( svaki sadrživrste ) će biti otkriveni , a kad je k=3 , jedan odklastera će biti podeljen na dva jednaka dela . Dakle , k=2 je prikladniji za set podataka , iako sadržiklase . 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šćuza 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 -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 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 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 ) Reference Алгоритми кластеризације података Статистички алгоритми