nnge.java

代码是一个分类器的实现,其中使用了部分weka的源代码。可以将项目导入eclipse运行

/*
 *    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.
 */

/*
 *    NNge.java
 *    Copyright (C) 2002 Brent Martin
 *
 */

package weka.classifiers.rules;

import weka.classifiers.Classifier;
import weka.classifiers.UpdateableClassifier;
import weka.core.Capabilities;
import weka.core.Instance;
import weka.core.Instances;
import weka.core.Option;
import weka.core.OptionHandler;
import weka.core.TechnicalInformation;
import weka.core.TechnicalInformationHandler;
import weka.core.Utils;
import weka.core.Capabilities.Capability;
import weka.core.TechnicalInformation.Field;
import weka.core.TechnicalInformation.Type;

import java.util.Enumeration;
import java.util.LinkedList;
import java.util.Vector;


/**
 <!-- globalinfo-start -->
 * Nearest-neighbor-like algorithm using non-nested generalized exemplars (which are hyperrectangles that can be viewed as if-then rules). For more information, see <br/>
 * <br/>
 * Brent Martin (1995). Instance-Based learning: Nearest Neighbor With Generalization. Hamilton, New Zealand.<br/>
 * <br/>
 * Sylvain Roy (2002). Nearest Neighbor With Generalization. Christchurch, New Zealand.
 * <p/>
 <!-- globalinfo-end -->
 *
 <!-- technical-bibtex-start -->
 * BibTeX:
 * <pre>
 * &#64;mastersthesis{Martin1995,
 *    address = {Hamilton, New Zealand},
 *    author = {Brent Martin},
 *    school = {University of Waikato},
 *    title = {Instance-Based learning: Nearest Neighbor With Generalization},
 *    year = {1995}
 * }
 * 
 * &#64;unpublished{Roy2002,
 *    address = {Christchurch, New Zealand},
 *    author = {Sylvain Roy},
 *    school = {University of Canterbury},
 *    title = {Nearest Neighbor With Generalization},
 *    year = {2002}
 * }
 * </pre>
 * <p/>
 <!-- technical-bibtex-end -->
 *
 <!-- options-start -->
 * Valid options are: <p/>
 * 
 * <pre> -G &lt;value&gt;
 *  Number of attempts of generalisation.
 * </pre>
 * 
 * <pre> -I &lt;value&gt;
 *  Number of folder for computing the mutual information.
 * </pre>
 * 
 <!-- options-end -->
 *
 * @author Brent Martin ([e-mail])
 * @author Sylvain Roy ([e-mail])
 * @version $Revision: 1.6 $
 */
public class NNge 
  extends Classifier 
  implements UpdateableClassifier, OptionHandler, TechnicalInformationHandler {

  /** for serialization */
  static final long serialVersionUID = 4084742275553788972L;
  
  /**
   * Returns a string describing classifier
   * @return a description suitable for
   * displaying in the explorer/experimenter gui
   */
  public String globalInfo() {

    return "Nearest-neighbor-like algorithm using non-nested generalized exemplars "
      + "(which are hyperrectangles that can be viewed as if-then rules). For more "
      + "information, see \n\n"
      + getTechnicalInformation().toString();
  }

  /**
   * Returns an instance of a TechnicalInformation object, containing 
   * detailed information about the technical background of this class,
   * e.g., paper reference or book this class is based on.
   * 
   * @return the technical information about this class
   */
  public TechnicalInformation getTechnicalInformation() {
    TechnicalInformation 	result;
    TechnicalInformation 	additional;
    
    result = new TechnicalInformation(Type.MASTERSTHESIS);
    result.setValue(Field.AUTHOR, "Brent Martin");
    result.setValue(Field.YEAR, "1995");
    result.setValue(Field.TITLE, "Instance-Based learning: Nearest Neighbor With Generalization");
    result.setValue(Field.SCHOOL, "University of Waikato");
    result.setValue(Field.ADDRESS, "Hamilton, New Zealand");
    
    additional = result.add(Type.UNPUBLISHED);
    additional.setValue(Field.AUTHOR, "Sylvain Roy");
    additional.setValue(Field.YEAR, "2002");
    additional.setValue(Field.TITLE, "Nearest Neighbor With Generalization");
    additional.setValue(Field.SCHOOL, "University of Canterbury");
    additional.setValue(Field.ADDRESS, "Christchurch, New Zealand");
    
    return result;
  }

  /**
   * Implements Exemplar as used by NNge : parallel axis hyperrectangle.
   */
  private class Exemplar 
    extends Instances {
    
    /** for serialization */
    static final long serialVersionUID = 3960180128928697216L;
    
    /** List of all the Exemplar */
    private Exemplar previous = null;
    private Exemplar next = null;
	
    /** List of all the Exemplar with the same class */
    private Exemplar previousWithClass = null;
    private Exemplar nextWithClass = null;

    /** The NNge which owns this Exemplar */
    private NNge m_NNge;

    /** class of the Exemplar */
    private double m_ClassValue;

    /** Number of correct prediction for this examplar */
    private int m_PositiveCount = 1;
    
    /** Number of incorrect prediction for this examplar */
    private int m_NegativeCount = 0;

    /** The max borders of the rectangle for numeric attributes */
    private double[] m_MaxBorder;
	                     
    /** The min borders of the rectangle for numeric attributes */
    private double[] m_MinBorder;
	                     
    /** The ranges of the hyperrectangle for nominal attributes */
    private boolean[][] m_Range;
	                     
    /** the arrays used by preGeneralise */
    private double[] m_PreMaxBorder = null;
    private double[] m_PreMinBorder = null;
    private boolean[][] m_PreRange = null;
    private Instance m_PreInst = null;


    /**
     * Build a new empty Exemplar
     *
     * @param nnge the classifier which owns this Exemplar
     * @param inst the instances from which the header information is to be taken
     * @param size the capacity of the Exemplar
     * @param classV the class of the Exemplar
     */
    private Exemplar (NNge nnge, Instances inst, int size, double classV){

      super(inst, size);
      m_NNge = nnge;
      m_ClassValue = classV;
      m_MinBorder = new double[numAttributes()];
      m_MaxBorder = new double[numAttributes()];
      m_Range = new boolean[numAttributes()][];
      for(int i = 0; i < numAttributes(); i++){
	if(attribute(i).isNumeric()){
	  m_MinBorder[i] = Double.POSITIVE_INFINITY;
	  m_MaxBorder[i] = Double.NEGATIVE_INFINITY;
	  m_Range[i] = null;
	} else {
	  m_MinBorder[i] = Double.NaN;
	  m_MaxBorder[i] = Double.NaN;
	  m_Range[i] = new boolean[attribute(i).numValues() + 1];
	  for(int j = 0; j < attribute(i).numValues() + 1; j++){
	    m_Range[i][j] = false;
	  }
	}
      }
    }


    /**
     * Generalise the Exemplar with inst
     *
     * @param inst the new example used for the generalisation
     * @throws Exception if either the class of inst is not equal to the class of the Exemplar or inst misses a value.
     */
    private void generalise(Instance inst) throws Exception {

      if(m_ClassValue != inst.classValue())
	throw new Exception("Exemplar.generalise : Incompatible instance's class.");

      add(inst);

      /* extends each range in order to cover inst */
      for(int i = 0; i < numAttributes(); i++){
	 
	if(inst.isMissing(i))
	  throw new Exception("Exemplar.generalise : Generalisation with missing feature impossible.");

	if(i == classIndex())
	  continue;
	    
	if(attribute(i).isNumeric()){
	  if(m_MaxBorder[i] < inst.value(i)) 
	    m_MaxBorder[i] = inst.value(i);
	  if(inst.value(i) < m_MinBorder[i]) 
	    m_MinBorder[i] = inst.value(i);  
		
	} else {
	  m_Range[i][(int) inst.value(i)] = true;
	}
      }
    } 


    /**
     * pre-generalise the Exemplar with inst
     * i.e. the boundaries of the Exemplar include inst but the Exemplar still doesn't 'own' inst.
     * To be complete, the generalisation must be validated with validateGeneralisation.
     * the generalisation can be canceled with cancelGeneralisation.
     * @param inst the new example used for the generalisation
     * @throws Exception if either the class of inst is not equal to the class of the Exemplar or inst misses a value.
     */
    private void preGeneralise(Instance inst) throws Exception {
	
      if(m_ClassValue != inst.classValue())
	throw new Exception("Exemplar.preGeneralise : Incompatible instance's class.");

      m_PreInst = inst;

      /* save the current state */
      m_PreRange = new boolean[numAttributes()][];
      m_PreMinBorder = new double[numAttributes()];
      m_PreMaxBorder = new double[numAttributes()];
      for(int i = 0; i < numAttributes(); i++){
	if(attribute(i).isNumeric()){
	  m_PreMinBorder[i] = m_MinBorder[i];
	  m_PreMaxBorder[i] = m_MaxBorder[i];
	} else {
	  m_PreRange[i] = new boolean[attribute(i).numValues() + 1];
	  for(int j = 0; j < attribute(i).numValues() + 1; j++){
	    m_PreRange[i][j] = m_Range[i][j];
	  }
	}
      }

      /* perform the pre-generalisation */
      for(int i = 0; i < numAttributes(); i++){
	if(inst.isMissing(i))
	  throw new Exception("Exemplar.preGeneralise : Generalisation with missing feature impossible.");
	if(i == classIndex())
	  continue;
	if(attribute(i).isNumeric()){
	  if(m_MaxBorder[i] < inst.value(i)) 
	    m_MaxBorder[i] = inst.value(i);
	  if(inst.value(i) < m_MinBorder[i]) 
	    m_MinBorder[i] = inst.value(i);  
	} else {
	  m_Range[i][(int) inst.value(i)] = true;
	}
      }
    }


    /**
     * Validates a generalisation started with preGeneralise.
     * Watch out, preGeneralise must have been called before.
     *
     * @throws Exception is thrown if preGeneralise hasn't been called before
     */
    private void validateGeneralisation() throws Exception {
      if(m_PreInst == null){
	throw new Exception("Exemplar.validateGeneralisation : validateGeneralisation called without previous call to preGeneralise!");
      }
      add(m_PreInst);
      m_PreRange = null;
      m_PreMinBorder = null;
      m_PreMaxBorder = null;
    }

    
    /**
     * Cancels a generalisation started with preGeneralise.
     * Watch out, preGeneralise must have been called before.
     *
     * @throws Exception is thrown if preGeneralise hasn't been called before
     */
    private void cancelGeneralisation() throws Exception {
      if(m_PreInst == null){
	throw new Exception("Exemplar.cancelGeneralisation : cancelGeneralisation called without previous call to preGeneralise!");
      }
      m_PreInst = null;
      m_Range = m_PreRange;
      m_MinBorder = m_PreMinBorder;
      m_MaxBorder = m_PreMaxBorder;
      m_PreRange = null;
      m_PreMinBorder = null;
      m_PreMaxBorder = null;
    }


    /**
     * return true if inst is held by this Exemplar, false otherwise
     *
     * @param inst an Instance
     * @return true if inst is held by this hyperrectangle, false otherwise
     */
    private boolean holds(Instance inst) {
	
      if(numInstances() == 0)
	return false;

      for(int i = 0; i < numAttributes(); i++){
	if(i != classIndex() && !holds(i, inst.value(i)))
	  return false;
      }
      return true;
    }


    /**
     * return true if value is inside the Exemplar along the attrIndex attribute.
     *
     * @param attrIndex the index of an attribute 
     * @param value a value along the attrIndexth attribute
     * @return true if value is inside the Exemplar along the attrIndex attribute.
     */
    private boolean holds(int attrIndex, double value) {
	
      if (numAttributes() == 0)
	return false;
	
      if(attribute(attrIndex).isNumeric())
	return(m_MinBorder[attrIndex] <= value && value <= m_MaxBorder[attrIndex]);
      else
	return m_Range[attrIndex][(int) value];
    }


    /**
     * Check if the Examplar overlaps ex
     *
     * @param ex an Exemplar
     * @return true if ex is overlapped by the Exemplar
     * @throws Exception
     */
    private boolean overlaps(Exemplar ex) {

      if(ex.isEmpty() || isEmpty())
	return false;

      for (int i = 0; i < numAttributes(); i++){
	    
	if(i == classIndex()){
	  continue;
	}
	if (attribute(i).isNumeric() && 
	    (ex.m_MaxBorder[i] < m_MinBorder[i] || ex.m_MinBorder[i] > m_MaxBorder[i])){
	  return false;
	}
	if (attribute(i).isNominal()) {
	  boolean in = false;
	  for (int j = 0; j < attribute(i).numValues() + 1; j++){
	    if(m_Range[i][j] && ex.m_Range[i][j]){
	      in = true;
	      break;
	    }
	  }
	  if(!in) return false;
	}
      }
      return true;
    }


    /** 
     * Compute the distance between the projection of inst and this Exemplar along the attribute attrIndex.
     * If inst misses its value along the attribute, the function returns 0.
     *
     * @param inst an instance
     * @param attrIndex the index of the attribute 
     * @return the distance between the projection of inst and this Exemplar along the attribute attrIndex.
     */
    private double attrDistance(Instance inst, int attrIndex) {

      if(inst.isMissing(attrIndex))
	return 0;

      /* numeric attribute */
      if(attribute(attrIndex).isNumeric()){