Feature Selection ToolboxFST3 Library / Documentation

demo43.cpp File Reference

Example 43: Fast Branch and Bound (FBB) optimal feature selection. More...

#include <boost/smart_ptr.hpp>
#include <exception>
#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
#include "error.hpp"
#include "global.hpp"
#include "subset.hpp"
#include "data_intervaller.hpp"
#include "data_splitter.hpp"
#include "data_splitter_5050.hpp"
#include "data_splitter_cv.hpp"
#include "data_splitter_randrand.hpp"
#include "data_scaler.hpp"
#include "data_scaler_void.hpp"
#include "data_accessor_splitting_memTRN.hpp"
#include "data_accessor_splitting_memARFF.hpp"
#include "criterion_normal_bhattacharyya.hpp"
#include "criterion_wrapper.hpp"
#include "distance_Lp.hpp"
#include "classifier_knn.hpp"
#include "branch_and_bound_predictor_averaging.hpp"
#include "search_branch_and_bound_fast.hpp"
#include "result_tracker_dupless.hpp"
Include dependency graph for demo43.cpp:

Functions

int main ()

Detailed Description

Example 43: Fast Branch and Bound (FBB) optimal feature selection.


Function Documentation

int main (  ) 

Example 43: Fast Branch and Bound (FBB) optimal feature selection.

Branch & Bound algorithms yield optimal result in shorter time than exhaustive search, but can not be used with non-monotonic criteria. 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. 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:
B&B are d-parametrized procedures.
Due to the necessary monotonicity condition the B&B algorithms can not be used with Criterion_Wrapper criteria.
Although B&B algorithms are much faster than exhaustive search, they are exponential in nature. As such they are generally unusable with problems of dimensionality (roughly) 50 or above.

References FST::Search< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >::enable_result_tracking(), FST::Search_Branch_And_Bound< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >::search(), and FST::Search< RETURNTYPE, DIMTYPE, SUBSET, CRITERION >::set_output_detail().


Generated on Thu Mar 31 11:36:29 2011 for FST3Library by  doxygen 1.6.1