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