Você está visualizando atualmente Como funciona o algoritmo Apriori

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?

Combinação possível de churrasco
Credits: Obrigado Jace Hentges pela fotografia. Licença: CC-BY-SA 3.0

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

Combinação de churrasco completa
Credits: Obrigado Jace Hentges pela fotografia. Licença: CC-BY-SA 3.0


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:

IDCebolaBatataHambúrguerLeiteCerveja
t111100
t201110
t300011
t411010
t511101
t611111


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.

itemFrequência nas
transações
cebola4
batata5
hambúrguer4
leite4
cerveja2



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.

itemFrequência nas
transações
cebola4
batata5
hambúrguer4
leite4


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}

itemFrequência nas
transações
cebola + batata4
cebola + hambúrguer3
cebola + leite2
batata + hambúrguer4
batata + leite3
hambúrguer + leite2



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. 

itemFrequência nas
transações
cebola + batata4
cebola + hambúrguer3
cebola + leite2
batata + hambúrguer4
batata + leite3
hambúrguer + leite2

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

ItemFrequência de
transações
Cebola + batata + Hambúrguer3
Batata + hambúrguer + leite2


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)

 

Vinicius dos Santos

Apenas um apaixonado por Ciência da Computação e a forma com que ela pode transformar vidas!

Este post tem 2 comentários

  1. Raul Magalhaes

    Boa noite Vinicius, consegui fazer uma melhoria no desempenho do seu código.

    Ao executa-lo em minha máquina, para um dataset com apenas 5 linhas, estava demorando cerca de 2 minutos, com a melhoria que fiz diminuiu para 3 segundos.

    A melhoria consiste apenas em limpar a lista listOfItems[], retirando os NaN (Not a Number) da seguinte forma:

    listOfItems = [x for x in listOfItems if pd.isnull(x) == False]

    1. Vinicius dos Santos

      Obrigado Raul!

      Se você quiser fazer essa contribuição via Github, fique a vontade!

      Pode abrir um pull request no repositório eu ficaria feliz em ter você como parceiro 🙂

Deixe um comentário

14 − um =