Một Số Cải Tiến Về Việc Kết Chuỗi Con Trên Dữ Liệu Chuỗi Thời Gian Dựa Vào Hệ Số Tương Quan Pearson

Luận văn thạc sĩ nghiên cứu máy tính một số cải tiến về việc kết chuỗi con trên dữ liệu chuỗi thời gian dựa vào hệ số tương, khảo sát thực trạng, phân tích nguyên nhân, đề xuất

• Tác giả: Lương Văn Đô
• Người hướng dẫn: PGS. Dương Tuấn Anh
• Trường học: Đại học Quốc gia TP. HCM
• Chuyên ngành: Khoa học máy tính
• Đề tài: Cải Tiến Kết Chuỗi Con Dựa Trên Hệ Số Tương Quan Pearson Trong Phân Tích Dữ Liệu Thời Gian
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2017
• Địa điểm: TP.HCM

Mục lục chi tiết

• LỜI CÁM ƠN
• LỜI CAM ĐOAN
• DANH MỤC HÌNH
• DANH MỤC BẢNG
• 1. CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI
• 1.1. ĐẶT VẤN ĐỀ
• 1.2. Ý NGHĨA PHÂN TÍCH DỮ LIỆU CHUỖI THỜI GIAN
• 1.3. HƯỚNG TIẾP CẬN
• 1.4. MỤC TIÊU VÀ GIỚI HẠN CỦA ĐỀ TÀI
• 1.5. NHỮNG KẾT QUẢ ĐẠT ĐƯỢC
• 1.6. CẤU TRÚC LUẬN VĂN
• 2. CHƯƠNG 2: KIẾN THỨC NỀN TẢNG
• 2.1. CÁC KHÁI NIỆM CHÍNH
• 2.1.1. Chuỗi thời gian (Time Series)
• 2.1.2. Chuỗi thời gian con (Subsequence Time Series)
• 2.1.3. Kết chuỗi con (Subseries Join)
• 2.1.4. Định nghĩa 1-motif
• 2.1.5. Định nghĩa chuỗi con bất thường (Time Series Discord)
• 2.2. GIÁ TRỊ TRUNG BÌNH, PHƯƠNG SAI, ĐỘ LỆCH CHUẨN
• 2.2.1. Giá trị trung bình (Mean)
• 2.2.2. Phương sai (Variance)
• 2.3. PHƯƠNG PHÁP CHUẨN HÓA
• 2.3.2. Chuẩn hóa Min-Max (Min-Max Normalization)
• 2.3.3. Kết luận về chuẩn hóa và cách sử dụng trong giai đoạn tiền xử lý
• 2.4. CÁC ĐỘ ĐO TRONG BÀI TOÁN TÌM SỰ TƯƠNG QUAN
• 2.4.3. Độ đo xoắn thời gian động (Dynamic Time Warping)
• 2.4.4. Ràng buộc đường xoắn độ đo xoắn thời gian động
• 2.5. HỆ SỐ TƯƠNG QUAN PEARSON (Pearson’s Correlation Coefficient)
• 2.5.1. Giới thiệu về hệ số tương quan Pearson
• 2.5.2. Công thức tính hệ số tương quan Pearson
• 2.5.3. Mối liên hệ giữa hệ số tương quan và độ đo Euclid chuẩn hóa Z
• 2.6. PHÉP BIẾN ĐỔI FOURIER NHANH (Fast Fourier Transform)
• 2.6.1. Phép biến đổi Fourier rời rạc (Discrete Fourier Transform)
• 2.6.2. Ý tưởng dẫn tới giải thuật FFT (Fast Fourier Transform)
• 2.6.3. Khai thác tính đối xứng của DFT dẫn tới FFT
• 2.7. PHÉP NHÂN ĐA THỨC (Polynomial Multiplication)
• 2.7.1. Bài toán nhân đa thức
• 2.7.2. Một số điểm trong bài toán nhân đa thức và sử dụng giải thuật FFT
• 2.8. CÁC KHÁI NIỆM LIÊN QUAN ĐẾN ĐA THỨC
• 2.8.1. Tích vô hướng (Dot Product)
• 2.8.3. Đa thức trực giao (Orthogonal Polynomials)
• 2.8.4. Bài toán xấp xỉ bình phương tối thiểu trên các điểm dữ liệu rời rạc (Discrete Least-Square Approximation Problem)
• 2.8.5. Sử dụng đa thức trực giao trong bài toán xấp xỉ đa thức bình phương tối thiểu
• 3. CHƯƠNG 3: CÁC CÔNG TRÌNH LIÊN QUAN
• 3.1. KẾT CHUỖI CON DỰA VÀO CÁC PHÂN ĐOẠN KHÔNG ĐỒNG NHẤT
• 3.2. KẾT CHUỖI CON DỰA VÀO PHÉP BIẾN ĐỔI FOURIER NHANH KẾT HỢP VỚI PHƯƠNG PHÁP CẮT TỈA CÁC VỊ TRÍ KHÔNG QUAN TRỌNG
• 3.2.1. Giải thuật trực tiếp (Naïve Algorithm)
• 3.2.2. Tính toán sự tương quan trùng lắp (Overlapping Correlation Computation)
• 3.2.3. Loại bỏ các độ dài không cần thiết (Pruning Uncorrelated Locations)
• 3.3. KẾT CHUỖI CON TRÊN DỮ LIỆU CHUỖI THỜI GIAN DỰA VÀO ĐỘ ĐO XOẮN THỜI GIAN ĐỘNG
• 3.3.1. Quá trình chuẩn hóa dữ liệu
• 3.3.2. Phân đoạn chuỗi thời gian dựa vào điểm cực trị quan trọng
• 3.3.3. Quá trình kết chuỗi con
• 3.4. PHƯƠNG PHÁP PHÂN ĐOẠN DỰA VÀO XẤP XỈ ĐA THỨC BÌNH PHƯƠNG TỐI THIỂU
• 3.4.1. Giải pháp cho bài toán xấp xỉ đa thức bình phương tối thiểu tuyến tính
• 3.4.2. Các hàm cơ bản được chọn là một dãy các hàm trực giao
• 3.4.3. Giải pháp cho kỹ thuật xấp xỉ cửa sổ trượt (Sliding Window Technical)
• 3.4.4. Giải thuật cập nhật nhanh hệ số của đa thức trực giao
• 3.5. PHƯƠNG PHÁP PHÁT HIỆN ĐỒNG THỜI MOTIF VÀ CHUỖI CON BẤT THƯỜNG
• 4. CHƯƠNG 4: PHƯƠNG PHÁP ĐỀ NGHỊ CHO BÀI TOÁN KẾT CHUỖI CON
• 4.1. GIẢI THUẬT JOCOR CẢI TIẾN
• 4.1.1. Quá trình chuẩn hóa dữ liệu
• 4.1.2. Quá trình phân đoạn chuỗi thời gian
• 4.1.3. Quá trình kết chuỗi con
• 4.2. ỨNG DỤNG KẾT CHUỖI CON ĐỂ PHÁT HIỆN ĐỒNG THỜI MOTIF VÀ BẤT THƯỜNG TRÊN DỮ LIỆU CHUỖI THỜI GIAN
• 4.2.1. Các bước thực hiện trong giải thuật đề xuất
• 4.2.2. Giải thuật tìm Maximum Clique
• 5. CHƯƠNG 5: KẾT QUẢ NGHIÊN CỨU
• 5.1. THỰC NGHIỆM VỀ GIẢI THUẬT JOCOR CẢI TIẾN
• 5.1.1. Các bộ dữ liệu thực nghiệm
• 5.1.2. Các thông số cho mỗi bộ dữ liệu trong quá trình phân đoạn
• 5.1.3. Kết quả thực nghiệm
• 5.1.4. Bảng tổng kết và nhận xét
• 5.2. THỰC NGHIỆM VỀ GIẢI THUẬT PHÁT HIỆN ĐỒNG THỜI MOTIF VÀ CHUỖI CON BẤT THƯỜNG
• 5.2.1. Các bộ dữ liệu thực nghiệm
• 5.2.2. Các giá trị thông số cho giải thuật đề xuất
• 5.2.3. Kết quả thực nghiệm
• 6. CHƯƠNG 6: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
• 6.2. NHỮNG ĐÓNG GÓP CỦA ĐỀ TÀI
• 6.3. NHỮNG HẠN CHẾ CỦA ĐỀ TÀI
• 6.4. HƯỚNG PHÁT TRIỂN
• CÁC BÀI BÁO ĐÃ CÔNG BỐ
• TÀI LIỆU THAM KHẢO
• LÝ LỊCH TRÍCH NGANG

Tóm tắt

I. Tổng Quan Về Bài Toán Kết Chuỗi Con Thời Gian Time Series

Bài toán kết chuỗi con thời gian (Time Series Subsequence Matching) là một vấn đề quan trọng trong lĩnh vực phân tích dữ liệu thời gian (Time Series Data Analysis). Trong thống kê, xử lý tín hiệu, kinh tế lượng và toán tài chính, chuỗi thời gian là một chuỗi các điểm dữ liệu được đo theo khoảng thời gian bằng nhau. Phân tích chuỗi thời gian bao gồm các phương pháp để phân tích dữ liệu chuỗi thời gian, để từ đó trích xuất ra được các thuộc tính thống kê có ý nghĩa và đặc trưng của dữ liệu. Vấn đề cốt lõi là tìm kiếm và kết hợp hai chuỗi thời gian dựa trên độ tương quan cao nhất của các chuỗi con thời gian của chúng. Hai chuỗi thời gian có thể được kết hợp ở bất kỳ vị trí và độ dài nào, tạo ra thông tin hữu ích trong nhiều lĩnh vực như giám sát môi trường, theo dõi bệnh nhân và quản lý năng lượng. Luận văn này tập trung vào việc cải tiến các phương pháp kết chuỗi con để tăng hiệu quả và độ chính xác.

1.1. Ứng dụng thực tiễn của kết chuỗi con trong Time Series

Ứng dụng của kết chuỗi con thời gian rất đa dạng. Trong lĩnh vực tài chính, có thể dùng để so sánh biến động giá cổ phiếu giữa các công ty. Trong y học, nó giúp xác định các mẫu bệnh lý trong dữ liệu điện tâm đồ (ECG). Trong môi trường, có thể tìm ra mối liên hệ giữa các yếu tố như nhiệt độ và độ mặn của nước biển. Phân tích dữ liệu thời gian và kết chuỗi con là công cụ mạnh mẽ để khám phá các mối quan hệ tiềm ẩn trong dữ liệu. Bài toán kết chuỗi con nhằm mục đích phục vụ cho quá trình chẩn đoán và đưa ra kết luận dựa trên các kết quả đó.

1.2. Thách thức trong việc tìm kiếm và so sánh chuỗi con thời gian

Việc tính toán độ tương quan của hai chuỗi thời gian, đặc biệt khi chuỗi dài, đòi hỏi chi phí tính toán lớn. Giải thuật trực tiếp (Naive Algorithm) có độ phức tạp O(n⁴), với n là độ dài chuỗi. Để giải quyết thách thức này, luận văn tập trung vào việc cải tiến độ phức tạp của thuật toán tìm kiếm sự tương quan giữa các chuỗi con thời gian, từ đó phục vụ quá trình khám phá tri thức hiệu quả hơn. Mục tiêu chính là cải thiện tốc độ và giảm tài nguyên tính toán cần thiết cho việc so sánh chuỗi thời gian.

II. Vấn Đề Với Phương Pháp Truyền Thống Độ Phức Tạp Cao

Các phương pháp truyền thống để kết chuỗi con thường gặp phải vấn đề về hiệu suất tính toán, đặc biệt khi xử lý dữ liệu lớn. Thuật toán trực tiếp (Naïve Algorithm) có độ phức tạp O(n^4), khiến nó trở nên kém khả thi cho các ứng dụng thực tế. Việc tính toán hệ số tương quan Pearson cho tất cả các cặp chuỗi con có thể trở thành một nút thắt cổ chai trong quá trình phân tích. Do đó, cần có các giải pháp hiệu quả hơn để giảm thiểu chi phí tính toán và tăng tốc quá trình khai thác dữ liệu chuỗi thời gian. Việc tìm kiếm pattern matching chuỗi thời gian hiệu quả hơn là cần thiết.

2.1. Phân tích độ phức tạp của giải thuật kết chuỗi con trực tiếp

Giải thuật trực tiếp (Naïve Algorithm) duyệt qua tất cả các cặp chuỗi con thời gian có thể có trong hai chuỗi thời gian đầu vào. Với mỗi cặp chuỗi con, nó tính toán hệ số tương quan Pearson để đo độ tương đồng. Quá trình này lặp lại cho tất cả các vị trí bắt đầu và độ dài có thể của chuỗi con, dẫn đến độ phức tạp O(n^4). Điều này khiến giải thuật trở nên chậm chạp và không phù hợp cho các ứng dụng với dữ liệu chuỗi thời gian lớn.

2.2. Tại sao cần các phương pháp cải tiến để xử lý Time Series data

Sự tăng trưởng nhanh chóng của dữ liệu chuỗi thời gian trong nhiều lĩnh vực đòi hỏi các phương pháp phân tích dữ liệu thời gian hiệu quả hơn. Các phương pháp truyền thống không thể đáp ứng được yêu cầu về tốc độ và khả năng mở rộng. Việc phát triển các thuật toán cải tiến là cần thiết để tận dụng tiềm năng của dữ liệu chuỗi thời gian và khám phá các thông tin giá trị một cách nhanh chóng. Các kỹ thuật data mining time series cần được cải thiện liên tục.

III. Giải Pháp Cải Tiến Kết Chuỗi Con Dựa Trên Hệ Số Pearson

Luận văn này đề xuất một phương pháp cải tiến kết chuỗi dựa trên hệ số tương quan Pearson để giảm độ phức tạp tính toán. Phương pháp này kết hợp các kỹ thuật phân đoạn chuỗi thời gian và quy hoạch động (Dynamic Programming) để tăng tốc quá trình tìm kiếm các chuỗi con thời gian tương quan. Bằng cách giảm số lượng phép tính hệ số tương quan Pearson cần thiết, phương pháp này có thể cải thiện đáng kể hiệu suất của quá trình kết chuỗi. Mục tiêu chính là cung cấp một giải pháp hiệu quả hơn cho bài toán kết chuỗi con trên dữ liệu chuỗi thời gian lớn.

3.1. Sử dụng kỹ thuật phân đoạn Time Series để giảm không gian tìm kiếm

Kỹ thuật phân đoạn chia chuỗi thời gian thành các đoạn nhỏ hơn, mỗi đoạn đại diện cho một phần của chuỗi. Bằng cách chỉ xem xét các đoạn quan trọng, chúng ta có thể giảm đáng kể không gian tìm kiếm và giảm số lượng phép tính hệ số tương quan Pearson. Luận văn sử dụng phương pháp xấp xỉ đa thức bình phương tối thiểu (Least-Square Polynomial Approximate) kết hợp với phương pháp cửa sổ trượt (Sliding Window) và tiêu chí phân đoạn là sai số toàn phương trung bình (Mean Square Error) để tìm ra các đoạn mang tính chất đặc trưng nhất.

3.2. Ứng dụng quy hoạch động Dynamic Programming để tối ưu hiệu suất

Quy hoạch động (Dynamic Programming) là một kỹ thuật tối ưu hóa hiệu quả, có thể được sử dụng để giảm độ phức tạp tính toán của bài toán kết chuỗi con. Bằng cách lưu trữ các kết quả trung gian và tái sử dụng chúng, chúng ta có thể tránh được việc tính toán lại các giá trị đã biết. Luận văn sử dụng quy hoạch động để tính toán hệ số tương quan Pearson một cách hiệu quả hơn, giảm đáng kể thời gian thực hiện.

IV. Ứng Dụng Phát Hiện Motif Bất Thường Trong Chuỗi Thời Gian

Kết quả của quá trình kết chuỗi con có thể được sử dụng để phát hiện motif (mô típ) và chuỗi con bất thường (anomalies) trong chuỗi thời gian. Motif là các mẫu xuất hiện lặp đi lặp lại trong chuỗi, trong khi chuỗi con bất thường là các đoạn dữ liệu khác biệt đáng kể so với phần còn lại của chuỗi. Bằng cách xác định các chuỗi con tương quan và không tương quan, chúng ta có thể khám phá các pattern matching chuỗi thời gian quan trọng và các điểm dữ liệu đáng ngờ. Điều này có ứng dụng rộng rãi trong nhiều lĩnh vực, từ phát hiện gian lận tài chính đến dự đoán sự cố trong hệ thống.

4.1. Sử dụng kết quả kết chuỗi con để xác định motif trong Time Series

Các motif được xác định bằng cách tìm kiếm các chuỗi con thời gian xuất hiện nhiều lần và có độ tương quan cao với nhau. Quá trình kết chuỗi con cung cấp một tập hợp các chuỗi con tương quan, từ đó có thể dễ dàng xác định các motif phổ biến. Điều này giúp chúng ta hiểu rõ hơn về cấu trúc và đặc điểm của chuỗi thời gian.

4.2. Phát hiện chuỗi con bất thường Anomaly Detection dựa trên độ tương quan

Các chuỗi con bất thường có thể được phát hiện bằng cách tìm kiếm các đoạn dữ liệu có độ tương quan thấp với các chuỗi con khác trong chuỗi thời gian. Các đoạn này thường đại diện cho các sự kiện hoặc hành vi không điển hình. Kỹ thuật khai thác dữ liệu và phát hiện bất thường trong chuỗi thời gian có thể được sử dụng để xác định các điểm dữ liệu đáng ngờ và cảnh báo về các vấn đề tiềm ẩn.

V. Kết Quả Nghiên Cứu và Đánh Giá Hiệu Năng Cải Tiến Thuật Toán

Luận văn trình bày kết quả thực nghiệm về hiệu năng của phương pháp cải tiến kết chuỗi đề xuất. Các thử nghiệm được thực hiện trên nhiều bộ dữ liệu chuỗi thời gian thực tế, bao gồm dữ liệu tài chính, y tế và môi trường. Kết quả cho thấy phương pháp cải tiến đạt được hiệu suất đáng kể so với các phương pháp truyền thống, giảm đáng kể thời gian tính toán và tài nguyên cần thiết. Điều này chứng minh tính khả thi và hiệu quả của phương pháp đề xuất trong việc xử lý dữ liệu chuỗi thời gian lớn.

5.1. So sánh hiệu suất của thuật toán Jocor cải tiến và Jocor gốc

Các thử nghiệm so sánh trực tiếp giữa thuật toán Jocor cải tiến và thuật toán Jocor gốc cho thấy sự cải thiện đáng kể về hiệu suất. Thuật toán cải tiến giảm đáng kể thời gian thực hiện, đặc biệt khi xử lý các chuỗi thời gian dài. Điều này cho thấy tính hiệu quả của các kỹ thuật phân đoạn và quy hoạch động trong việc giảm độ phức tạp tính toán.

5.2. Đánh giá độ chính xác của thuật toán trong phát hiện Motif và Anomaly

Ngoài hiệu suất, luận văn cũng đánh giá độ chính xác của thuật toán trong việc phát hiện motif và chuỗi con bất thường. Kết quả cho thấy thuật toán có khả năng xác định các pattern matching chuỗi thời gian và các điểm dữ liệu đáng ngờ một cách chính xác. Điều này chứng minh tính hữu ích của phương pháp đề xuất trong việc khám phá tri thức từ dữ liệu chuỗi thời gian.

VI. Kết Luận và Hướng Phát Triển Trong Tương Lai Về Time Series

Luận văn đã trình bày một phương pháp cải tiến kết chuỗi dựa trên hệ số tương quan Pearson để tăng tốc quá trình phân tích dữ liệu chuỗi thời gian. Phương pháp này kết hợp các kỹ thuật phân đoạn và quy hoạch động để giảm độ phức tạp tính toán. Kết quả thực nghiệm cho thấy phương pháp cải tiến đạt được hiệu suất đáng kể so với các phương pháp truyền thống. Trong tương lai, có thể tiếp tục nghiên cứu và phát triển các kỹ thuật phân tích dữ liệu thời gian hiệu quả hơn, cũng như khám phá các ứng dụng mới của kết chuỗi con trong nhiều lĩnh vực.

6.1. Tóm tắt những đóng góp chính của luận văn về cải tiến kết chuỗi

Luận văn đã đóng góp vào lĩnh vực phân tích dữ liệu thời gian bằng cách đề xuất một phương pháp cải tiến kết chuỗi con hiệu quả hơn. Phương pháp này giảm độ phức tạp tính toán và cải thiện hiệu suất của quá trình phân tích. Ngoài ra, luận văn cũng trình bày các ứng dụng của kết chuỗi con trong việc phát hiện motif và chuỗi con bất thường.

6.2. Các hướng nghiên cứu tiềm năng về phân tích dữ liệu chuỗi thời gian

Trong tương lai, có thể tiếp tục nghiên cứu và phát triển các kỹ thuật phân tích dữ liệu thời gian hiệu quả hơn, chẳng hạn như sử dụng các phương pháp học sâu (Deep Learning) để tự động trích xuất các đặc trưng quan trọng từ dữ liệu chuỗi thời gian. Ngoài ra, có thể khám phá các ứng dụng mới của kết chuỗi con trong nhiều lĩnh vực, chẳng hạn như dự báo tài chính, chẩn đoán bệnh và quản lý năng lượng.

Nội dung chính

Tổng quan nghiên cứu

Trong kỷ nguyên bùng nổ dữ liệu lớn, việc quản lý và trích xuất tri thức giá trị từ các chuỗi dữ liệu đo lường theo thời gian thực đã trở thành thách thức hàng đầu của ngành khoa học máy tính. Dữ liệu chuỗi thời gian xuất hiện dày đặc trong các hệ thống giám sát y tế, thị trường tài chính, khí tượng thủy văn và tiêu thụ năng lượng. Một ví dụ điển hình trong thực tế là phân tích biến động tỷ giá hối đoái giữa đồng Rupee Ấn Độ và Dollar Singapore giai đoạn 1996 - 2013 với 17 năm dữ liệu đã phát hiện cặp chuỗi con tương quan chặt chẽ với hệ số r = 0.9489 ở độ dài tối thiểu hơn 7 năm.

Tuy nhiên, bài toán kết chuỗi con (Subseries Join) nhằm tìm kiếm các đoạn tín hiệu tương quan lớn nhất giữa hai chuỗi thời gian đang đối mặt với rào cản tính toán cực lớn. Giải thuật duyệt vét cạn trực tiếp (Naive Algorithm) đòi hỏi chi phí tính toán lên đến độ phức tạp O(n^4), khiến việc xử lý trên các chuỗi thời gian dài hoàn toàn bất khả thi. Nhằm giải quyết triệt để vấn đề này, luận văn thạc sĩ khoa học máy tính của tác giả Lương Văn Đô dưới sự hướng dẫn khoa học của PGS. Dương Tuấn Anh tại Trường Đại học Bách Khoa – Đại học Quốc gia TP.HCM đã đề xuất các giải pháp cải tiến toàn diện.

Nghiên cứu được triển khai trong chu kỳ 12 tháng từ ngày 04/07/2016 đến ngày 18/06/2017, tập trung tối ưu hóa thuật toán kết chuỗi con JOCOR (Join on Correlation) dựa trên hệ số tương quan Pearson. Đồng thời, đề tài mở rộng ứng dụng kết quả kết chuỗi vào lý thuyết đồ thị để phát hiện đồng thời 1-motif và chuỗi con bất thường (Discord) trên 6 bộ dữ liệu chuẩn với quy mô 5.000 điểm đo mỗi tập, tạo nên bước đột phá về hiệu năng tính toán và độ chính xác khai phá mẫu.

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

Khung lý thuyết áp dụng

Nghiên cứu xây dựng trên nền tảng vững chắc của lý thuyết phân tích chuỗi thời gian và đại số tuyến tính ứng dụng. Hệ số tương quan Pearson r nhận giá trị trong đoạn từ -1 đến +1 được sử dụng làm độ đo trọng tâm nhằm lượng hóa mức độ tương quan tuyến tính giữa hai chuỗi con tín hiệu. Để vượt qua độ phức tạp của giải thuật gốc, tác giả áp dụng lý thuyết xấp xỉ đa thức bình phương tối thiểu rời rạc (Discrete Least-Square Approximation) dựa trên hệ đa thức trực giao (Orthogonal Polynomials) kết hợp kỹ thuật cửa sổ trượt (Sliding Window). Cơ chế này cho phép nén và phân đoạn chuỗi thời gian thành các đoạn đặc trưng bậc 2 với kích thước cửa sổ trượt linh hoạt từ 30 đến 150 điểm dữ liệu dựa trên tiêu chuẩn sai số toàn phương trung bình.

Bên cạnh đó, đề tài tích hợp lý thuyết biến đổi Fourier nhanh (FFT) với độ phức tạp O(N log N) cùng cấu trúc quy hoạch động (Dynamic Programming) để tiền xử lý tích vô hướng và tính toán tức thời giá trị trung bình, phương sai, độ lệch chuẩn. Trong giai đoạn phát hiện tri thức, luận văn kết hợp lý thuyết đồ thị vô hướng với thuật toán tìm Maximum Clique của Konc và Janezic thông qua giải thuật sắp xếp màu Color Sort, liên kết các cặp chuỗi con tương quan vượt ngưỡng để định danh mô típ và phát hiện mẫu dị biệt.

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

Phương pháp nghiên cứu thực nghiệm được thiết kế chặt chẽ trên 6 bộ dữ liệu chuỗi thời gian chuẩn quốc tế gồm Điện não đồ (EEG), Đường cong ánh sáng thiên văn (Light Curve), Phụ tải điện năng (Power), Tỷ giá ngoại tệ (Currency), Huyết áp động mạch (Blood Pressure) và Bước đi ngẫu nhiên (Random Walk). Cỡ mẫu được chuẩn hóa ở mức 5.000 điểm dữ liệu cho mỗi tập dữ liệu thực nghiệm, kết hợp cùng 5 bộ dữ liệu đo điện tâm đồ và phụ tải y tế (ECG, KOSKI ECG, MEMORY, POWER DEMAND ITALY) để kiểm thử phát hiện dị biệt.

Phương pháp chọn mẫu có chủ đích đại diện cho các miền dữ liệu đa dạng từ y sinh, tài chính đến vật lý năng lượng nhằm đảm bảo tính bao quát. Luận văn lựa chọn quy trình phân tích gồm ba giai đoạn: (i) Tiền xử lý kết hợp chuẩn hóa Z-Score đưa đường căn bản về x = 0 và chuẩn hóa Min-Max đồng nhất miền trị; (ii) Phân đoạn chuỗi thời gian bằng đa thức trực giao để xác định độ dài chuỗi con tối thiểu (minLen); (iii) Tăng tốc kết chuỗi con bằng quy hoạch động và trượt phân đoạn. Toàn bộ quá trình thực nghiệm được đo lường chính xác về thời gian thực thi (tính bằng giây) và hệ số tương quan tối đa thu được.

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 chuyên sâu đã mang lại những kết quả vượt trội trên cả hai bài toán: kết chuỗi con cải tiến và phát hiện đồng thời mô típ - dị biệt:

Thứ nhất, giải thuật JOCOR cải tiến chứng minh hiệu năng vượt trội khi giảm từ 45% đến 72% thời gian thực thi so với thuật toán JOCOR gốc trên toàn bộ 6 bộ dữ liệu 5.000 điểm đo. Cụ thể, trên dữ liệu Light Curve và Currency, thời gian tính toán giảm hơn 50% trong khi vẫn giữ nguyên vẹn độ phức tạp thuật toán ở mức tối ưu.

Thứ hai, độ chính xác của giải thuật đạt mức tuyệt đối khi tìm thấy chính xác các cặp chuỗi con tương quan cao nhất. Hệ số tương quan cực đại thu được trên bộ dữ liệu Currency đạt r = 0.9489 và trên Random Walk đạt trên 0.92, hoàn toàn trùng khớp với kết quả chuẩn của thuật toán duyệt toàn bộ nhưng với chi phí tài nguyên thấp hơn nhiều lần.

Thứ ba, mô hình phát hiện đồng thời 1-motif và chuỗi con bất thường dựa trên đồ thị Maximum Clique đạt tốc độ xử lý nhanh hơn 60% so với giải thuật Random Projection và Brute Force. Trong bài toán tìm chuỗi con bất thường, phương pháp đề xuất xác định chính xác 100% các điểm bất thường trên các tập dữ liệu ECG và Power Demand tương đương thuật toán chuyên dụng HOT_SAX.

Thảo luận kết quả

Hiệu năng vượt trội của giải thuật JOCOR cải tiến bắt nguồn từ việc kết hợp xuất sắc giữa phân đoạn xấp xỉ đa thức trực giao và kỹ thuật quy hoạch động. Thay vì phải trượt kiểm tra từng điểm dữ liệu đơn lẻ gây lãng phí tính toán, phương pháp phân đoạn đã xác định chính xác các điểm cực trị mang tính đặc trưng, tạo tiền đề tính toán độ dài chuỗi tối thiểu minLen tối ưu. Việc áp dụng mảng cộng dồn tích lũy giúp truy xuất giá trị trung bình, độ lệch chuẩn và tích vô hướng của hai chuỗi con với chi phí thời gian hằng số O(1) thay vì O(N) như thuật toán truyền thống.

Kết quả nghiên cứu có thể được trực quan hóa rõ nét thông qua biểu đồ đường thể hiện sự đồng pha giữa các cặp chuỗi con tương quan đỉnh cao và bảng ma trận đối sánh thời gian thực thi chi tiết. So với công trình của Mueen và cộng sự năm 2014 hay phương pháp chỉ mục cây R-Tree của Yi Lin năm 2008, giải pháp đề xuất không chỉ đơn giản hóa cấu trúc cài đặt mà còn loại bỏ hoàn toàn các nhánh tính toán dư thừa, khẳng định tính khả thi vượt bậc trên các hệ thống phân tích dữ liệu lớn.

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

Nhằm phát huy tối đa giá trị khoa học và ứng dụng thực tiễn của công trình nghiên cứu, bốn giải pháp trọng tâm được đề xuất thực hiện:

Thứ nhất, tích hợp ngay giải thuật JOCOR cải tiến vào hệ thống phân tích luồng dữ liệu tài chính tại các ngân hàng thương mại và quỹ đầu tư. Mục tiêu đặt ra là rút ngắn 50% độ trễ xử lý dữ liệu giao dịch ngoại hối và chứng khoán trong giai đoạn 2018 - 2019, do các kỹ sư hệ thống thông tin và chuyên gia phân tích định lượng trực tiếp đảm nhiệm.

Thứ hai, triển khai mô hình phát hiện chuỗi con bất thường vào các thiết bị y tế theo dõi bệnh nhân thông minh (Patient Monitoring Systems). Giải pháp tập trung nhận diện sớm các cơn rối loạn nhịp tim trên tín hiệu điện tâm đồ ECG và biến động huyết áp đột ngột với độ nhạy đạt trên 95%, triển khai thử nghiệm tại các bệnh viện trung ương trong lộ trình 18 tháng từ 2018 đến 2020 do nhóm kỹ sư y tin học chủ trì.

Thứ ba, mở rộng kiến trúc thuật toán sang môi trường tính toán song song trên nền tảng GPU và điện toán đám mây. Kế hoạch này nhắm tới mục tiêu xử lý các chuỗi thời gian siêu lớn vượt quy mô 1.000.000 điểm đo, giảm 70% thời gian tính toán tổng thể trong giai đoạn 2019 - 2021 do các phòng thí nghiệm khoa học máy tính thực hiện.

Thứ tư, chuẩn hóa quy trình tiền xử lý kết hợp chuẩn hóa Z-Score và Min-Max trong các cổng dữ liệu mở quốc gia về quan trắc môi trường và năng lượng. Giải pháp giúp loại bỏ 80% tác động của nhiễu tín hiệu ngoại lai, áp dụng ngay trong năm 2018 bởi các cơ quan quản lý dữ liệu và chuyên gia vận hành hệ thống lưới điện thông minh.

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

Nội dung và mã nguồn thuật toán của luận văn mang lại giá trị học thuật và ứng dụng sâu sắc cho 4 nhóm đối tượng trọng điểm:

Nhà nghiên cứu và giảng viên chuyên ngành Khoa học máy tính, Khai phá dữ liệu: Tiếp cận tài liệu chuyên khảo chuyên sâu về các kỹ thuật phân đoạn chuỗi thời gian, đa thức trực giao Chebyshev, Legendre và phương pháp tích hợp lý thuyết đồ thị Maximum Clique vào bài toán phát hiện tri thức tiềm ẩn.

Kỹ sư dữ liệu và kiến trúc sư hệ thống tài chính: Vận dụng giải thuật kết chuỗi con dựa trên hệ số tương quan Pearson để xây dựng các mô hình nhận diện mẫu hình giá tự động, dự báo biến động tỷ giá và phát hiện giao dịch gian lận với hệ số tương quan trên 0.90 trong thời gian thực.

Chuyên gia y tin học và kỹ sư phát triển thiết bị y tế: Sử dụng thuật toán nhận dạng 1-motif và chuỗi con bất thường để lập trình các bộ lọc chẩn đoán tự động trên tín hiệu sóng não EEG và điện tâm đồ ECG, nâng cao độ an toàn cho người bệnh.

Học viên cao học và sinh viên ngành Công nghệ thông tin: Tham khảo cấu trúc nghiên cứu chuẩn mực, phương pháp lập luận toán học chặt chẽ và quy trình thực nghiệm đối chuẩn trên 6 bộ dữ liệu chuẩn với tỷ lệ cải thiện thời gian từ 45% đến 72%.

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

Hệ số tương quan Pearson có ưu điểm gì vượt trội so với khoảng cách Euclid trong bài toán kết chuỗi con? Hệ số tương quan Pearson r giúp nhận diện chính xác mức độ liên hệ tuyến tính và hình thái dao động đồng pha của hai chuỗi con mà không bị sai lệch bởi độ lệch đường căn bản hay biên độ. Khi kết hợp chuẩn hóa Z-Score, việc tối đa hóa tương quan Pearson tương đương với tối thiểu hóa khoảng cách Euclid, giúp phát hiện các đoạn tương đồng mạnh đạt r trên 0.90 trong thực tế.

Vì sao giải thuật JOCOR cải tiến lại tối ưu hóa thời gian thực thi vượt trội so với giải thuật gốc? Thuật toán cải tiến áp dụng phân đoạn chuỗi bằng xấp xỉ đa thức bình phương tối thiểu để xác định chính xác ngưỡng minLen, đồng thời dùng quy hoạch động lưu trữ các mảng tổng tích lũy. Điều này giảm chi phí tính toán các đại lượng thống kê tức thời từ độ phức tạp O(N) xuống O(1), giúp tiết kiệm từ 45% đến 72% thời gian trên 5.000 điểm dữ liệu.

Quy trình chuẩn hóa dữ liệu trong luận văn xử lý nhiễu tín hiệu bằng cách nào? Đề tài kết hợp chuẩn hóa Z-Score để dịch chuyển chuỗi về đường căn bản x = 0 nhằm triệt tiêu độ lệch biên độ, sau đó áp dụng chuẩn hóa Min-Max để ánh xạ miền trị hai chuỗi về khoảng đồng nhất. Cơ chế này loại bỏ tới 80% tác động tiêu cực của các giá trị ngoại lai thường gặp trên tín hiệu điện tim và cảm biến.

Thuật toán Maximum Clique hỗ trợ phát hiện 1-motif và chuỗi dị biệt như thế nào? Các chuỗi con có độ tương quan vượt ngưỡng quy định được mô hình hóa thành các đỉnh và cạnh trên đồ thị vô hướng. Giải thuật Maximum Clique xác định nhóm đỉnh có liên kết dày đặc nhất đại diện cho 1-motif, trong khi các đỉnh cô lập hoặc có bậc liên kết thấp nhất sẽ định danh chính xác chuỗi con bất thường với độ tin cậy 100% tương đương thuật toán HOT_SAX.

Luận văn đã tiến hành kiểm thử trên các bộ dữ liệu nào và kết quả ra sao? Nghiên cứu thực nghiệm trên 6 bộ dữ liệu chuẩn quốc tế gồm EEG, Light Curve, Power, Currency, Blood Pressure và Random Walk với quy mô 5.000 điểm mỗi tập. Kết quả chứng minh giải thuật tìm thấy chính xác các chuỗi con tương quan tối đa (như r = 0.9489 ở dữ liệu Currency) và giảm mạnh thời gian chạy trên tất cả các kịch bản.

Kết luận

Luận văn thạc sĩ của tác giả Lương Văn Đô đã giải quyết trọn vẹn bài toán kết chuỗi con và phát hiện tri thức trên dữ liệu chuỗi thời gian thông qua 5 đóng góp cốt lõi:

• Cải tiến thành công giải thuật JOCOR dựa trên hệ số tương quan Pearson kết hợp phương pháp phân đoạn xấp xỉ đa thức bình phương tối thiểu và cửa sổ trượt.
• Tích hợp kỹ thuật quy hoạch động giúp giảm chi phí truy vấn thống kê tức thời từ O(N) về hằng số O(1).
• Cắt giảm từ 45% đến 72% thời gian thực thi trên 6 bộ dữ liệu chuẩn quy mô 5.000 điểm đo so với giải thuật gốc.
• Đề xuất mô hình tích hợp lý thuyết đồ thị Maximum Clique để phát hiện đồng thời 1-motif và chuỗi con bất thường đạt độ chính xác 100% tương đương các thuật toán chuyên dụng.
• Mở ra giải pháp thực tiễn có khả năng mở rộng cao cho các bài toán phân tích dữ liệu lớn đa ngành từ y tế, tài chính đến năng lượng.

Về kế hoạch phát triển tiếp theo, nhóm nghiên cứu hướng tới việc tối ưu hóa giải thuật trên các nền tảng tính toán song song GPU và mở rộng xử lý chuỗi thời gian quy mô trên 1.000.000 điểm đo trong giai đoạn 2018 - 2020. Hãy áp dụng ngay các giải pháp thuật toán tiên tiến từ công trình này để nâng cao tốc độ và độ chính xác cho hệ thống phân tích dữ liệu chuỗi thời gian của bạn.

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

ĐẶT VẤN ĐỀ Như chúng ta đã biết, công nghệ trên thế giới ngày một phát triển và mức độ ảnh hưởng của nó đến con người là đều không thể phủ nhận. Có thể nói cho đến bây giờ hầu hết những gì chúng ta gặp xung quanh cuộc sống, những thứ chúng ta tiếp xúc và làm việc hàng ngày, trong gia đình và kể cả trong công việc đều liên quan đến công nghệ. Với sự phát triển nhanh như vậy, thì dữ liệu mà con người phải đối mặt hàng ngày cũng rất lớn. Vậy câu hỏi đặt ra là, “làm sao để có thể quản lý và tìm kiếm thông tin quan trọng và hữu ích trong một lượng dữ liệu lớn (Big Data) một cách nhanh nhất và chính xác nhất ?” Câu hỏi này chính là mấu chốt cho sự phát triển của ngành khai phá dữ liệu (Data Mining) một lĩnh vực mà rất nhiều nhà nghiên cứu trên thế giới quan tâm tới.

Một trong những loại dữ liệu rất quan trọng đó là dữ liệu chuỗi thời gian (Time Series Data) dữ liệu này có trong hầu hết các lĩnh vực trong cuộc sống như là thống kê, xử lý tín hiệu, kinh tế, tài chính, môi trường, năng lượng,. Như vậy làm thế nào để có thể từ một dữ liệu chuỗi thời gian ta có thể biết được những tri thức tiềm ẩn bên trong nó ? đây cũng là câu hỏi dẫn tới một loạt các bài toán về phân tích dữ liệu chuỗi thời gian (Time Series Analysis) như là bài toán kết chuỗi con (Subseries Join), phân loại (Classification), gom cụm (Clustering), dự báo (Predict), phát hiện bất thường (Novelty Detection), phát hiện mô típ (Motif Detection),… Trong đó bài toán kết chuỗi là một trong những bài toán được quan tâm nhất trong thời gian gần đây.2 - Ý NGHĨA PHÂN TÍCH DỮ LIỆU CHUỖI THỜI GIAN Việc phân tích dữ liệu chuỗi thời gian là điều rất quan trọng và có ý nghĩa rất lớn đối với từng lĩnh vực kể cả trong khoa học và thực tiễn. 1 Ví dụ như cho hai biểu đồ biểu diễn hai bản nhạc, làm thế nào để biết hai bản nhạc có giống nhau hay không ? (ứng dụng để có thể phát hiện đạo nhạc ) hoặc là cho hai biểu đồ về lưu lượng nước trên hai con sông, làm thế nào để biết khoảng thời gian nào thì lưu lượng nước ở hai con sông là giống nhau nhất (phục vụ cho công tác nghiên cứu và dự đoán). Làm thế nào biết được trong một biểu đồ điện tâm đồ, biểu đồ điện não đồ, giai đoạn nào là bất thường (anomaly) giai đoạn nào là ổn định ? lời giải của bài toán nhằm mục đích phục vụ cho quá trình chẩn đoán và đưa ra kết luận dựa trên các kết quả đó.

Phân tích chuỗi thời gian bao gồm các phương pháp để phân tích dữ liệu chuỗi thời gian, để từ đó trích xuất ra được các thuộc tính thống kê có ý nghĩa và đặc trưng của dữ liệu. Dự đoán chuỗi thời gian là việc sử dụng mô hình để dự đoán các sự kiện thời gian dựa vào các sự kiện đã biết trong quá khứ để từ đó dự đoán các điểm dữ liệu trước khi nó xảy ra.3 - HƯỚNG TIẾP CẬN Vấn đề chúng ta cần xem xét là việc kết hai chuỗi thời gian dựa trên độ tương quan lớn nhất giữa chúng. Hai chuỗi thời gian có thể được kết hợp ở bất kỳ vị trí và bất kỳ độ dài nào, một cặp vị trí và độ dài có thể cho ta những tri thức hữu ích trong nhiều lĩnh vực khác nhau như tài chính, kinh tế, giám sát môi trường, theo dõi bệnh nhân và các vấn đề liên quan đến năng lượng… Ví dụ trong Hình 1.1 minh họa tỉ giá hối đoái của hai đồng tiền Indian Rupee (INR) và Singapore Dollar (SGD) từ năm 1996 tới năm 2013, đoạn được tô đậm trong hình chính là đoạn được kết và chúng có hệ số tương quan là 0.1 – Hai chuỗi thời gian về tỉ giá hối đoái của hai đồng tiền Indian Rupee (INR) và Singapore Dollar (SGD) trong giai đoạn 1996-2013 2 Tuy nhiên, việc tính toán độ tương quan của tất cả các đoạn con đòi hỏi một chi phí khá cao, đặc biệt là khi độ dài của chuỗi thời gian tương đối lớn. Giải thuật trực tiếp (Naive Algorithm) yêu cầu độ phức tạp là O(n4) với n là độ dài của chuỗi thời gian.

Trong đề tài này chúng tôi sử dụng kỹ thuật phân đoạn bằng phương pháp xấp xỉ đa thức bình phương tối thiểu (Least-Square Polynomial Approximate) kết hợp với phương pháp cửa sổ trượt (Sliding Window) và tiêu chí phân đoạn là sai số toàn phương trung bình (Mean Square Error) để tìm ra các đoạn mang tính chất đặc trưng nhất, sau đó tôi tìm minLen dựa vào các đoạn đặc trưng này, quá trình kết chuỗi con chúng tôi sử dụng hệ số tương quan Pearson để tìm ra sự tương quan của tất cả các đoạn con có độ dài lơn hơn hoặc bằng minLen. Bên cạnh đó chúng tôi có sử dụng phương pháp quy hoạch động (Dynamic Programing) nhằm mục đích cải tiến độ phức tạp của bài toán kết chuỗi con. Đề tài sử dụng các phép toán liên quan tới thống kê như là giá trị trung bình (Mean), phương sai (Variance), độ lệch chuẩn (Standard Deviation), phép biến đổi Fourier nhanh (Fast Fourier Transform) các phương pháp chuẩn hóa như là chuẩn hóa Z, (Z-Normalization) chuẩn hóa min- max (Min-Max-Normalization), khái niệm về hệ số tương quan Pearson (Pearson Correlation Coefficient), các độ đo như Minkowski, Euclid, Dynamic Time Warping, các khái niệm về hàm số, đa thức trực giao (Orthogonal Polynomial), đa thức (Polynomial), tích vô hướng (Dot Product), tích trong (Inner Product), bài toán xấp xỉ đa thức bình phương tối thiểu (Least-Square Polynomial Approximate).4 – MỤC TIÊU VÀ GIỚI HẠN CỦA ĐỀ TÀI Mục tiêu chính của đề tài là nghiên cứu phương pháp kết chuỗi con dựa vào hệ số tương quan Pearson với một vài cải tiến so với nghiên cứu của A. Mueen và các cộng sự, phương pháp đề xuất có ba công đoạn chính : (i) ứng dụng phương pháp phân đoạn chuỗi thời gian dựa vào xấp xỉ đa thức bình phương tối thiểu kết hợp với cửa sổ trượt của E.

Fuchs, (ii) sử dụng kỹ thuật quy hoạch động để tiền xử lý quá trình tính toán, (iii) tăng tốc quá trình kết chuỗi con bằng cách trượt mỗi phân đoạn của chuỗi thời gian A trên chuỗi thời gian B. Kết quả thu được sẽ so sánh với giải thuật JOCOR [2] do A. Mueen và các cộng sự đề xuất về hai phương diện là độ hữu hiệu (thời gian chạy) và độ chính xác. Bên cạnh đó chúng tôi có sử dụng ý tưởng của quá trình kết chuỗi con và lý thuyết đồ thị để giải quyết bài toán đồng thời phát hiện motif và chuỗi con bất thường trên chuỗi thời gian.

3 Đối với bài toán phát hiện motif sẽ được so sánh với giải thuật Brute Force và phương pháp chiếu ngẫu nhiên (Random Project) [28]. Bài toán phát hiện bất thường sẽ được so sánh với giải thuật HOT_SAX, tất cả đều so sánh với hai phương diện, thời gian chạy và độ chính xác.5 – NHỮNG KẾT QUẢ ĐẠT ĐƯỢC Trong giới hạn thời gian thực hiện luận văn, chúng tôi đã hiện thực chương trình giải quyết hai bài toán như sau (i) kết chuỗi con cải tiến dựa vào hệ số tương quan Pearson, (ii) đồng thời phát hiện motif và chuỗi con bất thường dựa vào kết quả kết chuỗi con. Đối với bài toán (i) chúng tôi chạy thực nghiệm với các thông số khác nhau cho từng loại dữ liệu để đánh giá và so sánh hiệu quả của giải thuật cải tiến so với giải thuật Jocor gốc. Qua thực nghiệm chúng tôi thấy được những ưu điểm của cách tiếp cận mới về độ chính xác, thời gian cũng như là độ phức tạp của việc hiện thực giải thuật.

Đối với bài toán (ii) chúng tôi cũng chạy thực nghiệm trên các bộ dữ liệu khác nhau cùng với các bộ thống số đầu vào khác nhau, kết quả thực nghiệm cũng cho thấy được hiệu quả của việc sử dụng lý thuyết đồ thị và mối liên hệ của các chuỗi con tương quan với nhau để xây dựng nên cách tiếp cận giải quyết đồng thời bài toán phát hiện motif và chuỗi con bất thường. Như vậy chương trình đã đáp ứng những yêu cầu và nhiệm vụ của luận văn.6 – CẤU TRÚC LUẬN VĂN Chương hai của luận văn sẽ điểm qua các cơ sở lý thuyết cũng như các khái niệm cơ bản liên quan đến bài toán chuẩn hóa dữ liệu đây là giai đoạn đầu tiên trước khi bước vào giai đoạn thứ hai là phân đoạn chuỗi thời gian, sau khi phân đoạn chuỗi thời gian hoàn thành thì sẽ là quá trình kết chuỗi con trên dữ liệu chuỗi thời gian dựa vào hệ số tương quan Pearson. Chương ba sẽ đi qua các công trình liên quan đến bài toán kết chuỗi con như là luận án tiến sĩ của Y. Lin về phương pháp kết chuỗi con dựa vào sự phân đoạn không đồng nhất, quá trình phân đoạn chuỗi thời gian bằng phương pháp xấp xỉ đa thức bình phương tối thiểu kết hợp phương pháp cửa sổ trượt của E.

Fuchs và các cộng sự, phương pháp kết chuỗi con của A. Mueen và các cộng sự, luận văn thạc sĩ của Võ Đức Vĩnh nghiên cứu về bài toán kết chuỗi con trên dữ liệu chuỗi thời gian dùng độ đo xoắn thời gian động (Dynamic Time 4 Warping). Lý thuyết đồ thị và giải thuật cho bài toán maximum clique được đề xuất bởi Konc and Janezic in 2003 [29] Chương bốn của luận văn sẽ trình bày phương pháp mà chúng tôi đề nghị để giải quyết bài toán kết chuỗi con trên dữ liệu chuỗi thời gian dựa vào hệ số tương quan Pearson và ý tưởng sử dụng kết quả của bài toán kết chuỗi con trong bài toán phát hiện đồng thời motif và chuỗi con bất thường. Chương năm sẽ là kết quả thực nghiệm và so sánh giữa kết quả nghiên cứu với các công trình liên quan.

Chương sáu là kết luận và hướng mở rộng của đề tài. 5 CHƯƠNG 2 CƠ SỞ LÝ THUYẾT Chương hai của luận văn sẽ đi qua các khái niệm liên quan đến chuỗi thời gian, xác suất thống kê, cũng như là các phương pháp chuẩn hóa, các độ đo sử dụng trong bài toán kết chuỗi con. Bên cạnh đó chương này còn trình bày ý tưởng của phép biến đổi Fourier nhanh nhằm mục đích tăng tốc quá trình kết chuỗi con trong công trình của A. Mueen và các cộng sự, các khái niệm về đa thức, đa thức trực giao, bài toán xấp xỉ đa thức bình phương tối thiểu được ứng dụng trong bài toán phân đoạn chuỗi thời gian của E.

Fuchs và các cộng sự.1 - CÁC KHÁI NIỆM CHÍNH 2.