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: 15520 $
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<Option>`
  `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<Option> listOptions()
    Returns an enumeration describing the available options.
    Specified by:
      `listOptions` in interface `OptionHandler`
    Overrides:
      `listOptions` in class `ASSearch`
    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`
    Overrides:
      `setOptions` in class `ASSearch`
    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`
    Overrides:
      `getOptions` in class `ASSearch`
    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