O cluster que encolhe
O HDBSCAN* pode mudar a resposta quando você aumenta o min_samples em um pequeno passo. Esta página explica por quê, como identificar o cluster em risco e como provar que um passo é seguro.
Um biólogo agrupa 20.000 células e encontra cinco tipos celulares. Um time de dados agrupa avaliações de clientes em tópicos com o BERTopic. Um astrônomo procura novos aglomerados estelares em um catálogo de estrelas. Os três usam o HDBSCAN*, e os três definem o parâmetro de densidade dele, o min_samples, uma única vez, ou o deixam no valor padrão.
Uma pequena mudança nesse parâmetro, digamos de 30 para 35, costuma mudar pouco. Nos benchmarks do meu preprint, com o min_cluster_size acompanhando o min_samples como no padrão, cerca de um passo em cada seis (16,9% em 47 datasets) mudou muito o resultado: um cluster sumiu, dois clusters se fundiram ou um quinto dos pontos mudou de rótulo.
Isso não é uma falha escondida. Qualquer regra com um limiar de tamanho se comporta assim: quando um parâmetro muda, um cluster perto do min_cluster_size pode sair da seleção ou se juntar a outro. A documentação diz isso. O guia do hdbscan mostra que o min_samples “clearly has a dramatic effect on clustering” e deixa o agrupamento mais conservador à medida que cresce. O guia do usuário do scikit-learn diz que o min_samples “tends to be a more robust hyperparameter” em comparação com o eps do DBSCAN, o que não quer dizer que a partição fique igual. As docstrings do scikit-learn e do hdbscan, e o guia do BERTopic, informam que o min_samples assume o valor do min_cluster_size quando não é definido. Campello et al. (2015) o descrevem como um fator de suavização clássico em estimativas de densidade, ao qual métodos com um parâmetro análogo costumam ser robustos, e o fixam em um único valor não crítico nos experimentos. Eles também relatam que rodadas com outros valores não mudaram as conclusões principais. O que faltava era medir com que frequência um passo pequeno muda a partição flat e ter um jeito de prever isso sem rodar de novo.
Testar os valores vizinhos por força bruta mostra se um passo muda o resultado, mas é lento: com 100.000 pontos, uma varredura por 24 valores leva de 24 a 80 minutos. O preprint propõe uma checagem mais barata, que usa a execução que você já tem. Ela explica por que um passo muda o resultado, marca o cluster em risco e prova quando um passo é seguro, a cerca de 1% do custo de uma nova execução. Esses resultados vêm de um único preprint, que ainda não passou por revisão por pares. Para testar a checagem nos seus próprios dados, com o scikit-learn ou com a biblioteca hdbscan:
pip install git+https://github.com/provezano/minpts-check
from minpts_check import check_min_samples
check_min_samples(X, min_samples=30, min_cluster_size=30).summary()
A demonstração abaixo roda o HDBSCAN* no seu navegador, para você ver um cluster sumir.
Três nuvens gaussianas (60, 60 e 40 pontos) e 20 pontos espalhados, como no exemplo do artigo, sorteadas aqui. Os números diferem dos do artigo; o comportamento é o mesmo.
O que o artigo encontrou
Um min_samples maior muda a árvore de clusters. Um cluster selecionado pode encolher abaixo do tamanho mínimo de cluster, sair da seleção e mudar a saída.
Uma contagem feita na execução atual sinaliza o cluster em risco. Em tabelas novas, 82% dos clusters sinalizados foram perdidos, contra 10% dos clusters não sinalizados de mesmo tamanho.
Um teorema dá condições, verificadas em uma única execução, sob as quais o próximo valor mantém os mesmos clusters. Nenhum passo certificado foi frágil.
Como o HDBSCAN* encontra clusters
Imagine os dados como uma paisagem em que a altitude é a densidade de pontos. À medida que o nível da água baixa, os picos mais densos aparecem primeiro como ilhas, e depois ilhas vizinhas se juntam. O HDBSCAN* registra essa história como uma árvore e então escolhe um conjunto de ilhas como os clusters.
Dois parâmetros guiam o processo. O min_samples (mpts no artigo) define quantos vizinhos um ponto precisa ter para contar como denso. O min_cluster_size (mclSize) define a menor ilha que conta como cluster. No scikit-learn, na biblioteca hdbscan e no BERTopic, o min_samples assume o valor do min_cluster_size quando não é definido, então por padrão os dois andam juntos. Clique nas cinco etapas para ver cada uma no exemplo.
A última etapa, excess of mass (EOM), dá a cada ramo uma pontuação de estabilidade: grosso modo, por quanto tempo os pontos dele ficam juntos enquanto o nível de densidade sobe. Depois, escolhe os ramos com a maior pontuação total, nunca um ramo junto com um de seus descendentes. Só ramos com pelo menos min_cluster_size pontos podem ser escolhidos, e essa regra está por trás de tudo o que vem a seguir.
Um passo pequeno, uma grande mudança
Com o método explicado, podemos medir com que frequência um passo pequeno muda a resposta. Neto et al. (2018) descrevem o HDBSCAN* como robusto ao min_samples, no sentido de que uma mudança pequena “typically leads to only a small or no change in the clustering structure”, uma afirmação sobre a hierarquia, e não sobre os clusters flat. Os usuários trabalham com a partição flat final; por isso, a medição precisa ser feita na partição.
O artigo chama um passo de frágil quando as saídas em dois valores vizinhos concordam pouco, com adjusted Rand index (ARI) abaixo de 0,8 e o ruído contado como um único rótulo. Os valores vizinhos vêm de um grid de 24 valores entre 5 e 120, cada um de 11% a 20% acima do anterior.
Os pipelines reais foram análise single-cell com scanpy e UMAP, modelagem de tópicos com BERTopic e a busca por aglomerados estelares em dados do satélite Gaia. Quando um passo foi frágil, quase sempre um cluster apareceu, desapareceu, se dividiu ou se fundiu.
A culpa é da árvore, não do limiar
Para prever essas mudanças, primeiro precisamos saber qual etapa do método as causa. Quando o min_cluster_size acompanha o min_samples, um passo muda duas coisas: a árvore, porque as core distances crescem, e o limiar de tamanho. Um desenho 2 × 2 separa as duas coisas, mudando só a árvore, só o limiar ou ambos. Escolha um passo no laboratório e compare os quatro painéis.
O laboratório mostra um único dataset. Em 47 datasets novos, os passos frágeis se dividem assim.
O EOM escolhe apenas entre ramos com pelo menos min_cluster_size pontos. Um novo limiar na árvore antiga só pode remover clusters que já estavam abaixo dele, o que é raro. Uma nova árvore pode encolher qualquer ramo. Quando um cluster selecionado cai abaixo do limiar, ele deixa de ser candidato, e o EOM decide de novo o ramo acima dele: o cluster vira ruído, se junta a um vizinho, ou o ramo é reorganizado.
Para testar isso diretamente, o artigo fixou o limiar e plantou clusters de tamanho conhecido. Clusters logo acima do limiar (1,2 a 1,35 vez) eram perdidos com frequência, e clusters duas a três vezes maiores nunca eram. Todas as formas testadas se comportaram assim.
Em dados reais, passos perto do limiar foram mais frágeis do que passos longe dele, após ajustar pelo número de clusters, pela fração de ruído e pelo próprio limiar (odds ratio 6,6). Alguns passos longe do limiar também são frágeis; portanto, o tamanho explica a maioria dos casos, mas não todos.
Um preditor que usa uma única execução
Se um cluster é perdido porque encolhe na nova árvore, podemos perguntar quantos dos pontos dele permanecem no nível em que ele nasce. Isso não exige uma nova árvore: basta calcular as core distances no próximo valor com uma consulta de vizinhos mais próximos e contar.
Se ŝ cai abaixo do próximo min_cluster_size, o cluster não pode reaparecer inalterado. No exemplo do artigo, o cluster de 41 pontos tem ŝ = 38 no passo para 40, e é perdido. No passo de 8 para 9, todo cluster tem ŝ ≥ 43, bem acima do limiar.
Em seguida, o preditor foi testado em 25 tabelas do OpenML que o trabalho nunca tinha usado, com a análise fixada antes do download dos dados.
O preditor ordena bem tanto os clusters absorvidos por um cluster maior (AUC 0,80) quanto os que se dissolvem em ruído (0,94). Ele não prevê divisões, que são raras aqui (40 de 1.620 perdas) e seguem outro mecanismo. As divisões predominam quando o min_samples diminui, caso que o artigo não cobre.
Usada como alarme, a regra “sinalize o passo se algum cluster tiver ŝ abaixo do próximo limiar” sinalizou 48% dos passos e pegou 89% dos frágeis. Só 4,4% dos passos não sinalizados eram frágeis. Essa análise é exploratória e não foi replicada.
Reamostrar os dados mostra o mesmo efeito de tamanho. Clusters logo acima do limiar desapareceram em 52% das reamostragens, contra 17% a 26% dos maiores.
Um certificado de que nada muda
Prever o risco é útil, mas provar a segurança é mais forte. O teorema do artigo usa a execução atual e as distâncias aos vizinhos no próximo valor. Se as três condições dele valem, o próximo valor seleciona os mesmos clusters, e todo ponto fora de um pequeno conjunto de tolerância U mantém o rótulo. A nova árvore nunca é construída.
Um núcleo que se mantém
Todo cluster selecionado mantém um núcleo certificado com pelo menos tantos pontos quanto o próximo min_cluster_size, em todos os níveis de densidade que o passo pode afetar.
Estabilidade de sobra
A estabilidade certificada de cada cluster selecionado supera o máximo que os descendentes dele poderiam alcançar.
Decisões folgadas
Toda decisão do EOM na execução atual venceu por uma margem maior do que o passo pode alterar.
É na condição de tamanho que o mecanismo de encolhimento volta. Se um cluster selecionado pode cair abaixo do limiar durante o passo, o certificado não afirma segurança. Dos passos frágeis, 82,7% falham primeiro nesta condição.
O certificado cobre uma minoria dos passos. Com U limitado a 1% dos pontos, ele certificou 9,5% dos passos nos dados exploratórios e 26,2% em um novo conjunto de benchmark. Ele foi construído como um diagnóstico que mostra onde a estabilidade pode ser provada e por que ela falha nos outros casos. Um U grande ainda permite ARI abaixo de 0,8, então U deve ser limitado.
min_samples precisa usar o crescimento observado das core distances.Por que não simplesmente rodar de novo?
As duas ferramentas podem parecer desnecessárias, já que bastaria rodar o HDBSCAN* de novo no próximo valor. Uma nova execução mostra o que mudou, mas não por quê, e custa um ajuste completo por valor. O preditor e o certificado precisam da execução atual mais uma consulta de vizinhos mais próximos para o grid inteiro.
| 100.000 pontos, 1 thread | covertype | Higgs |
|---|---|---|
| Um ajuste do HDBSCAN* | 63 s | 208 s |
| Varredura no grid de 24 valores | 24 min | 80 min |
| Verificação do certificado (após a consulta de vizinhos) | 1,5 s | 1,2 s |
O que fazer com isso
O caminho mais rápido é o minpts-check, que faz toda a checagem a partir de um único ajuste e uma consulta de vizinhos: aponta os clusters em risco, prova os passos seguros e cuida da convenção de contagem.
pip install git+https://github.com/provezano/minpts-check
from minpts_check import check_min_samples
check_min_samples(X, min_samples=30, min_cluster_size=30).summary()
Para checar à mão, seja usando o HDBSCAN* diretamente, no scikit-learn ou dentro do BERTopic:
- Rode alguns valores de
min_samplesem torno da sua escolha e verifique se os clusters se mantêm. - Trate como alerta um cluster selecionado próximo do
min_cluster_size, ou com ŝ abaixo do próximo limiar. Calcular ŝ custa uma consulta de vizinhos e nenhum novo ajuste. - Quando a estabilidade importa, reporte a concordância entre valores vizinhos, com e sem ruído, e os passos certificados.
- Atenção à convenção de contagem: o
min_samplesdo scikit-learn conta o próprio ponto e o da bibliotecahdbscannão; assim, m + 1 no scikit-learn equivale a m nohdbscan.
Se você compara métodos que usam o HDBSCAN*, reporte min_samples, min_cluster_size, o método de extração e o algoritmo da árvore. Prefira árvores exatas quando a estabilidade importa: a árvore aproximada padrão foi mais frágil (29,3% dos passos contra 23,4% nos dados exploratórios).
Calculando ŝ passo a passo
- Rode o HDBSCAN* no valor atual m e guarde a condensed tree e os clusters selecionados.
- Para cada cluster selecionado C, tome o nível λ em que ele nasce na condensed tree; o raio de nascimento dele é 1/λ.
- Calcule, para cada ponto, a distância até o vizinho que define a core distance dele no próximo valor m′ (uma consulta k-NN; atenção à convenção de contagem acima).
- ŝ(C) é o número de pontos de C cuja nova core distance é no máximo o raio de nascimento.
- Se ŝ(C) < m′ (o próximo
min_cluster_size), sinalize C como em risco.
O material suplementar do artigo inclui uma implementação de referência do relatório de estabilidade e do verificador do certificado; o minpts-check reúne os dois para uso no dia a dia.
Um estudo exploratório e seis replicações
Os números desta página vêm de sete estudos. As ferramentas foram desenvolvidas em 61 datasets. Cada estudo posterior usou dados que nenhum estudo anterior tinha tocado, testou poucas hipóteses com correção de Holm e seguiu um plano de análise escrito antes das execuções. Toda hipótese planejada é reportada, confirmada ou não.
| Dados | Pergunta | Confirmadas |
|---|---|---|
| 61 datasets de benchmark e do OpenML | exploração: primeira versão de cada ferramenta | – |
| 47 datasets novos, 3 seeds | com que frequência; qual etapa causa | 1 de 5 |
| gaussianas plantadas; 51 datasets | mecanismo, com o limiar fixo | 3 de 4 |
| cinco formas plantadas; 19 tabelas | robustez à forma e a confundidores | 8 de 8 |
| 10 tabelas do OpenML, até 20.000 pontos | tabelas maiores: taxa, mecanismo, certificado | 3 de 5 |
| 17 datasets: single-cell, BERTopic, Gaia | pipelines reais | 3 de 4 |
| 25 tabelas novas do OpenML | preditor ŝ; reamostragem | 3 de 4 |
Algumas hipóteses não foram confirmadas, e elas também são informativas:
- Nos pipelines reais, a taxa de fragilidade (13,6%) não ficou significativamente acima de 10%, e variou conforme o pipeline.
- No BERTopic, duas seeds do UMAP com o mesmo
min_samplesdiscordaram em 98,1% dos casos; ou seja, a seed do embedding move a saída muito mais do que o parâmetro. - Nas tabelas maiores, a razão de tamanho como pontuação única agregada ordenou os passos só moderadamente (AUC 0,71, abaixo da meta planejada), embora os tenha ordenado bem dentro de cada tabela.
- Reduções do
min_samples, a extração leaf e as árvores aproximadas ficam fora das afirmações principais.
O que já se sabia
O HDBSCAN* foi proposto por Campello, Moulavi e Sander (2013, 2015), e McInnes e colegas (2017) escreveram a implementação popular. A estabilidade da hierarquia é bem estudada, da teoria estatística das árvores de clusters de densidade ao ToMATo (Chazal e colegas, 2013) e ao trabalho de Rolle e Scoccola (2024), que também mostram que a hierarquia pode mudar arbitrariamente após uma mudança de uma unidade no parâmetro.
Trabalhos anteriores também já tinham notado sensibilidade na partição final. O PLSCAN (Bot e colegas, 2025) observa, em um exemplo, que os clusterings do HDBSCAN* variam consideravelmente com o parâmetro, e escolhe o tamanho mínimo de cluster por persistência. O FOSC-X (Simpson e Campello, 2026) lista soluções EOM quase ótimas em uma árvore fixa. Malzer e Baum (2020) documentaram a fragmentação excessiva em microclusters com valores pequenos. Neto e colegas (2018, 2021, 2022) calculam as hierarquias para todos os valores de uma vez e as descrevem como robustas a pequenas mudanças. Hunt e Reffert (2021) verificaram, em dados do Gaia, que a taxa de recuperação de aglomerados estelares conhecidos vai de 0,42 a 0,82 conforme o tamanho mínimo de cluster.
Que um cluster perto do limiar de tamanho possa sair da seleção quando um parâmetro muda é esperado de qualquer regra com limiar. O artigo acrescenta uma medida de concordância entre valores vizinhos que dispensa rótulos de referência, a etapa do método que causa cada mudança, uma previsão de qual cluster será perdido e uma prova de quando um passo é inofensivo. Esses resultados vêm de um único preprint e ainda precisam de replicação independente.
Glossário
- min_samples (mpts)
- Quantos vizinhos definem a core distance de um ponto. Controla a suavização da densidade.
- min_cluster_size (mclSize)
- Tamanho mínimo de um ramo para que ele conte como cluster na condensed tree.
- core distance
- Distância de um ponto até o m-ésimo vizinho mais próximo. Pequena em regiões densas.
- mutual reachability
- max(core(p), core(q), distância(p, q)). A distância usada para construir a árvore.
- λ (lambda)
- Nível de densidade, igual a 1 / raio. Quanto maior, mais denso.
- condensed tree
- A hierarquia depois de descartar os ramos menores que min_cluster_size.
- EOM
- Excess of mass: a regra que seleciona os clusters finais maximizando a estabilidade total.
- passo frágil
- Dois valores vizinhos de min_samples cujas saídas têm ARI < 0,8 (ruído contado como um único rótulo).
- ARI
- Adjusted Rand index: 1 = partições idênticas; perto de 0 = concordância ao acaso.
- cluster perdido
- Nenhum cluster da outra saída tem índice de Jaccard de pelo menos 1/2 com ele.
- ŝ
- Número de pontos do cluster cuja nova core distance cabe dentro do raio em que o cluster nasce (o raio de nascimento dele).
- conjunto de tolerância U
- Os únicos pontos que o certificado não cobre; todos os outros comprovadamente mantêm o rótulo.