contree/algorithms/
mod.rs

1mod continuous_tree;
2mod contree_lds;
3mod depth2;
4mod interval_pruner;
5mod shared;
6
7use crate::common::{
8    Cost, FitOutcome, PointSelector, ScheduleKind, SearchConfig, SearchError, SearchStatus,
9    Statistics,
10};
11use crate::data::view::DataView;
12use crate::data::Dataset;
13use crate::tree::Tree;
14pub use continuous_tree::ConTree;
15pub use contree_lds::ConTreeLds;
16
17/// The sub-range of `possible_splits` whose splits leave at least `min_sup`
18/// instances on both sides.
19///
20/// `possible_splits` holds positions into a column sorted by value, so a split
21/// at position `p` puts `p` instances on the left and `view_len - p` on the
22/// right, and the feasible positions form one contiguous run.
23///
24/// The returned range is empty when no split satisfies the constraint.
25pub(crate) fn support_feasible_splits(
26    possible_splits: &[usize],
27    view_len: usize,
28    min_sup: usize,
29) -> std::ops::Range<usize> {
30    let min_sup = min_sup.max(1);
31    if view_len < 2 * min_sup {
32        return 0..0;
33    }
34    let first = possible_splits.partition_point(|&p| p < min_sup);
35    let last = possible_splits.partition_point(|&p| view_len - p.min(view_len) >= min_sup);
36    first..last.max(first)
37}
38
39/// Checks the dataset and the parameters before a search starts.
40pub fn validate(config: &SearchConfig, dataset: &Dataset) -> Result<(), SearchError> {
41    if dataset.count() == 0 {
42        return Err(SearchError::EmptyDataset);
43    }
44    if dataset.num_features() == 0 {
45        return Err(SearchError::NoFeatures);
46    }
47    if !dataset.is_prepared() {
48        return Err(SearchError::UnpreparedDataset);
49    }
50    if config.min_sup == 0 {
51        return Err(SearchError::InvalidParameter {
52            name: "min_sup",
53            reason: "must be at least 1".to_string(),
54        });
55    }
56    if 2 * config.min_sup > dataset.count() {
57        return Err(SearchError::InvalidParameter {
58            name: "min_sup",
59            reason: format!(
60                "{} leaves no room for a split with n_samples={}",
61                config.min_sup,
62                dataset.count()
63            ),
64        });
65    }
66    if config.max_time.is_nan() || config.max_time <= 0.0 {
67        return Err(SearchError::InvalidParameter {
68            name: "max_time",
69            reason: "must be a positive number of seconds".to_string(),
70        });
71    }
72    Ok(())
73}
74
75/// Either search behind one interface, chosen at run time.
76pub enum GenericConTree {
77    /// The exhaustive search.
78    Normal(ConTree),
79    /// The anytime search.
80    LDS(ConTreeLds),
81}
82
83impl GenericConTree {
84    /// Builds the anytime search when `use_lds` is set, the exhaustive one
85    /// otherwise. The other arguments are those of [`ConTree::new`].
86    #[allow(clippy::too_many_arguments)]
87    pub fn new(
88        min_sup: usize,
89        max_depth: usize,
90        max_time: f64,
91        max_error: Cost,
92        split_selection_strategy: PointSelector,
93        max_gap: Cost,
94        use_heuristic: bool,
95        fast_d2: bool,
96        use_lds: bool,
97    ) -> Self {
98        match use_lds {
99            true => Self::LDS(ConTreeLds::new(
100                min_sup,
101                max_depth,
102                max_time,
103                max_error,
104                split_selection_strategy,
105                max_gap,
106                use_heuristic,
107                fast_d2,
108            )),
109            false => Self::Normal(ConTree::new(
110                min_sup,
111                max_depth,
112                max_time,
113                max_error,
114                split_selection_strategy,
115                max_gap,
116                use_heuristic,
117                fast_d2,
118            )),
119        }
120    }
121
122    /// Chooses the anytime search's budget schedule. No effect on the
123    /// exhaustive search, which has no budget.
124    pub fn with_budget_schedule(self, schedule: ScheduleKind) -> Self {
125        match self {
126            GenericConTree::LDS(solver) => GenericConTree::LDS(solver.with_schedule(schedule)),
127            other => other,
128        }
129    }
130
131    /// Runs the search on `dataset`.
132    pub fn fit(&mut self, dataset: &Dataset) -> Result<FitOutcome, SearchError> {
133        match self {
134            GenericConTree::Normal(solver) => solver.fit(dataset),
135            GenericConTree::LDS(solver) => solver.fit(dataset),
136        }
137    }
138
139    /// Runs one pass of the anytime search, returning whether it is done.
140    ///
141    /// The exhaustive solver has no notion of a partial fit, so it runs to
142    /// completion and reports that it is done.
143    pub fn partial_fit(&mut self, view: &DataView<'_>) -> Result<bool, SearchError> {
144        match self {
145            GenericConTree::Normal(_) => Ok(true),
146            GenericConTree::LDS(solver) => Ok(solver.partial_fit(view)),
147        }
148    }
149
150    /// Counters of the last search.
151    pub fn stats(&self) -> Statistics {
152        match self {
153            GenericConTree::Normal(solver) => solver.statistics(),
154            GenericConTree::LDS(solver) => *solver.statistics(),
155        }
156    }
157
158    /// Why the last search stopped.
159    pub fn status(&self) -> SearchStatus {
160        match self {
161            GenericConTree::Normal(solver) => solver.status(),
162            GenericConTree::LDS(solver) => solver.status(),
163        }
164    }
165
166    /// The tree found by the last `fit`. Empty if `fit` has not run.
167    pub fn tree(&mut self) -> Tree {
168        match self {
169            GenericConTree::Normal(solver) => solver.tree.clone(),
170            GenericConTree::LDS(solver) => solver.get_solution_tree(),
171        }
172    }
173}
contree/algorithms/mod.rs

contree/algorithms/
mod.rs
