Représentations condensées d'ensembles de règles d'association
Institution:
Lyon, INSADisciplines:
Directors:
Abstract EN:
Recently, the more and more intense usage of information systems yielded to the growth of the number and the size of the involved databases. The owners felt more and more the potential value of those databases. They started trying to these databases to advantage without being restricted to classical querying processes, but by attempting to extract information enclosing high added value, which could lead to the improvement of the users’ knowledge. This issue led to the creation of a new discipline : frequent pattern extraction. A lot more and more efficient algorithms were developed to address this kind of extraction since 1994. It is now often possible to extract in an exhaustive way in most of the cases certain types of frequent patterns enclosed in a database. The major drawback that met is the following : the discovered patterns are often too numerous. It is therefor difficult to sort them following an interest order in order to derive interesting information. In this context, it appeared that it is particularly interesting to find out more condensed representations of the extracted patterns in order to ensure a better reading of the results. More precisely, we have worked on the patterns called association rules, and we have proposed two global representations of association rules sets. We have designed and implemented tow algorithms for calculating each one of these representations, and we have shown their efficiency and effectiveness in practice. At last, we have conducted tests on real-life datasets.
Abstract FR:
Ces dernières années, l'utilisation de plus en plus massive des systèmes d'information a donné lieu à l'accroissement important du nombre de bases de données et à l'augmentation de leur taille. Leurs propriétaires ont ressenti de plus en plus fortement la valeur potentielle de ces bases de données. Ils ont alors commencé à essayer de valoriser ces grands volumes de données sans se limiter aux processus d'interrogation classiques, mais en tentant d'extraire des informations à forte valeur ajoutée pouvant aboutir à l'amélioration du niveau de connaissance des utilisateurs de ces bases. De ce problème est né une discipline : l'extraction de motifs fréquents. Beaucoup d’algorithmes de plus en plus performants furent développés pour ce type d’extractions entre 1994 et aujourd’hui. Il est maintenant souvent possible d’extraire de manière quasi exhaustive certains types de motifs fréquents contenus dans une base de données. L'inconvénient majeur rencontré est le suivant : les motifs trouvés sont trop nombreux. Il est difficile de les trier par ordre d'intérêt afin d'en tirer une information intéressante. Dans ce contexte, il nous a semblé particulièrement intéressant de trouver des représentations plus condensées de motifs extraits de manière à assurer une meilleur lecture de ces résultats. Plus précisément, nous avons travaillé sur les motifs appelés règles d'association et nous avons proposé deux représentations synthétiques de jeux de règles d'association. Nous avons conçu et implanté deux algorithmes pour calculer chacune de ces représentations, et nous avons montré leur efficacité en pratique. Enfin nous avons utilisé ces représentations avec des cas réels.