2.5 Partitionnement récursif

Le partitionnement récursif est un algorithme de classification supervisée qui crée un arbre dichotomique où, à chaque nœud, une variable permet de déterminer si le parcours de l’arbre doit être poursuivi vers la gauche du nœud (lorsque la valeur de la variable est inférieure à un seuil fixé), ou vers sa droite (si la valeur est supérieure ou égale à ce seuil). Le choix de la variable utilisée à chaque nœud, ainsi que la valeur du seuil, est déterminé par l’algorithme de façon à maximiser la séparation entre les deux sous-entités ainsi obtenues, qui doivent discriminer au mieux entre les différents groupes à identifier. Le traitement est poursuivi tout au long de l’arbre de manière récursive jusqu’à aboutir à une extrémité, nommée “feuille”, et qui représente une classe donnée. Notez qu’il peut très bien y avoir plusieurs feuilles qui représentent une même classe. La classe attribuée à un individu est donc celle à laquelle on aboutit après avoir parcouru l’arbre de la base jusqu’aux feuilles.

Schéma du principe d’un arbre de classification en 4 classes, A, B, C et D en utilisant les attributs x, y et z. À chaque nœud un attribut et un seuil sont choisis afin d’établir une règle de décision (en rouge). Pour un individu dont il faut prédire la classe, nous parcourons l’arbre de branche en branche depuis tout en haut et bifurquons à gauche ou à droite selon la comparaison à la règle à chaque nœud : vers la gauche si la variable est inférieure au seuil, vers la droite si elle est supérieure ou égale. Les feuilles représentent chacune une classe (en bleu, duplications possibles). Arrivés à une feuille, nous obtenons donc la classe prédite pour cet individu.
Schéma du principe d’un arbre de classification en 4 classes, A, B, C et D en utilisant les attributs x, y et z. À chaque nœud un attribut et un seuil sont choisis afin d’établir une règle de décision (en rouge). Pour un individu dont il faut prédire la classe, nous parcourons l’arbre de branche en branche depuis tout en haut et bifurquons à gauche ou à droite selon la comparaison à la règle à chaque nœud : vers la gauche si la variable est inférieure au seuil, vers la droite si elle est supérieure ou égale. Les feuilles représentent chacune une classe (en bleu, duplications possibles). Arrivés à une feuille, nous obtenons donc la classe prédite pour cet individu.

Vous pouvez aussi visionner une magnifique présentation animée de ce qu’est un arbre de partitionnement ou décisionnel (pensez bien à sélectionner le français en tout début de document et faites défiler jusqu’à la fin de l’histoire). Dans cette présentation, la notion de suréchantillonnage (oversampling en anglais) est abordée. C’est un problème qui se rencontre souvent en classification supervisée, tout comme en régression. Dans le cas de l’arbre de partitionnement, la solution consiste à élaguer les branches de moindre importance de l’arbre. Cette page explique de manière très claire de quoi il s’agit.

2.5.1 Pima avec rpart

Afin de rendre ceci plus concret, calculons l’arbre de partitionnement récursif pour pima1. Le package {mlearning} offre la fonction mlRpart() pour ce faire.

set.seed(465)
pima1_rpart <- mlRpart(data = pima1, diabetes ~ .)
pima1_rpart_conf <- confusion(cvpredict(pima1_rpart, cv.k = 10), pima1$diabetes)
plot(pima1_rpart_conf)

summary(pima1_rpart_conf, type = c("Fscore", "Recall", "Precision"))
# 392 items classified with 294 true positives (error = 25%)
# 
# Global statistics on reweighted data:
# Error rate: 25%, F(micro-average): 0.712, F(macro-average): 0.711
# 
# # A data.frame: 2 x 3
#   ` `        Fscore Recall Precision
#   <rownames>  <dbl>  <dbl>     <dbl>
# 1 neg         0.817  0.836     0.799
# 2 pos         0.605  0.577     0.636

Ici, nous obtenons 25% d’erreur. Un intérêt du partitionnement récursif est de pouvoir visualiser le dendrogramme qui matérialise les règles choisies. Si cet arbre est relativement petit, nous pouvons aisément lire et tenter de comprendre la logique derrière ces règles. Les méthodes plot() et text() permettent de tracer l’arbre décisionnel calculé. Différents arguments permettent d’adapter la présentation du dendrogramme. Voyez l’aide en ligne de ?plot.rpart et ?text.rpart.

# Visualisation et annotation de l'arbre
plot(pima1_rpart, margin = 0.03, uniform = TRUE)
text(pima1_rpart, use.n = FALSE)

Comment lire cet arbre ? Nous partons de tout en haut, et à chaque nœud correspond une variable et un seuil. Si la variable est inférieure au seuil, nous parcourons l’arbre vers la gauche. Si au contraire, la variable est supérieure ou égale au seuil, nous nous dirigeons vers la droite. Nous réitérons l’opération à chaque nœud, jusqu’à arriver à une feuille. À ce niveau, nous lisons la classe associée à la feuille que nous attribuons à l’individu. Considérons une femme Pima pour laquelle nous avons enregistré les informations suivantes :

  • âge = 34 ans,
  • elle a 4 enfants (pregnant),
  • son test glucose a donné la valeur de 118 et son insuline a été mesurée à 145 µU/mL,
  • sa pression sanguine est de 82 mm Hg (pressure),
  • au niveau corpulence, elle a un IMC de 33,2 (mass) et le pli de peau au niveau de son triceps est de 28 mm,
  • enfin son indice de susceptibilité au diabète d’après ses antécédents familiaux a été calculé à 0,43.

D’après notre classifieur par arbre de partitionnement, est-elle diabétique ou non ? Pour y répondre, nous devons traverser l’arbre de haut en bas jusqu’à aboutir à une feuille.

  1. La première règle rencontrée est “glucose < 127,5”. Comme la valeur mesurée est de 118, nous continuons vers la gauche,

  2. Seconde règle rencontrée : “insulin < 143,5”. La valeur mesurée est de 145. Cette fois, nous bifurquons à droite,

  3. Nous arrivons à la règle “age < 28,5”. À 33 ans, nous continuons à nouveau vers la droite pour aboutir à une feuille de l’arbre pos. Ainsi pour cette dame, la prédiction est qu’elle est diabétique.

Chemin parcouru dans notre arbre décisionnel pour aboutir à la décision que l’Indienne de notre exemple est probablement diabétique.
Chemin parcouru dans notre arbre décisionnel pour aboutir à la décision que l’Indienne de notre exemple est probablement diabétique.

Notons que toutes les variables n’ont pas été utilisées. glucose et age sont repris trois fois dans l’arbre. Les variables insulin, mass, pressure et pedigree sont également utilisées. Par contre, triceps n’est jamais utilisée, de même que pregnant. C’est une première indication de l’importance des variables dans la discrimination des classes, même si la version à partir de la forêt aléatoire à base de l’indice Gini (voir plus loin) sera plus efficace.

Voyons ce que cela donne avec pima2. Pour rappel, ce jeu de données contient pratiquement deux fois plus de cas que pima1, mais pour cela, nous avons dû éliminer les variables triceps et insulin. Dans notre partitionnement récursif de pima1, triceps n’était pas utilisé, par contre, insulin était utilisé deux fois.

set.seed(9643)
pima2_rpart <- mlRpart(data = pima2, diabetes ~ .)
pima2_rpart_conf <- confusion(cvpredict(pima2_rpart, cv.k = 10), pima2$diabetes)
plot(pima2_rpart_conf)

summary(pima2_rpart_conf, type = c("Fscore", "Recall", "Precision"))
# 724 items classified with 546 true positives (error = 24.6%)
# 
# Global statistics on reweighted data:
# Error rate: 24.6%, F(micro-average): 0.721, F(macro-average): 0.72
# 
# # A data.frame: 2 x 3
#   ` `        Fscore Recall Precision
#   <rownames>  <dbl>  <dbl>     <dbl>
# 1 neg         0.818  0.842     0.795
# 2 pos         0.621  0.586     0.661
# Visualisation et annotation de l'arbre
plot(pima2_rpart, margin = 0.03, uniform = TRUE)
text(pima2_rpart, use.n = FALSE)

Ici, nous sommes légèrement en dessous des 25%. L’arbre est différent. La perte de la variable insulin semble avoir été bien compensée par un nombre d’observations plus grand dans pima2.

Pour en savoir plus
  • Explication sur la façon dans les règles sont établies dans l’arbre ici.