CART (Classification and Regression Trees) › CART (Classification and Regression Trees)

CART, or Classification and Regression Trees, represents one of the most intuitive and interpretable machine learning algorithms. CART builds decision trees by recursively partitioning the feature space into regions that best separate the target variable. Think of it as creating a flowchart where each decision point asks a simple yes/no question about a feature, ultimately leading to a prediction.

CART's simplicity and transparency make it particularly useful in regulated domains such as healthcare and finance. Unlike black-box algorithms, every decision made by a CART model can be traced back to specific feature thresholds and logical rules. The algorithm works by finding the optimal splits that minimize impurity (for classification) or variance (for regression) at each node.

CART differs from other tree-based methods in several key ways. Unlike ensemble methods like Random Forest or Gradient Boosting that we will cover later, CART builds a single tree without any randomization or boosting mechanisms. It also uses a greedy approach, making the locally optimal split at each node without considering the global impact on the final tree structure. This can sometimes lead to suboptimal trees, but it makes the algorithm computationally efficient and easy to understand.

The algorithm's recursive nature means it continues splitting until it reaches a stopping criterion, such as maximum depth, minimum samples per leaf, or when no further improvement can be made. This process creates a hierarchical structure where each path from root to leaf represents a unique decision rule that can be easily translated into human-readable if-then statements.

CART models offer exceptional interpretability that sets them apart from many other algorithms. Unlike neural networks or ensemble methods, every prediction can be traced through a clear sequence of if-then rules. This makes CART particularly valuable in regulated industries like healthcare and finance, where model decisions must be explainable to reviewers and end users. A doctor can follow the tree path to understand why a patient was classified as high-risk, making CART well-suited for clinical decision support systems.

The algorithm handles several common problems in real-world data. It can work with mixed data types and accommodate missing values or outliers without extensive preprocessing. The algorithm's use of surrogate splits means that even when primary features are missing, alternative decision paths can still give reasonable predictions. This flexibility makes CART particularly useful for exploratory data analysis and rapid prototyping scenarios where data quality may be uncertain.

CART naturally captures complex interactions between features without requiring manual feature engineering, effectively performing automatic feature engineering during the tree-building process. The algorithm can discover non-obvious relationships, such as "if age > 65 AND income < 30k AND has_diabetes = true, then high_risk = true." These discovered patterns often provide valuable business insights beyond just predictions, making CART useful for both modeling and data exploration purposes.

Training and prediction with CART are computationally efficient. The greedy splitting approach, while sometimes suboptimal, ensures that training time scales reasonably with data size. This efficiency makes CART well-suited for embedded systems, mobile applications, and scenarios requiring low-latency predictions where computational resources are constrained.

CART models exhibit high variance, meaning small changes in training data can produce substantially different trees. This instability stems from the algorithm's sensitivity to data variations and its tendency to overfit. A single outlier or mislabeled sample can significantly alter the tree structure, which can be problematic for applications where consistency is important. This high variance also means that cross-validation results can vary between runs, making it challenging to obtain stable performance estimates.

The algorithm struggles with simple linear relationships that other algorithms handle effortlessly. While a linear regression can capture a relationship like "price = 2 × size + 100" with a single equation, CART might need dozens of splits to approximate the same relationship. This inefficiency makes CART suboptimal for problems where linear relationships dominate, such as many economic and physical modeling scenarios where the underlying relationships are inherently linear.

The algorithm exhibits a strong bias toward features with high cardinality or many unique values. Categorical features with many categories (like ZIP codes or product IDs) and continuous features with many distinct values get unfairly favored during split selection. This bias can lead to trees that perform well on training data but generalize poorly, as they may be overfitting to spurious patterns in high-cardinality features rather than learning meaningful relationships.

While CART can capture interactions, it's constrained by its axis-parallel splits, limiting its expressiveness for complex geometric patterns. It cannot efficiently represent certain geometric patterns, such as diagonal decision boundaries or circular regions, that might be natural for the underlying data. This limitation becomes particularly problematic in high-dimensional spaces where the curse of dimensionality makes axis-parallel splits increasingly ineffective at capturing the true data structure.