Classification multi-classe

Il existe plusieurs méthodes de transformation des problèmes de classification multi-label :

Certains algorithmes/modèles de classification ont été adaptés à la tâche multi-labels, sans nécessiter de transformation du problème. Voici quelques exemples, y compris pour les données multi-labels :

• k-plus-proches-voisins (KNN) : l'algorithme ML-kNN étend le classificateur k-NN aux données multi-labels^[5].
• Arbres de décision : « Clare » est une adaptation de l’algorithme C4.5 pour la classification multi-labels ; la modification porte sur les calculs d’entropie^[6]. MMC, MMDT et SSC (MMDT amélioré) permettent de classifier des données multi-labels en fonction d’attributs multivalués sans les convertir en valeurs uniques. Ces méthodes sont également appelées méthodes de classification par arbres de décision multivalués et multi-labels^[7],[3],[4].
• kernel methods for vector output (en)
• réseaux de neurones : BP-MLL est une adaptation de l'algorithme de rétro-propagation populaire pour l'apprentissage multi-label^[8].

Selon les paradigmes d'apprentissage, les techniques de classification multi-labels existantes se divisent en deux catégories : l'apprentissage par lots et l'apprentissage automatique en ligne . Les algorithmes d'apprentissage par lots nécessitent la disponibilité préalable de tous les échantillons de données. Ils entraînent le modèle à l'aide de l'ensemble des données d'entraînement, puis prédisent l'échantillon de test en utilisant la relation ainsi établie. Les algorithmes d'apprentissage en ligne, quant à eux, construisent leurs modèles de manière incrémentale par itérations successives. À l'itération t, un algorithme en ligne reçoit un échantillon x_t et prédit son ou ses labels ŷ _t à l'aide du modèle actuel; l'algorithme reçoit ensuite y _t, la ou les labels réels de x _t, et met à jour son modèle en fonction de la paire échantillon-étiquette : (x _t, y_t ).

Les flux de données sont des séquences de données potentiellement infinies qui croissent continuellement et rapidement au fil du temps^[3]. La classification de flux multi-labels (MLSC) est la version de la tâche de classification multi-labels qui s'effectue au sein de flux de données. Elle est parfois également appelée classification multi-labels en ligne. Les difficultés de la classification multi-labels (nombre exponentiel d'ensembles d'labels possibles, prise en compte des dépendances entre les labels) se combinent aux difficultés propres aux flux de données (contraintes de temps et de mémoire, traitement d'un flux infini avec des ressources finies, dérive conceptuelle ).

De nombreuses méthodes MLSC font appel à des méthodes ensemblistes afin d'améliorer leurs performances prédictives et de gérer les dérives conceptuelles. Voici les méthodes d'ensemble les plus couramment utilisées dans la littérature :

• Méthodes basées sur l'encaissement en ligne (OzaBagging^[3] ) : Constatant que la probabilité d'obtenir K points de données d'un certain type dans un échantillon bootstrap suit approximativement une loi de Poisson de paramètre 1 pour les grands ensembles de données, chaque instance de données entrante dans un flux de données peut être pondérée proportionnellement à une distribution de Poisson de paramètre 1 afin de simuler le bootstrap en ligne. C'est ce qu'on appelle l'encaissement en ligne (OzaBagging). De nombreuses méthodes multi-labels utilisant l'encaissement en ligne ont été proposées dans la littérature, chacune employant des méthodes de transformation du problème différentes. EBR , ECC^[1], EPS^[4] ], _EBRt^[9], _EBMt^[9] ML-Random Rules^[3] en sont des exemples.
• Méthodes basées sur l'agrégation ADWIN^[10] : Les méthodes d'agrégation en ligne pour l'apprentissage automatique multi-labels (MLSC) sont parfois combinées à des mécanismes explicites de détection de dérive conceptuelle, tels qu'ADWIN (Fenêtre adaptative). ADWIN utilise une fenêtre de taille variable pour détecter les changements dans la distribution des données et améliore l'ensemble en réinitialisant les composantes les moins performantes en cas de dérive des données entrantes. Généralement, la lettre « a » est utilisée en indice dans le nom de ces ensembles pour indiquer l'utilisation du détecteur de changement ADWIN. E _a BR^[10], E _a CC^[10] et E _{a HTPS}^[10] sont des exemples de tels ensembles multi-labels.
• Méthodes basées sur GOOWE-ML^[11] : En interprétant les scores de pertinence de chaque composante de l’ensemble comme des vecteurs dans l’espace des labels et en résolvant un problème des moindres carrés à la fin de chaque lot, l’ensemble pondéré en ligne géométriquement optimal pour la classification multi-labels (GOOWE-ML) est proposé. Cet ensemble cherche à minimiser la distance entre la prédiction pondérée de ses composantes et le vecteur de vérité terrain pour chaque instance d’un lot. Contrairement à Online Bagging et ADWIN Bagging, GOOWE-ML utilise un système de vote pondéré où les composantes les plus performantes de l’ensemble reçoivent un poids plus important. L’ensemble GOOWE-ML s’agrandit au fil du temps, et la composante ayant le poids le plus faible est remplacée par une nouvelle composante lorsqu’il est complet à la fin d’un lot. GOBR^[11], GOCC^[11], GOPS^[11] et GORT^[11] sont des ensembles multi-labels basés sur GOOWE-ML.
• Plusieurs fenêtres^[4] : Les modèles BR utilisant une fenêtre glissante sont remplacés par deux fenêtres par label : un pour les exemples pertinents et un pour les exemples non pertinents. Les instances sont sur-échantillonnées ou sous-échantillonnées selon un facteur de charge maintenu entre ces deux fenêtres. Ceci permet de détecter les dérives conceptuelles indépendantes pour chaque label et de gérer le déséquilibre des classes (asymétrie entre les exemples pertinents et non pertinents).

Considérant ${\displaystyle Y_{i}}$ être un ensemble de label pour un ${\displaystyle i^{eme}}$ échantillon de données (à ne pas confondre avec un vecteur encodé en « binaire à chaud » (one-hot en anglais); il s'agit simplement d'un ensemble de toutes les labels appartenant à cet échantillon), la mesure dans laquelle un ensemble de données est multi-label peut être capturée par deux statistiques :

• La cardinalité des labels correspond au nombre moyen d'labels par exemple dans l'ensemble : ${\displaystyle {\frac {1}{N}}\sum _{i=1}^{N}|Y_{i}|}$ où ${\displaystyle N}$ est le nombre total d'échantillons de données ;
• La densité des labels correspond au nombre d'labels par échantillon divisé par le nombre total de labels, moyenné sur l'ensemble des échantillons : ${\displaystyle {\frac {1}{N}}\sum _{i=1}^{N}{\frac {|Y_{i}|}{|L|}}}$ où ${\displaystyle L=\bigcup _{i=1}^{N}Y_{i}}$, le nombre total de classes disponibles (qui correspond au nombre maximal d'éléments pouvant composer ${\displaystyle Y_{i}}$ ).

Les métriques d'évaluation des performances de la classification multi-labels diffèrent fondamentalement de celles utilisées en classification multi-classe (ou binaire), en raison des différences inhérentes au problème de classification. Si T désigne l'ensemble réel des labels d'un échantillon donné et P l'ensemble des labels prédits, alors les métriques suivantes peuvent être définies sur cet échantillon :

• Distance de Hamming : la proportion de label erronées par rapport au nombre total de labels, c’est-à-dire ${\displaystyle {\frac {1}{|N|\cdot |L|}}\sum _{i=1}^{|N|}\sum _{j=1}^{|L|}\operatorname {xor} (y_{i,j},z_{i,j})}$, où ${\displaystyle y_{i,j}}$ est l'objectif, ${\displaystyle z_{i,j}}$ est la prédiction, et ${\displaystyle \operatorname {xor} (\cdot )}$ L' opérateur « OU exclusif » renvoie 0 lorsque la cible et la prédiction sont identiques, et 1 sinon. Il s'agit d'une fonction de perte ; sa valeur optimale est donc 0 et sa limite supérieure est 1.
• L' indice de Jaccard, étroitement lié à celui-ci et également appelé intersection sur union dans le contexte multi-labels, est défini comme le nombre de label correctement prédites divisé par l'union des labels prédits et réels. ${\displaystyle {\frac {|T\cap P|}{|T\cup P|}}}$, où ${\displaystyle P}$ et ${\displaystyle T}$ sont respectivement des ensembles de labels prédits et réels.
• Précision, rappel et ${\displaystyle F_{1}}$ score :
  • précision est ${\displaystyle {\frac {|T\cap P|}{|P|}}}$,
  • Rappel ${\displaystyle {\frac {|T\cap P|}{|T|}}}$,
  • ${\displaystyle F_{1}}$ score est leur moyenne harmonique^[12].
• Correspondance exacte (également appelée précision du sous-ensemble) : il s’agit de la mesure la plus stricte, indiquant le pourcentage d’échantillons dont toutes les labels ont été correctement classés.

La validation croisée dans un contexte multi-labels est compliquée par le fait que la méthode ordinaire (binaire/multi-classe) d' échantillonnage stratifié ne fonctionne pas ; des méthodes alternatives d'échantillonnage stratifié approximatif ont été suggérées^[3].

Des implémentations Java d'algorithmes multi-label sont disponibles dans les logiciels Mulan et Meka, tous deux basés sur Weka.

Le package Python scikit-learn implémente certains algorithmes et métriques multi-label .

Le package Python scikit-multilearn est spécifiquement conçu pour la classification multi-labels. Il propose une implémentation multi-labels de plusieurs techniques reconnues, notamment SVM, kNN et bien d'autres . Ce package repose sur l'écosystème scikit-learn .

La méthode de pertinence binaire, les chaînes de classificateurs et d'autres algorithmes multi-labels avec de nombreux apprenants de base différents sont implémentés dans le package R mlr

Une liste des ensembles de données multi-labels couramment utilisés est disponible sur le site Web de Mulan .

• Classification multi-classe
• Apprentissage à instances multiples
• Prédiction structurée
• Durée de vie de la corrélation