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

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.
Nội dung trích xuất từ tài liệu:
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: ...