Dizer que alguém que compra uma caixa de cereais para pequeno-almoço tem uma elevada probabilidade de comprar leite no mesmo ato de compra parece ser uma afirmação óbvia e lógica, visto que são dois produtos que aparentam ter uma elevada relação. Mas, e se existirem relações ocultas entre outros produtos nada semelhantes? A Walmart, uma multinacional norte-americana, descobriu algumas relações interessantes nas suas lojas, que não são nada óbvias:
- Homens jovens adultos compravam, no mesmo ato de compra, cervejas e fraldas de bebé, de forma regular [1];
- Antes de um furacão iniciar, era recorrente existirem diversos atos de compra com tartes de morango, para além de pilhas e outros itens essenciais [2];
- Clientes que comprassem bonecas Barbie teriam uma boa probabilidade de comprar um de três tipos de barras de chocolates disponíveis [3].
Descobrir estas relações permite mudar o layout de uma loja, colocando os produtos frequentemente associados mais perto uns dos outros. Estas relações permitem também gerir melhor o stock de uma loja e garantir que os produtos com prazo de validade são vendidos antes do fim do mesmo.
Por exemplo, uma loja da Walmart poderia ter em armazém algumas embalagens de chocolates (daquelas que são adquiridas juntamente com as bonecas Barbie) a chegar ao fim da validade. Sabendo antecipadamente que existe uma relação entre a compra de bonecas Barbie e três tipos de barras de chocolate, é possível montar uma campanha promocional onde na compra de uma boneca Barbie, existiria um desconto na aquisição de uma barra de chocolate.
É possível ainda reestruturar de que forma são vendidos os produtos. Por exemplo, as cadeias de fast-food descobriram muito cedo que quem compra fast-food tende a sentir sede devido ao sal que os alimentos contêm. Desta forma, as cadeias de fast-food começaram a criar menus que contêm comida e bebida [2].
Estas relações são também uma boa ferramenta para auxiliar o processo de compra de lojas online, tais como a Amazon. Ao adquirir um produto nas lojas online da Amazon, surge uma secção denominada por “Frequently Bought Together”, onde são apresentados conjuntos de produtos que são adquiridos em conjunto, construídos através de Regras de Associação [4].
Falar das relações entre produtos, é falar de Regras de Associação (Association Rule Mining). São estas Regras de Associação que compõem a Market Basket Analysis.
Algoritmos e Regras de Associação
Antes de proceder à explicação mais teórica sobre Market Basket Analysis, é necessário definir alguns conceitos-chave. O primeiro é o conceito de transação. Uma transação é um movimento de um ato de compra. Um basket é um ato de compra (é o “talão” final da compra) e é composto por uma ou mais transações. Um itemset é um conjunto de produtos que faz parte do basket (pode não ser composto por todos os produtos de um basket).
· Algoritmo Apriori
Na Market Basket Analysis, para o cálculo das Regras de Associação, pode ser utilizado um algoritmo denominado por Apriori. Este algoritmo trabalha assente no princípio “Tendo um conhecimento prévio dos diferentes itemsets, é possível gerar regras de associação fortes”. Este algoritmo encontra itemsets frequentes através de um processo denominado por “candidate itemset generation”. É um processo iterativo, onde k-itemsets são usados para explorar (k+1)-itemsets, onde k corresponde ao número de artigos do itemset [8].
Ou seja, em primeiro lugar, o algoritmo encontrará o conjunto de 1-itemsets frequente. De seguida, encontrará o conjunto de 2-itemsets frequente, e assim sucessivamente até não existirem mais k-itemsets frequentes.
O algoritmo Apriori apresenta algumas desvantagens, nomeadamente o facto de ser dispendioso a nível computacional e também a nível temporal, uma vez que necessita de iterar múltiplas vezes sobre o dataset para a geração de itemsets.
· Algoritmo FP-Growth
Para combater a desvantagem mencionada do algoritmo Apriori, foi criada uma versão melhorada do algoritmo, o algoritmo FP-Growth, onde “FP” significa “Frequent Pattern” [5].
Ao contrário do que acontece com a utilização do algortimo Apriori, o algoritmo FP-Growth apenas itera sobre o dataset duas vezes e utiliza uma estrutura em árvore (FP-Tree) para armazenar as informações. Cada nó da árvore representa um item e o número de baskets que são originados a partir desse nó. Cada ligação entre um nó representa um itemset.
Para uma melhor compreensão do funcionamento do algoritmo, cada fase será ilustrada a seguir. A tabela seguinte apresenta um possível dataset, em que cada linha representa um basket com os itens que o compõem.
Tabela 1 – Exemplo de um dataset transacional
Em primeiro lugar, o algoritmo vai iterar sobre o dataset e contar a frequência absoluta de cada item, ordenando os itens por ordem de frequência (support count). Caso a frequência seja a mesma e os mesmos sejam identificados por uma descrição textual, a ordenação é feita alfabeticamente. A tabela seguinte apresenta o output desta fase.
Tabela 2 – Support Count dos produtos contidos no dataset
De seguida, é construída uma árvore, iniciando pela raíz que não contém elementos (é nula). Vão sendo acrescentados itens por ordem decrescente de frequência e considerando também o conteúdo de cada basket. O árvore resultante dos dados considerados está representada abaixo.
Figura 1 – Árvore que relaciona os diferentes produtos dos baskets
O último passo do algoritmo é construir uma tabela de padrões condicionais e fazer a geração de padrões frequentes para cada item. A construção desta tabela é feita tendo em conta o support count por ordem crescente, ou seja, o primeiro item será o item G, o segundo item será o item D, e assim sucessivamente.
A primeira coluna, isto é, a base do padrão condicional de um dado item é obtida através da árvore anterior, descobrindo o caminho desde a raíz até ao item considerado, através das ligações entre nós. No caso do item D, os caminhos possíveis são C-A-D e C-A-F-D, sendo representados por {A, C:1} e por {A, C, F:1} respetivamente, onde o item D é contado uma vez em cada um dos caminhos.
A segunda coluna é a FP-Tree Condicional, onde se faz o somatório da contagem de cada item presente nos caminhos indicados. No caso do item D, a FP-Tree Condicional será obtida juntando <A:2>, <C:2> e <F:1>. No entanto, para serem obtidas regras de associação mais fortes, é possível definir um valor de minimum support count, escolhido pelo analista. Neste caso, esse valor será igual a 2. Desse modo, a FP-Tree Condicional para o item D será apenas <A:2, C:2>.
Para a terceira coluna, a geração dos padrões frequentes, fazem-se todas as combinações possíveis entre o item D e os restantes conjuntos. Neste caso, conjuga-se o item D com cada um dos restantes itens (ou seja, itens A e C) e depois obtém-se o conjunto final, onde se conjugam os três itens.
Tabela 3 – Tabela dos padrões condicionais do dataset.
Na tabela acima não estão apresentados os padrões frequentes do item G, uma vez que nenhum dos itens da FP-Tree Condicional cumpria com o requisito de ter uma contagem maior ou igual que o valor de minimum support count. É de salientar também que os itens que estão diretamente ligados à raíz da árvore, neste caso, não são considerados no processo de geração de padrões frequentes, uma vez que não existe qualquer nó intermediário entre a raíz e os nós que estão diretamente ligados à mesma.
Assim, os padrões frequentes encontrados para conjuntos de 2 itens são {A, D:2}, {C, D:2}, {A, F:2}, {C, F:2}, {B, E:2} e {A, C:3}. Para conjuntos de 3 itens são {A, C, D:2} e {A, C, F:2}.
É importante referir que os padrões frequentes gerados não necessitam de ser gerados a partir de um único item. Neste caso em específico, apenas foram consideradas gerações a partir de um item individualmente. No entanto, a tabela de padrões condicionais podia ser construída tendo em conta as combinações dos itens G e F, ou D e F, por exemplo, seguindo a estrutura da árvore.
Do exemplo anterior, para o item D (a título de exemplo), as regras obtidas são A → D, D → A, (A,C) → D, (A,D) → C e (C,D) → A.
A força destas regras é avaliada por algumas métricas que são explicadas na próxima secção.
· Métricas para avaliar as Regras de Associação
Para avaliar a força das regras de associação, existem algumas métricas. As três métricas mais utilizadas são support (diferente de support count), confidence e lift [6].
Uma regra de associação é estabelecida da seguinte forma:
Antecedente -> Consequente
Desta forma, sejam X e Y dois itens e seja X → Y a regra estabelecida entre os dois itens. As métricas, para a regra considerada, calculam-se da seguinte forma:
Onde frq (X,Y) representa o número de vezes que os itens X e Y aparecem em simultâneo num basket e onde N é o número total de baskets. No caso de freq (X) e freq (Y) , estes representam o número de vezes que o item X e o item Y aparecem num basket de forma individual, respetivamente. Tanto frq (X,Y) como freq (X) e freq (Y) são a representação dos padrões frequentes.
Nem todas as regras são realmente importantes ou significativas e portanto, para reduzir o tempo e o consumo dos recursos de computação, é necessário estabelecer alguns valores mínimos nas métricas de avaliação das regras. Geralmente, estes valores são definidos nos valores de support e de confidence. Contudo, não existe uma regra bem estabelecida para a escolha dos valores mínimos de support e confidence.
Se uma regra tiver um valor baixo de support, signfica que não existe informação suficiente sobre a relação entre os itens que constroem a regra. Relativamente à confidence, esta representa uma probabilidade condicional. Tipicamente, pretendem-se valores elevados de confidence. No entanto, estes valores não significam necessariamente uma regra de associação forte. Nesse sentido, existe a lift que, resumidamente, indica o quão significante e forte é uma determinada regra. A lift é o aumento na probabilidade de ter Y com o conhecimento de X estar presente (ou seja, o aumento da confidence) sobre a support de Y. Para que uma regra de associação seja considerada forte, é necessário também que exista um valor de lift muito maior do que 1. Um valor de lift menor do que 1 revela que o facto de ter X num basket não aumenta a hipótese de ocorrer Y, mesmo que essa regra tenha uma elevada confidence.
Caso Prático
De forma a demonstrar o uso desta técnica, foi desenvolvido um pequeno exemplo aplicando Market Basket Analysis com algoritmo FP-Growth num Workspace de Databricks. Para tal, utilizamos um dataset disponível em https://www.kaggle.com/psparks/instacart-market-basket-analysis?select=order_products__train.csv.
Existem já alguns packages de Python que contêm o algoritmo FP-Growth, assim como existem algumas abordagens descritas para implementar o algoritmo Apriori, através da escrita de código. No caso do algoritmo FP-Growth, este pode ser encontrado no package PySpark, no seguinte link: https://spark.apache.org/docs/2.3.0/ml-frequent-pattern-mining.html
Para iniciar, utilizando os ficheiros “order_products__train.csv” e “products.csv”, construiu-se uma Spark Dataframe no qual cada linha representa uma transação de um item de um basket, em que “order_id” é o identificador único de cada basket e “product_name” é o nome do produto que está dentro do basket. O código abaixo demonstra como é que os dois ficheiros foram conjugados [7]. A Figura 2 apresenta uma parte da tabela resultante.
from pyspark.sql import functions as F
from pyspark.ml.fpm import FPGrowth
productsDF = spark.read.csv(“products.csv”)
ordersDF = spark.read.csv(“order_products__train.csv”)
basketdata = ordersDF.join(productsDF, on=[“product_id”], how=”inner”).select(“order_id”, “product_name”)
Figura 2 – Parte da tabela resultante do processo referido, em que cada linha é uma transação do basket identificado na coluna “order_id”.
O objetivo é considerar apenas uma lista de produtos únicos em cada basket. Por esse motivo, removeram-se todas as linhas duplicadas da tabela, transformando-a de forma a que exista uma coluna com o identificador único de um basket e outra coluna com uma lista composta por todos os produtos únicos que pertecem a esse mesmo basket, sendo que cada linha passa a representar um basket. O código que executa o processo descrito é apresentado em baixo [7]. A Figura 3 apresenta a nova tabela resultante do processo.
basketdata = basketdata.dropDuplicates ([“order_id”, “product_name”]).sort (“order_id”)
basketdata = basketdata.groupBy(“order_id”).agg(F.collect_list(“product_name”)).sort(“order_id”)
Figura 3 – Parte da tabela resultante do processo referido, em que cada linha representa um basket composto pela lista de produtos da coluna “collect_list(product_name)”
De seguida, são definidos os valores de support e confidence mínimos, para fazer uma primeira distinção entre as regras que são potencialmente relevantes e entre as regras que não terão qualquer interesse. O valor de support mínimo é muito dependente dos dados disponíveis, não existindo um critério exato de como escolher. Os valores mínimos escolhidos neste caso foram support mínimo, 0.005 e confidence mínima, 0.1.
# support and confidence minimum values choice and fit model
fpGrowth = FPGrowth(itemsCol= “collect_list(product_name)“, minSupport=0.005, minConfidence=0.1)
model = fpGrowth.fit(basketdata)
# most frequent itemsets display
model.freqItemsets.display()
items = model.freqItemsets
# generated association rules display
model.associationRules.display()
rules = model.associationRules
As 7 regras mais fortes, tendo em conta a métrica lift, foram as seguintes:
Figure 5 – As 7 regras geradas com maior valor de lift
Em qualquer uma das regras, é possível verificar que as associações são feitas entre produtos que são frescos e orgânicos. Na maioria dos casos, existe a associação entre frutas ou entre alho e cebola. No entanto, a regras das linhas 3 e 4 fogem deste padrão, representando uma associação entre Coentros e Limas (Coentros → Limas); e Limas e Coentros (Limas → Coentros).
É possível verificar que a métrica confidence não apresenta valores muito elevados para os exemplos apresentados. No entanto, os valores de lift são suficientemente maiores do que 1 para considerar que estas regras são fortes. Um dos factores que pode ter conduzido a uma baixa confidence (e também um baixo valor de support) pode estar relacionado com o facto de existir uma grande variedade de produtos ao longo do dataset. De um modo geral, os produtos estão organizados por uma hierarquia com diversos níveis de especificidade. Quanto maior a especificidade, mais produtos existem nesse nível. Para contornar a elevada variedade de produtos o que muitos analistas tendem a fazer é aplicar a Market Basket Analysis utilizando níveis com uma especificidade menor, diminuindo assim a variedade.
Conclusão
A Market Basket Analysis é uma técnica de Associate Rule Mining em grande uso por diversas empresas interessadas em encontrar relações entre os diversos produtos que têm em loja. Este tipo de análise procura, através de dados transacionais, verificar quais os padrões mais frequentes, isto é, descobrir que tipos de produtos são mais frequentemente associados no mesmo ato de compra.
Este tipo de análise tem várias aplicações como a gestão de lojas e de stock para ajudar no desenvolvimento de campanhas promocionais. Assim, é possível maximizar as vendas e fazer retenção de clientes.
Inicialmente, era uma técnica realizada com um algoritmo denominado por Apriori. Posteriormente, pelas limitações que o algoritmo apresenta quanto aos tempo e recursos de computação, foi desenvolvido um novo algoritmo que procurasse resolver estas questões, o algoritmo FP-Growth.
A Market Basket Analysis pode ser implementada em Python seja através da escrita do algoritmo em código seja através da utilização de packages, como é o caso do FP-Growth, que pode ser implementado recorrendo a PySpark numa arquitetura de Big Data.
Referências
[1] https://medium.com/@kroneii/visualizing-diaper-beer-relationship-in-graph-database-e2790819ad13
[2] https://medium.com/analytics-vidhya/association-rule-mining-7f06401f0601
[3] Berry, M. J. A. and Linoff, G. S. (2004). Data Mining Techniques For Marketing, Sales, and Customer Relationship Management (2nd ed.). Wiley Publishing, Inc.
[5] https://www.mygreatlearning.com/blog/understanding-fp-growth-algorithm/
[6] https://towardsdatascience.com/association-rules-2-aa9a77241654
[7] https://towardsdatascience.com/market-basket-analysis-using-pysparks-fpgrowth-55c37ebd95c0
[8] https://towardsdatascience.com/complete-guide-to-association-rules-2-2-c92072b56c84
