CART Algorithm

CART, short for classification and regression trees, is an algorithm for building a decision tree that can predict either a category, as a classification tree, or a numeric value, as a regression tree, from a set of input features. It works top down, starting with the whole dataset at the root and repeatedly splitting it into smaller and smaller subsets, choosing at each step the split that best separates the data according to a fitness measure, commonly a measure like Gini impurity for classification or variance reduction for regression, and continuing until the resulting groups are reasonably pure or further splitting stops helping. Leo Breiman and his coauthors introduced the method in their 1984 book Classification and Regression Trees, and the term has since come to serve as a general label covering both the classification and regression variants of the same underlying tree-building procedure. CART's basic splitting and pruning logic also underlies later, more powerful ensemble methods that combine many individual trees.