Extraction de séquences fréquentes

Le processus d’ECD

   Le processus d’extraction de connaissances dans les bases de données (ECD), présenté sur la figure 1, désigne l’ensemble des opérations qui permettent d’exploiter avec facilité et rapidité des données stockées massivement. Il s’agit d’un processus non trivial, consistant à identifier dans les données des schémas nouveaux, valides, potentiellement utiles et surtout compréhensibles et utilisables [FPSS96a]. Le processus d’ECD peut avoir deux objectifs, soit vérifier les hypothèses d’un utilisateur, soit découvrir de nouveaux motifs. Un motif, ou schéma, est une expression dans un langage spécifique qui décrit un sous-ensemble de données ou un modèle applicable à ce sous-ensemble [FPSS96b]. Ce processus comporte quatre étapes principales : (1) la sélection, (2) la préparation des données, (3) la fouille de données et (4) l’interprétation. Les deux premières étapes, sélection et pré-traitement (ou préparation), regroupent les différentes transformations que les données doivent subir avant d’être disponibles pour l’analyse : le nettoyage, l’intégration des sources multiples, la transformation des données (agrégation, normalisation, …) et enfin la réduction des dimensions d’analyse [HK00]. Ces transformations dépendent du type de fouille à entreprendre. Le but de ces étapes est de construire une base de données contenant un ensemble d’enregistrements (ou lignes, n-uplets, tuples, exemples,transactions), décrits en fonction d’attributs (ou colonnes, items). Par exemple, on considère une base de données de grande surface où chaque ligne correspond à un achat, identifié par une date et un client et où les colonnes correspondent aux produits achetés. C’est lors du nettoyage que les données erronées ou bruitées sont identifiées, corrigées si possible ou supprimées et que les inconsistances sont résolues [BA96]. C’est également lors de cette étape que les valeurs manquantes sont prises en compte si elles ne peuvent être gérées lors de la fouille de données. Pour réaliser cette préparation des données et choisir la bonne technique de fouille, il est bien entendu nécessaire de bien connaître les données ainsi que les besoins de l’utilisateur. Une fois mises en forme, les données sont traitées par l’algorithme d’extraction, c’est l’étape de fouille de données. Cette phase consiste à utiliser des méthodes d’analyse de données et des algorithmes de recherche qui permettent d’obtenir, dans un temps acceptable, un certain nombre de schémas et de motifs caractéristiques des données [FPSS96b]. Il s’agit d’un processus interactif d’analyse d’un grand ensemble de données, destiné à extraire des connaissances exploitables. L’objectif de l’extraction de connaissances est l’extraction de motifs, c’est-à-dire la recherche d’un modèle, d’une structure ou encore tout autre description de haut niveau, caractérisant les données. Ce modèle peut être prédictif, dans ce cas, les motifs trouvés ont pour but de prédire des comportements futurs, ou bien il peut être descriptif, les motifs extraits ont alors pour but de décrire les données de façon compréhensible et intelligible pour l’utilisateur. Selon les objectifs que l’on souhaite remplir, les algorithmes de fouilles employés pour analyser les données seront différents. Ces différentes approches sont décrites dans la sous-section 1.2. Enfin, pour déterminer le niveau d’intérêt des découvertes réalisées lors de la fouille de données, on réalise une interprétation des résultats obtenus. Une fois cette interprétation terminée, l’utilisateur peut enfin savoir quels schémas intéressants se cachent dans la quantité de données qu’il a stockées. Pour cela, des mesures quantitatives et qualitatives sont dénies, an d’évaluer les motifs extraits et d’aider à leur utilisation.

La théorie des sous-ensembles flous en fouille de données

   Le but de l’extraction de connaissances est d’extraire des schémas et des modèles intelligibles pour l’utilisateur humain. Loin d’être binaire, la pensée humaine n’est pas toujours aisément modélisable par un programme informatique et parfois des outils permettant de raisonner avec des termes nuancés sont très utiles [BM99]. Par ailleurs, les bases de données du monde réel contiennent souvent de nombreuses imperfections : des informations non renseignées (incomplétudes), des données erronées (incertitudes) ou encore des données imprécises. Il est important de proposer des techniques permettant de détecter ces données an de les corriger ou des méthodes de fouille dont les résultats restent ables malgré les différentes imperfections des données exploitées. C’est pourquoi la théorie des sous-ensembles ous [Zad65] (annexe A) a largement été employée et de nombreux algorithmes de data mining ont désormais leurs extensions floues. Ils permettent ainsi de répondre à des problématiques plus larges et souvent de faciliter l’interprétation des résultats par l’utilisateur final [MPM02] en fournissant des schémas approximatifs robustes aux imperfections et utilisant des termes linguistiques. Plus généralement, les sous-ensembles flous sont utilisés pour gérer les problèmes liés à : l’interprétabilité et la compréhensibilité des schémas extraits, l’incomplétude et le bruit dans les données, la fusion des sources d’information de types variés, les interactions humaines. L’utilisation de la logique floue permet également dans certains cas de fournir des solutions approximatives plus rapidement. Enfin, elle autorise le traitement simultané de plusieurs types de variables [Yag96, Ped98] ou encore de requêtes flexibles aussi bien dans un contexte de base de données relationnelles que multidimensionnelles [Lau02]. Parmi les techniques de fouille de données utilisant la logique floue, on compte des méthodes de classication comme, par exemple, les arbres de décision ous [MBM99, OW03, HT03], diérents algorithmes de clustering dont le plus connu est l’algorithme fuzzy c-means [Dun73, Bez81, BHLK06]. Enfin, des techniques ont été proposées pour l’extraction de règles d’association floues [AC98, FWS+98, KFW98, CWK00, Gye00a, DSV02, HLW03].

Diérents types de bases de données

   Nous avons vu précédemment que le choix d’une technique de fouille de données dépend des objectifs de l’extraction de connaissances. Mais certaines techniques sont également plus adaptées à certaines données, comportant des informations caractéristiques. Il est donc important d’identifier le type de base de données dont on dispose. Les bases de données relationnelles regroupent un ensemble de données stockées dans des tables et décrites par un ensemble d’attributs. Généralement, la fouille dans de telles bases a pour but de découvrir des schémas et des tendances. Les bases de données de transactions, quant à elles, sont une collection d’enregistrements de transactions assimilables à des achats de supermarché. L’analyse de ces données consiste alors à trouver des corrélations entre les items des transactions enregistrées. Dans les bases de données temporelles, enfin, les données relationnelles sont associées à un attribut temporel. Les algorithmes de fouille de données utilisés ont alors pour objectif d’extraire des motifs périodiques, des épisodes ou encore des motifs séquentiels [ZB03, JKK99, LC92]. Les bases de séquences de données sont des bases de données temporelles particulières. Il s’agit en fait de bases de données relationnelles ou de transactions dans lesquelles les enregistrements peuvent être organisés en séquences d’évènements ordonnés selon une notion de temps, concrète ou non (e.g. achats de clients dans un supermarché, apparition de mots ou de concepts dans un texte, logs de navigation Internet) [HK00]. On peut y rechercher diérents types de motifs : des schémas d’évolution des attributs au cours du temps, an d’analyser des tendances, des séquences qui ne difièrent que légèrement les unes des autres, pour déceler des similitudes, des motifs séquentiels, an de trouver des relations entre les occurrences d’évènements séquentiels et l’ordre spécifique qui peut exister entre ces apparitions, des motifs périodiques, an de caractériser des successions d’évènements récurrents et répétés dans les séries temporelles.

Inférence statistique

   [AL99] introduit une nouvelle définition des règles d’association, basée sur une théorie d’inférence statistique. Cette définition est destinée à favoriser l’extraction de règles extraordinaires et correspondant à des phénomènes intéressants. Cette approche part de l’hypothèse que l’objectif d’une règle d’association est de trouver des phénomènes intéressants. Ainsi, an de déceler de tels phénomènes, cette proposition se base sur l’utilisation de la distribution des valeurs des attributs quantitatifs, ainsi que sur une généralisation statistique de la définition catégorielle. Exemple 1.1. Une règle extraite selon cette méthode pourrait être : sexe = femme ⇒ salaire : moyenne = 8$/h, alors que si l’ensemble des salariés est considéré, la moyenne des salaires horaires est en fait de 9$. Cette règle est donc significative et atypique. Toutefois, la forme de ces règles et leur construction limitent leurs champs d’application. En effet, l’antécédent des règles extraites donne la description d’un sous-ensemble de la population, le conséquent décrit un comportement intéressant spécifique de la population correspondant à la partie gauche, sous la forme d’une mesure statistique portant sur un attribut : la moyenne, la variance ou encore l’écart-type.

Motifs séquentiels flous

   Les principes utilisés lors de la recherche de motifs séquentiels flous sont similaires à ceux dénis pour les règles d’association floues. Plusieurs propositions ont été formulées dans ce sens, an d’extraire des motifs séquentiels à partir de données quantitatives [HLW01, CTCH01, CH02, HCTS03, HTC04, SG05]. Toutes ces approches sont fondées sur le même principe. An d’extraire les motifs, les univers de quantités de chaque attribut quantitatif sont partitionnés en plusieurs sous-ensembles flous. Le jeu de données est ensuite converti en une base de degrés d’appartenance. Ces approches diffèrent ensuite dans la manière de calculer le support d’une séquence. Cette phase est suffisante pour la plupart des algorithmes. Cependant, la première approche proposée pour la découverte de motifs séquentiels flous, [HLW01], opère une seconde étape avant la fouille proprement dite. En effet, an de minimiser le nombre d’items à traiter et ainsi réduire le temps d’extraction, l’algorithme sélectionne les items flous les plus significatifs : pour chaque item, seul le sous-ensemble ou dont la cardinalité (déterminée par Σ-comptage) est la plus élevée sur toute la base est conservé. Par exemple, si on considère un item X pouvant être associé à trois sous ensembles flous a, b et c, un seul des trois items flous (X, a), (X, b) ou (X, c) sera conservé. Une telle sélection nous semble réductrice et peut conduire à la découverte de motifs erronés. Les conséquences de cette stratégie sur les motifs séquentiels découverts sont mises en évidence dans les expérimentations présentées dans le chapitre 3. La seconde approche [CTCH01, HCTS03, HTC04, CH02], est très formelle. Elle n’introduit qu’un algorithme dont les structures de données sous-jacentes ne sont pas décrites. Aucune expérimentation n’est présentée. Par ailleurs, le formalisme et les notations utilisées pour dénir la fréquence d’un itemset ou ou d’une séquence floue sont plutôt ambigus, alors que la notion d’ordre est fondamentale pour la recherche de séquences fréquentes. Enfin, à l’instar des approches proposées pour les règles d’association floues, aucun de ces travaux ne considère les différents niveaux d’information qui peuvent être obtenus en considérant un cadre global pour la découverte de motifs séquentiels flous, ainsi que les diérents niveaux de fuzzication qui peuvent être utilisés pour évaluer la fréquence d’une séquence. C’est également le cas de la proposition la plus récente, [CH06], qui propose un algorithme efficace basé sur les mêmes principes que les travaux précédents.

Table des matières

Remerciements
Sommaire
Introduction
1 Extraction de Connaissances dans les grandes bases de Données
1.1 Le processus d’ECD
1.2 L’étape de fouille de données 
1.3 La théorie des sous-ensembles flous en fouille de données 
2 Découverte de motifs séquentiels 
2.1 Différents types de bases de données 
2.2 Un détour par les règles d’association 
2.3 Découverte de motifs séquentiels 
3 Objectifs et contributions
I – Motifs séquentiels et données quantitatives
Introduction
1 Règles d’association et données quantitatives 
1.1 Règles d’association pour les valeurs quantitatives
1.1.1 Intervalles
1.1.2 Inférence statistique
1.1.3 Conversion booléenne
1.1.4 Intervalles flous
1.2 Motifs séquentiels pour les valeurs quantitatives
1.2.1 Intervalles
1.2.2 Motifs séquentiels flous
1.3 Objectifs 
2 Un cadre pour la recherche de motifs séquentiels flous 
2.1 Motifs séquentiels flous : définitions
2.1.1 Fuzzification des définitions classiques
2.1.2 Préparation de la base de données
2.1.3 Plusieurs comptages
2.1.4 plusieurs fréquences
2.2 Calcul du support d’une séquence 
2.2.1 SpeedyFuzzy et MiniFuzzy
2.2.2 TotallyFuzzy
2.3 SMT-Fuzzy : Extraction de motifs séquentiels flous
2.3.1 Algorithme
2.3.2 Trois niveaux d’information
3 Expérimentations 
3.1 Données synthétiques
3.1.1 Algorithmes ous vs. PSP
3.1.2 TotallyFuzzy vs. Hong et al
3.1.3 Opérateurs
3.1.4 Réponse aux variations du paramètre ω
3.2 Données réelles
3.2.1 Web Access Log Mining
3.2.2 Composition des noms de marques déposées
II – Contraintes de temps étendues 
Introduction
1 Motifs séquentiels et contraintes de temps 
1.1 Contraintes pour la recherche de séquences 
1.2 Motifs séquentiels généralisés
1.2.1 Généralisation des items
1.2.2 Généralisation de la notion de transaction
1.2.3 Prise en compte des contraintes de temps
1.3 Contraintes temporelles pour les motifs séquentiels 
1.4 Algorithmes pour les contraintes de temps 
1.5 Objectifs de notre contribution 
2 Contraintes de temps étendues 
2.1 Principes et notations
2.1.1 Principe général
2.1.2 Valeurs limites utiles
2.1.3 Notations
2.2 Extension des contraintes de temps 
2.2.1 Extension de windowSize
2.2.2 Extension de maxgap
2.2.3 Extension de mingap
2.3 Précision temporelle d’une séquence 
3 GETC : Graph for Extended Time Constraints 
3.1 Construction du graphe de séquences
3.1.1 Construction des sommets
3.1.2 Construction des arcs
3.1.3 Suppression des inclusions
3.2 Calcul de la précision temporelle
3.2.1 Valuation des graphes de séquences
3.2.2 Calcul de la précision temporelle des séquences fréquentes
3.2.3 Un exemple
3.3 Expérimentations
3.3.1 Données synthétiques
3.3.2 Contraintes étendues pour la description d’accès Web atypique
III – Motifs séquentiels et données incomplètes 
Introduction
1 Traitement des valeurs manquantes et fouille de données 
1.1 Données incomplètes et valeurs manquantes 
1.1.1 Dénitions
1.1.2 Diérents types de valeurs manquantes
1.1.3 Les données manquantes dans le processus d’ECD
1.2 Valeurs manquantes en classication et segmentation
1.2.1 Des valeurs manquantes à chaque étape de l’élaboration d’un classieur
1.2.2 Clustering sur des données incomplètes
1.3 Règles d’association, valeurs manquantes et complétion
1.3.1 ∼AR
1.3.2 Robust Association Rules
1.3.3 Règles d’association et complétion des enregistrements
1.4 Motifs séquentiels et valeurs manquantes 
1.4.1 Motivations
1.4.2 Objectifs
2 Traitement par désactivation 
2.1 SPoID : désactivation des séquences de données incomplètes 
2.1.1 Principe
2.1.2 Fréquence et représentativité
2.1.3 Seuil de représentativité et marge d’erreur
2.2 Mise en oeuvre
2.2.1 Illustration
2.2.2 Algorithme
2.3 Expérimentations 
3 Traitement par estimation 
3.1 ApSPoID : estimation des valeurs possibles dans les données incomplètes 
3.1.1 Principe
3.1.2 Détermination des distributions de valeurs pour chaque valeur manquante
3.2 Mise en oeuvre 
3.2.1 Illustration
3.2.2 Algorithme
3.3 Expérimentations 
3.3.1 ApSPoID vs. SPoID
3.3.2 Choix de la distribution
4 Processus de complétion des valeurs manquantes 
4.1 Motifs séquentiels pour compléter des valeurs manquantes
4.1.1 Apport de l’information temporelle
4.1.2 Approche proposée
4.1.3 Un exemple
4.2 Expérimentations
4.2.1 Qualité de la complétion selon l’incomplétude de la base
4.2.2 Qualité de la complétion selon la fréquence des motifs
4.2.3 Conclusion
Bilan, perspectives et conclusion 
1 Travail réalisé 
1.1 Données numériques
1.2 Contraintes de temps étendues 
1.3 Séquences de données incomplète
1.4 Synthèse
2 Temporalité, séquentialité, causalité 
2.1 Règles d’association séquentielles
2.2 Séquences à forte causalité : motifs conséquentiels 
3 Schémas nouveaux, valides et potentiellement utiles 
4 Conclusion 
Bibliographie
Publications dans le cadre de cette thèse
Annexes 
A Quelques éléments de la théorie des sous-ensembles ous 
B SpeedyFuzzy, MiniFuzzy et TotallyFuzzy 
B.1 L’algorithme SpeedyFuzzy
B.2 L’algorithme MiniFuzzy
B.3 L’algorithme TotallyFuzzy
C Complétude de GETC : Démonstrations 
D Types de contraintes pour la recherche de motifs fréquents 
D.1 Diérents types de contraintes
D.2 Classes des contraintes
Résumé

Télécharger le rapport complet