nnge.java

一个数据挖掘软件ALPHAMINERR的整个过程的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.
 */

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

package weka.classifiers.rules;

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

import weka.classifiers.Classifier;
import weka.classifiers.Evaluation;
import weka.classifiers.UpdateableClassifier;
import weka.core.Instance;
import weka.core.Instances;
import weka.core.Option;
import weka.core.OptionHandler;
import weka.core.UnsupportedAttributeTypeException;
import weka.core.Utils;


/**
 * NNge classifier. 
 *
 * Nearest neighbor like algorithm using non-nested generalized exemplars.
 *
 * For more information, see <p>
 * 
 * Brent Martin, (1995) "Instance-Based learning : Nearest Neighbor With Generalization",
 * Master Thesis, University of Waikato, Hamilton, New Zealand
 * <p>
 *
 * Sylvain Roy (2002) "Nearest Neighbor With Generalization",
 * Unpublished, University of Canterbury, Christchurch, New Zealand
 * <p>
 *
 * Valid options are:<p>
 *
 * -I num <br>
 * Set the number of folder to use in the computing of the mutual information
 * (default 5) <p>
 *
 * -G num <br>
 * Set the number of attempts of generalisation
 * (default 5) <p>
 *
 * @author Brent Martin ([e-mail])
 * @author Sylvain Roy ([e-mail])
 * @version $$ 
 */
public class NNge extends Classifier implements UpdateableClassifier, OptionHandler {

  /**
   * 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"
      + "Brent Martin, (1995) \"Instance-Based learning : Nearest Neighbor With "
      + "Generalization\", Master Thesis, University of Waikato, Hamilton, New "
      + "Zealand\n\n"
      + "Sylvain Roy (2002) \"Nearest Neighbor With Generalization\","
      + "Unpublished, University of Canterbury, Christchurch, New Zealand\n\n";
  }

  /**
   * Implements Exemplar as used by NNge : parallel axis hyperrectangle.
   */
  private class Exemplar extends Instances {
    
    /** 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 instance the new example used for the generalisation
     * @exception 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 instance the new example used for the generalisation
     * @exception 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.
     *
     * @exception 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.
     *
     * @exception 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
     * @exception 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()){

	double norm = m_NNge.m_MaxArray[attrIndex] - m_NNge.m_MinArray[attrIndex];
	if(norm <= 0)
	  norm = 1;

	if (m_MaxBorder[attrIndex] < inst.value(attrIndex)) {
	  return (inst.value(attrIndex) - m_MaxBorder[attrIndex]) / norm;
	} else if (inst.value(attrIndex) < m_MinBorder[attrIndex]) {
	  return (m_MinBorder[attrIndex] - inst.value(attrIndex)) / norm;
	} else {
	  return 0;
	}

	/* nominal attribute */
      } else {
	if(holds(attrIndex, inst.value(attrIndex))){
	  return 0;
	} else {
	  return 1;
	}
      }
    }


    /**
     * Returns the square of the distance between inst and the Exemplar. 
     * 
     * @param inst an instance
     * @return the squared distance between inst and the Exemplar.
     */
    private double squaredDistance(Instance inst) {
	
      double sum = 0, term;
      int numNotMissingAttr = 0;
      for(int i = 0; i < inst.numAttributes(); i++){
	    
	if(i == classIndex())
	  continue;