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

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.

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].