use super::packed::{BuildNode, ClassTree, NO_CHILD, PackedTree};
use super::parameters::{MaxFeatures, Splitter};
use crate::api::ModelError;
use crate::data::MatrixView;
use crate::numeric::OwnedRng;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) struct GrowerConfig {
pub(crate) max_depth: Option<usize>,
pub(crate) min_samples_split: usize,
pub(crate) min_samples_leaf: usize,
pub(crate) max_features: MaxFeatures,
pub(crate) splitter: Splitter,
}
pub(crate) trait Objective<Y>: Copy + Send + Sync {
fn value(self, y: &Y) -> f64;
fn impurity(self, sum: f64, sum_sq: f64, weight: f64) -> f64;
fn leaf_value(self, sum: f64, weight: f64) -> f32 {
(sum / weight) as f32
}
fn pure(self, sum: f64, sum_sq: f64, weight: f64) -> bool;
}
#[derive(Clone, Copy)]
pub(crate) struct Classification;
impl Objective<u8> for Classification {
fn value(self, y: &u8) -> f64 {
f64::from(*y)
}
fn impurity(self, positives: f64, _sum_sq: f64, weight: f64) -> f64 {
let p = positives / weight;
2.0 * p * (1.0 - p)
}
fn pure(self, positives: f64, _sum_sq: f64, weight: f64) -> bool {
positives == 0.0 || positives == weight
}
}
#[derive(Clone, Copy)]
pub(crate) struct Regression;
impl Objective<f32> for Regression {
fn value(self, y: &f32) -> f64 {
f64::from(*y)
}
fn impurity(self, sum: f64, sum_sq: f64, weight: f64) -> f64 {
let mean = sum / weight;
(sum_sq / weight - mean * mean).max(0.0)
}
fn pure(self, sum: f64, sum_sq: f64, weight: f64) -> bool {
self.impurity(sum, sum_sq, weight) == 0.0
}
}
pub(crate) fn unbootstrapped_sample(
rows: usize,
sample_weights: Option<&[f32]>,
) -> (Vec<f64>, Vec<usize>) {
let Some(sample_weights) = sample_weights else {
return (vec![1.0_f64; rows], (0..rows).collect());
};
let mut weights = vec![0.0_f64; rows];
let mut retained = Vec::with_capacity(rows);
for row in 0..rows {
if sample_weights[row] > 0.0 {
weights[row] = f64::from(sample_weights[row]);
retained.push(row);
}
}
(weights, retained)
}
pub(crate) fn grow_tree<Y, O>(
data: &MatrixView<'_>,
targets: &[Y],
row_weights: &[f64],
rows: Vec<usize>,
config: &GrowerConfig,
objective: O,
rng: &mut OwnedRng,
) -> Result<PackedTree, ModelError>
where
O: Objective<Y>,
{
TreeBuilder {
data,
targets,
row_weights,
config,
objective,
rng,
nodes: Vec::new(),
}
.build_tree(rows)
}
pub(crate) fn grow_class_tree(
data: &MatrixView<'_>,
class_of_row: &[usize],
classes: usize,
row_weights: &[f64],
rows: Vec<usize>,
config: &GrowerConfig,
rng: &mut OwnedRng,
) -> Result<ClassTree, ModelError> {
ClassTreeBuilder {
data,
class_of_row,
classes,
row_weights,
config,
rng,
nodes: Vec::new(),
class_weights: Vec::new(),
weights: Vec::new(),
}
.build_tree(rows)
}
#[inline]
fn sample_features(rng: &mut OwnedRng, columns: usize, count: usize) -> Vec<usize> {
let mut features: Vec<usize> = (0..columns).collect();
for index in 0..count {
let other = index + rng.index(features.len() - index);
features.swap(index, other);
}
features
}
#[inline]
fn resolved_feature_count(max_features: MaxFeatures, columns: usize) -> usize {
match max_features {
MaxFeatures::All => columns,
MaxFeatures::Sqrt => integer_sqrt(columns).max(1),
MaxFeatures::Count(count) => count,
}
}
struct TreeBuilder<'a, 'm, Y, O> {
data: &'a MatrixView<'m>,
targets: &'a [Y],
row_weights: &'a [f64],
config: &'a GrowerConfig,
objective: O,
rng: &'a mut OwnedRng,
nodes: Vec<BuildNode>,
}
#[derive(Clone, Copy)]
struct Split {
feature: usize,
threshold: f32,
score: f64,
}
#[derive(Clone, Copy)]
enum Attachment {
Root,
Left(u32),
Right(u32),
}
struct PendingNode {
rows: Vec<usize>,
depth: usize,
attachment: Attachment,
}
impl<Y, O: Objective<Y>> TreeBuilder<'_, '_, Y, O> {
fn build_tree(mut self, rows: Vec<usize>) -> Result<PackedTree, ModelError> {
let mut pending = vec![PendingNode {
rows,
depth: 0,
attachment: Attachment::Root,
}];
while let Some(task) = pending.pop() {
let (sum, sum_sq, weight) = self.totals(&task.rows);
let prediction = self.objective.leaf_value(sum, weight);
let node_index = self.push_node(BuildNode::leaf(prediction))?;
match task.attachment {
Attachment::Root => debug_assert_eq!(node_index, 0),
Attachment::Left(parent) => self.nodes[parent as usize].left = node_index,
Attachment::Right(parent) => self.nodes[parent as usize].right = node_index,
}
let depth_limited = self
.config
.max_depth
.is_some_and(|max_depth| task.depth >= max_depth);
if depth_limited
|| weight < self.config.min_samples_split as f64
|| self.objective.pure(sum, sum_sq, weight)
{
continue;
}
let parent_impurity = self.objective.impurity(sum, sum_sq, weight);
let Some(split) = self.best_split(&task.rows, sum, sum_sq, weight) else {
continue;
};
if split.score >= parent_impurity {
continue;
}
let mut left_rows = Vec::with_capacity(task.rows.len());
let mut right_rows = Vec::with_capacity(task.rows.len());
for row in task.rows {
if self.data.row(row).expect("known row")[split.feature] <= split.threshold {
left_rows.push(row);
} else {
right_rows.push(row);
}
}
self.nodes[node_index as usize] = BuildNode {
feature: split.feature as u32,
left: NO_CHILD,
right: NO_CHILD,
payload: split.threshold,
};
pending.push(PendingNode {
rows: right_rows,
depth: task.depth + 1,
attachment: Attachment::Right(node_index),
});
pending.push(PendingNode {
rows: left_rows,
depth: task.depth + 1,
attachment: Attachment::Left(node_index),
});
}
PackedTree::from_build_nodes(self.nodes, self.data.columns())
}
fn push_node(&mut self, node: BuildNode) -> Result<u32, ModelError> {
let index = u32::try_from(self.nodes.len()).map_err(|_| ModelError::TreeTooLarge)?;
if index == NO_CHILD {
return Err(ModelError::TreeTooLarge);
}
self.nodes.push(node);
Ok(index)
}
fn totals(&self, rows: &[usize]) -> (f64, f64, f64) {
let mut sum = 0.0;
let mut sum_sq = 0.0;
let mut weight = 0.0;
for &row in rows {
let row_weight = self.row_weights[row];
let value = self.objective.value(&self.targets[row]);
sum += value * row_weight;
sum_sq += value * value * row_weight;
weight += row_weight;
}
(sum, sum_sq, weight)
}
fn best_split(
&mut self,
rows: &[usize],
total_sum: f64,
total_sum_sq: f64,
total_weight: f64,
) -> Option<Split> {
let feature_count = resolved_feature_count(self.config.max_features, self.data.columns());
let drawn = sample_features(self.rng, self.data.columns(), feature_count);
let features = &drawn[..feature_count];
match self.config.splitter {
Splitter::Best => {
self.best_exhaustive_split(features, rows, total_sum, total_sum_sq, total_weight)
}
Splitter::Random => {
self.best_random_split(features, rows, total_sum, total_sum_sq, total_weight)
}
}
}
fn best_exhaustive_split(
&self,
features: &[usize],
rows: &[usize],
total_sum: f64,
total_sum_sq: f64,
total_weight: f64,
) -> Option<Split> {
let mut ordered = Vec::with_capacity(rows.len());
let mut best: Option<Split> = None;
for &feature in features {
ordered.clear();
ordered.extend_from_slice(rows);
ordered.sort_unstable_by(|&left, &right| {
self.data.row(left).expect("known row")[feature]
.total_cmp(&self.data.row(right).expect("known row")[feature])
.then_with(|| left.cmp(&right))
});
let mut left_sum = 0.0;
let mut left_sum_sq = 0.0;
let mut left_weight = 0.0;
for boundary in 0..ordered.len().saturating_sub(1) {
let row = ordered[boundary];
let row_weight = self.row_weights[row];
let value = self.objective.value(&self.targets[row]);
left_sum += value * row_weight;
left_sum_sq += value * value * row_weight;
left_weight += row_weight;
let a = self.data.row(row).expect("known row")[feature];
let b = self.data.row(ordered[boundary + 1]).expect("known row")[feature];
if a == b {
continue;
}
let right_weight = total_weight - left_weight;
if left_weight < self.config.min_samples_leaf as f64
|| right_weight < self.config.min_samples_leaf as f64
{
continue;
}
let right_sum = total_sum - left_sum;
let right_sum_sq = total_sum_sq - left_sum_sq;
let left_impurity = self.objective.impurity(left_sum, left_sum_sq, left_weight);
let right_impurity = self
.objective
.impurity(right_sum, right_sum_sq, right_weight);
let score =
(left_weight * left_impurity + right_weight * right_impurity) / total_weight;
if best.as_ref().is_none_or(|current| score < current.score) {
best = Some(Split {
feature,
threshold: split_threshold(a, b),
score,
});
}
}
}
best
}
fn best_random_split(
&mut self,
features: &[usize],
rows: &[usize],
total_sum: f64,
total_sum_sq: f64,
total_weight: f64,
) -> Option<Split> {
let mut best: Option<Split> = None;
for &feature in features {
let (min, max) = column_range(self.data, rows, feature);
let Some(threshold) = random_threshold(self.rng, min, max) else {
continue;
};
let mut left_sum = 0.0;
let mut left_sum_sq = 0.0;
let mut left_weight = 0.0;
for &row in rows {
if self.data.row(row).expect("known row")[feature] <= threshold {
let row_weight = self.row_weights[row];
let value = self.objective.value(&self.targets[row]);
left_sum += value * row_weight;
left_sum_sq += value * value * row_weight;
left_weight += row_weight;
}
}
let right_weight = total_weight - left_weight;
if left_weight < self.config.min_samples_leaf as f64
|| right_weight < self.config.min_samples_leaf as f64
{
continue;
}
let right_sum = total_sum - left_sum;
let right_sum_sq = total_sum_sq - left_sum_sq;
let score = (left_weight * self.objective.impurity(left_sum, left_sum_sq, left_weight)
+ right_weight
* self
.objective
.impurity(right_sum, right_sum_sq, right_weight))
/ total_weight;
if best.as_ref().is_none_or(|current| score < current.score) {
best = Some(Split {
feature,
threshold,
score,
});
}
}
best
}
}
struct ClassTreeBuilder<'a, 'm> {
data: &'a MatrixView<'m>,
class_of_row: &'a [usize],
classes: usize,
row_weights: &'a [f64],
config: &'a GrowerConfig,
rng: &'a mut OwnedRng,
nodes: Vec<BuildNode>,
class_weights: Vec<f64>,
weights: Vec<f64>,
}
impl ClassTreeBuilder<'_, '_> {
fn build_tree(mut self, rows: Vec<usize>) -> Result<ClassTree, ModelError> {
let classes = self.classes;
let mut totals = vec![0.0_f64; classes];
let mut left = vec![0.0_f64; classes];
let mut right = vec![0.0_f64; classes];
let mut pending = vec![PendingNode {
rows,
depth: 0,
attachment: Attachment::Root,
}];
while let Some(task) = pending.pop() {
let weight = self.totals(&task.rows, &mut totals);
let node_index = self.push_node(BuildNode::leaf(0.0), &totals, weight)?;
match task.attachment {
Attachment::Root => debug_assert_eq!(node_index, 0),
Attachment::Left(parent) => self.nodes[parent as usize].left = node_index,
Attachment::Right(parent) => self.nodes[parent as usize].right = node_index,
}
let depth_limited = self
.config
.max_depth
.is_some_and(|max_depth| task.depth >= max_depth);
if depth_limited
|| weight < self.config.min_samples_split as f64
|| totals.contains(&weight)
{
continue;
}
let parent_impurity = gini(&totals, weight);
let Some(split) = self.best_split(&task.rows, &totals, weight, &mut left, &mut right)
else {
continue;
};
if split.score >= parent_impurity {
continue;
}
let mut left_rows = Vec::with_capacity(task.rows.len());
let mut right_rows = Vec::with_capacity(task.rows.len());
for row in task.rows {
if self.data.row(row).expect("known row")[split.feature] <= split.threshold {
left_rows.push(row);
} else {
right_rows.push(row);
}
}
self.nodes[node_index as usize] = BuildNode {
feature: split.feature as u32,
left: NO_CHILD,
right: NO_CHILD,
payload: split.threshold,
};
pending.push(PendingNode {
rows: right_rows,
depth: task.depth + 1,
attachment: Attachment::Right(node_index),
});
pending.push(PendingNode {
rows: left_rows,
depth: task.depth + 1,
attachment: Attachment::Left(node_index),
});
}
ClassTree::from_build_nodes(
self.nodes,
&self.class_weights,
&self.weights,
classes,
self.data.columns(),
)
}
fn push_node(
&mut self,
node: BuildNode,
class_weights: &[f64],
weight: f64,
) -> Result<u32, ModelError> {
let index = u32::try_from(self.nodes.len()).map_err(|_| ModelError::TreeTooLarge)?;
if index == NO_CHILD {
return Err(ModelError::TreeTooLarge);
}
self.nodes.push(node);
self.class_weights.extend_from_slice(class_weights);
self.weights.push(weight);
Ok(index)
}
fn totals(&self, rows: &[usize], class_weights: &mut [f64]) -> f64 {
class_weights.fill(0.0);
let mut weight = 0.0;
for &row in rows {
let row_weight = self.row_weights[row];
class_weights[self.class_of_row[row]] += row_weight;
weight += row_weight;
}
weight
}
fn best_split(
&mut self,
rows: &[usize],
totals: &[f64],
total_weight: f64,
left: &mut [f64],
right: &mut [f64],
) -> Option<Split> {
let feature_count = resolved_feature_count(self.config.max_features, self.data.columns());
let drawn = sample_features(self.rng, self.data.columns(), feature_count);
let features = &drawn[..feature_count];
match self.config.splitter {
Splitter::Best => {
self.best_exhaustive_split(features, rows, totals, total_weight, left, right)
}
Splitter::Random => {
self.best_random_split(features, rows, totals, total_weight, left, right)
}
}
}
fn best_exhaustive_split(
&self,
features: &[usize],
rows: &[usize],
totals: &[f64],
total_weight: f64,
left: &mut [f64],
right: &mut [f64],
) -> Option<Split> {
let mut ordered = Vec::with_capacity(rows.len());
let mut best: Option<Split> = None;
for &feature in features {
ordered.clear();
ordered.extend_from_slice(rows);
ordered.sort_unstable_by(|&left, &right| {
self.data.row(left).expect("known row")[feature]
.total_cmp(&self.data.row(right).expect("known row")[feature])
.then_with(|| left.cmp(&right))
});
left.fill(0.0);
let mut left_weight = 0.0;
for boundary in 0..ordered.len().saturating_sub(1) {
let row = ordered[boundary];
let row_weight = self.row_weights[row];
left[self.class_of_row[row]] += row_weight;
left_weight += row_weight;
let a = self.data.row(row).expect("known row")[feature];
let b = self.data.row(ordered[boundary + 1]).expect("known row")[feature];
if a == b {
continue;
}
let right_weight = total_weight - left_weight;
if left_weight < self.config.min_samples_leaf as f64
|| right_weight < self.config.min_samples_leaf as f64
{
continue;
}
for (slot, (&total, &left)) in right.iter_mut().zip(totals.iter().zip(left.iter()))
{
*slot = total - left;
}
let score = (left_weight * gini(left, left_weight)
+ right_weight * gini(right, right_weight))
/ total_weight;
if best.as_ref().is_none_or(|current| score < current.score) {
best = Some(Split {
feature,
threshold: split_threshold(a, b),
score,
});
}
}
}
best
}
fn best_random_split(
&mut self,
features: &[usize],
rows: &[usize],
totals: &[f64],
total_weight: f64,
left: &mut [f64],
right: &mut [f64],
) -> Option<Split> {
let mut best: Option<Split> = None;
for &feature in features {
let (min, max) = column_range(self.data, rows, feature);
let Some(threshold) = random_threshold(self.rng, min, max) else {
continue;
};
left.fill(0.0);
let mut left_weight = 0.0;
for &row in rows {
if self.data.row(row).expect("known row")[feature] <= threshold {
let row_weight = self.row_weights[row];
left[self.class_of_row[row]] += row_weight;
left_weight += row_weight;
}
}
let right_weight = total_weight - left_weight;
if left_weight < self.config.min_samples_leaf as f64
|| right_weight < self.config.min_samples_leaf as f64
{
continue;
}
for (slot, (&total, &left)) in right.iter_mut().zip(totals.iter().zip(left.iter())) {
*slot = total - left;
}
let score = (left_weight * gini(left, left_weight)
+ right_weight * gini(right, right_weight))
/ total_weight;
if best.as_ref().is_none_or(|current| score < current.score) {
best = Some(Split {
feature,
threshold,
score,
});
}
}
best
}
}
fn column_range(data: &MatrixView<'_>, rows: &[usize], feature: usize) -> (f32, f32) {
let mut min = f32::INFINITY;
let mut max = f32::NEG_INFINITY;
for &row in rows {
let value = data.row(row).expect("known row")[feature];
min = min.min(value);
max = max.max(value);
}
(min, max)
}
fn random_threshold(rng: &mut OwnedRng, min: f32, max: f32) -> Option<f32> {
if min >= max {
return None;
}
let span = f64::from(max) - f64::from(min);
let threshold = (f64::from(min) + rng.unit_f64() * span) as f32;
(threshold >= min && threshold < max).then_some(threshold)
}
fn gini(class_weights: &[f64], weight: f64) -> f64 {
let mut squares = 0.0_f64;
for &count in class_weights {
let proportion = count / weight;
squares += proportion * proportion;
}
1.0 - squares
}
fn split_threshold(a: f32, b: f32) -> f32 {
let midpoint = a + (b - a) * 0.5;
if midpoint.is_finite() && midpoint >= a && midpoint < b {
midpoint
} else {
a
}
}
fn integer_sqrt(value: usize) -> usize {
let mut root = (value as f64).sqrt() as usize;
while root.checked_add(1).is_some_and(|next| next <= value / next) {
root += 1;
}
while root != 0 && root > value / root {
root -= 1;
}
root
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn a_drawn_threshold_lands_strictly_inside_the_node_range() {
let mut rng = OwnedRng::new(4);
for (min, max) in [
(0.0_f32, 1000.0_f32),
(-3.5, 2.25),
(1e-6, 1.05e-6),
(-1e30, 1e30),
] {
for _ in 0..5_000 {
let threshold = random_threshold(&mut rng, min, max).expect("a spanned column");
assert!(
threshold >= min && threshold < max,
"draw {threshold} escaped [{min}, {max})"
);
}
}
}
#[test]
fn a_constant_column_consumes_no_draw() {
let mut rng = OwnedRng::new(21);
assert_eq!(random_threshold(&mut rng, 2.5, 2.5), None);
assert_eq!(random_threshold(&mut rng, 2.5, 1.0), None);
let mut untouched = OwnedRng::new(21);
assert_eq!(rng.next_u64(), untouched.next_u64());
let mut spent = OwnedRng::new(21);
let _ = random_threshold(&mut spent, 0.0, 1.0);
let mut stepped = OwnedRng::new(21);
let _ = stepped.next_u64();
assert_eq!(spent.next_u64(), stepped.next_u64());
}
#[test]
fn a_draw_that_narrows_onto_the_upper_endpoint_is_rejected_rather_than_nudged() {
let min = 1.0_f32;
let max = f32::from_bits(min.to_bits() + 1);
let mut rng = OwnedRng::new(5);
let mut kept = 0;
let mut rejected = 0;
for _ in 0..10_000 {
match random_threshold(&mut rng, min, max) {
Some(threshold) => {
assert_eq!(
threshold, min,
"the only representable interior value is min"
);
kept += 1;
}
None => rejected += 1,
}
}
assert!(
kept > 1_000 && rejected > 1_000,
"the narrowing guard did not fire on both sides: {kept} kept, {rejected} rejected"
);
}
#[test]
fn the_drawn_range_is_the_one_the_nodes_rows_span() {
let data = crate::data::DenseMatrix::new(vec![0.0, 5.0, 1.0, 6.0, 2.0, 7.0], 3, 2).unwrap();
let view = data.as_view();
assert_eq!(column_range(&view, &[0, 1, 2], 0), (0.0, 2.0));
assert_eq!(column_range(&view, &[1, 2], 0), (1.0, 2.0));
assert_eq!(column_range(&view, &[0, 2], 1), (5.0, 7.0));
assert_eq!(column_range(&view, &[1], 1), (6.0, 6.0));
}
}