dimanche 18 octobre 2009

Sipina - Echantillonnage dans les arbres

Lors de l’induction d’un arbre de décision, l’algorithme doit détecter la meilleure variable de segmentation pour chaque nœud que l’on souhaite partitionner. L’opération peut prendre du temps si le nombre d’observations est très élevé. Ceci d’autant plus que les variables candidates sont continues, il faut trouver la borne de discrétisation optimale.

Le logiciel Sipina introduit une option d’échantillonnage local dans tous les algorithmes d’induction d’arbres qu’il propose. L’idée est la suivante : sur chaque sommet, plutôt que de travailler sur la totalité des observations présentes pour choisir la variable de segmentation, il réalise les opérations sur un échantillon. Bien entendu, lorsque le nombre d’observations disponibles sur le sommet est plus faible que la taille d’échantillon demandée, il n’y a plus lieu de procéder à un échantillonnage, Sipina utilise toutes les observations. Cela arrive dans les parties bases de l’arbre lorsqu’il est particulièrement profond. Nous avions évoqué cette idée dans un de nos anciens posts (Echantillonnage dans les arbres de décision), nous la mettons en œuvre dans ce didacticiel.

Nous manipulons un fichier comportant 21 descripteurs et 2.000.000 d’observations, dont une moitié est utilisée pour construire l’arbre, l’autre pour son évaluation. Nous constaterons que, dans certaines circonstances, travailler sur un échantillon dans les nœuds permet de réduire le temps de calculs (divisé par 30 !) tout en préservant les performances en classement.

Nous comparerons les temps de calcul avec ceux de Tanagra où une autre stratégie a été mise en place pour accélérer les traitements.

Mots clés : arbre de décision, échantillonnage, sipina, apprentissage, test, traitement des grandes bases de données, gros fichier
Composants : SAMPLING, ID3, TEST
Lien : fr_Sipina_Sampling.pdf
Données : wave2M.zip
Références :
J.H. Chauchat, R. Rakotomalala, « A new sampling strategy for building decision trees from large databases », Proc. of IFCS-2000, pp. 199-204, 2000.