odtlearn.flow_oct

Classes

FlowOCT	An optimal decision tree classifier, fitted on a given integer-valued data set
BendersOCT	An optimal decision tree classifier using Benders' decomposition, fitted on a given integer-valued

Module Contents

class odtlearn.flow_oct.FlowOCT(solver: str, _lambda: float = 0.0, obj_mode: str = 'acc', depth: int = 1, time_limit: int = 60, num_threads: None | int = None, verbose: bool = False)

Bases: odtlearn.flow_oct_ss.FlowOCTSingleSink

An optimal decision tree classifier, fitted on a given integer-valued data set to produce a provably optimal decision tree.

Parameters:

solverstr

The solver to use for the MIP formulation. Currently, only “gurobi” and “CBC” are supported.

_lambdafloat, default=0

The regularization parameter for controlling the complexity of the learned tree.

obj_mode{‘acc’, ‘balance’, ‘weighted’}, optional (default=’acc’)

The objective mode to use. ‘acc’ for accuracy, ‘balance’ for balanced accuracy, ‘weighted’ for user-defined weights.

depthint, default=1

The maximum depth of the tree to be learned.

time_limitint, default=60

The time limit (in seconds) for solving the MIP formulation.

num_threadsint, default=None

The number of threads the solver should use. If not specified, solver uses all available threads

verbosebool, default=False

Whether to print verbose output during the tree learning process.

Notes

This class extends the FlowOCTSingleSink class and provides the implementation for learning optimal classification trees using the flow-based formulation with a single sink node.

The FlowOCT class is a user-facing class that can be instantiated directly to learn optimal classification trees. It inherits the basic structure and functionality from the FlowOCTSingleSink class and adds the specific objective function and model fitting process.

The class supports three objective modes: “acc” (accuracy), “balance”, and “weighted”. The accuracy objective aims to maximize the prediction accuracy of the learned tree, the balance objective aims to learn a balanced optimal decision tree to better generalize to out-of-sample data, and the weighted objective allows users to pass their own weights.

The The fit method method is used to fit the optimal classification tree to the given training data. It preprocesses the input data, creates the main optimization problem, and solves it using the specified solver and parameters.

The predict method is used to make predictions using the fitted optimal classification tree. It takes the input data and traverses the tree based on the learned branching and prediction decisions to generate the predictions.

The _define_objective method defines the objective function for the optimization problem based on the selected objective mode. It incorporates the regularization term and the accuracy or balance objective term.

Users can instantiate the FlowOCT class directly and use it to learn optimal classification trees by calling the fit method with the training data and then using the predict method to make predictions on new data.

Methods

fit(X, y)	Fit the optimal classification tree to the given training data.
predict(X)	Make predictions using the fitted optimal classification tree.
_define_objective()	Define the objective function for the optimization problem.

fit(X: numpy.ndarray | pandas.core.frame.DataFrame, y: numpy.ndarray | pandas.core.series.Series, weights: pandas.core.series.Series | numpy.ndarray | None = None) → FlowOCT

Fit the FlowOCT model to the given training data.

Parameters:

Xarray-like of shape (n_samples, n_features)

The training input samples. Each feature should be binary (0 or 1).

yarray-like of shape (n_samples,)

The target values (class labels) for the training samples.

weightsarray-like of shape (n_samples,), optional (default=None)

Sample weights. If None, then samples are equally weighted when obj_mode is ‘acc’, or weights are automatically calculated when obj_mode is ‘balance’. Must be provided when obj_mode is ‘weighted’.

Returns:

selfobject

Returns self.

Raises:

ValueError

If X contains non-binary values, or if X and y have inconsistent numbers of samples. Also raised if weights are not provided when obj_mode is ‘weighted’, or if the number of weights doesn’t match the number of samples.

Notes

The behavior of this method depends on the obj_mode specified during initialization: - If obj_mode is ‘acc’, equal weights are used (weights parameter is ignored). - If obj_mode is ‘balance’, weights are automatically calculated to balance class importance. - If obj_mode is ‘weighted’, the provided weights are used.

When obj_mode is not ‘weighted’ and weights are provided, a warning is issued and the weights are ignored.

This method fits the FlowOCT model using mixed-integer optimization. It sets up the optimization problem, solves it, and stores the results.

predict(X: pandas.core.frame.DataFrame | numpy.ndarray) → numpy.ndarray

Predict class labels for samples in X using the fitted FlowOCT model.

Parameters:

Xarray-like of shape (n_samples, n_features)

The input samples for which to make predictions. The features should match those used during the fit method.

Returns:

y_predndarray of shape (n_samples,)

The predicted class labels for each sample in X.

Raises:

NotFittedError

If the model has not been fitted yet.

ValueError

If the input X has a different number of features than the training data.

Notes

This method uses the decision tree learned during the fit process to classify new samples. It traverses the tree for each sample in X, following the branching decisions until reaching a leaf node, and returns the corresponding class prediction.

The input X should have the same feature set as the training data used in fit(). If categorical variables were one-hot encoded for training, the same encoding should be applied to X before calling predict().

Examples

>>> from odtlearn.flow_oct import FlowOCT
>>> import numpy as np
>>> X_train = np.array([[0, 0], [1, 1], [1, 0], [0, 1]])
>>> y_train = np.array([0, 1, 1, 0])
>>> clf = FlowOCT(depth=2)
>>> clf.fit(X_train, y_train)
>>> X_test = np.array([[1, 1], [0, 0]])
>>> y_pred = clf.predict(X_test)
>>> print(y_pred)
[1 0]

class odtlearn.flow_oct.BendersOCT(solver: str, _lambda: float = 0.0, obj_mode: str = 'acc', depth: int = 1, time_limit: int = 60, num_threads: None | int = None, verbose: bool = False)

Bases: odtlearn.flow_oct_ss.FlowOCTSingleSink

An optimal decision tree classifier using Benders’ decomposition, fitted on a given integer-valued data set to produce a provably optimal decision tree.

Parameters:

solverstr

The solver to use for the MIP formulation. Currently, only “gurobi” and “CBC” are supported.

_lambdafloat, default=0

The regularization parameter for controlling the complexity of the learned tree.

obj_mode{‘acc’, ‘balance’, ‘weighted’}, optional (default=’acc’)

The objective mode to use. ‘acc’ for accuracy, ‘balance’ for balanced accuracy, ‘weighted’ for user-defined weights.

depthint, default=1

The maximum depth of the tree to be learned.

time_limitint, default=60

The time limit (in seconds) for solving the MIP formulation.

num_threadsint, default=None

The number of threads the solver should use. If not specified, solver uses all available threads

verbosebool, default=False

Whether to print verbose output during the tree learning process.

Notes

This class extends the FlowOCTSingleSink class and provides the implementation for learning optimal classification trees using Benders’ decomposition with a single sink node.

The BendersOCT class is a user-facing class that can be instantiated directly to learn optimal classification trees using Benders’ decomposition. It inherits the basic structure and functionality from the FlowOCTSingleSink class and adds the specific Benders’ decomposition formulation.

Benders’ decomposition is a technique used to solve large-scale optimization problems by decomposing them into smaller subproblems. In the context of optimal classification trees, Benders’ decomposition is used to decompose the problem into a master problem and multiple subproblems, one for each datapoint.

The master problem focuses on the tree structure and branching decisions, while the subproblems optimize the class predictions for each datapoint based on the fixed tree structure. The master problem and subproblems are solved iteratively until convergence is reached.

The _define_variables method defines the decision variables specific to the Benders’ decomposition formulation, including the variables for the subproblem objective values.

The _define_constraints method defines the constraints specific to the Benders’ decomposition formulation, which ensure the proper linking of the master problem and subproblems.

The _define_objective method defines the objective function for the Benders’ decomposition formulation, which includes the regularization term and the objective values from the subproblems.

The fit method is used to fit the optimal classification tree using Benders’ decomposition to the given training data. It preprocesses the input data, creates the main optimization problem, and solves it using the specified solver and parameters.

The predict method is used to make predictions using the fitted optimal classification tree. It takes the input data and traverses the tree based on the learned branching and prediction decisions to generate the predictions.

Users can instantiate the BendersOCT class directly and use it to learn optimal classification trees using Benders’ decomposition by calling the fit method with the training data and then using the predict method to make predictions on new data.

Methods

fit(X, y)	Fit the optimal classification tree using Benders’ decomposition to the given training data.
predict(X)	Make predictions using the fitted optimal classification tree.
_define_variables()	Define the decision variables used in the Benders’ decomposition formulation.
_define_constraints()	Define the constraints used in the Benders’ decomposition formulation.
_define_objective()	Define the objective function for the Benders’ decomposition formulation.

fit(X: numpy.ndarray | pandas.core.frame.DataFrame, y: numpy.ndarray | pandas.core.series.Series, weights: pandas.core.series.Series | numpy.ndarray | None = None) → BendersOCT

Fit the BendersOCT model to the given training data.

Parameters:

Xarray-like of shape (n_samples, n_features)

The training input samples. Each feature should be binary (0 or 1).

yarray-like of shape (n_samples,)

The target values (class labels) for the training samples.

weightsarray-like of shape (n_samples,), optional (default=None)

Sample weights. If None, then samples are equally weighted when obj_mode is ‘acc’, or weights are automatically calculated when obj_mode is ‘balance’. Must be provided when obj_mode is ‘weighted’.

Returns:

selfobject

Returns self.

Raises:

ValueError

If X contains non-binary values, or if X and y have inconsistent numbers of samples. Also raised if weights are not provided when obj_mode is ‘weighted’, or if the number of weights doesn’t match the number of samples.

Notes

The behavior of this method depends on the obj_mode specified during initialization: - If obj_mode is ‘acc’, equal weights are used (weights parameter is ignored). - If obj_mode is ‘balance’, weights are automatically calculated to balance class importance. - If obj_mode is ‘weighted’, the provided weights are used.

When obj_mode is not ‘weighted’ and weights are provided, a warning is issued and the weights are ignored.

This method fits the BendersOCT model using Benders’ decomposition approach. It sets up the master problem and subproblems, iteratively solves them, and generates Benders’ cuts until convergence or the time limit is reached.

The BendersOCT algorithm generally provides faster solution times compared to standard MIO formulations, especially for larger problem instances.

Examples

>>> from odtlearn.flow_oct import BendersOCT
>>> import numpy as np
>>> X = np.array([[0, 0], [1, 1], [1, 0], [0, 1]])
>>> y = np.array([0, 1, 1, 0])
>>> clf = BendersOCT(depth=2, time_limit=60)
>>> clf.fit(X, y)

predict(X: pandas.core.frame.DataFrame | numpy.ndarray) → numpy.ndarray[Any, Any]

Predict class labels for samples in X using the fitted BendersOCT model.

Parameters:

Xarray-like of shape (n_samples, n_features)

The input samples for which to make predictions. The features should match those used during the fit method.

Returns:

y_predndarray of shape (n_samples,)

The predicted class labels for each sample in X.

Raises:

NotFittedError

If the model has not been fitted yet.

ValueError

If the input X has a different number of features than the training data.

Notes

This method uses the decision tree learned during the fit process to classify new samples. It traverses the tree for each sample in X, following the branching decisions until reaching a leaf node, and returns the corresponding class prediction.

The input X should have the same feature set as the training data used in fit(). If categorical variables were one-hot encoded for training, the same encoding should be applied to X before calling predict().

Examples

>>> from odtlearn.flow_oct import BendersOCT
>>> import numpy as np
>>> X_train = np.array([[0, 0], [1, 1], [1, 0], [0, 1]])
>>> y_train = np.array([0, 1, 1, 0])
>>> clf = BendersOCT(depth=2)
>>> clf.fit(X_train, y_train)
>>> X_test = np.array([[1, 1], [0, 0]])
>>> y_pred = clf.predict(X_test)
>>> print(y_pred)
[1 0]