Stage M2R - 2005/2006
Fouille d'arbres Floue
Encadrants : P. Poncelet, M. Teisseire, A. Laurent
La recherche de sous-structures fr
equentes dans les bases de données semi-structurées est
une problématique très active qui trouve de nombreuses
applications, notamment dans le cadre de la médiation de
données. Des méthodes
ont été
proposées. Cependant, elles ne permettent que de trouver des
sous-structures fréquentes de petite taille dans les bases de
données réelles (ce qui rend par exemple impossible la
construction de schéma m ediateur). Nous proposons donc, dans le
cadre de ce stage, d' étendre les méthodes
existantes à la recherche approximative de sous-structures
fréquentes. Il s'agira :
- d'étudier les pistes de recherche présentées
dans [2], de proposer des méthodes complêtes incluant le
cadre formel (e.g. définitions, mesures de comparaison) et les
algorithmes,
- de proposer une méthode permettant, à partir
des sous-structures approximatives fréquentes trouvées,
de construire un schéma m ediateur,
- de mettre en oeuvre ces solutions en les
implémentant et en les validant sur des bases de donnéees
réeelles et conséquentes.
[1] T. Asai, H. Arimura, T. Uno, and S. Nakano. Discovering
frequent sub-structures in large unordered trees. In Proceedings of the
6th International Conference on Discovery Science, pages 47-61,
Sapporo, Japan, October 2003.
[2] A. Laurent, P. Poncelet, M. Teisseire. Fuzzy Data Mining for the
Semantic Web : Building XML Mediator Schemas. Fuzzy Logic and the
Semantic Web. Elsevier. E. Sanchez (ed). To appear.
[3] P. Ceravolo, M. C. Nocerino, and M. Viviani. Knowledge extraction
from semi-structured data based on fuzzy techniques. In Proceedings of
the 8th International Conference on Knowledge-Based Intelligent
Information & Engineering Systems (KES 04), pages 328-334, 2004.
[4] M. Zaki. E ciently mining frequent trees in a forest. In
Proceedings of the 8th ACM SIGKDD International Conference on Knowledge
Discovery and Data Mining (KDD 02), pages 386-395, Edmonton, Canada,
July 2002.