dtrees_rs/algorithms/greedy/lgdt/
mod.rs

1use crate::algorithms::common::config::BaseSearchConfig;
2use crate::algorithms::common::types::FitError;
3use crate::algorithms::optimal::depth2::OptimalDepth2Tree;
4use crate::algorithms::TreeSearchAlgorithm;
5use crate::cover::Cover;
6use crate::globals::{float_is_null, item};
7use crate::tree::Tree;
8
9pub mod builder;
10pub mod factories;
11
12/// LGDT, a less greedy decision tree learner.
13///
14/// Like CART, it builds the tree top-down one test at a time, but it chooses
15/// each test by solving a depth-2 tree at the node with a
16/// [`OptimalDepth2Tree`] solver and keeping its root. This two-level
17/// lookahead is cheap thanks to the depth-2 solver and makes the tree much
18/// less myopic than a purely greedy one.
19///
20/// Kiossou, Schaus, Nijssen and Aglin, *Efficient Lookahead Decision Trees*
21/// (IDA 2024). Build one with [`LGDTBuilder`](builder::LGDTBuilder) or the
22/// functions in [`factories`].
23pub struct LGDT<D>
24where
25    D: OptimalDepth2Tree + ?Sized,
26{
27    search: Box<D>,
28    config: BaseSearchConfig,
29    tree: Tree,
30}
31
32impl<D> TreeSearchAlgorithm for LGDT<D>
33where
34    D: OptimalDepth2Tree + ?Sized,
35{
36    fn fit(&mut self, cover: &mut Cover) -> Result<(), FitError> {
37        let depth = self.config.max_depth.min(2);
38        let root_tree = match self.search.fit(self.config.min_support, depth, cover, None) {
39            // No split beats a leaf (e.g. a single class): the tree is a leaf.
40            Err(FitError::EmptyTree | FitError::EmptyCandidates) => {
41                self.tree = self.leaf_tree(cover);
42                return Ok(());
43            }
44            result => result?,
45        };
46        if self.config.max_depth <= 2 {
47            self.tree = root_tree;
48            return Ok(());
49        }
50
51        let mut solution_tree = Tree::new();
52        let root_index = solution_tree.add_default_root();
53
54        let root_attribute = root_tree.root_test().ok_or(FitError::EmptyTree)?;
55        solution_tree
56            .update_root()
57            .map(|updater| updater.value(root_tree.root_details()));
58        self.recursion(
59            self.config.max_depth - 1,
60            cover,
61            &mut solution_tree,
62            root_index,
63            root_attribute,
64        )?;
65        solution_tree.clean_orphaned_nodes();
66        self.tree = solution_tree;
67        Ok(())
68    }
69
70    fn tree(&self) -> &Tree {
71        &self.tree
72    }
73}
74
75impl<D> LGDT<D>
76where
77    D: OptimalDepth2Tree + ?Sized,
78{
79    /// Grows the subtree below `parent`, which tests `attribute`, with
80    /// `depth` levels left. Returns the error of the subtree.
81    fn recursion(
82        &self,
83        depth: usize,
84        cover: &mut Cover,
85        tree: &mut Tree,
86        parent: usize,
87        attribute: usize,
88    ) -> Result<f64, FitError> {
89        let mut parent_error = 0.0;
90        for branch_value in [0, 1] {
91            let support = cover.branch_on(item(attribute, branch_value));
92
93            if support < self.config.min_support {
94                parent_error +=
95                    self.create_leaf_node_in_tree(tree, parent, branch_value == 0, cover);
96                cover.backtrack();
97                continue;
98            }
99
100            if depth <= 1 {
101                let child_tree_result =
102                    self.search.fit(self.config.min_support, depth, cover, None);
103                parent_error += match child_tree_result {
104                    Err(FitError::EmptyTree) | Err(FitError::EmptyCandidates) => {
105                        self.create_leaf_node_in_tree(tree, parent, branch_value == 0, cover)
106                    }
107                    Ok(child_tree) => {
108                        let child_index = tree.create_child(parent, branch_value == 0);
109                        tree.update_subtree(child_index, &child_tree, child_tree.get_root_index());
110                        child_tree.root_error()
111                    }
112                    Err(err) => return Err(err),
113                };
114            } else {
115                let child_tree_result = self.search.fit(self.config.min_support, 2, cover, None);
116                let child_error_result = match child_tree_result {
117                    Err(FitError::EmptyTree) | Err(FitError::EmptyCandidates) => {
118                        Ok(self.create_leaf_node_in_tree(tree, parent, branch_value == 0, cover))
119                    }
120                    Ok(child_tree) => {
121                        let mut error = Ok(child_tree.root_error());
122                        let child_index = tree.create_child(parent, branch_value == 0);
123                        // A perfect depth-2 subtree is kept whole; otherwise
124                        // only its root is kept and the recursion continues.
125                        if float_is_null(child_tree.root_error()) {
126                            tree.update_subtree(
127                                child_index,
128                                &child_tree,
129                                child_tree.get_root_index(),
130                            );
131                        } else {
132                            tree.update_node(child_index)
133                                .map(|updater| updater.value(child_tree.root_details()));
134                            let next_attribute = child_tree
135                                .node_test(child_tree.get_root_index())
136                                .ok_or(FitError::AlgorithmError)?;
137
138                            error =
139                                self.recursion(depth - 1, cover, tree, child_index, next_attribute);
140                        }
141
142                        error
143                    }
144                    Err(err) => Err(err),
145                };
146
147                parent_error += child_error_result?;
148            }
149            cover.backtrack();
150        }
151
152        tree.update_node(parent)
153            .map(|updater| updater.error(parent_error));
154        Ok(parent_error)
155    }
156
157    fn create_leaf_node_in_tree(
158        &self,
159        tree: &mut Tree,
160        parent: usize,
161        left: bool,
162        cover: &mut Cover,
163    ) -> f64 {
164        let child_index = tree.create_child(parent, left);
165        let error = self.search.error(&cover.labels_count());
166        tree.update_leaf_node(child_index, error);
167        error.0
168    }
169
170    /// A tree that is a single leaf over all of `cover`.
171    fn leaf_tree(&self, cover: &mut Cover) -> Tree {
172        let mut tree = Tree::new();
173        let root = tree.add_default_root();
174        tree.update_leaf_node(root, self.search.error(&cover.labels_count()));
175        tree
176    }
177
178    /// The settings of the search.
179    pub fn config(&self) -> &BaseSearchConfig {
180        &self.config
181    }
182}
183
184#[cfg(test)]
185mod tests {
186    use crate::algorithms::greedy::lgdt::factories::with_error_minimizer;
187    use crate::algorithms::TreeSearchAlgorithm;
188    use crate::reader::data_reader::DataReader;
189    use std::path::Path;
190
191    #[test]
192    fn test_d2_lgdt() {
193        let reader = DataReader::default();
194        let path = Path::new("test_data/anneal.txt");
195        let cover_result = reader.read_file(path);
196
197        let mut cover = cover_result.expect("the test data is readable");
198
199        let mut lgdt = with_error_minimizer()
200            .min_support(1)
201            .max_depth(8)
202            .build()
203            .unwrap();
204        lgdt.fit(&mut cover).unwrap();
205        assert!(lgdt.tree.root_error() < cover.count() as f64);
206    }
207}
dtrees_rs/algorithms/greedy/lgdt/mod.rs

dtrees_rs/algorithms/greedy/lgdt/
mod.rs
