Depth-Based Local Center Clustering: A Framework for Handling Different Clustering Scenarios

Resumo Técnico: Agrupamento de Centros Locais Baseado em Profundidade (DLCC)

Declaração do Problema
A análise de agrupamento (clustering) é fundamental para a ciência de dados, mas os métodos existentes frequentemente lutam contra a diversidade das distribuições de dados do mundo real. As abordagens tradicionais geralmente se dividem em duas categorias, cada uma com limitações específicas:

• Métodos baseados em centros (ex: k-means) assumem um único ponto representativo por agrupamento e formas esféricas, tornando-se sensíveis a outliers e à inicialização, além de falharem ao modelar geometrias não convexas.
• Métodos baseados em densidade (ex: DBSCAN, Mean Shift) lidam com formas arbitrárias, mas dependem de estimativas de densidade ou limiares fixos, o que pode ser instável em espaços de alta dimensionalidade ou quando os agrupamentos possuem densidades variáveis.
• Métodos baseados em grafos frequentemente enfrentam proibições computacionais em dados de larga escala ou permanecem sensíveis às escolhas de métricas de distância.

Uma limitação central entre esses paradigmas é a definição de "exemplares" (pontos representativos). A maioria dos métodos vincula os exemplares a critérios de distância ou densidade que podem não se generalizar através de diferentes dimensionalidades e geometrias. Além disso, embora a profundidade estatística de dados ofereça uma ordenação robusta de centro para fora de dados multivariados, ela tem sido historicamente utilizada apenas como uma ferramenta auxiliar (ex: para inicialização), em vez de como o mecanismo primário para identificar a estrutura local e a multimodalidade. Funções de profundidade padrão também falham em capturar características multimodais diretamente.

Metodologia: O Framework DLCC
O artigo propõe o Agrupamento de Centros Locais Baseado em Profundidade (DLCC), um framework que utiliza a profundidade de dados estatística para definir centros locais e construir medidas de similaridade sem depender de métricas de distância globais ou estimativas de densidade.

1. Matriz de Similaridade Baseada em Profundidade:
   Em vez de usar a distância Euclidiana, o DLCC constrói uma matriz de similaridade $S$ baseada na Profundidade Espacial (SD). Para localizar o conceito de profundidade, o método define um conjunto de dados refletido $X_{Ri}$ para cada observação $x_i$, consistindo no conjunto original $X$ e na reflexão de todos os pontos através de $x_i$. Como $x_i$ é o centro de simetria para $X_{Ri}$, sua profundidade é máxima (1). A profundidade de qualquer outro ponto $x_j$ em relação a $X_{Ri}$, denotada por $D(x_j | X_{Ri})$, serve como uma medida de similaridade entre $x_j$ e $x_i$.

• Eficiência: Os autores introduzem uma implementação baseada em matrizes para calcular essas profundidades de forma eficiente, reduzindo cálculos redundantes através da pré-computação de somas de vetores unitários e normas, embora a complexidade teórica permaneça $O(n^3)$.

2. Identificação de Centros Locais:
   Para cada ponto $x_i$, um vizinhança $N_i$ de tamanho $s$ é definida por seus $s-1$ vizinhos mais próximos baseados na similaridade de profundidade. Dentro de cada vizinhança, o ponto com o maior ranking local (ponto mais profundo) é identificado como um centro local.

• Filtragem: Nem todos os centros locais são úteis. O método filtra candidatos com base em dois critérios: (1) o centro deve ser central dentro de sua vizinhança (rank $\le 2$) e (2) ele deve aparecer frequentemente em diferentes vizinhanças (frequência $f > 1$). Um critério de estabilidade, a Profundidade Média Induzida pelo Vizinho (AND), é usado para selecionar centros robustos adicionais.

3. Estratégias de Agrupamento:
   Os centros locais filtrados são agrupados em clusters usando duas estratégias distintas para lidar com diferentes geometrias de dados:

• Estratégia Min (Min Strategy): Agrupa centros de forma conservadora com base na sobreposição mútua de vizinhanças. É adequada para clusters convexos equilibrados, bem separados ou sobrepostos.
• Estratégia Max (Max Strategy): Agrupa centros via cadeias de conectividade onde a similaridade de vizinhança excede um limiar $\delta$. Esta estratégia é projetada para estruturas não convexas e tamanhos de clusters altamente desbalanceados. Inclui um mecanismo para segregar regiões "onipresentemente não convexas" (ex: espirais) através da identificação de centros locais isolados.

4. Formação de Clusters e Classificação:
   Uma vez que os grupos de centros locais são formados, clusters temporários são criados usando os vizinhos únicos de cada grupo. Os pontos são atribuídos pontuações baseadas em sua similaridade aos centros do grupo versus outros grupos. Pontos ambíguos ou não atribuídos são então classificados usando classificadores integrados (k-Vizinhos Mais Próximos ou Florestas Aleatórias) treinados nos rótulos dos clusters temporários, garantindo uma atribuição robusta sem necessidade de ajuste adicional de hiperparâmetros.

Principais Contribuições

• Framework Inovador: O DLCC é o primeiro método a colocar a profundidade de dados no núcleo tanto da identificação de exemplares quanto da construção de similaridade, abordando diretamente a multimodalidade.
• Computação Eficiente: O artigo desenvolve uma implementação baseada em matrizes para construir matrizes de similaridade de profundidade sob profundidade espacial, acelerando significativamente o cálculo em comparação com implementações ingênuas.
• Agrupamento Flexível: A abordagem de dupla estratégia (Min/Max) permite que o framework se adapte a diferentes formas de clusters (convexos vs. não convexos) e distribuições de densidade.
• Avaliação Abrangente: Os autores fornecem um procedimento completo de ponta a ponta, incluindo diretrizes de seleção de parâmetros (usando o índice CVDD e visualização) e extensas avaliações empíricas.

Resultos Experimentais
Os autores avaliaram o DLCC em 12 conjuntos de dados sintéticos e 13 benchmarks do mundo real (incluindo dados de imagens de alta dimensão e microarrays).

• Desempenho: O DLCC alcançou recuperação perfeita em 7 conjuntos de dados sintéticos e classificou-se consistentemente entre os três primeiros em todos os benchmarks do mundo real. Demonstrou desempenho superior ao lidar com formas não convexas, densidades variáveis e desbalanceamento de classes em comparação com competidores como LW-k-means, EKM, R-MDPC e ACLR.
• Limitações Observadas: O método teve dificuldades com estruturas do tipo "manifold" (variedade) onde as vizinhanças locais são inerentemente não convexas (ex: o conjunto de dados "Atom" e estruturas de espiral em "Blend"). Nesses casos, a suposição de que os centros locais residem em vizinhanças aproximadamente convexas falhou.
• Escalabilidade: Embora seja eficaz para conjuntos de dados de até $\sim 10^4$ observações, a complexidade $O(n^3)$ da construção da matriz de similaridade permanece um gargalo para dados de escala muito grande.

Significância e Alegações
O artigo afirma que o DLCC oferece uma alternativa flexível aos métodos de agrupamento tradicionais ao superar as suposições rígidas de métodos baseados em centros e a instabilidade de métodos baseados em densidade em altas dimensões. Ao utilizar a profundidade de dados para definir a geometria local, o DLCC amplia as capacidades de análise de dados em uma ampla gama de cenários sem exigir um número predefinido de clusters ou suposições distributivas estritas. Os autores posicionam o DLCC como uma ferramenta robusta para análise exploratória de dados, particularmente onde as formas dos clusters são complexas ou desconhecidas, ao mesmo tempo em que reconhecem que trabalhos futuros são necessários para melhorar a escalabilidade e automatizar a seleção de parâmetros.