Nouvelle approche de fouille de graphes AC-réduits fréquents - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Revue des Nouvelles Technologies de l'Information Year : 2011

Nouvelle approche de fouille de graphes AC-réduits fréquents

Abstract

La fouille de graphes est devenue une piste de recherche intéressante et un défi réel en matière de fouille de données. Parmi les différentes familles de motifs de graphes, les graphes fréquents permettent une caractérisation intéressante des groupes de graphes, ainsi qu'une discrimination des différents graphes lors de la classification ou de la segmentation. A cause de la NP-complétude du test d'isomorphisme de sous-graphes et de l'immensité de l'espace de recherche, les algorithmes de fouille de graphes sont exponentiels en temps d'exécution et/ou occupation mémoire. Dans cet article, nous étudions un nouvel opérateur de projection polynomial nommé AC-projection basé sur une propriété clé du domaine de la programmation par contraintes, à savoir l'arc consistance. Cet opérateur est censé remplacer l'utilisation de l'isomorphisme de sous-graphes en établissant un biais sur la projection. Cette étude est suivie d'une évaluation expérimentale du pouvoir discriminant des patterns AC-réduits découverts.
No file

Dates and versions

lirmm-00818206 , version 1 (26-04-2013)

Identifiers

  • HAL Id : lirmm-00818206 , version 1

Cite

Brahim Douar, Michel Liquière, Chiraz Latiri, Yahya Slimani. Nouvelle approche de fouille de graphes AC-réduits fréquents. Revue des Nouvelles Technologies de l'Information, 2011, 20 (vol.RNTI-E-20), pp.473-478. ⟨lirmm-00818206⟩
172 View
0 Download

Share

More