Kapittel 3 Vitskapsteori og metode
3.1 Vitskapsteoretiske merknader
3.1.4 Å lesa meir enn teksten – kva seier Gadamer om det?
Considerando a complexidade computacional do métodoHMC-LMLP, as variações HMC- LMLP-Predicted e HMC-LMLP-True possuem complexidade igual a O(Wl), sendo Wl o nú-
mero de pesos e biases de cada rede MLP associada com o nível l. Considerando que |A| é o número de atributos de um conjunto de dados, Hl é o número de neurônios da camada es-
condida da rede MLP associada ao nível l, e Ol é o número de neurônios de saída da MLP
associada ao nível l, o número de pesos e biases no primeiro nível hierárquico (W1) é defi-
nido como (|A| + 1) × H1 +(H1 + 1) × O1. A partir do segundo nível, Wl é definido como
(Ol−1+|A| +1) × Hl+(Hl +1) × Ol.
Na variação HMC-LMLP-NoLabels, o custo computacional é menor, já que as classes não são utilizadas para complementar os vetores de atributos dos exemplos. Assim, em todos os níveis l, a complexidade computacional é dada por O(Wl), com Wl = (|A|+1)× Hl+(Hl+1)×Ol.
A variação HMC-LMLP-Labels tem a menor complexidade computacional entre todas as variações quando o número de classes em cada nível é menor que o número de atributos. Isso ocorre porque do segundo nível em diante, são utilizadas apenas as predições como entrada das redes MLP. No primeiro nível, o custo computacional é o mesmo das outras variações. Do segundo nível em diante, a complexidade é dada por O(Wl), com Wl = (Ol−1+1) × Hl +(Hl+
1) × Ol.
Em todas as variações do método HMC-LMLP, o custo total de treinamento de cada rede
MLP associada a cada nível l é então definido como O(Wl ×ml × n), sendo ml o número de
exemplos de treinamento classificados em classes pertencentes ao nível l, e n o número de ciclos de treinamento.
4.7 Considerações Finais
Este capítulo apresentou o método Hierarchical Multi-Label Classification with Local Multi-Layer Perceptrons (HMC-LMLP), uma proposta de utilização de redes neurais artifici- ais para classificação hierárquica multirrótulo, na qual uma redeMLPé associada a cada nível hierárquico e responsável pelas predições em seu respectivo nível. Foram propostas duas varia- ções incrementais do método: utilizando as predições em um nível como as únicas entradas no próximo nível (HMC-LMLP-Labels), e utilizando as predições em um nível para complementar os vetores de atributos dos exemplos no próximo nível (HMC-LMLP-Predicted). Além disso, outras duas variações não incrementais foram apresentadas: utilizando as classes verdadeiras dos exemplos para complementar os vetores de atributos (HMC-LMLP-True), e utilizando ape- nas os exemplos sem as classes (HMC-LMLP-NoLabels). Foi também discutido como são
obtidas as predições finais e corrigidas as inconsistências de classificação, intrínsecas da es- tratégia adotada pelo método, que utiliza um classificador local por nível (LCL). O próximo capítulo apresenta os detalhes da proposta que utiliza algoritmos genéticos para a geração de regras de classificação hierárquicas multirrótulo.
5
Classificação Hierárquica Multirrótulo
com um Algoritmo Genético
Este capítulo apresenta o método para classificação hierárquica multirrótulo utilizando Al- goritmos Genéticos. Trata-se do método Hierarchical Multi-Label Classification with a Genetic Algorithm(HMC-GA), que é baseado na abordagem global para a geração de regras de classi- ficação. O pseudo-código do módulo principal do método é apresentado no Algoritmo3, que implementa um procedimento de cobertura sequencial de exemplos para evoluir os antecedentes das regras de classificação. Nesse procedimento de cobertura sequencial, os exemplos cobertos por uma regra são removidos do conjunto de treinamento, de maneira que novas regras possam ser geradas para cobrir os exemplos remanescentes. Ainda, no método proposto, o consequente de uma regra é obtido utilizando um procedimento determinístico que considera as classes atri- buídas aos exemplos cobertos pela regra. Este capítulo está organizado da seguinte maneira: na Seção5.1 é apresentado como um indivíduo do algoritmo é representado; a inicialização dos indivíduos é explicada na Seção 5.2; na Seção5.3 é explicado todo o processo evolutivo que leva à construção dos antecedentes das regras; o procedimento utilizado para a construção dos consequentes das regras é apresentado na Seção5.4; a complexidade computacional de algumas partes do método é apresentada na Seção5.5; por fim, a Seção5.6apresenta as considerações finais do capítulo.
Algoritmo 3: Classificação Hierárquica Multirrótulo com um Algoritmo Genético. procedimento HMC-GA(D,G,p,minCob,maxCob,maxNaoCob,cr,mr,t,e,pt) Entrada: conjunto de treinamento D
número de gerações G tamanho da população p
número mínimo de exemplos cobertos por uma regra minCob número máximo de exemplos cobertos por uma regra maxCob número máximo de exemplos não cobertos maxNaoCob taxa de crossover cr
taxa de mutação mr tamanho do torneio t
número de indivíduos selecionados por elitismo e probabilidade de usar um termo pt
Saída: conjunto de regras regrasDescobertas regrasDescobertas ← ∅
1
enquanto |D| > maxNaoCob faça
2 populacaoInicial ← geraPopulacao(D, p, pt) 3 calculaFitness(populacaoInicial, D) 4 populacaoAtual ← populacaoInicial 5
melhorRegra ←melhor regra da populacaoAtual segundo o f itness
6 j ← G 7 repita 8 novaPopulacao ← ∅ 9
novaPopulacao ← novaPopulacao ∪ elite(populacaoAtual, e)
10
pais ← selecaoT orneio(populacaoAtual, t, e, p)
11
f ilhos ← crossoverUni f ormeDistancia(pais, cr)
12
novaPopulacao ← novaPopulacao ∪ f ilhos
13
novaPopulacao ← mutacao(novaPopulacao, mr, pt)
14
novaPopulacao ← operadorLocal(novaPopulacao, minCob, maxCob)
15
populacaoAtual ← novaPopulacao
16
calculaFitness(populacaoAtual, D)
17
melhorRegra ← obtemMelhorRegra(populacaoAtual, melhorRegra)
18
j ← j −1
19
até j > 0 OU regraConverge() ;
20
regrasDescobertas ← regrasDescobertas ∪ melhorRegra
21
remove de D os exemplos cobertos pela melhorRegra
22
retorna regrasDescobertas
5.1 Representação dos Indivíduos
Os indivíduos do método HMC-GA são os antecedentes das regras de classificação. Um antecedente de uma regra é representado por um vetor de valores reais, no qual cada valor é decodificado em um componente do antecedente da regra, que pode ser um operador, um índice de atributo ou um valor de atributo. A Figura5.1apresenta a representação de um indivíduo no métodoHMC-GA.
FLAG OP 1 2 FLAG OP 1 2
Figura 5.1: Representação de um indivíduo no método HMC-GA.
Cada conjunto de quatro posições do vetor ilustrado na Figura5.1representa um teste sobre um atributo do conjunto de dados sendo utilizado para evolução das regras. Assim, o vetor antecedente tem tamanho igual a quatro vezes o número de atributos, e cada teste é codificado como um 4-tupla {FLAG,OP, ∆1, ∆2}. O gene FLAG pode ser tanto 0 quanto 1, indicando a
presença (1) ou ausência (0) do respectivo teste no antecedente da regra, já que uma regra pode ser composta apenas por alguns atributos. O gene OP deve conter o índice de um dos possíveis operadores do teste, e os genes ∆1and ∆2são valores reais utilizados como condições dos testes.
Todos os testes que compõem o antecedente de uma regra são separados por uma cláusula E. Esses testes testam um dado atributo Ai de acordo com um valor ∆, utilizando um operador
OP. No caso de atributos nominais, os operadores empregados podem ser =, , e in. O operador inpermite que um dado atributo categórico seja testado para verificar se seu valor pertence a um conjunto de valores. Para cada atributo categórico, todos os seus valores são indexados com valores numéricos, de modo a serem utilizados na representação dos indivíduos. Além disso, todos os possíveis conjuntos de dois ou mais valores formados pelos valores categóricos de um atributo também são indexados. Esse último procedimento é necessário para a utilização do operador in. Quando os operadores = e , são utilizados em um teste, ∆2recebe 0 e ∆1recebe o
índice correspondente ao valor categórico utilizado no teste da condição. Quando o operador in é utilizado, ∆2recebe 0 e ∆1recebe o índice correspondente ao conjunto de valores categóricos
utilizado no teste da condição.
No caso de atributos numéricos, podem ser utilizados os operadores ≥ e ≤. Além disso, é possível que um atributo numérico seja testado considerando um operador composto, para verificar se seu valor pertence a um dado intervalo, ou seja, ∆1 ≤ Ai ≤ ∆2. Nos casos em que
são utilizados operadores simples (não compostos), os valores de ∆1 e ∆2 são escolhidos de
acordo com o operador. Se o operador for ≤, ∆1recebe o valor 0 e ∆2recebe o valor de teste da
condição. Para o operador ≥, ∆2recebe 0 e ∆1recebe o valor de teste da condição.
Todos os operadores possíveis, numéricos e categóricos, e também os possíveis valores categóricos de um atributo, são previamente indexados e possuem índices fixos. Assim um teste pode ser facilmente executado por meio da recuperação dos índices e utilização do operador e valores correspondentes. A Figura5.2ilustra um exemplo desse processo.
1 1
1
0 0
A = C1 A in {Y,Z}2
A1
Valores Possíveis valores indexados A, B, C X, Y, Z A2 A, B, C, {A,B},{A,C},{B,C},{A,B,C} 0 1 2 3 4 5 6 X, Y, Z, {X,Y},{X,Z},{Y,Z},{X,Y,Z} 0 1 2 3 4 5 6 2 2
FLAG OP FLAG OP 1 2 FLAG OP 2
5 1 0
A 0.43
1
0.4 A3 Num Atributos numéricos não
precisam ser indexados
Tipo Operadores indexados Numérico Categórico 0 1 2
= =
in
0 1 2 0 2 1Figura 5.2: Exemplo de indexação de valores categóricos e operadores do método HMC-GA. Após construído o antecedente de uma regra, esse deve ser capaz de classificar um dado exemplo em um conjunto de classes, respeitando as restrições da estrutura hierárquica na qual as classes estão organizadas. Assim, uma regra de classificação para problemas hierárquicos multirrótulo do método HMC-GA deve ser estruturada como (lembrando que para atributos numéricos, testes compostos do tipo ∆1≤ Ai ≤ ∆2também são possíveis):
SE (A1 OP ∆) E . . . E (Am OP ∆) → Antecedente
ENTÃO
{C1,C1.3,C1.4,C1.4.2} → Consequente