Extraction de motifs séquentiels - Sequential pattern mining

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

Il existe plusieurs problèmes de calcul traditionnels clés abordés dans ce domaine. Celles-ci incluent la création de bases de données et d'index efficaces pour les informations de séquence, l'extraction des modèles fréquents, la comparaison des séquences pour la similitude et 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 comme l' exploration de chaînes, qui est généralement basée sur des algorithmes de traitement de chaînes et l' exploration d'ensembles d'éléments, qui est généralement basée 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 d'ordre séquentiel.

Extraction de cordes

L'exploration de chaînes traite généralement un alphabet limité pour les éléments qui apparaissent dans une séquence , mais la séquence elle-même peut être généralement 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 en chaînes 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. Au contraire, la tâche principale est de comprendre la séquence, en termes de structure et de fonction biologique . Ceci est généralement réalisé d'abord en identifiant 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 déjà étudiées. La comparaison entre les chaînes se complique lorsque des insertions , des suppressions et des mutations se produisent dans une chaîne.

Une étude et une taxonomie des algorithmes clés pour la comparaison de séquences pour la bioinformatique sont présentées par Abouelhoda & 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 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 manquantes (non épelées) sous-séquences.
  • Problèmes d'alignement : qui traitent de la comparaison entre les chaînes en alignant d'abord une ou plusieurs séquences ; des exemples de méthodes populaires incluent BLAST pour comparer une seule séquence avec plusieurs séquences dans une base de données, et ClustalW pour plusieurs alignements. 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 alignement local. Voir alignement de séquences .

Extraction d'objets

Certains problèmes dans 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 cherche des règles de la forme « si un {client achète une voiture}, il ou elle est susceptible de {acheter une assurance} dans un délai d'une semaine ", ou dans le contexte des cours des actions, "si {Nokia up et Ericsson up}, il est probable que {Motorola up et Samsung up} dans les 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 d'un client dans un supermarché, on peut produire une règle qui dit "si un client achète des oignons et des pommes de terre ensemble, il ou elle est susceptible d'acheter également de la viande de hamburger 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 qui sont appliquées aux bases de données de séquences pour l' exploration fréquente d'items sont l' algorithme apriori influent et la technique de croissance FP plus récente .

Applications

Avec une grande variété de produits et de comportements d'achat des utilisateurs, l'étagère sur laquelle les produits sont exposés est 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 également réduire leurs coûts grâce à une gestion appropriée de l'allocation de l'espace de stockage et de l'affichage des produits. Pour résoudre ce problème, George et Binu (2013) ont proposé une approche pour extraire les modèles d'achat des utilisateurs à l'aide de l'algorithme PrefixSpan et placer les produits sur des étagères en fonction de l'ordre des modèles d'achat extraits.

Algorithmes

Les algorithmes couramment utilisés incluent :

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

Voir également

Les références

Liens externes

  • SPMF comprend des implémentations open source de GSP, PrefixSpan, SPADE, SPAM et bien d'autres.