Conditional Inference Trees and Forests for Python

citrees implements statistically principled decision trees and random forests using permutation-based hypothesis testing for variable selection. Unlike traditional CART-style trees that greedily optimize split criteria, citrees separates variable selection from split point selection using statistical tests to determine significance.

Note: citrees is inspired by the conditional inference framework (Hothorn et al., 2006) but is not a direct port of R's partykit::ctree. We implement the core principles—permutation-based variable selection and statistical stopping rules—while adding our own extensions like RDC selectors and feature muting. In particular, Stage A screening is designed to mitigate the classic high-cardinality selection bias mechanism of greedy impurity optimization (with the usual fixed-node/root scope caveats for adaptive trees).

Traditional decision trees (CART, ID3, C4.5) suffer from variable selection bias:

# From source
git clone https://github.com/rmill040/citrees.git
cd citrees
pip install -e .

# With uv (recommended)
uv sync

from citrees import (
    ConditionalInferenceTreeClassifier,
    ConditionalInferenceTreeRegressor,
    ConditionalInferenceForestClassifier,
    ConditionalInferenceForestRegressor,
    MaxValuesMethod,
)

# Classification
clf = ConditionalInferenceTreeClassifier(
    selector="mc",           # Multiple correlation for feature selection
    splitter="gini",         # Gini impurity for split quality
    alpha_selector=0.05,     # Significance level for feature selection
    alpha_splitter=0.05,     # Significance level for split selection
)
clf.fit(X_train, y_train)
predictions = clf.predict(X_test)

# Regression
reg = ConditionalInferenceTreeRegressor(
    selector="pc",           # Pearson correlation
    splitter="mse",          # Mean squared error
)
reg.fit(X_train, y_train)

# Forest ensemble (parallel training)
forest = ConditionalInferenceForestClassifier(
    n_estimators=100,
    max_features=MaxValuesMethod.SQRT,  # Random feature subset per split
    n_jobs=-1,                          # Use all cores
)
forest.fit(X_train, y_train)

# Feature importance (impurity decrease; subject to known caveats)
importances = forest.feature_importances_

At each node, features are tested for association with the target using permutation tests. Only statistically significant features (p < alpha) are considered for splitting.

• Bonferroni Correction: Controls family-wise error rate when testing multiple features
• Feature Muting: Automatically removes clearly uninformative features
• Honest Estimation: Optional sample splitting to reduce adaptive bias in leaf estimation (Wager & Athey, 2018)

The conditional inference algorithm (Hothorn et al., 2006) proceeds as follows:

Algorithm: Conditional Inference Tree
Input: Data (X, y), significance levels α_select, α_split

function BuildTree(X, y, depth):
    # Step 1: Test global null hypothesis
    for each feature j in {1, ..., p}:
        H₀: X_j ⊥ Y (feature j independent of target)
        p_j ← PermutationTest(X_j, y)

    # Apply Bonferroni correction
    α_adjusted ← α_select / p

    # Select feature with strongest association
    j* ← argmin(p_j)

    if p_j* ≥ α_adjusted:
        return LeafNode(y)  # No significant feature found

    # Step 2: Find optimal split point
    for each threshold c in X_j*:
        H₀: Split at c provides no improvement
        p_c ← PermutationTest(X_j*, y, c)

    c* ← argmin(p_c)

    if p_c* ≥ α_split:
        return LeafNode(y)  # No significant split found

    # Step 3: Recurse
    left ← {i : X_ij* ≤ c*}
    right ← {i : X_ij* > c*}

    return InternalNode(
        feature=j*, threshold=c*,
        left=BuildTree(X[left], y[left], depth+1),
        right=BuildTree(X[right], y[right], depth+1)
    )

Notes:

• sampling_method applies to classification forests only and is ignored when bootstrap_method=None.
• max_samples is only used when bootstrap_method is not None.
• bootstrap_method=None disables bootstrapping (and thus OOB).
• Forest classes default max_features=MaxValuesMethod.SQRT (trees default None).
• OOB scores are computed only for samples that receive at least one OOB prediction.

citrees excels in scenarios requiring:

• Unbiased feature selection for interpretability
• High-dimensional data where many features are noise
• Statistical rigor for scientific applications
• Causal inference with honest estimation

For pure prediction performance on tabular data, gradient boosting methods (XGBoost, LightGBM) typically achieve higher accuracy.

# Install with dev dependencies
uv sync

# Run tests
uv run pytest tests/ -v

# Run linters
uv run pre-commit run --all-files

@software{citrees,
  title = {citrees: Conditional Inference Trees and Forests for Python},
  author = {Milletich, Robert J.},
  year = {2024},
  url = {https://github.com/rmill040/citrees}
}

1. Hothorn, T., Hornik, K., & Zeileis, A. (2006). Unbiased Recursive Partitioning: A Conditional Inference Framework. Journal of Computational and Graphical Statistics, 15(3), 651-674.

2. Strobl, C., Boulesteix, A. L., Zeileis, A., & Hothorn, T. (2007). Bias in Random Forest Variable Importance Measures. BMC Bioinformatics, 8(1), 25.

3. Strobl, C., Boulesteix, A. L., Kneib, T., Augustin, T., & Zeileis, A. (2008). Conditional Variable Importance for Random Forests. BMC Bioinformatics, 9(1), 307.

4. Wager, S., & Athey, S. (2018). Estimation and Inference of Heterogeneous Treatment Effects using Random Forests. JASA, 113(523), 1228-1242.

5. Lopez-Paz, D., Hennig, P., & Schölkopf, B. (2013). The Randomized Dependence Coefficient. NeurIPS.

6. Székely, G. J., Rizzo, M. L., & Bakirov, N. K. (2007). Measuring and Testing Dependence by Correlation of Distances. Annals of Statistics, 35(6), 2769-2794.

MIT License - see LICENSE for details.