Les données relationnelles sont omniprésentes dans la nature et leur accessibilité ne cesse d'augmenter depuis ces dernières années. Ces données, vues comme un tout, forment un réseau qui peut être représenté par une structure de données appelée graphe où chaque nœud du graphe est une entité et chaque arête représente une relation ou connexion entre ces entités. Les réseaux complexes en général, tels que le Web, les réseaux de communications ou les réseaux sociaux sont connus pour exhiber des propriétés structurelles communes qui émergent aux travers de leurs graphes. Dans cette thèse, nous mettons l'accent sur deux importantes propriétés appelées *homophilie* et *attachement préférentiel* qui se produisent dans un grand nombre de réseaux réels. Dans une première phase, nous étudions une classe de modèles de graphes aléatoires dans un contexte Bayésien non-paramétrique, appelé *modèle de composition mixée*, et nous nous concentrons à montrer si ces modèles satisfont ou non les propriétés mentionnées, après avoir proposé des définitions formelles pour ces dernières. Nous conduisons ensuite une évaluation empirique pour mettre à l'épreuve nos résultats sur des jeux de données de réseaux synthétiques et réels. Dans une seconde phase, nous proposons un nouveau modèle, qui généralise un précédent modèle à composition mixée stochastique, adapté pour les réseaux pondérés et nous développons un algorithme d'inférence efficace capable de s'adapter à des réseaux de grande échelle. / Relational data are ubiquitous in the nature and their accessibility has not ceased to increase in recent years. Those data, see as a whole, form a network, which can be represented by a data structure called a graph, where each vertex of the graph is an entity and each edge a connection between pair of vertices. Complex networks in general, such as the Web, communication networks or social network, are known to exhibit common structural properties that emerge through their graphs. In this work we emphasize two important properties called *homophilly* and *preferential attachment* that arise on most of the real-world networks. We firstly study a class of powerful *random graph models* in a Bayesian nonparametric setting, called *mixed-membership model* and we focus on showing whether the models in this class comply with the mentioned properties, after giving formal definitions in a probabilistic context of the latter. Furthermore, we empirically evaluate our findings on synthetic and real-world network datasets. Secondly, we propose a new model, which extends the former Stochastic Mixed-Membership Model, for weighted networks and we develop an efficient inference algorithm able to scale to large-scale networks.

La motivation principale de cette thèse est de proposer un système de recommandation personnalisé pour les plateformes d’informations. Pour cela, nous avons démontré que les opinions peuvent constituer un descripteur efficace pour améliorer la qualité de la recommandation. Au cours de cette thèse, nous avons abordé ce problème en proposant trois contributions principales. Tout d’abord, nous avons proposé un modèle de profil qui décrit avec précision les intérêts des utilisateurs ainsi que le contenu des articles de presse. Le modèle de profil proposé repose sur trois éléments : les entités nommées, les aspects et les sentiments. Nous avons testé notre modèle de profil sur les trois applications différentes que sont l’identification des orientations politiques des utilisateurs, la recommandation personnalisée des articles de presse et enfin la diversification de la liste des articles recommandés. Deuxièmement, nous avons proposé une approche de classement des opinions permettant de filtrer et sélectionner seulement les opinions pertinentes. Pour cela, nous avons utilisé une variation de la technique de PageRank pour définir le score de chaque opinion. Les résultats montrent que notre approche surpasse deux approches récemment proposées pour le classement des opinions. Troisièmement, nous avons étudié différentes façons d’enrichir le contenu des articles de presse par les opinions : par toutes les opinions, par seulement le topk des opinions, et enfin par un ensemble d’opinions diversifiées. Les résultats montrent que l’enrichissement des contenus des articles de presse / In this thesis, we have investigated how to exploit user-generated-content for personalized news recommendation purpose. The intuition behind this line of research is that the opinions provided by users, on news websites, represent a strong indicator about their profiles. We have addressed this problem by proposing three main contributions. Firstly, we have proposed a profile model that accurately describes both users’ interests and news article contents. The profile model was tested on three different applications ranging from identifying the political orientation of users to the context of news recommendation and the diversification of the list of recommended news articles. Results show that our profile model give much better results compared to state-of-the-art models. Secondly, we have investigated the problem of noise on opinions and how we can retrieve only relevant opinions in response to a given query.The proposed opinion ranking strategy is based on users’ debates features. We have used a variation of PageRank technique to define the score of each opinion. Results show that our approach outperforms two recent proposed opinions ranking strategies, particularly for controversial topics. Thirdly, we have investigated different ways of leveraging opinions on news article contents including all opinions, topk opinions based on opinion ranking strategy, and a set of diverse opinion. To extract a list of diverse opinions, we have employed a variation of an existing opinion diversification model. Results show that diverse opinions give the best performance over other leveraging strategies.

Dans le domaine de l'extraction de motifs, il existe un grand nombre d'algorithmes pour résoudre une large variété de sous problèmes sensiblement identiques. Cette variété d'algorithmes freine l'adoption des techniques d'extraction de motifs pour l'analyse de données. Dans cette thèse, nous proposons un formalisme qui permet de capturer une large gamme de problèmes d'extraction de motifs. Pour démontrer la généralité de ce formalisme, nous l'utilisons pour décrire trois problèmes d'extraction de motifs : le problème d'extraction d'itemsets fréquents fermés, le problème d'extraction de graphes relationnels fermés ou le problème d'extraction d'itemsets graduels fermés. Ce formalisme nous permet de construire ParaMiner qui est un algorithme générique et parallèle pour les problèmes d'extraction de motifs. ParaMiner est capable de résoudre tous les problèmes d'extraction de motifs qui peuvent ˆtre décrit dans notre formalisme. Pour obtenir de bonne performances, nous avons généralisé plusieurs optimisations proposées par la communauté dans le cadre de problèmes spécifique d'extraction de motifs. Nous avons également exploité la puissance de calcul parallèle disponible dans les archi- tectures parallèles. Nos expériences démontrent qu'en dépit de la généricité de ParaMiner ses performances sont comparables avec celles obtenues par les algorithmes les plus rapides de l'état de l'art. Ces algorithmes bénéficient pourtant d'un avantage important, puisqu'ils incorporent de nombreuses optimisations spécifiques au sous problème d'extraction de motifs qu'ils résolvent. / In the pattern mining field, there exist a large number of algorithms that can solve a large variety of distinct but similar pattern mining problems. This variety prevent broad adoption of data analysis with pattern mining algorithms. In this thesis we propose a formal framework that is able to capture a broad range of pattern mining problems. We illustrate the generality of our framework by formalizing three different pattern mining problems: the problem of closed frequent itemset mining, the problem of closed relational graph mining and the problem of closed gradual itemset mining. Building on this framework, we have designed ParaMiner, a generic and parallel algorithm for pattern mining. ParaMiner is able to solve any pattern mining problem that can be formalized within our framework. In order to achieve practical efficiency we have generalized important optimizations from state of the art algorithms and we have made ParaMiner able to exploit parallel computing platforms. We have conducted thorough experiments that demonstrate that despite being a generic algorithm, ParaMiner can compete with the fastest ad-hoc algorithms.

Dans la fouille de données multi-tables, les données sont représentées sous un format relationnel dans lequel les individus de la table cible sont potentiellement associés à plusieurs enregistrements dans des tables secondaires en relation un-à-plusieurs. Afin de prendre en compte les variables explicatives secondaires (appartenant aux tables secondaires), la plupart des approches existantes opèrent par mise à plat, obtenant ainsi une représentation attribut-valeur classique. Par conséquent, on perd la représentation initiale naturellement compacte mais également on risque d'introduire des biais statistiques. Dans cette thèse, nous nous intéressons à évaluer directement les variables secondaires vis-à-vis de la variable cible, dans un contexte de classification supervisée. Notre méthode consiste à proposer une famille de modèles non paramétriques pour l'estimation de la densité de probabilité conditionnelle des variables secondaires. Cette estimation permet de prendre en compte les variables secondaires dans un classifieur de type Bayésien Naïf. L'approche repose sur un prétraitement supervisé des variables secondaires, par discrétisation dans le cas numérique et par groupement de valeurs dans le cas catégoriel. Dans un premier temps, ce prétraitement est effectué de façon univariée, c'est-à-dire, en considérant une seule variable secondaire à la fois. Dans un second temps, nous proposons une approche de partitionnement multivarié basé sur des itemsets de variables secondaires, ce qui permet de prendre en compte les éventuelles corrélations qui peuvent exister entre variables secondaires. Des modèles en grilles de données sont utilisés pour obtenir des critères Bayésiens permettant d'évaluer les prétraitements considérés. Des algorithmes combinatoires sont proposés pour optimiser efficacement ces critères et obtenir les meilleurs modèles.Nous avons évalué notre approche sur des bases de données multi-tables synthétiques et réelles. Les résultats montrent que les critères d'évaluation ainsi que les algorithmes d'optimisation permettent de découvrir des variables secondaires pertinentes. De plus, le classifieur Bayésien Naïf exploitant les prétraitements effectués permet d'obtenir des taux de prédiction importants. / In multi-relational data mining, data are represented in a relational form where the individuals of the target table are potentially related to several records in secondary tables in one-to-many relationship. In order take into account the secondary variables (those belonging to a non target table), most of the existing approaches operate by propositionalization, thereby losing the naturally compact initial representation and eventually introducing statistical bias. In this thesis, our purpose is to assess directly the relevance of secondary variables w.r.t. the target one, in the context of supervised classification.We propose a family of non parametric models to estimate the conditional density of secondary variables. This estimation provides an extension of the Naive Bayes classifier to take into account such variables. The approach relies on a supervised pre-processing of the secondary variables, through discretization in the numerical case and a value grouping in the categorical one. This pre-processing is achieved in two ways. In the first approach, the partitioning is univariate, i.e. by considering a single secondary variable at a time. In a second approach, we propose an itemset based multivariate partitioning of secondary variables in order to take into account any correlations that may occur between these variables. Data grid models are used to define Bayesian criteria, evaluating the considered pre-processing. Combinatorial algorithms are proposed to efficiently optimize these criteria and find good models.We evaluated our approach on synthetic and real world multi-relational databases. Experiments show that the evaluation criteria and the optimization algorithms are able to discover relevant secondary variables. In addition, the Naive Bayesian classifier exploiting the proposed pre-processing achieves significant prediction rates.

De nombreux domaines ont intérêt à étudier les points de vue exprimés en ligne, que ce soit à des fins de marketing, de cybersécurité ou de recherche avec l'essor des humanités numériques. Nous proposons dans ce manuscrit deux contributions au domaine de la fouille de points de vue, axées sur la difficulté à obtenir des données annotées de qualité sur les médias sociaux. Notre première contribution est un jeu de données volumineux et complexe de 22853 profils Twitter actifs durant la campagne présidentielle française de 2017. C'est l'un des rares jeux de données considérant plus de deux points de vue et, à notre connaissance, le premier avec un grand nombre de profils et le premier proposant des communautés politiques recouvrantes. Ce jeu de données peut être utilisé tel quel pour étudier les mécanismes de campagne sur Twitter ou pour évaluer des modèles de détection de points de vue ou des outils d'analyse de réseaux. Nous proposons ensuite deux modèles génériques semi-supervisés de détection de points de vue, utilisant une poignée de profils-graines, pour lesquels nous connaissons le point de vue, afin de catégoriser le reste des profils en exploitant différentes proximités inter-profils. En effet, les modèles actuels sont généralement fondés sur les spécificités de certaines plateformes sociales, ce qui ne permet pas l'intégration de la multitude de signaux disponibles. En construisant des proximités à partir de différents types d'éléments disponibles sur les médias sociaux, nous pouvons détecter des profils suffisamment proches pour supposer qu'ils partagent une position similaire sur un sujet donné, quelle que soit la plateforme. Notre premier modèle est un modèle ensembliste séquentiel propageant les points de vue grâce à un graphe multicouche représentant les proximités entre les profils. En utilisant des jeux de données provenant de deux plateformes, nous montrons qu'en combinant plusieurs types de proximité, nous pouvons correctement étiqueter 98% des profils. Notre deuxième modèle nous permet d'observer l'évolution des points de vue des profils pendant un événement, avec seulement un profil-graine par point de vue. Ce modèle confirme qu'une grande majorité de profils ne changent pas de position sur les médias sociaux, ou n'expriment pas leur revirement. / Numerous domains have interests in studying the viewpoints expressed online, be it for marketing, cybersecurity, or research purposes with the rise of computational social sciences. We propose in this manuscript two contributions to the field of stance detection, focused around the difficulty of obtaining annotated data of quality on social medias. Our first contribution is a large and complex dataset of 22853 Twitter profiles active during the French presidential campaign of 2017. This is one of the rare datasets that considers a non-binary stance classification and, to our knowledge, the first one with a large number of profiles, and the first one proposing overlapping political communities. This dataset can be used as-is to study the campaign mechanisms on Twitter, or used to test stance detection models or network analysis tools. We then propose two semi-supervised generic stance detection models using a handful of seed profiles for which we know the stance to classify the rest of the profiles by exploiting various proximities. Indeed, current stance detection models are usually grounded on the specificities of some social platforms, which is unfortunate since it does not allow the integration of the multitude of available signals. By infering proximities from differents types of elements available on social medias, we can detect profiles close enough to assume they share a similar stance on a given subject. Our first model is a sequential ensemble algorithm which propagates stances thanks to a multi-layer graph representing proximities between profiles. Using datasets from two platforms, we show that, by combining several types of proximities, we can achieve excellent results. Our second model allows us to observe the evolution of profiles' stances during an event with as little as one seed profile by stance. This model confirms that a large majority of profiles do not change their stance on social medias, or do not express their change of heart.

Ce travail de thèse s'inscrit dans le contexte d'extraction de connaissances à partir de documents textuels, appelé Fouille de textes (FdT) ou Text Mining (TM). Ce mémoire s'articule autour des problématiques liées à la modélisation de documents et la représentation de connaissances textuelles. Il s'intéresse à des collections de documents qui abordent des thématiques différentes. Le mémoire s'attache à élaborer un modèle de représentation et un système permettant d'extraire automatiquement des informations sur les différentes thématiques abordées mais également des mécanismes offrant la possibilité d'avoir des aperçus sur les contenus. Il est montré que les approches basées sur les associations de termes sont adaptées à ce contexte. Cependant, ces approches souffrent de certaines lacunes liées au choix du modèle et de la connaissance à retenir. Pour l'élaboration du modèle de représentation, le choix porte sur l'extension de l'approche d'association de termes. A cet effet, la notion de contexte est étudiée et un nouveau critère appelé « partage de contextes » est défini. Via ce critère, il est possible de détecter des liens entre termes qui n'apparaîtraient pas autrement. L'objectif est de représenter le plus de connaissances possibles. Ces dernières sont exploitées pour une meilleure représentation du contenu et des informations enfouies dans les textes. Un système appelé IC-DOC est réalisé, ce dernier met en oeuvre le modèle de représentation dans un nouvel environnement d'extraction de connaissances à partir de documents textuels. Dans un contexte de veille scientifique, la proposition de ce type de systèmes devient indispensable pour extraire et visualiser de manière automatique l'information contenue dans les collections de documents textuels. L'originalité du système IC-DOC est de tirer profit du modèle de représentation proposé. Une série d'expérimentations et de validations sur divers jeux de données sont réalisées via le système IC-DOC. Deux applications sont considérées. La première s'intéresse à la caractérisation thématique et la seconde étend la première pour une cartographie visuelle de connaissances textuelles.

Le sujet principal de cette thèse est l'extraction de connaissances dans les bases de données (ECBD). Plus précisément, nous avons étudié deux des plus importantes tâches d'ECBD actuelles, qui sont l'extraction de motifs et la génération de règles d'association. Tout au long de notre travail, notre objectif a été de trouver des règles d'associations intéressantes selon plusieurs points de vue : dans un but de fouille efficace, pour réduire au minimum l'ensemble des règles extraites et pour trouver des unités de connaissances intelligibles (et facilement interprétables). Pour atteindre ce but, nous avons développé et adapté des algorithmes spécifiques. <br />Les contributions principales de cette thèse sont : <strong>(1)</strong> nous avons développé et adapté des algorithmes pour trouver les règles d'association minimales non-redondantes ; <strong>(2)</strong> nous avons défini une nouvelle base pour les règles d'associations appelée “règles fermées” ; <strong>(3)</strong> nous avons étudié un champ de l'ECBD important mais relativement peu étudié, à savoir l'extraction des motifs rares et des règles d'association rares ; <strong>(4)</strong> nous avons regroupé nos algorithmes et une collection d'autres algorithmes ainsi que d'autres opérations auxiliaires d'ECBD dans une boîte à outils logicielle appelée Coron.

L'expérience du résumé automatique m'a amené à élargir le champ de mes recherches en visant non plus de simples résumés automatiques non ciblés, mais des systèmes automatiques de filtrage sémantique d'informations, adaptés aux besoins spécifiques d'une tâche d'identification. Divers travaux menés parallèlement dans l'équipe LALIC depuis plusieurs années ont en effet permis d'identifier une même problématique qui relève du filtrage sémantique dans des textes. <br />Ce filtrage sémantique se fonde sur la méthode d'exploration contextuelle. Il s'effectue en exploitant des connaissances purement textuelles, indépendantes d'un domaine particulier, ce qui signifie que nous ne cherchons pas à construire des ontologies. Ces connaissances s'expriment sous forme de marqueurs linguistiques discursifs explicites d'une notion sémantique et sont organisées pour des tâches précises. L'exploitation de ces connaissances a pour finalité d'attribuer une ou plusieurs valeurs sémantiques à une unité textuelle. Il devient ainsi possible de produire un extrait textuel en « filtrant » les unités textuelles étiquetées selon le point de vue adopté. En d'autres termes, le filtrage sémantique est un moyen pour fouiller un texte selon le point de vue d'un utilisateur.<br />Ma recherche s'est déployée selon deux axes :<br />• La construction d'un système d'expression de l'exploration contextuelle ;<br />• La conception d'une plate-forme d'ingénierie linguistique, FilText, plate-forme dans laquelle s'inscrivent les concepts et méthodes définis.<br />Je présenterai l'architecture conceptuelle de la plate-forme FilText ainsi que les possibilités offertes par ContextO, instance logicielle de Filtext.<br />Enfin, je montrerais en quoi la problématique du filtrage sémantique d'informations s'étend à d'autres disciplines des sciences humaines dans lesquelles la recherche d'informations dans des textes constitue une activité essentielle des chercheurs.

Ce travail de thèse porte sur la problématique d'extraction de connaissances à partir de textes, plus communément appelée la fouille de textes (FdT). Il s'articule autour des problèmes liés à l'analyse des textes, la fouille de textes proprement dite, et l'interprétation des éléments de connaissances extraits. Dans ce cadre, un système d'extraction des connaissances nécessaires pour analyser les textes en fonction de leur contenu est étudié et implanté. Les méthodes de fouille de données appliquées sont la recherche de motifs fréquents (avec l'algorithme Close) et l'extraction de règles d'association. Le mémoire s'attache à définir précisément le processus de fouille de textes et ses principales caractéristiques et propriétés en s'appuyant sur l'extraction de motifs fréquents et de règles d'association. En outre, une étude minutieuse d'un ensemble donné de mesures de qualité qu'il est possible d'attacher aux règles d'association est menée, toujours dans le cadre de la fouille de textes. Il est montré quel rôle ces mesures peuvent avoir sur la qualité et sur l'interprétation des règles extraites ; comment peuvent-elles influer sur la qualité globale du processus de fouille de textes.<br />L'utilisation d'un modèle de connaissances vient appuyer et surtout compléter cette première approche. Il est montré, par la définition d'une mesure de vraisemblance, l'intérêt de découvrir de nouvelles connaissances en écartant les connaissances déjà répertoriées et décrites par un modèle de connaissances du domaine. Les règles d'association peuvent donc être utilisées pour alimenter un modèle de connaissances terminologiques du domaine des textes choisi. La thèse inclut la réalisation d'un système appelé TAMIS : "Text Analysis by Mining Interesting ruleS" ainsi qu'une expérimentation et une validation sur des données réelles de résumés de textes en biologie moléculaire.

Cette thèse traite le problème de la réécriture de requêtes en termes de vues en présence de contraintes de valeurs. Les contraintes de valeurs permettent de restreindre le domaine de valeur d'un attribut donné. Elles connaissent un regain d'intérêt depuis leur utilisation dans le cadre du langage d'ontologie du web OWL. Ce travail est motivé par une application réelle qui vise à permettre l'intégration flexible d'un grand nombre de sources de données agricoles. L'étude de la décidabilité de ce problème est basée sur le cadre des logiques de description. Ce travail montre également que le problème de calculer les réécritures engendrées par les contraintes de valeurs se rattache au cadre de découverte des connaissances dans les bases de données introduit par Mannila and Toivonen. Ceci nous permet d'adpter des algorithmes exustants et efficaces pour calculer ces réécritures et proposer un prototype de réécriture qui passe à l'echelle.