Extraction complète efficace de chemins pondérés dans un a-DAG

TitreExtraction complète efficace de chemins pondérés dans un a-DAG
Publication TypeConference Proceedings
Year of Publication2015
AuthorsSelmaoui-Folcher, N, Flouvat, F, Mu, C, Sanhes, J, Boulicaut, J-F
Conference Name15èmeconférence internationale sur l'extraction et la gestion des connaissances
VolumeRNTI E.28
EditionRNTI
Pagination179-190
Date Published01/2015
PublisherHermès
Conference LocationLuxembourg
Abstract

La fouille de données spatio-temporelles au moyen d’un nouveau domaine de motifs appelé chemins pondérés condensés a été introduite en 2013 dans les actes de la conférence IJCAI. Le contexte de fouille est alors un graphe acyclique orienté (DAG) dont les sommets sont étiquetés par des attributs. Nous avons voulu travailler à une implémentation efficace de ce type de motifs et nous montrons que l’algorithme proposé est juste mais incomplet. Nous établissons ce résultat d’incomplétude et nous l’expliquons avant de trouver une solution pour réaliser l’extraction de façon complète. Nous pouvons ensuite développer des structures complémentaires pour réaliser efficacement le calcul de tous les chemins pondérés condensés. Nous montrons que la performance de l’algorithme est améliorée de plusieurs ordres de magnitude sur des jeux de données artificiels et nous l’appliquons aussi à des données réelles pour motiver qualitativement l’usage des chemins pondérés.

no socket

no socket