Classification multi-étiquettes

En apprentissage automatique , la classification multi-étiquettes ou la classification multi-sorties est une variante du problème de classification dans laquelle plusieurs étiquettes non exclusives peuvent être attribuées à chaque instance. La classification multi-étiquettes est une généralisation de la classification multiclasse , qui est le problème d'une seule étiquette consistant à catégoriser les instances dans une classe précise parmi plusieurs (supérieures ou égales à deux). Dans le problème multi-étiquettes, les étiquettes ne sont pas exclusives et il n'y a aucune contrainte sur le nombre de classes auxquelles l'instance peut être affectée.

Formellement, la classification multi-étiquettes consiste à trouver un modèle qui mappe les entrées x aux vecteurs binaires y ; c'est-à-dire qu'il attribue une valeur de 0 ou 1 pour chaque élément (étiquette) dans y .

Méthodes de transformation des problèmes

Il existe plusieurs méthodes de transformation de problèmes pour la classification multi-étiquettes et peuvent être grossièrement décomposées en :

Transformation en problèmes de classification binaire

L'approche de base, appelée méthode de pertinence binaire , [1] revient à former indépendamment un classificateur binaire pour chaque étiquette. Étant donné un échantillon invisible, le modèle combiné prédit ensuite toutes les étiquettes de cet échantillon pour lesquelles 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 ressembler superficiellement aux méthodes un contre tous (OvA) et un contre reste (OvR) pour la classification multiclasse , elle est essentiellement différente des deux, car un seul classificateur sous pertinence binaire, il s'agit d'une seule étiquette, sans aucune considération pour les autres étiquettes. Une chaîne de classificateurs est une méthode alternative pour transformer un problème de classification multi-étiquettes en plusieurs problèmes de classification binaire. Elle diffère de la pertinence binaire en ce sens que les étiquettes sont prédites séquentiellement et que les résultats de tous les classificateurs précédents (c'est-à-dire positifs ou négatifs pour une étiquette particulière) sont entrés en tant que caractéristiques dans les classificateurs suivants. [1] Les chaînes de classificateurs ont été appliquées, par exemple, à la prédiction de la résistance aux médicaments du VIH . [2] [3] Le réseau bayésien a également été appliqué pour ordonner de manière optimale les classificateurs dans les chaînes de classificateurs . [4]

En cas de transformation du problème en plusieurs classifications binaires, la fonction de vraisemblance lit où l'index parcourt les échantillons, l'index parcourt les étiquettes, indique les résultats binaires 0 ou 1, indique le delta de Kronecker , indique les multiples étiquettes codées à chaud de l'échantillon .

Transformation en problème de classification multi-classes

La transformation Label Powerset (LP) crée un classificateur binaire pour chaque combinaison d'étiquettes présente dans l'ensemble d'apprentissage. Par exemple, si les étiquettes possibles pour un exemple étaient A, B et C, la représentation de l'ensemble de puissances d'étiquettes de ce problème est un problème de classification multi-classes avec les classes [0 0 0], [1 0 0], [0 1 0 ], [0 0 1], [1 1 0], [1 0 1], [0 1 1] et [1 1 1] où par exemple [1 0 1] désigne un exemple où les étiquettes A et C sont présentes et l'étiquette B est absente. [5]

Méthodes d'ensemble

Un ensemble de classificateurs multi-classes peut être utilisé pour créer un classificateur d'ensemble multi-étiquettes. Pour un exemple donné, chaque classificateur génère une seule classe (correspondant à une seule étiquette dans le problème multi-étiquettes). Ces prédictions sont ensuite combinées par une méthode d'ensemble, généralement un système de vote dans lequel chaque classe qui reçoit un pourcentage requis de votes de la part de classificateurs individuels (souvent appelé seuil de discrimination [6] ) est prédite comme une étiquette présente dans le multi-étiquette. sortir. Cependant, il existe des méthodes d'ensemble plus complexes, telles que les machines à comité . Une autre variante est l'algorithme RAKEL (random k -labelsets), qui utilise plusieurs classificateurs LP, chacun formé sur un sous-ensemble aléatoire des étiquettes réelles ; la prédiction d'étiquette est ensuite effectuée par un système de vote. [7] Un ensemble de classificateurs multi-étiquettes peut être utilisé de la même manière pour créer un classificateur d'ensemble multi-étiquettes. Dans ce cas, chaque classificateur vote une fois pour chaque étiquette qu’il prédit plutôt que pour une seule étiquette.

Algorithmes adaptés

Certains algorithmes/modèles de classification ont été adaptés à la tâche multi-étiquettes, sans nécessiter de transformations de problèmes. Des exemples de ceux-ci, y compris pour les données multi-étiquettes, sont

  • k-voisins les plus proches : l'algorithme ML-kNN étend le classificateur k-NN aux données multi-étiquettes. [8]
  • arbres de décision : "Clare" est un algorithme C4.5 adapté pour la classification multi-étiquettes ; la modification implique les calculs d'entropie. [9] MMC, MMDT et SSC ont affiné MMDT, peuvent classer des données multi-étiquetées en fonction d'attributs à valeurs multiples sans transformer les attributs en valeurs uniques. Elles sont également appelées méthodes de classification d'arbres de décision à valeurs multiples et à étiquettes multiples. [10] [11] [12]
  • méthodes du noyau pour la sortie vectorielle
  • réseaux de neurones : BP-MLL est une adaptation de l'algorithme de rétro-propagation populaire pour l'apprentissage multi-étiquettes. [13]

Paradigmes d'apprentissage

Sur la base des paradigmes d'apprentissage, les techniques de classification multi-étiquettes existantes peuvent être classées en apprentissage par lots et apprentissage automatique en ligne . Les algorithmes d’apprentissage par lots nécessitent que tous les échantillons de données soient disponibles au préalable. Il entraîne le modèle en utilisant l'intégralité des données d'entraînement, puis prédit l'échantillon de test à l'aide de la relation trouvée. Les algorithmes d’apprentissage en ligne, quant à eux, construisent progressivement leurs modèles par itérations séquentielles. Dans l'itération t, un algorithme en ligne reçoit un échantillon, x t et prédit sa ou ses étiquettes ŷ t en utilisant le modèle actuel ; l'algorithme reçoit ensuite y t , la ou les vraies étiquettes de x t et met à jour son modèle en fonction de la paire échantillon-étiquette : (x t , y t ).

Classification des flux multi-étiquettes

Les flux de données sont des séquences de données potentiellement infinies qui augmentent continuellement et rapidement au fil du temps. [14] La classification de flux multi-étiquettes (MLSC) est la version de la tâche de classification multi-étiquette qui a lieu dans les flux de données. On l'appelle parfois aussi classification multi-étiquettes en ligne. Les difficultés de la classification multi-étiquettes (nombre exponentiel d'ensembles d'étiquettes possibles, capture des dépendances entre étiquettes) se conjuguent aux difficultés des flux de données (contraintes de temps et de mémoire, adressage de flux infinis avec des moyens finis, dérives conceptuelles ).

De nombreuses méthodes MLSC recourent à des méthodes d’ensemble afin d’augmenter leurs performances prédictives et de gérer les dérives conceptuelles. Voici les méthodes d’ensemble les plus utilisées dans la littérature :

  • Méthodes basées sur le Online Bagging (OzaBagging [15] ) : L'observation de la probabilité d'avoir K plusieurs d'un certain point de données dans un échantillon bootstrap est approximativement de Poisson(1) pour les grands ensembles de données, chaque instance de données entrantes dans un flux de données peut être pondérée proportionnellement. à la distribution de Poisson(1) pour imiter le bootstrap dans un environnement en ligne. C'est ce qu'on appelle l'ensachage en ligne (OzaBagging). De nombreuses méthodes multi-étiquettes utilisant Online Bagging sont proposées dans la littérature, chacune utilisant différentes méthodes de transformation de problèmes. EBR, [1] ECC, [1] EPS, [16] E B RT, [17] E B MT, [17] ML-Random Rules [18] sont des exemples de telles méthodes.
  • Méthodes basées sur ADWIN Bagging [19] : Les méthodes de bagging en ligne pour MLSC sont parfois combinées avec des mécanismes de détection de dérive de concept explicites tels que ADWIN [20] (Adaptive Window). ADWIN conserve 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 composants qui fonctionnent mal en cas de dérive dans les données entrantes. Généralement, la lettre « a » est utilisée comme indice dans le nom de ces ensembles pour indiquer l'utilisation du détecteur de changement ADWIN. E a BR, [19] E a CC, [19] E a HT PS [19] sont des exemples de tels ensembles multi-étiquettes.
  • Méthodes basées sur GOOWE-ML [21] : Interprétation des scores de pertinence de chaque composant de l'ensemble sous forme de vecteurs dans l'espace des étiquettes et résolution d'un problème des moindres carrés à la fin de chaque lot, Ensemble pondéré en ligne géométriquement optimal pour multi-étiquettes Une classification (GOOWE-ML) est proposée. L'ensemble tente de minimiser la distance entre la prédiction pondérée de ses composants et le vecteur de vérité terrain pour chaque instance sur un lot. Contrairement à Online Bagging et ADWIN Bagging, GOOWE-ML utilise un système de vote pondéré dans lequel les composants les plus performants de l'ensemble reçoivent plus de poids. L'ensemble GOOWE-ML s'agrandit avec le temps, et le composant de poids le plus faible est remplacé par un nouveau composant lorsqu'il est plein à la fin d'un lot. GOBR, [21] GOCC, [21] GOPS, [21] GORT [21] sont les ensembles multi-étiquettes proposés basés sur GOOWE-ML.
  • Fenêtres multiples [22]  : Ici, les modèles BR qui utilisent une fenêtre coulissante sont remplacés par deux fenêtres pour chaque étiquette, une pour les exemples pertinents et une pour les exemples non pertinents. Les instances sont suréchantillonnées ou sous-échantillonnées selon un facteur de charge conservé entre ces deux fenêtres. Cela permet de détecter les dérives conceptuelles indépendantes pour chaque étiquette et de gérer le déséquilibre des classes (asymétrie dans les exemples pertinents et non pertinents).

Statistiques et mesures d'évaluation

Considérant qu'il s'agit d'un ensemble d'étiquettes pour un échantillon de données (ne le confondez pas avec un vecteur unique ; il s'agit simplement d'une collection de toutes les étiquettes qui appartiennent à cet échantillon), la mesure dans laquelle un ensemble de données est multi-étiquettes peut être capturé dans deux statistiques :

  • La cardinalité des étiquettes est le nombre moyen d'étiquettes par exemple dans l'ensemble : est le nombre total d'échantillons de données ;
  • La densité des étiquettes est le nombre d'étiquettes par échantillon divisé par le nombre total d'étiquettes, moyenné sur les échantillons : , le nombre total de classes disponibles (qui est le nombre maximum d'éléments pouvant constituer ).

Les mesures d'évaluation des performances de classification multi-étiquettes sont intrinsèquement différentes de celles utilisées dans la classification multi-classes (ou binaire), en raison des différences inhérentes au problème de classification. Si T désigne le véritable ensemble d'étiquettes pour un échantillon donné et P l'ensemble d'étiquettes prédit, alors les métriques suivantes peuvent être définies sur cet échantillon :

  • Perte de Hamming : la fraction des mauvaises étiquettes par rapport au nombre total d'étiquettes, c'est-à-dire est la cible, est la prédiction et est l' opérateur "Exclusif, ou" qui renvoie zéro lorsque la cible et la prédiction sont identiques et une dans le cas contraire. Il s'agit d'une fonction de perte , donc la valeur optimale est zéro et sa limite supérieure est un.
  • L' indice Jaccard étroitement lié , également appelé Intersection sur Union dans le cadre multi-étiquettes, est défini comme le nombre d'étiquettes correctement prédites divisé par l'union des étiquettes prédites et vraies, et sont respectivement des ensembles d'étiquettes prédites et d'étiquettes vraies.
  • Précision, rappel et score : la précision est , le rappel est , et est leur moyenne harmonique . [23]
  • Correspondance exacte (également appelée précision du sous-ensemble) : est la mesure la plus stricte, indiquant le pourcentage d'échantillons dont toutes leurs étiquettes sont correctement classées.

La validation croisée dans des contextes multi-étiquettes est compliquée par le fait que la méthode ordinaire (binaire/multiclasse) d' échantillonnage stratifié ne fonctionnera pas ; d'autres méthodes d'échantillonnage stratifié approximatif ont été suggérées. [24]

Implémentations et ensembles de données

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

Le package Python scikit-learn implémente des algorithmes et des métriques multi-étiquettes.

Le package Python scikit-multilearn s'adresse spécifiquement à la classification multi-étiquettes. Il fournit une implémentation multi-étiquettes de plusieurs techniques bien connues, notamment SVM, kNN et bien d'autres. Le package est construit sur l’ écosystème scikit-learn .

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

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

Voir également

Les références

  1. ^ abcd Jesse Read, Bernhard Pfahringer, Geoff Holmes, Eibe Frank. Chaînes de classificateurs pour la classification multi-étiquettes. Journal d'apprentissage automatique. Springer. Vol. 85(3), (2011).
  2. ^ Heider, D; Sengé, R ; Cheng, W; En ligneHüllermeier, E (2013). "Classification multilabel pour exploiter les informations sur la résistance croisée dans la prédiction de la résistance aux médicaments du VIH-1". Bioinformatique . 29 (16) : 1946-1952. est ce que je : 10.1093/bioinformatique/btt331 . PMID  23793752.
  3. ^ Riemenschneider, M; Sengé, R ; Neumann, U; Hullermeier, E; Heider, D (2016). "Exploiter les informations sur la résistance croisée de la protéase du VIH-1 et de la transcriptase inverse pour améliorer la prédiction de la résistance aux médicaments au moyen d'une classification multi-étiquettes". Exploration de biodonnées . 9 : 10. est ce que je : 10.1186/s13040-016-0089-1 . PMC4772363 . _ PMID  26933450. 
  4. ^ Soufan, Othman; Ba-Alawi, Gémissez ; Afef, Moataz ; Essack, Magbubah ; Kalnis, Panos ; Bajic, Vladimir B. (10/11/2016). "DRABAL : nouvelle méthode pour extraire de grands tests de criblage à haut débit en utilisant l'apprentissage actif bayésien" . Journal de Chemininformatique . 8 : 64. est ce que je : 10.1186/s13321-016-0177-8 . ISSN1758-2946  . PMC5105261 . _ PMID  27895719. 
  5. ^ Spolaôr, Newton ; Cherman, Everton Alvares ; Monard, Maria Caroline ; Lee, Huei Diana (mars 2013). "Une comparaison des méthodes de sélection de fonctionnalités multi-étiquettes utilisant l'approche de transformation des problèmes". Notes électroniques en informatique théorique . 292 : 135-151. est ce que je : 10.1016/j.entcs.2013.02.010 . ISSN1571-0661  .
  6. ^ "Seuil de discrimination — documentation Yellowbrick 0.9" . www.scikit-yb.org . Récupéré le 29/11/2018 .
  7. ^ Tsoumakas, Grigorios ; Vlahavas, Ioannis (2007). K-labelsets aléatoires : une méthode d'ensemble pour la classification multi-étiquettes (PDF) . CELV. Archivé de l'original (PDF) le 29/07/2014 . Récupéré le 26/07/2014 .
  8. ^ Zhang, ML; Zhou, ZH (2007). "ML-KNN : Une approche d'apprentissage paresseux pour l'apprentissage multi-étiquettes". La reconnaissance de formes . 40 (7) : 2038-2048. Bibcode :2007PatRe..40.2038Z. CiteSeerX10.1.1.538.9597 . _ est ce que je :10.1016/j.patcog.2006.12.019. S2CID14886376  . 
  9. ^ Madjarov, Gjorgji; Kocev, Dragi ; Gjorgjevikj, Dejan; Dzeroski, Saso (2012). "Une comparaison expérimentale approfondie des méthodes d'apprentissage multi-étiquettes". La reconnaissance de formes . 45 (9) : 3084-3104. Bibcode :2012PatRe..45.3084M. est ce que je :10.1016/j.patcog.2012.03.004. S2CID14064264  .
  10. ^ Chen, Yen-Liang; Hsu, Chang-Ling ; Chou, Shih-chieh (2003). "Construire un arbre de décision multi-valué et multi-étiqueté". Systèmes experts avec applications . 25 (2) : 199-209. est ce que je :10.1016/S0957-4174(03)00047-2.
  11. ^ Chou, Shihchieh ; Hsu, Chang-Ling (01/05/2005). "MMDT : un classificateur d'arbre de décision multi-valué et multi-étiqueté pour l'exploration de données". Systèmes experts avec applications . 28 (4) : 799-812. est ce que je :10.1016/j.eswa.2004.12.035.
  12. ^ Li, Hong; Guo, Yue-jian ; Wu, Min ; Li, Ping ; Xiang, Yao (01/12/2010). "Combinez la décomposition d'attributs à valeurs multiples avec l'apprentissage multi-étiquettes". Systèmes experts avec applications . 37 (12) : 8721-8728. est ce que je :10.1016/j.eswa.2010.06.044.
  13. ^ Zhang, ML; Zhou, ZH (2006). Réseaux de neurones multi-étiquettes avec applications à la génomique fonctionnelle et à la catégorisation de textes (PDF) . Transactions IEEE sur l'ingénierie des connaissances et des données. Vol. 18. pages 1338-1351.
  14. ^ Aggarwal, Charu C., éd. (2007). Flux de données . Avancées dans les systèmes de bases de données. Vol. 31. est ce que je :10.1007/978-0-387-47534-9. ISBN 978-0-387-28759-1.
  15. ^ Oza, Nikunj (2005). "Ensachage et boosting en ligne". Conférence internationale de l'IEEE sur les systèmes, l'homme et la cybernétique . hdl : 2060/20050239012 .
  16. ^ Lisez, Jesse; Pfahringer, Bernhard ; Holmes, Geoff (15/12/2008). "Classification multi-étiquettes utilisant des ensembles d'ensembles élagués". 2008 Huitième conférence internationale de l'IEEE sur l'exploration de données. Société informatique IEEE. pp. 995-1000. est ce que je :10.1109/ICDM.2008.74. hdl :10289/8077. ISBN 9780769535029. S2CID16059274  .
  17. ^ un b Osojnik, Aljaź; Panov, PanăźE; DźEroski, Sašo (01/06/2017). "Classification multi-étiquettes via régression multi-cibles sur les flux de données". Apprentissage automatique . 106 (6) : 745-770. est ce que je : 10.1007/s10994-016-5613-5 . ISSN0885-6125  .
  18. ^ Sousa, Ricardo; Gama, João (2018-01-24). "Classification multi-étiquettes à partir de flux de données à grande vitesse avec des règles de modèle adaptatives et des règles aléatoires". Progrès de l'intelligence artificielle . 7 (3) : 177-187. est ce que je :10.1007/s13748-018-0142-z. ISSN2192-6352  . S2CID32376722  .
  19. ^ abcd Lire, Jesse; Bifet, Albert ; Holmes, Geoff ; Pfahringer, Bernhard (21/02/2012). "Classification multi-étiquettes évolutive et efficace pour les flux de données évolutifs". Apprentissage automatique . 88 (1-2) : 243-272. est ce que je : 10.1007/s10994-012-5279-6 . ISSN0885-6125  .
  20. ^ Bifet, Albert ; Gavaldà, Ricard (2007-04-26), "Learning from Time-Changing Data with Adaptive Windowing", Actes de la Conférence internationale SIAM 2007 sur l'exploration de données , Society for Industrial and Applied Mathematics, pp. 443-448, CiteSeerX 10.1. 1.215.8387 , est ce que je :10.1137/1.9781611972771.42, ISBN  9780898716306, S2CID2279539  _
  21. ^ abcde Büyükçakir, Alican; Bonab, Hamed ; Peut, Fazli (17/10/2018). "Un nouvel ensemble empilé en ligne pour la classification de flux multi-étiquettes". Actes de la 27e Conférence internationale de l'ACM sur la gestion de l'information et des connaissances . ACM. pages 1063 à 1072. arXiv : 1809.09994 . est ce que je :10.1145/3269206.3271774. ISBN 9781450360142. S2CID52843253  .
  22. ^ Xioufis, Eleftherios Spyromitros; Spiliopoulou, Myra; Tsoumakas, Grigorios ; Vlahavas, Ioannis (16/07/2011). Gérer la dérive des concepts et le déséquilibre des classes dans la classification des flux multi-étiquettes. Presse AAAI. pages 1583 à 1588. est ce que je :10.5591/978-1-57735-516-8/IJCAI11-266. ISBN 9781577355144.
  23. ^ Godbole, Shantanu; Sarawagi, Sunita (2004). Méthodes discriminantes pour la classification multi-étiquetée (PDF) . Progrès dans la découverte des connaissances et l’exploration de données. p. 22-30.
  24. ^ Séchidis, Konstantinos ; Tsoumakas, Grigorios ; Vlahavas, Ioannis (2011). Sur la stratification des données multi-étiquettes (PDF) . CELV PKDD . pp. 145-158.
  25. ^ Philipp Probst, Quay Au, Giuseppe Casalicchio, Clemens Stachl, Bernd Bischl. Classification multilabel avec R Package mlr. Le Journal R (2017) 9:1, pages 352-369.

Lectures complémentaires

  • Madjarov, Gjorgji ; Kocev, Dragi ; Gjorgjevikj, Dejan; Dzeroski, Saso (2012). "Une comparaison expérimentale approfondie des méthodes d'apprentissage multi-étiquettes". La reconnaissance de formes . 45 (9) : 3084-3104. Bibcode :2012PatRe..45.3084M. est ce que je :10.1016/j.patcog.2012.03.004. S2CID14064264  .
Extrait de "https://en.wikipedia.org/w/index.php?title=Multi-label_classification&oldid=1203279413"