LeandroAntonioPasa-TESE

Prévia do material em texto

UNIVERSIDADE DO RIO GRANDE DO NORTEFEDERAL
UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE
CENTRO DE TECNOLOGIA
PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA E
DE COMPUTAÇÃO
Contribuição ao Estudo de Fusão de Mapas
Auto Organizáveis de Kohonen com Ponderação
por meio de Índices de Validação de
Agrupamentos
Leandro Antonio Pasa
Orientador: Prof. Dr. José Alfredo Ferreira Costa
Tese de Doutorado apresentada ao Pro-
grama de Pós-Graduação em Engenharia
Elétrica e da Computação da UFRN (área de
concentração: Engenharia de Computação)
como parte dos requisitos para obtenção do
título de Doutor em Ciências.
Número de ordem PPgEEC: D163
Natal, RN, Fevereiro de 2016.
Seção de Informação e Referência
Catalogação da publicação na fonte. UFRN / Biblioteca Central Zila Mamede
Pasa, Leandro Antonio.
Contribuição ao Estudo de Fusão de Mapas Auto Organizáveis de Kohonen
com Ponderação por meio de Índices de Validação de Agrupamentos / Leandro
Antonio Pasa. - Natal, 2016.
95 f.: il.
Orientador: José Alfredo Ferreira Costa.
Tese (Doutorado em Engenharia Elétrica e de Computação) - Universidade
Federal do Rio Grande do Norte. Centro de Tecnologia - Programa de Pós-
Graduação em Engenharia Elétrica e de Computação.
1. Comitês de máquinas - Tese. 2. Mapas auto-organizáveis de Kohonen -
Tese. 3. Índice de validação de agrupamentos - Tese. I. Costa, José Alfredo
Ferreira. II. Título.
RN/UF/BCZM CDU 621.3:004
Contribuição ao Estudo de Fusão de Mapas
Auto Organizáveis de Kohonen com Ponderação
por meio de Índices de Validação de
Agrupamentos
Leandro Antonio Pasa
Tese de Doutorado aprovada em 19 de fevereiro de 2016 pela banca examinadora com-
posta pelos seguintes membros:
Este trabalho é dedicado à querida
Carine e ao querido Eduardo.
Agradecimentos
A Deus, pela força e iluminação sempre presentes em nossas vidas.
A minha esposa Carine, pelo apoio, amor, paciência e compreensão durante a realização
deste trabalho.
À minha família, pelo apoio durante esta jornada, principalmente à minha mãe Teresinha
(sempre presente) e ao meu pai Evaristo, que sempre incentivaram os seus filhos a estudar.
Ao meu orientador, Professor José Alfredo Ferreira Costa, pela amizade e por comparti-
lhar seus conhecimentos, me orientando neste caminho.
Ao amigo Marcial Guerra de Medeiros, pela amizade, estímulo, contribuições fundamen-
tais e todo o tempo dedicado para auxiliar neste trabalho.
Ao amigo Fábio Augusto Procópio de Paiva, pela amizade e pelas sugestões para este
trabalho.
À Universidade Tecnológica Federal do Paraná, pelo apoio e tempo concedidos para a
realização deste trabalho.
Resumo
A quantidade de informações coletadas e armazenadas cresce a cada dia nas mais
diversas áreas do conhecimento e técnicas de mineração de dados são aplicadas a estes
conjuntos de dados com o objetivo de extrair conhecimento útil. A utilização de um ou
outro algoritmo, ou o mesmo algoritmo com diferentes atributos pode levar a diferentes
resultados, devido à diversidade dos conjuntos de dados. Na busca por soluções eficientes
para este problema, foram desenvolvidos métodos de comitês de máquinas. Um comitê
de máquinas é um conjunto de redes neurais trabalhando independentemente cujos resul-
tados são combinados em uma única saída, alcançando uma melhor generalização do que
cada uma das redes trabalhando separadamente. A proposta deste trabalho é desenvolver
um novo método para comitês de mapas de Kohonen, em que a combinação (fusão) dos
mapas seja ponderada por índices de validação de agrupamentos, que seja válido para
combinação de mapas de tamanhos iguais e mapas de tamanhos diferentes. O algoritmo
proposto foi testado em variados conjuntos de dados provenientes do repositório UCI e
do Conjunto de Problemas Fundamentais de Agrupamento. As simulações computaci-
onais demonstram que o método proposto neste trabalho é capaz de alcançar resultados
promissores, conseguindo elevar a performance em comparação com um único mapa de
Kohonen.
Palavras-chave: Comitês de máquinas, Mapas auto-organizáveis de Kohonen, Índice
de validação de agrupamentos.
Abstract
The amount of collected and stored information is growing every day in several areas
of knowledge and data mining techniques are applied to these datasets in order to extract
useful knowledge. One or another algorithm, or the same algorithm with different attri-
butes, can lead to different results due to the dataset diversity. To solve this problem,
machines committees methods were developed. A machine committee is a set of neural
networks working independently and the results are combined into a single output, achi-
eving a better generalization. The purpose of this work is to develop a new method for
Kohonen maps ensemble, where the maps fusion is weighted by cluster validation indi-
ces and is suitable for equal size maps fusion and for different size maps fusion. The
proposed algorithm has been tested in multiple data sets from the UCI Machine Learning
Repository and Fundamental Clustering Problems Suite. Computer simulations show the
proposed method is able to reach encouraging results, obtaining raising performance com-
pared with a single Kohonen map.
Keywords: Machine committee, Kohonen Self Organizing Maps, Cluster validity
index.
Sumário
Sumário i
Lista de Figuras iii
Lista de Tabelas v
List of Algorithms vi
1 Introdução 1
1.1 Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Organização do documento . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Fundamentação Teórica 5
2.1 Mapas Auto-organizáveis de Kohonen . . . . . . . . . . . . . . . . . . . 5
2.1.1 Treinamento do Mapa . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Índices de Validação . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.1 O índice de Dunn . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2.2 O índice de Calinski e Harabasz . . . . . . . . . . . . . . . . . . 9
2.2.3 O índice Davies-Bouldin . . . . . . . . . . . . . . . . . . . . . . 10
2.2.4 O índice PBM . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.5 O índice CDbw . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3 Modificação de índices de validação . . . . . . . . . . . . . . . . . . . . 14
2.4 Comitês de máquinas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4.1 Construção de um comitê de máquinas . . . . . . . . . . . . . . 16
2.4.2 Algumas aplicações de comitês de máquinas . . . . . . . . . . . 18
2.5 Resumo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3 Materiais e Métodos 21
3.1 Fusão de mapas de tamanhos iguais . . . . . . . . . . . . . . . . . . . . 21
3.1.1 Seleção e dos candidatos . . . . . . . . . . . . . . . . . . . . . . 22
i
3.1.2 Equações de fusão . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.1.3 Experimento fatorial . . . . . . . . . . . . . . . . . . . . . . . . 24
3.1.4 Abordagens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.1.5 Algoritmo proposto . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2 Fusão de mapas de tamanhos diferentes . . . . . . . . . . . . . . . . . . 27
3.2.1 Estrutura com 7 mapas . . . . . . . . . . . . . . . . . . . . . . . 28
3.2.2 Estrutura com 49 mapas . . . . . . . . . . . . . . . . . . . . . . 30
3.2.3 Validação Cruzada . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3 Medida de performance . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.4 Teste estatístico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.5 Resumo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4 Resultados 37
4.1 Conjunto de dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 Mapas de tamanhos iguais . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3 Mapas de tamanhos diferentes . . . . . . . . . . . . . . . . . . . . . . . 44
4.3.1 Estrutura com7 mapas . . . . . . . . . . . . . . . . . . . . . . . 44
4.3.2 Estrutura com 49 mapas . . . . . . . . . . . . . . . . . . . . . . 51
4.3.3 Estrutura de fusão com validação cruzada . . . . . . . . . . . . . 58
4.4 Resumo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5 Conclusão 63
5.1 Considerações finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.1.1 Mapas de tamanhos iguais . . . . . . . . . . . . . . . . . . . . . 64
5.1.2 Mapas de tamanhos diferentes . . . . . . . . . . . . . . . . . . . 64
5.2 Trabalhos futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.3 Publicações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
Referências bibliográficas 67
Apêndice A Conjuntos de dados utilizados 73
Apêndice B Trabalhos publicados 75
Lista de Figuras
2.1 Diagrama esquemático bidimensional da Rede de Kohonen. (Mattos, 2011) 6
2.2 Atualização do BMU e vizinhos. (Vesanto, 2002) . . . . . . . . . . . . . 7
2.3 Diagrama do cálculo do índice de Dunn. . . . . . . . . . . . . . . . . . . 9
2.4 Diagrama do cálculo do índice Davies-Bouldin. . . . . . . . . . . . . . . 10
2.5 Estrutura de um comitê de méquinas. (Coelho, 2006) . . . . . . . . . . . 15
3.1 Visão geral do processo. . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2 Seleção e combinação dos mapas. . . . . . . . . . . . . . . . . . . . . . 23
3.3 Estrutura do experimento fatorial. . . . . . . . . . . . . . . . . . . . . . 24
3.4 Abordagens para a fusão dos mapas. . . . . . . . . . . . . . . . . . . . . 25
3.5 Estrutura com 7 mapas. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.6 Estrutura com 49 mapas. . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.1 Acurácia média para mapas de tamanhos iguais. . . . . . . . . . . . . . . 41
4.2 Acurácia para mapas iguais - BC Wisconsin. . . . . . . . . . . . . . . . . 42
4.3 Acurácia para mapas iguais - Chainlink. . . . . . . . . . . . . . . . . . . 42
4.4 Acurácia para mapas iguais - Column. . . . . . . . . . . . . . . . . . . . 42
4.5 Acurácia para mapas iguais - Engytime. . . . . . . . . . . . . . . . . . . 42
4.6 Acurácia para mapas iguais - Heart. . . . . . . . . . . . . . . . . . . . . 43
4.7 Acurácia para mapas iguais - Ionosphere. . . . . . . . . . . . . . . . . . 43
4.8 Acurácia para mapas iguais - Iris. . . . . . . . . . . . . . . . . . . . . . . 43
4.9 Acurácia para mapas iguais - Lsun. . . . . . . . . . . . . . . . . . . . . . 43
4.10 Acurácia para mapas iguais - Pimaindians. . . . . . . . . . . . . . . . . . 43
4.11 Acurácia para mapas iguais - Seeds. . . . . . . . . . . . . . . . . . . . . 43
4.12 Acurácia para mapas iguais - Tetra. . . . . . . . . . . . . . . . . . . . . . 44
4.13 Acurácia para mapas iguais - Wine. . . . . . . . . . . . . . . . . . . . . 44
4.14 Acurácia para mapas iguais - Two diamonds. . . . . . . . . . . . . . . . 44
4.15 Acurácia para mapas iguais - Wingnut. . . . . . . . . . . . . . . . . . . . 44
4.16 Acurácia para 7 mapas diferentes - BC Wisconsin. . . . . . . . . . . . . . 49
4.17 Acurácia para 7 mapas diferentes - Chainlink. . . . . . . . . . . . . . . . 49
iii
4.18 Acurácia para 7 mapas diferentes - Column. . . . . . . . . . . . . . . . . 49
4.19 Acurácia para 7 mapas diferentes - Engytime. . . . . . . . . . . . . . . . 49
4.20 Acurácia para 7 mapas diferentes - Heart. . . . . . . . . . . . . . . . . . 50
4.21 Acurácia para 7 mapas diferentes - Hepatitis. . . . . . . . . . . . . . . . 50
4.22 Acurácia para 7 mapas diferentes - Ionosphere. . . . . . . . . . . . . . . 50
4.23 Acurácia para 7 mapas diferentes - Iris. . . . . . . . . . . . . . . . . . . 50
4.24 Acurácia para 7 mapas diferentes - Lsun. . . . . . . . . . . . . . . . . . . 50
4.25 Acurácia para 7 mapas diferentes - PimaIndians. . . . . . . . . . . . . . . 50
4.26 Acurácia para 7 mapas diferentes - Seeds. . . . . . . . . . . . . . . . . . 51
4.27 Acurácia para 7 mapas diferentes - Tetra. . . . . . . . . . . . . . . . . . 51
4.28 Acurácia para 7 mapas diferentes - Two Diamonds. . . . . . . . . . . . . 51
4.29 Acurácia para 7 mapas diferentes - Wine. . . . . . . . . . . . . . . . . . 51
4.30 Acurácia para 7 mapas diferentes - Wingnut. . . . . . . . . . . . . . . . . 51
4.31 Acurácia para 49 mapas diferentes - BC Wisconsin. . . . . . . . . . . . . 56
4.32 Acurácia para 49 mapas diferentes - Chainlink. . . . . . . . . . . . . . . 56
4.33 Acurácia para 49 mapas diferentes - Column. . . . . . . . . . . . . . . . 56
4.34 Acurácia para 49 mapas diferentes - Engytime. . . . . . . . . . . . . . . 56
4.35 Acurácia para 49 mapas diferentes - Heart. . . . . . . . . . . . . . . . . . 57
4.36 Acurácia para 49 mapas diferentes - Hepatitis. . . . . . . . . . . . . . . . 57
4.37 Acurácia para 49 mapas diferentes - Ionosphere. . . . . . . . . . . . . . . 57
4.38 Acurácia para 49 mapas diferentes - Iris. . . . . . . . . . . . . . . . . . . 57
4.39 Acurácia para 49 mapas diferentes - Lsun. . . . . . . . . . . . . . . . . . 57
4.40 Acurácia para 49 mapas diferentes - PimaIndians. . . . . . . . . . . . . . 57
4.41 Acurácia para 49 mapas diferentes - Seeds. . . . . . . . . . . . . . . . . 58
4.42 Acurácia para 49 mapas diferentes - Tetra. . . . . . . . . . . . . . . . . . 58
4.43 Acurácia para 49 mapas diferentes - Two Diamonds. . . . . . . . . . . . 58
4.44 Acurácia para 49 mapas diferentes - Wine. . . . . . . . . . . . . . . . . . 58
4.45 Acurácia para 49 mapas diferentes - Wingnut. . . . . . . . . . . . . . . . 58
4.46 Acurácia com validação cruzada estratificada. . . . . . . . . . . . . . . . 61
A.1 Conjunto de dados UCI. . . . . . . . . . . . . . . . . . . . . . . . . . . 73
A.2 Conjunto de dados do FCPS. (Ultsch, 2005) . . . . . . . . . . . . . . . . 74
Lista de Tabelas
4.1 Conjuntos de dados utilizados. . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 Resultados da fusão de mapas de tamanhos iguais . . . . . . . . . . . . . 40
4.3 Resultados da fusão de 7 mapas com a Equação 3.1 . . . . . . . . . . . . 46
4.4 Resultados da fusão de 7 mapas com a Equação 3.2 . . . . . . . . . . . . 47
4.5 Resultados da fusão de 7 mapas com a Equação 3.3 . . . . . . . . . . . . 48
4.6 Resultados das fusões para os 49 mapas com a Equação 3.1 . . . . . . . . 53
4.7 Resultados das fusões para os 49 mapas com a Equação 3.2 . . . . . . . 54
4.8 Resultados das fusões para os 49 mapas com a Equação 3.3 . . . . . . . . 55
4.9 Resultados para a validação cruzada estratificada . . . . . . . . . . . . . 60
v
Lista de Algoritmos
1 FUSÃO DE MAPAS DE TAMANHOS IGUAIS . . . . . . . . . . . . . . . . . 26
2 FUSÃO DE 7 MAPAS DE TAMANHOS DIFERENTES . . . . . . . . . . . . . 29
3 FUSÃO DE 49 MAPAS DE TAMANHOS DIFERENTES . . . . . . . . . . . . 31
4 FUSÃO ATRAVÉS DA VALIDAÇÃO CRUZADA . . . . . . . . . . . . . . . . 33
5 TESTE DE WILCOXON . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
vii
Capítulo 1
Introdução
Em várias áreas do conhecimento, cresce a cada dia a quantidade de informações
coletadas e armazenadas e devido ao volume e dimensionalidade, estes dados acabam
ficando sem uma análise e interpretação adequadas.
A diversidade de características dos conjuntos de dados pode fazer com que a utiliza-
ção de um ou outro algoritmo de agrupamento, ou o mesmo algoritmo, mas com diferen-
tes atributos, resulte em diferentes resultados. O aumento do desempenho de sistemas de
classificação, agrupamentos e análise de dados é uma busca constante em Mineração de
Dados e áreas correlatas.
Algoritmos novos ou variações de algoritmos já existentes são publicados na litera-
tura constantemente. Algoritmos não supervisionados são empregados quando não há um
conhecimento prévio sobre a estrutura e a distribuição do conjunto de dados. Dentre os
algoritmos não supervisionados, destaca-se a Rede de Kohonen, com aprendizado com-
petitivo e não supervisionado, capaz de projetar um mapa bidimensional de um conjunto
multidimensional de dados, preservando as relações topológicas destes dados.
Na buscapor soluções eficientes na exploração do conhecimento embutido nas massas
de dados, foram criados métodos de comitês de máquinas (ensemble), onde combinam-
se os resultados de várias redes neurais artificiais em um só. Esta abordagem tem sido
muito explorada, pois trata-se de uma técnica simples e que pode aumentar o poder de
generalização das redes neurais.
A combinação de múltiplos componentes é vantajosa, uma vez que componentes di-
ferentes podem implicitamente representar aspectos distintos e, ao mesmo tempo, rele-
vantes para a solução de um dado problema. Esta técnica é capaz de fornecer um melhor
resultado do que cada componente individualmente.
Duas características são fundamentais para o bom desempenho de um comitê de má-
quinas: diversidade de resultados e erros descorrelacionados dos componentes. É preciso
que os componentes do comitê apresentem resultados diferentes, pois de nada adianta
2 CAPÍTULO 1. INTRODUÇÃO
combinar soluções iguais. Também é necessário que os erros apresentados pelos compo-
nentes sejam independentes uns dos outros, pois não há ganho para o comitê se os todos
os componentes, por exemplo, errarem a mesma classificação de um padrão de entrada.
Para os mapas auto-organizáveis de Kohonen (Kohonen Self-Organizing Maps - SOM)
(Kohonen, 1982), erros descorrelacionados podem ser obtidos, por exemplo, utilizando
diferentes conjuntos de treinamento ou variando parâmetros de treinamento para cada
rede neural. A combinação das saídas dos mapas SOM em uma única saída pode ser feita
a partir da fusão dos neurônios dos mapas que compõem o comitê de máquinas.
1.1 Motivação
Tanto a abordagem de comitês de máquinas quanto o uso de Mapas Auto Organi-
záveis de Kohonen têm sido muito explorados nos últimos anos. Comitês de máquinas
são relativamente simples em seu conceito e complexos em sua implementação, mas são
capazes de aumentar a capacidade de generalização de um modelo. As Redes de Koho-
nen trabalham com dados multidimensionais, projetando-os em um mapa bidimensional,
preservando a topologia dos dados.
A motivação deste trabalho é desenvolver um novo método para combinação de mapas
de Kohonen que empregue a ponderação por índices de validação de agrupamentos, com
o objetivo de aumentar a acurácia desse método em relação a uma única rede de Kohonen.
1.2 Objetivos
A proposta deste trabalho é apresentar um método para fusão de Mapas de Kohonen
por meio de comitês de máquinas e com ponderação por índices de validação de agrupa-
mentos.
Os objetivos específicos desta pesquisa são:
1. Propor uma metodologia para implementar o comitê de máquinas de mapas de
Kohonen de tamanhos iguais e de tamanhos diferentes;
2. Verificar a influência da quantidade de hits e BMUs no resultado final do comitê de
máquinas;
3. Verificar a eficácia em empregar índices de validação de agrupamentos na seleção
de componentes do comitê de máquinas.
1.3. ORGANIZAÇÃO DO DOCUMENTO 3
1.3 Organização do documento
Este documento está organizado da seguinte forma: no Capítulo 1 é apresentada uma
breve descrição da proposta desta tese, bem como os aspectos que motivaram o seu de-
senvolvimento e os objetivos. No Capítulo 2 os conceitos principais que serão utilizados
neste trabalho são descritos e são apresentados alguns trabalhos relacionados. No Capí-
tulo 3 é apresentada a proposta para a fusão de mapas de Kohonen de tamanhos iguais e de
tamanhos diferentes. No Capítulo 4 são apresentados os resultados obtidos na aplicação
dos algoritmos propostos para a fusão de mapas de Kohonen. Por fim, no Capítulo 5 são
apresentadas as conclusões e os trabalhos futuros.
4 CAPÍTULO 1. INTRODUÇÃO
Capítulo 2
Fundamentação Teórica
Neste capítulo são apresentados os conceitos utilizados no desenvolvimento deste tra-
balho. Uma visão geral sobre mapas auto organizáveis de Kohonen é vista na Seção 2.1.
Já na Seção 2.2, são apresentadas descrições simplificadas de alguns índices de validação
e na Seção 2.3 temos a modificação dos índices de validação modificados para uso com o
SOM. Ao final, na Seção 2.4 temos uma introdução aos métodos de comitês de máquinas.
2.1 Mapas Auto-organizáveis de Kohonen
Os mapas auto-organizáveis de Kohonen (Self-Organizing Maps - SOM) (Kohonen,
1982) tornaram-se um modelo de rede neural muito popular. Constituem uma rede neural
artificial, com aprendizado competitivo e não supervisionado, que realiza uma projeção
não-linear de um espaço de entrada ℜp, sendo p >> 2, em uma grade de neurônios dis-
postos em um arranjo, normalmente, bidimensional, tendo apenas duas camadas: uma de
entrada de dados e outra de saída de dados.
As entradas da rede x são vetores no espaço p-dimensional. Os neurônios i da camada
de saída são conectados a todas as entradas da rede, representados por um vetor de pesos
sinápticos no espaço p-dimensional, wi = [wi1,wi2, ...,wip]T . Estes neurônios são conec-
tados aos neurônios adjacentes por uma relação de vizinhança que descreve a estrutura
topológica do mapa. A Figura 2.1 mostra um diagrama representativo da arquitetura da
Rede de Kohonen.
Na fase de treinamento, em uma sequência aleatória, os padrões de entrada x são
comparados com os neurônios da camada de saída. O neurônio vencedor, chamado de
BMU (Best Match Unit), representa o vetor peso com a menor distância, usualmente a
Euclidiana, em relação ao padrão de entrada x.
Chamando o neurônio vencedor de c, ele pode ser formalmente definido de acordo
com a Equação 2.1.
6 CAPÍTULO 2. FUNDAMENTAÇÃO TEÓRICA
Figura 2.1: Diagrama esquemático bidimensional da Rede de Kohonen. (Mattos, 2011)
‖x−wc‖= argmini‖x−wi‖ (2.1)
Os pesos do neurônio vencedor são ajustados de acordo com a Equação 2.2, junta-
mente com os pesos dos neurônios vizinhos.
wi (t +1) = wi (t)+α(t)hci (t) [x(t)−wi (t)] (2.2)
Onde t indica a iteração (ou época), x(t) é o padrão de entrada, hci(t) é a função de
vizinhança, centrada no neurônio vencedor ix, enquanto que α(t) é a taxa de aprendizado,
com valores entre 0 e 1.
Na Figura 2.2 é ilustrado o processo de atualização de pesos do neurônio vencedor e
sua vizinhança. As linhas sólidas correspondem à situação antes da atualização dos pesos
e as linhas tracejadas mostram a mudança devido à aproximação do BMU e seus vizinhos
do padrão de entrada x. Os círculos escuros e claros representam, respectivamente, os
neurônios antes e depois do ajuste dos pesos.
2.1.1 Treinamento do Mapa
São duas as maneiras de treinamento de um Mapa de Kohonen: treinamento se-
quencial e treinamento em lote. O processo de treinamento sequencial dos mapas auto-
organizáveis consiste em três etapas, segundo Haykin (2001):
1. Competição: a cada padrão de entrada que é apresentado para a rede, os neurônios
da camada de saída competem entre si, (esta competição é baseada em uma medida
de similaridade), Geralmente a menor distância euclidiana entre os pesos sinápticos
dos neurônios e o padrão de entrada determinará o único vencedor (BMU).
2.1. MAPAS AUTO-ORGANIZÁVEIS DE KOHONEN 7
Figura 2.2: Atualização do BMU e vizinhos. (Vesanto, 2002)
2. Cooperação: escolhido o neurônio vencedor, este torna-se o centro de uma vizi-
nhança topológica de neurônios excitados.
3. Adaptação: os neurônios da vizinhança topológica determinada na fase de coo-
peração têm seus pesos sinápticos ajustados, de maneira que os neurônios mais
próximos ao BMU sofrem ajustes maiores do que os neurônios mais distantes.
A função gaussiana é utilizada para descrever a influência do BMU sobre seus vizi-
nhos (atualização dos pesos sinápticos), pois apresenta um significado biológico coerente:
o neurônio ativado tende a excitar com maior intensidade os neurônios na sua vizinhança
imediata e decai suavemente com a distância lateral (Haykin, 2001). A Equação 2.3 mos-
tra como é calculada a excitação do neurônio j, em relação ao neurônio vencedor i, sendo
d ji a distância entre eles (normalmente, a distância euclidiana é utilizada).
hi j = exp
(
−
d2i j
2σ2
)
(2.3)
Com o fim do processo de aprendizagem, os vetores de código do SOMconstituem
uma aproximação não-linear dos padrões de entrada. O processo busca manter a preser-
vação topológica dos padrões, isto é, padrões próximos no conjunto de entrada da rede
permanecerão relacionados a neurônios próximos na grade de saída.
O processo de treinamento em lote difere do treinamento sequencial por apresentar
todos os vetores de entrada para a rede. de uma única vez. Assim, não é necessário o
parâmetro taxa de aprendizagem, α(t), da Equação 2.2 e também não se faz necessária
aleatoriedade para a apresentação dos vetores de entrada.
Na próxima seção, serão apresentados os índices de validação de agrupamentos utili-
zados como ponderação na fusão dos mapas de Kohonen.
8 CAPÍTULO 2. FUNDAMENTAÇÃO TEÓRICA
2.2 Índices de Validação
Devido às diferentes geometrias e dimensionalidades dos conjuntos de dados, não
existe um algoritmo único que possa agrupar, de forma não supervisionada, um conjunto
de dados qualquer. Os índices de validação são necessários para avaliar e validar os
resultados destes algoritmos de agrupamentos, auxiliando na tomada de decisão quanto à
definição da quantidade correta, ou natural, de grupos formados a partir de um conjunto
de dados.
Existe, na literatura, uma variedade muito grande de índices de validação de agrupa-
mentos, cada um com características próprias para aplicação em conjuntos de dados com
determinadas características. Alguns aplicam-se à conjuntos de dados que apresentam boa
separação entre os agrupamentos, outros se destinam a dados de alta dimensionalidade,
outros não apresentam boa resposta na presença de ruídos. Para cada tipo de aplicação,
um método para validar os agrupamentos foi desenvolvido.
Na validação de agrupamentos podem ser abordados três critérios: o externo, o interno
e o relativo (Theodoridis e Koutroumbas, 2009).
No critério externo a estrutura dos grupos é avaliada em termos de uma estrutura
independente, imposta ao conjunto de dados a priori.
No critério interno a estrutura dos grupos é avaliada em base em informações estatís-
ticas dos dados de cada grupo (por exemplo, a matriz de proximidade).
No critério relativo a estrutura dos grupos é avaliada por comparação com outras es-
truturas de agrupamentos, resultantes da aplicação do mesmo algoritmo (mas com parâ-
metros com diferentes valores), ou comparada com outros algoritmos de agrupamentos.
Como exemplos de índices de validação que utilizam critérios relativos, temos: o
índice de Dunn, o índice de Calinski e Harabasz o índice Davies-Bouldin, o índice PBM
e o índice CDbw. Nas seções 2.2.1, 2.2.3 e 2.2.5 estes índices serão explicados.
2.2.1 O índice de Dunn
O índice de Dunn (Dunn, 1973) é calculado pela razão entre a mínima distância entre
dois pontos pertencentes a dois diferentes grupos (δ(Ci,C j)) e a máxima distância entre
dois pontos pertencentes ao mesmo grupo (∆(Ck)), como ilustra a Figura 2.3. É adequado
para conjunto de dados que possuam grupos compactos e bem separados. É sensível a
ruídos, pois eles interferem no cálculo do diâmetro do grupo, e seu custo computacional
é elevado.
2.2. ÍNDICES DE VALIDAÇÃO 9
Figura 2.3: Diagrama do cálculo do índice de Dunn.
Fonte: Elaborada pelo autor.
O seu cálculo é mostrado na Equação 2.4
D = min
1≤i≤c
{
min
1≤ j≤c,i 6= j
{
δ(Ci,C j)
max1≤k≤c ∆(Ck)
}}
(2.4)
No artigo de Bezdec (Bezdek e Pal, 1998) são propostas generalizações do Índice de
Dunn, para melhor adequação às diferentes geometrias dos agrupamentos. Estas generali-
zações são obtidas pelas variações nos cálculos dos diâmetros dos grupos e das distâncias
entre grupos.
Valores elevados para o Índice de Dunn indicam a existência de grupos compactos
(diâmetro pequeno) e bem separados (distâncias grandes entre os grupos).
2.2.2 O índice de Calinski e Harabasz
O índice de Calinski e Harabasz (Calinski e Harabasz, 1974) avalia a quantidade de
grupos presentes em um conjunto de dados por meio de medidas de dispersão entre e intra
grupos. O seu cálculo é mostrado na Equação 2.5.
CH(k) =
B(k)/(k−1)
W (k)(n− k)
(2.5)
Onde:
• k indica a quantidade de grupos no conjunto de dados.
• n é a quantidade de pontos no conjunto.
• B(k) é a dispersão entre os grupos.
• W (k) é a soma das dispersões intra-grupos.
O número de ótimo de grupos é o valor de k que maximiza a função 2.5.
10 CAPÍTULO 2. FUNDAMENTAÇÃO TEÓRICA
2.2.3 O índice Davies-Bouldin
O índice Davies-Bouldin (Davies e Bouldin, 1979) é uma função da razão entre a
soma da dispersão interna dos grupos e a separação entre eles. Na Figura 2.4, as linhas
vermelhas no interior do grupo Ci, ilustram a dispersão interna, enquanto a linha verde
que une os centroides dos grupos Ci e C j representa a separação entre eles.
Figura 2.4: Diagrama do cálculo do índice Davies-Bouldin.
Fonte: Elaborada pelo autor.
A dispersão interna de um grupo é dada pela Equação 2.6:
S (Ci) =
1
c ∑
c∈Ci
‖x− ci‖ (2.6)
Onde:
• c indica a quantidade de elementos do grupo.
• ci representa o centroide do grupo.
• x representa cada ponto do grupo.
• ‖.‖ é a distância Euclidiana.
A separação entre os grupos é dada pela distância Euclidiana entre os centroides dos
grupos, como mostra a Equação 2.7:
δ
(
Ci,C j
)
=
∥∥ci,c j∥∥ (2.7)
Por fim, a Equação 2.8 calcula o índice Davies-Bouldin
DB =
1
k
k
∑
i=1
i6= j
max
S (Ci)+S
(
C j
)
δ
(
Ci,C j
) (2.8)
Onde k é o número de agrupamentos, S representa a dispersão interna do agrupa-
mento (distância intra-grupos), com relação ao centroide e δ corresponde à distância inter-
2.2. ÍNDICES DE VALIDAÇÃO 11
grupos, baseada nos centroides.
Valores pequenos para o Índice Davies-Bouldin indicam grupos compactos cujos cen-
tros estão bem separados entre si. O valor de k que minimiza o índice representará o valor
mais provável do número real de grupos no conjunto de dados. Este índice não depende
do número de grupos no conjunto de dados e nem do algoritmo utilizado para formar estes
grupos.
2.2.4 O índice PBM
O índice PBM (Pakhira et al., 2004), (acrônimo formado pelas iniciais dos autores
Pakhira, Bandyopadhyay and Maulik), baseia-se em compactação de grupos e separação
entre grupos. A compactação é medida pela soma das distâncias entre cada ponto do
grupo e seu centroide. A separação entre os grupos é medida pela máxima distância entre
dois centroides.
PBM(k) =
(
1
k
· E1
Ek
·Dk
)2
(2.9)
Onde:
• k indica a quantidade de grupos.
• E1 é a soma das distâncias entre cada ponto de um grupo e o centroide desse grupo.
• Ek é a soma das distâncias entre cada ponto e o centroide do conjunto de dados.
• Dk é a máxima distância entre dois quaisquer centroides de grupos.
Maximizando este índice, obtem-se o número ótimo de grupos em um conjunto de
dados.
2.2.5 O índice CDbw
Em Halkidi e Vazirgiannis (2008), foi proposto um índice de validação de agrupamen-
tos chamado CDbw (Composing Density Between and With clusters). Este índice CDbw
ajusta-se bem a geometrias não esféricas dos dados por considerar multi-representantes
por grupos e não apenas o centroide, podendo ser aplicado a conjuntos de dados com alta
dimensionalidade. Para um conjunto de dados particionados em c agrupamentos, define-
se um conjunto de pontos representativos Vi = {vi1,vi2, ...,vir} para o agrupamento i,
sendo que r representa o número de pontos de representação do agrupamento i.
Os representantes de cada grupo são assim determinados: na 1a iteração escolhe-se o
ponto mais distante do centro. Nas seguintes iterações escolhe-se o ponto mais distante
12 CAPÍTULO 2. FUNDAMENTAÇÃO TEÓRICA
do ponto escolhido previamente. Isso resulta em um conjunto de pontos r que representa
a periferia, ou contorno, do grupo. O critério de parada é definido empiricamente, ou seja,
escolhe-se previamente o número de representantes de cada grupo (Halkidi e Vazirgiannis,
2008).
Este índice de validação baseia-se na densidade intra-grupos e na separação entre os
grupos, conforme a Equação 2.10.
CDbw(c) = DensIntra(c)×Sep(c) (2.10)
Sendo DensIntra(c) a densidade intra-grupos e Sep(c) a separação entre os grupos. A
densidadeintra-grupos é definida como o número de pontos que pertencem à vizinhança
dos pontos que representam os grupos r. A densidade intra-grupos é alta para grupos bem
separados.
DensIntra(c) =
1
c
c
∑
i=1
1
ri
ri
∑
i=1
density(vi j),c > 1 (2.11)
Onde:
• c é o número de grupos.
• ri é número de pontos representativos.
• vi j é j-ésima a representação do agrupamento i.
Sendo a densidade:
density(vi j) =
ni
∑
l=1
f (xl,vi j) (2.12)
Onde:
• xl pertence ao i-ésimo agrupamento.
• ri é número de pontos representativos.
• vi j é j-ésima a representação do agrupamento i.
O termo do somatório é definido da seguinte maneira:
f (xl,vi j)i j =
1, se
∥∥xl− vi j∥∥≤ stdev,
0, se caso contrario.
Aqui, stdev corresponde à média dos desvios padrões de cada um dos c agrupamentos
(desvio padrão dos pontos do grupo até o centroide deste grupo).
2.2. ÍNDICES DE VALIDAÇÃO 13
A densidade inter-grupos é definida como a densidade nas áreas entre os grupos. Essa
densidade deve ser baixa quando temos grupos compactos e bem separados.
DensInter(c) =
c
∑
i=1
c
∑
j=1
∥∥close repi− close rep j∥∥
(‖stdev(i)‖+‖stdev( j)‖)
·density(ui j),c > 1 (2.13)
Onde:
• close repi− close rep j representam o par de pontos de representação mais próxi-
mos entre o agrupamento i e j.
• ui j é o ponto médio entre este par de pontos.
Sendo esta densidade:
density(ui j) =
ni+n j
∑
k=1
f (xk,ui j) (2.14)
Sendo xk o vetor de entrada que pertence ao grupo i ou j. Já o termo do somatório é
assim definido:
f (xk,ui j) =
1, se ‖x− v‖ ≤ 12 × (‖stdev(i)‖+‖stdev( j)‖),0, caso contrario.
A separação entre agrupamentos leva em conta a distância inter-grupos e a densidade
inter-grupos.
Sep(c) =
c
∑
i=1
c
∑
j=1
j 6=i
∥∥close repi− close rep j∥∥
1+ Inter den(c)
,c > 1 (2.15)
Assim, o índice de validação de agrupamentos CDbw é dado por pela equação 2.10.
O número ideal de grupos é indicado quando o valor do CDbw atinge o valor máximo,
independente do algoritmo utilizado para o agrupamento dos dados.
Este índice adapta-se bem a grupos com as mais variadas formas geométricas, uma
vez que usa vários vetores representativos para cada grupo e não somente o centroide.
Na seção seguinte será mostrada a modificação no cálculo dos índices de validação de
agrupamentos, adaptados para uso com os mapas de Kohonen, proposto em (Gonçalves,
2009).
14 CAPÍTULO 2. FUNDAMENTAÇÃO TEÓRICA
2.3 Modificação de índices de validação
Devido à alta complexidade computacional exigida no cálculo dos índices de vali-
dação de agrupamentos, Gonçalves (2009) propôs em sua Tese de doutoramento uma
modificação nos cálculos dos índices de validação, para aplicá-los em conjuntos de dados
de imagens de sensoriamento remoto que, por sua natureza, são bastante volumosos.
O autor modificou alguns índices de validação através da quantização vetorial produ-
zida pelo SOM. Assim, não foram utilizados os padrões originais e sim os vetores de pesos
sinápticos dos neurônios do SOM nos cálculos destes índices. Desta forma, diminui-se a
quantidade de dados e, consequentemente, a complexidade computacional para o cálculo
do índice de validação.
Para contornar possíveis diferenças de valores entre o cálculo do índice considerando
todos os dados e considerando apenas os protótipos, o autor também propôs que fossem
utilizados os níveis de atividade conjuntamente com os vetores de pesos sinápticos. O
nível de atividade significa a quantidade de padrões de entrada que foram associados a
cada protótipo pelo processo de mapeamento do SOM.
A modificação proposta no cálculo dos índices pode ser compreendida através de um
exemplo no cálculo de distância entre dois agrupamentos CI e C j:
δi, j =
1
|Ci|
∣∣C j∣∣∑x∈Ci
y∈C j
d (x,y) (2.16)
Na Equação 2.16, d (x,y) é uma medida de distância e |Ci|e
∣∣C j∣∣ referem-se à quanti-
dade de elementos dos grupos Ci e C j, respectivamente.
Quando a quantidade de elementos do grupo é elevada, a complexidade computacio-
nal é elevada. A Equação 2.17 mostra a modificação do cálculo através da metodologia
proposta em (Gonçalves, 2009) :
δ
SOM
i, j =
1
|Ci|
∣∣C j∣∣ ∑wi∈Wi
w j∈Wj
h(wi) ·h
(
w j
)
·d
(
wi,w j
)
(2.17)
Onde Wi e Wj são os conjuntos de protótipos do SOM que representam os grupos Ci
e C j, respectivamente, d (x,y) é a mesma medida de distância da Equação 2.16, h(wi) é
o nível de atividade do protótipo wi pertencente a Wi e h
(
w j
)
é o nível de atividade do
protótipo w j pertencente a Wj.
Assim o cálculo da distância apresenta um custo computacional mais baixo, uma vez
2.4. COMITÊS DE MÁQUINAS 15
que as quantidades envolvidas, Wi e Wj, são menores do que Ci e C j.
Com a inclusão dos níveis de atividades h(.) dos protótipos no cálculo, obtém-se
uma minimização dos erros causados pela quantização vetorial que o Mapa de Kohonen
produz, já que introduz no cálculo a aproximação da densidade de pontos no espaço de
entrada ora representados pelos protótipos.
Na sequência, os comitês de máquinas são introduzidos, abordando aspectos relativos
à geração, seleção e combinação dos componentes destes comitês.
2.4 Comitês de máquinas
Um comitê de máquinas, ou ensemble, pode ser visto como uma coleção de redes
neurais artificiais individuais, que possuem diversidade entre si e que levam à uma maior
capacidade de generalização do que quando trabalhando em separado (Dietterich, 2000).
Cada componente atua independentemente dos outros e gera uma solução que é com-
binada pelo comitê, produzindo uma única saída. A Figura 2.5 mostra a estrutura geral de
um comitê de máquinas.
Figura 2.5: Estrutura de um comitê de méquinas. (Coelho, 2006)
O estudo de comitês de máquinas iniciou com o trabalho de Hansen e Salamon (1990),
combinando redes neurais artificiais, treinadas separadamente, conseguindo melhorar a
capacidade de generalização do sistema.
Um comitê de máquinas baseia-se no princípio de "dividir-para-conquistar", bus-
cando superar o desempenho de uma máquina de aprendizado operando de modo isolado
(Haykin, 2001). Os comitês de máquinas podem ser divididos em dinâmicos e estáticos.
No caso dinâmico, o comitê recebe o nome de mistura de especialistas, onde a di-
visão de tarefas e a síntese dos especialistas são realizadas simultaneamente e de forma
automática pelo algoritmo de aprendizagem (Haykin, 2001).
Nos comitês estáticos cada componente apresenta uma solução para o problema e
estas soluções são agregadas fornecendo um só resultado. Desta forma, há um aumento
16 CAPÍTULO 2. FUNDAMENTAÇÃO TEÓRICA
da capacidade de generalização, diminuição da variância do modelo e maior tolerância à
ruídos quando comparados ao resultado de um único componente (Haykin, 2001).
Um dos requisitos básicos para o bom resultado do comitê de máquinas é que os com-
ponentes generalizem de forma diferente, pois de nada adianta combinar modelos que
adotam os mesmos procedimentos e hipóteses para a solução de um problema, sendo
fundamental que os erros apresentados por cada um dos componentes sejam descorrelaci-
onados (Perrone e Cooper, 1993). Isso pode ser obtido, por exemplo, utilizando diferentes
conjuntos para o treinamento ou variando os parâmetros de treinamento de cada rede neu-
ral que compõe o comitê de máquinas, entre outras maneiras.
2.4.1 Construção de um comitê de máquinas
As etapas da construção de um comitê de máquinas são: geração de componentes,
seleção dos componentes e combinação dos componentes individuais (Villanueva, 2006).
Inicialmente, geram-se os componentes candidatos a participarem do comitê. Na
sequência, selecionam-se os componentes candidatos que irão contribuir realmente para a
melhoria do desempenho do comitê. Por fim, combinam-se as saídas de cada componente
em uma única saída.
Na etapa da geração de componentes é preciso considerar um baixo erro de treina-
mento e uma descorrelação entre os erros de cada componente. Também é necessário
que haja diversidade entre os componentes, para garantir que generalizem de modo dife-
rente. Para garantir que as redes neurais tenham diversidade entresi, pode-se adotar como
estratégias:
• Inicialização aleatória dos pesos para cada componente.
• Variação na arquitetura da rede neural.
• Variação do algoritmo de treinamento.
• Re-amostragem dos dados.
No caso da re-amostragem dos dados duas técnicas são bastante utilizadas: Bagging
e Boosting.
Bagging (Breiman, 1996) é uma técnica de geração de conjuntos distintos de treina-
mento a partir de um único conjunto, através de re-amostragem com reposição.
Por exemplo, considere um único conjunto de treinamento com N amostras, para trei-
nar m componentes. O objetivo é construir m conjuntos de treinamento com N amostras
cada um. Com uma distribuição de probabilidade uniforme para seleção das amostras a
2.4. COMITÊS DE MÁQUINAS 17
partir do conjunto fonte, teremos algumas amostras selecionadas mais de uma vez, pois
há reposição.
Há a possibilidade de os componentes não generalizarem de forma satisfatória, mas
a combinação destes modelos pode resultar em uma generalização melhor do que cada
componente individual.
Boosting (Schapire, 1990) é um método em que os conjuntos de treinamento são ge-
rados através de uma amostragem não uniforme, diferentemente do método Bagging.
A probabilidade de uma dada amostra ser escolhida depende da contribuição desta
para o erro dos componentes já treinados.
Tomando como exemplo um problema de classificação, uma amostra que não seja cor-
retamente classificada pelos componentes já treinados terá uma maior probabilidade de
ser selecionada do que uma amostra que seja corretamente classificada. Assim, esta amos-
tra terá uma chance maior de compor o conjunto de treinamento do próximo componente
a ser treinado.
Um dos problemas desta técnica é a necessidade de treinamento sequencial dos com-
ponentes do comitê, uma vez que as probabilidades devem ser redefinidas de acordo com
o comportamento dos componentes já treinados.
A versão mais popular do algoritmo de Boosting é chamada AdaBoost, na qual cada
componente é treinado sequencialmente e a distribuição dos dados de treinamento é feita
levando-se em consideração os erros do componente treinado no passo imediatamente
anterior.
Considerando a etapa da seleção de componentes, pode ser que nem todos os com-
ponentes contribuam para o desempenho global do comitê. Assim, é preciso identificar
e descartar estes componentes, uma vez que a inclusão de todos eles no comitê pode
degradar sua performance (Zhou et al., 2002).
Uma maneira de selecionar os componentes é através de alguma medida de erro, por
exemplo. Dois são os métodos mais citados na literatura para seleção de componentes: o
construtivo e o da poda.
O método construtivo pode ser descrito desta maneira: os M candidatos a comporem
o comitê são ordenados com base em algum critério, por exemplo medida de erro, que irá
mensurar o desempenho individual de cada componente. O que tiver melhor desempenho
individual é inserido no comitê. O próximo candidato (o de segundo melhor desempenho
individual), é adicionado ao comitê. Se o desempenho do comitê de máquinas melhorar,
o comitê passa a ter dois componentes. Caso contrário, o elemento recém-inserido é
removido. Este processo se repete então para todos os demais candidatos restantes na
lista ordenada gerada inicialmente.
18 CAPÍTULO 2. FUNDAMENTAÇÃO TEÓRICA
O método da poda funciona de modo oposto ao método construtivo. Os M candida-
tos também são ordenados a partir de seu desempenho individual em relação à medida de
erro, por exemplo. Todos os candidatos são inseridos no comitê. O candidato com pior
performance individual é removido e o comitê de máquinas tem seu desempenho avaliado
novamente. Se ocorrer uma melhora de seu desempenho em relação à configuração an-
terior, o comitê passa a contar então com M-1 componentes. Senão, o candidato retirado
volta ao comitê e o processo se repete para os demais candidatos, exceto o de melhor
desempenho individual, que nunca é removido do comitê de máquinas.
A seleção de componentes é realizada basicamente para maximizar a generalização
do modelo, descartando componentes que não contribuam para o desempenho do comitê.
De acordo com Greene et al. (2004), a diversidade entre os componentes é necessária,
porém não é suficiente para gerar uma solução melhor do que um único componente se
não for utilizado um método de integração adequado para combinar estes componentes.
De acordo com Villanueva (2006), a combinação dos componentes para obter o re-
sultado final do comitê de máquinas pode ser baseada em técnicas de votação simples,
para tarefas de classificação de dados ou média simples ou ponderada, para tarefas de
regressão de dados. No caso de agrupamentos de dados, onde não há conhecimento à pri-
ori, uma opção é empregar a matriz de co-associação. Esta combinação dos componentes
é feita através da chamada função consenso. Ela deve ser escolhida cuidadosamente, pois
influencia diretamente o resultado do comitê de máquinas.
2.4.2 Algumas aplicações de comitês de máquinas
É possível encontrar variações nas implementações dos métodos de comitês de má-
quinas e suas aplicações em diversas áreas do conhecimento: Wang (2006) empregou
comitês para a classificação e predição de dados de expressão de genes, para a correta e
confiável classificação de tumores, o que é essencial para o sucesso do tratamento. Outra
aplicação médica é encontrada em Krawczyk et al. (2012), que utilizou comitês para re-
conhecimento não invasivo de fibrose hepática. Greene et al. (2004) também estudou as
técnicas de comitês aplicadas em diagnósticos médicos.
Em Villanueva (2006) e Chitra e Uma (2010) foram empregados comitês de máquinas
para predição de séries temporais, obtendo um ganho significativo quando comparado
com o uso de um único modelo preditor. Curiac e Volosencu (2012) utilizou comitês de
classificadores para detecção de anomalias em redes de sensores sem fio.
Comitês de máquinas também foram aplicados em previsão de tempo, com resultados
satisfatórios (Maqsood et al., 2004).
2.4. COMITÊS DE MÁQUINAS 19
A abordagem de comitês demonstrou ser uma forma eficaz para aumentar a precisão
e robustez de reconstrução de sinal de sensores em uma planta de geração de energia
nuclear (Baraldi et al., 2010).
Em seu trabalho, Coelho (2006), propôs uma metodologia de criação de comitês de
máquinas para problemas de classificação, onde os componentes são redes neurais ar-
tificiais do tipo perceptron multicamadas. Para que fossem gerados bons candidatos a
comporem o comitê, atendendo a critérios de desempenho e de diversidade, foi aplicada
uma meta-heurística populacional imuno-inspirada, caracterizada por definir automati-
camente o número de indivíduos na população a cada iteração, promover diversidade e
preservar ótimos locais ao longo da busca. Os resultados obtidos indicam a validade da
metodologia de criação de comitês de máquinas.
Em Naldi (2011), o autor investigou as técnicas de combinação de agrupamentos,
através de algoritmos evolutivos e de índices de validação aplicadas na seleção de agru-
pamentos para combinação e na mineração distribuída de dados, conseguindo partições
de boa qualidade e com bom desempenho computacional.
No trabalho de Ferreira (2012), o método para construção de comitês é baseado em
rotação, que utiliza a técnica de extração de características da análise de componentes
principais (PCA) como artifício para rotacionar os eixos formados pelos subgrupos de
atributos para construção de comitês diversos e acurados.
Até aqui foram relatados alguns trabalhos utilizando a técnica de comitês de máquinas,
para demonstrar a diversidade e exito na aplicação desta técnica em diversas áreas do
conhecimento. Neste trabalho são empregados comitês de Mapas de Kohonen. A seguir
são descritos apenas alguns trabalhos para ilustrar o emprego do método em variadas
áreas.
Em Jiang e Zhou (2004), um método de segmentação de imagens, baseado em um
conjunto de redes SOM é proposto. Os pixels são agrupados de acordo com a cor e carac-
terísticas espaciais em cada rede SOM. Após combinam-seos resultados de agrupamento
para dar a segmentação final. Os resultados experimentais mostram que o método pro-
posto apresenta um desempenho melhor do que métodos baseados em segmentação de
imagem.
Georgakis et al. (2005) comparou um comitê de máquinas de SOM com o SOM tra-
dicional em organização e recuperação de documentos. Como critério para combinação
dos mapas, foi utilizada a distância euclidiana entre os neurônios, para determinar quais
neurônios estavam alinhados, possibilitando a fusão. Os mapas foram avaliados dois a
dois, até que todos os mapas foram combinados em um só. O comitê de SOM obteve um
melhor resultado do que a aplicação tradicional. Para esta metodologia, todos os mapas
20 CAPÍTULO 2. FUNDAMENTAÇÃO TEÓRICA
devem ter o mesmo tamanho.
No trabalho de Saavedra et al. (2007), a fusão dos neurônios foi denominada Fusion-
SOM e baseia-se nos polígonos de Voronoi - regiões do espaço de entrada às quais os
neurônios do mapa de Kohonen podem ser associados, ou seja, para os neurônios serem
combinados, precisam representar a mesma região do espaço de entrada.
O trabalho de Low et al. (2005) apresenta uma abordagem de comitê chamada Mapa
de Kohonen Extendido e Cooperativo (Cooperative EKM - Extendend Kohonen Maps)
com mapeamento indireto aplicado a movimentação de robôs.
No trabalho de DeLooze (2006) um conjunto de redes SOM são utilizadas para iden-
tificar e caracterizar adequadamente ataques a computadores.
Tsai (2014) desenvolveu modelos de previsão de dificuldades no mercado financeiro,
baseados em comitê de SOM, obtendo resultados melhores do que modelos individuais.
Em Fustes et al. (2013) foi utilizado comitê de SOM, para análise não supervisionada
de outliers, que permite a descoberta de conhecimento em bancos de dados astronômicos,
como a missão Gaia, da agência espacial européia que vai observar com uma precisão
posições, distâncias, movimentos do espaço, e muitas propriedades físicas de mais de um
bilhão de objetos em nossa galáxia e além.
2.5 Resumo
Neste capítulo foram apresentados os principais conceitos que serão utilizados neste
trabalho: mapas auto organizáveis de Kohonen, índices de validação e comitês de má-
quinas. Os mapas auto organizáveis de Kohonen são uma rede neural artificial que têm
demonstrado bons resultados em tarefas de classificação, agrupamento e visualização de
conjuntos de dados multidimensionais. Os índices de validação de agrupamentos tem por
finalidade quantificar o quanto um algoritmo pode ser eficiente em agrupar dados. Os co-
mitês de máquinas constituem uma maneira para lidar com grandes conjuntos de dados,
produzindo bons resultados em relação ao custo computacional envolvido. No próximo
capítulo serão detalhadas as abordagens desenvolvidas neste trabalho para a fusão de ma-
pas de Kohonen.
Capítulo 3
Materiais e Métodos
Para projetar um comitê de máquinas é preciso definir três parâmetros importantes:
como obter a diversidade entre os componentes do comitê; como selecionar os com-
ponentes que farão parte do comitê e como agregar, ou combinar, o resultado de cada
componente.
Neste capítulo serão apresentadas as metodologias para a investigação da solução do
tema proposto por este trabalho através de duas Seções: fusão de mapas de tamanhos
iguais e fusão de mapas de tamanhos diferentes.
3.1 Fusão de mapas de tamanhos iguais
O método consiste na fusão de mapas de Kohonen formados a partir de subconjuntos
do conjunto de dados, criados por re-amostragem (Bagging).
Como descrito na Seção 2.4.1, Bagging e Boosting são duas técnicas bastante empre-
gadas para a re-amostragem de dados. Neste trabalho foi escolhida a técnica de Bagging
por ser de implementação e execução mais simples.
Uma visão geral do processo é mostrado na Figura 3.1. A fusão ocorre entre dois
neurônios que têm a mínima distância Euclidiana entre eles, indicando que eles represen-
tam a mesma região do espaço de entrada.
Figura 3.1: Visão geral do processo.
Fonte: Elaborada pelo autor.
22 CAPÍTULO 3. MATERIAIS E MÉTODOS
O método de re-amostragem foi utilizado para gerar subconjuntos a partir do conjunto
de treinamento, com probabilidade uniforme e reposição. O SOM foi aplicado a cada
subconjunto gerado e todos os mapas foram segmentadas pelo algoritmo k-means. Os
mapas segmentados são os candidatos a comporem o comitê de máquinas.
3.1.1 Seleção e dos candidatos
De acordo com Zhou et al. (2002), não se deve utilizar todos os componentes, pois
isso pode afetar o desempenho do comitê. Assim, a maneira de selecionar estes can-
didatos será através de índices de validação de agrupamentos modificados, propostos
por Gonçalves (2009), a saber: CDbw, Calinski-Harabasz, Dunn generalizado, PBM e
Davies-Bouldin. Estes índices serão a função consenso do comitê.
O método de seleção é baseado na ordenação dos componentes pelos índices de va-
lidação e pode ser descrito da seguinte maneira: os candidatos a compor o comitê são
ordenados com base nos valores dos índices de validação, do melhor para o pior. Assim,
temos uma medida de desempenho individual de cada componente.
O processo de seleção dos mapas de Kohonen desenvolvido neste trabalho é ilustrado
pela Figura 3.2. Neste exemplo os mapas foram ordenados pelo índice de validação de
agrupamentos CDbw e os valores foram normalizados no intervalo [0,1]. O mapa com o
melhor índice CDbw (0,5369), letra (a) na Figura, é o primeiro componente do comitê.
O mapa com o segundo melhor índice CDbw (0,4386), letra (b) na figura, é primeiro
candidato a compor o comitê. A combinação entre eles resultou em um mapa que, ao
ser segmentado, alcançou um valor para o índice CDbw igual a 0,7207, que é maior do
que o mapa melhor ordenado anteriormente. Desta forma, o segundo mapa é mantido no
comitê, letra (c) na figura. Caso o valor do índice do mapa combinado fosse menor do que
o índice do primeiro mapa, o segundo mapa seria retirado do comitê e o terceiro mapa
seria testado. Este processo de seleção prossegue até que todos os mapas disponíveis
sejam testados.
As equações de fusão, as abordagens e a estrutura geral do experimento fatorial são
descritas a seguir.
3.1.2 Equações de fusão
Foram testadas três diferentes equações para a fusão dos neurônios dos mapas de
Kohonen. A primeira, Equação 3.1, é uma média aritmética simples entre os vetores de
3.1. FUSÃO DE MAPAS DE TAMANHOS IGUAIS 23
Figura 3.2: Seleção e combinação dos mapas.
Fonte: Elaborada pelo autor.
peso dos neurônios as serem fundidos.
wc =
wi +w j
2
(3.1)
onde wc representa cada neurônio do mapa combinado; wi e w j são os neurônios dos
mapas a serem combinados.
A segunda equação é uma média ponderada entre os pesos dos neurônios e seus res-
pectivos hits. O propósito de incluir os hits é evitar a influência de neurônios sem hits no
resultado da fusão, como mostra a Equação 3.2
wc =
wi ·hi +w j ·h j
hi +h j
(3.2)
onde hi e h j são os hits de cada neurônio de cada mapa.
Através da Equação 3.3, a terceira equação testada, analisamos se o índice de valida-
ção de agrupamento influencia na melhora da acurácia do algoritmo.
wc =
wi ·hi ·V Ii +w j ·h j ·V I j
hi ·V Ii +h j ·V I j
(3.3)
onde V Ii e V I j são os valores dos índices de validação para cada um dos mapas a serem
combinados.
24 CAPÍTULO 3. MATERIAIS E MÉTODOS
3.1.3 Experimento fatorial
Foi definido um experimento fatorial para avaliar o algoritmo proposto para a fusão
dos mapas. Foram avaliados três tamanhos de mapas: o 10x10, o 15x15 e o 20x20. Atra-
vés da re-amostragem, foram gerados dez conjuntos de dados, com a seguinte quantidade
de subconjuntos: 10, 20, 30, 40, 50, 60, 70, 80, 90 e 100 subconjuntos. Cada um dos
subconjuntos foi criado com três diferentes porcentagens de Bagging, sendo 50%, 70% e
90% dos dados de treinamento.
Isto significa que para cada tamanho de mapa, há dez diferentes subconjuntos e três
valores de porcentagem da re-amostragem, resultando em 900 mapas. Assim, no primeiro
experimento o mapa tem o tamanho de 10x10, com 10 subconjuntos gerados pela re-
amostragemcom uma porcentagem de 50% dos dados de treinamento, como mostra a
Figura 3.3.
Figura 3.3: Estrutura do experimento fatorial.
Fonte: Elaborada pelo autor.
3.1.4 Abordagens
A ordenação dos mapas foi baseada nos cinco índices de validação de agupamentos
descritos na Seção 2.2 e ainda o MSQE (Mean Square Quantization Error).
O MSQE indica o quão bem os neurônios do mapa se aproximam dos dados do con-
junto de entrada (Corchado e Baruque, 2012), sendo utilizado para avaliar a qualidade da
adaptação do mapa aos dados (Saavedra et al., 2007).
3.1. FUSÃO DE MAPAS DE TAMANHOS IGUAIS 25
Nesta pesquisa, foram testadas quatro abordagens para ordenar as performances dos
mapas e para estabelecer os critérios de combinação ou fusão:
Abordagem 1: Mapas ordenados pelo índice de validação e combinados pelo critério da
melhora do MSQE.
Abordagem 2: Mapas ordenados pelo MSQE e combinados pelo critério da melhora do
índice de validação.
Abordagem 3: Mapas ordenados pelos índice de validação e combinados pelo critério da
melhora do índice de validação.
Abordagem 4: Mapas ordenados pelo MSQE e combinados pelo critério da melhora do
MSQE.
Na primeira abordagem, os mapas são ordenados por cada um dos cinco índices de
validação, mas a fusão é controlada pela melhora do MSQE do mapa fundido. Na segunda
abordagem, os mapas foram ordenados pelo MSQE e o processo de fusão foi controlado
pela melhora do índice de validação de agrupamento do mapa fundido. Na terceira abor-
dagem, os mapas foram ordenados por cada índice de validação de agrupamento e a fusão
foi controlada pela melhora destes índices. É importante destacar que , por exemplo, se os
mapas foram ordenados de acordo com o índice Davies-Bouldin, a fusão será controlada
pela melhoria deste índice. Finalmente, na quarta abordagem os mapas foram ordenados
pelo MSQE e fundidos pelo critério de melhoria do MSQE. A Figura 3.4 mostra o que foi
descrito.
Figura 3.4: Abordagens para a fusão dos mapas.
Fonte: Elaborada pelo autor.
26 CAPÍTULO 3. MATERIAIS E MÉTODOS
3.1.5 Algoritmo proposto
O algoritmo proposto foi aplicado em cada uma das combinações mostrada na Figura
3.3, de acordo com as abordagens ilustradas na Figura 3.4. O algoritmo é descrito a
seguir:
Algoritmo 1: FUSÃO DE MAPAS DE TAMANHOS IGUAIS
Entrada: Conjunto de dados, tamanho do mapa, número de subconjuntos,
porcentagem da re-amostragem
Saída: Mapas fundido
1 início
2 Gerar, através da re-amostragem (Bagging), os subconjuntos a partir do
conjunto de treinamento
3 Aplicar o SOM nos subconjuntos gerados, resultando em Ni (i = 1,2, ...) mapas
com a mesma dimensão
4 Segmentar os mapas com o algoritmo k-means
5 Calcular os índices de validação de agrupamentos e o MSQE para cada Ni
(i = 1,2, ...) mapa e ordená-los de acordo com os valores obtidos, do melhor
para o pior
6 Fundir o melhor mapa (mapa base - o que possuir o melhor valor para o índice
de validação de agrupamento ou MSQE) com o próximo melhor mapa, de
acordo com a ordenação, seguindo as Equações 3.1, 3.2 e 3.3
7 Calcular o índice de validação de agrupamento ou o MSQE do mapa fundido
8 Se
9 Há melhoria no índice de validação de agrupamento ou MSQE
10 Então
11 O mapa resultante da fusão torna-se o mapa base, retorne ao PASSO 6 até
que todos os mapas sejam fundidos;
12 Senão
13 A fusão é descartada, retorne ao PASSO 6 até que todos os mapas sejam
fundidos;
14 fim
Os principais parâmetros do SOM foram: grade hexagonal, vizinhança gaussiana,
raio inicial de treinamento igual a 4, raio final de treinamento igual a 1 e 2000 épocas de
treinamento. Devido à inicialização aleatória, o algoritmo k-means foi repetido dez vezes
e foi selecionado o resultado que apresentou a menor soma dos quadrados dos erros.
3.2. FUSÃO DE MAPAS DE TAMANHOS DIFERENTES 27
3.2 Fusão de mapas de tamanhos diferentes
Na literatura, até o momento, não foram encontrados métodos que possam resolver
o problema de fusão de mapas de Kohonen com diferentes tamanhos. A complexidade
está no fato de que, em mapas de tamanhos diferentes, teremos diferenças topológicas.
Mapas considerados pequenos têm neurônios vencedores (BMU) com grande número
de hits, isto é, vários padrões de entrada associados a eles. Por outro lado, em mapas
considerados grandes a vantagem é a distância elevada entre os BMUs, o que possibilita
melhor visualização do mapa.
Neste trabalho foi desenvolvido um novo método para combinar as saídas de mapas de
Kohonen com tamanhos diferentes em uma única saída. O objetivo é melhorar a acurácia
do comitê em relação à acurácia de um único mapa de Kohonen.
Para a fusão de mapas com tamanhos diferente novamente foram investigadas as pos-
sibilidades de ordenação e fusão de acordo com o que foi estabelecido para a fusão de
mapas de tamanhos iguais (Subseção 3.1.3).
O comitê é composto por mapas de diferentes tamanhos, derivados de um Mapa Base,
isto é, o mapa que será melhorado através de fusões consecutivas com outros mapas de
tamanhos diferentes.
Para determinação do tamanho do Mapa Base foi utilizada a Equação 3.4, definida em
Kohonen (1982), onde as dimensões x e y (linhas e colunas, respectivamente) do mapa
devem ser proporcionais aos dois maiores autovalores da matriz de covariância dos dados:
λ1 e λ2:
x
y
≈
√
λ1
λ2
(3.4)
O Mapa Base é o primeiro componente do comitê e os mapas restantes são candidatos
a comporem o comitê. Estes mapas são organizados de acordo com a performance obtida
(MSQE e os cinco índices de validação de agrupamentos). Os mapas são combinados aos
pares acordo com as três Equações de fusão: 3.1, 3.2 e 3.3.
Assim como na abordagem para fusão de mapas de mesmo tamanho, apresentada na
Seção 3.1, é preciso identificar e retirar do comitê os componentes que não contribuem
para o aumento do desempenho do comitê (Zhou et al., 2002).
Deste modo, o processo de seleção dos componentes é o mesmo que foi descrito para
mapas de tamanhos iguais (ver Figura 3.2), iniciando com o Mapa Base sendo combinado
com o mapa que apresenta a melhor performance entre os outros mapas. Se a performance
resultante da combinação dos mapas for melhorada em relação à performance do mapa
base, a combinação destes mapas é mantida. Caso contrário, a combinação destes dois
28 CAPÍTULO 3. MATERIAIS E MÉTODOS
mapas é descartada e o próximo mapa, com a segunda melhor performance, é combinado
com o mapa base. Cada vez que a combinação dos mapas resulta em um aumento da
performance, o próximo mapa (em ordem descendente de performance) é combinado a
eles e assim sucessivamente até que todos os mapas sejam testados na combinação.
Para a segmentação dos mapas foi utilizado o algoritmo k-means. O mesmo é repetido
dez vezes e o resultado escolhido é o que apresentar a menor soma dos quadrados dos
erros, devido à natureza de inicialização aleatória do k-means.
Para esta abordagem foram testadas duas maneiras distintas para a realização da fusão
dos mapas. A primeira maneira refere-se a uma estrutura de 7 mapas. Na segunda maneira
a estrutura é composta por 49 mapas. As diferenças e características de cada uma destas
variações é explicada nas subseções seguintes.
A influência do número de hits e BMUs no processo de fusão foi avaliada através da
variação das porcentagens destas medidas desde 10% até 100%, com passo de 10%. Cada
neurônio do Mapa Base tem um número de hits (quantas vezes o neurônio foi o vencedor
- BMU). Quando este neurônio é fundido a outro neurônio (de outro mapa), será levado
em consideração o valor mínimo da porcentagem de hits que este neurônio deve ter em
relação ao neurônio do Mapa Base.
A limitação da porcentagem de BMUs é o coração do método de fusão de mapas
com tamanhos diferentes. No processo de fusão, os mapas são avaliados aos pares. Os
neurônios destes mapas também são avaliados aos pares, através da distância Euclidiana.
Quando o Mapa Base tem dimensões menores do que o mapa a ser fundido com ele,
haverá mais neurônios neste segundo mapa do que no Mapa Base. Por exemplo, conside-
rando que um Mapa Base tenha tamanho de 10x10 e o mapaa ser com ele fundido tenha
tamanho de 12x12, haverá 100 neurônios no primeiro mapa e 144 no segundo mapa. Com
a limitação da porcentagem de BMUs, a fusão ficará limitada a 100% dos neurônios do
Mapa Base. Significa que, para o exemplo dado, apenas 100 dos 144 neurônios serão
avaliados no processo de fusão. Estes 100 neurônios são os que possuem as menores
distâncias Euclidianas com os 100 neurônios do Mapa Base. Os outros 44 neurônios não
entram no processo. Assim é possível fundir mapas maiores à mapas menores.
3.2.1 Estrutura com 7 mapas
Considerando o Mapa Base com dimensões N x M, os outros seis mapas têm as se-
guintes dimensões: (N+3) x M, N x (M+3), (N-3) x M, (N-3) x (M+3), (N-3) x (M-3),
N x (M-3), como mostrado na Fig. 3.5. Desta maneira teremos mapas com tamanhos
variados, promovendo uma certa diversidade entre estes mapas.
3.2. FUSÃO DE MAPAS DE TAMANHOS DIFERENTES 29
Figura 3.5: Estrutura com 7 mapas.
Fonte: Elaborada pelo autor.
O algoritmo para a fusão dos sete mapas é descrito a seguir.
Algoritmo 2: FUSÃO DE 7 MAPAS DE TAMANHOS DIFERENTES
Entrada: Conjunto de dados
Saída: Fusão dos mapas de Kohonen
1 início
2 Dividir o conjunto de dados em treinamento (80%) e teste (20%)
3 Calcular o tamanho do Mapa Base, através da Equação 3.4
4 Criar, a partir do Mapa Base, os outros seis mapas
5 Aplicar o algoritmo SOM ao conjunto de treinamento, criando as estruturas dos
sete mapas
6 Segmentar todos os mapas, através do algoritmo k-means
7 Calcular as performances de cada mapa - os cinco índices de validação de
agrupamentos e o MSQE
8 Ordenar os mapas de acordo com os critérios de performance, do melhor para o
pior
9 Fundir cada mapa ao Mapa Base de acordo com a equação de fusão
10 Calcular a performance do mapa fundido
11 Se
12 Há melhoria na performance
13 Então
14 O mapa resultante da fusão torna-se o mapa base, retorne ao PASSO 9 até
que todos os mapas sejam fundidos;
15 Senão
16 A fusão é descartada, retorne ao PASSO 9 até que todos os mapas sejam
fundidos;
17 fim
30 CAPÍTULO 3. MATERIAIS E MÉTODOS
3.2.2 Estrutura com 49 mapas
O comitê é composto por 49 mapas, sendo um Mapa Base e 48 mapas com tamanhos
derivados a partir do tamanho do Mapa Base.
As dimensões do Mapa Base são definidas pela Equação 3.4, tal como na estrutura
com 7 mapas. Neste trabalho definiu-se que uma permutação de 3 valores acima e abaixo
dos valores das dimensões do Mapa Base seria utilizada para gerar os outros 48 mapas.
Por exemplo, se o Mapa Base tiver dimensões iguais a 10x10, os mapas restantes
teriam os valores de linha e coluna variando entre 7 e 13, isto é, 7x7, 7x8, ..., 13x12,
13x13, totalizando 49 mapas com diferentes tamanhos, como mostra a Figura 3.6.
Figura 3.6: Estrutura com 49 mapas.
Fonte: Elaborada pelo autor.
3.2. FUSÃO DE MAPAS DE TAMANHOS DIFERENTES 31
O algoritmo para a fusão dos 49 mapas é descrito a seguir.
Algoritmo 3: FUSÃO DE 49 MAPAS DE TAMANHOS DIFERENTES
Entrada: Conjunto de dados
Saída: Fusão dos mapas de Kohonen
1 início
2 Dividir o conjunto de dados em treinamento (80%) e teste (20%)
3 Calcular o tamanho do Mapa Base, através da Equação 3.4
4 Criar, a partir do Mapa Base, os outros quarenta e oito mapas
5 Aplicar o algoritmo SOM ao conjunto de treinamento, criando as estruturas dos
mapas
6 Segmentar todos os mapas, através do algoritmo k-means
7 Calcular as performances de cada mapa - os cinco índices de validação de
agrupamentos e o MSQE
8 Ordenar os mapas de acordo com os critérios de performance, do melhor para o
pior
9 Fundir cada mapa ao Mapa Base de acordo com a equação de fusão
10 Calcular a performance do mapa fundido
11 Se
12 Há melhoria na performance
13 Então
14 O mapa resultante da fusão torna-se o mapa base, retorne ao PASSO 9 até
que todos os mapas sejam fundidos;
15 Senão
16 A fusão é descartada, retorne ao PASSO 9 até que todos os mapas sejam
fundidos;
17 fim
32 CAPÍTULO 3. MATERIAIS E MÉTODOS
3.2.3 Validação Cruzada
A validação cruzada (ou Cross Validation) é um procedimento para estimar a perfor-
mance de um algoritmo. Basicamente o conjunto de dados é dividido aleatoriamente em
K subconjuntos (ou folds), mutuamente exclusivos e com tamanhos iguais ou aproxima-
damente iguais.
Uma maneira usual é utilizar K igual a 10, chamando a validação cruzada de "10-fold
cross-validation". Neste caso, um dos subconjuntos é utilizado para o teste do algoritmo
e os outros K−1 subconjuntos formam o conjunto de treinamento. Este procedimento é
repetido K vezes, sendo que em cada repetição, um subconjunto diferente é usado para o
teste os subconjuntos restantes são utilizados no treinamento. Ao final, a performance do
algoritmo (acurácia, por exemplo) é obtida pela média das performances obtidas a cada
repetição deste procedimento (Kuncheva, 2004).
Uma variação do deste procedimento é a Validação Cruzada Estratificada. Aqui,
ao dividir o conjunto de dados em K subconjuntos, a distribuição de classes em cada
subconjunto é aproximadamente a mesma do conjunto original de dados (Diamantidis
et al., 2000).
Neste trabalho, foi utilizada a validação cruzada estratificada, para mapas de tamanhos
diferentes, na estrutura de 49 mapas, para estimar a acurácia do algoritmo proposto para
a fusão.
O algoritmo desenvolvido para a validação cruzada é descrito a seguir.
3.2. FUSÃO DE MAPAS DE TAMANHOS DIFERENTES 33
Algoritmo 4: FUSÃO ATRAVÉS DA VALIDAÇÃO CRUZADA
Entrada: Conjunto de dados
Saída: Estimativa de acurácia da fusão de mapas de tamanhos diferentes
1 início
2 Dividir o conjunto de dados em K=10 partes (folds), mantendo a proporção de
classes do conjunto de dados original
3 Retirar uma das partes (um dos subconjuntos) para o teste
4 Calcular o tamanho do Mapa Base, através da Equação 3.4, utilizando K-1
subconjuntos
5 Criar, a partir do Mapa Base, os outros 48 mapas
6 Aplicar o algoritmo SOM ao conjunto de treinamento, criando as estruturas dos
mapas
7 Segmentar todos os mapas, através do algoritmo k-means
8 Calcular as performances de cada mapa - os cinco índices de validação de
agrupamentos e o MSQE
9 Ordenar os mapas de acordo com os critérios de performance, do melhor para o
pior
10 Fundir cada mapa ao Mapa Base de acordo com a equação de fusão
11 Calcular a performance do mapa fundido, com o conjunto de testes (o
subconjunto que não foi utilizado no treinamento)
12 Se
13 Há melhoria na performance
14 Então
15 O mapa resultante da fusão torna-se o mapa base, retorne ao PASSO 10
até que todos os mapas sejam fundidos;
16 Senão
17 A fusão é descartada, retorne ao PASSO 10 até que todos os mapas sejam
fundidos
18 Retornar ao PASSO 2 até que o algoritmo seja repetido 10 vezes
19 Calcular a performance do algoritmo, como sendo a média das 10
performances obtidas.
20 fim
34 CAPÍTULO 3. MATERIAIS E MÉTODOS
3.3 Medida de performance
Quando há um conhecimento prévio da estrutura original dos dados, pode-se adotar
critérios externos para avaliação da performance do algoritmo de agrupamento.
Assim, os algoritmos são mensurados de forma a avaliar o quão bem o agrupamento
coincide com as classes verdadeiras presentes em um dado conjunto de dados.
A pureza (purity, em inglês) é um critério externo de qualidade para o agrupamento e
é utilizado quando os rótulos dos dados são conhecidos (Manning et al., 2008).
Esta medida de performance de agrupamento é calculada pela somatória das amostras
corretamente posicionadas em um dado grupo, dividida pelo número total de amostras.
A maneira mais fácil de calcular a pureza de um agrupamento é encontrar a classe
majoritária em cada grupo e contar o número de objetos marcados dessa classe em cada
grupo. Depois divide-se o valor desta somatória pela quantidade total de amostras do
conjunto de dados (Forestier et al., 2010). Os valores da pureza do agrupamento ficam
entre 0 e 1, sendo que valores próximos a 1 indicam bons agrupamentos e valores baixos
indicam agrupamentos ruins.
Esta definição da pureza e sua utilização como medida de performance de algoritmos
de agrupamento pode ser encontrada nostrabalhos de Amigó et al. (2009), Rendón et al.
(2011), Sripada e Rao (2011) e Deepa e Revathy (2012), entre outros.
Já nos trabalhos de Greene et al. (2004) e de Kuncheva et al. (2006), o critério para
avaliação de um comitê de máquinas de agrupamento foi uma medida de desempenho
denominada acurácia e definida como a proporção de atribuição correta de rótulos às
amostras em função do número total de amostras. Ou seja, a definição de pureza e acurácia
é a mesma.
Neste trabalho, será utilizado o termo “acurácia” para designar a performance dos
algoritmos propostos.
3.4 Teste estatístico
No trabalho de Demšar (2006) são apresentados alguns testes para comparação esta-
tística das performances de algoritmos considerando múltiplos conjuntos de dados. Com
base nos estudos apontados no trabalho, o autor sugere que seja utilizado o teste não pa-
ramétrico de Wilcoxon (Wilcoxon Signed Rank Test) para comparação de dois algoritmos,
pois é um teste simples, seguro e robusto.
Testes não paramétricos são mais seguros do que testes paramétricos, uma vez que
não assumem distribuição normal ou homogeneidade da variância dos dados. Assim, eles
3.5. RESUMO 35
podem ser aplicados para verificação da acurácia do modelo, taxas de erro ou qualquer
outra medida para avaliação de algoritmos. Os resultados empíricos sugerem que eles
também são mais fortes do que os outros testes estudados.
Por essa razão, entre os testes apresentados pelo autor, foi escolhido o teste não pa-
ramétrico de Wilcoxon (Signed Rank Test), com nível de significância de 0,05. Através
deste teste, serão avaliados os resultados obtidos pelo comitê de mapas de Kohonen, isto
é, se o algoritmo proposto leva a resultados estatisticamente diferentes das acurácias ob-
tidas por um único mapa. A hipótese nula, H0, é que não há diferença entre as acurácias
obtidas pelo mapa único e pelo comitê de mapas. O algoritmo para o teste de Wilcoxon é
descrito a seguir.
Algoritmo 5: TESTE DE WILCOXON
Entrada: Resultados obtidos por dois diferentes algoritmos
Saída: Aceitação ou rejeição da Hipótese nula
1 início
2 Calcular a diferença di = Xi−Yi, onde xi e yi são os pares dos resultados para
cada conjunto de dados
3 Ordenar os resultados de di, sem considerar os sinais, ou seja, atribuir o posto 1
para o menor valor de |di|, posto 2 para o próximo e assim por diante.
4 Atribuir o sinal para cada posto de acordo com o sinal de di
5 Calcular a soma dos postos positivos (R+) e a soma dos postos negativos (R−)
6 Escolha T = min(R+,R−)
7 Verificar o valor crítico para aceitação ou rejeição de H0
8 A Hipótese nula é rejeitada se o valor de T for menor do que o valor
encontrado nas tabelas de valores críticos para o teste de Wilcoxon
9 fim
3.5 Resumo
Neste capítulo foram apresentadas propostas de abordagens para a fusão de mapas de
Kohonen com tamanhos iguais e com tamanhos diferentes. Foram definidas as equações
para a fusão dos mapas, os critérios para ordenação e fusão, bem como os algoritmos
correspondentes a cada uma das abordagens, além da definição da acurácia utilizada neste
trabalho. Também foi apresentado o teste estatístico de Wilcoxon, que será utilizado na
comparação dos resultados obtidos. No próximo capítulo são apresentados os resultados
obtidos na fusão de mapas de Kohonen através dos algoritmos aqui propostos.
36 CAPÍTULO 3. MATERIAIS E MÉTODOS
Capítulo 4
Resultados
Este capítulo apresenta os resultados obtidos na aplicação dos algoritmos propostos
para a fusão de mapas de Kohonen. Está dividido em duas seções: fusão de mapas de
mesmo tamanho e fusão de mapas de tamanhos diferentes. Esta última contém três sub-
seções: estrutura com 7 mapas, estrutura com 49 mapas e validação cruzada estratificada.
4.1 Conjunto de dados
O algoritmo proposto foi testado em variados conjuntos de dados do Repositório UCI
(Lichman, 2013) e do FCPS (Fundamental Clustering Problems Suite) (Ultsch, 2005). As
características de cada conjunto de dados são mostradas na Tabela 4.1 e no Apêndice A
estão as ilustrações destes conjuntos de dados.
Tabela 4.1: Conjuntos de dados utilizados.
No Dataset Repositório Instâncias Atributos Classes
01 BC Wisconsin UCI 699 10 2
02 Column UCI 310 6 2
03 Heart UCI 303 75 2
04 Hepatitis UCI 155 19 2
05 Ionosphere UCI 351 34 2
06 Iris UCI 150 4 3
07 Pima Indians UCI 768 8 2
08 Seeds UCI 210 7 3
09 Wine UCI 178 13 3
10 Chainlink FCPS 1000 3 2
11 Engytime FCPS 4096 2 2
12 Lsun FCPS 400 2 3
13 Tetra FCPS 400 3 4
14 Two Diamonds FCPS 800 2 2
15 Wingnut FCPS 1070 2 2
38 CAPÍTULO 4. RESULTADOS
4.2 Mapas de tamanhos iguais
O objetivo da simulação foi verificar em qual configuração de tamanho do mapa, de
número de subconjuntos e de percentagem de bagging, o melhor valor da acurácia poderia
ser obtida.
Cada experimento foi executado 10 vezes e foram obtidos valores médios para um
intervalo de confiança de 95%. Os resultados foram comparados com um único mapa
SOM, para verificar a melhora na acurácia.
A Tabela 4.2 apresenta os resultados experimentais para cada conjunto de dados. A
coluna “Equação” mostra qual foi a equação de fusão que alcançou o melhor resultado,
para cada conjunto de dados. A Equação (3.1) é a mais simples das três equações tes-
tadas, sendo apenas uma média simples entre os vetores dos dois neurônios de peso. A
Equação (3.2) é uma média ponderada entre pesos dos neurônios e seus hits. A Equação
(3.3) é uma média ponderada entre pesos dos neurônios, hits e índice de validação de
agrupamento. Esta última equação, a mais complexa dentre as três utilizadas, apresentou
o melhor resultado para apenas 2 dos 15 conjuntos de dados avaliados.
A coluna “Abordagem” refere-se à forma como os mapas foram ordenados e fundidos,
tal como especificado na Subseção 3.1.3. Para a maioria dos conjuntos de dados, as
abordagens 2 (Mapas ordenados pelo MSQE e combinados pelo critério da melhora do
índice de validação) e 3 (Mapas ordenados pelo índice de validação e combinados pelo
critério da melhora do índice de validação) foram as que levaram aos melhores resultados
para o método proposto.
A coluna “CVI”, de Cluster Validity Index - índice de validação de agrupamentos -
mostra qual índice foi usado para conseguir a melhor acurácia de fusão em relação ao
único mapa, para cada conjunto de dados (DB é o índice Davies-Bouldin e CH é o índice
Calinski e Harabasz). O índice Davies-Bouldin é o que aparece mais vezes e o índice
PBM não conduziu a bons resultados para os conjuntos de dados utilizados.
A coluna “Tamanho do mapa” refere-se ao tamanho do mapa que alcançou o melhor
valor da acurácia. O mapa 15x15 não obteve resultados para os conjuntos de dados ava-
liados. Isto não significa que mapas com estas dimensões, ou seja, com 225 neurônios
na camada de saída, não são apropriados. Apenas significa que, para estes conjuntos de
dados, mapas com 100 ou com 400 neurônios se adaptaram melhor aos dados de entrada
e conduziram à melhores acurácias.
A coluna “Bagging” mostra que, para grande parte dos conjuntos de dados, utilizando
90% das amostras foi possível obter os melhores resultados. Uma elevada percentagem
do valor Bagging significa que há uma maior variedade de dados para o treinamento,
4.2. MAPAS DE TAMANHOS IGUAIS 39
levando a um melhor resultado de acurácia da fusão. Estes resultados mostram que é
possível obter boas precisões sem utilizar todos os elementos do conjunto de treinamento.
A coluna “Número de Subconjuntos” mostra o número de subconjuntos que foram
avaliados para encontrar a melhor acurácia. Para a maioria dos conjuntos de dados utili-
zados nesta experimento, as melhores acurácias foram obtidas com grandes quantidades
de subconjuntos. Isto era esperado, uma vez que quanto mais subconjuntos disponíveis,
mais fusões podem ocorrer e, consequentemente, o resultado da acurácia melhora.
A acurácia de um único mapa de Kohonen é comparado com os resultados da acurácia
do comitê de mapas nas duas últimas colunas da tabela.
Como pode ser visto na Tabela 4.2, para todos os conjuntos de dados utilizados neste
experimento,