Questão de Algoritmos e Estrutura de Dados — Algoritmos — FGV 2024
Algoritmos e Estrutura de Dados›Algoritmos
Código
fg077301
Banca
FGV
Órgão
CVM
Ano
2024
Nível
Superior
Cargo
Analista - Perfil 7 - Ciência de Dados - Tarde
Uma certa organização busca melhorar a qualidade e agilidade do seu atendimento eletrônico. Para isso um projeto foi criado para agrupar os e-mails recebidos de acordo com o tipo de problema a ser resolvido e assim repassá-los para o setor mais apropriado.A equipe responsável pela implementação do projeto resolveu utilizar um modelo de linguagem recente para representar o máximo possível de informação contida num e-mail em um vetor de dimensão 768. Entretanto, depararam-se com o seguinte problema: as distâncias entre os vetores se mostraram muito pequenas, tornando o agrupamento por diversos algoritmos muito pouco significativo.Com esse último problema em mente, a sequência mais apropriada de algoritmos a ser aplicada sobre os vetores, de forma a obter um agrupamento significativo dos e-mails, é:
APCA → t-SNE → KNN;
BUMAP → KNN;
Ct-SNE → HDBSCAN → K-Means;
DUMAP → HDBSCAN;
EK-Means -> t-SNE.
Revelar gabarito e comentário▾
GabaritoD — UMAP → HDBSCAN;
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Algoritmos de redução de dimensionalidade e clusterização
Gabarito: letra D. O problema descrito é típico da maldição da dimensionalidade: em espaços de alta dimensionalidade (vetores de 768 dimensões), as distâncias entre pontos tendem a se tornar muito pequenas e pouco discriminativas. A solução mais adequada é primeiro aplicar uma técnica de redução de dimensionalidade que preserve a estrutura local dos dados (como UMAP) e, em seguida, utilizar um algoritmo de clusterização baseado em densidade (como HDBSCAN), que é robusto para formas arbitrárias de clusters e funciona bem com embeddings do UMAP. A sequência UMAP → HDBSCAN é uma pipeline consagrada para clusterização de dados de alta dimensão.
Etapa
Algoritmo
Função
Justificativa
1
UMAP
Redução de dimensionalidade
Preserva estrutura local e global, mitigando a maldição da dimensionalidade (vetores de 768 dimensões com distâncias pouco discriminativas).
2
HDBSCAN
Clusterização baseada em densidade
Agrupa e-mails sem necessidade de definir número de clusters, robusto a formas arbitrárias e adequado para embeddings gerados pelo UMAP.
1Vetores 768D (alta dimensão)
2UMAP (redução de dimensionalidade)
3HDBSCAN (clusterização densidade-based)
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
A sequência PCA → t-SNE → KNN aplica duas reduções de dimensionalidade (PCA seguido de t-SNE) e depois utiliza KNN, que é um algoritmo de classificação supervisionada, não de clusterização. O objetivo do problema é agrupar (clusterizar) e-mails, não classificá-los com base em rótulos prévios. Além disso, a combinação PCA + t-SNE é redundante e t-SNE não é recomendado como etapa anterior a outros algoritmos de clusterização.
Alternativa B — ❌ Incorreta
UMAP → KNN: UMAP reduz a dimensionalidade adequadamente, mas KNN (k-nearest neighbors) é um algoritmo de classificação ou regressão, não de clusterização. Para agrupar os e-mails sem rótulos, é necessário um algoritmo de clusterização (como HDBSCAN ou K-Means).
Alternativa C — ❌ Incorreta
t-SNE → HDBSCAN → K-Means: t-SNE é uma técnica de visualização que não preserva distâncias globais e é estocástica; usá-la como pré-processamento para clusterização pode introduzir artefatos. HDBSCAN já é um algoritmo de clusterização densidade-based, e aplicar K-Means em seguida é desnecessário e pode distorcer os clusters encontrados. A pipeline com duas clusterizações consecutivas não é uma prática recomendada.
Alternativa D — ✅ Correta ⟵ GABARITO
UMAP → HDBSCAN: UMAP (Uniform Manifold Approximation and Projection) é uma técnica de redução de dimensionalidade que preserva a estrutura local e global dos dados de forma eficiente, gerando embeddings de baixa dimensão onde as distâncias se tornam mais significativas. HDBSCAN é um algoritmo de clusterização baseado em densidade que não exige número pré-definido de clusters e lida bem com ruído. Essa combinação é amplamente utilizada em problemas reais de clusterização de dados de alta dimensionalidade.
Alternativa E — ❌ Incorreta
K-Means → t-SNE: A ordem está invertida. Primeiro aplicar K-Means diretamente sobre os vetores de alta dimensão (768) provavelmente produzirá clusters pouco significativos devido à maldição da dimensionalidade. Além disso, t-SNE após clusterização é usado apenas para visualização, não para auxiliar na clusterização em si.
PEGA ESSA DICA!
Em problemas de clusterização de dados de alta dimensão com distâncias homogeneamente pequenas, o padrão-ouro atual é: redução de dimensionalidade com UMAP (ou t-SNE apenas para visualização) seguida de HDBSCAN. Evite usar KNN (classificação) ou múltiplas clusterizações em sequência.