Marcus Sampaio
DSC/UFCG
Marcus Sampaio
DSC/UFCG
O Modelo
Marcus Sampaio
DSC/UFCG
• Dados:
– Um banco de dados 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
– Exemplo: 98% das pessoas que compram fraldas e comidas
infantis também compram cerveja.
– Qualquer número de ítens no consequente Y / antecedente X
de uma regra
– Regras com restrições (i.e., encontrar somente regras
envolvendo produtos importados caros)
Aplicações
•
•
•
•
Marcus Sampaio
DSC/UFCG
Perfis de clientes (“Market basket analysis”)
“Merchandizing”
Detecção de fraudes em seguros de saúde
Organização de produtos em vitrines de lojas
Confiança e Suporte
Marcus Sampaio
DSC/UFCG
• Uma regra deve ter uma confiabilidade mínina
(confidence), especificada pelo usuário
– 1 & 2 => 3 tem 90% de confiabilidade se quando
um cliente comprou 1 e 2, em 90% dos casos, ele
também comprou 3
• Problema: poucas regras – sem validade estatística
• Solução: o conceito de suporte
• Uma regra deve ter um suporte (support)
mínimo especificado
– 1 & 2 => 3 1, 2 e 3 devem aparecer em pelo
menos uma quantidade mínima
Marcus Sampaio
DSC/UFCG
Exemplo
• Exemplo 1
Transaction Id
1
2
3
4
Purchased Items
{1, 2, 3}
{1, 4}
{1, 3}
{2, 5, 6}
• Para suporte mínimo = 50%, e confiabilidade
mínima = 50%, temos as seguintes regras
– 1 => 3 com 50% de suporte e 66% de
confiabilidade
– 3 => 1 com 50% de suporte e 100% de
confiabilidade
Exemplo (2)
Marcus Sampaio
DSC/UFCG
• Exemplo 2
Transaction Id
1
2
3
4
Purchased Items
{1, 2, 3}
{1, 4}
{1, 3}
{2, 5, 6}
• Para suporte mínimo = 50%, e confiabilidade mínima
= 90%, temos as seguintes regras
– 1 => 3 com 50% de suporte e 66% de confiabilidade –
excluída
– 3 => 1 com 50% de suporte e 100% de confiabilidade
• Conclusão: regras de associação não são
comutativas
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
– Os usuários do algoritmo ganham confiança
– Algoritmos de mineração de dados geralmente são
muito simples, não requerendo técnicas de
inteligência artificial, como linguagens indutivas do
tipo Prolog
• Resultados inteligentes
• Algoritmos tradicionais, e mais importante, com bom
desempenho
• Veremos o seminal algoritmo Apriori
Apriori (2)
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 gerar as regras
• Fase leve, em termos de custos
Marcus Sampaio
DSC/UFCG
Apriori (3)
TID
1
2
3
4
Items
{1, 2, 3}
{1, 3}
{1, 4}
{2, 5, 6}
Frequent Itemset
{1}
{2}
{3}
{1, 3}
Suporte mínimo = 50%
Confiabilidade mínima = 50%
Support
75%
50%
50%
50%
Para a regra 1 => 3:
•Suporte = Suporte({1, 3}) = 50%
•Confiabilidade = Suporte({1,3})/Suporte({1}) = 66%
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
– Para cada X, Y  Fk
• Se (Suporte(Fk) / Suporte(X))  Confiança 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 de ítens candidato – Fk – em
Ck+1 deve ser removido (“pruned”) se
qualquer um dos seus subconjuntos não
estiver contido em Fk
Marcus Sampaio
DSC/UFCG
Exemplo
Banco de Dados BD
TID
1
2
3
4
F1
C1
Items
Varre BD
{1, 3, 4}
{2, 3, 5}
Suporte > 50%
{1, 2, 3, 5}
{2, 5}
Itemset
{1}
{2}
{3}
{4}
{5}
Sup.
2
3
3
1
3
C2
Varre BD
{2, 3}
{2, 5}
{3, 5}
Itemset
{2}
{3}
{5}
Sup.
3
3
3
F2
2
3
2
Itemset
{2, 5}
Sup.
3
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
Quantitativas
Marcus Sampaio
DSC/UFCG
• Atributos numéricos (i.e. idade, rendimentos)
• Atributos nominais ou categóricos (i.e. temperatura
alta)
CID
Age
Married NumCars
1
2
3
4
5
23
25
29
34
38
No
Yes
No
Yes
Yes
1
1
0
2
2
suporte mínimo = 40% confiabilidade mínima = 50%
• [Idade: 30..39] e [Casado: Sim] => [NumCarros:2]
Regras de Associação
com Restrições
Marcus Sampaio
DSC/UFCG
• Restrições são especificadas para focar
somente em partes do BD 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
• Pode descrever 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