Littérature sur l'algorithme de fractionnement optimal dans la croissance des arbres de classification

Dans ESL , Section 9.7, il y a un paragraphe indiquant que le temps de calcul d'une scission dans la croissance d'un arbre de classification (ou de régression) s'échelonne généralement comme où est le nombre de prédicteurs et est le nombre de échantillons.$p N \log N$$p$$N$

Une approche naïve se traduit par une mise à l'échelle , et je n'ai pas pu trouver de références à la littérature qui explique les détails de la partie de fractionnement de l'algorithme et comment on obtient une mise à l'échelle typique .$pN^2$ $p N \log N$

Dans l'approche naïve, la répartition optimale pour une variable donnée, après un ordre initial des valeurs observées, est recherchée parmi les points médians entre les valeurs observées, et le calcul de la perte pour chaque répartition peut être effectué dans un temps qui évolue comme .$N-1$$N$

Je pourrais (et étudierai probablement) le code source de certaines des implémentations que je connais, mais une référence bibliographique serait bien en particulier en ce qui concerne la complexité temporelle.$-$

Je donnerai une réponse différente, car c'est trop pour un commentaire et cela traite d'une approche plus générale.

Ainsi, en ESL, ils décrivent en effet le temps de calcul pour une branche-et-borne (plus précisément cela ressemble à une division et une conquête pour moi).

On note avec le nombre d'observations et avec le nombre de nœuds enfants, quand on fait pousser un arbre. Je suppose que nous ne perdons pas en général si nous considérons comme fixe. De plus, nous pouvons indiquer avec le temps de traitement pour calculer les points de partage à un nœud donné.$N$$K$$K$$f(N)$

Ainsi, nous pouvons écrire récursivement la formule du temps d'exécution comme: nous avons considéré ici que les nœuds enfants divisent l'ensemble de données d'entrée de taille en sous-ensembles de même taille . Nous savons que c'est le meilleur cas.

Cependant, nous pouvons voir qu'il s'agit d'une application bien connue du théorème maître. Ceci est bien documenté dans le livre CLRS . J'ai la 3ème édition et les détails sont à la section 4.5 et la preuve est à la section suivante. Je ne me souviens pas bien des détails, mais je me souviens que ce n'est pas trop compliqué si l'on élargit la récursivité et regroupe quelques termes ensemble.

Cependant, ce qui est important dans ce cas, c'est que lorsque - temps linéaire, le temps résultant de l'algorithme est . Ce temps est calculé pour une seule variable d'entrée, donc notre temps total pour les variables serait$f(N)=O(N)$$T(N) = O(N logN)$$P$$O(P N logN)$

Ce temps est réalisable pour la croissance des arbres, si toutes les entrées sont initialement triées en , et la recherche de la valeur de fractionnement prend un temps linéaire sur ces entrées triées. Ici, nous pouvons appliquer l'algorithme de variance en ligne, comme je l'ai mentionné dans ma réponse précédente pour . Pourest encore plus facile de trouver la médiane. J'avoue que je n'ai jamais essayé une autre fonction de perte pour les arbres.$O(P N logN)$$L_2 = \frac{1}{N}(y-\hat{y})^2$$L_1 = \frac{1}{N}|y-\hat{y}|$

Notez cependant que le théorème maître s'applique dans le meilleur des cas si les divisions sont de taille égale. Le pire des cas est celui où la division est très déséquilibrée. Là, on peut appliquer un cas différent de théorème maître et le temps deviendra .$O(P N^2)$

En conclusion, je suppose que les auteurs d'ESL utilisent généralement le terme d'une manière qui est utilisée pour décrire l'algorithme de tri rapide. Le tri rapide donne généralement , avec le pire des cas , pour certaines configurations de données spécifiques.$O(N logN)$$O(N^2)$

J'espère que ça aide.

Voir ma réponse d'une autre question ici . Bien que je n'ai pas de références papier, vous pouvez vous retrouver trivialement que pour entrées numériques de longueur vous devez:$p$$N$

• itérer sur toutes les entrées -$p$$O(p)$
• trier par ordre croissant de chaque entrée -$O(N log(N))$
• calculer 2 variances en cours d'exécution une à partir de la gauche et une à partir de la droite en temps linéaire -$O(N)$

Le temps dominant pour chaque attribut est le temps de tri, nous avons donc .$O(p N log(N))$