Khai thác dàn tập phổ biến đóng sử dụng cấu trúc DSBV

memory 50

(MB)

BVCL+MG

BVCL cải tiến CharmL BVCL

DB: Retail 5 6 7 8

supp(%)

Hình 3.11: Biểu đồ so sánh bộ nhớ chiếm dụng của bộ dữ liệu Retail

Thời gian chạy trung bình của BVCL nhanh hơn so với CharmL: 1.6 lần. Bộ nhớ tiêu tốn trung bình của BVCL ít hơn so với CharmL: 6.7%.

Thời gian chạy trung bình của BVCL cải tiến nhanh hơn so với BVCL+MG: 3 lần. Bộ nhớ tiêu tốn trung bình của BVCL ít hơn so với CharmL: 13.9%.

5.5 Bộ dữ liệu T10I4D100K

Bộ dữ liệu gồm 100000 giao dịch với 870 hạng mục phân biệt.

Bảng 3.9: Bộ dữ liệu T10I4D100K

Database

minsup(%)	FCIs
T10I4D100K (100000 transactions) (870 items)	1	385
	2	155
	3	60
	4	26
	5	10

Có thể bạn quan tâm!

Xem toàn bộ 72 trang tài liệu này.

Bảng 3.10: Kết quả thực nghiệm thu được với bộ dữ liệu T10I4D100K

Time(s)

	1	2	3	4	5
BVCL	852	102	13	2.4	0.4
CharmL	755	99	13.6	2.5	0.4
BVCL cải tiến	853	102	13.5	2.4	0.4
BVCL+MG	890	228	30.5	5.4	0.7
database: T10I4D100K

Memory(MB)

	1	2	3	4	5
BVCL	225	32	16	13	12
CharmL	300	35	17	13.5	12
BVCL cải tiến	229	33	16.5	13	12
BVCL+MG	235	37	18	15	13

4000

time(s) 3500

3000

2500

2000

1500

1000

BVCL+MG

BVCL cải tiến

CharmL BVCL

500

DB:T10I4D100K 1

supp(%)

Hình 3.11: Biểu đồ so sánh thời gian thực thi của bộ dữ liệu T10I4D100K

1200

memory

(MB)

1000

800

600

400

BVCL+MG

BVCL cải tiến

CharmL BVCL

200

DB:T10I4D100K 1

supp(%)

Hình 3.12: Biểu đồ so sánh bộ nhớ chiếm dụng của bộ dữ liệu T10I4D100K

Thời gian chạy trung bình của CharmL nhanh hơn so với BVCL: 1.1 lần.

Bộ nhớ tiêu tốn trung bình của BVCL ít hơn so với CharmL: 21.1%.

Thời gian chạy trung bình của BVCL cải tiến nhanh hơn so với BVCL+MG: 1.2 lần. Bộ nhớ tiêu tốn trung bình của BVCL ít hơn so với CharmL: 4.6%.

Trong các bộ dữ liệu cho chạy thực nghiệm, chess, mushroom, pumsb, retail thì BVCL chạy nhanh hơn và chiếm dụng bộ nhớ ít hơn CharmL như vừa nêu trên. BVCL cải tiến chạy nhanh hơn và chiếm dụng bộ nhớ ít hơn BVCL+MG.

Với bộ dữ liệu T10I4D100K, thuật toán CharmL chạy nhanh hơn so với BVCL khoảng 10% nhưng bộ nhớ tiêu tốn nhiều hơn BVCL 21.1%.

Nhìn chung, trên các bộ dữ liệu phân lớp. BVCL và BVCL cải tiến chạy nhanh vượt trội và cũng chiếm dụng bộ nhớ ít hơn. Trên các bộ dữ liệu giao dịch BVCL và BVCL cải tiến tuy có nhanh và chiếm dụng bộ nhớ ít hơn, nhưng chưa vượt trội cần có nhiều nghiên cứu và cải tiến thêm.

KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN

1. Kết luận

Luận văn đã nghiên cứu tổng quan về bài toán khai thác Dàn các tập phổ biến đóng và khai thác đồng thời tập sinh của chúng bao gồm các khái niệm cơ bản, cơ sở lý thuyết của bài toán và các công trình nghiên cứu đã có của các tác giả trong và ngoài nước. Phân tích các ưu và khuyết điểm của các kỹ thuật. Từ đó, đề xuất kỹ thuật hiệu quả để khai khác Dàn các tập phổ biến đóng và tập sinh với bộ dữ liệu có kích thước lớn.

Luận văn đã trình bày ý tưởng và nội dung một phương pháp mới khai thác Dàn các tập phổ biến đóng và tập sinh. Thuật toán BVCL và BVCL cải tiến chỉ đọc CSDL một lần duy nhất cho toàn bộ quá trình khai thác. CSDL giao dịch ban đầu được chuyển sang CSDL chiều dọc. Sau đó, chuyển đổi dữ liệu ban đầu sang cấu trúc DBV và DSBV. Cuối cùng, thực hiện khai thác Dàn các tập phổ biến đóng và tập sinh trên dữ liệu đã chuyển đổi.

Các kết quả thực nghiệm trên các bộ dữ liệu phát sinh tổng hợp cho thấy phương pháp đề xuất hiệu quả trên CSDL giao dịch thưa (có tần xuất suất hiện bit 1 thấp trên bit vector). Đồng thời, phương pháp đề xuất cũng đạt tính mở rộng cao. Tuy nhiên, luận văn cũng còn hạn chế khi chưa thực nghiệm trên các bộ dữ liệu thực có kích thước lớn (trên vài triệu giao dịch). Hạn chế của cấu trúc dữ liệu bit vector động trên các CSDL giao dịch đặc (có tần xuất suất hiện bit 1 cao trên bit vector).

2. Hướng phát triển

Khai thác Dàn Tập phổ biến đóng và khai thác luật kết hợp được ứng dụng nhiều nhất trong lĩnh vực kinh doanh, tài chính, thị trường chứng khoán...Vì thế cần phải có thuật toán, hay công cụ mạnh mẽ để khai thác tập phổ biến đóng, tập sinh cũng như tập luật kết hợp, rút trích thông tin có giá trị. Nếu sử dụng thông tin có giá trị này, doanh nghiệp có thể chủ động đặt thêm món hàng nào đó vào giỏ mua sắm của khách hàng, hoặc lập chiến lược bán hàng như: khuyến mãi, quảng bá sản phẩm mới, tăng nguồn lợi tài chính và khả năng cạnh tranh của doanh nghiệp.

Ứng dụng khai thác luật kết hợp đem lại lợi ích thực tế to lớn như vậy, hứa hẹn ngày càng có nhiều công trình nghiên cứu sâu rộng hơn nữa.

Tiếp tục nghiên cứu cải tiến thuật toán BVCL, cải tiến cấu trúc DBV (bit vector động) sử dụng ma trận thưa để lưu trữ tidset, có thể làm giảm đáng kể không gian lưu trữ cho các bit 0. Từ đó cũng cải thiện tốc độ tìm kiếm cũng như tăng tốc độ tính toán trên các phép toán tập hợp.

TÀI LIỆU THAM KHẢO

[1] Tahrima Hashem, Md.Rezaul Karim, Md.Samiullah, Chowdhury Farhan Ahmed.(2016) An efficient dynamic superset bit-vector approach for mining frequent closed itemsets and their lattice structure”. Expert Systems With Applications 67 (2017) 252–271 .

[2] Vo.B & Le.B (2009). Fast algorithm for mining minimal generators of frequent closed itemsets and their applications. In Computers & industrial engineering, 2009. CIE 2009. (pp. 1407–1411). IEEE.

[3] Bay Vo, Tzung-Pei Hong, and Bac Le (30 October, 2011).Dynamic bit vectors: An efficient approach for mining frequent itemsets. Scientific Research and Essays Vol.6(25), pp.5358-5368

[4] Vo.B & Le.B (2011). A frequent closed itemsets lattice-based approach for mining minimal non-redundant association rules. CoRR. 1108.5253.

[5] Anh Tran, TinTruong, BacLe (2014) Simultaneous mining of frequent closed itemsets and their generators: Foundation and algorithm. Engineering ApplicationsofArtificial Intelligence 36(2014)64–80.

[6] Vo.B, Hong.T, & Le.B. (2012). DBV-Miner: A dynamic bit-vector approach for fast mining frequent closed itemsets. Expert Systems with Applications, 39, 7196–7206.

[7] Vo.B, Hong.T, & Le.B. (2013). A lattice-based approach for mining most general-ization association rules. Knowledge Based Systems, 45, 20–30.

[8] Zaki, M. J., & Hsiao, C. (2005). Efficient algorithms for mining closed itemsets and their lattice structure. IEEE Transactions on Knowledge and Data Engineering, 17, 462–478.

[9] Zaki, M. J., & Hsiao, C. (2002). CHARM: An efficient algorithm for closed itemset mining. In Proceedings of the second SIAM international conference on data mining, arlington, VA, USA, april 11–13, 2002 (pp. 457–473)

[10] Zaki, M. J., Parthasarathy, S., Ogihara, M., Li, W., et al. (1997). New algorithms for fast discovery of association rules. In KDD: vol. 97 (pp. 283–286).

[11] Han, J., Pei, J., Yin, Y., & Mao, R. (2004). Mining frequent patterns without candi-date generation: A frequent-pattern tree approach. Data Mining and Knowledge Discovery, 8, 53–87.

[12] Wille, R., 1982. Restructuring lattices theory: an approach based on hierarchies of concepts. In Ordered Sets, pp. 445–470.

[13] Wang, J., Han, J., Pei, J., 2003. Closet: searching foþr the best strategies for mining frequent closed itemsets. In: Proceedings of ACM SIGKDD’03.

[14] Dong, G., Jiang, C., Pei, J., Li, J., Wong, L., 2005. Mining succinct systems of minimal generators of formal concepts. In: Proceedings of DASFAA 2005, LNCS 3453, pp.175–187.

[15] Szathmary, L., Valtchev, P., Napoli, A., 2009. Efﬁcient vertical mining of frequent closed itemsets and generators. In: Proceedings of IDA 2009, pp. 393–404.

[16] Closed itemsets using frequent closed tidsets. In: Proceedings. Of the 5th ICDM, Washington DC, USA, pp. 633–636.

[17] Hashem, T., Ahmed, C. F., Samiullah, M., Akther, S., Jeong, B., & Jeon, S. (2014). An eﬃcient approach for mining cross-level closed itemsets and minimal associ-ation rules using closed itemset lattices.Expert Systems With Applications, 41, 2914–2938

[18] Zaki, M. J., & Phoophakdee, B. (2003). MIRAGE: A framework for mining, explor-ing and visualizing minimal association rules. Technical report. Computer Sci-ence Dept., Rensselaer Polytechnic Inst.

[19] Agrawal, R., & Srikant, R. (1994). Fast algorithms for mining association rules in large databases. In VLDB’94, proceedings of 20th international conference on very large data bases, September 12 – 15, 1994, santiago de chile, chile (pp.487–499).

[20] Han, J., Pei, J., Yin, Y., & Mao, R. (2004). Mining frequent patterns without candi-date generation: A frequent-pattern tree approach. Data Mining and Knowledge Discovery, 8, 53–87.

[21] Lucchese, C., Orlando, S., & Perego, R. (2006). Fast and memory eﬃcient mining of frequent closed itemsets. IEEE Transactions on Knowledge and Data Engineering, 18, 21–36.

[22] Uno, T., Kiyomi, M., & Arimura, H. (2004b). LCM ver. 2: Eﬃcient mining algorithms for frequent/closed/maximal itemsets. FIMI ’04, proceedings of the IEEE ICDM workshop on frequent itemset mining implementations, Brighton, UK, November 1, 2004.

[23] Zaki, M. J. (2000). Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering, 12, 372–390.

[24] Dong, J., & Han, M. (2007). BitTableFI: An eﬃcient mining frequent itemsets algo-rithm. Knowledge Based Systems, 20, 329–335.

[25] Song, W., Yang, B., & Xu, Z. (2008). Index-BitTableFI: An improved algorithm for mining frequent itemsets. Knowledge Based Systems, 21, 507– 513.

[26] Nori, F., Deypir, M., & Sadreddini, M. H. (2013). A sliding window based algorithm for frequent closed itemset mining over data streams. Journal of Systems and Software, 86, 615–623.

[27] Yen, S.-J., Lee, Y.-S., & Wang, C.-K. (2014).An eﬃcient algorithm for incrementally mining frequent closed itemsets. Applied intelligence, 40, 649– 668.

[28] Le.B & Vo.B (2015).An n-list-based algorithm for mining frequent closed patterns. Expert Systems with Applications, 42, 6648–6657.

[29] Deng, Z., Wang, Z., & Jiang, J. (2012). A new algorithm for fast mining frequent item-sets using n-lists. SCIENCE CHINA Information Sciences, 55, 2008–2030.

Xem toàn bộ nội dung bài viết ᛨ