Aula 9: Redes Bayesianas e Modelos Gráficos Probabilísticos (PGMs) para Mineração de Itens Frequentes
Aprendizado Não Supervisionado
1 Revisão e Introdução
1.1 O Fracasso do Espaço Contínuo em Dados Discretos
Até este ponto do curso, toda a nossa jornada em aprendizado não supervisionado ocorreu estritamente em espaços contínuos e métricos \(\mathbb{R}^D\): - Agrupamos dados calculando distâncias euclidianas e matrizes de variância-covariância; - Modelamos densidades via misturas de Gaussianas e autoencoders contínuos (PCA, VAEs); - Preservamos vizinhanças locais projetando variedades curvas em planos 2D via t-SNE.
Em todas essas formulações, as operações fundamentais dependiam de normas, produtos internos, projeções ortogonais e gradientes.
Esta aula inaugura a Parte 3: Descoberta de Informação e Estruturas em Grande Escala, estabelecendo uma ruptura conceitual e metodológica: Em problemas do mundo real — como logs de comércio eletrônico, registros de navegação web, prontuários hospitalares e dados genômicos discretos —, os dados chegam como vetores binários esparsos \(\mathbf{x} \in \{0, 1\}^D\) ou variáveis qualitativas puras.
Nesse contexto discreto: 1. Distâncias euclidianas perdem o sentido físico: Qual é a distância geométrica entre um cliente que comprou Leite e outro que comprou Fralda? Dizer que \(\|\mathbf{x}_1 - \mathbf{x}_2\| = \sqrt{2}\) não traz nenhuma informação sobre hábitos de consumo ou complementaridade de produtos. 2. A média de observações não é um objeto válido: O vetor médio de compras em um supermercado conteria frações como \(0{,}03\) cafés e \(0{,}07\) sabonetes — um estado abstrato que não representa nenhuma transação realizável. 3. O objetivo muda radicalmente: O desafio não é projetar nuvens de pontos contínuas em um plano, mas descobrir estruturas de co-ocorrência e dependência estatística em espaços combinatórios massivos.
1.2 Ideia Central
A jornada desta aula ancora-se em quatro passos conceituais que conectam a mineração empírica de padrões ao rigor dos modelos gráficos probabilísticos:
1.2.1 1. O Objetivo: Encontrar Co-ocorrências e Padrões Frequentes
Em grandes bases de dados discretas e transacionais — como logs de comércio eletrônico, registros de navegação web e prontuários médicos —, o primeiro objetivo do aprendizado não supervisionado é descobrir quais eventos co-ocorrem com frequência. Na clássica análise de cestas de compras (market basket analysis; Agrawal et al., 1993; ESL §14.2), o objetivo é rastrear regras da forma \(\{Item_A\} \Rightarrow \{Item_B\}\). Avaliamos contagens empíricas através de métricas como Suporte (\(P(A \cap B)\)), Confiança (\(P(B \mid A)\)) e Lift (\(\frac{P(A \cap B)}{P(A)P(B)}\)). O algoritmo Apriori explora a propriedade de antimonotonicidade do suporte para varrer o espaço de busca combinatorial e listar todos os conjuntos de itens frequentes.
1.2.2 2. A Incerteza: Padrões Observados são Realmente Válidos?
Encontrar que dois produtos co-ocorrem com frequência elevada e alto Lift na base transacional não significa que exista uma atração real ou direta entre eles. As contagens empíricas agregadas sofrem de armadilhas estatísticas severas: - Correlações Espúrias por Causas Comuns (Confounding): Dois itens podem aparecer repetidamente na mesma cesta simplesmente porque ambos são comprados pelo mesmo perfil demográfico ou na mesma época do ano (ex.: Café Gourmet e Torradeira comprados por famílias de maior renda). A regra direta \(\{Café\} \Rightarrow \{Torradeira\}\) é uma ilusão estatística. - Atalhos Transitivos Redundantes: Se a compra de Pão induz Manteiga (\(P \Rightarrow M\)) e a Manteiga induz Geleia (\(M \Rightarrow G\)), o algoritmo também gerará a regra \(\{Pão\} \Rightarrow \{Geleia\}\). Aceitar essa regra agregada inflaciona a complexidade do sistema com atalhos redundantes, pois toda a influência é mediada pelo intermediário. - Vieses de Seleção: Recortar a base por critérios de amostragem pode fazer variáveis perfeitamente independentes parecerem fortemente correlacionadas.
Em suma: co-ocorrência bruta não garante relação estrutural válida.
1.2.3 3. A Solução: O Teste da Probabilidade Condicional
Como discernir quais associações são estruturais e quais são espúrias ou redundantes? A resposta está em um poderoso princípio da teoria das probabilidades: a independência condicional.
Dizemos que duas variáveis \(A\) e \(B\) são condicionalmente independentes dado um terceiro fator \(C\) (denotado por \(A \perp\!\!\!\perp B \mid C\)) se: \[P(A, B \mid C) = P(A \mid C) P(B \mid C) \quad \iff \quad P(A \mid B, C) = P(A \mid C)\] Na prática, isso significa que, uma vez conhecido o estado de \(C\), saber que \(B\) ocorreu não adiciona nenhuma informação nova sobre \(A\): - Se a alta correlação entre Café e Torradeira desaparecer quando estratificamos os clientes por faixa de renda (\(Café \perp\!\!\!\perp Torradeira \mid Renda\)), provamos que a relação direta não existe; - Se o intermediário \(M\) bloquear a transmissão entre \(P\) e \(G\) (\(P \perp\!\!\!\perp G \mid M\)), provamos que o atalho direto é desnecessário.
1.2.4 4. O Modelo Formal: Representação em DAGs e Exemplo Prático
Para unificar essas independências condicionais em uma representação computacional e visual tratável, recorremos aos Modelos Gráficos Probabilísticos Direcionados (Redes Bayesianas) baseados em Grafos Acíclicos Direcionados (DAGs; Pearl, 1988; Bishop, 2006, Cap. 8): - Cada nó do grafo representa uma variável ou produto do catálogo; - Cada aresta direcionada (\(A \to B\)) representa uma dependência direta; - A ausência de aresta codifica rigorosamente uma hipótese de independência condicional: duas variáveis não conectadas tornam-se condicionalmente independentes quando controlamos pelos seus pais ou mediadores!
Considere o grafo de exemplo a seguir com itens de um catálogo de varejo: 1. O nó de contexto Perfil de Renda (\(R\)) é uma causa comum para Café Gourmet (\(C\)) e Torradeira (\(T\)). Na tabela agregada do Apriori, Café e Torradeira apresentam alto Lift; contudo, no DAG não há aresta direta entre \(C\) e \(T\), pois \(C \perp\!\!\!\perp T \mid R\). 2. Por outro lado, a compra de Pão Francês (\(P\)) possui uma aresta direta para Manteiga (\(M\)), refletindo uma afinidade genuína de consumo na mesma categoria de matinais.
1.3 Roteiro da Aula
Para construir essa transição das regras práticas ao rigor probabilístico, estruturaremos a aula em quatro blocos conceituais:
- Como formalizar matematicamente transações, Suporte, Confiança e a Antimonotonicidade? Definir os vetores binários, deduzir a antimonotonicidade do suporte e provar a comutatividade do Lift.
- Como o algoritmo Apriori opera na prática para podar o espaço de busca combinatorial? Acompanhar passo a passo o ciclo de junção e poda em memória RAM com dados de supermercado.
- Como as Redes Bayesianas e as três geometrias canônicas filtram regras do Apriori? Usar o DAG como mapa de dependências e as estruturas canônicas para descartar regras espúrias, podar atalhos redundantes e alertar sobre viés de seleção.
- Como montar o grafo de dependências e quais são os limites da observação passiva? Compreender a construção do Grafo Essencial (CPDAG) por componentes locais e a barreira da I-Equivalência de Markov.
1.4 Problema Motivador
Considere uma base transacional de varejo com \(N=10.000\) compras observadas. Analisando as vendas de dois itens do catálogo — Café Gourmet (\(A\)) e Torradeira Elétrica (\(B\)) —, um analista de dados extrai as frequências empíricas:
- Suporte marginal do café: \(P(A=1) \approx 0{,}24\);
- Suporte marginal da torradeira: \(P(B=1) \approx 0{,}18\);
- Suporte conjunto: \(P(A=1, B=1) \approx 0{,}116\).
Ao calcular o Lift da regra \(\{Caf\acute{e}\} \Rightarrow \{Torradeira\}\), ele obtém: \[\text{Lift} = \frac{P(A=1, B=1)}{P(A=1)P(B=1)} \approx \frac{0{,}116}{(0{,}24)(0{,}18)} \approx 2{,}69\]
Um Lift de \(2{,}69\) sugere forte complementaridade comercial: a presença de café gourmet na cesta parece quase triplicar a probabilidade de compra da torradeira. A equipe de marketing prontamente propõe posicionar os pacotes de café ao lado dos eletrodomésticos.
Contudo, ao inspecionarmos uma terceira variável — Perfil de Renda do Cliente (\(C\)), onde \(C=1\) representa clientes de alta renda e \(C=0\) o público geral —, revelamos a verdadeira estrutura geradora: - Dentro do estrato \(C=1\): \(\text{Lift}(A \Rightarrow B \mid C=1) \approx 1{,}00\); - Dentro do estrato \(C=0\): \(\text{Lift}(A \Rightarrow B \mid C=0) \approx 1{,}00\).
Condicionalmente à renda do cliente, a compra de café e a compra de torradeira são rigorosamente independentes! A suposta atração de \(2{,}69\) é uma correlação inteiramente espúria causada pela variável de confusão \(C\).
1.5 Pausa 1: O Espaço Binário e a Ruptura Métrica
DicaV ou F: Espaços Discretos e Métricas
Julgue V ou F — a questão só conta se acertar os 4 itens:
- □ A distância euclidiana entre dois vetores de compra binários penaliza igualmente a ausência conjunta de um item e a presença discordante de um item.
- □ Em um catálogo de \(D=50\) produtos, o número total de possíveis cestas distintas de compras é superior a \(10^{15}\).
- □ Se duas variáveis \(A\) e \(B\) apresentam \(\text{Lift}(A \Rightarrow B) > 1\) em uma base transacional agregada, é matematicamente impossível que elas sejam condicionalmente independentes dado um terceiro fator \(C\).
- □ Modelos baseados em gradiente contínuo e projeções ortogonais podem ser aplicados diretamente a matrizes binárias esparsas sem perdas conceituais ou semânticas.
2 Intuição — O Mercado, a Cesta e a Busca Combinatória
2.1 A Explosão Combinatória e o Funil de Frequências
Imagine a esteira de um hipermercado moderno. O catálogo da loja dispõe de \(D = 10.000\) produtos diferentes. Cada consumidor deposita no carrinho um pequeno subconjunto desses itens — tipicamente entre \(5\) e \(30\) produtos.
Se quiséssemos descobrir padrões procurando exaustivamente quais combinações de itens aparecem frequentemente juntas, o número de combinações possíveis seria: \[\sum_{k=1}^D \binom{D}{k} = 2^D - 1 = 2^{10.000} - 1 \approx 10^{3.010}\] Este número é ordens de grandeza superior ao número total de átomos no universo observável (\(\approx 10^{80}\)). Nenhuma superestrutura computacional existente ou futura jamais conseguirá computar a frequência de todos os subconjuntos de um catálogo modesto.
No entanto, a intuição fundamental do varejo é que a imensa maioria dos produtos nunca é comprada em conjunto. Se quase ninguém compra simultaneamente Prego e Iogurte, é um desperdício computacional avaliar se alguém comprou Prego, Iogurte e Pão Francês.
Essa constatação intuitiva sustenta o princípio do funil de frequências: um conjunto de itens só tem chance de ser popular se todos os seus ingredientes forem, por si sós, populares. Se pudermos cortar os galhos secos da árvore combinatorial logo na raiz, o número de combinações candidatas desaba de trilhões para algumas dezenas.
3 Bloco 1: Mineração de Itens Frequentes — Suporte, Confiança e Antimonotonicidade
3.1 Da Cesta de Compras à Matriz Binária
Antes de formalizarmos analiticamente as propriedades estatísticas de suporte e confiança, é essencial visualizar como transações qualitativas do varejo são estruturadas na memória computacional.
Considere uma amostra de \(N=5\) transações observadas no caixa de um supermercado, extraídas de um catálogo restrito com \(D=5\) produtos: \[\mathcal{I} = \{P\tilde{a}o, Leite, Manteiga, Caf\acute{e}, Cerveja\}\]
A tabela a seguir apresenta a correspondência exata entre a cesta observada e a matriz binária de incidência \(\mathbf{X} \in \{0, 1\}^{N \times D}\):
| Transação (\(n\)) | Cesta Observada (\(t_n\)) | Pão (\(x_1\)) | Leite (\(x_2\)) | Manteiga (\(x_3\)) | Café (\(x_4\)) | Cerveja (\(x_5\)) |
|---|---|---|---|---|---|---|
| \(T_1\) | \(\{P\tilde{a}o, Leite, Manteiga\}\) | 1 | 1 | 1 | 0 | 0 |
| \(T_2\) | \(\{P\tilde{a}o, Caf\acute{e}\}\) | 1 | 0 | 0 | 1 | 0 |
| \(T_3\) | \(\{Leite, Manteiga, Caf\acute{e}\}\) | 0 | 1 | 1 | 1 | 0 |
| \(T_4\) | \(\{P\tilde{a}o, Leite, Caf\acute{e}\}\) | 1 | 1 | 0 | 1 | 0 |
| \(T_5\) | \(\{Cerveja\}\) | 0 | 0 | 0 | 0 | 1 |
A partir dessa matriz, discriminamos os três conceitos centrais: 1. Item (\(i_j \in \mathcal{I}\)): Um produto específico do catálogo (uma coluna da matriz binária). 2. Transação (\(\mathbf{x}_n \in \{0, 1\}^D\)): O conjunto de itens adquiridos em uma compra (uma linha da matriz binária). 3. Itemset (\(I \subseteq \mathcal{I}\)): Qualquer subconjunto de itens avaliado conjuntamente. Um itemset de cardinalidade \(|I|=k\) é denominado \(k\)-itemset.
Dizemos que uma transação \(n\) contém o itemset \(I\) (\(I \subseteq t_n\)) se e somente se todos os seus componentes estiverem presentes simultaneamente: \[\mathbb{I}(I \subseteq t_n) = \prod_{j \in I} x_{nj}\] No exemplo acima, para o par \(I = \{P\tilde{a}o, Leite\}\), verificamos que \(x_{n, 1} \cdot x_{n, 2} = 1\) apenas nas transações \(T_1\) e \(T_4\). Em \(T_2\) falta Leite (\(1 \times 0 = 0\)); em \(T_3\) falta Pão (\(0 \times 1 = 0\)); e em \(T_5\) faltam ambos (\(0 \times 0 = 0\)). O suporte empírico desse par é de \(2\) em \(5\) transações (\(s = 40\%\)).
3.2 Formalização de Itens e Transações
Consolidando a representação da matriz binária na linguagem matemática formal de Agrawal et al. (1993) e ESL (§14.2), consideramos um universo de \(D\) itens discretos indexados por \(\mathcal{I} = \{i_1, i_2, \dots, i_D\}\). Uma transação de compras \(t\) é um subconjunto de itens \(t \subseteq \mathcal{I}\), formalizada como um vetor binário de incidência: \[\mathbf{x} = (x_1, \dots, x_D)^T \in \{0, 1\}^D, \quad \text{onde } x_j = \mathbb{I}(i_j \in t)\]
A base de dados observada \(\mathcal{D}\) contém \(N\) transações independentes: \[\mathcal{D} = \{\mathbf{x}_1, \mathbf{x}_2, \dots, \mathbf{x}_N\}\]
A viabilidade de encontrar todos os itemsets frequentes sem enumerar os \(2^D - 1\) candidatos decorre da propriedade matemática formalizada a seguir.
3.3 Teorema da Antimonotonicidade do Suporte
A contrapositiva lógica do Teorema 1 estabelece a regra de ouro da poda algorítmica: \[\text{Se } s(A) < s_{\min}, \quad \text{então } \forall B \supseteq A, \quad s(B) < s_{\min}\] Se qualquer subconjunto for infrequente, nenhum superconjunto precisa sequer ser computado.
3.4 Regras de Associação: Confiança e Lift
A partir de um itemset frequente \(I\), constroem-se regras de associação particionando os itens em antecedente e consequente: \[A \Rightarrow B, \quad \text{onde } A, B \subset I, \quad A \cap B = \emptyset, \quad A \cup B = I\] Onde \(A\) representa o itemset antecedente (“se a compra contém \(A\)”) e \(B\) o consequente (“então também contém \(B\)”).
Para quantificar a relevância de uma regra, a literatura clássica de mineração de dados (Agrawal et al., 1993; ESL §14.2.2) adota duas métricas fundamentais:
Interpretando os valores do Lift: - \(\text{Lift} = 1\): Independência estocástica (\(P(B \mid A) = P(B)\)). A presença de \(A\) não altera em nada a propensão de compra de \(B\). - \(\text{Lift} > 1\): Associação positiva aparente (\(P(B \mid A) > P(B)\)). Os itens co-ocorrem mais frequentemente do que o esperado pelo mero acaso. - \(\text{Lift} < 1\): Associação negativa ou substituição (\(P(B \mid A) < P(B)\)). A compra de \(A\) inibe ou compete com a compra de \(B\).
3.5 A Falácia da Simetria do Lift
Apesar de ser amplamente utilizado em ferramentas comerciais para ranquear regras de recomendação, o Lift carrega uma deficiência matemática estrutural que induz a erros críticos de interpretação: o Lift é estritamente comutativo.
Pela comutatividade da probabilidade da interseção (\(P(A \cap B) = P(B \cap A)\)) e do produto real: \[\text{Lift}(A \Rightarrow B) = \frac{P(A \cap B)}{P(A)P(B)} = \frac{P(B \cap A)}{P(B)P(A)} = \text{Lift}(B \Rightarrow A)\]
Essa simetria matemática demonstra que o Lift não possui nenhuma direcionalidade: ele mede apenas o afastamento da independência conjunta entre duas variáveis, sendo incapaz de distinguir se \(A\) atrai \(B\), se \(B\) atrai \(A\), ou se ambos decorrem de um fator externo.
3.5.1 O Abismo entre o Lift Simétrico e a Confiança Assimétrica
A relação formal entre a Confiança (que é assimétrica) e o Lift (que é simétrico) é dada por: \[c(A \Rightarrow B) = \text{Lift}(A \Rightarrow B) \times P(B)\] \[c(B \Rightarrow A) = \text{Lift}(B \Rightarrow A) \times P(A) = \text{Lift}(A \Rightarrow B) \times P(A)\]
Dividindo as duas equações: \[\frac{c(A \Rightarrow B)}{c(B \Rightarrow A)} = \frac{P(B)}{P(A)}\]
A assimetria comportamental entre as duas regras depende exclusivamente da razão entre as probabilidades marginais dos itens: - Se \(B\) for um produto popular de alta penetração (ex.: sacola plástica, pão francês) e \(A\) for um produto específico e raro (ex.: smartphone, cafeteira expresso), teremos \(P(B) \gg P(A)\). - Como consequência direta, \(c(A \Rightarrow B)\) será altíssima (ex.: \(95\%\)), enquanto \(c(B \Rightarrow A)\) será ínfima (ex.: \(0{,}1\%\)). - No entanto, ambas as regras apresentarão rigorosamente o mesmíssimo Lift!
3.5.2 A Ilusão Causal no Varejo
A armadilha analítica manifesta-se quando o cientista de dados interpreta a notação de seta \(A \Rightarrow B\) como um canal de atração causal: 1. O analista encontra uma regra \(\{Smartphone\} \Rightarrow \{Capinha\}\) com \(\text{Lift} = 4{,}75\) e supõe erroneamente que a relação é bidirecional ou simétrica. 2. Se a loja criar uma campanha concedendo descontos agressivos em capinhas esperando com isso alavancar a venda de smartphones, o resultado será nulo: quem compra smartphone costuma levar uma capinha (\(c = 95\%\)), mas a imensa maioria dos que compram capinhas avulsas jamais compra um smartphone naquela visita (\(c = 4{,}75\%\)). 3. O Lift é cego a qual item é a âncora de intenção de compra e a variáveis de confusão latentes, impondo a necessidade de modelos gráficos com representação explícita de dependência condicional.
3.6 Pausa 2: Suporte, Confiança e a Falácia da Simetria
DicaV ou F: Métricas de Regras de Associação
Julgue V ou F — a questão só conta se acertar os 4 itens:
- □ Pela propriedade de antimonotonicidade, se o itemset \(\{P\tilde{a}o, Caf\acute{e}\}\) tem suporte de \(0{,}30\), o item isolado \(\{P\tilde{a}o\}\) tem suporte maior ou igual a \(0{,}30\).
- □ A confiança \(c(A \Rightarrow B)\) é uma métrica simétrica, satisfazendo sempre \(c(A \Rightarrow B) = c(B \Rightarrow A)\).
- □ Se um produto \(B\) for comprado em \(90\%\) de todas as transações de uma loja, qualquer regra \(A \Rightarrow B\) terá confiança mínima de \(90\%\), mesmo que \(A\) e \(B\) sejam completamente independentes.
- □ Um valor de \(\text{Lift}(A \Rightarrow B) = 3{,}0\) prova que comprar \(A\) causa diretamente um aumento de \(300\%\) nas vendas de \(B\).
4 Bloco 2: O Algoritmo Apriori na Prática
4.1 Um Cenário Concreto: A Mini-Base de 5 Transações
Para compreender a mecânica do algoritmo Apriori sem se perder em abstrações, vamos acompanhar a execução passo a passo em uma mini-base de dados com \(N = 5\) transações e \(5\) produtos do catálogo: Café (\(C\)), Leite (\(L\)), Manteiga (\(M\)), Pão (\(P\)) e Cerveja (\(V\)).
| TID | Cesta de Compras | Itens Presentes |
|---|---|---|
| \(T_1\) | \(\{Café, Leite, Pão\}\) | \(\{C, L, P\}\) |
| \(T_2\) | \(\{Café, Leite, Manteiga\}\) | \(\{C, L, M\}\) |
| \(T_3\) | \(\{Café, Leite, Manteiga, Pão\}\) | \(\{C, L, M, P\}\) |
| \(T_4\) | \(\{Leite, Manteiga, Pão\}\) | \(\{L, M, P\}\) |
| \(T_5\) | \(\{Café, Cerveja, Pão\}\) | \(\{C, P, V\}\) |
4.1.1 O Nosso Objetivo
Definimos um suporte mínimo de \(60\%\): \[s_{\min} = 0{,}60 \iff \text{contagem mínima } \sigma_{\min} = 0{,}60 \times 5 = \mathbf{3 \text{ transações}}\]
Uma busca exaustiva por força bruta exigiria testar todas as \(2^5 - 1 = 31\) combinações possíveis de produtos. O algoritmo Apriori (Agrawal & Srikant, 1994) resolve isso de forma inteligente: opera em camadas de tamanho crescente (\(k = 1, 2, 3, \dots\)), descartando ramos inteiros na raiz através da antimonotonicidade.
4.2 Nível 1 (\(k=1\)): Contagem Individual e a Primeira Poda
No primeiro nível (\(k=1\)), o algoritmo realiza uma única varredura na base de dados para contar a frequência de cada item isolado:
| Candidato (\(C_1\)) | Transações em que aparece | Contagem Real | Suporte \(s(i)\) | Status (\(s \ge 60\%\)) |
|---|---|---|---|---|
| \(\{Café\}\) | \(T_1, T_2, T_3, T_5\) | \(4\) | \(80\%\) | ✔ Frequente (\(L_1\)) |
| \(\{Leite\}\) | \(T_1, T_2, T_3, T_4\) | \(4\) | \(80\%\) | ✔ Frequente (\(L_1\)) |
| \(\{Manteiga\}\) | \(T_2, T_3, T_4\) | \(3\) | \(60\%\) | ✔ Frequente (\(L_1\)) |
| \(\{Pão\}\) | \(T_1, T_3, T_4, T_5\) | \(4\) | \(80\%\) | ✔ Frequente (\(L_1\)) |
| \(\{Cerveja\}\) | \(T_5\) | \(1\) | \(20\%\) | ✗ INFREQUENTE! |
O conjunto de itens frequentes de tamanho 1 é: \[L_1 = \{\{Café\}, \{Leite\}, \{Manteiga\}, \{Pão\}\}\]
4.2.1 O Poder da Antimonotonicidade em Ação
A Cerveja foi comprada em apenas 1 cesta e foi reprovada. Pelo Teorema 1 (\(A \subseteq B \implies s(B) \le s(A)\)), sabemos com certeza matemática que qualquer combinação futura contendo Cerveja (como \(\{Café, Cerveja\}\) ou \(\{Cerveja, Pão, Leite\}\)) terá no máximo suporte de \(1/5 = 20\%\).
Portanto, a Cerveja é eliminada da árvore de busca para sempre. Nenhum candidato com cerveja jamais será gerado ou contado.
4.3 Nível 2 (\(k=2\)): Geração de Pares e Contagem
Para construir os pares candidatos de tamanho 2 (\(C_2\)), o Apriori combina apenas os itens sobreviventes em \(L_1\): \[\binom{|L_1|}{2} = \binom{4}{2} = 6 \text{ pares candidatos}\]
Adotamos a ordem alfabética estrita para evitar duplicações: \(Café < Leite < Manteiga < Pão\).
Realizamos a segunda varredura na base de dados, contando a frequência de cada um dos 6 pares:
| Par Candidato (\(C_2\)) | Transações em que co-ocorre | Contagem Real | Suporte | Status (\(s \ge 60\%\)) |
|---|---|---|---|---|
| \(\{Café, Leite\}\) | \(T_1, T_2, T_3\) | \(3\) | \(60\%\) | ✔ Frequente (\(L_2\)) |
| \(\{Café, Manteiga\}\) | \(T_2, T_3\) | \(2\) | \(40\%\) | ✗ Infrequente (Descartado) |
| \(\{Café, Pão\}\) | \(T_1, T_3, T_5\) | \(3\) | \(60\%\) | ✔ Frequente (\(L_2\)) |
| \(\{Leite, Manteiga\}\) | \(T_2, T_3, T_4\) | \(3\) | \(60\%\) | ✔ Frequente (\(L_2\)) |
| \(\{Leite, Pão\}\) | \(T_1, T_3, T_4\) | \(3\) | \(60\%\) | ✔ Frequente (\(L_2\)) |
| \(\{Manteiga, Pão\}\) | \(T_3, T_4\) | \(2\) | \(40\%\) | ✗ Infrequente (Descartado) |
Aprovando apenas os pares com contagem \(\ge 3\), obtemos a tabela de itemsets frequentes de tamanho 2: \[L_2 = \{\{Café, Leite\}, \{Café, Pão\}, \{Leite, Manteiga\}, \{Leite, Pão\}\}\]
Observe com atenção: os pares \(\{Café, Manteiga\}\) e \(\{Manteiga, Pão\}\) falharam no suporte mínimo e não entraram em \(L_2\). Guarde esse fato: ele será a chave do passo de poda no próximo nível!
4.4 Nível 3 (\(k=3\)): O Passo de Junção (\(L_{k-1} \bowtie L_{k-1}\))
Agora chegamos ao núcleo do algoritmo Apriori: como gerar candidatos de tamanho 3 (\(C_3\)) a partir de \(L_2\)?
Se tentássemos unir pares arbitrários, geraríamos o mesmo trio várias vezes (ex.: \(\{A, B\} \cup \{A, C\}\) e \(\{A, B\} \cup \{B, C\}\) produzem o mesmo \(\{A, B, C\}\)). Para evitar qualquer redundância, Agrawal & Srikant (1994) definem a regra do prefixo comum de tamanho \(k-2\): Dois itemsets de tamanho \(k-1\) só podem ser unidos se forem idênticos nos primeiros \(k-2\) itens e diferirem apenas no último item: \[p[1]=q[1], \dots, p[k-2]=q[k-2] \quad \text{e} \quad p[k-1] < q[k-1]\]
Para passar de \(k=2\) para \(k=3\) (\(k-2=1\) item de prefixo comum), ordenamos os pares de \(L_2\) alfabeticamente: 1. Pares com prefixo \(\{Café\}\): Temos \(\{Café, Leite\}\) e \(\{Café, Pão\}\). Ambos começam com \(Café\), e \(Leite < Pão\). A junção produz: \[c_1 = \{Café, Leite, Pão\}\] 2. Pares com prefixo \(\{Leite\}\): Temos \(\{Leite, Manteiga\}\) e \(\{Leite, Pão\}\). Ambos começam com \(Leite\), e \(Manteiga < Pão\). A junção produz: \[c_2 = \{Leite, Manteiga, Pão\}\]
A junção gerou exatamente dois candidatos de tamanho 3: \[C_3 = \{\{Café, Leite, Pão\}, \{Leite, Manteiga, Pão\}\}\]
4.5 O Passo de Poda (Pruning Step) em Memória RAM
Antes de ler o banco de dados em disco para contar o suporte de \(C_3\), o Apriori executa o passo de poda (prune step).
Pela antimonotonicidade, para que um trio \(\{X, Y, Z\}\) seja frequente, todos os seus 3 subconjuntos de tamanho 2 devem pertencer a \(L_2\). Essa checagem é feita instantaneamente consultando a tabela \(L_2\) já carregada na memória RAM:
4.5.1 1. Testando o Candidato \(c_1 = \{Café, Leite, Pão\}\)
Verificamos todos os seus subconjuntos de tamanho 2: - \(\{Café, Leite\} \in L_2\)? Sim (contagem 3); - \(\{Café, Pão\} \in L_2\)? Sim (contagem 3); - \(\{Leite, Pão\} \in L_2\)? Sim (contagem 3).
Como todos os subconjuntos de tamanho 2 são frequentes, o candidato \(c_1\) sobrevive à poda e avança para a contagem no banco de dados.
4.5.2 2. Testando o Candidato \(c_2 = \{Leite, Manteiga, Pão\}\)
Verificamos todos os seus subconjuntos de tamanho 2: - \(\{Leite, Manteiga\} \in L_2\)? Sim (contagem 3); - \(\{Leite, Pão\} \in L_2\)? Sim (contagem 3); - \(\{Manteiga, Pão\} \in L_2\)? NÃO!
No nível anterior, vimos que o par \(\{Manteiga, Pão\}\) apareceu em apenas 2 transações e foi reprovado. Pelo princípio da antimonotonicidade, se \(\{Manteiga, Pão\}\) não é frequente, é matematicamente impossível que o trio \(\{Leite, Manteiga, Pão\}\) seja frequente!
A Ação do Algoritmo: O candidato \(c_2 = \{Leite, Manteiga, Pão\}\) é PODADO IMEDIATAMENTE EM MEMÓRIA RAM. Ele é descartado sem que o algoritmo precise ler uma única linha de dados do disco!
4.6 Varredura Final e o Critério de Parada
Após a poda em RAM, apenas um único candidato sobreviveu em \(C_3\): \[C_3^{\text{filtrado}} = \{\{Café, Leite, Pão\}\}\]
Agora sim, realizamos a terceira varredura no banco de dados para computar a contagem real: - O trio \(\{Café, Leite, Pão\}\) aparece nas transações \(T_1\) e \(T_3\). - Contagem Real: \(2\) transações. - Suporte Real: \(s = 2/5 = 40\%\).
Como o suporte exigido é de pelo menos \(60\%\) (contagem \(\ge 3\)), o candidato não atinge o limiar e é reprovado.
Consequentemente: \[L_3 = \emptyset\]
4.6.1 O Critério de Parada
Como \(L_3\) é vazio, o algoritmo Apriori encerra sua execução imediatamente. Não há nenhum candidato para formar \(C_4\), poupando o sistema de testar quartetos ou quintetos.
O conjunto final de todos os itemsets frequentes da base é: \[L = L_1 \cup L_2 = \{\{Café\}, \{Leite\}, \{Manteiga\}, \{Pão\}, \{Café, Leite\}, \{Café, Pão\}, \{Leite, Manteiga\}, \{Leite, Pão\}\}\]
Em vez de avaliar \(31\) combinações e fazer dezenas de acessos a disco, o Apriori encontrou todos os itemsets frequentes com apenas \(3\) passadas pelo banco e com quase todas as combinações podadas em memória!
4.7 Da Poda de Itens à Extração de Regras
Uma vez que o algoritmo Apriori encerra e retorna o conjunto completo de todos os itemsets frequentes \(L = \bigcup_k L_k\), a tarefa subsequente é converter esses conjuntos em regras de associação acionáveis da forma: \[A \Rightarrow B, \quad \text{onde } A \subset I, \quad B = I \setminus A, \quad A \neq \emptyset, \quad B \neq \emptyset\]
Para cada itemset frequente \(I\) de tamanho \(|I| \ge 2\), existem \(2^{|I|} - 2\) partições possíveis em antecedente e consequente.
4.7.1 Exemplo Concreto Passo a Passo
Considere que o Apriori identificou como frequente o itemset de 3 produtos: \[I = \{Caf\acute{e}, Leite, P\tilde{a}o\} \quad \text{com suporte medido } s(I) = 0{,}30 \ (30\%)\]
Suponha que nas etapas anteriores tenhamos medido os suportes dos subconjuntos: - \(s(\{Caf\acute{e}, Leite\}) = 0{,}35\), \(s(\{Caf\acute{e}, P\tilde{a}o\}) = 0{,}40\), \(s(\{Leite, P\tilde{a}o\}) = 0{,}50\); - \(s(\{Caf\acute{e}\}) = 0{,}50\), \(s(\{Leite\}) = 0{,}60\), \(s(\{P\tilde{a}o\}) = 0{,}75\).
A partir de \(I\), geramos todas as 6 regras possíveis (\(2^3 - 2 = 6\)) e calculamos a confiança de cada uma:
| Tipo | Regra Candidata (\(A \Rightarrow B\)) | Suporte Conjunto \(s(I)\) | Suporte Antecedente \(s(A)\) | Confiança \(c = \frac{s(I)}{s(A)}\) |
|---|---|---|---|---|
| 1 item no consequente | \(\{Caf\acute{e}, Leite\} \Rightarrow \{P\tilde{a}o\}\) | \(0{,}30\) | \(0{,}35\) | \(\mathbf{85{,}7\%}\) |
| 1 item no consequente | \(\{Caf\acute{e}, P\tilde{a}o\} \Rightarrow \{Leite\}\) | \(0{,}30\) | \(0{,}40\) | \(\mathbf{75{,}0\%}\) |
| 1 item no consequente | \(\{Leite, P\tilde{a}o\} \Rightarrow \{Caf\acute{e}\}\) | \(0{,}30\) | \(0{,}50\) | \(\mathbf{60{,}0\%}\) |
| 2 itens no consequente | \(\{Caf\acute{e}\} \Rightarrow \{Leite, P\tilde{a}o\}\) | \(0{,}30\) | \(0{,}50\) | \(\mathbf{60{,}0\%}\) |
| 2 itens no consequente | \(\{Leite\} \Rightarrow \{Caf\acute{e}, P\tilde{a}o\}\) | \(0{,}30\) | \(0{,}60\) | \(\mathbf{50{,}0\%}\) |
| 2 itens no consequente | \(\{P\tilde{a}o\} \Rightarrow \{Caf\acute{e}, Leite\}\) | \(0{,}30\) | \(0{,}75\) | \(\mathbf{40{,}0\%}\) |
4.7.2 A Poda na Geração de Regras (Rule Pruning)
Repare no padrão matemático da tabela: em todas as regras geradas a partir do mesmo itemset \(I\), o numerador da confiança é idêntico (\(s(I) = 0{,}30\)). O único elemento que varia é o denominador \(s(A)\).
Pela antimonotonicidade do suporte: \[A' \subset A \implies s(A') \ge s(A) \implies \frac{s(I)}{s(A')} \le \frac{s(I)}{s(A)} \implies c(A' \Rightarrow (I \setminus A')) \le c(A \Rightarrow (I \setminus A))\]
A consequência prática é imediata: Mover itens do antecedente para o consequente (ou seja, diminuir \(A\)) só pode diminuir a confiança. Se fixarmos um limiar de confiança mínima \(c_{\min} = 70\%\): - Como \(\{Leite, P\tilde{a}o\} \Rightarrow \{Caf\acute{e}\}\) atinge apenas \(60{,}0\% < 70\%\), podemos deduzir matematicamente que as regras derivadas \(\{Leite\} \Rightarrow \{Caf\acute{e}, P\tilde{a}o\}\) (\(50\%\)) e \(\{P\tilde{a}o\} \Rightarrow \{Caf\acute{e}, Leite\}\) (\(40\%\)) jamais atingirão \(70\%\). - Elas são descartadas antecipadamente sem necessidade de consulta ou cálculo!
4.8 Aplicação Prática: Minerando Transações de Mercado
Executamos agora o algoritmo Apriori sobre a nossa base transacional de mercado (transacoes_mercado), configurando suporte mínimo \(s_{\min} = 0{,}20\) (\(20\%\)) e confiança mínima \(c_{\min} = 0{,}60\) (\(60\%\)).
A tabela abaixo exibe as regras de associação mineradas, ordenadas pelo Lift decrescente:
# Exibição das regras mineradas pelo algoritmo Apriori
print(f"Total de regras mineradas: {len(df_regras_pratico)}")
df_regras_display = df_regras_pratico.copy()
df_regras_display["Suporte"] = df_regras_display["Suporte"].apply(lambda v: brl(v, 2))
df_regras_display["Confiança"] = df_regras_display["Confiança"].apply(lambda v: brl(v, 2))
df_regras_display["Lift"] = df_regras_display["Lift"].apply(lambda v: brl(v, 2))
df_regras_display.head(8)Total de regras mineradas: 7| Antecedente | Consequente | Suporte | Confiança | Lift | |
|---|---|---|---|---|---|
| 0 | Cerveja | Fralda | 0,25 | 0,83 | 2,38 |
| 1 | Fralda | Cerveja | 0,25 | 0,71 | 2,38 |
| 2 | Manteiga | Pão | 0,35 | 0,87 | 1,46 |
| 3 | Café | Pão | 0,25 | 0,83 | 1,39 |
| 4 | Manteiga | Leite | 0,25 | 0,62 | 1,39 |
| 5 | Leite, Manteiga | Pão | 0,20 | 0,80 | 1,33 |
| 6 | Leite | Pão | 0,35 | 0,78 | 1,30 |
Repare nos resultados práticos obtidos: - A regra clássica \(\{Cerveja\} \Rightarrow \{Fralda\}\) atinge \(\text{Lift} = 2{,}14\), com suporte de \(25\%\) e confiança de \(71\%\). - As combinações de café da manhã \(\{Leite, Manteiga\} \Rightarrow \{P\tilde{a}o\}\) atingem confiança de \(100\%\) (\(c = 1{,}00\)) e \(\text{Lift} = 1{,}43\).
Essas regras são acionáveis no varejo para decisões operacionais de sortimento e cross-selling. No entanto, o algoritmo Apriori funciona estritamente como um gerador exaustivo de candidatos: ele produz uma lista plana de regras empíricas sem qualquer hierarquia ou filtro de causalidade estatística. Ele não nos diz: 1. Quais regras refletem dependências diretas e quais são meros atalhos transitivos redundantes (\(A \Rightarrow B\) e \(B \Rightarrow C\) tornam \(A \Rightarrow C\) desnecessária?); 2. Quais regras decorrem de causas comuns não observadas (correlações espúrias, como no nosso exemplo do Café e da Torradeira); 3. Quais regras surgem de vieses de seleção ao recortar a base de clientes.
Para validar, filtrar e estruturar essa lista de regras candidatas, precisamos do ferramental formal dos Modelos Gráficos Probabilísticos (PGMs).
4.9 Pausa 3: A Poda do Apriori e a Mineração Prática
DicaV ou F: Mecânica do Algoritmo Apriori
Julgue V ou F — a questão só conta se acertar os 4 itens:
- □ No algoritmo Apriori, o passo de poda (prune step) exige varrer novamente o banco de dados em disco para checar a frequência dos subconjuntos.
- □ Se um candidato de tamanho 3 tem um subconjunto de tamanho 2 que não está em \(L_2\), ele é descartado imediatamente pela antimonotonicidade.
- □ O algoritmo Apriori garante encontrar todos os itemsets frequentes da base de dados para o limiar \(s_{\min}\) escolhido.
- □ Se uma base transacional contiver \(1\) milhão de compras, o Apriori realizará \(1\) milhão de varreduras na base de dados.
5 Bloco 3: Redes Bayesianas como Filtro Estrutural de Regras
5.1 O DAG como Mapa de Dependências
Na primeira metade da aula, vimos que o Apriori gera uma lista plana de regras empíricas candidatas. Mas como saber quais dessas regras refletem conexões diretas genuínas e quais são meras ilusões estatísticas?
A resposta natural seria modelar a distribuição de probabilidade conjunta de todas as variáveis da loja. No entanto, para um catálogo de apenas \(K=30\) produtos, uma tabela conjunta irrestrita exigiria especificar: \[2^{30} - 1 = \mathbf{1.073.741.823 \text{ parâmetros livres (mais de 1 bilhão!)}}\] Nenhum banco de dados no mundo tem transações suficientes para estimar 1 bilhão de probabilidades por força bruta.
É aqui que entram os Modelos Gráficos Probabilísticos Direcionados, conhecidos como Redes Bayesianas (Bishop, 2006, Cap. 8; Pearl, 1988). A premissa central de um Grafo Acíclico Direcionado (DAG) é elegante e intuitiva: uma variável não precisa olhar para todo o histórico do universo: basta olhar para os seus pais imediatos no grafo (\(\text{pa}_k\)).
Na prática do aprendizado não supervisionado, o DAG funciona como um mapa visual rigoroso: - Nós: Produtos ou variáveis de contexto (\(A, B, C, \dots\)); - Arestas direcionadas (\(A \to B\)): Relações diretas de dependência ou atração; - Ausência de arestas: Declaração formal de independência condicional! Duas variáveis sem aresta direta tornam-se condicionalmente independentes quando controlamos pelos seus pais ou mediadores intermediários.
5.2 As Três Geometrias Canônicas do Fluxo de Informação
A propriedade mais poderosa dos Modelos Gráficos Probabilísticos é a capacidade de ler independências condicionais diretamente a partir da topologia do grafo (PRML §8.2; Pearl, 1988).
Dizemos que duas variáveis \(A\) e \(B\) são condicionalmente independentes dado \(C\), denotado por \(A \perp\!\!\!\perp B \mid C\), se: \[p(A, B \mid C) = p(A \mid C) p(B \mid C) \quad \iff \quad p(A \mid B, C) = p(A \mid C)\] Em termos práticos: conhecer o estado de \(B\) não adiciona nenhuma informação nova sobre \(A\) quando o estado de \(C\) já é conhecido.
Em caminhos de 3 variáveis, existem exatamente três geometrias canônicas que determinam se o canal de informação está aberto ou bloqueado:
- Cadeia (Head-to-tail): \(A \to B \to C\)
- Sem condicionamento: O canal está aberto (\(A \not\perp\!\!\!\perp C\)). A informação flui de \(A\) para \(C\) passando por \(B\).
- Condicionando em \(B\): O canal é bloqueado (\(\mathbf{A \perp\!\!\!\perp C \mid B}\)). Uma vez que conhecemos o estado do intermediário \(B\), a variável \(A\) não acrescenta informação sobre \(C\).
- Causa Comum (Tail-to-tail): \(A \leftarrow B \to C\)
- Sem condicionamento: O canal está aberto (\(A \not\perp\!\!\!\perp C\)). Ambas as variáveis variam juntas porque compartilham a mesma causa comum \(B\) (como Café Gourmet e Torradeira induzidos por alta Renda).
- Condicionando em \(B\): O canal é bloqueado (\(\mathbf{A \perp\!\!\!\perp C \mid B}\)). Ao controlar pela causa comum, a correlação espúria se dissipa completamente.
- Colisor (Head-to-head): \(A \to C \leftarrow B\)
- Sem condicionamento: O canal está naturalmente bloqueado (\(\mathbf{A \perp\!\!\!\perp B}\)). Duas causas independentes que geram um mesmo efeito comum não têm nenhuma correlação entre si.
- Condicionando em \(C\) (ou em descendentes de \(C\)): O canal é aberto (\(\mathbf{A \not\perp\!\!\!\perp B \mid C}\)) pelo fenômeno de Explaining Away! Quando o efeito comum \(C\) é observado, confirmar uma causa reduz a necessidade da outra, induzindo dependência estatística artificial entre elas.
5.3 Comparação das Três Geometrias Canônicas
A tabela e o diagrama a seguir consolidam a geometria completa do fluxo de informação em redes bayesianas de 3 nós:
| Geometria | Grafo | Sem Condicionamento | Condicionado no Nó Central (\(B\) ou \(C\)) |
|---|---|---|---|
| Cadeia (Head-to-tail) | \(A \to B \to C\) | Aberto (\(A \not\perp\!\!\!\perp C\)) | Bloqueado: \(\mathbf{A \perp\!\!\!\perp C \mid B}\) |
| Causa Comum (Tail-to-tail) | \(A \leftarrow B \to C\) | Aberto (\(A \not\perp\!\!\!\perp C\)) | Bloqueado: \(\mathbf{A \perp\!\!\!\perp C \mid B}\) |
| Colisor (Head-to-head) | \(A \to C \leftarrow B\) | Bloqueado: \(\mathbf{A \perp\!\!\!\perp B}\) | Aberto: \(\mathbf{A \not\perp\!\!\!\perp B \mid C}\) |
5.4 As Geometrias Canônicas como Filtro de Regras
Agora podemos conectar formalmente os dois universos da aula: como usar a teoria das estruturas canônicas para validar, filtrar e organizar as regras empíricas geradas pelo algoritmo Apriori?
Em bases reais de varejo, o Apriori gera centenas ou milhares de regras candidatas que superam os limiares de suporte e confiança. Em vez de aceitar passivamente essa lista plana ou tentar aprender um DAG global de 50 nós por força bruta (o que é computacionalmente proibitivo), realizamos testes locais de independência condicional sobre os candidatos minerados.
Vejamos exatamente o que é feito com a relação candidata em cada uma das três geometrias:
5.4.1 1. Filtragem de Regras Espúrias (Causa Comum: \(A \leftarrow B \to C\))
- O Candidato do Apriori: O algoritmo aponta a regra direta \(\{Café\} \Rightarrow \{Torradeira\}\) com alto suporte, alta confiança e \(\text{Lift} = 2{,}69\).
- O Teste Gráfico: Testamos a independência condicional controlando pela variável de contexto socioeconômico \(B\) (Perfil de Renda): \[P(Café, Torradeira \mid Renda) \stackrel{?}{=} P(Café \mid Renda) \cdot P(Torradeira \mid Renda)\]
- O Que é Feito com a Relação:
- No Grafo (DAG): Constatado que \(Café \perp\!\!\!\perp Torradeira \mid Renda\), eliminamos a aresta direta entre Café e Torradeira. O DAG não terá aresta entre eles; apenas arestas originadas na causa comum: \(Renda \to Café\) e \(Renda \to Torradeira\).
- No Sistema de Recomendação: A regra direta é descartada. Se recomendarmos torradeiras para quem comprou café, a taxa de conversão será decepcionante porque o café não atrai torradeiras. A recomendação correta deve ser contextualizada pela causa comum (oferecer itens premium apenas a clientes de maior poder aquisitivo).
5.4.2 2. Poda de Regras Redundantes (Cadeia / Transitividade: \(A \to B \to C\))
- Os Candidatos do Apriori: O algoritmo extrai três regras simultâneas sobre a mesma cesta: \[\{Manteiga\} \Rightarrow \{Pão\}, \quad \{Pão\} \Rightarrow \{Café\}, \quad \text{e} \quad \{Manteiga\} \Rightarrow \{Café\}\]
- O Teste Gráfico: Avaliamos se o intermediário \(B\) (\(Pão\)) bloqueia a transmissão de informação entre os extremos: \[P(Café \mid Pão, Manteiga) \stackrel{?}{=} P(Café \mid Pão)\]
- O Que é Feito com a Relação:
- No Grafo (DAG): Comprovado que \(Manteiga \perp\!\!\!\perp Café \mid Pão\), podamos a aresta direta \(\{Manteiga\} \to \{Café\}\). Mantemos apenas as arestas adjacentes da cadeia: \(Manteiga \to Pão\) e \(Pão \to Café\).
- No Sistema de Recomendação: A regra de atalho é arquivada como redundante. Não sobrecarregamos a interface do cliente recomendando tudo de uma vez. O sistema sugere o próximo complemento imediato (\(Pão\)); uma vez que o pão é adicionado à cesta, o sistema sugere o café. O pipeline de recomendações ganha clareza sequencial e evita repetições cansativas.
5.4.3 3. Proteção contra Falsas Associações por Seleção (Colisor: \(A \to C \leftarrow B\))
- O Cenário e a Armadilha: Na população geral de clientes, \(\{Fraldas\}\) e \(\{Vinho\}\) são itens independentes (\(A \perp\!\!\!\perp B\)). Contudo, se um analista filtrar a base de dados considerando apenas compras de tíquete elevado ou clientes do programa “Supermercado VIP” (\(C=1\)), o efeito comum é condicionado.
- O Teste Gráfico: Pelo fenômeno de explaining away, condicionar no colisor \(C\) abre o canal e faz os itens parecerem correlacionados na subamostra (\(A \not\perp\!\!\!\perp B \mid C=1\)).
- O Que é Feito com a Relação:
- No Grafo (DAG): Mantemos \(A\) e \(B\) estritamente desconectados (\(A \perp\!\!\!\perp B\)). Orientamos ambas as setas convergindo para o colisor: \(Fraldas \to CestaVIP \leftarrow Vinho\).
- No Sistema de Recomendação: Rejeitamos a regra para a loja ampla. Não criamos promoções cruzadas entre Fraldas e Vinho na loja física geral, pois essa regra foi um artefato criado pelo recorte amostral. Evitamos investimentos promocionais em falsas sinergias.
| Situação no Apriori | Teste Estatístico | Geometria | Ação no Grafo (DAG) | Decisão no Sistema / Negócio |
|---|---|---|---|---|
| Regra isolada com alto Lift: \(A \Rightarrow C\) | \(A \perp\!\!\!\perp C \mid B\) | Causa Comum (\(A \leftarrow B \to C\)) | Eliminar aresta direta (\(A - C\)) | Descartar regra (Correlação Espúria) |
| Triângulo de regras: \(A \Rightarrow B, B \Rightarrow C, A \Rightarrow C\) | \(A \perp\!\!\!\perp C \mid B\) | Cadeia (\(A \to B \to C\)) | Podar atalho transitivo (\(A \to C\)) | Arquivar redundância (Manter fluxo linear) |
| Regra detectada apenas em subamostra | \(A \not\perp\!\!\!\perp B \mid C\) | Colisor (\(A \to C \leftarrow B\)) | Manter nós desconectados (\(A \perp\!\!\!\perp B\)) | Rejeitar promoção geral (Viés de Seleção) |
5.5 Pausa 4: As Geometrias Canônicas como Filtro de Regras
DicaO Alarme e o Terremoto
Considere três variáveis: \(A\) (Ocorreu um terremoto), \(B\) (Houve uma tentativa de assalto) e \(C\) (O alarme da casa tocou). Terremotos e assaltos são independentes na natureza (\(A \perp\!\!\!\perp B\)).
Se você estiver viajando e receber uma notificação de que o alarme tocou (\(C=1\)), e dez segundos depois ouvir no rádio que um terremoto acabou de ocorrer na sua cidade (\(A=1\)), o que acontece com a probabilidade de que sua casa tenha sido assaltada (\(B=1\))?
DicaV ou F: As Três Geometrias Canônicas
Julgue V ou F — a questão só conta se acertar os 4 itens:
- □ Na cadeia \(A \to B \to C\), condicionar no nó intermediário \(B\) torna \(A\) e \(C\) condicionalmente independentes (\(A \perp\!\!\!\perp C \mid B\)).
- □ Na causa comum \(A \leftarrow B \to C\), condicionar em \(B\) induz dependência espúria entre \(A\) e \(C\).
- □ No colisor \(A \to C \leftarrow B\), as causas \(A\) e \(B\) são marginalmente independentes sem nenhum condicionamento (\(A \perp\!\!\!\perp B\)).
- □ Se \(C\) for um colisor entre \(A\) e \(B\), condicionar no nó \(C\) (ou em qualquer de seus descendentes) mantém o caminho bloqueado.
6 Bloco 4: Montando o Grafo e os Limites dos Dados Observacionais
6.1 Montando o Grafo por Componentes Locais
Uma das dúvidas mais naturais ao estudar Redes Bayesianas é: como sair da lista de regras do Apriori e chegar ao grafo geral de dependências da loja sem se perder na explosão combinatória?
Tentar testar todos os DAGs possíveis para um catálogo de 30 ou 50 produtos é computacionalmente intratável (o espaço de grafos cresce super-exponencialmente). A solução moderna, inspirada em algoritmos baseados em restrições como o algoritmo PC (Spirtes, Glymour & Scheines, 2000), consiste em construir o grafo por montagem de componentes locais:
- Esqueleto Inicial via Apriori: Em vez de começar com todas as conexões possíveis, usamos os pares frequentes minerados pelo Apriori (\(L_2\)) como o esqueleto inicial de arestas não direcionadas candidatas.
- Poda Local de Espúrios e Transitividades: Para cada aresta candidata \(A - C\), testamos a independência condicional \(A \perp\!\!\!\perp C \mid B\) condicionando nos possíveis intermediários ou causas comuns \(B\). Se a independência for confirmada:
- Se \(B\) for causa comum (\(A \leftarrow B \to C\)), descartamos a aresta direta (remoção de correlação espúria);
- Se \(B\) for mediador (\(A \to B \to C\)), podamos a aresta direta (remoção de atalho transitivo redundante).
- Orientação dos Colisores Unívocos: Se duas variáveis \(A\) e \(B\) eram independentes (\(A \perp\!\!\!\perp B\)), mas tornam-se dependentes ao condicionar em um vizinho compartilhado \(C\) (\(A \not\perp\!\!\!\perp B \mid C\)), identificamos uma v-structure não blindada e orientamos as setas convergentes de forma unívoca: \[A \longrightarrow C \longleftarrow B\]
- Grafo Essencial (CPDAG): As arestas que fazem parte de colisores recebem direções fixas, enquanto as demais permanecem não orientadas, formando a classe de equivalência observacional.
6.2 Exemplo Prático: Da Lista de Regras ao DAG
Para compreender concretamente como sair de uma lista de regras do Apriori e chegar ao grafo, acompanhemos um exemplo prático com cinco variáveis monitoradas em \(50.000\) transações de um supermercado: - \(R\): Perfil de Renda Alta (variável de contexto) - \(C\): Café Gourmet - \(T\): Torradeira Elétrica - \(P\): Pão Francês - \(M\): Manteiga
6.2.1 1. O Ponto de Partida: As Regras Brutas do Apriori
O algoritmo Apriori varreu a base transacional e retornou seis regras de associação frequentes que superaram os limiares mínimos de suporte e confiança: 1. \(\{R\} \Rightarrow \{C\}\) (\(\text{Lift} = 2{,}5\)) 2. \(\{R\} \Rightarrow \{T\}\) (\(\text{Lift} = 2{,}8\)) 3. \(\{C\} \Rightarrow \{T\}\) (\(\text{Lift} = 2{,}69\)) — Candidata a correlação espúria! 4. \(\{P\} \Rightarrow \{M\}\) (\(\text{Lift} = 2{,}2\)) 5. \(\{M\} \Rightarrow \{C\}\) (\(\text{Lift} = 1{,}8\)) 6. \(\{P\} \Rightarrow \{C\}\) (\(\text{Lift} = 1{,}7\)) — Candidata a atalho redundante!
Se parássemos no Apriori, o supermercado tentaria ativar seis promoções e recomendações diferentes. Veja como o processo de montagem por restrições locais organiza essas regras:
6.2.2 2. Passo 1: Construção do Esqueleto Inicial (Arestas Não Direcionadas)
Convertemos cada uma das seis regras frequentes em uma aresta não direcionada no grafo: \[\text{Esqueleto} = \{ R - C, \quad R - T, \quad C - T, \quad P - M, \quad M - C, \quad P - C \}\] Neste estágio, o grafo inicial é ruidoso e contém dois triângulos densos: \(\{R, C, T\}\) e \(\{P, M, C\}\).
6.2.3 3. Passo 2: Poda de Causa Comum (Filtro de Espúrios)
Analisamos o triângulo \(\{R, C, T\}\). Testamos a independência condicional entre \(C\) e \(T\) controlando pela variável comum \(R\): \[P(C, T \mid R) = P(C \mid R) P(T \mid R) \implies \mathbf{C \perp\!\!\!\perp T \mid R}\] - O que acontece: A aresta direta \(C - T\) é removida do esqueleto! A regra \(\{C\} \Rightarrow \{T\}\) é descartada do catálogo. Restam apenas as arestas legítimas ligadas à causa comum: \(R - C\) e \(R - T\).
6.2.4 4. Passo 3: Poda de Transitividade (Cadeia)
Analisamos o triângulo \(\{P, M, C\}\). Testamos se a compra de manteiga \(M\) atua como intermediário entre \(P\) e \(C\): \[P(C \mid P, M) = P(C \mid M) \implies \mathbf{P \perp\!\!\!\perp C \mid M}\] - O que acontece: A aresta \(P - C\) é um atalho redundante e é podada! Resta a cadeia linear limpa: \(P - M\) e \(M - C\).
6.2.5 5. Passo 4: Orientação e Obtenção do DAG Final
- O perfil de renda é uma característica socioeconômica prévia do cliente, orientando as causas comuns: \(R \to C\) e \(R \to T\).
- Na cesta matinal, a ordem de decisão de consumo orienta a cadeia: \(P \to M \to C\).
- O Resultado: Das 6 regras ruidosas iniciais, o processo converge para um DAG com apenas 4 arestas essenciais, sem correlações espúrias e sem atalhos repetitivos!
6.3 I-Equivalência e o Limite Epistemológico Observacional
Chegamos à questão metodológica decisiva do aprendizado não supervisionado: podemos descobrir relações de causa e efeito genuínas apenas observando matrizes de dados passivos?
A resposta teórica é não. Considere os três grafos a seguir: 1. \(A \to B \to C\) (Cadeia direta) 2. \(A \leftarrow B \leftarrow C\) (Cadeia reversa) 3. \(A \leftarrow B \to C\) (Causa comum)
Todos os três modelos codificam exatamente a mesma declaração de independência condicional: \(A \perp\!\!\!\perp C \mid B\). Nenhuma massa de dados puramente observacionais, por maior que seja o número de transações \(N\), consegue distinguir esses três grafos.
O colisor \(A \to C \leftarrow B\) é a única estrutura de 3 nós observacionalmente unívoca, pois codifica \(A \perp\!\!\!\perp B\) e \(A \not\perp\!\!\!\perp B \mid C\). Em contrapartida, cadeias e causas comuns pertencem à mesma classe de equivalência de Markov.
6.3.1 O Teto Observacional e a Intervenção Ativa
Essa equivalência define o teto epistemológico do aprendizado puramente observacional: - Com dados passivos, aprendemos o esqueleto e a orientação dos colisores; - Para desvendar a direção das arestas restantes e afirmar causalidade real (“\(A\) causa a compra de \(B\)”), é indispensável recorrer ao operador \(do(x)\) de Pearl — ou seja, realizar intervenções experimentais ativas (como um Teste A/B alterando preço, posicionamento ou estoque de \(A\) e medindo a resposta em \(B\)).
6.4 Pausa 5: Componentes do Grafo e o Teto Observacional
DicaO Teto dos Dados Passivos
Suponha que, analisando 500 mil transações de varejo com os produtos \(A\), \(B\) e \(C\), seus testes estatísticos comprovem rigorosamente que \(A \perp\!\!\!\perp C \mid B\), e nenhuma outra independência exista. É possível afirmar apenas com esses dados se \(A\) causa \(B\) ou se \(B\) causa \(A\)? O que seria necessário fazer na loja para desvendar a seta com certeza científica?
DicaV ou F: Componentes e Equivalência Observacional
Julgue V ou F — a questão só conta se acertar os 4 itens:
- □ O Apriori fornece o esqueleto inicial de conexões frequentes, enquanto os testes locais de independência condicional podam regras espúrias e atalhos transitivos.
- □ Dois DAGs com o mesmo esqueleto e as mesmas v-structures pertencem à mesma classe de equivalência de Markov e são indistinguíveis por dados puramente observacionais.
- □ O grafo de colisor \(A \to B \leftarrow C\) gera a mesma distribuição de independência condicional que a cadeia \(A \to B \to C\).
- □ Apenas com dados passivos de compras de supermercado, sem qualquer experimento ativo (\(do(x)\)), é sempre possível determinar a direção de causa e efeito de todas as arestas do grafo.
7 Fechamento
7.1 A Síntese: Do Candidato Bruto aos Componentes Validados
Nesta aula, articulamos dois pilares metodológicos fundamentais para lidar com dados discretos e transacionais:
O Algoritmo Apriori como Gerador Eficiente de Candidatos: A força do Apriori reside na propriedade de antimonotonicidade do suporte. Ele consegue varrer milhões de cestas de compras esparsas e encontrar de forma exaustiva todas as associações frequentes que superam os limiares mínimos. No entanto, o Apriori entrega uma tabela plana de regras empíricas, sem distinção entre causas reais, atalhos redundantes e correlações espúrias.
Modelos Gráficos Probabilísticos como Filtro e Validador Estrutural: As Redes Bayesianas e a independência condicional fornecem a régua formal para testar a validade de cada regra candidata:
- Bifurcação / Causa Comum (\(A \leftarrow B \to C\)): filtra e descarta regras diretas espúrias quando \(A \perp\!\!\!\perp C \mid B\);
- Cadeia / Transitividade (\(A \to B \to C\)): poda atalhos diretos redundantes quando o intermediário bloqueia o fluxo (\(A \perp\!\!\!\perp C \mid B\));
- Colisor (\(A \to C \leftarrow B\)): alerta contra regras artificiais originadas por viés de seleção e condicionamento em efeitos comuns.
Construção do Grafo por Montagem de Componentes Locais: Em vez de nos perdermos na armadilha combinatória intratável de tentar ajustar um DAG global completo a partir de \(2^K - 1\) parâmetros, construímos o grafo geral validando cada componente local. O resultado observacional rigoroso é o Grafo Essencial (CPDAG): esqueleto despoluído de transitividades e espúrios, com colisores unicamente orientados.
7.2 Retomando as Quatro Perguntas
- Como formalizar matematicamente transações, Suporte, Confiança e a Antimonotonicidade? Transações são vetores binários \(\mathbf{x} \in \{0, 1\}^D\). O suporte \(s(I)\) é a frequência conjunta empírica. Pela antimonotonicidade (\(A \subseteq B \implies s(B) \le s(A)\)), subconjuntos infrequentes garantem a infrequência de qualquer superconjunto. O Lift é comutativo e falha perante variáveis de confusão latentes (Paradoxo de Simpson).
- Como o algoritmo Apriori opera na prática para podar o espaço de busca combinatorial? Gera candidatos por junção \(L_{k-1} \bowtie L_{k-1}\), descarta candidatos cujos subconjuntos de tamanho \(k-1\) não estejam em \(L_{k-1}\) na memória RAM antes de acessar o disco, e varre a base apenas para os candidatos sobreviventes.
- Como as Redes Bayesianas e as três geometrias canônicas filtram regras do Apriori? Sob um DAG, a conjunta fatora nos pais imediatos (\(p(\mathbf{x}) = \prod_k p(x_k \mid \text{pa}_k)\)), reduzindo parâmetros de \(2^K\) para \(O(K \cdot 2^m)\). As três geometrias canônicas atuam como filtros estruturais: a Causa Comum (\(A \leftarrow B \to C\)) descarta regras espúrias, a Cadeia (\(A \to B \to C\)) poda atalhos redundantes, e o Colisor (\(A \to C \leftarrow B\)) previne armadilhas de seleção e explaining away.
- Como montar o grafo de dependências e quais são os limites da observação passiva? Construímos o grafo validando componentes locais (esqueleto do Apriori \(\to\) testes de independência \(\to\) colisores unívocos), gerando o Grafo Essencial (CPDAG). Pelo Teorema de I-Equivalência de Markov (Verma & Pearl, 1990), dados observacionais passivos não determinam a direção causal de arestas reversíveis; a causalidade plena exige intervenções experimentais ativas (\(do(x)\), teste A/B).
7.3 O Que Fica em Aberto e Limitações
- Complexidade do Aprendizado de Estrutura: Aprender a estrutura do DAG a partir de dados observacionais é um problema NP-difícil; algoritmos como o PC ou métodos baseados em pontuação (BIC/BDeu) utilizam aproximações gulosas.
- Variáveis Latentes não Observadas: Quando causas comuns não são medidas na base de dados, a equivalência de Markov exige extensões como Grafos Acíclicos Ancestrais (MAGs/PAGs).
- Esparsidade Extrema em Catálogos Massivos: Em sistemas de recomendação com milhões de itens e matrizes com mais de \(99\%\) de entradas ausentes, modelos gráficos tabulares tornam-se densos demais.
DicaPonte para a Aula 10
Nesta aula, modelamos dependências entre variáveis discretas através de regras de associação e redes bayesianas.
Na próxima aula (Aula 10: Sistemas de Recomendação — Fatoração de Matrizes: SVD e NMF), enfrentaremos o problema da esparsidade extrema sob a perspectiva de fatores latentes contínuos e matriciais. Investigaremos como decompor matrizes massivas e incompletas utilizando Truncated SVD (Funk-SVD) e Fatoração de Matrizes Não Negativas (NMF), demonstrando como restrições de positividade produzem representações aditivas naturais e altamente interpretáveis.