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.
