к-медоид
Algoritam 'k-medoida je algoritam grupisanja koji je povezan sa k-means algoritmom i „medoidšift algoritmom“. Oba i k-means and k-medoid algoritmi su partitivni (razdvaja skup podataka na grupe) i oba pokušavaju da umanje rastojanje između označenih tačaka u klasteru i tačke određene kao centar klastera. Nasuprot k-means algoritmu, k-medoid bira tačke podataka kao centre (medoidi ili primerci) i radi sa proizvoljnom matricom rastojanja između tačaka podataka umesto sa . Ovaj metod je bio predložen 1987. za rad sa normom i drugim distancama.
k-medoid je klasična partitivna tehnika grupisanja klastera skupa podataka n objekata u k klaster poznat kao priori. Koristan alat za određivanje k je siluet.
Medoid može biti definisan kao objekat klastera, čiji prosek različitosti za sve objekte u klasteru je minimalan, to je najviše centalno locirana tačka u klasteru.
Najuobičajenija realizacija grupisanja k-medoida je particionisanje oko medoida (PAM) algoritma kao što sledi:
- Inicijalizacija: nasumično izabrati k od n tačaka podataka kao medoide
- Vezati svaku tačku podataka sa najbližim medoidom (“najbliža” ovde je definisana koristeći bilo koje validno metričko rastojanje, najčešće Euklidovo rastojanje, Menhetn rastojanje ili Minkovski rastojanje)
- Za svaki medoid m
- Za svaki ne-medoid tačke podataka o
- Zameni m i o i izračunaj ukupnu cenu konfiguracije
- Za svaki ne-medoid tačke podataka o
- Izaberi konfiguraciju najniže cene
- ponavljaj korake 2 i 4 sve dok nema promena na medoidu
Demonstracija PAM-a[uredi | uredi izvor]
Grupisati sledeći skup tačaka podataka od deset objekata u dve grupe. k = 2.
Razmotriti ckup podataka od deset objekata na sledeći način:
X1 | 2 | 6 |
X2 | 3 | 4 |
X3 | 3 | 8 |
X4 | 4 | 7 |
X5 | 6 | 2 |
X6 | 6 | 4 |
X7 | 7 | 3 |
X8 | 7 | 4 |
X9 | 8 | 5 |
X10 | 7 | 6 |
Korak 1[uredi | uredi izvor]
Inicijalizuj k centara.
Pretpostavimo da je c1 = (3,4) i c2 = (7,4)
Tako da su c1 i c2 označeni kao medoidi.
Izračunati rastojanje tako da se udruži svaki skup objekata sa najbližim medoidom. Cena je izračunata koristeći Menhetn rastojanje (Minkovski rastojanje sa r = 1). Cena najbližeg medoida je pokazana boldovano u tabeli.
i | c1 | Objektni podaci (Xi) | Cena (rastojanje) | ||
1 | 3 | 4 | 2 | 6 | 3 |
3 | 3 | 4 | 3 | 8 | 4 |
4 | 3 | 4 | 4 | 7 | 4 |
5 | 3 | 4 | 6 | 2 | 5 |
6 | 3 | 4 | 6 | 4 | 3 |
7 | 3 | 4 | 7 | 3 | 5 |
9 | 3 | 4 | 8 | 5 | 6 |
10 | 3 | 4 | 7 | 6 | 6 |
i | c2 | Data objects (Xi) | Cost (distance) | ||
1 | 7 | 4 | 2 | 6 | 7 |
3 | 7 | 4 | 3 | 8 | 8 |
4 | 7 | 4 | 4 | 7 | 6 |
5 | 7 | 4 | 6 | 2 | 3 |
6 | 7 | 4 | 6 | 4 | 1 |
7 | 7 | 4 | 7 | 3 | 1 |
9 | 7 | 4 | 8 | 5 | 2 |
10 | 7 | 4 | 7 | 6 | 2 |
Tada grupe postaju:
Cluster1 = {(3,4)(2,6)(3,8)(4,7)}
Cluster2 = {(7,4)(6,2)(6,4)(7,3)(8,5)(7,6)}
Kako su tačke (2,6) (3,8) i (4,7) najbliže c1 dakle one formiraju jednu grupu dok ostale tačke formiraju drugu grupu.
Tako da je ukupna cena 20.
Gde je cena između bilo koje dve tačke tražena po formuli
gde je x bilo koji skup objekata, c je medoid, i d je dimenzija objekta, u ovom slučaju je 2.
Ukupna cena je suma cena skupa objekata iz svojih medoida i iz grupa:
Korak 2[uredi | uredi izvor]
Izaberi jedan od ne-medoida O'
Pretpostavimo da je O' = (7,3)
Tako da su sada medoidi c1(3,4) i O'(7,3)
Ako su c1 i O' novi medoidi, izračunati ukupnu cenu
Koristeći formulu iz koraka 1
i | c1 | Data objects (Xi) | Cost (distance) | ||
1 | 3 | 4 | 2 | 6 | 3 |
3 | 3 | 4 | 3 | 8 | 4 |
4 | 3 | 4 | 4 | 7 | 4 |
5 | 3 | 4 | 6 | 2 | 5 |
6 | 3 | 4 | 6 | 4 | 3 |
7 | 3 | 4 | 7 | 4 | 4 |
9 | 3 | 4 | 8 | 5 | 6 |
10 | 3 | 4 | 7 | 6 | 4 |
i | O' | Data objects (Xi) | Cost (distance) | ||
1 | 7 | 3 | 2 | 6 | 8 |
3 | 7 | 3 | 3 | 8 | 9 |
4 | 7 | 3 | 4 | 7 | 7 |
5 | 7 | 3 | 6 | 2 | 2 |
6 | 7 | 3 | 6 | 4 | 2 |
7 | 7 | 3 | 7 | 4 | 1 |
9 | 7 | 3 | 8 | 5 | 3 |
10 | 7 | 3 | 7 | 6 | 3 |
Dakle, cena menjanja medoida iz c2 u O' iznosi
Tako da bi pomeranje na O' bilo loša idea, što znači da je prethodni izbor bio dobar. Tako da mi probamo sa još ne-medoida i dođemo do zaključka da je prvi izbor bio najbolji. Tako da se konfiguracija ne menja i algoritam staje ovde. Može se desiti da neke tačke podataka se pomere iz jedne grupe u drugu u zavisnosti od njihovog najbližeg medoida.
U nekim standardima, k-medoidi pokazuju bolje rezultate od k-means algoritma. Primer je predstavljen na slici 2. U većini vremena k-medoid algoritam računa rastojanje između objekata. Ako je kvadratno preprocesiranje važi, rastojanje matrica može biti preračunato tako da dostigne dosledno ubrzanje. Videti za primer,[2] gde autori takođe heuristično rešenje za odabir inicijalnogk medoida. Uporedo proučavanje K-means and k-medoid algoritma je izvršena za normalnu i jedinstvenu distribuciju tačaka podataka[3] Pokazano je da za asimptotiku većeg skupa podataka k-medoid algoritma potrebno manje vremena.
Softver[uredi | uredi izvor]
Vidi još[uredi | uredi izvor]
Reference[uredi | uredi izvor]
- ^ Ilustracija pripremljena Java apletom, E.M. Mirkes, K-means and K-medoids: applet Архивирано на сајту Wayback Machine (29. мај 2013). University of Leicester, 2011.
- ^ H.S. Park , C.H. Jun, A simple and fast algorithm for K-medoids clustering, Expert Systems with Applications, 36, (2) (2009), 3336–3341.
- ^ T. Velmurugan and T. Santhanam, Computational Complexity between K-Means and K-Medoids Clustering Algorithms for Normal and Uniform Distributions of Data Points, Journal of Computer Science 6 (3) (2010), 363-368.
Spoljašnje veze[uredi | uredi izvor]
- E.M. Mirkes, K-means and K-medoids (Applet), University of Leicester, 2011.