Soluções — Aula 3: Topografia de Densidade e Grafos — Clustering Hierárquico e HDBSCAN

Aprendizado Não Supervisionado

Autor

Marcos M. Raimundo — Instituto de Computação, UNICAMP

Data de Publicação

18 de setembro de 2026

Dica

Gabarito das questões de Verdadeiro/Falso de exercicios.qmd. O glifo (✔/✗) antes do texto de cada afirmação já indica o veredito; o campo Resposta repete por extenso.

Teste 1 — Cluster como componente conexa vs. distância a centróide

Considere duas definições possíveis de cluster. Na primeira, cada ponto é atribuído ao protótipo (centro) mais próximo dentre um conjunto fixo de protótipos — a regra usada pelo K-Means — o que sempre particiona o espaço em regiões poligonais convexas (uma tesselação de Voronoi). Na segunda, para uma densidade estimada \(p(\mathbf{x})\) e um limiar \(\lambda\ge 0\), define-se o conjunto de nível \(L_\lambda=\{\mathbf{x}:p(\mathbf{x})\ge\lambda\}\) (os pontos do espaço com densidade pelo menos \(\lambda\)), e um cluster é uma componente conexa de \(L_\lambda\) — um bloco de densidade alta que se pode percorrer inteiro sem nunca sair de \(L_\lambda\).

□ Se um cluster verdadeiro tem formato de “U” (uma curva fechada quase se tocando nas duas pontas), uma atribuição por protótipo mais próximo com um número suficientemente grande de protótipos eventualmente recupera esse formato exato como um único cluster.
□ A convexidade de cada célula de Voronoi é uma consequência necessária de usar distância euclidiana ao protótipo mais próximo como regra de atribuição — não uma escolha adicional independente de qual algoritmo específico é usado para posicionar os protótipos.
□ Um cluster definido como componente conexa de um conjunto de nível \(L_\lambda\) pode, em princípio, ter qualquer formato geométrico, inclusive não-convexo, desde que exista um caminho contínuo dentro de \(L_\lambda\) ligando quaisquer dois de seus pontos.
□ Se dois pontos pertencem à mesma componente conexa de \(L_\lambda\), isso implica que a distância euclidiana direta entre eles é menor do que a distância de qualquer um dos dois a pontos fora dessa componente.

(Resposta) Teste 1 — Cluster como componente conexa vs. distância a centróide

✗ Falso — Apenas a soma de muitas células convexas pequenas aproxima visualmente a forma do “U”, essa abordagem nunca produz “um único cluster” — a saída são tantos rótulos distintos quantos protótipos, um por célula de Voronoi, cada um tratado como um cluster separado.
✔ Verdadeiro — A célula de cada protótipo \(k\) é a interseção dos semiespaços “mais perto de \(k\) do que de qualquer \(j\)” — toda interseção de semiespaços é convexa, por definição, para qualquer métrica induzida por norma (a euclidiana inclusa). Não existe uma variante de “atribuição ao protótipo mais próximo” que produza células não-convexas; a convexidade nasce da própria regra de atribuição, não é algo escolhido além dela.
✔ Verdadeiro — A definição de componente conexa não impõe nenhuma restrição de forma — qualquer subconjunto de \(L_\lambda\) que seja “percorrível” internamente conta como uma única componente, seja qual for seu contorno (espiral, forma de “U”, ramificado etc.), desde que exista uma trilha inteiramente dentro de \(L_\lambda\) ligando dois pontos quaisquer dela.
✗ Falso — Conectividade por densidade não controla distância geométrica direta — duas pontas de uma forma em “U” podem estar geometricamente mais distantes entre si do que cada uma está de pontos do lado de fora do cluster, mas próximas por uma trilha que contorna o “U” inteiro. “Estar no mesmo cluster” (via trilha densa) e “estar geometricamente mais próximo” são propriedades independentes; confundir as duas reintroduz, pela porta de trás, a suposição de convexidade que a definição pretende evitar.

Teste 2 — Conjuntos de nível e a hierarquia indexada por \(\lambda\)

Lembrete: para uma densidade \(p(\mathbf{x})\) e um limiar \(\lambda\ge0\), \(L_\lambda=\{\mathbf{x}:p(\mathbf{x})\ge\lambda\}\), e um cluster (nesse \(\lambda\) fixo) é uma componente conexa de \(L_\lambda\). Hastie, Tibshirani & Friedman (The Elements of Statistical Learning, ESL, 2009, p. 507) catalogam três paradigmas de clustering: o combinatório (atribuição a um conjunto fixo de protótipos, como no K-Means), a modelagem por mistura (assume uma densidade paramétrica com \(K\) componentes, como uma mistura de gaussianas ajustada pelo algoritmo EM) e os “buscadores de moda” (mode seekers), que estimam diretamente as regiões de alta densidade — a abordagem via \(L_\lambda\) descrita acima.

□ Decrescer \(\lambda\) de um valor alto para um valor baixo pode dividir uma componente conexa de \(L_\lambda\) em duas, além de poder fundir componentes existentes.
□ Se duas regiões de alta densidade são separadas por um vale de densidade exatamente zero em pelo menos um ponto em qualquer caminho entre elas, então, para qualquer \(\lambda>0\), elas nunca aparecem como uma única componente conexa de \(L_\lambda\).
□ A definição de cluster via \(L_\lambda\) dispensa completamente a necessidade de qualquer parâmetro de escala, ao contrário de uma atribuição por protótipos fixos (que exige escolher quantos protótipos usar).
□ ESL (p. 507) descreve “buscadores de moda” (mode seekers) como um paradigma que estima diretamente as modas da densidade e atribui cada observação à moda mais próxima — um paradigma distinto tanto do combinatório quanto da modelagem por mistura.

(Resposta) Teste 2 — Conjuntos de nível e a hierarquia indexada por \(\lambda\)

✗ Falso — \(L_\lambda\) só pode crescer (nunca encolher) conforme \(\lambda\) diminui, porque \(\{\mathbf{x}:p(\mathbf{x})\ge\lambda\}\) é um conjunto cada vez maior para \(\lambda\) menor. Um conjunto que só cresce nunca separa uma região previamente conectada em duas — crescer pode conectar regiões antes separadas (fundir), mas nunca desconecta uma região já conectada.
✔ Verdadeiro — Se existe um ponto no caminho com \(p(\mathbf{x})=0\), esse ponto nunca pertence a \(L_\lambda\) para nenhum \(\lambda>0\) (precisaria \(p(\mathbf{x})\ge\lambda>0\)). Sem esse ponto, qualquer trilha entre as duas regiões que passe por ele fica quebrada dentro de \(L_\lambda\) — as duas regiões nunca se tornam uma componente conexa só, para nenhum \(\lambda\) positivo. Essa é uma “barreira genuína” de densidade, e não um artefato do limiar escolhido.
✗ Falso — \(L_\lambda\) substitui a escolha de “quantos protótipos” por uma escolha diferente — o próprio \(\lambda\) (ou, no HDBSCAN, min_cluster_size/min_samples) — não elimina a necessidade de uma decisão de escala. min_cluster_size ainda é, ela mesma, uma escolha de escala. Trocar um parâmetro por outro não é o mesmo que eliminar o parâmetro.
✔ Verdadeiro — É o texto citado (ESL, p. 507, tradução livre): “buscadores de moda… tentando estimar diretamente as modas distintas da densidade… observações mais próximas de cada moda definem os clusters”. Os três paradigmas (combinatório, modelagem por mistura, mode seeking) são distintos entre si.

Teste 3 — Core distance: densidade local como peso de aresta

Para um ponto \(\mathbf{x}\) e um inteiro \(K\), seja \(d_K(\mathbf{x})\) a distância de \(\mathbf{x}\) ao seu \(K\)-ésimo vizinho mais próximo (sem contar o próprio ponto) — \(d_K(\mathbf{x})\) pequeno significa que \(\mathbf{x}\) tem muitos vizinhos por perto (região densa); \(d_K(\mathbf{x})\) grande significa que foi preciso ir longe para achar \(K\) vizinhos (região rara/isolada). Define-se \(\mathrm{core}_K(\mathbf{x}) = d_K(\mathbf{x})\), chamando-a de core distance: a mesma quantidade, usada aqui como peso de aresta num grafo, não mais só como estimador direto de densidade.

□ \(\mathrm{core}_K(\mathbf{x})\) pequeno continua significando região densa — a fórmula não mudou, só o papel que a quantidade desempenha (estimador de densidade vs. peso de aresta).
□ Se \(K\) for aumentado (por exemplo, de \(5\) para \(50\)), o valor de \(\mathrm{core}_K(\mathbf{x})\) para um ponto numa região densa tende a variar relativamente menos do que o mesmo aumento de \(K\) produziria para um ponto numa região rara — porque, numa região densa, os vizinhos adicionais estão a distâncias parecidas às já contadas, enquanto numa região rara é preciso alcançar vizinhos cada vez mais distantes.
□ Dois pontos com o mesmo valor de \(\mathrm{core}_K\), para o mesmo \(K\), necessariamente moram na mesma região do espaço de atributos.
□ \(\mathrm{core}_K(\mathbf{x})\), como definido acima, não depende em nada da escolha de \(K\) — é uma propriedade fixa de cada ponto, independente de qualquer parâmetro.

(Resposta) Teste 3 — Core distance: densidade local como peso de aresta

✔ Verdadeiro — \(\mathrm{core}_K(\mathbf{x})=d_K(\mathbf{x})\) é, por definição, a distância ao \(K\)-ésimo vizinho mais próximo — é literalmente o mesmo número usado antes como estimador direto de densidade, sem alteração de fórmula; só o uso muda, para peso de aresta num grafo.
✔ Verdadeiro — Numa região densa, muitos vizinhos estão a distâncias parecidas entre si, então aumentar \(K\) adiciona vizinhos a distâncias próximas (baixa variação relativa); numa região rara, os vizinhos ficam espalhados, e aumentar \(K\) precisa alcançar vizinhos cada vez mais distantes, produzindo maior variação relativa.
✗ Falso — \(\mathrm{core}_K\) é um escalar — dois pontos podem ter exatamente o mesmo valor estando em regiões completamente diferentes do espaço (ex.: duas montanhas distintas, cada uma com densidade local parecida, mas geometricamente distantes uma da outra). “Mesmo valor de uma estatística de densidade local” não implica “mesma localização” — \(\mathrm{core}_K\) descarta toda informação posicional, guardando só uma medida de escala local.
✗ Falso — \(\mathrm{core}_K(\mathbf{x})=d_K(\mathbf{x})\) é, por definição, a distância ao \(K\)-ésimo vizinho mais próximo — depende diretamente da escolha de \(K\) (\(K\) diferente, vizinho diferente, distância diferente). É exatamente o papel de min_samples no HDBSCAN: um parâmetro de escala que desempenha o papel de \(K\) no core distance.

Teste 4 — Distância de alcançabilidade mútua

Lembrete: \(\mathrm{core}_K(\mathbf{x})\) é a distância de \(\mathbf{x}\) ao seu \(K\)-ésimo vizinho mais próximo — pequena em regiões densas, grande em regiões raras/isoladas. A partir dela, define-se a distância de alcançabilidade mútua entre dois pontos \(a,b\): \[d_{\mathrm{mreach}}(a,b) = \max\bigl(\mathrm{core}_K(a),\ \mathrm{core}_K(b),\ d(a,b)\bigr),\] onde \(d(a,b)\) é a distância euclidiana bruta entre eles.

□ \(d_{\mathrm{mreach}}(a,b) \ge d(a,b)\) vale sempre, para quaisquer \(a,b\) e qualquer \(K\) — a alcançabilidade mútua nunca aproxima dois pontos além de sua distância bruta.
□ Se \(a\) e \(b\) estão ambos em regiões muito densas (ambos os core distances pequenos), \(d_{\mathrm{mreach}}(a,b)\) é, em geral, determinado pela distância bruta \(d(a,b)\), não pelos núcleos.
□ Num cenário em que \(a\) está numa região densa e \(b\) está isolado bem longe de qualquer vizinho, \(d_{\mathrm{mreach}}(a,b)\) é necessariamente igual a \(d(a,b)\), porque o núcleo de \(a\) (pequeno) domina o máximo.
□ Trocar a distância bruta \(d\) por \(d_{\mathrm{mreach}}\) em todo o grafo pode mudar quais arestas pertencem à MST, comparado à MST construída sobre a distância bruta original.

(Resposta) Teste 4 — Distância de alcançabilidade mútua

✔ Verdadeiro — Por definição, \(d_{\mathrm{mreach}}(a,b) = \max(\mathrm{core}_K(a), \mathrm{core}_K(b), d(a,b))\) — o máximo de um conjunto que inclui \(d(a,b)\) é, por definição, sempre maior ou igual a \(d(a,b)\): a alcançabilidade mútua nunca aproxima, só afasta.
✔ Verdadeiro — Quando \(\mathrm{core}_K(a)\) e \(\mathrm{core}_K(b)\) são pequenos (menores que \(d(a,b)\), o caso comum dentro de uma mesma região densa), o máximo é dominado pelo terceiro termo, \(d(a,b)\) — pontos que moram na mesma região densa têm sua alcançabilidade mútua praticamente inalterada em relação à distância bruta.
✗ Falso — O máximo é dominado pelo termo MAIOR, não pelo menor — um núcleo pequeno (de \(a\)) nunca “domina” o máximo. É o núcleo grande de \(b\) (o ponto isolado) que domina, forçando \(d_{\mathrm{mreach}}(a,b) \ge \mathrm{core}_K(b)\), tipicamente maior que \(d(a,b)\). O item inverte a lógica do máximo: confundir “qual termo é pequeno” com “qual termo decide o resultado” é o erro central.
✔ Verdadeiro — \(d_{\mathrm{mreach}}\) reordena e infla pesos de forma não-uniforme (afasta seletivamente pontos isolados, mantém pontos densos praticamente inalterados) — a ordenação relativa de arestas pode mudar: uma aresta que era a mais barata sob distância bruta pode deixar de ser sob \(d_{\mathrm{mreach}}\) (se um dos extremos tiver core distance grande), alterando quais arestas entram na árvore geradora mínima.

Teste 5 — MST e a equivalência com ligação simples

Dado um conjunto de \(N\) pontos com uma matriz de distâncias par a par, a Árvore Geradora Mínima (MST, Minimum Spanning Tree) é a árvore (subgrafo conexo, sem ciclos, com \(N-1\) arestas) que liga todos os \(N\) pontos minimizando a soma dos pesos das arestas. Ligação simples (single linkage) é o critério de clustering hierárquico aglomerativo em que a distância entre dois grupos \(G,H\) é a menor distância entre um ponto de cada grupo: \(d_{SL}(G,H)=\min_{i\in G,i'\in H}d_{ii'}\). A construção da MST vale para qualquer matriz de distâncias válida — inclusive a distância de alcançabilidade mútua \(d_{\mathrm{mreach}}(a,b)=\max(\mathrm{core}_K(a),\mathrm{core}_K(b),d(a,b))\), que combina a distância bruta com uma medida de densidade local.

□ Para um conjunto de \(N\) pontos, a MST sobre a matriz de distâncias brutas tem sempre exatamente \(N-1\) arestas, independente de quantos clusters “verdadeiros” existam nos dados.
□ Cortar as \(k-1\) arestas mais pesadas da MST produz sempre uma partição em exatamente \(k\) componentes conexas, para qualquer \(1\le k\le N\).
□ Se a MST inteira for reconstruída usando \(d_{\mathrm{mreach}}\) em vez da distância bruta, o resultado de “cortar as \(k-1\) arestas mais pesadas” ainda corresponde ao clustering de ligação simples — mas agora sobre as distâncias de alcançabilidade mútua, não sobre as distâncias brutas originais.
□ Considere um exemplo com \(7\) pontos formando três grupos visuais: A \(=\{0,1,2\}\), B \(=\{3,4,5\}\), e um ponto isolado, o ponto \(6\). A menor distância entre um ponto de A e um ponto de B é \(6{,}14\); a menor distância entre o ponto \(6\) e qualquer ponto de A ou de B é \(6{,}22\). Ao cortar a aresta mais pesada da MST (para obter \(k=2\) clusters), A e B se fundem entre si antes de o ponto \(6\) se juntar a qualquer um dos dois grupos — isso é uma inconsistência do algoritmo de ligação simples, não uma consequência esperada da definição \(d_{SL}(G,H)=\min_{i\in G,i'\in H}d_{ii'}\).

(Resposta) Teste 5 — MST e a equivalência com ligação simples

✔ Verdadeiro — É uma propriedade de teoria de grafos, não dos dados: qualquer árvore geradora de um grafo conexo com \(N\) vértices tem exatamente \(N-1\) arestas, por definição de árvore — independentemente de quantos “clusters verdadeiros” (um conceito estatístico, não estrutural) existam.
✔ Verdadeiro — Remover uma aresta de uma árvore sempre a desconecta em exatamente dois pedaços (árvores não têm ciclos, então cada aresta é uma “ponte”); remover \(k-1\) arestas de uma árvore de \(N-1\) arestas, uma por vez, produz exatamente \(k\) componentes — vale para qualquer \(k\) entre \(1\) (nenhuma removida) e \(N\) (todas as \(N-1\) removidas).
✔ Verdadeiro — O resultado clássico (MST-corte = ligação simples) é uma propriedade puramente de teoria de grafos, válida para qualquer matriz de pesos simétrica não-negativa — não depende de a matriz ser distância bruta especificamente. Trocar por \(d_{\mathrm{mreach}}\) (ainda uma matriz de pesos válida) preserva a equivalência, só sobre a métrica nova.
✗ Falso — É uma consequência direta e correta da definição — a distância mínima entre A e B (\(6{,}14\)) é, por pouco, menor que a distância mínima entre qualquer um dos dois grupos e o ponto 6 (\(6{,}22\)); ligação simples funde sempre o par de menor dissimilaridade primeiro, então A-B se fundem antes por definição, não por erro — mesmo sendo contraintuitivo à primeira vista (o ponto 6 “parece” mais isolado visualmente, mas a definição usa apenas o par mais próximo entre grupos).

Teste 6 — O defeito do encadeamento (chaining)

Lembrete: na ligação simples, a distância entre dois grupos é a menor distância entre um ponto de cada grupo. O fenômeno de encadeamento (chaining) citado abaixo é atribuído por Hastie, Tibshirani & Friedman (ESL, 2009, p. 524) a esse critério. O HDBSCAN (Hierarchical DBSCAN) é o algoritmo que constrói a hierarquia completa de ligação simples sobre a distância de alcançabilidade mútua \(d_{\mathrm{mreach}}(a,b)=\max(\mathrm{core}_K(a),\mathrm{core}_K(b),d(a,b))\) e extrai clusters usando um parâmetro min_cluster_size — o número mínimo de pontos para que um ramo da hierarquia conte como cluster, em vez de ser tratado como pontos perdidos do ramo-pai.

□ O encadeamento citado do ESL ocorre porque a ligação simples define a proximidade entre dois grupos pelo par mais próximo entre eles, ignorando todos os outros pares — uma única cadeia de pontos intermediários basta para acionar uma fusão.
□ Ligação completa (complete linkage, que usa a distância máxima entre pares, não a mínima) sofreria exatamente do mesmo defeito de encadeamento que a ligação simples, pela mesma razão matemática.
□ Um único ponto de ruído inserido bem no meio do vale entre dois clusters genuinamente distintos pode, por si só, fazer a ligação simples fundir os dois num nível de dissimilaridade artificialmente baixo.
□ \(d_{\mathrm{mreach}}\) reduz a chance de encadeamento causado por pontos isolados de baixa densidade, mas não elimina, por si só, todo encadeamento possível — daí a necessidade adicional de min_cluster_size no HDBSCAN.

(Resposta) Teste 6 — O defeito do encadeamento (chaining)

✔ Verdadeiro — É exatamente a definição de \(d_{SL}\) (mínimo entre pares) e a explicação do ESL: como só uma dissimilaridade pequena entre um par já basta, uma série de pontos intermediários próximos entre si (mesmo que os extremos da cadeia estejam distantes) já é suficiente para encadear uma fusão de baixo nível.
✗ Falso — Ligação completa usa o MÁXIMO entre pares — para fundir dois grupos, todos os pares precisam estar relativamente próximos, não só um. Isso é o oposto do mecanismo do encadeamento (que explora um único par próximo ignorando os demais); ligação completa tende, ao contrário, a produzir clusters compactos, não encadeados — o defeito citado é específico à regra do mínimo, não generaliza para o máximo.
✔ Verdadeiro — Um ponto no meio do vale cria dois pares de distâncias curtas (ponto-a-A e ponto-a-B), cada uma menor que a distância direta A-B — a ligação simples usa o mínimo entre pares, então essas novas distâncias curtas fazem a fusão ocorrer num nível de dissimilaridade bem mais baixo do que sem o ponto extra.
✔ Verdadeiro — \(d_{\mathrm{mreach}}\) penaliza pontos com core distance grande (isolados), reduzindo o caso mais comum de encadeamento por pontos raros — mas uma cadeia de pontos moderadamente densos (não isolados o bastante para ter core distance alto) ainda pode encadear via distância bruta dominando o máximo; por isso o HDBSCAN precisa da defesa adicional de min_cluster_size.

Teste 7 — Árvore condensada

O HDBSCAN constrói a hierarquia completa de ligação simples sobre a distância de alcançabilidade mútua \(d_{\mathrm{mreach}}\) e a condensa: com um parâmetro min_cluster_size (o número mínimo de pontos para contar como cluster), sempre que um ramo da hierarquia se divide em dois, o lado com menos que min_cluster_size pontos é tratado como pontos perdidos do ramo-pai (não como um ramo novo) — só divisões em que ambos os lados são grandes o bastante viram novos ramos (o ramo original passa a ser o cluster-pai dos dois ramos-filhos) na árvore condensada.

□ Na árvore condensada, um ramo com menos que min_cluster_size pontos, ao se separar do seu ramo-pai, é tratado como “pontos perdidos” do pai, não como um cluster novo — mesmo que, na hierarquia completa (não condensada), esse ramo aparecesse como uma divisão legítima.
□ Condensar a árvore usando min_cluster_size elimina completamente a necessidade de qualquer outro parâmetro de escala no HDBSCAN, já que a persistência decide tudo o mais automaticamente.
□ Aumentar min_cluster_size tende a reduzir o número de ramos que sobrevivem como clusters candidatos na árvore condensada, comparado a um min_cluster_size menor sobre a mesma hierarquia completa.
□ A árvore condensada de um conjunto de dados sem nenhuma estrutura de cluster real (por exemplo, uma única Gaussiana multivariada bem comportada) pode, ainda assim, ter ramos que sobrevivem ao condensamento, dependendo de min_cluster_size escolhido.

(Resposta) Teste 7 — Árvore condensada

✔ Verdadeiro — É exatamente a regra de condensamento: ramos pequenos (abaixo de min_cluster_size) são tratados como “pontos que se perderam do cluster pai”, não como novos ramos — independentemente de a hierarquia completa (sem condensamento) já registrar essa divisão como um evento válido.
✗ Falso — O HDBSCAN ainda depende de min_samples (o \(K\) do core distance), além de min_cluster_size — a persistência decide QUAIS ramos sobrevivem dada a árvore condensada, mas não decide, por si só, o que conta como “denso” em primeiro lugar (isso vem de min_samples/core distance) nem o tamanho mínimo de ramo (min_cluster_size). Dois parâmetros de escala continuam presentes.
✔ Verdadeiro — Um min_cluster_size maior exige que mais ramos sejam fundidos ao pai (só ramos suficientemente grandes contam como cluster candidato) — isso reduz o número total de ramos candidatos sobreviventes, comparado a um limiar menor sobre a mesma hierarquia.
✔ Verdadeiro — Mesmo numa única Gaussiana (sem clusters verdadeiros), flutuações amostrais locais produzem sub-regiões de densidade ligeiramente mais alta/mais baixa; se min_cluster_size for pequeno o suficiente, algumas dessas flutuações podem, por acaso, ter tamanho suficiente para sobreviver ao condensamento — um cluster espúrio. É por isso que a persistência (não só o condensamento) é necessária para distinguir estrutura real de flutuação amostral.

Teste 8 — Persistência por excesso de massa

Na árvore condensada do HDBSCAN, cada ramo (cluster candidato) nasce num certo nível de densidade \(\lambda\) e vai perdendo pontos (que viram ruído, ou passam a um ramo-filho quando o ramo se divide) até desaparecer. A persistência (excesso de massa) de um ramo \(C\), nascido em \(\lambda_{\mathrm{nasc}}(C)\), é \[\text{persistência}(C)=\sum_{p\in C}\bigl(\lambda_p-\lambda_{\mathrm{nasc}}(C)\bigr),\] onde \(\lambda_p\) é o valor de \(\lambda\) em que o ponto \(p\) deixou \(C\) — cada ponto contribui uma quantidade proporcional a quanto tempo (em \(\lambda\)) ficou dentro do ramo antes de sair. Clusters de maior persistência total sobreviveram por mais tempo como blocos coerentes.

□ A persistência de um cluster candidato é definida somando, para cada ponto do ramo, o intervalo de \(\lambda\) (ou de \(1/d_{\mathrm{mreach}}\)) em que esse ponto pertenceu a esse cluster específico antes de ser absorvido pelo pai ou virar ruído.
□ Um cluster que aparece por uma faixa muito curta de \(\lambda\) antes de se fundir com outro tem, em geral, persistência mais baixa do que um cluster de tamanho comparável que sobrevive por uma faixa longa de \(\lambda\).
□ A extração final por persistência, em cada ramificação da árvore condensada, escolhe sempre “dividir nos dois filhos” em vez de “manter o pai inteiro”, porque dois clusters específicos têm, por definição, mais persistência somada do que um cluster genérico.
□ Se dois clusters candidatos tivessem exatamente o mesmo tamanho (mesmo número de pontos), eles teriam, necessariamente, a mesma persistência, independente de quanto tempo cada um sobreviveu na hierarquia.

(Resposta) Teste 8 — Persistência por excesso de massa

✔ Verdadeiro — É exatamente a definição de persistência (excesso de massa): a soma, por ponto, do intervalo de sobrevivência daquele ponto como membro daquele cluster específico, ao longo da faixa de \(\lambda\).
✔ Verdadeiro — Persistência é, por definição, uma soma sobre o intervalo de sobrevivência — para tamanho de ramo comparável, uma faixa mais curta de \(\lambda\) produz uma soma menor do que uma faixa mais longa; é diretamente a definição de “excesso de massa” (mais tempo sobrevivendo = mais massa acumulada).
✗ Falso — A extração escolhe o lado de MAIOR persistência total entre as duas opções — não há garantia de que “dividir” sempre vença; se o pai (antes de dividir) já acumulou muita massa sozinho e os dois filhos, individualmente, têm persistências pequenas, manter o pai inteiro pode ter persistência total maior. Não existe uma regra fixa “dividir sempre vence” — é decidido caso a caso.
✗ Falso — Persistência depende do tamanho do ramo E de quanto tempo sobrevive (soma por ponto do intervalo de \(\lambda\)), não só do tamanho — dois clusters com o mesmo número de pontos, mas um sobrevivendo por uma faixa de \(\lambda\) muito mais longa que o outro antes de se fundir ou virar ruído, têm persistências diferentes. Confundir “mesmo tamanho” com “mesma persistência” ignora a dimensão de faixa de \(\lambda\) da definição.

Teste 9 — O resultado no Breast Cancer Wisconsin

No dataset Breast Cancer Wisconsin (\(569\) pacientes, cada um com diagnóstico rotulado como tumor benigno ou maligno), o HDBSCAN foi rodado usando apenas dois atributos numéricos do tumor, sem usar o rótulo de diagnóstico, encontrando dois clusters: o Cluster 0, com \(54\) pacientes, todos malignos (\(100\%\) de pureza maligna); e o Cluster 1, com \(347\) pacientes, dos quais \(315\) benignos e \(32\) malignos (\(\approx90{,}8\%\) de pureza benigna). Os demais \(168\) pacientes (\(\approx29{,}5\%\) do total) ficaram marcados como ruído, fora dos dois clusters. Dos \(212\) pacientes malignos ao todo, \(126\) (\(\approx59{,}4\%\)) caíram nesse ruído. O rótulo de diagnóstico só foi usado depois, para comparar com a partição encontrada — nunca durante o clustering.

□ O cluster de \(54\) pacientes, sendo \(100\%\) malignos, é uma evidência de que o HDBSCAN funcionou como um classificador treinado no rótulo diagnosis.
□ O fato de \(126\) dos \(212\) pacientes malignos totais caírem em ruído (não em nenhum dos dois clusters) é consistente com a ideia de que tumores malignos variam mais em apresentação clínica do que tumores benignos, formando uma “montanha” de densidade menos coesa nesses dois atributos.
□ A pureza benigna do Cluster 1 (\(315\) de \(347\), \(\approx90{,}8\%\)), medida só entre os pacientes que o HDBSCAN de fato agrupou (excluindo ruído), tende a parecer mais favorável do que a concordância geral com o diagnóstico, porque os casos mais ambíguos já foram descartados como ruído antes da comparação.
□ Se o HDBSCAN não tivesse encontrado cluster nenhum nesses dois atributos (todos os \(569\) pacientes marcados como ruído), a tabela de contingência não revelaria nenhum alinhamento com o diagnóstico, porque não haveria partição nenhuma para comparar contra ele.

(Resposta) Teste 9 — O resultado no Breast Cancer Wisconsin

✗ Falso — “Funcionar como um classificador treinado no rótulo” implicaria que o rótulo influenciou o ajuste — o que é falso: o HDBSCAN nunca viu diagnosis durante o clustering (só os atributos numéricos).
✔ Verdadeiro — Tumores malignos costumam ter múltiplos subtipos/estágios, então sua densidade nesses dois atributos tende a ser mais espalhada/menos coesa, formando uma “montanha” mais baixa e irregular que não sobrevive inteira como cluster de alta persistência; boa parte cai no “vale” entre o núcleo denso e a massa benigna, virando ruído.
✔ Verdadeiro — Os \(168\) pacientes marcados como ruído são justamente os casos mais ambíguos sob esses dois atributos — não se encaixam com confiança em nenhuma das duas regiões densas. Medir pureza só dentro dos clusters (excluindo esse grupo difícil) produz, mecanicamente, um número mais favorável do que uma métrica de concordância calculada sobre todos os \(569\) pacientes, ruído incluso: qualquer forma de descartar os casos mais difíceis antes de medir a qualidade tende a inflar o número resultante, não porque o método melhorou, mas porque a base de comparação ficou mais fácil.
✗ Falso — “Todos marcados como ruído” ainda é uma partição — trivial (uma única categoria, “ruído”, contendo todo mundo), mas uma partição válida, comparável a qualquer rótulo real numa tabela de contingência. Essa comparação existe e tem um resultado bem definido: como o ruído não distingue benignos de malignos (todos caem na mesma categoria), a tabela revelaria justamente a AUSÊNCIA de alinhamento com o diagnóstico — não a impossibilidade de comparar. Afirmar que “não haveria partição nenhuma para comparar” confunde “partição sem informação” com “nenhuma partição”.

Teste 10 — Hiperparâmetros: min_cluster_size e min_samples

No HDBSCAN, min_cluster_size é o número mínimo de pontos para que um ramo da árvore condensada conte como cluster (em vez de ser tratado como pontos perdidos do cluster-pai); min_samples é o valor de \(K\) usado no cálculo do core distance \(\mathrm{core}_K(\mathbf{x})\) — a distância de um ponto ao seu \(K\)-ésimo vizinho mais próximo, usada como medida de densidade local. Uma alternativa a esses dois parâmetros seria fixar diretamente um único limiar de densidade \(\lambda\) (como nos conjuntos de nível \(L_\lambda\)) ou um raio \(\varepsilon\) fixo (como no DBSCAN clássico).

□ Trocar a escolha de um valor de \(\lambda\) global (um limiar único de densidade, como nos conjuntos de nível \(L_\lambda\) ou no raio \(\varepsilon\) do DBSCAN clássico) por uma escolha de min_cluster_size no HDBSCAN elimina, por completo, qualquer decisão de escala que o usuário precise tomar.
□ Reduzir min_cluster_size para um valor muito pequeno (como \(2\)) tende a reintroduzir uma versão do problema de encadeamento discutido para a ligação simples pura.
□ min_samples desempenha, no HDBSCAN, um papel análogo ao de \(K\) no core distance \(\mathrm{core}_K(\mathbf{x})\) — ambos controlam quantos vizinhos definem a escala local de densidade.
□ Um cluster que só aparece ao forçar min_cluster_size bem mais alto do que o valor originalmente usado é, por esse único motivo, necessariamente tão confiável estatisticamente quanto um cluster que aparece de forma estável numa faixa ampla de valores testados.

(Resposta) Teste 10 — Hiperparâmetros: min_cluster_size e min_samples

✗ Falso — min_cluster_size (e min_samples) ainda são escolhas de escala — o HDBSCAN troca uma decisão (\(\lambda\) ou \(\varepsilon\) fixo) por outra (tamanho mínimo de cluster / \(K\) do core distance), não elimina a necessidade de decisão alguma.
✔ Verdadeiro — Com min_cluster_size=2, cadeias finas de poucos pontos passam a contar como clusters válidos por si mesmas, reintroduzindo o mesmo mecanismo de encadeamento (fusões via par único próximo) que a ligação simples pura já sofria.
✔ Verdadeiro — min_samples é exatamente o valor de \(K\) usado no cálculo do core distance — ambos determinam quantos vizinhos entram no cálculo da distância que define “quão densa” é a vizinhança de um ponto.
✗ Falso — Aparecer só sob um ajuste forçado do parâmetro (e não numa faixa estável de valores) é evidência de sensibilidade ao limiar escolhido — um sinal de possível artefato, não de robustez. Um cluster que aparece de forma estável através de vários valores de min_cluster_size é evidência mais forte de estrutura real.

Teste 11 — Maldição da dimensionalidade em clustering por densidade

Um teste do HDBSCAN no dataset Breast Cancer Wisconsin (\(569\) pacientes): usando apenas \(2\) atributos padronizados, \(70{,}5\%\) dos pacientes caem em algum cluster; usando os \(30\) atributos originais do mesmo dataset, todos padronizados, sem seleção de atributos, a fração de pacientes marcados como ruído já é \(\approx59{,}2\%\) com min_cluster_size \(=5\), e chega a \(100\%\) (nenhum cluster sobrevive) a partir de min_cluster_size \(\ge 10\). Isso reproduz, no clustering por densidade, um fenômeno geral de espaços de alta dimensão: à medida que o número de atributos cresce, as distâncias entre pontos tendem a ficar todas parecidas entre si, perdendo poder de discriminar “perto” de “longe” — e como \(\mathrm{core}_K(\mathbf{x})\) (a distância ao \(K\)-ésimo vizinho mais próximo) e \(d_{\mathrm{mreach}}\) dependem diretamente dessas distâncias, ambos herdam o mesmo problema.

□ A queda de \(70{,}5\%\) dos pacientes em algum cluster (com \(2\) atributos) para \(100\%\) de ruído (com \(30\) atributos, min_cluster_size \(\ge 10\)) ocorre porque \(\mathrm{core}_K\) (a distância ao \(K\)-ésimo vizinho mais próximo) herda o mesmo mecanismo pelo qual distâncias perdem poder discriminativo em alta dimensão.
□ Aumentar min_cluster_size até encontrar algum cluster de novo em 30 dimensões resolve a causa raiz da maldição da dimensionalidade para esse dataset, não só o sintoma de “nenhum cluster apareceu”.
□ Uma atribuição por protótipos fixos (distância euclidiana a centros) aplicada aos mesmos \(30\) atributos padronizados não sofre da maldição da dimensionalidade, porque não usa nenhum estimador de densidade baseado em vizinhos como \(\mathrm{core}_K\).
□ Reduzir a dimensionalidade (por exemplo, escolher um subconjunto pequeno de atributos informativos, como os dois atributos usados no exemplo do Breast Cancer Wisconsin acima) antes de rodar HDBSCAN ataca a causa do problema, não só o sintoma.

(Resposta) Teste 11 — Maldição da dimensionalidade em clustering por densidade

✔ Verdadeiro — Como \(\mathrm{core}_K(\mathbf{x})=d_K(\mathbf{x})\) e \(d_{\mathrm{mreach}}\) depende de \(\mathrm{core}_K\) e da distância bruta, ambas herdam a perda de poder discriminativo de distâncias em alta dimensão — o mesmo fenômeno geral de concentração de medida —, fazendo a árvore condensada não encontrar ramo estável o bastante para sobreviver como cluster.
✗ Falso — Forçar min_cluster_size mais alto ataca o sintoma (falta de clusters aparentes), não a causa (perda de poder discriminativo das distâncias em alta dimensão); um cluster que aparece só por esse ajuste não é necessariamente confiável — pode ser um artefato do limiar forçado, não estrutura real recuperada.
✗ Falso — Distância euclidiana a um protótipo fixo sofre sua própria versão da maldição (distâncias entre pontos e protótipos também perdem significado geométrico relativo em alta dimensão) — nenhum método baseado em distância escapa por completo desse fenômeno. Não usar \(\mathrm{core}_K\) especificamente não é o mesmo que estar imune à maldição em geral.
✔ Verdadeiro — Reduzir dimensionalidade ataca diretamente a causa (distâncias perdendo poder discriminativo por excesso de dimensões, muitas delas pouco informativas para a estrutura de cluster) — é a rota mais direta para recuperar poder discriminativo, em vez de mascarar o sintoma forçando um parâmetro de escala.

Teste 12 — Partição rígida vs. probabilística

O HDBSCAN produz uma partição rígida: cada ponto pertence a exatamente um cluster, ou é marcado como ruído — nunca uma mistura de vários ao mesmo tempo. Uma alternativa é uma partição probabilística, como a de um Modelo de Mistura Gaussiana (GMM) ajustado pelo algoritmo EM (Expectation-Maximization): cada ponto recebe uma probabilidade de pertencer a cada cluster (por exemplo, \(50\%\) de chance de vir do cluster 1 e \(50\%\) do cluster 2), em vez de um rótulo único. Hastie, Tibshirani & Friedman (ESL, 2009, p. 507) descrevem três paradigmas de clustering: o combinatório (protótipos fixos, como no K-Means), a modelagem por mistura (como o GMM acima) e os “buscadores de moda” (que estimam diretamente regiões de alta densidade — a abordagem do HDBSCAN).

□ A saída do HDBSCAN atribui cada ponto a exatamente um cluster, ou a ruído — nunca uma probabilidade de pertencimento a mais de um cluster ao mesmo tempo.
□ Um paciente cujos atributos tumorais ficam exatamente na fronteira entre uma região densa de tumores malignos e uma massa de tumores benignos, sob uma atribuição probabilística (GMM/EM), receberia tipicamente uma probabilidade bem definida e próxima de \(1\) para um único cluster, e próxima de \(0\) para o outro — igual ao HDBSCAN, sem diferença prática nesse caso.
□ O ESL (p. 507) cita “modelagem por mistura” como um paradigma de clustering distinto tanto do combinatório (protótipos fixos) quanto do “mode seeking” (HDBSCAN) — os três paradigmas citados acima.
□ A escolha entre uma partição rígida (HDBSCAN) e uma probabilística (GMM/EM) é, em essência, uma escolha sobre o quanto se acredita que os clusters verdadeiros se sobrepõem genuinamente, não uma escolha puramente de conveniência computacional.

(Resposta) Teste 12 — Partição rígida vs. probabilística

✔ Verdadeiro — É exatamente a definição de partição “rígida”: cada ponto recebe um rótulo único (um dos clusters, ou ruído), nunca uma distribuição de probabilidade entre múltiplos clusters simultaneamente.
✗ Falso — É exatamente o caso em que a atribuição probabilística DIFERE do HDBSCAN — um ponto genuinamente na fronteira (onde os clusters se sobrepõem) receberia, sob GMM/EM, probabilidades intermediárias (não próximas de \(0\) ou \(1\)) para os dois clusters, refletindo a ambiguidade real; forçar \(0\)/\(1\) nesse caso seria o comportamento do HDBSCAN, não a diferença que uma atribuição probabilística pretende introduzir.
✔ Verdadeiro — É exatamente a taxonomia de três paradigmas do ESL: combinatório, modelagem por mistura, mode seeking — cada um distinto dos outros dois.
✔ Verdadeiro — A escolha reflete uma hipótese sobre a estrutura real dos dados (existe ou não um vale de densidade genuíno separando os grupos) — não é uma questão de conveniência de implementação.