demo41.cpp File Reference

Example 41: Improved Branch and Bound (IBB) 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 "search_branch_and_bound_improved.hpp"
#include "result_tracker_dupless.hpp"

Include dependency graph for demo41.cpp:

Functions
int	main ()

---

Detailed Description

Example 41: Improved Branch and Bound (IBB) optimal feature selection.

---

Function Documentation

int main

(

)

Example 41: Improved Branch and Bound (IBB) 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. 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.

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().