content: /*
   *    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.RevisionUtils;
  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: 7266 $
   */
  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;
     *  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 -->
     *
     * @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();
  
      setSearchBackwards(Utils.getFlag('B', options));
  
      setConservativeForwardSelection(Utils.getFlag('C', options));
  
      optionString = Utils.getOption('P', options);
      if (optionString.length() != 0) {
        setStartSet(optionString);
      }
  
      setGenerateRanking(Utils.getFlag('R', options));
  
      optionString = Utils.getOption('T', options);
      if (optionString.length() != 0) {
        Double temp;
        temp = Double.valueOf(optionString);
        setThreshold(temp.doubleValue());
      }
  
      optionString = Utils.getOption('N', options);
      if (optionString.length() != 0) {
        setNumToSelect(Integer.parseInt(optionString));
      }
    }
  
    /**
     * Gets the current settings of ReliefFAttributeEval.
     *
     * @return an array of strings suitable for passing to setOptions()
     */
    public String[] getOptions () {
      String[] options = new String[9];
      int current = 0;
      
      if (getSearchBackwards()) {
        options[current++] = "-B";
      }
  
      if (getConservativeForwardSelection()) {
        options[current++] = "-C";
      }
  
      if (!(getStartSet().equals(""))) {
        options[current++] = "-P";
        options[current++] = ""+startSetToString();
      }
  
      if (getGenerateRanking()) {
        options[current++] = "-R";
      }
      options[current++] = "-T";
      options[current++] = "" + getThreshold();
  
      options[current++] = "-N";
      options[current++] = ""+getNumToSelect();
  
      while (current < options.length) {
        options[current++] = "";
      }
      return  options;
    }
  
    /**
     * converts the array of starting attributes to a string. This is
     * used by getOptions to return the actual attributes specified
     * as the starting set. This is better than using m_startRanges.getRanges()
     * as the same start set can be specified in different ways from the
     * command line---eg 1,2,3 == 1-3. This is to ensure that stuff that
     * is stored in a database is comparable.
     * @return a comma seperated list of individual attribute numbers as a String
     */
    protected String startSetToString() {
      StringBuffer FString = new StringBuffer();
      boolean didPrint;
      
      if (m_starting == null) {
        return getStartSet();
      }
      for (int i = 0; i < m_starting.length; i++) {
        didPrint = false;
        
        if ((m_hasClass == false) || 
  	  (m_hasClass == true && i != m_classIndex)) {
  	FString.append((m_starting[i] + 1));
  	didPrint = true;
        }
        
        if (i == (m_starting.length - 1)) {
  	FString.append("");
        }
        else {
  	if (didPrint) {
  	  FString.append(",");
  	  }
        }
      }
  
      return FString.toString();
    }
  
    /**
     * returns a description of the search.
     * @return a description of the search as a String.
     */
    public String toString() {
      StringBuffer FString = new StringBuffer();
      FString.append("\tGreedy Stepwise ("
  		   + ((m_backward)
  		      ? "backwards)"
  		      : "forwards)")+".\n\tStart set: ");
  
      if (m_starting == null) {
        if (m_backward) {
  	FString.append("all attributes\n");
        } else {
  	FString.append("no attributes\n");
        }
      }
      else {
        FString.append(startSetToString()+"\n");
      }
      if (!m_doneRanking) {
        FString.append("\tMerit of best subset found: "
  		     +Utils.doubleToString(Math.abs(m_bestMerit),8,3)+"\n");
      } else {
        if (m_backward) {
          FString.append("\n\tRanking is the order that attributes were removed, " +
          		"starting \n\twith all attributes. The merit scores in the left" +
          		"\n\tcolumn are the goodness of the remaining attributes in the" +
          		"\n\tsubset after removing the corresponding in the right column" +
          		"\n\tattribute from the subset.\n");
        } else {
          FString.append("\n\tRanking is the order that attributes were added, starting " +
          		"\n\twith no attributes. The merit scores in the left column" +
          		"\n\tare the goodness of the subset after the adding the" +
          		"\n\tcorresponding attribute in the right column to the subset.\n");
        }
      }
      
      if ((m_threshold != -Double.MAX_VALUE) && (m_doneRanking)) {
        FString.append("\tThreshold for discarding attributes: "
  		     + Utils.doubleToString(m_threshold,8,4)+"\n");
      }
  
      return FString.toString();
    }
  
  
    /**
     * Searches the attribute subset space by forward selection.
     *
     * @param ASEval the attribute evaluator to guide the search
     * @param data the training instances.
     * @return an array (not necessarily ordered) of selected attribute indexes
     * @throws Exception if the search can't be completed
     */
    public int[] search (ASEvaluation ASEval, Instances data)
      throws Exception {
  
      int i;
      double best_merit = -Double.MAX_VALUE;
      double temp_best,temp_merit;
      int temp_index=0;
      BitSet temp_group;
  
      if (data != null) { // this is a fresh run so reset
        resetOptions();
        m_Instances = data;
      }
      m_ASEval = ASEval;
  
      m_numAttribs = m_Instances.numAttributes();
  
      if (m_best_group == null) {
        m_best_group = new BitSet(m_numAttribs);
      }
  
      if (!(m_ASEval instanceof SubsetEvaluator)) {
        throw  new Exception(m_ASEval.getClass().getName() 
  			   + " is not a " 
  			   + "Subset evaluator!");
      }
  
      m_startRange.setUpper(m_numAttribs-1);
      if (!(getStartSet().equals(""))) {
        m_starting = m_startRange.getSelection();
      }
  
      if (m_ASEval instanceof UnsupervisedSubsetEvaluator) {
        m_hasClass = false;
        m_classIndex = -1;
      }
      else {
        m_hasClass = true;
        m_classIndex = m_Instances.classIndex();
      }
  
      SubsetEvaluator ASEvaluator = (SubsetEvaluator)m_ASEval;
  
      if (m_rankedAtts == null) {
        m_rankedAtts = new double[m_numAttribs][2];
        m_rankedSoFar = 0;
      }
  
      // If a starting subset has been supplied, then initialise the bitset
      if (m_starting != null && m_rankedSoFar <= 0) {
        for (i = 0; i < m_starting.length; i++) {
  	if ((m_starting[i]) != m_classIndex) {
  	  m_best_group.set(m_starting[i]);
  	}
        }
      } else {
        if (m_backward && m_rankedSoFar <= 0) {
  	for (i = 0; i < m_numAttribs; i++) {
  	  if (i != m_classIndex) {
  	    m_best_group.set(i);
  	  }
  	}
        }
      }
  
      // Evaluate the initial subset
      best_merit = ASEvaluator.evaluateSubset(m_best_group);
  
      // main search loop
      boolean done = false;
      boolean addone = false;
      boolean z;
      while (!done) {
        temp_group = (BitSet)m_best_group.clone();
        temp_best = best_merit;
        if (m_doRank) {
  	temp_best = -Double.MAX_VALUE;
        }
        done = true;
        addone = false;
        for (i=0;i<m_numAttribs;i++) {
  	if (m_backward) {
  	  z = ((i != m_classIndex) && (temp_group.get(i)));
  	} else {
  	  z = ((i != m_classIndex) && (!temp_group.get(i)));
  	}
  	if (z) {
  	  // set/unset the bit
  	  if (m_backward) {
  	    temp_group.clear(i);
  	  } else {
  	    temp_group.set(i);
  	  }
  	  temp_merit = ASEvaluator.evaluateSubset(temp_group);
  	  if (m_backward) {
  	    z = (temp_merit >= temp_best);
  	  } else {
              if (m_conservativeSelection) {
                z = (temp_merit >= temp_best);
              } else {
                z = (temp_merit > temp_best);
              }
  	  }
  
  	  if (z) {
              temp_best = temp_merit;
              temp_index = i;
              addone = true;
              done = false;
  	  }
  
  	  // unset this addition/deletion
  	  if (m_backward) {
  	    temp_group.set(i);
  	  } else {
  	    temp_group.clear(i);
  	  }
  	  if (m_doRank) {
  	    done = false;
  	  }
  	}
        }
        if (addone) {
  	if (m_backward) {
  	  m_best_group.clear(temp_index);
  	} else {
  	  m_best_group.set(temp_index);
  	}
  	best_merit = temp_best;
  	m_rankedAtts[m_rankedSoFar][0] = temp_index;
  	m_rankedAtts[m_rankedSoFar][1] = best_merit;
  	m_rankedSoFar++;
        }
      }
      m_bestMerit = best_merit;
      return attributeList(m_best_group);
    }
  
    /**
     * Produces a ranked list of attributes. Search must have been performed
     * prior to calling this function. Search is called by this function to
     * complete the traversal of the the search space. A list of
     * attributes and merits are returned. The attributes a ranked by the
     * order they are added to the subset during a forward selection search.
     * Individual merit values reflect the merit associated with adding the
     * corresponding attribute to the subset; because of this, merit values
     * may initially increase but then decrease as the best subset is
     * "passed by" on the way to the far side of the search space.
     *
     * @return an array of attribute indexes and associated merit values
     * @throws Exception if something goes wrong.
     */
    public double [][] rankedAttributes() throws Exception {
      
      if (m_rankedAtts == null || m_rankedSoFar == -1) {
        throw new Exception("Search must be performed before attributes "
  			  +"can be ranked.");
      }
      
      m_doRank = true;
      search (m_ASEval, null);
  
      double [][] final_rank = new double [m_rankedSoFar][2];
      for (int i=0;i<m_rankedSoFar;i++) {
        final_rank[i][0] = m_rankedAtts[i][0];
        final_rank[i][1] = m_rankedAtts[i][1];
      }
      
      resetOptions();
      m_doneRanking = true;
  
      if (m_numToSelect > final_rank.length) {
        throw new Exception("More attributes requested than exist in the data");
      }
  
      if (m_numToSelect <= 0) {
        if (m_threshold == -Double.MAX_VALUE) {
  	m_calculatedNumToSelect = final_rank.length;
        } else {
  	determineNumToSelectFromThreshold(final_rank);
        }
      }
  
      return final_rank;
    }
  
    private void determineNumToSelectFromThreshold(double [][] ranking) {
      int count = 0;
      for (int i = 0; i < ranking.length; i++) {
        if (ranking[i][1] > m_threshold) {
  	count++;
        }
      }
      m_calculatedNumToSelect = count;
    }
  
    /**
     * converts a BitSet into a list of attribute indexes 
     * @param group the BitSet to convert
     * @return an array of attribute indexes
     **/
    protected int[] attributeList (BitSet group) {
      int count = 0;
  
      // count how many were selected
      for (int i = 0; i < m_numAttribs; i++) {
        if (group.get(i)) {
  	count++;
        }
      }
  
      int[] list = new int[count];
      count = 0;
  
      for (int i = 0; i < m_numAttribs; i++) {
        if (group.get(i)) {
  	list[count++] = i;
        }
      }
  
      return  list;
    }
  
    /**
     * Resets options
     */
    protected void resetOptions() {
      m_doRank = false;
      m_best_group = null;
      m_ASEval = null;
      m_Instances = null;
      m_rankedSoFar = -1;
      m_rankedAtts = null;
    }
    
    /**
     * Returns the revision string.
     * 
     * @return		the revision
     */
    public String getRevision() {
      return RevisionUtils.extract("$Revision: 7266 $");
    }
  }
  