I. Tổng quan về khai phá dữ liệu
Khai phá dữ liệu là một quá trình quan trọng trong việc khám phá tri thức từ các nguồn dữ liệu lớn. Quá trình này không chỉ giúp phát hiện các mẫu có ích mà còn tìm ra mối liên hệ giữa chúng. Khai phá luật kết hợp là một phần thiết yếu trong khai phá dữ liệu, bao gồm hai bước chính: tìm các tập mục thường xuyên và sinh ra các luật kết hợp từ những tập mục này. Bài toán khai phá tập mục thường xuyên đã thu hút sự quan tâm của nhiều nhà nghiên cứu, dẫn đến sự phát triển của nhiều thuật toán mới. Một trong những thuật toán nổi bật là AprioriAll, được Agrawal và cộng sự giới thiệu vào năm 1995. Thuật toán này dựa trên nguyên tắc duyệt dữ liệu theo chiều rộng để khai phá các mẫu dãy thường xuyên có độ dài lớn nhất. Tuy nhiên, một trong những thách thức lớn nhất trong khai phá dữ liệu là xác định các mẫu dãy có giá trị và lợi ích khác nhau, điều này dẫn đến nhu cầu nghiên cứu về trọng số và khoảng cách thời gian trong các mẫu dãy.
1.1. Khái niệm về tập mục thường xuyên
Tập mục thường xuyên được định nghĩa là các tập mục có độ hỗ trợ lớn hơn ngưỡng hỗ trợ tối thiểu. Để tìm ra các tập mục này, người ta thường sử dụng hai ràng buộc chính: độ hỗ trợ và độ tin cậy. Độ hỗ trợ của một tập mục được tính bằng tỷ lệ giao dịch trong tập dữ liệu có chứa tập mục đó. Ví dụ, trong một cơ sở dữ liệu giao tác, nếu một tập mục xuất hiện trong 20% tổng số giao dịch, nó sẽ được coi là một tập mục thường xuyên nếu ngưỡng hỗ trợ tối thiểu là 10%. Việc xác định các tập mục thường xuyên là bước quan trọng trong quá trình tìm kiếm luật kết hợp, vì nó ảnh hưởng trực tiếp đến độ chính xác và tính hữu ích của các luật được sinh ra.
II. Khai phá mẫu dãy thường xuyên
Khai phá mẫu dãy thường xuyên là một mở rộng của khai phá tập mục thường xuyên, tập trung vào việc phát hiện các dãy con phổ biến trong cơ sở dữ liệu dãy. Một dãy được định nghĩa là một danh sách có thứ tự của các mục dữ liệu, và một dãy con được coi là một phần của dãy lớn hơn nếu các mục của nó xuất hiện theo thứ tự trong dãy đó. Để khai phá mẫu dãy thường xuyên, cần xác định các dãy có độ hỗ trợ lớn hơn ngưỡng hỗ trợ tối thiểu. Các thuật toán như AprioriAll và PrefixSpan đã được phát triển để giải quyết bài toán này. Tuy nhiên, một thách thức lớn là các mẫu dãy thường xuyên không chỉ cần được xác định dựa trên số lần xuất hiện mà còn cần xem xét đến trọng số và khoảng cách thời gian giữa các mục dữ liệu. Điều này dẫn đến việc phát triển các thuật toán mới nhằm khai thác thông tin này một cách hiệu quả.
2.1. Mẫu dãy thường xuyên có trọng số
Mẫu dãy thường xuyên có trọng số là một khái niệm quan trọng trong khai phá dữ liệu, nơi mà mỗi mẫu dãy được gán một trọng số phản ánh mức độ quan trọng của nó. Các thuật toán khai phá mẫu dãy thường xuyên truyền thống thường không xem xét đến trọng số, dẫn đến việc các mẫu có giá trị khác nhau được coi là như nhau. Để khắc phục điều này, các nghiên cứu đã chỉ ra rằng việc sử dụng trọng số có thể cải thiện đáng kể độ chính xác của các mẫu dãy được khai phá. Phương pháp tiếp cận này không chỉ giúp xác định các mẫu dãy quan trọng hơn mà còn cho phép người dùng điều chỉnh các mẫu dãy theo nhu cầu cụ thể của họ.
III. Bài 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
Bài 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 là một trong những vấn đề nghiên cứu mới trong lĩnh vực khai phá dữ liệu. Mục tiêu của bài toán này là tìm ra k mẫu dãy thường xuyên có trọng số cao nhất trong một cơ sở dữ liệu dãy, đồng thời xem xét khoảng cách thời gian giữa các mục dữ liệu. Việc xem xét khoảng cách thời gian là rất quan trọng, vì nó ảnh hưởng đến mức độ quan trọng của các mẫu dãy. Các thuật toán như WIPrefixSpan đã được phát triển để giải quyết bài toán này, cho phép khai thác thông tin về trọng số và khoảng cách thời gian một cách hiệu quả. Kết quả của nghiên cứu này không chỉ có giá trị lý thuyết mà còn có ứng dụng thực tiễn trong nhiều lĩnh vực như phân tích thị trường, dự đoán hành vi người tiêu dùng và phát hiện xâm nhập trong môi trường mạng.
3.1. Thuật toán WIPrefixSpan
Thuật toán WIPrefixSpan là một trong những thuật toán tiên tiến được sử dụng để khai phá top-k mẫu dãy thường xuyên trọng số với khoảng cách thời gian. Thuật toán này kết hợp giữa việc khai thác các mẫu dãy thường xuyên và việc xem xét trọng số cũng như khoảng cách thời gian giữa các mục. Bằng cách sử dụng các kỹ thuật tối ưu hóa, WIPrefixSpan có thể giảm thiểu thời gian tính toán và tăng cường độ chính xác của các mẫu dãy được khai phá. Kết quả thử nghiệm cho thấy thuật toán này có khả năng xử lý các bộ dữ liệu lớn một cách hiệu quả, đồng thời cung cấp các mẫu dãy có giá trị cao cho người dùng.
