weka.attributeSelection
Class ForwardSelection

java.lang.Object
  extended byweka.attributeSelection.ASSearch
      extended byweka.attributeSelection.ForwardSelection
All Implemented Interfaces:
OptionHandler, RankedOutputSearch, java.io.Serializable, StartSetHandler

public class ForwardSelection
extends ASSearch
implements RankedOutputSearch, StartSetHandler, OptionHandler

Class for performing a forward selection hill climbing search.

Valid options are:

-P
Specify a starting set of attributes. Eg 1,4,7-9.

-R
Produce a ranked list of attributes.

-T
Specify a threshold by which the AttributeSelection module can.
discard attributes. Use in conjunction with -R

Version:
$Revision: 1.15 $
Author:
Mark Hall (mhall@cs.waikato.ac.nz)
See Also:
Serialized Form

Field Summary
private  ASEvaluation m_ASEval
           
private  java.util.BitSet m_best_group
          the best subset found
private  double m_bestMerit
          the merit of the best subset found
private  int m_calculatedNumToSelect
           
private  int m_classIndex
          holds the class index
private  boolean m_doneRanking
          used to indicate whether or not ranking has been performed
private  boolean m_doRank
          go from one side of the search space to the other in order to generate a ranking
private  boolean m_hasClass
          does the data have a class
private  Instances m_Instances
           
private  int m_numAttribs
          number of attributes in the data
private  int m_numToSelect
          The number of attributes to select. -1 indicates that all attributes are to be retained.
private  double[][] m_rankedAtts
          a ranked list of attribute indexes
private  int m_rankedSoFar
           
private  boolean m_rankingRequested
          true if the user has requested a ranked list of attributes
private  int[] m_starting
          holds an array of starting attributes
private  Range m_startRange
          holds the start set for the search as a Range
private  double m_threshold
          A threshold by which to discard attributes---used by the AttributeSelection module
 
Constructor Summary
ForwardSelection()
           
 
Method Summary
private  int[] attributeList(java.util.BitSet group)
          converts a BitSet into a list of attribute indexes
private  void determineNumToSelectFromThreshold(double[][] ranking)
           
 java.lang.String generateRankingTipText()
          Returns the tip text for this property
 int getCalculatedNumToSelect()
          Gets the calculated number of attributes to retain.
 boolean getGenerateRanking()
          Gets whether ranking has been requested.
 int getNumToSelect()
          Gets the number of attributes to be retained.
 java.lang.String[] getOptions()
          Gets the current settings of ReliefFAttributeEval.
 java.lang.String getStartSet()
          Returns a list of attributes (and or attribute ranges) as a String
 double getThreshold()
          Returns the threshold so that the AttributeSelection module can discard attributes from the ranking.
 java.lang.String globalInfo()
          Returns a string describing this search method
 java.util.Enumeration listOptions()
          Returns an enumeration describing the available options.
 java.lang.String numToSelectTipText()
          Returns the tip text for this property
 double[][] rankedAttributes()
          Produces a ranked list of attributes.
private  void resetOptions()
          Resets options
 int[] search(ASEvaluation ASEval, Instances data)
          Searches the attribute subset space by forward selection.
 void setGenerateRanking(boolean doRank)
          Records whether the user has requested a ranked list of attributes.
 void setNumToSelect(int n)
          Specify the number of attributes to select from the ranked list (if generating a ranking). -1 indicates that all attributes are to be retained.
 void setOptions(java.lang.String[] options)
          Parses a given list of options.
 void setStartSet(java.lang.String startSet)
          Sets a starting set of attributes for the search.
 void setThreshold(double threshold)
          Set the threshold by which the AttributeSelection module can discard attributes.
 java.lang.String startSetTipText()
          Returns the tip text for this property
private  java.lang.String startSetToString()
          converts the array of starting attributes to a string.
 java.lang.String thresholdTipText()
          Returns the tip text for this property
 java.lang.String toString()
          returns a description of the search.
 
Methods inherited from class weka.attributeSelection.ASSearch
forName
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

m_hasClass

private boolean m_hasClass
does the data have a class


m_classIndex

private int m_classIndex
holds the class index


m_numAttribs

private int m_numAttribs
number of attributes in the data


m_rankingRequested

private boolean m_rankingRequested
true if the user has requested a ranked list of attributes


m_doRank

private boolean m_doRank
go from one side of the search space to the other in order to generate a ranking


m_doneRanking

private boolean m_doneRanking
used to indicate whether or not ranking has been performed


m_threshold

private double m_threshold
A threshold by which to discard attributes---used by the AttributeSelection module


m_numToSelect

private int m_numToSelect
The number of attributes to select. -1 indicates that all attributes are to be retained. Has precedence over m_threshold


m_calculatedNumToSelect

private int m_calculatedNumToSelect

m_bestMerit

private double m_bestMerit
the merit of the best subset found


m_rankedAtts

private double[][] m_rankedAtts
a ranked list of attribute indexes


m_rankedSoFar

private int m_rankedSoFar

m_best_group

private java.util.BitSet m_best_group
the best subset found


m_ASEval

private ASEvaluation m_ASEval

m_Instances

private Instances m_Instances

m_startRange

private Range m_startRange
holds the start set for the search as a Range


m_starting

private int[] m_starting
holds an array of starting attributes

Constructor Detail

ForwardSelection

public ForwardSelection()
Method Detail

globalInfo

public java.lang.String globalInfo()
Returns a string describing this search method

Returns:
a description of the search suitable for displaying in the explorer/experimenter gui

thresholdTipText

public java.lang.String thresholdTipText()
Returns the tip text for this property

Returns:
tip text for this property suitable for displaying in the explorer/experimenter gui

setThreshold

public void setThreshold(double threshold)
Set the threshold by which the AttributeSelection module can discard attributes.

Specified by:
setThreshold in interface RankedOutputSearch
Parameters:
threshold - the threshold.

getThreshold

public double getThreshold()
Returns the threshold so that the AttributeSelection module can discard attributes from the ranking.

Specified by:
getThreshold in interface RankedOutputSearch
Returns:
a threshold by which to discard attributes

numToSelectTipText

public java.lang.String numToSelectTipText()
Returns the tip text for this property

Returns:
tip text for this property suitable for displaying in the explorer/experimenter gui

setNumToSelect

public void setNumToSelect(int n)
Specify the number of attributes to select from the ranked list (if generating a ranking). -1 indicates that all attributes are to be retained.

Specified by:
setNumToSelect in interface RankedOutputSearch
Parameters:
n - the number of attributes to retain

getNumToSelect

public int getNumToSelect()
Gets the number of attributes to be retained.

Specified by:
getNumToSelect in interface RankedOutputSearch
Returns:
the number of attributes to retain

getCalculatedNumToSelect

public int getCalculatedNumToSelect()
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.

Specified by:
getCalculatedNumToSelect in interface RankedOutputSearch

generateRankingTipText

public java.lang.String generateRankingTipText()
Returns the tip text for this property

Returns:
tip text for this property suitable for displaying in the explorer/experimenter gui

setGenerateRanking

public void setGenerateRanking(boolean doRank)
Records whether the user has requested a ranked list of attributes.

Specified by:
setGenerateRanking in interface RankedOutputSearch
Parameters:
doRank - true if ranking is requested

getGenerateRanking

public boolean getGenerateRanking()
Gets whether ranking has been requested. This is used by the AttributeSelection module to determine if rankedAttributes() should be called.

Specified by:
getGenerateRanking in interface RankedOutputSearch
Returns:
true if ranking has been requested.

startSetTipText

public java.lang.String startSetTipText()
Returns the tip text for this property

Returns:
tip text for this property suitable for displaying in the explorer/experimenter gui

setStartSet

public void setStartSet(java.lang.String startSet)
                 throws java.lang.Exception
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.

Specified by:
setStartSet in interface StartSetHandler
Parameters:
startSet - a string containing a list of attributes (and or ranges), eg. 1,2,6,10-15.
Throws:
java.lang.Exception - if start set can't be set.

getStartSet

public java.lang.String getStartSet()
Returns a list of attributes (and or attribute ranges) as a String

Specified by:
getStartSet in interface StartSetHandler
Returns:
a list of attributes (and or attribute ranges)

listOptions

public java.util.Enumeration listOptions()
Returns an enumeration describing the available options.

Specified by:
listOptions in interface OptionHandler
Returns:
an enumeration of all the available options.

setOptions

public void setOptions(java.lang.String[] options)
                throws java.lang.Exception
Parses a given list of options. Valid options are:

-P
Specify a starting set of attributes. Eg 1,4,7-9.

-R
Produce a ranked list of attributes.

-T
Specify a threshold by which the AttributeSelection module can
discard attributes. Use in conjunction with -R

-N
Specify the number of attributes to retain. Overides any threshold.

Specified by:
setOptions in interface OptionHandler
Parameters:
options - the list of options as an array of strings
Throws:
java.lang.Exception - if an option is not supported

getOptions

public java.lang.String[] getOptions()
Gets the current settings of ReliefFAttributeEval.

Specified by:
getOptions in interface OptionHandler
Returns:
an array of strings suitable for passing to setOptions()

startSetToString

private java.lang.String startSetToString()
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.

Returns:
a comma seperated list of individual attribute numbers as a String

toString

public java.lang.String toString()
returns a description of the search.

Returns:
a description of the search as a String.

search

public int[] search(ASEvaluation ASEval,
                    Instances data)
             throws java.lang.Exception
Searches the attribute subset space by forward selection.

Specified by:
search in class ASSearch
Parameters:
data - the training instances.
ASEval - the attribute evaluator to guide the search
Returns:
an array (not necessarily ordered) of selected attribute indexes
Throws:
java.lang.Exception - if the search can't be completed

rankedAttributes

public double[][] rankedAttributes()
                            throws java.lang.Exception
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.

Specified by:
rankedAttributes in interface RankedOutputSearch
Returns:
an array of attribute indexes and associated merit values
Throws:
java.lang.Exception - if something goes wrong.

determineNumToSelectFromThreshold

private void determineNumToSelectFromThreshold(double[][] ranking)

attributeList

private int[] attributeList(java.util.BitSet group)
converts a BitSet into a list of attribute indexes

Parameters:
group - the BitSet to convert
Returns:
an array of attribute indexes

resetOptions

private void resetOptions()
Resets options