Mapa auto-organizável - Self-organizing map

Um mapa de auto-organização ( SOM ) ou mapa de recursos de auto-organização ( SOFM ) é uma técnica de aprendizado de máquina não supervisionada usada para produzir uma representação de baixa dimensão (normalmente bidimensional) de um conjunto de dados de dimensão superior, preservando a estrutura topológica do dados. Por exemplo, um conjunto de dados com p variáveis ​​medidas em n observações pode ser representado como grupos de observações com valores semelhantes para as variáveis. Esses aglomerados, então, podem ser visualizados como um "mapa" bidimensional, de modo que as observações em aglomerados proximais tenham valores mais semelhantes do que as observações em aglomerados distais. Isso pode tornar os dados de alta dimensão mais fáceis de visualizar e analisar.

Um SOM é um tipo de rede neural artificial, mas é treinado usando o aprendizado competitivo em vez do aprendizado de correção de erros (por exemplo, retropropagação com gradiente descendente ) usado por outras redes neurais artificiais. O SOM foi introduzido pelo professor finlandês Teuvo Kohonen na década de 1980 e, portanto, às vezes é chamado de mapa de Kohonen ou rede de Kohonen . O mapa ou rede de Kohonen é uma abstração conveniente computacionalmente baseada em modelos biológicos de sistemas neurais da década de 1970 e modelos de morfogênese que datam de Alan Turing na década de 1950.

Um mapa auto-organizado que mostra os padrões de votação do Congresso dos EUA . Os dados de entrada foram uma tabela com uma linha para cada membro do Congresso e colunas para determinados votos contendo o voto sim / não / abstenção de cada membro. O algoritmo SOM organizou esses membros em uma grade bidimensional, colocando membros semelhantes mais próximos. O primeiro gráfico mostra o agrupamento quando os dados são divididos em dois clusters. O segundo gráfico mostra a distância média aos vizinhos: distâncias maiores são mais escuras. O terceiro enredo prevê a adesão ao partido republicano (vermelho) ou democrata (azul). O outro plota cada um sobrepondo o mapa resultante com valores previstos em uma dimensão de entrada: vermelho significa um voto 'sim' previsto naquele projeto, azul significa um voto 'não'. O enredo foi criado em Synapse .

Visão geral

Mapas auto-organizáveis, como a maioria das redes neurais artificiais, operam em dois modos: treinamento e mapeamento. Primeiro, o treinamento usa um conjunto de dados de entrada (o "espaço de entrada") para gerar uma representação dimensional inferior dos dados de entrada (o "espaço do mapa"). Em segundo lugar, o mapeamento classifica dados de entrada adicionais usando o mapa gerado.

Na maioria dos casos, o objetivo do treinamento é representar um espaço de entrada com p dimensões como um espaço de mapa com duas dimensões. Especificamente, um espaço de entrada com p variáveis ​​é dito ter p dimensões. Um espaço de mapa consiste em componentes chamados "nós" ou "neurônios", que são organizados como uma grade hexagonal ou retangular com duas dimensões. O número de nós e sua disposição são especificados de antemão com base nos objetivos maiores da análise e exploração dos dados .

Cada nó no espaço do mapa está associado a um vetor de "peso", que é a posição do nó no espaço de entrada. Enquanto os nós no espaço do mapa permanecem fixos, o treinamento consiste em mover vetores de peso em direção aos dados de entrada (reduzindo uma métrica de distância como a distância euclidiana ) sem prejudicar a topologia induzida do espaço do mapa. Após o treinamento, o mapa pode ser usado para classificar observações adicionais para o espaço de entrada, encontrando o nó com o vetor de peso mais próximo (métrica de menor distância) para o vetor de espaço de entrada.

Algoritmo de aprendizagem

O objetivo da aprendizagem no mapa auto-organizado é fazer com que diferentes partes da rede respondam de maneira semelhante a certos padrões de entrada. Isso é parcialmente motivado pela forma como as informações visuais, auditivas ou outras informações sensoriais são tratadas em partes separadas do córtex cerebral no cérebro humano .

Uma ilustração do treinamento de um mapa auto-organizado. A mancha azul é a distribuição dos dados de treinamento e o pequeno disco branco é o dado de treinamento atual extraído dessa distribuição. No início (à esquerda), os nós SOM são arbitrariamente posicionados no espaço de dados. O nó (destacado em amarelo) que está mais próximo do dado de treinamento é selecionado. Ele é movido em direção ao dado de treinamento, pois (em menor extensão) são seus vizinhos na rede. Após muitas iterações, a grade tende a se aproximar da distribuição dos dados (direita).

Os pesos dos neurônios são inicializados em pequenos valores aleatórios ou amostrados uniformemente a partir do subespaço medido pelos dois maiores autovetores de componentes principais . Com a última alternativa, o aprendizado é muito mais rápido porque os pesos iniciais já fornecem uma boa aproximação dos pesos do SOM.

A rede deve ser alimentada com um grande número de vetores de exemplo que representam, o mais próximo possível, os tipos de vetores esperados durante o mapeamento. Os exemplos geralmente são administrados várias vezes como iterações.

O treinamento utiliza aprendizagem competitiva . Quando um exemplo de treinamento é fornecido à rede, sua distância euclidiana para todos os vetores de peso é calculada. O neurônio cujo vetor de peso é mais semelhante à entrada é chamado de unidade de melhor correspondência (BMU). Os pesos do BMU e dos neurônios próximos a ele na grade SOM são ajustados para o vetor de entrada. A magnitude da mudança diminui com o tempo e com a distância da grade do BMU. A fórmula de atualização para um neurônio v com vetor de peso W v (s) é

,

onde s é o índice do passo, t um índice na amostra de treinamento, u é o índice do BMU para o vetor de entrada D (t), α (s) é um coeficiente de aprendizagem monotonicamente decrescente ; Θ (u, v, s) é a função de vizinhança que fornece a distância entre o neurônio u e o neurônio v no passo s. Dependendo das implementações, t pode varrer o conjunto de dados de treinamento sistematicamente (t é 0, 1, 2 ... T-1, em seguida, repetir, sendo T o tamanho da amostra de treinamento), ser retirado aleatoriamente do conjunto de dados ( amostragem bootstrap ) ou implementar algum outro método de amostragem (como jackknifing ).

A função de vizinhança Θ (u, v, s) (também chamada de função de interação lateral ) depende da distância da grade entre o BMU (neurônio u ) e o neurônio v . Na forma mais simples, é 1 para todos os neurônios próximos o suficiente de BMU e 0 para os outros, mas as funções de chapéu gaussiano e mexicano também são escolhas comuns. Independentemente da forma funcional, a função de vizinhança diminui com o tempo. No início, quando o bairro é amplo, a auto-organização se dá em escala global. Quando a vizinhança encolheu para apenas alguns neurônios, os pesos estão convergindo para as estimativas locais. Em algumas implementações, o coeficiente de aprendizagem α e a função de vizinhança Θ diminuem de forma constante com o aumento de s, em outras (em particular aquelas onde t varre o conjunto de dados de treinamento), eles diminuem em etapas, uma vez a cada T etapas.

Processo de treinamento de SOM em um conjunto de dados bidimensional

Este processo é repetido para cada vetor de entrada por um número (geralmente grande) de ciclos λ . A rede acaba associando nós de saída a grupos ou padrões no conjunto de dados de entrada. Se esses padrões puderem ser nomeados, os nomes podem ser anexados aos nós associados na rede treinada.

Durante o mapeamento, haverá um único neurônio vencedor : o neurônio cujo vetor de peso está mais próximo do vetor de entrada. Isso pode ser determinado simplesmente calculando a distância euclidiana entre o vetor de entrada e o vetor de peso.

Embora a representação de dados de entrada como vetores tenha sido enfatizada neste artigo, qualquer tipo de objeto que possa ser representado digitalmente, que tenha uma medida de distância apropriada associada a ele, e no qual as operações necessárias para o treinamento sejam possíveis, pode ser usado para construir um self -organizando mapa. Isso inclui matrizes, funções contínuas ou até mesmo outros mapas auto-organizáveis.

Variáveis

Estas são as variáveis ​​necessárias, com vetores em negrito,

  • é a iteração atual
  • é o limite de iteração
  • é o índice do vetor de dados de entrada de destino no conjunto de dados de entrada
  • é um vetor de dados de entrada de destino
  • é o índice do nó no mapa
  • é o vetor de peso atual do nó
  • é o índice da melhor unidade correspondente (BMU) no mapa
  • é uma restrição devido à distância da BMU, geralmente chamada de função de vizinhança, e
  • é uma restrição de aprendizagem devido ao progresso da iteração.

Algoritmo

  1. Randomizar os vetores de peso do nó em um mapa
  2. Escolha aleatoriamente um vetor de entrada
  3. Percorra cada nó no mapa
    1. Use a fórmula da distância euclidiana para encontrar a similaridade entre o vetor de entrada e o vetor de peso do nó do mapa
    2. Rastreie o nó que produz a menor distância (este nó é a melhor unidade de correspondência, BMU)
  4. Atualize os vetores de peso dos nós na vizinhança do BMU (incluindo o próprio BMU) puxando-os para mais perto do vetor de entrada
  5. Aumente e repita a partir da etapa 2 enquanto

Algoritmo alternativo

  1. Randomizar os vetores de peso dos nós do mapa
  2. Percorra cada vetor de entrada no conjunto de dados de entrada
    1. Percorra cada nó no mapa
      1. Use a fórmula da distância euclidiana para encontrar a similaridade entre o vetor de entrada e o vetor de peso do nó do mapa
      2. Rastreie o nó que produz a menor distância (este nó é a melhor unidade de correspondência, BMU)
    2. Atualize os nós na vizinhança do BMU (incluindo o próprio BMU) puxando-os para mais perto do vetor de entrada
  3. Aumente e repita a partir da etapa 2 enquanto

Opções de inicialização

A seleção de pesos iniciais como boas aproximações dos pesos finais é um problema bem conhecido para todos os métodos iterativos de redes neurais artificiais, incluindo mapas auto-organizáveis. Kohonen propôs originalmente a iniciação aleatória de pesos. (Essa abordagem é refletida pelos algoritmos descritos acima.) Mais recentemente, a inicialização do componente principal, em que os pesos iniciais do mapa são escolhidos a partir do espaço dos primeiros componentes principais, tornou-se popular devido à reprodutibilidade exata dos resultados.

Uma comparação cuidadosa da iniciação aleatória com a inicialização do componente principal para um mapa unidimensional, entretanto, descobriu que as vantagens da inicialização do componente principal não são universais. O melhor método de inicialização depende da geometria do conjunto de dados específico. A inicialização do componente principal era preferível (para um mapa unidimensional) quando a curva principal que se aproximava do conjunto de dados poderia ser projetada de forma univalente e linear no primeiro componente principal (conjuntos quase-lineares). Para conjuntos de dados não lineares, no entanto, a iniciação aleatória teve um desempenho melhor.

Interpretação

Representação cartográfica de um mapa auto-organizado ( U-Matrix ) com base nos dados de artigos apresentados pela Wikipedia (frequência de palavras). A distância é inversamente proporcional à semelhança. As "montanhas" são bordas entre aglomerados. As linhas vermelhas são links entre artigos.
SOM unidimensional versus análise de componente principal (PCA) para aproximação de dados. SOM é uma linha tracejada vermelha com quadrados, 20 nós. O primeiro componente principal é apresentado por uma linha azul. Os pontos de dados são os pequenos círculos cinza. Para PCA, a fração de variância não explicada neste exemplo é 23,23%, para SOM é 6,86%.

Existem duas maneiras de interpretar um SOM. Como na fase de treinamento os pesos de toda a vizinhança são movidos na mesma direção, itens semelhantes tendem a excitar os neurônios adjacentes. Portanto, o SOM forma um mapa semântico em que amostras semelhantes são mapeadas juntas e as diferentes separadas. Isso pode ser visualizado por uma matriz U (distância euclidiana entre vetores de peso de células vizinhas) do SOM.

A outra maneira é pensar nos pesos neuronais como ponteiros para o espaço de entrada. Eles formam uma aproximação discreta da distribuição de amostras de treinamento. Mais neurônios apontam para regiões com alta concentração de amostra de treinamento e menos onde as amostras são escassas.

SOM pode ser considerada uma generalização não linear da análise de componentes principais (PCA). Foi demonstrado, usando dados geofísicos reais e artificiais, que o SOM tem muitas vantagens sobre os métodos convencionais de extração de características , como Funções Ortogonais Empíricas (EOF) ou PCA.

Originalmente, o SOM não foi formulado como uma solução para um problema de otimização. No entanto, tem havido várias tentativas para modificar a definição de SOM e para formular um problema de otimização que dá resultados semelhantes. Por exemplo, os mapas elásticos usam a metáfora mecânica da elasticidade para aproximar as variedades principais : a analogia é uma membrana elástica e uma placa.

Exemplos

Dados da flor da íris de Fisher

Considere uma matriz n × m de nós, cada um dos quais contém um vetor de peso e está ciente de sua localização na matriz. Cada vetor de peso tem a mesma dimensão do vetor de entrada do nó. Os pesos podem ser inicialmente definidos para valores aleatórios.

Agora precisamos de informações para alimentar o mapa. As cores podem ser representadas por seus componentes vermelho, verde e azul. Consequentemente, iremos representar as cores como vetores no cubo unitário do espaço vetorial livre sobre gerado pela base :

R = <255, 0, 0>
G = <0, 255, 0>
B = <0, 0, 255>

O diagrama mostrado

Mapas auto-organizáveis ​​(SOM) de três e oito cores com U-Matrix.

compara os resultados do treinamento nos conjuntos de dados

threeColors = [255, 0, 0], [0, 255, 0], [0, 0, 255]
oito cores = [0, 0, 0], [255, 0, 0], [0, 255, 0], [0, 0, 255], [255, 255, 0], [0, 255, 255], [255, 0, 255], [255, 255, 255]

e as imagens originais. Observe a notável semelhança entre os dois.

Da mesma forma, após treinar uma grade 40 × 40 de neurônios para 250 iterações com uma taxa de aprendizado de 0,1 na íris de Fisher , o mapa já pode detectar as principais diferenças entre as espécies.

Mapa de auto-organização (SOM) do conjunto de dados de flores de íris de Fisher com U-Matrix. Superior esquerdo: uma imagem colorida formada pelas primeiras três dimensões dos vetores de peso SOM quadridimensionais. Superior direito: uma imagem em pseudo-cor da magnitude dos vetores de peso do SOM. Esquerda inferior: uma matriz U (distância euclidiana entre vetores de peso de células vizinhas) do SOM. Parte inferior direita: Uma sobreposição de pontos de dados (vermelho: I. setosa , verde: I. versicolor e azul: I. virginica ) na matriz U com base na distância euclidiana mínima entre os vetores de dados e os vetores de peso SOM.

De outros

Alternativas

  • O mapa topográfico generativo (GTM) é uma alternativa potencial aos SOMs. No sentido de que um GTM requer explicitamente um mapeamento suave e contínuo do espaço de entrada para o espaço do mapa, ele preserva a topologia. No entanto, em um sentido prático, essa medida de preservação topológica está faltando.
  • A rede de mapas auto-organizáveis ​​adaptáveis ​​ao tempo (TASOM) é uma extensão do SOM básico. O TASOM emprega taxas de aprendizagem adaptativas e funções de vizinhança. Também inclui um parâmetro de dimensionamento para tornar a rede invariável em relação ao dimensionamento, translação e rotação do espaço de entrada. O TASOM e suas variantes têm sido usados ​​em várias aplicações, incluindo clustering adaptativo, limiarização multinível, aproximação de espaço de entrada e modelagem de contorno ativo. Além disso, foi proposta uma Árvore Binária TASOM ou BTASOM, semelhante a uma árvore natural binária com nós compostos por redes TASOM, onde o número de seus níveis e o número de seus nós são adaptativos ao seu ambiente.
  • O mapa de auto-organização crescente (GSOM) é uma variante crescente do mapa de auto-organização. O GSOM foi desenvolvido para resolver o problema de identificação de um tamanho de mapa adequado no SOM. Ele começa com um número mínimo de nós (geralmente quatro) e desenvolve novos nós na fronteira com base em uma heurística. Usando um valor denominado fator de propagação , o analista de dados tem a capacidade de controlar o crescimento do GSOM.
  • A abordagem dos mapas elásticos toma emprestado da interpolação spline a ideia de minimização da energia elástica . No aprendizado, ele minimiza a soma da energia quadrática de flexão e alongamento com o erro de aproximação de mínimos quadrados .
  • A abordagem conforme que usa mapeamento conforme para interpolar cada amostra de treinamento entre os nós da grade em uma superfície contínua. Um mapeamento suave um-para-um é possível nesta abordagem.
  • O mapa orientado e escalável (OS-Map) generaliza a função de vizinhança e a seleção vencedora. A função de vizinhança gaussiana homogênea é substituída pela matriz exponencial. Assim, pode-se especificar a orientação no espaço do mapa ou no espaço de dados. O SOM tem uma escala fixa (= 1), de modo que os mapas "descrevem de maneira ótima o domínio de observação". Mas que tal um mapa cobrindo o domínio duas vezes ou em n vezes? Isso envolve a concepção de escala. O OS-Map considera a escala como uma descrição estatística de quantos nós de melhor correspondência uma entrada tem no mapa.

Veja também

Notas

Referências