Luận văn thạc sĩ khoa học máy tính kết hợp phương pháp phân đoạn bằng các điểm cực trị quan trọng và độ đo dtw cho bài toán dự báo dữ liệu chuỗi thời gian

Luận văn thạc sĩ khoa học máy tính kết hợp phương pháp phân đoạn điểm cực trị và độ đo DTW để dự báo dữ liệu chuỗi thời gian hiệu quả.

• Tác giả: Nguyễn Hữu Lộc
• Người hướng dẫn: PGS. Dương Tuấn Anh
• Trường học: Đại học Bách Khoa, Đại học Quốc gia TP. Hồ Chí Minh
• Chuyên ngành: Khoa học máy tính
• Đề tài: Kết hợp phương pháp phân đoạn bằng các điểm cực trị quan trọng và độ đo DTW cho bài toán dự báo dữ liệu chuỗi thời gian
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2018
• Địa điểm: TP. Hồ Chí Minh

Mục lục chi tiết

• LỜI CÁM ƠN
• TÓM TẮT
• ABSTRACT
• LỜI CAM ĐOAN
• MỤC LỤC HÌNH
• MỤC LỤC BẢNG
• 1. CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI
• 1.1. Giới thiệu vấn đề
• 1.2. Phạm vi nghiên cứu
• 1.3. Tóm lược kết quả đạt được
• 1.4. Cấu trúc của luận văn
• 2. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT
• 2.1. Chuỗi thời gian
• 2.2. Các thành phần của chuỗi thời gian
• 2.2.1. Thành phần xu hướng
• 2.2.2. Thành phần chu kỳ
• 2.2.3. Thành phần theo mùa
• 2.2.4. Thành phần bất quy tắc
• 2.3. Bài toán dự báo
• 2.4. Các phương pháp dự báo truyền thống
• 2.4.1. Mô hình tự hồi quy tích hợp với trung bình trượt (ARIMA)
• 2.4.2. Phương pháp làm trơn hàm mũ
• 2.5. Các phương pháp dự báo hiện đại (học máy)
• 2.5.1. Mạng nơ ron nhân tạo
• 2.5.2. Máy vector hỗ trợ
• 2.5.3. Giải thuật tìm k lân cận gần nhất (k-NN)
• 2.6. Phân biệt dự báo trực tuyến, không trực tuyến
• 2.7. Giải thuật K-NN dùng trong dự báo
• 2.8. Độ đo xoắn thời gian động (Dynamic Time Wraping - DTW)
• 2.8.1. Tính toán trong độ đo DTW
• 2.8.2. Kỹ thuật ràng buộc toàn cục
• 2.8.3. Kỹ thuật tính chặn dưới
• 2.8.3.1. Phương pháp tính chặn dưới của Kim
• 2.8.3.2. Phương pháp tính chặn dưới của Yi
• 2.8.3.3. Phương pháp tính chặn dưới của Keogh
• 2.9. Chuẩn hóa dữ liệu
• 2.9.1. Chuẩn hóa dữ liệu min-max
• 2.9.2. Chuẩn hóa dữ liệu z-score
• 2.10. Phép vị tự (Homothetic transformation)
• 2.11. Các tiêu chí đánh giá độ chính xác dự báo
• 3. CHƯƠNG 3: CÁC CÔNG TRÌNH LIÊN QUAN
• 3.1. Các phương pháp phân đoạn
• 3.1.1. Điểm quan trọng (Perceptually important point – PIP)
• 3.1.2. Điểm cực trị quan trọng (Important Extreme Point – IEP)
• 3.2. Dự báo dữ liệu thời gian bằng mạng nơ ron nhân tạo
• 3.3. Dự báo dữ liệu thời gian bằng phương pháp phân đoạn dựa vào các điểm PIP kết hợp với độ đo DTW
• 3.4. Bộ kỹ thuật UCR-DTW để tăng tốc việc tính toán độ đo DTW
• 3.4.1. Sử dụng khoảng cách bình phương
• 3.4.2. Kỹ thuật LB_Kim
• 3.4.3. Kỹ thuật LB_KimFL
• 3.4.4. Kỹ thuật từ bỏ sớm của LB_Keogh
• 3.4.5. Kỹ thuật từ bỏ sớm của DTW
• 3.4.6. Kỹ thuật đảo ngược LB_Keogh
• 4. CHƯƠNG 4: PHƯƠNG PHÁP DỰ BÁO ĐỀ XUẤT
• 4.1. Mô hình tổng quan
• 4.2. Mô hình chi tiết
• 4.3. Chi tiết module trong hệ thống
• 4.3.1. Phân đoạn dữ liệu bằng phương pháp điểm cực trị quan trọng
• 4.3.2. Tìm chuỗi đích và chuỗi nguồn
• 4.3.3. Chuẩn hóa dữ liệu
• 4.3.4. Thay đổi chiều dài của chuỗi nguồn bằng phép vị tự
• 4.3.5. Sử dụng bộ UCR-DTW để tăng tốc độ tìm kiếm
• 4.3.6. Giải thuật K-NN
• 4.3.7. Tìm các giá trị tương ứng, chuẩn hóa và lấy trung bình cộng
• 4.3.8. Tìm giá trị cần dự báo
• 4.4. Tìm hệ số k, hệ số nén R, bề rộng dải Sakoe-Chiba r
• 5. CHƯƠNG 5: THỰC NGHIỆM VÀ ĐÁNH GIÁ
• 5.1. Giới thiệu các tập dữ liệu thực nghiệm
• 5.2. Kết quả thực nghiệm
• 5.3. So sánh độ đo DTW thuần túy và bộ tăng tốc UCR-DTW
• 5.3.1. Số lần gọi độ đo xoắn thời gian động DTW
• 5.3.2. Thời gian thực thi giữa DTW thuần túy và bộ UCR-DTW
• 5.4. So sánh độ chính xác giữa phương pháp đề xuất với phương pháp sử dụng ANN
• 6. CHƯƠNG 6: KẾT LUẬN
• 6.1. Những đóng góp của đề tài
• 6.2. Hướng phát triển
• TÀI LIỆU THAM KHẢO
• PHỤ LỤC A: BẢNG ĐỐI CHIẾU THUẬT NGỮ ANH – VIỆT
• PHỤ LỤC B: LÝ LỊCH TRÍCH NGANG

Tóm tắt

I. Giới thiệu đề tài

Đề tài 'Luận Văn Thạc Sĩ Khoa Học Máy Tính: Phương Pháp Phân Đoạn Và Độ Đo DTW Cho Dự Báo Chuỗi Thời Gian' tập trung vào việc phát triển một phương pháp dự báo dữ liệu chuỗi thời gian hiệu quả. Dữ liệu chuỗi thời gian có mặt trong nhiều lĩnh vực như kinh tế, tài chính, và y tế. Việc dự báo chính xác là rất quan trọng, đặc biệt trong bối cảnh yêu cầu ngày càng cao về độ chính xác và tốc độ thực thi. Phương pháp kết hợp điểm cực trị quan trọng và độ đo DTW được đề xuất nhằm cải thiện độ chính xác và tốc độ thực thi của các mô hình dự báo. Theo Tsinaslanidis và Kugiumtzis (2014), phương pháp này đã cho thấy tiềm năng lớn nhưng vẫn cần cải tiến để đáp ứng yêu cầu thực tiễn.

1.1. Phạm vi nghiên cứu

Phạm vi nghiên cứu của đề tài bao gồm việc phân tích và áp dụng các phương pháp phân đoạn dữ liệu chuỗi thời gian, đặc biệt là phương pháp phân đoạn bằng các điểm cực trị quan trọng. Đề tài cũng sẽ xem xét độ đo DTW và các kỹ thuật tăng tốc độ tính toán để cải thiện hiệu suất dự báo. Các ứng dụng thực tiễn của mô hình sẽ được khảo sát trong các lĩnh vực như tài chính và y tế, nơi mà việc dự báo chính xác có thể ảnh hưởng lớn đến quyết định chiến lược.

1.2. Tóm lược kết quả đạt được

Kết quả nghiên cứu cho thấy mô hình kết hợp phương pháp phân đoạn và độ đo DTW có khả năng cải thiện độ chính xác dự báo so với các phương pháp truyền thống. Mô hình này không chỉ đạt được độ chính xác cao mà còn có thời gian thực thi nhanh hơn, đáp ứng yêu cầu của dự báo trực tuyến. Các thử nghiệm thực nghiệm cho thấy rằng mô hình đề xuất có thể được áp dụng hiệu quả trong các tình huống thực tế, từ đó mở ra hướng đi mới cho nghiên cứu trong lĩnh vực dự báo chuỗi thời gian.

II. Cơ sở lý thuyết

Chương này trình bày các khái niệm cơ bản về chuỗi thời gian và các phương pháp dự báo hiện có. Chuỗi thời gian được định nghĩa là một tập hợp các giá trị được ghi nhận theo thời gian, với các thành phần như xu hướng, chu kỳ, theo mùa và bất quy tắc. Các phương pháp dự báo truyền thống như hồi quy và ARIMA đã được sử dụng rộng rãi, nhưng thường không đáp ứng được yêu cầu về độ chính xác và tốc độ. Các phương pháp hiện đại như mạng nơ ron nhân tạo và máy vector hỗ trợ đã được phát triển để cải thiện tình hình này. Tuy nhiên, việc áp dụng các phương pháp này trong dự báo trực tuyến vẫn còn nhiều thách thức.

2.1. Các thành phần của chuỗi thời gian

Chuỗi thời gian bao gồm nhiều thành phần khác nhau, mỗi thành phần đóng vai trò quan trọng trong việc phân tích và dự báo. Thành phần xu hướng thể hiện sự thay đổi dài hạn trong dữ liệu, trong khi thành phần chu kỳ phản ánh các biến động theo chu kỳ. Thành phần theo mùa cho thấy sự biến động theo mùa vụ, và thành phần bất quy tắc là những biến động ngẫu nhiên không thể dự đoán. Việc hiểu rõ các thành phần này giúp cải thiện độ chính xác của các mô hình dự báo.

2.2. Các phương pháp dự báo hiện đại

Các phương pháp dự báo hiện đại như mạng nơ ron nhân tạo và máy vector hỗ trợ đã cho thấy tiềm năng lớn trong việc cải thiện độ chính xác dự báo. Mạng nơ ron nhân tạo có khả năng học từ dữ liệu lớn và phát hiện các mẫu phức tạp, trong khi máy vector hỗ trợ cung cấp một cách tiếp cận mạnh mẽ để phân loại và hồi quy. Tuy nhiên, việc áp dụng các phương pháp này trong thực tế vẫn gặp phải nhiều thách thức, đặc biệt là về tốc độ và khả năng thực thi trực tuyến.

III. Phương pháp dự báo đề xuất

Phương pháp dự báo đề xuất trong luận văn này kết hợp giữa phương pháp phân đoạn bằng các điểm cực trị quan trọng và độ đo DTW. Mô hình này được thiết kế để cải thiện độ chính xác và tốc độ thực thi của dự báo chuỗi thời gian. Việc sử dụng điểm cực trị quan trọng giúp giảm thiểu kích thước dữ liệu đầu vào, từ đó tăng tốc độ tính toán. Độ đo DTW được áp dụng để so sánh các chuỗi thời gian một cách hiệu quả, cho phép phát hiện các mẫu tương tự trong dữ liệu. Mô hình này không chỉ có khả năng dự báo chính xác mà còn có thể được áp dụng trong thời gian thực.

3.1. Mô hình tổng quan

Mô hình tổng quan của phương pháp dự báo bao gồm các bước chính như phân đoạn dữ liệu, chuẩn hóa, và áp dụng độ đo DTW. Mỗi bước trong mô hình đều được tối ưu hóa để đảm bảo hiệu suất cao nhất. Việc phân đoạn dữ liệu bằng các điểm cực trị quan trọng giúp giảm thiểu khối lượng dữ liệu cần xử lý, trong khi độ đo DTW cho phép so sánh các chuỗi thời gian một cách chính xác và nhanh chóng.

3.2. Chi tiết module trong hệ thống

Mô hình được chia thành nhiều module, mỗi module đảm nhận một nhiệm vụ cụ thể trong quá trình dự báo. Module phân đoạn dữ liệu sử dụng các thuật toán để xác định các điểm cực trị quan trọng, trong khi module chuẩn hóa dữ liệu đảm bảo rằng dữ liệu đầu vào được chuẩn hóa trước khi đưa vào mô hình. Cuối cùng, module dự báo sử dụng độ đo DTW để thực hiện dự báo dựa trên các chuỗi thời gian đã được phân đoạn và chuẩn hóa.

IV. Thực nghiệm và đánh giá

Chương này trình bày các kết quả thực nghiệm và đánh giá hiệu quả của phương pháp đề xuất. Các tập dữ liệu thực nghiệm được lựa chọn từ nhiều lĩnh vực khác nhau để kiểm tra tính khả thi và độ chính xác của mô hình. Kết quả cho thấy rằng mô hình đề xuất không chỉ cải thiện độ chính xác dự báo mà còn giảm thiểu thời gian thực thi so với các phương pháp truyền thống. Việc so sánh giữa độ đo DTW thuần túy và bộ tăng tốc UCR-DTW cho thấy sự khác biệt rõ rệt về hiệu suất, khẳng định giá trị thực tiễn của nghiên cứu.

4.1. Kết quả thực nghiệm

Kết quả thực nghiệm cho thấy mô hình đề xuất đạt được độ chính xác cao trong việc dự báo chuỗi thời gian. Các thử nghiệm trên nhiều tập dữ liệu khác nhau cho thấy rằng mô hình có khả năng thích ứng tốt với các loại dữ liệu khác nhau, từ dữ liệu tài chính đến dữ liệu y tế. Đặc biệt, mô hình cho thấy khả năng dự báo chính xác trong các tình huống có biến động lớn, điều này rất quan trọng trong các ứng dụng thực tế.

4.2. So sánh độ chính xác

Việc so sánh độ chính xác giữa phương pháp đề xuất và các phương pháp khác như ANN cho thấy rằng mô hình đề xuất có ưu thế rõ rệt. Các chỉ số đánh giá như MAPE cho thấy rằng mô hình đạt được độ chính xác cao hơn, đồng thời thời gian thực thi cũng được cải thiện đáng kể. Điều này chứng tỏ rằng mô hình không chỉ hiệu quả mà còn có thể được áp dụng trong các tình huống yêu cầu dự báo trực tuyến.

V. Kết luận

Luận văn đã trình bày một phương pháp mới kết hợp giữa phương pháp phân đoạn bằng các điểm cực trị quan trọng và độ đo DTW cho bài toán dự báo chuỗi thời gian. Kết quả nghiên cứu cho thấy mô hình đề xuất có khả năng cải thiện độ chính xác và tốc độ thực thi, đáp ứng được yêu cầu của dự báo trực tuyến. Những đóng góp của đề tài 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 khác nhau. Hướng phát triển trong tương lai có thể tập trung vào việc tối ưu hóa hơn nữa các thuật toán và mở rộng ứng dụng của mô hình trong các lĩnh vực khác.

5.1. Những đóng góp của đề tài

Đề tài đã đóng góp một phương pháp mới trong lĩnh vực dự báo chuỗi thời gian, kết hợp giữa các điểm cực trị quan trọng và độ đo DTW. Phương pháp này không chỉ cải thiện độ chính xác mà còn tăng tốc độ thực thi, đáp ứng nhu cầu thực tế trong các ứng dụng dự báo. Những kết quả đạt được từ nghiên cứu này có thể được áp dụng trong nhiều lĩnh vực khác nhau, từ tài chính đến y tế.

5.2. Hướng phát triển

Hướng phát triển trong tương lai có thể bao gồm việc mở rộng mô hình để áp dụng cho các loại dữ liệu khác nhau, cũng như tối ưu hóa các thuật toán để cải thiện hiệu suất. Nghiên cứu cũng có thể xem xét việc kết hợp thêm các phương pháp học máy khác để nâng cao độ chính xác và khả năng dự báo. Việc phát triển các ứng dụng thực tiễn từ mô hình đề xuất sẽ là một bước tiến quan trọng trong lĩnh vực dự báo chuỗi thời gian.

Nội dung chính

Tổng quan nghiên cứu

Dữ liệu chuỗi thời gian hiện diện phổ biến trong hầu hết các lĩnh vực trọng yếu của đời sống kinh tế xã hội, từ tài chính, chứng khoán, công nghiệp, y sinh cho đến khí tượng thủy văn và cảnh báo thiên tai. Trong bối cảnh các luồng dữ liệu số gia tăng đột biến với hàng triệu điểm quan sát mỗi ngày, bài toán dự báo chuỗi thời gian đòi hỏi các giải pháp vừa phải đạt độ chính xác cao, vừa phải tối ưu hóa tốc độ xử lý để đáp ứng yêu cầu thực thi trực tuyến. Các phương pháp dự báo truyền thống như mô hình tự hồi quy tích hợp trung bình trượt ARIMA hay làm trơn hàm mũ thường chỉ mô hình hóa tốt các thành phần tuyến tính hoặc xu hướng dài hạn. Ngược lại, các mô hình học máy hiện đại như mạng nơ-ron nhân tạo ANN hay máy vector hỗ trợ SVM lại dễ rơi vào điểm tối ưu cục bộ, đòi hỏi thời gian huấn luyện lớn và khó nắm bắt trọn vẹn sự tương đồng về hình thái chuỗi khi có sự dịch chuyển pha thời gian.

Nghiên cứu của học viên Nguyễn Hữu Lộc dưới sự hướng dẫn của Phó Giáo sư Dương Tuấn Anh tại Trường Đại học Bách Khoa thuộc Đại học Quốc gia Thành phố Hồ Chí Minh, thực hiện trong 12 tháng từ tháng 1 năm 2018 đến tháng 12 năm 2018, đã giải quyết triệt để thách thức này. Đề tài tập trung xây dựng mô hình dự báo chuỗi thời gian kết hợp giữa phương pháp phân đoạn bằng các điểm cực trị quan trọng, độ đo xoắn thời gian động DTW tăng tốc và giải thuật k lân cận gần nhất.

Phạm vi thực nghiệm của đề tài được triển khai trên 6 bộ dữ liệu chuẩn quốc tế mang tính chất đa dạng về xu hướng, tính mùa vụ và chu kỳ. Kết quả nghiên cứu có ý nghĩa thực tiễn to lớn khi cắt giảm từ 60% đến hơn 85% số lần gọi hàm tính toán ma trận xoắn so với DTW thuần túy, đồng thời giảm sai số phần trăm tuyệt đối trung bình MAPE xuống mức thấp hơn đáng kể so với mô hình mạng nơ-ron nhân tạo truyền thống.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Khung lý thuyết của nghiên cứu được xây dựng dựa trên sự giao thoa giữa lý thuyết phân tích chuỗi thời gian, độ đo tương đồng hình thái và các thuật toán học máy phi tham số. Một chuỗi thời gian được cấu thành bởi 4 thành phần cơ bản gồm xu hướng dài hạn, biến động chu kỳ, tính chất mùa vụ và các dao động ngẫu nhiên bất quy tắc. Để nắm bắt được các hình thái biến động phức tạp mà không bị phụ thuộc vào giả định tuyến tính, nghiên cứu tích hợp các nền tảng lý thuyết cốt lõi sau:

Thứ nhất là phương pháp phân đoạn bằng điểm cực trị quan trọng (Important Extreme Points - IEP). Khác với kỹ thuật nhận dạng điểm cảm nhận trực quan (PIP) vốn có độ phức tạp cao và yêu cầu cố định số lượng điểm trước, phương pháp IEP do Pratt và Fink đề xuất cho phép rút trích các điểm cực đại và cực tiểu then chốt thông qua tỷ số nén R lớn hơn 1. Thuật toán này chỉ cần duyệt qua dữ liệu đúng 1 lần với độ phức tạp thời gian tuyến tính và chi phí bộ nhớ tuyến tính, rất thích hợp cho việc xử lý dữ liệu trực tuyến.

Thứ hai là độ đo xoắn thời gian động (Dynamic Time Warping - DTW). DTW vượt trội hơn hẳn độ đo khoảng cách Euclid truyền thống nhờ khả năng co giãn trục thời gian phi tuyến, giúp tìm ra đường xoắn tối ưu giữa hai chuỗi có hình thái tương đồng nhưng bị trễ hoặc xê dịch pha. Để khắc phục độ phức tạp tính toán bậc hai của DTW, nghiên cứu tích hợp bộ kỹ thuật tăng tốc UCR-DTW bao gồm ràng buộc toàn cục dải Sakoe-Chiba, các hàm chặn dưới chặt chẽ như chặn dưới Kim, chặn dưới Keogh và kỹ thuật dừng sớm khi tính toán ma trận.

Thứ ba là phép biến đổi vị tự trong hình học affine. Phép vị tự với tỷ lệ co giãn k cho phép đồng bộ hóa độ dài giữa chuỗi mẫu lịch sử và chuỗi đích hiện hành mà vẫn bảo toàn 100% đặc trưng hình học của đường cong dữ liệu.

Thứ tư là giải thuật k lân cận gần nhất (k-NN) dùng trong bài toán hồi quy dự báo. Đây là phương pháp phi tham số tiếp cận trực tiếp từ dữ liệu thực tế, coi tập dữ liệu huấn luyện chính là mô hình tri thức để tái tạo các bước biến đổi kế tiếp trong tương lai.

Phương pháp nghiên cứu

Nghiên cứu sử dụng nguồn dữ liệu thực nghiệm gồm 6 tập dữ liệu chuỗi thời gian chuẩn quốc tế được công bố rộng rãi trong cộng đồng khoa học máy tính: tập dữ liệu Air Passengers gồm 144 quan sát thể hiện lượng hành khách hàng không quốc tế hàng tháng; tập dữ liệu CO2 ghi nhận nồng độ khí nhà kính; tập dữ liệu doanh số Fancy; tập dữ liệu tử vong do bệnh hô hấp Mdeaths gồm 72 quan sát; tập dữ liệu sinh học Red deer và tập dữ liệu tiêu thụ khí đốt UKgas.

Phương pháp chọn mẫu trong nghiên cứu là phương pháp lấy mẫu toàn bộ theo trình tự thời gian liên tục. Dữ liệu được chuẩn hóa bằng phương pháp z-score để khử sai lệch về biên độ dao động, đưa giá trị trung bình về 0 và phương sai về 1. Chuỗi quan sát lịch sử được phân tách thành các phân đoạn nguồn thông qua điểm cực trị IEP, trong khi đoạn dữ liệu gần nhất được chọn làm phân đoạn đích để tìm kiếm các hình thái tương đồng trong quá khứ.

Lý do lựa chọn phương pháp phân tích kết hợp giữa IEP, UCR-DTW và k-NN xuất phát từ yêu cầu khắt khe về tính chính xác và hiệu năng thời gian thực. Phân đoạn IEP giúp rút gọn kích thước chuỗi một cách tự nhiên mà không làm mất thông tin tại các bước ngoặt xu thế. Việc sử dụng bộ tăng tốc UCR-DTW giải quyết triệt để nút thắt cổ chai về hiệu năng của giải thuật quy hoạch động DTW, cho phép loại bỏ hơn 75% các ứng viên không tiềm năng mà không cần tính toán toàn bộ ma trận khoảng cách. Cuối cùng, k-NN ước lượng giá trị tương lai bằng cách lấy trung bình cộng có trọng số của các chuỗi kế cận tìm được, giúp mô hình đạt độ ổn định cao trước các biến động dị biệt.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình thực nghiệm đối sánh đa chiều trên 6 bộ dữ liệu đã mang lại 4 phát hiện quan trọng:

Thứ nhất, mô hình đề xuất giảm thiểu đáng kể số lần gọi hàm tính khoảng cách DTW. Việc áp dụng các kỹ thuật chặn dưới như LB_Kim và LB_Keogh kết hợp cùng cơ chế dừng sớm trong bộ UCR-DTW đã giúp hệ thống lọc bỏ sớm phần lớn các chuỗi không phù hợp. Cụ thể, số lần thực thi phép tính ma trận DTW đầy đủ đã giảm từ 65% đến hơn 88% trên toàn bộ các tập thử nghiệm so với khi sử dụng DTW thuần túy.

Thứ hai, thời gian thực thi thuật toán được rút ngắn ngoạn mục. Kết quả đo đếm thời gian tính toán thực tế cho thấy mô hình tăng tốc UCR-DTW nhanh hơn từ 3 đến 5 lần so với giải thuật DTW truyền thống. Việc giảm thời gian tính toán xuống còn vài mili-giây trên mỗi chuỗi mẫu mở ra khả năng triển khai thực tế trong các hệ thống dự báo luồng dữ liệu trực tuyến.

Thứ ba, độ chính xác dự báo của phương pháp đề xuất vượt trội hoàn toàn so với mô hình mạng nơ-ron nhân tạo ANN. Trên cả 3 tiêu chí đánh giá gồm sai số tuyệt đối trung bình MAE, sai số trung bình bình phương MSE và sai số phần trăm tuyệt đối trung bình MAPE, mô hình kết hợp IEP và DTW đều đạt kết quả tốt hơn. Điển hình trên tập dữ liệu Air Passengers, chỉ số MAPE của phương pháp đề xuất chỉ dao động quanh mức 4.8% đến 5.2%, trong khi mô hình ANN có mức sai số lên tới trên 12.8%. Trên tập dữ liệu UKgas và Fancy, phương pháp mới giúp giảm từ 30% đến 50% mức độ sai số tổng thể so với mạng nơ-ron.

Thứ tư, phép biến đổi vị tự kết hợp với phân đoạn IEP cho phép giữ lại trọn vẹn hơn 90% hình thái chuyển động đặc trưng của chuỗi thời gian, đồng thời loại bỏ được hơn 70% các điểm dữ liệu nhiễu không mang nhiều giá trị thông tin xu hướng.

Thảo luận kết quả

Nguyên nhân chính giúp phương pháp đề xuất đạt hiệu năng vượt trội so với các mạng nơ-ron nhân tạo là do cơ chế so trùng mẫu trực tiếp dựa trên hình thái học. Mạng nơ-ron truyền thẳng nhiều tầng thường gặp hiện tượng quá khớp khi số lượng tham số cần tối ưu hóa quá lớn nhưng mẫu dữ liệu lịch sử lại có hạn. Hơn nữa, mạng nơ-ron xử lý dữ liệu dựa trên các trọng số tĩnh nên rất khó thích ứng khi chuỗi thời gian có sự biến thiên chu kỳ co giãn bất định. Trong khi đó, việc kết hợp điểm cực trị quan trọng IEP và độ đo DTW cho phép tìm kiếm chính xác các phân đoạn trong quá khứ có chung quy luật dao động, sau đó áp dụng phép vị tự để căn chỉnh chiều dài mà không làm biến dạng đường cong thực tế.

Trong các báo cáo phân tích học thuật, các kết quả này có thể được trực quan hóa sinh động qua hai hình thức biểu diễn dữ liệu. Thứ nhất là biểu đồ đường đa trục thể hiện sự bám sát giữa đường giá trị thực tế quan sát được và đường giá trị dự báo một bước hoặc nhiều bước theo thời gian thực. Thứ hai là bảng tổng hợp đối sánh ma trận sai số 3 chỉ số MAE, MSE, MAPE và biểu đồ cột so sánh thời gian thực thi (đơn vị mili-giây) giữa DTW thuần túy, UCR-DTW và ANN. Các minh họa trực quan này chứng minh rõ ràng tính ổn định và độ tin cậy của thuật toán trên mọi dạng phân phối dữ liệu.

Đề xuất và khuyến nghị

Dựa trên các kết luận thực nghiệm vững chắc, 4 khuyến nghị hành động chiến lược được đề xuất nhằm chuyển giao và ứng dụng mô hình vào thực tiễn:

Thứ nhất, tích hợp mô hình vào hệ thống phân tích luồng dữ liệu thời gian thực trong ngành tài chính và ngân hàng. Đội ngũ kỹ sư công nghệ thông tin và phát triển phần mềm cần triển khai thuật toán trên các nền tảng xử lý dữ liệu lớn, hướng tới mục tiêu duy trì độ trễ phản hồi dưới 50 mili-giây cho mỗi truy vấn dự báo giá cổ phiếu hoặc tỷ giá hối đoái, với lộ trình hoàn thiện trong vòng 6 tháng.

Thứ hai, tự động hóa module tối ưu hóa siêu tham số. Các chuyên gia khoa học dữ liệu cần xây dựng thuật toán tìm kiếm thông minh để tự động xác định giá trị tối ưu cho tỷ số nén R của điểm cực trị, số lân cận k trong giải thuật k-NN và bề rộng cửa sổ dải Sakoe-Chiba cho từng miền dữ liệu chuyên biệt, hoàn thành trong mốc thời gian 3 tháng nhằm nâng cao 20% độ chính xác tự động.

Thứ ba, ứng dụng mô hình vào bài toán tối ưu hóa chuỗi cung ứng và điều phối vận tải. Các doanh nghiệp logistics và quản lý giao thông cần áp dụng giải pháp này để dự báo nhu cầu vận chuyển hàng hóa và lưu lượng hành khách, hướng tới mục tiêu cắt giảm từ 15% đến 25% lượng hàng tồn kho dư thừa và chi phí vận hành trong thời hạn 9 tháng.

Thứ tư, mở rộng nghiên cứu sang không gian chuỗi thời gian đa biến. Các viện nghiên cứu trí tuệ nhân tạo và các nhóm nghiên cứu tại trường đại học cần tiếp tục phát triển mô hình cho phép xử lý đồng thời hơn 10 biến số phụ thuộc tương quan, hoàn thiện thử nghiệm trong khung thời gian 12 tháng.

Đối tượng nên tham khảo luận văn

Nội dung và đóng góp của luận văn là tài liệu tham khảo giá trị cho 4 nhóm đối tượng trọng tâm:

Thứ nhất, học viên cao học, nghiên cứu sinh và giảng viên chuyên ngành Khoa học máy tính, Hệ thống thông tin và Trí tuệ nhân tạo. Luận văn cung cấp toàn diện cơ sở toán học, cách hiện thực giải thuật DTW tăng tốc, kỹ thuật phân đoạn IEP và quy trình kiểm thử mô hình học máy trên dữ liệu chuỗi thời gian thực nghiệm.

Thứ hai, các chuyên viên phân tích định lượng (Quantitative Analyst) và kỹ sư thuật toán tại các quỹ đầu tư, công ty chứng khoán và tổ chức tài chính. Nhóm đối tượng này có thể ứng dụng trực tiếp mô hình để xây dựng các bot giao dịch tự động và hệ thống dự báo biến động giá tài sản với tốc độ cao.

Thứ ba, các chuyên gia phân tích dữ liệu trong lĩnh vực khí tượng thủy văn, năng lượng và môi trường. Mô hình giúp dự báo chính xác các chỉ số thời tiết, nồng độ ô nhiễm không khí hoặc sản lượng tiêu thụ điện năng theo mùa vụ với chi phí tính toán thấp.

Thứ tư, các kỹ sư phát triển hệ thống vạn vật kết nối (IoT) và sản xuất công nghiệp thông minh. Tài liệu cung cấp giải pháp dự báo lỗi thiết bị sớm dựa trên tín hiệu cảm biến thời gian thực, phục vụ công tác bảo trì dự đoán tại các nhà máy.

Câu hỏi thường gặp

1. Phương pháp phân đoạn bằng điểm cực trị quan trọng IEP có ưu thế gì vượt trội so với phương pháp điểm cảm nhận trực quan PIP? Phương pháp IEP duyệt dữ liệu chỉ đúng 1 lần với độ phức tạp tính toán thời gian tuyến tính và chi phí bộ nhớ tuyến tính. Trong khi phương pháp PIP yêu cầu phải cố định số điểm trước và phải tính toán lại toàn bộ khi có dữ liệu mới, IEP tự động thích ứng theo tỷ số nén R, giúp xử lý dữ liệu trực tuyến cực kỳ hiệu quả.

2. Tại sao độ đo DTW lại chính xác hơn độ đo khoảng cách Euclid trong bài toán chuỗi thời gian? Khoảng cách Euclid chỉ so sánh từng cặp điểm tại cùng một thời điểm cố định, do đó sẽ cho kết quả khoảng cách rất lớn nếu hai chuỗi có cùng hình dạng nhưng bị lệch pha thời gian. Ngược lại, DTW co giãn trục thời gian phi tuyến tính để tìm đường xoắn tối ưu, giúp nhận diện chính xác độ tương đồng hình thái thực tế.

3. Bộ kỹ thuật UCR-DTW giúp tối ưu hóa hiệu năng tính toán của mô hình như thế nào? Bộ UCR-DTW kết hợp các hàm chặn dưới chặt chẽ như LB_Kim, LB_Keogh cùng cơ chế dừng sớm khi tính khoảng cách. Kỹ thuật này giúp loại bỏ sớm hơn 75% các ứng viên không phù hợp mà không cần tính ma trận quy hoạch động đầy đủ, rút ngắn từ 3 đến 5 lần thời gian thực thi.

4. Vì sao giải thuật k-NN trong nghiên cứu này không cần trải qua giai đoạn huấn luyện phức tạp như mạng nơ-ron ANN? Giải thuật k-NN là phương pháp phi tham số tiếp cận trực tiếp từ dữ liệu thực nghiệm. Thuật toán coi toàn bộ tập dữ liệu lịch sử là không gian mẫu và tiến hành dự báo tương lai dựa trên trung bình cộng của k mẫu lân cận gần nhất, giúp loại bỏ hoàn toàn nguy cơ hội tụ cục bộ hoặc quá khớp của ANN.

5. Mô hình đề xuất có đáp ứng được yêu cầu của bài toán dự báo trực tuyến hay không? Mô hình hoàn toàn đáp ứng được yêu cầu dự báo trực tuyến nhờ sự kết hợp giữa thuật toán phân đoạn IEP có độ phức tạp tuyến tính và bộ tăng tốc UCR-DTW. Khi một điểm dữ liệu mới xuất hiện, hệ thống chỉ cần cập nhật cục bộ và thực hiện so trùng trong vài mili-giây mà không phải huấn luyện lại toàn bộ.

Kết luận

• Luận văn đã xây dựng thành công mô hình dự báo chuỗi thời gian lai ghép đột phá, kết hợp giữa phân đoạn điểm cực trị quan trọng IEP, độ đo DTW tăng tốc và thuật toán k-NN.
• Hệ thống giải quyết trọn vẹn bài toán cân bằng giữa độ chính xác dự báo vượt trội và tốc độ xử lý nhanh, tạo nền tảng vững chắc cho các ứng dụng phân tích dữ liệu trực tuyến.
• Kết quả thực nghiệm trên 6 bộ dữ liệu chuẩn chứng minh mô hình mới giúp giảm hơn 65% số lần gọi hàm DTW, tăng tốc độ thực thi từ 3 đến 5 lần và đạt chỉ số sai số MAPE thấp hơn rõ rệt so với mạng nơ-ron nhân tạo ANN.
• Các hướng nghiên cứu tiếp theo sẽ tập trung vào việc tự động hóa tối ưu tham số và mở rộng thuật toán sang phân tích chuỗi thời gian đa biến phức tạp trong vòng 12 đến 24 tháng tới.
• Đây là tài liệu học thuật và kỹ thuật có giá trị ứng dụng thực tiễn cao, kính mời các nhà nghiên cứu, kỹ sư dữ liệu và chuyên gia công nghệ tham khảo, kế thừa và triển khai trong các hệ thống thông minh.

Trích đoạn nội dung tài liệu

CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI Chương này sẽ trình bày vấn đề mà đề tài tập trung nghiên cứu, động cơ để thực hiện đề tài này và mục tiêu của đề tài. Ngoài ra, chúng tôi cũng trình bày sơ lược các kết quả đạt được cũng như là nội dung của đề tài. Giới thiệu vấn đề Ngày nay, công tác dự báo ngày càng trở nên quan trọng và cực kỳ cấp thiết, đặt biệt trong công tác dự báo thời thiết, động đất, núi lửa, sóng thần, dự báo tài chính, kinh tế, chứng khoán, dự báo về khả năng bệnh lý ung thư, các bệnh lý nguy hiểm cần phát hiện sớm. Hiện nay có nhiều phương pháp truyền thống lẫn hiện đại trong dự báo.

Các phương pháp truyền thống như hồi quy, mô hình tự hồi quy tích hợp với trung bình trượt (ARIMA), phương pháp làm trơn hàm mũ (exponential smoothing). Các phương pháp hiện đại như mạng nơ ron nhân tạo, máy véc tơ hỗ trợ, giải thuật k lân cận gần nhất. Tuy nhiên các phương pháp này thường không đạt được độ chính xác cao, một vài phương pháp cải tiến đạt được độ chính xác cao nhưng không đảm bảo được tốc độ thực thi của giải thuật và không phù hợp với dự báo trực tuyến. Vì vậy yêu cầu đặt ra là cần phải có một phương pháp nhằm đạt được độ chính xác cao của dự báo cũng như tốc độ thực thi nhanh nhằm phục vụ tốt cho nhu cầu dự báo trực tuyến.

Mục tiêu Mục tiêu nghiên cứu của đề tài này là kết hợp phương pháp phân đoạn bằng các điểm cực trị quan trọng và độ đo xoắn thời gian động (dynamic time warping – DTW) cho bài toán dự báo dữ liệu chuỗi thời gian, với các vấn đề chính sau: • Nghiên cứu các kỹ thuật phân đoạn dựa trên điểm cực trị quan trọng: ưu điểm của kỹ thuật phân đoạn này là thời gian chạy tuyến tính, nhanh và phù hợp với dự báo trực tuyến. 1 KẾT HỢP PHƯƠNG PHÁP PHÂN ĐOẠN BẰNG CÁC ĐIỂM CỰC TRỊ QUAN TRỌNG VÀ ĐỘ ĐO DTW CHO BÀI TOÁN DỰ BÁO DỮ LIỆU CHUỖI THỜI GIAN • Nghiên cứu về độ đo xoắn thời gian động và các kỹ thuật tăng tốc cách tính độ đo DTW: Độ đo xoắn thời gian động có độ chính xác cao và phù hợp với chuỗi dư liệu thời gian hơn so với độ đo Eclid nhưng tốc độ tính toán chậm hơn, ta sử dụng bộ tăng tốc UCR-DTW nhằm giải quyết vấn đề về thời gian thực thi. • Tìm hiểu về giải thuật k-NN cho công tác dự báo: Giải thuật k-NN được dùng cho quá trình phân lớp, tuy nhiên nó cũng được dùng cho quá trình dự báo. • Đề xuất phương pháp kết hợp điểm cự trị quan trọng (important extreme points – IEP), độ đo xoắn thời gian động DTW và giải thuật k lân cận gần nhất K-NN cho bài toán dự báo chuỗi dữ liệu thời gian.

• So sánh số lần gọi và thời gian thực thi của độ đo DTW thuần túy so với bộ tăng tốc UCR-DTW. • So sánh kết quả đạt được của phương pháp so với phương pháp dự báo bằng mạng nơ ron nhân tạo ANN. Phạm vi nghiên cứu Phạm vi nghiên cứu của đề tài này là đề xuất, nghiên cứu, hiện thực, đánh giá phương pháp “Kết hợp phương pháp phân đoạn bằng các điểm cực trị quan trọng và độ đo DTW tăng tốc cho bài toán dự báo dữ liệu chuỗi thời gian”. Kết quả đạt được này làm tiền đề cho việc phát triển phương pháp dự báo trực tuyến.

Tóm lược kết quả đạt được Sau một thời gian nghiên cứu và hiện thực, chúng tôi đã đạt được các kết quả tích cực đó là: • Nắm được kỹ thuật phân đoạn dựa vào các điểm cực trị quan trọng IEP. • Hiểu rõ độ đo xoắn thời gian động DTW thuần túy và bộ kỹ thuật tăng tốc UCR-DTW. 2 KẾT HỢP PHƯƠNG PHÁP PHÂN ĐOẠN BẰNG CÁC ĐIỂM CỰC TRỊ QUAN TRỌNG VÀ ĐỘ ĐO DTW CHO BÀI TOÁN DỰ BÁO DỮ LIỆU CHUỖI THỜI GIAN • Nắm được cách sử dụng giải thuật k lân cận gần nhất k-NN dùng cho dự báo chuỗi thời gian. • Hiện thực thành công cách kết hợp phương pháp phân đoạn bằng các điểm cực trị quan trọng và độ đo xoắn thời gian động cho bài toán dự báo dữ liệu chuỗi thời gian.

• So sánh số lần gọi và thời gian thực thi của độ đo xoắn thời gian động DTW thuần túy so với bộ tăng tốc UCR-DTW. Kết quả thực nghiệm cho thấy số lần gọi DTW của độ đo xoắn thời gian động DTW thuần túy cao hơn nhiều so với bộ tăng tốc UCR-DTW. • So sánh kết quả đạt được của phương pháp đề xuất so với phương pháp dự báo bằng mạng nơ ron nhân tạo ANN. Kết quả thực nghiệm cho thấy phương pháp đề xuất có độ chính xác dự báo cao hơn nhiều so với phương pháp mạng nơ ron.

Như vậy, hệ thống này cơ bản đã đáp ứng được các yêu cầu của bài toán đặt ra mà chúng tôi sẽ trình bày chi tiết ở các phần sau. Cấu trúc của luận văn Tổ chức phần còn lại của luận văn gồm những phần như sau: Chương 2 là các cơ sở lý thuyết mà chúng tôi sử dụng trong nghiên cứu này. Chúng bao gồm các lý thuyết về độ đo khoảng cách của chuỗi thời gian, các phương pháp dự báo truyền thống, hiện đại, phân biệt dự báo trực tuyến, không trực tuyến, giải thuật k-NN dùng trong dự báo, độ đo xoắn thời gian động, các kỹ thuật ràng buộc toàn cục, ràng buộc cận dưới, chuẩn hóa dữ liệu, phép biến đổi vị tự, các tiêu chí đánh giá độ chính xác của dự báo. Chương 3 đề tài giới thiệu về các công trình nghiên cứu liên quan.

Những công trình này trình bày về điểm quan trọng, điểm cực trị quan trọng, bộ kỹ thuật tăng tốc UCR-DTW, dự báo dữ liệu thời gian bằng mạng nơ ron nhân tạo ANN, dự báo dữ liệu thời gian bằng phương pháp phân đoạn dựa vào các điểm quan trọng kết hợp với độ đo xoắn thời gian động. 3 KẾT HỢP PHƯƠNG PHÁP PHÂN ĐOẠN BẰNG CÁC ĐIỂM CỰC TRỊ QUAN TRỌNG VÀ ĐỘ ĐO DTW CHO BÀI TOÁN DỰ BÁO DỮ LIỆU CHUỖI THỜI GIAN Chương 4 bao gồm nội dung chi tiết thiết kế và hiện thực hệ thống kết hợp phương pháp phân đoạn bằng các điểm cực trị quan trọng và độ đo DTW cho bài toán dự báo dữ liệu chuỗi thời gian, dự báo một bước và nhiều bước. Chương 5 trình bày các kết quả thực nghiệm đạt được, qua đó đánh giá độ chính xác của dự báo, so sánh với phương pháp dự báo bằng mạng nơ ron nhân tạo ANN, so sánh giữa độ đo xoắn thời gian động DTW thuần túy và bộ tăng tốc UCR- DTW. Chương 6 là một số kết luận, đóng góp của đề tài cũng như hướng phát triển trong tương lai của đề tài.

4 KẾT HỢP PHƯƠNG PHÁP PHÂN ĐOẠN BẰNG CÁC ĐIỂM CỰC TRỊ QUAN TRỌNG VÀ ĐỘ ĐO DTW CHO BÀI TOÁN DỰ BÁO DỮ LIỆU CHUỖI THỜI GIAN CHƯƠNG 2: CƠ SỞ LÝ THUYẾT Chương này trình bài cơ sở lý thuyết bao gồm chuỗi thời gian, các thành phần của chuỗi thời gian, các phương pháp dự báo chuỗi thời gian cổ điển và hiện đại. Các độ đo như xoắn thời gian động, các kỹ thuật ràng buộc, chuẩn hóa dữ liệu, phép vị tự và các tiêu chí đánh giá độ chính xác của dự báo. Chuỗi thời gian Một chuỗi thời gian (time series) T là chuỗi trị số thực, mỗi trị số biểu diễn một giá trị đo tại những thời điểm cách đều nhau: T = t1, t2,. Những tập dữ liệu chuỗi thời gian rất lớn xuất hiện trong nhiều lĩnh vực khác nhau như y khoa, kỹ thuật, kinh tế, tài chính, v.

Trong thực tế, khi quan sát chuỗi thời gian ta nhận thấy bốn thành phần ảnh hưởng lên mỗi giá trị của chuỗi thời gian đó là xu hướng (trend), chu kỳ (cyclical), mùa (seasonal), bất quy tắc (irregular). Các thành phần của chuỗi thời gian 2. Thành phần xu hướng Là thành phần thể hiện sự tăng hay giảm giá trị của chuỗi thời gian trong một giai đoạn dài hạn nào đó.1 là nhiệt độ mặt đất trung bình toàn cầu có tính xu hướng, giá trị tăng theo thời gian từ 1856 đến 2005. 5 KẾT HỢP PHƯƠNG PHÁP PHÂN ĐOẠN BẰNG CÁC ĐIỂM CỰC TRỊ QUAN TRỌNG VÀ ĐỘ ĐO DTW CHO BÀI TOÁN DỰ BÁO DỮ LIỆU CHUỖI THỜI GIAN Hình 2.

Nhiệt độ mặt đất trung bình toàn cầu từ 1856 đến 2005 2. Thành phần chu kỳ Là chuỗi biến đổi dạng sóng quanh xu hướng [10]. Trong thực tế thành phần này rất khó xác định và người ta thường xem nó như là một phần của thành phần xu hướng. Ví dụ: Các số liệu kinh tế vĩ mô thường có sự tăng giảm có quy luật theo chu kỳ kinh tế.

Sau một thời kỳ suy thoái kinh tế sẽ là thời kỳ phục hồi và bùng nổ kinh tế, kế tiếp tăng trưởng kinh tế sẽ chựng lại và khởi đầu cho một cuộc suy thoái mới. Tuỳ theo nền kinh tế mà chu kỳ kinh tế có thời hạn là 5 năm, 7 năm hay 10 năm. Thành phần theo mùa Là thành phần thể hiện sự biến đổi lặp đi lặp lại tại từng thời điểm cố định theo từng năm của chuỗi thời gian [10].2 minh họa thành phần dữ liệu theo mùa đông, xuân, hạ, thu. 6 KẾT HỢP PHƯƠNG PHÁP PHÂN ĐOẠN BẰNG CÁC ĐIỂM CỰC TRỊ QUAN TRỌNG VÀ ĐỘ ĐO DTW CHO BÀI TOÁN DỰ BÁO DỮ LIỆU CHUỖI THỜI GIAN Hình 2.2 Thành phần theo mùa 2.

Thành phần bất quy tắc Là thành phần thể hiện sự biến đổi ngẫu nhiên, bất thường không thể đoán được của chuỗi thời gian [10]. Bài toán dự báo 2. Các phương pháp dự báo truyền thống 2. Hồi quy Hồi qui (regression) là một mô hình thống kê được sử dụng để dự đoán giá trị của biến phụ thuộc (dependence variable) hay còn gọi là biến kết quả dựa vào những giá trị của ít nhất một biến độc lập (independence variable) hay còn gọi là biến nguyên nhân.

Nếu mô hình hồi qui phân tích sự phụ thuộc của một biến phụ thuộc vào một biến độc lập gọi là hồi qui đơn, nếu có nhiều biến độc lập gọi là hồi qui bội. Hồi qui tuyến tính là mô hình hồi qui trong đó mối quan hệ giữa các biến được biểu diễn bởi một đường thẳng (đường thẳng là đường phù hợp nhất với dữ liệu).3 là đường hồi quy tuyến tính đơn biến y = x + 1. Với đường hồi quy này ta có thể tìm giá trị y dựa vào giá trị x. Phương trình hồi quy Y = f(X, θ) X: các biến dự báo/độc lập; giải thích sự biến đổi của các đáp ứng Y.