example_set.cpp

本代码是支持向量机的vc++环境下的实现

#include "stdafx.h"
#include "example_set.h"

example_set_c::example_set_c(){
  init(0,0);
};


example_set_c::example_set_c(SVMINT new_total, SVMINT new_dim){
  init(new_total,new_dim);
};



void example_set_c::init(SVMINT new_total, SVMINT new_dim){
  examples_total = 0;
  capacity=0;
  has_y = 0;
  has_alphas = 0;
  has_scale = 0;
  has_pattern_y = 1;
  b = 0;
  all_alphas = 0;
  all_ys = 0;
  // create dummy
  the_set = new svm_example[1];
  the_set[0].example = 0;
  dim=0;
  Exp = 0;
  Var = 0;
  filename = new char[MAXCHAR];
  filename[0]='\0';
  set_dim(new_dim),
  resize(capacity);
  // set default file format
  my_format.sparse = 0;
  my_format.where_x = 2;
  my_format.where_y = 1;
  my_format.where_alpha = 0;
  my_format.delimiter = ' ';
}; 


example_set_c::~example_set_c(){
  delete []filename;
  clear();
  if(the_set) delete []the_set;
};


void example_set_c::set_format(example_format new_format){
  my_format = new_format;
};


void example_set_c::set_filename(char* new_filename){
  strcpy(filename,new_filename);
};

 
void example_set_c::clear(){
  if(all_alphas){
    delete []all_alphas;
    all_alphas=0;
  };
  if(all_ys){
    delete []all_ys;
    all_ys=0;
  };
  if(the_set){
    SVMINT i;
    SVMINT c;
    for(i=0;i<capacity;i++){
      if(the_set[i].example != 0){

	for(c=0;c<the_set[i].length;c++){
	  (((the_set[i]).example)[c]).index=28;
	  (((the_set[i]).example)[c]).att = 4;
	};

	delete [](the_set[i].example); 
	the_set[i].example=0;
      };
    };
    delete []the_set;
  };
  if(Exp) delete []Exp;
  if(Var) delete []Var;
  Exp = 0;
  Var = 0;
  the_set = new svm_example[1];
  the_set[0].example = 0;
  dim = 0;
  b = 0;
  examples_total = 0;
  capacity = 0;
  has_y = 0;
  has_alphas = 0;
  has_scale = 0;
};  


SVMINT example_set_c::size(){
  return examples_total;
};


SVMINT example_set_c::size_pos(){
  SVMINT i;
  SVMINT count=0;
  for(i=0;i<capacity;i++){
    if(the_set[i].y > 0){
      count++;
    };
  };
  return count;
};


SVMINT example_set_c::size_neg(){
  SVMINT i;
  SVMINT count=0;
  for(i=0;i<capacity;i++){
    if(the_set[i].y < 0){
      count++;
    };
  };
  return count;
};


void example_set_c::set_dim(SVMINT new_dim){
  if(new_dim<dim){
    throw general_exception("ERROR: Trying to decrease dimension of examples");
  };                                                                            
  dim = new_dim;
  if(Exp) delete []Exp;
  if(Var) delete []Var;
  Exp = 0;
  Var = 0;
};


SVMINT example_set_c::get_dim(){
  return dim;
};


void example_set_c::resize(SVMINT new_total){
  svm_example* new_set = 0;
  SVMINT i;
  if(new_total > capacity){
    // add new space to set
    new_set = new svm_example[new_total];
    // copy old values
    for(i=0;i<capacity;i++){
      new_set[i] = the_set[i];
    };
    for(i=capacity;i<new_total;i++){
      new_set[i].example = 0;
      new_set[i].length = 0;
    };
    delete []the_set;
    the_set=new_set;
    capacity = new_total;
    if(all_alphas != 0){
      delete []all_alphas;
      all_alphas = 0;
    };
    if(all_ys != 0){
      delete []all_ys;
      all_ys = 0;
    };
  }
  else if(new_total < capacity){
    new_set = new svm_example[new_total];
    // copy remaining values
    for(i=0;i<new_total;i++){
      new_set[i] = the_set[i];
    };
    // delete obsolete values
    for(i=new_total;i<capacity;i++){
      if(the_set[i].example != 0){
	delete [](the_set[i].example); 
	the_set[i].example = 0;
	examples_total--;
      };
    };
    delete []the_set;
    the_set=new_set;
    capacity = new_total;

    if(all_alphas != 0){
      delete []all_alphas;
      all_alphas = 0;
    };
    if(all_ys != 0){
      delete []all_ys;
      all_ys = 0;
    };
  };
};


void example_set_c::swap(SVMINT i, SVMINT j){
  svm_example ex_dummy;
  SVMFLOAT dummy;
  ex_dummy=the_set[i];
  the_set[i] = the_set[j];
  the_set[j] = ex_dummy;
  if(all_alphas != 0){
    dummy=all_alphas[i];
    all_alphas[i] = all_alphas[j];
    all_alphas[j] = dummy;
  };
  if(all_ys != 0){
    dummy = all_ys[i];
    all_ys[i] = all_ys[j];
    all_ys[j] = dummy;
  };
};


void example_set_c::put_example(const SVMINT pos, const SVMFLOAT* example){
  // examples is SVMFLOAT-array 1..dim

  SVMINT non_zero=0;
  svm_attrib* new_att;
  SVMINT i;
  for(i=0;i<dim;i++){
    if(0 != example[i]){
      non_zero++;
    };
  };
  if(pos>=capacity){
    // make set bigger
    resize(2*capacity+1);
  };
  if(0 == the_set[pos].example){
    // add new example, reserve space for y and alpha
    examples_total++;
  }
  else{
    delete [](the_set[pos].example);
    the_set[pos].example = 0;
  };
  new_att = new svm_attrib[non_zero];
  the_set[pos].example = new_att;
  // add attributes
  SVMINT j=0;
  for(i=0;i<non_zero;i++){
    while(0 == example[j]) j++;
    new_att[i].att = example[j];
    new_att[i].index=j;
    j++;
  };
  the_set[pos].y = example[dim];
  the_set[pos].alpha = example[dim+1];
  the_set[pos].length = non_zero;
  if(all_alphas != 0){
    all_alphas[pos] = the_set[pos].alpha;
  };
  if(all_ys != 0){
    all_ys[pos]=the_set[pos].y;
  };
  if((the_set[pos].y != 1) && (the_set[pos].y != -1)){
    has_pattern_y = 0;
  };
};


void example_set_c::put_example(const SVMFLOAT* example){
  put_example(examples_total,example);
};


void example_set_c::put_example(const SVMINT pos, const svm_example example){
  if(pos>=capacity){
    // make set bigger
    resize(2*capacity+1);
  };
  if(the_set[pos].example != 0){
    // overwrite old
    delete [](the_set[pos].example);
    the_set[pos].example = 0;
  }
  else{
    examples_total++;
  };
  the_set[pos].length = example.length;
  svm_attrib* new_att = new svm_attrib[example.length];
  SVMINT i;
  for(i=0;i<example.length;i++){
    new_att[i] = example.example[i];
  };
  the_set[pos].example = new_att;
  the_set[pos].y = example.y;
  the_set[pos].alpha = example.alpha;
  if(all_alphas != 0){
    all_alphas[pos] = the_set[pos].alpha;
  };
  if(all_ys != 0){
    all_ys[pos] = the_set[pos].y;
  };
  if((the_set[pos].y != 1) && (the_set[pos].y != -1)){
    has_pattern_y = 0;
  };
};


void example_set_c::put_example(const svm_example example){
  put_example(examples_total,example);
};


svm_example example_set_c::get_example(const SVMINT pos){
  return the_set[pos];
};


void example_set_c::put_y(const SVMINT pos, const SVMFLOAT y){
  the_set[pos].y = y;
  if(all_ys != 0){
    all_ys[pos] = y;
  };
  if((y != 1) && (y != -1)){
    has_pattern_y = 0;
  };
};


SVMFLOAT example_set_c::get_y(const SVMINT pos){
  return (the_set[pos].y);
};


void example_set_c::put_alpha(const SVMINT pos, const SVMFLOAT alpha){
  the_set[pos].alpha = alpha;
  if(all_alphas != 0){
    all_alphas[pos] = alpha;
  };
};


SVMFLOAT example_set_c::get_alpha(const SVMINT pos){
  return (the_set[pos].alpha);
};


void example_set_c::put_b(const SVMFLOAT new_b){
  b=new_b;
};


SVMFLOAT example_set_c::get_b(){
  return b;
};


SVMFLOAT* example_set_c::get_alphas(){
  if(0 == all_alphas){
    SVMINT the_size = size();
    all_alphas = new SVMFLOAT[the_size];
    SVMINT i;
    for(i=0; i<the_size; i++){
      all_alphas[i] = get_alpha(i);
    };
  };
  return all_alphas;
};


SVMFLOAT* example_set_c::get_ys(){
  if(0 == all_ys){
    SVMINT the_size = size();
    all_ys = new SVMFLOAT[the_size];
    SVMINT i;
    for(i=0; i<the_size; i++){
      all_ys[i] = get_y(i);
    };
  };
  return all_ys;
};


void example_set_c::compress(){
  // remove zeros out of examples
  SVMINT next=0;
  SVMINT i=0;
  for(i=0;i<capacity;i++){
    if(the_set[i].example != 0){
      the_set[next] = the_set[i];
      if(next != i){
	the_set[i].example = 0;
	the_set[i].length = 0;
      };
      next++;
    };
  };
  resize(next);
};


void example_set_c::scale_alphas(const SVMFLOAT factor){
  // set alpha -> factor*alpha
  SVMINT i;
  for(i=0;i<capacity;i++){
    put_alpha(i,factor*get_alpha(i));
  };
  if(all_alphas){
    for(i=0;i<capacity;i++){
      all_alphas[i] = get_alpha(i);
    };
  };
};


SVMFLOAT example_set_c::get_y_var(){
  if(0 != Var ){
    if(0 != Var[dim]){
      return  Var[dim];
    };
  };
  return 1;
};

void example_set_c::scale(){
  scale(1);
};


void example_set_c::scale(int scale_y){
  if(examples_total == 0) return;

  if(Exp == 0) Exp = new SVMFLOAT[dim+1];
  if(Var == 0) Var = new SVMFLOAT[dim+1];

  SVMINT i;

  // calculate Exp and Var 
  for(i=0;i<=dim;i++){
    Exp[i] = 0;
    Var[i] = 0;
  };
  SVMINT pos;
  svm_attrib the_att;
  for(pos=0;pos<capacity;pos++){
    for(i=0;i<the_set[pos].length;i++){
      the_att = (the_set[pos].example)[i];
      Exp[the_att.index] += the_att.att;
      Var[the_att.index] += the_att.att*the_att.att;
    };
    Exp[dim] += the_set[pos].y;
    Var[dim] += the_set[pos].y*the_set[pos].y;
  };
  for(i=0;i<=dim;i++){
    Exp[i] /= examples_total;
    Var[i] = (Var[i]-examples_total*Exp[i]*Exp[i])/(examples_total-1);
    if(Var[i] > 0){
      Var[i] = sqrt(Var[i]);
    }
    else{
      // numerical error
      Var[i] = 0;
    };
  };
  if(! scale_y){
    Exp[dim] = 0;
    Var[dim] = 0;
  };

  do_scale();

};


void example_set_c::do_scale(){
  // scale
  // precondition: Exp and Var are set.
  SVMINT i;
  SVMINT j=0;
  SVMINT k;
  //  SVMINT length;
  SVMINT nonzero=0;
  SVMINT pos;
  for(i=0;i<dim;i++){
    if(Var[i] != 0) nonzero++;
  };
  for(pos=0;pos<capacity;pos++){
    //    length = the_set[pos].length;

    // put zeros into vector, they might be scaled, kick constant atts out
    svm_attrib* new_example = new svm_attrib[nonzero];
    j = 0; // index in new vector
    k = 0; // index in old vector
    i=0;
    while((i<dim) && (j < nonzero)){
      if((k < the_set[pos].length) && (((the_set[pos].example)[k]).index < i)){
	k++;
      };
      if(Var[i] != 0){
	new_example[j].index = i;
	if(((the_set[pos].example)[k]).index == i){
	  new_example[j].att = ((the_set[pos].example)[k]).att;
	}
	else{
	  new_example[j].att = 0;
	};
	j++;
      };
      i++;
    };
    
    //    length = nonzero;
    the_set[pos].length = nonzero;
    delete []the_set[pos].example;
    the_set[pos].example = new_example;

    for(i=0;i<the_set[pos].length;i++){
      j = ((the_set[pos].example)[i]).index;
      if(0 != Var[j]){
	((the_set[pos].example)[i]).att = (((the_set[pos].example)[i]).att - Exp[j])/Var[j];
      }
      else{
	// shouldn't happen!
	((the_set[pos].example)[i]).att = 0; //  x - Exp = 0
      };
    };
    if(0 != Var[dim]){
      the_set[pos].y = (the_set[pos].y-Exp[dim])/Var[dim];
    }
    else{
      the_set[pos].y -= Exp[dim]; // don't know if to scale ys, so Exp could be 0 or y
    };

  };

  has_scale = 1;
};


void example_set_c::put_Exp_Var(SVMFLOAT *newExp, SVMFLOAT* newVar){
  // precondition: dim is ok

  if((newExp == 0) || (newVar == 0)){ return; };

  if(Exp==0) Exp = new SVMFLOAT[dim+1];
  if(Var==0) Var = new SVMFLOAT[dim+1];

  SVMINT i;

  for(i=0;i<=dim;i++){
    Exp[i] = newExp[i];
    Var[i] = newVar[i];
  };
};


void example_set_c::scale(SVMFLOAT *theconst, SVMFLOAT *thefactor,SVMINT scaledim){
  if((theconst == 0) || (thefactor == 0)) return;

  if(scaledim>dim) set_dim(scaledim);

  if(Exp==0) Exp = new SVMFLOAT[dim+1];
  if(Var==0) Var = new SVMFLOAT[dim+1];

  SVMINT i;

  for(i=0;i<scaledim;i++){
    Exp[i] = theconst[i];
    Var[i] = thefactor[i];
  };
  for(i=scaledim;i<dim;i++){
    Exp[i] = 0;
    Var[i] = 0;
  };
  Exp[dim] = theconst[scaledim];
  Var[dim] = thefactor[scaledim];

  do_scale();
};


SVMFLOAT example_set_c::unscale_y(const SVMFLOAT scaled_y){
  if((0 == Exp) || (0 == Var)){
    return scaled_y;
  }
  else if(0 == Var[dim]){
    return scaled_y+Exp[dim];
  }
  else{
    return (scaled_y*Var[dim]+Exp[dim]);
  };
};


void example_set_c::permute(){
  // permute the examples
  //  srand((unsigned int)time(0));
  svm_example dummy;
  SVMINT swap_pos;

  SVMINT pos;
  for(pos=0;pos<capacity-1;pos++){
    swap_pos = (SVMINT)((SVMFLOAT)(pos+1)*rand()/(RAND_MAX+1.0));
    dummy = the_set[swap_pos];
    the_set[swap_pos] = the_set[pos];
    the_set[pos] = dummy;
  };
  SVMINT i;
  SVMINT the_size;
  if(all_alphas != 0){
    the_size = size();
    for(i=0;i<the_size;i++){
      all_alphas[i] = get_alpha(i);
    };
  };
  if(all_ys != 0){
    the_size = size();
    for(i=0;i<the_size;i++){
      all_ys[i] = get_y(i);
    };
  };
};


void example_set_c::clear_alpha(){