Search

In this thesis, we propose methods to approximate an anomaly score in order to detect abnormal parts in data streams. Two main problems are considered in this context. Firstly, the handling of the high dimensionality of the objects describing the time series extracted from the raw streams, and secondly, the low computation cost required to perform the analysis on-the-fly. To tackle the curse of dimensionality, we have selected the CFOF anomaly score, that has been proposed recently and proven to be robust to the increase of the dimensionality. Our main contribution is then the proposition of two methods to quickly approximate the CFOF score of new objects in a stream. The first one is based on safe pruning and approximation during the exploration of object neighbourhood. The second one is an approximation obtained by the aggregation of scores computed in several subspaces. Both contributions complete each other and can be combined. We show on a reference benchmark that our proposals result in important reduction of the execution times, while providing approximations that preserve the quality of anomaly detection. Then, we present our application of these approaches within the SNCF information system. In this context, we have extended the existing monitoring modules by a new tool to help to detect abnormal behaviours in the real stream of messages within the SNCF communication system., Dans cette thèse, nous proposons des méthodes de calcul approchées d'un score d'anomalie, pouvant être mises en oeuvre sur des flux de données pour détecter des portions anormales. La difficulté du problème est de deux ordres. D'une part, la haute dimensionnalité des objets manipulés pour décrire les séries temporelles extraites d'un flux brut, et d'autre part la nécessité de limiter le coût de détection afin de pouvoir la réaliser en continu au fil du flux. Concernant le premier aspect du problème, notre étude bibliographique a permis de sélectionner un score de détection d'anomalies proposé récemment, le score CFOF, qui est le seul pour lequel il existe des garanties formelles quant à son adéquation pour les données en haute dimensionnalité. Nos contributions ont alors porté sur la proposition de deux méthodes d'approximation du score CFOF pour permettre son usage en continu sur des flux. La première est une approche combinant élagage et approximation lors du parcours des voisinages dans l'espace de description des objets. Notre second apport est une approximation par agrégation de scores obtenus sur des sous-espaces, qui complète la première contribution et se combine avec elle. Nous avons montré sur une collection de jeux de données, utilisés comme cadre d'évaluation de référence dans le domaine, que nos méthodes permettaient des gains importants en temps de calcul, tout en fournissant des approximations qui préservent la qualité des détections. Enfin, nous présentons également l'application de ces approches au sein du système d'information de la SNCF dans lequel de nombreux flux sont collectés en temps réel, transformés et rediffusés. Dans ce contexte, nous avons étendu la supervision de bout-en-bout existante par la mise en oeuvre d'un outil d'aide à la détection d'anomalies sur le flux de messages entrant d'une des principales plateformes de traitement.

Body Sensor Networks (BSNs) are formed of medical sensors that gather physiological and activity data from the human body and its environment, and send them wirelessly to a personal device like Personal Digital Assistant (PDA) or a smartphone that acts as a gateway to health care. Collaborative Body Sensor Networks (CBSNs) are collection of BSNs that move in a given area and collaborate, interact and exchange data between each other to identify group activity, and monitor the status of single and multiple persons.In both BSN and CBNS networks, sending data with the highest Quality of Service (QoS) and performance metrics is crucial since the data sent affects people’s life. For instance, the sensed physiological data should be sent reliably and with minimal delay to take appropriate actions before it is too late, and the energy consumption of nodes should be preserved as they have limited capacities and they are expected to serve for a long period of time. The QoS in BSNs and CBSNs largely depends on the choice of the Medium Access Control (MAC) protocols, the adopted routing schemes, and the efficient and accuracy of anomaly detection.The current MAC, routing and anomaly detection schemes proposed for BSNs and CBSNs in the literature present many limitations and open the door toward more research and propositions in these areas. Thus this thesis work focuses on three main axes. The first axe consists in studying and designing new and robust MAC algorithms able to address BSNs and CBSNs' challenges. Standard MAC protocols are compared in high traffic BSNs and a new MAC protocol is proposed for such environments; then an emergency aware MAC scheme is presented to address the dynamic traffic requirements of BSN in ensuring delivery of emergency data within strict delay requirements, and energy efficiency of nodes during regular observations; moreover, a traffic and mobility aware MAC scheme is proposed for CBSNs to address both traffic and mobility requirements for these networks.The second axe consists in proposing a thorough and efficient routing scheme suitable for BSNs and CBSNs. First, different routing models are compared for CBSNs and a new routing scheme is proposed in the aim of reducing the delay of data delivery, and increasing the network throughput and the energy efficiency of nodes. The proposed scheme is then adapted to BSN's requirements to become a solid solution for the challenges faced by this network. The third axe involves proposing an adaptive sampling approach that guarantees high accuracy in the detection of emergency cases, while ensuring at the same time high energy efficiency of the sensors.In the three axes, the performance of the proposed schemes is qualitatively compared to existing algorithms in the literature; then simulations are carried a posteriori with respect to different performance metrics and under different scenarios to assess their efficiency and ability to face BSNs and CBSNs' challenges.Simulation results demonstrate that the proposed MAC, routing and anomaly detection schemes outperform the existing algorithms, and present strong solutions that satisfy BSNs and CBSNs' requirements., Les réseaux de capteurs corporels (RC2) sont constitués de bio-capteurs à faibles ressources énergétiques et de calcul. Ils collectent des données physiologiques du corps humain et de son environnement, et les transmettent à un coordinateur comme le PDA (Personal Digital Assistant) ou un smartphone, pour être acheminé ensuite aux experts de santé. Les réseaux de capteurs corporels collaboratifs (RC3) sont une collection de RC2 qui se déplacent dans une zone donnée et collaborent,interagissent et échangent des données entre eux pour identifier l'activité du groupe et surveiller l'état individuel et collectif des participants. Dans les réseaux RC2 et RC3, l'envoi de données de manière fiable tout en assurant une bonne Quality of Service (QoS) et une latence de données optimisée est crucial, vu la sensibilité des données collectées. La QoS dans ce type de réseaux dépend en grande partie du choix des protocoles de contrôle d'accès MAC (Medium Access Control) et des protocoles de routage, de l'efficacité énergétique, de la précision et de la détection des anomalies.Les protocoles existants dans la littérature et proposés pour les RC2et RC3 présentent de nombreuses limites au niveau de la latence de données, de la fiabilité, et de la détection de pannes. Le travail présenté dans cette thèse a trois objectifs principaux. Le premier consiste à étudier et concevoir de nouveaux algorithmes pour la couche MAC, robustes et capables de répondre aux défis de RC2 et RC3. Pour cela, nous avons conçu un nouveau protocole MAC qui prend en considération le trafic élevé et les contraintes de ressources dans ces types de réseaux, ainsi que la latence des données et l'urgence de relayer les informations sensibles. Le deuxième objectif consiste à proposer des protocoles de routage efficaces en termes de consommation d'énergie et de calcul, adaptés aux RC2 et RC3. Le troisième objectif est dédiée à l'étude d'un algorithme d’échantillonnage de données permettant de réduire la quantité de données collectées et transmises dans le réseau, sans perte d'information. Notre approche garantit la détection et l'envoi d'information en cas d'urgence tout en optimisant la consommation énergétique des nœuds. Pour montrer l'efficacité de nos approches, nous les avons testées dans un environnement de simulation OPNet dédié aux réseaux de capteurs et nous les avons comparées à plusieurs protocoles existants. Les résultats obtenus montrent l'efficacité de ces protocoles en termes d'optimisation de la consommation d'énergie, de latence et d'intégrité des données, et de détection d'anomalies.

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., 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.; 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, 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.; 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.

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., 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.

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., 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.

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., 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.