Struct DL85 

pub struct DL85<C, D, E, H>
where
    C: Caching + ?Sized,
    D: OptimalDepth2Tree + ?Sized,
    E: ErrorWrapper + ?Sized,
    H: Heuristic + ?Sized,
{ /* private fields */ }

DL8.5: optimal decision trees over binary features by dynamic programming with branch-and-bound and a cache of subproblems.

A subproblem is the set of instances reaching a node, identified by the itemset of tests on the path to it. The search explores features at each node, prunes children with the upper bound left by their sibling, and caches every solved subproblem so it is solved once.

The search is also anytime. Relaxable search rules (see rules) restrict each pass, and the search restarts with widened budgets until a pass completes, which proves the tree optimal.

Aglin, Nijssen and Schaus, Learning Optimal Decision Trees Using Caching Branch-and-Bound Search (AAAI 2020). Build one with DL85Builder.

Implementations

impl<C, D, E, H> DL85<C, D, E, H>

where C: Caching + ?Sized, D: OptimalDepth2Tree + ?Sized, E: ErrorWrapper + ?Sized, H: Heuristic + ?Sized,

pub fn new( config: DL85Config, cache: Box<C>, depth2_search: Box<D>, error_fn: Box<E>, heuristic_fn: Box<H>, node_rules: RuleManager, search_rules: RuleManager, time_rule: TimeLimitRule, ) -> Self

Assembles a search from its parts. Prefer DL85Builder.

pub fn config(&self) -> DL85Config

The configuration of the search.

pub fn partial_fit(&mut self, cover: &mut Cover) -> SearchResult

Runs one pass of the search and rebuilds the tree.

The first call initialises the cache and the rules. When the result’s reason is Reason::RuleReason, a rule cut the pass short and the rules are relaxed for the next one; any other reason means the search is over.

pub fn statistics(&self) -> &SearchStatistics

Counters of the search.

pub fn elapsed_seconds(&self) -> f64

Seconds since the search started.

pub fn time_is_exhausted(&self) -> bool

Whether the time limit is reached.

pub fn cache_entry_to_tree_entry(&self, cache_entry: &CacheEntry) -> NodeInfos

Converts a cache entry into the content of a tree node.

Trait Implementations

impl<C, D, E, H> TreeSearchAlgorithm for DL85<C, D, E, H>

where C: Caching + ?Sized, D: OptimalDepth2Tree + ?Sized, E: ErrorWrapper + ?Sized, H: Heuristic + ?Sized,

fn fit(&mut self, cover: &mut Cover) -> Result<(), FitError>

Runs passes until one completes or the time limit is reached.

fn tree(&self) -> &Tree

The tree learned by the last fit.

fn error(&self) -> f64

Training error of the learned tree.

fn get_candidates( &self, cover: &mut Cover, min_sup: usize, provided_candidates: Option<&[usize]>, previous: Option<usize>, ) -> Vec<usize>

Features that can split the current node. See find_valid_split_attributes.