Como funciona o algoritmo Apriori

Nesta aula iremos explorar o algoritmo apriori, bastante interessante relacionado a mineração de dados utilizando regras de associação. Em primeiro lugar devemos compreender o contexto em que pensamos no funcionamento deste algoritmo. Atualmente com o crescimento do número de sistemas utilizados em pequenos negócios até grandes negócios propiciou o uso de softwares de gestão de estoque, vendas, logística ou até mesmo softwares integrados como os ERP’s.   

O grande problema desse crescimento é que os dados gerados tornaram-se um acumulado de dados “velhos”, ou seja, nada mais do que um arquivo morto. Após o fechamento do mês de uma empresa, ou até mesmo o balanço contábil no fim do ano os dados perdem sua utilidade no dia-a-dia. Isso passa ao gestor uma falsa impressão de que eles são descartáveis.  

A Inteligência Artificial com sua capacidade de tratar grandes massas de dados e extrair informações úteis trouxe utilidade ao banco de dados até então inútil. Quem melhor pode saber como seus clientes são do que o seu próprio banco de dados?   O algoritmo que estudaremos nesta aula busca analisar “transações” realizadas pelos clientes e descobrir relacionamentos que são impossíveis de um ser humano visualizar sem auxílio de uma máquina.   

Esse artigo faz parte de um grupo de conteúdos sobre ciência de dados. Quer ver mais sobre isso? clique aqui para ver.

Relacionamentos em toda parte

Todos os minutos estamos agindo e nos relacionando com alguém ou algo. Existem relacionamentos sociais, relacionamentos de trabalho, relacionamento entre objetos.   

Veja um exemplo muito simples, você conseguiria descobrir qual seria o item representado com a interrogação?

É claro que você consegue ver que existe uma relação entre os dois primeiros itens. É algo perfeitamente compreensivo para todos que já comeram um bom churrasco. Então, quem sabe, uma boa opção para satisfazer esta incógnita na “equação do churrasco” talvez seja completar dessa forma:

Certo, esse relacionamento foi fácil de prever. Porém imagine que você tem uma base de dados com 5 milhões de “cestas de compra”. Será que poderíamos inferir mais algum relacionamento entre produtos que passa despercebido aos olhos dos gestores? 
A resposta é sim! porém precisamos analisar estes dados e trazer com um certo nível de confiança que este relacionamento realmente existe. 

Considerando que um produto possui relação com o outro é possível definir estratégias de marketing para que um produto seja promovido pelo outro. Sendo assim, a forma de organizar os produtos em uma prateleira não é uma tarefa simplesmente aleatória.

Apriori

Considerando itens de um mercado e compras feitas por clientes é necessário definir uma forma de expressar a base de dados para que elas sejam passíveis de serem manipuladas. Imagine que em um mercado possuímos 5 ítens = {cebola, batata, hambúrguer, cerveja}, então para definir a compra dos clientes traçamos a seguinte tabela:

ID	Cebola	Batata	Hambúrguer	Leite	Cerveja
t1	1	1	1	0	0
t2	0	1	1	1	0
t3	0	0	0	1	1
t4	1	1	0	1	0
t5	1	1	1	0	1
t6	1	1	1	1	1

Dessa forma é possível observar que o número 1 ou 0 define se o item foi comprado ou não, respectivamente. 

Neste algoritmo, alguns termos são frequentemente usados e devemos entende-los para posteriormente podermos construí-lo em uma linguagem de programação.

3.1 – Suporte

Este número é a popularidade do item no conjunto de dados estudado (dataset). Sendo assim esse número é definido pela quantidade de vezes que o item apareceu em uma transação, dividido pela quantidade de transações existentes no dataset.

supp(x) = (numero de transações que X aparece) / (numero total de transações)

Por exemplo, calculando o numero do suporte para as cebolas.

supp(cebola) = 4/6 = 0.66667


Algo importante a ser citado neste momento é o support threshold. Este número irá expressar a quantidade mínima que o suporte de um item (ou conjunto de itens) deve aparecer para ele se tornar significante.

3.2 – Confiança

A confiança é um número que expressa a possibilidade de um item ser comprado quando outro item correlato é comprado. Por exemplo, qual a confiança que um cliente irá comprar um hambúrguer considerando que ele já comprou cebolas e batatas.    A confiança é calculada através da seguinte equação:

conf(X→Y) = supp(X U Y) / supp(X)

3.3 – Lift

Esta medida calcula também a possibilidade de um item ser comprado em relação a outro item. Porém, esta medida considera a popularidade de ambos os itens.

lift(X→Y) = supp(X U Y) / supp(X) * supp(Y)

Neste cálculo podemos analisar da seguinte forma: se o valor de lift(x→y) > 1 existe uma relação de compra entre estes dois itens. Já se o valor de lift(x→y) < 1 é muito provável que não exista uma relação clara expressa no dataset.

3.4 Convicção

Outra medida que pode ser calculada é a convicção:

conv (x → y) = 1 – supp(y) / 1 – conf(x → y)

Essa medida expressa a convicção pode ser interpretado como a razão da freqüência esperada que X ocorre sem Y (isto é, a freqüência que a regra faz uma predição incorreta) se X e Y fossem independentes divididos pela freqüência observada de predições incorretas.

4 – Criando um exemplo manual

Definimos o support threshold em 50%, ou seja, 0.5.

Passo 1: criar uma tabela que expressa a frequência de cada item.

item	Frequência nas transações
cebola	4
batata	5
hambúrguer	4
leite	4
cerveja	2

Passo 2: Considerando que o support threshold é de 50%, o mínimo de vezes que um item deve aparecer para ser considerado significante é a metade do número de transações (6/2 = 3). Portanto, o item “cerveja” será descartado.

item	Frequência nas transações
cebola	4
batata	5
hambúrguer	4
leite	4

Passo 3: Agora devemos realizar todas as combinações possíveis dentre os 3 itens analisados e criamos uma tabela contendo a combinação e quantas vezes essa combinação aparece nas transações. Lembrando que a ordem que os itens aparecem na combinação não importa, ou seja, {cebola + batata} = {batata + cebola}

item	Frequência nas transações
cebola + batata	4
cebola + hambúrguer	3
cebola + leite	2
batata + hambúrguer	4
batata + leite	3
hambúrguer + leite	2

Essencialmente estamos calculando as combinações possíveis entre 4 itens: 

n! / r!( n – r)!
4! / 2! (4 – 2)!  = 6 pares


Passo 4: novamente eliminamos os itens que não estão acima do threshold mínimo definido. 

item	Frequência nas transações
cebola + batata	4
cebola + hambúrguer	3
cebola + leite	2
batata + hambúrguer	4
batata + leite	3
hambúrguer + leite	2

Passo 5: O ultimo cálculo será semelhante aos anteriores, porém agora utilizando 3 itens em cada itemset. 

Item	Frequência de transações
Cebola + batata + Hambúrguer	3
Batata + hambúrguer + leite	2

Considerando o threshold mínimo de 50%, já podemos descartar o conjunto que possui support menor que 3. 

Se você quer ver uma versão animada desse algoritmo, veja o vídeo a seguir:

Implementação do algoritmo apriori em python

import pandas as pd

df = pd.read_csv('Market_Basket_Optimisation-tests.csv', header=None)
dataset = df.values
print (dataset)

# passo 1: definir o threshhold 

sThreshold = 0.1
numberOfTransactions = len(dataset)

# passo 2: definir uma tabela que expressa a frequência de cada item

# Primeiro criamos uma lista de todos os produtos disponíveis
listOfItems = []

for i in range(len(dataset)):
        for j in range(len(dataset[i])):
                if(dataset[i][j] not in listOfItems):
                    listOfItems.append(dataset[i][j])

# agora criamos contamos qual a frequência de cada item nas transações

singleItemFrequency = {}

for item in listOfItems:
    frequency = 0
    for i in range(len(dataset)):
        if(item in dataset[i]):
            frequency += 1
    singleItemFrequency[item] = frequency
    
print(singleItemFrequency)

# Aplicando a exclusão baseado no threshold

supportThreshold = len(dataset) * sThreshold
print("Support Threshold number: ", supportThreshold)

afterCleaning = {}


for key, value in singleItemFrequency.items():
    if(value > supportThreshold):
        afterCleaning[key]= value
        
print (afterCleaning)

# Agora fazendo o mesmo procedimento com grupos de 2 produtos

def is_in_array(item1, item2, tocheck):
    for i in range(len(tocheck)):
        if item1 in tocheck[i] and item2 in tocheck[i]:
            return True
    return False

itemFrequency = []

for item1 in listOfItems:
    for item2 in listOfItems:
        if(item1 == item2):
            continue
        frequency = 0
        isIn = is_in_array(item1, item2, itemFrequency)
        if (isIn):
            continue
        for i in range(len(dataset)):
            if(item1 and item2 in dataset[i]):
                frequency += 1
        itemFrequency.append([item1,item2,frequency])
    
print(itemFrequency)

twoItemsAfterCleaning = []


for i in range(len(itemFrequency)):
    if(itemFrequency[i][2] > supportThreshold):
        twoItemsAfterCleaning.append(itemFrequency[i])
print (twoItemsAfterCleaning)

for item in twoItemsAfterCleaning:
    value = singleItemFrequency[item[0]]
    if value <= 0:
        value = 1
    confiance = (item[2]/numberOfTransactions)/value
    print ("confiança de quem comprou ", item[0], " em comprar ", item[1], " = ", confiance)