Apriori

# =========================================================
# APRIORI DO ZERO — SEM BIBLIOTECA DE MINERAÇÃO
# =========================================================

transacoes = [
    {'Pão', 'Manteiga', 'Leite', 'Café'},
    {'Pão', 'Manteiga', 'Leite'},
    {'Pão', 'Manteiga', 'Leite', 'Café'},
    {'Pão', 'Manteiga', 'Leite'},
    {'Pão', 'Leite', 'Café'},
    {'Pão', 'Leite'},
    {'Manteiga', 'Leite'},
    {'Leite', 'Café'},
    {'Leite'},
    {'Café'}
]

SUPORTE_MINIMO = 0.30
CONFIANCA_MINIMA = 0.60


# ---------------------------------------------------------
# 1. GERAR COMBINAÇÕES SEM itertools
# ---------------------------------------------------------
def combinacoes(lista, tamanho, inicio=0, atual=None):
    if atual is None:
        atual = []

    if len(atual) == tamanho:
        return [atual[:]]

    resultado = []

    for i in range(inicio, len(lista)):
        atual.append(lista[i])
        resultado += combinacoes(lista, tamanho, i + 1, atual)
        atual.pop()

    return resultado


# ---------------------------------------------------------
# 2. CONTAR CANDIDATOS
# ---------------------------------------------------------
def contar_candidatos(transacoes, candidatos):
    contagem = {}

    # Todos começam com zero ocorrências.
    for candidato in candidatos:
        contagem[candidato] = 0

    # FOR EXTERNO:
    # pega UMA compra por vez.
    for compra in transacoes:

        # FOR INTERNO:
        # testa TODOS os candidatos nessa compra.
        for candidato in candidatos:

            # O candidato está INTEIRO dentro da compra?
            if candidato.issubset(compra):
                contagem[candidato] += 1

    return contagem


# ---------------------------------------------------------
# 3. TRANSFORMAR CONTAGEM EM SUPORTE E FILTRAR
# ---------------------------------------------------------
def filtrar_por_suporte(candidatos, contagem, total_transacoes):
    frequentes = []
    suportes = {}

    for candidato in candidatos:
        suporte = contagem[candidato] / total_transacoes
        suportes[candidato] = suporte

        if suporte >= SUPORTE_MINIMO:
            frequentes.append(candidato)

    return frequentes, suportes


# ---------------------------------------------------------
# 4. GERAR OS PRÓXIMOS CANDIDATOS + PODA APRIORI
# ---------------------------------------------------------
def gerar_proximos_candidatos(frequentes_anteriores, novo_tamanho):
    candidatos = set()
    frequentes_set = set(frequentes_anteriores)

    # Junta sobreviventes dois a dois.
    for a in frequentes_anteriores:
        for b in frequentes_anteriores:
            candidato = a | b

            # Queremos exatamente um item a mais.
            if len(candidato) != novo_tamanho:
                continue

            # Antes de aceitar esse candidato, verificamos
            # todos os subconjuntos com tamanho novo_tamanho - 1.
            lista = list(candidato)
            subconjuntos = combinacoes(lista, novo_tamanho - 1)

            pode_testar = True

            for subconjunto_lista in subconjuntos:
                subconjunto = frozenset(subconjunto_lista)

                # Se algum subconjunto já foi infrequente,
                # o candidato maior é PODADO sem contar na base.
                if subconjunto not in frequentes_set:
                    pode_testar = False
                    break

            if pode_testar:
                candidatos.add(frozenset(candidato))

    return list(candidatos)


# ---------------------------------------------------------
# 5. CRIAR OS CANDIDATOS DE 1 ITEM
# ---------------------------------------------------------
itens = set()

for compra in transacoes:
    for item in compra:
        itens.add(item)

candidatos = []

for item in itens:
    candidatos.append(frozenset([item]))


# ---------------------------------------------------------
# 6. LOOP PRINCIPAL DO APRIORI
# ---------------------------------------------------------
todos_frequentes = []
suportes_globais = {}
tamanho = 1

while len(candidatos) > 0:
    print('\nRODADA', tamanho)
    print('Candidatos:', [set(c) for c in candidatos])

    # A) percorre todas as compras e conta os candidatos.
    contagem = contar_candidatos(transacoes, candidatos)

    # B) contagem / número de compras = suporte.
    frequentes, suportes = filtrar_por_suporte(
        candidatos,
        contagem,
        len(transacoes)
    )

    for candidato in candidatos:
        print(
            set(candidato),
            'contagem =', contagem[candidato],
            'suporte =', round(suportes[candidato] * 100, 1), '%'
        )

    # C) guarda somente os sobreviventes.
    if len(frequentes) == 0:
        break

    todos_frequentes += frequentes
    suportes_globais.update(suportes)

    # D) cria candidatos um item maiores.
    tamanho += 1
    candidatos = gerar_proximos_candidatos(
        frequentes,
        tamanho
    )

    # O while volta para o começo.
    # Os NOVOS candidatos serão novamente testados
    # contra TODAS as compras.


# ---------------------------------------------------------
# 7. FUNÇÃO DE SUPORTE PARA ITEMSETS JÁ ENCONTRADOS
# ---------------------------------------------------------
def suporte(itemset):
    if itemset in suportes_globais:
        return suportes_globais[itemset]

    contagem = 0

    for compra in transacoes:
        if itemset.issubset(compra):
            contagem += 1

    return contagem / len(transacoes)


# ---------------------------------------------------------
# 8. SÓ AGORA GERAR REGRAS
# ---------------------------------------------------------
regras = []

for itemset in todos_frequentes:
    if len(itemset) < 2:
        continue

    itens_do_itemset = list(itemset)

    # Testa antecedentes com 1 item, 2 itens, ...
    for tamanho_antecedente in range(1, len(itemset)):
        possibilidades = combinacoes(
            itens_do_itemset,
            tamanho_antecedente
        )

        for antecedente_lista in possibilidades:
            antecedente = frozenset(antecedente_lista)
            consequente = itemset - antecedente

            suporte_itemset = suporte(itemset)
            suporte_antecedente = suporte(antecedente)
            suporte_consequente = suporte(consequente)

            confianca = suporte_itemset / suporte_antecedente
            lift = confianca / suporte_consequente

            if confianca >= CONFIANCA_MINIMA:
                regras.append({
                    'antecedente': antecedente,
                    'consequente': consequente,
                    'suporte': suporte_itemset,
                    'confianca': confianca,
                    'lift': lift
                })


# ---------------------------------------------------------
# 9. RESULTADO
# ---------------------------------------------------------
print('\nREGRAS ENCONTRADAS')

for regra in regras:
    print(
        set(regra['antecedente']),
        '=>',
        set(regra['consequente']),
        '| suporte =', round(regra['suporte'] * 100, 1), '%',
        '| confiança =', round(regra['confianca'] * 100, 1), '%',
        '| lift =', round(regra['lift'], 2)
    )