PRÁCTICA 2 K-MEANS

INTRODUCCIÓN

Cuando hablamos de agrupamiento nos referimos al  procedimiento para concentrar ciertos vectores dependiendo de las características de cada uno, de tal forma que queden agrupados por criterios de cercanía.

Por lo tanto los elementos de los grupos que se generarían a partir del proceso de agrupamiento compartirían características entre ellos.

Por mencionar un ejemplo de este procedimiento, hablaremos del método K-means que consiste en fraccionar  un grupo para formar colecciones de elementos   en base a sus características, de tal forma que con base a los criterios de agrupamiento queden más cercanos a la media  (centroides).

Para explicar el método de K-means lo haremos a partir del tema de Deportes con sus algunas características que lo definen; género, clasificación,  artístico, equipo, categoría.

A continuación se dará información más detallada sobre el tema de K-means dentro del Marco Teórico para tener una idea más clara sobre este método, para después mostrar un ejemplo de este mismo método implementado en la sección de Desarrollo y finalmente se mostrarán las conclusiones sobre esta práctica. 

MARCO TEÓRICO

Cuando hablamos de agrupamiento nos referimos al  procedimiento para concentrar ciertos vectores dependiendo de las características de cada uno, de tal forma que queden agrupados por criterios de cercanía.

Por lo tanto los elementos de los grupos que se generarían a partir del proceso de agrupamiento compartirían características entre ellos.

Existen diferentes tipos de agrupamiento según las características de sus elementos, entre ellos se encuentran el disjunto, traslape, traslape jerárquico  y difuso. El primero consiste en que los conjuntos no tengan ninguna propiedad en común.

El tipo de traslape consiste en tener ciertas características en sus componentes.

Mientras que el jerárquico se inicia con un solo grupo que incluye todas las características y dentro de él se hacen divisiones para generar nuevos,  y finalmente el difuso consiste en que un patrón puede tener niveles de pertenencia a los distintos subgrupos

Un vector, en programación es también conocida como arreglo o matriz unidimensional, como ya sabemos aquí se almacenan datos, elementos o características en cada casilla, que entre en un criterio de agrupamiento.

Como ya se ha mencionado antes, K-means o K-medias consiste en fraccionar  un grupo para formar colecciones de elementos   en base a sus características, de tal forma que con base a los criterios de agrupamiento queden más cercanos a la media  (centroides).

Para dejar este método de una forma más clara se realizó el siguiente diagrama.

DESARROLLO

Se agruparán Deportes de acuerdo a 5 criterios:

• Género: Si se juegan de forma varonil, femenil o mixto.
• Categoría: Si se agrupan por edad o por peso.
• Equipo: Si el deporte se practica individualmente o mayor de una persona
• Artístico: Si el deporte es artístico o no.
• Clasificación: Si el deporte se práctica de forma terrestre o acuático.

DEPORTE	GÉNERO	CATEGORÍA	EQUIPO	ARTÍSTICO	CLASIFICACIÓN
FÚTBOL	1 GÉNERO	EDAD	COLECTIVO	NO	TERRESTRE
JUDO	1 GÉNERO	PESO	INDIVIDUAL	NO	TERRESTRE
GIMNASIA	1 GÉNERO	EDAD	INDIVIDUAL	SÍ	TERRESTRE
NADO SINCRONIZADO	1 GÉNERO	EDAD	COLECTIVO	SÍ	ACUÁTICO
PATINAJE SOBRE HIELO	AMBOS	EDAD	COLECTIVO	SÍ	TERRESTRE

Se han pasado los datos anteriores de forma binaria para su manejo en el programa que se mostrará más adelante.

DEPORTE	GÉNERO	CATEGORÍA	EQUIPO	ARTÍSTICO	CLASIFICACIÓN
FÚTBOL	1	0	0	0	0
JUDO	1	1	1	0	0
GIMNASIA	1	0	1	1	0
NADO SINCRONIZADO	1	0	0	1	1
PATINAJE SOBRE HIELO	0	0	0	1	0

Algoritmo k-means

Generación de centroides

//generar centroides
    for(i=0;i<2;i++)
    {
         for(j=0;j<5;j++)
         {
              Centroides[i][j]=(0+rand()%(2-0));
         }     
    }

Cálculo de similitud entre vectores

for(d=0;d<=4;d++)//for de cada deporte
{
     for(i=0;i<=1;i++)//for para c/deporte con c/centroide
     {
          Aux[i][0]=sqrt((pow((double(Deportes[d][0])-Centroides[i][0]),2.0))+(pow((double(Deportes[d][1])-Centroides[i][1]),2.0))+(pow((double(Deportes[d][2])-Centroides[i][2]),2.0))+(pow((double(Deportes[d][3])-Centroides[i][3]),2.0))+(pow((double(Deportes[d][4])-Centroides[i][4]),2.0)));                 
     }
} 

Asignación de Grupos

if(Aux[0][0]<Aux[1][0])//Acomodarlos
{
     Agrupado[C1][0]=d;
     C1++;
}else
{
     Agrupado[C2][1]=d;
     C2++;
}

Actualización de centroides

//Calcular nuevos centroides
Aux[0][1]=C1;Aux[1][1]=C2;
         
for(i=0;i<2;i++)
{
     for(j=0;j<5;j++)
     {
          suma=0;
          for(c=0;c<Aux[i][1];c++)//promedios de cada grupo
          {
               suma=suma+Deportes[(Agrupado[c][i])][j];
          }
          Centroides[i][j]=(suma/Aux[i][1]);                  
     }
}    

Código Completo
https://www.dropbox.com/s/mhwl9evdpvltua7/Agrupamiento.cpp


Parámetros

El valor de k utilizada fue de 2, osea que generamos 2 grupos 

Nuestro criterio de terminación fueron un número de iteraciones, hicimos 4 iteraciones.





Ejecutamos varias veces el algoritmo aunque la verdad en las iteraciones no había cambio en los grupos si acaso solo una ves la primera iteracion salio diferente a las demás a partir de la segunda ya no hubo ningún cambio, la razón debe de ser porque utilizamos solo datos binarios



Resultados

Ejecución del código.

donde:

0 = Futbol

1 = Judo

2 = Gimnasia

3 = Nado sincronizado

4 = Patinaje sobre hielo

Mejores grupos encontrados:

Después de realizar varias corridas del código pensamos que el mejor grupo encontrado es el siguiente:

En el grupo 1 el programa agrupó a Fútbol y Judo y en el grupo 2 agrupo a Gimnasia, Nado sincronizado y Patinaje sobre hielo.

Lo que tienen en común los deportes del grupo 1 es que no son considerados artísticos y en el grupo 2 tienen en común que si son considerados deportes artísticos.

Es por eso que al grupo 1 lo llamaríamos "Deportes No artísticos"

y al grupo 2 "Deportes Artísticos".

Otros grupos que encontramos

Agrupados por "Categoría".

Agrupados por "Clasificación".

Agrupados por "Tipo de Equipo".

Todos estos grupos nos parecen adecuados pues si tienen coherencia para nosotras, aunque un resultado inesperado que tuvimos fue el siguiente:

Grupo 1: Judo, Gimnasia, Nado sincronizado.

Grupo 2: Fútbol y Patinaje sobre Hielo.

Es extraño porque Fútbol  y Patinaje difieren en las categorías "Género" y "Artístico", podría decirse que son muy diferentes.

La razón debe de ser porque al generar los centroides por primera vez estos fueron las cantidades que se generaron aleatoria mente:

El centroide 1 tenía puros 1's y el centroide 2 puros 0's.

CONCLUSIÓN

En conclusión de K- Means…

Después de realizar la práctica 1 de ACO, todo parecía más fácil.

Esta práctica en particular nos fue más sencilla, los conceptos de igual manera fueron sencillos y se comprendieron a la perfección por lo que llevarlo a la codificación no fue un problema.

La mayoría de los resultados fueron los esperados ya que se agrupaban los deportes y tenían una coherencia por lo que concluimos que el programa cumplía con su objetivo de agrupar los elementos según los criterios de cercanía.