Class 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 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 Tag[] TAGS_SELECTION
      search directions
    • Constructor Summary

      Constructors 
      Constructor Description
      BestFirst()
      Constructor
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method 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 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