Clasificación de múltiples etiquetas

Problema de clasificación en el que se pueden asignar múltiples etiquetas a cada instancia

En el aprendizaje automático , la clasificación de múltiples etiquetas o la clasificación de múltiples salidas es una variante del problema de clasificación en el que se pueden asignar múltiples etiquetas no exclusivas a cada instancia. La clasificación de múltiples etiquetas es una generalización de la clasificación de múltiples clases , que es el problema de etiqueta única de categorizar instancias en precisamente una de varias clases (mayores o iguales a dos). En el problema de múltiples etiquetas, las etiquetas no son exclusivas y no hay ninguna restricción sobre a cuántas de las clases se puede asignar la instancia.

Formalmente, la clasificación de múltiples etiquetas es el problema de encontrar un modelo que asigne las entradas x a los vectores binarios y ; es decir, asigna un valor de 0 o 1 para cada elemento (etiqueta) en y .

Métodos de transformación de problemas

Existen varios métodos de transformación de problemas para la clasificación de múltiples etiquetas, y se pueden dividir en:

Transformación enclasificación binariaproblemas

El método de referencia, llamado método de relevancia binaria , ^[1] consiste en entrenar de forma independiente un clasificador binario para cada etiqueta. Dada una muestra no vista, el modelo combinado predice entonces todas las etiquetas para esta muestra para las cuales los clasificadores respectivos predicen un resultado positivo. Aunque este método de dividir la tarea en múltiples tareas binarias puede parecerse superficialmente a los métodos uno contra todos (OvA) y uno contra el resto (OvR) para la clasificación multiclase , es esencialmente diferente de ambos, porque un solo clasificador bajo relevancia binaria trata con una sola etiqueta, sin tener en cuenta otras etiquetas en absoluto. Una cadena de clasificadores es un método alternativo para transformar un problema de clasificación de múltiples etiquetas en varios problemas de clasificación binaria. Se diferencia de la relevancia binaria en que las etiquetas se predicen secuencialmente, y la salida de todos los clasificadores anteriores (es decir, positiva o negativa para una etiqueta particular) se ingresa como características a los clasificadores posteriores. ^[1] Las cadenas de clasificadores se han aplicado, por ejemplo, en la predicción de la resistencia a los medicamentos contra el VIH . ^{[2] [3]} La red bayesiana también se ha aplicado para ordenar de forma óptima los clasificadores en cadenas de clasificadores . ^[4]

En caso de transformar el problema a clasificaciones binarias múltiples, la función de verosimilitud se lee donde el índice recorre las muestras, el índice recorre las etiquetas, indica los resultados binarios 0 o 1, indica el delta de Kronecker , indica las múltiples etiquetas codificadas en caliente de la muestra . ${\displaystyle L=\prod _{i=1}^{n}(\prod _{k}(\prod _{j_{k}}(p_{k,j_{k}}(x_{i})^{\delta _{y_{i,k},j_{k}}})))}$ ${\displaystyle i}$ ${\displaystyle k}$ ${\displaystyle j_{k}}$ ${\displaystyle \delta _{a,b}}$ ${\displaystyle y_{i,k}\in {0,1}}$ ${\displaystyle i}$

Transformación enclasificación multiclaseproblema

La transformación de conjunto de potencias de etiquetas (LP) crea un clasificador binario para cada combinación de etiquetas presente en el conjunto de entrenamiento. Por ejemplo, si las etiquetas posibles para un ejemplo fueran A, B y C, la representación del conjunto de potencias de etiquetas de este problema es un problema de clasificación de múltiples clases con las clases [0 0 0], [1 0 0], [0 1 0], [0 0 1], [1 1 0], [1 0 1], [0 1 1] y [1 1 1] donde, por ejemplo, [1 0 1] denota un ejemplo donde las etiquetas A y C están presentes y la etiqueta B está ausente. ^[5]

Métodos de conjunto

Un conjunto de clasificadores de múltiples clases se puede utilizar para crear un clasificador de conjunto de múltiples etiquetas. Para un ejemplo dado, cada clasificador genera una sola clase (que corresponde a una sola etiqueta en el problema de múltiples etiquetas). Estas predicciones se combinan luego mediante un método de conjunto, generalmente un esquema de votación donde cada clase que recibe un porcentaje requerido de votos de clasificadores individuales (a menudo denominado umbral de discriminación ^[6] ) se predice como una etiqueta presente en la salida de múltiples etiquetas. Sin embargo, existen métodos de conjunto más complejos, como las máquinas de comité . Otra variación es el algoritmo de k -etiquetas aleatorias (RAKEL), que utiliza múltiples clasificadores LP, cada uno entrenado en un subconjunto aleatorio de las etiquetas reales; la predicción de etiquetas se lleva a cabo luego mediante un esquema de votación. ^[7] Un conjunto de clasificadores de múltiples etiquetas se puede utilizar de manera similar para crear un clasificador de conjunto de múltiples etiquetas. En este caso, cada clasificador vota una vez por cada etiqueta que predice en lugar de por una sola etiqueta.

Algoritmos adaptados

Algunos algoritmos/modelos de clasificación se han adaptado a la tarea de etiquetas múltiples, sin necesidad de transformaciones de problemas. Algunos ejemplos de estos algoritmos/modelos de clasificación, incluidos los de datos de etiquetas múltiples, son:

• k-vecinos más cercanos : el algoritmo ML-kNN extiende el clasificador k-NN a datos de múltiples etiquetas. ^[8]
• Árboles de decisión : "Clare" es un algoritmo C4.5 adaptado para la clasificación de múltiples etiquetas; la modificación involucra los cálculos de entropía. ^[9] MMC, MMDT y SSC refinaron el MMDT, pueden clasificar datos de múltiples etiquetas en función de atributos de múltiples valores sin transformar los atributos en valores únicos. También se denominan métodos de clasificación de árboles de decisión de múltiples valores y múltiples etiquetas. ^{[10] [11] [12]}
• métodos de kernel para salida vectorial
• Redes neuronales : BP-MLL es una adaptación del popular algoritmo de retropropagación para el aprendizaje de múltiples etiquetas. ^[13]

Paradigmas de aprendizaje

Basándose en paradigmas de aprendizaje, las técnicas de clasificación de múltiples etiquetas existentes se pueden clasificar en aprendizaje por lotes y aprendizaje automático en línea . Los algoritmos de aprendizaje por lotes requieren que todas las muestras de datos estén disponibles de antemano. Entrena el modelo utilizando todos los datos de entrenamiento y luego predice la muestra de prueba utilizando la relación encontrada. Los algoritmos de aprendizaje en línea, por otro lado, construyen sus modelos de forma incremental en iteraciones secuenciales. En la iteración t, un algoritmo en línea recibe una muestra, x _t y predice su(s) etiqueta(s) ŷ _t utilizando el modelo actual; luego, el algoritmo recibe y _t , la(s) etiqueta(s) verdadera(s) de x _t y actualiza su modelo basándose en el par muestra-etiqueta: (x _t , y _t ).

Clasificación de flujos con múltiples etiquetas

Los flujos de datos son secuencias infinitas de datos que crecen de forma continua y rápida con el tiempo. ^[14] La clasificación de flujos de etiquetas múltiples (MLSC) es la versión de la tarea de clasificación de etiquetas múltiples que se lleva a cabo en flujos de datos. A veces también se denomina clasificación de etiquetas múltiples en línea. Las dificultades de la clasificación de etiquetas múltiples (número exponencial de conjuntos de etiquetas posibles, captura de dependencias entre etiquetas) se combinan con las dificultades de los flujos de datos (restricciones de tiempo y memoria, direccionamiento de flujos infinitos con medios finitos, derivas conceptuales ).

Muchos métodos MLSC recurren a métodos de conjunto para aumentar su rendimiento predictivo y abordar las desviaciones conceptuales. A continuación, se presentan los métodos de conjunto más utilizados en la literatura:

• Métodos basados ​​en Online Bagging (OzaBagging ^[15] ) : observar la probabilidad de tener K muchos de un cierto punto de datos en una muestra de bootstrap es aproximadamente Poisson(1) para grandes conjuntos de datos, cada instancia de datos entrante en un flujo de datos se puede ponderar proporcionalmente a la distribución de Poisson(1) para imitar el bootstrap en un entorno en línea. Esto se llama Online Bagging (OzaBagging). En la literatura se proponen muchos métodos de múltiples etiquetas que utilizan Online Bagging, cada uno de los cuales utiliza diferentes métodos de transformación de problemas. EBR, ^[1] ECC, ^[1] EPS, ^[16] E _B RT, ^[17] E _B MT, ^[17] ML-Random Rules ^[18] son ​​ejemplos de dichos métodos.
• Métodos basados ​​en ADWIN Bagging ^[19] : los métodos de Bagging en línea para MLSC a veces se combinan con mecanismos explícitos de detección de deriva de conceptos como ADWIN ^[20] (ventana adaptativa). ADWIN mantiene una ventana de tamaño variable para detectar cambios en la distribución de los datos y mejora el conjunto al restablecer los componentes que funcionan mal cuando hay una deriva en los datos entrantes. Generalmente, la letra 'a' se utiliza como subíndice en el nombre de dichos conjuntos para indicar el uso del detector de cambios ADWIN. E _a BR, ^[19] E _a CC, ^[19] E _a HT _PS ^[19] son ​​ejemplos de dichos conjuntos de múltiples etiquetas.
• Métodos basados ​​en GOOWE-ML ^[21] : interpretando las puntuaciones de relevancia de cada componente del conjunto como vectores en el espacio de etiquetas y resolviendo un problema de mínimos cuadrados al final de cada lote, se propone el conjunto ponderado en línea geométricamente óptimo para la clasificación de múltiples etiquetas (GOOWE-ML). El conjunto intenta minimizar la distancia entre la predicción ponderada de sus componentes y el vector de verdad fundamental para cada instancia en un lote. A diferencia del ensacado en línea y el ensacado ADWIN, GOOWE-ML utiliza un esquema de votación ponderada donde los componentes de mejor desempeño del conjunto reciben más peso. El conjunto GOOWE-ML crece con el tiempo y el componente de menor peso se reemplaza por un nuevo componente cuando está completo al final de un lote. GOBR, ^[21] GOCC, ^[21] GOPS, ^[21] GORT ^[21] son ​​los conjuntos de múltiples etiquetas basados ​​en GOOWE-ML propuestos.
• Ventanas múltiples ^[22]  : aquí, los modelos BR que utilizan una ventana deslizante se reemplazan con dos ventanas para cada etiqueta, una para los ejemplos relevantes y otra para los no relevantes. Las instancias se sobremuestrean o submuestrean según un factor de carga que se mantiene entre estas dos ventanas. Esto permite detectar desviaciones de conceptos que son independientes para cada etiqueta y manejar el desequilibrio de clases (desequilibrio en los ejemplos relevantes y no relevantes).

Estadísticas y métricas de evaluación

Considerando que es un conjunto de etiquetas para una muestra de datos (no lo confunda con un vector one-hot; es simplemente una colección de todas las etiquetas que pertenecen a esta muestra), el grado en el cual un conjunto de datos es multietiqueta se puede capturar en dos estadísticas: ${\displaystyle Y_{i}}$ ${\displaystyle i^{th}}$

• La cardinalidad de la etiqueta es el número promedio de etiquetas por ejemplo en el conjunto: donde es el número total de muestras de datos; ${\displaystyle {\frac {1}{N}}\sum _{i=1}^{N}|Y_{i}|}$ ${\displaystyle N}$
• La densidad de etiquetas es el número de etiquetas por muestra dividido por el número total de etiquetas, promediado sobre las muestras: donde , el número total de clases disponibles (que es el número máximo de elementos que pueden componer ). ${\displaystyle {\frac {1}{N}}\sum _{i=1}^{N}{\frac {|Y_{i}|}{|L|}}}$ ${\displaystyle L=\bigcup _{i=1}^{N}Y_{i}}$ ${\displaystyle Y_{i}}$

Las métricas de evaluación para el desempeño de la clasificación de múltiples etiquetas son inherentemente diferentes de las utilizadas en la clasificación de múltiples clases (o binaria), debido a las diferencias inherentes del problema de clasificación. Si T denota el conjunto real de etiquetas para una muestra dada y P el conjunto de etiquetas predicho, entonces se pueden definir las siguientes métricas para esa muestra:

• Pérdida de Hamming : la fracción de las etiquetas incorrectas con respecto al número total de etiquetas, es decir , donde es el objetivo, es la predicción y es el operador "Exclusivo o" que devuelve cero cuando el objetivo y la predicción son idénticos y uno en caso contrario. Esta es una función de pérdida , por lo que el valor óptimo es cero y su límite superior es uno. ${\displaystyle {\frac {1}{|N|\cdot |L|}}\sum _{i=1}^{|N|}\sum _{j=1}^{|L|}\operatorname {xor} (y_{i,j},z_{i,j})}$ ${\displaystyle y_{i,j}}$ ${\displaystyle z_{i,j}}$ ${\displaystyle \operatorname {xor} (\cdot )}$
• El índice de Jaccard estrechamente relacionado , también llamado Intersección sobre Unión en el entorno de etiquetas múltiples, se define como el número de etiquetas predichas correctamente dividido por la unión de etiquetas predichas y verdaderas, donde y son conjuntos de etiquetas predichas y etiquetas verdaderas respectivamente. ${\displaystyle {\frac {|T\cap P|}{|T\cup P|}}}$ ${\displaystyle P}$ ${\displaystyle T}$
• Precisión, recall y puntuación : la precisión es , el recall es , y es su media armónica . ^[23] ${\displaystyle F_{1}}$ ${\displaystyle {\frac {|T\cap P|}{|P|}}}$ ${\displaystyle {\frac {|T\cap P|}{|T|}}}$ ${\displaystyle F_{1}}$
• Coincidencia exacta (también llamada precisión de subconjunto): es la métrica más estricta, que indica el porcentaje de muestras que tienen todas sus etiquetas clasificadas correctamente.

La validación cruzada en entornos de múltiples etiquetas se complica por el hecho de que la forma ordinaria (binaria/multiclase) de muestreo estratificado no funcionará; se han sugerido formas alternativas de muestreo estratificado aproximado. ^[24]

Implementaciones y conjuntos de datos

Las implementaciones Java de algoritmos de etiquetas múltiples están disponibles en los paquetes de software Mulan y Meka, ambos basados ​​en Weka .

El paquete Python scikit-learn implementa algunos algoritmos y métricas de etiquetas múltiples.

El paquete de Python scikit-multilearn se ocupa específicamente de la clasificación de múltiples etiquetas. Proporciona la implementación de múltiples etiquetas de varias técnicas conocidas, incluidas SVM, kNN y muchas más. El paquete está construido sobre el ecosistema scikit-learn .

El método de relevancia binaria, las cadenas de clasificadores y otros algoritmos de múltiples etiquetas con muchos aprendices base diferentes se implementan en el paquete R mlr ^[25].

Una lista de conjuntos de datos de múltiples etiquetas comúnmente utilizados está disponible en el sitio web de Mulan.

Véase también

• Clasificación multiclase
• Aprendizaje de múltiples instancias
• Predicción estructurada
• Duración de la correlación

Referencias

1. Jesse Read, Bernhard Pfahringer, Geoff Holmes, Eibe Frank. Cadenas clasificadoras para clasificación de múltiples etiquetas. Revista de aprendizaje automático. Springer. Vol. 85(3), (2011).
2. Heider, D; Senge, R; Cheng, W; Hüllermeier, E (2013). "Clasificación multietiqueta para explotar la información de resistencia cruzada en la predicción de la resistencia a fármacos del VIH-1". Bioinformática . 29 (16): 1946–52. doi : 10.1093/bioinformatics/btt331 . PMID  23793752.
3. Riemenschneider, M; Senge, R; Neumann, U; Hüllermeier, E; Heider, D (2016). "Explotación de la información de resistencia cruzada de la proteasa del VIH-1 y la transcriptasa inversa para una mejor predicción de la resistencia a los fármacos mediante la clasificación de múltiples etiquetas". BioData Mining . 9 : 10. doi : 10.1186/s13040-016-0089-1 . PMC 4772363 . PMID  26933450. 
4. Soufan, Othman; Ba-Alawi, Wail; Afeef, Moataz; Essack, Magbubah; Kalnis, Panos; Bajic, Vladimir B. (10 de noviembre de 2016). "DRABAL: un nuevo método para extraer grandes ensayos de cribado de alto rendimiento utilizando aprendizaje activo bayesiano". Journal of Cheminformatics . 8 : 64. doi : 10.1186/s13321-016-0177-8 . ISSN  1758-2946. PMC 5105261 . PMID  27895719. 
5. Spolaôr, Newton; Cherman, Everton Alvares; Monard, Maria Carolina; Lee, Huei Diana (marzo de 2013). "Una comparación de métodos de selección de características de múltiples etiquetas utilizando el enfoque de transformación de problemas". Notas electrónicas en informática teórica . 292 : 135–151. doi : 10.1016/j.entcs.2013.02.010 . ISSN  1571-0661.
6. "Umbral de discriminación: documentación de yellowbrick 0.9". www.scikit-yb.org . Consultado el 29 de noviembre de 2018 .
7. Tsoumakas, Grigorios; Vlahavas, Ioannis (2007). Conjuntos aleatorios de k-etiquetas: un método de conjunto para la clasificación de múltiples etiquetas (PDF) . ECML. Archivado desde el original (PDF) el 29 de julio de 2014. Consultado el 26 de julio de 2014 .
8. Zhang, ML; Zhou, ZH (2007). "ML-KNN: Un enfoque de aprendizaje perezoso para el aprendizaje de múltiples etiquetas". Reconocimiento de patrones . 40 (7): 2038–2048. Bibcode :2007PatRe..40.2038Z. CiteSeerX 10.1.1.538.9597 . doi :10.1016/j.patcog.2006.12.019. S2CID  14886376. 
9. Madjarov, Gjorgji; Kočev, Dragi; Gjorgjevikj, Dejan; Džeroski, Sašo (2012). "Una extensa comparación experimental de métodos para el aprendizaje de etiquetas múltiples". Reconocimiento de patrones . 45 (9): 3084–3104. Código Bib : 2012PatRe..45.3084M. doi :10.1016/j.patcog.2012.03.004. S2CID  14064264.
10. Chen, Yen-Liang; Hsu, Chang-Ling; Chou, Shih-chieh (2003). "Construcción de un árbol de decisión multivalorado y multietiquetado". Expert Systems with Applications . 25 (2): 199–209. doi :10.1016/S0957-4174(03)00047-2.
11. Chou, Shihchieh; Hsu, Chang-Ling (1 de mayo de 2005). "MMDT: un clasificador de árbol de decisión multivalorado y multietiquetado para minería de datos". Expert Systems with Applications . 28 (4): 799–812. doi :10.1016/j.eswa.2004.12.035.
12. Li, Hong; Guo, Yue-jian; Wu, Min; Li, Ping; Xiang, Yao (1 de diciembre de 2010). "Combine la descomposición de atributos multivalorados con el aprendizaje de etiquetas múltiples". Expert Systems with Applications . 37 (12): 8721–8728. doi :10.1016/j.eswa.2010.06.044.
13. Zhang, ML; Zhou, ZH (2006). Redes neuronales de múltiples etiquetas con aplicaciones a la genómica funcional y la categorización de textos (PDF) . IEEE Transactions on Knowledge and Data Engineering. Vol. 18. págs. 1338–1351.
14. Aggarwal, Charu C., ed. (2007). Flujos de datos . Avances en sistemas de bases de datos. Vol. 31. doi :10.1007/978-0-387-47534-9. ISBN 978-0-387-28759-1.
15. Oza, Nikunj (2005). "Embalaje y refuerzo en línea". Conferencia internacional IEEE sobre sistemas, hombre y cibernética . hdl : 2060/20050239012 .
16. Read, Jesse; Pfahringer, Bernhard; Holmes, Geoff (15 de diciembre de 2008). "Clasificación de etiquetas múltiples utilizando conjuntos de conjuntos podados". Octava conferencia internacional IEEE sobre minería de datos de 2008. IEEE Computer Society. págs. 995–1000. doi :10.1109/ICDM.2008.74. hdl :10289/8077. ISBN. 9780769535029.S2CID 16059274  .
17. Osojnik, Aljaź; Panov, PanăźE; DźEroski, Sašo (1 de junio de 2017). "Clasificación de etiquetas múltiples mediante regresión de objetivos múltiples en flujos de datos". Aprendizaje automático . 106 (6): 745–770. doi : 10.1007/s10994-016-5613-5 . ISSN  0885-6125.
18. Sousa, Ricardo; Gama, João (24 de enero de 2018). "Clasificación de múltiples etiquetas a partir de flujos de datos de alta velocidad con reglas de modelos adaptativos y reglas aleatorias". Progreso en Inteligencia Artificial . 7 (3): 177–187. doi :10.1007/s13748-018-0142-z. ISSN  2192-6352. S2CID  32376722.
19. Read, Jesse; Bifet, Albert; Holmes, Geoff; Pfahringer, Bernhard (21 de febrero de 2012). "Clasificación multietiqueta escalable y eficiente para flujos de datos en evolución". Aprendizaje automático . 88 (1–2): 243–272. doi : 10.1007/s10994-012-5279-6 . ISSN  0885-6125.
20. Bifet, Albert; Gavaldà, Ricard (26 de abril de 2007), "Aprendizaje de datos que cambian en el tiempo con ventanas adaptativas", Actas de la Conferencia internacional SIAM de 2007 sobre minería de datos , Society for Industrial and Applied Mathematics, págs. 443–448, CiteSeerX 10.1.1.215.8387 , doi :10.1137/1.9781611972771.42, ISBN  9780898716306, Número de identificación del sujeto  2279539
21. Büyükçakir, Alican; Bonab, Hamed; Can, Fazli (17 de octubre de 2018). "Un nuevo conjunto apilado en línea para la clasificación de flujos de etiquetas múltiples". Actas de la 27.ª Conferencia internacional de la ACM sobre gestión de la información y el conocimiento . ACM. págs. 1063–1072. arXiv : 1809.09994 . doi :10.1145/3269206.3271774. ISBN 9781450360142.S2CID 52843253  .
22. Xioufis, Eleftherios Spyromitros; Spiliopoulou, Myra; Tsoumakas, Grigorios; Vlahavas, Ioannis (16 de julio de 2011). Cómo abordar la deriva de conceptos y el desequilibrio de clases en la clasificación de flujos de etiquetas múltiples. Prensa AAAI. págs. 1583-1588. doi :10.5591/978-1-57735-516-8/IJCAI11-266. ISBN 9781577355144.
23. Godbole, Shantanu; Sarawagi, Sunita (2004). Métodos discriminativos para la clasificación con múltiples etiquetas (PDF) . Avances en el descubrimiento de conocimientos y la minería de datos. pp. 22–30.
24. Sechidis, Konstantinos; Tsoumakas, Grigorios; Vlahavas, Ioannis (2011). Sobre la estratificación de datos de etiquetas múltiples (PDF) . ECML PKDD . págs. 145-158.
25. Philipp Probst, Quay Au, Giuseppe Casalicchio, Clemens Stachl, Bernd Bischl. Clasificación multietiqueta con el paquete R mlr. The R Journal (2017) 9:1, páginas 352-369.

Lectura adicional

• Madjarov, Gjorgji; Kočev, Dragi; Gjorgjevikj, Dejan; Džeroski, Sašo (2012). "Una extensa comparación experimental de métodos para el aprendizaje de etiquetas múltiples". Reconocimiento de patrones . 45 (9): 3084–3104. Código Bib : 2012PatRe..45.3084M. doi :10.1016/j.patcog.2012.03.004. S2CID  14064264.