Khai thác nhanh mẫu phổ biến trên cơ sở dữ liệu trọng số

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

Thêm vào BST

Báo xấu

23
lượt xem 4
download

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

Trong bài viết này tác giả đề xuất một định lý để tính nhanh độ hỗ trợ trọng số trên cấu trúc MBiS giúp giảm thời gian tính toán trong quá trình khai thác mẫu phổ biến trên cơ sở dữ liệu trọng số. Các kết quả thực nghiệm đã cho thấy phương pháp đề xuất hiệu quả hơn các phương pháp dựa trên MBiS, IWS, NFWI về thời gian thực thi.

Chủ đề:

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

Lưu

Nội dung Text: Khai thác nhanh mẫu phổ biến trên cơ sở dữ liệu trọng số

Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XIV về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR), TP. HCM, ngày 23-24/12/2021 DOI: 10.15625/vap.2021.0068 KHAI THÁC NHANH MẪU PHỔ BIẾN TRÊN CƠ SỞ DỮ LIỆU TRỌNG SỐ Nguyễn Duy Hàm Khoa Công nghệ thông tin - Trường Đại học Công nghệ TP. Hồ Chí Minh Trường Cao đẳng An ninh mạng iSPACE nd.ham@hutech.edu.vn, ham.nguyen@ispace.edu.vn TÓM TẮT: Khai thác mẫu là bài toán quan trọng, tiền đề cho khai thác luật kết hợp, nhằm tìm mối quan hệ hữu ích của các mục trong dữ liệu. Khai thác mẫu cũng là bài toán quan trọng có nhiều ứng dụng trong các hệ thống thông minh. Do đó, khai thác mẫu là bài toán được quan tâm nghiên cứu từ rất sớm, nhiều nghiên cứu đề xuất các thuật toán, phương pháp khai thác khá hiệu quả, như đề xuất các cấu trúc Nlist, cấu trúc bit véctơ DBV, MBiS, IWS,… sử dụng để tăng tốc độ tính toán trên các cơ sở dữ liệu dày. So với các tiếp cận khác thì Bit véctơ khá hiệu quả, giảm bộ nhớ lưu trữ và tăng tốc độ tính toán do sử dụng các phép toán bitwise. Trong bài báo này tác giả đề xuất một định lý để tính nhanh độ hỗ trợ trọng số trên cấu trúc MBiS giúp giảm thời gian tính toán trong quá trình khai thác mẫu phổ biến trên cơ sở dữ liệu trọng số. Các kết qủa thực nghiệm đã cho thấy phương pháp đề xuất hiệu quả hơn các phương pháp dựa trên MBiS, IWS, NFWI về thời gian thực thi. Từ khoá: Mẫu phổ biến, cơ sở dữ liệu trọng số, bit véctơ, MBiS. I. GIỚI THIỆU Khai thác mẫu phổ biến là bài toán quan trọng có nhiều ứng dụng trong thực tế. Nhu cầu về tìm mối liên hệ giữa các dữ liệu trong cơ sở dữ liệu (CSDL) là rất lớn và thực tế nên các nghiên cứu về mẫu phổ biến, luật kết hợp đã được quan tâm từ rất sớm [1-2]. Trong khai thác mẫu phổ biến có ba hướng tiếp cận chính, đó là: Thuật toán Apriori [1], thuật toán này theo tư tưởng vét cạn các khả năng sinh ra tập phổ biến bằng cách sinh tập phổ biến nhiều phần tử hơn từ tập phổ biến ít phần tử đã tìm thấy trước đó. Do việc quét CSDL nhiều lần nên cách tiếp cận này rất tốn thời gian, sau đó giải pháp sử dụng thuật toán FP-Growth dựa trên cây FP-Tree với hai lần quét CSDL, đây cũng là một giải pháp hiệu quả, theo hướng nghiên cứu này các tác giả đã đề xuất các cải tiến khá hiệu quả cho bài toán khai thác mẫu như NodeList, Nlist [10- 12]… tuy nhiên cách tiếp cận này không hiệu quả khi xét trên các ngưỡng lớn để tìm một tập nhỏ các mẫu phổ biến phục vụ cho một nhiệm vụ cụ thể nào đó; Tiếp theo là tiếp cận theo thuật toán Eclat dựa trên cây IT-tree với chỉ một lần đọc dữ liệu [6-9][13]. Cách tiếp cận này khá hiệu quả do quá trình cắt tỉa nhanh các nhánh chắc chắn không sinh ra mẫu phổ biến dựa trên ngưỡng đưa vào, song việc lưu trữ các tidset của tập mục lại tốn khá nhiều bộ nhớ. Theo hướng tiếp cận này cũng đã có nhiều cải tiến như sử dụng diffset thay cho tidset, sử dụng bit véctơ để lưu trữ tidset/diffset của các tập mục như DBV [6], MBiS [7], IWS [8], các cải tiến này đã cho thấy hiệu quả rõ rệt trong lưu trữ và tăng tốc độ tính toán. Tiếp cận bit véctơ là một tiếp cận hiệu quả với phương pháp Eclat, do thao tác tính giao các tidset của các tập mục chiếm phần lớn thời gian khai thác, mà tiếp cận này giúp cho việc tính nhanh do sử dụng các phép toán bitwise, đồng thời tiếp cận này cũng làm giảm bộ nhớ lưu trữ tidset của các tập mục. Trong bài báo này tác giả áp dụng phương pháp lưu tidset của các tập mục bằng cách lưu thành các đoạn giao dịch liên tiếp để giảm không gian lưu trữ tidset, đồng thời đề xuất một định lý trọng số về việc tính gộp tổng các trọng số các đoạn giao dịch liên tiếp giúp tính nhanh độ hộ trợ của các tập mục trong quá trình khai thác. Phương pháp này cải thiện đáng kể thời gian tính toán trong quá trình khai thác mẫu phổ biến trên cơ sở dữ liệu có trọng số. Ngoài phần mở đầu, bài báo được cấu trúc như sau: Phần II trình bày về các nghiên cứu liên quan của bài toán; phương pháp đề xuất được trình bày trong Phần III; Phần IV là kết quả thực nghiệm; kết luận và hướng nghiên cứu tiếp theo được trình bày trong Phần V. II. CÁC NGHIÊN CỨU LIÊN QUAN A. Bài toán khai thác mẫu phổ biến trên CSDL trọng số Bài toán khai thác mẫu phổ biến được phát biểu như sau: là một bộ gồm ba thành phần: , trong đó: T = {t1, t2, ..., tm} là tập gồm m giao dịch của CSDL. I = {i1, i2,.., in} là tập gồm n mục trong CSDL W = {w1, w2, …, wn} là tập gồm n trọng số của n mục tương ứng trong tập I Ví dụ 1: Cho CSDL DB gồm 6 giao dịch như Bảng 1, có 5 mục {A, B, C, D, E} và trọng số tương ứng của các mục như trong Bảng 2.
268 KHAI THÁC NHANH MẪU PHỔ BIẾN TRÊN CƠ SỞ DỮ LIỆU TRỌNG SỐ Bảng 1. CSDL DB Bảng 2. Trọng số các mục trong DB Giao dịch Các mục trong giao dịch Mục Trọng số t1 A, B, D, E A 0,6 t2 B, C, E B 0,1 t3 A, B, D, E C 0,3 t4 A, B, C, E D 0,9 t5 A, B, C, D, E E 0,2 t6 B, C, D Tidset của tập mục X là tập hợp các giao dịch chứa X. Như vậy: tidset(X) ={t|t ∈ T} Tao và các cộng sự [5] đã đề xuất công thức tính trọng số giao dịch tw và độ hỗ trợ trọng số ws của tập mục X dùng trong khai thác mẫu phổ biến trên CSDL trọng số. Công thức xác định trọng số của mỗi giao dịch tk: ∑𝑖 𝑤𝑖𝑗 𝑗∈(𝑡𝑘) tw(tk) = (1) 𝑠(𝑡𝑘 ) tw(𝑡𝑘 ) là trọng số của giao dịch 𝑡𝑘 𝑤𝑖𝑗 là trọng số của mục 𝑖𝑗 trong 𝑡𝑘 𝑠𝑠(𝑡𝑘 ) là số các mục có mặt trong giao dịch 𝑡𝑘 Bảng 3. Giá trị tw của CSDL DB Giao dịch tw Giá trị 0,6+0,1+0,9+0,2 t1 𝑡𝑤(𝑡1 ) = = 0,45 4 0,1+0,3+0,2 t2 𝑡𝑤(𝑡2 ) = = 0,20 3 0,6+0,1+0,9+0,2 t3 𝑡𝑤(𝑡3 ) = = 0,45 4 0,6+0,1+0,3+0,2 t4 𝑡𝑤(𝑡4 ) = = 0,3 4 0,6 + 0,1 + 0,3 + 0,9 +0 ,2 t5 𝑡𝑤(𝑡5 ) = = 0,42 5 0,1 + 0,3 + 0,9 t6 𝑡𝑤(𝑡1 ) = = 0,43 4 Sum tw 0,45 + 0,20 + 0,45 + 0,3 + 0,42 + 0,43 2,25 Công thức xác định độ hỗ trợ trọng số của mỗi tập mục X: ∑𝑡 𝑡𝑤(𝑡𝑘 ) 𝑘∈𝑡(𝑋) (2) ws(X) = 𝑆𝑢𝑚(𝑡𝑤) Với, t(X) là tập các giao dịch chứa tập mục X và sum(tw)= ∑𝑚 𝑘=1 𝑡𝑤 (𝑡𝑘 ) Ví dụ, với tập mục BD ở ví dụ 1.4 được xác định như sau: 𝑡𝑤(𝑡1 )+𝑡𝑤(3)+𝑡𝑤(𝑡5 )+𝑡𝑤(𝑡6 ) 0,45+0,45+0,42+0,43 ws(BD) = = ≈ 0,78 𝑤(𝑡1 )+𝑡𝑤(2)+𝑡𝑤(3)+𝑡𝑤(4)+𝑡𝑤(𝑡5 )+𝑡𝑤(𝑡6 ) 2,25 Tập mục X được gọi là phổ biến nếu và chỉ nếu ws(X) ≥ minws, với minws được xác định bởi người sử dụng. Bài toán khai thác mẫu phổ biến trọng số - frequent weighted (FWI) là bài toán tìm tất cả các tập mục X (X ⊆ I) thỏa mãn ws(X) ≥ minws, với minws là đại lượng được cho trước. B. Một số tiếp cận khai thác mẫu phổ biến Bài toán khai thác FWI trên CSDL trọng số được đề xuất lần đầu tiên bởi Ramkumar và đồng sự [4], trong nghiên cứu này, các tác giả đã đưa ra mô hình mô tả khái niệm về luật kết hợp có trọng số, trong đó đề xuất thuật toán WIS để khai thác FWI. Sau đó Tao và đồng sự [5] đề xuất độ đo trọng số giao dịch tw (transaction weight) theo công thức 1 và giá trị ws (weighted support) theo công thức 2 để khai thác mẫu phổ biến trọng số. Theo cách tiếp cận này thì giá trị ws của tập mục vừa phản ánh được mức độ xuất hiện của tập mục trong các giao dịch, vừa thể hiện được mức độ quan trọng khác nhau của các giao dịch. Một ưu điểm nữa của cách tiếp cận này là thỏa mãn tính chất bao đóng giảm một cách tự nhiên. Tuy nhiên, thuật toán do Tao và đồng sự đề xuất dựa vào việc sinh ứng viên theo phương pháp Apriori nên cần đọc CSDL nhiều lần, dẫn đến tốn thời gian xử lý và cả bộ nhớ lưu trữ và hiện nay hướng tiếp cận này không được tiếp tục phát triển. Tiếp theo, Han và các công sự đã đề xuất hướng tiếp cận mới dựa trên cây FP-tree với thuật toán FP-Growth [2]. FP-Growth đọc CSDL lần thứ nhất để tạo cây FP-tree, lần thứ 2 để chiếu lên cây và duyệt cây xác định các tập phổ biến. Sau đó Deng và các cộng sự [12] đề xuất cấu trúc N-list giúp khai thác nhanh trong quá trình duyệt cây FP-tree cùng một số kĩ thuật cắt nhánh trong tạo cây FP-tree làm giảm thời gian khai thác. Dựa trên cấu
Nguyễn Duy Hàm 269 trúc N-list, sau đó Bui và các công sự [11] đề xuất cấu trúc WN-List hiệu quả hơn với việc sử dụng khái niệm subsume để cắt nhánh nhanh và tăng tốc tính toán trên cây WN-tree. Tuy nhiên, các tiếp cận theo hướng này tốn thời gian trong xây dựng cây ban đầu, do đó với các trường hợp ngưỡng đủ lớn thì cách tiếp cận này chưa thật sự hiệu quả. Một tiếp cận khác là theo phương pháp Eclat [3]. Dựa trên tiếp cận này Vo và các đồng sự [13] đề xuất cách thức lưu trữ trọng số trên cây WIT-tree là một mở rộng của cây IT-tree. Do chỉ cần quét CSDL một lần, cùng với áp dụng chiến lược diffset thay cho tidset nên đã giảm được không gian lưu trữ tập giao dịch của các tập mục, đồng thời giúp giảm thời gian trong khai thác FWI trên cây WIT-tree, nên phương pháp này tỏ ra hiệu quả hơn phương pháp theo hướng tiếp cận Apriori trước đó, tuy nhiên diffset chỉ có hiệu quả trên các CSDL dày và kém hiệu quả trên CSDL thưa. Sau đó Nguyen và các cộng sự [8] đề xuất thuật toán hiệu quả hơn bằng việc cải tiến bit véctơ - cắt bỏ các đoạn bit 0 liên tiếp trong biểu diễn tidset của các tập mục để tối ưu tính toán và bộ nhớ rút ngắn thời gian khai thác. Các cải tiến sử dụng Bit Véctơ trong biểu diễn tidset chưa thật sự có hiệu quả trên CSDL dày do mật độ các mục xuất hiện trong các giao dịch là lớn nên việc cắt bỏ các bit 0 trong biểu diễn tidset không có nhiều ý nghĩa, mặt khác trong các tính toán độ hỗ trợ định lượng (trọng số và số lượng) của các tập mục còn mất nhiều thời gian do phải duyệt tất cả các bit 1 trong bit véctơ. III. THUẬT TOÁN ĐỀ XUẤT A. Biểu diễn tidset của tập mục Nguyen và các cộng sự [7] đã đề xuất cấu trúc MBiS để giảm không gian lưu trữ tidset trong khai thác mẫu phổ biến trên CSDL số lượng. Thay vì lưu toàn bộ các ID giao dịch của tập mục, MBiS chỉ cần lưu đầu mút của các đoạn liên tiếp. Ví dụ item A xuất hiện trọng các giao dịch 1, 3, 4, 5 thì MBiS(A)= {[1][3,5]} nghĩa là tidset(A) chỉ có 2 đoạn, đoạn 1 là giao dịch 1, đoạn 2 là từ giao dịch 3 đến giao dịch 5. Cách biểu diễn này cũng làm cho việc tính giao các MBiS của tập mục nhanh hơn do chỉ cần cập nhật lại đoạn đầu và cuối của các đoạn giao. Trong bài báo này tác giả sử dụng cấu trúc MBiS để lưu tidset của các tập mục. B. MBiS-Tree MBiS - Tree của CSDL DB là cây có 1 nút cha, mỗi nút con gồm ba thành phần: - X: là tập mục của; - ws: là độ hộ trợ trọng số của X; - MBiS(X). Lớp node thứ nhất của MBiS-tree là các tập mục 1 phần tử có ws thoả minws. Các nút trên cùng một mức của MBiS-tree được kết hợp với nhau để tạo ra nút ở mức kế tiếp nếu ws của tập mục nút tạo thành thoả minws. Khi nút X kết hợp với nút Y trên cùng một mức của cây để tạo ra nút Z = X ∪ Y và nút Z chỉ được thêm vào cây nếu ws(Z) > minws MBiS(Z) = MBiS(X) ∩ MBiS(Y) Các nút của MBiS-tree sau khi xây dựng xong chính là các mẫu phổ biến thoả mãn minws. C. Thuật toán xác định giao của hai MBiS Thuật toán 1 duyệt theo chiều dài của hai MBiS và tính các đoạn giao của hai MBiS này để tạo ra MBiS với tập mục mới kết hợp tạo thành Hình 1. Thuật toán xác định giao hai MBiS Độ phức tạp thuật toán INTERSECTION_WS là O(n1+m1) với n1 và m1 là số đoạn của MBiS(X) và MBiS(Y).
270 KHAI THÁC NHANH MẪU PHỔ BIẾN TRÊN CƠ SỞ DỮ LIỆU TRỌNG SỐ D. Thuật toán tính nhanh ws của tập mục Việc tính ws của các tập mục dựa trên MBiS khá đơn giản là duyệt hết các đoạn trong MBiS sau đó tính tổng tw của các giao dịch theo thuật toán như trong Hình 2. Hình 2. Thuật toán tính ws dựa trên MBiS Trong quá trình xây dựng cây MBiS để khai thác mẫu phổ biến thao tác tính ws của các tập mục tạo thành được thực hiện rất nhiều lần, tập mục nào có ws > minws mới được thêm vào cây MBiS. Để tính ws theo thuật toán 2, với mỗi tập mục, ta phải xét hết tất cả các đoạn bit trong MBiS của tập mục đó (dòng 1 và 2). Do cấu trúc của MBis là lưu hai đầu mút các đoạn bit 1 liên tiếp nhau, biễn diễn cho tập mục xuất hiện trong các giao dịch liền nhau, ví dụ MBiS(A) ={[1, 1],[3, 5]}nghĩa là A xuất hiện trong giao dịch 1 và trong các giao dịch từ 3 đến giao dịch 5, do đó ws(A) = tw1+ tw3+ tw4+ tw5. Định lý 1: Gọi PAi là tổng tw của các giao dịch từ giao dịch 1 đến giao dịch i ( ∀ i ∈ [1..m] với m là số lượng giao dịch của CSDL) thì tổng tw từ giao dịch l đến giao dịch k (l ≤ k ≤ m) được xác định theo công thức sau: ws(tl) + ws(tl+1) +..+ ws(tk-1) + ws(tk) = PAk -PAl-1. (3) Chứng minh: Theo định lý ta có PAk = tw1 + tw2 +…+ twk, tương tự PAl-1 = tw1 + tw2 +…+twl-1 Do đó, với k ≥ l ta có: PAk -PAl-1 = (tw1 + tw2 +…+twk) - ( tw1 + tw2 +…+twl-1) ⟹ PAj -PAi-1 = ws(tl) + ws(tl+1) +..+ ws(tk-1) + ws(tk) Định lý đã được chứng minh. Ngoài ra, theo định nghĩa của PA trong Định lý 1 ta có thể xác định các PAi rất đơn giản theo công thức sau: PAi = [ws(t1) + ws(t2) +..+ ws(ti-1) ]+ ws(ti) = PAi-1 + ws(ti) (4) Ví dụ, với CSDL DB ta tạo bảng PA của ws các giao dịch theo công thức 4 như sau: Index 0 1 2 3 4 5 6 tw 0 0,45 0,20 0,45 0,30 0,42 0,45 PA 0 0,45 0,65 1,1 1,4 1,82 2,25 Vậy, theo công thức 3 của Định lý 1 ta có: ws(A) = (PA1 - PA0) + (PA5 - PA2) = (0,45 - 0) + (1,82 - 0,65) =1,62 Tương tự ta có: ws(B) = PA6 - PA0 = 2,25 - 0 = 2,25. Tính ws của các tập mục dựa trên Định lý 1 được thực hiện theo thuật toán trong Hình 3. Hình 3. Thuật toán tính nhanh ws dựa trên MBiS Độ phức tạp thuật toán = O(k) với k là số đoạn của MBiS(X). E. Thuật toán khai thác nhanh FWI MBiS - Tree được tạo ra với thuật toán FAST_MBiS-tree được trình bày trong Hình 4 với đầu vào là tập P chứa các mục thoả mãn minws và minws
Nguyễn Duy Hàm 271 Hình 4. Thuật toán xây dựng MBiS-tree khai thác nhanh FWI Ví dụ minh hoạ với CSDL DB trong ví dụ 1 và minws = 0,5: Bước 1: Tính MBiS ws của các tập mục một phần tử như Bảng 5 và mảng PA như Bảng 4. Bảng 5. MBiS của các mục Mục Tidset MBiS ws A 1, 3, 4, 5 [1][3,5] 0,72 B 1, 2, 3, 4, 5, 6 [1,6] 1,00 C 2, 4, 5, 6 [2][4,6] 0,60 D 1, 3, 5, 6 [1][3][5][6] 0,78 E 1, 2, 3, 4, 5 [1,5] 0,81 Bước 2: Xây dựng MBiS-tree theo thuật toán 4. Tất cả các tập mục 1 phần tử {A, B, C, D, E} (tập P ban đầu ) đều thoả minws. Hình 5. Cây MBiS-tree với CSDL DB và minws = 0,5 Với mục A ta có wsA = 0,72, MBiS(A) ={[1][3,5]} kết nối với B có wsB = 1,0, MBiS(B) = {[1,6]} tạo ra tập mục AB có wsAB = 0,72 > minws và MBiS(AB) = MBiS(A) ∩ MBiS(B) ={[1][3,5]} ∪ {[1,6]} ={[1][3,5]} thêm node AB vào MBiS-tree. Tương tự ta có các node AD, AE, … cuối cùng ta có MBiS-tree như Hình 5. Bước 3: Xuất ra cây MBiS gồm các node là mẫu phổ biến khai thác được bao gồm: {A, B, C, D, E, AB, AD, AE, BC, BD, BE, DE, ABD, ABE, ADE, BDE, ABDE}. IV. KẾT QUẢ THỰC NGHIỆM A. Môi trường thực nghiệm Các thuật toán được cài đặt trên máy tính với cấu hình Intel i7-3632QM, CPU 2.2-GHz và RAM 8 GB, hệ điều hành Windows 10, sử dụng C# (phiên bản 2016).
272 KHAI THÁC NHANH MẪU PHỔ BIẾN TRÊN CƠ SỞ DỮ LIỆU TRỌNG SỐ Bốn CSDL thực nghiệm được lấy từ website http://fimi.ua.ac.be/data/ với đặc điểm được mô tả ở Bảng 6. Để đảm bảo tính khách quan của phương pháp đề xuất, tác giả chọn CSDL RETAIL và BMS-POS là các dữ liệu thưa, hai CSDL còn lại CONNECT và ACCIDENTS là các CSDL dày. Các CSDL này đều được thêm bảng trọng số bằng cách sinh ngẫu nhiên trong khoảng [0,1]. Bảng 6. Mô tả CSDL thực nghiệm Stt CSDL Số lượng mục Số lượng giao dịch Ghi chú 1 RETAIL 16.470 88.162 Thêm trọng số 2 BMS-POS 1.657 515.597 Thêm trọng số 3 CONNECT 468 340.183 Thêm trọng số 4 ACCIDENTS 130 67.557 Thêm trọng số Tác giả tiến hành so sánh thời gian chạy với các phương pháp DBV[6], IWS[8], MBiS (Chỉnh sửa từ MBiS_FWUI) [7] và NFWI[12]. Với mỗi ngưỡng thực nghiệm tác giả chạy 10 lần sau đó lấy kết quả trung bình của 10 lần chạy. Tất cả các phương pháp đều chạy trên cùng một nền tảng để đảm bảo kết quả khách quan nhất có thể. Về bộ nhớ FAST_MBiS không có thay đổi nào với phương pháp MBiS thông thường, trong quá trình so sánh tác giả không nhận thấy khác biệt nhiều về bộ nhớ giữa các phương pháp. Do đó trong bài báo này tác giả chỉ trình bày phần thực nghiệm với thời gian thực thi. B. So sánh thời gian thực thi 120 DBV FAST_MBiS MBiS NFWI 100 80 60 40 20 0 6 4 2 1 0,2 0,1 MINWS (%) Hình 6. So sánh thời gian chạy trên CSDL retail 250 DBV FAST_MBiS NFWI MBiS 200 150 100 50 0 6 4 2 1 0,2 0,1 MINWS (%) Hình 7. So sánh thời gian chạy và trên CSDL BMS-POS 250 DBV FAST_MBiS NFWI MBiS 200 150 100 50 0 6 4 2 1 0,2 0,1 MINWS (%) Hình 8. So sánh thời gian chạy trên CSDL connect
Nguyễn Duy Hàm 273 200 DBV FAST_MBiS NFWI MBiS 150 100 50 0 6 4 2 1 0,2 0,1 MINWS (%) Hình 9. So sánh thời gian chạy trên CSDL accidents Từ kết quả thực nghiệm từ Hình 6 đến Hình 9 trên chúng ta có thể thấy, FAST_MBiS hiệu quả hơn các phương pháp MBiS, và DBV trong toàn bộ ngưỡng minws. Tuy nhiên, đối với phương pháp NFWI - là phương pháp sử dụng cấu trúc NLIST với tiếp cận FP-Growth nên đọc CSDL hai lần do đó tốn thời gian đọc CSDL, nên với các ngưỡng minws lớn NFWI chạy chậm hơn các phương pháp còn lại do cây được tạo thành của DBV, MBiS, FAST_MBiS rất nhỏ khi ngưỡng lớn nên cắt nhánh rất nhanh, và với các ngưỡng minws lớn thì FAST_MBiS có hiệu quả hơn hẳn các phương pháp còn lại. V. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN Bài báo đề một phương pháp khai thác mẫu phổ biến trọng số hiệu quả bằng cách áp dụng cấu trúc cây MBiS trong khai thác mẫu phổ biến trên CSDL số lượng (định lượng) [7], đồng thời cải tiến thuật toán tính độ hỗ trợ trọng số ws dựa trên cấu trúc MBiS bằng cách áp dụng kĩ thuật prefix sum arrary. Các kết quả thực nghiệm cho thấy thuật toán hiệu quả hơn các phương pháp tiếp cận theo hướng bit véctơ như DBV, IWS, và hiệu quả hơn NFWI với cấu trúc NLIST theo tiếp cận FP-Growth ở các ngưỡng minws lớn. Trong thời gian tới tác giả tiếp tục nghiên cứu áp dụng phương pháp này cho các bài toán khai thác mẫu trên cơ sở dữ liệu phân cấp và các bài toán khai thác mẫu top rank k, top k. TÀI LIỆU THAM KHẢO [1] Agrawal, R., Srikant, R. Fast algorithms for mining association rules. VLDB’94, pp. 487-499, 1994. [2] Han, J., Pei, J., & Yin, Y. Mining frequent patterns without candidate generation. Proc. of Conf on ACM SIGMOD management of data, pp. 112, 2000. [3] Zaki, M. J. Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering, 12(3), pp. 372-390, 2000. [4] Ramkumar, G. D., Ranka, S., & Tsur, S. Weighted Association Rules: Model and Algorithm. Proc. of Conference on Knowledge Discovery and Data Mining - KDD, pp. 1-13, 1998. [5] Tao, F., Murtagh, F., & Farid, M. Weighted Association Rules mining using weighted support and signifocance framework. Proc. of Conference on ACM SIGKDD, pp. 661-666, 2003. [6] Vo, B., Hong, P. T., & Le, B. DBV-Miner: A Dynamic bit - Vectơr approach for fast mining frequent close itemsets. Expert Systems with Applications, 39(8), pp. 7196-7206, 2012. [7] Nguyen, D. H., Vo, D. B., Nguyen, T. H. M., Hong, T. P. MBiS: an efficient method for mining frequent weighted utility itemsets from QDB. Journal of Computer Science and Cybernetics, 31(1), pp.17-30, 2015. [8] Nguyen, D. H., Vo, B., Nguyen, T. H. M., Witold, P. An efficient algorithm for mining frequent weighted itemsets using interval word segments, Applied Intelligence 45(4), pp.1008 -1020, 2016. [9] Huynh M. H., Nguyen T. T. L., Vo B. Nguyen A., Tseng V. S. Efficient methods for mining weighted clickstream patterns. Expert Systems with Applications, 142, 112993, 2020. [10] Vo B., Bui H., Vo T., Le T. Mining top-rank-k frequent weighted itemsets using WN-list structures and an early pruning strategy. Knowledge Based Systems, 201-202, 106064, 2020. [11] Bui H., Vo B., Nguyen H., Nguyen Hoang T. A., Hong T. P. A weighted N-list-based method for mining frequent weighted itemsets. Expert Systems with Applications, 96, pp. 388-405, 2018. [12] Deng, Z., Wang, Z., & Jiang, J. A new algorithm for fast mining frequent item- sets using N-lists. Science China Information Sciences, 55(9), pp. 2008-2030, 2012. [13] Vo, B., Coenen, F., & Le, B. A new method for mining frequent weighted itemsets base on WIT-trees. Expert systems with applications, 40(4), pp. 1256-1264, 2013.
274 KHAI THÁC NHANH MẪU PHỔ BIẾN TRÊN CƠ SỞ DỮ LIỆU TRỌNG SỐ FAST MINING OF FREQUENT PATTERN ON THE WEIGHTED DATABASE Nguyen Duy Ham ABSTRACT: Frequent pattern mining is an important problem, the premise for association rule mining, to find useful relationships of items in the data. Frequent pattern mining is also an important problem that has many applications in intelligent systems. Therefore, pattern mining is a problem that has been studied very early, many studies have proposed quite effective mining algorithms and methods, such as the proposed Nlist structures, Bit véctơr structures DBV, MBiS, IWS,… or used to speed up computation on thick databases. Compared with other approaches, bit véctơrs are quite efficient, reducing storage memory and increasing computational speed due to the use of bitwise operations. In this paper, we propose a theorem for calculating weighted support on the segment of MBiS bit segment, used to quickly calculate the support of the generated item set to help reduce the computation time of the common pattern mining problem on the weighted database. The experimental results have shown that the proposed method is more efficient than the existing methods in terms of execution time.