Cải tiến thuật toán khai phá dữ liệu tuần tự CMSPAM cho trường hợp dữ liệu thưa

Bài viết sẽ phân tích ưu nhược điểm của các thuật toán và đề xuất một cải tiến cho thuật toán CMSPAM. Thuật toán cải tiến được đặt tên là CMSPAME cho hiệu quả tốt hơn đối với trường hợp dữ liệu thưa và vẫn giữ nguyên được hiệu năng như thuật toán CMSPAM trong các trường hợp khác.
Nội dung trích xuất từ tài liệu:
Cải tiến thuật toán khai phá dữ liệu tuần tự CMSPAM cho trường hợp dữ liệu thưaCẢI TIẾN THUẬT TOÁN KHAI PHÁ DỮ LIỆUTUẦN TỰ CMSPAM CHO TRƯỜNG HỢP DỮ LIỆU THƯA Nguyễn Mạnh Sơn *, Đặng Ngọc Hùng+ * Khoa CNTT1 – Học Viện Công Nghệ Bưu Chính Viễn Thông Email: sonnm@ptit.edu.vn + Khoa CNTT1 – Học Viện Công Nghệ Bưu Chính Viễn Thông Email: hungdn@ptit.edu.vn Abstract — Khai phá mẫu tuần tự (SPM) nhiều lĩnh vực khác như phân tích DNA, tư được ứng dụng rộng rãi trong các bài toán vấn điều trị bệnh, dự báo thiên tai, phân tích thương mại điện tử và ra quyết định. Các mẫu truy cập website …. thuật toán SPM tiêu biểu đã được áp dụng Phần lớn các thuật toán ban đầu cho bài trong nhiều hệ thống tư vấn, dự báo … như GSP, SPAM, CMSPAM. Bài báo sẽ phân tích toán khai phá mẫu tuần tự đều dựa trên tính ưu nhược điểm của các thuật toán và đề xuất chất Apriori được sử dụng trong khai phá một cải tiến cho thuật toán CMSPAM. Thuật luật kết hợp ([1],[2],[3]). Tính chất này cho toán cải tiến được đặt tên là CMSPAME cho rằng: mọi mẫu con (sub-pattern) của một hiệu quả tốt hơn đối với trường hợp dữ liệu mẫu phổ biến (frequent pattern) cũng chính thưa và vẫn giữ nguyên được hiệu năng như là một mẫu phổ biến. Dựa trên tính chất này, thuật toán CMSPAM trong các trường hợp rất nhiều các thuật toán được đề xuất như: khác. AprioriAll, AprioriSome, DynamicSome (Agrawal và Srikan 1995), GSP (Skrikant và Keywords— Khai phá dữ liệu tuần tự, SPM, Agrawal 1996) với phương pháp định dạng cải tiến CMSPAM, thuật toán CMSPAME. bộ nhớ theo chiều ngang (horizontal database format) ([2],[3]). Tuy nhiên khi các I. GIỚI THIỆU CSDL ngày càng lớn, thì phương pháp định Bài toán khai phá mẫu tuần tự (Sequential dạng bộ nhớ theo chiều ngang tỏ ra thiếu Pattern Mining - SPM) được R. Agrawal và hiệu quả [3]. Các phương pháp định dạng bộ R. Srikant giới thiệu vào năm 1995 [1]. Cho nhớ theo chiều dọc (vertical database một tập các dãy tuần tự, trong đó mỗi dãy format) mà tiêu biểu là thuật toán SPAM bao gồm một tập các giao dịch, và mỗi giao (Sequential PAttern Mining using A Bitmap dịch bao gồm một tập các phần tử, cùng một Representation) [4] với ý tưởng chính là sử ngưỡng phổ biến (minsup), khai phá mẫu dụng bitmap để lưu trữ CSDL đồng thời hỗ tuần tự tìm ra tất cả các chuỗi (subsequence) trợ tính toán giá trị hỗ trợ mà không phải phổ biến, là dãy tuần tự xuất hiện trong tập quét lại CSDL. Các thử nghiệm cho thấy dữ liệu với tần số không nhỏ hơn ngưỡng SPAM tìm được toàn bộ kết quả trùng khớp phổ biến. SPM ngày càng được sử dụng rộng với thuật toán GSP nhưng với tốc độ nhanh rãi trong thương mại điện tử (phân tích, dự hơn đáng kể [4]. báo xu hướng mua sắm, quản lý kho hàng, Các thuật toán sử dụng bitmap sau này như …) và cũng được ứng dụng hiệu quả cho Số 02 & 03 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 71CMSPAM(2014) và CMSPADE(2014) đều người dùng có thể cách xa nhau về mặt thờidựa trên ý tưởng của SPAM ([5],[6],[7]). gian. Và như vậy, nói chung các hệ thống Cơ sở dữ liệu bitmap theo chiều dọc thương mại điện tử sẽ đều gặp phải trường(Vertical Database Bitmap-VDB) có thể hợp dữ liệu thưa, tức là số giao dịch trungđược hiểu đơn giản là một CSDL mà mỗi bình trên một người dùng và số sản phẩmhàng đại diện cho một item và đưa ra danh trung bình trong một lần giao dịch khôngsách thứ tự xuất hiện của item đó trong cao.CSDL Thuật toán cải tiến được chúng tôi đặt tên Thuật toán SPAM có 3 điểm đáng chú ý là CMSPAME đưa ra một số thay đổi riêng[4]: cho trường hợp dữ liệu thưa. Các thử nghiệm SPAM sử dụng bitmap để lưu trữ cơ sở dữ đã được thực hiện trên bộ dữ liệu chuẩn củaliệu theo chiều dọc: đặc điểm này giúp tính P. Fournier-Viger [8] và cho ra kết quả tốttoán giá trị hỗ trợ cho mỗi item một cách hơn khá rõ ràng về mặt hiệu năng (thời giannhanh chóng mà không cần duyệt lại toàn bộ chạy thuật toán).cơ sở dữ liệu như các thuật toán sử dụng cơsở dữ liệu theo chiều ngang. Việc sử dụng II. THUẬT TOÁN KHAI PHÁ DỮ LIỆUbitmap để lưu trữ dữ liệu gi ...