Statistics Glossary → Tree pruning and the complexity parameter (cp)
Tree pruning and the complexity parameter (cp)concept
The process of turning an overgrown decision tree into a simpler, more generalizable one by removing branches that do not add enough to predictive performance; cp sets how far this simplification goes.
A decision tree grows by splitting the data into ever purer subgroups and can eventually branch so far that it memorizes even the noise in the training data. In the cost-complexity pruning of the CART method, a penalty proportional to the number of leaves is added to the tree's error. The complexity parameter cp sets the minimum reduction in relative error a split must achieve to be kept: splits that do not reduce the error by at least cp are pruned. The larger cp, the smaller the tree; cp = 0 gives the largest tree.
A suitable cp is usually chosen by cross-validation: the cross-validated error (xerror) and its standard error (xstd) are computed for each cp value. The cp with the smallest xerror can be chosen, or, with the 1-SE rule, the smallest tree whose error is within one standard error of the minimum. Pruning differs from early-stopping rules that restrict growth from the outset (minimum node size, maximum depth): the tree is grown first and then cut back, which avoids losing branches that look weak at first but make later splits valuable.
An everyday example
A gardener pruning a fruit tree cuts away thin branches that bear little fruit but drain the tree's energy. In a decision tree, likewise, branches that separate only a handful of observations and are of no use on new data are cut. A 40-leaf tree might classify 95% of the training data correctly but only 70% of new data, whereas a pruned 8-leaf tree might reach 78% on new data.
In MerQur
It is controlled in the Decision Tree (CART) by the 'Complexity parameter (cp)' and 'Pruning (Given cp / Minimum CV error / 1-SE rule)' parameters; the CV-based options require xval >= 2.