Universidade Federal do Pará
Programa de Pós-Graduação em Engenharia Elétrica
Fundamentos Matemáticos da Mineração de Dados
Fast Algorithms for Mining
Association Rules
Rakesh Agrawal
Ramakrishnan Srikant
IBM Almaden Research Center
Proceedings of 20th International
Conference on Very Large Data Bases,
September 12-15, 1994, Santiago de Chile,
Chile
1994
Artur Tupiassú
Fabíola Oliveira
Dezembro/2004
Roteiro da Apresentação
Objetivos dos autores;
Regras de associação;
Mineração de regras de associação;

Algoritmos Apriori , AprioriTid,

Descoberta de Regras;
AprioriHybrid;
Experimentos e resultados;
Conclusões.
Objetivos
Apresentação de novos algoritmos
para a mineração de regras de
associação entre itens em um banco
de dados de vendas (basket data);
Realização de experimentos com
dados sintéticos ilustrando a
performance dos algoritmos.
Regras de Associação
Representação: supermercado
Itens: banana, disquete, pizza, vinho e queijo.
Transações de venda:
100
200
TID
100
200
300
400
300
items
{banana,disquete,pizza}
{queijo,disquete,vinho}
{banana,queijo,disquete,vinho}
{queijo,vinho}
400
Regras de Associação:
Representação Formal
I = {i1,i2, … , im } é um conjunto de literais
chamados itens;

Ex.: I = {banana, disquete, queijo, vinho, pizza};
D = {T1,T2, …, Tn} é um conjunto de
transações com Ti  I;

Ex.: T100 = {banana, disquete, queijo};
Uma transação T contém um conjunto de
itens (Itemset) X se X  T

Ex. T100  X = {banana, disquete};
Regras de Associação:
Representação Formal
Uma regra de associação é uma implicação do
tipo: X  Y, onde os conjuntos de itens X e Y  I, X
 Y = ;
 Ex. {banana,disquete}  {queijo,vinho}
A regra X  Y apresenta-se no conjunto de
transações D com uma confiança c se c% das
transações em D que contém X também contém Y
 Ex. {banana,disquete}  {queijo,vinho}
TID
100
200
300
400
items
{banana,disquete,pizza}
{queijo,disquete,vinho}
{banana,queijo,disquete,vinho}
{queijo,vinho}
Confiança: 1/2 = 50%
Representação Formal
A regra X  Y tem suporte s no
conjunto de transações D se s% das
transações em D contém X  Y

TID
100
200
300
400
Ex. {banana, disquete}  {queijo, vinho}
items
{banana,disquete,pizza}
{queijo,disquete,vinho}
{banana,queijo,disquete,vinho}
{queijo,vinho}
Suporte: 1/4 = 25%
Mineração de Regras de
Associação
Algoritmo Apriori;
Algoritmo AprioriTid;
Algoritmo AprioriHybrid.
Itens: banana, disquete, pizza, vinho e queijo.
TID
100
200
300
400
items
{banana,disquete,pizza}
{queijo,disquete,vinho}
{banana,queijo,disquete,vinho}
{queijo,vinho}
Algoritmo AprioriTid:
database
TID
100
200
300
400
TC1
TID
100
200
300
400
items
{banana,floppy,pizza}
{cheese,floppy,wine}
{banana,cheese,floppy,wine}
{cheese,wine}
C2
itemset
BC
BF
BW
CF
CW
FW
support
1
2
1
2
3
2
TC2
TID
100
200
300
400
C3
itemset
CFW
support
2
set-of-itemsets
{B,F,P}
{C,F,W}
{B,C,F,W}
{C,W}
set-of-itemsets
{BF}
{CF,CW,FW}
{BC,BF,BW,CF,CW,FW}
{CW}
TC3
TID
200
300
set-of-itemsets
{CFW}
{CFW}
L1
itemset
B
C
F
W
support
2
3
3
3
L2
itemset
BF
CF
CW
FW
support
2
2
3
2
L3
itemset
CFW
support
2
Descoberta de Regras
1. Selecionar um k-itemset grande (k > 1);
2. Gerar todas as regras com 1 item na
consequência;
3. Aplicar o algoritmo para a geração de
candidatos (Apriori, AprioriTid) com dois
itens na consequência e assim por diante;
4. Contabilizar a confiança das regras e
armazenar aquelas que estivem dentro do
limite definido pelo usuário (minconf);
Descoberta de Regras
Algoritmo Simples
Confiança Mínima
Para cada itemset l serão definidos
subconjuntos a, gerando regras do tipo:
a  (l – a)
minconf = suporte(l)/suporte(a)
Ex. l = QDV e a = QD
Regra : QD  V
TID
100
200
300
400
items
{banana,disquete,pizza}
{queijo,disquete,vinho}
{banana,queijo,disquete,vinho}
{queijo,vinho}
Suporte da regra QDV = 2
Suporte da regra QD = 2
minconf = suporte(QDV)/suporte(QD) = 1
(100%)
Descoberta de Regras
Algoritmo Simples
Se um subconjunto de a de um itemset l, não
gera um regra, então os subconjuntos de a
não serão considerados para a geração de
regras.
Ex. l = ABCD e a = ABC
Regra : ABC  D
minconf < 50%
Regra : AB  CD  Não precisa ser avaliada!
Descoberta de Regras
Algoritmo Rápido (Fast)
Considerando um itemset l, se um a regra com
consequência c é válida, todas as regras com
consequências que são subconjuntos de c (c’)
também serão válidas.
(l – c)  c, então (l – c’)  c’
onde c’ é um subconjunto de c
Ex1. Regra : AB  CD
l = ABCD e c = CD
Regras : ABC  D e ABD  C  Serão válidas!

minconf > valor definido como “aceitável”.
Descoberta de Regras
Algoritmo Rápido (Fast)
Ex2. l = ABCDE
Regras (minconf) : ACDE  B e ABCE  D
Algoritmo Simples

Geração de Regras (ABCDE, ACDE)
 ACD  BE, ADE  BC, CDE  BA e ACE  BD

Geração de Regras (ABCDE, ABCE)
 ABC  DE, ABE  DC, BCE  DA e ACE  BD
 Algoritmo Rápido (Fast)

A única regra gerada (com dois itens na
consequência) que vai ser testada é aquela que
contém BD.
ACE  BD
Experimentos
Ambiente

Workstation IBM RS/6000 530H
 Clock 33MHz
 64MB de RAM
 2GB SCSI
 AIX 3.2
Dados sintéticos


Transações de um sistema de vendas
Compra de um conjunto de itens
Experimentos
Legenda:
T: Tamanho médio
das transações
I: Tamanho médio do
maior itemset
D: Número de transações
Experimentos
Mail Order
Experimentos
Apriori e AprioriTid
Experimentos
AprioriHybrid
Conclusões
Apresentação dos algoritmos Apriori e
AprioriTid para descoberta de regras de
associação significativas;
Comparação com os algoritmos AIS e SETM;
Combinação do Apriori e AprioriTid,
originando um algoritmo híbrido 
AprioriHybrid;
Algoritmo Rápido (Fast) para a descoberta
de regras de associação válidas.