De nos jours, les algorithmes de classification binaire sont utilisés dans des tâches touchant plusieurs champs d’applications comme les fraudes en-ligne, le dépistage bio-médical ou bien la toxicité en-ligne. Malgré le nombre de données qui est souvent disponible pour ces applications, qui viennent habituellement de source réelles, une particularité y est fréquemment observée: la représentation débalancée des classes. Cette imbalance demeure un problème d’envergure pour les algorithmes de classification, car la vaste majorité d’entre eux ne sont pas conçus avec cette représentation inégale à l’esprit. De plus, dans les paramètres expérimentaux, les données sur lesquelles ils sont appliqués sont souvent bien balancées, à cause de la finalité-même de ces expérimentations. Dans le présent mémoire, une revue des stratégies et techniques existantes pour contrer l’imbalance binaire est proposée, dans laquelle un point de vue par modification de données ainsi qu’un point de vue par modification algorithmique seront adressés. Le premier sujet des présents travaux consiste en les approches de pré-traitement et leurs effets sur les métriques de classification, dans lequel des expérimentations contrôlées (présentant différents niveaux de débalancement) et des applications d’entreprises sont présentées et analysées. Le second sujet consiste en le paradigme sensible-au-coût appliqué à l’optimisation directe de la métrique de la F-mesure en utilisant un réseau de neurones, dans lequel des expérimentations sur un jeu de données très débalancé sont présentées et discutées, le tout accompagné d’une comparaison avec différents paramètres usuels. À la lecture du présent document, le lecteur aura une bonne idée des techniques de prétraitement existantes et ce qu’on peut en retirer d’un point de vue expérimental selon des ensembles de données variés. Également, l’application du paradigme sensible-au-coût par optimisation de la F-mesure donnera un aperçu positif quant au point de vue algorithmique dans un contexte de données très débalancées. / Nowadays, binary classification algorithms are used in detection-related tasks touching many fields of application such as online frauds, biomedical screening, or online toxicity. Despite the amount of data that’s usually available for those applications, which habitually comes from real-world data sources, a particularity is frequently observed in it: the imbalanced representation of the classes. This imbalance remains a significant problem for binary classification algorithms, because the vast majority of these algorithms are not designed with this unequal representation in mind. Moreover, in experimental setups, the data on which they are usually applied is more than often well-balanced, because of the very purpose of these experiments. In the current thesis, a review of the existing strategies and techniques to face the binary imbalance problem is proposed in which both a data-modification point of view and a algorithmmodification point of view are addressed. The first subject of this work are data prepocessing approaches and their effects on classification metrics, in which both controlled experimental setups (showing different levels of imbalance), and enterprise data applications are presented and analyzed. The second subject is the cost-sensitive paradigm applied to the direct optimization of the F-measure metric using a neural network, in which experimentations on a highly imbalanced data set are presented and discussed, as well as comparisons with different common settings. After reading the current document, the reader will be well aware of the existing preprocessing techniques and what they can be achieve in an experimental context using various data sets. Moreover, the application of the cost-sensitive paradigm by optimization of the F-measure will give positive insight regarding the algorithmic point of view in a context of very imbalanced data.

De nombreuses applications de classification binaire, telles que la prédiction de fraude et la prédiction de rétention, impliquent des ensembles de données déséquilibrées. Bien que les méthodes d'ensemble soient les mieux adaptées à ces contraintes, les règles de décision produites sont difficiles à interpréter en tant que groupe en raison de leur nombre et de leurs redondances sous-jacentes. Il est donc intéressant de simplifier les méthodes d'ensemble apprises en un petit ensemble équivalent de conditions sans sacrifier la performance à la simplicité. En interprétant simplement un arbre de décision comme un empilement de fonctions indicatrices binaires et un modèle linéaire, nous proposons une méthode qui apprend le sous-ensemble efficace d'indicateurs qui relie les données à un espace de représentation de faible dimension où elles deviennent linéairement séparables. Ces fonctions binaires permettent à un large éventail d'algorithmes d'apprentissage automatique simples d'être efficaces et sont également plus faciles à analyser, à étudier ou à valider par les experts du domaine que les branches initiales de l'arbre dans l'ensemble appris. / Many binary classification applications, such as churn prediction and fraud detection, involve unbalanced large datasets. While ensemble trees are the most suited algorithms given these constraints, the decision rules produced are hard to interpret as a group due to their number and their underlying redundancies. It is then of interest to simplify the learned ensemble trees into a small equivalent set of conditions without trading performance for simplicity. By simply interpreting a decision tree as a stack of binary indicator functions and a linear model, we propose a method that learns the effective subset of indicators that map the data to a low dimension feature space where it becomes linearly separable. These binary functions enable a wide range of simple machine learning algorithms to be efficient and are also easier to analyze, investigate or validate by domain experts than the initial tree branches in the learned ensemble.

Du fait de la miniaturisation grandissante des circuits électroniques, la conception de système sur puce actuelle, se heurte au problème des latences sur les fils d'interconnexions traversant tout le circuit. Un système sur puce est un ensemble de blocs de calculs (les composants IP) qui s'échangent des données. Alors que la communication à l'intérieur de ces blocs de calculs peut toujours se faire de manière synchrone, c'est à dire s'abstraire comme une action instantanée, la communication d'un bloc de calculs à un autre prend un temps qui n'est pas négligeable. Il s'écoule plusieurs cycles d'horloge entre l'émission d'une donnée sur un fil d'interconnexion et sa réception. La théorie du Latency Insensitive Design créée par Luca Carloni et Alberto Sangiovanni-Vincentelli permet entre autre de résoudre ce problème en implantant un protocole de communication basé sur la segmentation des fils d'interconnexions et sur le principe de rétroaction en cas d'embouteillage. Dans un premier temps, nous avons donné un fondement théorique à cette théorie en la rapprochant formellement d'une modélisation par Marked/Event graph (Sous ensemble sans conflit des Réseaux de Pétri) et avec des places de capacité ; ce qui génère naturellement le protocole de contrôle de flux. Cette modélisation nous amène à la problématique principale de cet ouvrage: comment, et sous quelles conditions, peut on minimiser la taille des ressources de mémorisation utilisées comme tampons intermédiaires au long de ces fils d'interconnexions? Car leur nombre et leur position peuvent se révéler critique à l'implantation matérielle. Nous allons ensuite étudier cette question sous une hypothèse naturelle de déterminisme, ce qui permet d'obtenir des régimes de fonctionnement périodiques et réguliers. Le but de cette thèse est de modifier le protocole mis en place dans la théorie du Latency Insensitive Design en prenant en compte cette hypothèse. L'étude des systèmes déterministes et des résultats existant nous a permis une première phase de modification appelée: égalisation. L'étape suivante consiste à ordonnancer statiquement ces systèmes. Pour cela, nous avons choisi de représenter explicitement l'ordonnancement de chacun des éléments du système comme un mot binaire périodique où les "1" représentent les instants d'activités et les "0" d'inactivités tel que M. Pouzet et al. l'ont introduit dans le "N-synchronous Kahn network". Une étude approfondie des différentes classes de mots binaires existants (mot de Sturm, de Christoffel, de Lyndon ou encore mécaniques) a précédé leur association à la théorie du Latency Insensitive Design et au processus d'égalisation pour obtenir des systèmes déterministes ordonnancés statiquement.