Mapas Auto-Organizáveis de Kohonen

Mapas AutoOrganizáveis de Kohonen Hesdras Viana Hesdrasvianauninassauedubr Introdução O SelfOrganizing Map SOM ou Mapas Auto Organizáveis foram desenvolvidos por Kohonen a partir de 1982 Aprendizado nãosupervisionado diferente de todas as redes neurais artificiais desenvolvidas até então Possui forte inspiração neurofisiológica É baseado em Aprendizagem Competitiva Ouvido palavras Aprendizagem Competitiva Neurônios de saída da RNA competem entre si para se tornar ativos Apenas um neurônio de saída está ativo em um determinado instante Três elementos básicos 1 Neurônios com mesma estrutura diferente pelos pesos de forma que tenham respostas diferentes a uma entrada 2 Um limite imposto sobre a força de cada neurônio 3 Mecanismo de competição entre neurônios de forma que um neurônio é vencedor em um dado instante Lendo palavras Aprendizagem Competitiva Em cada momento o neurônio vencedor aprende a se especializar em agrupamentos de padrões similares tornamse detectores de características para classes diferentes de padrões de entrada O número de unidades de entrada define a dimensionalidade dos dados Falando palavras Aprendizagem Competitiva Exemplo Exemplo de estrutura simples 1 camada de saída Totalmente conectada à entrada Pode incluir realimentação entre neurônios para inibição lateral Conexões excitadoras das entradas para os neurônios setas fechadas com linhas contínuas Conexões laterais inibitórias entre os neurônios setas abertas em linhastracejadas x1 x2 y1 x3 x4 Entradas y2 y3 Neurônios Saída Pensando em palavras Aprendizagem Competitiva Neurônio Vencedor O neurônio vencedor é o que possui o maior campo local induzido υk para um dado padrão de entrada x O campo local induzido representa a ação combinada de todas as entradas do neurônio k A escolha do vencedor maximiza o produto interno entre os pesos do neurônio e o sinal de entrada O sinal de saída yk do neurônio vencedor é colocado em 1 um e dos outros neurônios em 0 zero 0 para todo j i caso contrario y k k 1 se j Aprendizagem Competitiva Pesos Considerando ωkj como o peso sináptico conectando o nó de entrada j ao neurônio k cada neurônio tem uma quantidade de peso sináptico Cada neurônio tem seus pesos inicializados aleatoriamente O aprendizado dáse então deslocando os pesos do neurônio vencedor na direção da entrada j kj 1para todo k Aprendizagem Competitiva Regra de Aprendizagem A regra de aprendizagem competitiva aplica uma variação ωkj ao peso ωkj definida por x j kj se o neurônio k for o vencedor caso contrario 0 kj onde α é a taxa de aprendizagem Esta regra move o vetor de peso do neurônio vencedor em direção ao padrão de entrada Mapas AutoOrganizáveis Grades neurais baseadas na aprendizagem competitiva Neurônios de saída da grade competem entre si para serem ativados ou disparados Os neurônios estão dispostos em nós de uma grade em geral uni ou bidimensional Torna a rede ideal para detecção de agrupamentos clusters O modelo de Kohonen Produz um mapeamento topológico Transforma um padrão de dimensão arbitrária em um mapa discreto uni ou bidimensional Preserva a relação de vizinhança entre os neurônios Mapas AutoOrganizáveis Mapa Topológico No caso bidimensional dois tipos de grade são possíveis hexagonal ou retangular Na hexagonal cada neurônio possui 6 vizinhos diretos Na retangular cada neurônio possui 4 vizinhos diretos Mapa Topológico Circular gaussiana Onde 𝑑𝑣 é a distância entre o nó vencedor e seus vizinhos σn é a largura de vizinhança hv i n exp 𝑑𝑣 2 𝜎2 𝑛 σn σ0 exp 𝑛 𝑡 Onde n é a iteração atual σ0 é o valor da largura inicial t é o número total de iteração Mapas AutoOrganizáveis Arquitetura Considere um espaço vetorial de entrada com dimensão d Cada amostra é um sinalpadrão representado por um vetor x x1 x2 xd A arquitetura do SOM consiste de 2 camadas de neurônios Camada de entrada composta por d neurônios Camada de saída ou de Kohonen formada por N neurônios denotados por A c1 c2 cN Mapas AutoOrganizáveis Arquitetura O vetor peso sináptico de cada neurônio da grade tem a mesma dimensão que o espaço de entrada O vetor peso do neurônio j é representado por w ωj1 ωj2 ωjd j 1 N este vetor indica as coordenadas de sua localização no espaço de entrada d dimensional SOM Algoritmo Básico 1 Inicialização geralmente aleatória pode ainda ser estimada por análise da representação dos dados 2 Competição para cada padrão de entrada calculase a resposta dos neurônios de saída grade O neurônio com a maior resposta é o vencedor da competição 3 Cooperação o neurônio vencedor define uma vizinhança topológica em função da grade de neurônios excitados 4 Adaptação Sináptica aprendizado em relação ao padrão de entrada Os pesos do neurônio vencedor e de sua vizinhança ficam mais próximos do padrão de entrada Critério de Competição O critério do melhor casamento best matching é baseado na maximização do produto interno como na aprendizagem competitiva Isto é matematicamente equivalente a minimizar a distância euclidiana entre w e x O neurônio vencedor v é escolhido por j v arg min x w j 12 N j Processo Cooperativo Compreende a definição de uma função de vizinhança hvj centrada no neurônio vencedor Define uma região de neurônios cooperativos que terão seus pesos ajustados juntamente com o neurônio vencedor Há diversas formas de implementar a função de vizinhança Mais simples é definir um conjunto Nvt de níveis de vizinhança ao redor do neurônio vencedor Adaptação Sináptica Modificação dos pesos em relação à entrada de forma iterativa A equação abaixo é aplicada a todos os neurônios da grade dentro da região de vizinhança hvj w jt 1 w jt thvjtx w jt O parâmetro de aprendizagem α assim como a função de vizinhança deve decrescer com o tempo para que as adaptações sejam cada vez mais finas Pode ser usada uma função linear decrescente mas é recomendada uma função exponencial decrescente Adaptação Sináptica onde τ2 é o número total de iterações Aplicações As aplicações concentramse principalmente em Organização da representação dos dados Redução de dimensionalidade Reconstrução de Superfícies Separação de agrupamentos de dados Segmentação de Imagens Data Mining Classificação de Documentos Classificação de dados Reconhecimento de Caracteres Reconhecimento de Fala Algoritmo 1 Selecione a topologia da rede defina os parâmetros 2 Selecione a região de vizinhança inicial 3 Inicialize os pesos aleatoriamente e defina o nº de iterações 4 Para cada iteração 1 Selecione um padrão de entrada 2 Encontre o neurônio vencedor pela menor distância 3 Atualize os pesos do neurônio vencedor e sua vizinhança w jt 1 w jt thvjtx w jt 1 Decremente a região de vizinhança e a taxa de aprendizagem caso desejado 2 Incremente o número da iteração 5 Fim Métricas de Qualidade para o SOM Erro de Quantização desconsidera a topologia do mapa em seu cálculo O erro de quantização QE é medido calculando a média das distâncias dos vetores de entrada aos seus melhores neurônios no espaço de saída Erro Topográfico métrica de preservação de topologia O erro topográfico TE é calculado da seguinte maneira os melhores e os segundo melhores neurônios dos vetores de entrada são encontrados para cada ocorrência onde o melhor neurônio e o segundo melhor neurônio não sejam adjacentes no mapa é considerado um erro Métricas de Qualidade para o SOM TradeOFF quanto menor o erro de quantização maior o erro topográfico Para encontrar um erro de quantização menor basta apenas aumentar o número de neurônios no mapa entretanto quanto maior o mapa maior a probabilidade que o melhor neurônio e o segundo melhor neurônio não sejam adjacentes Exemplo Animal Glândula Ovovivíparo Terrestre Mamífero 1 Galinha 1 1 1 0 2 Elefante 1 1 1 1 3 Peixe 1 1 1 0 4 Onitorrinco 1 1 1 1 5 Escorpião 1 1 1 0 6 Baleia 1 1 1 1 EXERCÍCIO 1 Treinar ao SOM por 3 ciclos com objetivo de realizar 2 agrupamentos de animais Adotar para a taxa de aprendizagem o valor constante de 01 Inicializar os pesos aleatórios Exemplo de Implementação em C parte 1 dados de entrada float x112 32 122 0 112520 035 float x212 12 1 22 2 23 1525 1 20 estado inicial dos vetores de peso float w14 0 1 01 float w24 1 espaco de saida 01 0 float S14 0 1 1 0 float S24 1 1 0 0 int iX 0 entrada atual int iter 1 iteracao atual int fConv 90 delimita iteracao da fase de convergencia int nD 12 numero de dados Exemplo de Implementação em C parte 2 encontra o neurônio vencedor pelo calculo da menor distancia wV neuronio vencedor wV 0 indice do neuronio vencedor float dist4 0 0 0 0 vetor de distancias for int j0 jnN j calcula distancia euclidiana distj sqrt powx1atw1j2 powx2atw2j2 verifica a menor distancia if distj distwV wV j Exemplo de Implementação em C parte 3 verifica entre todos os neuronios quais estao na regiao de vizinhanca wV neuronio vencedor for int j0 jnN j verifica se esta na regiao de vizinhanca note que o calculo e feito no espaco de saida S distviz sqrt powS1wVS1j2 powS2wVS2j2 se estiver dentro do raio funcao de vizinhanca circular atualiza o vetor de peso if distviz raio w1j w1jalphax1actw1j w2j w2jalphax2actw2j Exemplo de Implementação em C parte 4 escolhe nova entrada aleatoria entre 0 e nD entre os dados act intnD rand RANDMAX 10 iter incrementa iteraçao if iter fConv alpha 025 quando entra na fase de Convergencia atualiza parametros raio 05 a cada duas iteracoes decrementa taxa de aprendizagem if iter 2 0 decremento na fase de Ordenacao if iter fConv alpha 001 if iter fConv alpha 0001 if alpha 0 alpha 00005 decremento na fase de Convergencia protecao para alpha 0