Khai thác K tập hữu ích cao nhất trong cơ sở dữ liệu tăng trưởng

Nghiên cứu "Khai thác K tập hữu ích cao nhất trong cơ sở dữ liệu tăng trưởng" đề xuất thuật toán Top-k iHUIM để khai thác Top-k HUI trong cơ sở dữ liệu tăng trưởng. Nghiên cứu cũng cài đặt và tiến hành thực nghiệm trên các cơ sở dữ liệu thực tế để đánh giá hiệu quả thuật toán đã đề xuất. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Khai thác K tập hữu ích cao nhất trong cơ sở dữ liệu tăng trưởngKỷ yếu Hội thảo khoa học Khoa Công nghệ thông tin, năm 2024 KHAI THÁC K TẬP HỮU ÍCH CAO NHẤT TRONG CƠ SỞ DỮ LIỆU TĂNG TRƯỞNG Vũ Văn Vinh1, Lâm Thị Họa Mi1,* Trường Đại học Công thương Thành phố Hồ Chí Minh 1 * Email: milth@huit.edu.vn Ngày nhận bài 13/4/202; Ngày chấp nhận đăng: 20/05/2024 TÓM TẮT Phát hiện được các tri thức hữu ích, thú vị tiềm ẩn trong các cơ sở dữ liệu nhằm nângcao hiệu quả quá trình sản xuất và kinh doanh là một vấn đề thu hút được sự quan tâm củanhiều nhà nghiên cứu trong và ngoài nước. Trong đó, giải quyết bài toán khai thác k tập hữuích cao nhất (Top-k HUIM) trong cơ sở dữ liệu giao dịch là một hướng nghiên cứu quantrọng và đã có nhiều phương pháp hiệu quả được đề xuất. Bài toán này giúp giải quyết đượckhó khăn trong việc chọn ngưỡng sao cho phù hợp của bài toán khai thác tập hữu ích caotruyền thống. Tuy nhiên các thuật toán này đều đặt giải thiết rằng các cơ sở dữ liệu đều làtĩnh. Vì vậy khi áp dụng vào các cơ sử dữ liệu có tăng trưởng, cơ sở dữ liệu luôn được bổsung các giao dịch mới, chi phi khái thác K tập hữu ích cao nhất là rất lớn đặc biệt là về mặtthời gian và bộ nhớ. Do đó, trong nghiên cứu này chúng tôi sẽ tập trung vào việc điều chỉnhlại cấu trúc lưu trữ UtilityList và đề xuất cách tăng ngưỡng hiệu quả để giải quyết bài toánTop-k iHUIM trong cơ sở dữ liệu tăng trưởng. Trong nghiên cứu này, chúng tôi đề xuất thuậttoán Top-k iHUIM để khai thác Top-k HUI trong cơ sở dữ liệu tăng trưởng. Nghiên cứu cũngcài đặt và tiến hành thực nghiệm trên các cơ sở dữ liệu thực tế để đánh giá hiệu quả thuậttoán đã đề xuất.Từ khóa: tập hữu ích cao, K tập hữu ích cao nhất, chiến lược tăng ngưỡng, cơ sở dữ liệu tăngtrưởng. 1. MỞ ĐẦU Việc khám phá các tập mục phổ biến trong cơ sở dữ liệu giao dịch đã giúp phát hiện cáctập sản phẩm có tần xuất xuất hiện cao để từ đó đưa ra các chiến lược kinh doanh, sản xuấthiệu quả hơn trong thực tế cuộc sống. Tuy nhiên, việc khai thác tập phổ biến chỉ quan tâmtới một sản phẩm xuất hiện hay không trong các giao dịch mà bỏ qua nhiều yếu tố quantrọng khác liên quan tới sản phẩm đó như: lợi ích mà sản phẩm đó mang lại, số lượng sảnphẩm đó trong giao dịch, độ quan trọng của sản phẩm đó,….Để khắc phục hạn chế này củabài toán khai thác tập phổ biến, bài toán khai thác tập hữu ích cáo đã được đề xuất. Bài toánnày sẽ có đầu vào là cơ sở dữ liệu giao dịch và một ngưỡng độ hữu ích tối thiểu do ngườidùng xác định. Từ đó, nhiệm vụ của bài toán là tất cả các tập mục trong cơ sở dữ liệu đã chomà có độ hữu ích lớn hơn ngưỡng đã chọn. Nếu có hiểu biết rõ về dữ liệu đang khai thác vàđặc tính của các mục trong cơ sở liệu sẽ là một ưu thế trong việc lựa chọn ngưỡng tối thiểuphù hợp. Nhưng ngược lại, việc xác định một ngưỡng độ hữu ích tối thiểu là một bài toánkhông dễ nếu thiếu thông tin liên quan dữ liệu đang khai thác. Chọn một ngưỡng tối thiểuquá lớn có thể sẽ không thu được bất kỳ tập hữu ích cao nào. Chọn một ngưỡng tối thiểu quáthấp, không gian tìm kiếm của bài toán trở nên nên không lồ gây ra tốn kém chi phí cho quá 144Vũ Văn Vinh, Lâm Thị Họa Mitrình khai thác. Hơn thế nữa, số lượng tập hữu ích cao thu được cũng rất lớn gây khó khăntrong việc lựa chọn tập hữu ích cao phù hợp cho vấn đề đưa ra quyết định trong hoạt độngthực tế. Bài toán khai thác K tập hữu ích cao nhất (Top-K HUIM) được ra đời để giải quyếtvấn đề khó khăn này. Top-K HUIM chỉ yêu cầu người dùng lựa chọn số lượng tập hữu íchcao mà họ muốn và đầu ra sẽ cung cấp cho người dùng K tập có độ hữu ích cao nhất trong cơsở dữ liệu ban đầu. Bài toán này đã có nhiều nghiên cứu và nhiều thuật toán hiệu quả đãđược đề xuất. Nhưng các thuật toán này chỉ áp dụng trên các cơ sở dữ liệu tĩnh, không phùhợp với các cơ sở dữ liệu tăng trưởng. Cơ sở dữ liệu tăng trưởng là cơ sở dữ liệu mà dữ liệuluôn được được mở rộng, thêm mới các giao dịch. Ví du, các đơn hàng trong siêu thị luônđược phát sinh từng giờ từng phút làm cho cơ sở dữ liệu về bán hàng ngày càng được mởrộng cả về số lượng giao dịch và cả về số lượng sản phẩm. Trong nghiên cứu này, chúng tôisẽ tập trung giải quyết bài toán khai thác top-K tập hữu ích cao trong cơ sở dữ liệu tăngtrưởng. Trước hết, chúng tôi sẽ nghiên cứu cách thức lưu trữ thông tin để có thể sử dụng trongviệc khai thác tiếp khi dữ liệu có sự phát sinh các giao dịch mới cũng như các mục mới. Từđó, nghiên cứu tập trung vào một vào các đóng góp sau: Điều chỉnh lại cấu trúc lưu trữUtiltity List để lưu được thô ...