Similarité par recouvrement de séquences pour la fouille de données séquentielles et textuelles

Pierre-François Marteau (1, 2) , Nicolas Béchet (1, 2) , Oussama Ahmia (1, 2)

1 EXPRESSION - Expressiveness in Human Centered Data/Media
2 IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires

Nous introduisons la notion de similarité par recouvrement de sé- quences pour estimer la similarité entre une séquence et un ensemble de sé- quences. Nous en dérivons une pseudo-distance qui s’apparente aux distances d’édition de type Levenshtein pour comparer des paires de séquences. La com- plexité algorithmique associée à cette semi-métrique peut-être ramenée à O(n · log(n)) en utilisant des arbres de suffixes. Nous introduisons un nouveau mo- dèle discriminant dédié à la classification de données textuelles dont la com- plexité algorithmique ne dépend pas de la taille de l’ensemble d’apprentissage, mais uniquement du nombre de classes et de la longueur des séquences. L’étude expérimentale préliminaire présentée s’appuie sur deux benchmaks : le premier concerne des séquences de nucléotides, le second une tâche de classification de textes. Les résultats obtenus positionnent l’approche proposée au niveau de l’état de l’art (incluant les approches "deep learning") sur les tâches considérées., avec des temps de calcul et un nombre de méta-paramètres avantageux.

Domaines: Recherche d'information [cs.IR]; Intelligence artificielle [cs.AI]; Traitement du texte et du document; Apprentissage [cs.LG]

Pierre-François Marteau, Nicolas Béchet, Oussama Ahmia. Similarité par recouvrement de séquences pour la fouille de données séquentielles et textuelles. Extraction et Gestion des Connaissances (EGC 2019), Jan 2019, Metz, France. pp.105-116. ⟨hal-01999965⟩