"""Interface for different tree building strategies."""

cpdef build(

self,

Tree tree,

object X,

const float64_t[:, ::1] y,

const float64_t[:] sample_weight=None,

const uint8_t[::1] missing_values_in_feature_mask=None,

):

"""Build a decision tree from the training set (X, y)."""

"""Build a decision tree in depth-first fashion."""

def __cinit__(self, Splitter splitter, intp_t min_samples_split,

intp_t min_samples_leaf, float64_t min_weight_leaf,

intp_t max_depth, float64_t min_impurity_decrease):

self.splitter = splitter

self.min_samples_split = min_samples_split

self.min_samples_leaf = min_samples_leaf

self.min_weight_leaf = min_weight_leaf

self.max_depth = max_depth

self.min_impurity_decrease = min_impurity_decrease

cpdef build(

self,

Tree tree,

object X,

const float64_t[:, ::1] y,

const float64_t[:] sample_weight=None,

const uint8_t[::1] missing_values_in_feature_mask=None,

):

"""Build a decision tree from the training set (X, y)."""

# check input

X, y, sample_weight = self._check_input(X, y, sample_weight)

# Initial capacity

cdef intp_t init_capacity

if tree.max_depth <= 10:

init_capacity = <intp_t> (2 ** (tree.max_depth + 1)) - 1

else:

init_capacity = 2047

tree._resize(init_capacity)

# Parameters

cdef Splitter splitter = self.splitter

cdef intp_t max_depth = self.max_depth

cdef intp_t min_samples_leaf = self.min_samples_leaf

cdef float64_t min_weight_leaf = self.min_weight_leaf

cdef intp_t min_samples_split = self.min_samples_split

cdef float64_t min_impurity_decrease = self.min_impurity_decrease

# Recursive partition (without actual recursion)

splitter.init(X, y, sample_weight, missing_values_in_feature_mask)

cdef intp_t start

cdef intp_t end

cdef intp_t depth

cdef intp_t parent

cdef bint is_left

cdef intp_t n_node_samples = splitter.n_samples

cdef float64_t weighted_n_node_samples

cdef SplitRecord split

cdef intp_t node_id

cdef float64_t middle_value

cdef float64_t left_child_min

cdef float64_t left_child_max

cdef float64_t right_child_min

cdef float64_t right_child_max

cdef bint is_leaf

cdef bint first = 1

cdef intp_t max_depth_seen = -1

cdef int rc = 0

cdef stack[StackRecord] builder_stack

cdef StackRecord stack_record

cdef ParentInfo parent_record

_init_parent_record(&parent_record)

with nogil:

# push root node onto stack

builder_stack.push({

"start": 0,

"end": n_node_samples,

"depth": 0,

"parent": _TREE_UNDEFINED,

"is_left": 0,

"impurity": INFINITY,

"n_constant_features": 0,

"lower_bound": -INFINITY,

"upper_bound": INFINITY,

})

while not builder_stack.empty():

stack_record = builder_stack.top()

builder_stack.pop()

start = stack_record.start

end = stack_record.end

depth = stack_record.depth

parent = stack_record.parent

is_left = stack_record.is_left

parent_record.impurity = stack_record.impurity

parent_record.n_constant_features = stack_record.n_constant_features

parent_record.lower_bound = stack_record.lower_bound

parent_record.upper_bound = stack_record.upper_bound

n_node_samples = end - start

splitter.node_reset(start, end, &weighted_n_node_samples)

is_leaf = (depth >= max_depth or

n_node_samples < min_samples_split or

n_node_samples < 2 * min_samples_leaf or

weighted_n_node_samples < 2 * min_weight_leaf)

if first:

parent_record.impurity = splitter.node_impurity()

first = 0

# impurity == 0 with tolerance due to rounding errors

is_leaf = is_leaf or parent_record.impurity <= EPSILON

if not is_leaf:

splitter.node_split(

&parent_record,

&split,

)

# If EPSILON=0 in the below comparison, float precision

# issues stop splitting, producing trees that are

# dissimilar to v0.18

is_leaf = (is_leaf or split.pos >= end or

(split.improvement + EPSILON <

min_impurity_decrease))

node_id = tree._add_node(parent, is_left, is_leaf, split.feature,

split.threshold, parent_record.impurity,

n_node_samples, weighted_n_node_samples,

split.missing_go_to_left)

if node_id == INTPTR_MAX:

rc = -1

break

# Store value for all nodes, to facilitate tree/model

# inspection and interpretation

splitter.node_value(tree.value + node_id * tree.value_stride)

if splitter.with_monotonic_cst:

splitter.clip_node_value(tree.value + node_id * tree.value_stride, parent_record.lower_bound, parent_record.upper_bound)

if not is_leaf:

if (

not splitter.with_monotonic_cst or

splitter.monotonic_cst[split.feature] == 0

):

# Split on a feature with no monotonicity constraint

# Current bounds must always be propagated to both children.

# If a monotonic constraint is active, bounds are used in

# node value clipping.

left_child_min = right_child_min = parent_record.lower_bound

left_child_max = right_child_max = parent_record.upper_bound

elif splitter.monotonic_cst[split.feature] == 1:

# Split on a feature with monotonic increase constraint

left_child_min = parent_record.lower_bound

right_child_max = parent_record.upper_bound

# Lower bound for right child and upper bound for left child

# are set to the same value.

middle_value = splitter.criterion.middle_value()

right_child_min = middle_value

left_child_max = middle_value

else: # i.e. splitter.monotonic_cst[split.feature] == -1

# Split on a feature with monotonic decrease constraint

right_child_min = parent_record.lower_bound

left_child_max = parent_record.upper_bound

# Lower bound for left child and upper bound for right child

# are set to the same value.

middle_value = splitter.criterion.middle_value()

left_child_min = middle_value

right_child_max = middle_value

# Push right child on stack

builder_stack.push({

"start": split.pos,

"end": end,

"depth": depth + 1,

"parent": node_id,

"is_left": 0,

"impurity": split.impurity_right,

"n_constant_features": parent_record.n_constant_features,

"lower_bound": right_child_min,

"upper_bound": right_child_max,

})

# Push left child on stack

builder_stack.push({

"start": start,

"end": split.pos,

"depth": depth + 1,

"parent": node_id,

"is_left": 1,

"impurity": split.impurity_left,

"n_constant_features": parent_record.n_constant_features,

"lower_bound": left_child_min,

"upper_bound": left_child_max,

})

if depth > max_depth_seen:

max_depth_seen = depth

if rc >= 0:

rc = tree._resize_c(tree.node_count)

if rc >= 0:

tree.max_depth = max_depth_seen

if rc == -1:

# Record of information of a Node, the frontier for a split. Those records are

# maintained in a heap to access the Node with the best improvement in impurity,

# allowing growing trees greedily on this improvement.

"""Build a decision tree in best-first fashion.

cdef intp_t max_leaf_nodes

def __cinit__(self, Splitter splitter, intp_t min_samples_split,

intp_t min_samples_leaf, min_weight_leaf,

intp_t max_depth, intp_t max_leaf_nodes,

float64_t min_impurity_decrease):

self.splitter = splitter

self.min_samples_split = min_samples_split

self.min_samples_leaf = min_samples_leaf

self.min_weight_leaf = min_weight_leaf

self.max_depth = max_depth

self.max_leaf_nodes = max_leaf_nodes

self.min_impurity_decrease = min_impurity_decrease

cpdef build(

self,

Tree tree,

object X,

const float64_t[:, ::1] y,

const float64_t[:] sample_weight=None,

const uint8_t[::1] missing_values_in_feature_mask=None,

):

"""Build a decision tree from the training set (X, y)."""

# check input

X, y, sample_weight = self._check_input(X, y, sample_weight)

# Parameters

cdef Splitter splitter = self.splitter

cdef intp_t max_leaf_nodes = self.max_leaf_nodes

# Recursive partition (without actual recursion)

splitter.init(X, y, sample_weight, missing_values_in_feature_mask)

cdef vector[FrontierRecord] frontier

cdef FrontierRecord record

cdef FrontierRecord split_node_left

cdef FrontierRecord split_node_right

cdef float64_t left_child_min

cdef float64_t left_child_max

cdef float64_t right_child_min

cdef float64_t right_child_max

cdef intp_t n_node_samples = splitter.n_samples

cdef intp_t max_split_nodes = max_leaf_nodes - 1

cdef bint is_leaf

cdef intp_t max_depth_seen = -1

cdef int rc = 0

cdef Node* node

cdef ParentInfo parent_record

_init_parent_record(&parent_record)

# Initial capacity

cdef intp_t init_capacity = max_split_nodes + max_leaf_nodes

tree._resize(init_capacity)

with nogil:

# add root to frontier

rc = self._add_split_node(

splitter=splitter,

tree=tree,

start=0,

end=n_node_samples,

is_first=IS_FIRST,

is_left=IS_LEFT,

parent=NULL,

depth=0,

parent_record=&parent_record,

res=&split_node_left,

)

if rc >= 0:

_add_to_frontier(split_node_left, frontier)

while not frontier.empty():

pop_heap(frontier.begin(), frontier.end(), &_compare_records)

record = frontier.back()

frontier.pop_back()

node = &tree.nodes[record.node_id]

is_leaf = (record.is_leaf or max_split_nodes <= 0)

if is_leaf:

# Node is not expandable; set node as leaf

node.left_child = _TREE_LEAF

node.right_child = _TREE_LEAF

node.feature = _TREE_UNDEFINED

node.threshold = _TREE_UNDEFINED

else:

# Node is expandable

if (

not splitter.with_monotonic_cst or

splitter.monotonic_cst[node.feature] == 0

):

# Split on a feature with no monotonicity constraint

# Current bounds must always be propagated to both children.

# If a monotonic constraint is active, bounds are used in

# node value clipping.

left_child_min = right_child_min = record.lower_bound

left_child_max = right_child_max = record.upper_bound

elif splitter.monotonic_cst[node.feature] == 1:

# Split on a feature with monotonic increase constraint

left_child_min = record.lower_bound

right_child_max = record.upper_bound

# Lower bound for right child and upper bound for left child

# are set to the same value.

right_child_min = record.middle_value

left_child_max = record.middle_value

else: # i.e. splitter.monotonic_cst[split.feature] == -1

# Split on a feature with monotonic decrease constraint

right_child_min = record.lower_bound

left_child_max = record.upper_bound

# Lower bound for left child and upper bound for right child

# are set to the same value.

left_child_min = record.middle_value

right_child_max = record.middle_value

# Decrement number of split nodes available

max_split_nodes -= 1

# Compute left split node

parent_record.lower_bound = left_child_min

parent_record.upper_bound = left_child_max

parent_record.impurity = record.impurity_left

rc = self._add_split_node(

splitter=splitter,

tree=tree,

start=record.start,

end=record.pos,

is_first=IS_NOT_FIRST,

is_left=IS_LEFT,

parent=node,

depth=record.depth + 1,

parent_record=&parent_record,

res=&split_node_left,

)

if rc == -1:

break

# tree.nodes may have changed

node = &tree.nodes[record.node_id]

# Compute right split node

parent_record.lower_bound = right_child_min

parent_record.upper_bound = right_child_max

parent_record.impurity = record.impurity_right

rc = self._add_split_node(

splitter=splitter,

tree=tree,

start=record.pos,

end=record.end,

is_first=IS_NOT_FIRST,

is_left=IS_NOT_LEFT,

parent=node,

depth=record.depth + 1,

parent_record=&parent_record,

res=&split_node_right,

)

if rc == -1:

break

# Add nodes to queue

_add_to_frontier(split_node_left, frontier)

_add_to_frontier(split_node_right, frontier)

if record.depth > max_depth_seen:

max_depth_seen = record.depth

if rc >= 0:

rc = tree._resize_c(tree.node_count)

if rc >= 0:

tree.max_depth = max_depth_seen

if rc == -1:

n_node_samples < self.min_samples_split or

n_node_samples < 2 * self.min_samples_leaf or

weighted_n_node_samples < 2 * self.min_weight_leaf or

parent_record.impurity <= EPSILON # impurity == 0 with tolerance

if parent != NULL

else _TREE_UNDEFINED,

is_left, is_leaf,

split.feature, split.threshold, parent_record.impurity,

n_node_samples, weighted_n_node_samples,

"""Array-based representation of a binary decision tree.

# Wrap for outside world.

# WARNING: these reference the current `nodes` and `value` buffers, which

# must not be freed by a subsequent memory allocation.

# (i.e. through `_resize` or `__setstate__`)

@property

def n_classes(self):

return sizet_ptr_to_ndarray(self.n_classes, self.n_outputs)

@property

def children_left(self):

return self._get_node_ndarray()['left_child'][:self.node_count]

@property

def children_right(self):

return self._get_node_ndarray()['right_child'][:self.node_count]

@property

def n_leaves(self):

return np.sum(np.logical_and(

self.children_left == -1,

self.children_right == -1))

@property

def feature(self):

return self._get_node_ndarray()['feature'][:self.node_count]

@property

def threshold(self):

return self._get_node_ndarray()['threshold'][:self.node_count]

@property

def impurity(self):

return self._get_node_ndarray()['impurity'][:self.node_count]

@property

def n_node_samples(self):

return self._get_node_ndarray()['n_node_samples'][:self.node_count]

@property

def weighted_n_node_samples(self):

return self._get_node_ndarray()['weighted_n_node_samples'][:self.node_count]

@property

def missing_go_to_left(self):

return self._get_node_ndarray()['missing_go_to_left'][:self.node_count]

@property

def value(self):

return self._get_value_ndarray()[:self.node_count]

# TODO: Convert n_classes to cython.integral memory view once

# https://github.com/cython/cython/issues/5243 is fixed

def __cinit__(self, intp_t n_features, cnp.ndarray n_classes, intp_t n_outputs):

"""Constructor."""

cdef intp_t dummy = 0

size_t_dtype = np.array(dummy).dtype

n_classes = _check_n_classes(n_classes, size_t_dtype)

# Input/Output layout

self.n_features = n_features

self.n_outputs = n_outputs

self.n_classes = NULL

safe_realloc(&self.n_classes, n_outputs)

self.max_n_classes = np.max(n_classes)

self.value_stride = n_outputs * self.max_n_classes

cdef intp_t k

for k in range(n_outputs):

self.n_classes[k] = n_classes[k]

# Inner structures

self.max_depth = 0

self.node_count = 0

self.capacity = 0

self.value = NULL

self.nodes = NULL

def __dealloc__(self):

"""Destructor."""

# Free all inner structures

free(self.n_classes)

free(self.value)

free(self.nodes)

def __reduce__(self):

"""Reduce re-implementation, for pickling."""

return (Tree, (self.n_features,

sizet_ptr_to_ndarray(self.n_classes, self.n_outputs),

self.n_outputs), self.__getstate__())

def __getstate__(self):

"""Getstate re-implementation, for pickling."""

d = {}

# capacity is inferred during the __setstate__ using nodes

d["max_depth"] = self.max_depth

d["node_count"] = self.node_count

d["nodes"] = self._get_node_ndarray()

d["values"] = self._get_value_ndarray()

return d

def __setstate__(self, d):

"""Setstate re-implementation, for unpickling."""

self.max_depth = d["max_depth"]

self.node_count = d["node_count"]

if 'nodes' not in d:

raise ValueError('You have loaded Tree version which '

'cannot be imported')

node_ndarray = d['nodes']

value_ndarray = d['values']

value_shape = (node_ndarray.shape[0], self.n_outputs,

self.max_n_classes)

node_ndarray = _check_node_ndarray(node_ndarray, expected_dtype=NODE_DTYPE)

value_ndarray = _check_value_ndarray(

value_ndarray,

expected_dtype=np.dtype(np.float64),

expected_shape=value_shape

)

self.capacity = node_ndarray.shape[0]

if self._resize_c(self.capacity) != 0:

raise MemoryError("resizing tree to %d" % self.capacity)

memcpy(self.nodes, cnp.PyArray_DATA(node_ndarray),

self.capacity * sizeof(Node))

memcpy(self.value, cnp.PyArray_DATA(value_ndarray),

self.capacity * self.value_stride * sizeof(float64_t))

cdef int _resize(self, intp_t capacity) except -1 nogil:

"""Resize all inner arrays to `capacity`, if `capacity` == -1, then

if self._resize_c(capacity) != 0:

# Acquire gil only if we need to raise

with gil:

raise MemoryError()

cdef int _resize_c(self, intp_t capacity=INTPTR_MAX) except -1 nogil:

"""Guts of _resize

if capacity == self.capacity and self.nodes != NULL:

return 0

if capacity == INTPTR_MAX:

if self.capacity == 0:

capacity = 3 # default initial value

else:

capacity = 2 * self.capacity

safe_realloc(&self.nodes, capacity)

safe_realloc(&self.value, capacity * self.value_stride)

if capacity > self.capacity:

# value memory is initialised to 0 to enable classifier argmax

memset(<void*>(self.value + self.capacity * self.value_stride), 0,

(capacity - self.capacity) * self.value_stride *

sizeof(float64_t))

# node memory is initialised to 0 to ensure deterministic pickle (padding in Node struct)

memset(<void*>(self.nodes + self.capacity), 0, (capacity - self.capacity) * sizeof(Node))

# if capacity smaller than node_count, adjust the counter

if capacity < self.node_count:

self.node_count = capacity

self.capacity = capacity

return 0

cdef intp_t _add_node(self, intp_t parent, bint is_left, bint is_leaf,

intp_t feature, float64_t threshold, float64_t impurity,

intp_t n_node_samples,

float64_t weighted_n_node_samples,

uint8_t missing_go_to_left) except -1 nogil:

"""Add a node to the tree.

cdef intp_t node_id = self.node_count

if node_id >= self.capacity:

if self._resize_c() != 0:

return INTPTR_MAX

cdef Node* node = &self.nodes[node_id]

node.impurity = impurity

node.n_node_samples = n_node_samples

node.weighted_n_node_samples = weighted_n_node_samples

if parent != _TREE_UNDEFINED:

if is_left:

self.nodes[parent].left_child = node_id

else:

self.nodes[parent].right_child = node_id

if is_leaf:

node.left_child = _TREE_LEAF

node.right_child = _TREE_LEAF

node.feature = _TREE_UNDEFINED

node.threshold = _TREE_UNDEFINED

else:

# left_child and right_child will be set later

node.feature = feature

node.threshold = threshold

node.missing_go_to_left = missing_go_to_left

self.node_count += 1

return node_id

cpdef cnp.ndarray predict(self, object X):

"""Predict target for X."""

out = self._get_value_ndarray().take(self.apply(X), axis=0,

mode='clip')

if self.n_outputs == 1:

out = out.reshape(X.shape[0], self.max_n_classes)