Nội dung

BỘ GIÁO DỤC VIỆN HÀN LÂM KHOA HỌC VÀ ĐÀO TẠO VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------------------- Trần Thế Anh KHAI PHÁ MẪU DÃY LỢI ÍCH CAO VỚI KHOẢNG CÁCH THỜI GIAN LUẬN VĂN THẠC SĨ: CÔNG NGHỆ THÔNG TIN Hà Nội – 2020 BỘ GIÁO DỤC VIỆN HÀN LÂM KHOA HỌC VÀ ĐÀO TẠO VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------------------- Trần Thế Anh KHAI PHÁ MẪU DÃY LỢI ÍCH CAO VỚI KHOẢNG CÁCH THỜI GIAN Chuyên ngành: Hệ thống thông tin Mã số: 8480104 LUẬN VĂN THẠC SĨ: CÔNG NGHỆ THÔNG TIN CÁN BỘ HƯỚNG DẪN KHOA HỌC: Hướng dẫn 1 : TS. Đặng Thị Oanh Hướng dẫn 2 : PGS. TS. Phạm Thanh Giang Hà Nội – 2020 Lời cam đoan Tôi cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả nêu trong luận văn là trung thực và chưa từng được ai công bố trong bất cứ công trình nào. TÁC GIẢ LUẬN VĂN Trần Thế Anh Lời cảm ơn Lời đầu tiên, tôi xin gửi lời cảm ơn sâu sắc tới TS. Đặng Thị Oanh và PGS. TS Phạm Thanh Giang đã tận tình giúp đỡ, hướng dẫn, định hướng tôi trong quá trình nghiên cứu và hoàn thành luận văn này. Tôi xin cảm ơn Khoa Công nghệ thông tin và Truyền thông - Học Viện khoa học và Công nghệ đã tạo điều kiện cho tôi hoàn thành chương trình học tập và nghiên cứu trong hai năm học vừa qua. Tôi cũng xin chân thành cảm ơn Lãnh đạo Viện Công nghệ thông tin Viện Hàn lâm Khoa học và Công nghệ Việt Nam đã tạo điều kiện thuận lợi cho quá trình học tập của mình, cảm ơn các các bộ của phòng Công nghệ phần mềm trong quản lý đã nhiệt tình trong công tác, giúp tôi dành thời gian hoàn thành luận văn. Cuối cùng, tôi xin cảm ơn gia đình, bạn bè, đồng nghiệp đã luôn là nguồn động viên, ủng hộ, giúp tôi thêm động lực để hoàn thành tốt luận văn này. Trần Thế Anh Danh mục các ký hiệu và chữ viết tắt STT Từ viết Tiếng Anh Tiếng Việt tắt Cơ sở dữ liệu 1 CSDL 2 SPM Sequential pattern mining 3 SDB Sequence Database Cơ sở dữ liệu dãy HUSPM High utility sequential Khai phá mẫu dãy lợi ích 4 pattern mining cao Quantitative Sequence Cơ sở dữ liệu dãy định Database lượng 5 6 QSDB QiSDB Quantitative item interval Sequence Database Khai phá mẫu dãy thường xuyên Cơ sở dữ liệu dãy định lượng với khoảng cách thời gian Danh mục các bảng Bảng 1.1 Cơ sở dữ liệu dãy SDB ................................................................ 7 Bảng 1.2 Cơ sở dữ liệu chiếu với tiền tố ........................................... 17 Bảng 1.3 Cơ sở dữ liệu chiếu với tiền tố <(ab)> ...................................... 17 Bảng 2.1 Cơ sở dữ liệu dãy định lượng QSDB ........................................ 23 Bảng 2.2 Bảng lợi ích ngoài ...................................................................... 24 Bảng 2.3 Sinh mẫu dãy ứng viên trong thuật toán UL ............................. 31 Bảng 2.4 Sinh mẫu dãy ứng viên trong thuật toán US ............................. 34 Bảng 2.5 Bảng lợi ích của các mẫu dãy 1 phần tử trong QSDB............... 37 Bảng 2.6 Bảng chỉ mục ............................................................................. 38 Bảng 2.7 Lợi ích của từng mục dữ liệu trong từng dãy Si ........................ 41 Bảng 2.8 Lợi ích của các dãy Si ................................................................ 41 Bảng 2.9 CSDL thu được sau khi loại bỏ ứng viên không tiềm năng ...... 42 Bảng 2.10 CSDL chiếu QSDB|a của mẫu dãy ................................... 42 Bảng 2.11 Lợi ích của các dãy trong QSDB|a ........................................... 43 Bảng 2.12 Bảng lợi ích của các mẫu dãy 2 phần tử với tiền tố ......... 43 Bảng 2.13 CSDL QSDB|a mới sau khi loại bỏ mục f ............................... 44 Bảng 2.14 CSDL chiếu QSDB|aa của mẫu dãy ............................... 44 Bảng 3.1 Cơ sở dữ liệu dãy lợi ích cao với khoảng cách thời gian QiSDB ......................................................................................................................... 48 Bảng 3.2 Bảng lợi ích ngoài ...................................................................... 49 Bảng 3.3 Bảng lợi ích của các mẫu dãy 1 phần tử trong QiSDB ............. 53 Bảng 3.4 Sinh mẫu dãy ứng viên trong UIL ............................................. 59 Bảng 3.5 Đặc điểm các tập dữ liệu thử nghiệm ........................................ 60 Bảng 3.6 Ràng buộc thời gian ................................................................... 61 Danh mục các hình vẽ, đồ thị Hình 1.1. Các bước sinh mẫu dãy của thuật toán GSP ............................. 12 Hình 3.1 Thời gian chạy Bộ dữ liệu BMSWebView1 .............................. 62 Hình 3.2 Thời gian chạy Bộ dữ liệu BMSWebView2 .............................. 62 Hình 3.3 Thời gian chạy Bộ dữ liệu Bible ................................................ 63 Hình 3.4 Thời gian chạy Bộ dữ liệu Fifa .................................................. 63 Hình 3.5 Bộ nhớ sử dụng trên bộ dữ liệu BMSWebView1 ...................... 64 Hình 3.6 Bộ nhớ sử dụng trên bộ dữ liệu BMSWebView2 ...................... 64 Hình 3.7 Bộ nhớ sử dụng trên bộ dữ liệu Bible ........................................ 65 Hình 3.8 Bộ nhớ sử dụng trên bộ dữ liệu Fifa ......................................... 65 MỤC LỤC MỞ ĐẦU .................................................................................................... 3 CHƯƠNG 1. TỔNG QUAN KHAI PHÁ MẪU DÃY THƯỜNG XUYÊN VÀ MỘT SỐ MỞ RỘNG ................................................................ 5 1.1. GIỚI THIỆU ..................................................................................... 5 1.2. MỘT SỐ KHÁI NIỆM CƠ BẢN ............................................................ 6 1.3. KHAI PHÁ MẪU DÃY THƯỜNG XUYÊN ............................................. 9 1.3.1. Thuật toán GSP:...................................................................... 10 1.3.2. Thuật toán PrefixSpan: ........................................................... 13 a) Một số định nghĩa: .............................................................................13 b) Mô tả thuật toán: ...............................................................................15 1.4. MỞ RỘNG BÀI TOÁN KHAI PHÁ MẪU DÃY THƯỜNG XUYÊN ............ 17 1.5. KẾT LUẬN CHƯƠNG 1 ................................................................... 19 CHƯƠNG 2. KHAI PHÁ MẪU DÃY LỢI ÍCH CAO ..................... 21 2.1. GIỚI THIỆU ................................................................................... 21 2.2. BÀI TOÁN KHAI PHÁ MẪU DÃY LỢI ÍCH CAO .................................. 23 2.3. THUẬT TOÁN UL, US ................................................................... 28 2.3.1. Thuật toán UL: ........................................................................ 28 2.3.2. Thuật toán US: ........................................................................ 32 2.4. THUẬT TOÁN PHUS ..................................................................... 35 2.4.1. Bảng lợi ích:............................................................................ 36 2.4.2. Bảng chỉ mục: ......................................................................... 37 2.5. KẾT LUẬN CHƯƠNG 2 ................................................................... 44 CHƯƠNG 3. KHAI PHÁ MẪU DÃY LỢI ÍCH CAO VỚI KHOẢNG CÁCH THỜI GIAN ................................................................... 46 3.1. GIỚI THIỆU ................................................................................... 46 3.2. BÀI TOÁN KHAI PHÁ MẪU DÃY LỢI ÍCH CAO VỚI KHOẢNG CÁCH THỜI GIAN 47 3.2.1. Một số định nghĩa: .................................................................. 47 1 3.2.2. Khai phá mẫu dãy lợi ích cao với khoảng cách thời gian ...... 51 3.2.3. Thuật toán UIL: ...................................................................... 52 a) Ràng buộc thời gian:..........................................................................52 b) Bảng lợi ích: ......................................................................................52 c) Giảm dần cận trên lợi ích swu ...........................................................53 3.2.4. Thử nghiệm thuật toán UIL..................................................... 60 3.3. KẾT LUẬN CHƯƠNG 3 ................................................................... 66 CHƯƠNG 4. KẾT LUẬN VÀ KIẾN NGHỊ ...................................... 67 TÀI LIỆU THAM KHẢO ...................................................................... 69 2 MỞ ĐẦU Cùng với sự bùng nổ của ngành công nghệ thông tin trong vài thập kỷ qua, dữ liệu được sinh ra và lưu trữ trong các cơ sở dữ liệu ngày càng nhiều lên. Việc phân tích dữ liệu bằng phương pháp thủ công do vậy ngày càng khó khăn và tốn thời gian. Từ thực tế đó, một lĩnh vực nghiên cứu mới đã nổi lên để phát triển các kỹ thuật phân tích dữ liệu tự động: Khai phá dữ liệu. Mục tiêu của khai phá dữ liệu là tìm ra tri thức từ cơ sở dữ liệu. Khai phá dữ liệu gồm nhiều tác vụ khác nhau như: Phân loại dữ liệu (Classification), Gom cụm dữ liệu (Clustering), Khai phá luật kết hợp (Association Rule) … Khai phá tập mục thường xuyên là một bài toán con của bài toán khai phá luật kết hợp. Khởi nguồn là nghiên cứu của Agrawal [1] phân tích dữ liệu mua sắm của khách hàng trong siêu thị. Khai phá tập mục thường xuyên tập trung xác định các tập mục thường xuyên (frequent itemsets), nghĩa là các mục thường xuất hiện cùng nhau trong CSDL. Khai phá mẫu dãy thường xuyên là một bài toán mở rộng của khai phá tập mục thường xuyên. Các mẫu dãy là các phần tử được sắp xếp theo một thứ tự nhất định (thường là thứ tự thời gian). Mục tiêu của khai phá mẫu dãy thường xuyên là tìm ra các mẫu dãy thường xuyên (frequent sequence patterns), nghĩa là các mẫu dãy thường xuất hiện cùng nhau trong CSDL. Bài toán khai phá mẫu dãy thường xuyên cũng như tập mục thường xuyên sử dụng độ đo là tần xuất xuất hiện của dữ liệu (frequency). Tuy nhiên, tần xuất xuất hiện của dữ liệu không phải lúc nào cũng là độ đo tốt nhất để tìm ra các mẫu dãy có giá trị. Vì đôi khi một số mặt hàng có số lượng mua ít nhưng lại mang lại lợi nhuận cao. Từ thực tế này, một độ đo mới được đề xuất: lợi ích (utility) nhằm tìm ra các mẫu có giá trị. Bài toán khai phá mẫu dãy lợi ích cao được đặt ra để tìm ra các mẫu dãy có giá trị. Trong khai phá mẫu dãy lợi ích cao, các mục trong CSDL đều được gán 1 giá trị số lượng và 1 giá trị trọng số thể hiện mức độ quan trọng của mục đó. Các mẫu dãy trên thực tế ngoài các giá trị lợi ích của các mục còn có giá trị khoảng cách thời gian giữa các thành phần trong dãy. Các mẫu dãy với các 3