contree/algorithms/
mod.rs

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

contree/algorithms/
mod.rs
