O algoritmo apriori

Análise de Cesta de Compras em R

Christopher Bruffaerts

Statistician

Mineração de regras de associação

Mineração de regras de associação permite descobrir relações interessantes entre itens em um grande banco de dados transacional.

Essa tarefa se divide em dois subtarefas:

Geração de itemsets frequentes: identificar todos os itemsets frequentes em um banco de transações potencialmente grande. Um itemset é frequente se atende a um limiar mínimo de suporte.
Geração de regras: a partir dos itemsets frequentes, gerar regras de associação com confiança acima de um limiar mínimo de confiança.

O algoritmo apriori é um clássico e rápido, pertencente à classe de algoritmos de mineração de regras de associação.

Ideia por trás do algoritmo apriori

O algoritmo apriori:

Abordagem bottom-up
Gera itemsets candidatos explorando o princípio apriori

Princípio apriori:

Se um itemset é frequente, todos os seus subconjuntos também devem ser frequentes.
- ex. se {A,B} é frequente, então {A} e {B} são frequentes
Para um itemset infrequente, todos os seus superconjuntos são infrequentes.
- ex. se {A} é infrequente, então {A,B}, {A,C} e {A,B,C} são infrequentes.

¹ Agrawal e Srikant (1994)

Exemplo: 1-itemset

conjunto_de_itens_lattice2

TID	Transação
1	{A, B, C, D}
2	{A, B, D}
3	{A, B}
4	{B, C, D}
5	{B, C}
6	{C, D}
7	{B, D}

¹ Limiar mínimo de suporte = 3/7 = 0,42

Exemplo: 2-itemsets

conjunto_de_itens_lattice3

TID	Transação
1	{A, B, C, D}
2	{A, B, D}
3	{A, B}
4	{B, C, D}
5	{B, C}
6	{C, D}
7	{B, D}

¹ Limiar mínimo de suporte = 3/7 = 0,42

Exemplo: 3-itemsets

todos_os_itemsets

TID	Transação
1	{A, B, C, D}
2	{A, B, D}
3	{A, B}
4	{B, C, D}
5	{B, C}
6	{C, D}
7	{B, D}

¹ Limiar mínimo de suporte = 3/7 = 0,42

Exemplo: itemsets frequentes

conjunto_de_itens_lattice3

Itemset	Contagem	Suporte
{A}	3	0.42
{B}	6	0.85
{C}	4	0.57
{D}	5	0.71
{A,B}	3	0.42
{B,C}	3	0.42
{B,D}	4	0.57
{C,D}	3	0.42

¹ Limiar mínimo de suporte = 3/7 = 0,42

Apriori: geração de regras

Após a etapa custosa de geração de itemsets frequentes, o apriori gera regras:

Comece com regras de alta confiança e antecedente único
- ex. {A,C} $\rightarrow$ {B}
Construa regras mais complexas, com mais itens no consequente
- ex. {A,C} $\rightarrow$ {B, D}

Truque: poda de regras de associação

ex.: se a regra {B,C,D} $\rightarrow$ {A} tem baixa confiança, todas as regras com o item A no consequente podem ser descartadas (como {B,D} $\rightarrow$ {A, C} ou {D} $\rightarrow$ {A,B, C}).

Primeira tentativa com o apriori

Dados transacionais

inspect(head(trans,2))

    items     transactionID
[1] {A,B,C,D} 1            
[2] {A,B,D}   2

Primeira chamada da função apriori — itemsets frequentes

support.all = apriori(trans, 
                      parameter = list(supp = 3/7, target="frequent itemsets"))

Saída do apriori — itemsets frequentes

Itemsets frequentes

inspect(support.all)

    items support   count
[1] {A}   0.4285714 3    
[2] {C}   0.5714286 4    
[3] {D}   0.7142857 5    
[4] {B}   0.8571429 6    
[5] {A,B} 0.4285714 3    
[6] {C,D} 0.4285714 3    
[7] {B,C} 0.4285714 3    
[8] {B,D} 0.5714286 4

conjunto_de_itens_lattice3

Extraindo regras com a função apriori

Parâmetro: os parâmetros de mineração alteram as características dos itemsets ou regras extraídos.

Suporte = 3/7
Confiança = 60%
Tamanho mínimo da regra = 2

Chamada da função apriori para gerar regras com argumentos específicos

rules.all = apriori(trans,
                parameter = list(supp=3/7, conf=0.6, minlen=2),
                control = list(verbose=F)
                   )

Extraindo regras: saída

Inspecionando as regras

inspect(rules.all)

    lhs    rhs support   confidence lift      count
[1] {A} => {B} 0.4285714 1.0000000  1.1666667 3    
[2] {C} => {D} 0.4285714 0.7500000  1.0500000 3    
[3] {D} => {C} 0.4285714 0.6000000  1.0500000 3    
[4] {C} => {B} 0.4285714 0.7500000  0.8750000 3    
[5] {D} => {B} 0.5714286 0.8000000  0.9333333 4    
[6] {B} => {D} 0.5714286 0.6666667  0.9333333 4

Vamos praticar!

Análise de Cesta de Compras em R