svm.java

一个很好的LIBSVM的JAVA源码。对于要研究和改进SVM算法的学者。可以参考。来自数据挖掘工具YALE工具包。

/*
 *  YALE - Yet Another Learning Environment
 *  Copyright (C) 2001-2004
 *      Simon Fischer, Ralf Klinkenberg, Ingo Mierswa, 
 *          Katharina Morik, Oliver Ritthoff
 *      Artificial Intelligence Unit
 *      Computer Science Department
 *      University of Dortmund
 *      44221 Dortmund,  Germany
 *  email: [e-mail]
 *  web:   http://yale.cs.uni-dortmund.de/
 *
 *  This program is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU General Public License as 
 *  published by the Free Software Foundation; either version 2 of the
 *  License, or (at your option) any later version. 
 *
 *  This program is distributed in the hope that it will be useful, but
 *  WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 *  General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
 *  USA.
 */
package edu.udo.cs.mySVM.SVM;

import edu.udo.cs.mySVM.Optimizer.*;
import edu.udo.cs.mySVM.Examples.*;
import edu.udo.cs.mySVM.Kernel.*;
import edu.udo.cs.mySVM.Util.*;

import edu.udo.cs.yale.operator.Operator;
import edu.udo.cs.yale.tools.LogService;

import java.lang.Integer;
import java.lang.Double;
import java.util.Random;
import java.lang.Math;

/**
 * Abstract base class for all SVMs
 * @author Stefan R?ping, Ingo Mierswa (only Yale additions)
 * @version $Id: SVM.java,v 1.12 2004/08/27 11:57:30 ingomierswa Exp $
 */
public abstract class SVM implements SVMInterface {
    
    private static final int[] YALE_VERBOSITY = { LogService.STATUS, LogService.TASK, LogService.TASK, 
						  LogService.MINIMUM, LogService.MINIMUM };

    protected Kernel the_kernel;
    protected ExampleSet the_examples;
    double[] alphas;
    double[] ys;

    protected int examples_total;
    //protected int verbosity;
    protected int target_count;
    protected double convergence_epsilon = 1e-3;
    protected double lambda_factor;
    protected int[] at_bound;
    protected double[] sum;
    protected boolean[] which_alpha;
    protected int[] working_set;
    protected double[] primal;
    protected double sum_alpha;
    protected double lambda_eq;

    protected int to_shrink;
    protected double feasible_epsilon;
    protected double lambda_WS;
    protected boolean quadraticLossPos = false;
    protected boolean quadraticLossNeg = false;
    boolean shrinked;

    protected double epsilon_pos = 0.0d;
    protected double epsilon_neg = 0.0d;

    private int max_iterations = 100000;
    protected int working_set_size = 10;
    protected int parameters_working_set_size = 10; // was set in parameters
    protected double is_zero = 1e-10;
    protected int shrink_const = 50;
    protected double C = 0.0d;
    protected double Cpos = 1.0d;
    protected double Cneg = 1.0d;
    protected double descend = 1e-15;

    MinHeap heap_min;
    MaxHeap heap_max;

    protected quadraticProblem qp;

    //private Operator paramOperator;

    public SVM() {
    }

    /**
     * class constructor
     */
    public SVM(Operator paramOperator, Kernel new_kernel, ExampleSet new_examples) {
	the_examples = new_examples;
	max_iterations = paramOperator.getParameterAsInt("max_iterations");
	convergence_epsilon = paramOperator.getParameterAsDouble("convergence_epsilon");
	quadraticLossPos = paramOperator.getParameterAsBoolean("quadratic_loss_pos");
	quadraticLossNeg = paramOperator.getParameterAsBoolean("quadratic_loss_neg");

	C = paramOperator.getParameterAsDouble("C");
	Cpos = paramOperator.getParameterAsDouble("L_pos");
	Cneg = paramOperator.getParameterAsDouble("L_neg");

	double epsilonValue = paramOperator.getParameterAsDouble("epsilon");
	if (epsilonValue != -1) {
	    epsilon_pos = epsilon_neg = epsilonValue;
	} else {
	    epsilon_pos = paramOperator.getParameterAsDouble("epsilon+");
	    epsilon_neg = paramOperator.getParameterAsDouble("epsilon-");
	}

	if (paramOperator.getParameterAsBoolean("balance_cost")) {
	    Cpos *= ((double)the_examples.count_pos_examples())/((double)the_examples.count_examples());
	    Cneg *= ((double)(the_examples.count_examples()-the_examples.count_pos_examples()))/((double)the_examples.count_examples());
	}
	
	// init(new_kernel, the_examples);
    };

    
    /**
     * Init the SVM
     * @param new_kernel new kernel function.
     * @param new_examples the data container
     */
    public void init(Kernel new_kernel, ExampleSet new_examples) {
	the_kernel = new_kernel;
	the_examples = new_examples;
	examples_total = the_examples.count_examples();
	parameters_working_set_size = working_set_size;

	if(C <= 0.0d){
	    C = 0.0d;
	    for(int i=0;i<examples_total;i++){
		C += the_kernel.calculate_K(i,i);
	    };
	    C = examples_total/C;
	    logln(3,"C set to "+C);
	}
	Cpos *= C;
	Cneg *= C;

	lambda_factor = 1.0;
	lambda_eq=0;
	target_count=0;
	sum_alpha = 0;
	feasible_epsilon = convergence_epsilon;

	alphas = the_examples.get_alphas();
	ys =  the_examples.get_ys();
    };
        

    /**
     * Train the SVM
     */
    public void train()
    {
	if(examples_total <= 0){
	    // exception?
	    the_examples.set_b(Double.NaN);
	    return;
	}
	if(examples_total == 1){
	    the_examples.set_b(ys[0]);
	    return;
	}
	target_count = 0;
	shrinked = false;
	init_optimizer();
	init_working_set();
	int iteration = 0;
	boolean converged=false;
      M:while(iteration < max_iterations){
	    iteration++;
	    logln(4,"optimizer iteration "+iteration);
	    //log(3,".");
	    optimize(); 
	    put_optimizer_values();
	    converged = convergence();
	    if(converged){
		logln(3,"");  // dots
		project_to_constraint();

		if(shrinked){
		    // check convergence for all alphas  
		    logln(2,"***** Checking convergence for all variables");
      		    reset_shrinked();
		    converged = convergence();
		};
		
		if(converged){
		    logln(1,"*** Convergence");
		    break M;
		};
		
		// set variables free again
		shrink_const += 10;
		target_count = 0;
		for(int i=0;i<examples_total;i++){
		    at_bound[i]=0;
		};
	    };
	    shrink();
	    calculate_working_set();
	    update_working_set();

//        int shrinked=0;
//        int upper_bound=0;
//        int lower_bound=0;

//        for(int i=0;i<examples_total;i++){
//          if(at_bound[i] > 0){
//            shrinked++;
//          };
//          if(Math.abs(alphas[i]) < is_zero){
//            lower_bound++;
//          }
//          else if((alphas[i]-Cneg>-is_zero) || (alphas[i]+Cpos<is_zero)){
//            upper_bound++;
//          };
//        };
//        System.out.println(examples_total+" variables total, "
//  			 +lower_bound+" variables at lower bound, "
//  			 +upper_bound+" variables at upper bound, "
//  			 +shrinked+" variables shrinked, "
//  			 +to_shrink+" to shrink");


	};

	int i;
	if((iteration >= max_iterations) && (! converged)){
	  logln(1,"*** No convergence: Time up.");
	  if(shrinked){
	    // set sums for all variables for statistics
	    reset_shrinked();
	  };
	};
	
	// calculate b
	double new_b=0;
	int new_b_count=0;
	for(i=0;i<examples_total;i++){
	  if((alphas[i]-Cneg < -is_zero) && 
	     (alphas[i] > is_zero)){
	    new_b += ys[i] - sum[i]-epsilon_neg;
	    new_b_count++;
	  }
	  else if((alphas[i]+Cpos > is_zero) && 
		  (alphas[i] < -is_zero)){
	    new_b += ys[i] - sum[i]+epsilon_pos;
	    new_b_count++;
	  };
	};
	
	if(new_b_count>0){
	  the_examples.set_b(new_b/((double)new_b_count));
	}
	else{
	  // unlikely
	  for(i=0;i<examples_total;i++){
	    if((alphas[i]<is_zero) && 
	       (alphas[i]>-is_zero)) {
	      new_b += ys[i] - sum[i];
	      new_b_count++;
	    };
	  };
	  if(new_b_count>0){
	    the_examples.set_b(new_b/((double)new_b_count));
	  }
	  else{
	    // even unlikelier
	    for(i=0;i<examples_total;i++){
	      new_b += ys[i] - sum[i];
	      new_b_count++;
	    };
	    the_examples.set_b(new_b/((double)new_b_count));
	  };
	};
	
	//if(verbosity>= 2){
	logln(2,"Done training: "+iteration+" iterations.");
	//if(verbosity >= 2){
	double now_target=0;
	double now_target_dummy=0;
	for(i=0;i<examples_total;i++){
	    now_target_dummy=sum[i]/2-ys[i];
	    if(is_alpha_neg(i)){
		now_target_dummy+= epsilon_pos;
	    }
	    else{
		now_target_dummy-= epsilon_neg;
	    };
	    now_target+=alphas[i]*now_target_dummy;
	};
	logln(2,"Target function: "+now_target);
	//};
	//};
	
	print_statistics();
	
	exit_optimizer();
    };
    

    /**
     * print statistics about result
     */
    protected void print_statistics()
    {
      int dim = the_examples.get_dim();
      int i,j;
      double alpha;
      double[] x;
      int svs=0;
      int bsv = 0;
      double mae=0;
      double mse = 0;
      int countpos = 0;
      int countneg = 0;
      double y;
      double prediction;
      double min_lambda = Double.MAX_VALUE;
      double b = the_examples.get_b();
      
      for(i=0;i<examples_total;i++){
	  if(lambda(i) < min_lambda){
	      min_lambda = lambda(i);
	  };
	  y = ys[i];
	  prediction = sum[i]+b;
	  mae += Math.abs(y-prediction);
	  mse += (y-prediction)*(y-prediction);
	  alpha = alphas[i];
	  if(y < prediction-epsilon_pos){
	      countpos++;
	  }
	  else if(y > prediction+epsilon_neg){
	      countneg++;
	  };
	  if(alpha != 0){
	      svs++;
	      if((alpha == Cpos) || (alpha == -Cneg)){
		  bsv++;
	      };
	  };
      };
      mae /= (double)examples_total;
      mse /= (double)examples_total;
      min_lambda = -min_lambda;

      logln(1,"Error on KKT is "+min_lambda);
      logln(1,svs+" SVs");
      logln(1,bsv+" BSVs");
      logln(1,"MAE "+mae);
      logln(1,"MSE "+mse);
      logln(1,countpos+" pos loss");
      logln(1,countneg+" neg loss");


      //if(verbosity >= 2){
      // print hyperplane
      double[] w = new double[dim];
      for(j=0;j<dim;j++) w[j] = 0;
      for(i=0;i<examples_total;i++){
	  x = the_examples.get_example(i).toDense(dim);
	  alpha = alphas[i];
	  for(j=0;j<dim;j++){
	      w[j] += alpha*x[j];
	  };
      };
      //    double[] Exp = the_examples.Exp;
      //  	  double[] Dev = the_examples.Dev;
      //  	  if(Exp != null){
      //  	      for(j=0;j<dim;j++){
      //  		  if(Dev[j] != 0){
      //  		      w[j] /= Dev[j];
      //  		  };
      //  		  if(0 != Dev[dim]){
      //  		      w[j] *= Dev[dim];
      //  		  };
      //  		  b -= w[j]*Exp[j];
      //  	      };
      //  	      b += Exp[dim];
      //  	  };
      //  	  logln(2," ");
      for(j=0;j<dim;j++){
	  logln(2,"w["+j+"] = "+w[j]);
      };
      logln(2,"b = "+b);
      if(dim==1){
	  logln(2,"y = "+w[0]+"*x+"+b);
      };
      //};
    };


    /** Return the weights of the features. */
    public double[] getWeights() {
	int dim = the_examples.get_dim();
	double[] w = new double[dim];
	for(int j = 0; j < dim; j++) w[j] = 0;
	for(int i = 0; i < examples_total; i++){
	    double[] x = the_examples.get_example(i).toDense(dim);
	    double alpha = alphas[i];
	    for(int j = 0; j < dim; j++) {
		w[j] += alpha * x[j];
	    }
	}
	return w;
    }

    /** Returns the value of b. */
    public double getB() {
	return the_examples.get_b();
    }