Feature Selection ToolboxFST3 Library / DocumentationShare

FST::Search_Branch_And_Bound_Fast< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, PREDICTOR > Class Template Reference

Implements Fast Branch and Bound, i.e., B&B with full utilization of prediction mechanism. More...

#include <search_branch_and_bound_fast.hpp>

Inheritance diagram for FST::Search_Branch_And_Bound_Fast< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, PREDICTOR >:
Collaboration diagram for FST::Search_Branch_And_Bound_Fast< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, PREDICTOR >:

List of all members.

Public Types

typedef
Search_Branch_And_Bound
< RETURNTYPE, DIMTYPE, SUBSET,
CRITERION > 
parent
typedef parent::PCriterion PCriterion
typedef parent::PSubset PSubset
typedef parent::PNode PNode
typedef parent::Node Node
typedef parent::NodeType NodeType

Public Member Functions

void set_gamma (const RETURNTYPE gamma=1.0)
void set_delta (const unsigned int delta=1)
virtual std::ostream & print (std::ostream &os) const

Protected Member Functions

virtual void initialize (const DIMTYPE d, const DIMTYPE n, const PCriterion crit)
 called before search - enables set-up of additional structures in descendants
virtual void process_leafs ()
 can be overridden to implement prediction information learning, threading etc.
virtual void pre_evaluate_availables ()
 assign values to each feature in availables - to be used for node ordering
virtual void post_process_tree_level ()
 enables to substitute missing COMPUTED values in nodes just after level creation, if needed
virtual bool cut_possible ()
 tests current node for the possibility to cut its sub-branch

Protected Attributes

PREDICTOR _predictor

Detailed Description

template<class RETURNTYPE, typename DIMTYPE, class SUBSET, class CRITERION, class PREDICTOR>
class FST::Search_Branch_And_Bound_Fast< RETURNTYPE, DIMTYPE, SUBSET, CRITERION, PREDICTOR >

Implements Fast Branch and Bound, i.e., B&B with full utilization of prediction mechanism.

FBB is in most feature selection tasks the fastest of all Branch & Bound algorithms and as such should be the method of first choice whenever optimal feature selection is required and possible (see the warning below). Nevertheless, the FBB's prediction mechanism can theoretically fail and slow the search down (an analogy is perhaps the Quick Sort which is known as the best sorting algorithm for the general case but no guarantee is given about its actual speed). If you prefer more conservative option, try BBPP or the even slower but more predictable IBB or BBB.

Note:
All Branch & Bound algorithms by definition yield the solution with the same maximum criterion value, therefore the main concern regarding particular Branch & Bound algorithm is only its search speed.
Warning:
All Branch & Bound feature selection algorithms require the used CRITERION to be monotonic with respect to cardinality. More precisely, it must hold that removing a feature from a set MUST NOT increase criterion value. Otherwise there is no guarantee as of the optimality of obtained results with respect to the used criterion.
Note:
Due to possibly high number of subsets to be tested expect excessive computational time.
Result tracking in case of Branch & Bound algorithms records only results of target cardinality.
Examples:

demo43.cpp.


The documentation for this class was generated from the following file:

Generated on Thu Mar 31 11:38:50 2011 for FST3Library by  doxygen 1.6.1