Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal.

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Le web est maintenant devenu une importante source d’information et de divertissement pour un grand nombre de personnes et les techniques pour accéder au contenu désiré ne cessent d’évoluer. Par exemple, en plus de la liste de pages web habituelle, certains moteurs de recherche présentent maintenant directement, lorsque possible, l’information recherchée par l’usager. Dans ce contexte, l’étude des requêtes soumises à ce type de moteur de recherche devient un outil pouvant aider à perfectionner ce genre de système et ainsi améliorer l’expérience d’utilisation de ses usagers. Dans cette optique, le présent document présentera certaines techniques qui ont été développées pour faire l’étude des requêtes de recherche web soumises à un moteur de recherche. En particulier, le travail présenté ici s’intéresse à deux problèmes distincts. Le premier porte sur la classification non-supervisée d’un ensemble de requêtes de recherche web dans le but de parvenir à regrouper ensemble les requêtes traitant d’un même sujet. Le deuxième problème porte quant à lui sur la détection non-supervisée des entités nommées contenues dans un ensemble de requêtes qui ont été soumises à un moteur de recherche. Les deux techniques proposées utilisent l’information supplémentaire apportée par la connaissance des pages web qui ont été visitées par les utilisateurs ayant émis les requêtes étudiées.

Ces dernières années, le besoin de données géographiques de référence a significativement augmenté. Pour y répondre, il est nécessaire de mettre jour continuellement les données de référence existantes. Cette tâche est coûteuse tant financièrement que techniquement. Pour ce qui concerne les réseaux routiers, trois types de voies sont particulièrement complexes à mettre à jour en continu : les chemins piétonniers, les chemins agricoles et les pistes cyclables. Cette complexité est due à leur nature intermittente (elles disparaissent et réapparaissent régulièrement) et à l’hétérogénéité des terrains sur lesquels elles se situent (forêts, haute montagne, littoral, etc.).En parallèle, le volume de données GPS produites par crowdsourcing et disponibles librement augmente fortement. Le nombre de gens enregistrant leurs positions, notamment leurs traces GPS, est en augmentation, particulièrement dans le contexte d’activités sportives. Ces traces sont rendues accessibles sur les réseaux sociaux, les blogs ou les sites d’associations touristiques. Cependant, leur usage actuel est limité à des mesures et analyses simples telles que la durée totale d’une trace, la vitesse ou l’élévation moyenne, etc. Les raisons principales de ceci sont la forte variabilité de la précision planimétrique des points GPS ainsi que le manque de protocoles et de métadonnées (par ex. la précision du récepteur GPS).Le contexte de ce travail est l’utilisation de traces GPS de randonnées pédestres ou à vélo, collectées par des volontaires, pour détecter des mises à jours potentielles de chemins piétonniers, de voies agricoles et de pistes cyclables dans des données de référence. Une attention particulière est portée aux voies existantes mais absentes du référentiel. L’approche proposée se compose de trois étapes : La première consiste à évaluer et augmenter la qualité des traces GPS acquises par la communauté. Cette qualité a été augmentée en filtrant (1) les points extrêmes à l’aide d’un approche d’apprentissage automatique et (2) les points GPS qui résultent d’une activité humaine secondaire (en dehors de l’itinéraire principal). Les points restants sont ensuite évalués en termes de précision planimétrique par classification automatique. La seconde étape permet de détecter de potentielles mises à jour. Pour cela, nous proposons une solution d’appariement par distance tampon croissante. Cette distance est adaptée à la précision planimétrique des points GPS classifiés pour prendre en compte la forte hétérogénéité de la précision des traces GPS. Nous obtenons ainsi les parties des traces n’ayant pas été appariées au réseau de voies des données de référence. Ces parties sont alors considérées comme de potentielles voies manquantes dans les données de référence. Finalement nous proposons dans la troisième étape une méthode de décision multicritère visant à accepter ou rejeter ces mises à jour possibles. Cette méthode attribue un degré de confiance à chaque potentielle voie manquante. L’approche proposée dans ce travail a été évaluée sur un ensemble de trace GPS multi-sources acquises par crowdsourcing dans le massif des Vosges. Les voies manquantes dans les données de références IGN BDTOPO® ont été détectées avec succès et proposées comme mises à jour potentielles / Nowadays, the need for very up to date authoritative spatial data has significantly increased. Thus, to fulfill this need, a continuous update of authoritative spatial datasets is a necessity. This task has become highly demanding in both its technical and financial aspects. In terms of road network, there are three types of roads in particular which are particularly challenging for continuous update: footpath, tractor and bicycle road. They are challenging due to their intermittent nature (e.g. they appear and disappear very often) and various landscapes (e.g. forest, high mountains, seashore, etc.).Simultaneously, GPS data voluntarily collected by the crowd is widely available in a large quantity. The number of people recording GPS data, such as GPS traces, has been steadily increasing, especially during sport and spare time activities. The traces are made openly available and popularized on social networks, blogs, sport and touristic associations' websites. However, their current use is limited to very basic metric analysis like total time of a trace, average speed, average elevation, etc. The main reasons for that are a high variation of spatial quality from a point to a point composing a trace as well as lack of protocols and metadata (e.g. precision of GPS device used).The global context of our work is the use of GPS hiking and mountain bike traces collected by volunteers (VGI traces), to detect potential updates of footpaths, tractor and bicycle roads in authoritative datasets. Particular attention is paid on roads that exist in reality but are not represented in authoritative datasets (missing roads). The approach we propose consists of three phases. The first phase consists of evaluation and improvement of VGI traces quality. The quality of traces was improved by filtering outlying points (machine learning based approach) and points that are a result of secondary human behaviour (activities out of main itinerary). Remained points are then evaluated in terms of their accuracy by classifying into low or high accurate (accuracy) points using rule based machine learning classification. The second phase deals with detection of potential updates. For that purpose, a growing buffer data matching solution is proposed. The size of buffers is adapted to the results of GPS point’s accuracy classification in order to handle the huge variations in VGI traces accuracy. As a result, parts of traces unmatched to authoritative road network are obtained and considered as candidates for missing roads. Finally, in the third phase we propose a decision method where the “missing road” candidates should be accepted as updates or not. This decision method was made in multi-criteria process where potential missing roads are qualified according to their degree of confidence. The approach was tested on multi-sourced VGI GPS traces from Vosges area. Missing roads in IGN authoritative database BDTopo® were successfully detected and proposed as potential updates

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.

Les ressources d'information multilingues sur le Web sont devenues de plus en plus des objets d'études importantes pour différents domaines intervenant au traitement de l'information. Néanmoins, nous constatons que la structure des ressources multilingues est très peu explorée par rapport à l'abondance des méthodes de traitement automatique des langues naturelles. Dans cette thèse, nous abordons l'aspect multilinguisme dans un contexte de catégorisation des sites Web multilingues. Nous apportons quelques connaissances expérimentales portant sur la représentation de documents multilingues, la modélisation des données en une structure homogène, la qualité de la recherche d'information dans un contexte multilingues et enfin sur les notions de frontière et de centre de gravité pour départager des langues dominantes sans puiser dans des connaissances linguistiques.

La fouille de données vise à extraire des connaissances à partir d'un grand volume de données. Lorsque les associations et l'ordre chronologique d'apparition des items sont recherchés, les connaissances extraites sont appelées motifs séquentiels. Les travaux de recherche existants ont porté principalement sur l'étude de motifs séquentiels composés d'objets et dans un certain nombre de cas, de catégories d'objets (concepts). Alors que les motifs d'objets sont trop spécifiques, et de ce fait peuvent être peu fréquents, les motifs de concepts ont divers niveaux d'abstraction et risquent d'être moins précis. La prise en compte d'une ontologie du domaine dans le processus de fouille de données permet de découvrir des motifs plus compacts et plus pertinents qu'en l'absence d'une telle source de connaissance. En outre, les objets peuvent non seulement être décrits par les concepts auxquels ils se rattachent mais aussi par les liens sémantiques qui existent entre concepts. Cependant, les approches de fouille existantes restent restrictives par rapport aux modes d'expression offerts par une ontologie. La contribution de ce travail est de définir la syntaxe et la sémantique d'un langage de motifs qui prend en considération les connaissances incorporées dans une ontologie lors de la fouille de motifs séquentiels. Ce langage offre un ensemble de primitives pour la description et la manipulation de motifs. La méthode de fouille sous-jacente procède au parcours de l'espace de motifs par niveau en se basant sur un ensemble de primitives de navigation. Ces primitives tiennent compte de la relation de généralisation/spécialisation qui existe entre les concepts (et les relations) des motifs. Afin de valider notre approche et analyser la performance et la mise à l'échelle de l'algorithme proposé, nous avons développé la plateforme OntoMiner. Tout au long de la thèse, le potentiel de notre approche de fouille a été illustré à travers un cas de recom- mandation Web. Il ressort que l'inclusion des concepts et des relations dans le processus de fouille permet d'avoir des motifs plus pertinents et de meilleures recommandations que les approches classiques de fouille de motifs séquentiels ou de recommandation.

Dans cette thèse, nous proposons une nouvelle approche WCUM (Web Content and Usage Mining based approach) permettant de relier l'analyse du contenu à l'analyse de l'usage d'un site Web afin de mieux comprendre le comportement général des visiteurs du site. Ce travail repose sur l'utilisation de l'algorithme CROKI2 de classification croisée implémenté selon deux stratégies d'optimisation différentes que nous comparons à travers des expérimentations sur des données générées artificiellement. Afin de pallier le problème de détermination du nombre de classes sur les lignes et les colonnes, nous proposons de généraliser certains indices proposés initialement pour évaluer les partitions obtenues par des algorithmes de classification simple, aux algorithmes de classification simultanée. Pour évaluer la performance de ces indices nous proposons un algorithme de génération de biclasses artificielles pour effectuer des simulations et valider les résultats. Des expérimentations sur des données artificielles ainsi qu'une application sur des données réelles ont été réalisées pour évaluer l'efficacité de l'approche proposée.

Dans cette thèse, nous proposons une nouvelle approche WCUM (Web Content and Usage Mining based approach) permettant de relier l'analyse du contenu à l'analyse de l'usage d'un site Web afin de mieux comprendre le comportement général des visiteurs du site. Ce travail repose sur l'utilisation de l'algorithme CROKI2 de classification croisée implémenté selon deux stratégies d'optimisation différentes que nous comparons à travers des expérimentations sur des données générées artificiellement. Afin de pallier le problème de détermination du nombre de classes sur les lignes et les colonnes, nous proposons de généraliser certains indices proposés initialement pour évaluer les partitions obtenues par des algorithmes de classification simple, aux algorithmes de classification simultanée. Pour évaluer la performance de ces indices nous proposons un algorithme de génération de biclasses artificielles pour effectuer des simulations et valider les résultats. Des expérimentations sur des données artificielles ainsi qu'une application sur des données réelles ont été réalisées pour évaluer l'efficacité de l'approche proposée. / In this thesis, we propose a new approach WCUM (Web Content and Usage Mining based approach) for linking content analysis to usage analysis of a website to better understand the general behavior of the web site visitors. This work is based on the use of the block clustering algorithm CROKI2 implemented by two different strategies of optimization that we compared through experiments on artificially generated data. To mitigate the problem of determination of the number of clusters on rows and columns, we suggest to generalize the use of some indices originally proposed to evaluate the partitions obtained by clustering algorithms to evaluate bipartitions obtained by simultaneous clustering algorithms. To evaluate the performance of these indices on data with biclusters structure, we proposed an algorithm for generating artificial data to perform simulations and validate the results. Experiments on artificial data as well as on real data were realized to estimate the efficiency of the proposed approach.