\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.
 O 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$. Define a group identifier vector $G$ of size $n$ and start partitining as follows
until a stoping criteria have been reached or a group is defined for each individual:
\begin{enumerate}
\item compute the total homogeneity $H_k$ for the currently existing groups
\item For all the possible groups resulting of a next partition 
  \begin{itemize}
  \item for each group node (EDGE???)
    \begin{itemize}
    \item compute the diference between the homogeneity of the group and sum of the homogeneities of the
      two groups results resulting from the edge removal (?? TEM ALGO ESTRANHO AQUI)
    \end{itemize}
  \end{itemize}
\item Identify the node (EDGE????) resulting on the greater difference computed above and remove the node
  (EDGE???) spliting the group in two; 
\item Update the set of nodes (EDGES???) and $G$. 
\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.

The algorithme can be modified and/or enhanced by
imposing additional restrictions  as, for instence, 
limmiting the minimum number of individuals within each group.
This requires the restriction to be checked at each cycle 
and the unwanted edge removals removed from the proposal set.



