Questão de Algoritmos e Estrutura de Dados — Conceitos Básicos e Algoritmos — FGV 2024

Regras de Associação: Algoritmos e Conceitos

Gabarito: letra E. O Algoritmo Apriori é um método iterativo clássico para mineração de regras de associação, que gera conjuntos de itens frequentes por meio da propriedade anti-monotônica (se um conjunto é infrequente, todos os seus superconjuntos também são). As demais alternativas distorcem conceitos fundamentais, como suporte, frequência e o perfil do FP-Growth, que é eficiente para grandes bases.

A banca testa o conhecimento básico sobre algoritmos de associação (Apriori, FP-Growth) e métricas (suporte, confiança). O erro típico é confundir suporte com tamanho do conjunto ou achar que a frequência aumenta ao adicionar itens.

Alternativa A — ❌ Incorreta

Afirma que a frequência de um item não é pertinente. Pelo contrário, a mineração de regras de associação baseia-se na frequência dos itens: o suporte de um itemset é justamente a proporção de transações que o contêm. Sem frequência não há como calcular suporte nem gerar regras.

Alternativa B — ❌ Incorreta

O FP-Growth (Frequent Pattern Growth) foi projetado para ser eficiente em grandes bases de dados, construindo uma FP-Tree compacta e evitando a geração massiva de candidatos (que é o gargalo do Apriori). Portanto, a afirmação de que ele é "computacionalmente custoso" e "não apropriado para bases extensas" é contrária à sua característica principal.

Alternativa C — ❌ Incorreta

O suporte de um conjunto de itens mede a frequência (proporção de transações que contêm o itemset), e não o "tamanho do conjunto". A definição correta: $\text{Suporte}(X) = \frac{\text{transações com } X}{\text{total de transações}}$.

Alternativa D — ❌ Incorreta

Adicionar um novo item a um conjunto de itens cria um superconjunto. Como a frequência de um superconjunto nunca pode ser maior que a do subconjunto (princípio anti-monotônico), a afirmação de que a frequência poderá ser maior é falsa. Na verdade, ou permanece igual ou diminui.

Alternativa E — ✅ Correta ⟵ GABARITO

O Algoritmo Apriori é iterativo: a cada iteração gera candidatos de tamanho $k$ a partir dos frequentes de tamanho $k-1$, poda com base no suporte mínimo e repete até não haver mais candidatos. É o método mais conhecido para descoberta de regras de associação, conforme descrito na literatura de mineração de dados.

Gabarito: letra E.