Tóm tắt 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ẻ: _ _ | Ngày: | Loại File: PDF | Số trang:26

Thêm vào BST

Báo xấu

18
lượt xem 2
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. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

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

Lưu

Nội dung Text: Tóm tắt 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 Chuyên ngành: Hệ thống thông tin Mã số: 62 48 01 04 TÓM TẮT LUẬN ÁN TIẾN SỸ NGÀNH MÁY TÍNH Hà Nội – 2021
Công trình được hoàn thành tại: Học viện Khoa học và Công nghệ - Viện Hàn lâm Khoa học và Công nghệ Việt Nam Người hướng dẫn khoa học 1: TS. Nguyễn Trường Thắng Người hướng dẫn khoa học 2: GS.TS. Vũ Đức Thi Phản biện 1: … Phản biện 2: … Phản biện 3: …. Luận án sẽ được bảo vệ trước Hội đồng chấm luận án tiến sĩ, họp tại Học viện Khoa học và Công nghệ - Viện Hàn lâm Khoa học và Công nghệ Việt Nam vào hồi … giờ ..’, ngày … tháng … năm 201…. Có thể tìm hiểu luận án tại: - Thư viện Học viện Khoa học và Công nghệ - Thư viện Quốc gia Việt Nam
1 MỞ ĐẦU 1. Tổng quan Khai phá các mẫu dãy thường xuyên là một trong những vấn đề quan trọng và được nhiều học giả nghiên cứu trong lĩnh vực khai phá dữ liệu. Trong nhiều lĩnh vực như khai phá văn bản, phân tích trình tự gen, chống xâm nhập mạng trái phép dựa trên phân tích nhật ký truy cập... thì thứ tự của các mục đóng vai trò rất quan trọng. Để 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]. Các mẫu dãy thường xuyên không chỉ thể hiện số lần xuất hiện của các phần tử trong nó mà còn thể hiện được thứ tự của các phần tử đó. Khai phá mẫu dãy thường xuyên được ứng dụng trong nhiều lĩnh vực như phân tích hành vi mua sắm, phân tích các mẫu truy cập web, phân tích thảm họa tự nhiên, phân tích sự hình thành các chuỗi protein... Thông thường, khai phá mẫu dãy thường xuyên cổ điển 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 khi đó, việc mở rộng các thông tin của dãy dữ liệu rất đa dạng như đưa thêm các thông tin về trọng số của các mục trong dãy, thông tin về định lượng của các mục trong dãy, thông tin về khoảng cách thời gian giữa các thành phần trong dãy … Đối với các CSDL dãy có yếu tố thời gian tức là có thêm thông tin về khoảng cách thời gian xuất hiện của các dãy dữ liệu cho phép phân tích xem sau khoảng thời gian bao lâu thì các mẫu dãy sẽ xuất hiện. Các nghiên cứu đến nay đều tập trung phát hiện các mẫu dãy có khoảng cách thời gian xảy ra giữa các thành phần trong các CSDL dãy có khoảng cách thời gian, ở đó khoảng cách thời gian là giá trị số được xác định rõ ràng. Các thuật toán khai phá mẫu dãy cổ điển thông thường 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ũng như số lượng dữ liệu của từng mục dữ liệu trong dãy (định lượng) . Tuy nhiên trên thực tế, mỗi dãy dữ liệu đều có độ quan trọng khác nhau bao gồm cả giá trị lợi ích trong (định lượng) và lợi ích ngoài (trọng số) của các dãy dữ liệu trong CSDL. Đế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. Đồng thời cũng chưa có nhiều 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. Đó là lý do đề xuất luận án “Khai phá mẫu dãy có trọng số trong Cơ sở dữ liệu dãy”. Luận án đề xuất và giải quyết vấn đề về khai phá mẫu dãy thường xuyên trọng số trong CSDL dãy có khoảng cách thời gian 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. 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ế.
2 2. Mục tiêu và phạm vi nghiên cứ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 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. Phương pháp 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. 4. Các đóng góp 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: • Đề 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]. 5. 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 định nghĩa về 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 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 nêu vấn đề và đề xuất 01 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 đó.
3 • 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êu đặt vấn đề và đề xuất 02 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. 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 và những định nghĩa cơ bản những vấn đề khai phá các mẫu dãy trong CSLD dãy, mẫu dãy có trọng số trong CSDL dãy, mẫu dãy trong CSDL dãy định lượng và mẫu dãy trong CSDL dãy 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. Khai phá mẫu dãy trong các CSDL dãy CSDL dãy SDB: Gọi I={i1, i2, …, in} là tập hợp các mục duy nhất. Một tập con khác rỗng của I được gọi là một tập mục. Một dãy dữ liệu S là một danh sách sắp xếp theo thứ tự của các tập mục, ký hiệu 𝑆 = 〈(𝑠1 ), (𝑠2 ), … , (𝑠𝑚 )〉, trong đó sj là một tập mục hay một phần tử của dãy (𝑠𝑗 ⊆ 𝐼) . Một cơ sở dữ liệu dãy SDB là một bộ , trong đó sid là một định danh của dãy và Sk là một dãy dữ liệu. Kích thước của dãy: dãy 𝑆 = 〈(𝑠1 ), (𝑠2 ), … , (𝑠𝑚 )〉 được ký hiệu |S| là tổng số dãy sj trong dãy S. Ví dụ: dãy S= có kích thước |S| =5. Độ dài của dãy: dãy 𝑆 = 〈(𝑠1 ), (𝑠2 ), … , (𝑠𝑚 )〉 trong đó sj là một tập mục hay một phần tử của dãy (𝑠𝑗 ⊆ 𝐼) được ký hiệu l(S) là tổng số mục 𝑖𝑗 ∈ 𝐼 có trong dãy S. Một dãy có độ dài l được gọi là l-sequence. Ví dụ: dãy S= có độ dài là l(S) =7. Dãy con và dãy chứa: Dãy α = 〈(𝑆1 ), (𝑆2 ), … , (𝑆𝑚 )〉 được gọi là dãy con của dãy 𝛽 = 〈(𝑆′1 ), (𝑆′2 ), … , (𝑆′𝑚 ), … , (𝑆′𝑛 )〉 nếu và chỉ nếu 𝑆𝑖 ⊆ 𝑆 ′ 𝑖 Ký hiệu là 𝛼 ≼ 𝛽. Dãy β cũng được gọi là dãy chứa của dãy α. Ví dụ: Dãy và dãy là một trong các dãy con của dãy chứa . Độ hỗ trợ của dãy: Độ hỗ trợ (tuyệt đối) của dãy α trong CSDL dãy SDB là tổng số dòng có chứa α trong SDB, ký hiệu là sup(α). 𝑠𝑢𝑝(𝛼) = |{𝛼|𝛼 ≼ 𝑆𝑖 ∧ 𝑆𝑖 ∈ 𝑆𝐷𝐵}| Một dãy α được gọi là mẫu dãy thường xuyên khi và chỉ khi độ hỗ trợ của α không nhỏ hơn độ hộ trợ cực tiểu minsup cho trước, tức là sup(α)  minsup. Các thuật toán khai phá mẫu dãy thường xuyên trong các CSDL dãy thường được thực hiện theo các phương pháp sau: • Thực hiện sinh mẫu dãy bằng phương pháp tìm kiếm theo bề rộng (breath-first search). Các thuật toán điển hình nhất được phát triển theo cách tiếp cận này gồm AprioriAll[2], GSP[10]...
4 • Thực hiện sinh mẫu dãy bằng phương pháp tìm kiếm theo chiều sâu (depth-first search) theo phương pháp biểu diễn CSDL dọc. Các thuật toán điển hình được phát triển theo cách tiếp cận của nhóm này gồm Spade [11], Spam [30], Lapin-Spam [18], CM-Spade, CM-Spam [17] .. • Thực hiện tìm kiếm theo chiều sâu và sử dụng CSDL chiếu theo tiền tố (projected database). Các thuật toán điển hình nhất được phát triển theo cách tiếp cận của nhóm này gồm FreeSpan [13], PrefixSpan [31]…. 1.2. Khai phá mẫu dãy trọng số trong các CSDL dãy CSDL dãy SDB có trọng số: Gọi I={i1, i2, …, in} là tập hợp các mục duy nhất. Mỗi mục 𝑖𝑗 ∈ 𝐼 được gán 1 giá trị trọng số wj thể hiện mức độ quan trọng của mục i. Một tập con khác rỗng của I được gọi là một tập mục. Một dãy dữ liệu S là một danh sách sắp xếp theo thứ tự của các tập mục, ký hiệu 𝑆 = 〈(𝑠1 ), (𝑠2 ), … , (𝑠𝑚 )〉, trong đó sj là một tập mục hay một phần tử của dãy (𝑠𝑗 ⊆ 𝐼) . Một cơ sở dữ liệu dãy có trọng số SDB là một bộ , trong đó sid là một định danh của dãy và Sk là một dãy dữ liệu, đồng thời mỗi mục 𝑖𝑗 ∈ 𝐼 được gán 1 giá trị trọng số wj thể hiện mức độ quan trọng của mục 𝑖𝑗 trong CSDL Một số thuật toán khai phá mẫu dãy trọng số trong CSDL dãy như MWSP [32], Wspan [33], WSPM [34]… 1.3. Khai phá mẫu dãy trong các CSDL dãy định lượng CSDL dãy định lượng QSDB: Gọi I={i1, i2, …, in} là tập hợp các mục duy nhất. Một tập con khác rỗng của I được gọi là một tập mục. Một dãy dữ liệu S là một danh sách sắp xếp theo thứ tự của các tập mục, ký hiệu 𝑆 = 〈(𝑠1 ), (𝑠2 ), … , (𝑠𝑚 )〉, trong đó sj = (i1[k1], i2[k2], …, in[kn]) với 𝑖𝑗 ∈ 𝐼 và kj thể hiện giá trị định lượng của mục i xuất hiện trong giao dịch. Một cơ sở dữ liệu dãy định lượng QSDB là một bộ , trong đó sid là một định danh của dãy và Sk là một dãy dữ liệu định lượng. Một số thuật toán khai phá mẫu dãy trong CSDL định lượng như UL,US [42], Uspan [43], HuspExt [45], HUSPM [47], PHUS [44]... 1.4. Khai phá mẫu dãy trong CSDL dãy có khoảng cách thời gian CSDL dãy có khoảng cách thời gian iSDB: Gọi I={i1, i2, …, in} là tập hợp các mục duy nhất. Một tập con khác rỗng của I được gọi là một tập mục. Một dãy dữ liệu S là một danh sách sắp xếp theo thứ tự của các tập mục, ký hiệu 𝑆 = 〈(𝑡1,1 , 𝑠1 ), (𝑡1,2 , 𝑠2 ), … , (𝑡1,𝑚 , 𝑠𝑚 )〉, trong đó sj là một tập mục hay một phần tử của dãy (𝑠𝑗 ⊆ 𝐼) và t, là khoảng cách thời gian giữa tập mục s và s. Một cơ sở dữ liệu dãy iSDB có khoảng cách thời gian là một bộ , trong đó sid là một định danh của dãy và Sk là một dãy dữ liệu với khoảng cách thời gian. Một số thuật toán khai phá mẫu dãy trong CSDL dãy có khoảng cách thời gian như I-Apriori algorithm, I-PrefixSpan [38], FTI-Apriori và FTI-PrefixSpan [39] .. − Nếu các mục trong I được định nghĩa như nội dung trong phần 1.2 ở trên thì ta có các dãy dữ liệu trọng số trong CSDL dãy có khoảng cách thời gian.
5 Một số thuật toán khai phá mẫu dãy trọng số trong CSDL dãy có khoảng cách thời gian như WIPrefixSpan [40], TopKWFP [CT1] .. − Nếu các mục trong I được định nghĩa như nội dung trong phần 1.2 và 1.3 ở trên thì ta có các dãy dữ liệu lợi ích cao trong CSDL dãy định lượng có khoảng cách thời gian Một số 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 như FSPFTIM [48], UIPrefixSpan [CT3], HUISP [CT5]…. Kết luận Chương 1 Chương 1 đã trình bày tổng quan, tóm tắt những vấn đề liên quan đến khai phá mẫu dãy trong CSDL dãy, khai phá mẫu dãy trọng số trong CSDL dãy, khai phá mẫu dãy trong CSDL dãy định lượng, khai phá mẫu dãy trong CSDL dãy có khoảng cách thời gian. Hình 1.1 sau đây mô tả tổng quan về các vấn đề nghiên cứu của luận án. Hình 1.1. Các vấn đề nghiên cứu của luận án
6 Hiệ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. Tương tự, 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. Cụ thể, luận án sẽ tập trung nghiên cứu đề xuất và giải pháp giải quyết vấn đề sau đây: - Vấn đề 1: trong việc xác định vấn đề nghiên cứu của luận án là đề xuất 01 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. Nội dung này sẽ được trình bày chi tiết trong Chương 2. - Vấn đề 2 trong việc xác định vấn đề nghiên cứu của luận án là đề xuất 02 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. Nội dung này sẽ được trình bày chi tiết trong Chương 3. KHAI PHÁ MẪU DÃY CÓ TRỌNG SỐ TRONG CSDL DÃY CÓ KHOẢNG CÁCH THỜI GIAN Trong chương này, luận án sẽ tập trung trình bày khai phá top-k mẫu dãy thường xuyên trọng số có khoảng cách thời gian. Vấn đề phát hiện top-k mẫu dãy thường xuyên trọng số trên CSDL dãy có khoảng cách thời gian được thực hiện bắt đầu bằng việc nghiên cứu giải quyết bài toán khai phá top-k mẫu dãy thường xuyên trong CSDL dãy sử dụng phương pháp biểu diễn CSDL theo chiều dọc TKS [21] do Fournier-Viger và cộng sự và bài toán khai phá mẫu dãy thường xuyên trọng số có khoảng cách thời gian WIPrefixSpan [40] đã được NCS và đồng sự đề xuất và sau đó tiếp tục thực hiện nghiên cứu và NCS đề xuất thuật toán TopKWFP đã được đăng trên tạp chí Journal of Computer Science and Cybernetics [CT1]. 2.1. Một số khái niệm cơ bản Dãy con và dãy chứa với khoảng cách thời gian Dãy α = 〈(𝑡1,1 , 𝑆1 ), (𝑡1,2 , 𝑆2 ), … , (𝑡1,𝑚 , 𝑆𝑚 )〉 được gọi là dãy con của dãy 𝛽 = 〈(𝑡′1,1 , 𝑆′1 ), (𝑡 ′1,2 , 𝑆′2 ), … , (𝑡 ′1,𝑚 , 𝑆′𝑚 ), … , (𝑡 ′1,𝑛 , 𝑆′𝑛 )〉 nếu và chỉ nếu: 𝑆𝑖 ⊆ 𝑆 ′ 𝑖 ⋀ (|𝑡1,1 − 𝑡 ′1,1 | = |𝑡1,2 − 𝑡 ′1,2 |= ⋯ = |𝑡1,𝑚 − 𝑡 ′1,𝑚 |) Ký hiệu là 𝛼 ≼ 𝛽. Dãy β cũng được gọi là dãy chứa của dãy α. Ví dụ: Dãy và dãy là một trong các dãy con của dãy S1=, và S1 được gọi là dãy chứa của hai dãy con trên. Trọng số của dãy với khoảng cách thời gian
7 Cho I = {i1, i2, …, in} là tập hợp các mục dữ liệu. Mỗi mục ij  I được gán một trọng số wj với j = 1,.....,n. Khi đó trọng số của một dãy  = 〈(𝑡1,1 , 𝑠1 ), (𝑡1,2 , 𝑠2 ), … , (𝑡1,𝑚 , 𝑠𝑚 )〉 có độ dài k và sj có dạng (i1i2… ik) được tính bằng công thức 1 𝑁𝑊() = ∑ 𝑤𝑗 𝑘 𝑖𝑗 ∈  Độ hỗ trợ với trọng số của dãy với khoảng cách thời gian Độ hỗ trợ với trọng số của dãy ký hiệu là 𝑁𝑊𝑠𝑢𝑝𝑝𝑜𝑟𝑡(𝛼): 1 𝑁𝑊𝑠𝑢𝑝𝑝𝑜𝑟𝑡(𝛼) = 𝑁𝑊(𝛼) ∗ 𝑠𝑢𝑝(𝛼) = ( ∑ 𝑤𝑗 ) ∗ 𝑠𝑢𝑝(𝛼) 𝑘 𝑖𝑗 ∈𝛼 Ràng buộc khoảng cách thời gian Cho một dãy S= , các ràng buộc khoảng cách thời gian giữa các dãy được định nghĩa • C1 = min_time_interval là giá trị nhỏ nhất giữa hai dãy liền kề, tức là ti,i+1C1 • C2 = max_time_interval là giá trị lớn nhất giữa hai dãy liền kề, tức là ti,i+1≤C2 • C3 = min_whole_interval là giá trị nhỏ nhất giữa dãy đầu và dãy cuối, tức là ti,m  C3 • C4 = max_whole_interval là giá trị lớn nhất giữa dãy đầu và dãy cuối, tức là ti,m ≤ C4 Mẫu dãy thường xuyên trọng số với khoảng cách thời gian Cho một CSDL dãy iSDB có khoảng cách thời gian, mỗi mục ij  I được gán một trọng số wj, một ngưỡng hỗ trợ tối thiểu wminsup, các ràng buộc khoảng cách thời gian C1, C2, C3, C4. Một dãy  được gọi là mẫu dãy thường xuyên trọng số với khoảng cách thời gian nếu thỏa mãn tính chất: NWSupport()  wminsup ∧  thỏa mãn các ràng buộc C1, C2, C3, C4 Tiền tố và hậu tố trong dãy có khoảng cách thời gian Cho một dãy  = , một thành phần dãy s là một tập các mục ij  I. Khi đó tồn tại một giá trị j (1 ≤ j ≤ m) sao cho s ⊆ sj và t1,  = t1, j . Ta định nghĩa tiền tố trong dãy có khoảng cách thời gian của  với các giá trị s,t1, như sau: Prefix (,s, t1, ) = Khi đó hậu tố trong dãy có khoảng cách thời gian của  với các giá trị s,t1,  được định nghĩa như sau: Postfix (,s, t1, ) = Với s’j là một tập con của sj sau khi đã trừ đi tập s . Khi s’j = , thì hậu tố của  với các giá trị s , t1,  là: Postfix (,s, t1, ) = Cơ sở dữ liệu chiếu trong CSDL dãy có khoảng cách thời gian
8 Cho một dãy  = của một CSDL dãy iSDB có khoảng cách thời gian. Một CSDL chiếu theo  được định nghĩa là iSDB|, là các hậu tố (Postfix) của các dãy trong iSDB với tiền tố . Mẫu dãy ứng viên Cho một ngưỡng hỗ trợ tối thiểu wminsup. MaxW là giá trị lớn nhất của trọng số trong các mục trong iSDB.Một dãy α được gọi là mẫu dãy ứng viên thường xuyên trọng số với khoảng cách thời gian nếu thỏa mãn tính chất Sup(α) * MaxW  wminsup ∧  thỏa mãn các tính chất C1, C2, C3, C4 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 2.2.1. Bài toán đặt ra Cho một CSDL dãy iSDB có khoảng cách thời gian, mỗi mục ij  I được gán một trọng số wj, một số tự nhiên k, các ràng buộc khoảng cách thời gian C1, C2, C3, C4. Bài toán đặt ra: Tìm k- mẫu dãy trong đó mỗi dãy t được gọi là một dãy thuộc top- k mẫu dãy thường xuyên trọng số với khoảng cách thời gian nếu có ít hơn k dãy có độ hỗ trợ với trọng số chuẩn hóa lớn hơn NWSupport(t) và t thỏa mãn các ràng buộc thời gian C1, C2, C3, C4. Giá trị wminsup tối ưu được định nghĩa là: 𝜀 = min{NWSupport(t)|t ∈ Τ }. Với Τ là tập các top-k mẫu dãy thường xuyên trọng số với khoảng cách thời gian. 2.2.2. Ý tưởng thuật toán Đầu tiên đặt wminsup=0. Duyệt CSDL iSDB và tìm các mẫu dãy thường xuyên bằng cách áp dụng phương pháp tăng trưởng mẫu dãy. Mỗi khi một mẫu dãy được tìm thấy, nó sẽ được đưa vào một danh sách L các mẫu dãy được sắp xếp theo độ hỗ trợ có trọng số NWSupport. Danh sách này được sử dụng để lưu các mẫu dãy đã được tìm thấy. Khi có đủ k mẫu dãy trong danh sách L, giá trị wminsup sẽ được tăng lên bằng với NWSupport của mẫu dãy có giá trị NWSupport nhỏ nhất trong L. Việc tăng giá trị wminsup sẽ giúp giảm bớt không gian tìm kiếm. Sau khi tăng wminsup, các mẫu dãy thường xuyên tìm được sẽ được đưa vào L, các mẫu dãy trong L không thỏa mãn giá trị wminsup mới sẽ bị loại ra khỏi L và giá trị wminsup sẽ được tiếp tục tăng lên bằng với giá trị NWSupport của mẫu dãy có NWSupport nhỏ nhất trong L…. Để tăng hiệu suất của giải thuật, sử dụng chiến lược là tìm cách tăng trưởng các mẫu dãy ứng viên hứa hẹn nhất. Nghĩa là tìm cách tạo ra các ứng viên có NWSupport lớn trước, nhờ vậy ngưỡng hỗ trợ wminsup sẽ tăng nhanh hơn và không gian tìm kiếm cũng sẽ được giảm xuống. Cách làm này là sử dụng một tập ứng viên hứa hẹn nhất R để lưu các ứng viên mẫu dãy thường xuyên có trọng số. Sau đó thuật toán TopKWFP luôn mở rộng các mẫu dãy ứng viên có NWSupport lớn nhất trong R trước. Thuật toán tiếp tục đến khi không thể tìm ra được mẫu dãy nào nữa, khi đó thuật toán kết thúc và đưa ra top-k mẫu dãy thường xuyên. 2.2.3. Thuật toán TopKWFP Input: CSDL dãy có khoảng cách thời gian iSDB, W: Bảng giá trị trọng số của các mục i: wi  W, k: Giá trị số xác định top-k mẫu dãy, C1, C2, C3, C4:Giá trị ràng buộc khoảng cách thời gian.
9 Output: Tập top-k các mẫu dãy thường xuyên trọng số với khoảng khách thời gian Thuật toán TopKWFP được mô tả như trong Thuật toán 2.1: Thuật toán TopKWFP 1. Start 2. R= ∅; L= ∅; wminsup=0; 3. Duyệt iSDB lần đầu 4. Begin 5. Đếm giá trị hỗ trợ sup(i) của mỗi mục i trong iSDB; 6. Tính giá trị MaxW = max{W(i)}; 7. End; 8. For earch mỗi mục i trong iSDB 9.  = < (0, i) >; 10. If sup()*maxW  wminsup then 11. R=R; 12. End if; 13. If sup()*NW() wminsup then 14. SAVE(,L,k,wminsup) 15. End if; 16.End For; 17. If k < số lượng mục i trong iSDB then 18. Duyệt iSDB thứ hai 19. Begin 20. Xây dựng lại CSDL iSDB bằng cách loại bỏ tất cả các mục i trong iSDB không thỏa mãn điều kiện sup()*maxW  wminsup; 21. End; 22. End if; 23. While ∃𝑟 ∈ 𝑅 và sup(r)*maxW  wminsup do 24. r = mẫu dãy có sup(r)*NW(r) lớn nhất trong R; 25. Xây dựng cơ sở dữ liệu tiền tố r là iSDB|r; 26. PROJECTION(iSDB|r,W(i),C1,C2,C3,C4,wminsup,k); 27. Loại bỏ r trong R; 28. Loại bỏ khỏi R tất cả các mục s thỏa mãn điều kiện sup(s)*maxW
10 2. Duyệt iSDB|r để tìm tất cả các cặp (∆t; i) thỏa mãn sup(i)*maxW wminsup, C1 và C2, với i là một mục dữ liệu, ∆t là khoảng cách thời gian giữa r và i; 3. For each (∆t; i) 4. r = ; 5. If r thỏa mãn C4 then 6. R = R  r; 7. If r thỏa mãn C3 and sup(r)*NW(r)  wminsup then 8. SAVE(r,L,k,wminsup); 9. End if; 10. End if; 11. End For; 12. End. Thủ tục SAVE được mô tả như trong sau: Thủ tục SAVE (r,L,k,wminsup) 1. Start 2. L= L {r}; 3. If |L| > k then 4. If NWSupport(r) > wminsup then 5. While |L| > k and ∃s ∈ L| NWSupport(s) = wminsup 6. Loại bỏ s trong L. 7. End while; 8. End if; 9. wminsup = giá trị NWSupport nhỏ nhất trong L; 10. End if; 11. End. 2.2.4. Thử nghiệm thuật toán 2.2.4.1. Dữ liệu thử nghiệm Thông tin về các bộ dữ liệu được mô tả trong Bảng 2.1: Bảng 2.1. Các bộ dữ liệu thử nghiệm Số lượng Số mục dữ Trung bình độ CSDL Loại dữ liệu dãy liệu dài của dãy Bible 36369 13905 21.64 book BMS- 59601 497 2.42 web click stream WebView1 FIFA 20450 2990 34.74 web click stream Leviathan 5834 9025 33.81 book Sign sign language 730 267 51.99 utterances
11 Thuật toán TopKWFP được viết trên ngôn ngữ lập trình Java 1.8 trên IDE Eclipse và được thực hiện trên máy tính có chip Intel Core i7 3.6GHz processor, 8GB RAM, Windows10. 2.2.4.2. Kết quả thử nghiệm a) Ảnh hưởng của tham số k Thuật toán TopKWFP chạy với các giá trị k khác nhau từ 1000 đến 10000. Các ngưỡng khoảng cách thời gian được đặt cố định là C1=0; C2= 5; C3= 0; C4=15. Kết quả của thuật toán được thử nghiệm được thể hiện trong Hình 2.1. Có thể thấy thời gian chạy và bộ nhớ sử dụng của thuật toán tăng nhanh khi tăng tham số k. Điều này là do khi tăng tham số k, không gian tìm kiếm được mở rộng hơn dẫn tới số mẫu dãy ứng viên tạo ra cũng tăng lên đòi hỏi thuật toán cần phải thực hiện tính toán nhiều hơn. Bible BMS WebView1 Fifa Leviathan Sign Hình 2.1 Ảnh hưởng của tham số k b) So sánh hiệu năng thuật toán TopKWFP với thuật toán WIPrefixSpan Thử nghiệm so sánh thuật toán WIPrefixSpan và thuật toán TopKWFP. Thuật toán TopKWFP được so sánh với thuật toán WIPrefixSpan với ngưỡng hỗ trợ tối ưu. Để làm được điều này, đầu tiên thuật toán TopKWFP được chạy trước để tìm ra ngưỡng hỗ trợ tối ưu, sau đó ngưỡng này sẽ được sử dụng để chạy thuật toán WIPrefixSpan. Kết quả được thể hiện trong Hình 2.2.
12 Bible BMS WebView1 Fifa Leviathan Sign Hình 2.2. So sánh 2 thuật toán WIPrefixSpan và TopKWFP Có thể thấy, thuật toán TopKWFP có hiệu năng tốt hơn WIPrefixSpan trong tất cả các bộ dữ liệu thử nghiệm và trong một số trường hợp TopKWFP chạy nhanh hơn vài lần so với WIPrefixSpan. Nhờ sử dụng chiến lược sinh mẫu dãy hứa hẹn nhất nên thuật toán TopKWFP chỉ sinh ra các mẫu dãy hứa hẹn nhất (các mẫu dãy có độ hỗ trợ cao nhất) thay vì phải mở rộng ra toàn bộ không gian tìm kiếm như trong WIPrexSpan. Kết luận Chương 2 Trong chương này luận án đã trình bày việc phát hiện top-k mẫu dãy có trọng số trong Cơ sở dữ liệu dãy có khoảng cách thời gian. Trong thuật toán TopKWFP, mỗi mục dữ liệu được xác định giá trị trọng số riêng và dữ liệu giữa các dãy dữ liệu trong CSDL đều có khoảng cách thời gian. Thuật toán được phát triển dựa trên thuật toán WIPrefixSpan là thuật toán sử dụng cơ sở dữ liệu tiền tố và phương pháp tăng trưởng mẫu dãy và thuật toán TKS là thuật toán khai phá top-k mẫu dãy thường xuyên trong CSDL dãy. Thuật toán là đúng đắn và đầy đủ. Độ phức tạp của thuật toán là hàm mũ O(nn) (n là độ dài dãy lớn nhất). Các thuật toán theo phương pháp tăng trưởng mẫu dãy thường cố gắng làm giảm không gian dữ liệu để tìm được các mẫu dãy thường xuyên theo mục tiêu đặt ra, việc đánh giá tính hiệu quả dựa vào các kết quả thực nghiệm. Luận án cũng đã tiến hành thực nghiệm thuật toán trên tập dữ liệu thực. Kết quả thực nghiệm cho thấy tính đúng đắn và khả thi của thuật toán được đề xuất. Bài báo về thuật toán TopKWFP đã được đăng trên tạp chí Journal of Computer Science and Cybernetics [CT1].
13 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 Trong chương này, luận án sẽ tập trung trình bày khai phá các 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. Thực hiện khai phá mẫu dãy lợi ích cao trên CSDL dãy định lượng có khoảng cách thời gian được phát triển dựa trên thuật toán WIPrefixSpan [40] do Duong và cộng sự đề xuất và thuật toán khai phá mẫu dãy lợi ích cao như US, UL [42] đã được Ahdmed và cộng sự đề xuất. Kết quả nghiên cứu và đề xuất thuật toán UIPrefixSpan khai phá mẫu dãy lợi ích cao đã được đăng trên Kỷ yếu hội thảo Một số vấn đề chọn lọc của Công nghệ thông tin và Truyền thông [CT2] và tạp chí Cybernetics and Information Technologies [CT3]. Sau đó, NCS tiếp tục nghiên cứu giải thuật PHUS [44] do Lan và cộng sự đề xuất trong khai phá mẫu dãy trong CSDL dãy định lượng, đề xuất cách tiếp cận 1 pha bằng cách tính sử dụng bảng lợi ích, bảng chỉ mục, và kết quả nghiên cứu đề xuất thuật toán HUISP khai phá mẫu dãy lợi ích cao với khoảng cách thời gian đã được đăng trên Kỷ yếu hội thảo Một số vấn đề chọn lọc của Công nghệ thông tin và Truyền thông [CT4] và tạp chí Journal of Computer Science and Cybernetics [CT5]. 3.1. Một số khái niệm cơ bản Lợi ích trong và lợi ích ngoài Gọi i là một mục thuộc một dãy Sj, lợi ích trong của i trong dãy Sj được ký hiệu là iu(i,Sj) là giá trị được gán với mỗi lần xuất hiện của i trong dãy Sj biểu thị số lượng (định lượng) của i trong dãy Sj. Một mục i trong một dãy Sj có thể xuất hiện nhiều lần trong Sj nên khi đó, việc tính lợi ích trong của mục i với giá trị iu(i,Sj) là giá trị lớn nhất trong các định lượng của i trong dãy Sj. Lợi ích ngoài của i được ký hiệu là eu(i) là một giá trị cố định cho trước trong bảng lợi ích ngoài thể hiện mức độ quan trọng của mục i trong QiSDB. Lợi ích của một mục trong dãy Lợi ích của một mục i trong dãy Sj ký hiệu là su(i, Sj) và được tính bằng công thức: su(i, Sj) = iu(i, Sj) * eu(i). Vì mục i có thể xuất hiện nhiều lần trong dãy Sj nên ở đây lợi ích của mục i được tính bằng giá trị lớn nhất của các lợi ích của mục i trong Sj. Lợi ích của một mẫu dãy Cho 𝛼 = 〈(𝑡1,1 , 𝑋1 ), (𝑡1,2 , 𝑋2 ), … , (𝑡1,𝑛 , 𝑋𝑛 )〉 là một mẫu dãy có khoảng cách thời gian có độ dài n, với 𝛼 ≼ 𝑆𝑗 . Lợi ích của một mẫu dãy α trong Sj , ký hiệu su(α,Sj), được tính bằng công thức: 𝑠𝑢(α, 𝑆𝑗 ) = max {∑ 𝑠𝑢(i, 𝑆𝑗 ) , ∀α ≼ 𝑆𝑗 } 𝑖∈α Lợi ích của một dãy đầu vào Lợi ích của dãy đầu vào Sj, ký hiệu là su(Sj) và được tính bằng công thức:
14 𝑠𝑢(𝑆𝑗 ) = ∑ 𝑠𝑢(i,𝑆𝑗 ) 𝑖∈𝑆𝑗 Lợi ích của một mẫu dãy trong toàn bộ CSDL Lợi ích của mẫu dãy α trong QiSDB ký hiệu là su(α, QiSDB) và được tính bằng công thức: 𝑠𝑢(α, 𝑄𝑖𝑆𝐷𝐵) = ∑ 𝑠𝑢(α,𝑆𝑗 ) 𝑆𝑗 ∈𝑄𝑖𝑆𝐷𝐵 Lợi ích của CSDL dãy định lượng có khoảng cách thời gian Lợi ích của CSDL QiSDB, ký hiệu su(QiSDB) được tính bằng công thức: 𝑠𝑢(𝑄𝑖𝑆𝐷𝐵) = ∑ 𝑠𝑢(𝑆𝑗 ) 𝑆𝑗 ∈𝑄𝑖𝑆𝐷𝐵 Ràng buộc khoảng cách thời gian Cho một dãy S= , các ràng buộc khoảng cách thời gian giữa các dãy được định nghĩa • C5 = min_time_interval là giá trị nhỏ nhất giữa hai dãy liền kề, tức là ti,i+1C5 • C6 = max_time_interval là giá trị lớn nhất giữa hai dãy liền kề, tức là ti,i+1≤C6 • C7 = min_whole_interval là giá trị nhỏ nhất giữa dãy đầu và dãy cuối, tức là ti,m  C7 • C8 = max_whole_interval là giá trị lớn nhất giữa dãy đầu và dãy cuối, tức là ti,m ≤ C8 Mẫu dãy lợi ích cao với khoảng cách thời gian Cho một CSDL dãy định lượng QiSDB có khoảng cách thời gian, mỗi mục ij  I được gán một trọng số wj, một ngưỡng hỗ trợ tối thiểu minUtil, các ràng buộc khoảng cách thời gian C5, C6, C7, C8. Một dãy α được gọi là mẫu dãy lợi ích cao với khoảng cách thời gian nếu thỏa mãn tính chất: su(α,QiSDB)  minUtil ∧  thỏa mãn tính chất các ràng buộc C5, C6, C7, C8 Giá trị swu của dãy: Cho một dãy α, khi đó giá trị swu của dãy α được tính bằng công thức 𝑠𝑤𝑢(𝛼, 𝑄𝑖𝑆𝐷𝐵) = ∑ 𝑠𝑢(𝑆𝑎 ) 𝛼 ≼𝑆𝑎 ∧ 𝑆𝑎 ∈𝑄𝑖𝑆𝐷𝐵 Mẫu dãy ứng viên: Cho một ngưỡng hỗ trợ tối thiểu minUtil. Một dãy α được gọi là dãy ứng viên mẫu dãy thường xuyên lợi ích cao có khoảng cách thời gian nếu thỏa mãn tính chất swu(α, QiSDB)  minUtil ∧ α thỏa mãn các tính chất C5, C6, C7, C8. Với swu(α) là tổng giá trị lợi ích của các dòng dữ liệu 𝑆𝑎 có chứa α trong CSDL QiSDB. Vì vậy, mẫu dãy ứng viên được xây dựng nhằm mục đích tỉa bớt không gian tìm kiếm mà vẫn đảm bảo tính phản đơn điệu trong khai phá mẫu dãy lợi ích cao trong CSDL dãy định lượng với khoảng cách thời gian.
15 3.2. Thuật toán khai phá mẫu dãy lợi ích cao với khoảng cách thời gian (UIPrefixSpan) 3.2.1. Bài toán đặt ra Cho một CSDL dãy định lượng QiSDB có khoảng cách thời gian, mỗi mục ij  I trong dãy Sa được gán một giá trị lợi ích trong và một giá trị lợi ích ngoài, một ngưỡng hỗ trợ tối thiểu minUtil, các giá trị ràng buộc khoảng cách thời gian C5, C6, C7, C8. Bài toán đặt ra : Tìm tất cả các mẫu dãy lợi ích cao có khoảng cách thời gian trong QiSDB, tức là tìm tập L: 𝐿 = { ≼ 𝑆| 𝑠𝑢(, QiSDB) ≥ 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 ∧  thỏa mãn các ràng buộc 𝐶5 , 𝐶6 , 𝐶7 , 𝐶8 ∧ 𝑆 ∈ 𝑄𝑖𝑆𝐷𝐵} 3.2.2. Ý tưởng thuật toán Thuật toán UIPrefixSpan đầu tiên khởi tạo các giá trị tập ứng viên mẫu dãy lợi ích cao R , tập kết quả các mẫu dãy lợi ích cao L bằng rỗng. Sau đó quét CSDL QiSDB lần đầu để tìm các mục i là các ứng viên có độ dài = 1 trong CSDL. Với mỗi mục i thỏa mãn swu(i,QiSDB)  minUtil ghép giá trị  = < (0, i) >, đưa  vào tập ứng viên R. Thực hiện đệ quy để thủ tục subUIPrefixSpan để khai phá các mẫu dãy lợi ích cao trên CSDL chiếu với tiền tố . Tiếp theo, quét CSDL QiSDB lần 2 đề kiểm tra điều kiện su(,QiSDB)  minUtil với tất các mẫu dãy  trong tập ứng viên R tìm thấy. Nếu thỏa mãn thì đưa  vào tập kết quả L. 3.2.3. Thuật toán UIPrefixSpan Thuật toán được minh họa như Thuật toán 3.1. Thuật toán 3.1. Thuật toán UIPrefixSpan Thuật toán UIPrefixSpan (QiSDB,W(i),minUtil,C5,C6,C7,C8) 1. Start 2. α = ; 3. R = ; L = ; 4. Duyệt QiSDB lần đầu 5. Begin 6. For earch mỗi mục i trong QiSDB 7.  = < (0, i) >; 8. If swu(,QiSDB)  minUtil then 9. R=R; 10. End if; 11 R= subUIPrefixSpan (QiSDB|α,R,minUtil, C5, C6, C7, C8); 12. End For; 13. End; 14. Duyệt QiSDB lần 2 15. Begin 16. Tính giá trị hỗ trợ su(,QiSDB) của mỗi dãy   R; 17. If su(α,QiSDB)  minUtil then 18. L=L;
16 19. End if; 20. End; 21. Rerurn L; 22. End. Thủ tục subUIPrefixSpan được mô tả như sau: Thủ tục subUIPrefixSpan(QiSDB|r,R,minUtil,C5,C6,C7,C8) 1. Start 2. Duyệt QiSDB|r để tìm tất cả các cặp (∆t;i) thỏa mãn swu((∆t;i),QiSDB|r)minUtil, C5 và C6, với i là một mục dữ liệu, ∆t là khoảng cách thời gian giữa r và i; 3. For each (∆t; i) 4. r = ; 5. If r thỏa mãn C8 then 6. R= subUIPrefixSpan (QiSDB|r,R,minUtil, C5, C6, C7, C8); 7. If r thỏa mãn C7 then 8. R=Rr; 9. End if; 10. End if; 11. End For; 12. Rerurn R; 13. End. 3.2.4. Thử nghiệm thuật toán 3.2.4.1. Dữ liệu thử nghiệm Thông tin về các bộ dữ liệu được mô tả trong Bảng 3.1: Bảng 3.1. Các bộ dữ liệu thử nghiệm Trung Số Số bình độ CSDL Loại dữ liệu lượng dãy mục dài của dãy D10K.C9.T8.S7.I8.N1K (DS1) 10000 1000 8 IBM data generator D200K.C10.T9.S9.I7.N1K 200000 1000 7 IBM data generator (DS2) BMS-WebView1 (DS3) 59601 497 2.42 web click stream Thuật toán UIPrefixSpan được viết trên ngôn ngữ lập trình Java 1.8 trên IDE Eclipse và được thực hiện trên máy tính có chip Intel Core i7 3.6GHz processor, 8GB RAM, Windows10. 3.2.4.2. Kết quả thử nghiệm a) Đánh giá mối quan hệ giữa ngưỡng lợi ích tối thiểu và thời gian thực hiện
17 Việc thử nghiệm hiệu năng của thuật toán UIPrefixSpan trong hai trường hợp: Có sử dụng các ràng buộc thời gian C5=0; C6=5; C7=0; C8=20 (UIPrefixSpan1) và không sử dụng ràng buộc thời gian C5=0; C6=0; C7=0; C8=0 (UIPrefixSpan2). D10K.C9.T8.S7.I8.N1K D200K.C10.T9S9.I7.N1K BMS-WebView-1 Hình 3.1 Thời gian chạy UIPrefixSpan Hình 3.1: So sánh về thời gian chạy cho thấy UIPrefixSpan1 thực hiện nhanh hơn, hiệu quả hơn so với UIPrefixSpan2. Khi giá trị minUtil giảm thì thời gian chạy của UIPrefxiSpan2 tăng lên đáng kể. Ngược lại, UIPrefixSpan1 chạy tốt với minUtil thấp và nhanh hơn nhiều so với UIPrefixSpan2 trong cả tập dữ liệu tổng hợp (DS1-DS2) và tập dữ liệu thực (DS3). Đó là bởi vì khi sử dụng giới hạn thời gian (UIPrefixSpan1), ít ứng cử viên được tạo hơn, do đó, không gian tìm kiếm bị giảm và thời gian chạy giảm. b) Đánh giá mối quan hệ giữa ngưỡng lợi ích tối thiểu và bộ nhớ sử dụng D10K.C9.T8.S7.I8.N1K D200K.C10.T9S9.I7.N1K BMS-WebView-1 Hình 3.2 Bộ nhớ sử dụng UIPrefixSpan Hình 3.2: So sánh về hiệu quả bộ nhớ sử dụng: UIPrefixSpan1 cũng sử dụng ít bộ nhớ hơn UIPrefixSpan2. Trên DS1, UIPrefixSpan1 sử dụng bộ nhớ ít hơn 1,2 lần so với UIPrefixSpan2 và trong một số trường hợp (với minUtil là 2% 9% và 10%), thuật toán UIPrefixSpan1 sử dụng bộ nhớ ít hơn đến 2,2 lần. Trên DS2, UIPrefixSpan1 sử dụng bộ nhớ ít hơn 1,4 lần so với UIPrefixSpan2 và với minUtil thấp (
18 c) Đánh giá mối quan hệ giữa ngưỡng lợi ích tối thiểu và số mẫu dãy lợi ích cao D10K.C9.T8.S7.I8.N1K D200K.C10.T9.S9.I7.N1K BMS-WebView-1 Hình 3.3 Số mẫu dãy lợi ích cao UIPrefixSpan Hình 3.3: Thể hiện một số mẫu lợi ích cao được tìm thấy trong UIPrefixSpan1 ít hơn UIPrefixSpan2, nhưng những mẫu đó có ý nghĩa hơn bởi các điều kiện ràng buộc thời gian. Bằng cách sử dụng các ràng buộc về thời gian, có thể tránh được việc tạo ra các mẫu ít ý nghĩa hơn. 3.3. Thuật toán khai phá mẫu dãy lợi ích cao với khoảng cách thời gian (HUISP) 3.3.1. Bài toán đặt ra Cho một CSDL dãy định lượng QiSDB có khoảng cách thời gian, mỗi mục ij  I trong dãy Sa được gán một giá trị lợi ích trong và một giá trị lợi ích ngoài, một ngưỡng hỗ trợ tối thiểu minUtil, các giá trị ràng buộc khoảng cách thời gian C5, C6, C7, C8. Bài toán đặt ra : Tìm tất cả các mẫu dãy lợi ích cao có khoảng cách thời gian trong QiSDB, tức là tìm tập L: 𝐿 = { ≼ 𝑆| 𝑠𝑢(, QiSDB) ≥ 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 ∧  thỏa mãn các ràng buộc 𝐶5 , 𝐶6 , 𝐶7 , 𝐶8 ∧ 𝑆 ∈ 𝑄𝑖𝑆𝐷𝐵} 3.3.2. Ý tưởng thuật toán Thuật toán HUISP đầu tiên khởi tạo các giá trị tập ứng viên mẫu dãy lợi ích cao R, tập kết quả các mẫu dãy lợi ích cao L bằng rỗng. Sau đó quét CSDL QiSDB lần đầu để tính các giá trị lợi ích của mỗi mục i trong dãy đầu vào su(i,iSa), và giá trị lợi ích của mỗi dãy đầu vào su(iSa). Sau đó thực hiện xây dựng bảng lợi ích cho các mục i trong QiSDB. Thực hiện duyệt bảng lợi ích, với mỗi mục i ghép giá trị  = < (0, i) > thỏa mãn swu()  minUtil, đưa  vào tập ứng viên R. Loại bỏ các mục không nằm trong R khỏi CSDL QiSDB. Kiểm tra tiếp điều kiện su(,QiSDB)  minUtil, nếu thỏa mãn thì đưa  vào tập kết quả L. Tiếp theo xây dựng bảng chỉ mục cho mỗi dãy trong tập ứng viên R. Với mỗi dãy  trong R, dựa vào bảng chỉ mục thực hiện xây dựng CSDL chiếu cho  bao gồm tất cả các dãy đầu vào của QiSDB có chứa . Thực hiện đệ quy để thủ tục subHUISP để khai phá các mẫu dãy lợi ích cao trên CSDL chiếu với tiền tố . 3.3.3. Thuật toán HUISP Thuật toán được minh họa như Thuật toán 3.3. Thuật toán 3.2. Thuật toán HUISP Thuật toán HUISP (QiSDB,W(i),minUtil,C5,C6,C7,C8)