Agrupamento

Clustering, também conhecido como análise de agrupamento, é uma técnica de análise de dados que particiona um conjunto de objetos em grupos, ou clusters, de modo que objetos dentro do mesmo cluster sejam mais semelhantes entre si do que a objetos em outros clusters, de acordo com uma medida específica de similaridade ou distância definida pelo analista. É uma tarefa principal da análise exploratória de dados e uma técnica comum para análise estatística de dados, usada em campos como reconhecimento de padrões, análise de imagens, recuperação de informações, bioinformática, compressão de dados, computação gráfica e aprendizado de máquina. Como um método de aprendizado não supervisionado, o clustering não depende de dados rotulados; em vez disso, ele descobre estruturas e agrupamentos inerentes nos dados sem conhecimento prévio dos rótulos das classes.

O termo "clustering" abrange uma família de algoritmos e tarefas, em vez de um único algoritmo específico. Diferentes algoritmos variam significativamente em sua compreensão do que constitui um cluster e como identificar clusters de forma eficiente. Noções populares de clusters incluem grupos com pequenas distâncias entre membros, áreas densas do espaço de dados, intervalos ou distribuições estatísticas particulares. Consequentemente, o clustering pode ser formulado como um problema de otimização multiobjetivo, e o algoritmo e os parâmetros apropriados (como a função de distância, o limiar de densidade ou o número esperado de clusters) dependem do conjunto de dados individual e do uso pretendido dos resultados. A análise de cluster não é uma tarefa automática, mas um processo iterativo de descoberta de conhecimento ou otimização interativa multiobjetivo, frequentemente exigindo tentativa e erro para ajustar o pré-processamento de dados e os parâmetros do modelo até que o resultado alcance as propriedades desejadas.

Além do termo clustering, existem vários termos semelhantes, incluindo classificação automática, taxonomia numérica, botriologia (do grego βότρυς 'uva'), análise tipológica e detecção de comunidades. As diferenças sutis geralmente residem no uso dos resultados: em mineração de dados, os grupos resultantes são o objeto de interesse, enquanto na classificação automática, o poder discriminativo resultante é o interesse.

História

A análise de cluster originou-se na antropologia com o trabalho de Driver e Kroeber em 1932. Foi introduzida na psicologia por Joseph Zubin em 1938 e Robert Tryon em 1939, e famosamente usada por Raymond Cattell a partir de 1943 para classificação da teoria de traços na psicologia da personalidade. Desde então, o clustering evoluiu para uma ferramenta fundamental em inúmeras disciplinas científicas, com centenas de algoritmos publicados desenvolvidos ao longo das décadas.

Modelos de Cluster

A noção de "cluster" não pode ser definida com precisão, o que é uma razão chave para a diversidade de algoritmos de clustering. Há um denominador comum: um grupo de objetos de dados. No entanto, diferentes pesquisadores empregam diferentes modelos de cluster, e cada modelo pode ser implementado por vários algoritmos. Compreender esses modelos de cluster é essencial para entender as diferenças entre algoritmos. Modelos típicos de cluster incluem:

• Modelos de conectividade: O clustering hierárquico constrói modelos com base na conectividade de distância, onde clusters são formados pela ligação de objetos com base na proximidade.
• Modelos de centróide: O algoritmo k-means representa cada cluster por um único vetor médio, ou centróide, e atribui objetos ao centróide mais próximo.
• Modelos de distribuição: Clusters são modelados usando distribuições estatísticas, como distribuições normais multivariadas usadas pelo algoritmo de maximização de expectativa (EM).
• Modelos de densidade: Algoritmos como DBSCAN, OPTICS e HDBSCAN definem clusters como regiões densas conectadas no espaço de dados, separadas por áreas esparsas.
• Modelos de subespaço: No biclustering (também conhecido como co-clustering ou clustering de dois modos), clusters são modelados com ambos os membros do cluster e atributos relevantes, permitindo que clusters existam em diferentes subespaços dos dados.
• Modelos de grupo: Alguns algoritmos não fornecem um modelo refinado para seus resultados e simplesmente fornecem a informação de agrupamento.
• Modelos baseados em grafos: Uma clique, um subconjunto de nós em um grafo onde cada dois nós estão conectados por uma aresta, pode ser considerada uma forma prototípica de cluster. Relaxações do requisito de conectividade completa, conhecidas como quase-cliques, são usadas em algoritmos como o algoritmo de clustering HCS.
• Modelos de grafos assinados: Em grafos assinados, cada caminho tem um sinal do produto dos sinais nas arestas. Sob suposições da teoria do equilíbrio, as arestas podem mudar de sinal, resultando em um grafo bifurcado. O "axioma de agrupabilidade" mais fraco (nenhum ciclo tem exatamente uma aresta negativa) produz resultados com mais de dois clusters ou subgrafos com apenas arestas positivas.
• Modelos neurais: A rede neural não supervisionada mais conhecida é o mapa auto-organizável, e esses modelos geralmente podem ser caracterizados como semelhantes a um ou mais dos modelos acima, incluindo modelos de subespaço quando redes neurais implementam formas de Análise de Componentes Principais ou Análise de Componentes Independentes.

Tipos de Clustering

Um "clustering" é essencialmente um conjunto de clusters, geralmente contendo todos os objetos no conjunto de dados. Também pode especificar a relação dos clusters entre si, como uma hierarquia de clusters embutidos uns nos outros. Os clusterings podem ser aproximadamente distinguidos como:

• Clustering rígido: Cada objeto pertence a um cluster ou não.
• Clustering suave (também clustering fuzzy): Cada objeto pertence a cada cluster em um certo grau, como uma probabilidade de pertencimento.

Distinções mais finas incluem:

• Clustering de partição estrita: Cada objeto pertence exatamente a um cluster.
• Clustering de partição estrita com outliers: Objetos também podem não pertencer a nenhum cluster, caso em que são considerados outliers.
• Clustering sobreposto (também clustering alternativo, clustering multivisão): Objetos podem pertencer a mais de um cluster, geralmente envolvendo clusters rígidos.
• Clustering hierárquico: Objetos que pertencem a um cluster filho também pertencem ao cluster pai, criando uma estrutura em forma de árvore.
• Clustering de subespaço: Embora seja um clustering sobreposto, dentro de um subespaço definido de forma única, espera-se que os clusters não se sobreponham.

Algoritmos

Os algoritmos de clustering podem ser categorizados com base em seu modelo de cluster. Existem possivelmente mais de 100 algoritmos de clustering publicados, e nem todos fornecem modelos para seus clusters, tornando a categorização difícil. Não há um algoritmo de clustering objetivamente "correto"; como observado, "clustering está nos olhos de quem vê." Na verdade, uma abordagem axiomática demonstra que é impossível para qualquer método de clustering atender simultaneamente a três propriedades fundamentais: invariância de escala (os resultados permanecem inalterados sob escalonamento proporcional das distâncias), riqueza (todas as partições possíveis dos dados podem ser alcançadas) e consistência entre distâncias e a estrutura de clustering. O algoritmo mais apropriado para um problema específico frequentemente precisa ser escolhido experimentalmente, a menos que haja uma razão matemática para preferir um modelo de cluster a outro.

Algoritmos proeminentes de clustering incluem:

• K-means: Um algoritmo baseado em centróide que particiona dados em k clusters minimizando a soma dos quadrados dentro do cluster. É simples e eficiente, mas requer especificar o número de clusters e é sensível a outliers.
• Clustering hierárquico: Constrói uma hierarquia de clusters de forma aglomerativa (de baixo para cima) ou divisiva (de cima para baixo). Não requer um número predefinido de clusters e produz um dendrograma.
• DBSCAN: Um algoritmo baseado em densidade que identifica clusters como regiões densas separadas por áreas esparsas. Pode encontrar clusters de formas arbitrárias e lidar com outliers, mas requer ajuste de parâmetros como épsilon e pontos mínimos.
• Maximização de Expectativa (EM): Um algoritmo baseado em distribuição que modela clusters como distribuições gaussianas e estima iterativamente parâmetros para maximizar a verossimilhança.
• OPTICS: Uma extensão do DBSCAN que produz uma ordenação de clusters, tornando-o mais robusto a densidades variáveis.
• Mapas auto-organizáveis (SOM): Um modelo de rede neural que mapeia dados de alta dimensão para uma grade de baixa dimensão, preservando relações topológicas.

Aplicações

O clustering é amplamente usado em muitos domínios. No reconhecimento de padrões, ajuda a identificar grupos em dados para tarefas de classificação. Na análise de imagens, é usado para segmentação de imagens e detecção de objetos. Na recuperação de informações, o clustering organiza documentos por tópico para busca e recomendação. Na bioinformática, agrupa genes ou proteínas com padrões de expressão semelhantes. Na compressão de dados, o clustering reduz o tamanho dos dados representando grupos com protótipos. Na computação gráfica, auxilia na quantização de cores e simplificação de malhas. Na inteligência artificial, o clustering é uma técnica central para aprendizado não supervisionado, permitindo que sistemas descubram padrões sem exemplos rotulados.

Desafios e Considerações

O clustering apresenta vários desafios. Determinar o número ideal de clusters é frequentemente difícil e pode exigir conhecimento de domínio ou heurísticas. A escolha da métrica de distância afeta significativamente os resultados; métricas comuns incluem Euclidiana, Manhattan e similaridade de cosseno. Dados de alta dimensão podem sofrer da maldição da dimensionalidade, onde as distâncias se tornam menos significativas. Os resultados do clustering são sensíveis à inicialização e às configurações de parâmetros, e não há solução universal. Além disso, a natureza iterativa do clustering significa que os resultados devem ser validados usando métricas de avaliação internas ou externas, como o índice de silhueta ou o índice de Rand, para garantir que atendam às propriedades desejadas.

Conceitos Relacionados

O clustering está intimamente relacionado a outras técnicas de aprendizado não supervisionado, como redução de dimensionalidade e detecção de anomalias. É frequentemente usado em conjunto com aumento de dados para gerar amostras sintéticas ou no pré-processamento para aprendizado supervisionado. No contexto do aprendizado profundo, o clustering pode ser integrado a arquiteturas de redes neurais para aprendizado de representação. Os princípios do clustering também sustentam a detecção de comunidades em análise de redes e a segmentação de mercado em análise de negócios.