Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

Dans cette thèse nous considérons une plate-forme de filtrage collaboratif distribué dans laquelle chaque pair héberge ses informations personnelles, comme les URL qu'il a aimé, les pages d'information qui ont attiré son intérêt ou les vidéos qu'il a regardé, sur sa propre machine. Ensuite, sans reposer sur un tiers fiable, le pair s'engage dans un protocole distribué combinant ses données personnelles avec celles d'autres pairs afin d'exécuter un filtrage collaboratif. L'objectif principal est d'être capable de recevoir des recommandations personnalisées ou d'autres services comme un moteur de recherche distribué et personnalisé. Les protocoles de filtrage collaboratif basés sur les utilisateurs, qui demandent de calculer des similarités entre les utilisateurs, ont été appliqués aux systèmes distribués. Comme le calcul de similarité entre les utilisateurs nécessite d'utiliser leurs profils privés personnels, cela lève de sérieuses inquiétudes quant à la vie privée. Dans cette thèse nous adressons le problème du calcul de similarités entre les pairs sur une plate forme collaborative. Notre travail fournit une primitive préservant la vie privée pour le calcul de similarité qui peut rendre les protocoles collaboratifs respectueux de la vie privée. Nous adressons le challenge unique qui est d'appliquer des techniques de préservation de la vie privée pour le calcul de similarité aux systèmes dynamiques à large échelle. En particulier, nous introduisons un protocole cryptographique bipartite qui assure la differential privacy, une notion forte de préservation de la vie privée. De plus, nous résolvons le problème du budget de vie privée qui empêcherait les pairs de calculer leur similarité plus d'un nombre fixe de fois en introduisant la notion de canaux anonymes bidirectionnels. Nous développons aussi une variante hétérogène de la differential privacy qui peut apporter différent niveaux de confidentialité pour différent utilisateurs, et même différent niveaux de confidentialité pour différents items du profile d'un même utilisateur, prenant ainsi en compte différentes attentes en terme de préservation de la vie privée. De plus, nous proposons un protocole non interactif qui est très efficace pour publier une représentation compacte et préservant la vie privée des profiles des utilisateurs qui peut être utilisée pour estimer la similarité. Enfin, nous étudions le problème de choisir un paramètre de vie privée à la fois théoriquement et empiriquement en créant plusieurs attaques par inférence qui démontrent pour quelles valeurs du paramètre de vie privée le niveau de vie privée fournis est acceptable. / In this thesis, we consider a distributed collaborative platform in which each peer hosts his private information, such as the URLs he liked or the news articles that grabbed his interest or videos he watched, on his own machine. Then, without relying on a trusted third party, the peer engages in a distributed protocol, combining his private data with other peers' private data to perform collaborative filtering. The main objective is to be able to receive personalized recommendations or other services such as a personalized distributed search engine. User-based collaborative filtering protocols, which depend on computing user-to-user similarity, have been applied to distributed systems. As computing the similarity between users requires the use of their private profiles, this raises serious privacy concerns. In this thesis, we address the problem of privately computing similarities between peers in collaborative platforms. Our work provides a private primitive for similarity computation that can make collaborative protocols privacy-friendly. We address the unique challenges associated with applying privacy-preserving techniques for similarity computation to dynamic large scale systems. In particular, we introduce a two-party cryptographic protocol that ensures differential privacy, a strong notion of privacy. Moreover, we solve the privacy budget issue that would prevent peers from computing their similarities more than a fixed number of times by introducing the notion of bidirectional anonymous channel. We also develop a heterogeneous variant of differential privacy that can provide different level of privacy to different users, and even different level of privacy to different items within a single user's profile, thus taking into account different privacy expectations. Moreover, we propose a non-interactive protocol that is very efficient for releasing a small and private representation of peers' profiles that can be used to estimate similarity. Finally, we study the problem of choosing an appropriate privacy parameter both theoretically and empirically by creating several inference attacks that demonstrate for which values of the privacy parameter the privacy level provided is acceptable.

Un des premiers modèles d'indexation de documents qui utilise des termes comme descripteurs était une structure de treillis, cela une vingtaine d'années avant l'arrivée de l'analyse formelle de concepts (FCA pour "Formal Concept Analysis"), qui s'affirme maintenant comme un formalisme théorique important et solide pour l'analyse de données et la découverte de connaissances. Actuellement, la communauté en recherche d'information (RI) s'intéresse particulièrement à des techniques avancées pour la recherche des documents qui relèvent des probabilités et des statistiques. En parallèle, l'intérêt de la communauté FCA au développement de techniques qui font avancer l'état de l'art en RI tout en offrant des fonctionnalités sémantiques lui est toujours bien vivant. Dans cette thèse, nous présentons un ensemble de contributions sur ce que nous avons appelé les systèmes FCA de recherche d'information ("FCA-based IR systems''). Nous avons divisé nos contributions en deux parties, à savoir l'extraction et l'indexation. Pour la récupération, nous proposons une nouvelle technique qui exploite les relations sémantiques entre les descripteurs dans un corpus de documents. Pour l'indexation, nous proposons un nouveau modèle qui permet de mettre en oeuvre un modèle vectoriel d'indexation des documents s'appuyant sur un treillis de concepts (ou treillis de Galois). En outre, nous proposons un modèle perfectionné pour l'indexation hétérogène dans lequel nous combinons le modèle vectoriel et le modèle de recherche booléen. Finalement, nous présentons une technique de fouille de données inspiré de l'indexation des documents, à savoir un modèle d'énumération exhaustive des biclusters en utilisant la FCA. Le biclustering est une nouvelle technique d'analyse de données dans laquelle les objets sont liés via la similitude dans certains attributs de l'espace de description, et non pas par tous les attributs comme dans le "clustering'' standard. En traduisant ce problème en termes d'analyse formelle de concepts, nous pouvons exploiter l'algorithmique associée à la FCA pour développer une technique d'extraction de biclusters de valeurs similaires. Nous montrons le très bon comportement de notre technique, qui fonctionne mieux que les techniques actuelles de biclustering avec énumération exhaustive / One of the first models ever to be considered as an index for documents using terms as descriptors, was a lattice structure, a couple of decades before the arrival of Formal Concept Analysis (FCA) as a solid theory for data mining and knowledge discovery.While the Information Retrieval (IR) community has shifted to more advanced techniques for document retrieval, like probabilistic and statistic paradigms, the interest of the FCA community on developing techniques that would improve the state-of-the-art in IR while providing relevance feedback and semantic based features, never decayed. In this thesis we present a set of contributions on what we call FCA-based IR systems. We have divided our contributions in two sets, namely retrieval and indexing. For retrieval, we propose a novel technique that exploits semantic relations among descriptors in a document corpus and a new concept lattice navigation strategy (called cousin concepts), enabling us to support classification-based reasoning to provide better results compared with state-of-the-art retrieval techniques. The basic notion in our strategy is supporting query modification using "term replacements'' using the lattice structure and semantic similarity. For indexing, we propose a new model that allows supporting the vector space model of retrieval using concept lattices. One of the main limitations of current FCA-based IR systems is related to the binary nature of the input data required for FCA to generate a concept lattice. We propose the use of pattern structures, an extension of FCA to deal with complex object descriptions, in order to support more advanced retrieval paradigms like the vector space model. In addition, we propose an advanced model for heterogeneous indexing through which we can combine the vector space model and the Boolean retrieval model. The main advantage of this approach is the ability of supporting indexing of convex regions in an arbitrary vectorial space built from a document collection. Finally, we move forward to a mining model associated with document indexing, namely exhaustive bicluster enumeration using FCA. Biclustering is an emerging data analysis technique in which objects are related by similarity under certain attributes of the description space, instead of the whole description space like in standard clustering. By translating this problem to the framework of FCA, we are able to exploit the robust machinery associated with the computation of concept lattices to provide an algorithm for mining biclusters based on similar values. We show how our technique performs better than current exhaustive enumeration biclustering techniques.

Un système de recommandation a pour objectif de recommander à un utilisateur, appelé utilisateur actif, des ressources pertinentes pour lui. Le filtrage collaboratif (FC) est une approche de recommandation très répandue qui exploite les préférences exprimées par des utilisateurs sur des ressources. Le FC repose sur l'hypothèse que les préférences des utilisateurs sont cohérentes entre elles, ce qui permet d'inférer les préférences d'un utilisateur à partir des préférences des autres utilisateurs. Définissons une préférence spécifique comme une préférence qui ne serait partagée pour aucun groupe d'utilisateurs. Un utilisateur possédant plusieurs préférences spécifiques qu'il ne partage avec aucun autre utilisateur sera probablement mal servi par une approche de FC classique. Il s'agit du problème des Grey Sheep Users (GSU). Dans cette thèse, je réponds à trois questions distinctes. 1) Qu'est-ce qu'une préférence spécifique ? J'apporte une réponse en proposant des hypothèses associées que je valide expérimentalement. 2) Comment identifier les GSU dans les données ? Cette identification est importante afin d'anticiper les mauvaises recommandations qui seront fournies à ces utilisateurs. Je propose des mesures numériques permettant d'identifier les GSU dans un jeu de données de recommandation sociale. Ces mesures sont significativement plus performantes que celles de l'état de l'art. Enfin, comment modéliser ces GSU pour améliorer la qualité des recommandations qui leurs sont fournies ? Je propose des méthodes inspirées du domaine de l'apprentissage automatique et dédiées à la modélisation des GSU permettant d'améliorer la qualité des recommandations qui leurs sont fournies / A recommender system aims at providing relevant resources to a user, named the active user. To allow this recommendation, the system exploits the information it has collected about the active user or about resources. The collaborative filtering (CF) is a widely used recommandation approach. The data exploited by CF are the preferences expressed by users on resources. CF is based on the assumption that preferences are consistent between users, allowing a user's preferences to be inferred from the preferences of other users. In a CF-based recommender system, at least one user community has to share the preferences of the active user to provide him with high quality recommendations. Let us define a specific preference as a preference that is not shared by any group of user. A user with several specific preferences will likely be poorly served by a classic CF approach. This is the problem of Grey Sheep Users (GSU). In this thesis, I focus on three separate questions. 1) What is a specific preference? I give an answer by proposing associated hypotheses that I validate experimentally. 2) How to identify GSU in preference data? This identification is important to anticipate the low quality recommendations that will be provided to these users. I propose numerical indicators to identify GSU in a social recommendation dataset. These indicators outperform those of the state of the art and allow to isolate users whose quality of recommendations is very low. 3) How can I model GSU to improve the quality of the recommendations they receive? I propose new recommendation approaches to allow GSU to benefit from the opinions of other users

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Cette thèse traite des systèmes de recommandation automatiques. Les moteurs de recommandation automatique sont des systèmes qui permettent, par des techniques de data mining, de recommander automatiquement à des clients, en fonction de leurs consommations passées, des produits susceptibles de les intéresser. Ces systèmes permettent par exemple d'augmenter les ventes sur des sites web marchands : le site Amazon a une stratégie marketing en grande partie basée sur la recommandation automatique. Amazon a popularisé l'usage de la recommandation automatique par la célèbre fonction de recommandation que nous qualifions d'item-to-items, le fameux : " les personnes qui ont vu/acheté cet articles ont aussi vu/acheté ces articles. La contribution centrale de cette thèse est d'analyser les systèmes de recommandation automatiques dans le contexte industriel, et notamment des besoins marketing, et de croiser cette analyse avec les travaux académiques.

L'accès aux informations pertinentes, adaptées aux besoins et au profil de l'utilisateur est un enjeu majeur dans le cadre actuel caractérisé par une prolifération massive des ressources d'information hétérogènes. Le développement d'appareils mobiles équipés de plusieurs fonctionnalités telles que la caméra, le WIFI, la géo-localisation et bien plus d'autres permettent aux systèmes mobiles de recommandation actuels d'être hautement contextualisés et pouvant fournir à l'utilisateur des informations pertinentes au bon moment quand il en a le plus besoin, sans attendre qu'il établisse une interaction avec son appareil. C'est dans ce cadre que s'insère notre travail de thèse. En effet, nous proposons une approche de recommandation contextuelle et proactive dans un environnement mobile qui permet de recommander des informations pertinentes à l'utilisateur sans attendre à ce que ce dernier initie une interaction. Un système proactif peut prendre la forme d'un guide touristique personnalisé qui se base sur la localisation et les préférences de l'utilisateur pour suggérer à ce dernier des endroits intéressants sans qu'il fournisse, sa préférence ou une requête explicite. Cela permettra de réduire les efforts, le temps et l'interaction de l'utilisateur avec son appareil mobile et de présenter les informations pertinentes au bon moment et au bon endroit. Cette approche prend aussi en considération les situations où la recommandation pourrait déranger l'utilisateur. Il s'agit d'équilibrer le processus de recommandation contre les interruptions intrusives. En effet, il existe différents facteurs et situations qui rendent l'utilisateur moins ouvert aux recommandations. Comme nous travaillons dans le contexte des appareils mobiles, nous considérons que les applications mobiles telles que la caméra, le clavier, l'agenda, etc., sont de bons représentants de l'interaction de l'utilisateur avec son appareil puisqu'ils représentent en quelque sorte la plupart des activités qu'un utilisateur pourrait entreprendre avec son appareil mobile au quotidien, comme envoyer des messages, converser, tweeter, naviguer ou prendre des photos. / Just-In-Time recommender systems involve all systems able to provide recommendations tailored to the preferences and needs of users in order to help them access useful and interesting resources within a large data space. The user does not need to formulate a query, this latter is implicit and corresponds to the resources that match the user's interests at the right time. Our work falls within this framework and focuses on developing a proactive context-aware recommendation approach for mobile devices that covers many domains. It aims at recommending relevant items that match users' personal interests at the right time without waiting for the users to initiate any interaction. Indeed, the development of mobile devices equipped with persistent data connections, geolocation, cameras and wireless capabilities allows current context-aware recommender systems (CARS) to be highly contextualized and proactive. We also take into consideration to which degree the recommendation might disturb the user. It is about balancing the process of recommendation against intrusive interruptions. As a matter of fact, there are different factors and situations that make the user less open to recommendations. As we are working within the context of mobile devices, we consider that mobile applications functionalities such as the camera, the keyboard, the agenda, etc., are good representatives of the user's interaction with his device since they somehow stand for most of the activities that a user could use in a mobile device in a daily basis such as texting messages, chatting, tweeting, browsing or taking selfies and pictures.

The development of Web 2.0 has resulted in the generation of a vast amount of online discussions. Mining and extracting quality knowledge from online discussions is significant for the industrial and marketing sector, as well as for e-commerce applications. Discussions of this kind encapsulate people's interests and beliefs and hence, there is a great interest in acquiring and developing online discussion analysis tools. The objective of this thesis is to define a model which represents online discussions and facilitates their analysis. We propose a graph-oriented model. The vertices of the graph represent postings. Each posting encapsulates information such as the content of the message, the author who has written it, the opinion polarity of the message and the time that the message was posted. The edges among the postings point out a "reply-to" relation. In other words they show which posting replies to what as it is given by the structure of the online discussion.The proposed model is accompanied by a number of measures which facilitate the discussion mining and the extraction of knowledge from it. Defined measures consist in measures that are underlined by the structure of the discussion and the way the postings are linked to each other. There are opinion-oriented measures which deal with the opinion evolution within a discussion. Time-oriented measures exploit the presence of the temporal dimension within a model, while topic-oriented measures can be used in order to measure the presence of topics within a discussion. The user's presence inside the online discussions can be exploited either by social network techniques or through the new model which encapsulates knowledge about the author of each posting.The representation of an online discussion in the proposed way allows a user to "zoom" inside the discussion. A recommendation of messages is proposed to the user to enable a more efficient participation inside the discussion.Additionally, a prototype system has been implemented which allows the user to mine online discussions by selecting a subset of postings and browse through them efficiently. / 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. Les mesures sont définies par la structure de la discussion et la façon dont les objets messages sont liés entre eux. 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 représentation d'une discussion en ligne de la manière proposée permet à un utilisateur de "zoomer" dans une discussion. Une liste de messages clés est recommandée à l'utilisateur pour permettre une participation plus efficace au sein de la discussion. De plus, un système prototype a été implémenté pour permettre à l'utilisateur de fouiller les discussions en ligne en sélectionnant un sous ensemble d'objets de type message et naviguer à travers ceux-ci de manière efficace.

Nous sommes à l’aube d’une nouvelle ère du data mining, celle du stockage, traitement, analyse et exploitation des données massives que l’on appelle Big Data. Les données sont devenues une nouvelle matière première, très prisée par les entreprises de tout type et de toute taille à travers le monde ; elles permettent d’analyser, de comprendre, de modéliser et d’expliquer certains phénomènes comme le comportement et les préférences des utilisateurs ou clients d’une entreprise donnée. La compréhension des préférences des utilisateurs et des clients d’une entreprise permet de leur proposer de la publicité ciblée afin d’augmenter les ventes et la satisfaction des clients et ainsi pouvoir améliorer les revenues de l’entreprise, ce que les géants du Web comme Google, Facebook, LinkedIn et Twitter ont bien compris. Cette thèse de doctorat a été réalisée dans le cadre d’une convention CIFRE entre le laboratoire L2TI de l’université Paris 13 et la start-up franco-américaineWork4 qui développe des applications de recrutement sur Facebook. Son objectif principal était la mise au point d’un ensemble d’algorithmes et méthodes pour proposer aux utilisateurs des réseaux sociaux les offres d’emploi les plus pertinentes. Le développement de nos algorithmes de recommandation a nécessité de surmonter de nombreuses difficultés telles que le préservation de la vie privée des utilisateurs des réseaux sociaux, le traitement des données bruitées et incomplètes des utilisateurs et des offres d’emploi, la difficulté de traitement des données multi-langues et, plus généralement, la difficulté d’extraire automatiquement les offres d’emploi pertinentes pour un utilisateur donné parmi un ensemble d’offres d’emploi. Les systèmes développés durant cette thèse sont principalement basés sur les techniques de systèmes de recommandation, de recherche documentaire,de fouille de données et d’apprentissage artificiel ; ils ont été validés sur des jeux de données réels collectés par l’entreprise Work4. Dans le cadre de cette étude, les utilisateurs d’un réseau social sont liés à trois types entités : les offres d’emploi qui leur sont pertinentes, les autres utilisateurs du réseau social auxquels ils se sont liés d’amitié et les données personnelles qu’ils ont publiées sur leurs profils. Les profils des utilisateurs des réseaux sociaux et la description de nos offres d’emploi sont constitués de plusieurs champs contenant des informations textuelles. / We are entering a new era of data mining in which the main challenge is the storing andprocessing of massive data : this is leading to a new promising research and industry field called Big data. Data are currently a new raw material coveted by businesses of all sizes and all sectors. They allow organizations to analyze, understand, model and explain phenomen a such as the behavior of their users or customers. Some companies like Google, Facebook,LinkedIn and Twitter are using user data to determine their preferences in order to make targeted advertisements to increase their revenues.This thesis has been carried out in collaboration between the laboratory L2TI andWork4, a French-American startup that offers Facebook recruitment solutions. Its main objective was the development of systems recommending relevant jobs to social network users ; the developed systems have been used to advertise job positions on social networks. After studying the literature about recommender systems, information retrieval, data mining and machine learning, we modeled social users using data they posted on their profiles, those of their social relationships together with the bag-of-words and ontology-based models. We measure the interests of users for jobs using both heuristics and models based on machine learning. The development of efficient job recommender systems involved to tackle the problem of categorization and summarization of user profiles and job descriptions. After developing job recommender systems on social networks, we developed a set of systems called Work4 Oracle that predict the audience (number of clicks) of job advertisements posted on Facebook, LinkedIn or Twitter. The analysis of the results of Work4 Oracle allows us to find and quantify factors impacting the popularity of job ads posted on social networks, these results have been compared to those of the literature of Human Resource Management. All our proposed systems deal with privacy preservation by only using the data that social network users explicitly allowed to access to ; they also deal with noisy and missing data of social network users and have been validated on real-world data provided by Work4.

Les systèmes de recommandation essayent de déduire les intérêts de leurs utilisateurs afin de leurs suggérer des items pertinents. Ces systèmes offrent ainsi aux utilisateurs un service utile car ils filtrent automatiquement les informations non-pertinentes, ce qui évite le problème de surcharge d’information qui est courant de nos jours. C’est pourquoi les systèmes de recommandation sont aujourd’hui populaires, si ce n’est omniprésents dans certains domaines tels que le World Wide Web. Cependant, les intérêts d’un individu sont des données personnelles et privées, comme par exemple son orientation politique ou religieuse. Les systèmes de recommandation recueillent donc des données privées et leur utilisation répandue nécessite des mécanismes de protection de la vie privée. Dans cette thèse, nous étudions la protection de la confidentialité des intérêts des utilisateurs des systèmes de recommandation appelés systèmes de filtrage collaboratif (FC). Notre première contribution est Hide & Share, un nouveau mécanisme de similarité, respectueux de la vie privée, pour la calcul décentralisé de graphes de K-Plus-Proches-Voisins (KPPV). C’est un mécanisme léger, conçu pour les systèmes de FC fondés sur les utilisateurs et décentralisés (ou pair-à-pair), qui se basent sur les graphes de KPPV pour fournir des recommandations. Notre seconde contribution s’applique aussi aux systèmes de FC fondés sur les utilisateurs, mais est indépendante de leur architecture. Cette contribution est double : nous évaluons d’abord l’impact d’une attaque active dite « Sybil » sur la confidentialité du profil d’intérêts d’un utilisateur cible, puis nous proposons une contre-mesure. Celle-ci est 2-step, une nouvelle mesure de similarité qui combine une bonne précision, permettant ensuite de faire de bonnes recommandations, avec une bonne résistance à l’attaque Sybil en question. / Recommendation systems try to infer their users’ interests in order to suggest items relevant to them. These systems thus offer a valuable service to users in that they automatically filter non-relevant information, which avoids the nowadays common issue of information overload. This is why recommendation systems are now popular, if not pervasive in some domains such as the World Wide Web. However, an individual’s interests are personal and private data, such as one’s political or religious orientation. Therefore, recommendation systems gather private data and their widespread use calls for privacy-preserving mechanisms. In this thesis, we study the privacy of users’ interests in the family of recommendation systems called Collaborative Filtering (CF) ones. Our first contribution is Hide & Share, a novel privacy-preserving similarity mechanism for the decentralized computation of K-Nearest-Neighbor (KNN) graphs. It is a lightweight mechanism designed for decentralized (a.k.a. peer-to-peer) user-based CF systems, which rely on KNN graphs to provide recommendations. Our second contribution also applies to user-based CF systems, though it is independent of their architecture. This contribution is two-fold: first we evaluate the impact of an active Sybil attack on the privacy of a target user’s profile of interests, and second we propose a counter-measure. This counter-measure is 2-step, a novel similarity metric combining a good precision, in turn allowing for good recommendations,with high resilience to said Sybil attack.