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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

19
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết đề xuất một cách tiếp cận khai thác tập tương quan hiếm có trọng số theo hướng tiếp cận không thỏa tính chất bao đóng giảm và đồng thời thỏa ràng buộc phản đơn điệu của độ đo tương quan all-confidence.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Huế, ngày 07-08/6/2019 DOI: 10.15625/vap.2019.00058 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 Phan Thành Huấn1,2, Lê Hoài Bắc3 1 Khoa Toán - Tin học, Trƣờng Đại học Khoa học Tự nhiên, Đại học Quốc gia Tp. Hồ Chí Minh 2 Bộ môn Tin học, Trƣờng Đại học Khoa học Xã hội và Nhân văn, Đại học Quốc gia Tp. Hồ Chí Minh 3 Khoa Công nghệ thông tin, Trƣờng Đại học Khoa học Tự nhiên, Đại học Quốc gia Tp. Hồ Chí Minh huanphan@hcmussh.edu.vn, lhbac@fithcmus.edu.vn TÓM TẮT: Khai thác tập hiếm là một kỹ thuật khai thác rất quan trọng cùng với các ứng dụng tiềm năng như phát hiện các cuộc tấn công máy tính, giao dịch gian lận trong các tổ chức tài chính, tin sinh học, y tế. Trong khai thác dữ liệu truyền thống trên dữ liệu giao dịch thì các item không có trọng số (như nhau). Tuy nhiên, trong một số ứng dụng thực tế thì mỗi item có trọng số khác nhau (thể hiện mức độ quan trọng hay ý nghĩa của từng item) - cần khai thác các tập phổ biến/ hiếm có trọng số của item. Trong bài viết này, chúng tôi đề xuất một cách tiếp cận khai thác tập tương quan hiếm có trọng số theo hướng tiếp cận không thỏa tính chất bao đóng giảm và đồng thời thỏa ràng buộc phản đơn điệu của độ đo tương quan all-confidence. Thuật toán chúng tôi đề xuất được gọi là ALLCONF-CORSI. Chúng tôi tiến hành thực nghiệm thuật toán trên bộ dữ liệu thực của UCI và bộ dữ liệu giả lập của trung tâm nghiên cứu IBM Almaden, cho thấy thuật toán đề xuất hiệu quả. Từ khóa: độ đo all-confidence, tập tương quan hiếm có trọng số, thuật toán ALLCONF-CORSI. I. GIỚI THIỆU Thuật toán khai thác luật kết hợp truyền thống [1-3] chỉ dùng một giá trị ngƣỡng phổ biến tối thiểu minsup với ngầm định là các mặt hàng có cùng tính chất và tần số trong dữ liệu, điều này không thực tế. Trong kinh doanh bán lẻ, thƣờng các mặt hàng thiết yếu, hàng tiêu dùng và các sản phẩm giá rẻ đƣợc mua nhiều hơn, trong khi các mặt hàng xa xỉ và các sản phẩm giá trị cao lại ít đƣợc mua (tập hiếm). Nếu chọn minsup quá cao thì các mặt hàng đƣợc khai thác thông thƣờng có giá thành thấp và mang lại lợi nhuận không cao cho doanh nghiệp. Ngƣợc lại, nếu chọn minsup quá thấp thì các mặt hàng đƣợc khai thác quá lớn, điều này làm cho doanh nghiệp khó khăn khi ra quyết định kinh doanh. Từ đó, có nhiều thuật toán khai thác tập hiếm đƣợc đề xuất nhƣ Apriori-Inverse, Rarity, Walky-G. Các thuật toán này dựa trên Apriori [8-9], Eclat [10] và có nhiều hạn chế nhƣ quét dữ liệu nhiều lần, sử dụng nhiều bộ nhớ, các chiến lƣợc cắt tỉa (không tái sử dụng cho lần khai thác tiếp theo). Những năm cuối của thế kỷ 20, C.H.Cai và đồng sự [5] đã đề xuất mô hình khai thác tập phổ biến có trọng số của mục hàng (mức độ quan trọng hay mức ý nghĩa của các mục hàng là khác nhau) chứa nhiều tri thức hơn so với khai thác tập phổ biến truyền thống (không trọng số). Sau đó, có nhiều tác giả nghiên cứu và đề xuất thuật toán [5-6] giải quyết vấn đề này. Tuy nhiên, các thuật toán đều tiếp cận và giải quyết theo hƣớng thỏa tính chất bao đóng giảm. Năm 2003, F.Tao có bàn luận đến hƣớng giải quyết bài toán trên theo cách tiếp cận “không thỏa tính chất bao đóng giảm”, điều này làm gia tăng đáng kể không gian tìm kiếm. Nhƣng ở công trình [6] F.Tao và đồng sự vẫn giải quyết bài toán theo hƣớng thỏa tính chất bao đóng giảm và thuật toán tựa Apriori. Trong những năm gần đây, S. Kamepalli cùng đồng sự đề xuất thuật toán IWI [7] sử dụng cấu trúc FP-Tree và khai thác tập hiếm có trọng số theo hƣớng tiếp cận không thỏa tính chất bao đóng giảm. Trong những năm gần đây, để đáp ứng nhu cầu ứng dụng khai thác dữ liệu trong các bài toán tiềm năng nhƣ phát hiện các cuộc tấn công máy tính, giao dịch gian lận trong các tổ chức tài chính, tin sinh học, y tế,… S. Bouasker và đồng sự [10] đã đề xuất thuật toán CORI khai thác tập hiếm không trọng số và kết hợp độ đo tƣơng quan bond [4] (tương quan giữa độ phổ biến và độ phủ của tập mục hàng trong các giao dịch). Thuật toán sử dụng cấu trúc IT-Tree khai thác tập hiếm và từ tập hiếm này xác định tập tƣơng quan hiếm. Tuy nhiên, thuật toán CORI khai thác tập tƣơng quan hiếm trên dữ liệu không có trọng số. Từ những khảo sát trên, chúng tôi đề xuất thuật toán giải quyết bài toán khai thác tập tƣơng quan hiếm có trọng số “không thỏa tính chất bao đóng giảm”, đây là thách thức lớn. Trong bài toán này, chúng tôi giải quyết kết hợp khai thác tập hiếm có trọng số và độ đo tƣơng quan all_confidence [4] (tương quan giữa độ phổ biến tập mục hàng và độ phổ biến tối đại của mục hàng trong tập). Dựa vào tập tương quan hiếm có trọng số đã tìm đƣợc, chúng tôi khai thác luật kết hợp hiếm và tất cả luật kết hợp hiếm đều có độ tin cậy nhỏ hơn ngƣỡng minallconf cho trƣớc. Thuật toán đề xuất bao gồm các thuật toán con nhƣ sau: - Xây dựng mảng Index_COOC chứa các items đồng xuất hiện và các item xuất hiện ít nhất trong một giao dịch của từng item hạt nhân; - Xây dựng cây nLOOC-Tree chứa các mẫu xuất hiện ít nhất trong một giao dịch của item hạt nhân; - Thuật toán ALLCONF-CORSI khai thác hiệu quả tập tƣơng quan hiếm có trọng số kết hợp độ đo tƣơng quan All-Confidence dựa trên mảng Index_LOOC và cây nLOOC-Tree.
Phan Thành Huấn, Lê Hoài Bắc 451 Trong phần 2, bài báo trình bày các khái niệm cơ bản về khai thác tập phổ biến, tập hiếm không trọng số và có trọng số. Phần 3, xây dựng thuật toán xác định mảng chứa itemset đồng xuất hiện và itemset xuất hiện ít nhất trong một giao dịch của từng item hạt nhân, danh sách cây nLOOC-Tree và thuật toán ALLCONF-CORSI khai thác tập tƣơng quan hiếm có trọng số. Kết quả thực nghiệm đƣợc trình bày trong phần 4 và kết luận ở phần 5. II. CÁC VẤN ĐỀ LIÊN QUAN A. Khai thác tập phổ biến và tập hiếm không trọng số Cho I = {i1, i2,..., im} là tập gồm m mục hàng, mỗi mục hàng gọi là item. Tập các item X ={i1, i2,..., ik}, ij I (1 j k) gọi là itemset, itemset có k item gọi là k-itemset. Ɗ là dữ liệu giao dịch, gồm n bản ghi phân biệt gọi là tập các giao dịch T = {t1, t2,..., tn}, mỗi giao dịch tk ={ik1, ik2,..., ikm}, ikj I (1 kj m). Định nghĩa 1: Độ phổ biến (support) của itemset X I, ký hiệu sup(X) - tỷ lệ giữa số giao dịch trong Ɗ có chứa X và n giao dịch. Định nghĩa 2: Cho X I, X gọi là itemset phổ biến nếu sup(X) ≥ minsup, trong đó minsup là ngƣỡng phổ biến tối thiểu. Ký hiệu FI là tập hợp các itemset phổ biến. Định nghĩa 3: Cho X I, X gọi là itemset hiếm - nếu sup(X) < minsup. Ký hiệu RI là tập hợp chứa các itemset hiếm. Tính chất 1: X Y, sup(Y) ≥ minsup: sup(X) ≥ minsup; Tính chất 2: ik I, sup(ik) < minsup: ik RI; Tính chất 3: X Y, sup(X) < minsup: sup(Y) < minsup và X, Y RI. Cho dữ liệu giao dịch Ɗ trong Bảng 1. Bảng 1. Dữ liệu giao dịch Ɗ Mã giao dịch Tập mục t1 A C E F t2 A C G t3 E H t4 A C D F G t5 A C E G t6 E t7 A B C E t8 A C D t9 A B C E G t10 A C E F G Ví dụ 1: Dữ liệu giao dịch Ɗ trong Bảng 1, có 8 item riêng biệt I = {A, B, C, D, E, F, G, H} và 10 giao dịch T = {t1, t2, t3, t4, t5, t6, t7, t8, t9, t10} với giá trị ngƣỡng minsup = 0,20, ta có: Xét itemset X ={A, C, E}, sup({A,C,E}) = 0,50 ≥ minsup, ta nói: ”X ={A, C, E} phổ biến với minsup = 0,20”; Theo tính chất 1 thì các tập con của X ={A, C, E} cũng phổ biến, nghĩa là tất cả tập con của X đều phổ biến - sup({A}) = 0,80; sup({C}) = 0,80; sup({E}) = 0,70; sup({A, C}); sup({A, E}) = 0,50; sup({C, E}) = 0,50 ≥ minsup. Theo tính chất 2, Y = {H} thì sup({H}) = 0,10 < minsup, ta nói: ”Y = {H} itemset hiếm ngƣỡng minsup = 0,20”; Theo tính chất 3 thì các tập cha của Y ={H} cũng là itemset hiếm, nghĩa là Y = {E, H} cũng itemset hiếm, với sup({E, H}) = 0,10 < minsup = 0,20. B. Khai thác tập phổ biến và tập hiếm có trọng số Trong thực tế, nhiều ứng dụng tiềm năng cần khai thác các tập hiếm nhƣ ứng dụng phát hiện các cuộc tấn công máy tính, giao dịch gian lận trong các tổ chức tài chính, tin sinh học, y tế,…. Nhiều tác giả đã đề xuất thuật toán [7-10] khai thác tập hiếm thỏa một hoặc hai ngƣỡng hoặc tập tƣơng quan hiếm [11]. Sau đây là các khái niệm liên quan: Cho I = {i1, i2,..., im} là tập gồm m mục hàng, mỗi mục hàng gọi là item. Tập SIG = {sigi1, sigi2,..., sigim}, sigik [0, 1] là tập các mức ý nghĩa hay mức độ quan trọng của từng item (trọng số của từng mục hàng). Tập các item X ={i1, i2,..., ik}, ij I (1 j k)gọi là itemset, itemset có k item gọi là k-itemset. Ɗ là dữ liệu giao dịch, gồm n bản ghi phân biệt gọi là tập các giao dịch T={t1, t2,..., tn}, mỗi giao dịch tk ={ik1, ik2,..., ikm}, ikj I (1 kj m). Định nghĩa 4: Cho X I, mức ý nghĩa của itemset X đƣợc tính sig(X)=max(sigi1, sigi2,..., sigik), ij X (1 j k). Định nghĩa 5: Cho X I, X gọi là itemset phổ biến nếu sigsup(X) ≥ minsigsup, trong đó minsigsup là ngƣỡng mức ý nghĩa phổ biến tối thiểu (do người dùng chỉ định). Tập hợp chứa các itemset phổ biến có trọng số gọi là tập phổ biến có trọng số, ký hiệu là FSI.
452 KHAI THÁC TẬP TƢƠNG QUAN HIẾM CÓ TRỌNG SỐ KẾT HỢP ĐỘ ĐO ALL-CONFIDENCE Mức ý nghĩa phổ biến của itemset X: sigsup(X) = sig(X) sup(X) (1) Định nghĩa 6: Cho X I, X đƣợc gọi là itemset hiếm có trọng số, nếu sigsup(X) < minsigsup. Tập hợp chứa các itemset hiếm có trọng số gọi là tập hiếm có trọng số, ký hiệu là RSI. Tính chất 4: (mở rộng tính chất 2) ik I, sigsup(ik) < minsigsup: ik RSI. Định nghĩa 7: Cho X I. Độ đo all_confidence của itemset X đƣợc tính: sup( X ) all _ conf ( X ) (2) max(sup( i j )| i j X) Độ đo all_confidence thỏa tính chất bao đóng giảm: nếu X’ X thì all_conf(X’) ≥ all_conf(X). Ta có thể nói: tất cả các luật kết hợp sinh từ itemset X thì đều có độ tin cậy conf lớn hơn hoặc bằng ngƣỡng all_conf tối thiểu min_allconf. Định nghĩa 8: Cho X RSI, X đƣợc gọi là itemset tƣơng quan hiếm có trọng số, nếu all_conf(X) min_allconf, trong đó min_allconf là ngƣỡng độ tin cậy tối thiểu (do người dùng chỉ định). Tập hợp chứa các itemset tƣơng quan hiếm có trọng số gọi là tập tương quan hiếm có trọng số, ký hiệu là CORSI. Tính chất 5: (mở rộng tính chất 4) ik I, sigsup(ik) < minsigsup: all_conf(ik) = 1 và ik CORSI. Bảng 2. Mức ý nghĩa của từng item trong Ɗ Mục hàng A B C D E F G H Mức ý nghĩa (sigi) 0,55 0,70 0,50 0,65 0,40 0,60 0,30 0,80 Ví dụ 2: Cho Ɗ trong Bảng 1, và mỗi item có mức ý nghĩa đƣợc cho trong Bảng 2 và minsigsup = 0,20 Xét itemset Y ={A,C,G}, ta có: sup({A,C,G}) = 0,50; sig({A,C,G}) = max(sigA, sigC, sigG) = max(0,55; 0,50; 0,30) = 0,55 và sigsup = 0,55 0,50=0,275 ≥ minsigsup=0,20 - ta nói: ”Y ={A,C,G} là itemset phổ biến có trọng số”; Theo tính chất 1 (mở rộng cho trƣờng hợp có trọng số) thì các tập con của Y ={A,C,G} cũng phổ biến, nghĩa là tất cả tập con của Y đều phổ biến - Các con của Y là Ysub = {(A; 0,44), (C; 0,40), (G; 0,15), (AC; 0,44), (AG; 0,275), (CG; 0,25)}, tuy nhiên chỉ có các itemset {A, C, AC, AG, CG} là phổ biến; còn itemset {G}, ta có: sup({G}) = 0,50; sig({G}) = 0,30 và sigsup({G}) = 0,15 < minsigsup = 0,20 là không phổ biến. Điều này cho chúng ta thấy: “Khai thác tập phổ biến có trọng số (mức ý nghĩa của từng item) thì tính chất 1 là không thỏa”. Theo tính chất 4, xét itemset Z = {G} có sup({G}) = 0,50; sig({G}) = 0,30 và sigsup({G}) = 0,15 < minsigsup = 0,20, ta nói: “Itemset Z = {G} là itemset hiếm có trọng số”; Theo tính chất 2 thì các tập cha của Z ={G} cũng không phổ biến. Tuy nhiên, ta có Z ={G} Y = {A,C,G}, mà sup({A,C,G}) = 0,50; sig({A,C,G}) = max(0,55; 0,50; 0,30) = 0,55 và sigsup({A,C,G}) = 0,55 0,50=0,275 ≥ minsigsup=0,20 ; Y = {A,C,G} là itemset phổ biến. Điều này cho ta thấy: ”Khai thác tập hiếm có trọng số (mức ý nghĩa của từng item) thì tính chất 2 là không thỏa ”. Bảng 3. Tập RSI, CORSI trên dữ liệu giao dịch Ɗ với minsigsup = 0,15 Tập tương quan hiếm CORSI Tập tương quan hiếm CORSI Tập hiếm RSI k-itemset min_allconf = 0,25 min_allconf = 0,30 #RSI = 26 #CORSI = 23 #CORSI = 6 1 H, B, D H, B, D H, B, D BA, BG, BE, BG, DA, DC, DG, DF, BE, BA, BC, DA, DC, DF, FE, DF, FG, EG 2 FE, FG, EG FG, EG BEA, BEC, BAC, BGE, BGA, BGC, BEA, BEC, BAC, DAC, FEA, 3 DAC, DFA, DFC, DGA, DGC, DFG, FEC, FGA, FGC FEA, FEC, FGA, FGC, FEG BEAC, BGEA, BGEC, BGAC, BEAC, FEAC, FGAC 4 DFAC,DGAC, DFGA, DFGC, FEAC, FGAC, FEGA, FEGC 5 BGEAC, DFGAC, FEGAC Trong bảng 3, cho thấy tập hiếm có trọng số RSI và tập tƣơng quan hiếm CORSI chứa k-itemset với minsigsup = 0,15. Số lƣợng tập hiếm |RSI| = 46, số lƣợng tập tƣơng quan hiếm |CORSI|0,25 = 23 và số lƣợng tập tƣơng quan hiếm |CORSI|0,30 = 6. Tỷ suất CORSI 0,25 RSI 23 46 100% 50% . Qua đó, ta dễ dàng thấy mối quan hệ giữa tập hiếm và tập tƣơng quan hiếm kết hợp độ đo all_confidence nhƣ sau: CORSI RSI.
Phan Thành Huấn, Lê Hoài Bắc 453 C. Tổ chức lưu trữ dữ liệu giao dịch Lƣu trữ dữ liệu giao dịch dạng bit là cấu trúc hiệu quả trong khai thác tập phổ biến [12]. Chuyển đổi dữ liệu giao dịch thành ma trận nhị phân BiM, trong đó mỗi dòng ứng với một giao dịch và mỗi cột ứng với một item. Nếu item thứ ik xuất hiện trong giao dịch tj thì bit thứ k của dòng tj trong BiM mang giá trị 1, ngƣợc lại mang giá trị 0. III. CÁC THUẬT TOÁN A. Tập chiếu và itemset đồng xuất hiện Tập chiếu của item ik trên dữ liệu giao dịch Ɗ: (ik)={t Ɗ│ik t} là tập các giao dịch có chứa item ik. sup(ik) = | ( ik)| (3) Tập chiếu của itemset X ={i1, i2,..., ik}, ij I (1 j k), (X) = (i1) (i2)… (ik). sup(X) = | ( X )| (4) Ví dụ 3: Theo Bảng 1, có (A) = {t1, t2, t4, t5, t7, t8, t9, t10} và (B) = {t7, t9}. Khi đó, (AB) = (A) (B)= {t1, t2, t4, t5, t7, t8, t9, t10} {t7, t9} = {t7, t9}, (B) (A) và (AB) (A). Để tránh trùng lặp không gian sinh tập hiếm có trọng số, chúng tôi đƣa ra các định nghĩa và bổ đề rút gọn không gian sinh tập hiếm có trọng số nhƣ sau: Định nghĩa 9: Cho ik I (i1 i2 … im) thứ tự giảm dần theo mức ý nghĩa, ta gọi ik là item hạt nhân. Tập Xlexcooc I gọi đồng xuất hiện có thứ tự với item ik: Xlexcooc là tập các item có thứ tự theo độ phổ biến, đồng xuất hiện cùng ik và ( ik) ( ik ij) , i j Xlexcooc, i k ij. Ký hiệu, lexcooc(ik) = Xlexcooc. Định nghĩa 10: Cho ik I (i1 i2 … im) thứ tự giảm dần theo mức ý nghĩa, ta gọi ik là item hạt nhân. Tập Ylexlooc I chứa các item xuất hiện có thứ tự cùng với ik ít nhất trong một giao dịch, nhƣng không đồng xuất hiện: 1 | ( ik ij) | < | ( ik)| , i j Ylexlooc, i k ij. Ký hiệu, lexlooc(ik) = Ylexlooc. B. Thuật toán sinh itemset đồng xuất hiện có thứ tự Trong phần này, trình bày thuật toán sinh các item đồng xuất hiện và xuất hiện ít nhất trong một giao dịch với item hạt nhân, đƣợc lƣu trữ vào mảng Index_COOC. Mỗi phần tử trong Index_COOC gồm 4 thành phần thông tin: - Index_COOC[k].item: item hạt nhân thứ k; - Index_COOC[k].sup: độ phổ biến của item hạt nhân thứ k; - Index_COOC[k].cooc: các item đồng xuất hiện cùng item hạt nhân thứ k dạng bit; - Index_COOC[k].looc: các item xuất hiện cùng item hạt nhân thứ k ít nhất trong một giao dịch dạng bit; Mã giả thuật toán 1. Xây dựng bảng Index_COOC Đầu vào: Dữ liệu giao dịch Ɗ Đầu ra: Mảng Index_COOC, ma trận BiM 1: Với mỗi phần tử k của mảng Index_COOC thực hiện: 2: Index_COOC[k].item = ik 3: Index_COOC[k].sup = 0 4: Index_COOC[k].cooc= 2m - 1 5: Index_COOC[k].looc= 0 6: Với mỗi giao dịch ti thực hiện: 7: Lƣu giao dịch ti vào ma trận BiM 8: Với mỗi item k có trong giao dịch ti thực hiện: 9: Index_COOC[k].cooc = Index_COOC[k].cooc AND vectorbit(ti) 10: Index_COOC[k].looc = Index_COOC[k].looc OR vectorbit(ti) 11: Index_COOC[k].sup = Index_COOC[k].sup + 1 12: Sắp xếp mảng Index_COOC giảm dần theo sig 13: Với mỗi phần tử k của mảng Index_LOOC: 14: Index_LOOC[k].cooc= lexcooc(ik) 15: Index_LOOC[k].looc= lexclooc(ik) 16: Trả về mảng Index_COOC, ma trận BiM Dòng 1 đến dòng 5: khởi tạo cho mảng Index_COOC. Dòng 6 duyệt dữ liệu giao dịch, ứng với từng giao dịch: nếu có chứa item thứ k thì thực hiện phép AND trên bit để xác định các item đồng xuất hiện với item k (dòng 9) và thực hiện pháp OR trên bit để xác định các item xuất hiện với item k ít nhất trong một giao dịch (dòng 10).
454 KHAI THÁC TẬP TƢƠNG QUAN HIẾM CÓ TRỌNG SỐ KẾT HỢP ĐỘ ĐO ALL-CONFIDENCE Khởi tạo mảng Index_COOC: (thành phần cooc và looc biểu diễn dạng bit) số item là m = 8 item A B C D E F G H sup 0 0 0 0 0 0 0 0 cooc 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 looc 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 Đọc giao dịch t1: {A, C, E, F} có biểu diễn dạng bit là 10101100 item A B C D E F G H sup 1 0 1 0 1 1 0 0 cooc 10101100 11111111 10101100 11111111 10101100 10101100 11111111 11111111 looc 10101100 00000000 10101100 00000000 10101100 10101100 00000000 00000000 Duyệt lần lƣợt đến giao dịch t10: {A, C, E, F, G} có biểu diễn dạng bit là 10101110 item A B C D E F G H sup 8 2 8 2 7 3 5 1 cooc 10100000 11101000 10100000 10110000 00001000 10100100 10100010 00001001 looc 11111110 11101010 11111110 10110110 11101111 10111110 11111110 00001001 Thuật toán 1, trả về mảng Index_COOC sắp giảm theo mức ý nghĩa của item theo Bảng 4. Bảng 4. Trả về mảng Index_COOC sắp giảm theo mức ý nghĩa của item (dòng 1 đến 12) item H B D F A C E G sup 1 2 2 3 8 8 7 5 cooc E A, C, E A, C A, C C A Ø A, C looc Ø G F, G D, E, G B, D, E, F, G B, D, E, F, G A, B, C, F, G, H B, D, E, F Chỉ có itemset đồng xuất hiện của item C cần hiệu chỉnh. Ta có, cooc(C) = {A} và A C, nên lexcooc(C) = { }. Tƣơng tự, ta có looc(A) = {B, D, E, F, G} và B D F A E G, nên lexlooc(A) = {E, G}. Sau khi thực hiện dòng 13, 14 và 15, ta có kết quả trong Bảng 5. Chúng tôi thêm vào mảng Index_COOC thành phần sig để minh họa mảng có thứ tự giảm dần theo mức ý nghĩa. Bảng 5. Trả về mảng Index_COOC sắp giảm theo mức ý nghĩa của item, thành phần cooc và looc có thứ tự item H B D F A C E G sig 0,80 0,70 0,65 0,60 0,55 0,50 0,40 0,30 sup 0,10 0,20 0,20 0,30 0,80 0,80 0,70 0,50 cooc E E, A, C A, C A, C C Ø Ø Ø looc Ø G F, G E, G E, G E, G G Ø C. Thuật toán xây dựng cây nLOOC-Tree Thuật toán 2 - Từ mảng Index_LOOC xây dựng danh sách cây chứa các mẫu xuất hiện ít nhất trong một giao dịch với item hạt nhân. Mỗi cây có nút gốc là item hạt nhân và các nút con là các item xuất hiện ít nhất trong một giao dịch với item hạt nhân (có thứ tự giảm dần theo mức ý nghĩa). Mỗi nút gồm 2 thành phần: - nLOOC_Tree[k].item: item xuất hiện ít nhất với item hạt nhân (nút gốc); - nLOOC_Tree[k].sup: độ phổ biến của item xuất hiện cùng với item hạt nhân; Mã giả thuật toán 2. Xây dựng danh sách cây nLOOC-Tree Đầu vào: Ma trận BiM, Mảng Index_COOC Đầu ra: Danh sách cây nLOOC-Tree 1: Với mỗi phần tử k của mảng Index_COOC: 2: nLOOC_Tree[k].item = Index_COOC[k].item 3: nLOOC_Tree[k].sup = Index_COOC[k].sup 4: Với mỗi item ik giao dịch tℓ : 5: Với mỗi item ij Index_COOC[k].looc: 6: Nếu ij nút con của nút gốc nLOOC-Tree[k] thì 7: Thêm nút con ij vào nút gốc nLOOC-Tree[k] 8: Ngƣợc lại 9: Thêm nút con ij vào nút gốc nLOOC-Tree[k] 10: Cập nhật sup của nút con ij của nút gốc nLOOC-Tree[k] 11: Trả về danh sách cây nLOOC-Tree Cây nLOOC-Tree có các đặc trƣng nhƣ sau:
Phan Thành Huấn, Lê Hoài Bắc 455 - Chiều cao của cây nhỏ hơn hoặc bằng số lƣợng các item xuất hiện ít nhất trong một giao dịch với item hạt nhân (các item có thứ tự theo độ phổ biến). - Mỗi đƣờng đi đơn (single-path) là một mẫu có thứ tự từ nút gốc (item hạt nhân) đến nút lá và độ phổ biến của một mẫu là độ phổ biến của nút lá (ik ik+1 … iℓ). - Mỗi phân đoạn đƣờng đi đơn (sub-single-path) từ nút gốc đến nút con bất kỳ trong đƣờng đi đơn là một mẫu thứ tự và độ phổ biến của mẫu là độ phổ biến của nút con ở cuối của phân đoạn đƣờng đi đơn. Hình 1. Thuật toán 2 - sinh danh sách cây nLOOC-Tree theo mảng Index_COOC ở Bảng 5 Ví dụ 4: Xét item hạt nhân F, có đƣờng đi đơn {F E G} và sup({F,E,G}) = 0,10; phân đoạn đƣờng đi đơn {F E} và sup({F,E}) = 0,20 là độ phổ biến của nút con E. D. Thuật toán khai thác tập tương quan hiếm có trọng số ALLCONF-CORSI Thuật toán 3 - ALLCONF-CORSI khai thác các itemset tƣơng quan hiếm có trọng số từ mảng Index_COOC và cây nLOOC_Tree. Chúng tôi đề xuất các bổ đề rút gọn không gian sinh itemset tƣơng quan hiếm nhƣ sau: Bổ đề 1: lexcooc(ik) Xlexcooc thì sup(ik xsub) = sup(ik), xsub Ƥ 1(Xlexcooc). Chứng minh: lexcooc(ik) Xlexcooc, xsub Ƥ 1(Xlexcooc). Theo định nghĩa 9, ta có (ik xsub) = (ik) (xsub) = (ik) và theo phƣơng trình (3), (4) thì sup(ik xsub) = sup(ik), xsub Ƥ 1(Xlexcooc) ■. Ví dụ 5: Xét item F, với sup({F}) = 0,30. Ta có, lexcooc(F) = {A, C} thì 3 itemset kết hợp {A, C, AC} và sup({F}) = sup({FA}) = sup({FC}) = sup({FAC}) = 0,30. Bổ đề 2: lexlooc(ik) Ylexlooc thì sup(ik ysub) < sup(ik), ysub Ƥ 1(Ylexlooc). Chứng minh: Theo định nghĩa 10, 1 | ( ik ij) | < | ( ik)| , ij lexlooc(ik) và (4), ta có: sup(ik ysub) < sup(ik), ysub Ƥ 1(Ylexlooc), hiển nhiên (ik ysub) = (ik) (ysub) (ik) ■. Ví dụ 6: Xét item D, với sup({D}) = 0,20. Ta có, lexlooc(D) = {F, G} thì 3 itemset kết hợp {F, G, FG} và sup({D,F}) = sup({D,G}) = sup({D,F,G}) = 0,10 < sup({D}) = 0,10. Bổ đề 3: (Loại bỏ các item hạt nhân không sinh CORSI) nếu sig(ik) sup(ik) minsigsup thì {ik xsub} CORSI, xsub Ƥ 1(Xlexcooc). Chứng minh: Theo bổ đề 1, sup(ik xsub) = sup(ik), xsub Ƥ 1(Xlexcooc). Ta có, sigsup(ik xsub) = max(sig(ik),{sig(ij)| ij xsub}) sup(ik) = sig(ik) sup(ik) minsigsup; khi đó, {ik xsub} RSI và hiển nhiên {ik xsub} CORSI■. Ví dụ 7: Cho minsigsup = 0,15, xét item F, có sup({F})= 0,30 và lexcooc(F) = {A, C}. Khi đó, sup({F}) max(sig({F}), sig({A}), sig({C})) = sig({F}) sup({F}), = 0,60 0,30 = 0,18 minsigsup thì {FA, FC, FAC} CORSI, vì sigsup({F,A}) = sigsup({F,C}) = sigsup({G,A,C}) = 0,18 minsigsup. Bổ đề 4: (Loại bỏ các item hạt nhân không sinh CORSI) nếu sig(ik) sup(ik) < minsigsup và sup(ik) < min(sup(ij)| ij lexcooc(ik)) min_allconf thì {ik xsub} CORSI, xsub Ƥ 1(Xlexcooc). Chứng minh: Theo bổ đề 1, sup(ik xsub) = sup(ik), xsub Ƥ 1(Xlexcooc). Ta có, all_conf(ik xsub) = sup(ik xsub)/max(sup(ik), {sup(ij)| ij xsub}) = sup(ik)/max(sup(ik), {sup(ij)| ij xsub}) < sup(ik)/min({sup(ij)| ij xsub}) < sup(ik)/min({sup(ij)| ij lexcooc(ik)}) < min_allconf; khi đó, {ik xsub} CORSI, xsub Ƥ 1(Xlexcooc)■.
456 KHAI THÁC TẬP TƢƠNG QUAN HIẾM CÓ TRỌNG SỐ KẾT HỢP ĐỘ ĐO ALL-CONFIDENCE Ví dụ 8: Cho minsigsup = 0,15 và min_allconf = 0,70; xét item D, có sup({D})= 0,20 và sig({D} = 0,65 với lexcooc(D) = {A, C}. Khi đó, sigsup({D}) = 0,20 0,65 = 0,13 < minsigsup và sup({D}) = 0,20 < min(sup({A}), sup({C})) min_allconf = 0,80 0,70 = 0,56 thì {DA, DC, DAC} CORSI, vì all_conf({D,A}) = 0,25, all_conf({D,C}) = 0,25, all_conf({D,A,C}) = 0,25 < min_allconf. Bổ đề 5: (Loại bỏ các item hạt nhân không sinh CORSI) nếu sup(ik) < min(sup(ij)| ij lexlooc(ik)) min_allconf thì {ik ysub} CORSI, ysub Ƥ 1(Ylexlooc). Chứng minh: Theo bổ đề 2, sup(ik ysub) < sup(ik), ysub Ƥ 1(Ylexlooc). Ta có, all_conf(ik ysub) = sup(ik ysub)/max(sup(ik), {sup(ij)| ij ysub}) < sup(ik)/max(sup(ik), {sup(ij)| ij ysub}) < sup(ik)/min(sup(ik), {sup(ij)| ij ysub}) < sup(ik)/min(sup(ik), {sup(ij)| ij lexlooc(ik)}) < min_allconf; khi đó, {ik ysub} CORSI, ysub Ƥ 1(Ylexlooc)■. Ví dụ 9: Cho min_allconf = 0,70, xét item D, có sup({D})= 0,20 và lexlooc(D) = {G, F}. Khi đó, sup({D}) = 0,20 < 0,30 0,70 = 0,21 thì {DG, DF, DGF} CORSI, vì all_conf({D,G}) = 0,20, all_conf({D,F}) = 0,33, all_conf({D,G,F}) = 0,20 < min_allconf. Bổ đề 6: (Loại bỏ các đƣờng đi đơn không sinh CORSI) ik item hạt nhân và đƣờng đi đơn từ ik là spj (ik ik+1 … iℓ) nếu sig(ik) sup(spj) minsigsup thì {ik sspl} CORSI, sspl spj. Chứng minh: Theo đặc trƣng của cây nLOOC-Tree, sspl spj, sup(sspl) sup(spj). Ta có, sig(ik) sup(sspl) sig(ik) sup(spj) minsigsup; khi đó, {ik sspl} RSI và hiển nhiên {ik sspl} CORSI, sspl spj ■. Ví dụ 10: Cho minsigsup = 0,15, xét item hạt nhân A, có đƣờng đi đơn {A E G}, sup({A,E,G}) = 0,30 và sigsup({A,E,G}) = sig({A,E,G}) sup({A,E,G}) = sig({A}) sup({A,E,G}) = 0,55 0,30 = 0,165 minsigsup và phân đoạn đƣờng đi đơn {A E} và sigsup({A,E}) = sig({A,E}) sup({A,E}) = 0,55 0,50 = 0,275 minsigsup. Mã giả thuật toán 3. Khai thác tập tương quan hiếm có trọng số ALLCONF_CORSI Đầu vào: Mảng Dataset, Index_COOC, minsigsup và min_allconf Đầu ra: Tập tƣơng quan hiếm có trọng số CORSI 1: Với mỗi Index_COOC[k].sigsup < minsigsup 2: CORSI[k] = CORSI [k] Index_COOC[k].item//theo tính chất 5 3: Với mỗi (Index_COOC[k].item) 4: Nếu ((Index_COOC[k].looc ={ }) và không thỏa Bổ đề 3 và 4) 5: CORSI[k]= {Index_COOC[k].item xsub | xsub Ƥ 1(Index_COOC[k].cooc)} 6: Nếu ((Index_COOC[k].looc { } và không thỏa Bổ đề 5) 7: nLOOC_Tree(Index_COOC[k].item) 8: SP GenPath(Index_COOC[k].item)//sinh single-path 9: Với mỗi spj SP 10: Nếu (Index_COOC[k].sig sup(spj) < minsigsup và all_conf(Index_COOC[k].item spj) min_allconf)//Bổ đề 6 11: CORSI[k]= {Index_COOC[k].item sspl | sspl spj} 12: CORSI[k]= {Index_COOC[k].item sspl xsub| sspl spj, xsub Ƥ 1(Index_COOC[k].cooc) 13: Nếu (Index_COOC[k].sig Index_COOC[k].sup < minsigsup và không thỏa Bổ đề 4) 14: CORSI[k]= {Index_COOC[k].item xsub | xsub Ƥ 1(Index_COOC[k].cooc)} 15: Trả về tập tƣơng quan hiếm có trọng số CORSI Ví dụ 11: Cho dữ liệu giao dịch Ɗ trong Bảng 1, minsigsup = 0,15 và min_allconf = 0,25. Sau khi thực hiện thuật toán 1 và 2, ta có mảng INDEX_COOC cùng với cây nLOOC-Tree, nhƣ trong Bảng 5 và Hình 1. Dòng 1 và 2: các item hiếm theo tính chất 5 - có item H (sigsup(H) = 0,10 0,50 = 0,05 < minsigsup), B và D - CORSI[H] = {(H; 0,10; 0,08)}, CORSI[B] = {(B; 0,20; 0,14)}, CORSI[D] = {(D; 0,20; 0,13)}; Dòng 4 và 6: không sinh CORSI từ item H và G; Xây dựng các cây nLOOC-Tree cho các item cần khai phá: B, D, F, A và C ; Xét item B, nLOOC-Tree(B) có một đƣờng đi đơn {B G}, sigsup({BG}) = 0,07 < minsigsup và all_conf({BG}) = 0,20 < min_allconf , {BG} CORSI. Ta có, sigsup({B}) = 0,14 < minsigsup và không thỏa Bổ đề 4: sinh các itemset tƣơng quan hiếm có trọng số từ item B là CORSI[B] = {(BA; 0,20;0,14), (BC; 0,20;0,14), (BE; 0,20;0,14), (BAC; 0,20;0,14), (BAE; 0,20;0,14), (BCE; 0,20;0,14), (BACE; 0,20;0,14)}. Xét item D, nLOOC-Tree(D) có một đƣờng đi đơn {D F G} và sigsup({DFG}) = 0,065 < minsigsup và thỏa Bổ đề 4. Dòng 10, sinh phân đoạn đƣờng đi đơn {D F} có sigsup({DF}) = 0,065 < minsigsup và không thỏa Bổ đề 4: sinh các itemset tƣơng quan hiếm có trọng số từ item D là CORSI[D] = {(DF; 0,10;0,065), (DA; 0,20;0,13), (DC; 0,20;0,13), (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 Tập tương quan hiếm có trọng số CORSI nhân 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 [http://archive.ics.uci.edu/ml]. 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 [http://www.almaden.ibm.com]) gồm 2 tập T10I4D100K và T40I10D100K. Bảng 6. Dữ liệu thực nghiệm Số Số mục nhỏ nhất/ Số mục lớn nhất/ Số mục trung bình/ Mật độ Tên dữ liệu Số mục giao dịch giao dịch giao dịch giao dịch (%) 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. (a) Chess+min_allconf=0,30 (b) Mushroom+min_allconf=0,30 1000.000 1000.000 Thời gian (mili giây) Thời gian (mili giây) 100.000 100.000 IWI IWI 10.000 10.000 ALLCONF-CORSI ALLCONF-CORSI 1.000 1.000 0,20 0,21 0,22 0,23 0,24 0,15 0,16 0,17 0,18 0,19 minsigsup minsigsup 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. (a) T10I4D100K+min_allconf=0,25 (b) T40I10D100K+min_allconf=0,25 1000.000 100.000 Thời gian (mili giây) Thời gian (mili giây) 100.000 10.000 IWI IWI 10.000 ALLCONF-CORSI ALLCONF-CORSI 1.000 1.000 0,015 0,016 0,017 0,018 0,019 0,025 0,030 0,035 0,040 0,045 minsigsup minsigsup 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ố: sigi1 sigi2 ... sigim 1 (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. (a) Chess (b) Mushroom 1000.000 1000.000 Thời gian (mili giây) Thời gian (mili giây) 100.000 100.000 10.000 10.000 AprioriInverse AprioriInverse 1.000 ALLCONF-CORSI-0 1.000 ALLCONF-CORSI-0 .100 .100 25 30 35 40 45 10 15 20 25 30 Minsup (% ) Minsup (% ) 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. (a) T10I4D100K (b) T40I10D100K 1000.000 1000.000 Thời gian (mili giây) Thời gian (mili giây) 100.000 100.000 10.000 10.000 AprioriInverse AprioriInverse 1.000 ALLCONF-CORSI-0 1.000 ALLCONF-CORSI-0 .100 .100 0,1 0,2 0,3 0,4 0,5 0,3 0,4 0,5 0,6 0,7 Minsup (% ) Minsup (% ) 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 ﬁnancial 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.