Luận Án Tiến Sĩ: 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

• Tác giả: Đậu Hải Phong
• Người hướng dẫn: TS. Nguyễn Mạnh Hùng
• Trường học: Học viện Kỹ thuật Quân sự
• Chuyên ngành: Cơ sở Toán học cho Tin học
• Đề 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
• Loại tài liệu: luận án tiến sĩ
• Địa điểm: Hà Nội

• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: TỔNG QUAN
• 1.1. Giới thiệu chung
• 1.2. Tập phổ biến
• 1.3. Khái niệm cơ sở
• 1.4. Một số phương pháp khai phá tập phổ biến
• 1.5. Tập phổ biến có trọng số
• 1.6. Khái niệm cơ sở
• 1.7. Một số phương pháp khai phá tập phổ biến có trọng số
• 1.8. Thuật toán khai phá tập phổ biến có trọng số theo chiều dọc
• 1.9. Tập lợi ích cao
• 1.10. Khái niệm cơ sở
• 1.11. Một số phương pháp khai phá tập lợi ích cao
• 1.12. Kết luận chương
• 2. CHƯƠNG 2: THUẬT TOÁN KHAI PHÁ TẬP LỢI ÍCH CAO DỰA TRÊN MÔ HÌNH CWU
• 2.1. Giới thiệu chung
• 2.2. Mô hình hiệu quả khai phá tập lợi ích cao
• 2.3. Đề xuất mô hình CWU
• 2.4. Thuật toán HP khai phá tập lợi ích cao dựa trên chỉ số hình chiếu và mô hình CWU
• 2.4.1. Mô tả thuật toán HP
• 2.4.2. Ví dụ minh họa thuật toán HP
• 2.4.3. Độ phức tạp tính toán thuật toán HP
• 2.4.4. Kết quả thực nghiệm
• 2.5. Thuật toán song song PPB khai phá tập lợi ích cao dựa trên chỉ số hình chiếu và danh sách lợi ích
• 2.5.1. Một số cấu trúc được sử dụng trong thuật toán PPB
• 2.5.2. Mô tả thuật toán song song PPB
• 2.5.3. Ví dụ minh họa thuật toán PPB
• 2.5.4. Độ phức tạp tính toán của thuật toán PPB
• 2.5.5. Kết quả thực nghiệm
• 2.6. Thuật toán CTU-PRO+
• 2.6.1. Một số cấu trúc
• 2.6.2. Độ phức tạp tính toán thuật toán CTU-PRO+
• 2.6.3. Kết quả thực nghiệm
• 2.7. Kết luận chương
• 3. CHƯƠNG 3: THUẬT TOÁN KHAI PHÁ TẬP LỢI ÍCH CAO TRÊN CÂY DANH SÁCH LỢI ÍCH VÀ CẤU TRÚC RTWU
• 3.1. Cấu trúc dữ liệu hiệu quả cho khai phá tập lợi ích cao
• 3.2. Mô tả cấu trúc cây CUP
• 3.3. Ví dụ minh họa cây CUP
• 3.4. Thuật toán HUI-Growth
• 3.5. Ví dụ minh họa thuật toán HUI-Growth
• 3.6. Độ phức tạp thuật toán HUI-Growth
• 3.7. Kết quả thực nghiệm
• 3.8. Cấu trúc RTWU cho tỉa tập ứng viên
• 3.9. Thuật toán tuần tự EAHUI-Miner dựa trên cấu trúc RTWU
• 3.10. Xây dựng danh sách lợi ích mở rộng
• 3.11. Thuật toán tuần tự EAHUI-Miner
• 3.12. Độ phức toán tính toán thuật toán EAHUI-Miner
• 3.13. Thuật toán song song PEAHUI-Miner
• 3.14. Kết quả thực nghiệm
• 3.15. Kết luận chương
• KẾT LUẬN VÀ KIẾN NGHỊ
• Kết quả đạt được
• Hướng phát triển
• DANH MỤC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN QUAN ĐẾN LUẬN ÁN
• TÀI LIỆU THAM KHẢO

I. Phát triển mô hình

Phát triển mô hình là trọng tâm chính của luận án, tập trung vào việc xây dựng các mô hình toán học và cấu trúc dữ liệu hiệu quả để khai phá tập phần tử có trọng số và lợi ích cao. Mô hình CWU (Candidate Weighted Utility) được đề xuất nhằm giảm thiểu không gian tìm kiếm và tối ưu hóa quá trình khai phá. Mô hình này dựa trên việc sử dụng các chỉ số hình chiếu và danh sách lợi ích để cắt tỉa các tập ứng viên không cần thiết, từ đó nâng cao hiệu suất của thuật toán.

1.1. Mô hình CWU

Mô hình CWU là một cải tiến quan trọng trong việc khai phá tập lợi ích cao. Nó sử dụng chỉ số hình chiếu để tính toán lợi ích trọng số của các tập phần tử, giúp loại bỏ các ứng viên không đạt ngưỡng lợi ích. Mô hình này cũng tích hợp cấu trúc dữ liệu hiệu quả như cây CUP (Compressed Utility Pattern) để lưu trữ và xử lý dữ liệu một cách tối ưu.

1.2. Cấu trúc cây CUP

Cấu trúc cây CUP được thiết kế để nén và lưu trữ các mẫu lợi ích, giúp giảm thiểu không gian lưu trữ và tăng tốc độ truy xuất dữ liệu. Cây CUP kết hợp với danh sách lợi ích mở rộng, cho phép thuật toán HUI-Growth khai phá tập lợi ích cao một cách hiệu quả.

II. Thuật toán khai phá

Luận án đề xuất nhiều thuật toán khai phá hiệu quả, bao gồm thuật toán HP, PPB, và CTU-PRO+, nhằm tối ưu hóa quá trình khai phá tập phần tử có trọng số và lợi ích cao. Các thuật toán này được thiết kế để giảm thiểu số lượng ứng viên không cần thiết và tăng tốc độ xử lý dữ liệu.

2.1. Thuật toán HP

Thuật toán HP sử dụng chỉ số hình chiếu và mô hình CWU để khai phá tập lợi ích cao. Nó được thiết kế để giảm độ phức tạp tính toán bằng cách loại bỏ các tập ứng viên không đạt ngưỡng lợi ích. Thuật toán này cũng được minh họa qua các ví dụ cụ thể, cho thấy hiệu quả trong việc xử lý dữ liệu lớn.

2.2. Thuật toán PPB

Thuật toán PPB là một thuật toán song song, được thiết kế để khai phá tập lợi ích cao trên các cấu trúc dữ liệu phân tán. Nó sử dụng danh sách lợi ích và chỉ số hình chiếu để tối ưu hóa quá trình khai phá, đặc biệt hiệu quả khi xử lý các tập dữ liệu lớn.

III. Ứng dụng thực tế

Luận án không chỉ tập trung vào lý thuyết mà còn nhấn mạnh vào ứng dụng thực tế của các mô hình và thuật toán được đề xuất. Các kết quả thực nghiệm cho thấy hiệu quả của các thuật toán trong việc khai phá tập phần tử có trọng số và lợi ích cao, đặc biệt trong các lĩnh vực như kinh doanh, y tế, và tài chính.

3.1. Lợi ích kinh tế

Các thuật toán được đề xuất giúp tối ưu hóa lợi ích kinh tế bằng cách phát hiện các tập phần tử có giá trị cao trong các cơ sở dữ liệu giao dịch. Điều này có thể áp dụng trong việc tối đa hóa doanh thu, giảm thiểu chi phí, và quản lý hàng tồn kho.

3.2. Phân tích dữ liệu

Các mô hình và thuật toán này cũng được sử dụng trong phân tích dữ liệu để dự đoán các xu hướng và hành vi trong tương lai. Chúng giúp các nhà quản lý đưa ra các quyết định dựa trên dữ liệu một cách chính xác và hiệu quả.