piFP-growth: Um Algoritmo Paralelo para Geração Incremental de Regras de Associação
Resumo
Mineração de regras de associação tem sido amplamente utilizada em sistemas para suporte à decisão e para personalização do atendimento a clientes. Muitos destes sistemas são caracterizados por uma adição constante de dados às bases, o que inevitavelmente determina reavaliações constantes dos resultados das minerações. Nestes casos, utilizar algoritmos tradicionais, que mineram as bases inteiras a cada execução pode ser dispendioso e até impraticável. Neste artigo apresentamos o piFP-growth, um algoritmo que, a partir da árvore de padrões freqüentes armazenada em minerações anteriores e dados adicionados posteriormente, calcula as regras de associação do conjunto resultante em paralelo e de forma escalável. Este algoritmo é uma paralelização do algoritmo iFP-growth e se distingue não apenas pelo seu caráter incremental, mas também pela otimização do uso dos recursos computacionais. O algoritmo foi implementado em linguagem C, utilizando a biblioteca POSIX Threads, e avaliado para bases de dados reais e sintéticas, demonstrando os ganhos da sua utilização e a manutenção das propriedades do algoritmo não-incremental sequencial.
Referências
Jiawei Han, Jian Pei, and Yiwen Yin. Mining frequent pattems without candidate generation. pages 1-12, 2000.
W. Meira Jr., C. Murta, S. Campos, and D. Guedes. Comércio Eletrônico: Projeto e Desenvolvimento de Sistemas. edições Campus-SBC, Janeiro 2002.
Gustavo Menezes Siqueira, Tiago Adriano de Knegt López de Prado, Wagner Meira Jr., and Márcio Luiz Bunte de Carvalho. ifp-growth: Um algoritmo incremental para determinar regras de associação. In Anais do 17° Simpósio Brasileiro de Banco de Dados, 2002. Aceito para publicação.
W. M. Shaw, J. B. Wood, R. E. Wood, and H. R. Tibbo. The cystic fibrosis database: Content and research opportunities. In Library and Information Science Research, volume 13), pages 347-366, 1991.
Shiby Thomas, Sreenath Bodagala, Khaled Alsabti, and Sanjay Ranka. An efficient algorithm for the incremental updation of association rules in large databases. In Knowledge Discovery and Data Mining, pages 263-266, 1997.
A. Veloso, W. Meira Jr., M. B. de Carvalho, B. Pôssas, S. Parthasarathy, and M. Zaki. Mining frequent itemsets in evolving databases. In Proc. of the 2nd SIAM Int'l Conf. on Data Mining, Arlington, USA, April 2002.
A. Veloso, B. Pôssas, W. Meira Jr., and M. B. de Carvalho. Knowledge management in association rule mining. In Proc. of the 1st IEEE Int'l Workshop on Integrating Data Mining and Knowledge Management, San Jose, USA, november 2001.
Mohammed Javeed Zaki. Scalable algorithms for association mining. Knowledge and Data Engineering, 12(2):372-390, 2000.
Osmar R. Zaiane, Mohammad EI-Hajj, and Paul Lu. Fast parallel association rui e mining without candidacy generation. In ICDM, pages 665-668, 2001.
Mohammed Javeed Zaki, Mitsunori Ogihara, Srinivasan Parthasarathy, and Wei Li. Parallel data mining for association rules on shared-memory multiprocessors. Technical Report TR618, 1996.
