Feature Selection ToolboxFST3 Library / Documentation

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

Implements Branch and Bound template method as basis for more advanced B&B implementations. More...

#include <search_branch_and_bound.hpp>

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

List of all members.

Classes

struct  Node
 Structure representing search tree node. More...

Public Types

typedef Search< RETURNTYPE,
DIMTYPE, SUBSET, CRITERION > 
parent
typedef boost::shared_ptr
< CRITERION > 
PCriterion
typedef boost::shared_ptr< SUBSET > PSubset

Public Member Functions

virtual bool search (const DIMTYPE target_d, RETURNTYPE &result, const PSubset sub, const PCriterion crit, std::ostream &os=std::cout)
 returns found subset of target_d features (optimizes cardinality if target_d==0) + _criterion value
virtual std::ostream & print (std::ostream &os) const

Protected Types

enum  NodeType { UNKNOWN, RANDOM, PREDICTED, COMPUTED }
typedef NodePNode
typedef list< NodeListNode
typedef vector< ListNode > VectorListNode
typedef ListNode::iterator ListNodeIter
typedef vector< ListNode >
::iterator 
TreeLevelIter
typedef vector< NodeVectorNode

Protected Member Functions

PCriterion const & get_criterion () const
RETURNTYPE get_bound_value () const
bool is_bound_valid () const
int get_k () const
DIMTYPE get_n () const
DIMTYPE get_d () const
bool getFirstNode (PNode &nod)
bool getNextNode (PNode &nod)
bool getFirstAvailable (PNode &avail)
bool getNextAvailable (PNode &avail)
bool getAvailable (DIMTYPE idx, PNode &avail)
PSubset & get_currentset ()
Nodeget_parent_node ()
Nodeget_current_node ()
void setup_default_structures (const DIMTYPE d, const DIMTYPE n)
 initializes tree memory
void update_bound (const RETURNTYPE val, const PSubset &sub)
void make_tree_level ()
void process_rightmost_path ()
virtual void process_leafs ()
 can be overridden to implement prediction information learning, threading etc.
virtual void initialize (const DIMTYPE d, const DIMTYPE n, const PCriterion crit)=0
 called before search - enables set-up of additional structures in descendants
virtual void pre_evaluate_availables ()=0
 assign values to each feature in _available - to be used for node ordering
virtual void post_process_tree_level ()=0
 enables to substitute missing COMPUTED values in nodes just after level creation, if needed
virtual bool cut_possible ()=0
 tests _currentset node for the possibility to cut its sub-branch

Protected Attributes

std::ostream * shared_os
 to enable sharing the same stream across the methods below
boost::shared_ptr< StopWatchswatch

Private Member Functions

DIMTYPE get_available_size ()
void available_add (const DIMTYPE feature)
void available_remove (const DIMTYPE feature)
void currentset_add (const DIMTYPE feature)
void currentset_remove (const DIMTYPE feature)

Private Attributes

PCriterion _criterion
VectorListNode _tree
ListNodeIter _nodeiter
 used in get*Node()
DIMTYPE _availiter
VectorNode _available
 Node::feature takes the role of 1-selected/0-unselected indicator.
PSubset _currentset
 _currentset subset to be evaluated
PSubset _tempset
 temporary copy of _currentset subset to be modified and evaluated
PSubset _boundset
RETURNTYPE _boundvalue
bool _boundvalid
DIMTYPE k
 current tree level
DIMTYPE n
 no. of all features
DIMTYPE d
 no. of features to be selected

Detailed Description

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

Implements Branch and Bound template method as basis for more advanced B&B implementations.

This is the abstract basis of concrete Branch & Bound implementations.

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.

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

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