L'objectif principal de cette thèse est de développer un algorithme dynamique de partitionnement de données (classification non supervisée ou " clustering " en anglais) qui ne se limite pas à des concepts statiques et qui peut gérer des distributions qui évoluent au fil du temps. Cet algorithme peut être utilisé dans les systèmes de surveillance du processus, mais son application ne se limite pas à ceux-ci. Les contributions de cette thèse peuvent être présentées en trois groupes: 1. Contributions au partitionnement dynamique de données en utilisant : un algorithme de partitionnement dynamique basé à la fois sur la distance et la densité des échantillons est présenté. Cet algorithme ne fait aucune hypothèse sur la linéarité ni la convexité des groupes qu'il analyse. Ces clusters, qui peuvent avoir des densités différentes, peuvent également se chevaucher. L'algorithme développé fonctionne en ligne et fusionne les étapes d'apprentissage et de reconnaissance, ce qui permet de détecter et de caractériser de nouveaux comportements en continu tout en reconnaissant l'état courant du système. 2. Contributions à l'extraction de caractéristiques : une nouvelle approche permettant d'extraire des caractéristiques dynamiques est présentée. Cette approche, basée sur une approximation polynomiale par morceaux, permet de représenter des comportements dynamiques sans perdre les informations relatives à la magnitude et en réduisant simultanément la sensibilité de l'algorithme au bruit dans les signaux analysés. 3. Contributions à la modélisation de systèmes à événements discrets évolutifs a partir des résultats du clustering : les résultats de l'algorithme de partitionnement sont utilisés comme base pour l'élaboration d'un modèle à événements discrets du processus. Ce modèle adaptatif offre une représentation du comportement du processus de haut niveau sous la forme d'un automate dont les états représentent les états du processus appris par le partitionnement jusqu'à l'instant courant et les transitions expriment l'atteignabilité des états. / The main objective of this thesis is to propose a dynamic clustering algorithm that can handle not only dynamic data but also evolving distributions. This algorithm is particularly fitted for the monitoring of processes generating massive data streams, but its application is not limited to this domain. The main contributions of this thesis are: 1. Contribution to dynamic clustering by the proposal of an approach that uses distance- and density-based analyses to cluster non-linear, non-convex, overlapped data distributions with varied densities. This algorithm, that works in an online fashion, fusions the learning and lassification stages allowing to continuously detect and characterize new concepts and at the same time classifying the input samples, i.e. which means recognizing the current state of the system in a supervision application. 2. Contribution to feature extraction by the proposal of a novel approach to extract dynamic features. This approach ,based on piece-polynomial approximation, allows to represent dynamic behaviors without losing magnitude related information and to reduce at the same time the algorithm sensitivity to noise corrupting the signals. 3. Contribution to automatic discrete event modeling for evolving systems by exploiting informations brought by the clustering. The generated model is presented as a timed automaton that provides a high-level representation of the behavior of the process. The latter is adaptive in the sense that its construction is elaborated following the discovery of new concepts by the clustering algorithm.

Les travaux effectués lors de cette thèse concernent principalement la triangulation de Delaunay. On montre que la complexité en moyenne - en termes de sites inachevés - du processus de fusion multidimensionnelle dans l'hypothèse de distribution quasi-uniforme dans un hypercube est linéaire en moyenne. Ce résultat général est appliqué au cas du plan et permet d'analyser de nouveaux algorithmes de triangulation de Delaunay plus performants que ceux connus à ce jour. Le principe sous-jacent est de diviser le domaine selon des arbres bidimensionnels (quadtree, 2d-tree, bucket-tree. . . ) puis de fusionner les cellules obtenues selon deux directions. On étudie actuellement la prise en compte de contraintes directement pendant la phase de triangulation avec des algorithmes de ce type. De nouveaux algorithmes pratiques de localisation dans une triangulation sont proposés, basés sur la randomisation à partir d'un arbre binaire de recherche dynamique de type AVL, dont l'un est plus rapide que l'algorithme optimal de Kirkpatrick, au moins jusqu'à 12 millions de sites K Nous travaillons actuellement sur l'analyse rigoureuse de leur complexité en moyenne. Ce nouvel algorithme est utilisé pour construire " en-ligne " une triangulation de Delaunay qui est parmi les plus performantes des méthodes " en-ligne " connues à ce jour.