Partie 1 : Imbalanced data et Machine Learning

Les données déséquilibrées posent de réelles difficultés aux algorithmes de Machine Learning et de Deep Learning. Faisons le tour des nombreuses façon d’y remédier.
imbalanced-data
Sommaire

Les données déséquilibrées, rappels

Les données déséquilibrées sont un problème fréquemment rencontré dans les modèles de classification, qu’il s’agisse de classification binaire (détecter une maladie) ou de classification multi-classes (prédire le modèle de voiture acheté). Nous présentons ici le cas binaire, qui est plus simple à appréhender et peut ensuite facilement se généraliser au multi-classes.

 

On peut parler de données déséquilibrées dès lors que les deux classes ne sont pas présentes avec la même fréquence dans les données, i.e. que le ratio n’est pas 50%/50%. Mais en pratique on ne parle de données déséquilibrées qu’à partir du moment où le déséquilibre dépasse 10%/90%. Par exemple, dans le cas d’une détection de fraude, il se peut que 99.9% des transactions effectuées soient valides, et seulement 0.1% frauduleuses. Les transactions valides sont alors appelées la classe majoritaire, et les fraudes la classe minoritaire.

 

Imbalance ratio

Les articles de recherche utilisent souvent “l’Imbalance ratio” pour caractériser le degré de déséquilibre :

\begin{equation*} \text{Imbalance ratio} = \frac{\text{Nb d’observations majoritaires}}{\text{Nb d’observations minoritaires}} \end{equation*}

Avec cette définition, Imbalance ratio >= 1, la valeur 1 correspondant à des données parfaitement équilibrées. Dans notre exemple, il vaut 99.9/0.1 = 999.

 

Dans un modèle prédisant « Y = 1 si fraude, Y=0 s’il n’y a pas de fraude », les observations positives (Y=1) sont la classe minoritaire, et les négatives (Y=0) sont la classe majoritaire. La classe minoritaire correspond souvent aux observations positives, car ce sont elles que l’on cherche à prédire : la survenance de l’événement (la fraude, la panne, le décès…) qui nous intéresse est labellisée par Y=1. Mais il s’agit d’une pure convention ; il suffirait de prendre « Y = 1 s’il n’y a pas de fraude, Y = 0 s’il y a fraude » pour que la classe minoritaire corresponde aux observations négatives.

 

Nous gardons dans cette série la convention classe minoritaire = classe des positifs, i.e. des observations pour lesquelles Y=1. Nous parlerons donc indifféremment d’observations minoritaires ou d’observations positives.

 

 

Quels problèmes posent les données déséquilibrées ?

Le problème des données déséquilibrées se pose différemment selon les modèles.

 

Modèles par arbres

Un modèle par arbres (CART, Random Forest, Gradient Boosting) aura un biais faible mais une variance élevée [1]. Les arbres vont en effet avoir tendance à “surapprendre” : ils se situent dans un espace globalement “pur” (la majorité de l’espace ne contient que des observations négatives) avec quelques régions d’impureté très localisées (là où se trouvent les positifs). Ils peuvent donc facilement réduire leur biais en délimitant strictement les observations minoritaires. Dans l’exemple ci-dessous, le CART parvient à isoler parfaitement les positifs en surapprenant les données. Il prédit une probabilité de 1 à l’intérieur des rectangles verts et de 0 en dehors, et atteint ainsi une performance maximale sur la base Train (AUC Precision-Recall de 100%).

Imbalanced data Machine Learning Apprentissage des données train

Figure 1. Apprentissage des données Train. L’arbre (CART) surapprend et isole parfaitement les individus positifs. L’AUC Precision-Recall sur la base Train est donc de 100% (l’AUC ROC aussi).

Qu’en est-il sur la base Test ?

Les observations positives de la base Test se situent dans la même région – le signal est bien cohérent entre Train et Test – mais majoritairement hors des zones étroites définies par le modèle, générant des faux négatifs. A l’inverse, des observations négatives se trouvent dans ces zones, générant des faux positifs. La performance chute donc fortement (AUC Precision-Recall de 5%) : on obtient une variance élevée, caractéristique du surapprentissage.

Imbalanced data Machine Learning Prédiction sur données test

Figure 2. Prédiction sur données Test. Le modèle a surappris les données (overfitting) et n’obtient qu’un AUC Precision-Recall de 5%.

Il est possible de réduire ce problème en régularisant plus fortement les arbres (réduire max_depth, augmenter min_samples_split, min_impurity_decrease, max_leaf_nodes…) et en modifiant les hyperparamètres de bagging pour la random forest (bootstrap, max_features) ou de boosting pour le gradient boosting (subsample, learning_rate…). Mais si le signal est complexe, une régularisation forte conduira à une performance très limitée. Dans l’exemple ci-dessous, restreindre la profondeur de l’arbre permet de réduire sa variance, mais au prix d’une simplification trop grande. On tente “d’approximer” avec un rectangle vertical une ellipse diagonale, ce qui est sous-optimal.

Imbalanced data Machine Learning Apprentissage régularisé données Train

Figure 3. Apprentissage régularisé de Train. L’arbre fortement contraint (max_depth = 4 ici) généralise en n’identifiant qu’une seule région. Il obtient un AUC Precision-Recall de 20%, qui reste sous-optimal.

Imbalanced data Machine Learning Prédiction du modèle régularisé sur Test

Figure 4. Prédiction du modèle régularisé sur Test. La performance sur Test est proche de celle obtenue sur Train (faible variance), avec un AUC Precision-Recall de 16%.

Modèles linéaires

Un modèle linéaire parviendra difficilement à modéliser de telles données : si les observations minoritaires sont trop peu nombreuses, la maximisation de la vraisemblance conduira généralement à prédire une surface plane, de probabilité égale à la fréquence de la classe minoritaire. Car si le modèle tente de déformer cette surface pour capter le signal des positifs, l’augmentation des résidus sur les négatifs dépassera la baisse des résidus sur les positifs, ceux-ci étant trop peu nombreux. Ainsi dans notre exemple de fraude, une régression logistique aboutira probablement à prédire une probabilité de fraude de 0.1% à toutes les observations.
La performance sur la base Train est alors celle d’un modèle aléatoire : AUC ROC de 50%, AUC Precision-Recall de 0.1% (égale au taux de positifs dans la base). Nous obtenons un classifieur avec un biais maximal. La variance de ce classifieur est, elle, nulle puisque la performance sera la même sur la base de Test.

 

Réseaux de neurones

Un réseau de neurones présentera également des problèmes de biais et/ou de variance, similaires à ceux présentés dans le cas du CART.

 

 

Quelle métrique utiliser pour des données déséquilibrées ?

Il est bon de le rappeler, il ne faut pas utiliser l’accuracy sur des données déséquilibrées ! Pour optimiser l’accuracy dans notre exemple de fraude, il suffirait de prédire toutes les transactions comme normales (Y=0) pour obtenir 99.9% d’accuracy. Un modèle aussi performant qu’inutile.

 

Il est plus raisonnable, si l’on veut conserver une métrique très courante, de retenir l’AUC ROC – Area Under the ROC Curve. Mais les mesures appuyées sur la précision et le recall sont les plus adaptées. L’état de l’art est à notre sens d’utiliser l’AUC Precision-Recall, qui est plus informatif que l’AUC ROC lorsque les données sont déséquilibrées [2]. Notre expérience est qu’il arrive, lors de l’optimisation du modèle, de voir l’AUC PR évoluer quand l’AUC ROC reste figé, ce qui abonde dans le sens d’une moindre informativité de ce dernier.

 

Si l’on a une idée précise de la précision ou du recall que l’on cherche pour l’application opérationnelle de l’algorithme et que l’on choisit le seuil de la matrice de confusion en conséquence, on peut aussi utiliser des métriques qui supposent le choix de ce seuil, comme le F1-score.

 

Enfin, rappelons qu’il ne faut jamais modifier les données de validation et de test, et en particulier ne jamais les rééchantillonner !

 

 

Comment corriger le déséquilibre des données en Machine Learning ?

D’abord, jusqu’à quel point faut-il corriger ce déséquilibre ? Il n’est pas nécessaire de rétablir un équilibre parfait 50/50 entre les classes. L’optimum dépendra de vos données et du type d’algorithme que vous souhaitez entraîner. Mais en ordre de grandeur, un ratio de 5-10% d’observations minoritaires est suffisant pour les modèles par arbres.

 

La correction des déséquilibres a généré une littérature abondante depuis le début des années 2000, et de nombreuses méthodes sont implémentées et disponibles, sur Python comme sur R. Ces méthodes peuvent agir à 3 niveaux : au niveau des données (data-level solutions), au niveau des algorithmes (algorithm-level solutions), ou au niveau de l’erreur de classification.

 

Data-level solutions

  • Le sous-échantillonnage aléatoire (random undersampling) des observations majoritaires. Cet undersampling peut être global : on retire aléatoirement x% des observations majoritaires. Il peut aussi être spécifique, avec des méthodes de clustering-based undersampling ou d’undersampling des observations frontalières [3]
  • Le sur-échantillonnage aléatoire (random oversampling) des observations minoritaires. On tire au hasard des individus minoritaires que l’on rajoute aux données. Les individus minoritaires se voient ainsi « clonés » de multiples fois, raison pour laquelle cette méthode est parfois appelée « Replicative oversampling ». Elle est peu efficace pour les arbres car elle ne leur permet pas de généraliser, mais peut marcher sur une régression logistique.
  • Le sur-échantillonnage synthétique (SMOTE pour Synthetic Minority Oversampling Technique) est une méthode plus avancée, qui produit des observations minoritaires ressemblantes mais distinctes de celles déjà existantes.

 

Algorithm-level solutions

  • Le rééchantillonnage interne des arbres dans les méthodes de Boosting ou de Bagging Classifier Inducing Inner Balancing Sampler – [4], implémenté dans les fonctions BalancedBaggingClassifier ou RUSBoostClassifier.
  • La sur-pondération globale des observations minoritaires dans l’apprentissage :
    • Via le gradient (boosting) : c’est le rôle du paramètre scale_pos_weight dans XGBoost, qui permet de donner davantage de poids aux observations minoritaires.
    • Via le Gini (bagging) dans la Weighted Random Forest [5]. C’est le rôle du paramètre class_weight de RandomForestClassifier, qui accroît le poids des classes minoritaires dans le calcul de pureté pour le split-finding.

 

Cost-sensitive solutions

Le cost-sensitive learning (apprentissage sensible aux coûts) consiste ici à accorder un poids plus grand dans l’apprentissage aux faux négatifs (les positifs qui sont prédits négatifs) qu’aux faux positifs (les négatifs qui sont prédits positifs). Ces méthodes sont souvent confondues avec les méthodes de sur-pondération globales présentées ci-dessus. Elles sont pour autant bien différentes, car elles accroissent la pondération des positifs mal classés, là où les méthodes globales accroissent indifféremment la pondération de tous les individus positifs.

 

 

Quelle méthode choisir ?

Notons d’abord qu’il est difficile de faire émerger un consensus de la littérature, et notamment de comparer les méthodes car les articles de recherche :

  • Font appel à des jeux de données de tailles différentes (de 1k à 1M selon les articles) et avec des imbalance ratio différents
  • Font appel à des modèles différents, parfois sans les optimiser
  • N’optimisent pas toujours les méthodes qu’ils utilisent pour se comparer (par exemple un article sur une méthode d’undersampling qui se compare avec un SMOTE sans optimiser les hyperparamètres de ce dernier)

 

La principale leçon est donc : prudence !

Il convient de ne pas tirer de conclusions hâtives à partir d’un papier de recherche isolé, surtout si celui-ci n’est testé que sur un seul jeu de données.

 

Les cas simples où un random undersampling peut suffire

Si la classe majoritaire est en trop grand nombre, pourquoi ne pas simplement réduire ce nombre? On peut légitimement se poser cette question, dont la réponse dépend de trois critères : le volume de vos données, le taux de déséquilibre, et la complexité du signal. Quelques repères pour réfléchir à partir de ces critères :

  1. Le volume des données : plus ce volume est important, plus le random undersampling peut être intéressant. Supposons dans notre modèle de fraude que nous disposions d’un milliard de transactions. Nous avons 1 million de fraudes (0.1%), et 999 millions de transactions normales. Sur un tel volume de transactions normales, la loi des grands nombres s’applique, et il est possible de fortement sous-échantillonner sans modifier la structure des données. En réalisant un undersampling de 1% des observations majoritaires, on obtient une base avec 9.99 millions de négatifs et 1 million de positifs, soit 9% d’observations positives, ce qui est un grand progrès à moindre coût.
  2. Le taux de déséquilibre : si les données sont faiblement déséquilibrées (5%/95% par exemple), on peut faire un random undersampling léger (retirer un quart des observations majoritaires) pour atteindre un taux d’observations minoritaires de 8%. Les risques de dénaturer les données restent modérés du fait qu’on a peu sous-échantillonné, même si le volume des données est trop faible pour que la loi des grands nombres s’applique.
  3. La complexité du signal : ce critère est moins aisément quantifiable, mais peut s’appréhender par la connaissance que l’on a du domaine. Plus votre signal est complexe, et plus un undersampling qui ne respecte pas la loi des grands nombres lui sera préjudiciable. A l’inverse, si vous savez que votre signal est assez simple, sous-échantillonner brutalement est une option. Supposons que vous vouliez faire un modèle simple (une régression logistique par exemple), alors un fort undersampling est envisageable.

 

Dans les autres cas, quelle méthode choisir ?

D’une part, il nous paraît essentiel de choisir une méthode que l’on maîtrise pour la manipuler correctement et ne pas dénaturer les données. Beaucoup de data scientists utilisent par exemple le SMOTE avec un preprocessing inadapté (sans scaler les numériques de façon robuste et en utilisant le one-hot-encoding pour les catégorielles) qui peut avoir des conséquences désastreuses. Nous détaillerons ce point dans un prochain article.

 

D’autre part, il n’est pas forcément nécessaire de choisir. Par exemple, il est possible de combiner un Random undersampling et un SMOTE. Le plus simple est alors d’optimiser globalement le pipeline « undersampling + SMOTE + Modèle », en traitant le taux d’undersampling et les paramètres du SMOTE comme des hyperparamètres de ce pipeline global (au même titre que ceux du modèle). On peut ensuite optimiser ce pipeline avec une méthode d’optimisation des hyperparamètres comme un Random Search ou un Bayesian Search.

 

 

Conclusion

Les données déséquilibrées sont un problème pour la majorité des algorithmes de Machine Learning, qui surapprennent les observations minoritaires.

  • La régularisation est alors une solution naïve qui réduit la variance mais conduit à une performance très limitée.
  • Les données déséquilibrées nécessitent des métriques d’évaluation adaptées. Les métriques s’appuyant sur la précision et le recall comme l’AUC Precision-Recall sont les plus pertinentes.
  • Il existe trois familles de méthodes pour apprendre à partir de données déséquilibrées : des méthodes de resampling qui modifient les données brutes d’apprentissage, des méthodes d’apprentissage spécifique avec rééchantillonnage interne ou repondération, et les méthodes d’apprentissage sensibles aux coûts (cost-sensitive).
  • Il existe des cas dans lesquels un random undersampling peut suffire : grand volume de données, faible déséquilibre, signal peu complexe.
  • Dans les autres cas, de nombreuses options existent et peuvent se combiner mais attention à bien maîtriser les algorithmes utilisés pour choisir un preprocessing adapté !

Références :

  1. N. V. Chawla, K. W. Bowyer, L. O. Hall, and W. P. Kegelmeyer, “SMOTE: Synthetic Minority Over-sampling Technique,” Journal of Artificial Intelligence Research, vol. 16, pp. 321–357, Jun. 2002.
  2. T. Saito and M. Rehmsmeier, “The Precision-Recall Plot Is More Informative than the ROC Plot When Evaluating Binary Classifiers on Imbalanced Datasets,” PLOS ONE, vol. 10, no. 3, p. e0118432, Mar. 2015.
  3. N. Japkowicz, “The Class Imbalance Problem: Significance and Strategies,” in In Proceedings of the 2000 International Conference on Artificial Intelligence (ICAI, 2000, pp. 111–117.
  4. “5. Ensemble of samplers — Version 0.8.0.” https://imbalanced-learn.org/stable/ensemble.html.
  5. C. Chen, “Using Random Forest to Learn Imbalanced Data,” p. 12.
 

Crédit image : Joanna Ławniczak – Dribble

Sommaire

Voir aussi

Voir aussi

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *