On Measuring Similarity for Sequences of Itemsets
Résumé
Computing the similarity between sequences is a very important challenge for many different data mining tasks. There is a plethora of similarity measures for sequences in the literature, most of them being designed for sequences of items. In this work, we study the problem of measuring the similarity between sequences of itemsets. We present new combinatorial results for efficiently counting distinct and common subsequences. These theoretical results are the cornerstone of an effective dynamic programming approach to deal with this problem. Experiments on healthcare trajectories and synthetic datasets, show that our measure of similarity produces competitive scores and indicates that our method is relevant for large scale sequential data analysis.
Le calcul de similarité entre les séquences est d'une extrême importance dans de nombreuses approches d'explorations de données. Il existe une multitude de mesures de similarités de séquences dans la littérature. La plupart de ces mesures sont conçues pour des séquences simples, dites séquences d'items. Dans ce travail, nous étudions le problème de similarité entre des séquences complexes (i.e., des séquences d'ensembles ou itemsets) d'un point de vue purement combinatoire. Nous présentons de nouveaux résultats afin de compter efficacement toutes les sous-séquences communes à deux séquences. Ces résultats théoriques sont la base d'une mesure de similarité calculée efficacement grâce à une approche de programmation dynamique. Des expériences réalisées et présentées sur des soins de santé et sur des jeux de données synthétiques, montrent que notre mesure de similarité produit des résultats intéressants et probants. Cette série d'expériences indique que notre mesure de similarité est pertinente pour les applications impliquant l'analyse de données séquentielles
Domaines
Autre [cs.OH]
Origine : Fichiers produits par l'(les) auteur(s)
Loading...