piFP-growth: Um Algoritmo Paralelo para Geração Incremental de Regras de Associação

  • Tiago Adriano de Knegt López de Prado UFMG
  • Gustavo Menezes Siqueira UFMG
  • Wagner Meira Júnior UFMG
  • Márcio Luiz Bunte de Carvalho UFMG

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

Rakesh Agrawal and Ramakrishnan Srikant. Fast algorithms for mining association rules. In Jorge B. Bocca, Matthias Jarke, and Carlo Zaniolo, editors, Proc. 20th Int. Conf. Very Large Data Bases, VLDB, pages 487-499. Morgan Kaufmann, 12-15 1994.

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.
Publicado
28/10/2002
PRADO, Tiago Adriano de Knegt López de; SIQUEIRA, Gustavo Menezes; MEIRA JÚNIOR, Wagner; CARVALHO, Márcio Luiz Bunte de. piFP-growth: Um Algoritmo Paralelo para Geração Incremental de Regras de Associação. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 3. , 2002, Vitória. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2002 . p. 76-83. DOI: https://doi.org/10.5753/wscad.2002.20764.