Uma Introdução ao Algoritmo Apriori

8 min readDec 11, 2019

1. Introdução

Entre quase todas as listas dos "Algoritmos que todo Data Scientist deve conhecer", o Apriori é um dos algoritmos que menos ouço falar, tanto em cursos quanto em canais de propagação de Data Science, motivo deste ser o primeiro algoritmo que apresento aqui no Medium.

Antes de começar, preciso contar um pouco mais sobre a abordagem de apresentação que farei aqui nesse texto. Primeiro eu vou apresentar a visão mais intuitiva do algoritmo, ou seja, qual o tipo de problema ele se dispõe a resolver e a lógica usada para tal. Depois apresentarei uma visão mais matemática, mostrando as "contas" por trás da coisa, e por fim, mostrarei um um exemplo aplicado em um dataset de amostra, utilizando Python.

Vamos Lá!

2. Visão Intuitiva do Apriori

2.1 Intuição de Regras de Associação

Para entender melhor o que o Apriori tenta resolver. Imagine que você está trabalhando como vendedor de um supermercado e deseja descobrir algum método para aumentar suas vendas, aumentando assim os lucros. Para isso você resolve tentar "induzir" seu cliente a comprar produtos que ele vá consumir ao mesmo tempo, colocando-os próximos nos mercados.

Com essa ideia em mente, você decide testar sua hipótese com os produtos do dia-a-dia dos brasileiros, o pão e a manteiga. Para fazer isso você move as prateleiras onde os pães ficam para próximo de onde a manteiga fica. Passado um tempo, você percebe que os clientes estão comprando mais pão e manteiga juntos.

Com o sucesso das vendas do pão e da manteiga, você decide explorar mais essa ideia de produtos que podem ser comprados juntos. No meio das suas pesquisas, descobre que fraldas e cervejas são produtos que saem bastante juntos. Sem entender muito bem o motivo disso, você rapidamente coloca a prateleira das fraldas perto da prateleira d cerveja, fazendo a ilação de que pais estressados com seus bebês tendem a comprar cerveja para relaxar, o que faz suas vendas dispararem.

Dizem que essa história aconteceu no Walmart e faz parte das lendas de Data Mining. Lenda ou não, ela é uma boa história pra contar para os parentes no final do ano e entender melhor o conceito de Regras de Associação (Association Rules).

2.2 Intuição do Algoritmo Apriori

Para dar uma visão intuitiva do que o Apriori faz, iremos trabalhar com a amostra de um conjunto de dados referente a transações em uma loja de conveniência fictícia. Cada linha da amostra contém uma transação identificada por um ID, onde se a coluna referente ao produto (Cerveja, Fralda, Chiclete, Refrigerante e Salgadinho) estiver marcada com 1 significa que esse produto foi comprado nessa transação, 0 caso o contrário:

Para ilustrar, veja transação do ID igual a 4. Nessa transação foram comprados os Itens cerveja, fralda, refrigerante e salgadinho.

Regras de Associação

Com isso entendido, podemos definir então o que seria uma Regra de Associação, que nada mais é que um método de explorar relações entre Itens em conjuntos de dados. Vamos definir os seguintes termos para Regra de Associação:

I (Itens): conjunto dos seus n atributos {i_1, i_2, …, i_n};
D (Database): conjunto das m transações {t_1, t_2, …, t_m};
Toda transação t_i, é única em D e consiste em um subconjunto dos Itens I;
Vamos Definir uma Regra de Associação como a relação (X => Y) , onde X e Y são subconjuntos de I. Eles não podem ter nenhum elemento em comum.
X é chamado de antecedente e Y da consequência da Regra.

Com isso definido, considere a transação de ID igual a 2, podemos ter a seguinte Regra de Associação: {Beer} => {Diaper}. Essa é a Regra de Associação que define que nessa transação, quem comprou Cerveja também comprou Fralda.

Nesse ponto, se você começar a montar as Regras de Associação na sua cabeça, perceberá que mesmo para um conjunto de dados pequeno, existem muitas Regras. O desafio agora é encontrar um modo de selecionar as regras relevantes. O modo utilizado para encontrar tais regras envolve o cálculo de medidas como Support, Confidence, Lift e Conviction.

Embora o Apriori use apenas o Support, falarei um pouco dessas quatro para maior entendimento do problema que estamos tentando resolver.

1. Support (Suporte)

A medida que indica a proporção de X em D.

Supp(X) = (#X in D) / (#D)

Ou seja, Supp({Beer}) = 4/9.

2. Confidence (Confiança)

A medida de Confidence é calculada em cima de uma Regra (X => Y). Ela expressa a proporção de "Se X for comprado, qual a chance de Y ser comprado?"

Conf(X=>Y) = Supp(X union Y) / Supp(X)

Ou seja, Conf({Beer}=>{Gum}) = (2/9)/(4/9) = 1/2.

Isso nos diz que 50% das vezes que Cerveja é comprada, então Chiclete é comprado.

3. Lift (Levantamento, Alavancagem , ou algo assim)

A medida de Lift indica qual a chance de Y ser comprado, se X for comprado, e considerando toda a popularidade de Y. Em outras palavras, veja qual informação nos trás mais conhecimento sobre a possibilidade de Itens serem comprados juntos: 1) Conf(X) é muito alta se ele aparece em todas as transações ou 2) Conf(X) é alta e ele aparece em poucas transações? Essa diferenciação é calculada pelo Lift.

Lift(X=>Y) = Supp(X union Y) / ( Supp(X) * Supp(Y) )

No caso da Regra ({Beer}=>{Gum}), Lift({Beer}=>{Gum}) = (2/9)/((4/9)*(2/9)) = 2/3.

Com base nesse valor conferirmos:

Se Lift(X=>Y) > 1, então o conjunto Y é provável de ser comprado quando X for comprado.
Se Lift(X=>Y) ≤1, então NÃO é provável que Y seja comprado, caso X seja comprado.

4. Conviction (Convicção)

A medida de Conviction está interessada em calcular a frequência que X ocorre e Y não ocorre, ou seja, ela está interessada em quando a Regra falha.

Conv(X=>Y) = (1 — Supp(Y)) / (1 — Conf(X=>Y))

Essa medida varia entre [0, inf]. Se Conf(X=>Y) for igual a 1, então o denominador da fórmula é zerado e o resultado do Convinction é definido como infinito. Já se o Supp(Y) for igual a 1, ou seja, Y é presente em todas as transações, então Conv é igual a 0 — Você não erra nunca.

Vamos para o Exemplo:

Para facilitar a escrita aqui no texto, considere X = {Soda, Snack} e Y = {Beer}.

Precisamos primeiro calcular Supp(Y) = 4/9. Depois calculamos a Conf(X=>Y) = 3/9.

*Repare que transformei 1 em 9/9 para facilitar as contas.

Conv(X=>Y) = ((9/9) — (4/9)) / ((9/9) — (3/9))

Conv(X=>Y) = (5/9) / (6/9)

Conv(X=>Y) = 5/6

Certifique-se que você compreendeu bem as medidas antes de ir para próxima seção!

3. Apriori

Com entendimento das Regras de Associação, e de como interpretá-las, chegou a hora de entender o Apriori e como ele nos ajuda nesse processo de Data Mining.

O Apriori trabalha com o conceito de Itens frequentes, que são os Itens do seu conjunto I que têm a pontuação do Support mais que um threshold (hiper-parâmetro). Ou Seja, precisamos calcular o Support de todas as combinações de Itens e extrair um subconjunto de Itens frequentes. Sabendo disso, os passos do Apriori são:

Dentro dos Itens I, extraia um subconjunto (I_freq) dos Itens que tem o seu Support maior que o threshold.
Dentro de I_freq, itere para formar as combinações dos I_freq com I, aplique o threshold e acumule em I_freq.
Pare quando ao aplicar o threshold nenhum item sobrar.

Por exemplo, considere o nosso conjunto de dados de amostra e threshold=0.4:

1. Vamos calcular o Support para grupos de 1 Item:

2. Agora removemos os Items com Support menor que o threshold, ou seja, sai o Chiclete (note que esse é o primeiro I_freq):

Items apenas com support maior que o threshold de 0.4

3. Depois disso, realizamos o mesmo cálculo pra os pares de Itens, como por exemplo (Diaper, Beer)

Cálculo do support para grupos de 2 Itens

4. Aplicando o threshold, sobra apenas (Diaper, Beer), que devemos acumular em I_freq:

Item na segunda rodada com Support maior que o threshold de 0.4

Veja o I_freq do momento:

Nesse momento você já deve ter lembrado das aulas de Análise Combinatória do ensino médio e percebido que estamos calculando combinações (ordem não importa).

5. Calculamos agora para 3 items:

Cálculo do Support para grupos de 3 Itens

6. Após aplicar o threshold, percebemos que nenhum Item sobrou, logo o algoritmo para, visto que esse é o critério de parada.

Pronto, encontramos as Regras de Associação mais frequentes. Olhando o resultado acima, você colocaria as Fraldas perto das Cerveja?

4. Implementação em Python

Pegue o código completo no meu GitHub: https://github.com/bcosta12/ml-demos/tree/master/201-apriori

Vamos criar a representação do nosso conjuntos de dados de amostra com o Pandas. Veja o código para a criação do DataFrame de exemplo:

2. Para calcular o Apriori, vamos utilizar o mlxend, que é uma lib que contém algumas ferramentas de Machine Learning que não existem no scikit-learn. Vamos criar uma classe, chamada Apriori, para fazer a interação com o apriori do mlxtend.

3. Usando a classe que acabamos de criar:

No código acima, primeiro instanciamos um objeto da classe Apriori que criamos e com esse objeto, nós executamos o método run, que executa o apriori no DataFrame do Pandas que é passado como parâmetro.

A segunda parte do código mostra como utilizamos o resultado do apriori para filtrar os Itens que têm o support maior que o threshold e o tamanho maior que length.

Depois de realizarmos esses processos, fica possível começar a pensar em como recomendar produtos baseado no histórico de transações, ou por exemplo, dar desconto para produtos que aparecem como Itens frequentes.

Gostaria da implementação sem o uso de libs? comente #apriorirootmode que, havendo bastante comentários, mostrarei essa implementação.

5. Conclusão

O objetivo desse artigo foi abrir o horizonte para problemas que envolvam dados, usando técnicas de Data Mining, com o entendimento do que o algoritmo faz, que é o mais importante para um Cientista de Dados.

Meu próximo passo, seguindo a linha desse artigo, será mostrar a implementação do Apriori no ambiente de nuvem da AWS, no blog que compartilho com uns amigos chamado Cloud Hero (Segue lá!). Acredito que como Cientistas de Dados, devemos conhecer o caminho completo, desde entender e implementar o algoritmo, até colocá-lo pra funcionar na vida real.

Que outros algoritmos ou técnicas você gostaria que eu escrevesse sobre? Gostou dessa abordagem? Comentem, compartilhem e me sigam!

Até a próxima!

Me Siga!

LinkedIn: https://www.linkedin.com/in/obernardocosta
Instagram: https://www.instagram.com/obernardo.costa