Classification multi-classe

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

La traduction de cet article ou de cette section doit être revue (janvier 2026).

Le contenu est difficilement compréhensible vu les erreurs de traduction, qui sont peut-être dues à l'utilisation d'un logiciel de traduction automatique.

Discutez des points à améliorer en page de discussion ou modifiez l'article.

En apprentissage automatique, la classification multi-label (ou classification à sorties multiples) est une variante du problème de classification où plusieurs labels non exclusifs peuvent être attribués à chaque instance. La classification multi-label généralise la classification multi-classe, qui consiste à catégoriser les instances dans une seule classe parmi plusieurs (au moins deux). Dans le problème multi-label, les labels ne sont pas exclusifs et il n'y a aucune contrainte sur le nombre de classes auxquelles une instance peut appartenir. La formulation de l'apprentissage multi-label a été introduite pour la première fois par Shen et al. dans le contexte de la Semantic Scene Classification , et s'est ensuite répandue dans divers domaines de l'apprentissage automatique.

La classification multi-label est le problème de trouver un modèle qui mappe les entrées x sur des vecteurs binaires y ; c'est-à-dire qu'il attribue une valeur de 0 ou 1 à chaque élément (label) de y .

Méthodes de transformation des problèmes

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

Transformation en problèmes de classification binaire (en)

L'approche de base, appelée méthode de pertinence binaire , consiste à entraîner indépendamment un classificateur binaire pour chaque label. Étant donné un échantillon inconnu, le modèle combiné prédit ensuite toutes les labels de cet échantillon pour lesquels les classificateurs respectifs prédisent un résultat positif. Bien que cette méthode de division de la tâche en plusieurs tâches binaires puisse superficiellement ressembler aux méthodes « un contre tous » (OvA) et « un contre tous » (OvR) pour la classification multi-classe, elle en est fondamentalement différente, car un classificateur unique, dans le cadre de la pertinence binaire, traite une seule label, sans tenir compte des autres. Une chaîne de classificateurs est une méthode alternative pour transformer un problème de classification multi-labels en plusieurs problèmes de classification binaire. Elle diffère de la pertinence binaire en ce que les labels sont prédits séquentiellement et que la sortie de tous les classificateurs précédents (c'est-à-dire positive ou négative pour une label particulier) est utilisée comme caractéristiques pour les classificateurs suivants. Les chaînes de classificateurs ont été appliquées, par exemple, à la prédiction de la résistance aux médicaments contre le VIH^,. Le réseau bayésien a également été appliqué pour ordonner de manière optimale les classificateurs dans les chaînes de classificateurs.

Dans le cas d'une transformation du problème en plusieurs classifications binaires, la fonction de vraisemblance s'écrit : $L=\prod _{i=1}^{n}(\prod _{k}(\prod _{j_{k}}(p_{k,j_{k}}(x_{i})^{\delta _{y_{i,k},j_{k}}})))$

où l'index $i$ parcourt les échantillons, index $k$ passe sur les labels, $j_{k}$ indique les résultats binaires 0 ou 1, $\delta _{a,b}$ indique le delta de Kronecker, $y_{i,k}\in {0,1}$ indique les multiples labels encodées en one-hot de l'échantillon $i$ .

Transformation en problème de classification multi-classe

Dans la classification multi-label, une autre approche consiste à transformer le problème en un problème de classification multi-classes en considérant chaque combinaison possible de labels comme une classe distincte. Ainsi, au lieu de prédire séparément la présence ou l’absence de chaque label, le modèle apprend à prédire directement l’ensemble des labels associés à une observation. Par exemple, si trois labels A, B et C sont possibles, chaque observation peut appartenir à l’une des combinaisons [0 0 0], [1 0 0], [0 1 0], [0 0 1], [1 1 0], [1 0 1], [0 1 1] ou [1 1 1], où chaque vecteur indique la présence (1) ou l’absence (0) de chaque label. Cette transformation permet de prendre en compte explicitement les dépendances entre labels, au prix d’une augmentation potentielle du nombre de classes lorsque le nombre de labels est élevé.

Méthodes d'apprentissage ensembliste

Les méthodes d’ensemble consistent à combiner plusieurs classifieurs afin de produire une prédiction multi-label. Dans le cas d’un ensemble de classifieurs multi-classes, chaque modèle prédit une classe pour une observation donnée, et les prédictions sont agrégées, le plus souvent par un mécanisme de vote : un label est retenu s’il reçoit un nombre suffisant de votes, défini par un seuil de discrimination. D’autres approches plus élaborées existent, telles que les committee machines. L’algorithme random k-labelsets (RAKEL) repose quant à lui sur un ensemble de classifieurs de type label powerset, chacun entraîné sur un sous-ensemble aléatoire de labels, les prédictions finales étant obtenues par vote. Il est également possible de combiner directement plusieurs classifieurs multi-label, chacun contribuant par un vote pour chaque label qu’il prédit.

Algorithmes adaptés

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.
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. 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^,^,.
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.

Paradigmes d'apprentissage

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 ).

Classification de flux multi-label

Les flux de données sont des séquences de données potentiellement infinies qui croissent continuellement et rapidement au fil du temps. 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 ) : 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, EPS ], _EBRt, _EBMt ML-Random Rules en sont des exemples.
Méthodes basées sur l'agrégation ADWIN : 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, E _a CC et E _a _HTPS sont des exemples de tels ensembles multi-labels.
Méthodes basées sur GOOWE-ML : 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, GOCC, GOPS et GORT sont des ensembles multi-labels basés sur GOOWE-ML.
Plusieurs fenêtres : 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).

Statistiques et indicateurs d'évaluation

Considérant $Y_{i}$ être un ensemble de label pour un $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 : ${\frac {1}{N}}\sum _{i=1}^{N}|Y_{i}|$ où $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 : ${\frac {1}{N}}\sum _{i=1}^{N}{\frac {|Y_{i}|}{|L|}}$ où $L=\bigcup _{i=1}^{N}Y_{i}$ , le nombre total de classes disponibles (qui correspond au nombre maximal d'éléments pouvant composer $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 ${\frac {1}{|N|\cdot |L|}}\sum _{i=1}^{|N|}\sum _{j=1}^{|L|}\operatorname {xor} (y_{i,j},z_{i,j})$ , où $y_{i,j}$ est l'objectif, $z_{i,j}$ est la prédiction, et $\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. ${\frac {|T\cap P|}{|T\cup P|}}$ , où $P$ et $T$ sont respectivement des ensembles de labels prédits et réels.
Précision, rappel et $F_{1}$ score :
- précision est ${\frac {|T\cap P|}{|P|}}$ ,
- Rappel ${\frac {|T\cap P|}{|T|}}$ ,
- $F_{1}$ score est leur moyenne harmonique.
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.

Implémentations et ensembles de données

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 .

Voir aussi

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

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Multi-label classification » (voir la liste des auteurs).

1 2 (en) Jesse Read, Bernhard Pfahringer, Geoff Holmes et Eibe Frank, « Classifier Chains for Multi-label Classification », Machine Learning Journal, Springer, vol. 85, n^o 3,‎ 2011 (lire en ligne).
↑ Heider, Senge, Cheng et Hüllermeier, « Multilabel classification for exploiting cross-resistance information in HIV-1 drug resistance prediction », Bioinformatics, vol. 29, n^o 16,‎ 2013, p. 1946–52 (PMID 23793752, DOI 10.1093/bioinformatics/btt331)
1 2 3 4 5 6 Riemenschneider, Senge, Neumann et Hüllermeier, « Exploiting HIV-1 protease and reverse transcriptase cross-resistance information for improved drug resistance prediction by means of multi-label classification », BioData Mining, vol. 9,‎ 2016, p. 10 (PMID 26933450, PMCID 4772363, DOI 10.1186/s13040-016-0089-1)
1 2 3 4 Soufan, Ba-Alawi, Afeef et Essack, « DRABAL: novel method to mine large high-throughput screening assays using Bayesian active learning », Journal of Cheminformatics, vol. 8,‎ 10 novembre 2016, p. 64 (ISSN 1758-2946, PMID 27895719, PMCID 5105261, DOI 10.1186/s13321-016-0177-8)
↑ Zhang et Zhou, « ML-KNN: A lazy learning approach to multi-label learning », Pattern Recognition, vol. 40, n^o 7,‎ 2007, p. 2038–2048 (DOI 10.1016/j.patcog.2006.12.019, Bibcode 2007PatRe..40.2038Z, S2CID 14886376, CiteSeer^x 10.1.1.538.9597)
↑ Madjarov, Kocev, Gjorgjevikj et Džeroski, « An extensive experimental comparison of methods for multi-label learning », Pattern Recognition, vol. 45, n^o 9,‎ 2012, p. 3084–3104 (DOI 10.1016/j.patcog.2012.03.004, Bibcode 2012PatRe..45.3084M, S2CID 14064264)
↑ Chen, Hsu et Chou, « Constructing a multi-valued and multi-labeled decision tree », Expert Systems with Applications, vol. 25, n^o 2,‎ 2003, p. 199–209 (DOI 10.1016/S0957-4174(03)00047-2)
↑ M.L. Zhang et Z.H. Zhou « Multi-label neural networks with applications to functional genomics and text categorization » (2006) (lire en ligne).
— IEEE Transactions on Knowledge and Data Engineering.
1 2 Osojnik, Panov et DźEroski, « Multi-label classification via multi-target regression on data streams », Machine Learning, vol. 106, n^o 6,‎ 1^er juin 2017, p. 745–770 (ISSN 0885-6125, DOI 10.1007/s10994-016-5613-5)
1 2 3 4 Read, Bifet, Holmes et Pfahringer, « Scalable and efficient multi-label classification for evolving data streams », Machine Learning, vol. 88, n^os 1–2,‎ 21 février 2012, p. 243–272 (ISSN 0885-6125, DOI 10.1007/s10994-012-5279-6)
1 2 3 4 5 Alican Büyükçakir, Hamed Bonab et Fazli Can, Proceedings of the 27th ACM International Conference on Information and Knowledge Management, ACM, 17 octobre 2018, 1063–1072 p. (ISBN 9781450360142, DOI 10.1145/3269206.3271774, arXiv 1809.09994, S2CID 52843253), « A Novel Online Stacked Ensemble for Multi-Label Stream Classification »
↑ Shantanu Godbole et Sunita Sarawagi « Discriminative methods for multi-labeled classification » (2004) (lire en ligne).
— Advances in Knowledge Discovery and Data Mining.

Pour en savoir plus

Madjarov, Kocev, Gjorgjevikj et Džeroski, « An extensive experimental comparison of methods for multi-label learning », Pattern Recognition, vol. 45, n^o 9,‎ 2012, p. 3084–3104 (DOI 10.1016/j.patcog.2012.03.004, Bibcode 2012PatRe..45.3084M, S2CID 14064264)

Portail des mathématiques

Portail de l’informatique

[classifierchains-1] 1 2 (en) Jesse Read, Bernhard Pfahringer, Geoff Holmes et Eibe Frank, « Classifier Chains for Multi-label Classification », Machine Learning Journal, Springer, vol. 85, n^o 3,‎ 2011 (lire en ligne).

[CCHIV-2] Heider, Senge, Cheng et Hüllermeier, « Multilabel classification for exploiting cross-resistance information in HIV-1 drug resistance prediction », Bioinformatics, vol. 29, n^o 16,‎ 2013, p. 1946–52 (PMID 23793752, DOI 10.1093/bioinformatics/btt331)

[Exploiting_HIV-1_protease_and_reverse_transcriptase_cross-resistance_information_for_improved_drug_resistance_prediction_by_means_of_multi-label_classification-3] 1 2 3 4 5 6 Riemenschneider, Senge, Neumann et Hüllermeier, « Exploiting HIV-1 protease and reverse transcriptase cross-resistance information for improved drug resistance prediction by means of multi-label classification », BioData Mining, vol. 9,‎ 2016, p. 10 (PMID 26933450, PMCID 4772363, DOI 10.1186/s13040-016-0089-1)

[DRABAL:_novel_method_to_mine_large_high-throughput_screening_assays_using_Bayesian_active_learning-4] 1 2 3 4 Soufan, Ba-Alawi, Afeef et Essack, « DRABAL: novel method to mine large high-throughput screening assays using Bayesian active learning », Journal of Cheminformatics, vol. 8,‎ 10 novembre 2016, p. 64 (ISSN 1758-2946, PMID 27895719, PMCID 5105261, DOI 10.1186/s13321-016-0177-8)

[ml_knn-5] Zhang et Zhou, « ML-KNN: A lazy learning approach to multi-label learning », Pattern Recognition, vol. 40, n^o 7,‎ 2007, p. 2038–2048 (DOI 10.1016/j.patcog.2006.12.019, Bibcode 2007PatRe..40.2038Z, S2CID 14886376, CiteSeer^x 10.1.1.538.9597)

[comp_label-6] Madjarov, Kocev, Gjorgjevikj et Džeroski, « An extensive experimental comparison of methods for multi-label learning », Pattern Recognition, vol. 45, n^o 9,‎ 2012, p. 3084–3104 (DOI 10.1016/j.patcog.2012.03.004, Bibcode 2012PatRe..45.3084M, S2CID 14064264)

[chc2003-7] Chen, Hsu et Chou, « Constructing a multi-valued and multi-labeled decision tree », Expert Systems with Applications, vol. 25, n^o 2,‎ 2003, p. 199–209 (DOI 10.1016/S0957-4174(03)00047-2)

[bp_mll-8] M.L. Zhang et Z.H. Zhou « Multi-label neural networks with applications to functional genomics and text categorization » (2006) (lire en ligne).
— IEEE Transactions on Knowledge and Data Engineering.

[:1-9] 1 2 Osojnik, Panov et DźEroski, « Multi-label classification via multi-target regression on data streams », Machine Learning, vol. 106, n^o 6,‎ 1^er juin 2017, p. 745–770 (ISSN 0885-6125, DOI 10.1007/s10994-016-5613-5)

[:2-10] 1 2 3 4 Read, Bifet, Holmes et Pfahringer, « Scalable and efficient multi-label classification for evolving data streams », Machine Learning, vol. 88, n^os 1–2,‎ 21 février 2012, p. 243–272 (ISSN 0885-6125, DOI 10.1007/s10994-012-5279-6)

[:3-11] 1 2 3 4 5 Alican Büyükçakir, Hamed Bonab et Fazli Can, Proceedings of the 27th ACM International Conference on Information and Knowledge Management, ACM, 17 octobre 2018, 1063–1072 p. (ISBN 9781450360142, DOI 10.1145/3269206.3271774, arXiv 1809.09994, S2CID 52843253), « A Novel Online Stacked Ensemble for Multi-Label Stream Classification »

[godbole-12] Shantanu Godbole et Sunita Sarawagi « Discriminative methods for multi-labeled classification » (2004) (lire en ligne).
— Advances in Knowledge Discovery and Data Mining.