\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. 

SKATER - Spatial 'K'luster Analisys 
Through Edge Removal - is a proposal cluster analysis 
of spatial data \cite{assuncao:02,assuncao:06}. 
The methods consists of two mais steps: the obtention 
of a \texit{minumum spanning tree}
given by a graph conecting the area 
and the posterior removal of ``stems'' of the tree, 
or edges of the graph, generating the groups.

% 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\}$. 

Consider a spatial region $\bD$ partitioned 
in areas $v_1, ..., v_n$, 
with $v_i \cup v_j = \emptyset$ for $i\neq j$. 
Consider also the data vector $\by=\{y_1,y_2,...,y_n\}$, 
with $y_i$ the data measured at the area $v_i$.
We aim at define $k$ groups, 
$g_1, ..., g_k$ with $\bigcup_{i=0}^{k}g_i = \bD$ and 
$g_i = \bigcup_{j\in I_i}v_j$ and $I_i \in \{1,2,...,n\}$ 
is a set of indexes of the $i^{th}$ group.

% 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$. 

Consider an adjacency matrix $\bA$ of dimension 
$n \ times n$ related to the neighbourhood structure 
of the areas within $\bD$, e.g. each row of $\bA$ 
is binary 0/1 vector related to an area the 
with non null elements indicating the columns 
of the neighbouring areas. 
In other words $\bA$ defines a graph $\bG_D$ of 
the neighboring structure within region the $\bD$. 
The graph $\bG_D$ is defined by the set of nodes $\bV_D$ 
associated with the areas $v_1, v_2, ..., v_n$, and a set 
of edges $\bE_D$ specified by the adjacency structure. 
An edge $(i,j)$ exists if the node (area) $i$ is 
neighbour of the node (area) $j$. 

\subsection{Minimum sppaning tree}

% 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)$. 

The \textit{minimum spanning tree}-(MST), of the $n$ 
nodes is a connected graph $\Upsilon$ with 
$n$ nodes and $n-1$ edges.
With a connected graph $\Upsilon$ allows, starting from $v_i$, 
reaching any other $v_j$ by the $n-1$ edges of $\Upsilon$. 
Further, if an edge is removed $\Upsilon$ is divided 
in two unconnectd graphs which one being a MST. 
Form the set of observations $y_1, y_2, ..., y_n$ 
is is assigned for each possible edge $(i,j)$ between a 
pair of nodes an associated ``cost'' $d(i,j)=d_{ij}$ 
given by a measure of dissimilarity between nodes $v_i$ e $v_j$. 
The MST is the set of edges $e_1, e_2, ..., e_{n-1}$ 
which minimises an overall ``cost''  of the graph such as 
$\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$
% and the adjacency matrix $\bA$. 
% 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)$. 

The MST can be obtained by the Prim's algorithm \cite{prim:57} 
which operates as follows. 
Start with an empty set of nodes $\bV_{in}=\emptyset$ and 
an empty set of edges $\Upsilon=\emptyset$. 
Any $i^{th}$ node from the set  ${1, 2, \ldots, n}$ can be 
selected and included in  $\bV_{in}$.
Then iterate between the following steps until all nodes 
are included in  $\bV_{in}$:
\begin{enumerate}
\item compute the dissimilarity between nodes in $\bV_{in}$ 
and neighbours not included in  $\bV_{in}$;
\item identify the lowest dissimilarity pair $(v_i, v_j)$, 
$v_i\in \bV_{in}$ and  $v_j\notin \bV_{in}$ ;
\item add $v_j$ to $\bV_{in}$ and $(i,j)$ to $\Upsilon$.
\end{enumerate}
The set of edges in  $\Upsilon$ is the  MST and 
$\Upsilon$ is unique if and only if the 
dissimilarity measure is continuous and  $d_{ij}\neq d_{rs}$ 
for any pairs $(i,j)$ and $(r,s)$,  $(i,j)\neq (r,s)$.  (REF HERE???)

\subsection{The edge removal}

% O segundo passo do procedimento SKATER é a remoção 
% sucessiva de arestas de . 
% 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)$. 

The next step is the sequential removal from $\Upsilon$.
For each removed edge the current MST generate two groups
with individuals also connected by a MST. 
For choice of edge the simply removal of the costly 
(${rm max}(d_{ij})$) edge is not suitable since this 
is a local measure  of dissimilarity. 
\citeasnoun{assuncao:06} favors a choice which maximises the 
homogeineity within elements within the resulting groups.
%and heterogeineity between groups.
For intance, consider the nodes $v_1$, $v_2$, $v_3$ e $v_4$ 
and edges $\{(1,2),(2,3),(3,4)\}$, with associatd costs 
$d_{12}<d_{2,3}<d_{3,4}$. 
Suppose $v_2$ is very similar to $v_4$, 
and $v_3$ more similar to $v_2$. 
Assuming a measure of homogeneity within groups 
it is possible to find a smaller total between the groups 
given by the removal of lesser costly  edge $(1,2)$
than the total resulting of  the removal of $(3,4)$. 

% 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}


Define $H(g_i)$ the homogeneity within the group $g_i$,
$H_0$ the primary homogeneity for all nodes within a single group, 
and $H_k=\sum_{i=1}^k H(g_i)$ the total homogeneity for the $k$ 
groups at a particular partitioning step of the algorithm. 
Initially consider all the $n$ nodes within a unique group, 
the MST $\Upsilon$ and compute $H_0$. 
Defina o vetor $gv$ de tamanho $n$ para identificação 
de grupos a que cada nó pertence, 
inicialmente todos são iguais a 1.
Defina o vetor $ge$ de tamanho $n-1$ para identificação 
de grupos a que cada aresta da MST pertence, 
inicialmente todos são iguais a 1.
Defina um vetor $dw$ de tamanho $n-1$. 
Cada elemento deste vetor armazena a diferença de 
homogeneidade obtida se a aresta correspondente 
for removida. 
Essa diferença é entre a homogeneidade atual e 
a soma de homogeneidade dos grupos gerados pela 
remoção da aresta.

Inicialmente, preencha o vetor $dw$, removendo 
temporariamente cada aresta. 
Ordene a MST de acordo com $dw$ em ordem decrescente. 
Então corte definitivamente a primeira aresta da 
MST ordenada. 
Atualize $gv$, por exemplo, colocando 2 nas posição 
de $gv$ referente ao nó da primeira coordenada da 
aresta removida e nas posições referentes aos nós 
ainda ligados a este nó. 
Atualize $ge$, por exemplo, colocando 2 nas posições 
referentes 'as arestas que contém nós ainda conectados 
ao nó da primeira coordenada da aresta removida.
Recalcule $dw$ e ordene-o em ordem decrescente, 
colocando nesta mesma ordem as arestas existentes e $ge$. 

Prossiga na remoção de arestas até que um critério 
de parada seja atingido, com os seguintes passos: 
\begin{enumerate} 
\item corte a primeira aresta 
\item atualize o vetores $gv$ e $ge$ 
\item recalcule $dw$ nas posições correspondentes 
'a arestas que fazem parte dos novos dois grupos gerados 
\item ordene $dw$ em ordem decrescente e também $ge$ e 
o conjunto de arestas existentes nesta mesma ordem 
\item se o criterio de parada não foi atingido 
 volte ao passo 1.
\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. 
Neste caso, na atualização de $dw$, deve-se 
verificar que ao remover a aresta, os grupos 
gerados satisfazem a restrição. 
Se não satisfazem, fazer $dw$ igual a zero. 
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 
com $10$ nós. Se ao dividi-lo o resultado seja um grupo 
com $8$ nós e outro com $2$ nós. Neste caso, 
fazemos $dw$ correspondente ser igual a zero, 
embora a diferença de homogeneidade não necessariamente 
seja igual a zero.