Fiche de révision : KPPV et arbres de décision

Plan du Cours

  1. Principe et fonctionnement du KPPV
  2. Distances et choix des paramètres
  3. Coût et mise en œuvre du KPPV
  4. Principes des arbres de décision
  5. Construction et critères de découpe
  6. Arbres de décision en régression
  7. Interpréter et limiter les arbres
  8. Bagging et échantillonnage bootstrap
  9. Fonctionnement des forêts aléatoires
  10. Évaluer et comparer les ensembles
  11. Choisir un modèle selon le problème

1. Principe et fonctionnement du KPPV

Notions clés & Définitions

  • KPPV : Attribue à un nouvel objet la classe majoritaire parmi ses k voisins les plus proches dans les données d’entraînement.

★ À maîtriser

  • Pour classer un objet, le KPPV calcule sa distance à chaque exemple d’entraînement, sélectionne les k exemples les plus proches, puis attribue la classe majoritaire de ces voisins.

Compléments

  • Le KPPV est un apprentissage paresseux qui mémorise les données d’entraînement sans apprendre de modèle avant la prédiction.

  • En régression, le KPPV renvoie la moyenne des valeurs y des k voisins, éventuellement pondérée.

Astuce mémo

Un nouvel objet consulte ses voisins les plus proches pour leur emprunter leur classe.

2. Distances et choix des paramètres

★ À maîtriser

📌 Avant un KPPV, il faut normaliser les variables, car une variable de grande amplitude peut dominer la distance euclidienne et rendre les autres variables presque négligeables.

  • Une valeur de k trop petite rend le KPPV sensible au bruit et augmente la variance, tandis qu’une valeur trop grande mélange les classes et augmente le biais.

Compléments

  • Le KPPV est non paramétrique et ne suppose aucune forme particulière de frontière de décision.

  • Le KPPV nécessite un jeu d’entraînement, une mesure de distance, une valeur de k et une règle d’agrégation des voisins.

📐 Formule - La distance euclidienne entre deux objets de coordonnées xix_i et yiy_i est d(O1,O2)=∑i=1n(xi−yi)2d(O_1,O_2)=\sqrt{\sum_{i=1}^{n}(x_i-y_i)^2}.

  • Une distance doit vérifier la séparation des points, la positivité, la symétrie et l’inégalité triangulaire.

  • Les choix de distance selon le type de variable sont :

    • variables numériques : distance euclidienne ou Manhattan
    • variables catégorielles : distance 0 si identique et 1 sinon
    • variables binaires : distance de Hamming ou de Jaccard
    • variables ordinales : distance sur le rang

📌 En classification binaire, choisir un k impair permet d’éviter une égalité des votes entre deux classes.

📌 La valeur de k se choisit par validation ou validation croisée, avec comme heuristique de départ k≈nk\approx\sqrt{n} ou k égal au nombre d’attributs plus 1.

Astuce mémo

Un k petit suit les détails du voisinage ; un k grand lisse davantage la frontière.

3. Coût et mise en œuvre du KPPV

★ À maîtriser

📌 Le choix de k et des autres paramètres du KPPV doit se faire par validation croisée plutôt que sur le jeu de test.

Compléments

  • Le vote majoritaire attribue la classe la plus fréquente parmi les voisins, tandis que le vote pondéré donne davantage de poids aux voisins les plus proches.

  • Le coût d’une prédiction par force brute est O(kdn)O(kdn), où n est la taille du jeu d’entraînement et d le nombre d’attributs.

  • Dans scikit-learn, KNeighborsClassifier permet de choisir le nombre de voisins avec n_neighbors, le vote par distance avec weights="distance" et la distance de Manhattan avec metric="manhattan".

Astuce mémo

Le KPPV n’entraîne pas de modèle, mais concentre le calcul au moment de la prédiction.

4. Principes des arbres de décision

Notions clés & Définitions

  • Racine : Le premier nœud de l’arbre, où s’effectue le test initial.
  • Nœud interne : Teste un attribut de données.
  • Branche : Correspond à une valeur ou à un seuil du test effectué dans un nœud.
  • Feuille : Un nœud terminal qui prédit une classe.

★ À maîtriser

  • Un arbre de décision prend des décisions en enchaînant des tests sur les attributs, chaque réponse conduisant à une branche jusqu’à une décision.

Compléments

  • Les arbres de décision peuvent traiter des variables numériques et catégorielles sans normalisation.

  • Les tests de seuil d’un arbre découpent l’espace par des droites parallèles aux axes et produisent une frontière en rectangles, tandis qu’une frontière oblique peut nécessiter de nombreuses marches.

  • Un arbre de décision peut être utilisé pour justifier une décision auprès d’un humain et constitue une brique de base des forêts aléatoires et du gradient boosting.

Astuce mémo

Un jeu de « 20 questions » conduit de la racine, par des branches, jusqu’à une feuille.

5. Construction et critères de découpe

Notions clés & Définitions

  • Impureté : Mesure le mélange des classes dans un nœud, qui est pur lorsqu’il ne contient qu’une seule classe.

★ À maîtriser

  • La construction gloutonne d’un arbre part de la racine, choisit localement le meilleur test, partitionne les données et répète le procédé sur chaque sous-ensemble jusqu’à un critère d’arrêt.

📐 Formule - Le gain d’impureté d’un test est I(parent)−∑ininI(enfanti)I(\text{parent})-\sum_i\frac{n_i}{n}I(\text{enfant}_i), où n_i est la taille d’un enfant et n celle du parent.

Compléments

  • La construction gloutonne choisit le meilleur test localement à chaque nœud sans garantir un arbre globalement optimal, car trouver l’arbre optimal est NP-difficile.

📐 Formule - L’indice de Gini d’un nœud est G=1−∑kpk2G=1-\sum_k p_k^2, où pkp_k est la proportion de la classe k dans le nœud.

📐 Formule - L’entropie d’un nœud est H=−∑kpklog⁡2(pk)H=-\sum_k p_k\log_2(p_k), où pkp_k est la proportion de la classe k dans le nœud.

  • L’indice de Gini et l’entropie valent 0 pour un nœud pur et sont maximaux lorsque les classes sont équiprobables.

📌 Le meilleur test est celui qui maximise le gain d’impureté, c’est-à-dire qui minimise l’impureté moyenne pondérée des enfants.

  • Le gain d’information favorise les attributs ayant de nombreuses valeurs, tandis que le gain ratio de C4.5 corrige ce biais.

Astuce mémo

Un gain d’impureté élevé conduit à choisir le test qui sépare le mieux les classes.

6. Arbres de décision en régression

★ À maîtriser

  • En régression, un arbre prédit dans chaque feuille la moyenne des valeurs y des exemples qu’elle contient, produisant une fonction constante par morceaux.

  • Dans scikit-learn, DecisionTreeClassifier utilise les interfaces fit, predict et score, et son paramètre criterion choisit entre Gini et entropie.

Compléments

📌 Pour un arbre de régression, le critère de découpe minimise la variance ou l’erreur quadratique moyenne des enfants.

  • Plus un arbre de régression est profond, plus ses paliers sont fins, jusqu’au risque de surapprentissage.

  • Dans l’exemple de diagnostic de tumeurs, max_depth=4 et min_samples_leaf=5 limitent respectivement la profondeur de l’arbre et le nombre minimal d’exemples par feuille.

7. Interpréter et limiter les arbres

Notions clés & Définitions

  • Importance des variables : Dans un arbre, mesure combien la variable réduit l’impureté totale.

★ À maîtriser

  • Un arbre laissé libre peut se diviser jusqu’à isoler les exemples et apprendre par cœur le bruit, ce qui entraîne une variance très élevée.
  • Quand la profondeur de l’arbre augmente, l’erreur d’entraînement peut tomber à zéro tandis que l’erreur de test finit par remonter.

📌 Le pré-élagage arrête la croissance selon des seuils, tandis que le post-élagage laisse pousser l’arbre puis coupe les branches peu utiles.

📌 Les hyperparamètres de l’arbre se choisissent par validation, jamais sur le jeu de test, afin d’équilibrer sous-apprentissage et sur-apprentissage.

Compléments

  • La fonction export_text affiche les règles de l’arbre sous la forme de conditions « SI… ALORS ».

  • Le pré-élagage peut utiliser max_depth, min_samples_split, min_samples_leaf, max_leaf_nodes ou un gain minimal, tandis que le post-élagage peut utiliser cost-complexity pruning avec ccp_alpha.

Astuce mémo

Arbre plus profond → erreur d’entraînement plus faible, puis erreur de test plus élevée

8. Bagging et échantillonnage bootstrap

Notions clés & Définitions

  • Bagging : Entraînement de plusieurs arbres, chacun sur un échantillon bootstrap, puis agrégation de leurs prédictions par vote majoritaire en classification ou par moyenne en régression.
  • Échantillon bootstrap : Échantillon obtenu en tirant avec remise n exemples parmi les n exemples d’origine.

★ À maîtriser

📐 Formule - La moyenne de MM estimateurs indépendants de variance σ2\sigma^2 a une variance de σ2M\frac{\sigma^2}{M}.

Compléments

  • En moyenne, un échantillon bootstrap contient environ 63 % des exemples distincts et les quelque 37 % restants forment l’échantillon out-of-bag (OOB).

  • Les échantillons bootstrap différents font voir aux arbres des données légèrement différentes, ce qui rend leurs erreurs plus indépendantes et stabilise l’agrégation.

Astuce mémo

Des arbres entraînés sur des échantillons bootstrap différents votent ou calculent une moyenne

9. Fonctionnement des forêts aléatoires

Notions clés & Définitions

  • Forêt aléatoire : Breiman, 2001 - Ensemble d’arbres entraînés sur des échantillons bootstrap et ne considérant qu’un sous-ensemble aléatoire de variables à chaque nœud.

★ À maîtriser

  • Pour entraîner une forêt aléatoire, on tire un échantillon bootstrap pour chaque arbre, on fait pousser un arbre profond en tirant m variables à chaque nœud, puis on agrège les prédictions par vote majoritaire en classification ou par moyenne en régression.

Compléments

  • Le tirage aléatoire de variables décorrèle les arbres lorsque certaines variables très prédictives risqueraient autrement d’être choisies en haut par tous les arbres.

  • Les valeurs usuelles du nombre de variables considérées par nœud sont m=dm=\sqrt{d} en classification et m=d/3m=d/3 en régression, où d est le nombre total de variables.

Astuce mémo

Bootstrap des lignes, tirage aléatoire des variables, puis vote ou moyenne

10. Évaluer et comparer les ensembles

★ À maîtriser

  • Pour évaluer un exemple en OOB, on le prédit uniquement avec les arbres qui ne l’ont pas vu lors de leur entraînement, ce qui fournit une estimation de l’erreur de test sans jeu de validation supplémentaire.
  • L’importance des variables d’une forêt agrège les réductions d’impureté apportées par chaque variable dans les arbres, mais cette mesure est biaisée en faveur des variables à forte cardinalité, pour lesquelles la permutation importance est préférable.

  • Un arbre de décision est très interprétable, rapide et peu coûteux, mais instable et sujet au sur-apprentissage ; une forêt aléatoire est moins interprétable et plus coûteuse, mais présente une variance plus faible et résiste mieux au sur-apprentissage.

  • Le bagging entraîne des arbres en parallèle et réduit surtout la variance, tandis que le boosting entraîne des arbres en série, chacun corrigeant les erreurs du précédent, et réduit surtout le biais.

Compléments

  • L’erreur d’une forêt aléatoire décroît puis se stabilise lorsque le nombre d’arbres augmente, sans que l’ajout d’arbres entraîne de sur-apprentissage.

📌 Une règle pratique consiste à choisir n_estimators aussi grand que le budget le permet, souvent entre 100 et 500, car le gain devient négligeable après quelques centaines d’arbres.

  • Dans scikit-learn, l’évaluation OOB d’une forêt s’active avec oob_score=True et est particulièrement utile lorsque les données sont peu nombreuses.

  • Dans une forêt, max_features est un levier important de décorrélation des arbres, tandis que max_depth et min_samples_leaf contrôlent leur taille ; class_weight="balanced" peut être utilisé avec des classes déséquilibrées.

11. Choisir un modèle selon le problème

★ À maîtriser

  • Les arbres et les forêts aléatoires sont adaptés aux données tabulaires, aux mélanges de variables numériques et catégorielles, ainsi qu’aux relations non linéaires et aux interactions.

Compléments

📌 Un arbre unique est souvent choisi pour obtenir des explications, tandis qu’une forêt est souvent choisie pour ses performances ou comme baseline forte.

  • Les arbres et les forêts sont moins adaptés aux images, au son et au texte brut, pour lesquels le deep learning est.

  • Les arbres extrapolent mal hors du domaine d’entraînement, car leurs prédictions sont constantes aux bords.

  • Une forêt aléatoire peut être moins adaptée lorsque les contraintes de mémoire ou de latence sont fortes, car elle est plus coûteuse qu’un arbre seul.

Astuce mémo

Arbre pour expliquer, forêt pour performer

Tableaux de synthèse

Arbre de décision et forêt aléatoire

DimensionArbreForêt aléatoire
InterprétabilitéExcellente, règles lisiblesFaible, nombreux arbres
VarianceÉlevée et instableFaible grâce à l’agrégation
Sur-apprentissageFacilePlus résistante
CoûtTrès faibleÉlevé

Teste tes connaissances

Teste tes connaissances sur KPPV et arbres de décision avec 28 questions à choix multiples et corrections détaillées.

1. Un nouvel objet est entouré de cinq exemples d’entraînement, dont trois appartiennent à la classe A et deux à la classe B. Quelle classe le KPPV lui attribue-t-il ?

2. Pour classer un nouvel objet avec un KPPV de paramètre k, quelle opération doit être effectuée juste après le calcul de sa distance à chaque exemple d’entraînement ?

Faire le QCM →

Révisez avec les flashcards

Mémorisez les concepts clés de KPPV et arbres de décision avec 85 flashcards interactives.

Comment le KPPV attribue-t-il une classe à un nouvel objet ?

Il lui attribue la classe majoritaire parmi ses kk voisins les plus proches.

Que calcule le KPPV pour chaque exemple d’entraînement lors d’un classement ?

La distance à l’objet à classer.

Comment le KPPV choisit-il les exemples utilisés pour classer un objet ?

Il sélectionne les kk exemples les plus proches.

Voir les flashcards →

Cours similaires

Crée tes propres fiches de révision

Importe ton cours et l'IA génère fiches, QCM et flashcards en 30 secondes.

Générateur de fiches