🤖 machine learning

Hierarchical Clustering Can Jointly Satisfy Richness, Consistency, and Scale Invariance

Este artigo demonstra que, ao contrário do agrupamento plano, que é limitado pelo Teorema da Impossibilidade de Kleinberg, o agrupamento hierárquico pode satisfazer simultaneamente os axiomas de riqueza, consistência e invariância de escala através da existência de incontáveis métodos admissíveis que compartilham uma espinha dorsal estrutural comum, apesar de sua diversidade.

Autores originais: Daichi Kuroda, Maximilien Dreveton, Matthias Grossglauser, Patrick Thiran

Publicado 2026-09-11

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Daichi Kuroda, Maximilien Dreveton, Matthias Grossglauser, Patrick Thiran

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

No mundo da ciência de dados, existe uma tarefa fundamental chamada agrupamento (clustering). Imagine que você tem uma coleção de itens — talvez uma mistura de frutas, ou um grupo de pessoas, ou um conjunto de documentos — e deseja organizá-los em grupos significativos com base no quão semelhantes são entre si. Você não possui um rótulo dizendo qual maçã é qual; você possui apenas uma medida de quão diferente cada item é de todos os outros. O objetivo é deixar os dados falarem por si mesmos e revelar sua estrutura oculta. Por décadas, pesquisadores tentaram definir a maneira perfeita de realizar essa ordenação. Eles propuseram um conjunto de regras básicas que qualquer bom método de ordenação deveria seguir. Uma regra é que o método não deve se importar com as unidades de medida; quer você meça a distância em metros ou milhas, os grupos devem permanecer os mesmos. Outra regra é que o método deve ser flexível o suficiente para encontrar qualquer agrupamento possível, caso os dados sejam adequados para isso. Uma terceira regra é que, se você tornar os itens dentro de um grupo mais semelhantes entre si e tornar os itens entre os grupos mais diferentes, o método não deve decidir subitamente separar esse grupo.

Por muito tempo, acreditou-se que nenhum método único poderia satisfazer todas essas três regras ao mesmo mesmo tempo. Um resultado famoso na área mostrou que, se você for forçado a cortar seus dados em apenas uma camada plana de grupos — como separar um baralho de cartas em pilhas de naipes — você inevitavelmente terá que quebrar uma das regras. Você pode ter que ignorar a escala dos dados, ou pode ter que ignorar certos agrupamentos válidos, ou pode ter que ser instável quando os dados mudam ligeiramente. Isso criou uma sensação de limitação, como se a própria natureza de ordenar dados em grupos planos fosse falha. Mas e se a solução não fosse forçar os dados em uma única camada, mas deixá-los se desenrolar em uma árvore? E se, em vez de apenas dizer "estes são os grupos", você pudesse dizer "estes são os grupos, e dentro desses grupos, existem grupos menores, e dentro destes, outros ainda menores"? Esta é a ideia do agrupamento hierárquico, onde o resultado é uma estrutura aninhada em vez de uma lista plana.

Uma equipe de pesquisadores da École Polytechnique Fédérale de Lausanne e da Université Gustave Eiffel mostrou agora que essa abordagem hierárquica muda tudo. Eles pegaram as três regras estritas que tornavam o agrupamento plano impossível e perguntaram se elas poderiam ser satisfeitas se o resultado fosse uma hierarquia. A resposta é um sim definitivo. Eles provaram que não existe apenas uma maneira de fazer isso, mas um número incontavelmente grande de métodos que podem satisfazer todas as três regras simultaneamente. De fato, eles descobriram que o espaço desses métodos válidos é incrivelmente vasto e diverso. É tão grande que você nem consegue listar todos eles e, dentro dessa vasta coleção, existem muitos métodos que são fundamentalmente incompatíveis entre si. Você não pode simplesmente escolher o "melhor" que faça tudo perfeitamente, porque não existe um único método que seja o vencedor supremo que refine todos os outros.

Os pesquisadores não apenas provaram que esses métodos existem; eles construíram vários deles para mostrar como funcionam. Eles observaram formas comuns de ordenar dados, como o método que sempre funde os dois itens mais próximos primeiro. Descobriram que uma versão específica desse método, que permite fundir mais de dois grupos de uma vez quando estão igualmente próximos, funciona perfeitamente. Eles também inventaram novos métodos baseados em quão bem separados estão os grupos. Um método busca grupos onde os itens dentro deles estão muito mais próximos entre si do que de qualquer coisa fora deles. Outro busca um tipo ligeiramente diferente de separação. Eles mostraram que esses métodos são todos válidos, mas produzem resultados diferentes. Alguns métodos são muito rigorosos e encontram apenas os grupos mais óbvios e bem separados. Outros são mais permissivos e encontram muitas conexões mais sutis.

Apesar dessa diversidade selvagem, os pesquisadores descobriram uma ordem oculta. Embora os métodos discordem nos detalhes mais finos, todos concordam com as estruturas mais óbvias e bem separadas. Se você pegar quaisquer dois métodos válidos e observar os grupos nos quais ambos concordam, encontrará uma espinha dorsal comum de clusters claros e distintos. Isso significa que, embora os métodos possam diferir no tratamento da parte confusa e intermediária dos dados, todos respeitam a mesma fundação sólida. Os pesquisadores também exploraram o que acontece se adicionarmos uma quarta regra: que, se os dados já possuem uma estrutura de árvore perfeita integrada neles, o método deve encontrar exatamente essa árvore. Mesmo com esse requisito mais rigoroso, a vasta diversidade de métodos permanece, mas agora há um único método mais grosseiro que serve como ponto de partida para todos os outros.

Este trabalho remodela nossa compreensão de como podemos organizar dados. Ele mostra que a impossibilidade de satisfazer todos os nossos desejos por um método de ordenação não é uma falha fundamental do universo, mas uma limitação de forçar os dados em uma única camada plana. Ao permitir que os dados contem uma história de grupos aninhados, podemos ter o melhor dos dois mundos. Podemos ter um método que é invariante à escala, flexível e estável, tudo ao mesmo tempo. Os pesquisadores também mostraram que esses métodos são robustos às formas comuns de pré-processamento de dados, como mudar as unidades ou transformar os números antes da ordenação. Isso sugere que o framework não é apenas uma curiosidade matemática, mas uma ferramenta prática que pode ser usada em pipelines do mundo real. O estudo nos deixa com a imagem de uma paisagem repleta de inúmeras maneiras válidas de ordenar o mundo, todas concordando com as características mais importantes, mas oferecendo uma rica variedade de perspectivas sobre os detalhes.

Resumo Técnico: O Agrupamento Hierárquico Pode Satisfazer Conjuntamente Riqueza, Consistência e Invariância de Escala

Enunciado do Problema
O agrupamento (clustering) carece de uma definição universalmente aceita de um "cluster", uma dificuldade formalizada pelo Teorema da Impossibilidade de Kleinberg (Kleinberg, 2002). Este teorema demonstra que nenhum método de agrupamento plano (que mapeia dissimilaridades para uma partição única) pode satisfazer simultaneamente três axiomas naturais: invariância de escala (independência das unidades de medida), riqueza (a capacidade de produzir qualquer partição possível dado um input apropriado) e consistência (a propriedade de que o fortalecimento das similaridades intra-cluster e o enfraquecimento das dissimilaridades inter-cluster não deve alterar a partição resultante). A tensão surge porque a consistência permite a criação de novas subestruturas dentro de um cluster, o que uma partição plana não consegue expressar sem violar o axioma.

Este artigo investiga se essa impossibilidade persiste quando o resultado é uma hierarquia (uma família aninhada de clusters) em vez de uma partição plana. Os autores questionam se análogos hierárquicos dos axiomas de Kleinberg podem ser satisfeitos conjuntamente.

Metodologia e Definições
Os autores definem um método de agrupamento hierárquico como um mapa $T$ de um conjunto de funções de dissimilaridade $D(X)$ para o conjunto de hierarquias $T(X)$ , onde uma hierarquia é uma família laminar de clusters contendo o conjunto completo $X$ e todos os singletons. Eles formulam quatro axiomas para o agrupamento hierárquico:

Invariância de Escala: $T(\beta d) = T(d)$ para qualquer fator de escala $\beta > 0$ .
Riqueza de Partição: Para toda partição $\mathcal{C}$ de $X$ , existe uma dissimilaridade $d$ tal que $\mathcal{C} \subseteq T(d)$ . (Nota: A hierarquia deve conter a partição como um subconjunto de seus clusters).
Consistência de Partição: Se uma partição $\mathcal{C}$ está contida em $T(d)$ , e $d'$ é um fortalecimento de $d$ em relação a $\mathcal{C}$ (as distâncias intra-cluster diminuem, as distâncias inter-cluster aumentam), então $\mathcal{C} \subseteq T(d')$ .
Invariância de Permutação: O resultado depende apenas da estrutura de dissimilaridade, não da rotulagem dos pontos.

Um método que satisfaz todos os quatro é denominado admissível. Os autores também consideram uma condição mais forte, a exatidão em ultramétricas, exigindo que, se o input for uma ultramétrica, o método recupere a hierarquia canônica associada a essa ultramétrica.

Principais Contribuições e Resultados

1. Alcançabilidade da Admissibilidade
Ao contrário do cenário de agrupamento plano, os autores provam que existem métodos hierárquicos admissíveis. De fato, existem inumeráveis tais métodos.

Construções Explícitas: O artigo constrói diversos métodos admissíveis:
- Single Linkage Não-Binário ( $T_{SL}$ ): Diferente do single linkage binário padrão, a variante não-binária (que funde todos os clusters empatados simultaneamente) é admissível.
- Métodos de Separação: Duas famílias de métodos, $T_{glob}^\eta$ e $T_{loc}^\eta$ , baseadas em margens de separação globais e locais. Estes definem clusters onde as dissimilaridades internas são suficientemente pequenas em comparação com as externas.
- Clusters Estáveis de Bryant-Berry ( $T_{stable}$ ): Um método baseado em critérios de estabilidade combinatória, juntamente com suas variantes de transformação de potência $T_{stable}^{(p)}$ .
Impossibilidade para Outros Tipos de Linkage: As variantes não-binárias de complete, average, Ward, centroid e median linkage mostram-se incapazes de satisfazer pelo menos um axioma.

2. Análise Estrutural de Métodos Admissíveis
O conjunto de métodos admissíveis, denotado por $H_{\alpha_{adm}}(X)$ , é analisado sob a ordem de refinamento ( $T_1 \sqsubseteq T_2$ se $T_1(d) \subseteq T_2(d)$ para todo $d$ ).

Diversidade: O conjunto forma um conjunto parcialmente ordenado (poset) com altura, largura e celularidade incontáveis.
Ausência de um Elemento Máximo: Não existe um único método admissível "mais fino" que refine todos os outros.
Incompatibilidade: Existem inumeráveis elementos máximos mutuamente incompatíveis (métodos que não podem ser refinados conjuntamente por qualquer outro método admissível). Especificamente, a família $\{T_{stable}^{(p)} : p > 0\}$ forma uma antichain ascendente forte.
Espinha Dorsal Comum: Apesar dessa diversidade, os axiomas impõem uma estrutura comum não trivial. Todo método admissível refina uma hierarquia de clusters suficientemente bem separados ( $T_{glob}^\eta$ para alguma sequência de margem $\eta$ ). Além disso, qualquer coleção finita de métodos admissíveis compartilha uma espinha dorsal comum.
Ausência de um Elemento Mínimo: O método trivial (retornando apenas singletons e a raiz) é o ínfimo no espaço de todos os métodos hierárquicos, mas não é admissível porque falha na riqueza de partição. Assim, a classe admissível não possui um elemento mínimo.

3. Admissibilidade Forte e Ultramétricas
Quando o axioma de exatidão em ultramétricas é adicionado, a classe torna-se fortemente admissível ( $H_{\alpha_{adm}^+}(X)$ ).

Esta classe permanece incontável e retém a diversidade de elementos máximos.
Crucialmente, ao contrário da classe admissível canônica, a classe fortemente admissível possui um elemento mínimo: $T_{glob}$ (o método com sequência de margem $\eta = \mathbf{1}$ ). Isso fornece um método mais grosseiro para a classe fortemente admissível.

4. Pré-processamento e Composição
O artigo estuda transformações de pré-processamento $\mu: D(X) \to D(X)$ aplicadas antes do agrupamento.

Condições de Preservação: Os autores derivam condições gerais sob as quais uma transformação preserva os axiomas (por exemplo, a escala comuta com $\mu$ , e o fortalecimento mapeia para um fortalecimento).
Exemplos:
- Minimax-path (Ultramétrica Subdominante): A transformação $B^*$ que mapeia uma dissimilaridade para sua ultramétrica subdominante preserva invariância de escala, invariância de permutação e exatidão ultramétrica. Isso leva à fatoração $T_{SL} = T_{glob} \circ B^*$ , mostrando que o single linkage é uma composição de uma transformação ultramétrica e um método de separação.
- PCA e HDBSCAN: O artigo analisa o pré-processamento de PCA e de alcance mútuo (mutual-reachability), mostrando que preservam a invariância de escala e de permutação, mas geralmente falham em preservar a riqueza ou a consistência.

Significância
O artigo demonstra que a impossibilidade fundamental de satisfazer os axiomas de Kleinberg é um artefato de restringir o resultado a partições planas. Ao mover para saídas hierárquicas, os axiomas tornam-se conjuntamente satisfatíveis, abrindo as portas para um vasto panorama de métodos admissíveis.

O trabalho revela que, embora o espaço de métodos admissíveis seja extremamente diverso (carecendo de uma solução única ótima), ele não é desestruturado. Os axiomas impõem uma espinha dorsal "conservadora" de clusters bem separados que todos os métodos admissíveis devem respeitar, enquanto permitem liberdade na resolução de estruturas mais finas. Isso fornece um arcabouço principiológico para compreender os compromissos (trade-offs) no agrupamento hierárquico e sugere que a escolha de um método específico dentro da classe admissível depende do equilíbrio desejado entre sensibilidade ao ruído e granularidade do resultado, em vez de uma violação de princípios axiomáticos fundamentais.

Os autores observam que este arcabouço conecta-se ao trabalho anterior de Carlsson e Mémoli (2010) e Ackerman e Ben-David (2016), mas difere por focar em hierarquias não ponderadas e manter a força total do axioma de consistência de Kleinberg, resultando em uma classe mais ampla e diversa, em vez de uma caracterização de um único algoritmo.

Mais como este