Tăng tốc cho khai thác tập hữu ích cao bằng việc tránh khai thác lại các tập hữu ích cao phổ biến

Abstract

Khai thác tập hữu ích cao là tìm ra tập mặt hàng thường được bán cùng nhau và có lãi lớn hơn hoặc bằng một ngưỡng cho trước từ các cơ sở dữ liệu giao dịch về mua hàng. Các tập hữu ích cao thu được gồm các tập hữu ích cao xuất hiện nhiều lần. Tri thức về các tập hữu ích cao phổ biến này đã được biết và quen thuộc. Vì vậy, các thuật toán không cần khai thác lại các tập mục này. Các nghiên cứu trước đây chưa tránh khai thác lại các tập mục hữu ích cao phổ biến nên vẫn tốn thời gian tính toán và bộ nhớ lưu trữ. Trong bài báo này, chúng tôi đưa ra một thuật toán khai tập hữu ích cao mà tránh sinh ra các tập hữu ích cao phổ biến đã biết. Một danh sách nhỏ gọn để lưu trữ các tập mục sinh ra trong quá trình khai thác được trình bày. Thuật toán khai thác tập hữu ích cao gồm các bước sau: Đầu tiên, dùng một phần cơ sở dữ liệu để tìm các mục vừa phổ biến vừa có lãi cao. Tiếp theo, sinh ra các tập mục trong mỗi giao dịch mà mỗi tập mục chứa tối đa một mục vừa phổ biến vừa có lãi cao. Các tập mục được sinh ra được tính lãi và lưu vào một danh sách chung. Sau khi duyệt xong cơ sở dữ liệu, kiểm tra lãi của từng tập mục trong danh sách chung để đưa ra các tập hữu ích cao. Các thực nghiệm được làm trên các tập dữ liệu chuẩn. Thuật toán đề xuất được so sánh với các thuật toán chuẩn. Kết quả thực nghiệm cho thấy thuật toán đề xuất cho kết quả tốt hơn các thuật toán được so sánh khi cân đối thời gian tính toán và bộ nhớ lưu trữ. Đặc biệt, thuật toán mới giảm đáng kể dung lượng bộ nhớ.