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

Khai phá dữ liệu là một lĩnh vực quan trọng trong khoa học máy tính. Khai phá mẫu dãy (sequential pattern mining) là một nhánh chủ yếu của khai phá dữ liệu (data mining). Nó tìm kiếm các mẫu trình tự có ý nghĩa trong các cơ sở dữ liệu dãy. Các mẫu này đại diện cho các chuỗi sự kiện thường xuyên xảy ra theo một trình tự nhất định. Ví dụ, trong giỏ hàng trực tuyến, một khách hàng mua sản phẩm A, sau đó mua B, rồi mua C. Điều này tạo thành một mẫu dãy. Ứng dụng của khai phá mẫu dãy rất rộng. Chúng bao gồm phân tích hành vi khách hàng, chẩn đoán y tế, phân tích sự cố mạng và dự đoán chuỗi gen. Việc tìm ra các mẫu này giúp doanh nghiệp đưa ra quyết định kinh doanh tốt hơn. Nó cũng hỗ trợ các nhà khoa học trong việc khám phá tri thức mới. Tuy nhiên, các phương pháp truyền thống thường bỏ qua một số yếu tố quan trọng. Đó là trọng số của các mục và khoảng cách thời gian giữa các sự kiện. Mẫu dãy truyền thống chỉ xem xét tần suất xuất hiện. Điều này có thể không phản ánh đầy đủ giá trị thực của một mẫu. Một mẫu ít xuất hiện nhưng có giá trị cao vẫn có thể rất quan trọng.

Khai phá mẫu trình tự truyền thống đối mặt nhiều thách thức. Thứ nhất, dữ liệu ngày càng lớn. Việc xử lý tập dữ liệu khổng lồ yêu cầu tài nguyên tính toán lớn. Thứ hai, các thuật toán cũ thường chỉ tập trung vào tần suất. Chúng bỏ qua giá trị hay lợi ích khác nhau của các mục. Một sản phẩm giá trị cao chỉ cần xuất hiện vài lần cũng có thể quan trọng hơn một sản phẩm giá trị thấp xuất hiện nhiều lần. Thứ ba, khoảng cách thời gian giữa các sự kiện là một yếu tố then chốt. Nhiều ứng dụng yêu cầu các sự kiện phải xảy ra trong một khung thời gian nhất định. Ví dụ, một triệu chứng bệnh phải xuất hiện trong vài ngày để liên quan đến một chẩn đoán cụ thể. Các thuật toán truyền thống không xử lý hiệu quả khoảng cách thời gian này. Điều này làm giảm tính chính xác và hữu ích của các mẫu tìm được. Nhu cầu về các phương pháp khai phá dữ liệu mới, mạnh mẽ hơn là rõ ràng. Luận án này giải quyết các thách thức đó. Nó tập trung vào khai phá mẫu dãy có trọng số. Nó cũng xem xét khoảng cách thời gian. Mục tiêu là tìm ra các mẫu có giá trị thực sự cao.

Khai phá mẫu dãy có trọng số (weighted sequential pattern mining) là một hướng nghiên cứu mới. Nó giải quyết hạn chế của khai phá mẫu trình tự truyền thống. Mỗi mục trong một dãy được gán một trọng số. Trọng số này phản ánh mức độ quan trọng hoặc giá trị của mục đó. Ví dụ, trong dữ liệu mua sắm, một mặt hàng đắt tiền có trọng số cao hơn một mặt hàng rẻ tiền. Mục tiêu là tìm các mẫu dãy mà tổng trọng số của các mục vượt qua một ngưỡng nhất định. Luận án này mở rộng khái niệm này. Nó tích hợp thêm khoảng cách thời gian. Điều này có nghĩa là các sự kiện trong một mẫu dãy không chỉ có trọng số. Chúng còn phải xảy ra trong một khoảng thời gian cụ thể. Ví dụ, một chuỗi hoạt động mạng có thể chỉ là một cuộc tấn công nếu các sự kiện xảy ra liên tục trong 5 phút. Nếu các sự kiện cách nhau quá xa, chúng có thể không liên quan. Điều này làm tăng độ chính xác và tính thực tiễn của các mẫu tìm được. Phương pháp này cung cấp một cái nhìn sâu sắc hơn vào dữ liệu. Nó giúp khám phá các mối quan hệ tiềm ẩn có ý nghĩa. Nó có ứng dụng rộng rãi trong nhiều lĩnh vực như học máy và phân tích chuỗi.

Luận án giới thiệu thuật toán TopKWFP (Top-K Weighted Frequent Pattern). Thuật toán này được thiết kế để khai phá top-k mẫu dãy thường xuyên trọng số. Nó hoạt động trong cơ sở dữ liệu dãy có khoảng cách thời gian. TopKWFP tìm kiếm các mẫu dãy có tổng trọng số cao nhất. Đồng thời, nó tuân thủ các ràng buộc về khoảng cách thời gian. Ý tưởng chính của TopKWFP là sử dụng chiến lược tìm kiếm hiệu quả. Nó kết hợp cây tiền tố và các kỹ thuật cắt tỉa thông minh. Điều này giúp giảm không gian tìm kiếm. Nó cũng cải thiện hiệu suất. Thuật toán này không yêu cầu ngưỡng hỗ trợ tối thiểu (minimum support threshold). Thay vào đó, nó tìm ra k mẫu có trọng số cao nhất. Điều này rất hữu ích khi người dùng không biết đặt ngưỡng hỗ trợ như thế nào. Phân tích thuật toán chứng minh tính đúng đắn và hiệu quả của nó. Thử nghiệm trên các bộ dữ liệu thực tế cho thấy hiệu năng vượt trội. TopKWFP có khả năng tìm kiếm mẫu nhanh chóng. Nó cũng sử dụng ít bộ nhớ hơn các phương pháp truyền thống.

Khai phá mẫu dãy lợi ích cao (high-utility sequential pattern mining) là một bước tiến xa hơn. Nó không chỉ xem xét trọng số của các mục. Nó còn tính đến "lợi ích" hay "lợi nhuận" của chúng. Lợi ích của một mục có thể là giá trị tiền tệ, mức độ quan trọng hoặc các tiêu chí khác. Một mẫu dãy có lợi ích cao là một chuỗi các mục có tổng lợi ích vượt quá một ngưỡng đã định. Khái niệm này đặc biệt hữu ích trong các ứng dụng kinh doanh. Ví dụ, trong thương mại điện tử, việc biết rằng khách hàng thường mua sản phẩm X, sau đó Y, rồi Z có lợi ích cao sẽ giúp tối ưu hóa chiến lược tiếp thị. Các thuật toán khai phá truyền thống có thể bỏ qua các mẫu như vậy. Chúng chỉ tập trung vào tần suất. Luận án này tích hợp thêm ràng buộc về khoảng cách thời gian. Điều này đảm bảo rằng các sự kiện trong mẫu dãy lợi ích cao phải xảy ra trong một khung thời gian hợp lý. Phương pháp này tăng cường khả năng khám phá các mối quan hệ có giá trị thực sự. Nó mở ra nhiều ứng dụng mới trong lĩnh vực học máy và phân tích chuỗi.

Luận án đề xuất hai thuật toán mới để giải quyết bài toán này. Thuật toán UIPrefixSpan (Utility-Indexed Prefix-Span) là một phương pháp khai phá mẫu dãy lợi ích cao có khoảng cách thời gian. Nó dựa trên cấu trúc PrefixSpan. Tuy nhiên, nó được tối ưu hóa để xử lý lợi ích và khoảng cách thời gian. UIPrefixSpan sử dụng các chiến lược cắt tỉa thông minh. Nó giảm thiểu không gian tìm kiếm. Nó cũng tránh tạo ra các ứng viên không tiềm năng. Ngoài ra, luận án còn giới thiệu thuật toán HUISP (High-Utility Itemset-based Sequential Pattern mining). Đây là một thuật toán khai phá mẫu dãy lợi ích cao một pha. HUISP có khả năng xử lý hiệu quả các cơ sở dữ liệu lớn. Nó không cần tạo ra nhiều tập ứng viên trung gian. Điều này giúp giảm đáng kể chi phí tính toán và bộ nhớ. Cả hai thuật toán đều được thiết kế để tìm kiếm mẫu dãy có trọng số cao và lợi ích lớn. Chúng cũng đảm bảo tuân thủ các ràng buộc về khoảng cách thời gian. Việc phân tích và thử nghiệm chứng minh hiệu quả của các thuật toán này. Chúng vượt trội hơn các phương pháp hiện có.

Để đánh giá hiệu quả của các thuật toán được đề xuất, các thử nghiệm kỹ lưỡng đã được tiến hành. Môi trường thử nghiệm bao gồm phần cứng và phần mềm tiêu chuẩn. Các thuật toán được triển khai bằng ngôn ngữ lập trình hiệu suất cao. Nhiều bộ dữ liệu khác nhau được sử dụng. Chúng bao gồm cả dữ liệu tổng hợp và dữ liệu thực tế. Dữ liệu tổng hợp giúp kiểm soát các tham số. Dữ liệu thực tế mô phỏng các tình huống ứng dụng thực tế. Các bộ dữ liệu này được chọn để kiểm tra thuật toán trong nhiều điều kiện khác nhau. Bao gồm các cơ sở dữ liệu có kích thước khác nhau. Chúng cũng có mật độ dữ liệu và phân phối trọng số đa dạng. Việc sử dụng các bộ dữ liệu này đảm bảo rằng kết quả đánh giá là toàn diện. Nó cũng đáng tin cậy. Mục tiêu là xác nhận khả năng khai phá dữ liệu của các thuật toán. Đồng thời, đánh giá hiệu năng về thời gian chạy và bộ nhớ sử dụng. Các tham số như k (trong TopKWFP) và ngưỡng lợi ích tối thiểu cũng được thay đổi. Điều này để phân tích ảnh hưởng của chúng lên hiệu suất.

Kết quả thực nghiệm cho thấy hiệu năng vượt trội của các thuật toán mới. Thuật toán TopKWFP chứng tỏ khả năng tìm kiếm top-k mẫu dãy có trọng số hiệu quả. Nó hoạt động tốt ngay cả trên các bộ dữ liệu lớn. So sánh với các phương pháp hiện có, TopKWFP đạt được thời gian chạy nhanh hơn. Nó cũng tiêu thụ ít bộ nhớ hơn. Đặc biệt, chiến lược cắt tỉa thông minh đã giảm đáng kể số lượng ứng viên cần tạo ra. Các thuật toán UIPrefixSpan và HUISP cũng thể hiện hiệu quả cao. Chúng thành công trong việc khai phá mẫu dãy lợi ích cao. Đồng thời, chúng tính đến khoảng cách thời gian. HUISP, với cách tiếp cận một pha, đặc biệt ấn tượng. Nó giảm chi phí tính toán đáng kể. Nó duy trì độ chính xác cao. Biểu đồ và bảng biểu trong luận án minh họa rõ ràng các cải tiến này. Chúng thể hiện thời gian chạy, bộ nhớ sử dụng, và số lượng mẫu tìm được. Các thử nghiệm chứng minh rằng các thuật toán này có khả năng mở rộng tốt. Chúng có thể xử lý các cơ sở dữ liệu lớn. Đây là một đóng góp quan trọng cho lĩnh vực khai phá dữ liệu và học máy.

Luận án đã đóng góp đáng kể vào lĩnh vực khai phá dữ liệu (data mining) và ngành máy tính. Đầu tiên, nó định nghĩa và giải quyết bài toán khai phá mẫu dãy có trọng số. Đồng thời, nó tích hợp khoảng cách thời gian. Đây là một yếu tố quan trọng mà các nghiên cứu trước đây thường bỏ qua. Thứ hai, luận án đề xuất thuật toán TopKWFP. Thuật toán này hiệu quả trong việc tìm kiếm top-k mẫu dãy thường xuyên trọng số. Nó không yêu cầu ngưỡng hỗ trợ cố định. Thứ ba, luận án giới thiệu hai thuật toán tiên tiến. Đó là UIPrefixSpan và HUISP. Các thuật toán này giải quyết bài toán khai phá mẫu dãy lợi ích cao. Chúng cũng xem xét khoảng cách thời gian. Những thuật toán này thể hiện hiệu năng vượt trội về thời gian chạy và bộ nhớ. Chúng cũng có khả năng mở rộng tốt. Các đóng góp này mang lại các công cụ mạnh mẽ hơn. Chúng giúp các nhà khoa học và chuyên gia phân tích dữ liệu khám phá tri thức sâu sắc hơn. Đặc biệt, nó hữu ích trong các ứng dụng thực tế nơi trọng số và thời gian là then chốt. Luận án làm sâu sắc thêm hiểu biết về khai phá mẫu trình tự.

Các kết quả trong luận án mở ra nhiều hướng nghiên cứu tiềm năng trong tương lai. Một hướng là mở rộng các thuật toán đã đề xuất. Điều này nhằm xử lý các loại dữ liệu dãy phức tạp hơn. Ví dụ, dữ liệu dãy không chắc chắn hoặc dữ liệu dãy mờ. Một hướng khác là tích hợp các yếu tố ngữ cảnh. Các yếu tố này có thể ảnh hưởng đến trọng số hoặc lợi ích của các mục. Điều này sẽ làm cho các mẫu tìm được càng thêm ý nghĩa. Nghiên cứu cũng có thể tập trung vào việc phát triển các thuật toán song song. Hoặc là phân tán cho khai phá mẫu dãy. Điều này nhằm xử lý các tập dữ liệu cực lớn. Chúng không thể chứa trong một máy tính đơn. Áp dụng các kỹ thuật học máy (machine learning) để tự động hóa việc xác định trọng số. Hoặc là ngưỡng lợi ích cũng là một lĩnh vực hứa hẹn. Cuối cùng, việc phát triển các ứng dụng thực tế. Các ứng dụng này sử dụng các kỹ thuật khai phá mẫu dãy có trọng số. Đặc biệt trong các lĩnh vực mới như IoT và y tế thông minh, là rất quan trọng. Đây sẽ là những đóng góp tiếp theo cho lĩnh vực khai phá dữ liệu và phân tích chuỗi.