Luận án: Mô hình và thuật toán khai phá tập phần tử có trọng số và lợi ích cao

BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG HỌC VIỆN KỸ THUẬT QUÂN SỰ ĐẬU HẢI PHONG 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 LUẬN ÁN TIẾN SĨ CƠ SỞ TOÁN HỌC CHO TIN HỌC HÀ NỘI – NĂM 2018 2 BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG HỌC VIỆN KỸ THUẬT QUÂN SỰ ĐẬU HẢI PHONG 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 Chuyên ngành: Cơ sở Toán học cho Tin học Mã số : 62.10 LUẬN ÁN TIẾN SĨ CƠ SỞ TOÁN HỌC CHO TIN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. TS NGUYỄN MẠNH HÙNG 2.TS ĐOÀN VĂN BAN HÀ NỘI ­ 2018 4 LỜI CAM ĐOAN Tôi xin cam đoan luận án này là công trình nghiên cứu do tác giả thực hiện dưới sự hướng dẫn của tập thể cán bộ hướng dẫn. Luận án có sử dụng thông tin trích dẫn từ nhiều nguồn tham khảo khác nhau, các thông tin trích dẫn đều được ghi rõ nguồn gốc. Các số liệu thực nghiệm, kết quả nghiên cứu trình bày trong luận án là hoàn toàn trung thực, chưa được công bố bởi tác giả nào hay trong bất kì công trình nào khác.

5 LỜI CẢM ƠN Luận án này được thực hiện và hoàn thành tại Khoa Công nghệ Thông tin, Học viện kỹ thuật Quân sự. Để đạt được kết quả này không thể thiếu sự định hướng và hỗ trợ của giáo viên hướng dẫn. Tôi luôn tỏ lòng cảm ơn và tri ân những người đã giúp đỡ trong quá trình nghiên cứu sau đây. Tôi luôn tỏ lòng biết ơn công lao to lớn của hai giáo viên hướng dẫn.

Thầy là những người Thầy lớn tận tình, hướng dẫn và giúp đỡ trong nghiên cứu. Tôi trân trọng cảm ơn Lãnh đạo, Thầy/Cô trong Khoa Công nghệ Thông tin, Phòng Sau đại học ­ Học viện Kỹ thuật Quân sự đã tạo điều kiện thuận lợi, giúp đỡ trong quá trình học tập và nghiên cứu. Tôi cảm ơn tới Ban Giám Hiệu, Thầy/Cô và bạn bè đồng nghiệp tại trường Đại học Thăng Long đã tạo điều kiện để tôi tập trung nghiên cứu. Tôi xin dành tất cả sự yêu thương và lời cảm ơn tới gia đình, bố mẹ, vợ con, anh chị em và người thân luôn là động viên mạnh mẽ giúp tôi thực hiện Luận án.

Xin chân thành cảm ơn! Tác giả luận án Đậu Hải Phong 6 MỤC LỤC 7 DANH MỤC CÁC KÝ HIỆU VÀ CÁC CHỮ VIẾT TẮT ST Từ viết Thuật ngữ tiếng Anh Thuật ngữ tiếng Việt T tắt 1. AU Actual Utility Lợi ích thực tế 2. CFP Compact Frequent Pattern Mẫu phổ biến nén 3. CSDL Database Cơ sở dữ liệu 4.

CUP Compressed Utility Pattern Mẫu lợi ích nén 5. CWU Candidate Weighted Utility Lợi ích trọng số ứng viên 6. FI Frequent Itemsets Tập phổ biến 7. FP Frequent Pattern Mẫu phổ biến 8.

IT Index Table Bảng chỉ số High Candidate Weighted Lợi ích ứng viên có trọng 9. HCWU Utility số cao Low Candidate Weighted Lợi ích trọng số ứng viên 10. LCWU Utility thấp Remaining Transaction 11. RTWU Lợi ích giao dịch còn lại Weighted Utilization 12.

TC Table Candidate Bảng ứng viên 13. TWU Transaction Weighted Utility Lợi ích trọng số giao dịch 14. UL Utility List Danh sách lợi ích 15. UT Utility Table Bảng giao dịch lợi ích Vertical Mining using Khai phá theo chiều dọc 16.

VMUDG Diffset Groups sử dụng các nhóm Diffset Vertical Mining of Weighted Khai phá theo chiều dọc 17. VMWFP Frequent Patterns tập phổ biến có trọng số 8 DANH MỤC CÁC BẢNG 9 10 MỞ ĐẦU Ngày nay, công nghệ thông tin đóng một vai trò rất quan trọng trong mọi khía cạnh của cuộc sống con người, giúp thu thập khối lượng dữ liệu khổng lồ từ nhiều nguồn khác nhau. Dữ liệu này có thể được lưu trữ và duy trì để tạo ra thông tin và tri thức. Khai phá dữ liệu là một quá trình tìm kiếm thông tin hữu ích từ số lượng lớn dữ liệu.

Thông tin đó được sử dụng để dự đoán các xu hướng, hành vi trong tương lai. Hàng ngày một lượng dữ liệu khổng lồ được tạo ra trong các lĩnh vực khác nhau. Do đó, khai phá dữ liệu đang trở thành một kỹ thuật hữu ích và được ứng dụng rộng lớn trong các lĩnh vực khác nhau. Các phương pháp khai phá dữ liệu được sử dụng, giúp xây dựng mô hình dự đoán, phát hiện hành vi của dữ liệu, từ đó đưa ra quyết định [44].

Khai phá dữ liệu đang trở nên phổ biến từ những thành công trong nhiều lĩnh vực khác nhau như y tế, tài chính, viễn thông, kinh doanh, giáo dục,… [43]. Khai phá dữ liệu gồm các kỹ thuật khác nhau như: phân lớp, phân cụm, khai phá luật kết hợp,… Khai phá luật kết hợp là một trong những kỹ thuật quan trọng nhất trong khai phá dữ liệu. Mục đích chính của khai phá luật kết hợp là tìm ra mối quan hệ giữa các phần tử khác nhau trong cơ sở dữ liệu [54]. Bài toán khai phá luật kết hợp gồm hai bài toán con đó là khai phá tập phổ biến và sinh luật kết hợp, trong đó bài toán khai phá tập phổ biến thu hút nhiều nhà nghiên cứu trong nước và thế giới quan tâm.

Khai phá tập phổ biến trong thực tế vẫn còn nhiều hạn chế, không đáp ứng được nhu cầu của người sử dụng như đánh giá sự quan trọng của từng phần tử trong từng giao dịch hay trong cơ sở dữ liệu. Để khắc phục những hạn chế của khai phá tập phổ biến truyền thống, các nhà nghiên cứu đã đề xuất mô hình mở rộng, có tính đến mức độ quan trọng khác nhau của các phần tử trong cơ sở dữ liệu như: khai phá tập phổ biến có trọng số (WFI – Weighted Frequent Itemsets) [11], 11 [58], [72], [32], [33], [64],…; khai phá tập lợi ích cao (HUI – High Utility Itemsets) [13], [39], [23], [38], [62], [60], [26], [77], [65], [55], [17],… Trên thế giới, có rất nhiều nhà nghiên cứu quan tâm về khai phá dữ liệu. Đặc biệt, trong Hội thảo Châu Á Thái Bình Dương về Khai phá dữ liệu và Khám phá tri thức – PAKDD và Hội thảo Quốc tế về Khai phá dữ liệu – ICDM, nhiều công trình về khai phá, phân tích luật kết hợp và tập lợi ích cao đã được công bố. Trong những năm gần đây, các nghiên cứu lên quan đến tập lợi ích cao đã được công bố [62], [55], [38], [77], [17], [26], [24], [23], [37], [15],… Tại Việt Nam, đã có nhiều nhóm nghiên cứu, luận án về luật kết hợp và tập phổ biến tại Viện Hàn lâm Khoa học và Công nghệ Việt Nam, trường Đại học Quốc gia Hà Nội, Đại học Bách Khoa Hà Nội, Đại học Quốc gia thành phố Hồ Chí Minh thực hiện và đã có nhiều kết quả được công bố.

Các thuật toán đề xuất sử dụng cấu trúc cây FP­tree được Han, Wang và Yin giới thiệu năm 2000 trong [30], cách khai phá cây FP­tree không đệ quy bởi cấu trúc cây COFI­tree do Mohammad El­Hajj và Osmar R. Zaiane đề xuất năm 2003 trong [19], [20], [21]. Năm 2010, Nguyễn Huy Đức [2] thực hiện nghiên cứu đề tài “Khai phá tập mục cổ phần cao và lợi ích cao trong cơ sở dữ liệu” sử dụng cấu trúc cây đơn giản và khai phá không dùng đệ quy. Năm 2016, Nguyễn Duy Hàm [1] nghiên cứu đề tài “Phát triển một số thuật toán hiệu quả khai thác tập mục trên cơ sở dữ liệu số lượng có sự phân cấp tập mục” đã đưa ra một số cải tiến nâng cao hiệu quả khai thác tập phổ biến trọng số hữu ích trên CSDL số lượng có sự phân cấp.

Ngoài ra, hàng năm các Hội thảo Quốc gia về “Một số vấn đề chọn lọc của Công nghệ Thông tin” và “Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin ­ FAIR” có rất nhiều báo cáo liên quan đến khai phá dữ liệu. 12 Một trong những thách thức trong khai phá tập phổ biến có trọng số và tập lợi ích cao đó là tập phổ biến có trọng số, tập lợi ích cao không có tính chất đóng [6] ­ tính chất làm giảm số lượng ứng viên được sinh ra 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 đều sử dụng tính chất đóng của TWU (Transaction Weighted Utility) [39] dịch là lợi ích giao dịch có trọng số [39] do Liu và cộng sự công bố. Tuy nhiên, ngưỡng TWU vẫn còn khá cao so với lợi ích thực tế của các tập phần tử, do đó vẫn còn phát sinh một số lượng lớn các ứng viên không cần thiết, làm tiêu tốn thời gian và không gian tìm kiếm.

Trên cơ sở những nghiên cứu, nhận xét và đánh giá ở trên, nghiên cứu sinh đã 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” làm đề tài nghiên cứu cho luận án tiến sĩ của mình. Mục tiêu nghiên cứu ­ Nghiên cứu các thuật toán khai phá tập phổ biến, tập phổ biến có trọng số và tập lợi ích cao. ­ Xây dựng mô hình, cấu trúc dữ liệu nhằm giảm không gian tìm kiếm và dựa trên cơ sở đó để 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. Đối tượng nghiên cứu ­ Các mô hình, cấu trúc dữ liệu để cắt tỉa tập ứng viên được sử dụng trong các thuật toán khai phá tập phổ biến, tập phổ biến có trọng số và tập lợi ích cao.

­ Các thuật toán khai phá tập phổ biến có trọng số và tập lợi ích cao. Phạm vi nghiên cứu 13 ­ Nghiên cứu tổng quan về khai phá tập phổ biến, tập phổ biến có trọng số và tập lợi ích cao. ­ Nghiên cứu, đánh giá các mô hình, cấu trúc dữ liệu và thuật toán khai phá tập phổ biến có trọng số, tập lợi ích cao. Phương pháp nghiên cứu ­ Thu thập, phân tích các mô hình, cấu trúc dữ liệu, thuật toán liên quan đến khai phá tập phổ biến, tập phổ biến có trọng số và tập lợi ích cao.

­ Xây dựng mô hình, cấu trúc dữ liệu và thuật toán khai phá tập phổ biến có trọng số, tập lợi ích cao. ­ Lập trình, thử nghiệm, so sánh, đánh giá hiệu năng, hiệu quả sử dụng tài nguyên của các thuật toán đề xuất. Ngoài những phần mở đầu và kết luận, nội dung luận án bao gồm được trình bày trong 3 chương. Chương 1 giới thiệu các khái niệm cơ sở liên quan; phương pháp khai phá tập phổ biến, tập phổ biến có trọng số và tập lợi ích cao.

Chương 2 trình bày mô hình CWU, các thuật toán khai phá tập lợi ích cao dựa trên mô hình CWU như: HP, PPB, CTU­PRO+.