Thuật toán hiệu quả khai thác tập tương quan hiếm có trọng số kết hợp độ đo All-confidence

DAC; 0,20;0,13)}. Phan Thành Huấn, Lê Hoài Bắc 457 Xét item F, nLOOC-Tree(F) có hai đƣờng đi đơn {F E G} và {F G}: sigsup({FEG}) = 0,06 < minsigsup và thỏa Bổ đề 4. Dòng 10, sinh phân đoạn đƣờng đi đơn {F E} có sigsup({FE}) = 0,12 < minsigsup và không thỏa Bổ đề 4, sinh các itemset tƣơng quan hiếm có trọng số từ item F là CORSI[F] = {(FE; 0,20;0,12), {(FAE; 0,20;0,12), {(FCE; 0,20;0,12), {(FACE; 0,20;0,12)}, tƣơng tự đƣờng đi đơn {F G} sinh thêm các itemset tƣơng quan hiếm có trọng số CORSI[F] = {(FG; 0,20;0,12), {(FAG; 0,20;0,12), {(FCG; 0,20;0,12), {(FACG; 0,20;0,12)}. Xét item E, cây nLOOC-Tree(E): có một đƣờng đi đơn {E G} và ssigup(EG) = 0,12 < minsigsup và không thỏa Bổ đề 4: sinh các itemset tƣơng quan hiếm có trọng số từ item E là CORSI[E] = {(EG; 0,30;0,12)}. Tập tƣơng quan hiếm có trọng số CORSI trên Ɗ ở Bảng 1 với minsigsup = 0,15 và min_allconf = 0,25: Item hạt nhân Tập tương quan hiếm có trọng số CORSI H (H;0,1;0,08) B (B;0,2;0,14) (BE;0,2;0,14) (BA;0,2;0,14) (BC;0,2;0,14) (BAE;0,2;0,14) (BCE;0,2;0,14) (BAC;0,2;0,14) (BACE;0,2;0,14) D (D;0,2;0,13) (DA;0,2;0,13) (DC;0,2;0,13) (DF;0,1;0,065) (DAC;0,2;0,13) F (FE;0,2;0,12) (FG;0,2;0,12) (FAE;0,2;0,12) (FCE;0,2;0,12) (FGA;0,2;0,12) (FGC;0,2;0,12) (FACE;0,2;0,12) (FGAC;0,2;0,12) E (EG;0,3;0,12) IV. KẾT QUẢ THỰC NGHIỆM Thực nghiệm trên máy tính Core Duo 2.0 GHz, 4GB RAM, thuật toán cài đặt trên C#, MVS 2010. Nghiên cứu thực nghiệm trên hai nhóm dữ liệu: Nhóm dữ liệu thực có mật độ dày: sử dụng dữ liệu thực từ kho dữ liệu về học máy của trƣờng Đại học California (Lichman, M. (2013). UCI Machine Learning Repository []. Irvine, CA: University of California, School of Information and Computer Science) gồm 2 tập Chess và Mushroom. Nhóm dữ liệu giả lập có mật độ thưa: sử dụng phần mềm phát sinh dữ liệu giả lập của trung tâm nghiên cứu IBM Almaden (IBM Almaden Research Center, San Joe, California 95120, U.S.A []) gồm 2 tập T10I4D100K và T40I10D100K. Bảng 6. Dữ liệu thực nghiệm Tên dữ liệu Số mục Số giao dịch Số mục nhỏ nhất/ giao dịch Số mục lớn nhất/ giao dịch Số mục trung bình/ giao dịch Mật độ (%) Chess 75 3.196 37 37 37 49,3 Mushroom 119 8.142 23 23 23 19,3 T10I4D100K 870 100.000 1 29 10 1,1 T40I10D100K 942 100.000 4 77 40 4,2 Trong bài viết này, chúng tôi đề xuất thuật toán khai thác tập tƣơng quan hiếm có trọng số kết hợp độ đo All- Confidence và giải quyết bài toán theo hƣớng sinh các tập hiếm có trọng số không thoả tính chất bao đóng giảm. Đây là đề xuất đầu tiên theo hƣớng tiếp cận trên, nên chƣa có thuật toán cùng hƣớng tiếp cận để so sánh hiệu năng thuật toán. Vì vậy, chúng tôi đề xuất so sánh hiệu năng thuật toán theo 2 thực nghiệm sau: A. Thực nghiệm thứ 1 Khai thác tập tƣơng quan hiếm có trọng số kết hợp độ đo tƣơng quan All-Confidence: Trong thực nghiệm 1, chúng tôi dựa vào thuật toán IWI [7] và cải tiến thành thuật toán khai thác tập hiếm có trọng số item đồng thời kết hợp độ đo All-Confidence, gọi là IWI. Trên cơ sở này, chúng tôi so sánh hiệu năng thuật toán IWI với thuật toán đề xuất ALLCONF-CORSI: cho minsigsup thay đổi và cố định min_allconf. Mức ý nghĩa (trọng số) của từng item đƣợc phát sinh ngẫu nhiên trong [0, 1] và cố định ngƣỡng min_allconf. 1.000 10.000 100.000 1000.000 0,20 0,21 0,22 0,23 0,24 T h ờ i g ia n ( m il i g iâ y) minsigsup (a) Chess+min_allconf=0,30 IWI ALLCONF-CORSI 1.000 10.000 100.000 1000.000 0,15 0,16 0,17 0,18 0,19 T h ờ i g ia n ( m il i g iâ y) minsigsup (b) Mushroom+min_allconf=0,30 IWI ALLCONF-CORSI Hình 2. Thời gian thực hiện ALLCONF-CORSI và IWI trên Chess, Mushroom 458 KHAI THÁC TẬP TƢƠNG QUAN HIẾM CÓ TRỌNG SỐ KẾT HỢP ĐỘ ĐO ALL-CONFIDENCE Hình 2a và 2b là kết quả thực nghiệm trên nhóm dữ liệu có mật độ cao, ta thấy thuật toán ALLCONF-CORSI nhanh hơn thuật toán IWI. 1.000 10.000 100.000 1000.000 0,015 0,016 0,017 0,018 0,019 T h ờ i g ia n ( m il i g iâ y) minsigsup (a) T10I4D100K+min_allconf=0,25 IWI ALLCONF-CORSI 1.000 10.000 100.000 0,025 0,030 0,035 0,040 0,045 T h ờ i g ia n ( m il i g iâ y) minsigsup (b) T40I10D100K+min_allconf=0,25 IWI ALLCONF-CORSI Hình 3. Thời gian thực hiện ALLCONF-CORSI và IWI trên T10I4D100K, T40I10D100K Hình 3a và 3b là kết quả thực nghiệm trên nhóm dữ liệu giả lập có mật độ thấp, ta thấy thuật toán ALLCONF- CORSI nhanh hơn thuật toán IWI. Hiệu suất của thuật toán ALLCONF-CORSI rất cao so với IWI trên dữ liệu thƣa. B. Thực nghiệm thứ 2 Khai thác ALLCONF-CORSI không trọng số: 1 2 1 mi i i sig sig sig... (5) Thuật toán ALLCONF-CORSI, có mức ý nghĩa (trọng số) các mục thỏa (5) là thuật toán khai thác tập tƣơng quan hiếm không trọng số (mức ý nghĩa các item như nhau), đồng thời ngƣỡng độ đo tƣơng quan min_allconf = 0. Trong thực nghiệm 2, chúng tôi so sánh thuật toán đề xuất ALLCONF-CORSI (có trọng số là như nhau và ngưỡng độ đo tương quan minallconf = 0, ký hiệu là ALLCONF-CORSI-0) với thuật toán AprioriInverse [8], đây là thuật toán khai thác tập tƣơng quan hiếm không trọng số hiệu quả trong những năm gần đây. .100 1.000 10.000 100.000 1000.000 25 30 35 40 45 T h ờ i g ia n ( m il i g iâ y) Minsup (% ) (a) Chess AprioriInverse ALLCONF-CORSI-0 .100 1.000 10.000 100.000 1000.000 10 15 20 25 30 T h ờ i g ia n ( m il i g iâ y) Minsup (% ) (b) Mushroom AprioriInverse ALLCONF-CORSI-0 Hình 4. Thời gian thực hiện ALLCONF-CORSI-0 và AprioriInverse trên Chess, Mushroom Hình 4a và 4b là kết quả thực nghiệm trên nhóm dữ liệu có mật độ cao, ta thấy thuật toán ALLCONF-CORSI- 0 nhanh hơn thuật toán AprioriInverse. .100 1.000 10.000 100.000 1000.000 0,1 0,2 0,3 0,4 0,5 T h ờ i g ia n ( m il i g iâ y) Minsup (% ) (a) T10I4D100K AprioriInverse ALLCONF-CORSI-0 .100 1.000 10.000 100.000 1000.000 0,3 0,4 0,5 0,6 0,7 T h ờ i g ia n ( m il i g iâ y) Minsup (% ) (b) T40I10D100K AprioriInverse ALLCONF-CORSI-0 Hình 5. Thời gian thực hiện ALLCONF-CORSI-0 và AprioriInverse trên T10I4D100K, T40I10D100K Hình 5a và 5b là kết quả thực nghiệm trên nhóm dữ liệu giả lập có mật độ thấp, ta thấy thuật toán ALLCONF- CORSI-0 hiệu quả hơn thuật toán AprioriInverse rất nhiều. Hiệu suất của thuật toán ALLCONF-CORSI-0 rất cao so với AprioriInverse trên dữ liệu thƣa. Kết quả trên cho thấy thuật toán khai thác tập tƣơng quan hiếm có trọng số ALLCONF-CORSI tốt hơn thuật toán mới gần đây. Ngoài ra, thuật toán cũng cần thực nghiệm thêm trên nhiều tập dữ liệu có mật độ khác nhau, cũng nhƣ trên nhiều dữ liệu cỡ lớn. Phan Thành Huấn, Lê Hoài Bắc 459 V. KẾT LUẬN Nhóm tác giả đã đề xuất thuật toán khai thác tập tương quan hiếm có trọng số gồm ba giai đoạn: giai đoạn thứ nhất là tính nhanh mảng Index_COOC chứa các item đồng xuất hiện và item xuất hiện với item hạt nhân ít nhất trong một giao dịch; giai đoạn thứ hai: xây dựng cây nLOOC-Tree; giai đoạn thứ ba: thuật toán ALLCONF-CORSI khai thác hiệu quả tập tương quan hiếm có trọng số dựa trên mảng Index_COOC và cây nLOOC-Tree. Với kiến trúc nhƣ trên, khi ngƣời dùng khai thác tập tƣơng quan hiếm có trọng số với ngưỡng khác thì thuật toán đề xuất chỉ thực hiện khai thác tập tƣơng quan hiếm trên mảng Index_COOC và cây nLOOC-Tree đã tính ở lần khai thác trƣớc làm giảm thời gian xử lý đáng kể. Tƣơng lai, nhóm tác giả mở rộng thuật toán để có thể khai thác tập tương quan hiếm có trọng số kết hợp độ đo Any-confidence, Bond, trên dữ liệu giao dịch có trọng số của item, đây là hƣớng nghiên cứu đang đƣợc quan tâm vì khả năng ứng dụng vào nhiều lĩnh vực, đặc biệt là trong kinh doanh, y khoa. VI. LỜI CẢM ƠN Nhóm tác giả cảm ơn sự hỗ trợ từ Trƣờng Đại học Khoa học Xã hội và Nhân văn; Đại học Khoa học Tự nhiên Đại học Quốc gia Tp.HCM. TÀI LIỆU THAM KHẢO [1] R. Agrawal, T. Imilienski, A. Swami, “Mining association rules between sets of large databases”. Proc. of the ACM SIGMOD International Conference on Management of Data, Washington, DC, pp.207-216, 1993. [2] M. J. Zaki, S. Parthasarathy, M. Ogihara, W. Li, “New Algorithms for Fast Discovery of Association Rules”. In: Proc. of the 3rd International Conference on Knowledge Discovery in Databases, pp.283-286, 1997. [3] J. Han, J. Pei, Y. Yin, R. Mao, “Mining frequent patterns without candidate generation: A frequent pattern tree approach”. Data Mining and Knowledge Discovery, 8(1) pp.53-87, 2004. [4] E. Omiecinski, “Alternative interest measures for mining associations in databases”. IEEE Transactions on Knowledge and Data Engineering, 15(1), pp.57-69, 2003. [5] C.H. Cai, A.W. Fu, C.H. Cheng, W.W. Kwong, “Mining association rules with weighted items”. Proceedings of International Database Engineering and Applications Symposium (IDEAS 98), pp.68-77, 1998. [6] F. Tao, F. Murtagh, M. Farid, “Weighted association rule mining using weighted support and significance framework”. SIGKDD’03, pp.661-666, 2003. [7] S. Kamepalli, R. S. R. Kurra, Y. K. K. Sundara, “Infrequent Pattern Mining from Weighted Transactional Data Set”. International Journal of Research Studies in Computer Science and Engineering, 2(3), pp. 1-5, 2015. [8] Y. S. Koh, N. Rountree, “Finding sporadic rules using apriori-inverse”. In PAKDD’05, 3518, pp.97-106, 2005. [9] L. Troiano, C. Birtolo, “A fast algorithm for mining rare itemsets”. IEEE 19th International Conference on Intelligent Systems Design and Applications, pp.1149-1155, 2009. [10] L. Szathmary, P. Valtchev, A. Napoli, R. Godin, ”Efficient vertical mining of minimal rare itemsets”. Proc. of the 19th International Conference on Concept Lattices and Their Applications, pp.269-280, 2012. [11] S. Bouasker, S. B. Yahia, “Key correlation mining by simultaneous monotone and anti-monotone constraints checking”. Proc. of the 2015 ACM Symposium on Applied Computing (SAC 2015), pp. 851-856, 2015. [12] Phan Thành Huấn, Lê Hoài Bắc, “Thuật toán hiệu quả khai thác tập hiếm tối thiểu”. Hội nghị Quốc gia lần thứ XI về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); tr. 497-505, 2018. AN EFFICIENT MINING ALGORITHM RARE CORRELATED SIGNIFICANCE ITEMSET COHERENCE ALL-CONFIDENCE MEASURE Phan Thanh Huan, Le Hoai Bac ABSTRACTL: Rare itemsets mining is an important task for potential applications such as the detection of computer attacks, fraudulent transactions in financial institutions, bioinformatics and medical. In the traditional data mining on transaction databases, which items have no weight (equal weight, as equal to 1). However, in real world applications are often each item has a different weight (the importance/significance of each item). Therefore, we need to mining weighted frequent/rare itemsets on transaction databases. In this paper, we proposed an algorithm for mining rare correlated significance itemsets approach based on NOT satisfy the downward closure property and coherence the anti-monotone constraint of correlation belong to the all-confidence measure. We propose an efficient algorithm called ALLCONF-CORSI. The experimental results show that the proposed algorithms perform faster than other existing algorithms on both real-life datasets of UCI and synthetic datasets generated by IBM Almaden. Keywords: all-confidence measure, rare correlated significance itemset, ALLCONF-CORSI algorithm.