Le déséquilibre entre la distribution des a priori est rencontré dans un nombre très large de domaines. Les algorithmes d’apprentissage conventionnels sont moins efficaces dans la prévision d’échantillons appartenant aux classes minoritaires. Notre but est de développer une règle de reconstruction adaptée aux catégories de données biaisées. Nous proposons une nouvelle règle, la Reconstruction Rule par sélection, qui, dans le schéma ‘One-per-Class’, utilise la fiabilité, des étiquettes et des distributions a priori pour permettre de calculer une décision finale. Les tests démontrent que la performance du système s’améliore en utilisant cette règle plutôt que des règles classiques. Nous étudions également les règles dans l’ ‘Error Correcting Output Code’ (ECOC) décomposition. Inspiré par une règle de reconstitution de données statistiques conçue pour le ‘One-per-Class’ et ‘Pair-Wise Coupling’ des approches sur la décomposition, nous avons développé une règle qui s’applique à la régression ‘softmax’ sur la fiabilité afin d’évaluer la classification finale. Les résultats montrent que ce choix améliore les performances avec respect de la règle statistique existante et des règles de reconstructions classiques. Sur ce thème d’estimation fiable nous remarquons que peu de travaux ont porté sur l’efficacité de l’estimation postérieure dans le cadre de boosting. Suivant ce raisonnement, nous développons une estimation postérieure efficace en boosting Nearest Neighbors. Utilisant Universal Nearest Neighbours classification nous prouvons qu’il existe une sous-catégorie de fonctions, dont la minimisation apporte statistiquement de simples et efficaces estimateurs de Bayes postérieurs. / Disproportion among class priors is encountered in a large number of domains making conventional learning algorithms less effective in predicting samples belonging to the minority classes. We aim at developing a reconstruction rule suited to multiclass skewed data. In performing this task we use the classification reliability that conveys useful information on the goodness of classification acts. In the framework of One-per-Class decomposition scheme we design a novel reconstruction rule, Reconstruction Rule by Selection, which uses classifiers reliabilities, crisp labels and a-priori distributions to compute the final decision. Tests show that system performance improves using this rule rather than using well-established reconstruction rules. We investigate also the rules in the Error Correcting Output Code (ECOC) decomposition framework. Inspired by a statistical reconstruction rule designed for the One-per-Class and Pair-Wise Coupling decomposition approaches, we have developed a rule that applies softmax regression on reliability outputs in order to estimate the final classification. Results show that this choice improves the performances with respect to the existing statistical rule and to well-established reconstruction rules. On the topic of reliability estimation we notice that small attention has been given to efficient posteriors estimation in the boosting framework. On this reason we develop an efficient posteriors estimator by boosting Nearest Neighbors. Using Universal Nearest Neighbours classifier we prove that a sub-class of surrogate losses exists, whose minimization brings simple and statistically efficient estimators for Bayes posteriors.

Le déséquilibre entre la distribution des a priori est rencontré dans un nombre très large de domaines. Les algorithmes d'apprentissage conventionnels sont moins efficaces dans la prévision d'échantillons appartenant aux classes minoritaires. Notre but est de développer une règle de reconstruction adaptée aux catégories de données biaisées. Nous proposons une nouvelle règle, la Reconstruction Rule par sélection, qui, dans le schéma 'One-per-Class', utilise la fiabilité, des étiquettes et des distributions a priori pour permettre de calculer une décision finale. Les tests démontrent que la performance du système s'améliore en utilisant cette règle plutôt que des règles classiques. Nous étudions également les règles dans l' 'Error Correcting Output Code' (ECOC) décomposition. Inspiré par une règle de reconstitution de données statistiques conçue pour le 'One-per-Class' et 'Pair-Wise Coupling' des approches sur la décomposition, nous avons développé une règle qui s'applique à la régression 'softmax' sur la fiabilité afin d'évaluer la classification finale. Les résultats montrent que ce choix améliore les performances avec respect de la règle statistique existante et des règles de reconstructions classiques. Sur ce thème d'estimation fiable nous remarquons que peu de travaux ont porté sur l'efficacité de l'estimation postérieure dans le cadre de boosting. Suivant ce raisonnement, nous développons une estimation postérieure efficace en boosting Nearest Neighbors. Utilisant Universal Nearest Neighbours classification nous prouvons qu'il existe une sous-catégorie de fonctions, dont la minimisation apporte statistiquement de simples et efficaces estimateurs de Bayes postérieurs.

De nos jours, dans plusieurs domaines, tels que la bio-informatique ou le multimédia, les données peuvent être représentées par plusieurs ensembles d'attributs, appelés des vues. Pour une tâche de classification donnée, nous distinguons deux types de vues : les vues fortes sont celles adaptées à la tâche, les vues faibles sont adaptées à une (petite) partie de la tâche ; en classification multi-classes, chaque vue peut s'avérer forte pour reconnaître une classe, et faible pour reconnaître d’autres classes : une telle vue est dite déséquilibrée. Les travaux présentés dans cette thèse s'inscrivent dans le cadre de l'apprentissage supervisé et ont pour but de traiter les questions d'apprentissage multi-vue dans le cas des vues fortes, faibles et déséquilibrées. La première contribution de cette thèse est un algorithme d'apprentissage multi-vues théoriquement fondé sur le cadre de boosting multi-classes utilisé par AdaBoost.MM. La seconde partie de cette thèse concerne la mise en place d'un cadre général pour les méthodes d'apprentissage de classes déséquilibrées (certaines classes sont plus représentées que les autres). Dans la troisième partie, nous traitons le problème des vues déséquilibrées en combinant notre approche des classes déséquilibrées et la coopération entre les vues mise en place pour appréhender la classification multi-vues. Afin de tester les méthodes sur des données réelles, nous nous intéressons au problème de classification d'appels téléphoniques, qui a fait l'objet du projet ANR DECODA. Ainsi chaque partie traite différentes facettes du problème. / Nowadays, in many fields, such as bioinformatics or multimedia, data may be described using different sets of features, also called views. For a given classification task, we distinguish two types of views:strong views, which are suited for the task, and weak views suited for a (small) part of the task; in multi-class learning, a view can be strong with respect to some (few) classes and weak for the rest of the classes: these are imbalanced views. The works presented in this thesis fall in the supervised learning setting and their aim is to address the problem of multi-view learning under strong, weak and imbalanced views, regrouped under the notion of uneven views. The first contribution of this thesis is a multi-view learning algorithm based on the same framework as AdaBoost.MM. The second part of this thesis proposes a unifying framework for imbalanced classes supervised methods (some of the classes are more represented than others). In the third part of this thesis, we tackle the uneven views problem through the combination of the imbalanced classes framework and the between-views cooperation used to take advantage of the multiple views. In order to test the proposed methods on real-world data, we consider the task of phone calls classifications, which constitutes the subject of the ANR DECODA project. Each part of this thesis deals with different aspects of the problem.

L'apprentissage automatique doit faire face à différentes difficultés lorsqu'il est confronté aux particularités des données réelles. En effet, ces données sont généralement complexes, volumineuses, de nature hétérogène, de sources variées, souvent acquises automatiquement. Parmi les difficultés les plus connues, on citera les problèmes liés à la sensibilité des algorithmes aux données bruitées et le traitement des données lorsque la variable de classe est déséquilibrée. Le dépassement de ces problèmes constitue un véritable enjeu pour améliorer l'efficacité du processus d'apprentissage face à des données réelles. Nous avons choisi dans cette thèse de réfléchir à des procédures adaptatives du type boosting qui soient efficaces en présence de bruit ou en présence de données déséquilibrées.Nous nous sommes intéressés, d’abord, au contrôle du bruit lorsque l'on utilise le boosting. En effet, les procédures de boosting ont beaucoup contribué à améliorer l'efficacité des procédures de prédiction en data mining, sauf en présence de données bruitées. Dans ce cas, un double problème se pose : le sur-apprentissage des exemples bruités et la détérioration de la vitesse de convergence du boosting. Face à ce double problème, nous proposons AdaBoost-Hybride, une adaptation de l’algorithme Adaboost fondée sur le lissage des résultats des hypothèses antérieures du boosting, qui a donné des résultats expérimentaux très satisfaisants.Ensuite, nous nous sommes intéressés à un autre problème ardu, celui de la prédiction lorsque la distribution de la classe est déséquilibrée. C'est ainsi que nous proposons une méthode adaptative du type boosting fondée sur la classification associative qui a l’intérêt de permettre la focalisation sur des petits groupes de cas, ce qui est bien adapté aux données déséquilibrées. Cette méthode repose sur 3 contributions : FCP-Growth-P, un algorithme supervisé de génération des itemsets de classe fréquents dérivé de FP-Growth dans lequel est introduit une condition d'élagage fondée sur les contre-exemples pour la spécification des règles, W-CARP une méthode de classification associative qui a pour but de donner des résultats au moins équivalents à ceux des approches existantes pour un temps d'exécution beaucoup plus réduit, enfin CARBoost, une méthode de classification associative adaptative qui utilise W-CARP comme classifieur faible. Dans un chapitre applicatif spécifique consacré à la détection d’intrusion, nous avons confronté les résultats de AdaBoost-Hybride et de CARBoost à ceux des méthodes de référence (données KDD Cup 99). / Machine learning often overlooks various difficulties when confronted real data. Indeed, these data are generally complex, voluminous, and heterogeneous, due to the variety of sources. Among these problems, the most well known concern the sensitivity of the algorithms to noise and unbalanced data. Overcoming these problems is a real challenge to improve the effectiveness of the learning process against real data. In this thesis, we have chosen to improve adaptive procedures (boosting) that are less effective in the presence of noise or with unbalanced data.First, we are interested in robustifying Boosting against noise. Most boosting procedures have contributed greatly to improve the predictive power of classifiers in data mining, but they are prone to noisy data. In this case, two problems arise, (1) the over-fitting due to the noisy examples and (2) the decrease of convergence rate of boosting. Against these two problems, we propose AdaBoost-Hybrid, an adaptation of the Adaboost algorithm that takes into account mistakes made in all the previous iteration. Experimental results are very promising.Then, we are interested in another difficult problem, the prediction when the class is unbalanced. Thus, we propose an adaptive method based on boosted associative classification. The interest of using associations rules is allowing the focus on small groups of cases, which is well suited for unbalanced data. This method relies on 3 contributions: (1) FCP-Growth-P, a supervised algorithm for extracting class frequent itemsets, derived from FP-Growth by introducing the condition of pruning based on counter-examples to specify rules, (2) W-CARP associative classification method which aims to give results at least equivalent to those of existing approaches but in a faster manner, (3) CARBoost, a classification method that uses adaptive associative W-CARP as weak classifier. Finally, in a chapter devoted to the specific application of intrusion’s detection, we compared the results of AdaBoost-Hybrid and CARBoost to those of reference methods (data KDD Cup 99).

L'objectif de cette thèse est de proposer une méthodologie statistique permettant de formuler une règle de classement capable de surmonter les difficultés qui se présentent dans le traitement des données lorsque la distribution a priori de la variable réponse est déséquilibrée. Notre proposition est construite autour d'un ensemble particulier de règles d'association appelées "class association rules". Dans le chapitre II, nous avons exposé les bases théoriques qui sous-tendent la méthode. Nous avons utilisé les indicateurs de performance usuels existant dans la littérature pour évaluer un classifieur. A chaque règle "class association rule" est associée un classifieur faible engendré par l'antécédent de la règle que nous appelons profils. L'idée de la méthode est alors de combiner un nombre réduit de classifieurs faibles pour constituer une règle de classement performante. Dans le chapitre III, nous avons développé les différentes étapes de la procédure d'apprentissage statistique lorsque les observations sont indépendantes et identiquement distribuées. On distingue trois grandes étapes: (1) une étape de génération d'un ensemble initial de profils, (2) une étape d'élagage de profils redondants et (3) une étape de sélection d'un ensemble optimal de profils. Pour la première étape, nous avons utilisé l'algorithme "apriori" reconnu comme l'un des algorithmes de base pour l'exploration des règles d'association. Pour la deuxième étape, nous avons proposé un test stochastique. Et pour la dernière étape un test asymptotique est effectué sur le rapport des valeurs prédictives positives des classifieurs lorsque les profils générateurs respectifs sont emboîtés. Il en résulte un ensemble réduit et optimal de profils dont la combinaison produit une règle de classement performante. Dans le chapitre IV, nous avons proposé une extension de la méthode d'apprentissage statistique lorsque les observations ne sont pas identiquement distribuées. Il s'agit précisément d'adapter la procédure de sélection de l'ensemble optimal lorsque les données ne sont pas identiquement distribuées. L'idée générale consiste à faire une estimation bayésienne de toutes les valeurs prédictives positives des classifieurs faibles. Par la suite, à l'aide du facteur de Bayes, on effectue un test d'hypothèse sur le rapport des valeurs prédictives positives lorsque les profils sont emboîtés. Dans le chapitre V, nous avons appliqué la méthodologie mise en place dans les chapitres précédents aux données du projet QUARITE concernant la mortalité maternelle au Sénégal et au Mali.

La classification a été largement étudiée en apprentissage automatique. Les méthodes d’ensemble, qui construisent un modèle de classification en intégrant des composants d’apprentissage multiples, atteignent des performances plus élevées que celles d’un classifieur individuel. La précision de classification d’un ensemble est directement influencée par la qualité des données d’apprentissage utilisées. Cependant, les données du monde réel sont souvent affectées par les problèmes de bruit d’étiquetage et de déséquilibre des données. La marge d'ensemble est un concept clé en apprentissage d'ensemble. Elle a été utilisée aussi bien pour l'analyse théorique que pour la conception d'algorithmes d'apprentissage automatique. De nombreuses études ont montré que la performance de généralisation d'un classifieur ensembliste est liée à la distribution des marges de ses exemples d'apprentissage. Ce travail se focalise sur l'exploitation du concept de marge pour améliorer la qualité de l'échantillon d'apprentissage et ainsi augmenter la précision de classification de classifieurs sensibles au bruit, et pour concevoir des ensembles de classifieurs efficaces capables de gérer des données déséquilibrées. Une nouvelle définition de la marge d'ensemble est proposée. C'est une version non supervisée d'une marge d'ensemble populaire. En effet, elle ne requière pas d'étiquettes de classe. Les données d'apprentissage mal étiquetées sont un défi majeur pour la construction d'un classifieur robuste que ce soit un ensemble ou pas. Pour gérer le problème d'étiquetage, une méthode d'identification et d'élimination du bruit d'étiquetage utilisant la marge d'ensemble est proposée. Elle est basée sur un algorithme existant d'ordonnancement d'instances erronées selon un critère de marge. Cette méthode peut atteindre un taux élevé de détection des données mal étiquetées tout en maintenant un taux de fausses détections aussi bas que possible. Elle s'appuie sur les valeurs de marge des données mal classifiées, considérant quatre différentes marges d'ensemble, incluant la nouvelle marge proposée. Elle est étendue à la gestion de la correction du bruit d'étiquetage qui est un problème plus complexe. Les instances de faible marge sont plus importantes que les instances de forte marge pour la construction d'un classifieur fiable. Un nouvel algorithme, basé sur une fonction d'évaluation de l'importance des données, qui s'appuie encore sur la marge d'ensemble, est proposé pour traiter le problème de déséquilibre des données. Cette méthode est évaluée, en utilisant encore une fois quatre différentes marges d'ensemble, vis à vis de sa capacité à traiter le problème de déséquilibre des données, en particulier dans un contexte multi-classes. En télédétection, les erreurs d'étiquetage sont inévitables car les données d'apprentissage sont typiquement issues de mesures de terrain. Le déséquilibre des données d'apprentissage est un autre problème fréquent en télédétection. Les deux méthodes d'ensemble proposées, intégrant la définition de marge la plus pertinente face à chacun de ces deux problèmes majeurs affectant les données d'apprentissage, sont appliquées à la cartographie d'occupation du sol. / Classification has been widely studied in machine learning. Ensemble methods, which build a classification model by integrating multiple component learners, achieve higher performances than a single classifier. The classification accuracy of an ensemble is directly influenced by the quality of the training data used. However, real-world data often suffers from class noise and class imbalance problems. Ensemble margin is a key concept in ensemble learning. It has been applied to both the theoretical analysis and the design of machine learning algorithms. Several studies have shown that the generalization performance of an ensemble classifier is related to the distribution of its margins on the training examples. This work focuses on exploiting the margin concept to improve the quality of the training set and therefore to increase the classification accuracy of noise sensitive classifiers, and to design effective ensemble classifiers that can handle imbalanced datasets. A novel ensemble margin definition is proposed. It is an unsupervised version of a popular ensemble margin. Indeed, it does not involve the class labels. Mislabeled training data is a challenge to face in order to build a robust classifier whether it is an ensemble or not. To handle the mislabeling problem, we propose an ensemble margin-based class noise identification and elimination method based on an existing margin-based class noise ordering. This method can achieve a high mislabeled instance detection rate while keeping the false detection rate as low as possible. It relies on the margin values of misclassified data, considering four different ensemble margins, including the novel proposed margin. This method is extended to tackle the class noise correction which is a more challenging issue. The instances with low margins are more important than safe samples, which have high margins, for building a reliable classifier. A novel bagging algorithm based on a data importance evaluation function relying again on the ensemble margin is proposed to deal with the class imbalance problem. In our algorithm, the emphasis is placed on the lowest margin samples. This method is evaluated using again four different ensemble margins in addressing the imbalance problem especially on multi-class imbalanced data. In remote sensing, where training data are typically ground-based, mislabeled training data is inevitable. Imbalanced training data is another problem frequently encountered in remote sensing. Both proposed ensemble methods involving the best margin definition for handling these two major training data issues are applied to the mapping of land covers.

La problématique des jeux de données déséquilibrées en apprentissage supervisé est apparue relativement récemment, dès lors que le data mining est devenu une technologie amplement utilisée dans l'industrie. Le but de nos travaux est d'adapter différents éléments de l'apprentissage supervisé à cette problématique. Nous cherchons également à répondre aux exigences spécifiques de performances souvent liées aux problèmes de données déséquilibrées. Ce besoin se retrouve dans notre application principale, la mise au point d'un logiciel d'aide à la détection des cancers du sein.Pour cela, nous proposons de nouvelles méthodes modifiant trois différentes étapes d'un processus d'apprentissage. Tout d'abord au niveau de l'échantillonnage, nous proposons lors de l'utilisation d'un bagging, de remplacer le bootstrap classique par un échantillonnage dirigé. Nos techniques FUNSS et LARSS utilisent des propriétés de voisinage pour la sélection des individus. Ensuite au niveau de l'espace de représentation, notre contribution consiste en une méthode de construction de variables adaptées aux jeux de données déséquilibrées. Cette méthode, l'algorithme FuFeFa, est basée sur la découverte de règles d'association prédictives. Enfin, lors de l'étape d'agrégation des classifieurs de base d'un bagging, nous proposons d'optimiser le vote à la majorité en le pondérant. Pour ce faire nous avons mis en place une nouvelle mesure quantitative d'évaluation des performances d'un modèle, PRAGMA, qui permet la prise en considération de besoins spécifiques de l'utilisateur vis-à-vis des taux de rappel et de précision de chaque classe. / The problem of imbalanced datasets in supervised learning has emerged relatively recently, since the data mining has become a technology widely used in industry. The assisted medical diagnosis, the detection of fraud, abnormal phenomena, or specific elements on satellite imagery, are examples of industrial applications based on supervised learning of imbalanced datasets. The goal of our work is to bring supervised learning process on this issue. We also try to give an answer about the specific requirements of performance often related to the problem of imbalanced datasets, such as a high recall rate for the minority class. This need is reflected in our main application, the development of software to help radiologist in the detection of breast cancer. For this, we propose new methods of amending three different stages of a learning process. First in the sampling stage, we propose in the case of a bagging, to replaced classic bootstrap sampling by a guided sampling. Our techniques, FUNSS and LARSS use neighbourhood properties for the selection of objects. Secondly, for the representation space, our contribution is a method of variables construction adapted to imbalanced datasets. This method, the algorithm FuFeFa, is based on the discovery of predictive association rules. Finally, at the stage of aggregation of base classifiers of a bagging, we propose to optimize the majority vote in using weightings. For this, we have introduced a new quantitative measure of model assessment, PRAGMA, which allows taking into account user specific needs about recall and precision rates of each class.

L'objectif de cette thèse est de proposer une méthodologie statistique permettant de formuler une règle de classement capable de surmonter les difficultés qui se présentent dans le traitement des données lorsque la distribution a priori de la variable réponse est déséquilibrée. Notre proposition est construite autour d'un ensemble particulier de règles d'association appelées "class association rules". Dans le chapitre II, nous avons exposé les bases théoriques qui sous-tendent la méthode. Nous avons utilisé les indicateurs de performance usuels existant dans la littérature pour évaluer un classifieur. A chaque règle "class association rule" est associée un classifieur faible engendré par l'antécédent de la règle que nous appelons profils. L'idée de la méthode est alors de combiner un nombre réduit de classifieurs faibles pour constituer une règle de classement performante. Dans le chapitre III, nous avons développé les différentes étapes de la procédure d'apprentissage statistique lorsque les observations sont indépendantes et identiquement distribuées. On distingue trois grandes étapes: (1) une étape de génération d'un ensemble initial de profils, (2) une étape d'élagage de profils redondants et (3) une étape de sélection d'un ensemble optimal de profils. Pour la première étape, nous avons utilisé l'algorithme "apriori" reconnu comme l'un des algorithmes de base pour l'exploration des règles d'association. Pour la deuxième étape, nous avons proposé un test stochastique. Et pour la dernière étape un test asymptotique est effectué sur le rapport des valeurs prédictives positives des classifieurs lorsque les profils générateurs respectifs sont emboîtés. Il en résulte un ensemble réduit et optimal de profils dont la combinaison produit une règle de classement performante. Dans le chapitre IV, nous avons proposé une extension de la méthode d'apprentissage statistique lorsque les observations ne sont pas identiquement distribuées. Il s'agit précisément d'adapter la procédure de sélection de l'ensemble optimal lorsque les données ne sont pas identiquement distribuées. L'idée générale consiste à faire une estimation bayésienne de toutes les valeurs prédictives positives des classifieurs faibles. Par la suite, à l'aide du facteur de Bayes, on effectue un test d'hypothèse sur le rapport des valeurs prédictives positives lorsque les profils sont emboîtés. Dans le chapitre V, nous avons appliqué la méthodologie mise en place dans les chapitres précédents aux données du projet QUARITE concernant la mortalité maternelle au Sénégal et au Mali. / The aim of this thesis is to design a supervised statistical learning methodology that can overcome the weakness of standard methods when the prior distribution of the response variable is unbalanced. The proposed methodology is built using class association rules. Chapter II deals with theorical basis of statistical learning method by relating various classifiers performance metrics with class association rules. Since the classifier corresponding to a class association rules is a weak classifer, we propose to select a small number of such weak classifiers and to combine them in the aim to build an efficient classifier. In Chapter III, we develop the different steps of the statistical learning method when observations are independent and identically distributed. There are three main steps: In the first step, an initial set of patterns correlated with the target class is generated using "apriori" algorithm. In the second step, we propose a hypothesis test to prune redondant patterns. In the third step, an hypothesis test is performed based on the ratio of the positive predictive values of the classifiers when respective generating patterns are nested. This results in a reduced and optimal set of patterns whose combination provides an efficient classifier. In Chapter IV, we extend the classification method that we proposed in Chapter III in order to handle the case where observations are not identically distributed. The aim being here to adapt the procedure for selecting the optimal set of patterns when data are grouped data. In this setting we compute the estimation of the positive predictive values as the mean of the posterior distribution of the target class probability by using empirical Bayes method. Thereafter, using Bayes factor, a hypothesis test based on the ratio of the positive predictive values is carried out when patterns are nested. Chapter V is devoted to the application of the proposed methodology to process a real world dataset. We studied the QUARITE project dataset on maternal mortality in Senegal and Mali in order to provide a decision making tree that health care professionals can refer to when managing patients delivering in their health facilities.