Université Paris 6
Pierre et Marie Curie
Université Paris 7
Denis Diderot

CNRS U.M.R. 7599
``Probabilités et Modèles Aléatoires''

Oracle bounds and exact algorithm for dyadic classification trees


Code(s) de Classification MSC:

Résumé: This paper introduces a new method using dyadic decision trees for estimating a classification or a regression function in a multiclass classification problem. The estimator is based on model selection by penalized empirical loss minimization. Our work consists in two complementary parts: first, a theoretical analysis of the method leads to deriving oracle-type inequalities for three different possible loss functions. Secondly, we present an algorithm able to compute the estimator in an exact way.

Mots Clés: Supervised Classification ; Dyadic Tree ; Multi-class Classification ; Misclassification Error Bounds

Date: 2004-03-05

Prépublication numéro: PMA-889