KMeans Clusters

K-Means
Integrantes
Natalia Merino (85828)
Gastn Sabatelli (85523)
M. Florencia Pereira (88816)
Introduccin al problema
K-Means resuelve un problema de clustering, que
consiste
en:
Se tiene un conjunto de datos u observaciones (x1, x2, ,
xn) donde cada dato representa un vector de n variables.

Se desea particionar las observaciones en k grupos.
Se elige para cada grupo un centro o media y se ubica
cada observacin en el grupo cuya media sea ms
cercana.
Introduccin al problema (cont.)

Para medir la cercana se utiliza la norma eucldea
y se busca minimizar la siguiente funcin:
donde i es la media de la particin Si (un grupo).
Caractersticas del
algoritmo
Es un problema NP-hard an para k=2.
Un problema es NP-hard si puede resolverse mediante un algoritmo que
pueda ser traducido a otro que resuelve un problema NP.

Los problemas clasificados como NP son por lo menos tan complejos
como los que pueden resolverse mediante una mquina de Turing en
tiempo polinmico.
Complejidad
n = numero de puntos,
k = numero de clusters,
I = numero iteraciones,
d = numero de atributos
Si fijamos los parametros n, k, d, I, la complejidad es:

O( n * k * I * d )
Caractersticas del algoritmo (cont.)

Siempre se tienen K clusters.
Siempre hay por lo menos un objeto en cada
cluster.
Mtodo no supervisado de aprendizaje
Los objetos debern poder representarse
mediante atributos numricos.
Los clusters son mutuamente expluyentes.
Los objetos pertenecientes a un cluster estn
lo ms cerca posible entre s y lo ms lejos
posible de los elementos de otros clusters.
Algoritmo
1. Se eligen arbitrariamente k centros o medias, una por cada
particin. En la prctica usualmente se eligen en forma aleatoria.

2. Paso de asignacin: se asignan las observaciones a la particin
cuyo centro sea ms cercano.
3. Paso de actualizacin: se calculan cuales son los nuevos centros
de cada particin. El centro representara el centro de masa o

el promedio de todas las observaciones que pertenecen a esa
particin.
4. Se repiten los pasos 2 y 3 hasta que no haya ms movimientos en
las particiones (entonces se dice que el algoritmo converge).
Anlisis grfico
1) Se eligen k medias
iniciales (en este caso k=3)
en forma aleatoria .
2) Se crean k clusters
asociando cada
observacin con la media
que ms se le acerca.
Anlisis grfico (cont.)
3) Se recalculan las medias de

cada cluster en funcin de las
observaciones asociadas a
cada uno.
4) Se repiten los pasos 2 y 3 hasta

que no se produzcan movimientos
de observaciones.
Ejemplo numrico (I)

Se tiene 4 tipos de remedios que se desean agrupar
en k=2 clusters, considerando 2 atributos que son:
peso y PH.
Remedio
atributo 1 (X):
peso
Atributo 2 (Y):
pH
Remedio A
Remedio B
Remedio C
Remedio D
Ejemplo numrico (II)

Iteracin 0:
Inicialmente elegimos como centros a los remedios A
y B.
Iteracin 0
4.5
4
3.5
3
2.5
pH
2
1.5
1
0.5
0
0.5
1.5
2.5
3
Peso
3.5
4.5
5.5
Ejemplo numrico (III)

Iteracin 0:
Calculamos la distancia de cada centro a cada
remedio, usando la distancia Eucldea.
A B
D
C1
C2
Asignamos a cada remedio un cluster. Para A el

cluster 1, para B el cluster 2, para C el cluster 2 y
para D el cluster 2.
Ejemplo numrico (IV)

Iteracin 1:
Obtenemos los nuevos centros.
El cluster 1 solo tiene un miembro, el remedio A.
El cluster 2 tiene 3 miembros, el nuevo centroide es
el promedio de sus coordenadas.
Iteracin 1
4.5
4
3.5
3
2.5
pH
2
1.5
1
0.5
0
0.5
1.5
2.5
3
Peso
3.5
4.5
5.5
Ejemplo numrico (V)

Iteracin 1:
A
D
C1
C2

Ejemplo numrico (VI)

Iteracin 2:
Obtenemos los nuevos centros.
Iteracin 2
5
4
3
PH
2
1
0
0.5
1.5
2.5
3
Peso
3.5
4.5
5.5
Ejemplo numrico (VII)

Iteracin 2:
A
D
C1
C2

Al no haber cambios ya no se necesitan ms
iteraciones.
Resultado
Remedio
Peso
pH
Cluster
Remedio A
Remedio B
Remedio C
Remedio D
Ventajas
Es un algoritmo sencillo y rpido.
Fcil de implementar. Por esta razn, la
mayora de las herramientas de Data Mining

incluyen al algoritmo.
Es prctico si no se tiene un gran nmero de
observaciones.
La forma clsica de implementacin de
Kmeans es usando la distancia Eucldea, sin
embargo la misma metodologa funciona bien
con otro tipo de distancias.
Desventajas
El resultado del algoritmo es muy sensible a la
configuracin inicial de los agrupamientos, es decir

cmo se asignaron los centros inicialmente.
La necesidad de definir la cantidad de particiones de
antemano, ya que la eleccin de un k inadecuado
puede derivar en un resultado lejano al ptimo.
Posibilidad de que se presenten ptimos locales al
asignar los centros, es decir que la particin sea
ptima en la forma que minimiza las distancias dentro
de cada grupo pero no a nivel total (no tiende a
obtener mnimos globales).
Imposibilidad de trabajar con datos categricos.
Desventajas (cont.)
Muy sensible a datos anmalos.
No funciona bien si los grupos son de distinto
tamao y densidad o no convexos.
Variaciones del algoritmo

Existen varios algoritmos como por ejemplo
GRASP [Greedy Randomized Adaptive

Search Procedure] que utilizan heursticas
tales como Ant Colony para evitar ptimos
locales.
k-Modes (Huang1998) utiliza modas en vez
de medias (para poder trabajar con atributos
de tipo categrico).
k-Medoids utiliza medianas en vez de
medias para limitar la influencia de los
observaciones distantes del resto.
Ejemplo en
WEKA
Bibliografa
http://elvex.ugr.es/decsai/intelligent/slides/
dm/D3%20Clustering.pdf
http://home.dei.polimi.it/matteucc/Clustering
/tutorial_html/kmeans.html
http://maya.cs.depaul.edu/classes/ect584/we
ka/k-means.html
Preguntas?
Gracias

KMeans Clusters

Cargado por

Copyright:

Formatos disponibles

KMeans Clusters

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

KMeans Clusters

Cargado por

Copyright:

Formatos disponibles

K-Means

xn) donde cada dato representa un vector de n variables.

Introduccin al problema (cont.)

y se busca minimizar la siguiente funcin:

donde i es la media de la particin Si (un grupo).

pueda ser traducido a otro que resuelve un problema NP.

Si fijamos los parametros n, k, d, I, la complejidad es:

Caractersticas del algoritmo (cont.)

particin. En la prctica usualmente se eligen en forma aleatoria.

3. Paso de actualizacin: se calculan cuales son los nuevos centros

de cada particin. El centro representara el centro de masa o

4. Se repiten los pasos 2 y 3 hasta que no haya ms movimientos en

las particiones (entonces se dice que el algoritmo converge).

Anlisis grfico (cont.)

3) Se recalculan las medias de

4) Se repiten los pasos 2 y 3 hasta

Ejemplo numrico (I)

Ejemplo numrico (II)

Ejemplo numrico (III)

Asignamos a cada remedio un cluster. Para A el

Ejemplo numrico (IV)

Ejemplo numrico (V)

Asignamos a cada remedio un cluster. Para A el

Ejemplo numrico (VI)

Ejemplo numrico (VII)

Asignamos a cada remedio un cluster. Para A el

mayora de las herramientas de Data Mining

configuracin inicial de los agrupamientos, es decir

tamao y densidad o no convexos.

Variaciones del algoritmo

GRASP [Greedy Randomized Adaptive

También podría gustarte