weka.attributeSelection

Class GreedyStepwise

java.lang.Object

weka.attributeSelection.ASSearch

weka.attributeSelection.GreedyStepwise

All Implemented Interfaces:

Serializable, RankedOutputSearch, StartSetHandler, OptionHandler, RevisionHandler

public class GreedyStepwise
extends ASSearch
implements RankedOutputSearch, StartSetHandler, OptionHandler

GreedyStepwise :

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.

Valid options are:

 -C
  Use conservative forward search

 -B
  Use a backward search instead of a
  forward one.

 -P <start set>
  Specify a starting set of attributes.
  Eg. 1,3,5-7.

 -R
  Produce a ranked list of attributes.

 -T <threshold>
  Specify a theshold by which attributes
  may be discarded from the ranking.
  Use in conjuction with -R

 -N <num to select>
  Specify number of attributes to select

Version:

$Revision: 7267 $

Author:

Mark Hall

See Also:

Serialized Form

Field Summary

Fields

Modifier and Type	Field and Description
protected ASEvaluation	m_ASEval
protected boolean	m_backward Use a backwards search instead of a forwards one
protected BitSet	m_best_group the best subset found
protected double	m_bestMerit the merit of the best subset found
protected int	m_calculatedNumToSelect
protected int	m_classIndex holds the class index
protected boolean	m_conservativeSelection If set then attributes will continue to be added during a forward search as long as the merit does not degrade
protected boolean	m_doneRanking used to indicate whether or not ranking has been performed
protected boolean	m_doRank go from one side of the search space to the other in order to generate a ranking
protected boolean	m_hasClass does the data have a class
protected Instances	m_Instances
protected int	m_numAttribs number of attributes in the data
protected int	m_numToSelect The number of attributes to select.
protected double[][]	m_rankedAtts a ranked list of attribute indexes
protected int	m_rankedSoFar
protected boolean	m_rankingRequested true if the user has requested a ranked list of attributes
protected int[]	m_starting holds an array of starting attributes
protected Range	m_startRange holds the start set for the search as a Range
protected double	m_threshold A threshold by which to discard attributes---used by the AttributeSelection module

Constructor Summary

Constructors

Constructor and Description
GreedyStepwise() Constructor

Method Summary

Modifier and Type	Method and Description
protected int[]	attributeList(BitSet group) converts a BitSet into a list of attribute indexes
String	conservativeForwardSelectionTipText() Returns the tip text for this property
String	generateRankingTipText() Returns the tip text for this property
int	getCalculatedNumToSelect() Gets the calculated number of attributes to retain.
boolean	getConservativeForwardSelection() Gets whether conservative selection has been enabled
boolean	getGenerateRanking() Gets whether ranking has been requested.
int	getNumToSelect() Gets the number of attributes to be retained.
String[]	getOptions() Gets the current settings of ReliefFAttributeEval.
String	getRevision() Returns the revision string.
boolean	getSearchBackwards() Get whether to search backwards
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.
String	globalInfo() Returns a string describing this search method
Enumeration	listOptions() Returns an enumeration describing the available options.
String	numToSelectTipText() Returns the tip text for this property
double[][]	rankedAttributes() Produces a ranked list of attributes.
protected void	resetOptions() Resets options
int[]	search(ASEvaluation ASEval, Instances data) Searches the attribute subset space by forward selection.
String	searchBackwardsTipText() Returns the tip text for this property
void	setConservativeForwardSelection(boolean c) Set whether attributes should continue to be added during a forward search as long as merit does not decrease
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).
void	setOptions(String[] options) Parses a given list of options.
void	setSearchBackwards(boolean back) Set whether to search backwards instead of forwards
void	setStartSet(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.
String	startSetTipText() Returns the tip text for this property
protected String	startSetToString() converts the array of starting attributes to a string.
String	thresholdTipText() Returns the tip text for this property
String	toString() returns a description of the search.

Methods inherited from class weka.attributeSelection.ASSearch

forName, makeCopies

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

m_hasClass

protected boolean m_hasClass

does the data have a class

m_classIndex

protected int m_classIndex

holds the class index

m_numAttribs

protected int m_numAttribs

number of attributes in the data

m_rankingRequested

protected boolean m_rankingRequested

true if the user has requested a ranked list of attributes

m_doRank

protected boolean m_doRank

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

m_doneRanking

protected boolean m_doneRanking

used to indicate whether or not ranking has been performed

m_threshold

protected double m_threshold

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

m_numToSelect

protected 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

protected int m_calculatedNumToSelect

m_bestMerit

protected double m_bestMerit

the merit of the best subset found

m_rankedAtts

protected double[][] m_rankedAtts

a ranked list of attribute indexes

m_rankedSoFar

protected int m_rankedSoFar

m_best_group

protected BitSet m_best_group

the best subset found

m_ASEval

protected ASEvaluation m_ASEval

m_Instances

protected Instances m_Instances

m_startRange

protected Range m_startRange

holds the start set for the search as a Range

m_starting

protected int[] m_starting

holds an array of starting attributes

m_backward

protected boolean m_backward

Use a backwards search instead of a forwards one

m_conservativeSelection

protected boolean m_conservativeSelection

If set then attributes will continue to be added during a forward search as long as the merit does not degrade

Constructor Detail

GreedyStepwise

public GreedyStepwise()

Constructor

Method Detail

globalInfo

public String globalInfo()

Returns a string describing this search method

Returns:

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

searchBackwardsTipText

public String searchBackwardsTipText()

Returns the tip text for this property

Returns:

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

setSearchBackwards

public void setSearchBackwards(boolean back)

Set whether to search backwards instead of forwards

Parameters:

back - true to search backwards

getSearchBackwards

public boolean getSearchBackwards()

Get whether to search backwards

Returns:

true if the search will proceed backwards

thresholdTipText

public 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 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 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 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(String startSet)
                 throws 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:

Exception - if start set can't be set.

getStartSet

public 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)

conservativeForwardSelectionTipText

public String conservativeForwardSelectionTipText()

Returns the tip text for this property

Returns:

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

setConservativeForwardSelection

public void setConservativeForwardSelection(boolean c)

Set whether attributes should continue to be added during a forward search as long as merit does not decrease

Parameters:

c - true if atts should continue to be atted

getConservativeForwardSelection

public boolean getConservativeForwardSelection()

Gets whether conservative selection has been enabled

Returns:

true if conservative forward selection is enabled

listOptions

public 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(String[] options)
                throws Exception

Parses a given list of options.

Valid options are:

 -C
  Use conservative forward search

 -B
  Use a backward search instead of a
  forward one.

 -P <start set>
  Specify a starting set of attributes.
  Eg. 1,3,5-7.

 -R
  Produce a ranked list of attributes.

 -T <threshold>
  Specify a theshold by which attributes
  may be discarded from the ranking.
  Use in conjuction with -R

 -N <num to select>
  Specify number of attributes to select

Specified by:

setOptions in interface OptionHandler

Parameters:

options - the list of options as an array of strings

Throws:

Exception - if an option is not supported

getOptions

public 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

protected 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 String toString()

returns a description of the search.

Overrides:

toString in class Object

Returns:

a description of the search as a String.

search

public int[] search(ASEvaluation ASEval,
                    Instances data)
             throws Exception

Searches the attribute subset space by forward selection.

Specified by:

search in class ASSearch

Parameters:

ASEval - the attribute evaluator to guide the search

data - the training instances.

Returns:

an array (not necessarily ordered) of selected attribute indexes

Throws:

Exception - if the search can't be completed

rankedAttributes

public double[][] rankedAttributes()
                            throws 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:

Exception - if something goes wrong.

attributeList

protected int[] attributeList(BitSet group)

converts a BitSet into a list of attribute indexes

Parameters:

group - the BitSet to convert

Returns:

an array of attribute indexes

resetOptions

protected void resetOptions()

Resets options

getRevision

public String getRevision()

Returns the revision string.

Specified by:

getRevision in interface RevisionHandler

Overrides:

getRevision in class ASSearch

Returns:

the revision