Absolute indices for determining compactness, separability and number of clusters

Este artigo apresenta novos índices absolutos de validação de clusters que definem funções de compactação e margens de separabilidade para determinar o número verdadeiro de clusters, demonstrando sua eficácia em comparação com índices relativos tradicionais em diversos conjuntos de dados sintéticos e reais.

O essencial

Imagine que você é um organizador de uma grande festa e precisa separar os convidados em grupos para conversar. O desafio é: quantos grupos você deve fazer?

Se você fizer apenas um grupo gigante, ninguém se sente à vontade. Se fizer 50 grupos minúsculos, as pessoas ficarão sozinhas. O objetivo é encontrar o "número mágico" onde os grupos são:

1. Compactos: As pessoas dentro do mesmo grupo se conhecem bem e estão todas juntas (como um círculo de amigos apertado).
2. Separáveis: Os grupos estão distantes uns dos outros, sem confusão entre quem pertence a qual grupo (como mesas de jantar bem espaçadas).

O problema é que, na vida real (e nos dados de computadores), as pessoas não se sentam em círculos perfeitos. Às vezes, há grupos misturados, pessoas soltas ou espaços vazios. A maioria das ferramentas atuais para contar esses grupos é como um "espelho relativo": ela só diz "o Grupo A parece melhor que o Grupo B", mas não diz se o Grupo A é realmente bom ou se é apenas o "menos pior" de uma festa bagunçada.

A Solução: Uma Nova Régua Absoluta

Os autores deste artigo criaram uma nova ferramenta, uma "régua absoluta", para medir a qualidade dos grupos de forma independente. Eles propuseram dois conceitos principais, que vamos explicar com analogias simples:

1. O Índice de Compactação (O "Grudinho")

Imagine que cada grupo é uma bola de gude.

• A função de compactação: Eles criaram uma maneira de medir o quanto as pessoas (pontos de dados) estão "grudadas" no centro da bola.
• O truque: Eles olham para os espaços vazios dentro da bola. Se há muitos buracos ou espaços vazios entre as pessoas, o grupo é considerado "solto" e pouco compacto. Se as pessoas estão distribuídas uniformemente e sem buracos grandes, o grupo é "compacto".
• A analogia: É como medir a densidade de uma nuvem. Uma nuvem de chuva forte (compacta) tem gotas bem juntas. Uma nuvem de fumaça (pouco compacta) tem espaços vazios grandes.

2. O Índice de Separabilidade (O "Distanciamento")

Agora, imagine que você tem várias dessas bolas de gude espalhadas no chão.

• Conjunto Adjacente: Eles identificam quem são os "vizinhos" de cada grupo. São as pessoas que estão mais próximas da borda de um grupo e da borda do grupo vizinho.
• A Margem: Eles medem o "espaço de segurança" entre os grupos. Se as bordas dos grupos se tocam ou se misturam, a margem é zero (ou negativa). Se há um corredor claro entre eles, a margem é grande.
• A analogia: É como medir a distância entre duas ilhas. Se a maré sobe e as ilhas se conectam, elas não são separáveis. Se há um oceano profundo entre elas, elas são bem separadas.

O Grande Desafio: O Equilíbrio Perfeito

Aqui está o dilema:

• Se você fizer muitos grupos (ex: 100), cada grupo fica pequeno e super compacto (todos estão grudados), mas eles ficam tão perto uns dos outros que se misturam (baixa separabilidade).
• Se você fizer poucos grupos (ex: 2), eles ficam muito separados (fáceis de distinguir), mas dentro de cada grupo as pessoas estão espalhadas demais (baixa compactação).

Os autores propõem um mapa de decisão (um gráfico de duas dimensões):

• No eixo horizontal, você tem a Compactação.
• No eixo vertical, você tem a Separabilidade.

Cada tentativa de dividir os dados (2 grupos, 3 grupos, 4 grupos...) vira um ponto nesse gráfico.

• O "ponto ideal" é aquele que está no canto superior direito: o mais alto possível (muito separado) e o mais à direita possível (muito compacto).
• Eles usam uma lógica matemática para encontrar o ponto que não é "dominado" por nenhum outro (ou seja, não existe outro ponto que seja melhor nos dois aspectos ao mesmo tempo).

O Resultado na Prática

Os autores testaram essa nova "régua" em:

1. Dados Sintéticos: Desenhos de grupos perfeitos criados por computador. A nova régua acertou o número de grupos quase sempre, enquanto as regras antigas às vezes erravam.
2. Dados Reais: Dados do mundo real, como registros de doenças no fígado, sinais de rádio ou localização de pessoas em um shopping. Como ninguém sabe a resposta "certa" nesses casos, eles compararam com outras ferramentas famosas. A nova régua concordou com a maioria das outras, mas conseguiu identificar estruturas que as outras ferramentas ignoravam.

Resumo em uma frase

Este artigo apresenta uma nova maneira de contar grupos em dados que funciona como uma régua absoluta: ela mede o quão "apertados" os grupos estão internamente e o quão "distanciados" eles estão externamente, ajudando a encontrar o número perfeito de grupos sem depender de comparações relativas.

Em suma: É como ter um juiz que não compara o time A com o time B, mas olha para cada time individualmente e diz: "Este time está bem formado e separado dos outros. Este é o número certo de times."

Resumo técnico

Aqui está um resumo técnico detalhado do artigo "Absolute indices for determining compactness, separability and number of clusters", apresentado em português:

Título: Índices Absolutos para Determinar Compactação, Separabilidade e Número de Clusters

Autores: Adil M. Bagirov, Ramiz M. Aliguliyev, Nargiz Sultanova e Sona Taheri.

---

1. Problema e Motivação

A identificação do número "verdadeiro" ou ótimo de clusters em um conjunto de dados é um desafio fundamental na mineração de dados e no aprendizado de máquina não supervisionado.

• Limitação dos Métodos Atuais: A maioria dos índices de validade de clusters existentes são relativos. Eles são projetados principalmente para comparar diferentes algoritmos de clustering ou ajustar parâmetros, e seu desempenho depende fortemente da estrutura subjacente dos dados. Em estruturas complexas, diferentes índices frequentemente fornecem recomendações conflitantes.
• Necessidade: Existe uma necessidade crítica de índices de validade absolutos que possam avaliar a qualidade de uma única solução de clustering (compactação e separabilidade) de forma independente, permitindo determinar o número ótimo de clusters sem depender de comparações externas.

2. Metodologia Proposta

Os autores propõem uma abordagem nova baseada em duas funções principais: uma função de compactação e um índice de separabilidade, que são combinados para resolver o problema de determinar o número de clusters.

A. Função e Índice de Compactação

• Definição: Para um conjunto de dados $A$ com centro $x$, define-se uma função de compactação $f(t)$ que mede a média das distâncias dos pontos dentro de uma esfera de raio $t$ em relação ao centro.
• Detecção de Vazios: A função é uma função degrau não decrescente. Intervalos constantes na função indicam regiões vazias (espaços sem pontos de dados) entre camadas concêntricas.
• Cálculo do Índice ($c_A(\epsilon)$):
  • O espaço é dividido em intervalos baseados em uma tolerância $\epsilon$.
  • Identificam-se conjuntos de pontos densos e regiões vazias.
  • Utiliza-se um conjunto de direções de "spanning positivo" para verificar a uniformidade da distribuição dos pontos dentro dos conjuntos densos.
  • O índice penaliza a presença de grandes regiões vazias e a não uniformidade da distribuição, resultando em um valor entre 0 e 1 (onde 1 indica máxima compactação/uniformidade).

B. Adjacência e Índice de Separabilidade

• Conjuntos Adjacentes: Para dois clusters $A_1$ e $A_2$ com centros $x_1$ e $x_2$, define-se o conjunto adjacente como os pontos de $A_1$ que estão mais próximos de $x_2$ do que a distância entre os centros, e vice-versa.
• Margem (Margin): Calcula-se a margem entre os clusters subtraindo os raios máximos dos pontos adjacentes à distância entre os centros.
• Índice de Separabilidade ($\beta_{ij}$): É uma versão escalonada da margem, normalizada para o intervalo [0, 1]. Valores > 0.5 indicam que os clusters são separáveis.
• Índice Global ($s_k$): Calcula-se a separabilidade média ponderada de todos os pares de clusters na partição.

C. Determinação do Número de Clusters

O problema é formulado como um problema de otimização multiobjetivo:

1. Maximizar a Compactação ($C_k$).
2. Maximizar a Separabilidade ($s_k$).

• Plano de Decisão (Decision-Space Plot): Cada solução de clustering (para um número $k$ de clusters) é plotada como um ponto em um gráfico 2D, onde o eixo X é a separabilidade e o eixo Y é a compactação.
• Seleção da Solução: Identificam-se os pontos não dominados (soluções de Pareto). O número ótimo de clusters é escolhido como a solução não dominada com o maior índice de separabilidade, pois isso garante a estrutura de clusters mais distinta.
• Escalarização: Para facilitar a escolha, propõe-se um índice combinado $T_k(\epsilon) = (1 - C_k(\epsilon)) / s_k$, onde o valor mínimo indica a melhor solução.

3. Contribuições Chave

1. Índices Absolutos: Introdução de métricas que não dependem da comparação entre algoritmos, mas avaliam a qualidade intrínseca da estrutura de dados.
2. Função de Compactação Baseada em Geometria: Uma nova definição que detecta regiões esparsas e uniformidade de distribuição usando funções degrau e direções vetoriais.
3. Definição de Margem via Conjuntos Adjacentes: Uma abordagem geométrica rigorosa para medir a separação entre pares de clusters, superando limitações de métricas baseadas apenas em distâncias entre centróides.
4. Abordagem Multiobjetivo: A visualização e seleção de clusters através de um plano de decisão (compactação vs. separabilidade) oferece uma interpretação intuitiva e robusta para a escolha do número $k$.

4. Resultados Experimentais

Os autores avaliaram os índices em diversos conjuntos de dados sintéticos e do mundo real, comparando com índices clássicos (Silhouette, Davies-Bouldin, Calinski-Harabasz, Dunn, Xie-Beni) e índices absolutos anteriores (G-índices).

• Dados Sintéticos:
  • Em datasets com clusters circulares compactos (A1, A2, A3) e clusters desbalanceados (Unbalance), o índice proposto identificou consistentemente o número verdadeiro de clusters.
  • Em datasets com clusters misturados (DA3), onde outros índices falharam ao fundir clusters, o índice proposto (especialmente através da análise do plano de decisão) conseguiu distinguir a estrutura correta, priorizando a separabilidade.
• Dados Reais:
  • Testes em datasets como Liver Disorders, Ionosphere, Land Satellite e Shuttle Control mostraram forte concordância com a maioria dos outros índices de validade.
  • Para o dataset Localization Data for Person Activity (com 11 classes conhecidas), o índice proposto identificou corretamente 11 clusters, alinhando-se com a verdade fundamental.
• Visualização: Os "Decision-Space Plots" demonstraram ser ferramentas eficazes para visualizar o trade-off entre compactação e separabilidade, permitindo a identificação de soluções plausíveis além da ótima.

5. Significado e Conclusão

O trabalho oferece uma contribuição significativa para a teoria de clustering ao fornecer ferramentas absolutas e escaláveis para validar a qualidade de agrupamentos.

• Invariância: Os índices são invariantes à ordem dos dados e atributos.
• Robustez: A combinação de compactação e separabilidade em um framework multiobjetivo resolve o dilema comum de escolher entre muitos clusters compactos (mas sobrepostos) ou poucos clusters bem separados (mas esparsos).
• Aplicabilidade: A metodologia é aplicável a dados sintéticos e reais, oferecendo uma alternativa superior aos métodos relativos tradicionais, especialmente em cenários onde o número de clusters é desconhecido e a estrutura dos dados é complexa.

Em resumo, o artigo estabelece um novo padrão para a avaliação de clusters, permitindo que pesquisadores e praticantes determinem o número ótimo de clusters com base em propriedades geométricas intrínsecas dos dados, em vez de apenas comparações relativas.