MỘT CÁCH TỐI ƯU CƠ SỞ DỮ LIỆU GIAO TÁC TRONG THUẬT TOÁN FP_GROWTH
Abstract
Tìm các luật kết hợp là công việc cơ bản trong khai thác dữ liệu. Bài toán được giải theo hai bước chính: bước một: tìm tất cả các tập thường xuyên theo ngưỡng S0 cho trước; bước hai: dựa vào các tập thường xuyên, tìm các luật kết hợp. Tất cả khó khăn của bài toán tập trung ở bước một. Các nghiên cứu về khai thác luật kết hợp đều tập trung cải tiến tốc độ xử lý, dung lượng bộ nhớ và số lần truy cập đĩa. Năm 2000, J. Han đề xuất thuật toán FP_Growth để tìm tất cả các tập mục dữ liệu thường xuyên. Đây là một bước tiến lớn trong bài toán cơ bản. Bài toán có hai bước: bước một: tạo cây FP_Tree; bước hai: dùng thuật toán FP_Growth để tìm tập các tập mục dữ liệu thường xuyên. Với thuật toán này, với tập dữ liệu cố định, mỗi lần khai thác dữ liệu với một ngưỡng tối thiểu S0, bài toán phải làm lại từ đầu. Trong bài báo này, chúng tôi đề xuất phương án tối ưu cơ sở dữ liệu giao tác bằng cách thêm ”trọng số” cho mục dữ liệu nhằm tối ưu thời gian xây dựng FP_Tree cho những lần khai thác sauReferences
[1] QIANKUN ZHAO, SOURAV S. BHOWMICK, Association Rule Mining: A Survey. Technical Report, CAIS, Nanyang Technological University, Singapore, No. 2003116, 2003.
[2] AGRAWAL. R., IMIELINSKI. T., SWAMI. A., Mining Associations between Sets of Items in Massive Databases. In Proc.of the 1993 ACM-SIGMOD Int’l Conf. on Management of Data, pages 207-216.
[3] AGRAWAL. R., MANNULLA. H., SRIKANT. R., TOIVONEN. H., VERKAMO. A. I., Fast Discovery of Association Rules. In Advances in Knowledge Discovery and Data Mining, AAAI Press, 1996, pages 307-328.
[4] HAN J, PEI H, AND YIN Y. Mining Frequent Patterns without Candidate Generation. In: Proc. Conf. on the Management of Data (SIGMOD’00, Dallas, TX). ACM Press, New York, NY, USA 2000, pages 1-12.
[5] CLAUDIO LUCCHESE, SALVATORE ORLANDO, RAFFAELE PEREGO Fast and Memory Efficient Algorithm to Mine Frequent Closed Itemsets.IEEE Transaction On Knowledge and Data Engineering, Vol.18 No.1 (January 2006), pages 21-36.
[6] MOHAMMED J. ZAKI AND CHING-JUI HSIAO CHARM: Efficient Algorithm for Mining Closed Itemsets and Their Lattice Structure. IEEE Transactions On Knowledge And Data Engineering Vol 17 No 4 April 2005. http://www.cs.rpi.edu/_zaki.
[7] TAKEAKI UNO, MASASHI KIYOMI, HIROKI ARIMURA LCM ver.2: Efficient Mining Algorithms for Frequent/Closed/Maximal Itemsets. IEEE ICDM’04 Workshop FIMI’04 (International Conference on Data Mining, Frequent Itemset Mining Implementations). 2004. http://research.nii.ac.jp/~uno/papers/0411lcm2.pdf.
[8] VICKY CHOI Faster Algorithms for Constructing a Concept (Galois) Lattice. arXIV:cs.DM/0602069 v2 1 Jun 2006.
[9] SAVESERE, A., OMIECINSKI, E., AND NAVATHE, S. An efficient algorithm for mining association rules in large databases. In Proceedings of 20th International Conference on VLDB. Pager 432-444, 1995.
[10] SHAKIL AHMED, FRANS COENEN, AND PAUL LENG, Tree-based Partitioning of Data for Association Rule Mining. Knowledge and Information Systems, Volume 10, Number 3, 2006, pages 315-331.
[2] AGRAWAL. R., IMIELINSKI. T., SWAMI. A., Mining Associations between Sets of Items in Massive Databases. In Proc.of the 1993 ACM-SIGMOD Int’l Conf. on Management of Data, pages 207-216.
[3] AGRAWAL. R., MANNULLA. H., SRIKANT. R., TOIVONEN. H., VERKAMO. A. I., Fast Discovery of Association Rules. In Advances in Knowledge Discovery and Data Mining, AAAI Press, 1996, pages 307-328.
[4] HAN J, PEI H, AND YIN Y. Mining Frequent Patterns without Candidate Generation. In: Proc. Conf. on the Management of Data (SIGMOD’00, Dallas, TX). ACM Press, New York, NY, USA 2000, pages 1-12.
[5] CLAUDIO LUCCHESE, SALVATORE ORLANDO, RAFFAELE PEREGO Fast and Memory Efficient Algorithm to Mine Frequent Closed Itemsets.IEEE Transaction On Knowledge and Data Engineering, Vol.18 No.1 (January 2006), pages 21-36.
[6] MOHAMMED J. ZAKI AND CHING-JUI HSIAO CHARM: Efficient Algorithm for Mining Closed Itemsets and Their Lattice Structure. IEEE Transactions On Knowledge And Data Engineering Vol 17 No 4 April 2005. http://www.cs.rpi.edu/_zaki.
[7] TAKEAKI UNO, MASASHI KIYOMI, HIROKI ARIMURA LCM ver.2: Efficient Mining Algorithms for Frequent/Closed/Maximal Itemsets. IEEE ICDM’04 Workshop FIMI’04 (International Conference on Data Mining, Frequent Itemset Mining Implementations). 2004. http://research.nii.ac.jp/~uno/papers/0411lcm2.pdf.
[8] VICKY CHOI Faster Algorithms for Constructing a Concept (Galois) Lattice. arXIV:cs.DM/0602069 v2 1 Jun 2006.
[9] SAVESERE, A., OMIECINSKI, E., AND NAVATHE, S. An efficient algorithm for mining association rules in large databases. In Proceedings of 20th International Conference on VLDB. Pager 432-444, 1995.
[10] SHAKIL AHMED, FRANS COENEN, AND PAUL LENG, Tree-based Partitioning of Data for Association Rule Mining. Knowledge and Information Systems, Volume 10, Number 3, 2006, pages 315-331.
Published
2014-11-28
How to Cite
TRỌNG, Nguyễn Hữu; CHÂU, Nguyễn Thị Minh.
MỘT CÁCH TỐI ƯU CƠ SỞ DỮ LIỆU GIAO TÁC TRONG THUẬT TOÁN FP_GROWTH.
JBIS, [S.l.], nov. 2014.
Available at: <http://jbis.ueh.edu.vn/index.php/TSTHQL/article/view/32>. Date accessed: 04 may 2024.
Issue
Section
Bài viết
Keywords
Khai thác dữ liệu; luật kết hợp; FP-Tree; trọng số
