I. Giới thiệu đề tài
Luận văn thạc sĩ này tập trung vào khai phá dữ liệu trong cơ sở dữ liệu chuỗi thời gian, đặc biệt là mẫu phổ biến gia tăng. Chuỗi thời gian là chuỗi các giá trị đo lường tại các thời điểm cách đều nhau, được ứng dụng rộng rãi trong nhiều lĩnh vực như kinh tế, y tế, và môi trường. Với sự gia tăng dữ liệu theo thời gian, việc khai phá mẫu phổ biến trở nên phức tạp và cần thiết. Mục tiêu của đề tài là đề xuất phương pháp khai phá gia tăng mẫu phổ biến trong cơ sở dữ liệu chuỗi thời gian, cải tiến từ công trình nghiên cứu năm 2008. Ý nghĩa của đề tài nằm ở việc nâng cao hiệu suất khai phá dữ liệu, đặc biệt trong bối cảnh dữ liệu liên tục được cập nhật.
1.1. Vấn đề nghiên cứu
Dữ liệu chuỗi thời gian ngày càng phổ biến và quan trọng trong các ứng dụng thực tế. Tuy nhiên, việc dữ liệu gia tăng theo thời gian đặt ra thách thức lớn trong khai phá dữ liệu. Bài toán khai phá mẫu phổ biến gia tăng nhằm giải quyết vấn đề này bằng cách cập nhật các mẫu phổ biến khi dữ liệu mới được thêm vào. Đề tài tập trung vào việc cải tiến các kỹ thuật khai thác dữ liệu hiện có để tối ưu hóa quá trình này.
1.2. Mục tiêu và ý nghĩa
Mục tiêu chính của đề tài là phát triển phương pháp khai phá mẫu phổ biến gia tăng trong cơ sở dữ liệu chuỗi thời gian, đảm bảo hiệu suất cao cả về thời gian và không gian lưu trữ. Ý nghĩa khoa học của đề tài nằm ở việc đóng góp vào lĩnh vực còn ít được nghiên cứu này, trong khi ý nghĩa thực tiễn là cung cấp giải pháp hiệu quả cho các bài toán dự báo và phân tích dữ liệu trong thực tế.
II. Cơ sở lý thuyết
Chương này trình bày các khái niệm cơ bản về dữ liệu chuỗi thời gian, mẫu phổ biến, và khai phá dữ liệu. Chuỗi thời gian được định nghĩa là chuỗi các giá trị đo lường tại các thời điểm cách đều nhau, có thể là chuỗi đơn biến hoặc chuỗi đa biến. Mẫu phổ biến là các sự kiện hoặc chuỗi xuất hiện thường xuyên trong dữ liệu, được xác định dựa trên ngưỡng hỗ trợ tối thiểu. Khai phá mẫu phổ biến gia tăng là quá trình cập nhật các mẫu phổ biến khi dữ liệu mới được thêm vào, đảm bảo tính chính xác và kịp thời của kết quả.
2.1. Dữ liệu chuỗi thời gian
Chuỗi thời gian là chuỗi các giá trị đo lường tại các thời điểm cách đều nhau, được ứng dụng rộng rãi trong nhiều lĩnh vực. Chuỗi đơn biến chỉ chứa một quan sát tại mỗi thời điểm, trong khi chuỗi đa biến chứa nhiều quan sát. Chuỗi con là một dãy liên tiếp các giá trị trong chuỗi thời gian, được sử dụng trong các bài toán khai phá dữ liệu.
2.2. Khai phá mẫu phổ biến
Khai phá mẫu phổ biến là quá trình tìm ra các sự kiện hoặc chuỗi xuất hiện thường xuyên trong dữ liệu, dựa trên ngưỡng hỗ trợ tối thiểu. Khai phá mẫu phổ biến gia tăng là quá trình cập nhật các mẫu phổ biến khi dữ liệu mới được thêm vào, đảm bảo tính chính xác của kết quả. Các kỹ thuật khai thác dữ liệu như Apriori và FP-Growth thường được sử dụng trong quá trình này.
III. Các công trình nghiên cứu liên quan
Chương này tổng hợp các công trình nghiên cứu liên quan đến khai phá mẫu phổ biến và khai phá dữ liệu chuỗi thời gian. Các kỹ thuật thu giảm số chiều như PAA, PLA, và PCA được sử dụng để xử lý dữ liệu chuỗi thời gian. Các kỹ thuật rời rạc hóa như SAX và ESAX giúp chuyển đổi dữ liệu liên tục thành dữ liệu rời rạc. Các giải thuật khai phá mẫu tuần tự như GSP, SPADE, và PrefixSpan được sử dụng để tìm các mẫu tuần tự phổ biến. Các giải thuật khai phá gia tăng như ISM, IncSpan, và IncSP được đề xuất để cập nhật các mẫu phổ biến khi dữ liệu mới được thêm vào.
3.1. Kỹ thuật thu giảm số chiều
Các kỹ thuật thu giảm số chiều như PAA, PLA, và PCA được sử dụng để giảm kích thước dữ liệu chuỗi thời gian, giúp tối ưu hóa quá trình khai phá dữ liệu. PAA chia chuỗi thời gian thành các đoạn nhỏ và tính giá trị trung bình của mỗi đoạn. PLA sử dụng các đoạn thẳng để xấp xỉ chuỗi thời gian. PCA giảm số chiều dữ liệu bằng cách tìm các thành phần chính.
3.2. Kỹ thuật rời rạc hóa
Các kỹ thuật rời rạc hóa như SAX và ESAX chuyển đổi dữ liệu liên tục thành dữ liệu rời rạc, giúp đơn giản hóa quá trình khai phá dữ liệu. SAX chia chuỗi thời gian thành các đoạn và gán mỗi đoạn một ký hiệu. ESAX là phiên bản mở rộng của SAX, cho phép xử lý dữ liệu đa biến.
IV. Hướng tiếp cận giải quyết vấn đề
Chương này trình bày hướng tiếp cận của đề tài trong việc giải quyết bài toán khai phá mẫu phổ biến gia tăng trong cơ sở dữ liệu chuỗi thời gian. Đề tài tập trung vào việc cải tiến giải thuật Optimizied-Join từ công trình nghiên cứu năm 2008, đồng thời đề xuất giải pháp gia tăng theo chiều dọc cho cơ sở dữ liệu chuỗi thời gian. Môi trường giả lập được thiết lập để kiểm tra hiệu quả của các giải thuật trong các trường hợp gia tăng dữ liệu khác nhau.
4.1. Cải tiến giải thuật Optimizied Join
Đề tài cải tiến giải thuật Optimizied-Join bằng cách điều chỉnh một số bước trong quá trình thực hiện, đồng thời bổ sung giải pháp gia tăng theo chiều dọc cho cơ sở dữ liệu chuỗi thời gian. Giải thuật cải tiến được thiết kế để xử lý hiệu quả các trường hợp gia tăng dữ liệu, đảm bảo tính chính xác và kịp thời của kết quả.
4.2. Môi trường giả lập
Môi trường giả lập được thiết lập để kiểm tra hiệu quả của các giải thuật trong các trường hợp gia tăng dữ liệu khác nhau. Các bộ dữ liệu thực nghiệm được sử dụng để đánh giá hiệu suất của giải thuật cải tiến so với các giải thuật truyền thống như Brute-Force.
V. Thực nghiệm
Chương này trình bày quá trình thực nghiệm với các bộ dữ liệu khác nhau để đánh giá hiệu quả của giải thuật cải tiến. Các bộ dữ liệu bao gồm dữ liệu về số ca sinh nở ở California, số liệu về vết đen mặt trời, và một bộ dữ liệu mô phỏng. Kết quả thực nghiệm cho thấy giải thuật cải tiến có hiệu suất cao hơn so với giải thuật Brute-Force trong cả hai trường hợp gia tăng dữ liệu theo chiều ngang và chiều dọc.
5.1. Tiền xử lý dữ liệu
Các bộ dữ liệu thực nghiệm được tiền xử lý để chuẩn bị cho quá trình khai phá dữ liệu. Các bước tiền xử lý bao gồm làm sạch dữ liệu, chuẩn hóa dữ liệu, và chia dữ liệu thành các chuỗi con để phục vụ cho bài toán khai phá mẫu phổ biến.
5.2. Kết quả thực nghiệm
Kết quả thực nghiệm cho thấy giải thuật cải tiến có hiệu suất cao hơn so với giải thuật Brute-Force trong cả hai trường hợp gia tăng dữ liệu theo chiều ngang và chiều dọc. Giải thuật cải tiến cũng cho thấy khả năng xử lý hiệu quả các bộ dữ liệu lớn, đáp ứng nhu cầu thực tế.
VI. Kết luận
Luận văn thạc sĩ này đã đề xuất phương pháp khai phá mẫu phổ biến gia tăng trong cơ sở dữ liệu chuỗi thời gian, cải tiến từ công trình nghiên cứu năm 2008. Kết quả thực nghiệm cho thấy giải thuật cải tiến có hiệu suất cao hơn so với các giải thuật truyền thống. Hướng phát triển trong tương lai bao gồm việc áp dụng các kỹ thuật học máy để nâng cao hiệu quả của quá trình khai phá dữ liệu, cũng như mở rộng ứng dụng của phương pháp trong các lĩnh vực khác nhau.
6.1. Đóng góp của luận văn
Luận văn đã đóng góp vào lĩnh vực khai phá mẫu phổ biến gia tăng trong cơ sở dữ liệu chuỗi thời gian, cung cấp giải pháp hiệu quả cho các bài toán dự báo và phân tích dữ liệu trong thực tế. Giải thuật cải tiến được đề xuất đã chứng minh hiệu suất cao trong các thực nghiệm với các bộ dữ liệu khác nhau.
6.2. Hướng phát triển
Hướng phát triển trong tương lai bao gồm việc áp dụng các kỹ thuật học máy để nâng cao hiệu quả của quá trình khai phá dữ liệu, cũng như mở rộng ứng dụng của phương pháp trong các lĩnh vực khác nhau. Ngoài ra, việc tối ưu hóa giải thuật cải tiến để xử lý các bộ dữ liệu lớn hơn cũng là một hướng nghiên cứu tiềm năng.
