HDBSCAN* · clustering baseado em densidade · sensibilidade a parâmetros

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.

Experimente: 180 pontos, um controle de densidade Toque em um ponto para ver a core distance dele.
Cores: clusters selecionados. Cinza: ruído. Círculo sólido: core distance no valor atual; tracejado: no próximo valor.
m = 30
Aqui os dois parâmetros andam juntos, como quando o min_samples não é definido e assume o valor do min_cluster_size.
–clusters
–pontos de ruído
–ARI com o próximo valor
FAIXA DE ESTABILIDADE · cada barra é um passo m → próximo m (altura = ARI; vermelho = passo frágil, ARI < 0,8)
5valor de min_samples →70

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.

Resumo

O que o artigo encontrou

Por quê?Encolhimento

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.

Qual cluster?82% vs 10%

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.

Quando é seguro?0 erros

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.

Parte 1 · O básico

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.

CONDENSED TREE (valor atual de min_samples). Largura = pontos ainda no cluster; para baixo = mais denso (λ = 1/raio). Blocos coloridos = clusters selecionados pelo EOM.

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.

Parte 2 · O problema

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.

16,9%dos passos foram frágeis em 47 novos datasets de benchmark (IC 95%: 11,2–23,1)
91,2%dos passos frágeis em pipelines reais mudaram o número de clusters
16,5%dos pontos mudam de rótulo em um passo frágil típico (mediana, benchmarks)
22,6%dos passos foram frágeis em 10 tabelas maiores do OpenML

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.

O ARI pode esconder uma mudança dessas. No exemplo do artigo, o passo de 35 para 40 apaga um cluster de 41 pontos e muda o rótulo de 23,3% dos pontos, mas o ARI é 0,91. Por isso, o artigo também reporta o número de clusters e a fração de pontos que mudaram de rótulo.
Parte 3 · Por que acontece

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.

Laboratório 2 × 2 ARI medido em relação à saída original (canto superior esquerdo).
30 → 35

O laboratório mostra um único dataset. Em 47 datasets novos, os passos frágeis se dividem assim.

a nova árvore sozinha muda a saída cada mudança sozinha já muda o limiar sozinho (2%) só as duas juntas
Frações arredondadas dos passos frágeis. Fonte: Tabela 5 do artigo.

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.

Taxa de fragilidade quando só a árvore muda, para clusters plantados perto do limiar. Para clusters com 2–3 vezes o limiar, a taxa foi 0,0% em todas as formas. 300 réplicas; testes com correção de Holm. Fonte: Tabela 7 do artigo.

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.

Parte 4 · Qual cluster

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.

ŝ(C) = número de pontos p de C com corepróximo m(p) ≤ raio de nascimento de C

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.

O preditor no exemplo Usa o passo escolhido no laboratório acima.

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.

ŝ abaixo do próximo limiar
82%
ŝ igual ou acima do limiar
10%
Taxa de perda entre clusters de tamanho semelhante (1 a 1,25 vez o próximo limiar; 4.205 clusters). Diferença de 72,7 pontos, IC 95% 54,2–87,6. AUC 0,821 para o preditor contra 0,763 para o tamanho sozinho. Fonte: Tabela 9 do artigo.

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.

Parte 5 · Quando é seguro

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.

(S) tamanho

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.

(D1) clusters selecionados

Estabilidade de sobra

A estabilidade certificada de cada cluster selecionado supera o máximo que os descendentes dele poderiam alcançar.

(M) margens

Decisões folgadas

Toda decisão do EOM na execução atual venceu por uma margem maior do que o passo pode alterar.

Esquema (não são dados). Cada cluster selecionado tem um núcleo certificado (hachurado) que precisa manter pelo menos min_cluster_size pontos. Os pontos dentro do núcleo comprovadamente mantêm o rótulo; os pontos em U podem mudar.

É 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.

Mesma cobertura, menos erros
Certificado (|U| ≤ 1%)
0
Regra de persistência
12
Regra de tamanho
15
Passos frágeis entre os declarados seguros, quando cada regra declara seguro o mesmo número de passos (815 passos certificados em três estudos). Limite superior exato de 95% para o certificado: 0,5%. Em 25 tabelas novas: 0 de 261, contra 8 e 2. Fonte: Figura 4 do artigo (análise post hoc).

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.

Rolle e Scoccola (2024) propõem um flattening com um teorema de estabilidade. Na fatia horizontal que o HDBSCAN* usa, ele foi frágil em 22,1% dos passos, contra 16,7% do EOM (análise secundária, sem teste). Isso concorda com a Proposição 45 deles: uma mudança de uma unidade no parâmetro pode mover a hierarquia arbitrariamente para longe. Por isso, um certificado para o min_samples precisa usar o crescimento observado das core distances.
Parte 6 · Custo

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 threadcovertypeHiggs
Um ajuste do HDBSCAN*63 s208 s
Varredura no grid de 24 valores24 min80 min
Verificação do certificado (após a consulta de vizinhos)1,5 s1,2 s
A verificação custa cerca de 1% de um ajuste. Fonte: o artigo, Seção 1 e Seção Suplementar S4.3.
Parte 7 · Na prática

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:

  1. Rode alguns valores de min_samples em torno da sua escolha e verifique se os clusters se mantêm.
  2. 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.
  3. Quando a estabilidade importa, reporte a concordância entre valores vizinhos, com e sem ruído, e os passos certificados.
  4. Atenção à convenção de contagem: o min_samples do scikit-learn conta o próprio ponto e o da biblioteca hdbscan não; assim, m + 1 no scikit-learn equivale a m no hdbscan.

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
  1. Rode o HDBSCAN* no valor atual m e guarde a condensed tree e os clusters selecionados.
  2. Para cada cluster selecionado C, tome o nível λ em que ele nasce na condensed tree; o raio de nascimento dele é 1/λ.
  3. 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).
  4. ŝ(C) é o número de pontos de C cuja nova core distance é no máximo o raio de nascimento.
  5. 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.

Parte 8 · Como foi testado

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.

DadosPerguntaConfirmadas
61 datasets de benchmark e do OpenMLexploração: primeira versão de cada ferramenta–
47 datasets novos, 3 seedscom que frequência; qual etapa causa1 de 5
gaussianas plantadas; 51 datasetsmecanismo, com o limiar fixo3 de 4
cinco formas plantadas; 19 tabelasrobustez à forma e a confundidores8 de 8
10 tabelas do OpenML, até 20.000 pontostabelas maiores: taxa, mecanismo, certificado3 de 5
17 datasets: single-cell, BERTopic, Gaiapipelines reais3 de 4
25 tabelas novas do OpenMLpreditor ŝ; reamostragem3 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_samples discordaram 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.
Contexto

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.

Referência rápida

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.