ENHANCED SELF-ORGANIZING
INCREMENTAL NEURAL NETWORK
FOR ONLINE UNSUPERVISED
LEARNING
Cesar Lima
José Francisco
Maíra Nascimento
ROTEIRO
Introdução
 Revisão literária
 SOINN
 ESOINN
 Experimentos
 Conclusão
 Referências

INTRODUÇÃO

Aprendizagem não supervisionada
Construção de grupos (agrupamentos) de dados
baseado em suas características
 Aprendizagem de topologia


Encontrar grupos homogêneos de dados dentre
todos de um conjunto.
INTRODUÇÃO

Problemas
Custo computacional
 Armazenamento


Outros problemas referem-se a:
Inicialização do algoritmo
 Pré-definição do número desejado de clusters

INTRODUÇÃO

Algoritmos de agrupamento (clustering)


Hierárquico, por partição, fuzzy, nearest neighbor,
RNA etc.
Aprendizagem incremental

Adaptar-se a novas informações sem esquecer
informação previamente aprendida
REVISÃO LITERÁRIA

K-means e LBG
Inicialização dos parâmetros
 Determinação do número de clusters
 Ambos têm melhorias que reduzem suas limitações

REVISÃO LITERÁRIA
Redes neurais para clusterização
 “topology learning”



Geram mapeamentos entre dados em espaço de alta
dimensão para uma estrutura topológica
Redes auto-organizáveis (SOM, NG, etc.) são
utilizadas para este fim
REVISÃO LITERÁRIA

Self Organizing Map (SOM)

Estrutura predefinida
REVISÃO LITERÁRIA

Neural Gas (NG)
Competitive Hebbian Learning
 Decisão a priori do tamanho da rede


Growing Neural Gas (GNG)
Estrutura dinâmica, sem necessidade de definí-la
previamente
 Incremento constante de novos nodos, deslocamento
de centros (nodos representantes)

REVISÃO LITERÁRIA

Growing Neural Gas - Utility (GNG-U)


Remoção de nodos baseado em parâmetro de
utilidade
Limitações (GNG, GNG-U, etc)
Aumento permanente da rede
 Representação do estado atual da distribuição de
dados

SELF-ORGANIZING INCREMENTAL NEURAL
NETWORK (SOINN)

Objetivos:
Processar dados não estacionários on-line ou life-long
 Não necessitar de condições iniciais (quantidade de
classes, número de nodos, parâmetros iniciais, etc.)
 Separar classes com interseção de baixa densidade
(reportar clusters)

SELF-ORGANIZING INCREMENTAL NEURAL
NETWORK (SOINN)

Rede de duas camadas
1 ª: Densidade da distribuição dos dados
 2 ª: Separa clusters e fornece seus protótipos
representativos


Algoritmo
Recebe vetor de entrada ξ (na 1 ª camada)
 Encontra os dois nodos mais próximos: s1 e s2
 Julga se ξ pertence ao cluster s1 ou s2


Baseado em limiar adaptativo por nodo (Ts1 e Ts2 nesse
caso)
SELF-ORGANIZING INCREMENTAL NEURAL
NETWORK (SOINN)

Algoritmo (continuação)





Se ξ representa uma nova classe, adicionar nodo r
com vetor ξ à rede e reinicie com uma nova entrada.
Caso contrário crie uma nova aresta entre s1 e s2 e
zere sua idade
Incrementa a idade de todas as conexões do vencedor
Atualiza os pesos do vencedor e de seus vizinhos
Remove nodos com idade maior que agedead
SELF-ORGANIZING INCREMENTAL NEURAL
NETWORK (SOINN)

Algoritmo (continuação)

Após λ iterações
Insere um novo nodo onde o erro acumulado é maior
 Se não houver redução do erro local, cancela a inserção
 Remove nodos ruidosos
 Com nenhum ou um vizinho

SELF-ORGANIZING INCREMENTAL NEURAL
NETWORK (SOINN)

Algoritmo (continuação)

Após LT iterações
Submete os nodos atuais da rede como entrada para o
próprio algoritmo
 Gera os nodos da segunda camada
 Após aprendizagem, nodos conectados representam um
cluster

SOINN
ENHANCED SELF-ORGANIZING
INCREMENTAL NEURAL NETWORK
(ESOINN)

Principais problemas do SOINN:
Adotar rede de duas camadas
 Quando encerrar o treinamento da 1ª camada e
iniciar o da 2ª
 Requer grande número de parâmetros determinados
pelo usuário
 Separa clusters com interseção de baixa densidade

ENHANCED SELF-ORGANIZING
INCREMENTAL NEURAL NETWORK
(ESOINN)

ESOINN
Baseado no SOINN
 Herda todas as funções do SOINN
 Soluciona problemas citados
 Adota apenas uma camada


Algoritmo
Recebe vetor de entrada ξ
 Encontra os dois nodos mais próximos: s1 e s2
 Julga se ξ pertence ao cluster s1 ou s2


Baseado em limiar adaptativo por nodo (Ts1 e Ts2 nesse
caso)
ENHANCED SELF-ORGANIZING
INCREMENTAL NEURAL NETWORK
(ESOINN)

Algoritmo (continuação)
Se ξ representa uma nova classe, adiciona nodo r com vetor
ξ à rede e reinicia com uma nova entrada.
 Incrementa a idade de todas as conexões do vencedor
 Caso contrário cria uma nova aresta entre s1 e s2 e zera sua
idade, se:




s1 e s2 são nodos novos
Pertecem a mesma subclasse
Pertecem a classes diferentes e satisfazem:
 min(hs1, hs2) > αAAmax ou min(hs1, hs2) > αBBmax
Caso contrário, se existir uma conexão entre s1 e s2, ela é
removida
 Atualiza a densidade do vencedor, usando a equação: h = 1/
 Atualiza os pesos do vencedor e de seus vizinhos
 Remove nodos com idade maior que agedead
