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: 10396 $
  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

    All Methods Instance Methods Concrete Methods
    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<Option>` | `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<Option> 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