L'objectif de cette thèse est de trouver des techniques de détection et de localisation des anomalies au niveau des liens qui soient à faible coût, précises et rapides. La plupart des techniques de détection et de localisation des anomalies au niveau des liens qui existent dans la littérature calculent les solutions, c-à-d l'ensemble des chemins à monitorer et les emplacements des dispositifs de monitorage, en deux étapes. La première étape sélectionne un ensemble minimal d'emplacements des dispositifs de monitorage qui permet de détecter/localiser toutes les anomalies possibles. La deuxième étape sélectionne un ensemble minimal de chemins de monitorage entre les emplacements sélectionnés de telle sorte que tous les liens du réseau soient couverts/distinguables paire par paire. Toutefois, ces techniques ignorent l'interaction entre les objectifs d'optimisation contradictoires des deux étapes, ce qui entraîne une utilisation sous-optimale des ressources du réseau et des mesures de monitorage biaisées. L'un des objectifs de cette thèse est d'évaluer et de réduire cette interaction. A cette fin, nous proposons des techniques de détection et de localisation d'anomalies au niveau des liens qui sélectionnent les emplacements des moniteurs et les chemins qui doivent être monitorés conjointement en une seule étape. Par ailleurs, nous démontrons que la condition établie pour la localisation des anomalies est suffisante mais pas nécessaire. Une condition nécessaire et suffisante qui minimise le coût de localisation considérablement est établie. Il est démontré que les deux problèmes sont NP-durs. Des algorithmes heuristiques scalables et efficaces sont alors proposés. / The aim of this thesis is to come up with cost-efficient, accurate and fast schemes for link-level network anomaly detection and localization. It has been established that for detecting all potential link-level anomalies, a set of paths that cover all links of the network must be monitored, whereas for localizing all potential link-level anomalies, a set of paths that can distinguish between all links of the network pairwise must be monitored. Either end-node of each path monitored must be equipped with a monitoring device. Most existing link-level anomaly detection and localization schemes are two-step. The first step selects a minimal set of monitor locations that can detect/localize any link-level anomaly. The second step selects a minimal set of monitoring paths between the selected monitor locations such that all links of the network are covered/distinguishable pairwise. However, such stepwise schemes do not consider the interplay between the conflicting optimization objectives of the two steps, which results in suboptimal consumption of the network resources and biased monitoring measurements. One of the objectives of this thesis is to evaluate and reduce this interplay. To this end, one-step anomaly detection and localization schemes that select monitor locations and paths that are to be monitored jointly are proposed. Furthermore, we demonstrate that the already established condition for anomaly localization is sufficient but not necessary. A necessary and sufficient condition that minimizes the localization cost drastically is established. The problems are demonstrated to be NP-Hard. Scalable and near-optimal heuristic algorithms are proposed.

Les réseaux complexes constituent un outil pratique pour modéliser les systèmes complexes réels. Pour cette raison, ils sont devenus très populaires au cours de la dernière décennie. De nombreux outils existent pour étudier les réseaux complexes. Parmi ceux-ci, la détection de la communauté est l’un des plus importants. Une communauté est grossièrement définie comme un groupe de nœuds plus densément connectés entre eux qu’avec le reste du réseau. Dans la littérature, cette définition intuitive a été formalisée de plusieurs différentes façons, ce qui a conduit à d’innombrables méthodes et variantes permettant de les détecter. Du point de vue applicatif, le sens des communautés est aussi important que leur détection. Cependant, bien que la tâche de détection de communautés en elle-même ait attiré énormément d’attention, le problème de leur interprétation n’a pas été sérieusement abordé jusqu’à présent. Dans cette thèse, nous voyons l’interprétation des communautés comme un problème indépendant du processus de leur détection, consistant à identifier les éléments leurs caractéristiques les plus typiques. Nous le décomposons en deux sous-problèmes : 1) trouver un moyen approprié pour représenter une communauté ; et 2) sélectionner de façon objective les parties les plus caractéristiques de cette représentation. Pour résoudre ces deux sous-problèmes, nous exploitons l’information encodée dans les réseaux dynamiques attribués. Nous proposons une nouvelle représentation des communautés sous la forme de séquences temporelles de descripteurs associés à chaque nœud individuellement. Ces descripteurs peuvent être des mesures topologiques et des attributs nodaux. Nous détectons ensuite les motifs séquentiels émergents dans cet ensemble de données, afin d’identifier les ceux qui sont les plus caractéristiques de la communauté. Nous effectuons une validation de notre procédé sur des réseaux attribués dynamiques générés artificiellement. A cette occasion, nous étudions son comportement relativement à des changements structurels de la structure de communautés, à des modifications des valeurs des attributs. Nous appliquons également notre procédé à deux systèmes du monde réel : un réseau de collaborations scientifiques issu de DBLP, et un réseau d’interactions sociales et musicales tiré du service LastFM. Nos résultats montrent que les communautés détectées ne sont pas complètement homogènes. Certaines communautés sont composées de petits groupes de nœuds qui ont tendance à évoluer ensemble au cours du temps, que ce soit en termes de propriétés individuelles ou collectives. Les anomalies détectées correspondent généralement à des profils typiques : nœuds mal placés par l’outil de détection de communautés, ou nœuds différant des tendances de leur communautés sur certains points, et/ou non-synchrones avec l’évolution de leur communauté, ou encore nœuds complètement différents. / Complex Networks constitute a convenient tool to model real-world complex systems. For this reason, they have become very popular in the last decade. Many tools exist to study complex networks. Among them, community detection is one of the most important. A community is roughly defined as a group of nodes more connected internally than to the rest of the network. In the literature, this intuitive definition has been formalized in many ways, leading to countless different methods and variants to detect communities. In the large majority of cases, the result of these methods is set of node groups in which each node group corresponds to a community. From the applicative point of view, the meaning of these groups is as important as their detection. However, although the task of detecting communities in itself took a lot of attraction, the problem of interpreting them has not been properly tackled until now. In this thesis, we see the interpretation of communities as a problem independent from the community detection process, consisting in identifying the most characteristic features of communities. We break it down into two sub-problems: 1) finding an appropriate way to represent a community and 2) objectively selecting the most characteristic parts of this representation. To solve them, we take advantage of the information encoded in dynamic attributed networks. We propose a new representation of communities under the form of temporal sequences of topological measures and attribute values associated to individual nodes. We then look for emergent sequential patterns in this dataset, in order to identify the most characteristic community features. We perform a validation of our framework on artificially generated dynamic attributed networks. At this occasion, we study its behavior relatively to changes in the temporal evolution of the communities, and to the distribution and evolution of nodal features. We also apply our framework to real-world systems: a DBLP network of scientific collaborations, and a LastFM network of social and musical interactions. Our results show that the detected communities are not completely homogeneous, in the sense several node topic or interests can be identified for a given community. Some communities are composed of smaller groups of nodes which tend to evolve together as time goes by, be it in terms of individual (attributes, topological measures) or relational (community migration) features. The detected anomalies generally fit some generic profiles: nodes misplaced by the community detection tool, nodes relatively similar to their communities, but also significantly different on certain features and/or not synchronized with their community evolution, and finally nodes with completely different interests.

De nos jours, l'informatique omniprésente fait face à un progrès croissant. Ce paradigme est caractérisé par de multiples capteurs intégrés dans des objets du monde physique. Le développement d'applications personnelles utilisant les données fournies par ces capteurs a conduit à la création d'environnements intelligents, conçus comme un framework de superposition avancé qui aide de manière proactive les individus dans leur vie quotidienne. Une application d’environnement intelligent collecte les données de capteurs deployés d'une façon en continu , traite ces données et les analyse avant de prendre des décisions pour exécuter des actions sur l’environnement physique. Le traitement de données en ligne consiste principalement en une segmentation des données pour les diviser en fragments. Généralement, dans la littérature, la taille des fragments est fixe. Cependant, une telle vision statique entraîne généralement des problèmes de résultats imprécis. Par conséquent, la segmentation dynamique utilisant des tailles variables de fenêtres d’observation est une question ouverte. La phase d'analyse prend en entrée un segment de données de capteurs et extrait des connaissances au moyen de processus de raisonnement ou d'extraction. La compréhension des activités quotidiennes des utilisateurs et la prévention des situations anormales sont une préoccupation croissante dans la littérature, mais la résolution de ces problèmes à l'aide de données de petite taille et imparfaites reste un problème clé. En effet, les données fournies par les capteurs sont souvent imprécises, inexactes, obsolètes, contradictoires ou tout simplement manquantes. Par conséquent, l'incertitude liée à la gestion est devenue un aspect important. De plus, il n'est pas toujours possible et trop intrusif de surveiller l'utilisateur pour obtenir une grande quantité de données sur sa routine de vie. Les gens ne sont pas souvent ouverts pour être surveillés pendant une longue période. Évidemment, lorsque les données acquises sur l'utilisateur sont suffisantes, la plupart des méthodes existantes peuvent fournir une reconnaissance précise, mais les performances baissent fortement avec de petits ensembles de données. Dans cette thèse, nous avons principalement exploré la fertilisation croisée d'approches d'apprentissage statistique et symbolique et les contributions sont triples: (i) DataSeg, un algorithme qui tire parti à la fois de l'apprentissage non supervisé et de la représentation ontologique pour la segmentation des données. Cette combinaison choisit de manière dynamique la taille de segment pour plusieurs applications, contrairement à la plupart des méthodes existantes. De plus, contrairement aux approches de la littérature, Dataseg peut être adapté à toutes les fonctionnalités de l’application; (ii) AGACY Monitoring, un modèle hybride de reconnaissance d'activité et de gestion des incertitudes qui utilise un apprentissage supervisé, une inférence de logique possibiliste et une ontologie permettant d'extraire des connaissances utiles de petits ensembles de données; (iii) CARMA, une méthode basée sur les réseaux de Markov et les règles d'association causale pour détecter les causes d'anomalie dans un environnement intelligent afin d'éviter leur apparition. En extrayant automatiquement les règles logiques concernant les causes d'anomalies et en les intégrant dans les règles MLN, nous parvenons à une identification plus précise de la situation, même avec des observations partielles. Chacune de nos contributions a été prototypée, testée et validée à l'aide de données obtenues à partir de scénarios réels réalisés. / Nowadays, pervasive computing is facing an increasing advancement. This paradigm is characterized by multiple sensors highly integrated in objects of the physical world.The development of personal applications using data provided by these sensors has prompted the creation of smart environments, which are designed as an overlay advanced framework that proactively, but sensibly, assist individuals in their every day lives. A smart environment application gathers streaming data from the deployed sensors, processes and analyzes the collected data before making decisions and executing actions on the physical environment. Online data processing consists mainly in data segmentation to divide data into fragments. Generally, in the literature, the fragment size is fixed. However, such static vision usually brings issues of imprecise outputs. Hence, dynamic segmentation using variable sizes of observation windows is an open issue. The analysis phase takes as input a segment of sensor data and extract knowledge by means of reasoning or mining processes. In particular, understanding user daily activities and preventing anomalous situations are a growing concern in the literature but addressing these problems with small and imperfect data is still a key issue. Indeed, data provided by sensors is often imprecise, inaccurate, outdated, in contradiction, or simply missing. Hence, handling uncertainty became an important aspect. Moreover, monitoring the user to obtain a large amount of data about his/her life routine is not always possible and too intrusive. People are not often open to be monitored for a long period of time. Obviously, when the acquired data about the user are sufficient, most existing methods can provide precise recognition but the performances decline sharply with small datasets.In this thesis, we mainly explored cross-fertilization of statistic and symbolic learning approaches and the contributions are threefold: (i) DataSeg, an algorithm that takes advantage of both unsupervised learning and ontology representation for data segmentation. This combination chooses dynamically the segment size for several applications unlike most of existing methods. Moreover, unlike the literature approaches, Dataseg is able to be adapted to any application features; (ii) AGACY Monitoring, a hybrid model for activity recognition and uncertainty handling which uses supervised learning, possibilistic logic inference, and an ontology to extract meaningful knowledge from small datasets; (iii) CARMA, a method based on Markov Logic Networks (MLN) and causal association rules to detect anomaly causes in a smart environment so as to prevent their occurrence. By automatically extracting logic rules about anomalies causes and integrating them in the MLN rules, we reach a more accurate situation identification even with partial observations. Each of our contributions was prototyped, tested and validated through data obtained from real scenarios that are realized.

Aujourd'hui, le contrôle des procédés de fabrication est une tâche essentielle pour assurer une production de haute qualité. A la fin du processus de fabrication du semi-conducteur, un test électrique, appelé test paramétrique (PT), est effectuée. PT vise à détecter les plaques dont le comportement électrique est anormal, en se basant sur un ensemble de paramètres électriques statiques mesurées sur plusieurs sites de chaque plaque. Le but de ce travail est de mettre en place un système de détection dynamique au niveau de PT, pour détecter les plaques anormales à partir d'un historique récent de mesures électriques. Pour cela, nous développons un système de détection en temps réel basé sur une technique de réapprentissage optimisée, où les données d'apprentissage et le modèle de détection sont mis à jour à travers une fenêtre temporelle glissante. Le modèle de détection est basé sur les machines à vecteurs supports à une classe (1-SVM), une variante de l'algorithme d'apprentissage statistique SVM largement utilisé pour la classification binaire. 1-SVM a été introduit dans le cadre des problèmes de classification à une classe pour la détection des anomalies. Pour améliorer la performance prédictive de l'algorithme de classification 1-SVM, deux méthodes de sélection de variables ont été développées. La première méthode de type filtrage est basé sur un score calculé avec le filtre MADe,une approche robuste pour la détection univariée des valeurs aberrantes. La deuxième méthode de type wrapper est une adaptation à l'algorithme 1-SVM de la méthode d'élimination récursive des variables avec SVM (SVM-RFE). Pour les plaques anormales détectées, nous proposons une méthode permettant de déterminer leurs signatures multidimensionnelles afin d'identifier les paramètres électriques responsables de l'anomalie. Finalement, nous évaluons notre système proposé sur des jeux de données réels de STMicroelecronics, et nous le comparons au système de détection basé sur le test de T2 de Hotelling, un des systèmes de détection les plus connus dans la littérature. Les résultats obtenus montrent que notre système est performant et peut fournir un moyen efficient pour la détection en temps réel. / Nowadays, control of manufacturing process is an essential task to ensure production of high quality. At the end of the semiconductor manufacturing process, an electric test, called Parametric Test (PT), is performed. The PT aims at detecting wafers whose electrical behavior is abnormal, based on a set of static electrical parameters measured on multiple sites of each wafer. The purpose of this thesis is to develop a dynamic detection system at PT level to detect abnormal wafers from a recent history of electrical measurements. For this, we develop a real time detection system based on an optimized learning technique, where training data and detection model are updated through a moving temporal window. The detection scheme is based on one class Support Vector Machines (1-SVM), a variant of the statistical learning algorithm SVM widely used for binary classification. 1-SVM was introduced in the context of one class classification problems for anomaly detection. In order to improve the predictive performance of the 1-SVM classification algorithm, two variable selection methods are developed. The first one is a filter method based on a calculated score with MADe filter, a robust approach for univariate outlier detection. The second one is of wrapper type that adapts the SVM Recursive Feature Elimination method (SVM-RFE) to the 1-SVM algorithm. For detected abnormal wafers, we propose a method to determine their multidimensional signatures to identify the electrical parameters responsible for the anomaly. Finally, we evaluate our proposed system on real datasets of STMicroelecronics and compare it to the detection system based on Hotelling's T2 test, one of the most known detection systems in the literature. The results show that our system yields very good performance and can provide an efficient way for real-time detection.

Les traces réelles de réseaux cellulaires représentent une mine d’information utile pour améliorer les performances des réseaux. Des traces comme les CDRs (Call detail records) contiennent des informations horodatées sur toutes les interactions des utilisateurs avec le réseau sont exploitées dans cette thèse. Nous avons proposé des nouvelles approches dans l’étude et l’analyse des problématiques des réseaux de télécommunications, qui sont basé sur les traces réelles et des algorithmes d’apprentissage automatique. En effet, un outil global d’analyse de données, pour la classification automatique des stations de base, la prédiction de la charge de réseau et la gestion de la bande passante est proposé ainsi qu’un outil pour la détection automatique des anomalies de réseau. Ces outils ont été validés par des applications directes, et en utilisant différentes topologies de réseaux comme les réseaux WMN et les réseaux basés sur les drone-cells. Nous avons montré ainsi, qu’en utilisant des outils d’analyse de données avancés, il est possible d’optimiser dynamiquement les réseaux mobiles et améliorer la gestion de la bande passante. / Real datasets of mobile network traces contain valuable information about the network resources usage. These traces may be used to enhance and optimize the network performances. A real dataset of CDR (Call Detail Records) traces, that include spatio-temporal information about mobile users’ activities, are analyzed and exploited in this thesis. Given their large size and the fact that these are real-world datasets, information extracted from these datasets have intensively been used in our work to develop new algorithms that aim to revolutionize the infrastructure management mechanisms and optimize the usage of resource. We propose, in this thesis, a framework for network profiles classification, load prediction and dynamic network planning based on machine learning tools. We also propose a framework for network anomaly detection. These frameworks are validated using different network topologies such as wireless mesh networks (WMN) and drone-cell based networks. We show that using advanced data mining techniques, our frameworks are able to help network operators to manage and optimize dynamically their networks