Mining Frequent Patterns without
Candidate Generation
Jiawei Han, Jian Pei, and Yiwen Yin
School of Computing Science
Simon Fraser University
Alberto Bisognin
Introdução
– Algoritmo Apriori bastante usado
– Boa performance com conjuntos
reduzidos de candidatos
– Custoso com grande número de
candidatos
Principais problemas Apriori
– Geração de grande conjunto de
candidatos
– Várias verificações do banco de dados
– Checagem de grande conjunto de
candidatos
Algoritmo proposto
– Composto de 3 aspectos:
– Estrutura de dados mais compacta
denominada FP-tree
– Desenvolvida árvore baseada nos
fragmentos dos padrões
– Geração ascendente de itens frequentes
Frequent Pattern Tree – FP-tree
– Armazena informações cruciais
– Dados são compactados numa estrutura
de dados bem menor
– Reduz o espaço de busca
– Somente itens frequentes de
comprimento 1 tem nodo na árvore
– Disposição dos nós permite que nós mais
frequentes sejam melhor compartilhados
– Cada nodo contem 3 campos: nome do
item, contador e nodo link
Projeto e Construção da FP-tree
Dado um banco de dados e considerando um suporte mínimo
– Varrer o banco de dados para encontrar o conjunto de itens
frequentes que superam o suporte
– Armazenar o conjunto de itens frequentes em uma estrutura
compacta (evitar verificação do banco de dados)
– Ordenar os itens frequentes em ordem decrescente
– Criar a raiz da árvore, denominada null
– Examinar a primeira transação para construir o primeiro ramo da
árvore, seguindo sempre a ordem decrescente dos itens
frequentes
– Na próxima transação, se esta tiver itens semelhantes já
apresentados na árvore, o contador do mesmo item deve ser
incrementado e se apresentar nodos diferentes, estes devem ser
incluídos no ramo da árvore
– Se próxima transação tiver itens diferentes da anterior, novo
ramo será criado
Exemplo FP-tree
Suporte=3
Alguns detalhes
– Cada transição do banco de dados é mapeada
para um caminho na árvore
– Frequencia dos itens são armazenados na
árvore
– O tamanho é limitado pela ocorrência dos itens
frequentes no banco de dados
– A altura de uma árvore é limitada ao número
máximo de itens de uma transação do banco de
dados
– Um caminho pode representar itens frequentes
em múltiplas transações
Comparativo com FP-tree
Teste com base de dados Connect-4 usado em MaxMiner
Contém 67557 transações com 43 itens
Suporte de 50%
Número total de ocorrência de itens frequentes:2219609
Número total de nodos numa árvore FP-tree:13449
Relação de redução de 165,04 vezes
Gerando padrões frequentes através da FP-tree
– Para qualquer item freqüente ai, todos os possíveis
padrões que contem ai podem ser obtidos seguindo os nólinks de ai, a partir de ai na estrutura da FP-tree.
– Procura de padrões frequentes associados a um item
– Padrões de caminhos simples são gerados pela
combinação dos itens deste ramo
– Caminhos compostos é gerada uma árvore de padrão
base para cada item
Árvore condicional de m
Árvores condicionais
Algoritmo FP-growth
Avaliação experimental do algoritmo
Comparação entre os métodos FP-growth, Apriori
e TreeProjection
Computador Pentium 450MHz 128Mbytes Ram
Windows NT
Programas escritos em Microsoft Visual C++6.0
Banco de dados:
D1-T25.I10.D10K 1000 itens 10000 transações
D2-T25.I20.D100K 10000 itens
Avaliação FP-growth e Apriori
Tempo de execução FP-growth
Avaliação FP-growth e Apriori
Avaliação FP-growth e TreeProjection
Avaliação FP-growth e TreeProjection
Conclusão
– Gera uma árvore bastante compacta
– Reduz a geração de candidatos
– Redução do tamanho das bases subsequentes de padrões
condicionais e das árvores condicionais
– Muito eficiente para banco de dados com grande número
de transações e suportes baixos