Identifier les leviers de satisfaction des consommateurs est aujourd’hui capital dans un monde où la relation que tisse une entreprise avec ses clients est sa plus grande richesse. Le domaine de la fouille d’opinion, dans lequel s’inscrit cette thèse, propose des méthodes permettant de répondre à ce besoin. Celles-ci nécessitent cependant une mise à jour constante de ressources spécialisées qui sont la pierre angulaire des outils d’analyse d’opinion. Ce travail vise à développer des stratégies d’acquisition et de structuration de ces ressources, qui prennent la forme de lexiques, de patrons morpho-syntaxiques ou de textes annotés. Chacune de ces formes présente des difficultés d’acquisition propres, auxquelles s’ajoute la complexité de mettre à jour ces ressources en fonction de la langue à traiter ou du domaine des corpus analysés, notion primordiale en fouille d’opinion. Premièrement, nous menons une étude des éléments fondamentaux autour desquels l’opinion est construite dans le discours, conduisant à une nouvelle modélisation en étiquetage de séquence de l’opinion. Nous traitons ensuite la question de l’apport des différents types de ressources, dont il ressort que la meilleure stratégie est de les utiliser de concert. Enfin, nous proposons des méthodes d’acquisition pour chacune des ressources répondant non seulement aux besoins de la fouille d’opinion mais également aux contraintes du contexte industriel au sein duquel ces recherches sont menées. / Identifying satisfaction triggers among customers is a crucial need in today’s business world, as a strong customer relationship is now a most vital asset. The domain of opinion mining, in which this thesis falls into, offers several methods to answer this need. These methods, however, require a continuous update of specialized resources which are the cornerstone of many opinion mining tools. The objective of this work is to develop acquisition and structuration strategies for these resources, which can be lexicons, morphosyntactic rules or annotated data. Each of these items presents its own extraction difficulties, on top of the general issue of their update in a language- or domain-specific setting. Indeed, language constraints are fundamental in opinion mining, so the proposed methods must take these into account. First, we study the core elements from which opinion expressions are built in customer feedback. This study leads us to suggest a new modelisation of opinion mining as a sequence labeling task. We then compare the benefits of each type of resource through a benchmark of several opinion mining methods, and conclude that the best performing strategy is a hybrid approach. Finally, we present results for resource acquisition methods that answer not only the needs of opinion mining but also the constraints from the industrial setting in which this work has been conducted.

Dans un premier temps, nous étudions l'échantillonnage de flux de trajectoires. Garder l'intégralité des trajectoires capturées par les terminaux de géo-localisation modernes peut s'avérer coûteux en espace de stockage et en temps de calcul. L'élaboration de techniques d'échantillonnage adaptées devient primordiale afin de réduire la taille des données en supprimant certaines positions tout en veillant à préserver le maximum des caractéristiques spatiotemporelles des trajectoires originales. Dans le contexte de flux de données, ces techniques doivent en plus être exécutées "à la volée" et s'adapter au caractère continu et éphémère des données. A cet effet, nous proposons l'algorithme STSS (spatiotemporal stream sampling) qui bénéficie d'une faible complexité temporelle et qui garantit une borne supérieure pour les erreurs d’échantillonnage. Nous montrons les performances de notre proposition en la comparant à d'autres approches existantes. Nous étudions également le problème de la classification non supervisée de trajectoires contraintes par un réseau routier. Nous proposons trois approches pour traiter ce cas. La première approche se focalise sur la découverte de groupes de trajectoires ayant parcouru les mêmes parties du réseau routier. La deuxième approche vise à grouper des segments routiers visités très fréquemment par les mêmes trajectoires. La troisième approche combine les deux aspects afin d'effectuer un co-clustering simultané des trajectoires et des segments. Nous démontrons comment ces approches peuvent servir à caractériser le trafic et les dynamiques de mouvement dans le réseau routier et réalisons des études expérimentales afin d'évaluer leurs performances. / In this thesis, we explore two problems related to managing and mining moving object trajectories. First, we study the problem of sampling trajectory data streams. Storing the entirety of the trajectories provided by modern location-aware devices can entail severe storage and processing overheads. Therefore, adapted sampling techniques are necessary in order to discard unneeded positions and reduce the size of the trajectories while still preserving their key spatiotemporal features. In streaming environments, this process needs to be conducted "on-the-fly" since the data are transient and arrive continuously. To this end, we introduce a new sampling algorithm called spatiotemporal stream sampling (STSS). This algorithm is computationally-efficient and guarantees an upper bound for the approximation error introduced during the sampling process. Experimental results show that stss achieves good performances and can compete with more sophisticated and costly approaches. The second problem we study is clustering trajectory data in road network environments. We present three approaches to clustering such data: the first approach discovers clusters of trajectories that traveled along the same parts of the road network; the second approach is segment-oriented and aims to group together road segments based on trajectories that they have in common; the third approach combines both aspects and simultaneously clusters trajectories and road segments. We show how these approaches can be used to reveal useful knowledge about flow dynamics and characterize traffic in road networks. We also provide experimental results where we evaluate the performances of our propositions.

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

Dans cette thèse, nous abordons les problèmes bien connus de clustering et de fouille de règles d’association. Notre première contribution introduit un nouveau cadre de clustering, où les objets complexes sont décrits par des formules propositionnelles. Premièrement, nous adaptons les deux fameux algorithmes de clustering, à savoir, le k-means et l’algorithme hiérarchique ascendant, pour traiter ce type d’objets complexes. Deuxièmement, nous introduisons un nouvel algorithme hiérarchique descendant pour le clustering des objets représentés explicitement par des ensembles de modèles. Enfin, nous proposons un encodage basé sur la satisfiabilité propositionnelle du problème de clustering des formules propositionnelles sans avoir besoin d’une représentation explicite de leurs modèles. Dans une seconde contribution, nous proposons une nouvelle approche basée sur la satisfiabilité pour extraire les règles d’association en une seule étape. La tâche est modélisée comme une formule propositionnelle dont les modèles correspondent aux règles à extraire. Pour montrer la flexibilité de notre cadre, nous abordons également d’autres variantes, à savoir, l’extraction des règles d’association fermées, minimales non redondantes, les plus générales et les indirectes. Les expérimentations sur de nombreux jeux de données montrent que sur la majorité des tâches de fouille de règles d’association considérées, notre approche déclarative réalise de meilleures performances que les méthodes spécialisées. / In this thesis, We adress the well-known clustering and association rules mining problems. Our first contribution introduces a new clustering framework, where complex objects are described by propositional formulas. First, we extend the two well-known k-means and hierarchical agglomerative clustering techniques to deal with these complex objects. Second, we introduce a new divisive algorithm for clustering objects represented explicitly by sets of models. Finally, we propose a propositional satisfiability based encoding of the problem of clustering propositional formulas without the need for an explicit representation of their models. In a second contribution, we propose a new propositional satisfiability based approach to mine association rules in a single step. The task is modeled as a propositional formula whose models correspond to the rules to be mined. To highlight the flexibility of our proposed framework, we also address other variants, namely the closed, minimal non-redundant, most general and indirect association rules mining tasks. Experiments on many datasets show that on the majority of the considered association rules mining tasks, our declarative approach achieves better performance than the state-of-the-art specialized techniques.

Le développement du Web 2.0 a donné lieu à la production d'une grande quantité de discussions en ligne. La fouille et l'extraction de données de qualité de ces discussions en ligne sont importantes dans de nombreux domaines (industrie, marketing) et particulièrement pour toutes les applications de commerce électronique. Les discussions de ce type contiennent des opinions et des croyances de personnes et cela explique l'intérêt de développer des outils d'analyse efficaces pour ces discussions. L'objectif de cette thèse est de définir un modèle qui représente les discussions en ligne et facilite leur analyse. Nous proposons un modèle basé sur des graphes. Les sommets du graphe représentent les objets de type message. Chaque objet de type message contient des informations comme son contenu, son auteur, l'orientation de l'opinion qui y été exprimée et la date où il a été posté. Les liens parmi les objets message montrent une relation de type "répondre à". En d'autres termes, ils montrent quels objets répondent à quoi, conséquence directe de la structure de la discussion en ligne. Avec ce nouveau modèle, nous proposons un certain nombre de mesures qui guident la fouille au sein de la discussion et permettent d'extraire des informations pertinentes. Il existe des mesures centrées sur l'analyse de l'opinion qui traitent de l'évolution de l'opinion au sein de la discussion. Nous définissons également des mesures centrées sur le temps, qui exploitent la dimension temporelle du modèle, alors que les mesures centrées sur le sujet peuvent être utilisées pour mesurer la présence de sujets dans une discussion. La présence de l'utilisateur dans des discussions en ligne peut être exploitée soit par les techniques des réseaux sociaux, soit à travers notre nouveau modèle qui inclut la connaissance des auteurs de chaque objet message. De plus, une liste de messages clés est recommandée à l'utilisateur pour permettre une participation plus efficace au sein de la discussion.

Des millions de réactions chimiques sont décrites dans des bases de données sous la forme de transformations de graphes moléculaires. Cette thèse propose différentes méthodes de fouille de donnés pour extraire des motifs pertinents contenus dans ces graphes et ainsi aider les chimistes à améliorer leurs connaissances des réactions chimiques et des molécules. Ainsi on commence par montrer comment le problème central de la recherche des schémas de réactions fréquents peut se résoudre à l'aide de méthodes existantes de recherche de sous-graphes fréquents. L'introduction du modèle général des motifs les plus informatifs permet ensuite de restreindre l'analyse de ces motifs fréquents à un nombre réduit de motifs peu redondants et représentatifs des données. Si l'application du modèle aux bases de réactions permet d'identifier de grandes familles de réactions, le modèle est inadapté pour extraire les schémas caractéristiques de méthodes de synthèse (schémas CMS) dont la fréquence est trop faible. Afin de surmonter cet obstacle, est ensuite introduite une méthode de recherche heuristique fondée sur une contrainte d’intervalle entre graphes et adaptée à l’extraction de motifs de très faible fréquence. Cette méthode permet ainsi de déterminer à partir d'exemples de réactions et sous certaines conditions le schéma CMS sous-jacent à une réaction donnée. La même approche est ensuite utilisée pour traiter le problème de la classification supervisée de sommets ou d'arêtes fondée sur leurs environnements puis exploitée pour évaluer la formabilité des liaisons d'une molécule. Les résultats produits ont pu être analysés par des experts de la synthèse organique et sont très encourageants. / Millions of chemical reactions are described in databases as transformations of molecular graphs. This thesis proposes different data-mining methods to extract relevant patterns included in those graphs and therefore to help chemists in improving knowledge about chemical reactions and molecules. One first shows how the central problem of searching frequent reaction patterns can be solved using existing graph-mining methods. Introducing the general model of most informative patterns then allows experts to reduce the analysis of these frequent patterns to a very small set of non-redundant patterns characteristic of data. If the application of this model to reaction database identifies large and characteristic families of reactions, the model doesn't allow in practice the extraction of reaction patterns characteristic of synthesis methods (abbr. CSM patterns) as their frequencies are far too low. In order to overcome this problem, is introduced a heuristic search algorithm based on a graph interval constraint and able to extract patterns with very low frequency. Thus this method determines from examples of chemical reactions and under some conditions the CSM pattern underlying a given input reaction. The same approach is then used to address the problem of supervised classification of vertices or edges based on their environment and then applied to evaluate formability of bonds in molecules. Experimental results have been analyzed by experts and are very encouraging.

Les plateformes en ligne telles que les blogs et les réseaux sociaux permettent aux internautes de s'exprimer sur des sujets d'une grande variété (produits commerciaux, politique, services, etc.). Cet important volume de données d'opinions peut être exploré et exploité grâce à des techniques de fouille de texte connues sous le nom de fouille d'opinions ou analyse de sentiments. Contrairement à la majorité des travaux actuels en fouille d'opinions, qui se focalisent sur les opinions simplement positives ou négatives (ou un intermédiaire entre ces deux extrêmes), nous nous intéressons dans cette thèse aux points de vue. La fouille de point de vue généralise l'opinion au delà de son acception usuelle liée à la polarité (positive ou négative) et permet l'étude d'opinions exprimées plus subtilement, telles que les opinions politiques. Nous proposons dans cette thèse des approches non supervisées - ne nécessitant aucune annotation préalable - basées sur des modèles thématiques probabilistes afin de découvrir simultanément les thèmes et les points de vue exprimés dans des corpus de textes d'opinion. Dans notre première contribution, nous avons exploré l'idée de différencier mots d'opinions (spécifiques à la fois à un point de vue et à un thème) et mots thématiques (dépendants du thème mais neutres vis-à-vis des différents points de vue) en nous basant sur les parties de discours, inspirée par des pratiques similaires dans la littérature de fouille d'opinions classique - restreinte aux opinions positives et négatives. Notre seconde contribution se focalise quant à elle sur les points de vue exprimés sur les réseaux sociaux. Notre objectif est ici d'analyser dans quelle mesure l'utilisation des interactions entre utilisateurs, en outre de leur contenu textuel généré, est bénéfique à l'identification de leurs points de vue. Nos différentes contributions ont été évaluées et comparées à l'état de l'art sur des collections de documents réels. / The advent of online platforms such as weblogs and social networking sites provided Internet users with an unprecedented means to express their opinions on a wide range of topics, including policy and commercial products. This large volume of opinionated data can be explored and exploited through text mining techniques known as opinion mining or sentiment analysis. Contrarily to traditional opinion mining work which mostly focuses on positive and negative opinions (or an intermediate in-between), we study a more challenging type of opinions: viewpoints. Viewpoint mining reaches beyond polarity-based opinions (positive/negative) and enables the analysis of more subtle opinions such as political opinions. In this thesis, we proposed unsupervised approaches – i.e., approaches which do not require any labeled data – based on probabilistic topic models to jointly discover topics and viewpoints expressed in opinionated data. In our first contribution, we explored the idea of separating opinion words (specific to both viewpoints and topics) from topical, neutral words based on parts of speech, inspired by similar practices in the litterature of non viewpoint-related opinion mining. Our second contribution tackles viewpoints expressed by social network users. We aimed to study to what extent social interactions between users – in addition to text content – can be beneficial to identify users' viewpoints. Our different contributions were evaluated and benchmarked against state-of-the-art baselines on real-world datasets

Dans le cadre de cette thèse, nous avons établi des liens entre les modèles obtenus par des algorithmes d'inférence grammaticale et la connaissance induite par des techniques de fouille de données séquentielles. Partant du constat que le point commun entre ces deux contextes différents de travail est la manipulation de données structurées sous forme de séquences de symboles, nous avons tenté d'exploiter les propriétés des automates probabilistes inférés à partir de ces séquences au profit d'une fouille de données séquentielles plus efficace. <br />Dans ce contexte, nous avons montré que l'exploitation brute, non seulement des séquences d'origine mais aussi des automates probabilistes inférés à partir de celles-ci, ne garantit pas forcément une extraction de connaissance pertinente. Nous avons apporté dans cette thèse plusieurs contributions, sous la forme de bornes minimales et de contraintes statistiques, permettant ainsi d'assurer une exploitation fructueuse des séquences et des automates probabilistes. De plus, grâce à notre modèle nous apportons une solution efficace à certaines applications mettant en jeux des problèmes de préservation de vie privée des individus.

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.