Algoritmo apriori

O Apriori^[1] é um algoritmo para mineração de conjuntos de itens frequentes e aprendizado de regras de associação em bancos de dados relacionais. Ele prossegue identificando os itens individuais frequentes no banco de dados e estendendo-os a conjuntos de itens cada vez maiores, desde que esses conjuntos de itens apareçam com frequência suficiente no banco de dados. Os conjuntos de itens frequentes determinados por Apriori podem ser usados para determinar regras de associação que destacam tendências gerais no banco de dados: isso tem aplicações em domínios como análise de cesta de compras.

Visão geral

O algoritmo Apriori foi proposto por Agrawal e Srikant em 1994. O Apriori é projetado para operar em bancos de dados contendo transações (por exemplo, coleções de itens comprados por clientes, ou detalhes de uma frequência de site ou endereços IP^[2]). Outros algoritmos são projetados para encontrar regras de associação em dados sem transações (Winepi e Minepi) ou sem indicação de data/hora (sequenciamento de DNA). Cada transação é vista como um conjunto de itens. Dado um limiar ${\displaystyle C}$, o algoritmo a priori identifica os conjuntos de itens que são subconjuntos de pelo menos ${\displaystyle C}$ transações no banco de dados.

O Apriori usa uma abordagem "ascendente", em que subconjuntos frequentes são estendidos um item por vez (uma etapa conhecida como geração de candidatos) e grupos de candidatos são testados em relação aos dados. O algoritmo termina quando nenhuma outra extensão bem-sucedida é encontrada.

O Apriori usa busca em largura e uma estrutura de árvore de Hash para contar eficientemente os conjuntos de itens candidatos. Ele gera conjuntos de itens candidatos de comprimento ${\displaystyle k}$ partindo de conjuntos de itens de comprimento ${\displaystyle k-1}$ . Em seguida, ele poda os candidatos que têm um subpadrão infrequente. De acordo com o lema do fechamento para baixo, o conjunto candidato contém todos os conjuntos de itens de comprimento ${\displaystyle k}$. Depois disso, ele examina o banco de dados de transações para determinar conjuntos de itens frequentes entre os candidatos.

O pseudocódigo para o algoritmo é fornecido abaixo para um banco de dados de transações ${\displaystyle T}$, e um limiar de suporte ${\displaystyle \varepsilon }$. A notação usual da teoria de conjuntos é empregada, mas observe que ${\displaystyle T}$ é um multiconjunto. O conjunto de candidatos para o nível ${\displaystyle k}$ é ${\displaystyle C_{k}}$. Em cada etapa, supõe-se que o algoritmo gere os conjuntos de candidatos a partir dos grandes conjuntos de itens do nível anterior, atendendo ao lema do fechamento descendente. O código ${\displaystyle \mathrm {count} [c]}$ acessa um campo da estrutura de dados que representa o conjunto de candidatos ${\displaystyle c}$, que inicialmente é assumido como zero. Muitos detalhes são omitidos abaixo, geralmente a parte mais importante da implementação é a estrutura de dados usada para armazenar os conjuntos de candidatos e contar suas frequências.

Apriori (T, ε)
  L 1 ← {1 grande - conjuntos de itens}
  k ← 2
  enquanto Lk−1 não é vazio
    Ck ← Apriori_gen (Lk−1, k)
    para transações t em T
      Dt ← {c em Ck : c ⊆ t}
      para candidatos c em Dt
        contagem[c] ← contagem[c] + 1

    Lk ← {c em Ck: contagem [c] ≥ ε}
    k ← k + 1

  retornar União(Lk)
  
Apriori_gen (L, k)
   resultado ← lista()
   para todo p ⊆ L, q ⊆ L onde p1 = q1, p2 = q2, ..., pk-2 = qk-2 e pk-1 < qk-1
     c = p ∪ {qk-1}
     se u ⊆ c para todo u em L
       resultado.adicionar(c)
   retornar resultado

Exemplos

Exemplo 1

Considere o seguinte banco de dados, em que cada linha é uma transação e cada célula é um item individual da transação:

As regras de associação que podem ser determinadas a partir deste banco de dados são as seguintes:

1. 100% dos conjuntos com alfa também contêm beta
2. 50% dos conjuntos com alfa, beta também têm épsilon
3. 50% dos conjuntos com alfa, beta também têm teta

também podemos ilustrar isso por meio de uma variedade de exemplos.

Exemplo 2

Suponha que um grande supermercado monitore os dados de vendas por unidade de manutenção de estoque (SKU) para cada item: cada item, como "manteiga" ou "pão", é identificado por um SKU numérico. O supermercado possui um banco de dados de transações em que cada transação é um conjunto de SKUs que foram comprados juntos.

Assuma que o banco de dados de transações consista nos seguintes conjuntos de itens:

Usaremos o Apriori para determinar os conjuntos de itens frequentes deste banco de dados. Para isso, consideraremos que um conjunto de itens é frequente se aparecer em pelo menos 3 transações do banco de dados: o valor 3 é o limiar de suporte.

A primeira etapa do Apriori é contar o número de ocorrências, chamado de suporte, de cada item do membro separadamente. Ao escanear o banco de dados pela primeira vez, obtemos o seguinte resultado

Todos os conjuntos de itens de tamanho 1 têm um suporte de pelo menos 3, portanto, são todos frequentes.

A próxima etapa é gerar uma lista de todos os pares de itens frequentes.

Por exemplo, em relação ao par {1,2}: a primeira tabela do Exemplo 2 mostra os itens 1 e 2 aparecendo juntos em três dos conjuntos de itens; portanto, dizemos que o suporte do item {1,2} é três.

Cada um dos pares {1,2}, {2,3}, {2,4} e {3,4} atendem ou excedem o suporte mínimo de 3, e por isso são frequentes. Os pares {1,3} e {1,4} não são. Agora, como {1,3} e {1,4} não são frequentes, qualquer conjunto maior que contenha {1,3} ou {1,4} não pode ser frequente. Dessa forma, podemos podar conjuntos: agora procuraremos trios frequentes no banco de dados, mas já podemos excluir todos os trios que contêm um desses dois pares:

No exemplo, não há trios frequentes. O conjunto {2,3,4} está abaixo do limiar mínimo e os outros trios foram excluídos porque eram superconjuntos de pares que já estavam abaixo do limiar.

Assim, determinamos os conjuntos frequentes de itens no banco de dados e ilustramos como alguns itens não foram contados porque um de seus subconjuntos já estava abaixo do limiar.

Limitações

O Apriori, embora historicamente significativo, sofre de uma série de ineficiências ou trade-offs, que geraram outros algoritmos. A geração de candidatos gera um grande número de subconjuntos (o algoritmo tenta carregar o conjunto de candidatos, com o maior número possível de subconjuntos antes de cada varredura do banco de dados). A exploração de subconjuntos de baixo para cima (essencialmente uma travessia em largura do reticulado de subconjuntos) encontra qualquer subconjunto maximal S somente depois de todos os seus ${\displaystyle 2^{|S|}-1}$ subconjuntos próprios.

O algoritmo varre o banco de dados muitas vezes, o que reduz o desempenho geral. Devido a isso, o algoritmo assume que o banco de dados esteja permanentemente em memória.

Além disso, tanto a complexidade em tempo e quanto em espaço deste algoritmo são muito altas: ${\displaystyle O\left(2^{|D|}\right)}$, portanto exponencial, em que ${\displaystyle |D|}$ é a largura horizontal (o número total de itens) presente no banco de dados.

Algoritmos posteriores, como Max-Miner^[3] tentam identificar os conjuntos de itens frequentes máximos sem enumerar seus subconjuntos, e executam "saltos" no espaço de pesquisa em vez de uma abordagem puramente ascendente.

Referências

Ligações externas

• ARtool, aplicativo Java com GUI de mineração de regras de associação sob a GPL, oferecendo implementações de vários algoritmos para descoberta de padrões frequentes e extração de regras de associação (incluindo Apriori)
• O SPMF oferece implementações de código aberto em Java de Apriori e diversas variações, como AprioriClose, UApriori, AprioriInverse, AprioriRare, MSApriori, AprioriTID e outros algoritmos mais eficientes, como FPGrowth e LCM.
• Christian Borgelt fornece implementações em C para o Apriori e muitos outros algoritmos de mineração de padrões frequentes (Eclat, FPGrowth, etc.) O código é distribuído como software livre sob a licença do MIT.
• O pacote arules em R contém Apriori e Eclat e infraestrutura para representar, manipular e analisar dados de transação e padrões.
• Efficient-Apriori é um pacote em Python com uma implementação do algoritmo conforme apresentado no artigo original.