# Apriori

### 🎯 Descrição Geral

**Apriori** é um algoritmo clássico de **mineração de dados** para descoberta de **regras de associação** em grandes conjuntos de dados. Ele identifica itens que frequentemente aparecem juntos em transações, permitindo encontrar padrões como: *"clientes que compram pão também compram manteiga"*.

```
Transações de Supermercado:
┌─────────────────────────────────────┐
│ Cliente 1: {pão, leite, manteiga}   │
│ Cliente 2: {pão, manteiga, ovos}    │
│ Cliente 3: {leite, manteiga, café}  │
│ Cliente 4: {pão, leite, manteiga}   │
└─────────────────────────────────────┘
                    ↓
              Algoritmo Apriori
                    ↓
┌─────────────────────────────────────┐
│ Regra: {pão} → {manteiga} (75%)     │
│ Regra: {leite} → {manteiga} (75%)   │
└─────────────────────────────────────┘
```

#### Analogia

> *"Apriori é como um detetive de compras: analisa milhares de cestas de mercado e descobre que 'quase sempre que alguém compra cerveja, também compra amendoim'. Esses padrões são as regras de associação."*

***

### ⚙️ Conceitos Fundamentais

#### 1. Itens e Transações

| Conceito      | Definição                          | Exemplo                    |
| ------------- | ---------------------------------- | -------------------------- |
| **Item**      | Um produto/atributo individual     | "pão", "leite", "manteiga" |
| **Transação** | Conjunto de itens comprados juntos | {pão, leite, manteiga}     |
| **Itemset**   | Conjunto de k itens (k-itemset)    | {pão, leite} (2-itemset)   |

#### 2. Métricas de Interesse

| Métrica                    | Definição                 | Fórmula             | Exemplo                                 |
| -------------------------- | ------------------------- | ------------------- | --------------------------------------- |
| **Suporte (Support)**      | Frequência do itemset     | count(X) / total    | pão aparece em 5 de 10 transações → 50% |
| **Confiança (Confidence)** | Probabilidade de Y dado X | supp(X∪Y) / supp(X) | {pão} → {manteiga}: 80%                 |
| **Lift**                   | Força da associação       | conf(X→Y) / supp(Y) | >1: correlação positiva                 |

#### 3. Princípio Apriori (Propriedade Anti-monotônica)

> **Todo subconjunto de um itemset frequente é frequente.** **Todo superconjunto de um itemset infrequente é infrequente.**

```
Se {pão, leite} é infrequente (suporte baixo):
Então {pão, leite, manteiga} TAMBÉM é infrequente
```

Esta propriedade permite **podar** (cortar) a árvore de busca, eliminando combinações impossíveis.

***

### 🔧 Algoritmo Passo a Passo

#### Entrada

* Conjunto de transações `D`
* Suporte mínimo `min_sup` (ex: 0.3 = 30%)
* Confiança mínima `min_conf` (ex: 0.7 = 70%)

#### Saída

* Conjunto de regras de associação que satisfazem os mínimos

#### Fases do Algoritmo

```
FASE 1: Encontrar itemsets frequentes
    ↓
FASE 2: Gerar regras a partir dos itemsets frequentes
```

***

### 📝 Implementação

#### Implementação Básica em Python

```python
from collections import defaultdict
from itertools import combinations, chain

class Apriori:
    def __init__(self, min_support=0.01, min_confidence=0.5):
        self.min_support = min_support
        self.min_confidence = min_confidence
        self.frequent_itemsets = []
        self.rules = []
    
    def fit(self, transactions):
        """
        Executa o algoritmo Apriori
        transactions: lista de listas (ex: [['pão', 'leite'], ['pão', 'ovos']])
        """
        self.transactions = transactions
        self.n_transactions = len(transactions)
        
        # Converter para frozenset para operações de conjunto
        self.transactions = [frozenset(t) for t in transactions]
        
        # FASE 1: Encontrar itemsets frequentes
        self.frequent_itemsets = self._find_frequent_itemsets()
        
        # FASE 2: Gerar regras
        self.rules = self._generate_rules()
        
        return self
    
    def _find_frequent_itemsets(self):
        """Encontra todos os itemsets frequentes"""
        frequent_itemsets = []
        
        # k=1: itens individuais
        current_itemsets = self._get_frequent_items([frozenset([item]) for item in self._get_unique_items()])
        frequent_itemsets.extend(current_itemsets)
        
        k = 2
        while current_itemsets:
            # Gerar candidatos (k-itemsets)
            candidates = self._generate_candidates(current_itemsets, k)
            
            # Filtrar candidatos frequentes
            current_itemsets = self._get_frequent_items(candidates)
            frequent_itemsets.extend(current_itemsets)
            k += 1
        
        return frequent_itemsets
    
    def _get_unique_items(self):
        """Retorna todos os itens únicos"""
        items = set()
        for trans in self.transactions:
            items.update(trans)
        return items
    
    def _get_frequent_items(self, itemsets):
        """Filtra itemsets pelo suporte mínimo"""
        frequent = []
        
        for itemset in itemsets:
            support = self._calculate_support(itemset)
            if support >= self.min_support:
                frequent.append((itemset, support))
        
        return frequent
    
    def _calculate_support(self, itemset):
        """Calcula o suporte de um itemset"""
        count = 0
        for trans in self.transactions:
            if itemset.issubset(trans):
                count += 1
        return count / self.n_transactions
    
    def _generate_candidates(self, frequent_itemsets, k):
        """Gera candidatos k-itemsets a partir de (k-1)-itemsets frequentes"""
        candidates = set()
        
        # Extrair apenas os itemsets (sem o suporte)
        itemsets = [itemset for itemset, _ in frequent_itemsets]
        
        for i in range(len(itemsets)):
            for j in range(i + 1, len(itemsets)):
                # Unir dois itemsets que compartilham k-2 primeiros itens
                union = itemsets[i].union(itemsets[j])
                if len(union) == k:
                    # Verificar se todos os subconjuntos são frequentes (poda Apriori)
                    if self._all_subsets_frequent(union, itemsets):
                        candidates.add(union)
        
        return list(candidates)
    
    def _all_subsets_frequent(self, itemset, frequent_itemsets):
        """Verifica se todos os subconjuntos de tamanho k-1 são frequentes"""
        for subset in combinations(itemset, len(itemset) - 1):
            if frozenset(subset) not in frequent_itemsets:
                return False
        return True
    
    def _generate_rules(self):
        """Gera regras de associação a partir dos itemsets frequentes"""
        rules = []
        
        for itemset, support_itemset in self.frequent_itemsets:
            if len(itemset) < 2:
                continue
            
            # Gerar todas as combinações de antecedentes
            for i in range(1, len(itemset)):
                for antecedent in combinations(itemset, i):
                    antecedent = frozenset(antecedent)
                    consequent = itemset - antecedent
                    
                    if not consequent:
                        continue
                    
                    # Calcular confiança
                    support_antecedent = self._calculate_support(antecedent)
                    confidence = support_itemset / support_antecedent
                    
                    if confidence >= self.min_confidence:
                        # Calcular lift
                        support_consequent = self._calculate_support(consequent)
                        lift = confidence / support_consequent if support_consequent > 0 else 0
                        
                        rules.append({
                            'antecedent': set(antecedent),
                            'consequent': set(consequent),
                            'support': support_itemset,
                            'confidence': confidence,
                            'lift': lift
                        })
        
        # Ordenar por confiança (decrescente)
        rules.sort(key=lambda x: x['confidence'], reverse=True)
        return rules
    
    def print_rules(self, n=None):
        """Exibe as regras encontradas"""
        rules_to_show = self.rules if n is None else self.rules[:n]
        
        for i, rule in enumerate(rules_to_show):
            print(f"{i+1}. {set(rule['antecedent'])} → {set(rule['consequent'])}")
            print(f"   Suporte: {rule['support']:.2%} | Confiança: {rule['confidence']:.2%} | Lift: {rule['lift']:.2f}")
            print()

# Exemplo de uso
if __name__ == "__main__":
    # Dados de exemplo: transações de supermercado
    transacoes = [
        ['pão', 'leite', 'manteiga'],
        ['pão', 'manteiga', 'ovos'],
        ['leite', 'manteiga', 'café'],
        ['pão', 'leite', 'manteiga', 'ovos'],
        ['pão', 'leite', 'café'],
        ['pão', 'manteiga'],
        ['leite', 'manteiga', 'ovos'],
        ['pão', 'ovos'],
        ['leite', 'café'],
        ['pão', 'leite', 'manteiga', 'café']
    ]
    
    # Executar Apriori
    apriori = Apriori(min_support=0.3, min_confidence=0.6)
    apriori.fit(transacoes)
    
    print("=" * 50)
    print("REGRAS DE ASSOCIAÇÃO ENCONTRADAS")
    print("=" * 50)
    apriori.print_rules()
```

***

### 📊 Exemplo Detalhado

#### Dados de Exemplo

| Transação | Itens                        |
| --------- | ---------------------------- |
| T1        | {pão, leite, manteiga}       |
| T2        | {pão, manteiga, ovos}        |
| T3        | {leite, manteiga, café}      |
| T4        | {pão, leite, manteiga, ovos} |
| T5        | {pão, leite, café}           |

#### Cálculo de Suporte (min\_sup = 0.4 = 2/5)

| Itemset                | Contagem | Suporte | Frequente? |
| ---------------------- | -------- | ------- | ---------- |
| {pão}                  | 4        | 0.8     | ✅          |
| {leite}                | 4        | 0.8     | ✅          |
| {manteiga}             | 4        | 0.8     | ✅          |
| {ovos}                 | 2        | 0.4     | ✅          |
| {café}                 | 2        | 0.4     | ✅          |
| {pão, leite}           | 3        | 0.6     | ✅          |
| {pão, manteiga}        | 4        | 0.8     | ✅          |
| {leite, manteiga}      | 3        | 0.6     | ✅          |
| {pão, leite, manteiga} | 3        | 0.6     | ✅          |

#### Regras Geradas (min\_conf = 0.7)

| Regra                     | Suporte | Confiança  | Lift |
| ------------------------- | ------- | ---------- | ---- |
| {pão} → {manteiga}        | 0.8     | 1.0 (4/4)  | 1.25 |
| {leite} → {manteiga}      | 0.6     | 0.75 (3/4) | 0.94 |
| {manteiga} → {pão}        | 0.8     | 1.0 (4/4)  | 1.25 |
| {pão, leite} → {manteiga} | 0.6     | 1.0 (3/3)  | 1.25 |

***

### 📈 Otimizações e Variações

#### 1. FP-Growth (Alternativa mais eficiente)

O FP-Growth evita a geração de candidatos, sendo mais rápido para grandes conjuntos de dados.

```python
# FP-Growth é geralmente preferível para datasets grandes
# (implementação disponível em bibliotecas como mlxtend)
```

#### 2. Eclat (Algoritmo baseado em interseção)

Usa interseção de listas de transações (TID-lists) em vez de contagem.

#### 3. Redução de Suporte Mínimo Dinâmico

Adapta o suporte mínimo durante a execução para encontrar itens raros.

***

### 💻 Aplicações Práticas

#### Exemplo 1: Market Basket Analysis

```python
# Dados de e-commerce
pedidos = [
    ['celular', 'capa', 'película'],
    ['celular', 'carregador'],
    ['notebook', 'mouse', 'mousepad'],
    ['celular', 'capa', 'carregador', 'fone'],
    ['notebook', 'carregador', 'mouse']
]

apriori = Apriori(min_support=0.4, min_confidence=0.8)
apriori.fit(pedidos)
apriori.print_rules()

# Resultado esperado:
# {celular} → {capa} (clientes que compram celular também compram capa)
```

#### Exemplo 2: Análise de Recomendação

```python
# Dados de streaming (filmes assistidos)
usuarios = [
    ['Inception', 'Matrix', 'Interestelar'],
    ['Matrix', 'John Wick', 'Duro de Matar'],
    ['Inception', 'Interestelar', 'Perdido em Marte'],
    ['Matrix', 'Inception', 'Interestelar']
]

apriori = Apriori(min_support=0.5, min_confidence=0.6)
apriori.fit(usuarios)
apriori.print_rules()

# Resultado:
# {Inception} → {Interestelar} (fãs de Inception também gostam de Interestelar)
```

#### Exemplo 3: Análise de Logs de Sistema

```python
# Logs de falhas de sistema
falhas = [
    ['CPU alta', 'memoria_baixa', 'disco_lento'],
    ['CPU alta', 'temperatura_alta'],
    ['memoria_baixa', 'swap_uso'],
    ['CPU alta', 'memoria_baixa', 'swap_uso']
]

apriori = Apriori(min_support=0.5, min_confidence=0.7)
apriori.fit(falhas)

# Resultado:
# {CPU alta} → {memoria_baixa} (quando CPU está alta, memória também costuma estar baixa)
```

***

### 📊 Comparação com Outros Algoritmos

| Algoritmo     | Vantagem                    | Desvantagem            | Uso                      |
| ------------- | --------------------------- | ---------------------- | ------------------------ |
| **Apriori**   | Simples, fácil de entender  | Gera muitos candidatos | Datasets pequenos/médios |
| **FP-Growth** | Mais rápido, sem candidatos | Mais complexo          | Datasets grandes         |
| **Eclat**     | Bom para padrões densos     | Memória intensiva      | Transações densas        |

***

### 🎯 Configuração de Parâmetros

#### Como escolher min\_support

| Dataset                | min\_support típico | Por que                       |
| ---------------------- | ------------------- | ----------------------------- |
| Supermercado (grande)  | 0.01 - 0.05         | Muitos produtos diferentes    |
| Supermercado (pequeno) | 0.1 - 0.3           | Menos produtos                |
| Logs de sistema        | 0.05 - 0.2          | Erros são relativamente raros |
| Recomendação de filmes | 0.01 - 0.1          | Muitos filmes diferentes      |

#### Como escolher min\_confidence

| Cenário              | min\_confidence | Interpretação                          |
| -------------------- | --------------- | -------------------------------------- |
| Recomendações        | 0.3 - 0.5       | Aceita associações moderadas           |
| Regras de negócio    | 0.7 - 0.9       | Exige alta confiança                   |
| Análise exploratória | 0.5 - 0.7       | Equilíbrio entre descoberta e precisão |

***

### ⚠️ Limitações

| Limitação                 | Descrição                          | Mitigação                              |
| ------------------------- | ---------------------------------- | -------------------------------------- |
| **Geração de candidatos** | Para k=10, milhões de candidatos   | Usar FP-Growth                         |
| **Múltiplas leituras**    | Escaneia o dataset a cada iteração | Otimizar com hash tables               |
| **Itens raros**           | Descartados pelo suporte mínimo    | Usar min\_support dinâmico             |
| **Regras triviais**       | {pão} → {pão} (sempre verdade)     | Filtrar regras com consequentes vazios |
| **Alta dimensionalidade** | 10.000 itens → 10²⁰ candidatos     | Redução de dimensionalidade            |

***

### 🔗 Links Úteis

* [mlxtend - Biblioteca Apriori para Python](http://rasbt.github.io/mlxtend/user_guide/frequent_patterns/apriori/)
* [Apriori Algorithm - Wikipedia](https://en.wikipedia.org/wiki/Apriori_algorithm)
* [FP-Growth Algorithm](https://en.wikipedia.org/wiki/FP-growth)

***

### 📚 Exemplo com mlxtend (Biblioteca Prática)

```python
# pip install mlxtend
import pandas as pd
from mlxtend.frequent_patterns import apriori, association_rules

# Dados no formato one-hot encoded
dataset = pd.DataFrame({
    'pão': [1, 1, 0, 1, 1],
    'leite': [1, 0, 1, 1, 1],
    'manteiga': [1, 1, 1, 1, 0],
    'ovos': [0, 1, 0, 1, 0],
    'café': [0, 0, 1, 0, 1]
})

# Encontrar itemsets frequentes
frequent_itemsets = apriori(dataset, min_support=0.4, use_colnames=True)

# Gerar regras
rules = association_rules(frequent_itemsets, metric="confidence", min_threshold=0.7)

print("Itemsets frequentes:")
print(frequent_itemsets)

print("\nRegras de associação:")
print(rules[['antecedents', 'consequents', 'support', 'confidence', 'lift']])
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://0xmorte.gitbook.io/bibliadopentestbr/conceitos/algoritmos/aprendizado-de-maquina-machine-learning/apriori.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.