Otimização da Técnica
Apriori
Sandra de Amo
Data Mining
AULA 4
11/5/2015
Mestrado em Ciencia da Computacao - 2012
1
Maneiras de Otimizar
 Otimização 1 : reduzir



numero de testes durante a fase de geracao
numero de testes durante a fase da poda
numero de testes durante a fase do calculo du suporte
 Otimização 2 : reduzir o tamanho da base de dados
 Otimização 3 : reduzir o numero de varridas do BD
 Otimização 4 : reduzir o numero de candidatos
gerados
11/5/2015
Mestrado em Ciencia da Computacao - 2012
2
Otimização 1 Arvore Hash
1
Tabelas Hash
2
3
1
1
1
2
2
2
3
3
3
1
2
Folhas : itemsets estocados
3
11/5/2015
Mestrado em Ciencia da Computacao - 2012
3
Como estocar os candidatos na
árvore hash ?
h(i1) = 1
Pao, Leite
Pao, Acucar
Pao, Manteiga
Leite, Acucar
Leite, Manteiga
Acucar, Manteiga
h(Pao) = h(Acucar) = 1
Pao, Leite
Pao, Acucar
Pao, Manteiga
Acucar, Manteiga
h(i1) = 2
Leite, Acucar
Leite, Manteiga
N = N. maximal de itemsets nas folhas = 3
h(Manteiga) = h(Leite) = 2
11/5/2015
Mestrado em Ciencia da Computacao - 2012
4
Como estocar os candidatos
na árvore hash ?
Pao, Leite
Pao, Acucar
Pao, Manteiga
Acucar, Manteiga
h(i1) = 1
h(i1) = 2
h(i2) = 2
h(i2) = 1
Leite, Acucar
Leite, Manteiga
Pao, Acucar
h(Pao) = h(Acucar) = 1
h(Manteiga) = h(Leite) = 2
11/5/2015
Pao, Leite
Pao, Manteiga
Acucar, Manteiga
N = N. maximal de itemsets nas folhas = 3
Mestrado em Ciencia da Computacao - 2012
5
Geração dos Candidatos
1
1
x 2 2
2 2 y
2
2
1
2
< 3, 6, 8 > x
1
< 1, 2, 5 >
< 2, 4, 7 >
2
< 1, 4, 8 >
< 3, 6, 8 >
< 1, 2, 4 >
< 6, 8, 9 >
< 3, 6, 8, 9 >
2
1
< 6, 8, 9 >
< 6, 8, 10 >
< 2, 4, 6 >
< 3, 6, 8 > x
< 1, 2, 4 > x
< 6, 8, 10 >
< 2, 4, 6 >
<3, 6, 8, 10 >
<1, 2, 4, 6>
Não são testados !
11/5/2015
Mestrado em Ciencia da Computacao - 2012
6
Poda dos Candidatos
Candidato: { 1, 2, 5, 6 }
sub-itemset:
1
2, 656 }}
{ 1, 2,
1
h(n) = 1 se n é impar
2
2
1
1
2
2
1
2
h(n) = 2 se n é par
{ 1, 2, 5 }}
{ 2, 4, 7 }
{ 1, 4, 8 }
{ 3, 6, 8 }
{ 1, 2, 4 }
{ 6, 8, 9 }
{ 6, 8, 10 }
{ 2, 4, 6 }
Folhas : 3 itemsets no máximo
Não são testados !
11/5/2015
Mestrado em Ciencia da Computacao - 2012
7
Cálculo do Suporte
Transação no BD
{ 1, 2, 5, 6 }
2
1
1
2
1
{ 1, 5, 9 } - 0
{ 1, 2, 5 } - 10
{ 2, 4, 7 } - 0
1
2
1
2
2
{ 2, 5, 6 } - 10
{ 1, 4, 8 } - 0
{ 3, 6, 8 } - 0
{ 1, 2, 6 } - 10
{ 6, 8, 9 } - 0
{ 6, 8, 10 } - 0
{ 2, 4, 6 } - 0
Não são testados !
11/5/2015
Mestrado em Ciencia da Computacao - 2012
8
Otimização 2
Redução do tamanho do BD
Iteração k
t : transação do BD nao contém nenhum
candidato de tamanho k
Iteração k+1
t pode ser eliminada do BD
t nao conterá nenhum candidato de tamanho
k +1
11/5/2015
Mestrado em Ciencia da Computacao - 2012
9
Otimização 3
Redução das varridas do BD
 Método convencional
N varridas na base
N = Número de iterações do algoritmo
 Método do Particionamento [Savarese+
1995]
O número de varridas na la base é = 2
11/5/2015
Mestrado em Ciencia da Computacao - 2012
10
Método do Particionamento
Executa Apriori na
memória principal
Encontra os itemsets localmente
frequentes
Globalmente Frequente
Localmente Frequente em pelo
menos uma das partições
BD
11/5/2015
Teste os itemsets localmente frequentes
Mestrado em Ciencia da Computacao - 2012
11
Otimização 4
Redução do Número de
Candidatos Gerados
 Restrições sobre os padrões : regras devem
satisfazer uma expressão booleana dada
 Itemsets: restrição de items (Agrawal-Srikant
1997)
(Pão AND Leite) OR (Açucar AND Café AND ¬ Sal)
11/5/2015
Mestrado em Ciencia da Computacao - 2012
12
Constraint Mining
Algoritmo DIRECT
11/5/2015
Mestrado em Ciencia da Computacao 2012
13
Restrição de Itens
Uma fórmula proposicional em Forma Normal Disjuntiva
B = D1 OR D2 OR …. OR Dn
Di = p1 AND p2 AND … AND pm
pj = item
pj = ¬ item
Exemplo:
B = (Pão AND Manteiga) OR (Café AND ¬ Sal)
Itemset I = (Café, Açúcar, Trigo) satisfaz a fórmula B
11/5/2015
Mestrado em Ciencia da Computacao 2012
14
Problema de Mineração

Dados



Banco de dados de transações
Uma restrição de itens B
B = D1 AND D2 AND …. AND Dn
Minerar todos os itemsets frequentes e que
satisfazem a restrição B
A fórmula B serve como um molde para guiar o
processo de mineração
11/5/2015
Mestrado em Ciencia da Computacao 2012
15
Algoritmo DIRECT


Fase da Geração
Ideia Principal do algoritmo

Se um itemset I de tamanho k+1 satisfaz B então
uma das duas condições se verifica:


11/5/2015
Todos os Di verificados por I tem exatamente k+1
elementos positivos
Existe ao menos um k-subitemset de I que satisfaz B
Mestrado em Ciencia da Computacao 2012
16
Prova da propriedade

Seja I = {a1,….,ak,ak+1} que satisfaz B

Se existe um Di satisfeito por I, com m <= k elementos positivos:
Di = a1 AND a2 AND …. am AND ¬ B1 AND ¬ B2 AND … ¬ Bp
I = {a1,…,am,am+1,…,ak,ak+1}
Não aparecem entre os negativos de Di
Logo qualquer subitemset de I contendo a1,…,am satisfaz Di
11/5/2015
Mestrado em Ciencia da Computacao 2012
17
Fase da Geração de DIRECT
Itemset de tamanho k+1 frequente que satisfaz B
1a possibilidade : A1,…,Ak, Ak+1
Satisfaz B
É frequente
Deve ser frequente
Logo um bom conjunto de
CANDIDATOS DE TAMANHO k+1 =
CbK+1 = Fbk x F
onde F = conjunto de items frequentes
Fbk = k-itemsets frequentes e que satisfazem B
11/5/2015
Mestrado em Ciencia da Computacao 2012
18
Fase da Geração

Gera Cbk+1

Elimina-se de Cbk+1 todos os itemsets que
não satisfazem B
11/5/2015
Mestrado em Ciencia da Computacao 2012
19
Fase da Poda

Dispomos do conjunto Fbk da fase anterior =
Frequentes e que satisfazem B

Se um itemset I= (a1,…,ak,ak+1) contiver um
subitemset J de tamanho k que satisfaz B e que não
esteja em Fbk
então com certeza J não será frequente, portanto I
poderá ser podado.
11/5/2015
Mestrado em Ciencia da Computacao 2012
20
Fase da Geração- complemento
2a Possibilidade de se obter candidatos de tamanho
k+1 potencialmente frequentes e satisfazendo B.
Adicionar todos os k+1-itemsets correspondendo aos
Di com exatamente k+1 items positivos e
frequentes.
11/5/2015
Mestrado em Ciencia da Computacao 2012
21
Resumo da etapa k+1 do algoritmo
Fase da Geração e Poda
1. Fbk x F
2. Elimina os itemsets que não satisfazem B
3. Poda os que possuem k-subitemsets que satisfazem B e
que não estão em Fbk
4. Junta-se os obtidos dos Di com k+1 elementos positivos e
frequentes
Fase do Cálculo do Suporte
5. Varre banco de dados e calcula suporte dos candidatos
restantes.
11/5/2015
Mestrado em Ciencia da Computacao 2012
22
Exercicio
Gerar Cb2 sabendo que :


O conjunto dos items frequentes =
{1, 2, 3, 4, 5}
B = (1 AND 2) OR (4 AND ¬5)
11/5/2015
Mestrado em Ciencia da Computacao 2012
23
Fb1 = {4}
1. Cb2 = { {1,4}, {2,4}, {3,4}, {4,5}}
2.
Elimina os que não satisfazem B
Cb2 = { {1,4}, {2,4}, {3,4}}
3.
Poda os que possuem 1-subitemset que satisfaz B e que não
está em Fb1 : único 1-subitemset que satisfaz B é {4}
4.
Junta os Di com exatamente 2 elementos positivos e frequentes.
Cb2 = { {1,4}, {2,4}, {3,4}, {1,2} }
11/5/2015
Mestrado em Ciencia da Computacao 2012
24