kernel.cpp

介绍支持向量机SVM介绍的参考文献以及程序源代码

/*
 *
 * kernel_exponential_c
 *
 */ 
SVMFLOAT kernel_exponential_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 i=0;
  SVMFLOAT mylambda=1;
  while((pos_x < length_x) && (pos_y < length_y)){
    if(att_x[pos_x].index == att_y[pos_y].index){
      for(;i<att_x[pos_x].index;i++) mylambda *= lambda;
      result += mylambda*att_x[pos_x++].att*att_y[pos_y++].att;
    }
    else if(att_x[pos_x].index < att_y[pos_y].index){
      pos_x++;
    }
    else{
      pos_y++;
    };
  };
  return result;
};

void kernel_exponential_c::input(istream& data_stream){
  // read comments and parameters until next @
  char next = data_stream.peek();
  if(next == EOF){ 
    // set stream to eof
    next = data_stream.get(); 
  };
  int ok_lambda=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("lambda",s)){
	data_stream >> lambda;
	ok_lambda = 1;
      }
      else{
	cout<<"Ignoring unknown parameter: "<<s<<endl;
      };
      data_stream.getline(s,MAXCHAR);
    };
    next = data_stream.peek();
    if(next == EOF){ 
      // set stream to eof
      next = data_stream.get(); 
    };
  };
  if(!ok_lambda){
    throw read_exception("The parameters did not contain a valid description of an exponential kernel.");
  };
  delete []s;
};

void kernel_exponential_c::output(ostream& data_stream) const{
  data_stream<<"type exponential"<<endl;
  data_stream<<"lambda "<<lambda<<endl;
};


/*
 *
 *
 * kernel_aggregation_c : kernels, that consist of some other kernels
 *
 */

kernel_aggregation_c::kernel_aggregation_c(){
  number_elements = 0;
  elements = 0;
  from = 0;
  to = 0;
  new_x.example = 0;
  new_y.example = 0;
};


kernel_aggregation_c::~kernel_aggregation_c(){
  if(number_elements > 0){
    delete []elements;
    elements = 0;
    delete []from;
    from = 0;
    delete[] to;
    to = 0;
    number_elements = 0;
  };
  if(new_x.example){ delete []new_x.example; };
  if(new_y.example){ delete []new_y.example; };
};


void kernel_aggregation_c::init(SVMINT new_cache_MB,example_set_c* new_examples){
  kernel_c::init(new_cache_MB,new_examples);
  SVMINT i;
  for(i=0;i<number_elements;i++){
    (elements[i])->init(0,new_examples);
    (elements[i])->dim = to[i]-from[i];
  };
  new_x.example = new svm_attrib[dim];
  new_y.example = new svm_attrib[dim];
};


void kernel_aggregation_c::input(istream& data_stream){
  // read comments and parameters until next @
  // WARNING: no checks of the input values are performed
  char next = data_stream.peek();
  if(next == EOF){ 
    // set stream to eof
    next = data_stream.get(); 
  };
  char* s = new char[MAXCHAR];
  SVMINT parts_read=0;
  while((! data_stream.eof()) && (next != '@')){
    if('#' == next){
      // ignore comment
      data_stream.getline(s,MAXCHAR);
    }
    else if(('\n' == next) ||
	    (' ' == next) ||
	    ('\r' == next) ||
	    ('\f' == next) ||
	    ('\t' == next)){
      // ignore line-end
      next = data_stream.get();
    }
    else{
      // trying to read in parameter
      data_stream >> s;
      if(0 == strcmp("number_parts",s)){
	if(number_elements>0){
	  throw read_exception("Parameter 'number_parts' cannot be defined twice.");
	};
	data_stream >> number_elements;
	if(number_elements<=0){
	  throw read_exception("Invalid value for parameter 'number_parts'.");
	};
	elements = new kernel_c*[number_elements];
	from = new SVMINT[number_elements];
	to = new SVMINT[number_elements];
      }
      else if(0==strcmp("range",s)){
	if(parts_read<number_elements){
	  data_stream >> from[parts_read];
	  from[parts_read]--;
	  data_stream >> to[parts_read];
	  parts_read++;
	}
	else{
	  throw read_exception("too much ranges defined in aggregation kernel or 'number_parts' not given.");
	};
      }
      else{
	throw read_exception("Unknown parameter in aggregation kernel.");
      };
      data_stream.getline(s,MAXCHAR); // ignore rest of line
    };
    next = data_stream.peek();
    if(next == EOF){ 
      // set stream to eof
      next = data_stream.get(); 
    };
  };
  if(!data_stream.eof()){
    kernel_container_c cont;
    SVMINT i;
    for(i=0;i<number_elements;i++){
      // next line should be "@kernel"
      data_stream >> s;
      if(0==strcmp("@kernel",s)){
	data_stream.getline(s,MAXCHAR); // ignore rest of line
	data_stream >> cont;
	elements[i] = cont.get_kernel();
	cont.clear();
      }
      else{
	throw read_exception("Could not find enough kernel parts for aggregation kernel.");
      };
    };
  };
  delete []s;
};


void kernel_aggregation_c::output_aggregation(ostream& data_stream) const{
  data_stream<<"number_parts "<<number_elements<<endl;
  SVMINT i;
  for(i=0;i<number_elements;i++){
    data_stream<<"range "
	       <<(from[i]+1)  // inner format: [from,to[, starting at 0
                              // io format:    [from,to], starting at 1
	       <<" "<<to[i]<<endl;
  };
  for(i=0;i<number_elements;i++){
    data_stream<<"@kernel"<<endl
	       <<"# "<<(i+1)<<". part of aggregation kernel"<<endl;
    (elements[i])->output(data_stream);
  };
};


void kernel_aggregation_c::output(ostream& data_stream)const{
  data_stream<<"type aggregation"<<endl;
  output_aggregation(data_stream);
};


SVMFLOAT kernel_aggregation_c::calculate_K(const svm_example x, const svm_example y){
  SVMFLOAT result=0;
  //  svm_example  new_x = x;
  //  svm_example new_y = y;
  SVMINT start;
  SVMINT stop;
  SVMINT count;

  for(SVMINT i=0;i<number_elements;i++){
    // find matching part of x and y
    start=0;
    while((start<x.length) && (((x.example)[start]).index < from[i])){
      start++;
    };
    //    new_x.example = x.example + start;
    stop=start;
    count=0;
    while((stop<x.length) && (((x.example)[stop]).index < to[i])){
      (new_x.example)[count] = (x.example)[stop];
      ((new_x.example)[count]).index -= from[i]; 
      //      cout<<"x: "<<((new_x.example)[count]).index<<" --> "<<((new_x.example)[count]).att<<endl;
      count++;
      stop++;
    };
    new_x.length = stop-start;
    start=0;
    while((start<y.length) && (((y.example)[start]).index < from[i])){
      start++;
    };
    //    new_y.example = y.example + start;
    stop=start;
    count=0;
    while((stop<y.length) && (((y.example)[stop]).index < to[i])){
      (new_y.example)[count] = (y.example)[stop];
      ((new_y.example)[count]).index -= from[i]; 
      //      cout<<"y: "<<((new_y.example)[count]).index<<" --> "<<((new_y.example)[count]).att<<endl;
      count++;
      stop++;
    };
    new_y.length = stop-start;

    // default ist sum-kernel
    result += (elements[i])->calculate_K(new_x,new_y);
  };
  //  exit(1);
  return result;
};

/*
 *
 *
 * kernel_prod_aggregation_c : kernel, that consist of the 
 *                             prodcut of some other kernels
 *
 */

kernel_prod_aggregation_c::kernel_prod_aggregation_c(){
  number_elements = 0;
  elements = 0;
  from = 0;
  to = 0;
  new_x.example = 0;
  new_y.example = 0;
};


kernel_prod_aggregation_c::~kernel_prod_aggregation_c(){
  if(number_elements > 0){
    delete []elements;
    elements = 0;
    delete []from;
    from = 0;
    delete[] to;
    to = 0;
    number_elements = 0;
  };
  if(new_x.example){ delete []new_x.example; };
  if(new_y.example){ delete []new_y.example; };
};


void kernel_prod_aggregation_c::output(ostream& data_stream)const{
  data_stream<<"type prod_aggregation"<<endl;
  output_aggregation(data_stream);
};


SVMFLOAT kernel_prod_aggregation_c::calculate_K(const svm_example x, const svm_example y){
  SVMFLOAT result=1;
  //  svm_example new_x = x;
  //  svm_example new_y = y;
  SVMINT start;
  SVMINT stop;
  SVMINT count;
  SVMINT i;
  for(i=0;i<number_elements;i++){
    // find matching part of x and y
    start=0;
    while((start<x.length) && (((x.example)[start]).index < from[i])){
      start++;
    };
    //    new_x.example = x.example + start;
    stop=start;
    count=0;
    while((stop<x.length) && (((x.example)[stop]).index < to[i])){
      (new_x.example)[count] = (x.example)[stop];
      ((new_x.example)[count]).index -= from[i]; 
      count++;
      stop++;
    };
    new_x.length = stop-start;
    start=0;
    while((start<y.length) && (((y.example)[start]).index < from[i])){
      start++;
    };
    //    new_y.example = y.example + start;
    stop=start;
    count = 0;
    while((stop<y.length) && (((y.example)[stop]).index < to[i])){
      (new_y.example)[count] = (y.example)[stop];
      ((new_y.example)[count]).index -= from[i]; 
      count++;
      stop++;
    };
    new_y.length = stop-start;

    // default ist sum-kernel
    result *= (elements[i])->calculate_K(new_x,new_y);

  };
  return result;
};


/*
 *
 * kernel_fourier_c: Kernel generating fourier expansions
 *
 */

kernel_fourier_c::kernel_fourier_c(){
  N = 1;
};


void kernel_fourier_c::input(istream& data_stream){
    // read comments and parameters until next @
  char next = data_stream.peek();
  if(next == EOF){ 
    // set stream to eof
    next = data_stream.get(); 
  };
  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("n",s)) || 
	 (0 == strcmp("N",s))){
	data_stream >> N;
	ok = 1;
      }
      else{
	cout<<"Ignoring unknown parameter: "<<s<<endl;
      };
      data_stream.getline(s,MAXCHAR);
    };
    next = data_stream.peek();
    if(next == EOF){ 
      // set stream to eof
      next = data_stream.get(); 
    };
  };
  if(! ok){
    throw read_exception("The parameters did not contain a valid description of a fourier kernel.");
  };
  delete []s;
};


void kernel_fourier_c::output(ostream& data_stream) const{
  data_stream<<"type fourier"<<endl;
  data_stream<<"N "<<N<<endl;
};
  

SVMFLOAT kernel_fourier_c::calculate_K(const svm_example x, const svm_example y){
  SVMFLOAT result=1;  
  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;
  SVMFLOAT dummy;
  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;
    }
    else if(att_x[pos_x].index < att_y[pos_y].index){
      diff = att_x[pos_x++].att;
    }
    else{
      diff = -att_y[pos_y++].att;
    };
    dummy = sin(diff/2);
    if(0 == dummy){
      dummy = 1/2+(SVMFLOAT)N;
    }
    else{
      dummy = sin((2*(SVMFLOAT)N+1)/2*diff) / dummy;
    };
    result *= dummy;
    zeros--;
  };
  SVMINT i;
  for(i=0;i<zeros;i++){
    result *=  1/2+(SVMFLOAT)N;
  };
  return result;
};


/*
 *
 * kernel_reg_fourier_c: Kernel generating regularized fourier expansions
 *
 */

kernel_reg_fourier_c::kernel_reg_fourier_c(){
  q = 0.5;
};


void kernel_reg_fourier_c::input(istream& data_stream){
    // read comments and parameters until next @
  char next = data_stream.peek();
  if(next == EOF){ 
    // set stream to eof
    next = data_stream.get(); 
  };
  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("q",s)) || 
	 (0 == strcmp("Q",s))){
	data_stream >> q;
	if((q>0) && (q<1)){
	  ok = 1;
	};
      }
      else{
	cout<<"Ignoring unknown parameter: "<<s<<endl;
      };
      data_stream.getline(s,MAXCHAR);
    };
    next = data_stream.peek();
    if(next == EOF){ 
      // set stream to eof
      next = data_stream.get(); 
    };
  };
  if(! ok){
    throw read_exception("The parameters did not contain a valid description of a regularized fourier kernel.");
  };
  delete []s;
};


void kernel_reg_fourier_c::output(ostream& data_stream) const{
  data_stream<<"type reg_fourier"<<endl;
  data_stream<<"q "<<q<<endl;
};
  

SVMFLOAT kernel_reg_fourier_c::calculate_K(const svm_example x, const svm_example y){
  SVMFLOAT result=1;  
  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;
  SVMFLOAT q2 = q*q;
  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;