🤖 machine learning

Topology-Driven Clustering: Enhancing Performance with Betti Number Filtration

Este artigo apresenta o BFTC, um novo algoritmo de agrupamento topológico que utiliza sequências de Betti multiescala derivadas de filtrações de Vietoris-Rips locais para construir estruturas de similaridade conscientes da topologia, agrupando assim de forma eficaz estruturas de dados complexas, não convexas e entrelaçadas, ao mesmo tempo em que supera os métodos de estado da arte existentes.

Autores originais: Arghya Pratihar, Kushal Bose, Swagatam Das

Publicado 2026-07-22

📖 6 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Arghya Pratihar, Kushal Bose, Swagatam Das

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

A Forma das Coisas por Vir

Imagine que você esteja tentando organizar uma pilha gigante de brinquedos misturados. Alguns são blocos vermelhos, outros são bolas azuis e outros são cobras verdes. Se você apenas observar o quão próximos eles estão uns dos outros no chão, pode acabar agrupando os blocos vermelhos com as bolas azuis simplesmente porque eles caíram um ao lado do outro. É assim que muitos programas de computador tradicionais tentam classificar dados: eles medem a distância em linha reta entre os pontos. Mas e se as "cobras" forem, na verdade, laços longos e sinuosos que se enrolam ao redor das "bolas"? A distância sozinha não consegue dizer que a cobra é uma forma única e conectada; ela vê apenas um monte de pontos espalhados.

Para resolver isso, cientistas utilizam um campo chamado Análise de Dados Topológicos (TDA). Pense na TDA como uma forma de olhar para os dados não apenas como uma dispersão de pontos, mas como uma paisagem com colinas, vales e túneis. Uma ferramenta fundamental neste campo é a "homologia persistente", que atua como uma câmera que tira fotos dos dados em diferentes níveis de zoom. À medida que você afasta o zoom, pode ver quais características (como um buraco em uma rosquinha ou um laço em uma cobra) permanecem visíveis e quais são apenas ruído aleatório. Outro conceito chave é o "número de Betti", que é simplesmente uma contagem dessas características: quantos ilhas separadas existem? Quantos túneis? Quantas bolhas ocas? Ao contar essas formas, os computadores podem entender a verdadeira estrutura dos dados, mesmo quando eles estão torcidos, emaranhados ou não convexos (ou seja, quando não parecem uma simples bola ou caixa).

A Grande Ideia do Artigo: BFTC

Neste artigo, os autores apresentam um novo método chamado Agrupamento Topológico baseado em Filtração de Números de Betti, ou BFTC para abreviar. Eles argumentam que, embora métodos anteriores tenham tentado usar essas ideias topológicas, muitas vezes erraram o alvo ao olhar para todo o conjunto de dados de uma vez ou ao contar apenas as características mais simples (como apenas contar ilhas). O BFTC sugere uma abordagem mais inteligente: olhar para os dados localmente, como um detetive examinando um bairro específico, e contar as formas complexas em cada escala.

Aqui está como a mágica acontece, passo a passo:

A Vigilância do Bairro: Primeiro, o algoritmo escolhe um ponto e observa seus vizinhos imediatos (sejam os $k$ amigos mais próximos ou todos dentro de um determinado raio).
A Lente de Zoom (Filtração): Em vez de apenas olhar para esse bairro uma única vez, o BFTC cria uma "filtração". Imagine inflar lentamente um balão ao redor do seu bairro. À medida que o balão cresce, ele conecta pontos que estavam distantes. Em cada estágio desta inflação, o algoritmo constrói uma forma temporária (chamada de complexo de Vietoris–Rips) e conta os buracos e laços.
A Impressão Digital Topológica: Conforme o balão infla de pequeno para grande, o número de buracos muda. Um balão pequeno pode ver 10 ilhas separadas. Um balão médio pode vê-las se fundirem em 2 ilhas com 1 túnel. Um balão grande pode ver tudo se tornar 1 ilha gigante. Essa sequência de números é chamada de sequência de Betti. É como uma impressão digital única para aquele bairro específico, descrevendo como sua forma evolui.
Correspondência de Impressões Digitais: O algoritmo então compara as sequências de Betti de pontos vizinhos. Se dois pontos têm sequências semelhantes (significando que seus bairros evoluem da mesma forma conforme você afasta o zoom), eles são considerados "topologicamente similares", mesmo que não estejam fisicamente mais próximos.
Limpeza: O algoritmo usa essas similaridades para limpar o mapa. Ele remove "outliers" (valores atípicos) ou vizinhos que não se encaixam no padrão topológico, criando um mapa mais limpo e preciso da verdadeira estrutura dos dados.
A Classificação Final: Finalmente, ele utiliza uma técnica matemática padrão (agrupamento espectral) neste novo mapa consciente da topologia para agrupar os dados em clusters.

O Que Eles Descobriram

Os autores testaram o BFTC em uma variedade de conjuntos de dados complicados, incluindo sintéticos projetados para enganar outros algoritmos. Estes incluíam:

Tori Interligados: Dois tori (rosquinhas) que estão interligados como uma corrente.
Formas Torcidas: Dados que formam espirais, círculos e esferas misturadas.
Dados do Mundo Real: Conjuntos de dados como o "Zoo" (classificação de animais), "Ecoli" (bactéria) e "MNIST" (dígitos escritos à mão).

Os resultados foram bastante promissores. Nas simulações, o BFTC superou consistentemente outros métodos de ponta, incluindo abordagens topológicas mais antigas como ToMATo, TPCC e TKM. Por exemplo, no conjunto de dados "Linked Tori" (onde duas rosquinhas estão emaranhadas), o BFTC alcançou pontuações quase perfeitas (ARI de 1.00 e NMI de 1.00), enquanto outros métodos tiveram dificuldade em separar as duas formas interligadas. Mesmo quando os pesquisadores adicionaram ruído (estática aleatória) aos dados, o BFTC permaneceu robusto, sugerindo que pode lidar bem com informações bagunçadas do mundo real.

O artigo também explorou como diferentes configurações afetam os resultados. Eles descobriram que o uso de similaridade de cosseno (comparando a direção das sequências de Betti em vez de apenas o seu tamanho) funcionou melhor do que as medidas de distância padrão. Eles também descobriram que o tamanho do "bairro" importa: se o bairro for muito pequeno, ele perde a visão geral; se for muito grande, ele conecta formas não relacionadas. No entanto, ao ajustar essas configurações, o BFTC identificou com sucesso estruturas complexas que outros algoritmos perderam.

O Que Eles Não Fazem (Ainda)

É importante notar o que o artigo não afirma. Os autores não dizem que este método é uma solução mágica para todos os problemas. Eles apontam explicitamente que seu método depende do cálculo de números de Betti, o que pode se tornar computacionalmente caro se você tentar contar buracos de altíssima dimensão (como buracos 4D ou 5D) em conjuntos de dados massivos. Eles sugerem que, para dimensões muito altas, é melhor manter as dimensões baixas (como 0, 1 ou 2), onde a matemática é gerenciável.

Além disso, embora o artigo prove matematicamente que o algoritmo é estável (significando que pequenas mudanças nos dados não fazem os resultados desmoronarem), estas são provas teóricas baseadas em suposições. As "vitórias" reais mostradas no artigo baseiam-se em simulações e experimentos em conjuntos de dados específicos, não em uma garantia universal para todos os dados possíveis no universo. Os autores sugerem que trabalhos futuros poderiam focar em tornar o método mais rápido para conjuntos de dados de escala gigantesca e explorar como escolher automaticamente as melhores configurações sem ajuda humana.

Em resumo, o BFTC sugere que, ao ouvir a "forma" dos dados através de seus buracos e laços em evolução, podemos classificar informações complexas e emaranhadas muito melhor do que apenas medindo o quão perto os pontos estão uns dos outros.

Resumo Técnico: Agrupamento Topológico Baseado em Filtragem de Números de Betti (BFTC)

1. Definição do Problema

Algoritmos de agrupamento tradicionais (ex: k-Means, DBSCAN, Spectral Clustering) dependem fortemente de medidas de similaridade euclidianas ou baseadas em kernels. Embora eficazes para muitas aplicações, esses métodos frequentemente enfrentam dificuldades com conjuntos de dados que exibem estruturas geométricas complexas, como formas não convexas, múltiplas escalas ou variedades (manifolds) entrelaçadas. Eles frequentemente falham em capturar características topológicas intrínsecas, como loops, vazios e conectividade de dimensões superiores.

Abordagens de Análise de Dados Topológicos (TDA) existentes tentam preencher essa lacuna, mas enfrentam limitações específicas:

ToMATo: Baseia-se na homologia de dimensão 0 (componentes conexos) e paisagens de densidade, limitando sua capacidade de incorporar informações topológicas de dimensões superiores.
TPCC: Utiliza complexos simpliciais e Laplacianos de Hodge, mas pode ter dificuldade em distinguir regiões onde características topológicas emergem em diferentes escalas de filtragem.
Topological k-Means (TKM): Incorpora diagramas de persistência em Espaços de Hilbert de Núcleo Reproduzível (RKHS), mas foca em resumos topológicos globais em vez de uma topologia multiescalar localizada.

O desafio central abordado por este trabalho é a necessidade de um algoritmo de agrupamento que possa capturar simultaneamente a proximidade geométrica local e estruturas topológicas de dimensões superiores de uma maneira multiescalar, sem depender apenas de resumos de persistência globais ou escalas topológicas fixas.

2. Metodologia: Algoritmo BFTC

O método proposto, Agrupamento Topológico Baseado em Filtragem de Números de Betti (BFTC), constrói uma estrutura de similaridade consciente da topologia através das seguintes etapas:

A. Construção do Grafo de Vizinhança

O algoritmo começa construindo um grafo de vizinhança local para o conjunto de dados $X$ . Ele suporta duas variantes:

k-NN BFTC: Utiliza um grafo de k-vizinhos mais próximos para garantir cardinalidade uniforme e esparsidade controlada.
$\epsilon$ -BFTC: Utiliza um grafo de vizinhança $\epsilon$ baseado em um raio geométrico fixo, alinhando-se naturalmente com construções de limiar métrico.

B. Filtragem de Vietoris-Rips Local e Sequências de Betti

Para cada ponto de dado $x_i$ , o algoritmo constrói uma série de complexos Vietoris-Rips (VR) aninhados sobre sua vizinhança local $N(x_i) \cup \{x_i\}$ .

Uma escala de filtragem é definida por uma sequência de limiares $\epsilon_1, \epsilon_2, \dots, \epsilon_L$ .
Para cada escala, o complexo VR $VR(x_i, \epsilon_l)$ é formado.
Números de Betti: O algoritmo computa os números de Betti $\beta_m$ até uma dimensão máxima $M$ especificada pelo usuário (onde $M$ reflete a complexidade topológica intrínseca, não necessariamente a dimensão do espaço ambiente).
Sequências de Betti: Para cada dimensão $m \in [0, M]$ , a sequência de números de Betti através das escalas de filtragem forma uma sequência de Betti $\beta^{(i)}_m = (\beta^{(i)}_{1m}, \dots, \beta^{(i)}_{Lm})$ . Essas sequências servem como assinaturas topológicas multiescalares de la vizinhança local.

C. Similaridade Consciente da Topologia e Refinamento de Grafo

O algoritmo quantifica a similaridade topológica entre pontos vizinhos comparando suas sequências de Betti.

Métrica de Similaridade: A similaridade de cosseno é computada entre as sequências de Betti dos pontos adjacentes $x_i$ e $x_j$ para cada dimensão $m$ :
$(d_{ij})_m = \frac{\langle \beta^{(i)}_m, \beta^{(j)}_m \rangle}{\|\beta^{(i)}_m\| \|\beta^{(j)}_m\|}$
Remoção de Outliers: Um conjunto de limiares $\alpha_0, \dots, \alpha_M$ é aplicado. Um vizinho $x_j$ é retido na vizinhança refinada $N'(x_i)$ apenas se $(d_{ij})_m \geq \alpha_m$ para todas as dimensões $m$ . Esta etapa elimina vizinhos topologicamente dissimilar e outliers, resultando em um grafo mais esparso e informativo.

D. Agrupamento Espectral (Spectral Clustering)

Uma matriz de adjacência ponderada simétrica $A'$ é construída a partir do grafo refinado usando um kernel Gaussiano. A matriz Laplaciana $L' = D' - A'$ é computada, e o agrupamento espectral (via k-Means nos autovetores dos $p$ menores autovalores) é aplicado para obter o agrupamento final.

3. Principais Contribuições

O artigo delineia três contribuições primárias:

Novo Algoritmo (BFTC): Um algoritmo de agrupamento eficiente que constrói complexos de Vietoris-Rips sobre vizinhanças locais e avalia números de Betti até uma dimensão prescrita. Ele utiliza sequências de Betti para medir a similaridade topológica, indo além da simples conectividade ( $\beta_0$ ) para capturar características de dimensões superiores.
Eficácia em Estruturas Complexas: O método é especificamente projetado para lidar com conjuntos de dados com formas e estruturas complexas e entrelaçadas, aproveitando as características topológicas subjacentes.
Análise Teórica: O artigo fornece fundamentos teóricos extensos sobre a convergência e estabilidade do BFTC. Estabelece que, sob condições razoáveis de separação geométrica e espectral, o algoritmo é estruturalmente estável; pequenas perturbações nos dados de entrada não alteram o agrupamento resultante (salvo permutação de rótulos).

4. Resultados Experimentais

Os autores avaliaram o BFTC (variantes k-NN e $\epsilon$ ) contra baselines de estado da arte (k-Means, Spectral, DBSCAN, ToMATo, TPCC, TKM, etc.) em conjuntos de dados sintéticos e do mundo real.

Conjuntos de Dados Sintéticos: Em conjuntos de dados com estruturas não convexas e entrelaçadas (ex: Linked Tori, 3MC, Smile1, Torus Sphere Line), o BFTC alcançou consistentemente pontuações superiores de Índice Rand Ajustado (ARI) e Informação Mútua Normalizada (NMI). Por exemplo, no dataset Linked Tori com ruído ( $\rho=0.3$ ), o k-NN BFTC alcançou um ARI de 0.49 e NMI de 0.56, superando significativamente competidores como DBSCAN (0.01 ARI) e ToMATo (0.17 ARI).
Conjuntos de Dados do Mundo Real: Experimentos em datasets do UCI (Zoo, Ecoli, Wisconsin B.C., Glass, ORHD, MNIST, Phishing URL) demonstraram que o BFTC superou quase todos os concorrentes.
Robustez: O método mostrou estabilidade contra perturbações de ruído Gaussiano.
Estudos de Ablação:
- Construção de Vizinhança: Tanto as vizinhanças k-NN quanto as $\epsilon$ provaram ser eficazes, embora o k-NN tenha oferecido um comportamento espectral mais suave para variedades altamente entrelaçadas.
- Métricas de Distância: A similaridade de cosseno entre sequências de Betti mostrou-se significativamente mais eficaz do que a distância Euclidiana para capturar relações topológicas.
- Funções de Kernel: A inclusão de um kernel Gaussiano na matriz de adjacência melhorou o desempenho em comparação com grafos não ponderados.

5. Significância e Alegações

O artigo afirma que o BFTC representa um avanço significativo ao integrar informação topológica multiescalar diretamente no processo de agrupamento. Ao contrário de métodos anteriores que dependem de resumos de persistência globais ou escalas fixas, o BFTC captura a topologia multiescalar localizada através de sequências de Betti.

Os autores afirmam que esta abordagem permite ao algoritmo:

Distinguir regiões de uma variedade onde as características topológicas emergem em diferentes escalas de filtragem.
Capturar simultaneamente a proximidade geométrica e estruturas topológicas de dimensões superiores (loops, vazios).
Fornecer uma solução robusta para conjuntos de dados com estruturas complexas, não convexas e entrelaçadas, onde métodos tradicionais baseados em Euclides falham.

A análise teórica sustenta ainda os resultados empíricos, alegando que o BFTC não é apenas computacionalmente finito, mas também estruturalmente estável, garantindo que o pipeline de agrupamento seja localmente invariante a pequenas perturbações nos dados de entrada. O trabalho conclui que explorar aspectos topológicos para conjuntos de dados de larga escala com estruturas complexas sobrepostas continua sendo uma direção promissora para pesquisas futuras.