Uma Introdução ao Algoritmo Apriori
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/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):
3. Depois disso, realizamos o mesmo cálculo pra os pares de Itens, como por exemplo (Diaper, Beer)
4. Aplicando o threshold, sobra apenas (Diaper, Beer), que devemos acumular em I_freq:
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:
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
Referências
- https://github.com/bcosta12/ml-demos/tree/master/201-apriori
- Learning Data Mining with Python — Second Edition (LINK)
- https://www.hackerearth.com/blog/developers/beginners-tutorial-apriori-algorithm-data-mining-r-implementation/
- https://www.kdnuggets.com/2016/04/association-rules-apriori-algorithm-tutorial.html
- https://www.geeksforgeeks.org/implementing-apriori-algorithm-in-python/
- https://www.forbes.com/forbes/1998/0406/6107128a.html#24b642016260
- www.inf.ufsc.br › ~luis.alvares › INE5644 › RegrasDeAssociacao
- https://en.wikipedia.org/wiki/Apriori_algorithm
- https://en.wikipedia.org/wiki/Association_rule_learning
- http://rasbt.github.io/mlxtend/user_guide/frequent_patterns/association_rules/