mercredi 2 avril 2008

Règles d’association avec Apriori PT

La construction de règles d’association pose de problèmes de performances, tant en occupation mémoire qu’en temps de traitement. L’implémentation actuelle dans TANAGRA est relativement rapide, en revanche, elle est très gourmande en mémoire, au point de la saturer très rapidement dès que l’on a à produire un grand nombre de règles. De plus, l’affichage des règles en HTML est tributaire du composant d’affichage, un peu limité, au point que le temps consacré à l’affichage est parfois aussi important que le temps consacré à l’élaboration des règles.

Il fallait donc se tourner vers un module très performant de construction des règles et proposer une nouvelle fenêtre d’affichage peu sensible au nombre de règles, fussent-elles de plusieurs centaines de milliers.

Sur la création des règles, j’ai découvert les travaux de Christian BORGELT. Il propose une implémentation réellement impressionnante. Traduire le code en DELPHI m’exposait aux risques de mauvaises interprétations de son travail, et donc d’introduction d’erreurs ; le passage par des DLL est également séduisant mais m’oblige à faire un travail de traduction des structures en C vers DELPHI, toujours hasardeux, pour la définition des unités d’import. J’ai donc décidé d’inaugurer une nouvelle approche avec cette nouvelle version, l’appel à un programme externe avec passage de fichiers temporaires. La rapidité de l’ensemble dépend en grande partie du temps consacré à l’écriture et à la lecture des fichiers temporaires. Force est de constater que le travail de Borgelt est réellement impressionnant. Au final, cette approche semble viable, du moins tant qu’il n’est pas nécessaire de produire des données qui seront par la suite utilisées dans le diagramme. Nous en montrons un exemple dans ce didacticiel.

L’autre point important était de créer une fenêtre de visualisation des règles qui ne s’effondre pas dès que leur nombre excède la centaine de milliers de règles, et qui par ailleurs, comporte des fonctionnalités de tri selon différents critères. Nous avons donc élaboré un outil simple qui permet de récupérer les sorties de Borgelt et d’afficher simplement les règles dans une fenêtre conviviale.

Après les commentaires des utilisateurs, je me suis rendu compte que l’implémentation distribuée par Borgelt, intégrée dans Tanagra, ne génère des règles qu’avec un seul item dans le conséquent. La limitation est inhérente au code source, on ne peut pas la dépasser en modifiant simplement les paramétrages.

Quoiqu’il en soit, dès que la base est d’une taille relativement importante, c’est bien ce composant qu’il faut utiliser en priorité.

Mots clés : règles d’association, traitement de grandes bases
Composants : A priori PT
Lien : fr_Tanagra_A_Priori_Prefix_Tree.pdf
Données : assoc_census.zip
Références :
C. Borgelt, "A priori - Association Rule Induction / Frequent Item Set Mining"
Voir « Les règles d’association – A priori »