к-медоид

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 $l_{2}$. Ovaj metod je bio predložen 1987. za rad sa normom $l_{1}$ 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:

1. Inicijalizacija: nasumično izabrati k od n tačaka podataka kao medoide
2. 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)
3. Za svaki medoid m
   1. Za svaki ne-medoid tačke podataka o
      1. Zameni m i o i izračunaj ukupnu cenu konfiguracije
4. Izaberi konfiguraciju najniže cene
5. ponavljaj korake 2 i 4 sve dok nema promena na medoidu

Demonstracija PAM-a

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:

Slika 1.1 – distribucija podataka

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

Slika 1.2 – klasteri nakon prvog koraka

Inicijalizuj k centara.

Pretpostavimo da je c₁ = (3,4) i c₂ = (7,4)

Tako da su c₁ i c₂ 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:

Cluster₁ = {(3,4)(2,6)(3,8)(4,7)}

Cluster₂ = {(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 c₁ 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

${\mbox{cost}}(x,c)=\sum _{i=1}^{d}|x_{i}-c_{i}|$

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:

${\begin{aligned}{\mbox{total cost}}&=\{{\mbox{cost}}((3,4),(2,6))+{\mbox{cost}}((3,4),(3,8))+{\mbox{cost}}((3,4),(4,7))\}\\&~+\{{\mbox{cost}}((7,4),(6,2))+{\mbox{cost}}((7,4),(6,4))+{\mbox{cost}}((7,4),(7,3))\\&~+{\mbox{cost}}((7,4),(8,5))+{\mbox{cost}}((7,4),(7,6))\}\\&=(3+4+4)+(3+1+1+2+2)\\&=20\\\end{aligned}}$

Korak 2

Slika 1.3 – klasteri nakon drugog koraka

Izaberi jedan od ne-medoida O'

Pretpostavimo da je O' = (7,3)

Tako da su sada medoidi c₁(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

Slika 2. K-medoidi nasuprot k-sredina. slike 2.1a-2.1f predstavljaju tipične primere konvergencije k-sredina ka lokalnom minimumu. Ovaj rezultat klasterizovanja k-sredinama predstavlja kontradikciju očiglednoj strukturi klastera skupa podataka. U ovom primeru, algoritam k-medoida (slike 2.2a-2.2h) sa istim početnim položajem medoida (slika 2.2a) konvergira očiglednoj strukturi klastera. Mali krugovi su podaci, četiri zračne zvezde su centroidi (sredine), devet zračnih zvezda su medoidi.

${\begin{aligned}{\mbox{total cost}}&=3+4+4+2+2+1+3+3\\&=22\\\end{aligned}}$

Dakle, cena menjanja medoida iz c₂ u O' iznosi

${\begin{aligned}S&={\mbox{current total cost}}-{\mbox{past total cost}}\\&=22-20\\&=2>0.\end{aligned}}$

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, 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 Pokazano je da za asimptotiku većeg skupa podataka k-medoid algoritma potrebno manje vremena.

Softver

• ELKI
• GNU R

Vidi još

• Klasterska analiza
• k-means
• K-medijanska klasterizacija
• Medoid

Spoljašnje veze

• E.M. Mirkes, K-means and K-medoids (Applet), University of Leicester, 2011.