Kvar kjem etos frå?

Nessa abordagem, qualquer algoritmo tradicional de classifica¸c˜ao pode ser utilizado para tratar o problema multirr´otulo. A id´eia ´e transformar o problema original em um conjunto de problemas de classifica¸c˜ao simples-r´otulo. Essa transforma¸c˜ao pode ser base- ada nos r´otulos de classes dos exemplos ou nos pr´oprios exemplos de treinamento.

Transforma¸c˜ao Baseada nos R´otulos das Classes

Nesse tipo de transforma¸c˜ao, s˜ao utilizados L classificadores, sendo L o n´umero de classes que est˜ao envolvidas no problema. Cada classificador ´e ent˜ao associado a uma

classe e treinado para resolver um problema de classifica¸c˜ao bin´aria, na qual ´e considerada a classe a qual ele est´a associado contra todas as outras classes envolvidas. Essa t´ecnica ´e tamb´em chamada de t´ecnica bin´aria ou um-contra-todos ou Binary-Relevance (Tsoumakas e Vlahavas, 2007).

Um exemplo dessa t´ecnica ´e ilustrado na Figura 3.3, na qual ´e considerado o problema multirr´otulo de classifica¸c˜ao de textos cient´ıficos nas classes “Computa¸c˜ao”, “Biologia” e “Medicina”. Como cada classificador ´e associado a uma classe, trˆes classificadores s˜ao treinados. O problema ´e ent˜ao dividido em trˆes problemas de classifica¸c˜ao bin´arios, sendo um para cada classe. O i-´esimo classificador ´e treinado para considerar os exemplos pertencentes `a i-´esima classe como positivos e os outros exemplos como negativos. Assim, cada classificador torna-se especializado na classifica¸c˜ao de uma classe particular. Quando um novo exemplo ´e apresentado, as classes para as quais os classificadores apresentarem uma sa´ıda positiva s˜ao atribu´ıdas a ele.

Figura 3.3: Transforma¸c˜ao Baseada em R´otulos

Um ponto fraco dessa t´ecnica ´e que ela assume que as classes atribu´ıdas a um exemplo s˜ao independentes entre si. Isso nem sempre ´e verdade, e ignorar as poss´ıveis correla¸c˜oes entre as classes pode fazer com que o m´etodo tenha pouca capacidade de generaliza¸c˜ao. Seu processo de transforma¸c˜ao ´e revers´ıvel, ou seja, ´e poss´ıvel recuperar as classes do problema original a partir do novo problema criado.

Nos experimentos desta pesquisa, uma varia¸c˜ao hier´arquica da t´ecnica um-contra-todos foi implementada e utilizada para a tarefa de classifica¸c˜ao hier´arquica multirr´otulo, por meio da utiliza¸c˜ao da abordagem Top-Down. Essa varia¸c˜ao ser´a explicada com detalhes na Se¸c˜ao 5.3.

Transforma¸c˜ao Baseada nos Exemplos

Nesse tipo de transforma¸c˜ao, o conjunto de classes associado a cada exemplo ´e re- definido, de maneira a converter o problema multirr´otulo original em um ou mais pro- blemas simples-r´otulo. Ao contr´ario da t´ecnica anterior, essa t´ecnica n˜ao produz apenas problemas de classifica¸c˜ao bin´aria, podendo produzir tanto problemas bin´arios quanto multiclasse.

Trˆes diferentes estrat´egias s˜ao propostas para esse tipo de transforma¸c˜ao (Carvalho e Freitas, 2009):

3.1 Abordagens para Tratar Problemas Multirr´otulo 33 • Elimina¸c˜ao de exemplos multirr´otulo;

• Cria¸c˜ao de novos r´otulos para os exemplos multirr´otulo existentes; • Convers˜ao de exemplos multirr´otulo em exemplos simples-r´otulo. Elimina¸c˜ao de exemplos multirr´otulo

A estrat´egia mais simples que existe da transforma¸c˜ao baseada em exemplos, mas tam- b´em a mais ineficaz, ´e eliminar do conjunto de dados os exemplos que s˜ao multirr´otulo. A elimina¸c˜ao dos exemplos com mais de uma classe n˜ao resolve o problema multirr´otulo original. Ela apenas muda o problema, tranformando-o em outro mais simples e prova- velmente n˜ao t˜ao relevante quanto o original. A Figura 3.4 ilustra um exemplo dessa estrat´egia. Os exemplos multirr´otulo 1 e 3 s˜ao eliminados do conjunto de dados original para transformar o problema em simples-r´otulo. Os exemplos removidos, por´em, podem representar informa¸c˜oes importantes sobre o dom´ınio do problema, e essas informa¸c˜oes s˜ao perdidas.

Figura 3.4: Elimina¸c˜ao de exemplos com mais de um r´otulo

Um exemplo de perda de informa¸c˜ao causada por essa estrat´egia pode ser dado atra- v´es de um problema de classifica¸c˜ao de prote´ınas. Prote´ınas podem desempenhar mais de uma fun¸c˜ao, e eliminar essas prote´ınas do conjunto de dados reduz a significˆancia do classificador (Carvalho e Freitas,2009), que n˜ao teria como predizer as outras fun¸c˜oes de uma prote´ına. Essa transforma¸c˜ao ´e irrevers´ıvel, pois n˜ao ´e poss´ıvel descobrir no novo problema criado, quais exemplos foram eliminados do problema original. O n´umero de classificadores necess´arios tamb´em n˜ao ´e alterado.

Cria¸c˜ao de novos r´otulos para os exemplos multirr´otulo existentes

Nessa estrat´egia, para cada exemplo, todas as classes atribu´ıdas `aquele exemplo s˜ao combinadas em uma nova e ´unica classe. Com essa combina¸c˜ao, o n´umero de classes envolvidas no problema pode aumentar consideravelmente, e algumas classes podem ter- minar com poucos exemplos. A Figura 3.5 ilustra um exemplo. Pode-se observar que as classes dos exemplos 1 e 3 foram combinadas, dando origem a uma nova classe “Biomedi- cina”. Essa t´ecnica de combina¸c˜ao de r´otulos foi utilizada nos trabalhos de Tsoumakas e Vlahavas(2007) e Boutell et al. (2004), e chamada de Label-Powerset.

Figura 3.5: Cria¸c˜ao de novas classes

Com a cria¸c˜ao de novas classes, as classes do problema original n˜ao s˜ao perdidas. Se forem utilizados classificadores multiclasse no novo problema criado, a quantidade desses classificadores se mant´em a mesma. Se forem utilizados classificadores bin´arios, o n´umero de classificadores necess´arios aumenta, devido ao aumento do n´umero de classes.

Uma das t´ecnicas propostas neste trabalho para a tarefa de classifica¸c˜ao hier´arquica multirr´otulo consiste de uma varia¸c˜ao hier´arquica da t´ecnica Label-Powerset, utilizando a abordagem Top-Down. Essa varia¸c˜ao ser´a explicada com detalhes na Se¸c˜ao 5.4.

Ainda no trabalho de Tsoumakas e Vlahavas (2007), foi criada uma t´ecnica cha- mada RAndom k-LabELsets (RAKEL), baseada na t´ecnica Label-Powerset. Esta t´ec- nica iterativamente constr´oi uma combina¸c˜ao de m classificadores Label-Powerset. Sendo L = {λi} , i = 1..|L| o conjunto de r´otulos do problema, um k-labelset ´e dado por um sub-

conjunto Y ⊆ L, com k = |Y |. O termo Lk _{representa o conjunto de todos os k-labelsets}

de L. A cada itera¸c˜ao, 1..m, um k-labelset Yi ´e selecionado randomicamente de Lk, sem

reposi¸c˜ao. Um classificador Hi ´e ent˜ao treinado para Yi.

Para a classifica¸c˜ao de um novo exemplo x, cada classificador Hi toma uma decis˜ao

bin´aria para cada r´otulo λj do k-labelset Yicorrespondente. Uma decis˜ao m´edia ´e calculada

para cada r´otulo λj em L, e a decis˜ao final ´e positiva para um dado r´otulo se a decis˜ao

m´edia for maior que um dado limiar t.

O prop´osito da t´ecnica RAKEL ´e levar em considera¸c˜ao as correla¸c˜oes entre as classes e, ao mesmo tempo, evitar a desvantagem da t´ecnica Label-Powerset, em que algumas classes podem terminar com poucos exemplos.

Convers˜ao de exemplos multirr´otulo em exemplos simples-r´otulo

Existem duas varia¸c˜oes para essa estrat´egia. Na primeira, todos os exemplos multir- r´otulo s˜ao convertidos para exemplos simples-r´otulo, em um processo chamado de simpli- fica¸c˜ao ou elimina¸c˜ao de r´otulos. Uma segunda varia¸c˜ao, chamada de decomposi¸c˜ao de r´otulos, decomp˜oe todos os exemplos multirr´otulo em um conjunto de exemplos simples- r´otulo.

Na simplifica¸c˜ao de r´otulos, quando um exemplo possui mais de uma classe, uma de suas classes ´e escolhida e as outras s˜ao eliminadas. Essa escolha pode ser feita de maneira determin´ıstica, selecionando, dentre as classes as quais o exemplo pertence, aquela que

3.1 Abordagens para Tratar Problemas Multirr´otulo 35 possui mais chance de ser a classe verdadeira, ou pode ser feita de maneira aleat´oria, selecionando uma classe randomicamente. A Figura3.6 mostra um exemplo.

Figura 3.6: Transforma¸c˜ao por simplifica¸c˜ao de r´otulos ´

E poss´ıvel ver na figura que um processo de simplifica¸c˜ao foi empregado, no qual foram escolhidas as classes “Biologia” e “Medicina” dos exemplos 1 e 3 respectivamente. A escolha de uma classe simplifica o problema, mas tamb´em apresenta desvantagens. Tomando novamente o exemplo de um problema de classifica¸c˜ao de prote´ınas, se uma prote´ına, por exemplo, tem mais de uma fun¸c˜ao, ela seria classificada como tendo apenas uma fun¸c˜ao e, portanto, informa¸c˜ao relevante seria perdida.

Se for adotado um crit´erio determin´ıstico na escolha das classes, ´e poss´ıvel retornar ao problema multirr´otulo original a partir do problema simples-r´otulo criado. Se as classes forem escolhidas de maneira randˆomica, esse retorno n˜ao ´e poss´ıvel. O n´umero de classi- ficadores utilizados no problema multirr´otulo e no simples-r´otulo geralmente ´e o mesmo.

No processo de decomposi¸c˜ao de r´otulos, um problema multirr´otulo com L classes e M exemplos ´e dividido em K conjuntos de problemas simples-r´otulo. O valor de K varia de 1, quando nenhum exemplo possui mais do que uma classe, a (L − 1)M_{, se todos os}

exemplos possuem L − 1 classes. O processo de decomposi¸c˜ao pode ser dividido em dois m´etodos: aditivo e multiplicativo (Carvalho e Freitas,2009).

O m´etodo aditivo ´e ilustrado na Figura 3.7. Nesse m´etodo, para cada exemplo, cada uma das poss´ıveis classes ´e considerada como sendo a classe positiva, em sequˆencia. Para o exemplo de conjunto de dados de textos com r´otulos “Biologia”, “Medicina” e “Compu- ta¸c˜ao”, quando um classificador para a classe “Biologia” for treinado, todos os exemplos multirr´otulo que pertencerem `a classe “Biologia” tornam-se exemplos simples-r´otulo para a classe “Biologia”, e o mesmo acontece para as outras classes. O m´etodo foi proposto por

Shen et al.(2004) e ´e chamado de Cross-Training.

Nesta pesquisa, uma varia¸c˜ao hier´arquica da t´ecnica Cross-Training foi proposta para a tarefa de classifica¸c˜ao hier´arquica multirr´otulo, por meio da abordagem Top-Down. Essa nova varia¸c˜ao ser´a explicada com detalhes na Se¸c˜ao5.5.

O n´umero de classificadores utilizados ´e igual ao n´umero de classes que rotulam pelo menos um exemplo multirr´otulo. Esse m´etodo permite que o problema multirr´otulo origi- nal seja recuperado a partir do problema simples-r´otulo criado. No exemplo da Figura3.7, o n´umero de classificadores utilizados ´e igual a 2, pois as classes “Biologia” e “Medicina” rotulam exemplos multirr´otulo.

Figura 3.7: Processo de decomposi¸c˜ao utilizando m´etodo aditivo

No m´etodo multiplicativo, por outro lado, uma combina¸c˜ao de todos os poss´ıveis problemas simples-r´otulo ´e utilizada. Esse m´etodo ´e similar a um m´etodo chamado um- contra-um (Carvalho e Freitas, 2009), utilizado para dividir um problema multiclasse em um conjunto de problemas bin´arios.

O n´umero de classificadores utilizados no m´etodo multiplicativo ´e igual ao Qli, que

´e o produto do n´umero de classes presentes em cada exemplo do conjunto de dados. A Figura 3.8 ilustra um exemplo, no qual o n´umero de classificadores ´e dado pelo produto 2 × 1 × 2 × 1 × 1 × 1. Nesse produto, cada n´umero corresponde `a quantidade de classes que rotulam cada exemplo do conjunto de dados.

O n´umero de classificadores desse m´etodo cresce exponencialmente com o n´umero de classes de cada exemplo do conjunto de dados. ´E poss´ıvel notar tamb´em que o m´etodo aditivo produz um subconjunto de problemas simples-r´otulo produzidos pelo m´etodo mul- tiplicativo. O m´etodo multiplicativo tamb´em ´e revers´ıvel, permitindo a recupera¸c˜ao do problema multirr´otulo original.

O m´etodo multiplicativo tamb´em minimiza a deficiˆencia de m´etodos que eliminam ou combinam r´otulos e perdem informa¸c˜ao. Por´em, ele n˜ao leva em considera¸c˜ao poss´ıveis rela¸c˜oes entre os r´otulos de classes de um mesmo exemplo.

Esta se¸c˜ao abordou as principais t´ecnicas utilizadas para tratar problemas de classi- fica¸c˜ao multirr´otulo, utilizando a abordagem independente de algoritmo. A tabela 3.1

3.1 Abordagens para Tratar Problemas Multirr´otulo 37

Figura 3.8: Processo de decomposi¸c˜ao utilizando m´etodo multiplicativo

apresenta uma compara¸c˜ao dessas t´ecnicas, em que L representa o n´umero de classes, li

representa o n´umero de classes que rotulam o i-´esimo exemplo e K representa o n´umero de classes do conjunto de dados que rotulam pelo menos um exemplo multirr´otulo. Pode- se notar, pela tabela, que as t´ecnicas diferem principalmente quanto `a reversibilidade, ao n´umero de classificadores utilizados, e ao tamanho do conjunto de dados ap´os sua transforma¸c˜ao.

Tabela 3.1: Compara¸c˜ao das t´ecnicas independentes de algoritmo

T´ecnica de Transforma¸c˜ao Reversibilidade N. Classificadores N. Exemplos

Baseada nos r´otulos SIM L _{Se mant´em}

Elimina¸c˜ao de exemplos N ˜AO Se mant´em Reduz Cria¸c˜ao de r´otulos SIM Se mant´em Se mant´em Simplifica¸c˜ao de r´otulos Depende de crit´erio Se mant´em Se mant´em

Decomp.: m´etodo aditivo SIM K _Aumenta

Decomp.: m´etodo multiplicativo SIM Qli Aumenta