# Clustering

O clustering ou análise de agrupamento de dados é o conjunto de técnicas de prospecção de dados (data mining) que visa a fazer agrupamentos automáticos de dados segundo o seu grau de semelhança. O critério de semelhança faz parte da definição do problema e, dependendo, do algoritmo. A cada conjunto de dados resultante do processo dá-se o nome de grupo, aglomerado ou agrupamento (cluster).
O procedimento de agrupamento (clustering) também pode ser aplicado a bases de texto utilizando algoritmos de prospeção de texto (text mining), onde o algoritmo procura agrupar textos que falem sobre o mesmo assunto e separar textos de conteúdo diferentes.
Normalmente o usuário do sistema deve escolher a priori o número de grupos a serem detectados. Alguns algoritmos mais sofisticados pedem apenas o número mínimo, outros tem a capacidade de subdividir um grupo em dois.
Os tipos de algoritmos de agrupamento de dados mais comuns são: os particionais e os hierárquicos.

## Função distância

Quando se tem um conjunto de objetos é natural olhar para eles tentando perceber o quão semelhantes ou diferentes eles são uns dos outros. Uma abordagem comum consiste em definir uma função de distância entre os objetos, com a interpretação de que objetos a uma distância menor são mais semelhantes uns aos outros. Assim, a distância assume um significado mais abstrato. Por exemplo, podemos definir a distância entre pessoas como a diferença do ano em que nasceram. O clustering, que traduz-se em agrupamento, surge quando tentamos classificar ou organizar objetos em grupos coerentes. Dada uma função de distância, o problema pretende dividi-los em grupos para que, intuitivamente, objetos dentro do mesmo grupo estejam "próximos", e em diferentes grupos, "distantes".

## Agrupamento de máximo espaçamento

Suponha que temos um conjunto $U$ de n objetos $p_{1},p_{2},...,p_{n}$. Para cada par, $p_{i}$e $p_{j}$, temos uma distância d numérica $(p_{i},p_{j})$. Exigimos apenas que $d(p_{i},p_{j})=0$ para todo $i$=j; que $d(p_{i},p_{j})>0$ para $i$ e $j$ distintos; e que as distâncias sejam simétricas, ou seja, que $d(p_{i},p_{j})=d(p_{j},p_{i})$. Suponha que queremos dividir os objetos de $U$ em k grupos, para um determinado parâmetro k. Denominamos por k-grupo de $U$ cada elemento duma qualquer partição de $U$ em k conjuntos não vazios $C_{1},C_{2},...,C_{k}$. Definimos ainda o espaçamento de um k-grupo, como sendo a distância mínima entre qualquer ponto pertencente a esse k-grupo e qualquer ponto situado num k-grupo diferente. Sendo o objetivo do agrupamento de dados a criação de grupos bem distintos entre si, e portanto com elevadas distâncias entre pontos pertencentes a grupos diferentes, um objetivo natural é buscar k-grupos com o máximo espaçamento possível. Entretanto, há muitos k-grupos diferentes num conjunto $U$. O problema agora se resume em encontrar de forma eficiente a partição de $U$ que nos conduza ao espaçamento máximo.

## Algoritmo de agrupamento

Para a argumentação do funcionamento do algoritmo, necessita-se do conceito de árvore de extensão mínima, também conhecida por minimum spanning tree.

### Árvore de extensão mínima

O problema da árvore de extensão mínima se resume, basicamente, em buscar a forma mais barata de conectar todos os nós de um grafo, uma vez que podemos usar apenas um subconjunto de suas arestas para conectá-los. Isto pode ser útil na construção de uma rede elétrica, na construção do núcleo de uma rede rodoviária ou ferroviária, no estabelecimento de um circuito, ou mesmo na realização de algumas formas de agrupamento.
Existem diversos algoritmos para encontrar uma árvore de extensão mínima. Aqui, vamos mostrar um algoritmo guloso, o algoritmo de Prim.

#### Algoritmo de Prim

Tomamos um nó no grafo como inicial e todas as arestas que o tem como extremidade como arestas viáveis. Adicionamos ao novo grafo a aresta viável de menor custo e, consequentemente, o nó recém descoberto de sua outra extremidade. Assim, o conjunto de arestas viáveis passa ser todas as arestas que tem como extremidade ao menos um dos nós já descobertos. Seguimos adicionando as arestas de menor custo desde que um dos nós de suas extremidades ainda não esteja descoberto. Não entraremos no mérito de demonstrar que o algoritmo de Prim de fato funciona e é eficiente, entretanto daremos a intuição. A cada passo do algoritmo, encontramos uma árvore de extensão mínima para um subgrafo contido no grafo original. Digamos que o algoritmo é executado a partir de um nó inicial v, construindo assim um novo grafo. Sendo (v,u) a aresta de menor custo que liga v a um de seus vizinhos, digamos u, adicionaremos ela ao novo grafo e, consequentemente, teremos uma árvore de extensão mínima para o subgrafo formado pelos nós u e v. Repetindo esse processo, teremos uma árvore de extensão mínima para um dado grafo ao termos adicionado todos os seus nós ao novo grafo.

### Descrição do algoritmo

Agora temos o conhecimento necessário para compreender o algoritmo de encontrar k grupos de máximo espaçamento de um determinado grafo conexo.
Ao deletarmos uma aresta de uma árvore, criamos dois componentes conexos que também são árvores, tal fato é usado fortemente neste algoritmo. Encontrar k grupos consiste em deletar arestas de um grafo até obtermos k componentes conexos. No problema que estamos tratando, desejamos, além de encontrar k componentes conexos, que estes componentes sejam o mais distantes possível entre si. Definiremos o espaçamento de um conjunto de grupos de um grafo como a menor distância entre dois nós que pertencem a componentes conexos distintos. Provaremos agora, que ao deletar as k-1 maiores arestas de uma árvore de extensão mínima de um grafo conexo U, obteremos k grupos e o espaçamento entre eles será máximo.

### A otimalidade do algoritmo

Tome $C$ o conjunto de grupos (ou clusters) $C_{1},C_{2},...,C_{k}$ que particiona um grafo conexo $U$. O espaçamento $d^{*}$ de $C$ é o comprimento da (k-1)-ésima aresta mais custosa da árvore de extensão mínima, que é a última aresta deletada pelo algoritmo de agrupamento. Para confirmarmos essa afirmação, precisamos provar que o espaçamento de qualquer outro conjunto de k grupos é, no máximo, d*. Seja $C'$ um outro conjunto de k grupos que também particiona o grafo $U$ em conjuntos não vazios $C_{1}',C_{2}',...,C_{k}'$ .Como $C$ e $C'$ são diferentes, existe, necessariamente, um grupo $C_{r}$ que não é subconjunto de nenhum $C_{s}'$ pertencente a $C'$. Logo, existem pontos $p_{i}$ e $p_{j}$ em $Cr$ que pertencem a grupos diferentes em $C'$ - digamos $p_{i}$pertencente a $C_{s}'$ e $p_{j}$ pertencente a $C_{t}'$ diferente de $C_{s}'$. Dado que $p_{i}$e $p_{j}$pertencem a um mesmo grupo, nenhuma das arestas do caminho $P$ entre eles foi deletado pelo algoritmo. Ou seja, cada aresta pertencente a $P$ tem comprimento menor ou igual a $d^{*}$. Por outro lado, sabemos que $p_{i}$pertence a $C_{s}'$, mas $p_{j}$ não; logo, tomemos $p'$ como o primeiro nó em $P$ que não pertence a $C_{s}'$ e $p$ o nó que vem logo antes de $p'$ no caminho $P$. Sabemos que $d(p,p')\leq d^{*}$ em $C'$ e isso completa a prova, pois o $d\leq d(p,p')$, sendo $d$ o espaçamento de $C'$.

### Implementação e análise da complexidade

Implementar este algoritmo consiste em descobrir uma maneira eficiente de encontrar a aresta menos custosa dentro de um subconjunto de arestas do grafo original - para construir a árvore de extensão mínima - e a mais custosa - para deletá-la na segunda etapa do algoritmo. Tais operações são facilmente realizadas com o uso de uma fila de prioridades que pode ser mantida com complexidade $O(logm)$, onde m é o número de elementos na fila. A complexidade de montar a árvore de extensão mínima é $O(nlogm)$, onde $n$ é o número de nós no grafo e $m$ o número de arestas. Já a complexidade de deletar k-1 arestas é $O((k-1)log(n-1))$. Logo, o tempo de execução é dominado pela construção da árvore de extensão mínima. Conclui-se, então, que encontrar k grupos em um grafo $U$ com $n$ nós e $m$arestas é uma tarefa que possuí tempo de execução $O(nlogm)$.