Marcus Sampaio
DSC/UFCG
O Problema
Marcus Sampaio
DSC/UFCG
• Dados
– Um banco de transações de compra
– Cada transação é um conjunto de ítens comprados
• Encontrar todas as regras X => Y que
associam um conjunto de ítens X com outro
conjunto de ítens Y, com um certo grau de
confiabilidade
– Exemplo: 98% das pessoas que compram fraldas
e comidas infantis também compram cerveja
O Modelo de Regras
de Associação
Marcus Sampaio
DSC/UFCG
• Regras do tipo Se X então Y
– Outra representação: X  Y
–…
•X  Y = 
• Qualquer número de ítens no conseqüente
(Y)
• Qualquer número de ítens no antecedente (X)
• Cláusulas conjuntivas
– Antecedente e conseqüente
• Uma generalização de regras de classificação
Aplicações
Marcus Sampaio
DSC/UFCG
• Perfis de compra de clientes (“Market basket
analysis”)
• “Merchandizing”
• Organização de produtos em vitrines de lojas
Métricas de
Desempenho
• Um modelo induzido de Regras de
Associação deve ser avaliado
• Duas métricas de desempenho
– Suporte
– Confiança
Marcus Sampaio
DSC/UFCG
Confiança
Marcus Sampaio
DSC/UFCG
• Uma regra deve ter uma confiança
(“confidence”) mínina, especificada pelo
usuário
– 1 & 2 => 3  outra representação de regra de
associação  tem 90% de confiabilidade se
quando um cliente comprou 1 e 2, em 90% dos
casos, ele também comprou 3
• Só Confiança não é suficiente
– Problema: poucas regras – sem validade
estatística
– Solução: a métrica suporte, junto com confiança
Suporte
Marcus Sampaio
DSC/UFCG
• Uma regra deve ter um suporte (“support”)
mínimo especificado pelo usuário
– 1 & 2 => 3
• 1, 2 e 3 devem aparecer em pelo menos uma quantidade
mínima de transações de compra
Marcus Sampaio
DSC/UFCG
Exemplos
• Exemplo 1
Id Transaçao
1
2
3
4
Itens Comprados
{1, 2, 3}
{1, 4}
{1, 3}
{2, 5, 6}
• Para suporte mínimo = 50%, e confiança
mínima = 50%, temos as seguintes regras
– 1 => 3 com 50% de suporte e 66% de confiança
– 3 => 1 com 50% de suporte e 100% de confiança
Marcus Sampaio
DSC/UFCG
• Regras de Associação não são comutativas!
– O usuário especificou 40% de suporte mínimo, e
85% de confiança mínima
• Somente a regra 3 => 1
0,5 1,0 é válida
– Note esta outra representação de regra de associação,
com seu suporte e sua confiança
– Na WEKA, a representação é ainda um pouco diferente
Marcus Sampaio
DSC/UFCG
• Exemplo 2
Id Transação
1
2
3
4
Itens Comprados
{1, 2, 3}
{1, 4}
{1, 3}
{2, 5, 6}
• Para suporte mínimo = 50%, e confiança
mínima = 90%, temos as seguintes regras
– 3 => 1 com 50% de suporte e 100% de confiança
O Algortimo Apriori de
Regras de Associação
Marcus Sampaio
DSC/UFCG
• Há dois motivos fortes para mostrar como
funciona um algoritmo de regras de
associação, ou como funciona qualquer
algoritmo de Mineração de Dados
– Os usuários do algoritmo ganham confiança
– Algoritmos de mineração de dados geralmente são
muito simples, não requerendo técnologias de
inteligência artificial, como linguagens indutivas do
tipo Prolog
• Resultados inteligentes
• Algoritmos tradicionais, e mais importante, com bom
desempenho
Marcus Sampaio
DSC/UFCG
• Algoritmo Apriori
– Etapa 1: Encontrar todos os conjuntos de ítens
com suporte  mínimo — conjuntos de ítens
freqüentes
• Fase mais pesada, em termos de custos
• Muitos trabalhos de pesquisa em otimização
– Etapa 2: Uso dos conjuntos de ítens freqüentes
para induzir as regras de associação, com suporte
e confinaça acima dos mínimos especificados
• Fase leve, em termos de custos
Marcus Sampaio
DSC/UFCG
TID
1
2
3
4
Itens
{1, 2, 3}
{1, 3}
{1, 4}
{2, 5, 6}
Suporte mínimo = 50%
Confiança mínima = 50%
Conjunto Freqüente
{1}
{2}
{3}
{1, 3}
Suporte
75%
50%
50%
50%
Para a regra 1 => 3:
• Suporte = Suporte({1, 3}) = 50%
• Confiança = Suporte({1,3}) / Suporte({1}) = 66%
Marcus Sampaio
DSC/UFCG
• Regra geral para o cálculo da confiança, em
termos de suporte
– XY
• Confiança = Suporte (XY) / Suporte (X)
• XY  X, Y  X AND Y
• Confiança e Probabilidade Condicional
– Confiança = P(Y|X)
– Interpretação
• Probabilidade de Y acontecer, se X acontecer
Apriori - Etapa 1
•
•
•
•
Marcus Sampaio
DSC/UFCG
Fk : Conjuntos de ítens freqüentes de tamanho k
Ck : Conjuntos de ítens candidatos de tamanho k
F1 = {conjuntos de ítens de tamanho 1}
Para ( k=1; Fk != ; k++) faça {
Ck+1 = Novos candidatos gerados de Fk
Para cada transação t no banco de dados faça
Incremente o contador de todos os candidatos em
Ck+1 que estão contidos em t
Fk+1 = Candidatos em Ck+1 com suporte mínimo
}
• Saída: k Fk
Apriori - Etapa 2
Marcus Sampaio
DSC/UFCG
• Entrada: k Fk
• Para cada Fk  1
– Para cada X, Y  Fk
• Se (Suporte(Fk) / Suporte(X))  Confiança Mínima então
seleciona a regra X  Y
Otimização
Marcus Sampaio
DSC/UFCG
• Cada subconjunto do um conjunto de ítens
freqüente é também um conjunto de ítens
freqüente
• Um conjunto candidato de ítens deve ser
removido (“pruned”) se qualquer um dos seus
subconjuntos não for um Fk
Uma Instanciação do
Apriori
Marcus Sampaio
DSC/UFCG
Etapa 1: Suporte > 50%
Banco de Transações (BD)
TID
1
2
3
4
Itens
Varre BD
{1, 3, 4}
{2, 3, 5}
Suporte > 50%
{1, 2, 3, 5}
{2, 5}
F1
C1
It. Freq.
{1}
{2}
{3}
{4}
{5}
Sup.
2
3
3
1
3
C2
Varre BD
{2, 3}
{2, 5}
{3, 5}
It. Freq.
{2}
{3}
{5}
Sup.
3
3
3
F2
2
3
2
It. Freq.
{2, 5}
Sup.
3
Marcus Sampaio
DSC/UFCG
• Etapa 2
– Entrada: {2,5}
• 2 => 5?
– Suporte {2,5} / Suporte {2} = 3 / 3 = 100%
• 5 => 2?
– Suporte {2,5} / Suporte {5} = 3 / 3 = 100%
– Regras Induzidas
• 2 => 5 1,0 1,0
• 5 => 2 1,0 1,0
A Família Apriori
Marcus Sampaio
DSC/UFCG
• O algoritmo Apriori é *seminal*
– Inspirou muitos outros algoritmos de regra de
associação
– Essas variações constituem a família de
algoritmos Apriori
• Algumas variações diferem do Apriori com
relação à abordagem
– Apriori: consulta aberta
– Variações: consultas semi-abertas
• Algoritmos parametrizados
• Outras variações exploram o caráter temporal
das transações
Regras de Associação
Generalizadas
Marcus Sampaio
DSC/UFCG
• Hierarquias de ítens
vestuário
outwear
jaquetas
camisas
calças
calçados
sapatos
botas
• Associações através de hierarquias
– A regra vestuário => calçados pode ser válida
mesmo que vestuário => botas não seja válida
Regras de Associação
com Restrições
Marcus Sampaio
DSC/UFCG
• Restrições são especificadas para focar
somente em partes de interesse
– Exemplo: encontrar regras de associação em que
os preços dos ítens são no máximo 200 reais
Regras de Associação
Temporais
Marcus Sampaio
DSC/UFCG
• Descrevem o rico caráter temporal dos dados
• Exemplo
– {fralda}  {cerveja} (suporte = 5%, confiabilidade
= 87%)
– O suporte desta regra pode saltar para 25% aos
sábados de manhã
Padrões de Seqüência
Marcus Sampaio
DSC/UFCG
• Dadas
– Uma seqüência de transações de clientes
– Cada transação é um conjunto de ítens
• Encontrar os padrões das seqüências de
transações desses clientes
• Exemplo: 10% dos clientes que compraram
um PC fizeram um “upgrade” da memória do
PC em uma transação subsequente
– 10% é o suporte dos padrões de seqüência