K-medoizi

K-medoizii este un algoritm de grupare de partiții legat de algoritmul K-means . Oferă ca intrare un set de $n$ ${\ displaystyle n}$ $n$ obiecte și un număr $k$ ${\ displaystyle k}$ $k$ care determină câte clustere doriți să scoateți.

Ambii algoritmi se partiționează (împărțind setul de date în grupuri) și ambii încearcă să minimizeze eroarea pătrată medie a rădăcinii , distanța dintre punctele dintr-un cluster și punctul desemnat a fi centrul. În K-înseamnă punctul este „artificial”, de fapt este centrul de greutate al tuturor punctelor din cluster. În medoidele K, punctul este utilizat, printre cele date, situat „mai central”, în acest fel centrul este una dintre datele observate. K-medoizii sunt mai robusti la zgomot și valori aberante decât K-înseamnă .

Un medoid poate fi definit ca un element al unui cluster a cărui diferență medie față de toate obiectele din cluster este minimă, deci va fi punctul cel mai central al unui set dat de puncte.

Algoritm

Algoritmul de grupare este după cum urmează:

începe cu o selecție arbitrară de $k$ ${\ displaystyle k}$ $k$ obiecte precum punctele medoide dintr-un set de $n$ ${\ displaystyle n}$ $n$ puncte de date (cu $n>k$ ${\ displaystyle n> k}$ ${\ displaystyle n> k}$ );
fiecare element din date este asociat împreună cu cel mai similar medoid, unde similitudinea este dată de funcția de cost care este definită folosind distanțe precum distanța euclidiană , distanța Manhattan sau distanța Minkowski ;
un element non-medoid este selectat aleatoriu ${SAU}^{'};$ ${\ displaystyle O ';}$ ${\ displaystyle O ';}$
se calculează costul total $S_{i},$ ${\ displaystyle S_ {i},}$ ${\ displaystyle S_ {i},}$ care este suma costurilor elementelor individuale din medoidul corespunzător, în cazul medoidului inițial și costul total $S_{f}$ ${\ displaystyle S_ {f}}$ $S_ {f}$ în cazul medoidului ${SAU}^{'}$ ${\ displaystyle O '}$ ${\ displaystyle O '}$ iar diferența este calculată $S=S_{f}-S_{i};$ ${\ displaystyle S = S_ {f} -S_ {i};}$ ${\ displaystyle S = S_ {f} -S_ {i};}$
de sine $S<0,$ ${\ displaystyle S <0,}$ ${\ displaystyle S <0,}$ atunci medoidul inițial este schimbat cu cel nou (dacă $S<0,$ ${\ displaystyle S <0,}$ ${\ displaystyle S <0,}$ atunci va exista un nou set de medoid);
etapele de la 2 la 5 se repetă până când apar modificări în ansamblul medoid.

Exemplu

Apoi, trebuie să grupați următorul set de date de 10 obiecte în 2 clustere $n=10$ ${\ displaystyle n = 10}$ ${\ displaystyle n = 10}$ Și $k=2:$ ${\ displaystyle k = 2:}$ ${\ displaystyle k = 2:}$

Distribuirea datelor

Obiecte (Xi)	Coordonata X	Coordonata Y
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

Pasul 1

Initializez $k$ ${\ displaystyle k}$ $k$ centre. Să presupunem că $C_{1}=(3,4)$ ${\ displaystyle C_ {1} = (3,4)}$ ${\ displaystyle C_ {1} = (3,4)}$ Și $C_{2}=(7,4)$ ${\ displaystyle C_ {2} = (7,4)}$ ${\ displaystyle C_ {2} = (7,4)}$ sunt medoizii noștri inițiali.

Calculăm distanța astfel încât să asociem fiecare element cu medoidul său cel mai apropiat.

Deci, să începem gruparea:

Clusterul 1 = $\{(3,4)(2,6)(3,8)(4,7)\};$ ${\ displaystyle \ {(3,4) (2,6) (3,8) (4,7) \};}$ ${\ displaystyle \ {(3,4) (2,6) (3,8) (4,7) \};}$
Clusterul 2 = $\{(7,4)(6,2)(6,4)(7,3)(8,5)(7,6)\}.$ ${\ displaystyle \ {(7.4) (6.2) (6.4) (7.3) (8.5) (7.6) \}.}$ ${\ displaystyle \ {(7.4) (6.2) (6.4) (7.3) (8.5) (7.6) \}.}$

Fiind $(3,4),(2,6),(3,8)$ ${\ displaystyle (3,4), (2,6), (3,8)}$ ${\ displaystyle (3,4), (2,6), (3,8)}$ Și $(4,7)$ ${\ displaystyle (4,7)}$ ${\ displaystyle (4,7)}$ puncte apropiate de $C_{1}$ ${\ displaystyle C_ {1}}$ $C_ {1}$ vor forma un cluster, în timp ce punctele rămase vor forma altul.

Costul total va fi de 20.

Costul dintre oricare două puncte se găsește folosind distanța Manhattan care este exprimată prin următoarea formulă:

\mathrm {Cost} (x,c)=\sum _{i=1}^{d}|x_{i}-c_{i}|,

{\ displaystyle \ mathrm {Cost} (x, c) = \ sum _ {i = 1} ^ {d} | x_ {i} -c_ {i} |,}

{\ displaystyle \ mathrm {Cost} (x, c) = \ sum _ {i = 1} ^ {d} | x_ {i} -c_ {i} |,}

unde este $x=(x_{1},\ldots ,x_{d})$ ${\ displaystyle x = (x_ {1}, \ ldots, x_ {d})}$ ${\ displaystyle x = (x_ {1}, \ ldots, x_ {d})}$ este orice element, $c=(c_{1},\ldots ,c_{d})$ ${\ displaystyle c = (c_ {1}, \ ldots, c_ {d})}$ ${\ displaystyle c = (c_ {1}, \ ldots, c_ {d})}$ este medoidul și $d$ ${\ displaystyle d}$ $d$ este dimensiunea spațiului elementelor, în acest caz $d=2.$ ${\ displaystyle d = 2.}$ ${\ displaystyle d = 2.}$

Costul total este suma costurilor pentru articolele din medoidul dvs.:

{\text{Costo totale}}={\mathrm {Cost} ((3,4),(2,6))+\mathrm {Cost} ((3,4),(3,8))+\mathrm {Cost} ((3,4),(4,7))}+{\mathrm {Cost} ((7,4),(6,2))+\mathrm {Cost} ((7,4),(6,4))+\mathrm {Cost} ((7,4),(7,3))+\mathrm {Cost} ((7,4),(8,5))+\mathrm {Cost} ((7,4),(7,6))}=3+4+4+3+1+1+2+2=20.

{\ displaystyle {\ text {Cost total}} = {\ mathrm {Cost} ((3,4), (2,6)) + \ mathrm {Cost} ((3,4), (3,8)) + \ mathrm {Cost} ((3,4), (4,7))} + {\ mathrm {Cost} ((7,4), (6,2)) + \ mathrm {Cost} ((7, 4), (6,4)) + \ mathrm {Cost} ((7,4), (7,3)) + \ mathrm {Cost} ((7,4), (8,5)) + \ mathrm {Cost} ((7,4), (7,6))} = 3 + 4 + 4 + 3 + 1 + 1 + 2 + 2 = 20.}

{\ displaystyle {\ text {Cost total}} = {\ mathrm {Cost} ((3,4), (2,6)) + \ mathrm {Cost} ((3,4), (3,8)) + \ mathrm {Cost} ((3,4), (4,7))} + {\ mathrm {Cost} ((7,4), (6,2)) + \ mathrm {Cost} ((7, 4), (6,4)) + \ mathrm {Cost} ((7,4), (7,3)) + \ mathrm {Cost} ((7,4), (8,5)) + \ mathrm {Cost} ((7,4), (7,6))} = 3 + 4 + 4 + 3 + 1 + 1 + 2 + 2 = 20.}

Cluster după primul pas

Pasul 2

Selectarea unui nonmedoid ${SAU}^{'}$ ${\ displaystyle O '}$ ${\ displaystyle O '}$ la întâmplare. Presupunem $O'=(7,3).$ ${\ displaystyle O '= (7,3).}$ ${\ displaystyle O '= (7,3).}$

Prin urmare, medoizii sunt $C_{1}(3,4)$ ${\ displaystyle C_ {1} (3,4)}$ ${\ displaystyle C_ {1} (3,4)}$ Și $O'(7,3).$ ${\ displaystyle O '(7,3).}$ ${\ displaystyle O '(7,3).}$ De sine $C_{1}$ ${\ displaystyle C_ {1}}$ $C_ {1}$ Și ${SAU}^{'}$ ${\ displaystyle O '}$ ${\ displaystyle O '}$ sunt medoizi noi, costul total este recalculat folosind formula din pasul 1.

Cluster după pasul 2

{\text{Costo totale}}=3+4+4+2+2+1+3+3=22.

{\ displaystyle {\ text {Cost total}} = 3 + 4 + 4 + 2 + 2 + 1 + 3 + 3 = 22.}

{\ displaystyle {\ text {Cost total}} = 3 + 4 + 4 + 2 + 2 + 1 + 3 + 3 = 22.}

Astfel, costul schimbării medoidului din $C_{2}$ ${\ displaystyle C_ {2}}$ $C_ {2}$ la ${SAU}^{'}$ ${\ displaystyle O '}$ ${\ displaystyle O '}$ Și:

$S={\text{Costo totale attuale}}-{\text{Costo totale precedente}}=22-20=2>0.$ ${\ displaystyle S = {\ text {Cost total actual}} - {\ text {Cost total anterior}} = 22-20 = 2> 0.}$ ${\ displaystyle S = {\ text {Cost total actual}} - {\ text {Cost total anterior}} = 22-20 = 2> 0.}$

Apoi schimbați medoidul în ${SAU}^{'}$ ${\ displaystyle O '}$ ${\ displaystyle O '}$ nu este o idee bună, alegerea anterioară a fost bună și algoritmul se încheie în acest moment (deoarece nu există modificări pentru medoizi).

Se poate întâmpla ca unele puncte de date să migreze de la un cluster la altul, acest lucru depinde de apropierea de noul medoid ales.

Portal IT : accesați intrările Wikipedia care se ocupă cu IT