Aprenda Processamento de Fluxos de Dados Transacionais com o Algoritmo Apriori | Fundamentos de Regras de Associação e Análise Transacional

Deslize para mostrar o menu

O algoritmo Apriori é uma ferramenta fundamental para identificar conjuntos frequentes de itens em dados transacionais, sendo essencial para a análise de cesta de mercado. No centro do Apriori está o Princípio de Apriori, também conhecido como propriedade de fechamento descendente.

Definição

Princípio de Apriori - Se um conjunto de itens é frequente, então todos os seus subconjuntos também devem ser frequentes.

Esse conceito reduz drasticamente o número de conjuntos de itens que precisam ser avaliados, pois qualquer conjunto que contenha um subconjunto infrequente pode ser imediatamente descartado da análise.

A geração de candidatos é a fase de combinação do algoritmo. Em cada rodada, o algoritmo observa os conjuntos frequentes vencedores da rodada anterior e os combina para formar novos grupos maiores chamados de candidatos. Para fazer isso de forma eficiente, o algoritmo apenas une conjuntos de itens que são quase idênticos, compartilhando todos os itens, exceto o último.

Como funciona: Se o algoritmo descobre que {Bread, Milk} e {Bread, Diapers} são ambos bastante populares individualmente, ele os combina para criar um novo candidato de três itens para a próxima rodada: {Bread, Milk, Diapers}.

Imediatamente após gerar novos candidatos, o algoritmo inicia a fase de Poda para eliminar combinações desnecessárias antes de executar cálculos pesados no banco de dados. Essa etapa depende inteiramente do Princípio de Apriori, que afirma que um conjunto grande de itens só pode ser frequente se todas as suas partes menores também forem frequentes. Durante a poda, o algoritmo examina cuidadosamente cada novo candidato e analisa seus subconjuntos menores. Se ao menos um subconjunto não foi aprovado na rodada anterior, todo o candidato é imediatamente descartado.

Como funciona: Imagine que o candidato {Bread, Milk, Eggs} foi gerado. O algoritmo verifica seus subcomponentes: {Bread, Milk}, {Bread, Eggs} e {Milk, Eggs}. Se seus registros históricos de transações mostram que {Milk, Eggs} é uma combinação rara que falhou em uma rodada anterior, o algoritmo elimina completamente {Bread, Milk, Eggs}. Isso evita o desperdício de recursos computacionais em uma combinação que está matematicamente garantida a falhar.

Depois que a lista de candidatos é reduzida aos concorrentes mais viáveis, o algoritmo passa para a Identificação de Conjuntos Frequentes de Itens. O sistema examina os bancos de dados de transações brutas para contar exatamente quantas vezes esses grupos candidatos restantes aparecem juntos em compras reais. A contagem total de cada candidato é convertida em uma porcentagem. Se essa pontuação atingir ou exceder o seu Limite Mínimo de Suporte pré-determinado, o candidato é oficialmente reconhecido como um Conjunto Frequente de Itens.

Definição

Limite Mínimo de Suporte é um valor definido pelo usuário que determina a menor frequência que um conjunto de itens deve ter para ser considerado significativo no algoritmo Apriori. Ao definir esse limite, você filtra os conjuntos de itens que aparecem com pouca frequência no conjunto de dados. Escolher um limite alto resultará em menos conjuntos de itens, mais comuns, podendo perder combinações interessantes, porém raras. Definir um valor muito baixo pode gerar muitos conjuntos de itens, incluindo aqueles de pouco valor prático. O limite selecionado impacta diretamente a profundidade e o foco da análise, devendo refletir os objetivos e a escala da exploração dos dados.

Esse ciclo de três etapas se repete consecutivamente. Ele avança de itens únicos para pares, depois para grupos de três, e continua expandindo até executar uma rodada em que nenhum novo conjunto frequente de itens possa ser encontrado, mapeando com sucesso toda a rede de comportamento de compra dos consumidores.

Para tornar essas ideias mais concretas, considere um Exemplo usando um pequeno conjunto de dados. Suponha que você tenha as seguintes transações:

Transaction 1: {Milk, Bread};
Transaction 2: {Milk, Diaper, Beer, Bread};
Transaction 3: {Milk, Diaper, Beer, Cola};
Transaction 4: {Diaper, Beer};
Transaction 5: {Milk, Diaper, Bread, Beer}.

O algoritmo primeiro identificaria todos os itens únicos que aparecem com frequência, depois geraria pares candidatos a partir desses, eliminaria aqueles que contêm itens pouco frequentes e continuaria esse processo para descobrir grupos frequentes maiores, como {Milk, Diaper, Beer}.


              1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
            
import pandas as pd
from itertools import combinations

# Example transaction dataset
transactions = [
    ['Milk', 'Bread'],
    ['Milk', 'Diaper', 'Beer', 'Bread'],
    ['Milk', 'Diaper', 'Beer', 'Cola'],
    ['Diaper', 'Beer'],
    ['Milk', 'Diaper', 'Bread', 'Beer']
]

# Convert transactions to a DataFrame of one-hot encoded items
all_items = sorted(set(item for transaction in transactions for item in transaction))
df = pd.DataFrame([{item: (item in transaction) for item in all_items} for transaction in transactions])

def apriori(df, min_support=0.6):

    def get_support(itemset):
        return (df[list(itemset)].all(axis=1).sum()) / len(df)

    # Step 1: Finding frequent 1-itemsets
    frequent_itemsets = []
    current_level = []
    for item in all_items:
        support = get_support([item])
        if support >= min_support:
            current_level.append(frozenset([item]))
            frequent_itemsets.append((frozenset([item]), support))

    k = 2
    while current_level:
        # Step 2: Candidate generation
        candidates = []
        level_list = list(current_level)
        for i in range(len(level_list)):
            for j in range(i+1, len(level_list)):
                union = level_list[i] | level_list[j]
                if len(union) == k and union not in candidates:
                    # Step 3: Pruning
                    subsets = list(combinations(union, k-1))
                    if all(frozenset(subset) in current_level for subset in subsets):
                        candidates.append(union)

        # Step 4: Support counting
        next_level = []
        for candidate in candidates:
            support = get_support(candidate)
            if support >= min_support:
                next_level.append(candidate)
                frequent_itemsets.append((candidate, support))

        current_level = next_level
        k += 1

    # Format output
    return [(set(itemset), round(support, 2)) for itemset, support in frequent_itemsets]

# Running Apriori and displaying frequent itemsets
frequent_itemsets = apriori(df, min_support=0.6)
for itemset, support in frequent_itemsets:
    print(f"Frequent Itemset: {itemset}, Support: {support}")

Este código Python demonstra uma implementação simples do algoritmo Apriori para identificar conjuntos frequentes de itens em dados transacionais. Veja como cada etapa é realizada:

Preparação dos Dados

As transações são representadas como uma lista de listas, onde cada sublista contém itens comprados juntos.
Todos os itens únicos são identificados e ordenados.
Um DataFrame codificado em one-hot é criado: cada linha representa uma transação e cada coluna corresponde a um item, com True ou False indicando presença ou ausência.

Etapas do Algoritmo Apriori

1. Identificação de Conjuntos Frequentes de 1 Item

O algoritmo calcula o suporte para cada item individual (a proporção de transações que contêm o item).
Se o suporte de um item atingir ou exceder o limite de min_support (aqui, 0.6), ele é considerado frequente e incluído na primeira lista de conjuntos frequentes.

2. Geração de Candidatos

Para conjuntos de itens de comprimento k (a partir de 2), o algoritmo gera novos conjuntos candidatos combinando conjuntos frequentes da rodada anterior que compartilham todos os itens, exceto um.
Apenas combinações únicas são consideradas, garantindo que não haja duplicatas.

3. Poda

Cada subconjunto de comprimento k-1 dos novos candidatos é verificado.
Se algum subconjunto não estiver na lista de conjuntos frequentes da iteração anterior, o candidato é podado (excluído), com base no Princípio de Apriori.

4. Contagem de Suporte

Para cada candidato restante, o algoritmo conta quantas transações contêm todos os itens do candidato.
O suporte é calculado e comparado ao limite. Apenas candidatos que atingem o limite são mantidos como conjuntos frequentes para a próxima rodada.

5. Iteração

As etapas 2–4 se repetem, aumentando o tamanho dos conjuntos de itens a cada vez, até que não sejam encontrados novos conjuntos frequentes.

Saída

A lista final inclui todos os conjuntos frequentes e seus valores de suporte.
O código imprime cada conjunto frequente e seu suporte, mostrando quais combinações de itens aparecem frequentemente juntos nas transações.

1. Qual das alternativas a seguir melhor descreve a etapa de geração de candidatos no algoritmo Apriori?

2. Qual é o principal motivo para podar conjuntos candidatos durante o algoritmo Apriori?

Tudo estava claro?

Obrigado pelo seu feedback!

Seção 1. Capítulo 4

Pergunte à IA

Pergunte o que quiser ou experimente uma das perguntas sugeridas para iniciar nosso bate-papo

Seção 1. Capítulo 4