Exploration de modèles séquentiels

L'exploration de modèles séquentiels est un sujet d' exploration de données qui vise à trouver des modèles statistiquement pertinents entre des exemples de données où les valeurs sont fournies dans une séquence. On suppose généralement que les valeurs sont discrètes, et donc l'exploration de séries temporelles est étroitement liée, mais généralement considérée comme une activité différente. L'exploration de modèles séquentiels est un cas particulier d' exploration de données structurées .

Plusieurs problèmes informatiques traditionnels clés sont abordés dans ce domaine. Il s'agit notamment de la création de bases de données et d'index efficaces pour les informations de séquence, de l'extraction des modèles fréquemment utilisés, de la comparaison des séquences pour la similarité et de la récupération des membres de séquence manquants. En général, les problèmes d'exploration de séquences peuvent être classés en exploration de chaînes , qui repose généralement sur des algorithmes de traitement de chaînes , et en exploration d'ensembles d'éléments , qui repose généralement sur l'apprentissage de règles d'association . Les modèles de processus locaux étendent l'exploration de modèles séquentiels à des modèles plus complexes qui peuvent inclure des choix (exclusifs), des boucles et des constructions de concurrence en plus de la construction de commande séquentielle.

L'exploration de chaînes de caractères traite généralement d'un alphabet limité pour les éléments qui apparaissent dans une séquence , mais la séquence elle-même peut généralement être très longue. Des exemples d'alphabet peuvent être ceux du jeu de caractères ASCII utilisé dans le texte en langage naturel, les bases nucléotidiques « A », « G », « C » et « T » dans les séquences d'ADN , ou les acides aminés pour les séquences de protéines . Dans les applications biologiques, l'analyse de la disposition de l'alphabet dans les chaînes de caractères peut être utilisée pour examiner les séquences de gènes et de protéines afin de déterminer leurs propriétés. Connaître la séquence de lettres d'un ADN ou d'une protéine n'est pas un but ultime en soi. La tâche principale consiste plutôt à comprendre la séquence, en termes de structure et de fonction biologique . Cela est généralement réalisé en identifiant d'abord des régions individuelles ou des unités structurelles au sein de chaque séquence, puis en attribuant une fonction à chaque unité structurelle. Dans de nombreux cas, cela nécessite de comparer une séquence donnée avec celles étudiées précédemment. La comparaison entre les chaînes de caractères devient compliquée lorsque des insertions , des suppressions et des mutations se produisent dans une chaîne de caractères.

Une étude et une taxonomie des algorithmes clés pour la comparaison de séquences en bioinformatique sont présentées par Abouelhoda et Ghanem (2010), qui comprennent :

• Problèmes liés aux répétitions : qui traitent des opérations sur des séquences uniques et peuvent être basés sur des méthodes de correspondance de chaînes exactes ou de correspondance de chaînes approximatives pour trouver des répétitions dispersées de longueur fixe et de longueur maximale, trouver des répétitions en tandem et trouver des sous-séquences uniques et des sous-séquences manquantes (non orthographiées).
• Problèmes d'alignement : ils traitent de la comparaison entre des chaînes en alignant d'abord une ou plusieurs séquences. Parmi les exemples de méthodes courantes, on peut citer BLAST pour comparer une séquence unique avec plusieurs séquences dans une base de données et ClustalW pour les alignements multiples. Les algorithmes d'alignement peuvent être basés sur des méthodes exactes ou approximatives et peuvent également être classés en alignements globaux, alignements semi-globaux et alignements locaux. Voir Alignement de séquences .

Certains problèmes de l'exploration de séquences se prêtent à la découverte d'ensembles d'éléments fréquents et de l'ordre dans lequel ils apparaissent. Par exemple, on recherche des règles du type « si un {client achète une voiture}, il est susceptible de {souscrire une assurance} dans un délai d'une semaine », ou dans le contexte des cours boursiers, « si {Nokia et Ericsson augmentent}, il est probable que {Motorola et Samsung augmentent} dans un délai de 2 jours ». Traditionnellement, l'exploration d'ensembles d'éléments est utilisée dans les applications marketing pour découvrir des régularités entre des éléments fréquemment co-occurrents dans des transactions importantes. Par exemple, en analysant les transactions des paniers d'achat des clients dans un supermarché, on peut produire une règle qui se lit comme suit : « si un client achète des oignons et des pommes de terre ensemble, il est susceptible d'acheter également de la viande hachée dans la même transaction ».

Une étude et une taxonomie des algorithmes clés pour l'exploration d'ensembles d'éléments sont présentées par Han et al. (2007).

Les deux techniques courantes appliquées aux bases de données de séquences pour l'exploration fréquente d'ensembles d'éléments sont l' algorithme a priori influent et la technique plus récente de croissance FP .

Avec une grande variété de produits et de comportements d'achat des utilisateurs, les étagères sur lesquelles les produits sont exposés constituent l'une des ressources les plus importantes dans l'environnement de vente au détail. Les détaillants peuvent non seulement augmenter leurs bénéfices, mais aussi réduire les coûts en gérant correctement l'allocation de l'espace en rayon et la présentation des produits. Pour résoudre ce problème, George et Binu (2013) ont proposé une approche permettant d'exploiter les habitudes d'achat des utilisateurs à l'aide de l'algorithme PrefixSpan et de placer les produits sur les étagères en fonction de l'ordre des habitudes d'achat extraites.

Les algorithmes couramment utilisés incluent :

• Algorithme GSP
• Découverte de modèles séquentiels à l'aide de classes d'équivalence (SPADE)
• Portée libre
• PréfixeSpan
• MAPres
• Seq2Pat (pour l'exploration de modèles séquentiels basée sur des contraintes)