Une masse de données importante est collectée chaque jour par les gestionnaires de site internet sur les visiteurs qui accèdent à leurs services. La collecte de ces données a pour objectif de mieux comprendre les usages et d'acquérir des connaissances sur le comportement des visiteurs. A partir de ces connaissances, les gestionnaires de site peuvent décider de modifier leur site ou proposer aux visiteurs du contenu personnalisé. Cependant, le volume de données collectés ainsi que la complexité de représentation des interactions entre le visiteur et le site internet nécessitent le développement de nouveaux outils de fouille de données. Dans cette thèse, nous avons exploré l’utilisation des méthodes d’alignement de séquences pour l'extraction de connaissances sur l'utilisation de site Web (web mining). Ces méthodes sont la base du regroupement automatique d’internautes en segments, ce qui permet de découvrir des groupes de comportements similaires. De plus, nous avons également étudié comment ces groupes pouvaient servir à effectuer de la prédiction et la recommandation de pages. Ces thèmes sont particulièrement importants avec le développement très rapide du commerce en ligne qui produit un grand volume de données (big data) qu’il est impossible de traiter manuellement. / This thesis explored the application of sequence alignment in web usage mining, including user clustering and web prediction and recommendation.This topic was chosen as the online business has rapidly developed and gathered a huge volume of information and the use of sequence alignment in the field is still limited. In this context, researchers are required to build up models that rely on sequence alignment methods and to empirically assess their relevance in user behavioral mining. This thesis presents a novel methodological point of view in the area and show applicable approaches in our quest to improve previous related work. Web usage behavior analysis has been central in a large number of investigations in order to maintain the relation between users and web services. Useful information extraction has been addressed by web content providers to understand users’ need, so that their content can be correspondingly adapted. One of the promising approaches to reach this target is pattern discovery using clustering, which groups users who show similar behavioral characteristics. Our research goal is to perform users clustering, in real time, based on their session similarity.

Avec la croissance importante du besoin d'analyser une grande masse de données structurées tels que les composés chimiques, les structures de protéines ou même les réseaux sociaux, la fouille de sous-graphes fréquents est devenue un défi réel en matière de fouille de données. Ceci est étroitement lié à leur nombre exponentiel ainsi qu'à la NP-complétude du problème d'isomorphisme d'un sous-graphe général. Face à cette complexité, et pour gérer cette taille importante de l'espace de recherche, les méthodes classiques de fouille de graphes ont exploré des heuristiques de recherche basées sur le support, le langage de description des exemples (limitation aux chemins, aux arbres, etc.) ou des hypothèses (recherche de sous-arborescence communes, de chemins communs, etc.). Dans le cadre de cette thèse, nous nous basons sur une méthode d'appariement de graphes issue du domaine de la programmation par contraintes, nommée AC-projection, qui a le mérite d'avoir une complexité polynomiale. Nous introduisons des approches de fouille de graphes permettant d'améliorer les approches existantes pour ce problème. En particulier, nous proposons deux algorithmes, FGMAC et AC-miner, permettant de rechercher les sous-graphes fréquents à partir d'une base de graphes. Ces deux algorithmes profitent, différemment, des propriétés fortes intéressantes de l'AC-projection. En effet, l'algorithme FGMAC adopte un parcours en largeur de l'espace de recherche et exploite l'approche par niveau introduite dans Apriori, tandis que l'algorithme AC-miner parcourt l'espace en profondeur par augmentation de motifs, assurant ainsi une meilleure mise à l'échelle pour les grands graphes. Ces deux approches permettent l'extraction d'un type particulier de graphes, il s'agit de celui des sous-graphes AC-réduits fréquents. Dans un premier temps, nous prouvons, théoriquement, que l'espace de recherche de ces sous-graphes est moins important que celui des sous-graphes fréquents à un isomorphisme près. Ensuite, nous menons une série d'expérimentations permettant de prouver que les algorithmes FGMAC et AC-miner sont plus efficients que ceux de l'état de l'art. Au même temps, nous prouvons que les sous-graphes AC-réduits fréquents, en dépit de leur nombre sensiblement réduit, ont le même pouvoir discriminant que les sous-graphes fréquents à un isomorphisme près. Cette étude est menée en se basant sur une évaluation expérimentale de la qualité des sous-graphes AC-réduits fréquents dans un processus de classification supervisée de graphes. / With the important growth of requirements to analyze large amount of structured data such as chemical compounds, proteins structures, social networks, to cite but a few, graph mining has become an attractive track and a real challenge in the data mining field. Because of the NP-Completeness of subgraph isomorphism test as well as the huge search space, frequent subgraph miners are exponential in runtime and/or memory use. In order to alleviate the complexity issue, existing subgraph miners have explored techniques based on the minimal support threshold, the description language of the examples (only supporting paths, trees, etc.) or hypothesis (search for shared trees or common paths, etc.). In this thesis, we are using a new projection operator, named AC-projection, which exhibits nice complexity properties as opposed to the graph isomorphism operator. This operator comes from the constraints programming field and has the advantage of a polynomial complexity. We propose two frequent subgraph mining algorithms based on the latter operator. The first one, named FGMAC, follows a breadth-first order to find frequent subgraphs and takes advantage of the well-known Apriori levelwise strategy. The second is a pattern-growth approach that follows a depth-first search space exploration strategy and uses powerful pruning techniques in order to considerably reduce this search space. These two approaches extract a set of particular subgraphs named AC-reduced frequent subgraphs. As a first step, we have studied the search space for discovering such frequent subgraphs and proved that this one is smaller than the search space of frequent isomorphic subgraphs. Then, we carried out experiments in order to prove that FGMAC and AC-miner are more efficient than the state-of-the-art algorithms. In the same time, we have studied the relevance of frequent AC-reduced subgraphs, which are much fewer than isomorphic ones, on classification and we conclude that we can achieve an important performance gain without or with non-significant loss of discovered pattern's quality.

Le nombre d'accès aux pages Web ne cesse de croître. Le Web est devenu l'une des plates-formes les plus répandues pour la diffusion et la recherche d'information. Par conséquence, beaucoup d'opérateurs de sites Web sont incités à analyser l'usage de leurs sites afin d'améliorer leur réponse vis-à-vis des attentes des internautes. Or, la manière dont un site Web est visité peut changer en fonction de divers facteurs. Les modèles d'usage doivent ainsi être mis à jour continuellement afin de refléter fidèlement le comportement des visiteurs. Ceci reste difficile quand la dimension temporelle est négligée ou simplement introduite comme un attribut numérique additionnel dans la description des données. C'est précisément sur cet aspect que se focalise la présente thèse. Pour pallier le problème d'acquisition des données réelles d'usage, nous proposons une méthodologie pour la génération automatique des données artificielles permettant la simulation des changements. Guidés par les pistes nées des analyses exploratoires, nous proposons une nouvelle approche basée sur des fenêtres non recouvrantes pour la détection et le suivi des changements sur des données évolutives. Cette approche caractérise le type de changement subi par les groupes de comportement (apparition, disparition, fusion, scission) et applique deux indices de validation basés sur l'extension de la classification pour mesurer le niveau des changements repérés à chaque pas de temps. Notre approche est totalement indépendante de la méthode de classification et peut être appliquée sur différents types de données autres que les données d'usage. Des expérimentations sur des données artificielles ainsi que sur des données réelles issues de différents domaines (académique, tourisme et marketing) ont été réalisées pour l'évaluer l'efficacité de l'approche proposée.

Ces dernières années ont vu une croissance phénoménale dans la production et la diffusion des données spatiales de sources aussi variées qu'hétérogènes. Cela a généré des besoins d'intégration dans des entrepôts de données et des perspectives d'analyse exploratoire et de fouille de données spatiales et spatiotemporelles. Nos travaux se placent dans ce contexte visant l'analyse et l'extraction des connaissances depuis les bases de données spatiotemporelles. Ils traitent différents aspects allant de la modélisation avancée des données spatiales, à la fouille de ces données en passant par leur intégration dans un entrepôt, l'optimisation des requêtes et l'analyse en ligne. Ainsi, nous décrivons nos approches pour la modélisation 3D, puis pour la modélisation spatiotemporelle d'objets mobiles. Ensuite, l'intégration de données spatiales est traitées selon deux aspects : l'intégration de formats et l'intégration de données par l'appariement géométrique. Une architecture d'entrepôt de données spatiales basée sur les standards XML et GML est proposée, puis dotée d'une technique d'optimisation de requêtes spatiales basée sur un cache sémantique. L'exploration des données spatiotemporelles a donné lieu à des solutions originales extension de l'OLAP. Enfin, différentes approches sont proposées pour la fouille de données spatiales. Nous avons ouvert le spectre de nos recherches à la fouille d'autres données complexes, telles que les données séquentielles et textuelles. Ces travaux ainsi que les développements futurs sont exposés dans ce mémoire.

Le travail réalisé dans le cadre de cette thèse concerne l'extraction de connaissances dans des données transactionnelles.<br />L'analyse de telles données est souvent contrainte par la définition d'un support minimal utilisé pour filtrer les connaissances non intéressantes.<br />Les experts des données ont souvent des difficultés pour déterminer ce support.<br />Nous avons proposé une méthode permettant de ne pas fixer un support minimal et fondée sur l'utilisation de mesures de qualité.<br />Nous nous sommes focalisés sur l'extraction de connaissances de la forme "règles d'association".<br />Ces règles doivent vérifier un ou plusieurs critères de qualité pour être considérées comme intéressantes et proposées à l'expert.<br />Nous avons proposé deux mesures de qualité combinant différents critères et permettant d'extraire des règles intéressantes.<br /><br />Nous avons ainsi pu proposer un algorithme permettant d'extraire ces règles sans utiliser la contrainte du support minimal.<br />Le comportement de notre algorithme a été étudié en présence de données bruitées et nous avons pu mettre en évidence la difficulté d'extraire automatiquement des connaissances fiables à partir de données bruitées.<br />Une des solutions que nous avons proposée consiste à évaluer la résistance au bruit de chaque règle et d'en informer l'expert lors de l'analyse et de la validation des connaissances obtenues.<br /><br />Enfin, une étude sur des données réelles a été effectuée dans le cadre d'un processus de fouille de textes.<br />Les connaissances recherchées dans ces textes sont des règles d'association entre des concepts définis par l'expert et propres au domaine étudié.<br />Nous avons proposé un outil permettant d'extraire les connaissances et d'assister l'expert lors de la validation de celles-ci.<br />Les différents résultats obtenus montrent qu'il est possible d'obtenir des connaissances intéressantes à partir de données textuelles en minimisant la sollicitation de l'expert dans la phase d'extraction des règles d'association.

Dans un contexte riche d'information, un système de recherche d'information doit être capable de trouver les meilleurs résultats possibles dans un océan d'information. Notre étude s'intéresse aux connaissances qui peuvent être extraites du contenu textuel des documents en associant la finesse d'analyse d'une approche linguistique (extraction et structuration) à la capacité d'une approche statistique de traiter de gros corpus. L'approche statistique se base sur la fouille de données textuelles et principalement la technique de règles d'association. L'approche linguistique se base sur les syntagmes nominaux que nous considérons comme des entités textuelles plus susceptibles de représenter l'information contenue dans le texte que les termes simples. Elle explicite les contraintes linguistiques nécessaires à l'extraction des syntagmes nominaux et défini les rapports syntagmatiques entre les composantes d'un syntagme nominal. Ces relations syntagmatiques sont exploitées pour la structuration des syntagmes nominaux. Une mesure, appelée ``quantité d'information'', est proposée pour évaluer le pouvoir évocateur de chaque syntagme nominal, filtrer et comparer les syntagmes nominaux. Le modèle proposé démontre que la combinaison d'une approche statistique et d'une approche linguistique affine les connaissances extraites et améliore les performances d'un système de recherche d'information.

Au cours de ces dernières années, un nouvel environnement s'est développé dans lequel les données doivent être collectées et traitées instantanément dès leur arrivée. La gestion de cette volumétrie nécessite la mise en place d'un nouveau modèle et de nouvelles techniques de traitements de l'information. Il s'agit du traitement des flux de données. Ces derniers ont la particularité d'être continus, évolutifs, volumineux et ne peuvent être stockés, dans leur intégralité, en tant que données persistantes. Plusieurs travaux de recherche se sont intéressés à cette problématique ce qui a engendré l'apparition des systèmes de gestion de flux de données (SGFD). Ces systèmes permettent d'exprimer des requêtes continues qui s'évaluent au fur et à mesure sur un flux ou sur des fenêtres (sous ensembles finis du flux). Toutefois, dans certaines applications, de nouveaux besoins peuvent apparaître après le passage des données. Dans ce cas, le système ne peut répondre aux requêtes posées car toutes les données n'appelant aucun traitement sont définitivement perdues. Il est ainsi nécessaire de conserver un résumé du flux de données. De nombreux algorithmes de résumé ont été développés. Le choix d'une méthode de résumé particulière dépend de la nature des données à traiter et de la problématique à résoudre. Dans ce manuscrit, nous nous intéressons en premier lieu à l'élaboration d'un résumé généraliste permettant de créer un compromis entre la vitesse de construction du résumé et la qualité du résumé conservé. Nous présentons une nouvelle approche de résumé qui se veut performance face à des requêtes portant sur des données du passé lointain. Nous nous focalisons par la suite sur l'exploitation et l'accès aux évènements du flux conservés dans ces résumés. Notre objectif consiste à intégrer les structures de résumés généralistes dans l'architecture des SGFD existantes de façon à étendre le champ de requêtes possibles. A cet effet, l'évaluation des requêtes qui font appel aux données du passé lointain d'un flux (i.e. données expirées de la mémoire du SGFD) serait possible au même titre que les requêtes posées sur le passé proche d'un flux de données. Nous présentons deux approches permettant d'atteindre cet objectif. Ces approches se différencient par le rôle que détient le module de résumé lors de l'évaluation d'une requêtes.

Les séquences temporelles d'images présentent une quantité d'information bien plus importante que des images individuelles. En effet, la prise en compte du temps accroit considérablement le nombre d'états possibles ce qui se traduit par une quantité d'information plus importante (au sens entropie). Grâce à l'agilité des satellites de nouvelle génération et à leur utilisation dans des constellations, des séquences temporelles d'images satellitaires, STIS, vont maintenant être accessibles à haute résolution. Ces données sont extrêmement riches, mais en contrepartie, elles sont complexes et difficiles à interpréter manuellement. Des méthodes d'analyse automatique sont donc requises. Les STIS à haute résolution (STISHR) se distinguent des autres types de séquences existantes par la nature des changements qu'elles présentent. En effet, contrairement aux STIS à basse résolution, les STISHR contiennent des objets. Afin de tenir compte de cette particularité, une méthode d'analyse orientée objet doit donc être utilisée. De telles méthodes existent dans le domaine de la vidéo. Cependant, les objets des STISHR peuvent subir des changements radiométriques, par exemple liés à la croissance des plantes, alors que la radiométrie des objets de vidéo est généralement supposée invariante. Nous devons donc concevoir une méthode d'analyse orientée objet adaptée à la STISHR. Par ailleurs, l'échantillonnage temporel des STISHR est irrégulier et généralement sous-échantillonné par rapport aux phénomènes observables à ces résolutions spatiales. De plus, du point de vue du satellite, aux évolutions radiométriques propres aux objets de la scène se rajoutent les évolutions radiométriques liées à l'épaisseur atmosphérique. Néanmoins, hormis de faibles erreurs de recalage géométrique, la STISHR présente une redondance temporelle dans la forme des objets. Ainsi, une construction est généralement pérenne et une zone cultivable est rarement modifiée. Nous proposons donc une méthode d'analyse de la STISHR basée objet de façon à exploiter d'une part la redondance radiométrique intra objets spatiaux, et d'autre part, la redondance temporelle de forme entre ces objets. Une étude phénoménologique de la dynamique de la scène et de la STISHR nous permet d'identifier les caractéristiques d'une représentation adaptée à la description de ses changements : il s'agit d'un graphe dont les noeuds sont des objets spatiaux reliés par des arcs exprimant leur dépendance temporelle. Le calcul de ce graphe est cependant un problème difficile, et nous proposons d'en calculer une approximation. Cette approximation est calculée en deux temps. Dans un premier temps, on considère une approximation forte sur les dépendances temporelles afin de faciliter la détermination des régions spatiales. Celles-ci sont extraites grâce à un algorithme de segmentation exploitant conjointement les deux types de redondances disponibles : l'homogénéité radiométrique spatiale, et la redondance géométrique temporelle. Les noeuds du graphe ainsi déterminés, on relaxe l'approximation sur les dépendances temporelles de façon à obtenir une estimation plus fine du graphe. Nous proposons ensuite deux utilisations de ce graphe. L'une exploite ses caractéristiques structurelles telles que la valence des noeuds afin de détecter les changements géométriques. L'autre, utilise une version attribuée par des propriétés radiométriques du graphe pour mettre en évidence des comportements fréquents.

Les domaines de la médecine, du web, du commerce ou de la nance génèrent et stockent de grandes masses d'information sous la forme de séquences d'événements. Ces archives représentent des sources d'information très riches pour des analystes avides d'y découvrir des perles de connaissance. Par exemple, les biologistes cherchent à découvrir les facteurs de risque d'une maladie en analysant l'historique des patients, les producteurs de contenu web et les bureaux de marketing examinent les habitudes de consommation des clients et les opérateurs boursiers suivent les évolutions du marché pour mieux l'anticiper. Cependant, ces applications requièrent l'exploration de séquences d'événements très volumineuses, par exemple, la nance génère quotidiennement des millions d'événements, où les événements peuvent être décrits par des termes extraits de riches contenus textuels. La variabilité des descripteurs peut alors être très grande. De ce fait, découvrir des connaissances non triviales à l'aide d'approches classiques de fouille de données dans ces sources d'information prolixes est un problème dicile. Une étude récente montre que les approches classiques de fouille de données peuvent tirer prot de formes condensées de ces données, telles que des résultats d'agrégation ou encore des résumés. La connaissance ainsi extraite est qualiée de connaissance d'ordre supérieur. À partir de ce constat, nous présentons dans ces travaux le concept de résumé de séquence d'événements dont le but est d'amener les applications dépendantes du temps à gagner un facteur d'échelle sur de grandes masses de données. Un résumé s'obtient en transformant une séquence d'événements où les événements sont ordonnés chronologiquement. Chaque événement est précisément décrit par un ensemble ni de descripteurs symboliques. Le résumé produit est alors une séquence d'événements, plus concise que la séquence initiale, et pouvant s'y substituer dans les applications. Nous proposons une première méthode de construction guidée par l'utilisateur, appelée TSaR. Il s'agit d'un processus en trois phases : i) une généralisation, ii) un regroupement et iii) une formation de concepts. TSaR utilise des connaissances de domaine exprimées sous forme de taxonomies pour généraliser les descripteurs d'événements. Une fenêtre temporelle est donnée pour contrôler le processus de regroupement selon la proximité temporelle des événements. Dans un second temps, pour rendre le processus de résumé autonome, c'est- à-dire sans paramétrage, nous proposons une redénition du problème de résumé en un nouveau problème de classication. L'originalité de ce problème de classication tient au fait que la fonction objective à optimiser dépend simultanément du contenu des événements et de leur proximité dans le temps. Nous proposons deux algorithmes gloutons appelés G-BUSS et GRASS pour répondre à ce problème. Enn, nous explorons et analysons l'aptitude des résumés de séquences d'événements à contribuer à l'extraction de motifs séquentiels d'ordre supérieur. Nous analysons les caractéristiques des motifs fréquents extraits des résumés et proposons une méthodologie qui s'appuie sur ces motifs pour en découvrir d'autres, à granularité plus ne. Nous évaluons et validons nos approches de résumé et notre méthodologie par un ensemble d'expériences sur un jeu de données réelles extraites des archives d'actualités nancières produites par Reuters.

Les travaux présentés dans le cadre de cette Habilitation à Diriger des Recherches, qui se situent au carrefour de l'informatique et de la linguistique, s'intéressent au traitement de l'écrit. Ils s'articulent autour de deux axes de recherche, celui de la fouille terminologique multilingue et celui de la reconnaissance de l'écriture manuscrite en ligne. Dans un premier temps, notre étude est consacrée à la fouille terminologique multilingue. Nous commençons par rappeler les fondements théoriques en acquisition lexicale multilingue, qui s'inscrivent dans l'héritage de la sémantique distributionnelle de Harris. Nous présentons ensuite les travaux réalisés en acquisition de lexiques bilingues à partir de corpus comparables. Nous décrivons notamment la méthode par similarité interlangue proposée pour l'alignement de termes complexes et la plate-forme informatique associée. À la lumière des nombreux résultats que nous avons engrangés dans ce champ de recherche, nous précisons les apports et limites des différentes approches utilisées. Dans un deuxième temps, nous présentons les différentes facettes de la reconnaissance de l'écriture manuscrite en ligne auxquelles nous nous sommes intéressés et les modèles développés. Ces travaux, qui se situent au niveau de la modélisation du langage naturel, visent à concevoir des modèles de langage adaptés à la reconnaissance de documents dénotant un « écrit standard » (où un stylo numérique vient remplacer la saisie sur un clavier numérique) ou un « écrit déviant » (où un stylo numérique s'offre comme une nouvelle alternative pour l'écriture de SMS). Nous présentons les modèles développés et les résultats obtenus. Nous revenons aussi sur l'importance et la difficulté de concevoir des ressources adaptées à la prise en compte de ces différents écrits. Dans un dernier temps, qui constitue le trait d'union entre nos deux axes de recherche, nous indiquons la synergie possible entre les approches et ressources déployées. En particulier, nous montrons que les méthodes probabilistes ne sont plus une alternative aux systèmes à base de règles, mais bien complémentaires et que les ressources exploitées doivent être adaptées à la tâche visée.