Introdução aos Self Organizing Maps

On 10 de junho de 2017 by Mateus Coelho

Self-Organizing Maps são um dos tipos mais antigos de Rede Neural Artificial ainda em uso. Elas classificam cada instância apresentada na entrada em um entre diversos grupos distintos. Dados com maior similaridade serão agrupados juntos, de maneira semelhante a métodos de clustering.

Introdução aos Self Organizing Maps

Redes Neurais Artificiais são estruturas computacionais criadas com base no funcionamento de redes de neurônios biológicos. As primeiras aparições das ideias fundamentais foram no final da década de 1940 e início da década de 1950, a partir das ideias e modelos construídos por neuropsiquiatras e psicólogos. Os experimentos pioneiros nesse sentido foram realizados na segunda metade da década de 50, e as Redes Neurais Artificiais voltaram a ficar em evidência na década de 80, quando passaram a integrar de vez o cenário das publicações de renome internacional. As arquiteturas, modelos utilizados e funções associadas às redes neurais são diversas, e cada arquitetura pode ser alvo de estudo individual. Essas Redes são invariavelmente constituídas de estruturas individuais denominadas neurônios, que recebem um conjunto de entradas e as analisam gerando uma saída.

Self-Organizing Maps, ou abreviadamente SOM’s, são Redes Neurais Artificias que utilizam uma das arquiteturas mais clássicas ainda em uso, e foi por esse motivo escolhida pelo autor do livro Artificial Intelligence for Humans Vol. 3 – Deep Learning and Neural Networks para ser a primeira a receber uma análise mais detalhada. Na figura a seguir é possível ver um exemplo de organização de SOM.

Self-Organizing Map

SOM’s classificam dados de entradas em grupos. Em algoritmos de aprendizado de máquina, muitas vezes há problemas que procuram ser resolvidos da mesma maneira. Esses algoritmos, bastante conhecidos e estudados na área de otimização, também buscam agrupar os dados em grupos. Contudo, diferentemente de métodos de clustering como o k-means, ele não precisa analisar um conjunto inicial de dados para treinar, tendo em vista que o aprendizado dele é não supervisionado, ou seja, ele não depende de conhecer um conjunto de respostas certas para aprender um padrão e agrupar os dados.

Self-Organizing Maps

Introduzidos em 1988, essas redes neurais possuem apenas duas camadas, uma de entrada e uma de saída, e não utilizam Bias para ajuste de resposta. Bias é um termo que é adicionado junto às entradas de neurônios de algumas Redes Neurais para ajuste da saída. Self-Organizing Maps também são chamados de Redes Neurais de Kohonen, em homenagem ao pesquisador a quem se atribuem os créditos pela criação e divulgação do algoritmo. Cada neurônio possui um conjunto de pesos, que nesse caso são valores que serão comparados com a entrada para obter o resultado. A saída compara o conjunto de dados de entrada de acordo com a distância euclidiana entre os valores de entrada e os pesos, O neurônio com maior similaridade, ou seja, menor distância euclidiana, vence.

Diferentemente de outras redes neurais, é importante saber como a estrutura dos neurônios está organizada no espaço. Inicialmente isso parece não fazer sentido para quem já conhece outras arquiteturas de Redes Neurais, tendo em vista que a maioria delas dificilmente se preocupa com a ordem em que os neurônios estão colocados. Contudo, ao analisar a maneira com que o treinamento é realizado, essa necessidade ficará evidenciada. Comumente utilizam-se estruturas uni, bi ou tridimensionais para agrupar os neurônios, e é preciso mapear a ordem das entradas, e saber a posição de cada neurônio:

  • Linha (Unidimensional)
  • Grid (Bidimensional)
  • Cubo (Tridimensional)

Implementação de um Self-Organizing Map

Para analisar o funcionamento e a implementação de um Self-Organizing Map, as estruturas e funções serão implementadas baseadas nas estruturas sugeridas pelo site AI-Junkie.  Apesar das estruturas do site serem implementadas com Programação Orientada a Objetos, especificamente usando a linguagem C++, essas implementações seguem estruturas mais simples, que podem ser implementadas em linguagens com níveis menores de abstração. A linguagem de foco será a linguagem C.

Inicialmente, é interessante ter um tipo abstrato de dados que agrupa as variáveis que caracterizam o neurônio. Esse tipo de estrutura é importante para organizar os dados, padronizar e abstrair da implementação de cada variável separadamente. Um neurônio é composto basicamente por seu conjunto de pesos. O trecho de código a seguir representa essa implementação em C.

typedef struct tneuron{
	double weightVec[NUMWEIGHTS];    //VETOR DE PESOS
	//NUMWEIGHTS - VARIAVEL QUE ARMAZENA O NUMERO DE PESOS
} Neuron;

int initNeuron(Neuron * N)  //FUNCAO QUE INICIALIZA OS VALORES DOS PESOS
{
    srand(time(NULL));
    for (int i = 0; i < NUMWEIGHTS; i++)
    {
		N->weightVec[i] = (double)rand() / RAND_MAX; //BIBLIOTECE <time.h> GERA NUMERO ALEATORIO ENTRE
    }//0.0 E 1.0 UNIFORMEMENTE DISTRIBUIDO
    return 0;
}

Essas funções permitem que na função principal seja iniciada um vetor ou matriz de neurônios, e que para cada neurônio seja associado um peso aleatório de valor pequeno. Estando a inicialização realizada de maneira correta na função principal, é possível iniciar a etapa de treinamento do SOM.

Treinamento de Self-Organizing Maps

Conforme mencionado, uma rede neural precisa ser treinada para realizar determinada tarefa. O treinamento de SOM’s acontece inicializando os pesos das entradas de cada neurônio com um valor aleatório. Após essa etapa, ele seleciona aleatoriamente um numero de elementos do conjunto de entradas.O treinamento de SOM’s é iterativo, e ocorre em um número fixo de iterações determinado pelo desenvolvedor. A cada iteração, um dos elementos do conjunto de treinamento é selecionado. Esse treinamento se inicia medindo a distância de uma instância de entrada para o vetor de pesos de cada entrada. Para isso, utilizamos a seguinte função, que mede essa distância euclidiana.

Função que calcula a distância euclidiana

double getDistance (double input[NUMWEIGHTS], Neuron N)
//FUNCAO: DISTANCIA EUCLIDIANA ENTRE UMA ENTRADA E UM VETOR DE PESOS
{
    double dist = 0.0;
    
    for (int i = 0; i < NUMWEIGHTS; i++)
        dist += dist + (input[i] - N.weightVec[i])*(input[i] - N.weightVec[i]);
    
    return sqrt(dist);
}

Após comparar a distância euclidiana com o peso de cada entrada, o neurônio com menor distância euclidiana para essa amostra é encontrado. Esse neurônio é denominado BMU (Best Matching Unit), e a função de treinamento usada nesse tipo de rede faz com que esse neurônio receba mais treinamento, e quanto mais distantes dessa amostra os demais neurônios forem, menos treinamento eles recebem. Por esse motivo é tão importante saber onde cada neurônio está posicionado. Para encontrar o BMU em uma matriz NxN neurônios, a função utilizada teria estrutura semelhante à seguinte, usando um tipo abstrato de dados para encapsular o endereço de um neurônio.

Estrutura de dados e função para encontrar o BMU

typedef struct taddr
{
    int x, y;
} address;

address findBMU(Neuron SOM[n][n], double input[NUMWEIGHTS])
//FUNCAO: ENCONTRA O NEURONIO COM MENOR DISTANCIA (BMU)
{
    address BMU;
    BMU.x = 0;
    BMU.y = 0;
    
    double dist = getDistance(input, SOM[0][0]);
    
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (getDistance(input, SOM[i][j]) < dist)
            {
                dist = getDistance(input, SOM[i][j]);
                BMU.x = i;
                BMU.y = j;
            }
        }
    }
    return BMU;
}

A partir do BMU, se inicia o treinamento do SOM. Iterativamente todos os neurônios do mapa serão treinados. A cada iteração, os pesos de cada neurônio da rede são atualizados de acordo com uma função de treinamento. O BMU receberá uma carga máxima de treinamento, e quanto mais próximos a ele estão os neurônios, maior a carga de treinamento. Além disso, todos os neurônios serão atualizados de acordo com uma taxa de aprendizado, que pode ser constante ou uma função que decresce o valor a cada iteração. A equação que caracteriza esse treinamento é:

Na equação acima, Wv(t+1) representa os valores dos pesos atualizados, que serão recalculados a cada iteração, que é o objetivo final do treinamento. Wv(t) representa os pesos atuais, θ(v,t) é a função de vizinhança, α(t) é a taxa de aprendizado e a cláusula [D(t)-Wv(t)] é o que torna o peso local mais semelhante à amostra de treinamento indicada. Analisando esse treinamento, é perceptível que queremos atualizar os pesos a uma determinada taxa, de acordo com a distância euclidiana entre ele e a amostra de treinamento, mas também queremos que esse treinamento seja ponderado pela distância entre o neurônio atual e o BMU. A função que pondera esse treinamento é chamada função de vizinhança.

Taxa de aprendizado

A taxa de aprendizado é o elemento que pondera a velocidade de aprendizado de um neurônio. De acordo com essa definição, é possível pensar que essa taxa deveria assumir o maior valor possível. Contudo, o aprendizado da maneira como é realizado não tem que ser simplesmente rápido. É desejável que quanto mais treinada a rede esteja, a característica dos pesos mude cada vez menos. O aprendizado deve ser, portanto, estável. Algumas Redes Neurais usam taxas de aprendizado constantes, mas elas podem também ser recalculadas a cada iteração para se tornarem funções decrescentes.

Utilizando como exemplo uma taxa de aprendizado que possui valor decrescente, baseado na seguinte função, onde t é a contagem da iteração atual (t = 0, 1, 2…), e λ é o número máximo de iterações:

Função que calcula a taxa de aprendizado

//Lo E MAXITER DEFINIDOS NO ESCOPO
double tRate (int t)
//FUNCAO: VALOR DA TAXA DE APRENDIZADO
{
	return Lo*exp(-1 * ((double)t) / ((double)MAXITER));
}

Funções de Vizinhança

As funções de vizinhança mostram a proximidade do neurônio analisado com o BMU. Em geral, as funções de vizinhança utilizadas apresentam valor 1 (um) caso o neurônio comparado seja o próprio BMU, e valores que decrescem até 0 (zero). Alguns tipos de treinamento podem aplicar valores negativos na função de vizinhança, que funcionam como penalidades para vizinhos muito distantes. A dimensionalidade dessa função segue a dimensionalidade da representação da rede, ou seja, tipicamente utilizam-se representações unidimensionais ou bidimensionais.

Função de Vizinhança Gaussiana

Uma das funções mais utilizadas com função de vizinhança é a Gaussiana, que segue a equação:

A Gaussiana é muitas vezes chamada de “Distribuição Normal”, tendo em vista que muitos processos naturais e muitas distribuições estocásticas possuem essa característica. A representação da função gaussiana no plano cartesiano pode ser vista na figura a seguir.

Exemplo de distribuição Gaussiana

A função de vizinhança Gaussiana pode ser aplicada em várias tarefas distintas, como reconhecimento de fala automático, sistemas automáticos de recomendação de música e até em aplicações para tentar prever falência de empresas.

Função de Vizinhança de Ricker

Outra delas é a função de onda de Ricker, também chamada de função “Chapéu Mexicano”, que pode ser representada por:

Essa função “Chapéu Mexicano” é interessante pois aplica não somente uma diminuição no aprendizado, mas uma penalidade quando o neurônio está muito afastado do BMU. É possível observar esse comportamento analisando a representação dessa função no plano cartesiano, apresentada na figura a seguir. Essa função é usada para análise de componentes de dados sísmicos, por exemplo.

Exemplo de distribuição de Ricker

Na implementação de exemplo, será usada uma função de vizinhança gaussiana. Para isso, é preciso codificar a função representada na equação da distribuição gaussiana. Contudo, nessa aplicação a função de raio será modificada para que o raio de ação do treinamento diminua com o tempo. Dessa forma, a nova equação da gaussiana de vizinhança tem a seguinte forma:

onde σ(t) vale:

O raio σ de ação do treinamento diminui com o tempo. O termo η é um valor fixo e predefinido. Seguindo a recomendação da fonte, esse valor será a divisão do número de iterações pelo logaritmo do tamanho de uma linha da matriz.

Função que calcula o raio de ação da função exponencial e função de vizinhança

double radius(int t, address BMU)
//FUNCAO: RAIO DE ACAO DA FUNCAO EXPONENCIAL
{
	double maxRadius = min(min(BMU.x - 0, n - BMU.x), min(BMU.y - 0, n - BMU.y));
	//MAXIMO RAIO DE ACAO: PERPENDICULAR ATE A PAREDE
	//MAIS PROXIMA

	return (maxRadius * exp(-1 * ((double)t) / (((double)MAXITER) / log((double)n))));
}

double hood(int t, address BMU, address N)
//FUNCAO DE VIZINHANCA
{	
	//GAUSSIANA DE VIZINHANCA
	return exp(
		sqrt(-1 * (((N.x-BMU.x)*(N.x-BMU.x))/((N.y-BMU.y)))/
		(2 * radius(t, BMU)*radius(t, BMU))));
}

Dessa maneira já é possível definir uma função para o treinamento do SOM. O escopo da função de treinamento pode ser visto na função a seguir.

Treinamento de um Self-Organizing Map

//TAD PARA FACILITAR CHAMADA POR REFERENCIA
typedef struct tMap{
	Neuron SOM[n][n];
} Map;

//FUNCAO DE TREINAMENTO DO SELF ORGANIZING MAP
//INPUTSIZE INFORMADO NO ESCOPO GLOBAL
void trainSOM(Map * SOM, double inpConj[INPUTSIZE][NUMWEIGHTS])
{
	srand(time(NULL)); 

	double train[5][NUMWEIGHTS];	//5 ELEMENTOS NO CONJUNTO DE TREINAMENTO

	for (int i = 0; i < 5; i++)
	{
		int r = rand()%INPUTSIZE;
		for (int j = 0; j < NUMWEIGHTS; j++) 
			train[i][j] = inpConj[r][j];
	}

	//INICIALIZACAO DOS PESOS ALEATORIOS DOS NEURONIOS
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			initNeuron(&(SOM->SOM[i][j]));
		}
	}

	//LOOP DE TREINAMENTO
	for (int i = 0; i < MAXITER; i++)
	{
		for (int j = 0; j < 5; j++)
		{
			double input[NUMWEIGHTS];

			for (int v = 0; v < NUMWEIGHTS; v++) 
				input[v] = train[j][v];

			address BMU;
			BMU = findBMU(SOM->SOM, input);

			for (int j = 0; i < n; i++)
			{
				for (int k = 0; j < n; j++)
				{
					for (int l = 0; k < NUMWEIGHTS; k++)
					{
						address N;
						N.x = i;
						N.y = j;

						SOM->SOM[j][k].weightVec[l] = SOM->SOM[j][k].weightVec[l] + 
							tRate(i) *
							hood(i, BMU, N) *
							(input[l] - SOM->SOM[j]n[k].weightVec[l]);
					}
				}
			}
		}
	}
}

Cálculo do Erro de saída dos Self-Organizing Maps

Redes Neurais Artificiais utilizam uma métrica para medir a assertividade de uma solução. Em casos onde a rede usa um aprendizado supervisionado, na etapa de treinamento é possível analisar diretamente a qualidade da solução atual comparando a saída produzida pela rede com a configuração atual com a saída ideal. Basta então observar se as amostras correspondem ao esperado.

Para mensurar o erro de uma solução que usa Self-Organizing Maps, não é possível fazer uma análise direta da saída como em casos onde se utiliza aprendizado supervisionado, pois não há conjunto de saída conhecido. A métrica utilizada então é a maior distância euclidiana registrada entre uma BMU e uma instância de entrada registrada em uma iteração. Na figura a seguir é possível observar a evolução do fator de erro de um SOM.

Evolução do Erro de um SOM

Aplicações Práticas de Self-Organizing Maps

Análise de dados de condição socioeconômica do Banco Mundial usando Self-Organizing Maps

Uma das aplicações mais conhecidas de Self-Organizing Maps são problemas que envolvem reconhecimento de cores. Imagine um mapa mundi onde a qualidade de vida de cada país é reconhecida por uma cor, com base em algum índice. Muitas vezes pode ser complexo saber como os países estão agrupados, ou seja, quais países tem qualidade de vida semelhante de acordo com esse índice. Um Self-Organizing Map pode ser treinado para agrupar os países por cores. Essa aplicação foi utilizada em 1992 utilizando as estatísticas do banco mundial.

Mapa mundi gerado pelo Banco Mundial

Classificação dos países usando um Self-Organizing Map

No mapa da primeira figura não é tão simples visualizar a maneira com que os países estão agrupados. Após o tratamento de dados usando Self-Organizing Maps, foi possível compreender melhor quais países possuíam índices semelhantes de acordo com esse índice do Banco Mundial. O resultado da análise dos dados utilizando um SOM treinado pode ser visualizado na segunda figura.

Previsão de de vida útil residual em rolamentos de esferas usando Self-Organizing Maps

Rolamentos de esferas são estruturas utilizadas em praticamente todas as aplicações que envolvem máquinas em rotação. Falhas em rolamentos de esferas podem ser críticas, portanto existe uma necessidade de se monitorar e prever a vida útil e planejar a substituição das peças antes que elas causem um incidente na máquina, que pode causar custos altos relacionados a paradas na produção e reparos, além de eventualmente poderem causar perdas humanas. Na figura a seguir é possível observar rolamentos de esferas de diversos tamanhos, que serão utilizados para diversos fins.

Rolamentos de Esferas

A maneira mais eficiente de monitorar a vida útil de um rolamento é através da análise de vibração. Para substituir a manutenção corretiva, é importante ter um processo eficiente de manutenção preditiva. Consequentemente, as ferramentas de prognóstico devem ser avançadas. Uma abordagem encontrada para analisar esses danos foi a normalização dos dados de vibração de um rolamento em um vetor de entrada que alimenta um Self-Organizing Map. Os dados de saída serão depois pós-processados para tentar prever o tempo de vida útil restante.

fonte: https://goo.gl/3ob0Lt

Relação contextual entre palavras usando Self Organizing Maps

A relação contextual de palavras pode ser visualizado através de um Self-Organizing Map. Isso significa que as linguagens naturais seguem uma lógica que pode ser interpretada. A área de pesquisa que realiza esse tipo de trabalho é chamada de processamento de linguagem natural.

O pesquisador Timo Honkela, realizou estudos, em parceria e sob orientação do próprio Kohonen, para analisar análise da relação contextual de itens. Para isso, em uma fase de pré-processamento, artigos definidos e indefinidos são removidos do texto, e todas as letras maiúsculas são transformadas em minúsculas.

Self-Organizing Map para processamento de linguagem Natural

O uso de Self-Organizing Maps para processamento de linguagem natural foi amplamente divulgado na comunidade acadêmica. Há diversos artigos de trabalhos realizados nesse sentido. Um exemplo de mapa produzido utilizando essa ferramenta pode ser visto na figura acima.

fonte: https://goo.gl/MpDJHk

Diagnóstico de Câncer de Mama através de imagens de Ultrassonografia usando Self-Organizing Maps

O câncer de mama é o segundo tipo de câncer mais comum do mundo, é mais comum entre as mulheres, embora possa aparecer também em homens e responde por 22% dos novos casos de câncer todos os anos.  O processamento de imagens de ultrassonografia busca distinguir tumores benignos e malignos, para auxiliar no diagnóstico desse tipo de câncer. A intensidade e textura de uma anomalia identificada nesse exame pode ser identificada como benigna ou maligna utilizando Self-Organizing Maps.

Imagem obtida por ultrassonografia onde uma anomalia foi detectada

Na figura acima é possível ver uma imagem onde uma anomalia foi identificada. No processo de diagnóstico assistido por SOM, apenas a região de interesse é analisada. Essa região é o retângulo de menores lados que contem integralmente toda a anomalia identificada, com margem de 1 a 2 mm. O Self-Organizing Map analisa então a correlação da textura de pixels adjacentes para classificar os tumores.

fonte: http://www.sciencedirect.com/science/article/pii/S0301562999001568

Summary
Review Date
Reviewed Item
Self-Organized Maps
Author Rating
51star1star1star1star1star

Deixe um comentário

O seu endereço de e-mail não será publicado.