use super::grower::{
Classification, GrowerConfig, grow_class_tree, grow_tree, unbootstrapped_sample,
};
use super::packed::{ClassTree, PackedTree};
use super::parameters::{DecisionTreeClassifierParams, encode_max_features, encode_splitter};
use super::validation::{
MAX_ARTIFACT_FEATURES, MAX_ARTIFACT_TOTAL_NODES, check_feature_width, check_output_len,
check_prediction_data, check_row, read_common_metadata, tree_seed, validate_fit,
write_common_metadata,
};
use crate::api::{
Capabilities, Classifier, Estimator, HasCapabilities, HasParams, ModelError,
ProbabilisticClassifier,
};
use crate::artifact::{
ArtifactCursor, ArtifactError, ArtifactPayloadWriter, DECISION_TREE_CLASSIFIER_ARTIFACT_KIND,
LogicalTreeNode, ModelArtifact, SchemaRole, decode_component, decode_logical_tree,
decode_v2_envelope, encode_component, encode_logical_tree, encode_v2_envelope,
};
use crate::data::{BinaryTargets, ClassTargets, MatrixView, SampleWeights};
use crate::numeric::OwnedRng;
const PAYLOAD_VERSION: u16 = 1;
const OBJECTIVE_VERSION: u32 = 1;
const METADATA_COMPONENT_KIND: u16 = 1;
const TREE_COMPONENT_KIND: u16 = 2;
const LEAF_PROBABILITY_COMPONENT_KIND: u16 = 3;
const COMPONENT_VERSION: u16 = 1;
const METADATA_BYTES: usize = 11 * 4 + 8;
const TREE_BINARY: u32 = 1;
const TREE_MULTICLASS: u32 = 2;
const MAX_CLASSES: usize = 256;
#[derive(Clone, Debug, PartialEq)]
enum Tree {
Binary(PackedTree),
Multiclass(ClassTree),
}
#[derive(Clone, Debug, PartialEq)]
pub struct DecisionTreeClassifier {
n_features_in: usize,
params: DecisionTreeClassifierParams,
classes: Vec<u8>,
tree: Tree,
}
impl DecisionTreeClassifier {
#[inline]
pub fn n_features_in(&self) -> usize {
self.n_features_in
}
#[inline]
pub fn get_params(&self) -> &DecisionTreeClassifierParams {
&self.params
}
#[inline]
pub fn classes(&self) -> &[u8] {
&self.classes
}
pub fn fit(
data: &MatrixView<'_>,
targets: &BinaryTargets,
params: DecisionTreeClassifierParams,
) -> Result<Self, ModelError> {
Self::fit_binary(data, targets, None, params)
}
pub fn fit_weighted(
data: &MatrixView<'_>,
targets: &BinaryTargets,
sample_weights: &SampleWeights,
params: DecisionTreeClassifierParams,
) -> Result<Self, ModelError> {
Self::fit_binary(data, targets, Some(sample_weights), params)
}
fn fit_binary(
data: &MatrixView<'_>,
targets: &BinaryTargets,
sample_weights: Option<&SampleWeights>,
params: DecisionTreeClassifierParams,
) -> Result<Self, ModelError> {
let config = grower_config(¶ms);
validate_fit(
data,
targets.as_slice().len(),
sample_weights.map(SampleWeights::len),
&config,
)?;
let saw_zero = targets.as_slice().contains(&0);
let saw_one = targets.as_slice().contains(&1);
let classes = match (saw_zero, saw_one) {
(true, true) => vec![0, 1],
(true, false) => vec![0],
(false, true) => vec![1],
(false, false) => unreachable!("non-empty validated binary targets"),
};
let (weights, rows) =
unbootstrapped_sample(data.rows(), sample_weights.map(SampleWeights::as_slice));
let mut rng = OwnedRng::new(tree_seed(params.random_state()));
let tree = grow_tree(
data,
targets.as_slice(),
&weights,
rows,
&config,
Classification,
&mut rng,
)?;
Ok(Self {
n_features_in: data.columns(),
params,
classes,
tree: Tree::Binary(tree),
})
}
pub fn fit_multiclass(
data: &MatrixView<'_>,
targets: &ClassTargets,
params: DecisionTreeClassifierParams,
) -> Result<Self, ModelError> {
Self::fit_multiclass_internal(data, targets, None, params)
}
pub fn fit_multiclass_weighted(
data: &MatrixView<'_>,
targets: &ClassTargets,
sample_weights: &SampleWeights,
params: DecisionTreeClassifierParams,
) -> Result<Self, ModelError> {
Self::fit_multiclass_internal(data, targets, Some(sample_weights), params)
}
fn fit_multiclass_internal(
data: &MatrixView<'_>,
targets: &ClassTargets,
sample_weights: Option<&SampleWeights>,
params: DecisionTreeClassifierParams,
) -> Result<Self, ModelError> {
let config = grower_config(¶ms);
validate_fit(
data,
targets.len(),
sample_weights.map(SampleWeights::len),
&config,
)?;
let classes = targets.classes().to_vec();
let class_of_row = targets
.as_slice()
.iter()
.map(|&label| {
targets
.class_index(label)
.expect("every target label is an observed class")
})
.collect::<Vec<_>>();
let (weights, rows) =
unbootstrapped_sample(data.rows(), sample_weights.map(SampleWeights::as_slice));
let mut rng = OwnedRng::new(tree_seed(params.random_state()));
let tree = grow_class_tree(
data,
&class_of_row,
classes.len(),
&weights,
rows,
&config,
&mut rng,
)?;
Ok(Self {
n_features_in: data.columns(),
params,
classes,
tree: Tree::Multiclass(tree),
})
}
#[cfg(test)]
pub(crate) fn packed_binary(&self) -> &PackedTree {
match &self.tree {
Tree::Binary(tree) => tree,
Tree::Multiclass(_) => unreachable!("binary fixture"),
}
}
#[cfg(test)]
pub(crate) fn packed_multiclass(&self) -> &ClassTree {
match &self.tree {
Tree::Multiclass(tree) => tree,
Tree::Binary(_) => unreachable!("multiclass fixture"),
}
}
pub fn predict_one(&self, row: &[f32]) -> Result<u8, ModelError> {
check_row(row, self.n_features_in)?;
Ok(match &self.tree {
Tree::Binary(tree) => {
if self.classes.len() == 1 {
self.classes[0]
} else {
u8::from(positive_probability(tree, row) > 0.5)
}
}
Tree::Multiclass(tree) => self.classes[argmax(tree.probabilities(row))],
})
}
pub fn predict(&self, data: &MatrixView<'_>) -> Result<Vec<u8>, ModelError> {
<Self as Classifier>::predict(self, data)
}
pub fn predict_into(&self, data: &MatrixView<'_>, output: &mut [u8]) -> Result<(), ModelError> {
check_prediction_data(data, output.len(), data.rows(), self.n_features_in)?;
match &self.tree {
Tree::Binary(tree) => {
if self.classes.len() == 1 {
output.fill(self.classes[0]);
return Ok(());
}
for (row, slot) in data.iter_rows().zip(output) {
*slot = u8::from(positive_probability(tree, row) > 0.5);
}
}
Tree::Multiclass(tree) => {
for (row, slot) in data.iter_rows().zip(output) {
*slot = self.classes[argmax(tree.probabilities(row))];
}
}
}
Ok(())
}
pub fn predict_proba_one(&self, row: &[f32]) -> Result<Vec<f32>, ModelError> {
let mut output = vec![0.0; self.classes.len()];
self.predict_proba_one_into(row, &mut output)?;
Ok(output)
}
pub fn predict_proba_one_into(
&self,
row: &[f32],
output: &mut [f32],
) -> Result<(), ModelError> {
check_row(row, self.n_features_in)?;
check_output_len(output.len(), self.classes.len())?;
self.write_probabilities(row, output);
Ok(())
}
pub fn predict_proba(&self, data: &MatrixView<'_>) -> Result<Vec<f32>, ModelError> {
<Self as ProbabilisticClassifier>::predict_proba(self, data)
}
pub fn predict_proba_into(
&self,
data: &MatrixView<'_>,
output: &mut [f32],
) -> Result<(), ModelError> {
let columns = self.classes.len();
let expected = data
.rows()
.checked_mul(columns)
.ok_or(ModelError::OutputShapeOverflow {
rows: data.rows(),
columns,
})?;
check_prediction_data(data, output.len(), expected, self.n_features_in)?;
for (row, slot) in data.iter_rows().zip(output.chunks_exact_mut(columns)) {
self.write_probabilities(row, slot);
}
Ok(())
}
pub fn predict_class_proba_one(&self, row: &[f32], class: u8) -> Result<f32, ModelError> {
check_row(row, self.n_features_in)?;
let class_index = self.class_index(class)?;
let mut storage = [0.0_f32; MAX_CLASSES];
let probabilities = &mut storage[..self.classes.len()];
self.write_probabilities(row, probabilities);
Ok(probabilities[class_index])
}
pub fn predict_class_proba(
&self,
data: &MatrixView<'_>,
class: u8,
) -> Result<Vec<f32>, ModelError> {
<Self as ProbabilisticClassifier>::predict_class_proba(self, data, class)
}
pub fn predict_class_proba_into(
&self,
data: &MatrixView<'_>,
class: u8,
output: &mut [f32],
) -> Result<(), ModelError> {
check_feature_width(data, self.n_features_in)?;
let class_index = self.class_index(class)?;
check_output_len(output.len(), data.rows())?;
let mut storage = [0.0_f32; MAX_CLASSES];
let probabilities = &mut storage[..self.classes.len()];
for (row, slot) in data.iter_rows().zip(output) {
self.write_probabilities(row, probabilities);
*slot = probabilities[class_index];
}
Ok(())
}
pub fn predict_positive_proba_one(&self, row: &[f32]) -> Result<f32, ModelError> {
let tree = self.require_binary_tree()?;
check_row(row, self.n_features_in)?;
if self.classes.len() == 1 {
return Ok(f32::from(self.classes[0]));
}
Ok(positive_probability(tree, row))
}
pub fn predict_positive_proba(&self, data: &MatrixView<'_>) -> Result<Vec<f32>, ModelError> {
self.require_binary_tree()?;
check_prediction_data(data, data.rows(), data.rows(), self.n_features_in)?;
let mut output = vec![0.0; data.rows()];
self.predict_positive_proba_into(data, &mut output)?;
Ok(output)
}
pub fn predict_positive_proba_into(
&self,
data: &MatrixView<'_>,
output: &mut [f32],
) -> Result<(), ModelError> {
let tree = self.require_binary_tree()?;
check_prediction_data(data, output.len(), data.rows(), self.n_features_in)?;
if self.classes.len() == 1 {
output.fill(f32::from(self.classes[0]));
return Ok(());
}
for (row, slot) in data.iter_rows().zip(output) {
*slot = positive_probability(tree, row);
}
Ok(())
}
fn write_probabilities(&self, row: &[f32], output: &mut [f32]) {
match &self.tree {
Tree::Binary(tree) => {
if self.classes.len() == 1 {
output[0] = 1.0;
} else {
let positive = positive_probability(tree, row);
output[0] = 1.0 - positive;
output[1] = positive;
}
}
Tree::Multiclass(tree) => output.copy_from_slice(tree.probabilities(row)),
}
}
#[inline]
fn class_index(&self, class: u8) -> Result<usize, ModelError> {
self.classes
.binary_search(&class)
.map_err(|_| ModelError::UnknownClass { class })
}
fn require_binary_tree(&self) -> Result<&PackedTree, ModelError> {
match &self.tree {
Tree::Binary(tree) => Ok(tree),
Tree::Multiclass(_) => Err(ModelError::MulticlassOutput {
columns: self.classes.len(),
}),
}
}
}
impl ModelArtifact for DecisionTreeClassifier {
const ARTIFACT_KIND: u16 = DECISION_TREE_CLASSIFIER_ARTIFACT_KIND;
fn to_artifact(&self, schema: [u8; 32]) -> Result<Vec<u8>, ArtifactError> {
let (flavour, node_count) = match &self.tree {
Tree::Binary(tree) => (TREE_BINARY, tree.logical_node_count()),
Tree::Multiclass(tree) => (TREE_MULTICLASS, tree.logical_node_count()),
};
if self.n_features_in > MAX_ARTIFACT_FEATURES
|| node_count > MAX_ARTIFACT_TOTAL_NODES
|| self.classes.is_empty()
|| self.classes.len() > MAX_CLASSES
{
return Err(ArtifactError::InvalidPayload);
}
let class_count =
u32::try_from(self.classes.len()).map_err(|_| ArtifactError::InvalidPayload)?;
let mut metadata =
ArtifactPayloadWriter::with_capacity(METADATA_BYTES + self.classes.len() * 4);
write_common_metadata(
&mut metadata,
OBJECTIVE_VERSION,
self.n_features_in,
self.params.max_depth(),
self.params.min_samples_split(),
self.params.min_samples_leaf(),
encode_max_features(self.params.max_features())?,
encode_splitter(self.params.splitter()),
self.params.random_state(),
node_count,
)?;
metadata.u32(flavour);
metadata.u32(class_count);
for &class in &self.classes {
metadata.u32(u32::from(class));
}
let mut payload = encode_component(
METADATA_COMPONENT_KIND,
COMPONENT_VERSION,
&metadata.finish(),
)?;
match &self.tree {
Tree::Binary(tree) => {
payload.extend_from_slice(&encode_component(
TREE_COMPONENT_KIND,
COMPONENT_VERSION,
&encode_logical_tree(&tree.to_logical_nodes())?,
)?);
}
Tree::Multiclass(tree) => {
let (nodes, probabilities) = tree.to_logical_nodes();
payload.extend_from_slice(&encode_component(
TREE_COMPONENT_KIND,
COMPONENT_VERSION,
&encode_logical_tree(&nodes)?,
)?);
let mut block = ArtifactPayloadWriter::with_capacity(8 + probabilities.len() * 4);
block.u32(
u32::try_from(probabilities.len() / self.classes.len())
.map_err(|_| ArtifactError::InvalidPayload)?,
);
block.u32(class_count);
for &value in &probabilities {
block.f32(value);
}
payload.extend_from_slice(&encode_component(
LEAF_PROBABILITY_COMPONENT_KIND,
COMPONENT_VERSION,
&block.finish(),
)?);
}
}
encode_v2_envelope(
Self::ARTIFACT_KIND,
PAYLOAD_VERSION,
&[(SchemaRole::Input, schema)],
&payload,
)
}
fn from_artifact(bytes: &[u8], schema: [u8; 32]) -> Result<Self, ArtifactError> {
let mut envelope = decode_v2_envelope(
bytes,
Self::ARTIFACT_KIND,
PAYLOAD_VERSION,
&[(SchemaRole::Input, schema)],
)?;
let mut metadata =
decode_component(&mut envelope, METADATA_COMPONENT_KIND, COMPONENT_VERSION)?;
let common = read_common_metadata(&mut metadata, OBJECTIVE_VERSION)?;
let flavour = metadata.u32()?;
let class_count = metadata.u32()? as usize;
if (flavour != TREE_BINARY && flavour != TREE_MULTICLASS)
|| class_count == 0
|| class_count > MAX_CLASSES
{
return Err(ArtifactError::InvalidPayload);
}
let mut classes: Vec<u8> = Vec::with_capacity(metadata.bounded_capacity(class_count, 4));
for _ in 0..class_count {
let label = u8::try_from(metadata.u32()?).map_err(|_| ArtifactError::InvalidPayload)?;
if classes.last().is_some_and(|&previous| previous >= label) {
return Err(ArtifactError::InvalidPayload);
}
classes.push(label);
}
if flavour == TREE_BINARY && classes.iter().any(|&label| label > 1) {
return Err(ArtifactError::InvalidPayload);
}
if !metadata.is_empty() {
return Err(ArtifactError::TrailingBytes);
}
let logical = decode_logical_tree(decode_component(
&mut envelope,
TREE_COMPONENT_KIND,
COMPONENT_VERSION,
)?)?;
if logical.len() != common.node_count {
return Err(ArtifactError::InvalidPayload);
}
let tree = if flavour == TREE_BINARY {
if logical.iter().any(|node| {
matches!(node, LogicalTreeNode::Leaf { value } if !(0.0..=1.0).contains(value))
}) {
return Err(ArtifactError::InvalidPayload);
}
Tree::Binary(PackedTree::from_logical_nodes(
&logical,
common.n_features_in,
)?)
} else {
let probabilities = decode_leaf_probabilities(
decode_component(
&mut envelope,
LEAF_PROBABILITY_COMPONENT_KIND,
COMPONENT_VERSION,
)?,
class_count,
)?;
Tree::Multiclass(ClassTree::from_logical_nodes(
&logical,
&probabilities,
class_count,
common.n_features_in,
)?)
};
if !envelope.is_empty() {
return Err(ArtifactError::TrailingBytes);
}
Ok(Self {
n_features_in: common.n_features_in,
params: DecisionTreeClassifierParams::default()
.with_max_depth(common.max_depth)
.with_min_samples_split(common.min_samples_split)
.with_min_samples_leaf(common.min_samples_leaf)
.with_max_features(common.max_features)
.with_splitter(common.splitter)
.with_random_state(common.random_state),
classes,
tree,
})
}
}
fn decode_leaf_probabilities(
mut cursor: ArtifactCursor<'_>,
class_count: usize,
) -> Result<Vec<f32>, ArtifactError> {
let leaves = cursor.u32()? as usize;
let declared_classes = cursor.u32()? as usize;
let expected = leaves.checked_mul(class_count);
if leaves == 0 || declared_classes != class_count || expected.is_none() {
return Err(ArtifactError::InvalidPayload);
}
let expected = expected.expect("checked above");
let mut probabilities = Vec::with_capacity(cursor.bounded_capacity(expected, 4));
for _ in 0..expected {
let value = cursor.f32()?;
if !value.is_finite() || !(0.0..=1.0).contains(&value) {
return Err(ArtifactError::InvalidPayload);
}
probabilities.push(value);
}
if !cursor.is_empty() {
return Err(ArtifactError::TrailingBytes);
}
Ok(probabilities)
}
#[inline]
fn positive_probability(tree: &PackedTree, row: &[f32]) -> f32 {
tree.predict(row).clamp(0.0, 1.0)
}
fn argmax(values: &[f32]) -> usize {
let mut best = 0;
for index in 1..values.len() {
if values[index] > values[best] {
best = index;
}
}
best
}
fn grower_config(params: &DecisionTreeClassifierParams) -> GrowerConfig {
GrowerConfig {
max_depth: params.max_depth(),
min_samples_split: params.min_samples_split(),
min_samples_leaf: params.min_samples_leaf(),
max_features: params.max_features(),
splitter: params.splitter(),
}
}
impl Estimator for DecisionTreeClassifier {
fn n_features_in(&self) -> usize {
self.n_features_in
}
}
impl Classifier for DecisionTreeClassifier {
fn classes(&self) -> &[u8] {
&self.classes
}
fn predict_into(&self, data: &MatrixView<'_>, output: &mut [u8]) -> Result<(), ModelError> {
DecisionTreeClassifier::predict_into(self, data, output)
}
}
impl ProbabilisticClassifier for DecisionTreeClassifier {
fn predict_proba_into(
&self,
data: &MatrixView<'_>,
output: &mut [f32],
) -> Result<(), ModelError> {
DecisionTreeClassifier::predict_proba_into(self, data, output)
}
fn predict_class_proba_into(
&self,
data: &MatrixView<'_>,
class: u8,
output: &mut [f32],
) -> Result<(), ModelError> {
DecisionTreeClassifier::predict_class_proba_into(self, data, class, output)
}
}
impl HasParams for DecisionTreeClassifier {
type Params = DecisionTreeClassifierParams;
fn get_params(&self) -> &Self::Params {
&self.params
}
}
impl HasCapabilities for DecisionTreeClassifier {
const CAPABILITIES: Capabilities = Capabilities::NONE
.with_sample_weights(true)
.with_artifact(true)
.with_multiclass(true)
.with_probability(true);
}