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
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
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.
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|}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.
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.
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)}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
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çãoCopiado.Apriori algorithm. Wikipedia.
Abrir referência da publicaçãoCopiado.