BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------------------- TRẦN HUY DƯƠNG KHAI PHÁ MẪU DÃY CÓ TRỌNG SỐ TRONG CƠ SỞ DỮ LIỆU DÃY LUẬN ÁN TIẾN SĨ NGÀNH MÁY TÍNH HÀ NỘI – 2021 BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------------------- Trần Huy Dương KHAI PHÁ MẪU DÃY CÓ TRỌNG SỐ TRONG CƠ SỞ DỮ LIỆU DÃY Chuyên ngành: Hệ thống thông tin Mã số: 9 48 01 04 LUẬN ÁN TIẾN SĨ NGÀNH MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. Nguyễn Trường Thắng 2. Vũ Đức Thi Hà Nội – Năm 2021 1 LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của tôi và những kết quả trình bày trong luận án là mới, trung thực và chưa từng được công bố trong bất kỳ công trình của người khác. Những kết quả viết chung với cán bộ hướng dẫn và các tác giả khác đều được sự đồng ý khi đưa vào luận án. Việc tham khảo các nguồn tài liệu, bài viết được thực hiện trích dẫn và ghi nguồn tham khảo theo đúng quy định. Tác giả luận án NCS. Trần Huy Dương i 2 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.Nguyễn Trường Thắng và GS.Vũ Đức Thi đã tận tình hướng dẫn, giúp đỡ tôi trong quá trình nghiên cứu, đăng bài và hoàn thành luận án này. Tôi cũng xin chân thành cảm ơn Ban 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, lãnh đạo Học viện Khoa học và Công nghệ đã tạo điều kiện thuận lợi cho quá trình nghiên cứu của tôi, cảm ơn các cán 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 tập trung nghiên cứu và hoàn thành luận á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 luận án này. Người thực hiện Trần Huy Dương ii 1 MỤC LỤC DANH MỤC HÌNH VẼ.3 DANH MỤC BẢNG BIỂU.4 DANH MỤC CÁC TỪ VIẾT TẮT. TỔNG QUAN KHAI PHÁ MẪU DÃY CÓ TRỌNG SỐ TRONG CƠ SỞ DỮ LIỆU DÃY. Tổng quan tình hình nghiên cứu. Khai phá mẫu dãy có trọng số trong CSDL dãy. Khai phá mẫu dãy có trọng số trong CSDL dãy với khoảng cách thời gian. Khai phá mẫu dãy lợi ích cao trong CSDL định lượng có khoảng cách thời gian 47 Kết luận Chương 1. KHAI PHÁ MẪU DÃY CÓ TRỌNG SỐ TRONG CƠ SỞ DỮ LIỆU DÃY CÓ KHOẢNG CÁCH THỜI GIAN. Thuật toán khai phá top-k mẫu dãy thường xuyên trọng số với khoảng cách thời gian (TopKWFP). Bài toán đặt ra. Ý tưởng thuật toán. Thuật toán TopKWFP. Phân tích thuật toán TopKWFP. Thử nghiệm thuật toán.78 Kết luận Chương 2. KHAI PHÁ MẪU DÃY LỢI ÍCH CAO TRONG CƠ SỞ DỮ LIỆU DÃY CÓ KHOẢNG CÁCH THỜI GIAN. Thuật toán khai phá mẫu dãy lợi ích cao có khoảng cách thời gian (UIPrefixSpan). Bài toán đặt ra. Ý tưởng thuật toán. Thuật toán UIPrefixSpan. Phân tích thuật toán UIPrefixSpan. Thử nghiệm thuật toán. Thuật toán khai phá mẫu dãy lợi ích cao có khoảng cách thời gian 1 pha (HUISP). Bài toán đặt ra. Ý tưởng thuật toán. Thuật toán HUISP. Phân tích thuật toán HUISP. Thử nghiệm thuật toán.126 Kết luận Chương 3.133 KẾT LUẬN VÀ KIẾN NGHỊ. 134 DANH MỤC CÔNG TRÌNH ĐÃ CÔNG BỐ.137 TÀI LIỆU THAM KHẢO. 138 3 DANH MỤC HÌNH VẼ Hình 1. Các vấn đề nghiên cứu của luận án.1 Ảnh hưởng của tham số k.2 Ảnh hưởng của chiến lược tối ưu lên thời gian chạy.3 Ảnh hưởng của chiến lược tối ưu lên số ứng viên tạo ra. So sánh 2 thuật toán WIPrefixSpan và TopKWFP.1 Biểu đồ phân phối giá trị lợi nhuận của 1000 mục (UIPrefixSpan).2 Thời gian chạy UIPrefixSpan.3 Bộ nhớ sử dụng UIPrefixSpan.4 Số mẫu dãy lợi ích cao UIPrefixSpan.5 Biểu đồ phân phối giá trị lợi nhuận của 1000 mục (HUISP).6 Thời gian chạy HUISP.7 Bộ nhớ sử dụng HUISP.8 Ảnh hưởng của số lượng mẫu dãy với thời gian chạy và bộ nhớ.132 4 DANH MỤC BẢNG BIỂU Bảng 1.1 Danh sách một số công trình liên quan đến luận án.3 Trọng số của các mục trong SDB.4 CSDL dãy iSDB với khoảng cách thời gian.5 Trọng số của các mục trong iSDB.6 CSDL dãy QiSDB với khoảng cách thời gian.7 Trọng số của các mục trong QiSDB.8 Bảng lợi ích QiSDB.9 Bảng chỉ mục.1 CSDL dãy iSDB với khoảng cách thời gian.2 Trọng số của các mục trong iSDB.3 CSDL chiếu của dãy <0,c>.4 Các bộ dữ liệu thực nghiệm.5 Thống kê chi tiết số lượng mẫu dãy ứng viên tạo ra.1 Cơ sở dữ liệu điều kiện với tiền tố <0,a>.2 Cơ sở dữ liệu điều kiện với tiền tố <0,a><1, b >.3 Cơ sở dữ liệu điều kiện với tiền tố <0,a><1, b ><2, a>.4 Cơ sở dữ liệu điều kiện với tiền tố <0,a><1, b ><2, ab>.5 Các mẫu dãy ứng viên ứng với tiền tố <0, a>.6 Bảng thống kê khai phá mẫu dãy lợi ích cao với khoảng cách thời gian trong QiSDB.7 Lợi ích của mẫu dãy 1 phần tử.8 Lợi ích của các dãu đầu vào.9 Bảng lợi ích của các mẫu dãy 1 phần tử.10 Bảng chỉ mục trong QiSDB.11 CSDL chiếu của <0,a> QiSDB|<0,a>.12 Bảng lợi ích của các mẫu ứng viên độ dài 2 với tiền tố <0,a>.13 CSDL chiếu của <0,a><1,b> QiSDB|<0,a><1,b>.14 Bảng lợi ích của các mục ứng viên độ dài 3 với tiền tố <0,a><1,b>.15 CSDL chiếu của <0,a><1,b><2,a> QiSDB|<0,a><1,b><2,a>.16 Bảng lợi ích của các mục ứng viên độ dài 4 với tiền tố <0,a><1,b><2,a> .17 Bảng mẫu dãy lợi ích cao tìm được với tiền tố <0,a>.18 Bảng mẫu dãy lợi ích cao với khoảng cách thời gian của QiSDB.19 Bảng thống kê số lượng mẫu dãy ứng viên và số mẫu dãy lợi ích cao của UIPrefixSpan và HUISP.130 6 DANH MỤC CÁC TỪ VIẾT TẮT Từ viết tắt Tiếng Anh Tiếng Việt CSDL Database Cơ sở dữ liệu UL Utility Level Thuật toán khai phá mẫu dãy lợi ích cao theo phương pháp Apriori US Utility Span Thuật toán khai phá lợi ích cao theo phương pháp PrefixSpan PrefixSpan Prefix-Projected Sequential Thuật toán khai phá mẫu dãy Patterns Mining Algorithm thường xuyên theo phương pháp tăng trưởng mẫu dãy TopKWFP Top-k weighted sequential Thuật toán khai phá top-k pattern mining with item interval mẫu dãy trọng số có khoảng Algorithm cách thời gian WIPrefixSpan Weighted sequential pattern Thuật toán khai phá mẫu dãy mining with item interval trọng số có khoảng cách thời Algorithm gian UIPrefixSpan High Utility Sequential Patterns Thuật toán khai phá mẫu dãy with Time Interval Algorithm lợi ích cao có khoảng cách thời gian theo phương pháp 2 pha HUISP High Utility Item Interval Thuật toán khai phá mẫu dãy Sequential Pattern Algorithm lợi ích cao có khoảng cách thời gian theo phương pháp sử dụng bảng lợi ích GSP Generalized Sequential Pattern Thuật toán khai phá mẫu dãy tổng quát SDB Sequence Database Cơ sở dữ liệu dãy iSDB Sequence Database with item Cơ sở dữ liệu dãy có khoảng interval cách thời gian QiSDB Quantitative Sequence Database Cơ sở dữ liệu dãy định lượng with item interval có khoảng cách thời gian UCI UC Irvine Machine Kho dữ liệu chuẩn UCI 7 MỞ ĐẦU 1. Tổng quan Khai phá dữ liệu được định nghĩa là quá trình trích xuất các thông tin có giá trị tiềm ẩn bên trong lượng lớn dữ liệu được lưu trữ trong các cơ sở dữ liệu, kho dữ liệu. Khai phá tập mục thường xuyên là một hướng cơ bản trong khai phá dữ liệu. Bài toán khai phá tập mục thường xuyên được Agrawal và Srikant giới thiệu trong [1] với mục đích tìm ra các mục thường xuất hiện cùng nhau trong CSDL giao dịch. Ví dụ như một tập mục thường xuyên {Máy in; Giấy} thể hiện rằng các sản phẩm này thường được mua cùng nhau. Các tập mục thường xuyên có dạng đơn giản và dễ hiểu đối với con người nhưng lại rất hữu ích trong việc ra quyết định. Từ khi ra đời, lĩnh vực khai phá tập mục thường xuyên đã thu hút rất nhiều nhà nghiên cứu. Rất nhiều công trình đã và đang tiếp tục được công bố nhằm phát triển các kỹ thuật khai phá tập mục thường xuyên cũng như mở rộng bài toán khai phá tập mục thường xuyên. Tuy nhiên, trong bài toán này, thứ tự của các mục lại bị bỏ qua. Điều này có thể dẫn tới việc không tìm được các tập mục hữu ích hoặc các tập mục được tìm thấy không thực sự hữu ích. Khai phá các mẫu dãy tiềm năng và và hữu ích trong các cơ sở dữ liệu dãy là một trong những nội dung quan trọng trong khai phá dữ liệu cơ bản. Những năm gần đây, các xu hướng nghiên cứu các vấn đề khai phá dữ liệu là đề xuất các thuật toán để khai phá các mẫu dãy trong các loại CSDL dữ liệu dãy. Một trong những nội dung khai thác dữ liệu phổ biến nhất trên dãy là khai phá các mẫu dãy tuần tự. Để có thể giải quyết vấn đề này, bài toán khai phá mẫu dãy thường xuyên đã được Agrawal và Srikant đề xuất trong [2]. Nội dung theo hướng này bao gồm các việc khai phá các mẫu dãy tiềm năng, hữu ích trong một tập hợp các dãy dữ liệu, trong đó mức độ hữu ích của một dãy con có thể được tính toán và xác định theo nhiều tiêu chí khác nhau như tần suất xuất hiện, độ dài, trọng số, lợi ích của dãy và khoảng thời gian xuất hiện giữa các dãy. Khai phá các mẫu dãy có rất nhiều ứng dụng trong thực tiễn hiện nay vì dữ liệu thu thập được cơ bản đã được mã hóa thành các dãy dữ liệu trong nhiều lĩnh vực như tin sinh học, đào tạo trực 8 tuyến, phân tích thị trường, phân tích mua bán, phân tích văn bản và phân tích thông tin nhấp chuột trên trang web. Mối quan tâm đến các kỹ thuật khai phá mẫu dãy đến từ khả năng phát hiện ra các mẫu dãy có thể ẩn bên trong cơ sở dữ liệu dãy lớn và con người có thể giải thích được và rất hữu ích cho việc hiểu dữ liệu và ra các quyết định phù hợp. Ví dụ, một mẫu dãy {Sữa, bánh quy} có thể được sử dụng để hiểu hành vi của khách hàng và đưa ra các quyết định chiến lược để tăng doanh số bán hàng, chẳng hạn như đồng quảng cáo sản phẩm và giảm giá. Một số kỹ thuật khai thác theo mẫu dãy như kỹ thuật khai thác tập mục phổ biến thường xuyên [1], [3], [4], [5], [6], [7] và khai phá các luật kết hợp [1] nhằm phân tích dữ liệu, trong đó thứ tự tuần tự của các sự kiện xuất hiện các mục không được tính đến.
Luận Án Tiến Sĩ: Khai Phá Mẫu Dãy Có Trọng Số Trong Cơ Sở Dữ Liệu Dãy
Luận án tiến sĩ ngành máy tính nghiên cứu khai phá mẫu dãy có trọng số trong cơ sở dữ liệu dãy, góp phần nâng cao hiệu quả phân tích dữ liệu.
Trường đại học
Học viện Khoa học và Công nghệChuyên ngành
Hệ thống thông tinNgười đăng
Ẩn danhThể loại
luận ánPhí lưu trữ
45 PointMục lục chi tiết
THÔNG TIN CHI TIẾT
Tác giả: Trần Huy Dương
Người hướng dẫn: TS. Nguyễn Trường Thắng
Trường học: Học viện Khoa học và Công nghệ
Chuyên ngành: Hệ thống thông tin
Đề tài: Khai Phá Mẫu Dãy Có Trọng Số Trong Cơ Sở Dữ Liệu Dãy
Loại tài liệu: luận án
Năm xuất bản: 2021
Địa điểm: Hà Nội
Trích đoạn nội dung tài liệu
Nội dung được bảo vệ bản quyền — Tải xuống đầy đủ