ternary-trees

Decision trees and random forests for ternary classification on {-1, 0, +1} — ternary splits, ternary entropy, feature importance, pruning, and Gini impurity.

Why This Exists

Standard decision trees split binary thresholds on continuous features. When both your features and labels are inherently ternary — three-level signals, tri-state sensors, approve/abstain/reject decisions — you need a tree that natively handles three-way splits. This crate implements decision trees with ternary branching (less than / equal to / greater than), random forests with bootstrap aggregation and ternary majority voting, plus information-theoretic metrics (ternary entropy, Gini impurity, information gain) designed for the three-class setting. forbid(unsafe_code) throughout.

Core Concepts

• Ternary splits: Internal nodes split on feature < threshold / feature == threshold / feature > threshold, producing three children.
• Ternary entropy: Shannon entropy over three classes, used for information-gain-based splitting.
• TernaryDecisionTree: Build with fit(samples), predict with predict(features). Supports max_depth and min_samples hyperparameters.
• Pruning: Post-hoc pruning against a validation set — converts internal nodes to leaves when it doesn't hurt accuracy.
• RandomForest: Ensemble of TernaryDecisionTree instances with bootstrap sampling, ternary majority voting, and permutation-based feature importance.
• Gini impurity: Complement of squared class probabilities, a purity measure for ternary labels.

Quick Start

# Cargo.toml
[dependencies]
ternary-trees = "0.1"

use ternary_trees::{
    Ternary, TernaryDecisionTree, RandomForest,
    Sample, ternary_entropy, gini_impurity, information_gain,
};

fn main() {
    // Training data: features are i8, labels are Ternary
    let samples: Vec<Sample> = vec![
        (vec![-1, -1], Ternary::Neg),
        (vec![-1,  0], Ternary::Neg),
        (vec![ 1,  1], Ternary::Pos),
        (vec![ 1,  0], Ternary::Pos),
        (vec![ 0,  0], Ternary::Zero),
        (vec![ 0,  0], Ternary::Zero),
    ];

    // Decision tree
    let mut tree = TernaryDecisionTree::new(5, 1);
    tree.fit(&samples);
    assert_eq!(tree.predict(&[-1, -1]), Some(Ternary::Neg));
    assert_eq!(tree.predict(&[1, 1]), Some(Ternary::Pos));

    // Random forest with feature importance
    let mut rf = RandomForest::new(5, 5, 1, 2);
    rf.fit(&samples);
    let prediction = rf.predict(&[-1, -1]);
    let importance = rf.feature_importance(&samples, 2);
    println!("Feature importance: {:?}", importance);

    // Information-theoretic metrics
    let h = ternary_entropy([10, 10, 10]); // log₂(3) ≈ 1.585
    let gini = gini_impurity(&samples);
}

API Overview

How It Works

TernaryDecisionTree::fit recursively splits the training set. At each node, it evaluates all features at thresholds -1 and 0, computing the information gain (parent entropy minus weighted child entropy) of each three-way split. The best split becomes the node's decision rule. Splitting stops when purity reaches 95%, max_depth is exceeded, or too few samples remain.

RandomForest creates n_trees decision trees, each trained on a bootstrap sample (sampling with replacement). Prediction is by majority vote across trees. Feature importance permutes each feature and measures the accuracy drop.

Pruning is bottom-up: for each internal node, it compares validation accuracy of the subtree vs. a single leaf. If the leaf does no worse, the subtree is replaced.

Use Cases

• Tri-state sensor classification: Classify sensor readings that are naturally {-1, 0, +1} (e.g., magnetometer polarity, ternary logic outputs).
• Sentiment classification: Use ternary-labeled features (word sentiment scores) to predict document sentiment.
• Decision support systems: Build interpretable models where features and outcomes are approve/abstain/reject.
• Quality control: Ternary pass/marginal/fail classification from multi-feature inspections.

Ecosystem

Part of the SuperInstance ternary computing suite:

• ternary-lattice — lattice structures for ternary values
• ternary-codes — error-correcting codes for ternary data
• ternary-gradient — gradient-free optimization on ternary landscapes
• ternary-language — ternary NLP and grammar processing
• ternary-trees — this crate
• ternary-transform — wavelet, Fourier, and kernel transforms
• ternary-planning — planning and scheduling with ternary priorities
• ternary-rl — reinforcement learning with ternary actions
• ternary-som — self-organizing maps for ternary data
• ternary-failure — failure analysis with ternary classification

License

MIT