Tesi sul tema "Exploration sous contrainte"

Les services de chirurgies sont confrontés à des difficultés à répondre à la demande et les patients font face à de longues listes d’attente avant d’être traités. Afin d’améliorer les services, des délais maximums à respecter ont été mis en place pour certains types de chirurgie, ajoutant toutefois une contrainte au système surchargé. Finalement, l’annulation de chirurgies pour cause de manque de lits aux soins intensifs et sur les unités de soins est considérée comme assez fréquente, causant un goulot d’étranglement dans le flux de patients. Dans ce contexte, l’objectif de cette thèse est de proposer et de valider une procédure de planification des activités chirurgicales tenant compte de la capacité dans les unités de soins post-opératoires, dans le but d’améliorer l’utilisation des lits d’hospitalisation et ainsi d’augmenter le flux de patients dans le système. Cette thèse propose un outil d’aide à la décision pour formaliser le processus de planification des activités chirurgicales au niveau tactique/opérationnel et permettant de tenir compte de la disponibilité des lits d’hospitalisation et de la variabilité de la durée de séjour des patients, en fonction de différents facteurs. Cet outil tient compte du fonctionnement actuel du système et du contexte l’entourant en vue d’assurer la faisabilité de la mise en oeuvre. Dans un premier temps, un modèle de prédiction de la durée de séjour des patients est conçu en combinant une méthode de classification des données, soit les arbres de classification et de régression, avec une méthode permettant l’estimation de la distribution des données, les distributions phase-type. Une étape de validation permettra de comparer les résultats du modèle aux données empiriques. En second lieu, un outil de planification des activités chirurgicales est développé en utilisant la programmation linéaire en nombres entiers et en y incorporant la composante « durée de séjour des patients » dans le but de contrôler l’occupation des lits d’hospitalisation en plus de l’occupation des salles de chirurgies. Finalement, un simulateur est développé et utilisé pour permettre d’évaluer différentes stratégies et critères d’ordonnancement des activités en plus de tenir compte de la variabilité inhérente au problème. À ce niveau il est possible d’intégrer le modèle de prévision des durées de séjour développé en début de projet
Surgical services face difficulties in meeting demand and patients face long waiting lists for treatment. In order to improve services, maximum deadlines have been set for certain types of surgery, but this adds a constraint to the already overloaded system. Finally, the cancellation of surgeries due to a lack of beds in intensive care and on care units is considered quite frequent, causing a bottleneck in the patient flow. In this context, the objective of this thesis is to propose and validate a surgical activity planning procedure that takes into account capacity in post-operative care units, with the aim of improving the use of hospital beds and thus increasing patient flow in the system. This thesis proposes a decision support tool to formalize the surgical activity planning process at the tactical/operational level and to take into account the availability of hospital beds and the variability in patients' length of stay according to different factors. This tool takes into account the current functioning of the system and the context surrounding it in order to ensure the feasibility of implementation. First, a model for predicting the length of patients' stay is designed by combining a data classification method, classification and regression tree theory, with a method for estimating the data distribution, phase-type distributions. A validation step will compare the model results with empirical data. Second, a surgical activity planning tool is being developed using integer linear programming and incorporating the "length of stay" component to control hospital bed occupancy in addition to surgical room occupancy. Finally, a simulator is developed and used to evaluate different strategies and criteria for scheduling activities and to take into account the inherent variability of the problem. At this point, it is possible to integrate the model for predicting the length of stay developed at the beginning of the project

Une application majeure de l'apprentissage machine automatisée est la personnalisation des différents contenus recommandé à différents utilisateurs. Généralement, les algorithmes étant à la base de ces systèmes sont dit supervisé. C'est-à-dire que les données utilisées lors de la phase d'apprentissage sont supposées provenir de la même distribution. Cependant, ces données sont générées par des interactions entre un utilisateur et ces mêmes algorithmes. Ainsi, les recommandations pour un utilisateur à un instant t peuvent modifier l'ensemble des recommandations pertinentes à un instant ultérieur. Il est donc nécessaire de prendre en compte ces interactions afin de produire un service de la meilleure qualité possible. Ce type d'interaction est réminiscente du problème d'apprentissage en ligne. Parmi les algorithmes dit en ligne, les algorithmes de bandits et d'apprentissage par Renforcement (AR) semblent être les mieux positionnés afin de remplacer les méthodes d'apprentissage supervisé pour des applications nécessitant un certain degré de personnalisation. Le déploiement en production d'algorithmes d'apprentissage par Renforcement présente un certain nombre de difficultés tel que garantir un certain niveau de performance lors des phases d'exploration ou encore comment garantir la confidentialité des données collectées par ces algorithmes. Dans cette thèse nous considérons différentes contraintes freinant l’utilisation d’algorithmes d’apprentissage par renforcement, en fournissant des résultats à la fois empirique et théorique sur la vitesse d’apprentissage en présence de différentes contraintes
A major application of machine learning is to provide personnalized content to different users. In general, the algorithms powering those recommandation are supervised learning algorithm. That is to say the data used to train those algorithms are assumed to be sampled from the same distribution. However, the data are generated through interactions between the users and the recommendation algorithms. Thus, recommendations for a user a time t can have an impact on the set of pertinent recommandation at a later time. Therefore, it is necessary to take those interactions into account. This setting is reminiscent of the online learning setting. Among online learning algorithms, Reinforcement Learning algorithms (RL) looks the most promising to replace supervised learning algorithms for applications requiring a certain degree of personnalization. The deployement in production of RL algorithms presents some challenges such as being able to guarantee a certain level of performance during exploration phases or how to guarantee privacy of the data collected by RL algorithms. In this thesis, we consider different constraints limiting the use of RL algorithms and provides both empirical and theoretical results on the impact of those constraints on the learning process

La prise de décision est un domaine très étudié en sciences, que ce soit en neurosciences pour comprendre les processus sous tendant la prise de décision chez les animaux, qu’en robotique pour modéliser des processus de prise de décision efficaces et rapides dans des tâches en environnement réel. En neurosciences, ce problème est résolu online avec des modèles de prises de décision séquentiels basés sur l’apprentissage par renforcement. En robotique, l’objectif premier est l’efficacité, dans le but d’être déployés en environnement réel. Cependant en robotique ce que l’on peut appeler le budget et qui concerne les limitations inhérentes au matériel, comme les temps de calculs, les actions limitées disponibles au robot ou la durée de vie de la batterie du robot, ne sont souvent pas prises en compte à l’heure actuelle. Nous nous proposons dans ce travail de thèse d’introduire la notion de budget comme contrainte explicite dans les processus d’apprentissage robotique appliqués à une tâche de localisation en mettant en place un modèle basé sur des travaux développés en apprentissage statistique qui traitent les données sous contrainte de budget, en limitant l’apport en données ou en posant une contrainte de temps plus explicite. Dans le but d’envisager un fonctionnement online de ce type d’algorithmes d’apprentissage budgétisé, nous discutons aussi certaines inspirations possibles qui pourraient être prises du côté des neurosciences computationnelles. Dans ce cadre, l’alternance entre recherche d’information pour la localisation et la décision de se déplacer pour un robot peuvent être indirectement liés à la notion de compromis exploration-exploitation. Nous présentons notre contribution à la modélisation de ce compromis chez l’animal dans une tâche non stationnaire impliquant différents niveaux d’incertitude, et faisons le lien avec les méthodes de bandits manchot
Decision-making is a highly researched field in science, be it in neuroscience to understand the processes underlying animal decision-making, or in robotics to model efficient and rapid decision-making processes in real environments. In neuroscience, this problem is resolved online with sequential decision-making models based on reinforcement learning. In robotics, the primary objective is efficiency, in order to be deployed in real environments. However, in robotics what can be called the budget and which concerns the limitations inherent to the hardware, such as computation times, limited actions available to the robot or the lifetime of the robot battery, are often not taken into account at the present time. We propose in this thesis to introduce the notion of budget as an explicit constraint in the robotic learning processes applied to a localization task by implementing a model based on work developed in statistical learning that processes data under explicit constraints, limiting the input of data or imposing a more explicit time constraint. In order to discuss an online functioning of this type of budgeted learning algorithms, we also discuss some possible inspirations that could be taken on the side of computational neuroscience. In this context, the alternation between information retrieval for location and the decision to move for a robot may be indirectly linked to the notion of exploration-exploitation compromise. We present our contribution to the modeling of this compromise in animals in a non-stationary task involving different levels of uncertainty, and we make the link with the methods of multi-armed bandits

Un axe de recherche typique du data mining, et qui nous concerne dans cette thèse, est la recherche de régularités dans des bases de séquences (e. G. , séquences d'achats, de navigation, d'ADN). De nombreux algorithmes ont été proposés pour traiter l'extraction de motifs séquentiels satisfaisant des contraintes variées. Parmi ceux existants, certains exploitent une représentation en mémoire des positions des motifs (listes d'occurences), ce qui permet de réduire les coûts liés aux accès disque lors de l'exécution d'un processus. Cependant, leurs performances peuvent être grandement améliorées lorsque ces données comportent des répétitions consécutives, c'est-à-dire, en quelque sorte, une redondance de certaines informations dans le temps. Par exemple, un client peut acheter plusieurs fois le même article lors d'achats successifs, la même erreur peut se reproduire plusieurs fois d'affilé sur un réseau informatique, ou encore, comme c'est le cas dans notre contexte d'application (traitement de données financières où l'évolution de produits boursiers est représentée par des séquences d'évènements), lorsque les séquences sont construites à partir de données quantitatives discrétisées. Dans cette thèse, nous tentons d'apporter des solutions efficaces au problème de l'extraction, contrainte ou non, de motifs séquentiels, dans le cas de données contenant des répétitions consécutives. Celles-ci s'appuient sur une généralisation des listes d'occurences et proposent de condenser les informations qu'elles contiennent, sans perte pour les extractions. Cette nouvelle représentation a donné lieu aux développements d'extracteurs de motifs séquentiels, GoSpade (traitement de la seule contrainte de fréquence minimum) et GoSpec (traitement de contraintes temporelles), particulièrement bien adaptés à la présence de répétitions consécutives dans les données. Les algorithmes correspondants ont respectivement fait l'objet d'une démonstration de justesse et de complétude afin d'assurer la correction des résultats qu'ils retournent. De plus, il a été montré, par des expérimentations sur des jeux de données réelles et synthétiques, que ces extracteurs présentaient une nette amélioration des performances en présence de répétitions consécutives. Les gains obtenus, en terme d'espace mémoire et de temps d'exécution, permettent de travailler sur des volumes de données plus importants et à des seuils de fréquence plus faibles, dans des temps raisonnables. Enfin, une application dans le domaine des marchés financiers, visant à construire une représentation synthétique de différentes tendances boursières sous forme de motifs séquentiels caractéristiques, a été effectuée. Nous avons pu montrer que des motifs fréquents constituant une tendance contiennent une information qui est bien spécifique de la tendance représentée
This PhD Thesis concerns the particular data mining field that is the sequential pattern extractions from event sequence databases (e. G. Customer transaction sequences, web logs, DNA). Among existing algorithms, those based on the use of a representation in memory of the pattern locations (called occurrence lists), present a lost of efficiency when the sequences contain consecutive repetitions. This PhD Thesis proposes some efficient solutions to the sequential pattern extraction in such a context (constraints and repetitions) based on a condensation of informations contained in the occurrence lists, without lost for the extraction process. This new representation leads to new sequential pattern extraction algorithms (GoSpade and GoSpec) particularly well adapted to the presence of consecutive repetitions in the datasets. These algorithms have been proved to be sound and complete and experiments on both real and synthetic datasets enabled to show that the gain in term of memory space and execution time is important and that they increase with the number of consecutive repetitions contained in the datasets. Finally, a financial application has been performed in order to make a condensed representation of market trends by means of frequent sequential patterns

Dans le domaine du calcul générique, les circuits FPGA sont très attrayants pour leur performance et leur faible consommation. Cependant, leur présence reste marginale, notamment à cause des limitations des logiciels de développement actuels. En effet, ces limitations obligent les utilisateurs à bien maîtriser de nombreux concepts techniques. Ils obligent à diriger manuellement les processus de synthèse, de façon à obtenir une solution à la fois rapide et conforme aux contraintes des cibles matérielles visées.Une nouvelle méthodologie de génération basée sur la synthèse d'architecture est proposée afin de repousser ces limites. L'exploration des solutions consiste en l'application de transformations itératives à un circuit initial, ce qui accroît progressivement sa rapidité et sa consommation en ressources. La rapidité de ce processus, ainsi que sa convergence sous contraintes de ressources, sont ainsi garanties. L'exploration est également guidée vers les solutions les plus pertinentes grâce à la détection, dans les applications à synthétiser, des sections les plus critiques pour le contexte d'utilisation réel. Cette information peut être affinée à travers un scénario d'exécution transmis par l'utilisateur.Un logiciel démonstrateur pour cette méthodologie, AUGH, est construit. Des expérimentations sont menées sur plusieurs applications reconnues dans le domaine de la synthèse d'architecture. De tailles très différentes, ces applications confirment la pertinence de la méthodologie proposée pour la génération rapide et autonome d'accélérateurs matériels complexes, sous des contraintes de ressources strictes. La méthodologie proposée est très proche du processus de compilation pour les microprocesseurs, ce qui permet son utilisation même par des utilisateurs non spécialistes de la conception de circuits numériques. Ces travaux constituent donc une avancée significative pour une plus large adoption des FPGA comme accélérateurs matériels génériques, afin de rendre les machines de calcul simultanément plus rapides et plus économes en énergie
In the field of high-performance computing, FPGA circuits are very attractive for their performance and low consumption. However, their presence is still marginal, mainly because of the limitations of current development tools. These limitations force the user to have expert knowledge about numerous technical concepts. They also have to manually control the synthesis processes in order to obtain solutions both fast and that fulfill the hardware constraints of the targeted platforms.A novel generation methodology based on high-level synthesis is proposed in order to push these limits back. The design space exploration consists in the iterative application of transformations to an initial circuit, which progressively increases its rapidity and its resource consumption. The rapidity of this process, along with its convergence under resource constraints, are thus guaranteed. The exploration is also guided towards the most pertinent solutions thanks to the detection of the most critical sections of the applications to synthesize, for the targeted execution context. This information can be refined with an execution scenarion specified by the user.A demonstration tool for this methodology, AUGH, has been built. Experiments have been conducted with several applications known in the field of high-level synthesis. Of very differen sizes, these applications confirm the pertinence of the proposed methodology for fast and automatic generation of complex hardware accelerators, under strict resource constraints. The proposed methodology is very close to the compilation process for microprocessors, which enable it to be used even by users non experts about digital circuit design. These works constitute a significant progress for a broader adoption of FPGA as general-purpose hardware accelerators, in order to make computing machines both faster and more energy-saving

Bien que les FPGA soient très attrayants pour leur performance et leur faible consommation, leur emploi en tant qu'accélérateurs matériels reste marginal. Les logiciels de développement existants ne sont en effet accessibles qu'à un public expert en conception de circuits. Afin de repousser leurs limites, une nouvelle méthodologie de génération basée sur la synthèse d'architecture est proposée. En appliquant des transformations successives à une solution initiale, le processus converge rapidement et permet de respecter strictement des contraintes matérielles, notamment en ressources. Un logiciel démonstrateur, AUGH, a été construit, et des expérimentations ont été menées sur plusieurs applications reconnues. La méthodologie proposée est très proche du processus de compilation pour les microprocesseurs, ce qui permet son utilisation même par des utilisateurs non spécialistes de la conception de circuits numériques.

Pour un processus, notre objectif a été, d'une part, de quantifier la disponibilité des informations nécessaires à la conduite et, d'autre part, de déterminer où placer des capteurs pour que lors de la défaillance d'un ou de plusieurs capteurs, les variables nécessaires à la conduite soient toujours observables en fonction de contraintes de fiabilité, de position ou de coût financier. Pour évaluer la fiabilité d'une architecture d'instrumentation donnée (MTIF : Mean Time To Failure), deux approches ont été développées. Dans la-première approche, la fiabilité est calculée directement en recherchant toutes les pannes de capteurs qui ne nuisent pas à l'observabilité des variables. Dans la deuxième approche, plus simple et plus rapide, on calcule la fonction de défiabilité de l'architecture en utilisant la Méthode de l'Arbre des Causes (MAC). Pour rechercher l'architecture d'instrumentation la plus fiable, quatre méthodes ont été développées. Ces méthodes sont basées soit sur une comparaison du MTTF de différentes architectures, soit sur une analyse de la structure du graphe du processus, soit sur une analyse de l'évolution de la fiabilité dans le temps ou encore sur une analyse des cycles contenus dans le graphe du processus. Les méthodes développées ont été appliquées avec succès sur des plates-formes pétrolières de la société Elf
For a given process, our aim is on the one hand to assess the availability of the necessary informations for the process control, and on the other hand to define the sensor location in order that the necessary variables for control are al ways observable when one or more sensors are defective subject to reliability,location and cost constraints. Two approaches to estimate the reliability of a measurement system are presented. In the first, the reliability is simply calculated by searching the sensory breakdown configurations for which. The system remains observable. Ln the second; we calculate the unrelizbility function using Fault Tree Method. To search the most reliable measurement system, four methods are presented. These methods are based on the MTIF comparison among different measurement systems, or on the structural analysis of the process graph, or on the analysis of the reliability evaluation vs time or more on the cycles study of the process graph. The proposed methods are successfully applied to an off-shore platform of the French petroleum company Elf Aquitaine

La découverte de motifs est une tâche centrale pour
l'extraction de connaissances dans les bases de données. Cette thèse
traite de l'extraction de motifs locaux sous contraintes. Nous
apportons un éclairage nouveau avec un cadre combinant des primitives
monotones pour définir des contraintes quelconques. La variété de ces
contraintes exprime avec précision l'archétype des motifs recherchés
par l'utilisateur au sein d'une base de données. Nous proposons alors
deux types d'approche d'extraction automatique et générique malgré les
difficultés algorithmiques inhérentes à cette tâche. Leurs efficacités
reposent principalement sur l'usage de conditions nécessaires pour
approximer les variations de la contrainte. D'une part, des méthodes
de relaxations permettent de ré-utiliser les nombreux algorithmes
usuels du domaines. D'autre part, nous réalisons des méthodes
d'extraction directes dédiées aux motifs ensemblistes pour les données
larges ou corrélées en exploitant des classes d'équivalences. Enfin,
l'utilisation de nos méthodes ont permi la découverte de phénomènes
locaux lors d'applications industrielles et médicales.

Le travail que nous développons dans le cadre de cette thèse s'articule autour des problèmes de recherche de structure de recouvrement de graphes sous contrainte sur le degré des sommets. Comme l'arbre de recouvrement couvre les sommets d'un graphe connexe avec un minimum de liens, il est généralement proposé comme solution à ce type de problèmes. Cependant, pour certaines applications telles que le routage dans les réseaux optiques, les solutions ne sont pas nécessairement des sous-graphes. Nous supposons dans cette thèse que la contrainte sur le degré est due à une capacité limitée instantanée des sommets et que la seule exigence sur le recouvrement est sa connexité. Dans ce cas, la solution peut être différente d'un arbre. Nous reformulons ces problèmes de recouvrement en nous appuyant sur une extension du concept d'arbre appelée hiérarchie de recouvrement. Notre objectif principal est de démontrer son intérêt vis-à-vis de l'arbre en termes de faisabilité et de coût du recouvrement. Nous considérons deux types de contraintes sur le degré : des bornes sur le degré des sommets ou une borne sur le nombre de sommets de branchement et cherchons dans les deux cas un recouvrement de coût minimum. Nous illustrons aussi l'applicabilité des hiérarchies en étudiant un problème prenant davantage en compte la réalité du routage optique. Pour ces différents problèmes NP-difficiles, nous montrons, tant sur le coût des solutions optimales que sur la garantie de performance des solutions approchées, l'intérêt des hiérarchies de recouvrement. Ce constat se voit conforté par des expérimentations sur des graphes aléatoires
The work conducted in this thesis is focused on the minimum spanning problems in graphs under constraints on the vertex degrees. As the spanning tree covers the vertices of a connected graph with a minimum number of links, it is generally proposed as a solution for this kind of problems. However, for some applications such as the routing in optical networks, the solution is not necessarily a sub-graph. In this thesis, we assume that the degree constraints are due to a limited instantaneous capacity of the vertices and that the only pertinent requirement on the spanning structure is its connectivity. In that case, the solution may be different from a tree. We propose the reformulation of this kind of spanning problems. To find the optimal coverage of the vertices, an extension of the tree concept called hierarchy is proposed. Our main purpose is to show its interest regarding the tree in term of feasibility and costs of the coverage. Thus, we take into account two types of degree constraints: either an upper bound on the degree of vertices and an upper bound on the number of branching vertices. We search a minimum cost spanning hierarchy in both cases. Besides, we also illustrate the applicability of hierarchies by studying a problem that takes more into account the reality of the optical routing. For all those NP-hard problems, we show the interest of the spanning hierarchy for both costs of optimal solutions and performance guarantee of approximate solutions. These results are confirmed by several experimentations on random graphs

Les robots sous-marins peuvent aujourd'hui évoluer dans des environnements complexes difficilement accessibles à l'Homme pour des raisons de coût ou de sécurité. Ils peuvent donc intervenir dans une grande variété de missions en environnement aquatique. Or, la complexité de ces milieux impose de doter le vecteur robotique d'une autonomie opérationnelle suffisante afin qu'il puisse mener sa mission à bien tout en préservant son intégrité. Cela nécessite de développer des lois de commande répondant aux spécificités de l'application. Ces lois de commande se basent sur des connaissances provenant de différentes disciplines scientifiques ce qui souligne l'interdisciplinarité inhérente à la robotique. Une fois la loi de commande développée, il faut implémenter le contrôleur sur le robot sous forme de logiciel de contrôle basé sur une architecture logicielle temps-réel.Or la conception actuelle des lois de commande, sous forme de blocs "monolithiques", rend difficile l'évolution d'une loi de commande d'une application à l'autre, l'intégration de connaissances provenant d'autres disciplines scientifiques que ne maitrisent pas forcément les automaticiens et pénalisent son implémentation sur des architectures logicielles qui nécessitent la modularité. Pour résoudre ces problèmes nous cherchons à proprement séparer les différentes connaissances afin que chacune soit aisément manipulable, son rôle clair et que les relations établies entre les différentes connaissances soient explicites. Cela permettra en outre une projection plus efficace sur l'architecture logicielle. Nous proposons donc un nouveau formalisme de description des lois de commande selon une composition modulaire d'entités de base appelées Atomes et qui encapsulent les différents éléments de connaissance. Nous nous intéressons également à l'établissement d'une meilleure synergie entre les aspects automatique et génie logiciel qui se construit autour de préoccupations communes telles que les contraintes temporelles et la stabilité. Pour cela, nous enrichissons nos Atomes de contraintes chargées de véhiculer les informations relatives à ces aspects temporels. Nous proposons également une méthodologie basée sur notre formalisme afin de guider l'implémentation de nos stratégies de commande sur un Middleware temps-réel, dans notre cas le Middleware ContrACT développé au LIRMM.Nous illustrons notre approche par diverses fonctionnalités devant être mises en oeuvre lors de missions d'exploration de l'environnement aquatique et notamment pour l'évitement de parois lors de l'exploration d'un aquifère karstique
Underwater robots can nowadays operate in complex environments in a broad scope of missions where the use of human divers is difficult for cost or safety reasons. However the complexity of aquatic environments requires to give the robotic vector an autonomy sufficient to perform its mission while preserving its integrity. This requires to design control laws according to application requirements. They are built on knowledge from several scientific fields, underlining the interdisciplinarity inherent to robotics. Once the control law designed, it must be implemented as a control Software working on a real-time Software architecture.Nonetheless the current conception of control laws, as "monolithic" blocks, makes difficult the adaptation of a control from an application to another and the integration of knowledge from various scientific fields which are often not fully understood by control engineers. It also penalizes the implementation of control on Software architectures, at least its modularity and evolution. To solve those problems we seek a proper separation of knowledge so that each knowledge item can be easily used, its role precisely defined and we want to reify the interactions between them. Moreover this will allow us a more efficient projection on the Software architecture. We thus propose a new formalism for control laws description as a modular composition of basic entities named Atoms used to encapsulate the knowledge items.We also aim at building a better synergy between control and software engineering based on shared concerns such as temporal constraints and stability. Hence we extend the definition of our Atoms with constraints carrying information related to their temporal behaviour. We propose as well a methodology relying on our formalism to guide the implementation of control on a real-time Middleware. We will focus on the ContrACT Middleware developed at LIRMM.Finally we illustrate our approach on several robotic functionalities that can be used during aquatic environments exploration and especially for wall avoidance during the exploration of a karst aquifer

Les problèmes d’optimisation combinatoire sont devenus la cible de nombreuses recherches scientifiques pour leur importance dans la résolution de problèmes académiques et de problèmes réels rencontrés dans le domaine de l’ingénierie et dans l’industrie. La résolution de ces problèmes par des méthodes exactes ne peut être envisagée à cause des délais de traitement souvent exorbitants que nécessiteraient ces méthodes pour atteindre la (les) solution(s) optimale(s). Dans cette thèse, nous nous sommes intéressés au contexte algorithmique de résolution des problèmes combinatoires, et au contexte de modélisation de ces problèmes. Au niveau algorithmique, nous avons appréhendé les méthodes hybrides qui excellent par leur capacité à faire coopérer les méthodes exactes et les méthodes approchées afin de produire rapidement des solutions. Au niveau modélisation, nous avons travaillé sur la spécification et la résolution exacte des problématiques complexes de fouille des ensembles de motifs en étudiant tout particulièrement le passage à l’échelle sur des bases de données de grande taille. D'une part, nous avons proposé une première parallélisation de l'algorithme DGVNS, appelée CPDGVNS, qui explore en parallèle les différents clusters fournis par la décomposition arborescente en partageant la meilleure solution trouvée sur un modèle maître-travailleur. Deux autres stratégies, appelées RADGVNS et RSDGVNS, ont été proposées qui améliorent la fréquence d'échange des solutions intermédiaires entre les différents processus. Les expérimentations effectuées sur des problèmes combinatoires difficiles montrent l'adéquation et l'efficacité de nos méthodes parallèles. D'autre part, nous avons proposé une approche hybride combinant à la fois les techniques de programmation linéaire en nombres entiers (PLNE) et la fouille de motifs. Notre approche est complète et tire profit du cadre général de la PLNE (en procurant un haut niveau de flexibilité et d’expressivité) et des heuristiques spécialisées pour l’exploration et l’extraction de données (pour améliorer les temps de calcul). Outre le cadre général de l’extraction des ensembles de motifs, nous avons étudié plus particulièrement deux problèmes : le clustering conceptuel et le problème de tuilage (tiling). Les expérimentations menées ont montré l’apport de notre proposition par rapport aux approches à base de contraintes et aux heuristiques spécialisées
Combinatorial optimization problems have become the target of many scientific researches for their importance in solving academic problems and real problems encountered in the field of engineering and industry. Solving these problems by exact methods is often intractable because of the exorbitant time processing that these methods would require to reach the optimal solution(s). In this thesis, we were interested in the algorithmic context of solving combinatorial problems, and the modeling context of these problems. At the algorithmic level, we have explored the hybrid methods which excel in their ability to cooperate exact methods and approximate methods in order to produce rapidly solutions of best quality. At the modeling level, we worked on the specification and the exact resolution of complex problems in pattern set mining, in particular, by studying scaling issues in large databases. On the one hand, we proposed a first parallelization of the DGVNS algorithm, called CPDGVNS, which explores in parallel the different clusters of the tree decomposition by sharing the best overall solution on a master-worker model. Two other strategies, called RADGVNS and RSDGVNS, have been proposed which improve the frequency of exchanging intermediate solutions between the different processes. Experiments carried out on difficult combinatorial problems show the effectiveness of our parallel methods. On the other hand, we proposed a hybrid approach combining techniques of both Integer Linear Programming (ILP) and pattern mining. Our approach is comprehensive and takes advantage of the general ILP framework (by providing a high level of flexibility and expressiveness) and specialized heuristics for data mining (to improve computing time). In addition to the general framework for the pattern set mining, two problems were studied: conceptual clustering and the tiling problem. The experiments carried out showed the contribution of our proposition in relation to constraint-based approaches and specialized heuristics

Dans le cadre de cette thèse, nous avons établi des liens entre les modèles obtenus par des algorithmes d'inférence grammaticale et la connaissance induite par des techniques de fouille de données séquentielles. Partant du constat que le point commun entre ces deux contextes différents de travail est la manipulation de données structurées sous forme de séquences de symboles, nous avons tenté d'exploiter les propriétés des automates probabilistes inférés à partir de ces séquences au profit d'une fouille de données séquentielles plus efficace.
Dans ce contexte, nous avons montré que l'exploitation brute, non seulement des séquences d'origine mais aussi des automates probabilistes inférés à partir de celles-ci, ne garantit pas forcément une extraction de connaissance pertinente. Nous avons apporté dans cette thèse plusieurs contributions, sous la forme de bornes minimales et de contraintes statistiques, permettant ainsi d'assurer une exploitation fructueuse des séquences et des automates probabilistes. De plus, grâce à notre modèle nous apportons une solution efficace à certaines applications mettant en jeux des problèmes de préservation de vie privée des individus.

De nombreuses méthodes d'Extraction de Connaissances dans les Données (ECD) produisent des résultats sous forme de règles. Les règles ont l'avantage de représenter les connaissances de manière explicite, ce qui en fait des modèles tout à fait intelligibles pour un utilisateur. Elles sont d'ailleurs au fondement de la plupart des théories de
représentation de la connaissance en sciences cognitives. En fouille de données, la principale technique à base de règles est l'extraction de règles d'association, qui a donné lieu à de nombreux travaux de recherche.

La limite majeure des algorithmes d'extraction de règles d'association est qu'ils produisent communément de grandes quantités de règles, dont beaucoup se révèlent même sans aucun intérêt pour l'utilisateur. Ceci s'explique par la nature non supervisée de ces algorithmes : ne considérant aucune variable endogène, ils envisagent dans les règles toutes les combinaisons possibles de variables. Dans la pratique, l'utilisateur ne peut pas exploiter les résultats tels quels directement à la sortie des algorithmes. Un post-traitement consistant en une seconde opération de fouille se
révèle indispensable pour valider les volumes de règles et découvrir des connaissances utiles. Cependant, alors que la fouille de données est effectuée automatiquement par des algorithmes combinatoires, la fouille de règles est une
tâche laborieuse à la charge de l'utilisateur.

La thèse développe deux approches pour assister l'utilisateur dans le post-traitement des règles d'association :
– la mesure de la qualité des règles par des indices numériques,
– la supervision du post-traitement par une visualisation interactive.

Pour ce qui concerne la première approche, nous formalisons la notion d'indice de qualité de règles et réalisons une classification inédite des nombreux indices de la littérature, permettant d'aider l'utilisateur à choisir les indices pertinents pour son besoin. Nous présentons également trois nouveaux indices aux propriétés originales : l'indice
probabiliste d'écart à l'équilibre, l'intensité d'implication entropique, et le taux informationnel. Pour ce qui concerne la seconde approche, nous proposons une méthodologie de visualisation pour l'exploration interactive des règles. Elle
est conçue pour faciliter la tâche de l'utilisateur confronté à de grands ensembles de règles en prenant en compte ses capacités de traitement de l'information. Dans cette méthodologie, l'utilisateur dirige la découverte de connaissances
par des opérateurs de navigation adaptés en visualisant des ensembles successifs de règles décrits par des indices de qualité.

Les deux approches sont intégrées au sein de l'outil de visualisation ARVis (Association Rule Visualization) pour l'exploration interactive des règles d'association. ARVis implémente notre méthodologie au moyen d'une représentation
3D, inédite en visualisation de règles, mettant en valeur les indices de qualité. De plus, ARVis repose sur un algorithme spécifique d'extraction sous contraintes permettant de générer les règles interactivement au fur et à mesure de la navigation de l'utilisateur. Ainsi, en explorant les règles, l'utilisateur dirige à la fois l'extraction et le
post-traitement des connaissances.

La quantité de données aujourd'hui emmagasinées dans tous les domaines ainsi que leur diversité d'origines et de formats rendent impossibles l'analyse, le résumé ou l'extraction manuelle de connaissances. Pour répondre à ces besoins, diverses communautés se sont intéressées à la conception et au développement d'outils permettant d'extraire automatiquement de la connaissance de ces grandes bases. Désormais ces travaux visent à prendre en compte l'hétérogénéité de ces données, de leur format et de leur qualité. Notre travail s'inscrit dans cet axe de recherche et, plus précisément, dans le contexte de la découverte de schémas fréquents à partir de données regroupées sous la forme de séquences ordonnées. Ces schémas, appelés motifs séquentiels, n'étaient jusqu'alors extraits que sur des bases de données de séquences symboliques et parfaites, c'est-à-dire des bases ne contenant que des informations binaires ou pouvant être traitées comme telles et ne contenant aucun enregistrement incomplet. Nous avons donc proposé plusieurs améliorations des techniques d'extraction de séquences fréquentes afin de prendre en compte des données hétérogènes, incomplètes, incertaines ou mal connues de leur utilisateur, tout en minimisant les pertes éventuelles d'informations. Ainsi, le travail présenté dans cette thèse comporte la mise en oeuvre d'un cadre pour l'extraction de motifs séquentiels en présence de données numériques quantitatives, la définition de contraintes temporelles relâchées autorisant l'utilisateur à spécifier des contraintes temporelles approximatives et permettant un tri des résultats obtenus selon un indice de précision temporelle, enfin, le développement de deux approches pour l'extraction de motifs séquentiels sur des données symboliques incomplètes.

La quantité de données aujourd'hui emmagasinées dans tous les domaines ainsi que leur diversité d'origines et de formats rendent impossibles l'analyse, le résumé ou l'extraction manuelle de connaissances. Pour répondre à ces besoins, diverses communautés se sont intéressées à la conception et au développement d'outils permettant d'extraire automatiquement de la connaissance de ces grandes bases. Désormais ces travaux visent à prendre en compte l'hétérogénéité de ces données, de leur format et de leur qualité. Notre travail s'inscrit dans cet axe de recherche et, plus précisément, dans le contexte de la découverte de schémas fréquents à partir de données regroupées sous la forme de séquences ordonnées. Ces schémas, appelés motifs séquentiels, n'étaient jusqu'alors extraits que sur des bases de données de séquences symboliques et parfaites, c'est-à-dire des bases ne contenant que des informations binaires ou pouvant être traitées comme telles et ne contenant aucun enregistrement incomplet. Nous avons donc proposé plusieurs améliorations des techniques d'extraction de séquences fréquentes afin de prendre en compte des données hétérogènes, incomplètes, incertaines ou mal connues de leur utilisateur, tout en minimisant les pertes éventuelles d'informations. Ainsi, le travail présenté dans cette thèse comporte la mise en oeuvre d'un cadre pour l'extraction de motifs séquentiels en présence de données numériques quantitatives, la définition de contraintes temporelles relâchées autorisant l'utilisateur à spécifier des contraintes temporelles approximatives et permettant un tri des résultats obtenus selon un indice de précision temporelle, enfin, le développement de deux approches pour l'extraction de motifs séquentiels sur des données symboliques incomplètes.