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