Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — FGV 2024

Agrupamento hierárquico vs K-means

Gabarito: letra D (2 – 1 – 1 – 2). O K-means exige a definição prévia do número de clusters (sensibilidade a K), enquanto o agrupamento hierárquico constrói dendrogramas a partir de abordagens top-down ou bottom-up. A sequência correta relaciona cada característica ao método correspondente.

A questão testa a distinção entre os dois principais tipos de algoritmos de agrupamento não supervisionado. Vamos analisar cada afirmativa:

( ) Seus resultados são altamente sensíveis ao número de clusters que deve ser pré-definido pelo usuário do algoritmo. Essa é uma característica do K-means (2). O algoritmo requer que o usuário informe o valor de K antes da execução, e o resultado final depende fortemente dessa escolha. No agrupamento hierárquico, o número de clusters não precisa ser definido a priori; o dendrograma permite escolher o corte após a construção.

( ) Baseia-se em abordagens top-down ou bottom-up, isto é, com a divisão ou com a união sucessiva de clusters. Refere-se ao agrupamento hierárquico (1). As abordagens podem ser aglomerativa (bottom-up: cada elemento começa como um cluster e os mais próximos são mesclados) ou divisiva (top-down: todos os elementos iniciam em um único cluster que é sucessivamente dividido).

( ) Seus resultados costumam ser graficamente visualizados por dendrogramas, que podem ser seccionados de acordo com o número de clusters determinado pelo usuário do algoritmo. Também é característica do agrupamento hierárquico (1). O dendrograma é uma árvore que mostra a hierarquia dos agrupamentos; o usuário pode “cortar” o dendrograma em um nível para obter o número desejado de clusters.

( ) Avalia distâncias entre as instâncias de dados e os centroides dos clusters e atualiza a posição dos centroides dos clusters sucessivamente, até a convergência. Descrição típica do K-means (2). O algoritmo atribui cada ponto ao centroide mais próximo, recalcula os centroides como a média dos pontos do cluster e repete até que os centroides não se movam significativamente.

Portanto, a sequência correta é 2 – 1 – 1 – 2, que corresponde à alternativa D.

Gabarito: letra D.