A FAST APRIORI
implementation
Aérton Dillenburg;
Alisson Moscato Loy.
APRIORI Original
Objetivo: encontrar os itemsets
freqüentes, usando geração de
Candidatos.
Entradas: banco de dados de transações
D; limite de suporte mínimo (sup_min).
Saída: itemsets freqüentes em D (L ).
APRIORI Original
O algoritmo Apriori considera a
seguinte propriedade para diminuir
o espaço de busca a ser avaliado
na extração dos conjuntos
freqüentes: todo conjunto de itens
que contém um subconjunto não
freqüente também não é freqüente.
Objetivos do Artigo
Melhorar a performance do
algoritmo APRIORI (através
do uso de uma estrutura de
dados denominada TRIE)
Estrutura de dados TRIE
A estrutura de dados TRIE foi introduzida
originalmente para armazenar e recuperar
eficientemente palavras de um dicionário.
Uso da TRIE no fast APRIORI
Usando as características da TRIE, o autor
propõem a ordenação dos itens em cada
transação e a construção dos ramos da
árvore. Para itens iguais em diferentes
transações, um contador é incrementado
reduzindo o tamanho da árvore criada.
OBS.: É pré-requisito do algoritmo que os itens
na transação estejam ordenados.
Uso da TRIE no fast APRIORI
Exemplo da construção de uma TRIE para os seguintes candidatos:
Benefícios TRIE
A árvore armazena não somente candidatos, mas itemsets
freqüentes também. Isto tem as seguintes vantagens:
1. A geração do candidato torna-se fácil e rápida. É possível
gerar candidatos dos pares de nós que têm os mesmos pais.
2. As regras de associação são produzidas muito mais
rapidamente, pois a recuperação de um itemset é mais rápida
(relembrando que TRIE foi desenvolvida originalmente para
decidir rapidamente se uma palavra é incluída em um
dicionário).
3. Apenas uma estrutura de dados tem que de ser
executada, assim o código é mais simples e mais fácil de
manter.
4. Nós podemos imediatamente gerar a chamada negative
border; Característica importante em alguns casos do uso de
algoritmos baseados no apriori.
Métodos da contagem com uso de
uma TRIE
A contagem de suporte é feita, one-by-one
lendo as transações e determinando quais
candidatos estão contidos na transação
atual.
A seleção dos itens freqüentes é feita com
base no counter de cada nodo, conforme
exemplo posterior.
Estrutura da TRIE em memória
O algoritmo faz uso de vetores para armazenar os dados
em memória. Os principais são:
EDGE NUMBER: Contém o número de itens partindo do
nó atual;
ITEM ARRAY: Descrição ou rótulo dos vetores filhos do nó
atual;
STATE ARRAY: Nós destinos (filhos) do nó atual;
PARENT: Nó pai do atual;
Estrutura da TRIE em memória (continuação)
MAX-PATH: Maior caminho a ser seguido a partir do nó
atual; Este valor será usado para minimizar a quantidade
de caminhos a serem percorridos quando da geração de
itens frequentes. Ex: para a geração de 5-itemset os nós
com MAX-PATH menores que 5 são ignorados.
COUNTER: Contador incrementado a cada ocorrência do
item na seqüência de montagem da árvore;
Estrutura da TRIE em memória
(exemplo)
Processo de criação da TRIE
Para exemplificar o algoritmo Fast Apriori, tomemos por
exemplo o seguinte banco de dados com 10 transações e
7 itens por transação.
Processo de criação da TRIE
Na primeira transação encontramos os seguintes itens
ordenados: {café, manteiga, pão}
Os números dentro dos círculos
servem apenas para referência
ao nó, sendo que o 0 (zero) é a
raiz. Entre parênteses o contador
de ocorrências do item na arvore
(counter).
Processo de criação da TRIE
Na segunda transação encontramos os seguintes itens
ordenados: {cerveja, leite, manteiga, pão}
Processo de criação da TRIE
A terceira transação é exatamente igual à primeira. {café,
manteiga, pão}
Assim o algoritmo somente
irá incrementar os
contadores em cada item da
árvore que se repete.
Processo de criação da TRIE
Na quarta transação encontramos os seguintes itens: {café,
leite, manteiga, pão}
Os ramos são inseridos na
TRIE sempre observando a
ordem correta, neste caso,
alfabética.
Processo de criação da TRIE
Na quinta transação somente {cerveja} e na sexta transação
somente {manteiga}
Processo de criação da TRIE
Sétima transação somente {pão} e na oitava transação
somente {feijão}
Processo de criação da TRIE
Nas duas últimas transações encontramos na ordem:
{arroz, feijão} e {arroz}.
Esta é a representação da
árvore completa, de acordo
com as transações dadas
como entrada.
Tabela comparativa entre variações do APRIORI e o
Fast Apriori (Apriori Brave)
Tabela comparativa entre variações do APRIORI e o
Fast Apriori (Apriori Brave)
Tabela comparativa entre variações do APRIORI e o
Fast Apriori (Apriori Brave)
Conclusão
A estrutura de dados influencia
fortemente no tempo de
execução do algoritmo.
Trabalhos futuros
Melhorar a performance do algoritmo
utilizando de um grupo menor de
dados na TRIE, através da
remoção do nodo da TRIE que não
tiver nenhum candidato.