Package weka.attributeSelection

# Class BestFirst

java.lang.Object
weka.attributeSelection.ASSearch
weka.attributeSelection.BestFirst

All Implemented Interfaces:
  `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
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
Description
`static final Tag[]`
`TAGS_SELECTION`
search directions

## Constructor Summary

Constructors
Constructor
Description
`BestFirst()`
Constructor

## Method Summary

Modifier and Type
Method
Description
`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.
`String[]`
`getOptions()`
Gets the current settings of BestFirst.
`String`
`getRevision()`
Returns the revision string.
`int`
`getSearchTermination()`
Get the termination criterion (number of non-improving nodes).
`String`
`getStartSet()`
Returns a list of attributes (and or attribute ranges) as a String
`String`
`globalInfo()`
Returns a string describing this search method
`Enumeration`
`listOptions()`
Returns an enumeration describing the available options.
`String`
`lookupCacheSizeTipText()`
Returns the tip text for this property
`int[]`
`search(ASEvaluation ASEval, Instances data)`
Searches the attribute subset space by best first search
`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(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(String startSet)`
Sets a starting set of attributes for the search.
`String`
`startSetTipText()`
Returns the tip text for this property
`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 Details

### TAGS_SELECTION

public static final Tag[] TAGS_SELECTION
search directions

## Constructor Details

### BestFirst

public BestFirst()
Constructor

## Method Details

### globalInfo

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

     -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:
  `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 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 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)

### searchTerminationTipText

public 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 Exception
Set the numnber of non-improving nodes to consider before terminating search.

Parameters:
  `t` - the number of non-improving nodes
Throws:
  `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 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 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 String toString()
returns a description of the search as a String

Overrides:
  `toString` in class `Object`
Returns:
  a description of the search

### search

public int[] search(ASEvaluation ASEval, Instances data) throws 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:
  `Exception` - if the search can't be completed

### getRevision

public String getRevision()
Returns the revision string.

Specified by:
  `getRevision` in interface `RevisionHandler`
Overrides:
  `getRevision` in class `ASSearch`
Returns:
  the revision