DisTreebution.CRPSRT package#

Submodules#

DisTreebution.CRPSRT.FenwickTree module#

class DisTreebution.CRPSRT.FenwickTree.FenwickTree(n)[source]#

Bases: object

A data structure for maintaining cumulative (prefix) sums. (aka “binary indexed tree”) Incrementing a value is O(log n). Calculating a cumulative sum is O(log n). Retrieving a single frequency is a special case of calculating a cumulative sum, and is thus O(log n).

prefix_sum(stop)[source]#: Returns sum of first elements (sum up to stop, exclusive).

range_sum(start, stop)[source]#: Returns sum from start (inclusive) to stop (exclusive).

frequencies()[source]#: Retrieves all frequencies in O(n).

add(idx, k)[source]#: Adds k to idx’th element (0-based indexing).

init(frequencies)[source]#: Initialize in O(n) with specified frequencies.

DisTreebution.CRPSRT.MinMaxHeap module#

class DisTreebution.CRPSRT.MinMaxHeap.MinMaxHeap(reserve=0)[source]#

Bases: object

Implementation of a Min-max heap following Atkinson, Sack, Santoro, and Strothotte (1986): https://doi.org/10.1145/6617.6621

insert(key)[source]#: Insert key into heap. Complexity: O(log(n))

peekmin()[source]#: Get minimum element. Complexity: O(1)

peekmax()[source]#: Get maximum element. Complexity: O(1)

popmin()[source]#: Remove and return minimum element. Complexity: O(log(n))

popmax()[source]#: Remove and return maximum element. Complexity: O(log(n))

DisTreebution.CRPSRT.MinMaxHeap.level(i)[source]#

DisTreebution.CRPSRT.MinMaxHeap.trickledown(array, i, size)[source]#

DisTreebution.CRPSRT.MinMaxHeap.trickledownmin(array, i, size)[source]#

DisTreebution.CRPSRT.MinMaxHeap.trickledownmax(array, i, size)[source]#

DisTreebution.CRPSRT.MinMaxHeap.bubbleup(array, i)[source]#

DisTreebution.CRPSRT.MinMaxHeap.bubbleupmin(array, i)[source]#

DisTreebution.CRPSRT.MinMaxHeap.bubbleupmax(array, i)[source]#

DisTreebution.CRPSRT.MinMaxHeap.peekmin(array, size)[source]#

DisTreebution.CRPSRT.MinMaxHeap.peekmax(array, size)[source]#

DisTreebution.CRPSRT.MinMaxHeap.removemin(array, size)[source]#

DisTreebution.CRPSRT.MinMaxHeap.removemax(array, size)[source]#

DisTreebution.CRPSRT.MinMaxHeap.insert(array, k, size)[source]#

DisTreebution.CRPSRT.MinMaxHeap.minmaxheapproperty(array, size)[source]#

DisTreebution.CRPSRT.MinMaxHeap.test(n)[source]#

DisTreebution.CRPSRT.MinMaxHeap.test_heap(n)[source]#

DisTreebution.CRPSRT.RegressionTree module#

class DisTreebution.CRPSRT.RegressionTree.RegressionTree(max_depth=None, min_samples_split=2, limit_use_CRPS=None, quantiles=None, IG_biais_correction=None)[source]#

Bases: object

A custom regression tree class computing information gains based on the entropy associated with the CRPS loss.

Parameters:

max_depth int: The maximum depth of the tree. If None, nodes are expanded until all leaves are pure or contain fewer than min_samples_split samples.
min_samples_split int: (default=2) The minimum number of samples required to split an internal node.
limit_use_CRPS int or None: If set, use CRPS loss for nodes with sample size <= limit_use_CRPS, otherwise use multiple quantile loss.
quantiles list or None: List of quantiles to use for the multiple quantile loss. Required if limit_use_CRPS is set.
IG_biais_correction str: (default=None) Whether to use leave-one-out or Mallows estimation in the entropy/loss calculation.

Attributes

Variables:

feature_index int: Index of the feature used for splitting at the current node.
threshold float: Threshold value for the split at the current node.
left RegressionTree: Left child node.
right RegressionTree: Right child node.
y array-like: Target values at the leaf node.

Methods

fit(X, y, depth=0, ref_tree=None, max_depth_ref_tree=-1)[source]#
Fit the regression tree to the data.

find_best_split(X, y)[source]#
Find the best feature and threshold to split the data at the current node.

predict(X)[source]#
Predict target values for given input samples.

get_values_leaf(X, indexes)[source]#
Retrieve the samples and their target values for each leaf.

get_values_leaf_and_groups(X, indexes, current_group_depth=str(), max_depth_group=1)[source]#
Retrieve the samples, their target values, and group identifiers for each leaf up to a specified group depth.

Notes

This implementation supports custom loss functions CRPS for splitting.
The tree can optionally follow the structure of a reference tree up to a certain depth.

fit(X, y, depth=0, ref_tree=None, max_depth_ref_tree=-1)[source]#

Recursively fits the regression tree to the provided data.

Parameters:

X np.ndarray: Feature matrix of shape (n_samples, n_features).
y np.ndarray: Target values of shape (n_samples,).
depth int: (default=0) Current depth of the tree.
ref_tree RegressionTree or None: (default=None) Reference tree to guide the splitting process. If provided, the tree will copy splits from the reference tree up to max_depth_ref_tree.
max_depth_ref_tree int: (default=-1) Maximum depth up to which the reference tree is used for splitting. A value of -1 means not used.

Returns:

None

If the maximum depth is reached or the number of samples is less than min_samples_split, the node becomes a leaf and stores the target values.
If a reference tree is provided and the current depth is less than max_depth_ref_tree, the split is copied from the reference tree.
Otherwise, the best split is found using the find_best_split method.
The method recursively fits the left and right child nodes.

find_best_split(X, y)[source]#

Finds the best feature and threshold to split the data for a regression tree node.

This method evaluates all possible splits across all features to determine the optimal split point that minimizes a custom score based on the CRPS entropy. It ensures that the resulting child nodes satisfy the minimum sample split constraint.

Parameters:

X np.ndarray: Feature matrix of shape (n_samples, n_features).
y np.ndarray: Target values of shape (n_samples,).

Returns tuple or None:

A tuple (feature_index, threshold) representing the best split found, or None if no valid split exists.

predict(X)[source]#

Predict target values for the given input samples.

Parameters:

X np.ndarray: Feature matrix of shape (n_samples, n_features).

Returns np.ndarray:

Predicted target values of shape (n_samples,).

get_values_leaf(X, indexes)[source]#

Retrieve the samples and their target values for each leaf.

Parameters:

X np.ndarray: Feature matrix of shape (n_samples, n_features).
indexes np.ndarray: Array of sample indexes corresponding to the rows in X.

Returns list:

A list of lists, where each sublist contains the sample indexes and target values for each leaf.

get_values_leaf_and_groups(X, indexes, current_group_depth='', max_depth_group=1)[source]#

Retrieve the samples, their target values, and group identifiers for each leaf up to a specified group depth.

Parameters:

X np.ndarray: Feature matrix of shape (n_samples, n_features).
indexes np.ndarray: Array of sample indexes corresponding to the rows in X.
current_group_depth str: (optional) Current group depth identifier (default is an empty string).
max_depth_group int: (optional) Maximum depth for group identifiers (default is 1).

Returns list: