contree/common/
mod.rs

1mod budget_schedule;
2
3mod outcome;
4
5pub use budget_schedule::{Budget, BudgetSchedule, PassReport, ScheduleBounds, ScheduleKind};
6pub use outcome::{FitOutcome, SearchError, SearchStatus};
7
8use serde::{Deserialize, Serialize};
9use std::fmt;
10use std::str::FromStr;
11
12/// Which candidate threshold the search evaluates next inside an interval of
13/// candidates.
14#[derive(Default, Copy, Debug, Clone, PartialOrd, PartialEq, Eq, Serialize, Deserialize)]
15#[serde(rename_all = "lowercase")]
16pub enum PointSelector {
17    /// The middle candidate, which bisects the interval. The default.
18    #[default]
19    Mid,
20    /// Candidates are tried one at a time instead of by bisection, in Gini
21    /// order when the heuristic is on. The anytime search limits how many are
22    /// tried with its split budget.
23    First,
24    /// A uniformly random candidate.
25    Random,
26}
27
28impl PointSelector {
29    /// The spelling used on the command line and in the Python API.
30    pub const fn as_str(self) -> &'static str {
31        match self {
32            Self::Mid => "mid",
33            Self::First => "first",
34            Self::Random => "random",
35        }
36    }
37
38    /// Every selector, in declaration order.
39    pub const ALL: [Self; 3] = [Self::Mid, Self::First, Self::Random];
40}
41
42impl fmt::Display for PointSelector {
43    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
44        f.write_str(self.as_str())
45    }
46}
47
48impl FromStr for PointSelector {
49    type Err = String;
50
51    fn from_str(s: &str) -> Result<Self, Self::Err> {
52        match s.trim().to_ascii_lowercase().as_str() {
53            "mid" => Ok(Self::Mid),
54            "first" => Ok(Self::First),
55            "random" => Ok(Self::Random),
56            other => Err(format!(
57                "unknown split selection strategy `{other}` (expected one of: mid, first, random)"
58            )),
59        }
60    }
61}
62
63/// Settings of a search, and the per-node state derived from them.
64#[derive(Copy, Clone, Debug)]
65pub struct SearchConfig {
66    /// Maximum depth of the tree (remaining depth, below the root).
67    pub max_depth: usize,
68    /// Minimum number of instances in each leaf.
69    pub min_sup: usize,
70    /// Time limit in seconds.
71    pub max_time: f64,
72    /// Error gap tolerated with respect to the optimum; 0 for an exact search.
73    pub max_gap: usize,
74    /// Initial upper bound on the error.
75    pub max_error: usize,
76    /// Whether this configuration is the root's.
77    pub is_root: bool,
78    /// Order features and thresholds by Gini impurity.
79    pub use_heuristic: bool,
80    /// Use the specialised solver for depth-2 subtrees.
81    pub fast_d2: bool,
82    /// How thresholds are picked inside an interval.
83    pub point_selector: PointSelector,
84    /// Number of passes run so far (anytime search).
85    pub nb_runs: usize,
86    /// Discrepancy used on the path to this node (anytime search).
87    pub discrepancy: usize,
88    /// Discrepancy budget of the current pass (anytime search).
89    pub budget: usize,
90}
91
92impl SearchConfig {
93    /// A root configuration with the given settings.
94    #[allow(clippy::too_many_arguments)]
95    pub fn new(
96        min_sup: usize,
97        max_depth: usize,
98        max_time: f64,
99        max_gap: usize,
100        max_error: usize,
101        use_heuristic: bool,
102        fast_d2: bool,
103        split_strategy: PointSelector,
104    ) -> Self {
105        Self {
106            max_depth,
107            min_sup,
108            max_time,
109            max_gap,
110            max_error,
111            is_root: true,
112            use_heuristic,
113            fast_d2,
114            point_selector: split_strategy,
115            nb_runs: 0,
116            discrepancy: 0,
117            budget: 0,
118        }
119    }
120
121    /// The configuration of the first child searched: one level shallower,
122    /// with part of the gap.
123    pub fn derive_left(&self) -> Self {
124        let mut left_config = *self;
125        left_config.max_depth -= 1;
126        left_config.is_root = false;
127        left_config.max_gap = (self.max_gap - self.max_gap.div_ceil(2)) / 2;
128        left_config
129    }
130
131    /// The configuration of the second child searched, given the gap already
132    /// handed to the first.
133    pub fn derive_right(&self, left_gap: usize) -> Self {
134        let mut right_config = *self;
135        right_config.max_depth -= 1;
136        right_config.is_root = false;
137        right_config.max_gap = (self.max_gap - self.max_gap.div_ceil(2)).saturating_sub(left_gap);
138        right_config
139    }
140}
141
142/// Counters collected during a search.
143#[derive(Copy, Clone, Debug, Default, PartialEq, Serialize, Deserialize)]
144pub struct Statistics {
145    /// Number of cached subproblems.
146    pub cache_size: usize,
147    /// Subproblems answered from the cache.
148    pub cache_hits: usize,
149    /// Calls to the general search.
150    pub general_solver_call: usize,
151    /// Calls to the depth-2 solver.
152    pub specialized_solver_call: usize,
153    /// Number of training instances.
154    pub num_samples: usize,
155    /// Number of features.
156    pub num_features: usize,
157    /// Training misclassifications of the best tree.
158    pub error: usize,
159    /// Search time in seconds.
160    pub duration: f64,
161}
162
163/// `(misclassifications, majority class)` of a leaf with the given class
164/// counts. Ties go to the highest class index.
165pub fn classification_error(classes_support: &[usize]) -> (usize, usize) {
166    let mut max_idx = 0;
167    let mut max_value = 0;
168    let mut total = 0;
169    for (idx, value) in classes_support.iter().enumerate() {
170        total += value;
171        if *value >= max_value {
172            max_value = *value;
173            max_idx = idx;
174        }
175    }
176    let error = total - max_value;
177    (error, max_idx)
178}
contree/common/mod.rs

contree/common/
mod.rs
