k-medoids

k-medoids és un algoritme de agrupamiento (de l'anglés clustering) relacionat en els algoritmes k-means i medoidshift.

Tant el k-medoids com el k-means són algoritmes que treballen en particions (dividint el conjunt de senyes en grups) i abdós intenten minimisar la distància entre punts que s'afegirien a un grup i un atre punt designat com el centre d'eixe grup. En contrast en l'algoritme k-means, k-medoids tria datapoints com a centres i treballa en una mètrica arbitrària de distàncies entre datapoints en lloc d'usar la norma $l_2$. En 1987 es va propondre este método per al treball en la norma $l_1$ i atres distàncies.

K-medoid és una tècnica clàssica de particionado de grups que dividix les senyes conformades per n objectes en k grups (en k conegut de bestreta).

És més robust davant el soroll i a parts aïllades que k-means perque minimisa una suma de disimilaridades (entre parells de punts) en lloc d'una suma de distàncies euclidianes quadrades.

Un medoid pot ser definit com l'objecte d'un grup que la seua disimilaridad mija a tots els objectes en el grup és mínima. És el punt ubicat més cap al centre en tot el grup.

Algoritmes

L'aplicació pràctica més comuna de k-medoids és l'algoritme Partició Al voltant de Medoids (PAM). PAM utilisa una busca golosa que pugues no trobar la solució òptima, pero és més ràpit que la busca exhaustiva.Treballa com seguix:

1. Inicialisació: seleccionar k dels n punts com el medoid.
2. Associar cada punt al medoid més propenc.
3. Mentres el cost de la configuració disminuïxca:
   1. Per a cada medoid m, per a cada no medoid o:
      1. Intercanviar m i o, recalcular el cost (sumixca de la distància dels punts als seus medoids).
      2. Si el cost total de la configuració va aumentar en el pas anterior, desfer l'intercanvi.

Atres algoritmes han segut sugerits en la lliteratura, incloent el següent método de Iteración Voronoi:

1. Seleccionar els medoids inicials.
2. Iterar mentres el cost disminuïxca:
   1. En cada grup, marcar com medoid el punt que minimisa la suma de distàncies dins del grup.
   2. Reasignar cada punt al grup definit pel medoid més propenc determinat en el pas anterior.

Demostració de PAM

Agrupar el següent conjunt de senyes de dèu objectes en dos grups (k = 2).

Considera el següent conjunt de senyes:

Figura 1.1 - distribució de les senyes.

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

Pas 1

Figura 1.2 - grups despuix del pas 1.

Inicializar k centres.

Assumir x2 i x8 està marcats com medoids, aixina que els centres són c1 = (3,4) i c2 = (7,4).

Calcular distàncies a cada centre per a associar cada objecte al seu medoid més propenc. El cost està calculat utilisant distancia de Manhattan. Costs al medoid més propenc estan mostrats en negreta en la taula.

Cost (distància) a c1
i	c1		Objectes (Xi)		Cost (distància)
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

Cost (distància) a c2
i	c2		Objectes (Xi)		Cost (distància)
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

Llavors els grups serien:

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

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

Ya que els punts (2,6) (3,8) i (4,7) són més propencs a c1, per això formen un grup, mentres que els demés punts formen un atre grup.

Aixina que el cost total implicat és 20.

A on el cost entre qualsevol dos punts s'ha calculat utilisant la fòrmula:

$costo(x,c)=\sum _{k=1}^d|x_i-c_i|$

a on x és cualquier objecte, c és el medoid, i d és la dimensió de l'objecte, en este cas 2.

El cost total és la suma dels costs dels objectes al seu medoid en el grup, sent:

$$\begin{array}{cc}costototal& =\{costo((3,4),(2,6))+costo((3,4),(3,8))+costo((3,4),(4,7))\}\\ & +\{costo((7,4),(6,2))+costo((7,4),(6,4))+costo((7,4),(7,3))+costo((7,4),(8,5))\\ & +costo((7,4),(7,6))\}\\ costototal& =(3+4+4)+(3+1+1+2+2)\\ costototal& =20\end{array}$$

Pas 2

Figura 1.3 - grups despuix del pas 2.

Selecciona un dels no medoids O'.

Assumim O′ = (7,3).

Ara els medoids són c1(3,4) i O′(7,3).

Si c1 i O′ són nou medoids, calcular el cost total implicat.

Utilisant la fòrmula del pas 1.

i	c1		Objectes (Xi)		Cost (distància)
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
8	3	4	7	4	4
9	3	4	8	5	6
10	3	4	7	6	6

i	O′		Objectes (Xi)		Cost (distància)
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
8	7	3	7	4	1
9	7	3	8	5	3
10	7	3	7	6	3

Figura 2. K-medoids versus k-Mijos. Figs 2.1a-2.1f presenta un eixemple típic de la convergència de k-means a un mínim local. Este resultat de k-means contradiu l'estructura de grup obvia del conjunt de senyes. En este eixemple, l'algoritme k-medoids (Figs 2.2a-2.2h) en la mateixa posició inicial de medoids (Fig. 2.2a) convergix a l'estructura de grup obvia. Els círculs més chicotets són objectes, les quatre estreles de raig són centroids (miges), les nou estreles de raig són medoids.

$\begin{array}{cc}costototal& =3+4+4+2+2+1+3+3\\ costototal& =22\end{array}$

Sent el cost de l'intercanvi de medoids de c2 a O′:

$$\begin{array}{cc}S& =costototalactual-costototalpasado\\ & =22-20\\ & =2>0\end{array}$$

De manera que canviar a O′ seria una idea mala, aixina que l'elecció anterior estava ben. Aixina que provem en uns atres no-medoids i trobats que la nostra primera elecció era la millor. Aixina que la configuració no canvia i l'algoritme termina ací (ya que no hi ha cap canvi en els medoids).

Pot passar que alguns punts de senyes poden canviar d'un grup a un atre en dependència de la seua rodalia als medoids.

En algunes situacions estàndars, k-medoids demostra rendiment millor que k-means. Un eixemple es presenta en la Fig. 2.

La part més costosa de l'algoritme és el càlcul de les distàncies entre els punts o objectes. Si fora aplicable un preprocesamiento quadràtic i l'almagasenament, la matriu de distàncies pot ser precalculada per a conseguir una major rapidea. Existixen eixemples, a on els autors també introduïxen una heurística per a triar els k medoids inicials.