ginisvm.cpp

一种新的SVM算法

               {
                  phase1++;
                  return 1;
               }
            }
         }
      }


      // If the previous strategy failed then start at a 
      // random point in the sv list.
      GINI_u32 srchwin = 0;
      GINI_u32 start = rand()%setsize[c1];
      GINI_u32 startclass = rand()%classes;
      startptr = svset[c1];
      for ( i = 0; i < start; i++ )
      {
         startptr = startptr->next;
      }

      i2 = startptr->dataind;
      // Now iterate from this random point.
      while (( startptr != (GINI_Set*) GINI_NULL ) && 
             ( srchwin < maxsvsrch ) &&
	     ( srchwin < setsize[c1]))
      {
         if ( g11 - startptr->E  > 0 ) 
         {
            // a11 will most probably decrease so make sure that
            // a21 is not at bounds
	    if ( _getdirection(startptr->dataind,c1) == GINI_UP_DOWN )
            {
               // Select the class with the maximum value of
               // E22.
               c2 = 0;
               evalue = -9999999;
               found = GINI_FALSE;
               for ( i = startclass; i < classes; i++ )
               {
                  if (( (currptr = svmap[startptr->dataind][i]) != (GINI_Set*) GINI_NULL ) &&
                      ( i != c1 ) &&
		      (_getdirection(i1,i) == GINI_UP_DOWN))
                  {
                     if ( currptr->shrinklevel == 0)
                     {
                        if ( evalue < currptr->E)
                        {
                           evalue = currptr->E;
	                   c2 = i;
			   i2 = currptr->dataind;
			   found = GINI_TRUE;
                        }
                     }
                  }
               }
            }
         }
         else
         {
            // a11 will most probably increase so make sure that
            // a21 is not at bounds
	    if ( dir == GINI_UP_DOWN )
            {
               // Select the class with the minimum value of
               // E22.
               c2 = 0;
               evalue = 99999;
               found = GINI_FALSE;
               for ( i = startclass; i < classes; i++ )
               {
                  if (( (currptr = svmap[startptr->dataind][i]) != (GINI_Set*) GINI_NULL ) &&
                      ( i != c1 ) &&
		      (_getdirection(i1,i) == GINI_UP_DOWN) &&
		      (_getdirection(startptr->dataind,i) == GINI_UP_DOWN ))
                  {
                     if ( currptr->shrinklevel == 0)
                     {
                        if ( evalue > currptr->E)
                        {
                           evalue = currptr->E;
	                   c2 = i;
			   i2 = currptr->dataind;
			   found = GINI_TRUE;
                        }
                     }
                  }
               }
            }
         }

	 if ( found == GINI_TRUE )
         {
            if ( _takestep(i1,c1,i2,c2,&g11,(GINI_double*)GINI_NULL,&startptr->E,&evalue) )
            {
               phase2++;
               return 1;
            }
         }
	 srchwin++;
	 startptr = startptr->next;
	 if ( startptr == ( GINI_Set*) GINI_NULL )
         {
            startptr = svset[c1];
         }
      }
   }

   // If both the above strategies failed then we
   // pick a random dataid and random classid
   // and proceed from there.
   i2 = i1;
   while ( i2 == i1)
   {
      i2 = rand()%totaldata;
   }

   count = 0;
   while ( count < srchwindow )
   {
      c2 = c1;
      while ( c2 == c1 )
      {
         c2 = rand()%classes;
      }

      if ( _takestep(i1,c1,i2,c2,(GINI_double*)GINI_NULL,(GINI_double*)GINI_NULL,(GINI_double*)GINI_NULL,(GINI_double*)GINI_NULL))
      {
         phase3++;
         return 1;
      }
      count++;
      //currcnt--;
      i2 = (i2+1)%totaldata;
   }

   phase4++;
   return 0;
}

/*****************************************************************************/
// FUNCTION  :
// 
// DESCRIPTION :
//
// INPUT :
//
// OUTPUT :
//
//
/*****************************************************************************/
/*GINI_u32 GINI_SVMBlock::_examinesvExample( GINI_u32 i1 )
{
   GINI_u32 i2,c2,i,c1;
   GINI_Set *currptr, *startptr;
   GINI_bool found;
   GINI_double g11,evalue;
   GINI_status dir;

   struct timeval tv;
   struct timezone tz;
   (void) gettimeofday(&tv,&tz);

   // First evaluate the KKT condition for this data point
   // and choose the corresponding class for which its violated.
   if ( _kktcondition(i1,&c1,&g11,&dir) == GINI_FALSE )
   {
      timer1 += currtimeval(&tv);
      return 0;
   }
   timer1 += currtimeval(&tv);

   // We would want to select other three set of data points
   // such that there is a maximum decrease in the cost function.
   // The valid combinations are 
   // (GINI_DOWN, GINI_UP_DOWN, GINI_UP_DOWN, *)
   // (GINI_UP_DOWN, * , * , * )
   
   // Strategy 1
   // First search along the same data point but different
   // class, if there exist an sv and if there is one choose
   // the one with the maximum or minimum gradient depending
   // on the sign of g11 and dir.
   //
   if ( dir == GINI_DOWN )
   {
      // minimum g12 minimum g21 and a12 and a21 can go up
      c2 = 0;
      evalue = 9999999;
      found = GINI_FALSE;
      for ( i = 0; i < classes; i++ )
      {
         if (( (currptr = svmap[i1][i]) != (GINI_Set*) GINI_NULL ) &&
             ( svmap[minE[c1]->dataind][i] != (GINI_Set*) GINI_NULL ) &&
             ( i != c1 ) &&
	     (_getdirection(i1,i) == GINI_UP_DOWN ))
         {
            if ( currptr->shrinklevel == 0 )
            {
                  if ( evalue > currptr->E )
                  {
                     evalue = currptr->E;
		     c2 = i;
	             found = GINI_TRUE;
                  }
             }
          }
      }

      // Once the second class is found choose the
      // data point in that set corresponding to the
      // maximum gradient.
      if ( found == GINI_TRUE )
      {
         //if ( setsize[c2] > 0 )
         if ( setsize[c1] > 0 )
         {
            if ( _getdirection(minE[c1]->dataind,c1) == GINI_UP_DOWN )
            {
               if ( _takestep(i1,c1,minE[c1]->dataind,c2,&g11,&evalue,&(minE[c1]->E), (GINI_double*)GINI_NULL ))
               {
                  phase1++;
                  return 1;
               }
            }
         }
      }
   }
   else
   {
       // If there is no specific choice of current data point
       // then try either direction.
       // Check which directional gradient is bigger g11-min(g21)
      if ( fabs(g11-minE[c1]->E) > fabs(g11-maxE[c1]->E))
      {
         // First min g12 and max g22
         c2 = 0;
         evalue = 9999999;
         found = GINI_FALSE;
         for ( i = 0; i < classes; i++ )
         {
            if (( (currptr = svmap[i1][i]) != (GINI_Set*) GINI_NULL ) &&
                ( svmap[minE[c1]->dataind][i] != (GINI_Set*) GINI_NULL ) &&
             ( i != c1 ) &&
	     (_getdirection(i1,i) == GINI_UP_DOWN))
            {
                if ( currptr->shrinklevel == 0 )
                {
                     if ( evalue > currptr->E )
                     {
                        evalue = currptr->E;
		        c2 = i;
	                found = GINI_TRUE;
                     }
                  }
              }
          }

         // Once the second class is found choose the
         // data point in that set corresponding to the
         // maximum gradient.
         if ( found == GINI_TRUE )
         {
            if ( setsize[c1] > 0 )
            {
               if ( _getdirection(minE[c1]->dataind,c1) == GINI_UP_DOWN )
               {
                  if ( _takestep(i1,c1,minE[c1]->dataind,c2,&g11,&evalue,&(minE[c1]->E),(GINI_double*)GINI_NULL ))
                  {
                     phase1++;
                     return 1;
                  }
               }
            }
         }
      }
      else
      {
         // If the previous step was unsuccesful try
         // the other direction now
         // max g12 and min g22
         c2 = 0;
         evalue = -9999999;
         found = GINI_FALSE;
         for ( i = 0; i < classes; i++ )
         {
            if (( (currptr = svmap[i1][i]) != (GINI_Set*) GINI_NULL ) &&
             ( i != c1 ) &&
	     ( svmap[maxE[c1]->dataind][i] != (GINI_Set*) GINI_NULL ) &&
	     ( _getdirection(maxE[c1]->dataind,i) == GINI_UP_DOWN))
            {
               if ( currptr->shrinklevel == 0 )
                {
                     if ( evalue < currptr->E )
                     {
                        evalue = currptr->E;
		        c2 = i;
	                found = GINI_TRUE;
                     }
                  }
              }
          }

         // Once the second class is found choose the
         // data point in that set corresponding to the
         // maximum gradient.
         if ( found == GINI_TRUE )
         {
            if ( setsize[c1] > 0 )
            {
               if ( _takestep(i1,c1,maxE[c1]->dataind,c2,&g11,&evalue,&(maxE[c1]->E),(GINI_double*)GINI_NULL ))
               {
                  phase1++;
                  return 1;
               }
            }
         }
      }
   }


   // If the previous strategy failed then start at a 
   // random point in the sv list.
   GINI_u32 srchwin = 0;
   if ( setsize[c1] > 0 )
   {
      GINI_u32 start = rand()%setsize[c1];
      GINI_u32 startclass = rand()%classes;
      startptr = svset[c1];
      for ( i = 0; i < start; i++ )
      {
         startptr = startptr->next;
      }

      i2 = startptr->dataind;
      // Now iterate from this random point.
      while (( startptr != (GINI_Set*) GINI_NULL ) && 
             ( srchwin < maxsvsrch ) &&
	     ( srchwin < setsize[c1]))
      {
         if ( g11 - startptr->E  > 0 ) 
         {
            // a11 will most probably decrease so make sure that
            // a21 is not at bounds
	    if ( _getdirection(startptr->dataind,c1) == GINI_UP_DOWN )
            {
               // Select the class with the maximum value of
               // E22.
               c2 = 0;
               evalue = -9999999;
               found = GINI_FALSE;
               for ( i = startclass; i < classes; i++ )
               {
                  if (( (currptr = svmap[startptr->dataind][i]) != (GINI_Set*) GINI_NULL ) &&
	              ( svmap[i1][i] != (GINI_Set*) GINI_NULL ) &&
                      ( i != c1 ) &&
		      (_getdirection(i1,i) == GINI_UP_DOWN))
                  {
                     if ( currptr->shrinklevel == 0)
                     {
                        if ( evalue < currptr->E)
                        {
                           evalue = currptr->E;
	                   c2 = i;
			   i2 = currptr->dataind;
			   found = GINI_TRUE;
                        }
                     }
                  }
               }
            }
         }
         else
         {
            // a11 will most probably increase so make sure that
            // a21 is not at bounds
	    if ( dir == GINI_UP_DOWN )
            {
               // Select the class with the minimum value of
               // E22.
               c2 = 0;
               evalue = 99999;
               found = GINI_FALSE;
               for ( i = startclass; i < classes; i++ )
               {
                  if (( (currptr = svmap[startptr->dataind][i]) != (GINI_Set*) GINI_NULL ) &&
                      ( i != c1 ) &&
		      ( svmap[i1][i] != (GINI_Set*) GINI_NULL ) &&
		      (_getdirection(startptr->dataind,i) == GINI_UP_DOWN ))
                  {
                     if ( currptr->shrinklevel == 0)
                     {
                        if ( evalue > currptr->E)
                        {
                           evalue = currptr->E;
	                   c2 = i;
			   i2 = currptr->dataind;
			   found = GINI_TRUE;
                        }
                     }
                  }
               }
            }
         }

	 if ( found == GINI_TRUE )
         {
            if ( _takestep(i1,c1,i2,c2,&g11,(GINI_double*)GINI_NULL,&startptr->E,&evalue) )
            {
               phase2++;
               return 1;
            }
         }
	 srchwin++;
	 startptr = startptr->next;
	 if ( startptr == ( GINI_Set*) GINI_NULL )
         {
            startptr = svset[c1];
         }
      }
   }

   phase4++;
   return 0;
}

*/

/*****************************************************************************/
// FUNCTION  :
// 
// DESCRIPTION :
//
// INPUT :
//
// OUTPUT :
//
//
/*****************************************************************************/
GINI_u32 GINI_SVMBlock::_examinesvExample( GINI_u32 i1 )
{
   GINI_u32 i2,c2,i,c1;
   GINI_Set *currptr, *startptr;
   GINI_bool found;
   GINI_double g11,evalue;
   GINI_status dir;

   struct timeval tv;
   struct timezone tz;
   (void) gettimeofday(&tv,&tz);

   // First evaluate the KKT condition for this data point
   // and choose the corresponding class for which its violated.
   if ( _kktsvcondition(i1,&c1,&g11,&dir) == GINI_FALSE )
   {
      timer1 += currtimeval(&tv);
      return 0;
   }
   timer1 += currtimeval(&tv);

   // We would want to select other three set of data points
   // such that