kernel.cpp

支持向量机(SVM)的VC源代码

    SVMINT new_pos=0;
    new_index[cache_size] = new_examples_size;
    while((old_pos<old_cache_size) && (new_pos < cache_size)){
      if(last_used[old_pos] > 0){
	// copy example into new cache at new_pos
	new_rows[new_pos] = new SVMFLOAT[new_examples_size];
	for(SVMINT j=0;j<new_examples_size;j++){
	  (new_rows[new_pos])[j] = (rows[old_pos])[j];
	};
	delete [](rows[old_pos]);
	new_last_used[new_pos] = last_used[old_pos];
	new_index[new_pos] = index[old_pos];
	new_pos++;
      }
      else{
	if(rows[old_pos] != 0){
	  delete [](rows[old_pos]);
	};
      };
      old_pos++;
    };
    while(new_pos < cache_size){
      new_rows[new_pos] = 0; //new SVMFLOAT[new_examples_size];
      new_last_used[new_pos] = 0;
      new_index[new_pos] = new_examples_size;
      new_pos++;
    };
    while(old_pos < old_cache_size){
      if(rows[old_pos] != 0){
	delete [](rows[old_pos]);
      };
      old_pos++;
    };
    delete []rows;
    rows = new_rows;
    delete []last_used;
    last_used = new_last_used;
    delete []index;
    index = new_index;
    examples_size = new_examples_size;
  };

};


void kernel_c::compute_row(const SVMINT i, SVMFLOAT* myrow){
  // place row i in row
  svm_example x = the_examples->get_example(i);
  svm_example y;
  for(SVMINT k=0;k<examples_size;k++){
    y = the_examples->get_example(k);
    myrow[k] = calculate_K(x,y);
  };
};


SVMFLOAT* kernel_c::get_row(const SVMINT i){
  // lookup row in cache or compute
  //    cout<<"get_row "<<i<<endl;
  SVMINT low=0;
  SVMINT high=cache_size;
  SVMINT pos=0;
  // binary search for i in [low,high]
  high = lookup(i);
  if(high==cache_size){
    pos = high-1;
  }
  else{
    pos=high;
  };
  if((index[pos] != i) || (last_used[pos] == 0)){
    // cache miss
    SVMINT k;
    if(index[pos] == i){
      low = pos;
    }
    else{
      SVMINT min_time = last_used[cache_size-1];  // empty entries are at the end
      low=cache_size-1;
      for(k=0;k<cache_size;k++){
	// search for last recently used element
	if(last_used[k] < min_time){
	  min_time = last_used[k];
	  low = k;
	};
      };
    };
    
    // delete low, calculate row i, place in high
    SVMFLOAT* a_row = rows[low];
    if(high<=low){
      for(SVMINT j=low;j>high;j--){
	rows[j] = rows[j-1];
	index[j] = index[j-1];
	last_used[j] = last_used[j-1];
      };
    }
    else{
      for(SVMINT j=low;j<high-1;j++){
	rows[j] = rows[j+1];
	index[j] = index[j+1];
	last_used[j] = last_used[j+1];
      };
      high--;
    };
    pos=high;
    if(0 == a_row){
      a_row = new SVMFLOAT[examples_size];
    };
    rows[high] = a_row;
    compute_row(i,a_row);
    index[high]=i;
  };

  counter++;
  last_used[pos] = counter;


  return(rows[pos]);
};


void kernel_c::input(istream& data_stream){
  throw read_exception("ERROR: Attempt to read in abstract kernel.");
};

void kernel_c::output(ostream& data_stream) const{
  data_stream<<"Abstract kernel"<<endl;
};

istream& operator >> (istream& data_stream, kernel_c& the_kernel){
  the_kernel.input(data_stream);
  //  throw read_exception("ERROR: Attempt to read in abstract kernel.");
  return data_stream;
};

ostream& operator << (ostream& data_stream, kernel_c& the_kernel){
  the_kernel.output(data_stream);
  //  data_stream<<"Abstract kernel"<<endl;
  return data_stream;
};


/*
 *
 * The following kernels are defined
 * - kernel_dot_c: inner product
 * - kernel_pol_c: polynomial
 * - kernel_radial_c: radial basis function
 * plus:
 * - kernel_user_c: user defined kernel 1
 * - kernel_user2_c: user defined kernel 2
 *
 */

/*
 *
 * kernel_dot_c
 *
 */
SVMFLOAT kernel_dot_c::calculate_K(const svm_example x, const svm_example y){
  SVMFLOAT result = innerproduct(x,y);
  return(result);
};

void kernel_dot_c::input(istream& data_stream){
  // read comments until next @, throw error at parameters
  char next = data_stream.peek();

  char* s = new char[MAXCHAR];
  while((! data_stream.eof()) && (next != '@')){
    if((next != '#') && (next != '\n')){
      // trying to read in parameter
      cout<<"WARNING: Parameters for dot kernel are ignored."<<endl;
    };
    data_stream.getline(s,MAXCHAR);
    next = data_stream.peek();
  };
  delete []s;
};

void kernel_dot_c::output(ostream& data_stream) const{
  data_stream<<"type dot"<<endl;
};


/*
 *
 * kernel_lin_dot_c
 *
 */
SVMFLOAT kernel_lin_dot_c::calculate_K(const svm_example x, const svm_example y){
  SVMFLOAT result = a*innerproduct(x,y)+b;
  return(result);
};


void kernel_lin_dot_c::input(istream& data_stream){
  // read comments and parameters until next @
  char next = data_stream.peek();
  a=1; 
  b=0;
  char* s = new char[MAXCHAR];
  while((! data_stream.eof()) && (next != '@')){
    if('#' == next){
      // ignore comment
      data_stream.getline(s,MAXCHAR);
    }
    else if('\n' == next){
      // ignore line-end
      next = data_stream.get();
    }
    else{
      // trying to read in parameter
      data_stream >> s;
      if(0 == strcmp("a",s)){
	data_stream >> a;
      }
      if(0 == strcmp("b",s)){
	data_stream >> b;
      }
      else{
	cout<<"Ignoring unknown parameter: "<<s<<endl;
      };
      data_stream.getline(s,MAXCHAR);
    };
    next = data_stream.peek();
  };
  delete []s;
};


void kernel_lin_dot_c::output(ostream& data_stream) const{
  data_stream<<"type dot"<<endl;
  data_stream<<"a "<<a<<endl;
  data_stream<<"b "<<b<<endl;
};


/*
 *
 * kernel_polynomial_c
 *
 */
SVMFLOAT kernel_polynomial_c::calculate_K(const svm_example x, const svm_example y){
  SVMFLOAT prod=1+innerproduct(x,y);
  SVMFLOAT result=1;
  for(SVMINT i=0;i<degree;i++) result *= prod;
  return (result);
};

void kernel_polynomial_c::input(istream& data_stream){
  // read comments and parameters until next @
  char next = data_stream.peek();
  int ok=0;
  char* s = new char[MAXCHAR];
  while((! data_stream.eof()) && (next != '@')){
    if('#' == next){
      // ignore comment
      data_stream.getline(s,MAXCHAR);
    }
    else if('\n' == next){
      // ignore line-end
      next = data_stream.get();
    }
    else{
      // trying to read in parameter
      data_stream >> s;
      if(0 == strcmp("degree",s)){
	data_stream >> degree;
	ok = 1;
      }
      else{
	cout<<"Ignoring unknown parameter: "<<s<<endl;
      };
      data_stream.getline(s,MAXCHAR);
    };
    next = data_stream.peek();
  };
  if(! ok){
    throw read_exception("The parameters did not contain a valid description of a polynomial kernel.");
  };
  delete []s;
};

void kernel_polynomial_c::output(ostream& data_stream) const{
  data_stream<<"type polynomial"<<endl;
  data_stream<<"degree "<<degree<<endl;
};

/*
 *
 * kernel_radial_c
 *
 */
SVMFLOAT kernel_radial_c::calculate_K(const svm_example x, const svm_example y){
  return exp(-gamma*norm2(x,y));
};

void kernel_radial_c::input(istream& data_stream){
  // read comments and parameters until next @
  char next = data_stream.peek();
  int ok=0;
  char* s = new char[MAXCHAR];
  while((! data_stream.eof()) && (next != '@')){
    if('#' == next){
      // ignore comment
      data_stream.getline(s,MAXCHAR);
    }
    else if('\n' == next){
      // ignore line-end
      next = data_stream.get();
    }
    else{
      // trying to read in parameter
      data_stream >> s;
      if(0 == strcmp("gamma",s)){
	data_stream >> gamma;
	ok = 1;
      }
      else{
	cout<<"Ignoring unknown parameter: "<<s<<endl;
      };
      data_stream.getline(s,MAXCHAR);
    };
    next = data_stream.peek();
  };
  if(! ok){
    throw read_exception("The parameters did not contain a valid description of a radial kernel.");
  };
  delete []s;
};

void kernel_radial_c::output(ostream& data_stream) const{
  data_stream<<"type radial"<<endl;
  data_stream<<"gamma "<<gamma<<endl;
};

/*
 *
 * kernel_neural_c
 *
 */
SVMFLOAT kernel_neural_c::calculate_K(const svm_example x, const svm_example y){
  return tanh(a*innerproduct(x,y)+b);
};

void kernel_neural_c::input(istream& data_stream){
  // read comments and parameters until next @
  char next = data_stream.peek();
  a=1; 
  b=1;
  char* s = new char[MAXCHAR];
  while((! data_stream.eof()) && (next != '@')){
    if('#' == next){
      // ignore comment
      data_stream.getline(s,MAXCHAR);
    }
    else if('\n' == next){
      // ignore line-end
      next = data_stream.get();
    }
    else{
      // trying to read in parameter
      data_stream >> s;
      if(0 == strcmp("a",s)){
	data_stream >> a;
      }
      else if(0 == strcmp("b",s)){
	data_stream >> b;
      }
      else{
	cout<<"Ignoring unknown parameter: "<<s<<endl;
      };
      data_stream.getline(s,MAXCHAR);
    };
    next = data_stream.peek();
  };
  delete []s;
};

void kernel_neural_c::output(ostream& data_stream) const{
  data_stream<<"type neural"<<endl;
  data_stream<<"a "<<a<<endl;
  data_stream<<"b "<<b<<endl;
};

/*
 *
 * kernel_anova_c
 *
 */
SVMFLOAT kernel_anova_c::calculate_K(const svm_example x, const svm_example y){
  SVMFLOAT result=0;
  SVMINT length_x = x.length;
  SVMINT length_y = y.length;
  svm_attrib* att_x = x.example;
  svm_attrib* att_y = y.example;
  SVMINT pos_x=0;
  SVMINT pos_y=0;
  SVMINT zeros=dim;
  SVMFLOAT diff;
  while((pos_x < length_x) && (pos_y < length_y)){
    if(att_x[pos_x].index == att_y[pos_y].index){
      diff = att_x[pos_x++].att-att_y[pos_y++].att;
      result += exp(-gamma*(diff*diff));
    }
    else if(att_x[pos_x].index < att_y[pos_y].index){
      diff = att_x[pos_x++].att;
      result += exp(-gamma*(diff*diff));
      pos_x++;
    }
    else{
      diff = att_y[pos_y++].att;
      result += exp(-gamma*(diff*diff));
      pos_y++;
    };
    zeros--;
  };
  result += (SVMFLOAT)zeros;
  SVMFLOAT result2=1;
  for(SVMINT i=0;i<degree;i++){
    result2 *= result;
  };
  return result2;
};

void kernel_anova_c::input(istream& data_stream){
  // read comments and parameters until next @
  char next = data_stream.peek();
  int ok_gamma=0;
  int ok_degree=0;
  char* s = new char[MAXCHAR];
  while((! data_stream.eof()) && (next != '@')){
    if('#' == next){
      // ignore comment
      data_stream.getline(s,MAXCHAR);
    }
    else if('\n' == next){
      // ignore line-end
      next = data_stream.get();
    }
    else{
      // trying to read in parameter
      data_stream >> s;
      if(0 == strcmp("gamma",s)){
	data_stream >> gamma;
	ok_gamma = 1;
      }
      else if(0 == strcmp("degree",s)){
	data_stream >> degree;
	ok_degree = 1;
      }
      else{
	cout<<"Ignoring unknown parameter: "<<s<<endl;
      };
      data_stream.getline(s,MAXCHAR);
    };
    next = data_stream.peek();
  };
  if((!ok_gamma) || (!ok_degree)){
    throw read_exception("The parameters did not contain a valid description of an anova kernel.");
  };
  delete []s;
};

void kernel_anova_c::output(ostream& data_stream) const{
  data_stream<<"type anova"<<endl;
  data_stream<<"gamma "<<gamma<<endl;