The most popular method to construct Classification Trees from a training dataset is CART, introduced by Brieman et. al [1]}. CART is a greedy heuristic approach, which myopically constructs the tree without further foreseen to deeper nodes. Starting at the root node, it decides the splits by means of hyperplanes minimizing an impurity function in each node. Each split results in two new nodes, and this procedure is repeated until a stopping criterion is reached (maximal depth, minimum number of observations in the same class, etc). CART produces deep trees, which may lead to overfitting in out-of-sample observations. Also, trees are normally subject to a prune process based on the trade-off between the impurity function reduction and a cost-complexity parameter. The main advantage of CART is that it is easy to implement and fast to train.
