Risk bounds for CART classifiers under a margin condition

Non-asymptotic risk bounds for Classification And Regression Trees (CART) classifiers are obtained in the binary supervised classification framework under a margin assumption on the joint distribution of the covariates and the labels. These risk bounds are derived conditionally on the construction of the maximal binary tree and allow to prove that the linear penalty used in the CART pruning algorithm is valid under the margin condition.It is also shown that, conditionally on the construction of the maximal tree, the final selection by test sample does not alter dramatically the estimation accuracy of the Bayes classifier.

► Analysis of the CART pruning algorithm in the binary classification context.
► Margin assumptions are made on the data distribution to improve results on CART classifiers.
► CART pruning algorithm provides classifiers performant in terms of risk under a margin condition.