Dada una familia de n vectores {v_1,v_2...v_n} el método de agrupamiento K-means permite agruparlos en un número k determinado de grupos {S_1,S_2...S_k}, de manera que se minimice la suma de los errores cuadraticos de cada vector respecto al punto medio de todos los vectores del mismo grupo al que pertenece.
Este método es utilizado para la compresión de imágenes en tratamiento de señal, así como para la explotación de datos en lo que concierne al data mining y big data. Es un método bastante sencillo pero que consigue unos buenos resultados. Si necesitan más información sobre este método una búsqueda rápida les puede solucionar las dudas. Si es algo del código, encantado de ayudarles mediante un comentario en este post.
El fichero de entrada que contiene los vectores a ordenar debe ser del tipo (por defecto este fichero se llama "datos.txt"):
0.5 -2 3 4
1 2.4 -1.2 0
1 2.9 4 2
0.1 0.002 -3.14 5
6.1 -5.1 -6.4 7
9.9 7 -2.4 3
-8 1 0.1 -3
0.03 -5 2.9 6
Donde cada fila representa un vector (un total de ocho en este caso), y cada columna una componente de ese vector (4 en este caso).
El fichero de salida que se obtiene es:
SALIDA DEL METODO KMEANS
KMeans ha generado los siguientes grupos:
- Grupo 0 con media: [ -8.000000 1.000000 0.100000 -3.000000 ]
- Grupo 1 con media: [ 0.526000 -0.339600 1.112000 3.400000 ]
- Grupo 2 con media: [ 8.000000 0.950000 -4.400000 5.000000 ]
KMeans ha generado los siguientes grupos:
0.500000 -2.000000 3.000000 4.000000 1
1.000000 2.400000 -1.200000 0.000000 1
1.000000 2.900000 4.000000 2.000000 1
0.100000 0.002000 -3.140000 5.000000 1
6.100000 -5.100000 -6.400000 7.000000 2
9.900000 7.000000 -2.400000 3.000000 2
-8.000000 1.000000 0.100000 -3.000000 0
0.030000 -5.000000 2.900000 6.000000 1
Error: 8.097519
Reparticion grupos:
Grupo 0 : 1 elementos.
Grupo 1 : 5 elementos.
Grupo 2 : 2 elementos.
El código escrito en C está suficientemente comentado por lo que no debería suponer ningún problema:
/*Metodo k-means de agrupamiento CYPASCAL.BLOGSPOT.COM*/
/*NOTAS IMPORTANTES:
- Variables principales:
Comp: Numero de componenetes que tiene cada vector. Dimensón del espacio vectorial Rn al que
pertenecen.
Grup: Numero de conjuntos en los que se van a agrupar los vectores.
Epsilon: Si la diferencia entre el error cometido en la iteración anterior y el error cometido
en la iteración actual es menor que este valor, se sale del algoritmo.
- En el fichero de entrada cada vector aparece en una linea, y cada componente separada por un espacio.
A modo de ejemplo, si el numero de componentes es 3, y el numero de vectores a ordenar es 5, un fichero
tipo podría ser:
0.25 21.2 -1.25
14.3 -1.2 5
-0.001 10 0
0 -1.5 4
1 2 7
*/
#include <stdio.h>
#include <stdlib.h>
FILE *Lectura, *Escritura;
int Comp,Vect,Grup;
float Epsilon;
float Norma(float Vect1[], float Vect2[]);
int main(void)
{
/* 1: Pedimos los datos necesarios */
srand(time(NULL));
printf("METODO K-MEANS (Agrupamiento de vectores minimizando el ECM) \n");
printf("Numero de componentes del vector: ");
scanf("%i", &Comp);
printf("Numero de vectores a ordenar: ");
scanf("%i", &Vect);
printf("Numero de conjuntos en los que agrupar los vectores: ");
scanf("%i", &Grup);
printf("Limite de convergencia: ");
scanf("%f", &Epsilon);
int aVect=0,aComp=0,i,j,minG;
float Tabla[Vect][Comp];
float min,aux,ErrorAct,ErrorAnt=0,dif;
float MediaGrup[Grup][Comp],maxi[Comp],mini[Comp];
for (i=0; i<Comp; i++){maxi[i]=0; mini[i]=0;}
int CompGrup[Vect]; //Grupo en el que se encuentra el vector
int NumCompGrup[Grup]; //Numero de componentes en cada grupo
/* 2: Leemos el fichero de lectura y cargamos los datos en la tabla para un acceso más rápido*/
Lectura=fopen("datos.txt","r");
if (Lectura) {
for (i=0; i<Vect; i++) for (j=0; j<Comp; j++) {{
fscanf(Lectura,"%f",&Tabla[i][j]);
if (mini[j] > Tabla[i][j]) mini[j] = Tabla[i][j];
if (maxi[j] < Tabla[i][j]) maxi[j] = Tabla[i][j];
if (Tabla[i][j]==EOF){
i=Vect;
j=Comp;}
printf("%f \n",Tabla[i][j]);
}}
fclose(Lectura);
}
/* 3: Inicializamos el vector de medias con valores aleatorios*/
for (i=0; i<Grup; i++) for (j=0; j<Comp; j++) {
MediaGrup[i][j]=(float)rand()/RAND_MAX*(maxi[j]-mini[j])+mini[j];
}
dif=Epsilon+1; //Para entrar en el bucle
/* 4: Bucle principal del que no se sale hasta ser inferior a epsilon*/
while (dif>Epsilon){
ErrorAct=0;
/* 4.1: Se mira a que grupo pertenece cada vector*/
for (i=0; i<Vect; i++){
min = Norma(Tabla[i],MediaGrup[0]);
minG=0;
for (j=1; j<Grup; j++){
aux=Norma(Tabla[i],MediaGrup[j]);
if (aux<min){min=aux; minG=j;}
}
CompGrup[i]=minG;
ErrorAct=ErrorAct+min;
}
/* 4.2: Se actualiza el valor de la media del grupo*/
for (i=0; i<Grup; i++){
for (j=0; j<Comp; j++){
MediaGrup[i][j]=0;
}
NumCompGrup[i]=0;
}
for (i=0; i<Vect; i++){
for (j=0; j<Comp; j++){
MediaGrup[CompGrup[i]][j]=MediaGrup[CompGrup[i]][j]+Tabla[i][j];
}
NumCompGrup[CompGrup[i]]++;
}
for (i=0; i<Grup; i++){
for (j=0; j<Comp; j++){
MediaGrup[i][j]=MediaGrup[i][j]/NumCompGrup[i];
}
}
dif=abs(ErrorAct-ErrorAnt);
ErrorAnt=ErrorAct;
}
/* 5: Escritura de los resultados finales*/
Escritura=fopen("SalidaKMEANS.txt","w");
fprintf(Escritura, "\n SALIDA DEL METODO KMEANS\n\n");
fprintf(Escritura, "KMeans ha generado los siguientes grupos: \n");
for (i=0; i<Grup; i++){
fprintf(Escritura, "- Grupo %i con media: [",i);
for (j=0; j<Comp; j++) fprintf(Escritura, " %f ",MediaGrup[i][j]);
fprintf(Escritura, "]\n");
}
fprintf(Escritura, "\n\nKMeans ha generado los siguientes grupos: \n");
for (i=0; i<Vect; i++){
for (j=0; j<Comp; j++){
fprintf(Escritura, "%f ", Tabla[i][j]);
}
fprintf(Escritura, "%i \n", CompGrup[i]);
}
fprintf(Escritura, "\n Error: %f \n", ErrorAct);
fprintf(Escritura, "\n Reparticion grupos: \n");
for (i=0; i<Grup; i++){
fprintf(Escritura, "Grupo %i : %i elementos. \n", i,NumCompGrup[i]);
}
fclose(Escritura);
return 0;
}
float Norma(float Vect1[], float Vect2[])
{
float aux=0;
int n,j;
n = (int) sizeof(Vect1)/sizeof(Vect1[0]);
for (j=0; j<n; j++) {
aux=aux+(Vect1[j]-Vect2[j])*(Vect1[j]-Vect2[j]);
}
return aux;
}
Salu10.
No hay comentarios:
Publicar un comentario