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

Implements Improved Branch and Bound (IBB) method, i.e., with fully computed node ordering. More...

#include <search_branch_and_bound_improved.hpp>

Inheritance diagram for FST::Search_Branch_And_Bound_Improved< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >:

[legend]

Collaboration diagram for FST::Search_Branch_And_Bound_Improved< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >:

[legend]

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
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	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 ()
	enables to substitute missing COMPUTED values in nodes just after level creation, if needed

---

Detailed Description

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

Implements Improved Branch and Bound (IBB) method, i.e., with fully computed node ordering.

IBB is the well-known B&B variant that orders tree nodes in each constructed tree level so as to increase the chance that the bound gets higher soon. This effectively improves chances that larger sub-trees can be cut and thus more time saved, but this is achieved at the cost of additional criterion evaluations in each tree level. In time consuming tasks this mechanism proves capable of considerably overperforming the Basic Branch & Bound algorithm.

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:

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.

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:

demo41.cpp.

---

Member Function Documentation

template<class RETURNTYPE , typename DIMTYPE , class SUBSET , class CRITERION >

bool FST::Search_Branch_And_Bound_Improved< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >::cut_possible

(

)

[inline, protected, virtual]

enables to substitute missing COMPUTED values in nodes just after level creation, if needed

tests current node for the possibility to cut its sub-branch

Implements FST::Search_Branch_And_Bound< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >.

---

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

• search_branch_and_bound_improved.hpp