A técnica de associação pelo algoritmo Frequent Pattern-Growth (FP-Growth) na shell Orion Data Mining Engine

Abstract

O crescimento acelerado na coleta de dados nos mais variados campos dos negócios e da área científica tem despertado o interesse dos profissionais a atentar para a necessidade de se desenvolver tecnologias que permitam a análise e exploração de conhecimentos úteis implícitos nesses dados. Neste contexto, o data mining se destaca, pois automatiza o processo da extração de conhecimentos por meio de ferramentas e algoritmos computacionais. Essas ferramentas, por sua vez, na grande maioria são proprietárias e possuem um alto custo de aquisição. Considerando isso, o Grupo de Pesquisa em Inteligência Computacional Aplicada do Curso de Ciência da Computação da Universidade do Extremo Sul Catarinense, desenvolve diversos métodos e tarefas de data mining por meio do projeto da Shell Orion Data Mining Engine. Dentre as tarefas de data mining, a descoberta de regras de associação tem recebido atenção por parte de pesquisadores tanto da área acadêmica como das organizações. Na área acadêmica, as pesquisas desenvolvidas estão gerando bons resultados. Esses resultados, por sua vez, estão sendo utilizados pelas organizações em aplicações práticas. Objetivando ampliar as funcionalidades da Shell Orion, essa pesquisa consiste na demonstração do funcionamento e na implementação do algoritmo Frequent Pattern-Growth, desenvolvido para superar as limitações presentes no algoritmo Apriori e melhorar a eficiência da descoberta de regras de associação por meio de uma abordagem diferente, sem a geração do conjunto de candidatos. Também não concorda com o paradigma de gerar e testar do Apriori, uma vez, que codifica a base de dados em uma estrutura compacta em forma de árvore chamada Frequent Pattern tree e extrai os conjuntos de itens frequentes diretamente desta estrutura. Isso possibilita uma melhor eficiência na geração das regras de associação, pois evita constantes acessos na base de dados. Tendo-se concluída a implementação, diversos testes foram efetuados tendo por objetivo a análise de desempenho do algoritmo implementado. Fez-se isso por meio de medidas de qualidade para regras de associação, análise dos resultados obtidos e análise do tempo de processamento por meio de cálculos estatísticos. Os resultados das regras identificadas, comparadas com a Weka, mostraram que a Shell Orion encontrou corretamente as regras de associação úteis e fortes e também calculou corretamente as medidas de qualidade. Já quanto ao tempo de processamento verificou-se que a Weka obteve tempos um pouco melhores, porém do ponto de vista estatístico, a diferença não foi significativa.