Navigation – Plan du site

Construction efficace du treillis des motifs fermés fréquents et extraction simultanée des bases génériques de règles

Efficient construction of the lattice of frequent closed patterns and simultaneous extraction of generic bases of rules
Tarek Hamrouni, Sadok Ben Yahia et Engelbert Mephu Nguifo
p. 5-54

Résumés

Durant ces dernières années, les quantités de données collectées, dans divers domaines d’application de l’informatique, deviennent de plus en plus importantes. Ces quantités suscitent le besoin d’analyse et d’interprétation afin d’en extraire des connaissances utiles. Dans ce travail, nous nous intéressons à la technique d’extraction des règles d’association à partir de larges contextes. Cette dernière est parmi les techniques les plus fréquemment utilisées en fouille de données. Toutefois, le nombre de règles extraites est généralement important avec en outre la présence de règles redondantes. Dans cet article, nous proposons un nouvel algorithme, appelé PRINCE, dont la principale originalité est de construire une structure partiellement ordonnée (nommée treillis d’Iceberg) dans l’objectif d’extraire des ensembles réduits de règles, appelés bases génériques. Ces bases forment un sous-ensemble, sans perte d’information, des règles d’association. Pour réduire le coût de cette construction, le treillis d’Iceberg est calculé grâce aux générateurs minimaux, associés aux motifs fermés fréquents. Ces derniers sont simultanément dérivés avec les bases génériques grâce à un simple parcours ascendant de la structure construite. Les expérimentations que nous avons réalisées sur des contextes de référence et « pire des cas » ont montré l’efficacité de l’algorithme proposé, comparativement à des algorithmes tels que CLOSE, A-CLOSE et TITANIC.

Efficient construction of the lattice of frequent closed patterns and simultaneous extraction of generic bases of rules

In the last few years, the amount of collected data, in various computer science applications, has grown considerably. These large volumes of data need to be analyzed in order to extract useful hidden knowledge. This work focuses on association rule extraction. This technique is one of the most popular in data mining. Nevertheless, the number of extracted association rules is often very high, and many of them are redundant. In this paper, we propose a new algorithm, called PRINCE. Its main feature is the construction of a partially ordered structure for extracting subsets of association rules, called generic bases. Without loss of information these subsets form representation of the whole association rule set. To reduce the cost of such a construction, the partially ordered structure is built thanks to the minimal generators associated to fréquent closed patterns. The closed ones are simultaneously derived with generic bases thanks to a simple bottom up traversal of the obtained structure. The experimentations we carried out in benchmark and « worst case » contexts showed the efficiency of the proposed algorithm, compared to algorithms like CLOSE, A-CLOSE and TITANIC.

Haut de page

Pour citer cet article

Référence électronique

Tarek Hamrouni, Sadok Ben Yahia et Engelbert Mephu Nguifo, « Construction efficace du treillis des motifs fermés fréquents et extraction simultanée des bases génériques de règles », Mathématiques et sciences humaines [En ligne], 195 | Automne 2011, mis en ligne le 09 janvier 2012, consulté le 19 octobre 2017. URL : http://msh.revues.org/12081

Haut de page

Auteurs

Tarek Hamrouni

Unité de Recherche en Programmation Algorithmique et Heuristique (URPAH), Département des Sciences de l’Informatique, Faculté des Sciences de Tunis, Université Tunis El Manar, Campus Universitaire, Tunis, tarek.hamrouni@fst.rnu.tn

Sadok Ben Yahia

Unité de Recherche en Programmation Algorithmique et Heuristique (URPAH), Département des Sciences de l’Informatique, Faculté des Sciences de Tunis, Université Tunis El Manar, Campus Universitaire, Tunis, sadko.benyahia@fst.rnu.tn

Engelbert Mephu Nguifo

Clermont Université, Université Blaise Pascal, Laboratoire d’Informatique, de Modélisation et d’Optimisation des Systèmes (LIMOS), BP 10448, 6300 Clermont-Ferrand, engelbert.mephu_nguifo@unibpclermont.fr

Haut de page

Droits d’auteur

© École des hautes études en sciences sociales

Haut de page