demo42.cpp File Reference

Example 42: Branch and Bound with Partial Prediction (BBPP) 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_partial_prediction.hpp"
#include "result_tracker_dupless.hpp"

Include dependency graph for demo42.cpp:

Functions
int	main ()

---

Detailed Description

Example 42: Branch and Bound with Partial Prediction (BBPP) optimal feature selection.

---

Function Documentation

int main

(

)

Example 42: Branch and Bound with Partial Prediction (BBPP) 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. BBPP is generally slower than FBB but faster than IBB. Its principle is identical to that of Improved Branch & Bound (IBB), but it replaces large amount of criterion evaluations needed for ordering nodes in tree levels by quickly predicted values. The optimality of final result is not jeopardized but considerable amount of time is saved. See FBB for a more radical but still optimality preserving use of value prediction.

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