\section{O método SKATER}
\label{sec:skater}

O SKATER - Spatial 'K'luster Analisys 
Through Edge Removal - é uma metodologia 
proposta para fazer análise de agrupamentos 
de dados espaciais, \cite{assuncao:02} e 
\cite{assuncao:06}. 
Essa metodologia é dividida em duas partes: 
A construção de uma árvore geradora mínima 
e a remoção de galhos dessa árvore. 

Suponhamos que temos uma região $\bD$ 
particionada em áreas $v_1, ..., v_n$, 
com $v_i \cup v_j = \emptyset$ para $i\neq j$. 
Seja o vetor de dados $\by=\{y_1,y_2,...,y_n\}$, 
com $y_i$ a observação da área $v_i$.
Nós estamos interessados procurar $k$ grupos, 
$g_1, ..., g_k$ com $\bigcup_{i=0}^{k}g_i = \bD$ 
e $g_i = \bigcup_{j\in I_i}v_j$ em que $I_i$ é o 
conjunto de índices do grupo $i$ 
contido em $\{1,2,...,n\}$. 

Inicialmente, vamos considerar uma matriz de 
adjacência $\bA$ associada à uma estrutura de 
vizinhança entre as áreas pertencentes à região $\bD$. 
$\bA$ define o grafo $\bG_D$ da estrutura de 
vizinhança da região $\bD$. Formalmente o grafo 
$\bG_D$ é definido pelos conjunto de vértices $\bV_D$, 
que são as áreas $v_1, v_2, ..., v_n$, e por um 
conjunto de arestas $\bE_D$ definidas a partir da 
matriz de adjacência. O vértice $(i,j)$ existe 
se a área (nó) $i$ é vizinha da área (nó) $j$. 

\subsection{A árvore geradora mínima}

A árvore geradora mínima, ou 
\textit{minimum spanning tree}-(MST), 
das $n$ áreas (nós) é um grafo conectado 
$\Upsilon$ com $n$ nó e $n-1$ arestas. 
Sendo $\Upsilon$ um grafo conectado, então é 
possível partir de um nó $v_i$ qualquer e chegar a 
um nó $v_j$ qualquer andando pelo conjunto de 
$n-1$ arestas de $\Upsilon$. 
Além disso, se uma aresta de $\Upsilon$ é removida, 
ocorre a divisão de $\Upsilon$ em dois grafos, cada um 
é uma MST, mas os nós de uma não estão conectados com 
os nós da outra. Portanto, a remoção de uma aresta de 
$\Upsilon$ gera dois grupos de nós cujas 
áreas de cada grupo são contíguas.

Os vértices de uma MST são aqueles que fazem com que 
a soma dos custos associados a cada um seja mínima. 
Considerando as observações $y_1, y_2, ..., y_n$, 
precisamos definir uma medida de custo em $\{y_i,y_j\}$ 
para calcular o custo da aresta $(i,j)$. 
Essa medida é chamada de medida de similaridade 
(ou dissimilaridade) entre as áreas $v_i$ e $v_j$.
Dada uma medida $d(i,j)=d_{ij}$ de dissimilaridade,
a MST é o conjunto de arestas $e_1, e_2, ..., e_{n-1}$ 
que minimiza $\sum_{j=1}^{n-1}d(e_j)$. 

A MST pode ser gerada utilizando o algoritmo de 
Prim, \cite{prim:57}. Esse altoritmo inicia com 
um conjunto  vazio de nós, $\bV_{in}=\emptyset$, 
e um conjunto vazio de arestas, $\Upsilon=\emptyset$. 
No primeiro passo, qualquer nó $i$ do conjunto de $n$
nós pode ser selecionado e colocado em $\bV_{in}$.
Em seguida a MST é gerada com o seguinte algoritmo.
\begin{enumerate}
\item Calcule a medida de dissimilaridade entre os nós
em $\bV_{in}$ seus vizinhos que não estão em $\bV_{in}$
\item Encontre os nós $v_i$ e $v_j$, com $v_i\in \bV_{in}$ 
e $v_j\notin \bV_{in}$, com a menor medida de dissimilaridade
\item Faça $v_j$ pertencer a $\bV_{in}$
\item Faça o vértice $(i,j)$ pertencer a $\Upsilon$
\item Retorne ao primeiro passo enquanto existir algum vértice
não pertencente a $\bV_{in}$
\end{enumerate}
O conjunto de vértices $\Upsilon$ retornado é a MST. 
$\Upsilon$ é única se e somente se a medida de 
dissimilaridade é contínua e $d_{ij}\neq d_{rs}$ 
para qualquer conjunto de pares $(i,j)$ e $(r,s)$ 
com $(i,j)\neq (r,s)$. 

\subsection{O procedimento de remoção de arestas}

O segundo passo do procedimento SKATER é a remoção 
sucessiva de arestas de $\Upsilon$. 
A cada remoção, um grupo é subdividido em dois, 
isso divide a MST em duas MST. 
A remoção de arestas pode ser feita até que todas os 
nós estejam isolados, porém é necessário estabelecer 
algum critério de parada. 
Esse critério pode ser o número de grupos, 
o tamanho dos grupos ou alguma medida da homogeneidade 
dentro dos grupos ou da heterogeneidade entre os grupos. 

No procedimento de remoção, nós poderíamos remover 
as arestas de maior custo. Porém, $d_{ij}$ é uma 
medida local de dissimilaridade. 
\citeasnoun{assuncao:06} propõe o uso da homogeneidade 
dos grupos para definir qual aresta remover. 
Seja $H(g_i)$ a homogeneidade do grupo $g_i$,  
$H_0$ a homogeneidade considerando que todos os 
nós estão no mesmo grupo e $H_k=\sum_{i=1}^k H(g_i)$ 
a soma das homogeneidades dos $k$ grupos. 
Por exemplo, nós poderíamos ter três nós $v_1$, 
$v_2$, $v_3$ e $v_4$ e o conjunto de arestas 
$\{(1,2),(2,3),(3,4)\}$, com custos 
$d_{12}<d_{2,3}<d_{3,4}$. 
Suponha que $v_2$ é muito similar a $v_4$, 
embora $v_3$ seja mais parecido com $v_2$. 
Suponha que haja uma medida de homogeneidade dentro 
dos grupos de forma que a soma da homogeneidade dos 
dois grupos obtidos pela remoção de $(1,2)$ seja 
menor que a soma da homogeneidade dentro dos grupos 
obtidos pela remoção de $(3,4)$. 
Neste caso é melhor remover a aresta $(1,2)$. 
 
Neste segundo passo, comece fazendo todos os $n$ 
nós pertencentes à um único grupo e $\Upsilon$ a 
MST associada. Calcule a homogeneidade desse grupo, $H_0$. 
Crie um vetor de tamanho $n$ para identificador de grupo.
O procedimento sequencial de remoção é o seguinte:
\begin{enumerate}
\item Calcule a soma da homogeneidade de todos os grupos 
existentes até o momento 
\item Para cada um dos grupos candidatos à divisão
 \begin{itemize}
  \item Para cada vértice do grupo
  \begin{itemize}
    \item Calcule a diferença entre a homogeneidade do grupo e a
  soma da homogeneidade calculada para cada um dos dois grupos gerados
  pela remoção dessa aresta
  \end{itemize}
 \end{itemize}
\item Encontre o vértice que cuja remoção resulta na maior
  diferença de homogeneidade
\item Corte esse vértice gerando dois grupos
\item Atualize o conjunto de nós candidatos com esses grupos
\item Atualize o vetor de identificador de grupo
\item Volte ao primeiro passo até que o critério estabelecido
 seja atingido
\end{enumerate}

É possível também estabelecer uma restrição aos grupos 
formados, por exemplo, um número mínimo de nós 
em cada grupo ou de população em cada grupo. 
Portanto a cada passo, é necessário verificar se esse 
critério estabelecido é verificado. 
Suponha que a restrição é que o número de nós em 
cada grupo seja no mínimo $3$ e temos um grupo candidato 
coma $10$ nós. Se ao dividi-lo o resultado seja um grupo 
com $8$ nós e outro com $2$ nós, esse grupo candidato 
será retirado do conjunto de grupos candidatos a divisão.

