funcionesKNN.cpp

00001 //#include <HardwareSerial.h> // solo para Debug
00002 
00003 /*------------------------------------------ 
00004 funciones para el computo del algoritmo KNN
00005 --------------------------------------------*/
00006 //#include "dataset.h"
00007 #include "funcionesKNN.h"
00008 #include <math.h>
00009 
00010 /*----------------------------------------------
00011 calculo de distancia euclidiana entre dos puntos
00012 ------------------------------------------------*/
00013 double distanciaEuclidiana(double pt1[], double pt2[], int co){  
00014   int i;
00015   double suma = 0;
00016   for(i=0; i<co; i++){
00017     suma = pow(pt1[i] - pt2[i], 2) + suma;
00018   }
00019   return sqrt(suma);
00020 }
00021 
00022 
00023 /*---------------------------------------------------------------
00024 calculo de distancia euclidiana entre un punto y la base de datos
00025 ----------------------------------------------------------------*/
00026 void todasDistEuclid(double pt1[], double aux[], double** atributos, int fi, int co){
00027   int i = 0, j = 0;
00028   double pt2[co];
00029   
00030   // falta esto
00031   for(i = 0; i<fi; i++){
00032     // extraer un punto de la base de datos
00033     for(j=0; j<co; j++){
00034       pt2[j] = atributos[i][j];       
00035     }
00036     
00037     aux[i] = distanciaEuclidiana(pt1, pt2, co);
00038   }
00039 }
00040 
00041 /*----------------------------------------------------------------
00042 Ordenamiento de las distancias de menor a mayor
00043 ----------------------------------------------------------------*/
00044 void ordena(double datos[], int clases[], int clasesNo[], int fi){
00045   int i =1, j = 1, f = 1, temp[2];
00046   
00047   //crear una copia de las clases originales
00048   for(i=0; i<fi; i++){
00049     clases[i] = clasesNo[i];  
00050   }
00051   
00052   // ordenar
00053   for(i=1; (i<=fi)&&f; i++){
00054     f = 0;
00055     for(j=0; j<(fi-1); j++){
00056       if(datos[j+1] < datos[j]){ // orden descendente >, ascendente <
00057         temp[0] = datos[j];    temp[1] = clases[j];
00058         datos[j] = datos[j+1]; clases[j] = clases[j+1]; 
00059         datos[j+1] = temp[0];  clases[j+1] = temp[1];
00060         f = 1;
00061       }
00062     }
00063   }
00064 }
00065 
00066 /*----------------------------------------------------------------
00067 Extraer los N primeros
00068 ----------------------------------------------------------------*/
00069 void extraeKPrimeros(double datos[], double kPrimeros[], int clases[], 
00070                      int kClases[], int k){
00071  
00072   for(int i=0; i<k; i++){
00073     kPrimeros[i] = datos[i];  
00074     kClases[i] = clases[i];
00075   }
00076 }
00077 
00078 /*----------------------------------------------------------------
00079 Calcula la clase mas frecuente: Moda
00080 ----------------------------------------------------------------*/
00081 int claseMasFrecuente(int clases[], int k){
00082   
00083   int cont = 0, cont2 = 0, pos = 0, num = 0, i = 0;
00084   int frec[k], mayor = 0, posmayor = 0, aux[k];
00085   
00086   // inicializar el contador de frecuencias
00087   for(i=0; i<k; i++){
00088     frec[k] = 0;  
00089   }
00090 
00091   // comprobar las repeticiones de cada numero
00092   for(cont=0; cont<k; cont++){
00093     num = clases[cont];
00094     pos = cont;
00095     
00096     for(cont2 = 0; cont2<k; cont2++){
00097       if(clases[cont2] == num){
00098         aux[pos]++;
00099       }  
00100     }
00101   }
00102    
00103   mayor =aux[0];
00104   posmayor = 0;
00105     
00106   for(cont=0; cont<k; cont++){
00107     if(aux[cont] > mayor){
00108       posmayor = cont;
00109       mayor = aux[cont];
00110     }  
00111   }
00112   
00113   return clases[posmayor];
00114 }
00115 
00116   
00117 /*----------------------------------------------------------------
00118 Calcula la clase de un conjunto de atributos usando KNN
00119 ----------------------------------------------------------------*/
00120 int clasificaKNN(double** datos, int clasesNum[], double dato[], int k, int fi, int co){
00121   double distancias[fi], kPrimeros[k];
00122   int clases[fi];
00123   int kClases[k];
00124   
00125   todasDistEuclid(dato, distancias, datos, fi, co); 
00126   ordena(distancias, clases, clasesNum, fi); 
00127   extraeKPrimeros(distancias, kPrimeros, clases, kClases, k); 
00128   
00129   // calculo de la moda
00130   int cont = 0, cont2 = 0, pos = 0, num = 0, i = 0;
00131   int frec[k], mayor = 0, posmayor = 0, aux[k];
00132   
00133   // inicializar el contador de frecuencias
00134   for(i=0; i<k; i++){
00135     frec[k] = 0;  
00136   }
00137  
00138   // comprobar las repeticiones de cada numero
00139   for(cont=0; cont<k; cont++){
00140     num = clases[cont];
00141     pos = cont;
00142     
00143     for(cont2 = 0; cont2<k; cont2++){
00144       if(clases[cont2] == num){
00145         aux[pos]++;
00146       }  
00147     }
00148   }
00149    
00150   mayor =aux[0];
00151   posmayor = 0;
00152     
00153   for(cont=0; cont<k; cont++){
00154     if(aux[cont] > mayor){
00155       posmayor = cont;
00156       mayor = aux[cont];
00157     }  
00158   }
00159   
00160   return clases[posmayor];
00161 }
00162