Thuật toán hiệu quả khai thác tập hiếm tối thiểu

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

Thêm vào BST

Báo xấu

22
lượt xem 2
download

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

Trong khai thác dữ liệu, khai thác tập hiếm là một kỹ thuật khai thác rất quan trọ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 bài viết này, chúng tôi đề xuất thuật toán hiệu quả khai thác tập hiếm tối thiểu. Kết quả thực nghiệm trên bộ dữ liệu thực và giả lập, cho thấy thuật toán đề xuất hiệu quả hơn so với thuật toán hiện hành.

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 hiếm tối thiểu

Kỷ yếu Hội nghị KHCN 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); Hà Nội, ngày 09-10/8/2018 DOI: 10.15625/vap.2018.00065 THUẬT TOÁN HIỆU QUẢ KHAI THÁC TẬP HIẾM TỐI THIỂU Phan Thành Huấn1,2, Lê Hoài Bắc3 1 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 2 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 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: Trong khai thác dữ liệu, khai thác tập hiếm là một kỹ thuật khai thác rất quan trọ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 bài viết này, chúng tôi đề xuất thuật toán hiệu quả khai thác tập hiếm tối thiểu. Kết quả thực nghiệm trên bộ dữ liệu thực và giả lập, cho thấy thuật toán đề xuất hiệu quả hơn so với thuật toán hiện hành. Từ khóa: khai thác dữ liệu, tập hiếm, tập hiếm tối thiểu. I. GIỚI THIỆU Khai thác luật kết hợp là một kỹ thuật quan trọng trong lĩnh vực khai thác dữ liệu. Mục tiêu khai thác là phát hiện những mối liên hệ giữa các giá trị dữ liệu trong dữ liệu giao dịch. Mô hình đầu tiên của bài toán khai thác luật kết hợp là mô hình nhị phân hay còn gọi là mô hình cơ bản được Agrawal và đồng sự đề xuất vào năm 1993 [1], phân tích dữ liệu giao dịch, phát hiện các mối liên hệ giữa các tập mục hàng hoá đã bán được tại các siêu thị. Từ đó có kế hoạch bố trí, sắp xếp, kinh doanh hợp lý, đồng thời tổ chức sắp xếp các quầy gần nhau như thế nào để có doanh thu trong các phiên giao dịch là lớn nhất. Bài toán khai thác luật kết hợp là khai phá các luật kết hợp có độ phổ biến (support) cũng như độ tin cậy (confidence) lớn hơn hoặc bằng một ngưỡng phổ biến tối thiểu (minsup) và ngưỡng tin cậy tối thiểu (minconf). Các thuật toán được đề xuất để khai thác luật kết hợp chia thành 2 giai đoạn [1-5]: Giai đoạn 1: Tìm tất cả các tập mục phổ biến từ dữ liệu giao dịch thoả mãn minsup; Giai đoạn 2: Sinh các luật tin cậy kết hợp từ các tập mục phổ biến tìm thấy ở giai đoạn thứ nhất. Giai đoạn thứ nhất chiếm hầu hết thời gian cho toàn quá trình khai thác luật kết hợp [1-5]. Giá trị ngưỡng phổ biến tối thiểu minsup là yếu tố quan trọng trong quá trình rút gọn không gian tìm kiếm cũng như giới hạn các luật sinh trong giai đoạn thứ hai. Các thuật toán khai thác luật kết hợp truyền thống 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 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. Năm 1999, Liu và các đồng sự [6] đã mở rộng bài toán khai thác luật kết hợp với nhiều ngưỡng phổ biến tối thiểu (mỗi mặt hàng có một ngưỡng phổ biến tối thiểu riêng) tương ứng mỗi mặt hàng khác nhau có tính chất khác nhau và tần số giao dịch khác nhau. Nhóm tác giả này đã đề xuất thuật toán MSApriori - khai thác luật kết hợp khác nhau thỏa ngưỡng phổ biến tối thiểu khác nhau phụ thuộc vào các mặt hàng có trong luật. Từ đó, thấy được tầm quan trọng của tập hiếm, một số tác giả đã đề xuất thuật toán khai thác tập hiếm [7-10]: Thuật toán Apriori-Inverse: Koh và các đồng sự [7] đề xuất hướng tiếp cận ngược theo thuật toán Apriori trong khai thác tập hiếm tối thiểu. Thuật toán sử dụng hai ngưỡng minsup và maxsup. Thuật toán cho kết quả gồm cả các itemset có độ phổ biến bằng 0 và itemset không có trong dữ liệu giao dịch. Ngoài ra, thuật toán này còn quét dữ liệu nhiều lần. Thuật toán ARIMA: Szathmary và các đồng sự [8] đề xuất hướng tiếp cận tựa thuật toán Apriori trong khai thác tập hiếm tối thiểu. Thuật toán sử dụng cấu trúc dàn để lưu trữ dữ liệu giao dịch. Thuật toán khai thác tập hiếm tối thiểu theo hướng tiếp cận từ dưới lên - không hiệu quả khi các mẫu hiếm tập trung ở phần đỉnh. Thuật toán cho kết quả gồm cả các itemset có độ phổ biến bằng 0 và itemset không có trong dữ liệu giao dịch. Ngoài ra, thuật toán này còn quét dữ liệu nhiều lần. Thuật toán Rarity: Troiano và các đồng sự [9] đề xuất dựa trên các hạn chế của thuật toán ARIMA. Thuật toán Rarity thực hiện chiến lược duyệt từ trên xuống trên cấu trúc dàn để khai thác các itemset hiếm tập trung ở đỉnh. Ngoài ra, thuật toán Rarity khai thác tập hiếm tối thiểu không gồm các itemset có độ phổ biến bằng 0. Tuy nhiên, thuật toán này sử dụng nhiều bộ nhớ so với ARIMA. Thuật toán Walky-G: Szathmary và các đồng sự [10] đề xuất hướng tiếp cận tựa thuật toán Eclat [2] trong khai thác tập hiếm tối thiểu. Thuật toán sử dụng cấu trúc IT-Tree để lưu trữ dữ liệu giao dịch. Thuật toán cho kết quả
498 THUẬT TOÁN HIỆU QUẢ KHAI THÁC TẬP HIẾM TỐI THIỂU không gồm các itemset có độ phổ biến bằng 0. Thuật toán hiệu quả hơn so với ARIMA. Thuật toán sử dụng nhiều bộ nhớ và không hiệu quả khi ngưỡng minsup nhỏ (duyệt theo chiều sâu). Các thuật toán trên [7-10] chưa đáp ứng thực tế khi cần khai thác luật kết hợp thì người dùng có thể yêu cầu thực hiện khai thác luật kết hợp thỏa ngưỡng minsup trong nhiều chuỗi thao tác liên tiếp khác nhau. Để đáp ứng thực tế, nhóm tác giả đề xuất thuật toán NOV-mRI khai thác nhanh tập hiếm tối thiểu từ mảng chứa các itemset đồng xuất hiện và không đọc lại dữ liệu cho lần khai thác tiếp theo, bao gồm các thuật toán con sau: - Xây dựng mảng Index_LOOC chứa 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; - Thuật toán NOV-mRI khai thác hiệu quả tập hiếm tối thiểu dựa trên mảng Index_LOOC. Trong phần II, 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 và tập hiếm tối thiểu. Phần III, 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 và thuật toán NOV-mRI khai thác tập hiếm tối thiểu. Kết quả thực nghiệm được trình bày trong phần IV và kết luận ở phần V. II. CÁC VẤN ĐỀ LIÊN QUAN 2.1. Khai thác tập phổ biến Khai thác tập phổ biến truyền thống là các thuật toán [1-5] chỉ dùng duy nhất 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à độ phổ biến trong dữ liệu. Các hạn chế khi khai thác tập phổ biến: giá trị minsup cao thì các tập mục hiếm bị bỏ qua hoặc khi giá trị minsup thấp thì sinh tập mục phổ biến quá lớn. 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 riêng biệt, mỗi mục hàng gọi là item. Tập các item X { i1 ,i2 ,...,ik }, i j I ( 1 j k ) gọi là itemset, tập mục có k mục hàng 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 ti { ik1 ,ik 2 ,...,ik j },ik j I (1 k j m). Định nghĩa 1: Độ phổ biến (support) của itemset X I, ký hiệu sup(X), là số các giao dịch trong Ɗ có chứa X. Đị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. Tính chất 1: X Y: sup(Y) ≥ minsup sup(X) ≥ minsup; Tính chất 2: X Y: sup(X) < minsup sup(Y) < minsup; 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 = 2, ta có: Xét itemset X ={A, C, E}, sup(ACE) = 5 ≥ minsup, ta nói: “X ={A, C, E} phổ biến theo ngưỡng minsup = 2”; 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) = 8, sup(C) = 8, sup(E) = 7, sup(AC) , sup(AE) = 5, sup(CE) = 5 ≥ minsup. Tương tự, với Y = {H} thì sup(H) = 1 < minsup, ta nói: “Y = {H} không phổ biến theo ngưỡng minsup = 2”; Theo tính chất 2 thì các tập cha của Y ={H} cũng không phổ biến, nghĩa là Y = {EH} cũng không phổ biến, với sup(EH) = 1 < minsup = 2.
Phan Thành Huấn, Lê Hoài Bắc 499 2.2. Khai thác tập hiếm và tập hiếm tối thiểu 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 tối thiểu thỏa một hoặc hai ngưỡng. Sau đây là các khái niệm liên quan: Đị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. Định nghĩa 4: Cho X I, X gọi là itemset hiếm tối thiểu - nếu X là itemset hiếm và tất cả tập con thực sự của X là phổ biến. Ký hiệu mRI là tập hợp chứa các itemset hiếm tối thiểu. Tính chất 3: ik I, nếu sup(ik) < minsup thì ik mRI. Ví dụ 2: Dữ liệu giao dịch Ɗ trong Bảng 1 với minsup = 2, ta có: Xét itemset X ={F, G, E}, sup(FGE) = 1 < minsup, ta nói: “Itemset X ={F, G, E} là itemset hiếm”; Xét itemset Y ={H, E}, sup(HE) = 1 < minsup, ta nói: “Itemset Y ={H, E} là itemset hiếm”; Ngoài ra, itemset X ={F, G, E} còn là itemset hiếm tối thiểu, nghĩa là các tập con thực sự của itemset X là phổ biến: sup(F) = 3, sup(G) = 5, sup(E) = 7, sup(FG) = 2, sup(FE) = 2, sup(GE) = 3 minsup = 2. Trong khi đó, itemset Y = {H, E} không là itemset hiếm tối thiểu, do sup(H) = 1 < minsup. Theo tính chất 3 thì các item có độ phổ biến nhỏ hơn minsup thì thuộc mRI, ta có: item H, sup(H) = 1 < minsup, suy ra item H là item hiếm tối thiểu. Bảng 2. Tập FI, RI và mRI trên dữ liệu giao dịch Ɗ với minsup =2 Tập hiếm Tập phổ biến FI Tập hiếm RI k-itemset tối thiếu mRI #FI = 39 #RI = 26 #mRI = 5 1 B, D, F, G, E, A, C H H BE, BA, BC, DA, DC, FA, FC, FG, FE, HE, DF, DG, BG BG, DF, DG 2 GA, GC, GE, EA, EC, AC BAC, BEA, BEC, DAC, FAC, FAG, FAE, BGE, BGC, BGA, DFG, DFC, DFA, FGE 3 FCG, FCE, GAC, GAE, GCE, EAC DGA, DGC, FGE BEAC, FACG, FACE, GACE BEFC, BGEA, BGAC, DFGC, DFGA, 4 DFAC, DGAC, FGEA, FGEC 5 BGEAC, DFGAC, FGEAC Trong bảng 2, cho thấy tập phổ biến FI, tập hiếm RI và tập hiếm tối thiểu mRI chứa k-itemset với minsup = 2. Số lượng tập mục phổ biến |FI| = 39, số lượng tập mục hiếm |RI| = 26 và số lượng tập mục hiếm tối phổ |mRI| = 5. Tỷ suất mRI RI 5 26 100% 19% . Qua đó, ta dễ dàng thấy mối quan hệ giữa tập itemset hiếm và tập itemset hiếm tối thiểu như sau: mRI RI. 2.3. 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 dữ liệu hiệu quả trong khai thác tập phổ biến [4, 5]. Chuyển đổi dữ liệu giao dịch thành một ma trận nhị phân BiM, trong đó mỗi dòng tương ứng với một giao dịch và mỗi cột tương ứng với một mục hàng. Nếu mục hàng thứ ik xuất hiện trong giao dịch tj thì bit thứ k của dòng tj trong BiM sẽ mang giá trị 1, ngược lại sẽ mang giá trị 0. Mã giao dịch A B C D E F G H t1 1 0 1 0 1 1 0 0 t2 1 0 1 0 0 0 1 0 t3 0 0 0 0 1 0 0 1 t4 1 0 1 1 0 1 1 0 t5 1 0 1 0 1 0 1 0 t6 0 0 0 0 1 0 0 0 t7 1 1 1 0 1 0 0 0 t8 1 0 1 1 0 0 0 0 t9 1 1 1 0 1 0 1 0 t10 1 0 1 0 1 1 1 0 Hình 1. Biểu diễn dạng bit của dữ liệu giao dịch Ɗ
500 THUẬT TOÁN HIỆU QUẢ KHAI THÁC TẬP HIẾM TỐI THIỂU III. CÁC THUẬT TOÁN 3.1. Tập chiếu và itemset đồng xuất hiện Tập chiếu của mục hàng ik trên dữ liệu giao dịch Ɗ: (ik)={t Ɗ│ik t} là tập các giao dịch có chứa mục hàng ik ( - đơn điệu giảm) . sup(ik) = | ( ik)| (1) Tập chiếu của tập mục X { i1 ,i2 ,...,ik }, i j I (1 j k ) , (X) = (i1) (i2)… (ik). sup(X) = | ( X )| (2) Ví dụ 3: Theo Bảng 1, có (A) = {1, 2, 4, 5, 7, 8, 9, 10} và (B) = {7, 9}. Khi đó, (AB) = (A) (B)= {1, 2, 4, 5, 7, 8, 9, 10} {7, 9} = {7, 9}, (B) (A) và (AB) (A). Định nghĩa 5: Cho ik I, ta gọi ik là item hạt nhân. Tập Xcooc I gọi đồng xuất hiện với ik: Xcooc là tập các item xuất hiện cùng ik thì ( ik) ( ik xcooc) , xcooc Ƥ 1(Xcooc). Ký hiệu, cooc(ik) = Xcooc. Ví dụ 4: Xem item B là item hạt nhân, ta xác định được itemset đồng xuất hiện cùng độ phổ biến với item B là cooc(B) = {A, C, E} và sup(B) = sup(BACE) = 2. Định nghĩa 6: Cho ik I, ta gọi ik là item hạt nhân. Tập Ylooc I chứa các item xuất hiện 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 ylooc) | < | ( ik)| , ylooc Ƥ 1(Ylooc). Ký hiệu, looc(ik) = Ylooc. Ví dụ 5: Xem item G là item hạt nhân, ta xác định được các item xuất hiện cùng với item G ít nhất trong một giao dịch là looc(G) = {B, D, E, F} có (G) = {2, 4, 5, 9, 10} và (GB) = {9}, (GE) = {5, 9, 10}. 3.2. Thuật toán sinh itemset đồng xuất hiện có thứ tự Trong phần này, chúng tôi trình bày thuật toán sinh các item đồng xuất hiện và item 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 có 4 thành phần thông tin sau: - 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 tăng dần theo sup 13: Trả về mảng Index_COOC, ma trận BiM Từ dòng 1 đến dòng 5 là các bước 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 ta xem xét có chứa item thứ k thì thực hiện phép toán 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 toán 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, nhưng không là đồng xuất hiện (dòng 10).
Phan Thành Huấn, Lê Hoài Bắc 501 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 tăng theo độ phổ biến của item theo Bảng 3. Bảng 3. Trả về mảng Index_COOC sắp tăng theo độ phổ biến của item Item H B D F G E A C Sup 1 2 2 3 5 7 8 8 Cooc E A, C, E A, C A, C A, C Ø C A Looc Ø G F, G D, E, G B, D, E, F A, B, C, F, G, H B, D, E, F, G B, D, E, F, G Để tránh trùng lặp không gian sinh tập hiếm tối thiểu, 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 tối thiểu như sau: Định nghĩa 7: Cho ik I (i1  i2  …  im) thứ tự theo độ phổ biến, 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 xlexcooc) , xlexcooc Ƥ 1(Xlexcooc), i j Xlexcooc, i k  ij. Ký hiệu, lexcooc(ik) = Xlexcooc. Định nghĩa 8: Cho ik I (i1  i2  …  im) thứ tự theo độ phổ biến, 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 ylexlooc) | < | ( ik)| , ylexlooc Ƥ 1(Ylexlooc), i j Ylexlooc, i k  ij. Ký hiệu, lexlooc(ik) = Ylexlooc. 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 7, ta có (ik xsub) = (ik) (xsub) = (ik) và theo phương trình (1), (2) thì sup(ik xsub) = sup(ik), xsub Ƥ 1(Xlexcooc) ■. Ví dụ 6: Xét item F, với sup(F) = 3. 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) = 3. Bổ đề 2: nếu lexcooc(ik) = Xlexcooc và sup(ik) < minsup thì {ik xsub} RI, xsub Ƥ 1(Xlexcooc). Chứng minh: theo bổ đề 1, ta có sup(ik xsub) = sup(ik) < minsup, nên {ik xsub} RI, xsub Ƥ 1(Xlexcooc) ■. Ví dụ 7: Cho minsup = 5, xét item F, có sup(F)= 3< minsup. Theo ví dụ 6, ta có sup(F) = sup(FA) = sup(FC) = sup(FAC) = 3 < minsup. Khi đó, các itemset {F, FA, FC, FAC} RI. Bổ đề 3: nếu lexcooc(ik) = Xlexcooc và sup(ik) < minsup thì {ik xsub} mRI, xsub Ƥ 1(Xlexcooc). Chứng minh: theo mệnh đề 1, ta có {ik xsub} RI, xsub Ƥ 1(Xlexcooc). Khi đó, ik { ik xsub} RI, mà sup(ik) < minsup (định nghĩa 4), nên {ik xsub} mRI, xsub Ƥ 1(Xlexcooc) ■. Ví dụ 8: Cho minsup = 5, xét item F, có sup(F)= 3< minsup. Theo ví dụ 6, ta có sup(F) = sup(FA) = sup(FC) = sup(FAC) = 3 < minsup. Khi đó, các itemset {F, FA, FC, FAC} RI, nhưng các itemset {F, FA, FC, FAC} không là các itemset hiếm tối thiểu - {FAC} RI, item F {FAC} và sup(F) = 3 < minsup (item F không phổ biến). Bổ đề 4: ik  ij, nếu ij lexlooc(ik) thì sup(ik ij) < sup(ik). Chứng minh: sup(ik ij) < sup(ik), hiển nhiên (ik ij) = (ik) (ij) (ik) ■. Ví dụ 9: Xét item F, với sup(F) = 3. Ta có, lexlooc(F) = {G, E} thì 3 itemset kết hợp {G, E, GE} và sup(F) = sup(FG) = sup(FE) = 2 < sup(F) và sup(FGE) = 1 < sup(F).
502 THUẬT TOÁN HIỆU QUẢ KHAI THÁC TẬP HIẾM TỐI THIỂU Bổ đề 5: ik I, sup(ik) minsup, nếu lexlooc(ik) = Ylexlooc và sup(ik ysub) < minsup thì {ik ysub}, {ik xsub ysub } RI, xsub Ƥ 1(Xlexcooc), ysub Ƥ 1(Ylexlooc). Chứng minh: theo bổ đề 1, 4, ta có sup(ik xsub) = sup(ik) và sup(ik ysub) = sup(ik xsub ysub) < minsup, nên {ik xsub}, {ik xsub ysub } RI, xsub Ƥ 1(Xlexcooc), ysub Ƥ 1(Ylexlooc) ■. Ví dụ 10: Cho minsup = 5, xét item G, có sup(G)= 5 minsup. Ta có lexcooc(G) = {A, C}, lexlooc(G) = {E}, sup(GE) = sup(GAE) = sup(GCE) = sup(GACE) = 3 < minsup. Khi đó, các itemset {GE, GAE, GCE, GACE} RI. Bổ đề 6: ik I, sup(ik) minsup, nếu lexlooc(ik) = Ylexlooc và sup(ik ysub) < minsup thì {ik xsub ysub } mRI, xsub Ƥ 1(Xlexcooc), ysub Ƥ 1(Ylexlooc). Chứng minh: theo bổ đề 5, ta có {ik xsub}, {ik xsub ysub } RI, mà {ik xsub} {ik xsub ysub } nên {ik xsub ysub } mRI, xsub Ƥ 1(Xlexcooc), ysub Ƥ 1(Ylexlooc) ■. Ví dụ 11: Cho minsup = 5, xét item G, có sup(G)= 5 minsup. Ta có lexcooc(G) = {A, C}, lexlooc(G) = {E}, sup(GE) = sup(GAE) = sup(GCE) = sup(GACE) = 3 < minsup. Theo định nghĩa thì các itemset {GAE, GCE, GACE} mRI, do {G, E} là tập con thực sự của lần lượt {G, A, E}, {G, C, E}, {G, A, C, E} mà sup(GE) < minsup. Theo các bổ đề trên, cần thiết phải rút gọn trường cooc trên mỗi phần tử của mảng INDEX_COOC. Chúng tôi, đặt lại tên gọi của mảng INDEX_COOC thành INDEX_LOOC, chứa các item xuất hiện ít nhất trong một giao dịch với item hạt nhân. Bỏ dòng lệnh 4 và 9, đồng thời bổ sung 2 dòng lệnh sau vào thuật toán 1: 1: Với mỗi phần tử k của mảng Index_LOOC: 2: Index_LOOC[k].looc= lexlooc(ik) Xét item G, có các item xuất hiện ít nhất trong một giao dịch với item G, ta có looc(G) = {B, D, E, F} và B, D  F  G  E, nên lexlooc(G) = {E}. Sau khi thực hiện thay đổi trên, ta có kết quả trong bảng 4. Bảng 4. Trả về mảng Index_LOOC sắp tăng theo độ phổ biến của item, thành phần looc có thứ tự Item H B D F G E A C Sup 1 2 2 3 5 7 8 8 Looc Ø G F, G G, E E A, C Ø Ø 3.3. Thuật toán khai thác tập hiếm tối thiểu NOV-mRI 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ự theo độ phổ biến). 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_LOOC Đầu ra: Danh sách cây nLOOC-Tree 1: Với mỗi phần tử k của mảng Index_LOOC: 2: nLOOC_Tree[k].item = Index_LOOC[k].item 3: nLOOC_Tree[k].sup = Index_LOOC[k].sup 4: Với mỗi item ik giao dịch tℓ : 5: Với mỗi item ij Index_LOOC[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
Phan Thành Huấn, Lê Hoài Bắc 503 Thuật toán 2 sinh cây nLOOC-Tree có các đặc trưng như sau: - 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 2. Thuật toán 2 - sinh danh sách cây nLOOC-Tree theo mảng Index_LOOC ở bảng 4 Ví dụ 12: Xét item hạt nhân F, có đường đi đơn {F G E} và sup(FGE) = 1; phân đoạn đường đi đơn {F G} và sup(FG) = 2 là độ phổ biến của nút con G. Mã giả thuật toán 3. Khai thác tập hiếm tối thiểu NOV-mRI Đầu vào: Mảng Dataset, Index_LOOC và minsup Đầu ra: Tập hiếm tối thiểu mRI 1: Với mỗi Index_LOOC[k].sup < minsup 2: mRI[k] = mRI[k] Index_LOOC[k].item//theo tính chất 3 3: Với mỗi (Index_LOOC[k].sup minsup) và (Index_LOOC[k].looc { }) // Bổ đề 6 4: nLOOC_Tree(Index_LOOC[k].item) 5: SSP GenPath(Index_LOOC[k].item)//sinh sub-single-path 6: Với mỗi sspj SSP 7: Nếu (sup(sspj) < minsup) và (sup(sspj \{iℓ}) minsup) thì 8: mRI[k] = mRI[k] {(sspj \{iℓ})} 9: Trả về tập hiếm tối thiểu mRI Ví dụ 13: Cho dữ liệu giao dịch Ɗ trong bảng 1 và minsup = 2. Sau khi thực hiện thuật toán 1, ta có mảng INDEX_LOOC chứa các item xuất hiện ít nhất trong một giao dịch với item hạt nhân, như trong bảng 4. Dòng 1 và 2: các item hiếm tối thiểu theo tính chất 3 - có item H (sup(H) = 1 < minsup); Dòng 3: loại bỏ item A và C khỏi danh sách các item khai phá; (Bổ đề 6) Xây dựng các cây nLOOC-Tree cho các item cần khai phá: B, D, F và G ; Xét item B, xem cây nLOOC-Tree(B): có một đường đi đơn {B G} và sup(BG) = 1 < minsup. Ta có, mRI[B] = {(BG, 1)}. Xét item D, xem cây nLOOC-Tree(D): có một đường đi đơn {D F G} và sup(DFG) = 1 < minsup. Ta có, mRI[D] = {(DF, 1), (DG, 1)}. Xét item F, xem cây nLOOC-Tree(F): có 2 đường đi đơn {F G E}, {F E} và 1 phân đoạn đường đi đơn {F G} lần lượt có sup(FGE) = 1 < minsup, sup(FG) = 2 minsup và sup(FE) = 2 minsup. Ta có, mRI[F] = {(FGE, 1)}. Xét item G, xem cây nLOOC-Tree(G): có một đường đi đơn {G E} và sup(GE) = 3 minsup. Ta có, mRI[G] = { }. Xét item E, có đường đi đơn {E A C} và sup(EAC) = 5 minsup. Ta có, mRI[E] = { }.
504 THUẬT TOÁN HIỆU QUẢ KHAI THÁC TẬP HIẾM TỐI THIỂU Tập hiếm tối thiểu mRI trên dữ liệu giao dịch Ɗ ở bảng 1 với minsup = 2: Item hạt nhân Tập hiếm tối thiểu mRI H (H, 1) B (BG, 1) D (DF, 1) (DG, 1) F (FGE, 1) IV. KẾT QUẢ THỰC NGHIỆM Thực nghiệm trên máy tính CF-74, Core Duo 2.0 GHz, 4GB RAM, thuật toán cài đặt trên C#, Microsoft Visual Studio 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 5. 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 phần thực nghiệm, chúng tôi sử dụng 4 tập dữ liệu được mô tả ở bảng 5 và so sánh thuật toán đề xuất NOV-mRI với thuật toán AprioriRare [8] (loại bỏ các itemset có độ phổ biến bằng 0) và thuật toán Walky-G [10]. Để so sánh thời gian thực hiện giữa thuật toán đề xuất với thuật toán AprioriRare và Walky-G, chúng tôi chỉ tiến hành so sánh theo từng ngưỡng minsup và cả 3 thuật toán đều cho cùng kết quả số lượng itemsets hiếm. (a) Chess (b) Mushroom 250000 500 Thời gian (mili giây) Thời gian (mili giây) 200000 400 150000 300 AprioriRare AprioriRare 100000 200 Walky-G Walky-G 50000 NOV-mRI 100 NOV-mRI 0 0 11 12 13 14 15 0,1 0,2 0,3 0,4 0,5 Minsup (% ) Minsup (% ) Hình 3. Thời gian thực hiện NOV-mRI, Walky-G và AprioriRare trên dữ liệu Chess, Mushroom Hình 3a và 3b 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 NOV-mRI nhanh hơn thuật toán Walky-G và AprioriRare. (a) T10I4D100K (b) T40I10D100K 1000000 1000000 Thời gian (mili giây) Thời gian (mili giây) 100000 100000 10000 10000 1000 AprioriRare 1000 AprioriRare 100 Walky-G 100 Walky-G 10 NOV-mRI 10 NOV-mRI 1 1 0,010 0,015 0,020 0,025 0,030 0,075 0,080 0,085 0,090 0,095 Minsup (% ) Minsup (% ) Hình 4. Thời gian thực hiện NOV-mRI, Walky-G và AprioriRare trên dữ liệu T10I4D100K, T40I10D100K
Phan Thành Huấn, Lê Hoài Bắc 505 Hình 4a và 4b 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 NOV-mRI nhanh hơn thuật toán Walky-G và AprioriRare. Hiệu suất của thuật toán NOV-mRI rất cao so với Walky-G và AprioriRare trên dữ liệu thưa. Kết quả trên cho thấy thuật toán khai thác tập hiếm tối thiểu NOV-mRI tốt hơn thuật toán Walky-G và AprioriRare. 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. V. KẾT LUẬN Nhóm tác giả đã đề xuất kiến trúc khai thác tập hiếm tối thiểu với một ngưỡng phổ biến tối thiểu gồm hai giai đoạn: giai đoạn thứ nhất là tính nhanh mảng Index_LOOC chứa các 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: đề xuất thuật toán NOV-mRI khai thác hiệu quả tập hiếm tối thiểu dựa trên mảng Index_LOOC. Với kiến trúc như trên, khi người dùng khai thác tập hiếm tối thiểu với ngưỡng khác thì thuật toán đề xuất chỉ thực hiện khai thác tập hiếm tối thiều trên mảng Index_LOOC đã 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 hiếm tối thiểu 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. VII. 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] J. Dong, M. Han. “BitTableFI: An efficient mining frequent itemsets algorithm”. Knowledge-Based Systems 20(4), pp.329-335, 2007. [5] W. Song, B. Yang. “Index-BitTableFI: An improved algorithm for mining frequent itemsets”. Knowledge-Based Systems 21, pp.507-513, 2008. [6] B. Liu, W. Hsu, Y. Ma. “Mining association rules with multiple minimum supports”. Proc. of the 15th ACM SIGKDD International Conference on Knowledge discovery and Data mining, pp.337-341, 1999. [7] Y. S. Koh, N. Rountree. “Finding sporadic rules using apriori-inverse”. In PAKDD’05, 3518, Springer, pp.97-106, 2005. [8] L. Szathmary, A. Napoli, P. Valtchev. “Towards rare itemset mining”. Proc. of the 19th IEEE Int. Conf. on Tools with Artiﬁcial Intelligence. Washington, DC, USA: IEEE Computer Society, pp.305-312, 2007. [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. AN EFFICIENT MINING ALGORITHM FOR MINIMAL RARE ITEMSETS IN TRANSACTINAL DATABASES Phan Thanh Huan, Le Hoai Bac ABSTRACT: In the field of data mining, 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 this paper, we propose an efficient mining algorithm for minimal rare itemsets. Finally, we present result experiments on both synthetic and real-life datasets, which shows the proposed algorithm has better than the existing algorithms. Keywords: Data mining, rare itemsets, minimal rare itemsets.