Classificação multi-rótulo

Da Wikipédia, a enciclopédia livre

No aprendizado de máquina , classificação multi-rótulo ou classificação multi-saída é uma variante do problema de classificação em que vários rótulos não exclusivos podem ser atribuídos a cada instância. A classificação multi-rótulo é uma generalização da classificação multiclasse , que é o problema de rótulo único de categorizar instâncias precisamente em uma das várias (mais de duas) classes. No problema de rótulos múltiplos, os rótulos não são exclusivos e não há restrição sobre quantas classes a instância pode ser atribuída.

Formalmente, a classificação multi-rótulo é o problema de encontrar um modelo que mapeie entradas x para vetores binários y ; ou seja, atribui um valor de 0 ou 1 para cada elemento (rótulo) em y .

Métodos de transformação de problemas

Existem vários métodos de transformação de problemas para classificação multi-rótulo e podem ser divididos em:

  • Transformação em problemas de classificação binária : a abordagem de linha de base, chamada de método de relevância binária , [1] equivale a treinar independentemente um classificador binário para cada rótulo. Dada uma amostra não vista, o modelo combinado então prevê todos os rótulos para esta amostra para os quais os respectivos classificadores prevêem um resultado positivo. Embora esse método de dividir a tarefa em várias tarefas binárias possa se assemelhar superficialmente aos métodos um contra todos (OvA) e um contra descanso (OvR) para classificação multiclasse, ele é essencialmente diferente de ambos, porque um único classificador sob relevância binária lida com um único rótulo, sem qualquer consideração a outros rótulos. Uma cadeia classificadoraé um método alternativo para transformar um problema de classificação multirrótulo em vários problemas de classificação binária. Difere da relevância binária porque os rótulos são preditos sequencialmente e a saída de todos os classificadores anteriores (isto é, positiva ou negativa para um rótulo específico) é inserida como recursos para os classificadores subsequentes. [1] As cadeias classificadoras foram aplicadas, por exemplo, na previsão de resistência a medicamentos para o HIV . [2] [3] A rede bayesiana também foi aplicada para classificar classificadores de maneira otimizada em cadeias de classificadores . [4]
  • Transformação em problema de classificação multiclasse : A transformação de conjunto de rótulos (LP) cria um classificador binário para cada combinação de rótulos presente no conjunto de treinamento. Por exemplo, se possíveis rótulos para um exemplo forem A, B e C, a representação do conjunto de potência do rótulo desse problema é um problema de classificação multiclasse com as classes [0 0 0], [1 0 0], [0 1 0 ], [0 0 1], [1 1 0], [1 0 1], [0 1 1]. [1 1 1] onde, por exemplo, [1 0 1] denota um exemplo em que os rótulos A e C estão presentes e o rótulo B está ausente. [5]
  • Métodos de conjunto : um conjunto de classificadores de várias classes pode ser usado para criar um classificador de conjunto de vários rótulos. Para um determinado exemplo, cada classificador gera uma única classe (correspondente a um único rótulo no problema multi-rótulo). Essas previsões são então combinadas por um método de conjunto, geralmente um esquema de votação em que cada classe que recebe uma porcentagem necessária de votos de classificadores individuais (geralmente referidos como limite de discriminação [6] ) é prevista como um rótulo presente no rótulo múltiplo saída. No entanto, existem métodos de ensemble mais complexos, como máquinas de comitê . Outra variação é o aleatório k- algoritmo de conjuntos de rótulos (RAKEL), que usa vários classificadores LP, cada um treinado em um subconjunto aleatório dos rótulos reais; a predição do rótulo é então realizada por um esquema de votação. [7] Um conjunto de classificadores multi-rótulo pode ser usado de maneira semelhante para criar um classificador de conjunto multi-rótulo. Nesse caso, cada classificador vota uma vez para cada rótulo que prevê, em vez de um único rótulo.

Algoritmos adaptados

Alguns algoritmos/modelos de classificação foram adaptados para a tarefa multi-rótulo, sem exigir transformações do problema. Exemplos destes, inclusive para dados de vários rótulos.

  • k-vizinhos mais próximos : o algoritmo ML-kNN estende o classificador k-NN para dados multirótulos. [8]
  • árvores de decisão : "Clare" é um algoritmo C4.5 adaptado para classificação multi-rótulo; a modificação envolve os cálculos de entropia. [9] MMC, MMDT e MMDT refinada SSC podem classificar dados com vários rótulos com base em atributos de vários valores sem transformar os atributos em valores únicos. Eles também são chamados de métodos de classificação de árvore de decisão com vários valores e vários rótulos. [10] [11] [12]
  • métodos de kernel para saída vetorial
  • redes neurais : BP-MLL é uma adaptação do popular algoritmo de retropropagação para aprendizado multi-rótulo. [13]

Paradigmas de aprendizagem

Com base em paradigmas de aprendizado, as técnicas de classificação multi-rótulo existentes podem ser classificadas em aprendizado em lote e aprendizado de máquina online . Os algoritmos de aprendizado em lote exigem que todas as amostras de dados estejam disponíveis antecipadamente. Ele treina o modelo usando todos os dados de treinamento e, em seguida, prevê a amostra de teste usando o relacionamento encontrado. Os algoritmos de aprendizado online, por outro lado, constroem seus modelos de forma incremental em iterações sequenciais. Na iteração t, um algoritmo online recebe uma amostra, x t e prediz seu(s) rótulo(s) ŷ t usando o modelo atual; o algoritmo então recebe y t , o(s) rótulo(s) verdadeiro(s) de x t e atualiza seu modelo com base no par amostra-rótulo: (x t , yt ).

Classificação de fluxo de vários rótulos

Os fluxos de dados são possivelmente sequências infinitas de dados que crescem contínua e rapidamente com o tempo. [14] Classificação de fluxo multi-rótulo (MLSC) é a versão da tarefa de classificação multi-rótulo que ocorre em fluxos de dados. Às vezes, também é chamada de classificação multi-rótulo online. As dificuldades da classificação multi-rótulo (número exponencial de conjuntos de rótulos possíveis, captura de dependências entre rótulos) são combinadas com dificuldades de fluxos de dados (restrições de tempo e memória, endereçamento de fluxo infinito com meios finitos, desvios de conceito ) .

Muitos métodos MLSC recorrem a métodos ensemble para aumentar seu desempenho preditivo e lidar com desvios de conceito. Abaixo estão os métodos de ensemble mais utilizados na literatura:

  • Métodos baseados em Bagging Online (OzaBagging [15] ) : Observando a probabilidade de ter K muitos de um certo ponto de dados em uma amostra bootstrap é aproximadamente Poisson(1) para grandes conjuntos de dados, cada instância de dados de entrada em um fluxo de dados pode ser ponderada proporcionalmente para a distribuição de Poisson(1) para imitar o bootstrap em um ambiente online. Isso é chamado de Ensacamento Online (OzaBagging). Muitos métodos multi-rótulo que usam Online Bagging são propostos na literatura, cada um dos quais utiliza diferentes métodos de transformação de problemas. EBR, [1] ECC, [1] EPS, [16] E B RT, [17] E B MT, [17] ML-Random Rules [18]são exemplos de tais métodos.
  • Métodos baseados em ADWIN Bagging [19] : Métodos Online Bagging para MLSC às vezes são combinados com mecanismos explícitos de detecção de desvio de conceito, como ADWIN [20] (Janela Adaptativa). O ADWIN mantém uma janela de tamanho variável para detectar mudanças na distribuição dos dados e melhora o conjunto redefinindo os componentes que funcionam mal quando há um desvio nos dados recebidos. Geralmente, a letra 'a' é usada como subscrito no nome de tais conjuntos para indicar o uso do detector de alterações ADWIN. E a BR, [19] E a CC, [19] E a HT PS [19] são exemplos de tais conjuntos de rótulos múltiplos.
  • Métodos baseados em GOOWE-ML [21] : Interpretando as pontuações de relevância de cada componente do conjunto como vetores no espaço de rótulos e resolvendo um problema de mínimos quadrados no final de cada lote, Conjunto ponderado on-line geometricamente ideal para vários rótulos A classificação (GOOWE-ML) é proposta. O ensemble tenta minimizar a distância entre a predição ponderada de seus componentes e o vetor de verdade para cada instância em um lote. Ao contrário do Online Bagging e do ADWIN Bagging, o GOOWE-ML utiliza um esquema de votação ponderada em que os componentes de melhor desempenho do conjunto recebem mais peso. O conjunto GOOWE-ML cresce com o tempo e o componente de menor peso é substituído por um novo componente quando está cheio no final de um lote. GOBR, [21]GOCC, [21] GOPS, [21] GORT [21] são os conjuntos multirótulos baseados em GOOWE-ML.
  • Janelas Múltiplas [22]  : Aqui, os modelos BR que usam uma janela deslizante são substituídos por duas janelas para cada etiqueta, uma para exemplos relevantes e outra para exemplos não relevantes. As instâncias são superamostradas ou subamostradas de acordo com um fator de carga que é mantido entre essas duas janelas. Isso permite que desvios de conceito independentes para cada rótulo sejam detectados e que o desequilíbrio de classe (distorção nos exemplos relevantes e não relevantes) seja tratado.

Estatísticas e métricas de avaliação

Considerandoser um conjunto de rótulos paraamostra de dados (não confunda com um vetor one-hot; é simplesmente uma coleção de todos os rótulos que pertencem a esta amostra), até que ponto um conjunto de dados é multi-rótulo pode ser capturado em duas estatísticas:

  • A cardinalidade do rótulo é o número médio de rótulos por exemplo no conjunto:ondeé o número total de amostras de dados;
  • A densidade do rótulo é o número de rótulos por amostra dividido pelo número total de rótulos, calculado em média sobre as amostras:onde, o número total de classes disponíveis (que é o número máximo de elementos que podem compor).

As métricas de avaliação para o desempenho da classificação multirrótulo são inerentemente diferentes daquelas usadas na classificação multiclasse (ou binária), devido às diferenças inerentes ao problema de classificação. Se T denota o verdadeiro conjunto de rótulos para uma determinada amostra e P o conjunto de rótulos previsto, as seguintes métricas podem ser definidas nessa amostra:

  • Perda de Hamming : a fração dos rótulos errados para o número total de rótulos, ou seja,, ondeé o alvo,é a previsão, eé o operador "Exclusivo ou" que retorna zero quando o destino e a previsão são idênticos e um caso contrário. Esta é uma função de perda , então o valor ideal é zero e seu limite superior é um.
  • O índice Jaccard intimamente relacionado , também chamado de Interseção sobre União na configuração de vários rótulos, é definido como o número de rótulos previstos corretamente dividido pela união de rótulos previstos e verdadeiros,, ondeesão conjuntos de rótulos previstos e rótulos verdadeiros, respectivamente.
  • Precisão, recall epontuação : a precisão é, lembre-se, eé sua média harmônica . [23]
  • Correspondência exata (também chamada de precisão do subconjunto): é a métrica mais rigorosa, indicando a porcentagem de amostras que têm todos os seus rótulos classificados corretamente.

A validação cruzada em configurações multi-rótulo é complicada pelo fato de que a forma comum (binária/multiclasse) de amostragem estratificada não funcionará; foram sugeridas formas alternativas de amostragem estratificada aproximada. [24]

Implementações e conjuntos de dados

As implementações Java de algoritmos multi-rótulo estão disponíveis nos pacotes de software Mulan e Meka , ambos baseados em Weka .

O pacote Python scikit-learn implementa alguns algoritmos e métricas multi-rótulos .

O pacote Python scikit-multilearn atende especificamente à classificação multi-rótulo. Ele fornece implementação multi-rótulo de várias técnicas conhecidas, incluindo SVM, kNN e muito mais . O pacote é construído sobre o ecossistema scikit-learn .

O método de relevância binária, cadeias de classificadores e outros algoritmos multirrótulo com vários aprendizes de base diferentes são implementados no pacote R mlr [25]

Uma lista de conjuntos de dados de vários rótulos comumente usados ​​está disponível no site da Mulan .

Veja também

Referências

  1. ^ a b c d Jesse Read, Bernhard Pfahringer, Geoff Holmes, Eibe Frank. Cadeias classificadoras para classificação multirótulo . Jornal de aprendizado de máquina. Springer. Vol. 85(3), (2011).
  2. ^ Heider, D; Senge, R; Cheng, W; Hüllermeier, E (2013). "Classificação multilabel para explorar informações de resistência cruzada na previsão de resistência a medicamentos para HIV-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). "Explorando as informações de resistência cruzada da protease do HIV-1 e da transcriptase reversa para melhorar a previsão de resistência a medicamentos por meio da classificação multimarca" . Mineração de Biodados . 9 : 10. doi : 10.1186/s13040-016-0089-1 . PMC 4772363 . PMID 26933450 .  
  4. ^ Soufan, Othman; Ba-Alawi, Lamento; Afeef, Moataz; Essack, Magbubah; Kalnis, Panos; Bajic, Vladimir B. (2016-11-10). "DRABAL: novo método para extrair grandes ensaios de triagem de alto rendimento usando aprendizado ativo 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 (março de 2013). "Uma comparação de métodos de seleção de recursos de vários rótulos usando a abordagem de transformação do problema" . Notas Eletrônicas em Ciência da Computação Teórica . 292 : 135–151. doi : 10.1016/j.entcs.2013.02.010 . ISSN 1571-0661 . 
  6. ^ "Limite de discriminação — documentação do Yellowbrick 0.9" . www.scikit-yb.org . Recuperado 2018-11-29 .
  7. ^ Tsoumakas, Grigorios; Vlahavas, Ioannis (2007). Random k -labelsets: Um método de conjunto para classificação multilabel (PDF) . ECML. Arquivado do original (PDF) em 29/07/2014 . Recuperado 2014-07-26 .
  8. ^ Zhang, ML; Zhou, ZH (2007). "ML-KNN: Uma abordagem de aprendizagem preguiçosa para aprendizagem multi-rótulo". Reconhecimento de padrões . 40 (7): 2038–2048. CiteSeerX 10.1.1.538.9597 . doi : 10.1016/j.patcog.2006.12.019 . 
  9. ^ Madjarov, Gjorgji; Kocev, Dragi; Gjorgjevikj, Dejan; Džeroski, Sašo (2012). "Uma extensa comparação experimental de métodos para aprendizagem multi-rótulo". Reconhecimento de padrões . 45 (9): 3084–3104. doi : 10.1016/j.patcog.2012.03.004 .
  10. ^ Chen, Yen-Liang; Hsu, Chang-Ling; Chou, Shih-chieh (2003). "Construindo uma árvore de decisão com vários valores e vários rótulos". Sistemas Especialistas com Aplicações . 25 (2): 199–209. doi : 10.1016/S0957-4174(03)00047-2 .
  11. ^ Chou, Shihchieh; Hsu, Chang-Ling (2005-05-01). "MMDT: um classificador de árvore de decisão com vários valores e rótulos para mineração de dados". Sistemas Especialistas com Aplicações . 28 (4): 799–812. doi : 10.1016/j.eswa.2004.12.035 .
  12. ^ Li, Hong; Guo, Yue-jian; Wu, Min; Li, Ping; Xiang, Yao (2010-12-01). "Combine decomposição de atributos multivalorados com aprendizado multirótulo". Sistemas Especialistas com Aplicações . 37 (12): 8721–8728. doi : 10.1016/j.eswa.2010.06.044 .
  13. ^ Zhang, ML; Zhou, ZH (2006). Redes neurais multi-rótulo com aplicativos para genômica funcional e categorização de texto (PDF) . IEEE Transactions on Knowledge and Data Engineering. Vol. 18. pp. 1338–1351.
  14. ^ Aggarwal, Charu C., ed. (2007). Fluxos de Dados . Avanços em Sistemas de Banco de Dados . Vol. 31. doi : 10.1007/978-0-387-47534-9 . ISBN 978-0-387-28759-1.
  15. ^ Oza, Nikunj (2005). "Bagging e Boosting Online" . Conferência Internacional IEEE sobre Sistemas, Homem e Cibernética . hdl : 2060/20050239012 .
  16. ^ Leia, Jesse; Pfahringer, Bernhard; Holmes, Geoff (2008-12-15). Classificação multirrótulo usando conjuntos de conjuntos podados . Sociedade de Computação IEEE. pp. 995–1000. doi : 10.1109/ICDM.2008.74 . hdl : 10289/8077 . ISBN 9780769535029. S2CID  16059274 .
  17. ^ a b Osojnik, Aljaź; Panov, PanăźE; DźEroski, Sašo (2017-06-01). "Classificação multi-rótulo via regressão multi-alvo em fluxos de dados" . Aprendizado de Máquina . 106 (6): 745–770. doi : 10.1007/s10994-016-5613-5 . ISSN 0885-6125 . 
  18. Sousa, Ricardo; Gama, João (2018-01-24). "Classificação multi-rótulo de fluxos de dados de alta velocidade com regras de modelo adaptável e regras aleatórias". Progresso em Inteligência Artificial . 7 (3): 177–187. doi : 10.1007/s13748-018-0142-z . ISSN 2192-6352 . S2CID 32376722 .  
  19. ^ a b c d Leia, Jesse; Bifet, Albert; Holmes, Geoff; Pfahringer, Bernhard (2012-02-21). "Classificação multi-rótulo escalável e eficiente para fluxos de dados em evolução" . Aprendizado de Máquina . 88 (1–2): 243–272. doi : 10.1007/s10994-012-5279-6 . ISSN 0885-6125 . 
  20. ^ Bifet, Albert; Gavaldà, Ricard (26/04/2007), "Aprendendo com dados que mudam no tempo com janelas adaptativas", Procedimentos da Conferência Internacional SIAM 2007 sobre Mineração de Dados , Sociedade para Matemática Industrial e Aplicada, pp. 443–448, CiteSeerX 10.1. 1.215.8387 , doi : 10.1137/1.9781611972771.42 , ISBN  9780898716306
  21. ^ a b c d e Büyükçakir, Alican; Bonab, Hamed; Can, Fazli (2018-10-17). Um novo conjunto empilhado on-line para classificação de fluxo de vários rótulos . ACM. pp. 1063–1072. arXiv : 1809.09994 . doi : 10.1145/3269206.3271774 . ISBN 9781450360142. S2CID  52843253 .
  22. ^ Xioufis, Eleftherios Spyromitros; Spiliopoulou, Myra; Tsuumakas, Grigorios; Vlahavas, Ioannis (2011-07-16). Lidando com desvio de conceito e desequilíbrio de classe na classificação de fluxo multi-rótulo . Imprensa AAAI. pp. 1583–1588. doi : 10.5591/978-1-57735-516-8/IJCAI11-266 . ISBN 9781577355144.
  23. ^ Godbole, Shantanu; Sarawagi, Sunita (2004). Métodos discriminativos para classificação multi-rótulo (PDF) . Avanços em Descoberta de Conhecimento e Mineração de Dados. pp. 22–30.
  24. ^ Sechidis, Konstantinos; Tsuumakas, Grigorios; Vlahavas, Ioannis (2011). Sobre a estratificação de dados multi-rótulo (PDF) . ECML PKDD . pp. 145–158.
  25. ^ Philipp Probst, Quay Au, Giuseppe Casalicchio, Clemens Stachl, Bernd Bischl. Classificação Multilabel com R Package mlr . The R Journal (2017) 9:1, páginas 352-369.

Leitura adicional

  • Madjarov, Gjorgji; Kocev, Dragi; Gjorgjevikj, Dejan; Džeroski, Sašo (2012). "Uma extensa comparação experimental de métodos para aprendizagem multi-rótulo". Reconhecimento de padrões . 45 (9): 3084–3104. doi : 10.1016/j.patcog.2012.03.004 .