ginikernel.cpp

SVM经典调试程序,内有说明,应用简便,可用做回归分类方面的计算

/*****************************************************************************/
// NAME  :
// 
// DESCRIPTION :
//
//
/*****************************************************************************/
#include<ginikernel.h>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>


/*****************************************************************************/
// FUNCTION  :    InitializeCache
// 
// DESCRIPTION :  Initializes the kernel cache with cachesize=inpsize
//                and training data size inptrain.
//
// INPUT :
//
// OUTPUT :
//
//
/*****************************************************************************/
GINI_bool GINI_SVMKernel::InitializeCache ( GINI_u32 inpsize , GINI_u32 inptrain)
{
   GINI_u32 i,j;
   trainsize = inptrain;
   cachesize = inpsize;
   totalactive = 0;
   swapcounter = 0;
   if ( inpsize > 0 )
   {
      cachedata = new (GINI_double*)[inpsize];
      cachemap = new GINI_u32[trainsize];
      activity = new GINI_u32[inpsize];
      reversemap = new GINI_u32[inpsize];
      if (( cachedata == (GINI_double**) GINI_NULL ) ||
          ( cachemap == (GINI_u32*) GINI_NULL )     ||
	  ( activity == (GINI_u32*) GINI_NULL )     ||
          ( reversemap == (GINI_u32*) GINI_NULL )     
      )
      {
         ginierr = GINI_OUTOF_MEMORY;
         return GINI_FALSE;
      }

      // Initialize the cachemap zeros
      for ( i = 0; i<trainsize; i++ )
      {
         cachemap[i] = 0;
      }

      // Initialize the cache to GINI_FLOAT_INVALID
      for ( i = 0; i < inpsize; i++ )
      {
         cachedata[i] = new GINI_double[inpsize];
         for ( j = 0; j < inpsize; j++ )
         {
            cachedata[i][j] = GINI_FLOAT_INVALID;
         }
	 activity[i] = 0;
	 reversemap[i] = 0;
      }
   }
   return GINI_TRUE;
}

/*****************************************************************************/
// FUNCTION  :
// 
// DESCRIPTION :
//
// INPUT :
//
// OUTPUT :
//
//
/*****************************************************************************/
GINI_bool GINI_SVMKernel::ComputeAll( GINI_double** training, GINI_u32 dimension )
{
   if ( cachedata == (GINI_double**) GINI_NULL )
   {
      ginierr = GINI_ILLEGAL_OPERATION;
      return GINI_FALSE;
   }

   for ( GINI_u32 i = 0; i<trainsize; i++)
   {
      for ( GINI_u32 j = 0; j<trainsize; j++ )
      {
         cachedata[i][j] = Value(training[i],training[j],dimension); 
	 evaluations++;
      }
      // Set the corresponding cachemap
      cachemap[i] = i+1;
   }
   return GINI_TRUE;
}

/*****************************************************************************/
// FUNCTION  :    Value
// 
// DESCRIPTION :  Returns the value of the kernel between two training
//                data points. Cachemap keeps a mapping between the data
//                points and the cacheid. Cacheids start from 1, and zeros
//                is a reserved number for invalid id.
//
// INPUT :
//
// OUTPUT :
//
//
/*****************************************************************************/
GINI_double GINI_SVMKernel::Value( GINI_double **traindata,
		              GINI_u32 a, 
			      GINI_u32 b,
			      GINI_u32 dim
			     )
{
   GINI_double retval;

   // Check if a and b are in the cache
   if  (( cachemap[a] != 0 ) && ( cachemap[b] != 0 ))
   {
      // If they are then check if the kernel between
      // them has been computed or not.  
      if((retval = cachedata[cachemap[a]-1][cachemap[b]-1]) == GINI_FLOAT_INVALID)
      {
         retval = Value(traindata[a],traindata[b],dim);
	 cachedata[cachemap[a]-1][cachemap[b]-1] = retval;
	 cachedata[cachemap[b]-1][cachemap[a]-1] = retval;
	 activity[cachemap[a]-1]++;
	 activity[cachemap[b]-1]++;
	 evaluations++;
      }
   }
   else
   {
      retval = Value(traindata[a],traindata[b],dim);
      evaluations++;

        // Check if the current size of cache is less than the maximum allowed.
	// then just put it in
        if ((cachemap[a] == 0 ) &&( currentcachesize < cachesize ))
        {
           // Reverse mapping from cache id to data id.
           reversemap[currentcachesize] = a;

	   // Forward mapping from data id to cache id.
           cachemap[a] = ++currentcachesize; 
	   totalactive++;

           if ((cachemap[b] == 0 ) && ( currentcachesize < cachesize ))
           {
              // Reverse mapping from cache id to data id.
              reversemap[currentcachesize] = b;

	      // Forward mapping from data id to cache id.
              cachemap[b] = ++currentcachesize; 
	      totalactive++;

	      cachedata[cachemap[a]-1][cachemap[b]-1] = retval;
	      cachedata[cachemap[b]-1][cachemap[a]-1] = retval;
           }
       }
   }
   return retval;
}

/*****************************************************************************/
// FUNCTION  :
// 
// DESCRIPTION :
//
// INPUT :
//
// OUTPUT :
//
//
/*****************************************************************************/
GINI_bool GINI_SVMKernel::ResetActivity( GINI_u32 a )
{
    // Check if the data point is present in the cache or not.
    if ( cachemap[a] != 0 )
    {
       activity[cachemap[a]-1] = 0;
       totalactive--;
    }

    // Indicator if the cache is full or not.
    if ( totalactive < cachesize )
    {
       return GINI_FALSE;
    }
    else
    {
       return GINI_TRUE;
    }
}

/*****************************************************************************/
// FUNCTION  :
// 
// DESCRIPTION :
//
// INPUT :
//
// OUTPUT :
//
//
/*****************************************************************************/
GINI_bool GINI_SVMKernel::InsertCache( GINI_u32 a )
{

    GINI_u32 mina,minind,i;
    // Sets the cache flag to start caching
    // the kernel values.

    // Check if the data point is present in the cache or not.
    if ( cachemap[a] == 0 )
    {
        // Check if the current size of cache is less than the maximum allowed.
	// then just put it in
        if ( currentcachesize < cachesize )
        {
           // Reverse mapping from cache id to data id.
           reversemap[currentcachesize] = a;

	   // Forward mapping from data id to cache id.
           cachemap[a] = ++currentcachesize; 
	   totalactive++;
        }
	else
        {
           // If the cache is full then take the data point out whose
           // inactivity is the lowest. If several of them have 
	   // the same inactivity counter then eliminate the one which
           // is last in the cache. If we encounter an activity counter
           // of zero anywhere then immediately replace it using that.
           mina = 999999;
	   minind = 0;
	   for ( i = 0; i< cachesize; i++)
           {
              // Found an inactive cache which is old, so we
	      // immediately replace it.
              if ( activity[i] == 0 )
              {
                 minind = i;
                 break;
              }
              if (activity[i] <= mina )
              {
                 minind = i;
		 mina = activity[i];
              }
           }

	   // Reset all activity counters
	   //printf("Replacing Data %d with %d\n",reversemap[minind],a);
	   swapcounter++;
	   cachemap[a] = minind+1;
	   cachemap[reversemap[minind]] = 0;
	   reversemap[minind] = a;
	   for ( i = 0; i < cachesize; i++ )
           {
               cachedata[cachemap[a]-1][i] = GINI_FLOAT_INVALID;
               cachedata[i][cachemap[a]-1] = GINI_FLOAT_INVALID;
	       //activity[i] = 0;
           }
        }
    }
    if ( totalactive < cachesize )
    {
       return GINI_FALSE;
    }
    else
    {
       return GINI_TRUE;
    }
}
/*****************************************************************************/
// FUNCTION  :
// 
// DESCRIPTION :
//
// INPUT :
//
// OUTPUT :
//
//
/*****************************************************************************/
GINI_SVMKernel::~GINI_SVMKernel()
{
   if ( cachedata != (GINI_double**)GINI_NULL )
   {
      for (GINI_u32 i = 0; i < cachesize; i++)
      {
         delete [] cachedata[i];
      }
      delete [] cachedata;
   }
   if ( cachemap != (GINI_u32*)GINI_NULL )
   {
      delete [] cachemap;
   }

   delete [] activity;
   delete [] reversemap;
}

/*****************************************************************************/
// FUNCTION  :
// 
// DESCRIPTION :
//
// INPUT :
//
// OUTPUT :
//
//
/*****************************************************************************/
GINI_GaussianKernel::GINI_GaussianKernel( GINI_double inpgamma, GINI_bool inpflag )
{
   gamma = inpgamma;
   sparseflag = inpflag;
}

/*****************************************************************************/
// FUNCTION  :
// 
// DESCRIPTION :
//
// INPUT :
//
// OUTPUT :
//
//
/*****************************************************************************/
GINI_double GINI_GaussianKernel::Value( GINI_double* a, GINI_double* b, GINI_u32 dim)
{
   GINI_double currval = 0.0;
   GINI_u32 count1 = 1;
   GINI_u32 count2 = 1;

   if ( sparseflag == GINI_FALSE )
   {
      for ( GINI_u32 i = 0; i < dim; i++)
      {
          currval += (a[i]-b[i])*(a[i]-b[i]);
      }
   }
   else
   {
      // In sparse format the first dimension stores the length
      // of the vector.
      while (( count1+1 <= (GINI_u32)(2*a[0]) ) && ( count2+1 <= (GINI_u32)(2*b[0])))
      {
         while (( a[count1] < b[count2] ) && ( count1+1 <= (GINI_u32)(2*a[0])))
         {
            count1 += 2;
         }
         while (( b[count2] < a[count1] ) && ( count2+1 <= (GINI_u32)(2*b[0])))
         {
            count2 += 2;
         }
	 if ( b[count2] == a[count1] )
         {
             currval += (a[count1+1]-b[count2+1])*(a[count1+1]-b[count2+1]);
	     count2+=2;
	     count1+=2;
         }
      }
   }
   return exp(-gamma*currval);
}

/*****************************************************************************/
// FUNCTION  :
// 
// DESCRIPTION :
//
// INPUT :
//
// OUTPUT :
//
//
/*****************************************************************************/
GINI_bool GINI_GaussianKernel::Write( FILE* output )
{
   GINISVMKernelType ktype = GetId();
   if ( fwrite(&ktype,sizeof(GINISVMKernelType),1,output) == 0 )
   {
         return GINI_FALSE;
   }

   if ( fwrite(&gamma,sizeof(GINI_double),1,output) == 0 )
   {
         return GINI_FALSE;
   }
   if ( fwrite(&sparseflag,sizeof(GINI_bool),1,output) == 0 )
   {
         return GINI_FALSE;
   }

   return GINI_TRUE;
}

/*****************************************************************************/
// FUNCTION  :
// 
// DESCRIPTION :
//
// INPUT :
//
// OUTPUT :
//
//
/*****************************************************************************/
GINI_bool GINI_GaussianKernel::Read( FILE* output )
{
   GINISVMKernelType ktype;
   if ( fread(&ktype,sizeof(GINISVMKernelType),1,output) == 0 )
   {
         return GINI_FALSE;
   }

   if ( ktype != GetId())
   {
      return GINI_FALSE;
   }

   if ( fread(&gamma,sizeof(GINI_double),1,output) == 0 )
   {
         return GINI_FALSE;
   }

   GINI_bool inpflag;
   if ( fread(&inpflag,sizeof(GINI_bool),1,output) == 0 )
   {
         return GINI_FALSE;
   }

   if ( inpflag != sparseflag )
   {
      printf("Data format mismatch !! Both SV and Test data should be sparse/non-sparse\n");
      return GINI_FALSE;
   }

   printf("Gaussian Kernel with parameters = (%4.5f)\n",gamma);
   return GINI_TRUE;
}

/*****************************************************************************/
// FUNCTION  :
// 
// DESCRIPTION :
//
// INPUT :
//
// OUTPUT :
//
//
/*****************************************************************************/
GINI_PolyKernel::GINI_PolyKernel( GINI_double inpscale, GINI_u32 inppower, GINI_bool inpflag )
{
   scale = inpscale;
   power = inppower;
   sparseflag = inpflag;
   offset = 1;
}

/*****************************************************************************/
// FUNCTION  :
// 
// DESCRIPTION :
//
// INPUT :
//
// OUTPUT :
//
//
/*****************************************************************************/
GINI_PolyKernel::GINI_PolyKernel( GINI_double inpoffset,
		                  GINI_double inpscale,
				  GINI_u32 inppower,
				  GINI_bool inpflag
	                	)
{
   scale = inpscale;
   power = inppower;
   offset = inpoffset;
   sparseflag = inpflag;
}

/*****************************************************************************/
// FUNCTION  :
// 
// DESCRIPTION :
//
// INPUT :
//
// OUTPUT :
//
//
/*****************************************************************************/
GINI_double GINI_PolyKernel::Value( GINI_double* a, GINI_double* b, GINI_u32 dim)
{
   GINI_double currval = 0.0;
   GINI_u32 count1 = 1;
   GINI_u32 count2 = 1;

   if ( sparseflag == GINI_FALSE )
   {