Details

Recursive partitioning is a tree-based method for classifying data. For data points in with labels , the recursive partitioning algorithm splits the data in one of the dimensions into two sets such that some node purity criterion is met. The simplest node purity criterion, called the Gini index, attempts to maximize the proportion of data points with one of the labels in each set. The partitioning algorithm is then run recursively on each set until nodes are totally pure in the sense that only one of the class labels is represented. Thus recursive partitioning splits the feature space into distinct regions. Each region is then given a label based on the represented class in that region.

Recursive partitioning is a fast and fairly accurate algorithm for classifying data. It works well for real-valued variables as well as for categorical variables. It also has the appealing property of being interpretable. For instance, consider a medical example, a model for predicting whether a patient has diabetes or not. The training data consists of height, weight, age, and so on and each case is labeled either "Diabetes" or "Not". The recursive partitioning algorithm would construct a rule that maps naturally to a medical professional's intuition: If the patient's age is greater than 50 and the patient's weight is greater than 180 pounds and the patient's height is less than 5' 5", then use the label "Diabetes", and so on.

T. Hastie, R. Tibshirani, and J. Friedman, The Elements of Statistical Learning: Data Mining, Inference, and Prediction, 2nd ed., New York: Springer, 2001.