lunes, 28 de octubre de 2013

Practica #2 : K-means

Publicado por Pamela Olivares en 11:45 Etiquetas: , , ,

Introducción

Un agrupamiento consiste en formar grupos de elementos con características en común (similitud), de tal forma que se podría decir que se analiza un elemento para determinar si pertenece o no a un grupo. Los grupos que obtendremos de los agrupamientos deben ser todos sus elementos parecidos de tal forma que todos elementos que conformen el grupo deberán ser similares.
En esta entrada realizaremos un algoritmo de agrupamiento denominado K-means el cual como ya mencionamos consiste en agrupar vectores por su similitud con los centroides (grupos). El contexto con el cual trabajaremos K-means sera determinar si una persona es apta o no es apta para realizar un trabajo.
En esta entrada podrás encontrar:
  • Marco teórico - Contendrá información acerca del tema.
  • Desarrollo- Contendrá la programación de las funciones mas importantes y una explicación detallada de nuestro caso de estudio.
  • Resultados
  • Conclusiones
  • Referencias

Marco Teórico
Un agrupamiento consiste en formar grupos de elementos, donde estos elementos deberán ser similares. Los grupos que se formen de este proceso deberán ser todos sus elementos parecidos(similares) de tal forma que el grupo no tendrá elementos que no seas similares.
Existen diferentes tipos de grupos que se pueden generar por ejemplo:

  • Partición: Busca grupos y estos grupos son representados por objetos (centroides), donde calculamos la similitud y asignamos los grupos.
  • Traslape : El algoritmo actualiza el agrupamiento.
  • Jerarquico: Agrupa y forma nuevos elementos , separando los grupos ya formados, para asi poder originar otros.
  • Difuso: Permite que un elemento quede en mas e un grupo
Un vector de características es aquel que contiene la información de un elemento en este caso como dice su nombre sus características, las cuales nos servirán para comparar mas adelante con las características de los centroides (los grupos) y así determinar a que grupo pertenece cada elemento.
Para calcular la similitud (distancia) entre vectores veremos 3 formas:
  • Distancia Euclidiana : Es el espacio entre dos puntos 
d_E(P,Q)=\sqrt{(p_1-q_1)^2 + (p_2-q_2)^2 + \cdots + (p_n-q_n)^2} = \sqrt{\sum_{i=1}^n (p_i-q_i)^2}.
donde:
Pn = características del vector que se esta analizando
Qn= características del centroide que se esta analizando.
  • Indice de Jaccard : Comparación de dos elementos para determinar si son parecidos o no.
c/a+b+c

donde:
a = numero de características del vector que se esta analizando
b= numero de características del centroide.
c= La suma total de todas las características.

  • Cosenoidal: Compara los elementos para determinar la similitud , calculando el coseno del angulo entre los vectores.
cos( Vdx, Vdy) = Vdx < Vdy / ||Vdx|| ||Vdy||

donde:
Vdx < Vdy  = Se obtiene el angulo entre un par de vectores
||Vdx|| ||Vdy|| = se obtiene la norma de cada vector.

K-means es un algoritmo de agrupamiento el cual consiste en tener un numero n de vectores a comparar con un numero n de centroides (grupos) y a partir de esa comparación obtener la similitud para así sabrá a que grupo pertenece el vector.

A continuación un ejemplo de K-means :
Vectores
Centroides
P1 (12,5)
C1 = (4.2, 1.5)
P2 (5,6)
C2 = (1.5 , 4)
P3 (4,2)

P4 (1,4)

P5 (6,3)

P6 (9,6)


Cálculos para la distancia:
P(1,C1) = ((12-4.2)2 + (5-1.5)2)1/2 =  8.54
 P(1,C2) = ((12-1.5)2 + (5-4)2)1/2 =  10.54

P(2,C1) = ((5-4.2)2 + (6-1.5)2)1/2 =  4.57
P(2,C2) = ((5-1.5)2 + (6-4)2)1/2 =  4.03

P(3,C1) = ((4-4.2)2 + (2-1.5)2)1/2 =  0.53
 P(3,C2) = ((4-1.5)2 + (2-4)2)1/2 =  3.30

P(4,C1) = ((1-4.2)2 + (4-1.5)2)1/2 =  4.06
P(4,C2) = ((1-1.5)2 + (4-4)2)1/2 =  0.5

P(5,C1) = ((6-4.2)2 + (3-1.5)2)1/2 =  2.34
 P(5,C2) = ((6-1.5)2 + (3-4)2)1/2 =  4.60

P(6,C1) = ((9-4.2)2 + (6-1.5)2)1/2 =  6.57
P(6,C2) = ((9-1.5)2 + (6-4)2)1/2 =  7.76
P(n,C)
C1
C2
12,5
8.54
10.54
5,6
4.57
4.03
4,2
.53
3.30
1,4
4.06
.5
6,3
2.34
4.60
9,6
6.57
7.76

C1
C2
12,5
5,6
4,2
1,4
6,3

9,6


Actualizar centroides:

C1(x) = (12+4+6+9)/4 = 7.75
C1 (y) = (5+2+3+6)/4 = 4
C1 = (7.75 , 4)

C2(x) = (5+1)/2 =3

C2(y) = (6+4) /2 = 5
C2 = (3,5)

Desarrollo

Nuestro contexto de agrupamiento consiste en agrupar a un grupo de personas para determinar si son aptos o no para un trabajo.

Nuestros vectores de características se realizaron a partir de una serie de preguntas donde las respuestas podían ser "si o no", donde si es 1 y 0 es no.

1.       ¿Cuenta con un título?
2.       ¿Cuenta con maestría?
3.       ¿Cuenta con doctorado?
4.       ¿Tiene experiencia?
5.       ¿Tiene disponibilidad de tiempo?
6.       ¿Vive cerca?
7.       ¿Ha trabajado en esta área?

1 =  Si                    0= No

Individuo
Preg.1
Preg.2
Preg.3
Preg.4
Preg.5
Preg.6
Preg.7
1
1
1
1
0
1
0
0
2
1
1
0
1
1
0
1
3
1
0
0
1
1
1
1
4
0
0
0
0
1
1
0
5
1
0
0
1
1
0
1

El equipo opto por utilizar la distancia euclidiana para calcular la similitud, por que es la que nos pareció mas sencilla y es con la que mas trabajamos en clase.

A continuación mostraremos algunos fragmentos de código:

Generación de centroides

Nosotros generamos los centroides asignándole nosotros mismos valores estáticos y los pusimos dentro de un arreglo.

C1 = 1111111
C2 = 0000000



Calculo de similitud entre vectores

Utilizamos la formula de la distancia euclidiana y al final imprimimos los valores para cada uno de los vectores con cada uno de los centroides.



Asignación de grupos

Aquí a través de unos if comparamos cada uno de los resultados obtenidos en el calculo de la distancia euclidiana y seleccionar el menor de estos.


 Actualización de los centroides

 Como se puede observar actualizamos los valores de arreglo donde guardamos los centroides, sumando los valores de cada una de las características de cada vector.


Si deseas descargar el código completo  haz Click aqui

Resultados




Parámetros

Núm. K (grupos)
2 (aptos y no aptos)
Núm. De Interacciónes
1

El criterio de terminación sucede cuando todos los vectores han sido agrupados y se calcula la actualización de los centroides.
Nota: Ya que es un grupo pequeño y los valores del vector son únicamente 1 y 0, no es necesario hacer demasiadas interacciones.

Los mejores grupos encontrados fueron :

C1 (apto)
1110100
1101101
1001111
1001101

C2 (no apto)
0000110

los resultados son algo predecibles ya que a simple vista podemos agrupar los vectores, por lo mismo solo se realizo una Interacción.

Conclusión

K-means es un método de agrupamiento muy fácil de implementar y sobre todo muy útil por ejemplo para agrupar correos o en una empresa agrupar piezas, entre muchas otras cosas mas.

El algoritmo se puede complicar cuando hay muchos vectores a agrupar, ya que se requiere un numero mayor de cálculos y mas interacciones.

Esperamos que esta entrada pueda ser de gran utilidad.

Referencias
Garza, S. E. (15 de octubre de 2013). Similitud Cosenoidal. Obtenido de elisa.dyndns: http://elisa.dyndns-web.com/saraelena/material/sistadap/cosim.pdf
Rojas, J. C., & Ponce Medellin, I. R. (s.f.). Programacion del algorito de agrupamiento K-means en SQL. Recuperado el 20 de 10 de 2013, de CENIDET: dsc.itmorelia.edu.mx/~jcolivares/documents/kmeanSQL.doc‎
Wikipedia. (7 de septiembre de 2013). Distancia Euclidiana. Obtenido de Wikipedia: http://es.wikipedia.org/wiki/Distancia_euclidiana
Wikipedia. (5 de marzo de 2013). Indice de Jaccard. Obtenido de Wikipedia.




0 comentarios:

Publicar un comentario

Suscribirse a: Enviar comentarios (Atom)