| Titre | Construction efficace du treillis des motifs fermés fréquents et extraction simultanée des bases génériques de règles | |
|---|---|---|
| Auteur | Tarek Hamrouni, Sadok Ben Yahia, Engelbert Mephu Nguifo | |
 |
Revue | Mathématiques et sciences humaines |
| Numéro | no 195, automne 2011 | |
| Page | 5-54 | |
| Résumé |
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. Source : Éditeur (via OpenEdition Journals) |
|
| Résumé anglais |
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. Source : Éditeur (via OpenEdition Journals) |
|
| Article en ligne | http://msh.revues.org/12081 |
