jeudi 27 mars 2008

Echantillonnage dans les arbres de décision

Stratégie d'échantillonnage pour les arbres de décision. Dans tous les algorithmes d'induction d'arbres, SIPINA introduit une option d'échantillonnage. L'idée est la suivante : plutôt que de travailler sur l'ensemble des individus disponibles sur chaque noeud pour choisir la variable de segmentation, nous proposons d'extraire un sous-échantillon et de calculer sur ces observations les indicateurs appropriés (gain d'entropie, statistique du khi-2, indice de Gini, etc.).

L'expérimentation montre que l'ordonnancement des variables de segmentation sur chaque noeud reste le même, et de fait, les caractéristiques des arbres produits, notamment les performances en prédiction, sont préservées.

L'intérêt de cette approche est le gain de temps lors de la construction de l'arbre. Il peut être déterminant sur les grandes bases, surtout lorsqu'elles comportent un nombre important de variables continues, nécessitant la répétition du tri des données lors de la discrétisation.

L'échantillonnage sur un noeud est toujours sans remise. Il peut être représentatif (aléatoire simple), équilibré (le même nombre d'observations pour chaque modalité de la variable à prédire), ou stratifié (respectant les proportions de la totalité des observations sur le noeud).

Changement de stratégie dans Tanagra. Notons que par la suite, dans TANAGRA, nous avons adopté une autre stratégie. Toutes les variables continues sont triées une fois pour toutes avant l'induction. Un tableau d'index permet de conserver l'ordre des observations. Lors du traitement d'un noeud, nous y puisons les individus présents. La phase de tri n'est donc plus nécessaire puisque les observations sont déjà ordonnées. Le prix de cette approche est la nécessité de conserver en mémoire le tableau d'index, à savoir 4 octets par observation et par variable. Pourquoi ce revirement ? La raison est simplement pragmatique. En 1998, on disait d'une machine qu'elle était performante lorsqu'elle disposait de 256 Mo de RAM. En 2004, et plus récemment encore, un ordinateur avec 2Go de RAM est tout à fait courant.

Mots clés : arbres de décision, échantillonnage, optimisation des calculs, traitement des grandes bases de données
Référence : J.H. Chauchat, R. Rakotomalala, « A new sampling strategy for building decision trees from large databases », Proc. of IFCS-2000, pp. 199-204, 2000.