Kapittel 3 Vitskapsteori og metode
3.3 I det metodiske
Na Equação5.1, foi mostrado como é construído o vetor médio de classes vrde uma regra,
obtido utilizando os vetores de classes dos exemplos cobertos pela regra. Esse vetor médio também pode ser interpretado como o consequente da regra. Assim, cada posição do vetor consequente de uma regra é um valor contínuo no intervalo [0,1]. Como resultado, o valor do i-ésimo componente do vetor consequente de uma regra representa a probabilidade de um
exemplo que satisfaz seu antecedente pertencer a classe i da hierarquia.
Uma vez construídos os consequentes das regras, essas são avaliadas por meio de uma fun- ção de fitness. A função de fitness utilizada aqui é o ganho de variância (Vens et al.,2008;Otero
et al.,2010). O ganho de variância é maior para regras que cobrem um conjunto mais homogê-
neo de exemplos e deixam sem cobertura também um conjunto mais homogêneo de exemplos, ou seja, regras que particionam o conjunto de treinamento em conjuntos mais homogêneos. Além disso, o ganho de variância lida diretamente com dados hierárquicos multirrótulo, le- vando em consideração os relacionamentos e similaridades entre as classes (Otero et al.,2010). O ganho de variância é apresentado na Equação5.6.
ganhoVariancia(r, S ) = variancia(S ) − |Sr|
|S | ×variancia(Sr) − |S¬r|
|S | ×variancia(S¬r) (5.6) Como observado na Equação5.6, o conjunto de treinamento S é divido em dois subconjun- tos: o conjunto de exemplos cobertos pela regra r, denominado Sr, e o conjunto de exemplos
não cobertos pela regra r, denominado S¬r. O ganho de variância da regra r é então calcu-
lado com relação ao conjunto S . Além disso, esse cálculo envolve a variância dos conjuntos de exemplos cobertos e não cobertos pela regra. Essa variância é definida como a distância quadrática média entre o vetor de classes de cada exemplo e o vetor médio de classes de todo conjunto de exemplos (S , Sr ou S¬r) sendo utilizado. O cálculo da variância de um conjunto
de exemplos S é apresentado na Equação5.7. A distância utilizada é a distância Euclidiana ponderada, apresentada anteriormente na Equação5.2.
variancia(S ) = P|S |
k=1distanciaEuclidiana(vk,v)2
|S | (5.7)
5.5 Complexidade Computacional
A análise de complexidade computacional de algoritmos evolutivos geralmente não é feita, pois apesar de estudos teóricos (He e Yao,2003) sugerirem o uso de cadeias de Markov para esse fim, não se trata de uma tarefa de análise simples. Assim, esta seção apresenta a complexidade computacional dos procedimentos mais críticos do métodoHMC-GA.
São considerados com maior custo computacional o procedimento de semeadura utilizado para a criação da população inicial (Seção5.2), o operador de busca local que visa evitar que as regras sejam muito específicas ou muito gerais (Algoritmo9), e o cálculo do fitness das regras (Seção5.4). Além desses procedimentos, existem outros procedimentos executados durante a evolução do algoritmo genético, como a operação de crossover, que também consomem tempo. No entanto, eles também utilizam funções que são utilizadas no cálculo do fitness e na busca local, como o cálculo da distância entre dois vetores médios de classes, ou utilizam funções que já foram calculadas previamente, como a verificação de quais exemplos são cobertos por uma regra. Todas essas funções serão analisadas dentro das operações de busca local e cálculo
do fitness.
Inicialização da população
A inicialização da população é considerada crítica porque todos os atributos do exemplo selecionado como semente para dar origem a uma regra devem ser percorridos. Ainda, para cada atributo do exemplo, existem quatro posições no vetor representando o indivíduo sendo construído. Assim, sendo |A| o número de atributos de um conjunto de dados, e pop o número de indivíduos da população inicial, a complexidade computacional do procedimento de semeadura é dado por O(|A| × 4 × pop).
Operador de busca local
O procedimento de busca local é executado enquanto a convergência de uma regra não é alcançada. Essa convergência é alcançada quando o número de exemplos cobertos por uma re- gra encontra-se entre um valor mínimo e um valor máximo de exemplos. Existem dois cenários para o pior caso nessa busca. No primeiro cenário, uma regra tem todos os atributos ativados, sendo muito específica (cobrindo um número muito pequeno de exemplos). Nesse caso ela terá um número de termos ativos igual a |A|. O pior caso ocorre quando |A| − 1 atributos do ante- cedente da regra necessitarem ser desativados (FLAG = 0) para que a regra cubra um número desejado se exemplos, entre um mínimo e um máximo. Assim, todos os atribuutos necessitam ser percorridos, resultando em complexidade computacional igual a O(|A|). O segundo cená- rio ocorre quando a regra tem apenas um atributo ativado, sendo muito geral, e todos os seus atributos necessitarem ser ativados (FLAG = 1) para que a regra cubra o número desejado de exemplos. Nesse caso, também todos os atributos devem ser percorridos, sendo a complexidade igual a O(|A|).
Além de percorrer os atributos de uma regra, toda vez que um atributo é ativado ou desati- vado, é necessário que seja computado o número de exemplos cobertos pela regra. Para isso, é necessário que cada atributo ativo de uma regra seja comparado com o respectivo atributo de todos os exemplos. Considere o cenário de pior caso no qual uma regra tem apenas um atributo ativado, e necessita que todos os seus atributos sejam ativados para que ela cubra o número desejado de exemplos. Assim, após a ativação do segundo atributo, os dois atributos da regra devem ser comparados com os respectivos atributos dos exemplos. Com |X| sendo o número total de exemplos, são realizadas |X| × 2 comparações. Ainda, como a comparação envolve a verificação da 4-tupla correspondente ao atributo na regra, esse número de comparações deve ser multiplicado por quatro, resultando em |X| × 2 × 4 comparações. Assim, o custo total das comparações a medida que atributos do exemplo vão sendo ativados é dado por:
Custocomp = 2 × 4 × |X| + 3 × 4 × |X| + · · · + |A| × 4 × |X| = |X| ×4 × |A| X i=2 i = |X| ×4 × |A|(|A| + 1) 2 −1 !
Sendo essa equação quadrática do número de atributos |A|, a complexidade computacional da busca local é dada por O(|X| × 4 × |A|2).
Cálculo do fitness
O cálculo do fitness de uma regra consiste no cálculo das variâncias de todos os exemplos de treinamento, do conjunto de exemplos cobertos, e do conjunto de exemplos não cobertos pela regra. A variância de um conjunto de exemplos consiste no cálculo do vetor médio de classes dos exemplos, e depois, do cálculo das Distâncias Euclidianas entre os vetores de classes de todos os exemplos e o vetor médio de classes.
O vetor médio de classes de um conjunto de exemplos é dado pela soma de todos os valores vj dos vetores de classes v de cada exemplo, dividido pelo número total de exemplos do con-
junto. Assim, sendo |C| o número de classes do problema, o número de operações necessárias para o cálculo do vetor médio de classes é dado por |X| × |C|. Sendo Sr e S¬r os conjuntos
de exemplos cobertos e não cobertos por uma regra r, os cálculos dos vetores médios desses respectivos conjuntos são dados por |Sr| × |C|e |S¬r| × |C|.
Após a obtenção dos vetores médios de classes, são calculadas as Distâncias Euclidianas entre cada vetor de classes dos exemplos de cada conjunto de exemplos (X, SreS¬r) e os res-
pectivos vetores médios de classes desses conjuntos. A Distância Euclidiana entre dois vetores de classes requer |C| operações. Portanto, o cálculo da Distância Euclidiana envolvendo to- dos os exemplos de cada conjunto de exemplos requer, respectivamente, |X| × |C|, |Sr| × |C| e
|S¬r| × |C|operações.
Assim, as variâncias dos conjuntos X, Sr e S¬r possuem, respectivamente, complexidade
igual a O(2 × |X| × |C|), O(2 × |Sr| × |C|) e O(2 × |S¬r| × |C|).
5.6 Considerações Finais
Este capítulo apresentou o método Hierarchical Multi-Label Classification with a Genetic Algorithm(HMC-GA), um método baseado na abordagem global que induz regras de classifica- ção hierárquicas multirrótulo. O processo evolutivo é utilizado para a geração dos antecedentes das regras, e seus respectivos consequentes são gerados por meio de um processo determinístico que utiliza as classes dos exemplos cobertos pelos antecedentes. Ainda, o método utiliza um procedimento de cobertura sequencial de exemplos, no qual ao final de várias gerações de um
processo completo de evolução de regras, a melhor regra é salva, e os exemplos cobertos por ela são removidos do conjunto de treinamento. Todos os detalhes do método foram apresentados, desde a representação dos indivíduos e o procedimento para geração da população inicial, até os detalhes envolvidos nos operadores utilizados no processo evolutivo dos antecedentes e cons- trução dos respectivos consequentes. O próximo capítulo apresenta os experimentos realizados envolvendo os dois métodos propostos nesta pesquisa de Doutorado.
6
Experimentos
Neste capítulo são apresentados os experimentos realizados. As medidas de avaliação uti- lizadas e os métodos da literatura utilizados nos experimentos para fins de comparação são apresentados, respectivamente, nas Seções6.1e 6.2; a seção6.3descreve os conjuntos de da- dos utilizados; na Seção6.4 são apresentados e discutidos os experimentos realizados com o métodoHMC-LMLP, e a Seção6.5contém os experimentos com o métodoHMC-GA; na Se- ção6.6, são apresentados gráficos comparando os desempenhos de todos os métodos utilizados nos experimentos; por fim, a Seção6.7é dedicada às considerações finais do Capítulo.
6.1 Medidas de Avaliação
Como visto nos Capítulos 4 e 5, os métodos HMC-LMLP e HMC-GApossuem a carac- terística comum de que suas saídas, para cada exemplo, são formadas por um vetor no qual cada posição corresponde à predição para uma classe. Ainda, cada posição possui um valor real entre 0 e 1. Esse é o mesmo tipo de saída fornecida pelos métodos da literatura utilizados nos experimentos. Assim, de maneira a se obter as predições finais de todos os métodos, um valor de limiar deve ser utilizado. Quando classificando um exemplo, se o valor de saída correspon- dente a uma dada classe for igual ou superior a um dado limiar, a classe é atribuída ao exemplo. Caso contrário, a classe não é atribuída ao exemplo. Atribuir uma classe a um exemplo significa atribuir o valor 1 à posição correspondente a essa classe no vetor de saída. A atribuição do valor 0 significa que a classe não foi atribuída ao exemplo.
A escolha de um valor ótimo para o limiar não é uma tarefa trivial. A escolha de um valor baixo para o limiar faz com que muitas classes sejam atribuídas a cada exemplo, resultando em um alto valor de revocação e um baixo valor de precisão. A escolha de um valor de limiar alto, por outro lado, resulta em muito poucas classes atribuídas a cada exemplo, o que faz com que seja obtido um valor alto de precisão e um valor baixo de revocação. Para evitar o problema da
escolha de um limiar adequado, foram utilizadas curvas precisão-revocação (curvasPR) como medida de avaliação para comparar os diferentes métodos. Para se obter uma curvaPRpara um dado método de classificação, diferentes valores de limiares variando num intervalo [0, 1] são aplicados às saídas dos métodos. Assim, diferentes valores de precisão e revocação são obtidos, um para cada valor de limiar. Cada valor de precisão e revocação então representa um ponto no espaçoPR. A união desses pontos forma uma curvaPR, e a área abaixo dessa curva pode ser calculada. Diferentes métodos podem então ser comparados com base nas áreas abaixo de suas respectivas curvasPR.
Para calcular a área abaixo de uma curvaPR, inicialmente os pontos obtidos com a utilização dos limiares devem ser interpolados (Davis e Goadrich, 2006). Essa interpolação garante que a área abaixo da curva não seja aumentada artificialmente, o que pode acontecer se as curvas forem construídas apenas conectando os pontos sem interpolação. Nesta pesquisa, as curvasPR
foram utilizadas de duas maneiras. Os métodos foram comparados utilizando a área abaixo da curva PRmédia (AU(PRC)), e a média ponderada das áreas abaixo das curvasPRindividuais (por classe) (AUPRCw).
Para verificar a significância estatística dos resultados, foram empregados os testes de Fri- edman e Nemenyi, recomendados para comparações envolvendo vários métodos e muitos con- juntos de dados (Demšar, 2006). O teste de Friedman é um teste não paramétrico, pois não assume nada acerca da distribuição dos dados. Ele é baseado em rankings, e verifica se há di- ferença estatisticamente significante em um grupo de comparações. O teste de Nemenyi é um teste post-hoc aplicado após o teste de Friedman. Ele é utilizado para encontrar quais pares de comparações apresentam diferenças estatisticamente significantes. Nos testes estatísticos, foi utilizado um nível de confiança de 95%. As próximas subseções apresentam o cálculo das medidas AU(PRC) e AUPRCw. Nas equações apresentadas, i varia de 1 até o número total de
classes |C| do problema.
Área abaixo da curva PR média
Dado um valor de limiar, um ponto precisão-revocação (Prec, Rec) no espaçoPRé obtido por meio das Equações6.1 e6.2. Essas equações correspondem às micro médias da precisão e da revocação, e assim como as medidas de Precisão e Revocação Hierárquicas propostas em
(Kiritchenko et al.,2005), consideram os relacionamentos hierárquicos entre as classes, ou seja,
consideram que um exemplo pertence não apenas a uma classe, mas também a todas as classes ancestrais dessa classe na estrutura hierárquica. Nessas equações, i varia de 1 até o número total de classes |C| do problema. Prec = P iVPi P iVPi+ PiFPi (6.1) Rec = P iVPi P iVPi+ PiFNi (6.2)
Média ponderada das áreas abaixo das curvas PR individuais
Para calcular a média ponderada das áreas abaixo das curvasPR individuais, primeiro são calculadas as áreas abaixo das curvas PR individuais obtidas em cada classe do problema (AUPRCi). A média ponderada dessas áreas é então obtida por meio da Equação6.3.
AUPRCw =
X
i
wi·AUPRCi (6.3)
Na Equação (6.3), wi é utilizado para ponderar a contribuição de cada classe de acordo sua
frequência, ou seja, wi =vi/Pjvj, sendo via frequência da classe cino conjunto de dados (Vens
et al.,2008). A ideia aqui é que as classes mais frequentes sejam consideradas mais importantes.
Além das curvas PR terem sido escolhidas pelo fato de permitirem uma avaliação inde- pendente de limiares, elas foram escolhidas também porque as Equações6.1 e 6.2 podem ser aplicadas diretamente a qualquer tipo de hierarquia, tanto estruturada como árvore ou grafo, e também podem ser utilizadas diretamente na avaliação de qualquer tipo de classificador, tanto local ou global, e que utilize qualquer tipo de estratégia de classificação, obrigatória ou não obrigatória em nós-folha (Silla e Freitas, 2010). Além disso, experimentos preliminares desta tese mostraram que não existe nenhuma desvantagem na utilização das medidas de precisão e revocação, e que essas medidas são consistentes com outras medidas da literatura, possuindo a vantagem de não dependerem de nenhum parâmetro fornecido por usuários (Cerri et al.,2013).