Luận án Tiến sĩ Máy tính: Khai phá mẫu dãy có trọng số trong cơ sở dữ liệu dãy

Chia sẻ: Buctranhdo Buctranhdo | Ngày: | Loại File: PDF | Số trang:151

Thêm vào BST

Báo xấu

33
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục tiêu của luận án là đề xuất giải pháp khai phá các mẫu dãy có trọng số có khoảng cách thời gian giữa các dãy trong các CSDL dãy có khoảng cách thời gian và CSDL dãy định lượng có khoảng cách thời gian.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án Tiến sĩ Máy tính: Khai phá mẫu dãy có trọng số trong cơ sở dữ liệu dãy

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. TS. Nguyễn Trường Thắng 2. GS.TS. 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.TS.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 ..........................................................................6 MỞ ĐẦU ....................................................................................................................7 CHƯƠNG 1. TỔNG QUAN KHAI PHÁ MẪU DÃY CÓ TRỌNG SỐ TRONG CƠ SỞ DỮ LIỆU DÃY ............................................................................................15 1.1. Tổng quan tình hình nghiên cứu ..................................................................15 1.2. Khai phá mẫu dãy có trọng số trong CSDL dãy..........................................25 1.3. Khai phá mẫu dãy có trọng số trong CSDL dãy với khoảng cách thời gian ... .....................................................................................................................32 1.4. 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 ....................................................................................................61 CHƯƠNG 2. 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 .....................................................63 2.1. Giới thiệu .....................................................................................................63 2.2. 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) ...............................................................................................65 2.2.1. Bài toán đặt ra ..............................................................................................65 2.2.2. Ý tưởng thuật toán .......................................................................................66 2.2.3. Thuật toán TopKWFP .................................................................................67 2.2.4. Phân tích thuật toán TopKWFP ...................................................................70 2.2.5. Thử nghiệm thuật toán .................................................................................78 Kết luận Chương 2 ....................................................................................................86 CHƯƠNG 3. 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 ...............................................................87 3.1. Giới thiệu .....................................................................................................87 3.2. Thuật toán khai phá mẫu dãy lợi ích cao có khoảng cách thời gian (UIPrefixSpan) ..........................................................................................................89 3.2.1. Bài toán đặt ra ..............................................................................................89 3.2.2. Ý tưởng thuật toán .......................................................................................90 3.2.3. Thuật toán UIPrefixSpan .............................................................................90 3.2.4. Phân tích thuật toán UIPrefixSpan ..............................................................92
2 3.2.5. Thử nghiệm thuật toán ...............................................................................103 3.3. 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)...................................................................................................................109 3.3.1. Bài toán đặt ra ............................................................................................109 3.3.2. Ý tưởng thuật toán .....................................................................................110 3.3.3. Thuật toán HUISP .....................................................................................112 3.3.4. Phân tích thuật toán HUISP .......................................................................114 3.3.5. 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.1. Các vấn đề nghiên cứu của luận án ...........................................................25 Hình 2.1 Ảnh hưởng của tham số k ..........................................................................80 Hình 2.2 Ảnh hưởng của chiến lược tối ưu lên thời gian chạy .................................81 Hình 2.3 Ảnh hưởng của chiến lược tối ưu lên số ứng viên tạo ra ...........................82 Hình 2.4. So sánh 2 thuật toán WIPrefixSpan và TopKWFP ...................................85 Hình 3.1 Biểu đồ phân phối giá trị lợi nhuận của 1000 mục (UIPrefixSpan) ........104 Hình 3.2 Thời gian chạy UIPrefixSpan...................................................................106 Hình 3.3 Bộ nhớ sử dụng UIPrefixSpan .................................................................107 Hình 3.4 Số mẫu dãy lợi ích cao UIPrefixSpan ......................................................109 Hình 3.5 Biểu đồ phân phối giá trị lợi nhuận của 1000 mục (HUISP) ...................127 Hình 3.6 Thời gian chạy HUISP .............................................................................128 Hình 3.7 Bộ nhớ sử dụng HUISP ............................................................................129 Hình 3.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 ..................................22 Bảng 1.2 CSDL dãy SDB .........................................................................................26 Bảng 1.3 Trọng số của các mục trong SDB ..............................................................26 Bảng 1.4 CSDL dãy iSDB với khoảng cách thời gian ..............................................33 Bảng 1.5 Trọng số của các mục trong iSDB .............................................................34 Bảng 1.6 CSDL dãy QiSDB với khoảng cách thời gian ...........................................48 Bảng 1.7 Trọng số của các mục trong QiSDB ..........................................................49 Bảng 1.8 Bảng lợi ích QiSDB ...................................................................................56 Bảng 1.9 Bảng chỉ mục .............................................................................................56 Bảng 2.1 CSDL dãy iSDB với khoảng cách thời gian ..............................................75 Bảng 2.2 Trọng số của các mục trong iSDB .............................................................75 Bảng 2.3 CSDL chiếu của dãy ........................................................................77 Bảng 2.4 Các bộ dữ liệu thực nghiệm .......................................................................79 Bảng 2.5 Thống kê chi tiết số lượng mẫu dãy ứng viên tạo ra .................................83 Bảng 3.1 Cơ sở dữ liệu điều kiện với tiền tố ..................................................97 Bảng 3.2 Cơ sở dữ liệu điều kiện với tiền tố .......................................97 Bảng 3.3 Cơ sở dữ liệu điều kiện với tiền tố ............................98 Bảng 3.4 Cơ sở dữ liệu điều kiện với tiền tố ..........................98 Bảng 3.5 Các mẫu dãy ứng viên ứng với tiền tố ...........................................99 Bảng 3.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. ....................................................................................................................100 Bảng 3.7 Lợi ích của mẫu dãy 1 phần tử ................................................................118
5 Bảng 3.8 Lợi ích của các dãu đầu vào ....................................................................119 Bảng 3.9 Bảng lợi ích của các mẫu dãy 1 phần tử ..................................................119 Bảng 3.10 Bảng chỉ mục trong QiSDB ...................................................................120 Bảng 3.11 CSDL chiếu của QiSDB|....................................................121 Bảng 3.12 Bảng lợi ích của các mẫu ứng viên độ dài 2 với tiền tố ..............122 Bảng 3.13 CSDL chiếu của QiSDB| ................................122 Bảng 3.14 Bảng lợi ích của các mục ứng viên độ dài 3 với tiền tố .....123 Bảng 3.15 CSDL chiếu của QiSDB| ..............123 Bảng 3.16 Bảng lợi ích của các mục ứng viên độ dài 4 với tiền tố .................................................................................................................................124 Bảng 3.17 Bảng mẫu dãy lợi ích cao tìm được với tiền tố ...........................124 Bảng 3.18 Bảng mẫu dãy lợi ích cao với khoảng cách thời gian của QiSDB ........125 Bảng 3.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 mẫu pattern mining with item interval dãy trọng số có khoảng cách Algorithm 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. Do đó, nếu các kỹ thuật khai phá mẫu dãy như vậy áp dụng trên các dữ liệu có thông tin về thời gian hoặc thứ tự tuần tự thì các thông tin này sẽ bị bỏ qua. Điều này có thể dẫn đến việc không khai phá ra được các mẫu dãy quan trọng trong dữ liệu hoặc tìm kiếm các mẫu có thể không hữu ích vì chúng bỏ qua mối quan hệ tuần tự giữa các sự kiện hoặc các phần tử của dữ liệu. Trong nhiều lĩnh vực, thứ tự của các sự kiện là đặc biệt quan trọng. Ví dụ, để phân tích các văn bản, cần phải xem xét thứ tự của các từ trong câu [8]. Trong phát hiện xâm nhập mạng, thứ tự của các sự kiện xảy ra rất quan trọng [9]. Một số phương pháp chính phân tích và khai phá dữ liệu mẫu dãy tuần tự [2], [10], [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23] trong các phương pháp này bao gồm việc khám phá các dãy con tiềm năng và có ý nghĩa trong một tập hợp các dãy, trong đó mức độ tiềm năng của một dãy con có thể được đo lường theo các tiêu chí khác nhau như tần suất xuất hiện, độ dài và lợi nhuận của dãy, khoảng cách thời gian. Khai phá mẫu dãy tuần tự có nhiều ứng dụng trong đời thực do dữ liệu được mã hóa tự nhiên dưới dạng dãy ký hiệu trong nhiều lĩnh vực như tin sinh học [24], e-learning [25], [26], phân tích thị trường [10], phân tích văn bản [8], tiết kiệm năng lượng trong smarthomes [27], phân tích luồng nhấp chuột trên các trang web [28]. Hơn nữa, khai phá các mẫu dãy cũng có thể được áp dụng cho chuỗi thời gian (ví dụ: dữ liệu cổ phiếu), khi việc tùy chỉnh các tham số được thực hiện như một bước tiền xử lý [29].
9 Thông thường, khai phá mẫu dãy thường xuyên được khai phá trong bài toán mua sắm thực hiện như ví dụ sau: một dãy dữ liệu tương đương với tình huống khi khách hàng mua mặt hàng b sau khi đã mua mặt hàng a và b, sau đó họ mua tiếp mặt hàng b,c sau khi mua mặt hàng b. Tuy nhiên, người quản lý bán hàng không biết được thời gian mà khách hàng đã mua các sản phẩm trên nếu chỉ thực hiện khai phá mẫu dãy thường xuyên mà không có thêm các thông tin mở rộng khác. Trong thực tế, khoảng cách thời gian giữa các thành phần trong dãy cũng đóng vai trò rất quan trọng. Dãy với khoảng cách thời gian là 1 ngày sẽ có ý nghĩa hơn rất nhiều dãy mà có khoảng cách là 1 năm. Cũng với ví dụ trên, một dãy dữ liệu tương đương với tình huống khách hàng mua mặt hàng a và b, sau đó 1 ngày khách hàng mua mặt hàng b, và sau 30 ngày tiếp theo khách hàng mua mặt hàng b và c. Khi đó thông tin mở rộng của khai phá dãy có khoảng cách thời gian có ý nghĩa cho phép người quản lý bán hàng phân tích xem sau khoảng thời gian bao lâu, khách hàng sẽ mua các mặt hàng tiếp theo. Mặt khác, các giải thuật khai phá mẫu dãy sử dụng một ngưỡng hỗ trợ nhằm thu nhỏ không gian tìm kiếm các mẫu dãy thường xuyên. Tuy nhiên, sau khi có mẫu dãy thường xuyên, không có cách nào để điều chỉnh số các dãy thường xuyên thông qua phản hồi của người sử dụng, ngoại trừ sự thay đổi ngưỡng hỗ trợ tối thiểu. Một trong những hạn chế chính của phương pháp tiếp cận truyền thống các các thuật toán khai phá dãy thường xuyên là các mục trong dãy đều có giá trị như nhau, tuy nhiên trong thực tế, các mục lại có các mức độ quan trọng khác nhau. Với ví dụ trên, với một dãy dữ liệu có thông tin khoảng cách thời gian , việc người sử dụng đưa thêm các giá trị trọng số của từng mục a, b, c khác nhau phản ánh mức độ quan trọng của mục dữ liệu trong dãy đó, bởi vì nếu mục a là mặt hàng máy in (có giá trị cao, thông thường có số lượng mua ít) và mục b là mặt hàng giấy in (có giá trị ít hơn, thông thường có số lượng mua nhiều) và mục c là mặt hàng hộp mực in (có giá trị trung bình, có số lượng mua trung bình) thì việc đưa trọng số của a (máy in) cao hơn trọng số của c (hộp mực in) và trọng số của b (giấy in) cho phép người sử dụng cân bằng được độ hỗ trợ (tần suất mua) và trọng số (mức độ quan trọng) của các mục (mặt hàng) đó.
10 Năm 1995, Agrawal và Srikant phát triển bài toán khai phá mẫu dãy thường xuyên và đề nghị thuật toán AprioriAll [2], một thuật toán dựa trên thuật toán Apriori để khai thác mẫu dãy thường xuyên. Cũng giống như Apriori, AproiriAll duyệt CSDL nhiều lần và dựa vào phương pháp sinh ứng viên nên tốn thời gian khai phá. Hiện nay trên thế giới có nhiều nhóm tác giả nghiên cứu đề xuất các thuật toán với các phương pháp tiếp cận khai phá mẫu dãy khác nhau như GSP [10], Spade [11], Spam [30], PrefixSpan [31] Các thuật toán khai phá mẫu dãy nêu ở trên không quan tâm tới mức độ quan trọng của từng mục dữ liệu trong dãy (trọng số của dãy). Tuy nhiên trên thực tế, mỗi dãy dữ liệu đều có độ quan trọng khác nhau. Một số công trình đã nghiên cứu về trọng số, đưa các giá trị trọng số khác nhau đến các mục trong dãy như MWSP [32], Wspan [33], WSPM [34] Tuy nhiên trên thực tế, mỗi dãy dữ liệu xuất hiện đều có thông tin về khoảng cách thời gian giữa các dãy. Có 2 hướng tiếp cận chính được các nhà nghiên cứu đề xuất trong khai phá mẫu dãy có khoảng cách thời gian: tiếp cận dựa trên ràng buộc cSpade [35], Prefix-growth [14] và tiếp cận dựa trên việc mở rộng cơ sở dữ liệu dãy [36] [37] [38] [39] [40] [41]. Một số công trình tiêu biểu như cSpade [35], Prefix- growth [14], I-PrefixSpan [38] [39], TGSP [41], TiWS [36], Nhóm tác giả Y. Hirate và cộng sự [37]. Tuy nhiên, đến nay chưa có nhiều các nghiên cứu về khai phá mẫu dãy có trọng số trong CSDL dãy có khoảng cách thời gian trong đó quan tâm đến cả đến trọng số của mỗi mục trong dãy dữ liệu và khoảng cách thời gian giữa các dãy. Việc phát hiện top-k mẫu dãy thường xuyên trên CSDL dãy được thực hiện bằng việc nghiên cứu giải quyết của thuật toán TKS [21] do Fournier-Viger và cộng sự đề xuất thực hiện khai phá top-k mẫu dãy thường xuyên trong CSDL dãy sử dụng biểu diễn CSDL theo chiều dọc và nghiên cứu Dương và cộng sự [40] đã đề xuất thuật toán khai phá mẫu dãy thường xuyên trọng số chuẩn hóa với khoảng cách thời gian trong CSDL dãy có khoảng cách thời gian và thuật toán WIPrefixSpan để khai phá mẫu dãy này. Nhằm tiếp tục phát triển dựa trên các kết quả giải thuật TKS [21] và
11 WIPrefixSpan [40] trong việc khai phá mẫu dãy trọng số trong CSDL dãy có khoảng cách thời gian, NCS đề xuất nội dung nghiên cứu và phát triển thuật toán trong Nội dung thứ 1. Nội dung thứ 1 trong việc xác định vấn đề nghiên cứu của luận án là phát triển và đề xuất 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 trong đó quan tâm đến cả đến trọng số của mỗi mục trong dãy dữ liệu và khoảng cách thời gian giữa các dãy trong CSDL dãy có khoảng cách thời gian và số lượng top-k mẫu dãy khai phá được. Bài toán khai phá mẫu dãy lợi ích cao là một mở rộng của bài toán khai phá mẫu dãy có trọng số. Trong khai phá mẫu dãy lợi ích cao, các mục có thể có các giá trị khác nhau trong các lần xuất hiện khác nhau. Ví dụ, xét một dãy dữ liệu như sau , mẫu dãy a nhận 2 giá trị khác nhau (lần lượt là 3 và 2) trong 2 lần xuất hiện thể hiện mục a được mua với số lượng 3 và 2 trong 2 lần giao dịch liên tiếp. CSDL dãy có chứa các giá trị số lượng như vậy được gọi là CSDL dãy định lượng. Một số công bố tiêu biểu như UL, US [42], Uspan [43], PHUS [44], HuspExt [45], HUS-Span [46], HUSPM [47] . Tuy nhiên, đến nay chưa có nhiều các nghiên cứu về khai phá mẫu dãy lợi ích cao trong CSDL dãy định lượng có khoảng cách thời gian trong đó quan tâm đến cả đến trọng số của mỗi mục trong dãy dữ liệu, giá trị định lượng của các mục xuất hiện và khoảng cách thời gian giữa các dãy trong CSDL dãy định lượng có khoảng cách thời gian. Năm 2018, Phương và cộng sự [48] đề xuất thuật toán FSPFTIM phát hiện mẫu dãy cổ điển mờ với khoảng cách thời gian mờ trong các CSDL định lượng bằng cách sử dụng lý thuyết mờ đề chuyển đổi các thuộc tính định lượng, khoảng cách thời gian thành các khái niệm mờ và thực hiện khai phá giống như thuật toán Apriori, từ đó tìm ra các mẫu dãy mờ với khoảng cách thời gian mờ. Nhằm phát triển các giải thuật khai phá mẫu dãy lợi ích cao với khoảng cách thời gian trong CSDL dãy định lượng có khoảng cách thời gian, NCS đề xuất nội dung nghiên cứu và phát triển thuật toán trong Nội dung thứ 2.
12 Nội dung thứ 2 trong việc xác định vấn đề nghiên cứu của luận án là phát triển và đề xuất các thuật toán khai phá mẫu dãy lợi ích cao trong CSDL dãy định lượng có khoảng cách thời gian trong đó quan tâm cả đến trọng số của mỗi mục trong dãy dữ liệu, giá trị định lượng của mỗi mục dữ liệu và khoảng cách thời gian giữa các dãy trong CSDL dãy định lượng có khoảng cách thời gian. Luận án này nhằm giải quyết 02 nội dung được xác định ở trên. Việc nghiên cứu giải quyết những vấn đề đó là thực sự cần thiết không chỉ ở phương diện phát triển lý thuyết mà cả ở phương diện ứng dụng thực tế. Đó là động lực để tác giả luận án thực hiện nghiên cứu đề tài “Khai phá mẫu dãy có trọng số trong Cơ sở dữ liệu dãy”. Cụ thể luận án đề xuất và giải quyết các vấn đề về khai phá các mẫu dãy thường xuyên có tính đến trọng số của từng mục dữ liệu, khoảng cách thời gian giữa các dãy và giá trị định lượng của các mục dữ liệu xuất hiện trọng dãy. 2. Mục tiêu của luận án Mục tiêu của luận án là đề xuất giải pháp khai phá các mẫu dãy có trọng số có khoảng cách thời gian giữa các dãy trong các CSDL dãy có khoảng cách thời gian và CSDL dãy định lượng có khoảng cách thời gian. Cụ thể luận án tập trung đề xuất các giải pháp nhằm:  Phát hiện các mẫu dãy có trọng số trong các CSDL dãy khoảng cách thời gian. Các mẫu dãy tìm được khi đó được gọi là mẫu dãy thường xuyên trọng số với khoảng cách thời gian.  Phát hiện các mẫu dãy có trọng số trong các CSDL dãy định lượng có khoảng cách thời gian. Các mẫu dãy tìm được khi đó được gọi là mẫu dãy thường xuyên lợi ích cao với khoảng cách thời gian. NCS tập trung vào nghiên cứu đề xuất các thuật toán mới để khai phá các mẫu mẫu dãy thường xuyên; chứng minh tính đúng đắn và tính đầy đủ, phân tích độ phức tạp tính toán của các thuật toán; thử nghiệm và phân tích ý nghĩa của mẫu dãy thường xuyên khai phá được. 3. Đối tượng nghiên cứu
13 Dữ liệu có giá trị trọng số trong Cơ sở dữ liệu dãy có khoảng cách thời gian. Dữ liệu có giá trị trọng số trong Cơ sở dữ liệu dãy định lượng có khoảng cách thời gian. Các thuật toán khai phá các mẫu mẫu dãy có trọng số, có tính đến khoảng cách thời gian trong các CSDL dãy có khoảng cách thời gian và CSDL dãy định lượng có khoảng cách thời gian. 4. Phạm vi nghiên cứu Luận án nghiên cứu các mẫu dãy, trọng số của các mục trong dãy, khoảng cách thời gian giữa các dãy, các CSDL dãy có khoảng cách thời gian và CSDL dãy định lượng có khoảng cách thời gian. Các nghiên cứu, thuật toán và phương pháp khai phá mẫu dãy hiện nay trên CSDL dãy, CSDL dãy định lượng có các yếu tố khoảng cách thời gian, trọng số, lợi ích cao. 5. Phương pháp nghiên cứu Phương pháp nghiên cứu của luận án là nghiên cứu lý thuyết và nghiên cứu thực nghiệm. Về nghiên cứu lý thuyết: các định lý, mệnh đề trong luận án được chứng minh chặt chẽ dựa vào các kiến thức cơ bản và các kết quả nghiên cứu đã công bố. Về nghiên cứu thực nghiệm: luận án thực hiện cài đặt các thuật toán, chạy thử nghiệm thuật toán với các bộ số liệu lấy từ kho dữ liệu UCI, so sánh và đánh giá kết quả thực nghiệm so với kết quả nghiên cứu lý thuyết, từ đó kết luận tính đúng đắn của kết quả nghiên cứu. Về nghiên cứu đánh giá độ phức tạp thuật toán được sử dụng để thiết kế thuật toán giải quyết bài toán cụ thể được đặt ra trong luận án và ước lượng độ phức tạp tính toán của các thuật toán này và việc đánh giá tính hiệu quả các thuật toán dựa vào các kết quả thực nghiệm. 6. Các đóng góp chính của luận án Những đóng góp chính của luận án là đề xuất và giải quyết các vấn đề sau:
14  Đề xuất 01 thuật toán khai phá top-k mẫu dãy có tính đến trọng số của các mục và khoảng cách thời gian trong các CSDL dãy có khoảng cách thời gian. Kết quả công trình được đăng trong kết quả tại [CT1].  Đề xuất 02 thuật toán khai phá mẫu dãy lợi ích cao có tính đến trọng số của các mục, giá trị định lượng của mỗi mục và khoảng cách thời gian trong các CSDL dãy định lượng có khoảng cách thời gian. Kết quả công trình được đăng trong kết quả tại [CT2], [CT3], [CT4], [CT5] 7. Bố cục luận án Luận án gồm phần mở đầu, 03 chương nội dung và phần kết luận:  Phần mở đầu: Trình bày tổng quan của luận án; mục tiêu, đối tượng, phạm vi nghiên cứu; phương pháp nghiên cứu; những đóng góp chính và cấu trúc của luận án.  Chương 1: Tổng quan tình hình nghiên cứu và các vấn đề liên quan trong khai phá mẫu dãy có trọng số trong CSDL dãy, trong CSDL dãy có khoảng cách thời gian và trong CSDL dãy định lượng có khoảng cách thời gian. Chương này trình bày các khái niệm, định nghĩa và các phương pháp khai phá các mẫu dãy liên quan của các nghiên cứu trước đó.  Chương 2: Khai phá mẫu dãy có trọng số trong CSDL dãy có khoảng cách thời gian. Chương này đặt vấn đề và đề xuất thuật toán khai phá top-k mẫu dãy thường xuyên trọng số trong CSDL dãy có khoảng cách thời gian. Tính đúng đắn và đầy đủ của thuật toán, việc thực nghiệm thuật toán trên các bộ dữ liệu thực và so sánh với các nghiên cứu trước đó.  Chương 3: Khai phá mẫu dãy lợi ích cao trong CSDL dãy định lượng có khoảng cách thời gian. Chương này này đặt vấn đề và đề xuất thuật toán khai phá mẫu dãy lợi ích cao trong CSDL dãy định lượng có khoảng cách thời gian. Tính đúng đắn và đầy đủ của thuật toán, việc thực nghiệm thuật toán trên các bộ dữ liệu thực và so sánh với các nghiên cứu trước đó.  Phần kết luận: Trình bày một số kết luận những đóng góp của luận án, hướng phát triển và những vấn đề quan tâm của NCS.
15 CHƯƠNG 1. TỔNG QUAN KHAI PHÁ MẪU DÃY CÓ TRỌNG SỐ TRONG CƠ SỞ DỮ LIỆU DÃY Chương này trình bày tổng quan tình hình nghiên cứu và những định nghĩa cơ bản những vấn đề khai phá các mẫu dãy có trọng số trong các CSDL dãy, mẫu dãy có trọng số trong CSDL dãy có khoảng cách thời gian, mẫu dãy lợi ích cao trong CSDL dãy định lượng có khoảng cách thời gian. Chương này cũng chỉ ra các khoảng trống chưa được giải quyết để từ đó xác định vấn đề nghiên cứu của luận án. 1.1. Tổng quan tình hình nghiên cứu Khai phá mẫu dãy là nhiệm vụ thực hiện tìm kiếm tất cả các mẫu dãy con thường xuyên trong cơ sở dữ liệu dãy. Một dãy s được cho là một mẫu dãy thường xuyên nếu và chỉ khi độ hỗ trợ sup (s) ≥ minsup, vì ngưỡng minsup do người dùng đặt [10]. Nhiệm vụ khai phá mẫu dãy là một bài toán liệt kê nhằm mục đích liệt kê tất cả các mẫu dãy con có độ hỗ trợ không thấp hơn ngưỡng hỗ trợ tối thiểu do người dùng đặt ra. Do đó, luôn có một kết quả đúng duy nhất cho một bài toán khai phá mẫu dãy thường xuyên. Để thực hiện khai phá các mẫu dãy thường xuyên, cách tiếp cận đơn giản là tính toán hỗ trợ của tất cả các mẫu dãy con có thể có trong cơ sở dữ liệu dãy để sau đó chỉ đưa ra những mẫu dãy đáp ứng ràng buộc hỗ trợ tối thiểu do người dùng đặt ra. Tuy nhiên, với cách tiếp cận như vậy sẽ ít hiệu quả vì thông thường số lượng dãy con tìm được có thể rất lớn. Ví dụ như một dãy chứa q mục dữ liệu trong một CSDL dãy có thể có tối đa 2q-1 các mẫu dãy con riêng biệt. Do đó, để giải quyết vấn đề khai phá các mẫu dãy con đối với hầu hết các cơ sở dữ liệu dãy có trong thực tế là phức tạp và khó khăn. Vì vậy, các nghiên cứu và phát triển các thuật toán hiệu quả khai phá mẫu dãy cần hạn chế phải khai phá không gian tìm kiếm của tất cả các dãy con có thể có trong CSDL dãy. Hiện nay có nhiều thuật toán đã được đề xuất để khai phá các mẫu dãy trong cơ sở dữ liệu dãy. Một số thuật toán phổ biến nhất là GSP [10], Spade [11], PrefixSpan [31], Spam [30], Lapin [18], CM-Spam và CM-Spade [17]. Tất cả các thuật toán khai thác mẫu dãy này lấy đầu vào là cơ sở dữ liệu dãy và ngưỡng hỗ trợ tối thiểu (do người dùng chọn) và trả kết quả là tập hợp các mẫu dãy thường xuyên và luôn chỉ có một
16 kết quả đúng cho nhiệm vụ khai phá mẫu dãy (đối với cơ sở dữ liệu dãy và giá trị ngưỡng). Do đó, tất cả các thuật toán khai phá mẫu dãy luôn trả về cùng một kết quả là tập hợp các mẫu dãy nếu chúng được chạy với cùng một tham số trên cùng một cơ sở dữ liệu. Sự khác biệt giữa các thuật toán khác nhau không phải là đầu ra của chúng, mà là cách mỗi thuật toán thực hiện khai phá ra các mẫu dãy. Các thuật toán khác nhau sử dụng các chiến lược và cấu trúc dữ liệu khác nhau để tìm kiếm và khai phá các mẫu dãy một cách hiệu quả, một số thuật toán hiệu quả hơn những thuật toán khác trong cùng mục đích khai phá mẫu dãy. Hiện nay, các thuật toán khai phá mẫu dãy có thể được phân thành 02 loại là thuật toán tìm kiếm theo chiều sâu hoặc thuật toán tìm kiếm theo chiều rộng. AprioriAll là thuật toán khai phá mẫu dãy đầu tiên được đề xuất [2]. Các tác giả của AprioriAll sau đó đã đề xuất một phiên bản cải tiến được gọi là GSP [10]. Các thuật toán AprioriAll và GSP được đề xuất theo phương pháp của thuật toán Apriori nhằm khai phá tập mục thường xuyên [1]. Đối với các thuật toán tìm kiếm theo chiều rộng như GSP tiến hành như sau. Đầu tiên duyệt cơ sở dữ liệu để tìm mẫu dãy thường xuyên có độ dài 1 (các mẫu dãy chứa một mục). Sau đó, sẽ thực hiện sinh ra mẫu dãy có độ dài 2 bằng cách thực hiện phần ghép cặp của các mẫu dãy độ dài 1. Sau đó mẫu dãy có độ dài 3 tiếp tục được tạo ra từ việc ghép cặp các mẫu dãy có độ dài 2 .v.v. cho đến khi không còn mẫu dãy nào có thể được tạo ra nữa. Có thể thấy rằng với phương pháp tìm kiếm theo chiều rộng này thì không gian tìm kiếm có thể rất lớn. Giả sử rằng dãy dài nhất trong cơ sở dữ liệu chứa m mục thì các thuật toán khai phá mẫu dãy thực hiện tìm kiếm theo chiều rộng trong trường hợp xấu nhất là tất cả các mẫu dãy có thể chứa m mục hoặc ít hơn. Nếu một cơ sở dữ liệu dãy chứa m mục, thì các mẫu dãy phải khai phá có thể thể lớn hơn 2m. Trong những năm gần đây, nhiều thuật toán đã được chứng minh là hiệu quả hơn GSP do GSP thực hiện nhiều lần duyệt cơ sở dữ liệu để tính toán sự hỗ trợ của các mẫu dãy ứng viên. Điều này có thể rất tốn kém tài nguyên đối với các cơ sở dữ liệu lớn, ngay cả khi một số tối ưu hóa có thể được thực hiện để giảm chi phí đó (ví dụ: bằng cách sắp xếp các dãy theo kích thước của chúng để tránh so sánh các mẫu dài với các dãy ngắn). Mặt khác GSP có thể tạo ra các mẫu không tồn tại trong cơ sở