Aula 01 - Apriori

1- Introdução

Nesta aula iremos explorar um algoritmo 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. 

2- 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.

3 - 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:

5 - Implementação do algoritmo 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)

Esse código está disponível no Github