Skip to content
Voltar aos resultados

Algoritmo Apriori

Proposto por
Agrawal, R. & Srikant, R.
Ano
1994
Tipo
Frequent itemset and association rule mining algorithm
Família
Machine learning

Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês

Tamanho da fonte

O que ele faz?

O algoritmo Apriori, introduzido por Agrawal e Srikant em 1994, é o método fundamental para descobrir conjuntos de itens frequentes e regras de associação em bancos de dados transacionais.

Ele utiliza uma busca de nível a nível, em largura, guiada pela propriedade anti-monotônica de suporte para enumerar eficientemente todas as combinações de itens que coocorrem acima de um limiar mínimo definido pelo usuário, e então extrai regras interpretáveis do tipo se-então a partir desses padrões.

A intuição por trás do método

Considere um banco de dados de recibos de supermercado. A percepção do Apriori é a propriedade anti-monotônica: se um par de produtos raramente é comprado junto, nenhum conjunto maior contendo esse par pode ser frequente. Isso permite que o algoritmo corte o espaço de busca exponencialmente grande de combinações possíveis de itens, construindo candidatos nível a nível — começando com itens individuais, depois pares, depois trios — e descartando qualquer candidato cujos subconjuntos já sejam conhecidos por serem infrequentes, antes mesmo de contá-los nos dados.

História

Negligenciar a remoção de regras não informativas (por exemplo, regras envolvendo itens universalmente comprados, como um cartão de fidelidade da loja).

Quando usar

Use o Apriori quando o objetivo for descobrir padrões de coocorrência ou relações do tipo se-então em dados transacionais ou de presença binária de itens — análise de cesta de compras, coendosso de itens em pesquisas, coocorrência de diagnósticos médicos ou associação de termos em textos. É adequado para conjuntos de dados de tamanho moderado onde a transparência e a interpretabilidade das regras de saída são uma prioridade. Não use o Apriori quando o banco de dados transacional for muito grande (milhões de linhas com catálogos de itens amplos), pois suas varreduras repetidas e completas do banco de dados o tornam lento em comparação com o FP-Growth; nesses casos, o FP-Growth é preferível. Também é inadequado para dados numéricos contínuos sem discretização prévia e não modela direcionalidade ou causalidade.

Limitações e considerações

  • Varreduras repetidas e completas do banco de dados o tornam lento em grandes conjuntos de dados — o FP-Growth é frequentemente preferido em escala.
  • A redução do limiar de suporte pode produzir um número exponencial de conjuntos de itens candidatos e regras, dificultando a interpretação.
  • Não captura ordem temporal, direcionalidade ou relações causais entre itens.
  • Os resultados são sensíveis à escolha dos limiares de suporte e confiança, que exigem conhecimento do domínio ou ajuste sistemático.

As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.

Pontos fortes

  • Gera regras do tipo se-então totalmente interpretáveis com suporte, confiança e lift quantificados.
  • A propriedade de poda anti-monotônica torna tratável uma busca que, de outra forma, seria exponencial.
  • Não requer rotulagem prévia dos dados; é inteiramente não supervisionado.
  • Parâmetros de limiar (suporte, confiança) dão ao analista controle direto sobre a granularidade das regras.
  • As regras de saída são acionáveis e podem ser comunicadas a partes interessadas não técnicas sem conhecimento algorítmico prévio.
  • Seminal, amplamente citado e implementado em praticamente todas as principais bibliotecas de mineração de dados.

Aplicações

  • Rakesh Agrawal e Ramakrishnan Srikant introduziram o algoritmo Apriori na VLDB 1994, baseando-se na formulação de Agrawal et al. de 1993 do problema de mineração de regras de associação. O nome reflete sua percepção chave: usar conhecimento prévio de conjuntos de (k) itens frequentes para podar candidatos no nível k+1. Tornou-se o benchmark canônico contra o qual todos os algoritmos subsequentes de conjuntos de itens frequentes — incluindo FP-Growth (2000) e Eclat — são medidos, e permanece um capítulo padrão em livros didáticos de mineração de dados e aprendizado de máquina.
  • Análise de cesta de compras: descobrir quais produtos são frequentemente comprados juntos para orientar o layout das prateleiras e promoções.
  • Informática médica: identificar sintomas, diagnósticos ou prescrições de medicamentos que ocorrem juntos em registros de pacientes.
  • Mineração de uso da web: encontrar quais páginas ou recursos os usuários tendem a visitar ou ativar juntos.
  • Análise de pesquisas e questionários: detectar quais itens ou respostas de escala são sistematicamente coendossados.
  • Inicialização de sistemas de recomendação: gerar associações de itens candidatos antes de implantar filtragem colaborativa.

Como funciona

Como funciona

1

O analista escolhe dois limiares antes de executar o algoritmo: suporte mínimo (a fração de transações que devem conter um determinado conjunto de itens para ser considerado frequente) e confiança mínima (a probabilidade condicional exigida para que uma regra se-então seja retida). Esses dois valores controlam o volume e a especificidade da saída e devem ser calibrados com base no conhecimento do domínio ou em execuções exploratórias.

2

O algoritmo faz uma varredura completa do banco de dados de transações para contar a frequência de cada item individual. Apenas os itens cujo suporte atende ou excede o limiar mínimo de suporte são mantidos; os demais são descartados. Esse conjunto de itens individuais frequentes forma o primeiro nível de candidatos.

Fórmula
\text{support}(X) = \frac{|\{t \in T : X \subseteq t\}|}{|T|}
3

Os conjuntos de itens frequentes encontrados no nível k são unidos em pares para formar conjuntos de itens candidatos de tamanho k+1. Apenas pares que compartilham os mesmos k-1 primeiros itens são unidos, uma regra que mantém o conjunto de candidatos compacto. Uma nova varredura do banco de dados conta o suporte de cada candidato.

4

Antes da contagem, cada candidato de tamanho k+1 é verificado contra todos os seus subconjuntos de tamanho (k). Se algum subconjunto não foi frequente no nível anterior, o candidato é podado imediatamente sem ler os dados, explorando a propriedade anti-monotônica para reduzir o cálculo. Os sobreviventes desta etapa de poda formam o próximo nível de conjuntos de itens frequentes.

5

A partir de cada conjunto de itens frequentes de tamanho dois ou mais, todas as regras possíveis do tipo se-então são geradas particionando os itens em um antecedente e um consequente. Cada regra é avaliada quanto à confiança — a proporção de transações com o antecedente que também contêm o consequente. Regras abaixo da confiança mínima são descartadas.

Fórmula
\text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)}
6

As regras sobreviventes são classificadas por lift, que compara a confiança observada com a frequência de base do consequente. Um lift acima de 1 sinaliza que o antecedente e o consequente coocorrem mais do que por acaso; lift próximo a 1 indica independência; lift abaixo de 1 indica uma associação negativa. As regras com o maior lift são as descobertas mais acionáveis.

Fórmula
\text{lift}(X \Rightarrow Y) = \frac{\text{confidence}(X \Rightarrow Y)}{\text{support}(Y)}

Erros comuns

  • Executar o Apriori diretamente no MethodMind — carregue seu conjunto de dados transacional, defina os limiares de suporte e confiança e receba regras de associação classificadas com suporte, confiança e lift, juntamente com uma visualização em rede das conexões de itens mais fortes.
  • Definir o suporte mínimo muito baixo e afogar-se em milhares de regras de baixa qualidade sem filtragem por lift.
  • Interpretar alta confiança como causalidade em vez de coocorrência — uma regra com alta confiança, mas lift próximo a 1, é trivial.
  • Aplicar o Apriori a recursos contínuos sem discretizá-los primeiro, o que infla o espaço de itens e degrada os resultados.
  • Relatar regras sem verificar se os tamanhos das amostras dos conjuntos de itens são grandes o suficiente para confiar nas estimativas de suporte.

Perguntas frequentes

Detecção de fraudes: identificar padrões de coocorrência incomuns em logs de transações que se desviam das cestas normais.

Qual é a diferença entre suporte, confiança e lift?

Suporte é a fração de todas as transações que contêm o conjunto de itens — mede a prevalência. Confiança é a probabilidade condicional de que o consequente apareça dado o antecedente — mede a confiabilidade da regra. Lift é a razão entre a confiança observada e a frequência de base do consequente; um lift acima de 1 mostra uma associação positiva genuína em vez de uma coincidência impulsionada pela popularidade do item.

Quando devo escolher FP-Growth em vez de Apriori?

O FP-Growth comprime o banco de dados em uma estrutura de árvore e o minera sem varreduras completas repetidas, tornando-o substancialmente mais rápido em grandes conjuntos de dados ou quando o suporte mínimo é baixo. O Apriori é mais fácil de entender e implementar e funciona bem em conjuntos de dados pequenos a moderados onde o tempo de execução não é um gargalo.

Como escolho o suporte e a confiança mínimos?

Não há regra universal. A prática comum é executar o algoritmo em vários níveis de suporte, plotar o número de conjuntos de itens frequentes contra o suporte e escolher um valor no cotovelo da curva. A confiança é então definida com base na pergunta de negócios ou pesquisa — maior confiança para regras críticas para a missão, menor para descoberta exploratória. Sempre valide as regras de topo contra a expertise do domínio.

O Apriori pode lidar com dados numéricos ou contínuos?

O Apriori requer dados binários de presença de itens. Variáveis contínuas devem ser discretizadas em intervalos (por exemplo, idade em baixo/médio/alto) antes de serem codificadas como itens. Uma discretização inadequada pode distorcer severamente as regras descobertas, portanto, a estratégia de agrupamento merece atenção cuidadosa.

O Apriori implica causalidade entre itens?

Métodos relacionados

Fontes

  1. Agrawal, R. & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th International Conference on Very Large Data Bases (VLDB), 487–499.

    Abrir referência da publicação
    Copiado.
  2. Apriori algorithm. Wikipedia.

    Abrir referência da publicação
    Copiado.