Skip to content
Voltar aos resultados

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

Tamanho da fonte

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

1

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} \}
2

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_k
3

De 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}
4

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

  1. 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 DOI
    Copiado.
  2. Agrawal, R., & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th VLDB Conference, 487–499.

    Abrir referência da publicação
    Copiado.