9.2. Métodos de Agrupamento para Séries Temporais
Na literatura, existem diferentes métodos para agrupamento de dados. Segundo [151], esses métodos podem ser classificados em: (1) Métodos baseados em partição que criam partições ortogonais em um conjunto de dados (ex.: K-means); (2) Métodos baseados em hierarquia que criam uma decomposição hierárquica em conjunto de dados (ex.: Hierarchical Clustering); (3) Métodos que criam grupos com base em densidade (ex.: DBSCAN); e (4) Métodos baseados em Redes Neurais (ex. SOM).
Para agrupamento de séries temporais, um dos métodos mais utilizado é o SOM (Self-Organizing Maps), ou Mapas Auto-organizáveis em português, que é uma rede neural artificial [144]. As redes neurais artificiais (do inglês, Artificial Neural Networks, ANNs) são métodos inspirados em redes neurais biológicas e possui aplicações tanto em tarefas de classificação como em agrupamento [152]. Algumas características das ANNs que são importantes nos métodos de agrupamento são: processamento de vetores numéricos; arquiteturas de processamento inerentemente paralelas e distribuídas e aprendizado a partir de pesos por interconexões.
9.2.1. SOM (Self-Organizing Maps)
O SOM (Self-Organizing Map) é uma rede neural não supervisionada, que aplica o procedimento de aprendizado competitivo para mapear os vetores de entrada multidimensionais para uma grade bidimensional retangular ou hexagonal de baixa dimensão [153]. SOM mapeia um espaço de alta dimensão para um espaço de baixa dimensão preservando sua topologia de vizinhança. Ele é composto por uma camada de entrada (input layer) e uma de saída (output layer), sendo esta última geralmente uma grade bidimensional onde cada elemento é chamado de neurônio (2-D Neuron Grid). Uma propriedade importante do SOM é que os neurônios são organizados de forma que eles mantenham uma vizinhança similar, ou seja, neurônios que têm características similares estão próximos na camada de saída. Figura 9.9 e Figura 9.10 ilustram as camadas do SOM e a similaridade entre neurônios vizinhos.
Figura 9.9 - Camadas de entrada (input layer) e saída (output layer) do SOM (Self-Organizing Map). No mapa ou camada de saída, os neurônios pintados em laranja são vizinhos do neurônio amarelo.
Figura 9.10 - Um exemplo de uma mapa SOM 4x4. O vetor de entrada (input) é mapeado para uma grade de saída composta por neuônios (2-D Neuron Grid). O neurônio mais similar ao vetor de entrada adapta seu vetor de peso (weight vector) e dos seus neurônios vizinhos, gerando uma vizinhança similar.
Fonte: [154].
Cada neurônio \(j\) tem um vetor de peso (weight vector) n-dimensional \(w_j=[w_{1},\ldots,w_{n} ]\). Um vetor de entrada \(x(t)=[x(t)_1,\ldots,x(t)_n ]\) é associado ao neurônio mais similiar a ele, segundo uma certa métrica de distância, como Euclidiana e DTW. A distância \(D_j\) é computada entre o vetor de entrada e o vetor de peso de cada neurônio \(j\), para todos os neurônios da camada de saída:
Depois de computar todas as distâncias entre o vetor de entrada e todos os neurônios, a menor dessas distâncias identifica o Best-Matching-Unit (BMU). O BMU é o neurônio \(d_{b}\) cujo vetor de peso é o mais próximo, ou mais similar, a \(x(t)\):
Os vetores de peso do BMU e de seus vizinhos dentro de um raio \(r\) são alterados para aumentar a similaridade com o vetor de entrada:
onde \(\alpha(t)\) representa a taxa de aprendizado (learning rate), com valores entre 0 e 1 (\(0<\alpha(t)<1\)), e \(h_{b,j}\) é uma função de vizinhança (neighborhood function).
O SOM termina quando todos os vetores de entrada são representados na camada de saída. Ao longo do tempo, o valor de \(\alpha(t)\) e o raio da vizinhança devem ser reduzidos e existem diferenteres abordagens para reduzir esses valores [155].
Em resumo, no mapa SOM os neurônios competem entre si pelos vetores de entrada. Ao final de cada iteração é determinado o neurônio vencedor (BMU, do inglês Best Match Unit), aquele que possui a menor distância com o vetor de entrada apresentado na iteração. Após a escolha do BMU, todos os neurônios vizinhos em um determinado raio atualizam seus vetores de peso, para se aproximarem do padrão escolhido no BMU [153]. A Figura 9.11 a seguir apresenta uma visão geral da estrutura do SOM.
Figura 9.11 - Estrutura geral do SOM (Self-Organizing Map).
Adaptado de: [114]
9.2.2. Evolving SOM (Self-Organizing Maps)
No SOM, o tamanho da grade ou da camada de saída é fixo e definido a priori. Muitos trabalhos na literatura apontam que a definição do tamanho dessa grade é um processo empírico. A quantidade de vetores de entrada influencia no tamanho da grade [153]. Grade superestimada implica em neurônios vazios sem nenhum vetor de entrada associado, ou neurônios sem capacidades de generalização, com um único vetor de entrada associado. Subestimar a grade implica em neurônios generalistas e erros de agrupamento.
Para tentar resolver essa questão do tamanho da grade fixa do SOM, algumas variações do SOM são propostas para evoluir a grade dinamicamente ao invés de definir seu tamanho inicialmente. Essas abordagens são chamadas de Evolving SOM e alguns exemplos são: (1) Growing hierarchical self-organizing maps (GHSOM) [156]; (2) Growing cell structure of map (GCS) [157]; e (3) Growing SOM (GSOM) [158].
A Figura 9.12 mostra mapas gerados pelo SOM e pelo GSOM para séries temporais de imagens, resultado do trabalho de Adeu et. al [154].
Figura 9.12 - A topologia do mapa do SOM (a), do GSOM com initial neighborhood influence 0.6 (b) e com initial neighborhood influence 1.0 (c). O aumento do parâmetro do GSOM initial neighborhood influence resulta em clusters mais concisos e agrupados.
Adaptado de: [154]