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

/*
 *    ReliefFAttributeEval.java
 *    Copyright (C) 1999 University of Waikato, Hamilton, New Zealand
 *
 */

package weka.attributeSelection;

import weka.core.Attribute;
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.Random;
import java.util.Vector;

/** 
 <!-- globalinfo-start -->
 * ReliefFAttributeEval :<br/>
 * <br/>
 * Evaluates the worth of an attribute by repeatedly sampling an instance and considering the value of the given attribute for the nearest instance of the same and different class. Can operate on both discrete and continuous class data.<br/>
 * <br/>
 * For more information see:<br/>
 * <br/>
 * Kenji Kira, Larry A. Rendell: A Practical Approach to Feature Selection. In: Ninth International Workshop on Machine Learning, 249-256, 1992.<br/>
 * <br/>
 * Igor Kononenko: Estimating Attributes: Analysis and Extensions of RELIEF. In: European Conference on Machine Learning, 171-182, 1994.<br/>
 * <br/>
 * Marko Robnik-Sikonja, Igor Kononenko: An adaptation of Relief for attribute estimation in regression. In: Fourteenth International Conference on Machine Learning, 296-304, 1997.
 * <p/>
 <!-- globalinfo-end -->
 *
 <!-- technical-bibtex-start -->
 * BibTeX:
 * <pre>
 * &#64;inproceedings{Kira1992,
 *    author = {Kenji Kira and Larry A. Rendell},
 *    booktitle = {Ninth International Workshop on Machine Learning},
 *    editor = {Derek H. Sleeman and Peter Edwards},
 *    pages = {249-256},
 *    publisher = {Morgan Kaufmann},
 *    title = {A Practical Approach to Feature Selection},
 *    year = {1992}
 * }
 * 
 * &#64;inproceedings{Kononenko1994,
 *    author = {Igor Kononenko},
 *    booktitle = {European Conference on Machine Learning},
 *    editor = {Francesco Bergadano and Luc De Raedt},
 *    pages = {171-182},
 *    publisher = {Springer},
 *    title = {Estimating Attributes: Analysis and Extensions of RELIEF},
 *    year = {1994}
 * }
 * 
 * &#64;inproceedings{Robnik-Sikonja1997,
 *    author = {Marko Robnik-Sikonja and Igor Kononenko},
 *    booktitle = {Fourteenth International Conference on Machine Learning},
 *    editor = {Douglas H. Fisher},
 *    pages = {296-304},
 *    publisher = {Morgan Kaufmann},
 *    title = {An adaptation of Relief for attribute estimation in regression},
 *    year = {1997}
 * }
 * </pre>
 * <p/>
 <!-- technical-bibtex-end -->
 *
 <!-- options-start -->
 * Valid options are: <p/>
 * 
 * <pre> -M &lt;num instances&gt;
 *  Specify the number of instances to
 *  sample when estimating attributes.
 *  If not specified, then all instances
 *  will be used.</pre>
 * 
 * <pre> -D &lt;seed&gt;
 *  Seed for randomly sampling instances.
 *  (Default = 1)</pre>
 * 
 * <pre> -K &lt;number of neighbours&gt;
 *  Number of nearest neighbours (k) used
 *  to estimate attribute relevances
 *  (Default = 10).</pre>
 * 
 * <pre> -W
 *  Weight nearest neighbours by distance</pre>
 * 
 * <pre> -A &lt;num&gt;
 *  Specify sigma value (used in an exp
 *  function to control how quickly
 *  weights for more distant instances
 *  decrease. Use in conjunction with -W.
 *  Sensible value=1/5 to 1/10 of the
 *  number of nearest neighbours.
 *  (Default = 2)</pre>
 * 
 <!-- options-end -->
 *
 * @author Mark Hall ([e-mail])
 * @version $Revision: 1.21 $
 */
public class ReliefFAttributeEval
  extends AttributeEvaluator
  implements OptionHandler, TechnicalInformationHandler {
  
  /** for serialization */
  static final long serialVersionUID = -8422186665795839379L;

  /** The training instances */
  private Instances m_trainInstances;

  /** The class index */
  private int m_classIndex;

  /** The number of attributes */
  private int m_numAttribs;

  /** The number of instances */
  private int m_numInstances;

  /** Numeric class */
  private boolean m_numericClass;

  /** The number of classes if class is nominal */
  private int m_numClasses;

  /** 
   * Used to hold the probability of a different class val given nearest
   * instances (numeric class)
   */
  private double m_ndc;

  /** 
   * Used to hold the prob of different value of an attribute given
   * nearest instances (numeric class case)
   */
  private double[] m_nda;

  /**
   * Used to hold the prob of a different class val and different att
   * val given nearest instances (numeric class case)
   */
  private double[] m_ndcda;

  /** Holds the weights that relief assigns to attributes */
  private double[] m_weights;

  /** Prior class probabilities (discrete class case) */
  private double[] m_classProbs;

  /** 
   * The number of instances to sample when estimating attributes
   * default == -1, use all instances
   */
  private int m_sampleM;

  /** The number of nearest hits/misses */
  private int m_Knn;

  /** k nearest scores + instance indexes for n classes */
  private double[][][] m_karray;

  /** Upper bound for numeric attributes */
  private double[] m_maxArray;

  /** Lower bound for numeric attributes */
  private double[] m_minArray;

  /** Keep track of the farthest instance for each class */
  private double[] m_worst;

  /** Index in the m_karray of the farthest instance for each class */
  private int[] m_index;

  /** Number of nearest neighbours stored of each class */
  private int[] m_stored;
 
  /** Random number seed used for sampling instances */
  private int m_seed;

  /**
   *  used to (optionally) weight nearest neighbours by their distance
   *  from the instance in question. Each entry holds 
   *  exp(-((rank(r_i, i_j)/sigma)^2)) where rank(r_i,i_j) is the rank of
   *  instance i_j in a sequence of instances ordered by the distance
   *  from r_i. sigma is a user defined parameter, default=20
   **/
  private double[] m_weightsByRank;
  private int m_sigma;
  
  /** Weight by distance rather than equal weights */
  private boolean m_weightByDistance;

  /**
   * Constructor
   */
  public ReliefFAttributeEval () {
    resetOptions();
  }

  /**
   * Returns a string describing this attribute evaluator
   * @return a description of the evaluator suitable for
   * displaying in the explorer/experimenter gui
   */
  public String globalInfo() {
    return "ReliefFAttributeEval :\n\nEvaluates the worth of an attribute by "
      +"repeatedly sampling an instance and considering the value of the "
      +"given attribute for the nearest instance of the same and different "
      +"class. Can operate on both discrete and continuous class data.\n\n"
      + "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.INPROCEEDINGS);
    result.setValue(Field.AUTHOR, "Kenji Kira and Larry A. Rendell");
    result.setValue(Field.TITLE, "A Practical Approach to Feature Selection");
    result.setValue(Field.BOOKTITLE, "Ninth International Workshop on Machine Learning");
    result.setValue(Field.EDITOR, "Derek H. Sleeman and Peter Edwards");
    result.setValue(Field.YEAR, "1992");
    result.setValue(Field.PAGES, "249-256");
    result.setValue(Field.PUBLISHER, "Morgan Kaufmann");
    
    additional = result.add(Type.INPROCEEDINGS);
    additional.setValue(Field.AUTHOR, "Igor Kononenko");
    additional.setValue(Field.TITLE, "Estimating Attributes: Analysis and Extensions of RELIEF");
    additional.setValue(Field.BOOKTITLE, "European Conference on Machine Learning");
    additional.setValue(Field.EDITOR, "Francesco Bergadano and Luc De Raedt");
    additional.setValue(Field.YEAR, "1994");
    additional.setValue(Field.PAGES, "171-182");
    additional.setValue(Field.PUBLISHER, "Springer");
    
    additional = result.add(Type.INPROCEEDINGS);
    additional.setValue(Field.AUTHOR, "Marko Robnik-Sikonja and Igor Kononenko");
    additional.setValue(Field.TITLE, "An adaptation of Relief for attribute estimation in regression");
    additional.setValue(Field.BOOKTITLE, "Fourteenth International Conference on Machine Learning");
    additional.setValue(Field.EDITOR, "Douglas H. Fisher");
    additional.setValue(Field.YEAR, "1997");
    additional.setValue(Field.PAGES, "296-304");
    additional.setValue(Field.PUBLISHER, "Morgan Kaufmann");
    
    return result;
  }

  /**
   * Returns an enumeration describing the available options.
   * @return an enumeration of all the available options.
   **/
  public Enumeration listOptions () {
    Vector newVector = new Vector(4);
    newVector
      .addElement(new Option("\tSpecify the number of instances to\n" 
                             + "\tsample when estimating attributes.\n" 
                             + "\tIf not specified, then all instances\n" 
                             + "\twill be used.", "M", 1
                             , "-M <num instances>"));
    newVector.
      addElement(new Option("\tSeed for randomly sampling instances.\n" 
                            + "\t(Default = 1)", "D", 1
                            , "-D <seed>"));
    newVector.
      addElement(new Option("\tNumber of nearest neighbours (k) used\n" 
                            + "\tto estimate attribute relevances\n" 
                            + "\t(Default = 10).", "K", 1
                            , "-K <number of neighbours>"));
    newVector.
      addElement(new Option("\tWeight nearest neighbours by distance", "W"
                            , 0, "-W"));
    newVector.
      addElement(new Option("\tSpecify sigma value (used in an exp\n" 
                            + "\tfunction to control how quickly\n" 
                            + "\tweights for more distant instances\n" 
                            + "\tdecrease. Use in conjunction with -W.\n" 
                            + "\tSensible value=1/5 to 1/10 of the\n" 
                            + "\tnumber of nearest neighbours.\n" 
                            + "\t(Default = 2)", "A", 1, "-A <num>"));
    return  newVector.elements();
  }


  /**
   * Parses a given list of options. <p/>
   *
   <!-- options-start -->
   * Valid options are: <p/>
   * 
   * <pre> -M &lt;num instances&gt;
   *  Specify the number of instances to
   *  sample when estimating attributes.
   *  If not specified, then all instances
   *  will be used.</pre>
   * 
   * <pre> -D &lt;seed&gt;
   *  Seed for randomly sampling instances.
   *  (Default = 1)</pre>
   * 
   * <pre> -K &lt;number of neighbours&gt;
   *  Number of nearest neighbours (k) used
   *  to estimate attribute relevances
   *  (Default = 10).</pre>
   * 
   * <pre> -W
   *  Weight nearest neighbours by distance</pre>
   * 
   * <pre> -A &lt;num&gt;
   *  Specify sigma value (used in an exp
   *  function to control how quickly
   *  weights for more distant instances
   *  decrease. Use in conjunction with -W.
   *  Sensible value=1/5 to 1/10 of the
   *  number of nearest neighbours.
   *  (Default = 2)</pre>
   * 
   <!-- options-end -->
   *
   * @param options the list of options as an array of strings
   * @throws Exception if an option is not supported
   */
  public void setOptions (String[] options)
    throws Exception {
    String optionString;
    resetOptions();
    setWeightByDistance(Utils.getFlag('W', options));
    optionString = Utils.getOption('M', options);

    if (optionString.length() != 0) {
      setSampleSize(Integer.parseInt(optionString));
    }

    optionString = Utils.getOption('D', options);

    if (optionString.length() != 0) {
      setSeed(Integer.parseInt(optionString));
    }

    optionString = Utils.getOption('K', options);

    if (optionString.length() != 0) {
      setNumNeighbours(Integer.parseInt(optionString));
    }

    optionString = Utils.getOption('A', options);

    if (optionString.length() != 0) {
      setWeightByDistance(true); // turn on weighting by distance
      setSigma(Integer.parseInt(optionString));
    }
  }

  /**
   * Returns the tip text for this property
   * @return tip text for this property suitable for
   * displaying in the explorer/experimenter gui
   */
  public String sigmaTipText() {
    return "Set influence of nearest neighbours. Used in an exp function to "
      +"control how quickly weights decrease for more distant instances. "
      +"Use in conjunction with weightByDistance. Sensible values = 1/5 to "
      +"1/10 the number of nearest neighbours.";
  }

  /**
   * Sets the sigma value.
   *
   * @param s the value of sigma (> 0)
   * @throws Exception if s is not positive
   */
  public void setSigma (int s)
    throws Exception {
    if (s <= 0) {
      throw  new Exception("value of sigma must be > 0!");
    }

    m_sigma = s;
  }


  /**
   * Get the value of sigma.
   *
   * @return the sigma value.
   */
  public int getSigma () {
    return  m_sigma;
  }

  /**
   * Returns the tip text for this property
   * @return tip text for this property suitable for
   * displaying in the explorer/experimenter gui
   */
  public String numNeighboursTipText() {
    return "Number of nearest neighbours for attribute estimation.";
  }

  /**
   * Set the number of nearest neighbours
   *
   * @param n the number of nearest neighbours.
   */
  public void setNumNeighbours (int n) {
    m_Knn = n;
  }


  /**
   * Get the number of nearest neighbours
   *