Mineração de Regras de Associação (Apriori)
- Proposto por
- Rakesh Agrawal & Ramakrishnan Srikant
- Ano
- 1994
- Tipo
- Unsupervised pattern discovery algorithm
- Família
- Pattern mining
Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês
O que ele faz?
Mineração de Regras de Associação é uma técnica de mineração de dados não supervisionada que descobre padrões de coocorrência entre itens em conjuntos de dados transacionais.
Formalmente introduzida por Agrawal, Imieliński e Swami em 1993, e refinada com o algoritmo seminal Apriori por Agrawal e Srikant em 1994, ela identifica regras da forma X ⇒ Y — significando que transações contendo o itemset X tendem a conter também o itemset Y — quantificadas por suporte, confiança e lift.
A intuição por trás do método
Imagine um registro de recibos de supermercado: se milhares de clientes que compram pão e manteiga também compram leite, esse padrão merece atenção. A Mineração de Regras de Associação funciona como um bibliotecário meticuloso vasculhando cada recibo, contando a frequência com que combinações de itens aparecem juntas e destacando as combinações que excedem uma frequência mínima. Uma vez encontradas as combinações frequentes, o algoritmo pergunta: dado que você já tem esses itens, com que confiabilidade isso prevê o próximo item? Essa lógica de duas passagens, frequência e depois confiança, é o cerne do Apriori.
História
O artigo fundamental de Agrawal, Imieliński e Swami (1993) definiu o problema de regras de associação no contexto de dados de transação de supermercado. O artigo de 1994 da VLDB de Agrawal e Srikant introduziu o algoritmo Apriori e sua estratégia eficiente de poda, tornando a mineração em larga escala prática. Trabalhos subsequentes produziram o FP-Growth (Han et al., 2000), que evita completamente a geração de candidatos, e o ECLAT, que minera em formato de dados vertical — estabelecendo uma rica família algorítmica agora central nos currículos de mineração de dados.
Quando usar
A Mineração de Regras de Associação é adequada para grandes conjuntos de dados transacionais onde o objetivo é descobrir padrões de coocorrência sem uma variável alvo predefinida. Assume que os itens são binários (presente/ausente) por transação. É apropriada para análise de cesta de compras, sistemas de recomendação, análise de fluxos de cliques na web e descoberta de co-diagnóstico médico. É inadequada para dados contínuos ou ordinais a menos que pré-discretizados, para conjuntos de dados com dimensionalidade muito alta (espaço candidato exponencial) ou quando se requer inferência causal em vez de associativa. Alternativas incluem FP-Growth para enumeração mais rápida de itemsets frequentes e mineração de sequências quando a ordem temporal importa.
Limitações e considerações
- Espaço candidato exponencial: a contagem de regras cresce combinatoriamente com o número de itens distintos.
- O framework suporte-confiança pode gerar regras enganosas quando as taxas base dos itens variam amplamente (ajuste de lift necessário).
- O modelo binário de transação requer discretização de variáveis contínuas, introduzindo perda de informação.
- Limiares de suporte mínimo altos perdem regras raras, mas valiosas; limiares baixos geram milhares de regras triviais.
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
- Totalmente não supervisionada: nenhum dado rotulado ou alvo predefinido necessário.
- Saída interpretável: regras são declarações se-então legíveis por humanos com suporte e confiança quantificados.
- Escalável via poda Apriori; a variante FP-Growth elimina completamente varreduras repetidas do banco de dados.
- Agnóstica ao domínio: aplicada em varejo, saúde, análise web e bioinformática.
Aplicações
- Varejo: posicionamento de produtos e recomendação de vendas cruzadas a partir de logs de transações de ponto de venda.
- Saúde: análise de coocorrência de diagnósticos, procedimentos ou medicamentos em registros eletrônicos de saúde.
- Análise web: descoberta de padrões de fluxo de cliques para recomendação de páginas e otimização de navegação.
- Bioinformática: identificação de conjuntos de genes coexpressos e motivos de interação proteica.
- Cibersegurança: detecção de eventos de rede correlacionados indicativos de padrões de intrusão.
Como funciona
Como funciona
O algoritmo escaneia o banco de dados de transações D para contar a frequência com que cada itemset X aparece. Um itemset é declarado frequente — e colocado em L_k — apenas quando seu suporte (a fração de transações que o contêm) atinge ou excede o limiar de suporte mínimo definido pelo usuário σ_min. O processo começa com itens individuais (k=1) e constrói iterativamente conjuntos candidatos maiores.
Fórmula
L_k = \{ X \subseteq I \mid |X| = k,\; \text{support}(X) = \frac{|\{t \in D : X \subseteq t\}|}{|D|} \geq \sigma_{\min} \}A propriedade anti-monotônica do suporte afirma que qualquer subconjunto de um itemset frequente deve ser ele próprio frequente. O Apriori explora isso podando cada candidato a k-itemset cujos (k-1)-subconjuntos não estejam todos no conjunto frequente verificado L_{k-1}. Isso reduz drasticamente o espaço de busca, evitando varreduras caras do banco de dados para itemsets que não podem ser frequentes.
Fórmula
\forall X \in C_k,\; \forall Y \subset X,\; |Y| = k-1 : Y \notin L_{k-1} \Rightarrow X \notin L_kDe cada itemset frequente X ∪ Y, o algoritmo gera regras X ⇒ Y onde X e Y são subconjuntos disjuntos. Uma regra é retida apenas quando sua confiança — a probabilidade condicional de Y dado X, calculada como suporte(X ∪ Y) / suporte(X) — atinge ou excede o limiar de confiança mínimo γ_min. Esta etapa converte a coocorrência bruta em declarações preditivas direcionais.
Fórmula
X \Rightarrow Y \text{ where } X \cap Y = \emptyset,\quad \text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)} \geq \gamma_{\min}Regras retidas são classificadas e filtradas por lift, que mede o quão mais provável é que Y apareça com X do que por acaso. Lift > 1 indica correlação positiva além da independência; lift = 1 indica independência; lift < 1 indica uma correlação negativa. Medidas adicionais de interesse, como convicção e alavancagem, podem refinar ainda mais o conjunto de regras para implantação prática.
Fórmula
\text{lift}(X \Rightarrow Y) = \frac{\text{confidence}(X \Rightarrow Y)}{\text{support}(Y)} = \frac{\text{support}(X \cup Y)}{\text{support}(X) \cdot \text{support}(Y)}Erros comuns
- Definir o suporte mínimo muito baixo inunda o analista com regras espúrias; a seleção do limiar requer conhecimento do domínio ou validação cruzada.
- Confundir associação estatística com causalidade: alto lift não implica que X causa Y.
- Ignorar a distribuição de frequência dos itens: itens comuns dominam as regras e ofuscam associações significativas de itens raros.
- Tratar a confiança isoladamente como métrica de qualidade; uma regra com alta confiança, mas baixo lift, pode não ter desempenho melhor que o acaso.
Perguntas frequentes
Qual a diferença entre suporte, confiança e lift?
Suporte mede a frequência com que um itemset aparece no conjunto de dados como um todo. Confiança mede a probabilidade condicional do consequente dado o antecedente. Lift normaliza a confiança pela frequência marginal do consequente, revelando se a coocorrência excede o que seria esperado sob independência. Todas as três métricas são necessárias juntas para uma avaliação robusta de regras.
Como o algoritmo Apriori reduz o custo computacional?
O Apriori explora a propriedade anti-monotônica: se um itemset é infrequente, todos os seus superconjuntos também devem ser infrequentes. Ao descartar qualquer candidato cujos subconjuntos não sejam todos verificados como frequentes, o algoritmo poda vastas porções do espaço de busca antes da contagem, reduzindo drasticamente o número de passagens pelo banco de dados necessárias em comparação com a enumeração por força bruta.
Quando devo usar FP-Growth em vez de Apriori?
FP-Growth é preferível quando o conjunto de dados é grande e o limiar de suporte mínimo é baixo, pois comprime o banco de dados de transações em uma estrutura compacta de árvore FP e minera padrões diretamente sem gerar candidatos explícitos. Isso elimina varreduras repetidas do banco de dados completo, tornando-o substancialmente mais rápido que o Apriori em conjuntos de dados densos com muitos itemsets frequentes.
Métodos relacionados
Fontes
Agrawal, R., Imieliński, T., & Swami, A. (1993). Mining association rules between sets of items in large databases. ACM SIGMOD, 207–216.
Abrir referência DOICopiado.Agrawal, R., & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th VLDB Conference, 487–499.
Abrir referência da publicaçãoCopiado.