Luận văn thạc sĩ khoa học máy tính rút trích luật dự báo từ dữ liệu chuỗi thời gian dựa vào mô típ và nguyên lý mdl

Khám phá luận văn thạc sĩ về rút trích luật dự báo từ dữ liệu chuỗi thời gian, ứng dụng mô típ và nguyên lý MDL trong khoa học máy tính.

• Tác giả: Lâm Tuấn Anh
• 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: Rút trích luật dự báo từ dữ liệu chuỗi thời gian dựa trên mô típ và nguyên lý MDL
• 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 LUẬN VĂN
• ABSTRACT
• LỜI CAM ĐOAN
• DANH MỤC HÌNH
• DANH MỤC BẢNG
• 1. CHƯƠNG 1: GIỚI THIỆU VẤN ĐỀ
• 1.1. Giới thiệu về Luật Dự Báo
• 1.2. Nguyên nhân dự báo
• 1.3. Phương pháp dự báo
• 1.4. Mục tiêu và giới hạn của đề tài
• 1.5. Các 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. Giới thiệu nguyên lý MDL
• 2.1.1. Ý tưởng chính của nguyên lý MDL
• 2.1.2. Ví dụ đơn giản về MDL
• 2.2. Chuỗi thời gian và các khái niệm liên quan
• 2.2.1. Chuỗi thời gian (Time Series)
• 2.2.2. Khung cửa sổ trượt (Sliding Window)
• 2.2.3. Cơ sở dữ liệu chuỗi thời gian (Time Series Database)
• 2.2.4. Trùng khớp tầm thường (Trivial Match)
• 2.2.5. Mô típ bậc K với độ sai lệch d (kí hiệu K-Motif(n, R, d))
• 2.2.6. Mô típ toàn chuỗi (Time Series Motif)
• 2.2.7. Mô Típ Toàn Chuỗi Bậc K của chuỗi thời gian (Kth Time Series Motif)
• 2.2.8. Tầm của mô típ (Motif Range)
• 2.2.9. Biến đổi chuỗi thời gian thành cơ sở dữ liệu chuỗi thời gian
• 2.2.10. Mô típ của chuỗi con
• 2.2.11. So sánh hai khái niệm mô típ bậc K của B
• 2.3. Bài toán phát hiện Mô típ
• 2.3.1. Giới thiệu bài toán Mô típ
• 2.3.2. Các nghiên cứu đi trước về bài toán tìm kiếm Mô típ
• 2.4. Bài toán phát hiện Luật Dự Báo
• 2.4.1. Khung làm việc Luật dự báo (Rule Framework)
• 2.4.2. Chuỗi con Tiền đề (Antecedent)
• 2.4.3. Chuỗi con Kết quả (Consequent)
• 2.4.4. Luật Dự Báo của chuỗi thời gian
• 2.4.5. Điểm phân tách (Split Point)
• 3. CHƯƠNG 3: CÁC CÔNG TRÌNH LIÊN QUAN
• 3.1. Phát hiện mô típ bằng giải thuật Chiếu Ngẫu Nhiên
• 3.2. Tìm kiếm chính xác Mô típ chuỗi thời gian
• 3.3. Rút trích luật có ý nghĩa trong chuỗi thời gian
• 3.4. Các công trình tham khảo khác
• 3.4.1. Về luật dự báo
• 3.4.2. Về nguyên lý MDL
• 4. CHƯƠNG 4: PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
• 4.1. Điểm cực trị quan trọng (Important Extreme Points)
• 4.1.1. Điểm cực tiểu quan trọng
• 4.1.2. Điểm cực đại quan trọng
• 4.1.3. Giải thuật tìm điểm cực trị quan trọng
• 4.2. Nhận diện mô típ dựa vào Điểm cực trị quan trọng và Gom cụm phân cấp theo hướng từ dưới lên
• 4.2.1. Độ đo khoảng cách có ràng buộc
• 4.2.2. Tìm ứng viên mô típ
• 4.2.3. Giải thuật gom cụm phân cấp theo hướng từ dưới lên (Hierarchical Bottom-Up Algorithm)
• 4.2.4. Giải thuật gom cụm K-Means
• 5. CHƯƠNG 5: HIỆN THỰC VÀ THỬ NGHIỆM
• 5.1. Hợp nhất các điểm cực trị quan trọng
• 5.2. Lấy mẫu các ứng viên bằng phương pháp Nội suy tuyến tính
• 5.3. Lấy mẫu các ứng viên bằng Phép biến hình vị tự
• 5.3.1. Khái niệm về Phép biến hình vị tự
• 5.3.2. Giải thuật phép biến hình vị tự
• 5.4. Mô hình hiện thực phương pháp rút trích luật dự báo sử dụng thuật toán phát hiện mô típ EP_C|HAC
• 5.5. Kết quả thực hiện của hai giải thuật
• 5.5.1. Dữ liệu xe điện 40 ngày (40daytrain) với kích thước 3000 điểm
• 5.5.2. Tập dữ liệu memory với kích thước 6875 điểm
• 5.6. Những đóng góp của đề tài
• 5.7. Hướng phát triển đề tài
• DANH MỤC CÁC TÀI LIỆU THAM KHẢO

Tóm tắt

I. Giới thiệu về Luật Dự Báo và Phương pháp dự báo

Luật Dự Báo là một kỹ thuật quan trọng trong lĩnh vực khai phá dữ liệu, đặc biệt là với dữ liệu chuỗi thời gian. Mục tiêu chính của luật dự báo là dự đoán các sự kiện tương lai dựa trên các mẫu hình xuất hiện trong quá khứ. Nguyên lý MDL (Minimum Description Length) và mô típ chuỗi thời gian là hai khái niệm cốt lõi được sử dụng trong phương pháp này. Nguyên lý MDL giúp tối ưu hóa việc nén dữ liệu, trong khi mô típ chuỗi thời gian giúp nhận diện các mẫu hình lặp lại trong dữ liệu. Phương pháp này không chỉ giúp dự báo chính xác hơn mà còn giảm thiểu thời gian xử lý dữ liệu.

1.1. Nguyên lý MDL

Nguyên lý MDL là một nguyên lý trong lý thuyết thông tin và học máy, dựa trên ý tưởng rằng mô hình tốt nhất là mô hình có thể nén dữ liệu một cách hiệu quả nhất. Trong bối cảnh dữ liệu chuỗi thời gian, nguyên lý này được áp dụng để tìm ra các mẫu hình có thể nén dữ liệu tốt nhất, từ đó rút trích các luật dự báo có ý nghĩa. Ví dụ, nếu một mẫu hình xuất hiện nhiều lần trong chuỗi thời gian, nó có thể được sử dụng để dự đoán các sự kiện tương lai.

1.2. Mô típ chuỗi thời gian

Mô típ chuỗi thời gian là các mẫu hình lặp lại trong dữ liệu chuỗi thời gian. Chúng đóng vai trò quan trọng trong việc nhận diện các quy luật và xu hướng trong dữ liệu. Ví dụ, trong dự báo thời tiết, các mô típ có thể giúp dự đoán các hiện tượng thời tiết lặp lại. Trong đề tài này, mô típ được sử dụng để tìm ra các luật dự báo dựa trên sự tương đồng giữa các chuỗi con trong dữ liệu.

II. Phương pháp và kỹ thuật dự báo

Phương pháp dự báo trong đề tài này dựa trên việc kết hợp nguyên lý MDL và mô típ chuỗi thời gian. Thuật toán MK được sử dụng để tìm kiếm các mô típ, nhưng do hạn chế về thời gian thực thi, đề tài đề xuất sử dụng thuật toán EP_C|HAC để cải thiện hiệu suất. Thuật toán EP_C|HAC kết hợp Điểm Cực trị Quan trọng và Gom cụm Phân cấp, giúp tìm ra các mô típ một cách hiệu quả hơn. Phương pháp này không chỉ giảm thời gian xử lý mà còn tăng độ chính xác của các luật dự báo.

2.1. Thuật toán MK và hạn chế

Thuật toán MK là một thuật toán tìm kiếm chính xác các mô típ chuỗi thời gian, nhưng có thời gian thực thi khá lâu. Hơn nữa, thuật toán này chỉ tìm ra hai chuỗi con giống nhau nhất mà không phải là chuỗi con có tần suất lặp lại nhiều nhất. Điều này dẫn đến các luật dự báo tìm được thường không mang tính tổng quát cao.

2.2. Thuật toán EP_C HAC

Thuật toán EP_C|HAC được đề xuất để thay thế thuật toán MK trong việc tìm kiếm mô típ chuỗi thời gian. Thuật toán này kết hợp Điểm Cực trị Quan trọng và Gom cụm Phân cấp, giúp tìm ra các mô típ một cách hiệu quả hơn. Kết quả thử nghiệm cho thấy, thuật toán EP_C|HAC không chỉ giảm thời gian xử lý mà còn tăng độ chính xác của các luật dự báo.

III. Thử nghiệm và kết quả

Đề tài đã thử nghiệm phương pháp đề xuất trên các bộ dữ liệu mẫu như 40daytrain và Memory. Kết quả cho thấy, thuật toán EP_C|HAC giúp cải thiện đáng kể hiệu suất và độ chính xác của các luật dự báo. Các luật dự báo tìm được không chỉ có tính tổng quát cao mà còn giúp dự đoán các sự kiện tương lai một cách chính xác hơn. Điều này chứng tỏ tính khả thi và hiệu quả của phương pháp đề xuất trong việc rút trích luật dự báo từ dữ liệu chuỗi thời gian.

3.1. Kết quả trên bộ dữ liệu 40daytrain

Trên bộ dữ liệu 40daytrain, thuật toán EP_C|HAC đã tìm ra các luật dự báo có độ chính xác cao hơn so với thuật toán MK. Các luật này không chỉ giúp dự đoán các sự kiện tương lai mà còn giảm thiểu thời gian xử lý dữ liệu.

3.2. Kết quả trên bộ dữ liệu Memory

Tương tự, trên bộ dữ liệu Memory, thuật toán EP_C|HAC cũng cho kết quả vượt trội so với thuật toán MK. Các luật dự báo tìm được có tính tổng quát cao và giúp dự đoán các sự kiện tương lai một cách chính xác hơn.

IV. Đóng góp và hướng phát triển

Đề tài đã đóng góp quan trọng trong việc cải thiện hiệu suất và độ chính xác của các luật dự báo từ dữ liệu chuỗi thời gian. Việc sử dụng thuật toán EP_C|HAC thay thế cho thuật toán MK đã mang lại kết quả tích cực trong thử nghiệm. Hướng phát triển tiếp theo của đề tài là áp dụng phương pháp này vào các lĩnh vực khác như dự báo thị trường chứng khoán, dự báo thời tiết, và phân tích dữ liệu y tế.

4.1. Đóng góp của đề tài

Đề tài đã đề xuất một phương pháp mới để rút trích luật dự báo từ dữ liệu chuỗi thời gian dựa trên nguyên lý MDL và mô típ chuỗi thời gian. Phương pháp này không chỉ giảm thời gian xử lý mà còn tăng độ chính xác của các luật dự báo.

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

Hướng phát triển tiếp theo của đề tài là áp dụng phương pháp này vào các lĩnh vực khác như dự báo thị trường chứng khoán, dự báo thời tiết, và phân tích dữ liệu y tế. Điều này sẽ mở ra nhiều cơ hội ứng dụng thực tế cho phương pháp đề xuất.

Nội dung chính

Tổng quan nghiên cứu

Trong kỷ nguyên số hóa và vạn vật kết nối, khối lượng dữ liệu chuỗi thời gian được thu thập từ các hệ thống cảm biến, thiết bị công nghiệp và thị trường tài chính đang tăng trưởng với tốc độ bình quân trên 25% mỗi năm. Khai phá dữ liệu chuỗi thời gian nhằm phát hiện các quy luật tiềm ẩn và đưa ra dự báo tương lai chính xác là bài toán trọng tâm trong ngành khoa học máy tính. Hầu hết các phương pháp dự báo truyền thống chỉ dựa trên giá trị đơn lẻ tức thời, trong khi hình dạng cấu trúc cục bộ của chuỗi thời gian mới là yếu tố quyết định hành vi tiếp theo của hệ thống. Khung sườn rút trích luật dự báo kinh điển của Mohammad Shokoohi-Yekta dựa trên thuật toán tìm kiếm mô típ chính xác MK (Mueen-Keogh) và nguyên lý Độ dài Miêu tả Tối thiểu (Minimum Description Length - MDL) đã tạo nên bước đột phá lớn. Tuy nhiên, giải thuật MK có độ phức tạp tính toán O(m^2), tiêu tốn rất nhiều thời gian xử lý trên các chuỗi dữ liệu dài và chỉ ưu tiên cặp chuỗi con có khoảng cách Euclid nhỏ nhất mà không xét đến tần suất lặp lại, khiến luật trích xuất dễ mất đi tính khái quát.

Luận văn thạc sĩ khoa học máy tính của tác giả Lâm Tuấn Anh, hoàn thành năm 2018 tại Trường Đại học Bách Khoa – Đại học Quốc gia Thành phố Hồ Chí Minh dưới sự hướng dẫn của Phó Giáo sư Tiến sĩ Dương Tuấn Anh, đã giải quyết triệt để nút thắt cổ chai này. Đề tài tập trung nghiên cứu giải pháp thay thế thuật toán MK bằng giải thuật kết hợp Điểm Cực trị Quan trọng và Gom cụm Phân cấp (kí hiệu là EP_C|HAC) trong khung sườn luật dự báo MDL. Nghiên cứu được thử nghiệm trên các tập dữ liệu chuỗi thời gian đơn biến có quy mô từ 3.000 đến 6.875 điểm đo lường. Ý nghĩa khoa học và thực tiễn của công trình được chứng minh qua các metrics ấn tượng: tốc độ xử lý nhanh hơn từ 8 đến 120 lần so với phương pháp gốc, trong khi vẫn bảo đảm độ tương đồng và tính phổ quát của luật dự báo đạt từ 80% đến 100%.

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 được xây dựng trên sự giao thoa của hai nền tảng lý thuyết lớn trong khoa học dữ liệu và lý thuyết thông tin:

1. Nguyên lý Độ dài Miêu tả Tối thiểu (MDL): Dựa trên tư tưởng lưỡi dao cạo Occam, nguyên lý MDL khẳng định rằng mô hình giải thích tốt nhất cho một tập dữ liệu chính là mô hình có khả năng nén dữ liệu đó tối đa. Trong khai phá chuỗi thời gian, việc học mẫu quy luật được quy đổi thành việc tính toán số lượng bit tiết kiệm được khi sử dụng chuỗi giả thuyết H để nén chuỗi thời gian tương lai thông qua mã hóa Huffman. Phương pháp này giúp tự động kiểm soát hiện tượng quá khít (overfitting) và đánh giá độ tin cậy của quy luật một cách khách quan.

2. Lý thuyết Mô típ Chuỗi thời gian (Time Series Motif): Được định nghĩa từ năm 2002 bởi B. Chiu dựa trên tần suất xuất hiện và năm 2009 bởi A. Mueen dựa trên khoảng cách metric Euclid nhỏ nhất. Mô típ đại diện cho các cặp chuỗi con hoặc tập hợp chuỗi con có hình thái tương đồng nhất lặp lại trong chuỗi thời gian dài.

Hệ thống khái niệm nòng cốt trong nghiên cứu bao gồm: Khung cửa sổ trượt (Sliding Window) kích thước n dùng để trích xuất các chuỗi con dọc theo chuỗi thời gian T độ dài m; Trùng khớp tầm thường (Trivial Match) nhằm loại bỏ các chuỗi con lân cận có độ chồng lấn trong phạm vi 2R; Bộ tứ Luật Dự báo R = {Ra, Rc, maxlag, t} trong đó Ra là chuỗi tiền đề (Antecedent), Rc là chuỗi kết quả (Consequent), maxlag là độ trễ thời gian cực đại và t là ngưỡng khoảng cách kích hoạt; Điểm phân tách (Split Point) xác định ranh giới giữa tiền đề và kết quả theo tỷ lệ từ 0 đến 1.

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

Nghiên cứu áp dụng phương pháp thực nghiệm định lượng kết hợp phát triển thuật toán cải tiến, trải qua các giai đoạn từ ngày 15/01/2018 đến ngày 17/06/2018:

• Nguồn dữ liệu và cỡ mẫu: Đề tài thu thập và đánh giá trên 3 bộ dữ liệu chuẩn thực tế với kích thước mẫu cụ thể: tập 40DayTrain gồm 3.000 điểm đo từ hệ thống giám sát xe điện trong 40 ngày; tập Memory gồm 6.875 điểm ghi nhận trạng thái cấp phát bộ nhớ máy chủ; tập dữ liệu phụ tải điện năng Power với hơn 4.000 điểm đo liên tục.
• Phương pháp chọn mẫu: Nghiên cứu áp dụng phương pháp chọn mẫu có chủ đích trên các chuỗi thời gian đơn biến thực tế có biên độ dao động mạnh và xuất hiện nhiễu môi trường, nhằm kiểm chứng chính xác khả năng chịu lỗi và tính ổn định của giải thuật xấp xỉ.
• Phương pháp phân tích và lý do lựa chọn: Thay vì dùng thuật toán vét cạn hay tìm kiếm chính xác MK có chi phí tính toán O(m^2), tác giả đề xuất quy trình phân tích EP_C|HAC gồm các bước: (1) Trích chọn các điểm cực đại và cực tiểu quan trọng (Important Extreme Points) theo hệ số nén R >= 1 để loại bỏ nhiễu; (2) Chuẩn hóa độ dài các chuỗi con ứng viên bằng Phép biến hình vị tự (Homothety transformation); (3) Gom cụm phân cấp từ dưới lên (Hierarchical Bottom-Up Agglomerative Clustering) dựa trên độ đo khoảng cách có ràng buộc; (4) Xếp hạng các mô típ từ bậc 1 đến bậc K theo kích thước cụm để phản ánh đúng tần suất xuất hiện; (5) Đưa mô típ vào khung sườn MDL để sàng lọc luật dự báo tối ưu.

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

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

1. Tăng tốc độ tính toán vượt bậc: Giải thuật đề xuất EP_C|HAC đạt tốc độ thực thi nhanh hơn từ 8 lần đến 120 lần so với thuật toán gốc MK khi thử nghiệm trên các tập dữ liệu có quy mô từ 3.000 đến 6.875 điểm.
2. Độ chuẩn xác và tương đồng cao: Tỷ lệ các luật dự báo tìm thấy bởi thuật toán đề xuất đạt mức tương đồng từ 80% đến 100% so với luật tìm được từ thuật toán chính xác MK trên toàn bộ các tập dữ liệu thực nghiệm.
3. Tính đại diện cấu trúc hình thái ưu việt: Có trên 50% số lượng các thể hiện thực tế của luật trùng khớp hoàn toàn với mẫu hình dự báo, giải quyết triệt để hạn chế của thuật toán MK vốn chỉ tìm ra luật mang tính cục bộ tại đúng 2 vị trí chuỗi con ban đầu.
4. Giảm thiểu chi phí không gian và loại bỏ nhiễu: Nhờ kỹ thuật hợp nhất điểm cực trị quan trọng và phép biến hình vị tự với hệ số co giãn k = 0.5, số lượng điểm dữ liệu cần xử lý trong ma trận khoảng cách giảm hơn 65%, giúp thuật toán triệt tiêu hiệu quả các điểm nhiễu cục bộ tại các vị trí đột biến tức thời.

Thảo luận kết quả

Nguyên nhân cốt lõi giúp giải thuật EP_C|HAC đạt hiệu năng vượt trội là sự chuyển dịch không gian tìm kiếm từ tập hợp điểm thô sang không gian đặc trưng hình học của các điểm cực trị quan trọng. Trong khi thuật toán MK mất hàng nghìn giây để tính toán ma trận khoảng cách đầy đủ nhằm tìm ra 2 chuỗi con có khoảng cách Euclid tối thiểu, phương pháp EP_C|HAC chỉ gom cụm trên các đỉnh sóng then chốt. Hơn nữa, việc xếp hạng mô típ theo kích thước cụm của thuật toán Gom cụm Phân cấp bảo đảm luật rút ra phản ánh đúng tần suất xuất hiện tự nhiên của sự kiện trong chuỗi thời gian, bám sát định nghĩa mô típ theo tần số của B. Chiu.

Về phương diện biểu diễn dữ liệu, kết quả so sánh giữa hai thuật toán được mô tả trực quan thông qua biểu đồ dạng sóng chồng lớp (overlay waveforms) của tiền đề và kết quả. Bảng tổng hợp số bit tiết kiệm (saved bits) chứng minh rằng tại các điểm phân tách từ 0.3 đến 0.7, điểm chất lượng MDL của luật tạo bởi EP_C|HAC hoàn toàn tương đương với thuật toán gốc nhưng thời gian xử lý giảm tới 99% trên tập dữ liệu Memory với 6.875 điểm đo.

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

1. Tích hợp mở rộng khung làm việc cho chuỗi thời gian đa biến: Các nhóm nghiên cứu AI và kỹ sư dữ liệu cần phát triển thêm hàm đo khoảng cách không gian nhiều chiều và cơ chế đồng bộ hóa điểm cực trị giữa 3 đến 5 luồng tín hiệu liên kết, nhằm nâng cao độ chính xác dự báo toàn diện thêm 15% trong lộ trình 12 tháng tới.
2. Tối ưu hóa động hệ số nén cực trị R: Các chuyên gia phát triển thuật toán cần thiết lập cơ chế tự động điều chỉnh ngưỡng R từ 1.05 đến 1.5 dựa trên độ lệch chuẩn của dữ liệu đầu vào, hướng tới mục tiêu giảm thiểu tỷ lệ bỏ sót điểm đặc trưng xuống dưới 3% trong vòng 6 tháng.
3. Triển khai xử lý song song trên phần cứng GPU và kiến trúc phân tán: Đội ngũ kỹ sư hạ tầng phần mềm cần tái cấu trúc thuật toán Gom cụm Phân cấp và tính toán độ nén MDL trên nền tảng CUDA hoặc Apache Spark, đặt mục tiêu xử lý các chuỗi dữ liệu lớn trên 1.000.000 điểm trong thời gian dưới 10 giây trước quý 4 năm 2027.
4. Ứng dụng mô hình vào hệ thống cảnh báo sớm công nghiệp và tài chính: Các doanh nghiệp sản xuất và tổ chức tài chính cần tích hợp bộ luật trích xuất từ EP_C|HAC vào hệ thống giám sát thời gian thực, mục tiêu giảm thiểu 30% sự cố quá tải thiết bị và tối ưu hóa điểm vào lệnh giao dịch tự động trong giai đoạn 2026 - 2028.

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

1. Nhà nghiên cứu và giảng viên Khoa học dữ liệu / Trí tuệ nhân tạo: Tiếp cận mô hình toán học kết hợp chặt chẽ giữa nguyên lý lý thuyết thông tin MDL và kỹ thuật khai phá chuỗi thời gian; sử dụng làm tài liệu tham khảo cho các đề tài phát triển giải thuật học máy tối ưu hóa.
2. Kỹ sư phân tích dữ liệu IoT và giám sát công nghiệp: Nắm bắt phương pháp trích xuất mẫu hình bất thường và dự báo sự cố dựa trên chuỗi thời gian cảm biến (như dữ liệu xe điện 40DayTrain với 3.000 điểm đo), giúp xây dựng hệ thống bảo trì dự đoán chính xác và hiệu quả.
3. Chuyên gia phân tích kỹ thuật và định lượng tài chính (Quant Traders): Ứng dụng nguyên lý nhận diện mô típ hình thái biểu đồ và độ trễ maxlag để tự động hóa việc phát hiện tín hiệu giao dịch cổ phiếu, ngoại hối với độ tin cậy được kiểm chứng toán học.
4. Học viên cao học và sinh viên ngành Công nghệ thông tin: Khảo sát một trường hợp nghiên cứu chuẩn mực về quy trình thực nghiệm, kỹ thuật xử lý tín hiệu (phép vị tự, nội suy tuyến tính, nén Huffman) và phương pháp đánh giá hiệu năng giải thuật từ mức độ lý thuyết đến ứng dụng thực tế.

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

1. Nguyên lý MDL đóng vai trò gì trong việc xác định luật dự báo chuỗi thời gian?
   Nguyên lý MDL đóng vai trò như tiêu chuẩn thẩm định khách quan dựa trên lý thuyết thông tin. Bằng cách tính toán lượng bit tiết kiệm khi nén chuỗi thời gian gốc thông qua chuỗi tiền đề và chuỗi kết quả kết hợp mã hóa Huffman, MDL giúp chọn ra luật có khả năng khái quát cao nhất, tránh hiện tượng quá khít trên 100% dữ liệu quan sát.

2. Tại sao thuật toán EP_C|HAC lại chạy nhanh hơn thuật toán MK từ 8 đến 120 lần?
   Thuật toán MK là giải thuật tìm kiếm chính xác với độ phức tạp tiệm cận O(m^2), đòi hỏi quét toàn bộ các cặp chuỗi con. Trong khi đó, EP_C|HAC sử dụng điểm cực trị quan trọng để nén dữ liệu và gom cụm phân cấp trên không gian rút gọn, giúp giảm hơn 65% số phép tính khoảng cách Euclid mà vẫn bảo đảm độ chính xác.

3. Sự khác biệt cốt lõi giữa định nghĩa mô típ của B. Chiu và A. Mueen là gì?
   Định nghĩa của B. Chiu (năm 2002) dựa trên tần suất xuất hiện, xem chuỗi con lặp lại nhiều nhất là mô típ bậc 1. Ngược lại, A. Mueen (năm 2009) định nghĩa mô típ dựa trên khoảng cách nhỏ nhất giữa hai chuỗi con. Luận văn đã kết hợp ưu điểm của cả hai để trích xuất luật mang tính quy luật phổ quát cao.

4. Phép biến hình vị tự giải quyết vấn đề gì trong quá trình gom cụm mô típ?
   Khi trích xuất các đoạn chuỗi con từ các điểm cực trị quan trọng, chiều dài giữa các chuỗi thường không đồng đều. Phép biến hình vị tự với hệ số k (như k = 0.5) cho phép co giãn tỷ lệ hình học một cách bảo toàn đặc trưng sóng, đưa các ứng viên về cùng chiều dài cố định để tính khoảng cách Euclid chính xác.

5. Khung làm việc rút trích luật dự báo có thể xử lý được dữ liệu bị nhiễu không?
   Hoàn toàn có thể. Nhờ cơ chế lọc điểm cực trị có hệ số nén R và độ đo khoảng cách có ràng buộc, giải thuật tự động bỏ qua các điểm dao động vi mô không đáng kể (như nhiễu điểm đo đơn lẻ), giúp luật trích xuất duy trì độ tương đồng trên 80% so với dữ liệu chuẩn.

Kết luận

• Đóng góp 1: Cải tiến thành công khung sườn rút trích luật dự báo của Shokoohi-Yekta bằng cách tích hợp giải thuật EP_C|HAC thay thế cho thuật toán tìm kiếm chính xác MK.
• Đóng góp 2: Tăng tốc độ thực thi thuật toán từ 8 đến 120 lần trên các tập dữ liệu thực nghiệm có quy mô từ 3.000 đến 6.875 điểm đo lường.
• Đóng góp 3: Đảm bảo độ chính xác và tính đại diện của luật dự báo với độ tương đồng đạt từ 80% đến 100% so với thuật toán gốc.
• Đóng góp 4: Đề xuất quy trình xử lý dữ liệu toàn diện kết hợp điểm cực trị quan trọng, phép biến hình vị tự và gom cụm phân cấp bottom-up.
• Đóng góp 5: Mở ra hướng tiếp cận mang tính ứng dụng cao cho việc khai phá dữ liệu lớn thời gian thực trong các lĩnh vực IoT, năng lượng và tài chính.

Kế hoạch triển khai tiếp theo: Trong giai đoạn 2026 - 2027, các nhóm nghiên cứu và kỹ sư phát triển tiếp tục mở rộng mô hình sang chuỗi thời gian đa biến và tối ưu hóa xử lý phân tán trên nền tảng GPU.

Hãy tham khảo chi tiết toàn văn luận văn thạc sĩ của tác giả Lâm Tuấn Anh và ứng dụng ngay giải thuật EP_C|HAC để tối ưu hóa hiệu năng phân tích chuỗi thời gian cho hệ thống của bạn!

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

Chương 1 của luận văn sẽ giới thiệu tổng thể về luận văn, cũng như cho độc giả một cái nhìn tổng quát về đề tài chúng tôi sẽ thực hiện. • Chương 2 chúng tôi nói về các cơ sở lý thuyết, chủ yếu tập trung vào việc giải thích các khái niệm và thuật ngữ có liên quan đến đề tài. • Chương 3 sẽ trình bày một cách vắn tắt các công trình liên quan đến đề tài. • Chương 4 là một chương trọng yếu khi diễn giải về các khái niệm có liên quan đến thuật toán chúng tôi sử dụng để thay thế thuật toán MK.

• Chương 5 giải thích quá trình hiện thực cũng như kết quả thực nghiệm trên các tập dữ liệu khác nhau. • Chương 6 đưa ra kết luận của chúng tôi về đề tài này cũng như nói đến các hướng phát triển tiếp theo của đề tài. Lâm Tuấn Anh - 1570202 4 Chương 2: CƠ SỞ LÝ THUYẾT Trong chương này, phần đầu chúng tôi sẽ giới thiệu về các khái niệm liên quan đến chuỗi thời gian cũng như nguyên lý MDL. Phần tiếp theo của chương sẽ trình bày về bài toán phát hiện Mô típ.

Phần cuối của chương chúng tôi muốn trình bày về bài toán phát hiện Luật dự báo và khung sườn dùng để phát hiện Luật dự báo.1 Giới thiệu nguyên lý MDL Theo bài báo hướng dẫn nhập môn Minimal Description Length, Grünwald cho rằng[4]: Minimum Description Length (MDL) tạm dịch là Độ dài Miêu tả Tối thiểu là một phương pháp gần đây dành cho suy luận quy nạp để đưa ra một giải pháp tổng quát cho vấn đề lựa chọn mô hình như sau: Làm thế nào để quyết định chọn ra trong rất nhiều cách giải thích về một tập dữ liệu, nếu như việc khảo sát dữ liệu đó bị giới hạn? Nguyên lý MDL dựa vào lập luận sau: Bất kì sự giống nhau nào trong dữ liệu đều có thể dùng để nén dữ liệu đó, nghĩa là để biểu diễn dữ liệu đó, cần dùng ít kí tự hơn là số kí tự dùng để biểu diễn một cách thuần tuý nguyên gốc. Nếu coi việc “học hỏi” tương đồng với việc “tìm điểm giống nhau” hay “tìm điểm bình thường” của dữ liệu, ta có thể nói càng nén được nhiều dữ liêu, ta càng học nhiều hay hiểu rõ hơn về dữ liệu đó. Việc biểu diễn một cách chính thống ý tưởng này dẫn đến một lý thuyết tổng quát về phương pháp suy luận quy nạp với nhiều tính chất nổi trội [4]: 2.1 Lưỡi dao của Occam Lưỡi dao của Occam từ lâu đã là kim chỉ nam cho việc phát triển các mô hình lý thuyết. Nguyên lý này nói rằng: giữa các giả thuyết có thể chọn, ta nên chọn giả thuyết với ít giả định nhất.

Tuy nhiên, người ta không bắt buộc phải theo lưỡi dao của Occam khi lựa chọn giữa các mô hình vì lưỡi dao Occam không phải là một kết quả khoa học hay một nguyên lý luận lý. Đối với mỗi lý giải được chấp nhận về một hiện tượng, có hàng trăm triệu cách giải thích khác phức tạp hơn. Người ta cũng có thể chọn giả thuyết đơn giản để có thể khó bị phản biện hay phủ định. Do đó vậy việc chọn sự đơn giản là do các lý thuyết đơn giản có thể kiểm chứng dễ dàng hơn chứ không phải vì lưỡi dao Occam.

Một điều ngạc nhiên là lịch sử đã chứng minh sự phát huy của lưỡi dao Occam. Một ví dụ cho điều đó là vào thế kỉ XVII con người có thể tính toán chính Lâm Tuấn Anh - 1570202 5 xác vị trí của mặt trời, mặt trăng và các hành tinh trong hệ mặt trời bằng hai mô hình: địa tâm (geocentric) là mô hình mà Trái Đất là trung tâm và nhật tâm (heliocentric) là mô hình Mặt Trời là trung tâm. Cả hai đều cho ra kết quả chính xác như nhau nhưng mô hình địa tâm phức tạp hơn rất nhiều so với mô hình nhật tâm. Đây cũng là heuristic mà các nhà khoa học lớn như Albert Einstein, Euler, Max Planck, Heisenberg, Broglie … dùng để định hướng cho việc phát triển mô hình cũng như các nguyên lý của mình.

Quay lại vấn đề, nguyên lý MDL chọn ra mô hình mà mô hình đó sẽ đánh đổi sự chính xác của mô hình đối với dữ liệu quan sát được lấy tính tổng quát của mô hình. Như vậy, đây chính là một dạng lưỡi dao Occam, cạo đi những chi tiết không cần thiết để tìm ra mô hình đơn giản nhất mà vẫn giải thích được hiện tượng từ tập dữ liệu. Chính vì thế nguyên lý MDL mang tính chất của lưỡi dao cạo Occam.2 Nguyên lý MDL không bị quá khít (quá chính xác) Nguyên lý MDL tự động điều chỉnh để bảo vệ khỏi hiện tượng quá khít (overfitting) và có thể dùng để ước đoán cả thông số lẫn cấu trúc của một mô hình.3 Nguyên lý MDL có thể chuyển thành xác suất Bayes Nguyên lý MDL rất gần với suy luận Bayes, tuy nhiên tránh được một số điểm phức tạp của hướng Bayes, đặc biệt trong trường hợp không có mô hình nào đang xét là đúng, do đó: 2.4 Nguyên lý MDL không cần sự tồn tại của sự thật ẩn bên trong dữ liệu Khác với các phương pháp thống kê khác, MDL tạo ra một lời giải thích không lệ thuộc vào việc có tồn tại hay không một mô hình “đúng” bên dưới dữ liệu.5 Nguyên lý MDL có thể dùng để tiên đoán Bởi vì việc nén dữ liệu tương đương với một dạng tiên đoán theo xác suất, phương pháp MDL có thể hiểu là đi tìm một mô hình có khả năng tiên đoán tốt đối với dữ liệu không có trong tập mẫu.2 Ý tưởng chính của nguyên lý MDL Mục đích của suy luận thống kê (statistic inference) có thể xem như việc cố gắng tìm kiếm càng nhiều điểm “bình thường”(regularity) trong dữ liệu. “Bình thường” ở đây có thể hiểu là “có thể nén được” và thường là giống nhau ở các điểm nào đó.

Nguyên lý MDL kết hợp hai điểm này lại bằng cách xem việc “học về dữ Lâm Tuấn Anh - 1570202 6 liệu” như thể “nén dữ liệu”. Nguyên lý nói rằng, cho một tập các giả thiết H và tập dữ liệu D, ta phải tìm ra giả thuyết hay tổ hợp các giả thiết trong H mà nó nén D nhiều nhất.3 Ví dụ đơn giản về MDL Cho 3 chuỗi sau. Chúng ta giả định rằng mỗi chuỗi dài 10000 bits và ta chỉ liệt kê phần bắt đầu cũng như kết thúc của mỗi chuỗi: 0010001000010000001000110000 (C) Chuỗi đầu tiên của cả ba chứa 2500 lần lặp lại của 0001. Ta có thể thấy chuỗi này có vẻ “bình thường” và có một quy luật bên dưới nó.

Ta nghiễm nhiên nghĩ rằng dữ liệu trong tương lai cũng tuân theo quy luật này và sẽ dùng luật đó để tiên đoán. Chuỗi B chính là giá trị tung đồng xu. Dĩ nhiên, chuỗi này sẽ ngẫu nhiên hết sức có thể và không có sự “bình thường” nào trong nó. Chuỗi C chứa số lượng bit 0 nhiều gấp 4 lần số lượng bit 1 và vì vậy trông có vẻ ít “bình thường” hơn.

Chuỗi C ngẫu nhiên hơn chuỗi A và ít ngẫu nhiên hơn chuỗi B. Chúng ta nói rằng bất cứ sự “bình thường” nào trong dữ liệu đều có thể dùng để nén nó, hay nói cách khác là để diễn tả dữ liệu một cách ngắn gọn. Bây giờ, dùng một ngôn ngữ tương tự Pascal, ta có thể viết một chương trình để in ra A: for i = 1 to 2500; print ‘0001‘; next; halt mà nó sẽ ngắn hơn bản thân chuỗi A rất nhiều, do đó chuỗi A có thể nén tốt. Mặc khác, ta thấy chuỗi B hầu như không thể nén được: print ‘ 1010111010111011000101100010’; halt Kích thước của chương trình này gần bằng với kích thước của chuỗi.

Rõ ràng, chương trình không làm gì ngoài việc lặp lại chuỗi gốc đặt vào trong mã chương trình. Chuỗi C nằm giữa hai chuỗi trên, C có thể nén đến độ dài 𝛼𝑛 với 0 < 𝛼 < 1. Tuy nhiên do phần chứng minh khá dài và cũng không phục vụ mục tiêu của đề tài nên xin tham khảo ở bài báo gốc [4]. Lâm Tuấn Anh - 1570202 7 2.2 Chuỗi thời gian và các khái niệm liên quan 2.1 Chuỗi thời gian (Time Series) Định nghĩa 1: Chuỗi Thời Gian, kí hiệu T=(t1, t2, …, tn) là một tập có thứ tự của n số thực [2].

Thứ tự của tập thường lệ thuộc vào thời gian, tuy nhiên một số kiểu dữ liệu khác như sự phân bố của màu sắc, hình dạng và đồ thị các dải tần số cũng được định nghĩa rõ ràng về thứ tự và có thể được coi như là một chuỗi thời gian để tạo chỉ mục và khai phá. Khoảng thời gian giữa những điểm của chuỗi thời gian cũng có thể không bằng nhau, tuy nhiên để đơn giản ta có thể xét chúng là bằng nhau mà vẫn không ảnh hưởng đến tính tổng quát. Có một ví dụ đơn giản là T = (40, 05, 93, 18) chính là chuỗi thời gian thể hiện kết quả số xố kiến thiết của thành phố Hồ Chí Minh trong tháng 11 năm 2017.2 Khung cửa sổ trượt (Sliding Window) B. Chiu và các cộng sự [5] đặt ra một khái niệm để xử lí chuỗi thời gian dài bằng cách cắt thành những chuỗi thời gian con và đặt chúng trong một ma trận: Cho trước một chuỗi thời gian T có độ dài m, và một chuỗi con chiều dài n, một ma trận S chứa tất cả các chuỗi con có thể xây dựng bằng cách trượt một khung cửa sổ có kích thước n dọc theo thời gian T và đặt các chuỗi con Cp trong hàng thứ p của S.

Ma trận S có độ lớn là (m – n + 1) x n. Ví dụ: A T G X A T A T G A T T A G (chuỗi con có độ dài 14) Khung cửa sổ trượt có độ dài 4 Ma trận S có kích thước 11 x 4 thu được khi trượt khung cửa sổ ATGX TGXA … TTAG Khái niệm này được tổng quát hoá ở định nghĩa về cơ sở dữ liệu chuỗi thời gian sau đây: 2.3 Cơ sở dữ liệu chuỗi thời gian (Time Series Database) Lâm Tuấn Anh - 1570202 8 Trong thực tế, ta thường phải xét đến nhiều chuỗi thời gian một lúc và do đó cần định nghĩa về khái niệm cơ sở dữ liệu chuỗi thời gian. Định nghĩa 2: Một Cơ Sở Dữ Liệu chuỗi thời gian (D) là một tập không có thứ tự chứa m chuỗi thời gian với độ dài tuỳ biến, nghĩa là chúng có thể chứa các chuỗi thời gian với độ dài khác nhau [2].