Artigo: Mining Frequent Patterns without Candidate Generation Jiawei Han, Jian Pei, and Yiwen Yin...

Artigo: ‘Mining Frequent Patterns Artigo: ‘Mining Frequent Patterns without Candidate Generation’without Candidate Generation’Jiawei Han, Jian Pei, and Yiwen Yin

Resumo: Davis Ant. Peñaranda Zárate, Bolsista da CAPES/CNPq – IEL Nacional - Brasil

1

SumárioSumárioAlgoritmo A prioriSolução propostaAlgoritmo

◦ExecuçãoPropriedadesDesempenho

2

Algoritmo A prioriAlgoritmo A prioriÉ cansativo escanear repetidamente

a base de dados e verificar um conjunto grande de candidatos usando ‘Pattern matching’.

Congestionamento acontece na geração de conjunto de candidatos e os testes.

Se fosse possível evitar gerar um conjunto grande de candidatos, o desempenho pode ser muito melhor.

3

Solução propostaSolução proposta• Frequent pattern tree (FP-tree),

para armazenar informação quantitativa sobre padrões frequentes.

• O crescimento é atingido com a concatenação do padrão sufixo com os nodos gerados de um FP-tree condicional.

• A técnica utilizada na mineração é baseada em partições e dividir-e-conquistar e não como o Apriori que é bottom-up na geração de combinações de itemset frequentes.

4

O algoritmo em termos O algoritmo em termos formaisformaisCriar a raiz da árvore FP e cujo valor seja null.

E para cada transação na BD fazer o seguinte.Seja [p|P], onde p é o primeiro elemento e P é

o resto da lista.Executar com insertar_FP ([p|P], T)Definição de insertar_FP ([p|P], T):

◦ Se T tem um filho N e N.nome = p.nome, Então imcrementar a conta de N em 1. Sçenão criar novo nodo N com conta de 1.

◦ O enlace do pai ser enlaçado a T, e o enlace do nodo será enlaçado aos nodos com o mesmo nome.

Se P não é vazio, chamar insertar_FP(P, N) recursivamente.

5

Execução do algoritmoExecução do algoritmoItemes Itens frequentes

ordenados

f, a, c, d, g, i, m, p f, c, a, m, p

a, b, c, f, l, m, o f, c, a, b, m

b, f, h, j, o f, b

b, c, k, s, p c, b, p

a, f, c e, l, p, m, n f, c, a, m, p

6

Item

Soporte

f 4

c 4

a 3

b 3

m 3

p 3

Soporte mínimo= 3

Item

Soporte

d 1

g 1

i 1

l 2

o 2

h 1

Item

Soporte

k 1

s 1

e 1

n 1

j 1

Itens frequentes ordenados

f, c, a, m, pf, c, a, m, pf, c, a, b, m

f, b

c, b, p

f, c, a, m, p

7

null

c:1

a:1

f:1

m:1

p:1

Itens frequentes ordenados

f, c, a, m, p

f, c, a, b, mf, c, a, b, mf, b

c, b, p

f, c, a, m, p

8

null

c:2

a:2

f:2

m:1

p:1

b:1

m:1

Itens frequentes ordenados

f, c, a, m, p

f, c, a, b, m

f, bf, bc, b, p

f, c, a, m, p

9

null

c:2

a:2

f:3

m:1

p:1

b:1

m:1

b:1

Itens frequentes ordenados

f, c, a, m, p

f, c, a, b, m

f, b

c, b, pc, b, pf, c, a, m, p

10

null

c:2

a:2

f:3

m:1

p:1

b:1

m:1

b:1 b:1

p:1

c:1

Itens frequentes ordenados

f, c, a, m, p

f, c, a, b, m

f, b

c, b, p

f, c, a, m, pf, c, a, m, p

11

null

c:3

a:3

f:4

m:2

p:2

b:1

m:1

b:1 b:1

p:1

c:1

CompletitudeCompletitudeUma rota na árvore representa

conjuntos de dados frequentes em multiplas transações sem ambiguidade.

12

CompactnessCompactnessExiste uma alta probabilidade de

compartilhar os Itens por que os mais frequentes estão mais perto da raiz.

O tamanho da árvore é muito menor que a base de dados original.

13

Propriedade: Propriedade: enlace-nodoenlace-nodoPara cada qualquer item

frequente a, todos os possíveis padrões frequentes que contem a podem ser obtidos seguindo os enlaces do nodo.

Padrão condicional base, é o conjunto de rotas na árvore que estão antes de um item.

14

Propriedade: Propriedade: enlace-nodoenlace-nodoItem

Padrão condicional base

Árvore FP condicional

p {(f:2, c:2, a:2, m:2),(c:1, b:1)}

({c:3})

m {(f:2, c:2, a:2), (f:1, c:1, a:1, b:1)}

{(f:3, c:3, a:3)}

b {(f:1, c:1, a:1),(f:1), (c:1)}

a {(f:3, c:3)} {(f:3, c:3)}

c {(f:3)} {(f:3)}

f

15

null

c:3

a:3

f:4

m:2

p:2

b:1

m:1

b:1 b:1

p:1

c:1

Comparação A priori-FPComparação A priori-FP

16

Comparação A priori-FPComparação A priori-FP

17

Comparação TreeProjection-Comparação TreeProjection-FPFP

18

Comparação TreeProjection-Comparação TreeProjection-FPFP

19