weka.attributeSelection

Class BestFirst

java.lang.Object

weka.attributeSelection.ASSearch

weka.attributeSelection.BestFirst

All Implemented Interfaces:

java.io.Serializable, StartSetHandler, OptionHandler, RevisionHandler

public class BestFirst
extends ASSearch
implements OptionHandler, StartSetHandler

BestFirst:

Searches the space of attribute subsets by greedy hillclimbing augmented with a backtracking facility. Setting the number of consecutive non-improving nodes allowed controls the level of backtracking done. Best first may start with the empty set of attributes and search forward, or start with the full set of attributes and search backward, or start at any point and search in both directions (by considering all possible single attribute additions and deletions at a given point).

Valid options are:

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

 -D <0 = backward | 1 = forward | 2 = bi-directional>
  Direction of search. (default = 1).

 -N <num>
  Number of non-improving nodes to
  consider before terminating search.

 -S <num>
  Size of lookup cache for evaluated subsets.
  Expressed as a multiple of the number of
  attributes in the data set. (default = 1)

Version:

$Revision: 1.29 $

Author:

Mark Hall (mhall@cs.waikato.ac.nz) Martin Guetlein (cashing merit of expanded nodes)

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
class	BestFirst.Link2 Class for a node in a linked list.
class	BestFirst.LinkedList2 Class for handling a linked list.

Field Summary

Fields

Modifier and Type	Field and Description
static Tag[]	TAGS_SELECTION search directions

Constructor Summary

Constructors

Constructor and Description
BestFirst() Constructor

Method Summary

Modifier and Type	Method and Description
java.lang.String	directionTipText() Returns the tip text for this property
SelectedTag	getDirection() Get the search direction
int	getLookupCacheSize() Return the maximum size of the evaluated subset cache (expressed as a multiplier for the number of attributes in a data set.
java.lang.String[]	getOptions() Gets the current settings of BestFirst.
java.lang.String	getRevision() Returns the revision string.
int	getSearchTermination() Get the termination criterion (number of non-improving nodes).
java.lang.String	getStartSet() Returns a list of attributes (and or attribute ranges) as a String
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	lookupCacheSizeTipText() Returns the tip text for this property
int[]	search(ASEvaluation ASEval, Instances data) Searches the attribute subset space by best first search
java.lang.String	searchTerminationTipText() Returns the tip text for this property
void	setDirection(SelectedTag d) Set the search direction
void	setLookupCacheSize(int size) Set the maximum size of the evaluated subset cache (hashtable).
void	setOptions(java.lang.String[] options) Parses a given list of options.
void	setSearchTermination(int t) Set the numnber of non-improving nodes to consider before terminating search.
void	setStartSet(java.lang.String startSet) Sets a starting set of attributes for the search.
java.lang.String	startSetTipText() Returns the tip text for this property
java.lang.String	toString() returns a description of the search as a String

Methods inherited from class weka.attributeSelection.ASSearch

forName, makeCopies

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

TAGS_SELECTION

public static final Tag[] TAGS_SELECTION

search directions

Constructor Detail

BestFirst

public BestFirst()

Constructor

Method Detail

globalInfo

public java.lang.String globalInfo()

Returns a string describing this search method

Returns:

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

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 <start set>
  Specify a starting set of attributes.
  Eg. 1,3,5-7.

 -D <0 = backward | 1 = forward | 2 = bi-directional>
  Direction of search. (default = 1).

 -N <num>
  Number of non-improving nodes to
  consider before terminating search.

 -S <num>
  Size of lookup cache for evaluated subsets.
  Expressed as a multiple of the number of
  attributes in the data set. (default = 1)

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

setLookupCacheSize

public void setLookupCacheSize(int size)

Set the maximum size of the evaluated subset cache (hashtable). This is expressed as a multiplier for the number of attributes in the data set. (default = 1).

Parameters:

size - the maximum size of the hashtable

getLookupCacheSize

public int getLookupCacheSize()

Return the maximum size of the evaluated subset cache (expressed as a multiplier for the number of attributes in a data set.

Returns:

the maximum size of the hashtable.

lookupCacheSizeTipText

public java.lang.String lookupCacheSizeTipText()

Returns the tip text for this property

Returns:

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

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)

searchTerminationTipText

public java.lang.String searchTerminationTipText()

Returns the tip text for this property

Returns:

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

setSearchTermination

public void setSearchTermination(int t)
                          throws java.lang.Exception

Set the numnber of non-improving nodes to consider before terminating search.

Parameters:

t - the number of non-improving nodes

Throws:

java.lang.Exception - if t is less than 1

getSearchTermination

public int getSearchTermination()

Get the termination criterion (number of non-improving nodes).

Returns:

the number of non-improving nodes

directionTipText

public java.lang.String directionTipText()

Returns the tip text for this property

Returns:

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

setDirection

public void setDirection(SelectedTag d)

Set the search direction

Parameters:

d - the direction of the search

getDirection

public SelectedTag getDirection()

Get the search direction

Returns:

the direction of the search

getOptions

public java.lang.String[] getOptions()

Gets the current settings of BestFirst.

Specified by:

getOptions in interface OptionHandler

Returns:

an array of strings suitable for passing to setOptions()

toString

public java.lang.String toString()

returns a description of the search as a String

Overrides:

toString in class java.lang.Object

Returns:

a description of the search

search

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

Searches the attribute subset space by best first search

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:

java.lang.Exception - if the search can't be completed

getRevision

public java.lang.String getRevision()

Returns the revision string.

Specified by:

getRevision in interface RevisionHandler

Overrides:

getRevision in class ASSearch

Returns:

the revision