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

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

package weka.attributeSelection;

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

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

/** 
 <!-- globalinfo-start -->
 * RankSearch : <br/>
 * <br/>
 * Uses an attribute/subset evaluator to rank all attributes. If a subset evaluator is specified, then a forward selection search is used to generate a ranked list. From the ranked list of attributes, subsets of increasing size are evaluated, ie. The best attribute, the best attribute plus the next best attribute, etc.... The best attribute set is reported. RankSearch is linear in the number of attributes if a simple attribute evaluator is used such as GainRatioAttributeEval.<br/>
 * <p/>
 <!-- globalinfo-end -->
 *
 <!-- options-start -->
 * Valid options are: <p/>
 * 
 * <pre> -A &lt;attribute evaluator&gt;
 *  class name of attribute evaluator to use for ranking. Place any
 *  evaluator options LAST on the command line following a "--".
 *  eg.:
 *   -A weka.attributeSelection.GainRatioAttributeEval ... -- -M
 *  (default: weka.attributeSelection.GainRatioAttributeEval)</pre>
 * 
 * <pre> -S &lt;step size&gt;
 *  number of attributes to be added from the
 *  ranking in each iteration (default = 1).</pre>
 * 
 * <pre> -R &lt;start point&gt;
 *  point in the ranking to start evaluating from. 
 *  (default = 0, ie. the head of the ranking).</pre>
 * 
 * <pre> 
 * Options specific to evaluator weka.attributeSelection.GainRatioAttributeEval:
 * </pre>
 * 
 * <pre> -M
 *  treat missing values as a seperate value.</pre>
 * 
 <!-- options-end -->
 *
 * @author Mark Hall ([e-mail])
 * @version $Revision: 1.17 $
 */
public class RankSearch 
  extends ASSearch 
  implements OptionHandler {
  
  /** for serialization */
  static final long serialVersionUID = -7992268736874353755L;

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

  /** the best subset found */
  private BitSet m_best_group;

  /** the attribute evaluator to use for generating the ranking */
  private ASEvaluation m_ASEval;

  /** the subset evaluator with which to evaluate the ranking */
  private ASEvaluation m_SubsetEval;

  /** the training instances */
  private Instances m_Instances;

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

  /** will hold the attribute ranking */
  private int [] m_Ranking;

  /** add this many attributes in each iteration from the ranking */
  protected int m_add = 1;

  /** start from this point in the ranking */
  protected int m_startPoint = 0;

  /**
   * Returns a string describing this search method
   * @return a description of the search method suitable for
   * displaying in the explorer/experimenter gui
   */
  public String globalInfo() {
    return "RankSearch : \n\n"
      +"Uses an attribute/subset evaluator to rank all attributes. "
      +"If a subset evaluator is specified, then a forward selection "
      +"search is used to generate a ranked list. From the ranked "
      +"list of attributes, subsets of increasing size are evaluated, ie. "
      +"The best attribute, the best attribute plus the next best attribute, "
      +"etc.... The best attribute set is reported. RankSearch is linear in "
      +"the number of attributes if a simple attribute evaluator is used "
      +"such as GainRatioAttributeEval.\n";
  }

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

  /**
   * Returns the tip text for this property
   * @return tip text for this property suitable for
   * displaying in the explorer/experimenter gui
   */
  public String attributeEvaluatorTipText() {
    return "Attribute evaluator to use for generating a ranking.";    
  }

  /**
   * Set the attribute evaluator to use for generating the ranking.
   * @param newEvaluator the attribute evaluator to use.
   */
  public void setAttributeEvaluator(ASEvaluation newEvaluator) {
    m_ASEval = newEvaluator;
  }

  /**
   * Get the attribute evaluator used to generate the ranking.
   * @return the evaluator used to generate the ranking.
   */
  public ASEvaluation getAttributeEvaluator() {
    return m_ASEval;
  }

  /**
   * Returns the tip text for this property
   * @return tip text for this property suitable for
   * displaying in the explorer/experimenter gui
   */
  public String stepSizeTipText() {
    return "Add this many attributes from the ranking in each iteration.";
  }

  /**
   * Set the number of attributes to add from the rankining
   * in each iteration
   * @param ss the number of attribes to add.
   */
  public void setStepSize(int ss) {
    if (ss > 0) {
      m_add = ss;
    }
  }

  /**
   * Get the number of attributes to add from the rankining
   * in each iteration
   * @return the number of attributes to add.
   */
  public int getStepSize() {
    return m_add;
  }

  /**
   * Returns the tip text for this property
   * @return tip text for this property suitable for
   * displaying in the explorer/experimenter gui
   */
  public String startPointTipText() {
    return "Start evaluating from this point in the ranking.";
  }

  /**
   * Set the point at which to start evaluating the ranking
   * @param sp the position in the ranking to start at
   */
  public void setStartPoint(int sp) {
    if (sp >= 0) {
      m_startPoint = sp;
    }
  }

  /**
   * Get the point at which to start evaluating the ranking
   * @return the position in the ranking to start at
   */
  public int getStartPoint() {
    return m_startPoint;
  }

  /**
   * 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(
        "\tclass name of attribute evaluator to use for ranking. Place any\n" 
        + "\tevaluator options LAST on the command line following a \"--\".\n" 
        + "\teg.:\n"
        + "\t\t-A weka.attributeSelection.GainRatioAttributeEval ... -- -M\n"
        + "\t(default: weka.attributeSelection.GainRatioAttributeEval)", 
        "A", 1, "-A <attribute evaluator>"));
    
    newVector.addElement(new Option(
        "\tnumber of attributes to be added from the"
        +"\n\tranking in each iteration (default = 1).", 
        "S", 1,"-S <step size>"));
    
    newVector.addElement(new Option(
        "\tpoint in the ranking to start evaluating from. "
        +"\n\t(default = 0, ie. the head of the ranking).", 
        "R", 1,"-R <start point>"));

    if ((m_ASEval != null) && 
        (m_ASEval instanceof OptionHandler)) {
      newVector.addElement(new Option("", "", 0, "\nOptions specific to " 
                                      + "evaluator " 
                                      + m_ASEval.getClass().getName() 
                                      + ":"));
      Enumeration enu = ((OptionHandler)m_ASEval).listOptions();

      while (enu.hasMoreElements()) {
        newVector.addElement(enu.nextElement());
      }
    }

    return newVector.elements();
  }