Breiman CART

---

Contact

Adam Khald - ad.khald@edu.umi.ac.ma

Project Link: https://github.com/Adamkhald/breiman-cart

Available on pypi: https://pypi.org/project/breiman-cart/

---

A pure Python implementation of Classification and Regression Trees (CART) following the original methodology from Breiman, Friedman, Olshen, and Stone (1984).

Why use this? Unlike sklearn's implementation, this provides a faithful reproduction of the original CART algorithm with full access to the tree-building process, cost-complexity pruning, and educational transparency.

---

What is CART?

CART (Classification and Regression Trees) is the decision tree algorithm introduced by Leo Breiman, Jerome Friedman, Richard Olshen, and Charles Stone in their 1984 book Classification and Regression Trees. It builds a predictive model by recursively partitioning the feature space into a binary tree of decision rules.

The core mechanics of the algorithm are:

• Recursive binary splitting. Starting from the full dataset at the root node, CART searches over every feature and every possible split point for that feature, and selects the single split that best separates the data according to an impurity criterion. Each resulting subset becomes a child node, and the process repeats recursively.
• Splitting criteria. For classification trees, the quality of a split is measured using Gini impurity, which quantifies how mixed the classes are within a node. For regression trees, the quality of a split is measured using mean squared error (MSE) of the target variable within each resulting subset.
• Binary splits only. Unlike algorithms such as ID3 or C4.5, which can produce multi-way splits, CART always partitions a node into exactly two children, regardless of whether the feature is continuous or categorical. For categorical features, this means CART evaluates possible groupings of categories into two subsets to find the binary partition that best reduces impurity, rather than treating each category as its own branch.
• Stopping criteria. Tree growth halts at a node when further splitting would violate constraints such as maximum depth, minimum samples required to split a node, or minimum samples required at a leaf.
• Cost-complexity pruning. A fully grown tree tends to overfit the training data. CART addresses this with cost-complexity pruning (also called weakest-link pruning): a complexity parameter (alpha) penalizes trees with more leaves, and the algorithm identifies the subtree that minimizes a combination of training error and tree size, typically selected via cross-validation on a held-out set.

This package reproduces that original formulation directly, rather than the modified/optimized variant used internally by scikit-learn, so that every step of the tree-building and pruning process remains inspectable.

How It Is Implemented

This implementation follows the original CART formulation in pure Python, organized around three main classes:

• BRCRegression and BRCClassification implement the tree-growing algorithm: at each node, every candidate feature and split point is evaluated against the relevant impurity criterion (MSE for regression, Gini impurity for classification), and the split that yields the greatest impurity reduction is chosen. Growth continues recursively, subject to max_depth, min_samples_split, and min_samples_leaf constraints, until no further valid split improves the objective or a stopping condition is reached.
• Categorical features are handled natively: instead of one-hot encoding, the algorithm searches over binary groupings of category values directly, in line with the original CART methodology, so categorical columns can be passed in as-is via the categorical_features argument.
• Cost-complexity pruning is implemented as a post-processing step (prune()) that walks the fully grown tree, computes the effective alpha for each candidate subtree, and either selects the optimal alpha automatically using a validation set or applies a user-specified alpha directly.
• Tree structure is represented as a recursive node structure, exposing structural queries such as depth, leaf count, and total node count directly on the fitted model, as well as export to a dictionary or JSON representation for external inspection.
• BRCInference wraps a trained model (or a model loaded from disk) to provide a stable, minimal interface for deployment: prediction, scoring, feature importance, and structural metadata, without exposing the training-time API surface.
• Feature importance is computed from the total impurity reduction attributable to each feature across all splits in the tree, normalized across features.
• The public API mirrors scikit-learn's fit / predict / score conventions so it can be used as a drop-in educational or diagnostic alternative in familiar workflows, while model persistence (save / load) and JSON export support production and inspection use cases respectively.

---

Features

• Original CART Algorithm - Faithful implementation of Breiman et al. (1984)
• Regression & Classification - Support for both continuous and categorical targets
• Categorical Features - Native handling of categorical variables without encoding
• Cost-Complexity Pruning - Automatic tree pruning to prevent overfitting
• Feature Importance - Built-in feature importance calculation
• Model Persistence - Easy save/load functionality
• Tree Inspection - Full access to tree structure and node information
• Sklearn Compatible - Familiar API for ML practitioners

---

Quick Start

Installation

pip install breiman-cart

Basic Usage

import breiman_cart as brc
import pandas as pd
import numpy as np

# Prepare your data
X = pd.DataFrame({
    'age': [25, 30, 35, 40, 45, 50, 55, 60],
    'income': [30000, 35000, 50000, 60000, 70000, 80000, 90000, 100000]
})
y = np.array([0, 0, 0, 1, 1, 1, 1, 1])

# Train a classifier
model = brc.BRCClassification(max_depth=5, min_samples_split=2)
model.fit(X, y)

# Make predictions
predictions = model.predict(X)
accuracy = model.score(X, y)
print(f"Accuracy: {accuracy:.2%}")

---

Complete Examples

Regression Example

import breiman_cart as brc
import pandas as pd
import numpy as np

# Create regression data
X_train = pd.DataFrame({
    'square_feet': [1200, 1500, 1800, 2000, 2200, 2500, 2800, 3000],
    'bedrooms': [2, 3, 3, 4, 4, 4, 5, 5],
    'age': [10, 8, 5, 3, 2, 1, 0, 0]
})
y_train = np.array([250000, 300000, 350000, 400000, 450000, 500000, 550000, 600000])

# Train model
model = brc.BRCRegression(
    max_depth=5,
    min_samples_split=2,
    min_samples_leaf=1,
    verbose=1  # Show training progress
)
model.fit(X_train, y_train)

# Make predictions
X_test = pd.DataFrame({
    'square_feet': [1600, 2400],
    'bedrooms': [3, 4],
    'age': [7, 2]
})
predictions = model.predict(X_test)
print(f"Predicted prices: ${predictions}")

# Get R² score
r2 = model.score(X_train, y_train)
print(f"R² Score: {r2:.3f}")

# Feature importance
importance = model.get_feature_importance()
for feature, score in zip(X_train.columns, importance):
    print(f"{feature}: {score:.3f}")

Classification Example

import breiman_cart as brc
import pandas as pd
import numpy as np

# Create classification data
X_train = pd.DataFrame({
    'temperature': [30, 25, 20, 15, 10, 5, 0, -5],
    'humidity': [80, 75, 70, 65, 60, 55, 50, 45],
    'wind_speed': [5, 10, 15, 20, 25, 30, 35, 40]
})
y_train = np.array([1, 1, 1, 0, 0, 0, 0, 0])  # 1=Rain, 0=No Rain

# Train classifier
clf = brc.BRCClassification(
    max_depth=3,
    min_samples_split=2,
    min_samples_leaf=1
)
clf.fit(X_train, y_train)

# Predictions
X_test = pd.DataFrame({
    'temperature': [22, 8],
    'humidity': [72, 58],
    'wind_speed': [12, 28]
})
predictions = clf.predict(X_test)
print(f"Predictions: {predictions}")  # [1, 0]

# Accuracy
accuracy = clf.score(X_train, y_train)
print(f"Accuracy: {accuracy:.2%}")

Inference Engine

Use the inference engine for production deployments:

import breiman_cart as brc

# Option 1: From trained model
model = brc.BRCRegression(max_depth=5)
model.fit(X_train, y_train)

inference = brc.BRCInference(model)

# Option 2: Load from saved file
inference = brc.BRCInference('my_model.pkl')

# Make predictions
predictions = inference.predict(X_new)

# Get model information
info = inference.get_model_info()
print(f"Model type: {info['model_type']}")
print(f"Tree depth: {info['tree_depth']}")
print(f"Number of leaves: {info['n_leaves']}")

# Feature importance (as dictionary)
importance = inference.get_feature_importance()
print(importance)  # {'feature1': 0.65, 'feature2': 0.35}

# Pretty print
print(inference)

---

Advanced Features

Cost-Complexity Pruning

Prevent overfitting with automatic pruning:

# Train a full tree
model = brc.BRCRegression(max_depth=10)
model.fit(X_train, y_train)

# Prune using validation set
# (automatically finds optimal alpha)
model.prune(X_val, y_val)

# Or specify alpha manually
model.prune(X_val, y_val, alpha=0.01)

Categorical Features

Native support for categorical variables:

X = pd.DataFrame({
    'color': ['red', 'blue', 'red', 'green', 'blue', 'green'],
    'size': ['S', 'M', 'L', 'M', 'S', 'L'],
    'price': [10, 20, 15, 25, 12, 30]
})
y = np.array([0, 1, 0, 1, 0, 1])

# Specify categorical features
model = brc.BRCClassification(
    max_depth=5,
    categorical_features=['color', 'size']  # These won't be treated as numerical
)
model.fit(X, y)

Model Persistence

Save and load models:

# Save model
model.save('my_cart_model.pkl')

# Load model later
loaded_model = brc.BRCRegression.load('my_cart_model.pkl')

# Or use with inference
inference = brc.BRCInference('my_cart_model.pkl')

Tree Inspection

Explore the tree structure:

# Get tree statistics
print(f"Tree depth: {model.root.get_depth()}")
print(f"Number of leaves: {model.root.count_leaves()}")
print(f"Total nodes: {model.root.get_n_nodes()}")

# Export tree structure
tree_dict = model.to_dict()

# Save as JSON
model.to_json('tree_structure.json')

---

API Reference

BRCRegression

Decision tree regressor using MSE criterion.

brc.BRCRegression(
    max_depth=None,           # Maximum tree depth
    min_samples_split=2,      # Min samples to split node
    min_samples_leaf=1,       # Min samples at leaf
    categorical_features=[],  # List of categorical feature names
    verbose=0                 # Verbosity level (0, 1, or 2)
)

Methods:

• fit(X, y) - Train the model
• predict(X) - Make predictions
• score(X, y) - Calculate R² score
• get_feature_importance() - Get feature importances
• prune(X_val, y_val, alpha=None) - Prune the tree
• save(filepath) - Save model to disk
• load(filepath) - Load model from disk (static method)

BRCClassification

Decision tree classifier using Gini impurity criterion.

brc.BRCClassification(
    max_depth=None,
    min_samples_split=2,
    min_samples_leaf=1,
    categorical_features=[],
    verbose=0
)

Methods: Same as BRCRegression, but score() returns accuracy.

BRCInference

Inference engine for making predictions with trained models.

brc.BRCInference(model)  # Pass trained model or file path

Methods:

• predict(X) - Make predictions
• score(X, y) - Evaluate performance
• get_feature_importance() - Get feature importance dict
• get_tree_depth() - Get tree depth
• get_n_leaves() - Get number of leaves
• get_n_nodes() - Get total nodes
• get_model_info() - Get comprehensive model info
• save_model(filepath) - Save model
• export_to_json(filepath) - Export tree as JSON

---

Comparison with Sklearn

Feature	breiman-cart	sklearn DecisionTree
CART Algorithm	Original (1984)	Modified
Cost-Complexity Pruning	Automatic	Manual (ccp_alpha)
Categorical Features	Native	Requires encoding
Tree Inspection	Full access	Limited
Educational Value	High	Medium
Performance	Good	Excellent (C++)
Interpretability	Excellent	Good

Use breiman-cart when:

• You want the original CART algorithm
• You need educational transparency
• You're working with categorical features
• You want easy tree inspection
• You need cost-complexity pruning

Use sklearn when:

• Performance is critical
• You need integration with sklearn pipelines
• You're working with very large datasets

---

Testing

Run the test suite:

# test_example.py
import breiman_cart as brc
import pandas as pd
import numpy as np

# Test regression
X = pd.DataFrame({'x1': [1, 2, 3, 4, 5], 'x2': [2, 4, 6, 8, 10]})
y = np.array([3, 6, 9, 12, 15])

reg = brc.BRCRegression(max_depth=5)
reg.fit(X, y)
assert reg.score(X, y) > 0.9, "Regression test failed"

# Test classification
y_class = np.array([0, 0, 1, 1, 1])
clf = brc.BRCClassification(max_depth=3)
clf.fit(X, y_class)
assert clf.score(X, y_class) >= 0.8, "Classification test failed"

# Test inference
inference = brc.BRCInference(reg)
preds = inference.predict(X)
assert len(preds) == len(X), "Inference test failed"

print("All tests passed!")

---

Background

This implementation follows the seminal work:

Breiman, L., Friedman, J., Olshen, R., & Stone, C. (1984). Classification and Regression Trees. Wadsworth International Group.

CART is a decision tree algorithm that:

1. Recursively partitions the feature space into rectangular regions
2. Uses Gini impurity (classification) or MSE (regression) for splitting
3. Employs binary splits only (unlike ID3/C4.5)
4. Prunes using cost-complexity to find the optimal subtree

---

Contributing

Contributions are welcome! Please feel free to submit a Pull Request.

1. Fork the repository
2. Create your feature branch (git checkout -b feature/amazing-feature)
3. Commit your changes (git commit -m 'Add amazing feature')
4. Push to the branch (git push origin feature/amazing-feature)
5. Open a Pull Request

---

License

This project is licensed under the MIT License - see the LICENSE file for details.

---

Acknowledgments

• Leo Breiman and colleagues for the original CART algorithm
• The scikit-learn team for API inspiration
• The Python data science community

---

Changelog

Version 0.2.0 (Current)

• NEW: Clean sklearn-compatible API with BRCRegression, BRCClassification, BRCInference
• NEW: BRCInference class for production deployments
• Improved user experience with intuitive class names
• Comprehensive documentation and examples
• Better error messages and validation
• Feature importance as named dictionary in BRCInference

Version 0.1.1

• Added comprehensive input validation
• Improved performance for categorical features
• Added model save/load functionality
• Enhanced pruning algorithm efficiency

Version 0.1.0

• Initial release
• Basic CART implementation
• Cost-complexity pruning
• Categorical feature support

---

Made by Adam Khald