smo.java

:<<数据挖掘--实用机器学习技术及java实现>>一书的配套源程序

/*
 *    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., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

/*
 *    SMO.java
 *    Copyright (C) 1999 Eibe Frank
 */

package weka.classifiers;

import java.util.*;
import java.io.*;
import weka.core.*;
import weka.filters.*;

/**
 * Implements John C. Platt's sequential minimal optimization
 * algorithm for training a support vector classifier using polynomial
 * kernels. Transforms output of SVM into probabilities by applying a
 * standard sigmoid function that is not fitted to the data.
 *
 * This implementation globally replaces all missing values and
 * transforms nominal attributes into binary ones. For more
 * information on the SMO algorithm, see<p>
 *
 * J. Platt (1998). <i>Fast Training of Support Vector
 * Machines using Sequential Minimal Optimization</i>. Advances in Kernel
 * Methods - Support Vector Learning, B. Sch鰈kopf, C. Burges, and
 * A. Smola, eds., MIT Press. <p>
 *
 * S.S. Keerthi, S.K. Shevade, C. Bhattacharyya, K.R.K. Murthy (2001).
 * <i> Improvements to Platt's SMO Algorithm for SVM Classifier
 * Design.  Neural Computation, 13(3), pp 637-649, 2001. <p>
 *
 * Note: for improved speed normalization should be turned off when
 * operating on SparseInstances.<p>
 *
 * Valid options are:<p>
 *
 * -C num <br>
 * The complexity constant C. (default 1)<p>
 *
 * -E num <br>
 * The exponent for the polynomial kernel. (default 1)<p>
 *
 * -N <br>
 * Don't normalize the training instances. <p>
 *
 * -L <br>
 * Rescale kernel. <p>
 *
 * -O <br>
 * Use lower-order terms. <p>
 *
 * -A num <br>
 * Sets the size of the kernel cache. Should be a prime number. 
 * (default 1000003) <p>
 *
 * -T num <br>
 * Sets the tolerance parameter. (default 1.0e-3)<p>
 *
 * -P num <br>
 * Sets the epsilon for round-off error. (default 1.0e-12)<p>
 *
 * @author Eibe Frank ([e-mail])
 * @author Shane Legg ([e-mail]) (sparse vector code)
 * @author Stuart Inglis ([e-mail]) (sparse vector code)
 * @version $Revision: 1.23.2.2 $ 
 */
public class SMO extends DistributionClassifier implements OptionHandler {

  /**
   * Stores a set of a given size.
   */
  private class SMOset implements Serializable {

    /** The current number of elements in the set */
    private int m_number;

    /** The first element in the set */
    private int m_first;

    /** Indicators */
    private boolean[] m_indicators;

    /** The next element for each element */
    private int[] m_next;

    /** The previous element for each element */
    private int[] m_previous;

    /**
     * Creates a new set of the given size.
     */
    private SMOset(int size) {
      
      m_indicators = new boolean[size];
      m_next = new int[size];
      m_previous = new int[size];
      m_number = 0;
      m_first = -1;
    }
 
    /**
     * Checks whether an element is in the set.
     */
    private boolean contains(int index) {

      return m_indicators[index];
    }

    /**
     * Deletes an element from the set.
     */
    private void delete(int index) {

      if (m_indicators[index]) {
	if (m_first == index) {
	  m_first = m_next[index];
	} else {
	  m_next[m_previous[index]] = m_next[index];
	}
	if (m_next[index] != -1) {
	  m_previous[m_next[index]] = m_previous[index];
	}
	m_indicators[index] = false;
	m_number--;
      }
    }

    /**
     * Inserts an element into the set.
     */
    private void insert(int index) {

      if (!m_indicators[index]) {
	if (m_number == 0) {
	  m_first = index;
	  m_next[index] = -1;
	  m_previous[index] = -1;
	} else {
	  m_previous[m_first] = index;
	  m_next[index] = m_first;
	  m_previous[index] = -1;
	  m_first = index;
	}
	m_indicators[index] = true;
	m_number++;
      }
    }

    /** 
     * Gets the next element in the set. -1 gets the first one.
     */
    private int getNext(int index) {

      if (index == -1) {
	return m_first;
      } else {
	return m_next[index];
      }
    }

    /**
     * Prints all the current elements in the set.
     */
    private void printElements() {

      for (int i = getNext(-1); i != -1; i = getNext(i)) {
	System.err.print(i + " ");
      }
      System.err.println();
      for (int i = 0; i < m_indicators.length; i++) {
	if (m_indicators[i]) {
	  System.err.print(i + " ");
	}
      }
      System.err.println();
      System.err.println(m_number);
    }

    /** 
     * Returns the number of elements in the set.
     */
    private int numElements() {
      
      return m_number;
    }
  }

  /** The exponent for the polnomial kernel. */
  private double m_exponent = 1.0;

  /** The complexity parameter. */
  private double m_C = 1.0;

  /** Epsilon for rounding. */
  private double m_eps = 1.0e-12;
  
  /** Tolerance for accuracy of result. */
  private double m_tol = 1.0e-3;

  /** The Lagrange multipliers. */
  private double[] m_alpha;

  /** The thresholds. */
  private double m_b, m_bLow, m_bUp;

  /** The indices for m_bLow and m_bUp */
  private int m_iLow, m_iUp;

  /** The training data. */
  private Instances m_data;

  /** Weight vector for linear machine. */
  private double[] m_weights;

  /** Kernel function cache */
  private double[] m_storage;
  private long[] m_keys;

  /** The transformed class values. */
  private double[] m_class;

  /** The current set of errors for all non-bound examples. */
  private double[] m_errors;

  /** The five different sets used by the algorithm. */
  private SMOset m_I0; // {i: 0 < m_alpha[i] < C}
  private SMOset m_I1; // {i: m_class[i] = 1, m_alpha[i] = 0}
  private SMOset m_I2; // {i: m_class[i] = -1, m_alpha[i] =C}
  private SMOset m_I3; // {i: m_class[i] = 1, m_alpha[i] = C}
  private SMOset m_I4; // {i: m_class[i] = -1, m_alpha[i] = 0}

  /** The set of support vectors */
  private SMOset m_supportVectors; // {i: 0 < m_alpha[i]}

  /** The filter used to make attributes numeric. */
  private NominalToBinaryFilter m_NominalToBinary;

  /** The filter used to normalize all values. */
  private NormalizationFilter m_Normalization;

  /** The filter used to get rid of missing values. */
  private ReplaceMissingValuesFilter m_Missing;

  /** Counts the number of kernel evaluations. */
  private int m_kernelEvals;

  /** The size of the cache (a prime number) */
  private int m_cacheSize = 1000003;

  /** True if we don't want to normalize */
  private boolean m_Normalize = true;

  /** Rescale? */
  private boolean m_rescale = false;
  
  /** Use lower-order terms? */
  private boolean m_lowerOrder = false;

  /** Only numeric attributes in the dataset? */
  private boolean m_onlyNumeric;

  /** Precision constant for updating sets */
  private static double m_Del = 1000 * Double.MIN_VALUE;

  /**
   * Method for building the classifier.
   *
   * @param insts the set of training instances
   * @exception Exception if the classifier can't be built successfully
   */
  public void buildClassifier(Instances insts) throws Exception {

    int m_kernelEvals = 0;

    if (insts.checkForStringAttributes()) {
      throw new Exception("Can't handle string attributes!");
    }
    if (insts.numClasses() > 2) {
      throw new Exception("Can only handle two-class datasets!");
    }
    if (insts.classAttribute().isNumeric()) {
      throw new Exception("SMO can't handle a numeric class!");
    }

    m_data = insts;

    m_onlyNumeric = true;
    for (int i = 0; i < m_data.numAttributes(); i++) {
      if (i != m_data.classIndex()) {
	if (!m_data.attribute(i).isNumeric()) {
	  m_onlyNumeric = false;
	  break;
	}
      }
    }

    m_Missing = new ReplaceMissingValuesFilter();
    m_Missing.setInputFormat(m_data);
    m_data = Filter.useFilter(m_data, m_Missing); 

    if (m_Normalize) {
      m_Normalization = new NormalizationFilter();
      m_Normalization.setInputFormat(m_data);
      m_data = Filter.useFilter(m_data, m_Normalization); 
    } else {
      m_Normalization = null;
    }

    if (!m_onlyNumeric) {
      m_NominalToBinary = new NominalToBinaryFilter();
      m_NominalToBinary.setInputFormat(m_data);
      m_data = Filter.useFilter(m_data, m_NominalToBinary);
    } else {
      m_NominalToBinary = null;
    }

    // If machine is linear, reserve space for weights
    if (m_exponent == 1.0) {
      m_weights = new double[m_data.numAttributes()];
    } else {
      m_weights = null;
    }

    // Initialize alpha array to zero
    m_alpha = new double[m_data.numInstances()];

    // Initialize thresholds
    m_bUp = -1; m_bLow = 1; m_b = 0;

    // Initialize sets
    m_supportVectors = new SMOset(m_data.numInstances());
    m_I0 = new SMOset(m_data.numInstances());
    m_I1 = new SMOset(m_data.numInstances());
    m_I2 = new SMOset(m_data.numInstances());
    m_I3 = new SMOset(m_data.numInstances());
    m_I4 = new SMOset(m_data.numInstances());

    // Set class values
    m_class = new double[m_data.numInstances()];
    m_iUp = -1; m_iLow = -1;
    for (int i = 0; i < m_class.length; i++) {
      if ((int) m_data.instance(i).classValue() == 0) {
	m_class[i] = -1; m_iLow = i;
      } else {
	m_class[i] = 1; m_iUp = i;
      }
    }
    if ((m_iUp == -1) || (m_iLow == -1)) {
      if ((m_iUp == -1) && (m_iLow == -1)) {
	throw new Exception ("No instances without missing class values!");
      } else {
	if (m_iUp == -1) {
	  m_b = 1;
	} else {
	  m_b = -1;
	}
	return;
      }
    }

    // Initialize error cache
    m_errors = new double[m_data.numInstances()];
    m_errors[m_iLow] = 1; m_errors[m_iUp] = -1;

    // The kernel calculations are cached
    m_storage = new double[m_cacheSize];
    m_keys = new long[m_cacheSize];

    // Build up I1 and I4
    for (int i = 0; i < m_class.length; i++ ) {
      if (m_class[i] == 1) {
	m_I1.insert(i);
      } else {
	m_I4.insert(i);
      }
    }

    // Loop to find all the support vectors
    int numChanged = 0;
    boolean examineAll = true;
    while ((numChanged > 0) || examineAll) {
      numChanged = 0;
      if (examineAll) {
	for (int i = 0; i < m_alpha.length; i++) {
	  if (examineExample(i)) {
	    numChanged++;
	  }
	}
      } else {

	// This code implements Modification 1 from Keerthi et al.'s paper
	for (int i = 0; i < m_alpha.length; i++) {
	  if ((m_alpha[i] > 0) &&  (m_alpha[i] < m_C)) {
	    if (examineExample(i)) {
	      numChanged++;
	    }
	    
	    // Is optimality on unbound vectors obtained?
	    if (m_bUp > m_bLow - 2 * m_tol) {
	      numChanged = 0;
	      break;
	    }
	  }
	}
	
	//This is the code for Modification 2 from Keerthi et al.'s paper
	/*boolean innerLoopSuccess = true; 
	numChanged = 0;
	while ((m_bUp < m_bLow - 2 * m_tol) && (innerLoopSuccess == true)) {
	  innerLoopSuccess = takeStep(m_iUp, m_iLow, m_errors[m_iLow]);
	  }*/
      }

      if (examineAll) {
	examineAll = false;