đặ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. 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. 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.
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ở 17 dữ liệu do việc tạo ra các ứng viên bằng cách kết hợp các mẫu nhỏ hơn mà không cần truy cập cơ sở dữ liệu. GSP có thể tốn nhiều thời gian kiểm tra nhiều mẫu không tồn tại trong cơ sở dữ liệu.
Một vấn đề khác của thuật toán GSP là phải sử dụng bộ nhớ lớn vì tại bất kỳ thời điểm nào thuật toán cũng phải giữ tất cả các mẫu dãy thường xuyên có độ dài k trong bộ nhớ để có thể tạo ra các mẫu dãy có độ dài k + 1. Các thuật toán tìm kiếm theo chiều sâu như Spade [11], PrefixSpan [31], Spam [30], Lapin [18], CM-Spam và CM-Spade [17] thực hiện khai phá không gian tìm kiếm của các mẫu dãy bằng các cách khác nhau. Bắt đầu từ các mẫu dãy chứa các mục đơn lẻ, sau đó thực hiện đệ quy đối với các mở rộng của các mẫu dãy này để tạo ra các mẫu dãy lớn hơn. Sau đó, khi một mẫu dãy không thể được mở rộng nữa, thuật toán sẽ quay trở lại để tạo các mẫu dãy khác.
Thuật toán Spade [11] là một thuật toán sử dụng phương pháp tìm kiếm theo chiều sâu và tránh một số nhược điểm của thuật toán GSP. Thuật toán Spade được thực hiện theo phương pháp từ thuật toán Eclat [4] để khai phá tập mục thường xuyên. Spade sử dụng biểu diễn cơ sở dữ liệu dọc thay thế biểu diễn cơ sở dữ liệu ngang ban đầu. Biểu diễn theo chiều dọc của cơ sở dữ liệu dãy cho biết các tập hợp mục mà mỗi mục i xuất hiện trong cơ sở dữ liệu dãy.
Đối với một mặt hàng nhất định, thông tin này được gọi là IDList của mặt hàng đó. Bằng cách sử dụng biểu diễn CSDL dọc, các thuật toán như Spade [11], Spam [30], CM-Spam và CMSpade [17] khai phá toàn bộ không gian tìm kiếm của các mẫu dãy bằng cách đọc cơ sở dữ liệu chỉ một lần để tạo IDLists duy nhất mặt hàng. Sau đó, các IDLists của bất kỳ mẫu dãy nào gặp phải khi duyệt không gian tìm kiếm thu được bằng cách thực hiện phép nối các IDLists, cho phép tính toán hỗ trợ của mẫu dãy. Vì vậy tất cả các mẫu dãy thường xuyên có thể được liệt kê mà không cần duyệt liên tục cơ sở dữ liệu và không cần duy trì một số lượng lớn các mẫu dãy trong bộ nhớ (trái ngược với các thuật toán tìm kiếm theo chiều rộng).
Cách tiếp cận này được xem là một trong những cách hiệu quả để khai thác mẫu dãy hơn so với các thuật toán theo tiếp cận tìm kiếm theo chiều rộng. Bên cạnh thuật toán tìm kiếm theo chiều rộng và thuật toán khai thác theo chiều sâu sử dụng CSDL dọc, một phương pháp quan trọng khác để khai phá mẫu dãy là các thuật toán tăng trưởng mẫu dãy. Các thuật toán tăng trưởng mẫu dãy thực hiện tìm 18 kiếm theo chiều sâu, được thiết kế để giải quyết một hạn chế của các thuật toán được mô tả trước đó vì có thể tạo ra các mẫu ứng cử viên không tồn tại trong cơ sở dữ liệu ban đầu. Lý do là các thuật toán theo phương pháp tìm kiếm theo chiều rộng và thuật toán khai thác theo chiều sâu sử dụng CSDL dọc có thể tạo ra các mẫu dãy không xuất hiện trong cơ sở dữ liệu vì việc thực hiện tạo ra các mẫu dãy ứng viên bằng cách kết hợp các mẫu dãy nhỏ hơn nhưng quá trình này không liên quan đến việc truy cập cơ sở dữ liệu.
Các thuật toán theo phương pháp tăng trưởng mẫu dãy bằng cách duyệt đệ quy cơ sở dữ liệu để tìm các mẫu dãy lớn hơn, vì vậy chỉ thực hiện khai phá các mẫu dãy thực sự tồn tại trong cơ sở dữ liệu. Tuy nhiên, việc thực hiện duyệt cơ sở dữ liệu nhiều lần có thể gây tốn kém tài nguyên. Để giảm chi phí duyệt cơ sở dữ liệu, thuật toán tăng trưởng mẫu dãy có đưa ra khái niệm cơ sở dữ liệu chiếu theo tiền tố nhằm mục đích giảm kích thước của cơ sở dữ liệu vì các mẫu lớn hơn được tìm kiếm theo chiều sâu. Thuật toán khai phá mẫu dãy tăng trưởng đầu tiên được đề xuất là FreeSpan [13], sau đó cùng một nhóm nghiên cứu đề xuất thuật toán PrefixSpan [31] theo phương pháp của thuật toán FPGrowth cho khai thác tập mục thường xuyên.
PrefixSpan thực hiện khai phá không gian tìm kiếm của các mẫu dãy bằng cách sử dụng phương pháp tìm kiếm theo chiều sâu. Bắt đầu từ các mẫu dãy chứa một mục và khai phá các mẫu dãy lớn hơn bằng cách nối đệ quy các mục vào các mẫu dãy này để tạo ra các mẫu dãy lớn hơn.