Clustering
Clustering, ou análise de agrupamento de dados, é um conjunto de técnicas de prospecção de dados que visa agrupar automaticamente dados com base em seu grau de semelhança. O critério de semelhança é definido no problema e pelo algoritmo. Cada conjunto de dados resultante é chamado de grupo, aglomerado ou cluster.
Pontos-chave
- Clustering agrupa dados automaticamente por semelhança.
- A função de distância mede a similaridade entre objetos.
- O agrupamento de máximo espaçamento busca grupos bem distintos.
- Algoritmos de clustering utilizam conceitos como a árvore de extensão mínima.
- A eficiência do algoritmo é dominada pela construção da árvore de extensão mínima.
Ao analisar um conjunto de objetos, é fundamental entender o quão semelhantes ou diferentes eles são. Uma abordagem comum é definir uma função de distância entre eles: quanto menor a distância, maior a semelhança. Essa distância pode ser abstrata, como a diferença de anos de nascimento entre pessoas. O clustering, que significa agrupamento, surge ao tentar organizar esses objetos em grupos coerentes. Dada uma função de distância, o objetivo é dividir os objetos em grupos onde os elementos de um mesmo grupo estejam 'próximos' e os de grupos diferentes estejam 'distantes'.
Considere um conjunto U de 'n' objetos (p1, p2, ..., pn). Para cada par de objetos (pi, pj), existe uma distância numérica d(pi, pj). Essa distância é zero se os objetos são idênticos (i=j), positiva se são distintos, e simétrica (d(pi, pj) = d(pj, pi)). Se quisermos dividir U em 'k' grupos (C1, C2, ..., Ck), chamamos cada elemento dessa partição de 'k-grupo'. O espaçamento de um 'k-grupo' é a distância mínima entre qualquer ponto de um grupo e qualquer ponto de um grupo diferente. Para criar grupos bem distintos, o objetivo é encontrar 'k-grupos' com o máximo espaçamento possível. O desafio é encontrar eficientemente a partição de U que maximize esse espaçamento.
Para entender o funcionamento do algoritmo de agrupamento de máximo espaçamento, é essencial compreender o conceito de árvore de extensão mínima (Minimum Spanning Tree).
O que é uma Árvore de Extensão Mínima?
O problema da árvore de extensão mínima (AEM) consiste em encontrar a maneira mais 'barata' de conectar todos os nós de um grafo, utilizando apenas um subconjunto de suas arestas. Isso é útil em diversas aplicações, como na construção de redes elétricas, rodoviárias, ferroviárias ou circuitos, e também em certas formas de agrupamento. Existem vários algoritmos para encontrar uma AEM. Um deles é o algoritmo de Prim, que é um algoritmo guloso. Ele começa com um nó inicial e considera todas as arestas conectadas a ele como 'viáveis'. Em cada passo, a aresta viável de menor custo é adicionada ao novo grafo, juntamente com o nó recém-descoberto em sua outra extremidade. O conjunto de arestas viáveis é então atualizado para incluir todas as arestas conectadas aos nós já descobertos. O processo continua adicionando arestas de menor custo, desde que um dos nós de suas extremidades ainda não tenha sido descoberto. A intuição é que, a cada passo, o algoritmo constrói uma AEM para um subgrafo, expandindo-a até incluir todos os nós do grafo original.
Descrição do Algoritmo de Agrupamento
Com o conhecimento sobre árvores de extensão mínima, podemos entender o algoritmo para encontrar 'k' grupos de máximo espaçamento em um grafo conexo. Uma propriedade importante é que, ao remover uma aresta de uma árvore, ela se divide em dois componentes conexos, que também são árvores. O algoritmo de agrupamento utiliza essa propriedade: para encontrar 'k' grupos, removem-se arestas do grafo até que 'k' componentes conexos sejam formados. No contexto do problema de máximo espaçamento, queremos que esses 'k' componentes sejam o mais distantes possível entre si. O espaçamento de um conjunto de grupos é definido como a menor distância entre dois nós que pertencem a componentes conexos distintos. A prova demonstra que, ao deletar as 'k-1' maiores arestas de uma árvore de extensão mínima de um grafo conexo U, obtêm-se 'k' grupos com o espaçamento máximo entre eles.
A Otimização do Algoritmo
Considere C como o conjunto de 'k' grupos (C1, C2, ..., Ck) 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 removida pelo algoritmo de agrupamento. Para provar a otimalidade, precisamos demonstrar que o espaçamento de qualquer outro conjunto de 'k' grupos (C') é, no máximo, d*. Se C e C' são diferentes, deve existir um grupo Cr em C que não é um subconjunto de nenhum grupo Cs' em C'. Isso implica que existem pontos pi e pj em Cr que pertencem a grupos diferentes em C' (digamos, pi em Cs' e pj em Ct', onde Ct' é diferente de Cs'). Como pi e pj estão no mesmo grupo em C, nenhuma das arestas no caminho P entre eles foi removida pelo algoritmo, ou seja, cada aresta em P tem comprimento menor ou igual a d*. Além disso, como pi pertence a Cs' mas pj não, deve haver um primeiro nó p' no caminho P que não pertence a Cs', e um nó p que o precede em P. A distância d(p, p') é menor ou igual a d*. Consequentemente, o espaçamento de C' (d) é menor ou igual a d(p, p'), o que prova que d é menor ou igual a d*.
Implementação e Análise de Complexidade
A implementação deste algoritmo envolve encontrar eficientemente a aresta de menor custo para construir a árvore de extensão mínima e a aresta de maior custo para removê-la. Essas operações podem ser realizadas eficientemente usando uma fila de prioridades, que mantém uma complexidade de O(logm), onde 'm' é o número de elementos na fila. A complexidade para montar a árvore de extensão mínima é O(n logm), onde 'n' é o número de nós no grafo e 'm' é o número de arestas. A complexidade para remover 'k-1' arestas é O((k-1)log(n-1)). Portanto, o tempo de execução total do algoritmo é dominado pela construção da árvore de extensão mínima. Conclui-se que encontrar 'k' grupos em um grafo U com 'n' nós e 'm' arestas tem um tempo de execução de O(n logm).
