Profondeur d'un arbre de décision

l'erreur d'apprentissage descend toujours ; l'erreur de test, elle, finit par remonter

1 · CRITÈRE DE COUPURE (CART, GINI)

$$G(t)=1-\sum_{k}\hat p_k(t)^2,\qquad (j^\star,s^\star)=\arg\max_{j,s}\ \Big[G(t)-\frac{n_L}{n_t}G(t_L)-\frac{n_R}{n_t}G(t_R)\Big]$$

\(t_L=\{x\in t:\ x_j\le s\}\), \(t_R=\{x\in t:\ x_j\gt s\}\) ; on coupe tant qu'un nœud n'est pas pur. L'arbre de profondeur \(D\) est l'arbre complet lu jusqu'au niveau \(D\).

$$\widehat{\mathrm{err}}_{\text{app}}(D)=\frac1n\sum_{i=1}^{n}\mathbf 1\{\hat f_D(x_i)\neq y_i\},\qquad \widehat{\mathrm{err}}_{\text{test}}(D)=\frac1{m}\sum_{i=1}^{m}\mathbf 1\{\hat f_D(x'_i)\neq y'_i\}$$

2 · À TOI : FAIS VARIER LA PROFONDEUR D

données et régions de l'arbre de profondeur \(D\) ; trait vert : frontière de Bayes
erreurs en fonction de la profondeur : glisse pour changer \(D\)

Deux gaussiennes bivariées de covariances différentes, probabilités a priori égales : la frontière de Bayes est une conique, que l'arbre approche par des marches d'escalier parallèles aux axes. Test : \(m=4000\) nouveaux points de la même loi. Points cerclés de noir : points d'apprentissage mal classés.

3 · RAPPELS