dtrees_rs/algorithms/optimal/depth2/
mod.rs

1//! Specialised solvers for trees of depth one and two.
2//!
3//! Instead of recursing, they count the classes of every pair of features
4//! once, in a matrix, and deduce every leaf of every depth-2 tree from it.
5//! DL8.5 uses them for the last two levels, and LGDT uses them at each step.
6//! The idea comes from MurTree (Demirović et al., JMLR 2022).
7
8use crate::algorithms::common::types::FitError;
9use crate::algorithms::common::utils::find_valid_split_attributes;
10use crate::cover::Cover;
11use crate::tree::Tree;
12
13mod config;
14mod error_minimizer;
15mod info_gain_maximizer;
16
17pub use error_minimizer::ErrorMinimizer;
18pub use info_gain_maximizer::InfoGainMaximizer;
19
20/// A solver for trees of depth at most 2.
21pub trait OptimalDepth2Tree {
22    /// Finds the best tree of the given depth (1 or 2) on the instances of
23    /// `cover`, using only `provided_candidates` when given.
24    fn fit(
25        &self,
26        min_sup: usize,
27        depth: usize,
28        cover: &mut Cover,
29        provided_candidates: Option<&[usize]>,
30    ) -> Result<Tree, FitError> {
31        match depth {
32            1 => self.find_optimal_depth_one_tree(min_sup, cover, provided_candidates),
33            2 => self.find_optimal_depth_two_tree(min_sup, cover, provided_candidates),
34            x => Err(FitError::InvalidDepth(x)),
35        }
36    }
37
38    /// The best tree with a single test.
39    fn find_optimal_depth_one_tree(
40        &self,
41        min_sup: usize,
42        cover: &mut Cover,
43        provided_candidates: Option<&[usize]>,
44    ) -> Result<Tree, FitError>;
45
46    /// The best tree with at most two levels of tests.
47    fn find_optimal_depth_two_tree(
48        &self,
49        min_sup: usize,
50        cover: &mut Cover,
51        provided_candidates: Option<&[usize]>,
52    ) -> Result<Tree, FitError>;
53
54    /// `(error, prediction)` of a leaf with the given class counts.
55    fn error(&self, distribution: &[usize]) -> (f64, f64);
56
57    /// Features that split the instances of `cover` with at least `min_sup`
58    /// instances on each side.
59    #[inline]
60    fn get_candidates(
61        &self,
62        cover: &mut Cover,
63        min_sup: usize,
64        provided_candidates: Option<&[usize]>,
65    ) -> Vec<usize> {
66        find_valid_split_attributes(cover, min_sup, provided_candidates, None)
67    }
68}
dtrees_rs/algorithms/optimal/depth2/mod.rs

dtrees_rs/algorithms/optimal/depth2/
mod.rs
