Nghiên cứu phát triển mô hình, thuật toán khai phá tập phần tử có trọng số và lợi ích cao
Khai phá dữ liệu
Nghiên cứu này tập trung vào khai phá luật kết hợp, một trong những kỹ thuật quan trọng nhất trong khai phá dữ liệu, nhằm tìm ra mối quan hệ giữa các phần tử trong cơ sở dữ liệu. Bài toán con khai phá tập phổ biến đã thu hút nhiều quan tâm nhưng vẫn tồn tại hạn chế khi không đánh giá được sự quan trọng khác nhau của từng phần tử trong các giao dịch hoặc cơ sở dữ liệu. Để khắc phục, các mô hình mở rộng như khai phá tập phổ biến có trọng số (WFI) và khai phá tập lợi ích cao (HUI) đã được đề xuất, tính đến mức độ quan trọng khác nhau của các phần tử.
Một thách thức lớn trong WFI và HUI là thiếu tính chất đóng, vốn giúp giảm số lượng ứng viên và không gian tìm kiếm. Hầu hết các thuật toán khai phá tập lợi ích cao sử dụng ngưỡng lợi ích trọng số giao dịch (TWU) do Liu và cộng sự công bố năm 2005. Tuy nhiên, ngưỡng TWU còn khá cao so với lợi ích thực tế, dẫn đến việc sinh ra một lượng lớn ứng viên không cần thiết, tiêu tốn thời gian và không gian tìm kiếm.
Trên cơ sở những phân tích này, luận án tiến sĩ đã chọn đề tài “Nghiên cứu phát triển mô hình, thuật toán khai phá tập phần tử có trọng số và lợi ích cao”. Mục tiêu nghiên cứu là tìm hiểu các thuật toán khai phá tập phổ biến, WFI và HUI; xây dựng mô hình, điều kiện, cấu trúc dữ liệu nhằm giảm không gian tìm kiếm; và từ đó xây dựng các thuật toán khai phá tập phổ biến có trọng số và tập lợi ích cao hiệu quả hơn.
Luận án đề xuất mô hình Lợi ích ứng viên có trọng số (CWU – Candidate Weighted Utility) để khắc phục nhược điểm của mô hình TWU. Mô hình CWU định nghĩa các khái niệm như tập tiền tố và lợi ích ứng viên có trọng số, đồng thời chứng minh tính chất đóng của các tập phần tử theo mô hình CWU. Các mệnh đề được đưa ra khẳng định CWU(Y) ≤ TWU(Y) và HCWUs ⊆ HTWUs, cho thấy mô hình CWU có thể giảm số lượng ứng viên.
Dựa trên mô hình CWU, luận án trình bày thuật toán HP, cải tiến từ thuật toán PB, sử dụng kết hợp hai mô hình TWU và CWU, sắp xếp các phần tử trong giao dịch giảm dần theo lợi ích, và sử dụng các cấu trúc dữ liệu như bảng ứng viên TCk, bảng chỉ số ITX và bảng giao dịch lợi ích UTi. Bên cạnh đó, luận án còn đề xuất thuật toán song song PPB khai phá tập lợi ích cao trên mô hình chia sẻ bộ nhớ, sử dụng bảng chỉ số kết hợp danh sách lợi ích và giản lược thông tin lưu trữ. Một thuật toán khác là CTU-PRO+ cũng được cải tiến từ CTU-PRO, sử dụng mô hình CWU.
Kết quả thực nghiệm của các thuật toán HP và PPB, so sánh với các thuật toán hiện có (Two Phase, PB) trên các bộ dữ liệu T30I4D100K và Mushroom, cho thấy sự cải thiện đáng kể về số lượng ứng viên được sinh ra và thời gian thực hiện.