hierarquiaa

Prévia do material em texto

UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE
CENTRO DE CIÊNCIAS EXATAS E DA TERRA
DEPARTAMENTO DE INFORMÁTICA E MATEMÁTICA APLICADA
PROGRAMA DE PÓS-GRADUAÇÃO EM SISTEMAS E COMPUTAÇÃO
Investigando a Combinação de Técnicas de
Aprendizado Semissupervisionado e
Classi�cação Hierárquica Multirrótulo
Araken de Medeiros Santos
Natal - RN
Maio de 2012
Araken de Medeiros Santos
Investigando a Combinação de Técnicas de
Aprendizado Semissupervisionado e
Classi�cação Hierárquica Multirrótulo
Tese de doutorado submetida ao Programa
de Pós-Graduação em Sistemas e Computa-
ção do Departamento de Informática e Mate-
mática Aplicada da Universidade Federal do
Rio Grande do Norte como parte dos requi-
sitos para a obtenção do grau de Doutor em
Ciência da Computação.
Orientador:
Profa. Dra. Anne Magaly de Paula Canuto
Natal - RN
Maio de 2012
 
ii
À minha família, por todo apoio, amor e com-
preensão.
iii
Agradecimentos
A Deus: por estar sempre presente em minha vida, iluminando o meu caminho;
À minha mãe: por dedicar sua vida às realizações pessoais e pro�ssionais de seus �lhos.
Nada em minha vida seria possível sem o seu apoio;
À minha esposa: pela compreensão e apoio nos momentos de ausência;
Ao meu pai e minhas irmãs: meus agradecimentos por tudo que �zeram para a con-
cretização deste sonho. Saibam que vocês estarão sempre em meu coração;
À minha orientadora Anne Magály: obrigado pela paciência, compreensão, colaboração
e amizade;
Aos amigos, porque os são;
En�m, a todos que, mesmo que minimamente, vieram a contribuir para meu êxito.
iv
"A mente que se abre a uma nova idéia, jamais voltará ao seu tamanho original."
Albert Einstein
v
Resumo
A classi�cação de dados é uma tarefa com alta aplicabilidade em uma grande quanti-
dade de domínios. A maioria dos métodos para tratar problemas de classi�cação encontra-
dos na literatura, tratam problemas tradicionais ou unirrótulo. Nos últimos anos vem sendo
identi�cada uma série de tarefas de classi�cação nas quais os exemplos podem ser rotulados
a mais de uma classe simultaneamente (classi�cação multirrótulo). Adicionalmente, tais
classes podem estar hierarquicamente organizadas (classi�cação hierárquica e classi�cação
hierárquica multirrótulo). Por outro lado, tem-se estudado também uma nova categoria de
aprendizado, chamada de aprendizado semissupervisionado, que combina dados rotulados
(aprendizado supervisionado) e dados não-rotulados (aprendizado não-supervisionado), du-
rante a fase de treinamento, reduzindo, assim, a necessidade de uma grande quantidade de
dados rotulados quando somente um pequeno conjunto de exemplos rotulados está disponí-
vel. Desse modo, uma vez que tanto as técnicas de classi�cação multirrótulo e hierárquica
multirrótulo quanto o aprendizado semissupervisionado vem apresentando resultados fa-
voráveis à sua utilização, neste trabalho é proposta e utilizada a aplicação de aprendizado
semissupervisionado em tarefas de classi�cação hierárquica multirrótulo, de modo a se
atender e�cientemente as principais necessidades das duas áreas. Uma análise experimen-
tal dos métodos propostos veri�cou que a utilização do aprendizado semissupervisionado
em métodos de classi�cação hierárquica multirrótulo apresentou resultados satisfatórios,
uma vez que as duas abordagens apresentaram resultados estatisticamente semelhantes
Palavras-chave: classi�cação multirrótulo; classi�cação hierárquica multirrótulo; apren-
dizado semissupervisionado.
vi
Abstract
Data classi�cation is a task with high applicability in a lot of areas. Most methods for
treating classi�cation problems found in the literature dealing with single-label or traditio-
nal problems. In recent years has been identi�ed a series of classi�cation tasks in which the
samples can be labeled at more than one class simultaneously (multi-label classi�cation).
Additionally, these classes can be hierarchically organized (hierarchical classi�cation and
hierarchical multi-label classi�cation). On the other hand, we have also studied a new
category of learning, called semi-supervised learning, combining labeled data (supervised
learning) and non-labeled data (unsupervised learning) during the training phase, thus
reducing the need for a large amount of labeled data when only a small set of labeled sam-
ples is available. Thus, since both the techniques of multi-label and hierarchical multi-label
classi�cation as semi-supervised learning has shown favorable results with its use, this work
is proposed and used to apply semi-supervised learning in hierarchical multi-label classi-
�cation tasks, so e�ciently take advantage of the main advantages of the two areas. An
experimental analysis of the proposed methods found that the use of semi-supervised le-
arning in hierarchical multi-label methods presented satisfactory results, since the two
approaches were statistically similar results
Keywords: multi-label classi�cation; hierarchical multi-label classi�cation, semi-supervised
learning.
vii
Sumário
Lista de Figuras xiv
Lista de Tabelas xviii
Lista de Abreviaturas e Siglas xxi
1 Introdução 1
1.1 Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Principais Contribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Estrutura do Trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Aprendizado de Máquina 8
2.1 Conceitos Básicos de Aprendizado de Máquina . . . . . . . . . . . . . . . . 9
2.2 Tipos de Aprendizado de Máquina . . . . . . . . . . . . . . . . . . . . . . 11
2.2.1 Aprendizado Supervisionado . . . . . . . . . . . . . . . . . . . . . . 11
2.2.2 Aprendizado Não-Supervisionado . . . . . . . . . . . . . . . . . . . 13
2.2.3 Aprendizado Semissupervisionado . . . . . . . . . . . . . . . . . . . 14
2.3 Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3 Classi�cação de Dados 18
Sumário viii
3.1 Classi�cação de Dados Multirrótulo . . . . . . . . . . . . . . . . . . . . . . 20
3.1.1 Transformação do Problema . . . . . . . . . . . . . . . . . . . . . . 23
3.1.1.1 Relevância Binária . . . . . . . . . . . . . . . . . . . . . . 24
3.1.1.2 Label Powerset . . . . . . . . . . . . . . . . . . . . . . . . 24
3.1.1.3 Random K-labelsets . . . . . . . . . . . . . . . . . . . . . 27
3.1.1.4 Técnicas Baseadas em Ranking . . . . . . . . . . . . . . . 28
3.1.2 Adaptação de Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . 29
3.1.2.1 Árvore de Decisão . . . . . . . . . . . . . . . . . . . . . . 30
3.1.2.2 Redes Neurais Arti�ciais . . . . . . . . . . . . . . . . . . . 30
3.1.2.3 Máquinas de Vetores Suporte . . . . . . . . . . . . . . . . 31
3.1.2.4 k Vizinhos Mais Próximos . . . . . . . . . . . . . . . . . . 32
3.1.2.5 Algoritmos de Agrupamento . . . . . . . . . . . . . . . . . 33
3.1.2.6 Métodos Probabilísticos . . . . . . . . . . . . . . . . . . . 34
3.1.2.7 Métodos Associativos . . . . . . . . . . . . . . . . . . . . 34
3.2 Classi�cação de Dados Hierárquico . . . . . . . . . . . . . . . . . . . . . . 35
3.2.1 Abordagens de Classi�cação Para Problemas Hierárquicos . . . . . 39
3.2.1.1 Transformação do Problema Hierárquico em um Problema
de Classi�cação Plana . . . . . . . . . . . . . . . . . . . . 39
3.2.1.2 Predição Hierárquica com Algoritmos de Classi�cação Plana 41
3.2.1.3 Classi�cação Hierárquica Top-Down . . . . . . . . . . . . 42
3.2.1.4 Classi�cação Hierárquica Big-Bang . . . . . . . . . . . . . 44
3.3 Classi�cação de Dados Hierárquica Multirrótulo . . . . . . . . . . . . . . . 45
3.4 Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Sumário ix
4 Trabalhos Relacionados 53
4.1 Classi�cação Hierárquica Multirrótulo . . . . . . . . . . . . . . . . . . . . . 55
4.1.1 Aprendizado Semissupervisionado . . . . . . . . . . . . . . . . . . . 58
4.2 Considerações Finais . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . 59
5 Métodos Propostos 60
5.1 Classi�cação Multirrótulo Semissupervisionada . . . . . . . . . . . . . . . . 61
5.1.1 SSBR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.1.2 SSLP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.1.3 SSRAkEL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
5.1.4 SSRAkELd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.2 Classi�cação Hierárquica Multirrótulo Semissupervisionada . . . . . . . . . 70
5.2.1 HMC-SSBR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5.2.2 HMC-SSLP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.2.3 HMC-SSRAkEL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.2.4 HMC-SSRAkELd . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.3 Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
6 Metodologia dos Experimentos 76
6.1 Bases de Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
6.1.1 Bases de Dados Multirrótulo . . . . . . . . . . . . . . . . . . . . . . 77
6.1.1.1 Emotions . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6.1.1.2 Genbase . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6.1.1.3 Medical . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
Sumário x
6.1.1.4 Scene . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
6.1.1.5 Yeast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
6.1.2 Bases de Dados Hierárquica Multirrótulo . . . . . . . . . . . . . . . 78
6.1.2.1 Cellcycle . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
6.1.2.2 Church . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
6.1.2.3 Derisi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
6.1.2.4 Eisen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
6.1.2.5 Pheno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
6.2 Métodos Utilizados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
6.2.1 Métodos de Classi�cação Multirrótulo . . . . . . . . . . . . . . . . . 81
6.2.2 Métodos de Classi�cação Hierárquica Multirrótulo . . . . . . . . . . 81
6.3 Métricas de Avaliação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6.3.1 Métricas Baseadas em Bipartição . . . . . . . . . . . . . . . . . . . 83
6.3.1.1 Hamming Loss . . . . . . . . . . . . . . . . . . . . . . . . 83
6.3.1.2 Subset Accuracy . . . . . . . . . . . . . . . . . . . . . . . 84
6.3.1.3 Precision . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.3.1.4 Recall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.3.1.5 F-Measure . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.3.1.6 Accuracy . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6.3.2 Métricas Baseadas em Ranking . . . . . . . . . . . . . . . . . . . . 85
6.3.2.1 One-Error . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6.3.2.2 Average Precision . . . . . . . . . . . . . . . . . . . . . . 86
6.3.2.3 Is-Error . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
Sumário xi
6.3.2.4 Error Set Size . . . . . . . . . . . . . . . . . . . . . . . . 86
6.3.2.5 Coverage . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
6.3.2.6 Ranking Loss . . . . . . . . . . . . . . . . . . . . . . . . . 86
6.3.3 Hierarquical Loss . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
6.4 Con�guração dos Experimentos . . . . . . . . . . . . . . . . . . . . . . . . 87
6.5 Testes Estatísticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
7 Resultados Experimentais: Métodos de Classi�cação Multirrótulo 90
7.1 Métodos Multirrótulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
7.1.1 Fator de Con�dência . . . . . . . . . . . . . . . . . . . . . . . . . . 92
7.1.2 Número de Classi�cadores . . . . . . . . . . . . . . . . . . . . . . . 97
7.1.3 Percentual de Rotulados . . . . . . . . . . . . . . . . . . . . . . . . 100
7.1.4 Percentual de Não-Rotulados . . . . . . . . . . . . . . . . . . . . . 104
7.1.5 Análise dos Resultados . . . . . . . . . . . . . . . . . . . . . . . . . 107
7.1.5.1 Métodos baseados no BR . . . . . . . . . . . . . . . . . . 107
7.1.5.2 Métodos baseados no LP . . . . . . . . . . . . . . . . . . . 108
7.1.5.3 Métodos baseados no RAkEL . . . . . . . . . . . . . . . . 112
7.1.5.4 Métodos baseados no RAkELd . . . . . . . . . . . . . . . 114
7.1.5.5 Abordagem Supervisionada versus Abordagem Semissuper-
visionada . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
7.2 Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
8 Resultados Experimentais: Métodos de Classi�cação Hierárquica Mul-
tirrótulo 120
8.1 Métodos Hierárquicos Multirrótulo: Primeiro Nível da Hierarquia . . . . . 121
Sumário xii
8.1.1 Fator de Con�dencia . . . . . . . . . . . . . . . . . . . . . . . . . . 122
8.1.2 Número de Classi�cadores . . . . . . . . . . . . . . . . . . . . . . . 127
8.1.3 Percentual de Rotulados . . . . . . . . . . . . . . . . . . . . . . . . 127
8.1.4 Percentual de Não-Rotulados . . . . . . . . . . . . . . . . . . . . . 132
8.1.5 Análise dos Resultados . . . . . . . . . . . . . . . . . . . . . . . . . 135
8.1.5.1 Métodos baseados no BR . . . . . . . . . . . . . . . . . . 135
8.1.5.2 Métodos baseados no LP . . . . . . . . . . . . . . . . . . . 136
8.1.5.3 Métodos baseados no RAkEL . . . . . . . . . . . . . . . . 140
8.1.5.4 Métodos baseados no RAkELd . . . . . . . . . . . . . . . 142
8.1.5.5 Abordagem Supervisionada versus Abordagem Semissuper-
visionada . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
8.2 Métodos Hierárquicos Multirrótulo: Segundo Nível da Hierarquia . . . . . 146
8.2.1 Fator de Con�dencia . . . . . . . . . . . . . . . . . . . . . . . . . . 147
8.2.2 Número de Classi�cadores . . . . . . . . . . . . . . . . . . . . . . . 151
8.2.3 Percentual de Rotulados . . . . . . . . . . . . . . . . . . . . . . . . 153
8.2.4 Percentual de Não-Rotulados . . . . . . . . . . . . . . . . . . . . . 157
8.2.5 Análise dos Resultados . . . . . . . . . . . . . . . . . . . . . . . . . 159
8.2.5.1 Métodos baseados no BR . . . . . . . . . . . . . . . . . . 160
8.2.5.2 Métodos baseados no LP . . . . . . . . . . . . . . . . . . . 162
8.2.5.3 Métodos baseados no RAkEL . . . . . . . . . . . . . . . . 164
8.2.5.4 Métodos baseados no RAkELd . . . . . . . . . . . . . . . 166
8.2.5.5 Abordagem Supervisionada versus Abordagem Semissuper-
visionada . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
8.3 Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
Sumário xiii
9 Conclusão 173
9.1 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
Referências 177
xiv
Lista de Figuras
1.1 Caracterização das Aplicações de Aprendizado de Máquina. . . . . . . . . . 2
2.1 Estrutura das tarefas de aprendizado de máquina . . . . . . . . . . . . . . 12
3.1 (a) Problema de classi�cação tradicional ou unirrótulo. (b) Problema de
classi�cação multirótulo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.2 Processo utilizado pelo BR. . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3 Processo utilizado pelo LP. . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.4 Processo utilizado pelo RAkEL. . . . . . . . . . . . . . . . . . . . . . . . . 27
3.5 Processo utilizado pelo RAkELd. . . . . . . . . . . . . . . . . . . . . . . . 28
3.6 Classi�cação Plana (FREITAS; CARVALHO, 2007). . . . . . . . . . . . . . . . 36
3.7 Classi�cação Hierárquica (FREITAS; CARVALHO, 2007). . . . . . . . . . . . 36
3.8 Exemplo de uma hierarquia de classes especi�cada como uma Árvore (FREI-
TAS; CARVALHO, 2007). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.9 Exemplo de uma hierarquia de classes especi�cada como um Grafo AcíclicoDirecionado (DAG) (FREITAS; CARVALHO, 2007). . . . . . . . . . . . . . . 38
3.10 Abordagens para resolução de problemas hierárquicos: (a) Exemplo de uma
hierarquia de classes; (b)Abordagem 1 - Transformação de um Problema
de Classi�cação Hierárquica em um Problema de Classi�cação Plana; (c)
Abordagem 2 - Predição Hierárquica de Classes utilizando Algoritmos de
Classi�cação Plana; (d) Abordagem 3 - Classi�cação Hierárquica Top-Down;
(e) Abordagem 4 - Classi�cação Hierárquica Big-Bang (COSTA, 2008). . . . 40
Lista de Figuras xv
3.11 Hierarquia de classes de um problema hierárquico multirrótulo estruturado
como uma árvore (CERRI; CARVALHO, 2009). . . . . . . . . . . . . . . . . . 47
3.12 Predições gerando uma subárvore (CERRI; CARVALHO, 2009). . . . . . . . . 47
7.1 Métodos de Classi�cação Multirrótulo Semissupervisionada sem fator de
con�dência e com fator de con�dência. . . . . . . . . . . . . . . . . . . . . 94
7.2 Métodos de Classi�cação Multirrótulo Semissupervisionada por fator de con-
�dência: (a) Por base de dados utilizada; (b) Soma de todas as bases de dados. 94
7.3 Ranking dos Métodos de Classi�cação Multirrótulo Semissupervisionada por
fator de con�dência. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
7.4 Métodos de Classi�cação Multirrótulo Semissupervisionada por número de
classi�cadores: (a) Por base de dados utilizada; (b) Soma de todas as bases
de dados. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
7.5 Métodos de Classi�cação Multirrótulo Semissupervisionada por percentual
inicial de exemplos rotulados: (a) Por base de dados utilizada; (b) Soma de
todas as bases de dados. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
7.6 Ranking dos Métodos de Classi�cação Multirrótulo Semissupervisionada por
percentual inicial de exemplos rotulados. . . . . . . . . . . . . . . . . . . . 102
7.7 Métodos de Classi�cação Multirrótulo Semissupervisionada por percentual
de exemplos não-rotulados utilizados a cada iteração: (a) Por base de dados
utilizada; (b) Soma de todas as bases de dados. . . . . . . . . . . . . . . . 106
7.8 Ranking dos Métodos de Classi�cação Multirrótulo Semissupervisionada por
Percentual de Exemplos Não Rotulados Utilizados a cada iteração. . . . . . 106
7.9 Métodos de Classi�cação Multirrótulo Supervisionada e Semissupervisionada.116
8.1 Métodos de Classi�cação Hierárquica Multirrótulo Semissupervisionada sem
fator de con�dência e com fator de con�dência no primeiro nível da hierarquia.124
Lista de Figuras xvi
8.2 Métodos de Classi�cação Hierárquica Multirrótulo Semissupervisionada por
fator de con�dência no primeiro nível da hierarquia: (a) Por base de dados
utilizada; (b) Média de todas as bases de dados. . . . . . . . . . . . . . . . 126
8.3 Ranking dos Métodos de Classi�cação Hierárquica Multirrótulo Semissuper-
visionada por fator de con�dência no primeiro nível da hierarquia. . . . . . 126
8.4 Métodos de Classi�cação Hierárquica Multirrótulo Semissupervisionada por
número de classi�cadores no primeiro nível da hierarquia: (a) Por base de
dados utilizada; (b) Média de todas as bases de dados. . . . . . . . . . . . 129
8.5 Métodos de Classi�cação Hierárquica Multirrótulo Semissupervisionada por
percentual inicial de exemplos rotulados no primeiro nível da hierarquia: (a)
Por base de dados utilizada; (b) Média de todas as bases de dados. . . . . 131
8.6 Ranking dos Métodos de Classi�cação Hierárquica Multirrótulo Semissuper-
visionada por percentual inicial de exemplos rotulados no primeiro nível da
hierarquia. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
8.7 Métodos de Classi�cação Hierárquica Multirrótulo Semissupervisionada por
percentual de exemplos não-rotulados a cada iteração no primeiro nível da
hierarquia: (a) Por base de dados utilizada; (b) Média de todas as bases de
dados. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
8.8 Ranking dos Métodos de Classi�cação Hierárquica Multirrótulo Semissu-
pervisionada por percentual de exemplos não rotulados a cada iteração no
primeiro nível da hierarquia. . . . . . . . . . . . . . . . . . . . . . . . . . . 134
8.9 Métodos de Classi�cação Hierárquica Multirrótulo Supervisionada e Semis-
supervisionada. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
8.10 Métodos de Classi�cação Hierárquica Multirrótulo Semissupervisionada sem
fator de con�dência e com fator de con�dência no segundo nível da hierarquia.147
8.11 Métodos de Classi�cação Hierárquica Multirrótulo Semissupervisionada por
fator de con�dência no segundo nível da hierarquia: (a) Por base de dados
utilizada; (b) Média de todas as bases de dados. . . . . . . . . . . . . . . . 150
Lista de Figuras xvii
8.12 Ranking dos Métodos de Classi�cação Hierárquica Multirrótulo Semissuper-
visionada por fator de con�dência no segundo nível da hierarquia. . . . . . 150
8.13 Métodos de Classi�cação Hierárquica Multirrótulo Semissupervisionada por
número de classi�cadores no segundo nível da hierarquia: (a) Por base de
dados utilizada; (b) Média de todas as bases de dados. . . . . . . . . . . . 153
8.14 Métodos de Classi�cação Hierárquica Multirrótulo Semissupervisionada por
percentual inicial de exemplos rotulados no segundo nível da hierarquia: (a)
Por base de dados utilizada; (b) Média de todas as bases de dados. . . . . 156
8.15 Ranking dos Métodos de Classi�cação Hierárquica Multirrótulo Semissuper-
visionada por percentual inicial de exemplos rotulados no segundo nível da
hierarquia. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
8.16 Métodos de Classi�cação Hierárquica Multirrótulo Semissupervisionados por
percentual de exemplos não-rotulados a cada iteração no segundo nível da
hierarquia. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
8.17 Ranking dos Métodos de Classi�cação Hierárquica Multirrótulo Semissu-
pervisionados por percentual de exemplos não-rotulados a cada iteração no
segundo nível da hierarquia. . . . . . . . . . . . . . . . . . . . . . . . . . . 159
8.18 Métodos de Classi�cação Hierárquica Multirrótulo Supervisionada e Semis-
supervisionada. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
xviii
Lista de Tabelas
2.1 Conjunto de exemplos no formato atributo-valor. . . . . . . . . . . . . . . 12
3.1 Conjunto de dados para o diagnóstico da saúde de um paciente. . . . . . . 19
3.2 Exemplos de um conjunto de dados multirrótulo. . . . . . . . . . . . . . . 21
3.3 Conjuntos de dados obtidos ao utilizar o método de Relevância Binária nos
dados da Tabela 3.1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.4 Conjunto de dados transformado usando o método Label Powerset. . . . . . 26
3.5 Conjunto de dados transformado usando o método RAkEL. . . . . . . . . . 28
3.6 Conjuntos de dados obtidos ao utilizar o método de RPC nos dados da
Tabela 3.2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
6.1 Resumo das Bases de Dados Multirrótulo utilizadas. . . . . . . . . . . . . . 77
6.2 Resumo das Bases de Dados Hierarquica Multirrótulo utilizadas. . . . . . . 79
7.1 Média dos Métodos de Classi�cação Multirrótulo sem fator de con�dência e
com fator de con�dência . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
7.2 Média dos Métodos de Classi�cação Multirrótulo Semissupervisionada por
fator de con�dência. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
7.3 Média dos Métodos de Classi�cação Multirrótulo Semissupervisionada por
número de classi�cadores. . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
7.4 Média dos Métodos de Classi�cação Multirrótulo Semissupervisionada por
percentual inicial de exemplos rotulados. . . . . . . . . . . . . . . . . . . . 101
7.5 Média dos Métodos de Classi�cação Multirrótulo Semissupervisionada por
percentual de exemplos não-rotulados a cada iteração.. . . . . . . . . . . . 105
Lista de Tabelas xix
7.6 Métodos de Classi�cação Multirrótulo baseados no BR. . . . . . . . . . . . 109
7.7 Métodos de Classi�cação Multirrótulo baseados no LP. . . . . . . . . . . . 111
7.8 Métodos de Classi�cação Multirrótulo baseados no RAkEL. . . . . . . . . 113
7.9 Métodos de Classi�cação Multirrótulo baseados no RAkELd. . . . . . . . . 115
7.10 Média dos Métodos de Classi�cação Multirrótulo Supervisionada e Semis-
supervisionada. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
8.1 Média dos Métodos de Classi�cação Hierárquica Multirrótulo Semissuper-
visionada sem fator de con�dência e com fator de con�dência no primeiro
nível da hierarquia. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
8.2 Média dos Métodos de Classi�cação Hierárquica Multirrótulo Semissupervi-
sionada por fator de con�dência no primeiro nível da hierarquia. . . . . . . 125
8.3 Média dos Métodos de Classi�cação Hierárquica Multirrótulo Semissupervi-
sionada por número de classi�cadores no primeiro nível da hierarquia. . . . 128
8.4 Média dos Métodos de Classi�cação Hierárquica Multirrótulo Semissuper-
visionada por percentual inicial de exemplos rotulados no primeiro nível da
hierarquia. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
8.5 Média dos Métodos de Classi�cação Hierárquica Multirrótulo Semissuper-
visionada por percentual de exemplos não-rotulados a cada iteração no pri-
meiro nível da hierarquia. . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
8.6 Métodos de Classi�cação Hierárquica Multirrótulo baseados no BR no pri-
meiro nível da hierarquia. . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
8.7 Métodos de Classi�cação Hierárquica Multirrótulo baseados no LP no pri-
meiro nível da hierarquia. . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
8.8 Métodos de Classi�cação Hierárquica Multirrótulo baseados no RAkEL no
primeiro nível da hierarquia. . . . . . . . . . . . . . . . . . . . . . . . . . . 141
8.9 Métodos de Classi�cação Hierárquica Multirrótulo baseados no RAkELd no
primeiro nível da hierarquia. . . . . . . . . . . . . . . . . . . . . . . . . . . 144
Lista de Tabelas xx
8.10 Média dos Métodos de Classi�cação Hierárquica Multirrótulo Supervisio-
nada e Semissupervisionada no primeiro nível da hierarquia. . . . . . . . . 145
8.11 Média dos Métodos de Classi�cação Hierárquica Multirrótulo Semissuper-
visionada sem fator de con�dência e com fator de con�dência no segundo
nível da hierarquia. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
8.12 Média dos Métodos de Classi�cação Hierárquica Multirrótulo Semissupervi-
sionada por fator de con�dência no segundo nível da hierarquia. . . . . . . 149
8.13 Média dos Métodos de Classi�cação Hierárquica Multirrótulo Semissupervi-
sionada por número de classi�cadores no segundo nível da hierarquia. . . . 152
8.14 Média dos Métodos de Classi�cação Hierárquica Multirrótulo Semissuper-
visionada por percentual inicial de exemplos rotulados no segundo nível da
hierarquia. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
8.15 Média dos Métodos de Classi�cação Hierárquica Multirrótulo Semissuper-
visionada por percentual de exemplos não-rotulados a cada iteração no se-
gundo nível da hierarquia. . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
8.16 Métodos de Classi�cação Hierárquica Multirrótulo baseados no BR no se-
gundo nível da hierarquia. . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
8.17 Métodos de Classi�cação Hierárquica Multirrótulo baseados no LP no se-
gundo nível da hierarquia. . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
8.18 Métodos de Classi�cação Hierárquica Multirrótulo baseados no RAkEL no
segundo nível da hierarquia. . . . . . . . . . . . . . . . . . . . . . . . . . . 165
8.19 Métodos de Classi�cação Hierárquica Multirrótulo baseados no RAkELd no
segundo nível da hierarquia. . . . . . . . . . . . . . . . . . . . . . . . . . . 167
8.20 Média dos Métodos de Classi�cação Hierárquica Multirrótulo Supervisio-
nada e Semissupervisionada no segundo nível da hierarquia. . . . . . . . . 170
xxi
Lista de Abreviaturas e Siglas
AD � Árvore de Decisão
ACO � Ant Colony Optimization
AM � Aprendizado de Máquina
BP-MLL � BackPropagation for MultiLabel Learning
BR � Binary Relevance
CBMLC � Clustering-based MultiLabel Classi�cation
CLR � Calibrated Label Ranking
DAG � Directed Acyclic Graph
DT � Decision Tree
ESSBR � Ensemble of Semi-Supervised Binary Relevance
ESSBRc � Ensemble of Semi-Supervised Binary Relevance with con�dence
ESSLP � Ensemble of Semi-Supervised Label Powerset
ESSLPc � Ensemble of Semi-Supervised Label Powerset with Con�dence
ESSRAkEL � Ensemble of Semi-Supervised Random k-Labelsets
ESSRAkELc � Ensemble of Semi-Supervised Random k-Labelsets with Con�dence
ESSRAkELd � Ensemble of Semi-Supervised Random k disjoint Labelsets
ESSRAkELdc � Ensemble of Semi-Supervised Random k-Labelsets disjoint with Con�dence
GO � Gene Ontology
HMC � Hierarchical Multilabel Classi�cation
Lista de Abreviaturas e Siglas xxii
HMC-BR � Hierarchical Multilabel Classi�cation with Binary Relevance
HMC-ESSBR � Hierarchical Multilabel Classi�cation using Ensemble of Semi-Supervised
Binary Relevance
HMC-ESSBRc � Hierarchical Multilabel Classi�cation using Ensemble of Semi-Supervised
Binary Relevance with Con�dence
HMC-ESSLP � Hierarchical Multilabel Classi�cation using Ensemble of Semi-Supervised
Label Powerset
HMC-ESSLPc � Hierarchical Multilabel Classi�cation using Ensemble of Semi-Supervised
Label Powerset with Con�dence
HMC-ESSRAkEL �Hierarchical Multilabel Classi�cation using Ensemble of Semi-Supervised
Random k-Labelsets
HMC-ESSRAkELc �Hierarchical Multilabel Classi�cation using Ensemble of Semi-Supervised
Random k-Labelsets with Con�dence
HMC-ESSRAkELd �Hierarchical Multilabel Classi�cation using Ensemble of Semi-Supervised
Random k disjoint Labelsets
HMC-ESSRAkELdc �Hierarchical Multilabel Classi�cation using Ensemble of Semi-Supervised
Random k disjoint Labelsets with Con�dence
HMC-LP � Hierarchical Multilabel Classi�cation with Label Powerset
HMC-RAkEL � Hierarchical Multilabel Classi�cation with Random k-Labelsets
HMC-RAkELd � Hierarchical Multilabel Classi�cation with Random k disjoint Labelsets
HMC-SSBR � Hierarchical Multilabel Classi�cation using Semi-Supervised Binary Rele-
vance
HMC-SSBRc � Hierarchical Multilabel Classi�cation using Semi-Supervised Binary Rele-
vance with Con�dence
HMC-SSLP � Hierarchical Multilabel Classi�cation using Semi-Supervised Label Powerset
HMC-SSLPc � Hierarchical Multilabel Classi�cation using Semi-Supervised Label Powerset
Lista de Abreviaturas e Siglas xxiii
with Con�dence
HMC-SSRAkEL � Hierarchical Multilabel Classi�cation using Semi-Supervised Random
k-Labelsets
HMC-SSRAkELc � Hierarchical Multilabel Classi�cation using Semi-Supervised Random
k-Labelsets with Con�dence
HMC-SSRAkELd � Hierarchical Multilabel Classi�cation using Semi-Supervised Random
k disjoint Labelsets
HMC-SSRAkELdc � Hierarchical Multilabel Classi�cation using Semi-Supervised Random
k disjoint Labelsets with Con�dence
HMLC � Hierarchical Multilabel Classi�cation
HSC � Hierarchical Single-label Classi�cation
kNN � k-Nearest Neighbour
LP � Label Powerset
MIML-RBF � Multi-Instance Multi-Label Radial Basis Function
ML-kNN � MultiLabel k Nearest Neighbors
MLP � Multilayer Perceptron
MMAC � Multi-Class Multilabel Associative Classi�cation
MMP � Multiclass Multilabel Perceptron
PNN � Probabilistc Neural Networks
PSO � Particle Swarm Optimization
SSBR � Semi-Supervised Binary Relevance
SSBRc � Semi-Supervised Binary Relevance with Con�dence
SSLP � Semi-Supervised Label Powerset
SSLPc � Semi-Supervised Label Powerset with Con�dence
Lista de Abreviaturas e Siglas xxiv
SSRAkEL � Semi-Supervised Random k-Labelsets
SSRAkELc � Semi-SupervisedRandom k-Labelsets with Con�dence
SSRAkELd � Semi-Supervised Random k disjoint Labelsets
SSRAkELdc � Semi-Supervised Random k-Labelsets disjoint with Con�dence
SVM � Support Vector Machines
RAkEL � RAndom k-LabELsets
RAkELd � RAndom k-LabELsets disjoint
RPC � Ranking by Pairwise Comparison
RBF � Radial Basis Function
SC � Single-label Classi�cation
SOM � Self-Organizing Maps
1
Capítulo 1
Introdução
Aprendizado de Máquina (AM) é uma área dedicada ao estudo e desenvolvimento
de técnicas computacionais que permitam o aperfeiçoamento do desempenho em alguma
tarefa através de experiências acumuladas (MONARD, 2003; MITCHELL, 1997).
Na literatura, há uma grande variedade de algoritmos de AM propostos para a solução
de uma ampla variedade de problemas e aplicações. As aplicações de Aprendizado de
Máquina podem ser agrupadas segundo várias perspectivas. Em uma destas perspectivas,
três pontos principais são tomados como base: grau de supervisão empregado, quantidade
de rótulos de cada instância e quantidade de níveis dos rótulos. A Figura 1.1 ilustra uma
estrutura dos tipos de aplicações de AM segundo estas três caracteríticas principais.
Considerando o grau de supervisão aplicado durante o processo de aprendizado, o
aprendizado de máquina pode ser dividido em duas categorias principais: aprendizado
supervisionado e aprendizado não-supervisionado (MONARD, 2003). A principal diferença
entre o aprendizado supervisionado e o não-supervisionado diz respeito à forma como é
realizado o processo de generalização do conhecimento.
No aprendizado supervisionado, durante o treinamento, os métodos ou algoritmos rece-
bem como entrada exemplos juntamente com a informação de saída desejada, representando
CAPÍTULO 1. INTRODUÇÃO 2
Figura 1.1: Caracterização das Aplicações de Aprendizado de Máquina.
a classe a que aquele exemplo pertence. Por sua vez, no aprendizado não-supervisionado,
os métodos recebem como entrada exemplos sem a informação de saída, ou seja, não se
conhece a priori a classe a qual os exemplos do conjunto de treinamento pertencem.
Recentemente, a comunidade cientí�ca vem estudando uma terceira categoria de apren-
dizado, surgida através da junção do aprendizado supervisionado com o aprendizado não-
supervisionado. A essa nova categoria de aprendizado dá-se o nome de aprendizado se-
missupervisionado (MATSUBARA; MONARD; BATISTA, 2005). O aprendizado semissupervi-
sionado combina dados rotulados e dados não-rotulados, durante a fase de treinamento,
reduzindo assim, a necessidade de uma grande quantidade de dados rotulados quando
somente um pequeno conjunto de exemplos rotulados está disponível. Essa redução na
necessidade de um grande número de dados rotulados é uma das principais vantagens do
aprendizado semissupervisionado.
Muitos dos algoritmos de AM propostos na literatura têm como objetivo a solução de
problemas de classi�cação de dados. A classi�cação de dados é um processo no qual, a partir
de um conjunto de dados brutos, são extraídas informações por meio de categorização.
Desse modo, um processo de classi�cação consiste na atribuição de rótulos aos dados, de
tal forma que esses rótulos con�ram informações aos dados categorizados sob o mesmo
rótulo.
Tradicionalmente, a classi�cação de dados trata do aprendizado de um conjunto de
exemplos em que cada exemplo é associado a somente uma única classe de um conjunto
�nito de classes. Neste trabalho, chamaremos esta tarefa de classi�cação unirrótulo ou clas-
si�cação tradicional. Embora a classi�cação unirrótulo seja bastante utilizada, há vários
CAPÍTULO 1. INTRODUÇÃO 3
domínios nos quais os exemplos podem estar associados a mais de uma classe do conjunto
�nito de classes, tais como: classi�cação de textos (LUO; ZINCIR-HEYWOOD, 2005) e bioin-
formática (ZHANG; ZHOU, 2005). Nesses casos, à tarefa de classi�cação dá-se o nome de
classi�cação multirrótulo.
Além disso, a grande maioria das soluções propostas aos problemas de classi�cação
descritos na literatura envolve um tipo de classi�cação no qual as classes pertencentes ao
conjunto �nito de classes estão todas em um mesmo nível, ou seja, neste tipo de classi�cação
não são considerados relacionamentos hierárquicos entre as classes, supondo assim, inde-
pendência entre as classes envolvidas. Este tipo de classi�cação é chamada de classi�cação
plana.
Outrossim, há também um grande número de problemas de classi�cação mais comple-
xos, nos quais as classes a serem preditas estão dispostas em uma estrutura hierárquica.
Nestes tipos de problemas, uma ou mais classes podem ser divididas em subclasses ou
agrupadas em superclasses. Esses problemas são conhecidos na literatura de aprendizado
de máquina como problemas de classi�cação hierárquica.
Ademais, recentemente, têm-se identi�cado a existência de muitos problemas de clas-
si�cação hierárquica em que duas ou mais classes do conjunto �nito de classes podem ser
atribuídas simultaneamente à mesma instância. Esses problemas nos quais são combina-
das a classi�cação hierárquica e a classi�cação multirrótulo são chamados de problemas de
classi�cação hierárquica multirrótulo.
A maioria dos trabalhos encontrados na literatura aplicam o aprendizado supervisio-
nado em tarefas de classi�cação plana unirrótulo. Além disso, alguns trabalhos se dedicam
ao estudo da aplicação do aprendizado semissupervisionado ou em problemas de classi�ca-
ção hierárquica unirrótulo ou em problemas de classi�cação plana multirrótulo.
Neste contexto, considerando as vantagens do aprendizado semissupervisionado e o
aumento no número de aplicações multirrótulo e hierárquicas multirrótulo, este trabalho
apresenta uma investigação do comportamento obtido pela aplicação de técnicas de apren-
dizado semissupervisionado em tarefas de classi�cação multirrótulo e hierárquica multir-
rótulo, de modo a identi�car suas vantagens e desvantagens.
1.1 Motivação 4
Desse modo, este capítulo está organizado da seguinte maneira: a Seção 1.1 apresenta
as motivações para a investigação realizada neste trabalho; na Seção 1.2 são destacados os
principais objetivos da pesquisa; na Seção 1.3 são apresentadas as principais contribuições
deste trabalho; e na Seção 1.4 é apresentada a estrutura geral deste documento.
1.1 Motivação
Recentemente, com o aumento no número de aplicações multirrótulo e hierárquicas
multirrótulo, vem sendo identi�cada uma grande tendência da comunidade cientí�ca para
a realização de pesquisas envolvendo problemas de classi�cação multirrótulo e hierárquica
multirrótulo. Tal fato se deve, provavelmente, aos resultados favoráveis à utilização. Por
serem áreas relativamente novas, ainda há muito a ser explorado nestas áreas para a rea-
lização de pesquisas, melhoria das técnicas existentes e contribuição com novas propostas
que permitam o avanço da área.
Adicionalmente, o aprendizado semissupervisionado tem emergido como uma aborda-
gem bastante interessante para o aprendizado de máquina, principalmente em problemas
onde a quantidade de exemplos não-rotulados gerados é alta e a quantidade de exemplos
rotulados é muito baixa. Nestes casos, pode-se fazer necessária a utilização de um conjunto
de exemplos de treinamento rotulados maior do que o conjunto disponível, de modo a se
obter um classi�cador com maior precisão. Contudo, incrementar o conjunto de exem-
plos rotulados por meio da atribuição de rótulos a exemplos não-rotulados manualmente
pode ser bastante difícil e custoso, seja pela falta de um especialista do domínio ou por
esse especialista não possuir total conhecimento do domínio. Assim, faz-se necessária a
utilização de um processo automático de atribuição de rótulos para esses novos exemplos.
Neste contexto, em que tanto as técnicas de classi�cação hierárquica multirrótulo quanto o
aprendizado semissupervisionado vêm apresentando resultados favoráveis à sua utilização,
sem que nenhum estudo da aplicação de aprendizado semissupervisionado em problemas
de classi�cação hierárquicamultirrótulo seja realizado, surge a motivação de combiná-las
de modo a se aproveitar e�cientemente as principais vantagens das duas áreas.
1.2 Objetivos 5
1.2 Objetivos
O objetivo principal deste trabalho é o desenvolvimento de novos métodos de classi�ca-
ção multirrótulo e hierárquica multirrótulo através da aplicação de técnicas de aprendizado
semissupervisionado.
Para tal, os seguintes objetivos secundários deverão ser alcançados:
• Elaboração e Implementação de novas técnicas de classi�cação multirrótulo e hie-
rárquica multirrótulo: consiste na proposta e implementação de novas técnicas de
classi�cação multirrótulo e hierárquica multirrótulo aplicando técnicas de aprendi-
zado semissupervisionado, abrindo possibilidade para contribuições originais para o
avanço do estado da arte na área;
• Aplicação dos modelos propostos a diferentes problemas de classi�cação: vários pro-
blemas de classi�cação podem ser investigados utilizando os modelos de classi�cação
supervisionados existentes e os métodos semissupervisionados propostos, de modo a
viabilizar um estudo comparativo entre técnicas existentes e as técnicas propostas;
• Avaliação dos resultados por meio de diferentes medidas especí�cas para classi�cação
multirrótulo e hierárquica multirrótulo: tendo em vista as peculiaridades inerentes a
problemas de classi�cação multirrótulo e hierárquica multirrótulo, medidas de avali-
ação especí�cas devem ser utilizadas para mensurar o desempenho dos classi�cadores
desenvolvidos para tais problemas. Tais medidas de avaliação requerem algumas con-
siderações adicionais, além dos aspectos normalmente considerados na avaliação de
modelos convencionais de classi�cação. Desse modo, um dos objetivos deste projeto
é a avaliação dos modelos de classi�cação multirrótulo e hierárquica multirrótulo por
meio de medidas especí�cas para esse contexto.
Neste contexto, ao �nal deste trabalho espera-se avaliar se a aplicação do aprendizado
semissupervisionado em métodos de classi�cação multirrótulo e hierárquica multirrótulo é
capaz de aproximar os resultados dos métodos nos quais é utilizado o aprendizado super-
visionado.
1.3 Principais Contribuições 6
1.3 Principais Contribuições
Conforme citado anteriormente, tanto a classi�cação multirrótulo e hierárquica multir-
rótulo, quanto o aprendizado semissupervisionado são áreas relativamente, com muito a ser
explorado para a realização de pesquisas, melhoria das técnicas existentes e contribuição
com novas propostas que permitam o avanço das áreas. Desse modo, a principal contribui-
ção deste trabalho é a investigação da aplicação do aprendizado semissupervisionado em
métodos de classi�cação multirrótulo e hierárquico multirrótulo.
Durante a execução desta investigação, os seguintes trabalhos foram publicados e sub-
metidos para publicação:
• SANTOS, Araken de Medeiros; CANUTO, Anne Magaly de Paula; FEITOSA NETO,
Antonino A.. A Comparative Analysis of Classi�cation Methods to Multi-label Tasks
in Di�erent Application Domains. International Journal of Computer Information
Systems and Industrial Management Applications, v. 3, p. 218-227, 2011.
• SANTOS, Araken de Medeiros; XAVIER JÚNIOR, Joao Carlos; CANUTO, Anne
Magaly de Paula. Using Semi-Supervised Learning in Multi-label Classi�cation Pro-
blems. In: International Joint Conference on Neural Networks (IJCNN) (Aceito para
publicação), 2012, Brisbane. IEEE proceedings of IJCNN 2012, 2012.
• SANTOS, Araken de Medeiros; FEITOSA NETO, Antonino A.; CANUTO, Anne
Magaly de Paula. Evaluating classi�cation methods applied to multi-label tasks in
di�erent domains. In: International Conference on Hybrid Intelligent Systems (HIS),
2010, Atlanta. IEEE proceedings of the 10th International Conference on Hybrid
Intelligent Systems (HIS), 2010.
• SANTOS, Araken de Medeiros; CANUTO, Anne Magaly de Paula; SANTANA,
Laura. Analyzing Classi�cation Methods in Multi-label Tasks. In: International Con-
ference on Arti�cial Neural Networks, 2010. Lecture Notes on Computer Science
(LNCS) 6352 - Springer, 2010. v. III. p. 137-142.
1.4 Estrutura do Trabalho 7
1.4 Estrutura do Trabalho
O restante deste trabalho está organizado da seguinte forma:
• No Capítulo 2 são apresentados os principais conceitos associados à área de apren-
dizado de máquina, assim como os diferentes tipos de aprendizado de máquina exis-
tentes;
• O Capítulo 3 apresenta as principais características e algoritmos existentes associados
aos diferentes tipos de problemas de classi�cação de dados;
• O Capítulo 4 trata dos principais trabalhos envolvendo problemas de classi�cação
multirrótulo, hierárquica e hierárquica multirrótulo, bem como as técnicas de apren-
dizado semissupervisionado;
• No Capítulo 5 são propostos alguns algoritmos para a construção de classi�cadores
multirrótulo e hierárquicos multirrótulo através da aplicação de técnicas de aprendi-
zado semissupervisionado;
• O Capítulo 6 trata dos procedimentos utilizados para a execução dos experimentos,
assim como da descrição das bases de dados e medidas de avaliação utilizadas;
• No Capítulo 7 são apresentados os resultados experimentais obtidos pelos métodos
de classi�cação multirrótulo semissupervisionada;
• No Capítulo 8 são apresentados os resultados experimentais obtidos pelos métodos
de classi�cação hierárquica multirrótulo semissupervisionada;
• O Capítulo 9 apresenta as considerações �nais deste trabalho, assim como identi�ca
os possíveis trabalhos futuros.
8
Capítulo 2
Aprendizado de Máquina
Aprendizado de Máquina (AM) é uma área cujo objetivo é o desenvolvimento de téc-
nicas computacionais que tornem viáveis ao computador tomar decisões baseadas em ex-
periências acumuladas, ou seja, tratar da questão da construção de algoritmos capazes de
adquirir conhecimento de forma automática, melhorando seu desempenho na tomada de
decisões por meio de soluções bem-sucedidas de problemas anteriores (MITCHELL, 1997;
MONARD, 2003). Um dos principais focos das pesquisas em aprendizado de máquina é
produzir modelos aumaticamente a partir de dados, como, por exemplo, regras e padrões.
A construção de modelos capazes de adquirir conhecimento de forma automática atra-
vés da experência tem sido, por um longo período, objeto de intensas pesquisas. Na litera-
tura, há uma grande variedade de algoritmos de AM propostos, com diferentes paradigmas
e formas de aprendizado. Contudo, apesar de tais técnicas utilizarem metodologias bem
distintas, em alguns casos, estão fundamentadas no conceito de indução.
A indução é uma forma de raciocício lógico. Tal conceito permite que conclusões gené-
ricas sejam obtidas a partir de um conjunto particular de exemplos. O raciocínio indutivo
origina-se em conceito especí�co e generalizado, ou seja, da parte para o todo (MONARD,
2003). O processo de aquisição de conhecimento baseado em indução é conhecido como
2.1 Conceitos Básicos de Aprendizado de Máquina 9
aprendizado indutivo.
Este capítulo está organizado do seguinte modo: na Seção 2.1, são apresentados os
conceitos básicos associados à área de aprendizado de máquina. Por sua vez, a Seção 2.2
trata das categorias de aprendizado indutivo existentes.
2.1 Conceitos Básicos de Aprendizado de Máquina
Conforme citado anteriormente, na literatura, há uma grande variedade de algoritmos
de aprendizado de máquina, cada um com características que lhes são peculiares. Contudo,
alguns termos podem ser aplicados à grande maioria desses métodos. Dessa forma, nesta
seção são apresentados os principais termos associados à área de aprendizado de máquina.
• Atributo: um atributo descreve uma característica ou aspecto de um exemplo. Nor-
malmente, esses atributos podem ser de dois tipos: discretos ou contínuos. Atributos
discretos, também chamados de atributos nominais ou categóricos, contêm um nú-
mero �nito de valores. Por sua vez, os atributos contínuos podem assumir um número
in�nito de valores. Um importante ponto a ser considerado na escolha dos atributosque serão utilizados para descrever os exemplos, é a sua capacidade preditiva, ou
seja, a capacidade de discriminação entre os exemplos (MONARD, 2003; FACELLI et
al., 2011).
• Classe ou rótulo: uma classe ou rótulo, também chamado de atributo-alvo, descreve
o conceito-meta, ou seja, o conceito que se deseja aprender para tornar viável a
realização de predições a seu respeito.
• Exemplo: um exemplo, também chamado de padrão ou instância, descreve um objeto
de um determinado conceito que se deseja aprender através de um vetor de valores
de características ou atributos (MONARD, 2003). Um exemplo pode conter, além do
vetor de características, um atributo especial, indicando a classe a que este exemplo
pertence.
• Conjunto de exemplos: um conjunto de exemplos, também chamado de conjunto
de dados, é composto por um número de exemplos com seus respectivos valores de
2.1 Conceitos Básicos de Aprendizado de Máquina 10
atributos.
• Conjunto de treinamento: utilizado como entrada pelos algoritmos de aprendizado.
A partir deste conjunto são construídos (induzidos) modelos ou hipóteses. Assim,
devem possuir uma quantidade representativa da população dos dados do domínio.
• Conjunto de teste: utilizado para avaliar o modelo construído. Idealmente, o conjunto
de teste não deve ter exemplos em comum com o conjunto de treinamento.
• Conjunto de validação: utilizado, em alguns casos, para realizar ajustes no mo-
delo construído pelo algoritmo de aprendizado. Os exemplos desse conjunto não
são utilizados diretamente na construção do modelos, mas são utilizados para o seu
ajuste. Dessa maneira, esses exemplos são indiretamente "vistos"durante o processo
de aprendizado, obrigando que os exemplos de validação sejam distintos dos exemplos
de teste.
• Indutor: algoritmo de aprendizado que utiliza um processo indutivo para gerar a
sua hipótese ou modelo. Essa hipótese é utilizada para classi�car uma instância ou
exemplo.
• Classi�cador ou hipótese: dado um conjunto de exemplos de treinamento, um indutor
ou algoritmo de aprendizado gera como saída um classi�cador (ou hipótese) de forma
que, dado um novo padrão, ele possa predizer sua classe com a maior precisão possível
(MONARD, 2003).
• Over�tting (superajustamento): o over�tting ocorre quando, após o treinamento, o
classi�cador gerado é muito especí�co para o conjunto de exemplos de treinamento
utilizado. Assim, a maioria das instâncias que não pertence ao conjunto de exemplos
utilizado durante o processo de aprendizado é classi�cada erroneamente. Desse modo,
pode-se dizer que, durante o treinamento, o classi�cador gerado foi superajustado ao
conjunto de treinamento, incapacitando-o a classi�car ou generalizar corretamente
exemplos diferentes daqueles utilizados na fase de treinamento.
• Under�tting : o under�tting consiste no caso inverso ao over�tting, ou seja, o classi-
�cador gerado ajustou-se muito pouco ao conjunto de treinamento, incapacitando-o
2.2 Tipos de Aprendizado de Máquina 11
a classi�car corretamente tanto os exemplos do conjunto de dados de treinamento,
quanto os exemplos em um conjunto de teste (MONARD, 2003).
• Acurácia: a acurácia de um classi�cador é uma medida de desempenho obtida por
este classi�cador para uma determinada tarefa. Essa medida é calculada de acordo
com a taxa de predições corretas (precisão) ou incorretas (taxa de erro) realizadas por
esse classi�cador para um determinado conjunto de dados. Desse modo, a acurácia
pode ser interpretada como a quantidade de padrões que esse classi�cador acertou
ou errou de acordo com a classe a que este padrão de fato pertence. Essa taxa de
acurácia é, em geral, estimada utilizando um conjunto diferente do conjunto utilizado
no processo de aprendizado, chamado de conjunto de teste.
2.2 Tipos de Aprendizado de Máquina
O aprendizado indutivo pode ser dividido em duas categorias principais: aprendizado
supervisionado e aprendizado não-supervisionado (MONARD, 2003). A diferença entre o
aprendizado supervisionado e o não-supervisionado diz respeito à forma como é realizado
o processo de generalização do conhecimento. Recentemente, a comunidade cientí�ca vem
estudando uma terceira categoria de aprendizado, surgida através da junção do apren-
dizado supervisionado com o aprendizado não-supervisionado. A essa nova categoria de
aprendizado dá-se o nome de aprendizado semissupervisionado (MATSUBARA; MONARD;
BATISTA, 2005). A Figura 2.1 ilustra a estrutura das tarefas do aprendizado.
Nas seções seguintes, serão apresentadas as principais características de cada uma das
três categorias de aprendizado.
2.2.1 Aprendizado Supervisionado
No aprendizado supervisionado, cada exemplo do conjunto de treinamento é rotulado
como pertencente a alguma classe. O rótulo atribuído a um exemplo, também chamado
de saída desejada, atributo-alvo ou dependente, é fornecido juntamente com seus atributos
de entrada, também chamados de atributos independentes. Desse modo, durante o trei-
namento, ao apresentar um exemplo ao algoritmo de aprendizado, além dos atributos que
2.2 Tipos de Aprendizado de Máquina 12
Figura 2.1: Estrutura das tarefas de aprendizado de máquina
Tabela 2.1: Conjunto de exemplos no formato atributo-valor.
X1 X2 · · · XM Y
E1 x11 x12 · · · x1M y1
E2 x21 x22 · · · x2M y2
...
...
...
...
...
EN xN1 xN2 · · · xNM yN
representam as características do domínio, um atributo especial também é apresentado,
representando a classe à qual este exemplo pertence. Para rótulos de classe discretos (por
exemplo, classe A, classe B, etc.), o problema é denominado de classi�cação. Por outro
lado, para rótulos contínuos, o problema é chamado de regressão.
A Tabela 2.1 apresenta o formato geral de uma tabela atributo-valor com N exemplos
Ei com i = 1, ..., N , na forma {(~x1, y1), ..., (~xN , yN)} para alguma função desconhecida
y = f(x). Os ~xi são tipicamente vetores da forma 〈xi1, xi2, ..., xiM〉 com valores discretos
ou contínuos. Assim, xij refere-se ao valor do atributo j, denominado Xj, do exemplo Ei,
como mostra a Tabela 2.1. Os valores yi referem-se ao valor do atributo Y , frequentemente
denominado classe ou rótulo.
Desse modo, no aprendizado supervisionado, os modelos são construídos com o obje-
tivo de realizar inferências a partir desse conjunto de exemplos de treinamento para os
quais se conhece a priori as classes às quais estes exemplos pertencem. Durante a fase
2.2 Tipos de Aprendizado de Máquina 13
de treinamento, o algoritmo ajusta o indutor utilizando os exemplos, juntamente com a
informação de sua saída esperada (classe).
Assim, após o processo de treinamento (construção do modelo), logo que um novo
exemplo não-rotulado for apresentado ao modelo, tais algoritmos poderão, utilizando ex-
periências adquiridas anteriormente através do processo de treinamento, determinar uma
classe para esse novo exemplo, ou seja, rotular esse exemplo como pertencente a uma das
classes possíveis, de acordo com o conjunto de dados.
Na literatura, há vários métodos de aprendizado supervisionado propostos, dentre os
quais podemos destacar: k vizinhos mais próximos (kNN, do inglês, k-Nearest Neighbour)
(COVER; HART, 1967), algoritmos de indução de árvore de decisão (DT, do inglês, Decision
Tree) (QUINLAN, 1993), máquina de vetores suporte (SVM, do inglês, Support Vector Ma-
chines) (VAPNIK, 1995, 1998; HAYKIN, 1998; CRISTIANINI; SHAWE-TAYLOR, 2000), além de
vários modelos de redes neurais arti�ciais, tais como MLP (do inglês, Multilayer Percep-
tron) (HAYKIN, 1998) e RBF (do inglês, Radial Basis Function) (HAYKIN, 1998), dentre
outros.
2.2.2 Aprendizado Não-Supervisionado
Conforme citado anteriormente, no aprendizado supervisionado, durante o treinamento,
os métodos recebem como entrada exemplos juntamente com a informação de saída dese-
jada, representando a classe a que aquele exemplo pertence. Por outro lado, no aprendi-
zado não-supervisionado, os métodos recebem como entrada exemplos sem a informação
de saída, ou seja, não se conhecea priori a classe a que as instâncias do conjunto de
exemplos pertencem. Dessa maneira, o principal objetivo dos métodos de aprendizado
não-supervisionado é agrupar exemplos não-rotulados através da identi�cação de padrões
ou tendências, gerando agrupamentos ou clusters distintos, auxiliando assim no entendi-
mento desses dados (COSTA, 1999). Os algoritmos desse tipo de aprendizado são chamados
de algoritmos de agrupamento ou clustering.
Em geral, o processo de agrupamento dos algoritmos de aprendizado não-supervisionado
pode ser realizado através de duas abordagens principais: por meio de alguma medida de
distância ou de alguma medida de correlação. No agrupamento através de uma medida
2.2 Tipos de Aprendizado de Máquina 14
de distância, os exemplos podem ser agrupados com outros mais próximos, fomando assim
um cluster. Diversas medidas de distância podem ser utilizadas, dentre as quais pode-
mos destacar a distância Euclidiana e a distância de Mahalanobis (MAHALANOBIS, 1936).
Por outro lado, no agrupamento realizado por meio de uma medida de correlação, pode-
mos destacar a correlação de Pearson (PEARSON, 1901) como a medida de correlação mais
conhecida. Ao utilizar essas medidas de distância e de correlação, os grupos serão formados
de acordo com a distribuição linear apresentada entre cada exemplo. Dessa forma, pode-se
dizer que os exemplos presentes em um mesmo grupo podem apresentar uma maior seme-
lhança entre si do que exemplos em grupos diferentes. Contudo, é importante enfatizar que
os grupos no aprendizado não-supervisionado e as classes no aprendizado supervisionado
não agrupam ou representam, necessariamente, os mesmos exemplos (MATSUBARA, 2004).
Como exemplo de métodos de aprendizado não-supervisionado pode ser citado, dentre
outros: redes neurais do tipo Mapa Auto-Organizáveis (SOM, do inglês, Self-Organizing
Maps) (KOHONEN, 1982), k -Médias (do inglês, k-Means) (JAIN; DUBES, 1988) e Agrupa-
mento Hierárquico (SANGER, 1989).
2.2.3 Aprendizado Semissupervisionado
Conforme citado anteriormente, caso existam exemplos cujos rótulos de classes são
conhecidos antecipadamente, pode-se utilizar o aprendizado supervisionado para induzir
classi�cadores a partir desses exemplos. Por outro lado, quando os rótulos de classes
dos exemplos não são conhecidos antecipadamente, pode-se utilizar o aprendizado não-
supervisionado com o objetivo de encontrar clusters. Contudo, há situações em que há
uma pequena quantidade de exemplos rotulados, enquanto a quantidade de exemplos não
rotulados é alta. Assim, induzir classi�cadores exclusivamente a partir de um pequeno
conjunto de exemplos rotulados, geralmente, leva à indução de classi�cadores com baixa
acurácia. Uma possível solução para esse problema é aumentar o conjunto de exemplos ro-
tulados através da atribuição de rótulos a exemplos do conjunto de exemplos não-rotulados.
Contudo, esse processo de atribuição manual de rótulos pode ser bastante difícil e custoso,
seja pela falta de um especialista do domínio ou por esse especialista não possuir total
conhecimento do domínio a ser apresentado. Desse modo, pode ser identi�cada a necessi-
2.2 Tipos de Aprendizado de Máquina 15
dade de métodos capazes de incrementar a quantidade de exemplos rotulados através de
um processo automático, possibilitando o aumento da precisão dos classi�cadores a serem
gerados.
Nesse contexto, o aprendizado semissupervisionado, área de pesquisa relativamente
nova em Aprendizado de Máquina, representa a junção do aprendizado supervisionado e
não-supervisionado (SANCHES, 2003). Assim, no aprendizado semissupervisionado, exem-
plos em que os rótulos das classes são conhecidos e exemplos em que os rótulos das classes
não são conhecidos são apresentados ao algoritmo de aprendizado. Um dos principais
objetivos do aprendizado semissupervisionado é rotular mais exemplos e, desse modo, in-
crementar a quantidade de exemplos do conjunto de dados de treinamento. Desse modo,
este conjunto de dados de treinamento incrementado pode ser apresentado a um algoritmo
de aprendizado supervisionado para que este, por sua vez, possa induzir classi�cadores
mais precisos.
Uma das vantagens do aprendizado semissupervisionado é o potencial de reduzir a
necessidade de uma grande quantidade de dados rotulados, em domínios nos quais somente
um pequeno conjunto de padrões rotulados está disponível. Outra vantagem desse tipo de
aprendizado pode ser veri�cada quando o especialista não apresenta um total conhecimento
sobre o conceito a ser aprendido, ou seja, esse especialista tem apenas o conhecimento
de alguns padrões de um determinado conjunto de dados, aprensentando assim, grande
di�culdade de rotular exemplos para incrementar o conjunto de dados de treinamento.
Como exemplos de técnicas de aprendizado semissupervisionado bastante utilizados po-
demos citar o Self-Training (ROSENBERG; HEBERT; SCHNEIDERMAN, 2005) e o Co-Training
(BLUM; MITCHELL, 1998).
No self-training um classi�cador é primeiramente gerado a partir de uma pequena
quantidade de exemplos rotulados. Logo após ser gerado, o classi�cador é então utilizado
para classi�car exemplos não-rotulados. Assim, os exemplos não-rotulados, juntamente
com os rótulos preditos pelo classi�cador, são adicionados ao conjunto de treinamento.
Em seguida, o classi�cador é retreinado e todo o procedimento é repetido. É importante
ressaltar que o classi�cador faz uso de suas próprias predições para ensinar a si próprio,
daí o nome self-training (autotreinamento).
2.3 Considerações Finais 16
por sua vez, o Co-Training (BLUM; MITCHELL, 1998) é uma poderosa abordagem ao
aprendizado semissupervisionado baseada na ideia da multidescrição. Nesta abordagem, os
exemplos de treinamento são descritos por dois ou mais conjuntos de atributos disjuntos,
ou seja, através de diferentes descrições (MATSUBARA; MONARD; BATISTA, 2005). Um
dos algoritmos de aprendizado semissupervisionado multidescrição mais utilizados é o Co-
Training (BLUM; MITCHELL, 1998). Nesse algoritmo, dois classi�cadores são inicialmente
gerados, cada um utilizando uma descrição diferente dos exemplos rotulados. Uma vez
que são utilizadas duas descrições, pode-se utilizar o mesmo algoritmo de aprendizado
supervisionado para induzir as duas hipóteses (classi�cadores), assim como dois algoritmos
de aprendizado supervisionado distintos. Assim, é gerado um classi�cador sobre os mesmos
exemplos, mas cada um induzido segundo visões (descrições) diferentes. Desse modo, pode-
se a�rmar que o Co-Training baseia-se na ideia de que cada um dos classi�cadores rotulará
exemplos que conterão informações desconhecidas pelo outro classi�cador.
Uma vez gerados os dois classi�cadores, os exemplos não-rotulados são apresentados
aos dois classi�cadores, os quais terão suas saídas combinadas. Em seguida, os exemplos
que apresentarem o grau de con�ança de classi�cação mais altos são inseridos no conjunto
de exemplos rotulados. A partir desse conjunto incrementado de exemplos rotulados, são
gerados dois novos classi�cadores e o processo é repetido.
2.3 Considerações Finais
Este capítulo teve início com a apresentação dos principais conceitos básicos associ-
ados à área de Aprendizado de Máquina. Em seguida, foram apresentadas as principais
características de cada uma das categorias de aprendizado: aprendizado supervisionado,
aprendizado não-supervisionado e aprendizado semissupervisionado. No aprendizado su-
pervisionado, os métodos tratam da construção de indutores com o objetivo de realizar
inferências a partir de um conjunto de exemplos de treinamento rotulados, ou seja, para os
quais se conhece a priori as classes às quais esses exemplos pertencem. Enquanto isso, no
aprendizado não-supervisionado, os métodos recebem como entrada exemplos sem a infor-
mação de saída, ou seja, não se conhece a priori a classe a que as instâncias do conjunto de
exemplos pertencem. Por sua vez, o aprendizado semissupervisionado representa ajunção
2.3 Considerações Finais 17
do aprendizado supervisionado e não-supervisionado. A junção dos dois primeiros tipos
de aprendizado tem como objetivo reduzir a necessidade de uma grande quantidade de
dados rotulados, quando somente um pequeno conjunto de exemplos rotulados está dispo-
nível, através da atribuição de rótulos a exemplos não-rotulados por meio de um processo
automático.
18
Capítulo 3
Classi�cação de Dados
A classi�cação de dados é um processo no qual, a partir de um conjunto de dados
brutos, são extraídas informações por meio de categorização. Desse modo, um processo
de classi�cação consiste na atribuição de rótulos aos dados, de tal forma que esses rótulos
con�ram informações aos dados categorizados sob o mesmo rótulo (COSTA, 2008).
O conceito de classi�cação de dados é bastante comum em várias áreas de conheci-
mento, tais como: Computação, Engenharia, Matemática, Estatística, dentre outras. Em
computação, uma área de estudo com amplo interesse em classi�cação de dados é a área
de aprendizado de máquina.
Nas últimas décadas, intensas pesquisas vêm sendo realizadas na área de aprendizado
de máquina, focando principalmente a classi�cação de dados, tais como em (CANUTO et al.,
2009; ALMEIDA; LUDERMIR, 2010; LORENA; CARVALHO, 2010; OLIVEIRA; CANUTO; SOUTO,
2007; SANTANA; CANUTO; ABREU, 2006).
Como citado anteriormente, problemas de classi�cação de dados são um subconjunto
dos problemas de aprendizado supervisionado. Assim, o processo de classi�cação ocorre
por meio de um algoritmo de aprendizado, cujo objetivo é gerar um classi�cador a partir
de dados de entrada rotulados.
CAPÍTULO 3. CLASSIFICAÇÃO DE DADOS 19
Tabela 3.1: Conjunto de dados para o diagnóstico da saúde de um paciente.
Exemplo Febre Enjôo Manchas Dor Diagnóstico
E1 sim sim pequenas sim doente
E2 não não grandes não saudável
E3 sim sim pequenas não saudável
E4 sim não grandes sim doente
E5 sim não pequenas sim saudável
E6 não não grandes sim doente
Desse modo, para a geração do classi�cador, é necessário um conjunto de exemplos
rotulados, chamado conjunto de dados de treinamento. Cada exemplo do conjunto de
dados de treinamento é constituído por um vetor ~xi de atributos. Cada atributo de entrada
corresponde a uma característica ou propriedade do exemplo. Juntamente com os atributos,
também é fornecido o rótulo de cada exemplo. Na Tabela 3.1, têm-se um conjunto de dados
para classi�cação do estado de saúde de um paciente. Nesta tabela, cada linha representa
um exemplo do conjunto de dados e cada coluna um atributo deste exemplo. O atributo
Diagnóstico é especial, pois possui o rótulo da classe para cada exemplo, ou seja, doente
ou saudável.
O processo de geração de um classi�cador se inicia com uma fase de pré-processamento
dos dados. Esta fase tem como objetivo fazer com que os dados brutos pertencentes ao
domínio sobre o qual será aplicado o algoritmo de classi�cação sejam representados de
forma adequada, possibilitando a sua utilização na fase de treinamento.
Após a fase de pré-processamento, inicia-se a fase de treinamento. Nesta fase, cada
exemplo Ei, representado por um par (~xi, yi), tal que i = 1, 2, ..., N é o número de exemplos
de treinamento, ~xi é vetor de atributos que descrevem cada exemplo e yi é o valor do
atributo-alvo Y , também conhecido como rótulo ou classe. O objetivo do processo de
treinamento é obter uma função que mapeie cada Ei a seu Yi correspondente. A função de
mapeamento é encontrada com base nos ajustes dos parâmetros livres do modelo.
Sendo assim, ao �nalizar a fase de treinamento, obtêm-se um classi�cador capaz de
realizar o processo de predição da classe à qual um novo exemplo de entrada pertence,
através da generalização dos exemplos do conjunto de treinamento.
3.1 Classi�cação de Dados Multirrótulo 20
A classi�cação de dados é, provavelmente, uma das tarefas mais estudadas em aprendi-
zado de máquina. Tal fato se deve, principalmente, pela possiblidade de aplicação em uma
grande quantidade de domínios. Na literatura, diversos métodos consolidados para tratar
problemas de classi�cação pode ser encontrada . No entanto, a maioria desses métodos de
classi�cação, ditos tradicionais, consideram que para cada exemplo é atribuído um único
rótulo. Além disso, nenhuma relação hierárquica entre as classes possíveis é considerada.
Contudo, nos últimos anos vem sendo identi�cada uma série de tarefas de classi�cação nas
quais os exemplos podem ser rotulados a mais de uma classe simultaneamente. Adicional-
mente, tais classes podem estar hierarquicamente organizadas.
Este capítulo está organizado da seguinte forma: a Seção 3.1 apresenta a classi�cação
de dados multirrótulo e as principais técnicas existentes. A Seção 3.2 trata de problemas
de classi�cação de dados hierárquica. Na Seção 3.3, é apresentada uma recente área de
classi�cação de dados, resultante da combinação da classi�cação de dados multirrótulo e
classi�cação de dados hierárquica, chamada classi�cação de dados hierárquica multirrótulo.
3.1 Classi�cação de Dados Multirrótulo
A classi�cação de dados tradicional trata do aprendizado de um conjunto de exemplos
(instâncias) em que cada um é associado a uma única classe (rótulo) de um conjunto de
classes Y , de modo que |Y | > 1 . Essa tarefa é chamada de classi�cação unirrótulo (do
inglês, single-label classi�cation). Se |Y | = 2, então a tarefa de aprendizado é chamada de
classi�cação unirrótulo binária. Por outro lado, se |Y | > 2, a tarefa é chamada de classi�-
cação unirrótulo multiclasse. Embora a classi�cação unirrótulo seja bastante utilizada, há
vários domínios nos quais as instâncias estão associados a um conjunto de classes L, tal que
L ⊆ Y , ou seja, cada exemplo pode ser associado a mais de uma classe simultaneamente.
Nesses casos, em que as classes não são disjuntas, à tarefa de classi�cação dá-se o nome
de classi�cação multirrótulo (do inglês, multi-label classi�cation) (TSOUMAKAS; KATAKIS;
VLAHAVAS, 2008). Por exemplo, um �lme pode ser classi�cado como ação e aventura,
um artigo no jornal pode ser classi�cado como pertencente às seções de música e cultura,
dentre outros.
Para uma descrição formal, seja L = λj : j = 1, ...,M um conjunto �nito de classes (ró-
3.1 Classi�cação de Dados Multirrótulo 21
Tabela 3.2: Exemplos de um conjunto de dados multirrótulo.
Exemplo Rótulos
1 {λ1, λ4}
2 {λ3, λ4}
3 {λ1}
4 {λ2, λ3 λ4}
tulos) em uma tarefa de aprendizado multirrótulo e D = {(~xi|Li), i = 1, ..., N} o conjunto
de exemplos de treinamento multirrótulo, onde ~xi é o vetor de características (atributos)
e Li ⊆ Y o conjunto de classes da i -ésima instância (TSOUMAKAS; KATAKIS; VLAHAVAS,
2009). Na Tabela 3.2, são apresentados quatro exemplos rotulados com um ou mais rótulos:
λ1, λ2, λ3 e λ4.
Apesar de grande parte das pesquisas na área de classi�cação de dados se concentrarem
na análise de dados com um único rótulo, nos últimos anos, a área de classi�cação de da-
dos multirrótulo têm atraído a atenção de grande parte da comunidade cientí�ca, motivado
principalmente pelo grande aumento no número de novas aplicações, tais como anotação
semântica de imagens (BOUTELL et al., 2004; ZHANG; ZHOU, 2007; YANG; KIM; RO, 2007)
e vídeo (QI et al., 2007; SNOEK et al., 2006), função genômica (BLOCKEEL et al., 2006; BA-
RUTCUOGLU; SCHAPIRE; TROYANSKAYA, 2006; ELISSEEFF; WESTON, 2001; CLARE; KING,
2001), categorização de músicas através de emoções (LI; OGIHARA, 2003, 2006; WIEC-
ZORKOWSKA; SYNAK; RA±, 2006; TROHIDIS et al., 2008) e marketing direcionado (ZHANG;
BURER; STREET, 2006). Classi�cação de textos pode ser identi�cada como a área que tem
maior aplicação de técnicas de classi�cação multirrótulo (ESULI; SEBASTIANI, 2009a, 2009b;
KATAKIS; TSOUMAKAS; VLAHAVAS, 2008; PESTIAN et al., 2007; GONCALVES; QUARESMA,
2003; LAUSER; HOTHO, 2003).
Na Figura 3.1, é apresentada uma comparação entre um problema de classi�cação
unirrótulo e um problema de classi�cação multirrótulo. A Figura 3.1.a ilustra umproblema
de classi�cação unirrótulo no qual um exemplo pode pertencer à classe "Biologia"ou à classe
"Informática", mas nunca às duas classes simultaneamente. Por outro lado, a Figura 3.1.b
ilustra um exemplo de classi�cação multirrótulo, em que os exemplos podem pertencer
simultaneamente às classes "Biologia"e "Informática", podendo, então, serem classi�cados
3.1 Classi�cação de Dados Multirrótulo 22
Figura 3.1: (a) Problema de classi�cação tradicional ou unirrótulo. (b) Problema de
classi�cação multirótulo.
como pertencentes à classe "Bioinformática".
Na literatura, podem ser encontradas diferentes métodos e técnicas para tratar pro-
blemas de classi�cação multirrótulo. Em algumas destas técnicas, problemas multirrótulo
são quebrados em vários problemas unirrótulo. Assim, classi�cadores unirrótulo podem ser
combinados para viabilizar o tratamento de problemas de classi�cação multirrótulo. Por
outro lado, há técnicas que resultam da modi�cação de algoritmos de classi�cação unirró-
tulo, de modo que, através da adaptação de seus mecanismos internos, torna-se possível
a sua utilização em problemas de classi�cação multirrótulo. Adicionalmente, novos me-
canismos podem ser desenvolvidos para tratar especi�camente problemas de classi�cação
multirrótulo (TSOUMAKAS; KATAKIS; VLAHAVAS, 2009).
Neste contexto, duas importantes abordagens podem ser utilizadas para tratar um
problema de classi�cação multirrótulo:
• Independente do algoritmo;
• Dependente do algoritmo.
Na abordagem independente do algoritmo, também chamada de transformação do pro-
blema, problemas de classi�cação multirrótulo são tratados utilizando qualquer algoritmo
de classi�cação tradicional. Para isso, basta que o problema multirrótulo original seja
3.1 Classi�cação de Dados Multirrótulo 23
transformado em um conjunto de problemas de classi�cação unirrótulo. Por sua vez, na
abordagem dependente do algoritmo, novos algoritmos são propostos para tratar proble-
mas de classi�cação multirrótulo como um todo, em uma única etapa. Tais algoritmos
podem ser desenvolvidos especi�camente para classi�cação multirrótulo ou serem baseados
em técnicas de classi�cação convencionais, como SVMs e árvores de decisão (FACELLI et
al., 2011).
Há extensões multirrótulo de vários algoritmos de aprendizado de máquina, tais como:
árvore de decisão (CLARE; KING, 2001), máquina de vetores suporte (SVM, do inglês,
support vector machines) (ELISSEEFF; WESTON, 2001; GODBOLE; SARAWAGI, 2004), redes
neurais arti�ciais (CRAMMER; SINGER, 2003; ZHANG; ZHOU, 2006), aprendizado bayesiano
(MCCALLUM, 1999), k vizinhos mais próximos (kNN, do inglês, k nearest neighbor) (ZHANG;
ZHOU, 2007) e boosting (SCHAPIRE; SINGER, 2000).
Nas próximas subseções são apresentadas alguns algoritmos, de acordo com a aborda-
gem utilizada para tratar problemas de classi�cação multirrótulo.
3.1.1 Transformação do Problema
Como citado anteriormente, a abordagem de transformação do problema, também
chamada de abordagem independente do algoritmo, consiste na conversão de uma tarefa
multirrótulo em um conjunto de tarefas unirrótulo. A idéia é transformar o problema
original em um conjunto de problemas de classi�cação unirrótulo. Assim, torna-se possí-
vel a utilização de qualquer algoritmo tradicional de classi�cação para tratar o problema
multirrótulo.
Na literatura, há vários trabalhos propondo métodos de transformação simples que
podem ser usados para converter um conjunto de dados multirrótulo em um conjunto
de dados unirrótulo com o mesmo conjunto de rótulos como por exemplo em (BOUTELL et
al., 2004; TSOUMAKAS; KATAKIS, 2007; KATAKIS; TSOUMAKAS; VLAHAVAS, 2008; TSOUMA-
KAS; KATAKIS; VLAHAVAS, 2009; NASIERDING; TSOUMAKAS; KOUZANI, 2009; TSOUMAKAS;
KATAKIS; VLAHAVAS, 2010). Dentre os métodos mais utilizados podem ser citados: BR
(do inglês Binary Relevance) (TSOUMAKAS; KATAKIS, 2007), LP (do inglês, Label Power-
set)(KATAKIS; TSOUMAKAS; VLAHAVAS, 2008) e RAkEL (do inglês, RAndom k-LabELsets)
3.1 Classi�cação de Dados Multirrótulo 24
(TSOUMAKAS; KATAKIS; VLAHAVAS, 2010).
3.1.1.1 Relevância Binária
Dentre os métodos de transformação do problema, o mais popular é o método de
Relevância Binária (BR, do inglês Binary Relevance) (TSOUMAKAS; KATAKIS, 2007). Neste
método, o problema multirrótulo é dividido em |L| problemas de classi�cação unirrótulo
binário, onde |L| é a quantidade de rótulos contidos em L. Assim, pode-se a�rmar que a
predição de cada rótulo é considerada como uma tarefa independente.
No método de Relevância Binária, o conjunto de dados original é transformado em |L|
conjuntos de dados Dλj , cada um dos quais contendo todos os exemplos do conjunto de
dados original, rotulados como λj se o conjunto de rótulos do exemplo original contém λj
e como ¬λj, caso contrário. Com isso, um classi�cador binário Cλj : X → {¬λj, λj} é
treinado para cada diferente rótulo λj ∈ L. Assim, uma vez que todos os classi�cadores
tenham sido treinados, para a classi�cação de uma nova instância é retornada como saída
a união dos λj rótulos que são positivamente preditos pelos |L| classi�cadores. Na Tabela
3.3, são apresentados os conjuntos de dados produzidos ao utilizar o método de Relevância
Binária. A Figura 3.2 ilustra o processo utilizado pelo BR.
Uma das principais críticas ao BR é o fato de neste método não serem consideradas as
correlações entre os rótulos, descartando assim informações que podem ser importantes à
tarefa de classi�cação. Desse modo, o modelo gerado pelo método de Relevância Binária
pode levar à uma pouca capacidade de generalização. Além disso, o modelo de classi�cação
gerado é de baixa legibilidade, uma vez que é gerado um modelo em separado para cada
um dos rótulos associado a um exemplo de teste.
3.1.1.2 Label Powerset
Outro método de transformação de problema menos comum, mas ainda assim bastante
utilizado é o Label Powerset (LP)(KATAKIS; TSOUMAKAS; VLAHAVAS, 2008). Neste mé-
todo, cada subconjunto diferente de rótulos de L é considerado como uma única classe da
nova tarefa de classi�cação unirrótulo. Desse modo, um classi�cador unirrótulo C : X →
P (L) é treinado, onde P (L) é o powerset de L, contendo todos os subconjuntos de rótulos
3.1 Classi�cação de Dados Multirrótulo 25
Figura 3.2: Processo utilizado pelo BR.
Tabela 3.3: Conjuntos de dados obtidos ao utilizar o método de Relevância Binária nos
dados da Tabela 3.1.
Exemplo Rótulos
1 {λ1}
2 {¬λ1}
3 {λ1}
4 {¬λ1}
Exemplo Rótulos
1 {¬λ2}
2 {¬λ2}
3 {¬λ2}
4 {λ2}
Exemplo Rótulos
1 {¬λ3}
2 {λ3}
3 {¬λ3}
4 {λ3}
Exemplo Rótulos
1 {λ4}
2 {λ4}
3 {¬λ4}
4 {λ4}
3.1 Classi�cação de Dados Multirrótulo 26
Tabela 3.4: Conjunto de dados transformado usando o método Label Powerset.
Exemplo Rótulos
1 {λ1,4}
2 {λ3,4}
3 {λ1}
4 {λ2,3,4}
possíveis. Assim, dada uma nova instância, o classi�cador unirrótulo C retorna como saída
a classe mais provável, que neste caso é um conjunto de rótulos. A Tabela 3.4 mostra o
resultado da transformação do conjunto de dados da Tabela 3.2 usando o método Label
Powerset. A Figura 3.3 ilustra o processo utilizado pelo LP.
Figura 3.3: Processo utilizado pelo LP.
Um das vantagens deste método é que, ao contrário do BR, no LP, as correlações
entre os rótulos são consideradas. Contudo, é suscetível ao fato de, no caso de haver um
número muito grande de subconjuntos de rótulos, o número de rótulos de uma classe pode
crescer exponencialmente, resultando em muitas classes com poucos exemplos associados,
aumentando o custo computacional do LP e diminuindo a acurácia dos classi�cadores.
Além disso, o LP só pode prever con�avelmente conjuntos de rótulos (labelsets) observados
no conjunto de treinamento. Esta é uma importante limitação, uma vez que novos labelsets
tipicamente aparecerão em instâncias de teste.
3.1 Classi�cação de Dados Multirrótulo 27
3.1.1.3 Random K-labelsets
Tendo como objetivo minimizar os problemas do LP mencionados anteriormente, em
(TSOUMAKAS; KATAKIS; VLAHAVAS, 2010) foi proposta uma abordagem na