On measuring similarity for sequences of itemsets

Elias Egho 1 Chedy Raïssi 1 Toon Calders 2 Nicolas Jay 1 Amedeo Napoli 1
1 ORPAILLEUR - Knowledge representation, reasonning
Inria Nancy - Grand Est, LORIA - NLPKD - Department of Natural Language Processing & Knowledge Discovery
Abstract : 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 focus on the notion of common subsequences as a way to measure similarity between a pair of sequences composed of a list 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. In addition, we propose an approximate method to speed up the computation process for long sequences. We have applied our method to various data sets: healthcare trajectories, online handwritten characters and synthetic Responsible editors: 123 Elias Egho et al. data. Our results confirm that our measure of similarity produces competitive scores and indicate that our method is relevant for large scale sequential data analysis.
Type de document :
Article dans une revue
Data Mining and Knowledge Discovery, Springer Verlag, 2015, 29 (3), pp.33. 〈10.1007/s10618-014-0362-1〉
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

Contributeur : Elias Egho <>
Soumis le : mardi 13 janvier 2015 - 19:21:59
Dernière modification le : jeudi 11 janvier 2018 - 06:25:24
Document(s) archivé(s) le : samedi 15 avril 2017 - 07:51:08


Fichiers produits par l'(les) auteur(s)




Elias Egho, Chedy Raïssi, Toon Calders, Nicolas Jay, Amedeo Napoli. On measuring similarity for sequences of itemsets. Data Mining and Knowledge Discovery, Springer Verlag, 2015, 29 (3), pp.33. 〈10.1007/s10618-014-0362-1〉. 〈hal-01094383〉



Consultations de la notice


Téléchargements de fichiers