Présentations

Techniques d’arbres de classification et de régression – Xavier Milaud

Compte rendu

Lors de cette réunion, X. Milhaud a effectué une présentation sur les techniques d’arbres de classification et de régression.

L’objectif de telles techniques est la classification par groupe d’individus homogènes selon une quantité d’intérêt par rapport à certains paramètres connus. Par exemple, on peut chercher à déterminer qui est propriétaire dans une population connaissant le salaire et la surface du lieu d’habitation de chaque individu. On regroupera alors les individus de salaires proches et dont la surface du lieu d’habitation est du même ordre de grandeur et pour chacun de ces groupes, on déterminera s’ils sont propriétaires ou non. Quelques exemples et généralités ont été donnés sur ces techniques.

Ensuite, l’une d’entre elles a été développée : la méthode CART pour Classification And Regression Tree.

La méthode CART

C’est une méthode supervisée, c’est-à-dire qu’on dispose d’observations pour la quantité d’intérêt.

Le principe de cette méthode est le suivant : on se donne un critère pour évaluer la classification estimée par rapport à l’observation qui est l’erreur quadratique moyenne que l’on cherche donc à minimiser. L’arbre que l’on construit récursivement est caractérisé par un ensemble de règles. Une règle est une question qui admet un nombre de fini de réponses (ici la réponse est binaire). Chaque nœud est une intersection d’un ensemble de règles, ce qui correspond à un partitionnement de la population observée. Par exemple, si on cherche à déterminer dans une population donnée qui est propriétaire et qui ne l’est pas en fonction de paramètres comme le salaire et la surface, l’arbre estimé classifie les individus tout d’abord si la surface excède 19 m² ou pas, si oui alors la règle suivante est de savoir si le revenu excède 5750$ ou pas, etc. Le nœud correspondant à la dernière règle énoncée est alors associé au partitionnement suivant {individus ayant une surface supérieure à 19 m²} ∩ {individus ayant un revenu supérieur à 5750$}. Les feuilles finales regroupent alors des individus homogènes (par rapport à leur salaire et à la surface de leur lieu d’habitation) pour lesquelles on détermine s’ils sont propriétaires ou non.

Une fois l’arbre obtenu, on élague de sorte à ne pas avoir un arbre trop complexe et trop de groupes constitués d’un petit nombre d’individus.

 

Avantages et inconvénients

La relation entre la classification d’un individu et les paramètres connus caractérisant cet individu n’étant pas forcément linéaire, la méthode CART dépourvue d’hypothèse a priori capte bien ces non-linéarités. L’algorithme est également bien adapté à la gestion de grandes bases de données type Big Data du fait que l’algorithme est récursif et qu’il facilite la parallélisation des calculs. De plus, l’interprétation et le visionnage des résultats sont relativement simples.

Toutefois, la méthode étant bâtie par rapport à un jeu de données, la question de la robustesse se pose. Pour répondre à cette question, des procédures de choix aléatoire des facteurs de risque considérés lors d’une division (bagging) ou de tirage de sous-jeux de données aléatoires ont été proposés dont la consistance a aussi été démontrée (voir [MDvdL04] and [GN05]).

Une remarque a été formulée pour savoir si les signaux faibles étaient bien pris en compte (ce qui constitue notamment un intérêt de l’utilisation de Big Data). Il a été retenu qu’ils l’étaient puisqu’ils pourraient être représentés par les branches isolées qui apparaitraient plus ou moins en amont dans l’arbre.

Annexe : Résumé de l’algorithme

A chaque étape, pour chaque nœud, on retient le partitionnement qui minimise l’espérance de l’erreur quadratique induite par chacun des partitionnements supplémentaires possibles. La convergence de cette procédure a ainsi été prouvée mathématiquement (voir [BFOS84]).

Au final, un arbre peut être vu comme un estimateur par morceaux, où le morceau est une feuille dont la valeur est la moyenne empirique des valeurs de notre variable d’intérêts pour chaque individu, l’idée étant de maximiser l’homogénéité.

Une fois l’arbre obtenu sans critère d’arrêt (du type nombre maximal de subdivisions), on élague ensuite a posteriori l’arbre de sorte à éviter de générer un arbre trop complexe.  Cet élagage consiste à introduire pour chaque règle de division un paramètre α de pénalisation multiplicatif du nombre de divisions K divisé par le nombre d’individus. On calcule alors l’erreur quadratique moyenne plus pénalisation correspondant pour chaque étape de subdivision et on retient l’étape pour laquelle cette erreur est minimisée.

Enfin, on fait varier α, ce qui nous donne un arbre associé et on retient celui qui minimise notre « erreur moyenne quadratique pénalisée ». La consistance de cette méthode d’élagage a également été démontrée (voir [MDvdL04] and [GN05]).

 

Présentation

Un exemple en R

Détection de spam

Répondre

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l'aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s