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

/*
 *    GreedyStepwise.java
 *    Copyright (C) 2004 University of Waikato, Hamilton, New Zealand
 *
 */

package weka.attributeSelection;

import weka.core.Instances;
import weka.core.Option;
import weka.core.OptionHandler;
import weka.core.Range;
import weka.core.Utils;

import java.util.BitSet;
import java.util.Enumeration;
import java.util.Vector;

/** 
 <!-- globalinfo-start -->
 * GreedyStepwise :<br/>
 * <br/>
 * Performs a greedy forward or backward search through the space of attribute subsets. May start with no/all attributes or from an arbitrary point in the space. Stops when the addition/deletion of any remaining attributes results in a decrease in evaluation. Can also produce a ranked list of attributes by traversing the space from one side to the other and recording the order that attributes are selected.<br/>
 * <p/>
 <!-- globalinfo-end -->
 *
 <!-- options-start -->
 * Valid options are: <p/>
 * 
 * <pre> -C
 *  Use conservative forward search</pre>
 * 
 * <pre> -B
 *  Use a backward search instead of a
 *  forward one.</pre>
 * 
 * <pre> -P &lt;start set&gt;
 *  Specify a starting set of attributes.
 *  Eg. 1,3,5-7.</pre>
 * 
 * <pre> -R
 *  Produce a ranked list of attributes.</pre>
 * 
 * <pre> -T &lt;threshold&gt;
 *  Specify a theshold by which attributes
 *  may be discarded from the ranking.
 *  Use in conjuction with -R</pre>
 * 
 * <pre> -N &lt;num to select&gt;
 *  Specify number of attributes to select</pre>
 * 
 <!-- options-end -->
 *
 * @author Mark Hall
 * @version $Revision: 1.9 $
 */
public class GreedyStepwise 
  extends ASSearch 
  implements RankedOutputSearch, StartSetHandler, OptionHandler {
  
  /** for serialization */
  static final long serialVersionUID = -6312951970168325471L;

  /** does the data have a class */
  protected boolean m_hasClass;
 
  /** holds the class index */
  protected int m_classIndex;
 
  /** number of attributes in the data */
  protected int m_numAttribs;

  /** true if the user has requested a ranked list of attributes */
  protected boolean m_rankingRequested;

  /** 
   * go from one side of the search space to the other in order to generate
   * a ranking
   */
  protected boolean m_doRank;

  /** used to indicate whether or not ranking has been performed */
  protected boolean m_doneRanking;

  /**
   * A threshold by which to discard attributes---used by the
   * AttributeSelection module
   */
  protected double m_threshold;

  /** The number of attributes to select. -1 indicates that all attributes
      are to be retained. Has precedence over m_threshold */
  protected int m_numToSelect = -1;

  protected int m_calculatedNumToSelect;

  /** the merit of the best subset found */
  protected double m_bestMerit;

  /** a ranked list of attribute indexes */
  protected double [][] m_rankedAtts;
  protected int m_rankedSoFar;

  /** the best subset found */
  protected BitSet m_best_group;
  protected ASEvaluation m_ASEval;

  protected Instances m_Instances;

  /** holds the start set for the search as a Range */
  protected Range m_startRange;

  /** holds an array of starting attributes */
  protected int [] m_starting;

  /** Use a backwards search instead of a forwards one */
  protected boolean m_backward = false;

  /** If set then attributes will continue to be added during a forward
      search as long as the merit does not degrade */
  protected boolean m_conservativeSelection = false;

  /**
   * Constructor
   */
  public GreedyStepwise () {
    m_threshold = -Double.MAX_VALUE;
    m_doneRanking = false;
    m_startRange = new Range();
    m_starting = null;
    resetOptions();
  }

  /**
   * Returns a string describing this search method
   * @return a description of the search suitable for
   * displaying in the explorer/experimenter gui
   */
  public String globalInfo() {
    return "GreedyStepwise :\n\nPerforms a greedy forward or backward search "
      +"through "
      +"the space of attribute subsets. May start with no/all attributes or from "
      +"an arbitrary point in the space. Stops when the addition/deletion of any "
      +"remaining attributes results in a decrease in evaluation. "
      +"Can also produce a ranked list of "
      +"attributes by traversing the space from one side to the other and "
      +"recording the order that attributes are selected.\n";
  }

  /**
   * Returns the tip text for this property
   * @return tip text for this property suitable for
   * displaying in the explorer/experimenter gui
   */
  public String searchBackwardsTipText() {
    return "Search backwards rather than forwards.";
  }

  /**
   * Set whether to search backwards instead of forwards
   *
   * @param back true to search backwards
   */
  public void setSearchBackwards(boolean back) {
    m_backward = back;
    if (m_backward) {
      setGenerateRanking(false);
    }
  }

  /**
   * Get whether to search backwards
   *
   * @return true if the search will proceed backwards
   */
  public boolean getSearchBackwards() {
    return m_backward;
  }

  /**
   * Returns the tip text for this property
   * @return tip text for this property suitable for
   * displaying in the explorer/experimenter gui
   */
  public String thresholdTipText() {
    return "Set threshold by which attributes can be discarded. Default value "
      + "results in no attributes being discarded. Use in conjunction with "
      + "generateRanking";
  }

  /**
   * Set the threshold by which the AttributeSelection module can discard
   * attributes.
   * @param threshold the threshold.
   */
  public void setThreshold(double threshold) {
    m_threshold = threshold;
  }

  /**
   * Returns the threshold so that the AttributeSelection module can
   * discard attributes from the ranking.
   */
  public double getThreshold() {
    return m_threshold;
  }

  /**
   * Returns the tip text for this property
   * @return tip text for this property suitable for
   * displaying in the explorer/experimenter gui
   */
  public String numToSelectTipText() {
    return "Specify the number of attributes to retain. The default value "
      +"(-1) indicates that all attributes are to be retained. Use either "
      +"this option or a threshold to reduce the attribute set.";
  }

  /**
   * Specify the number of attributes to select from the ranked list
   * (if generating a ranking). -1
   * indicates that all attributes are to be retained.
   * @param n the number of attributes to retain
   */
  public void setNumToSelect(int n) {
    m_numToSelect = n;
  }

  /**
   * Gets the number of attributes to be retained.
   * @return the number of attributes to retain
   */
  public int getNumToSelect() {
    return m_numToSelect;
  }

  /**
   * Gets the calculated number of attributes to retain. This is the
   * actual number of attributes to retain. This is the same as
   * getNumToSelect if the user specifies a number which is not less
   * than zero. Otherwise it should be the number of attributes in the
   * (potentially transformed) data.
   */
  public int getCalculatedNumToSelect() {
    if (m_numToSelect >= 0) {
      m_calculatedNumToSelect = m_numToSelect;
    }
    return m_calculatedNumToSelect;
  }

  /**
   * Returns the tip text for this property
   * @return tip text for this property suitable for
   * displaying in the explorer/experimenter gui
   */
  public String generateRankingTipText() {
    return "Set to true if a ranked list is required.";
  }
  
  /**
   * Records whether the user has requested a ranked list of attributes.
   * @param doRank true if ranking is requested
   */
  public void setGenerateRanking(boolean doRank) {
    m_rankingRequested = doRank;
  }

  /**
   * Gets whether ranking has been requested. This is used by the
   * AttributeSelection module to determine if rankedAttributes()
   * should be called.
   * @return true if ranking has been requested.
   */
  public boolean getGenerateRanking() {
    return m_rankingRequested;
  }

  /**
   * Returns the tip text for this property
   * @return tip text for this property suitable for
   * displaying in the explorer/experimenter gui
   */
  public String startSetTipText() {
    return "Set the start point for the search. This is specified as a comma "
      +"seperated list off attribute indexes starting at 1. It can include "
      +"ranges. Eg. 1,2,5-9,17.";
  }

  /**
   * Sets a starting set of attributes for the search. It is the
   * search method's responsibility to report this start set (if any)
   * in its toString() method.
   * @param startSet a string containing a list of attributes (and or ranges),
   * eg. 1,2,6,10-15.
   * @throws Exception if start set can't be set.
   */
  public void setStartSet (String startSet) throws Exception {
    m_startRange.setRanges(startSet);
  }

  /**
   * Returns a list of attributes (and or attribute ranges) as a String
   * @return a list of attributes (and or attribute ranges)
   */
  public String getStartSet () {
    return m_startRange.getRanges();
  }

  /**
   * Returns the tip text for this property
   * @return tip text for this property suitable for
   * displaying in the explorer/experimenter gui
   */
  public String conservativeForwardSelectionTipText() {
    return "If true (and forward search is selected) then attributes "
      +"will continue to be added to the best subset as long as merit does "
      +"not degrade.";
  }

  /**
   * Set whether attributes should continue to be added during
   * a forward search as long as merit does not decrease
   * @param c true if atts should continue to be atted
   */
  public void setConservativeForwardSelection(boolean c) {
    m_conservativeSelection = c;
  }

  /**
   * Gets whether conservative selection has been enabled
   * @return true if conservative forward selection is enabled
   */
  public boolean getConservativeForwardSelection() {
    return m_conservativeSelection;
  }

  /**
   * Returns an enumeration describing the available options.
   * @return an enumeration of all the available options.
   **/
  public Enumeration listOptions () {
    Vector newVector = new Vector(5);

    newVector.addElement(new Option("\tUse conservative forward search"
				    ,"-C", 0, "-C"));

    newVector.addElement(new Option("\tUse a backward search instead of a"
				    +"\n\tforward one."
				    ,"-B", 0, "-B"));
    newVector
      .addElement(new Option("\tSpecify a starting set of attributes." 
			     + "\n\tEg. 1,3,5-7."
			     ,"P",1
			     , "-P <start set>"));

    newVector.addElement(new Option("\tProduce a ranked list of attributes."
				    ,"R",0,"-R"));
    newVector
      .addElement(new Option("\tSpecify a theshold by which attributes" 
			     + "\n\tmay be discarded from the ranking."
			     +"\n\tUse in conjuction with -R","T",1
			     , "-T <threshold>"));

    newVector
      .addElement(new Option("\tSpecify number of attributes to select" 
			     ,"N",1
			     , "-N <num to select>"));

    return newVector.elements();

  }
  
  /**
   * Parses a given list of options. <p/>
   *
   <!-- options-start -->
   * Valid options are: <p/>
   * 
   * <pre> -C
   *  Use conservative forward search</pre>
   * 
   * <pre> -B
   *  Use a backward search instead of a
   *  forward one.</pre>
   * 
   * <pre> -P &lt;start set&gt;