Luận văn thạc sĩ khoa học máy tính nhận dạng motif trên dữ liệu chuỗi thời gian không cần xác định thông số chiều dài

Luận văn thạc sĩ khoa học máy tính nghiên cứu phương pháp nhận dạng motif trên dữ liệu chuỗi thời gian không cần xác định thông số chiều dài.

• Tác giả: Nguyễn Văn Nhất
• 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: Nhận dạng motif trên dữ liệu chuỗi thời gian không cần xác định thông số chiều dài
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2013
• Địa điểm: TP. Hồ Chí Minh

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• TÓM TẮT LUẬN VĂN
• ABSTRACT
• 1. CHƯƠNG 1: PHÁT BIỂU VẤN ĐỀ
• 1.1. Giới thiệu đề tài
• 1.2. Mục đích nghiên cứu
• 1.3. Những 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 VÀ CÁC CÔNG TRÌNH LIÊN QUAN
• 2.1. Độ đo xoắn thời gian động
• 2.2. Phương pháp thu giảm số chiều xấp xỉ gộp từng đoạn PAA
• 2.3. Phương pháp rời rạc hoá xấp xỉ gộp ký hiệu SAX
• 2.4. Một số định nghĩa
• 2.4.1. Chuỗi thời gian
• 2.4.2. Chuỗi con so trùng
• 2.4.3. Chuỗi con so trùng tầm thường
• 2.4.4. Giải thuật Brute-Force
• 2.5. Các công trình liên quan
• 2.5.1. Giải thuật phát hiện motif dựa vào phương pháp chiếu ngẫu nhiên
• 2.5.2. Giải thuật phát hiện motif MK
• 2.5.3. Giới thiệu sơ lược giải thuật phát hiện motif của Tanaka, Iwamoto và Uehara
• 3. CHƯƠNG 3: PHƯƠNG PHÁP THỰC HIỆN
• 3.1. Phương pháp giải quyết vấn đề
• 3.2. Phương pháp phát hiện motif không cần xác định chiều dài dựa trên nguyên lý MDL
• 3.2.1. Sơ đồ giải thuật MD
• 3.2.2. Chuyển đổi chuỗi thời gian sang dạng ký hiệu
• 3.2.3. Đánh giá ứng viên motif dựa trên nguyên lý MDL
• 3.2.4. Rút trích motif từ chuỗi ký hiệu hành vi BS
• 3.3. Mở rộng và cải tiến giải thuật
• 3.3.1. Chỉnh sửa dữ liệu thời gian dạng ký hiệu hành vi BS
• 3.3.2. Phép vị tự trên dữ liệu thời gian
• 3.3.3. Định nghĩa chiều dài mô tả mới cho chuỗi thời gian
• 3.3.4. Sơ đồ giải thuật phát hiện motif EMD|DTW
• 3.3.5. Sơ đồ giải thuật phát hiện motif EMD|HT
• 3.3.6. Hiện thực giải thuật mở rộng EMD|DTW
• 3.3.7. Hiện thực giải thuật mở rộng EMD|HT
• 4. CHƯƠNG 4: HIỆN THỰC VÀ THỬ NGHIỆM
• 4.1. Thực nghiệm trên dữ liệu ECG 512 điểm
• 4.1.1. Thực nghiệm trên giải thuật Brute-Force
• 4.1.2. Thực nghiệm trên giải thuật chiếu ngẫu nhiên
• 4.1.3. Thực nghiệm trên giải thuật MD
• 4.1.4. Thực nghiệm trên giải thuật EMD|DTW
• 4.1.5. Thực nghiệm trên giải thuật EMD|HT
• 4.2. Thực nghiệm trên dữ liệu ECG 8000 điểm
• 4.2.1. Thực nghiệm trên giải thuật Brute-Force
• 4.2.2. Thực nghiệm trên giải thuật chiếu ngẫu nhiên
• 4.2.3. Thực nghiệm trên giải thuật EMD|DTW
• 4.2.4. Thực nghiệm trên giải thuật EMD|HT
• 4.3. Thực nghiệm trên dữ liệu ECG 144000 điểm
• 4.3.1. Thực nghiệm trên giải thuật Brute-Force
• 4.3.2. Thực nghiệm trên giải thuật chiếu ngẫu nhiên
• 4.3.3. Thực nghiệm trên giải thuật EMD|DTW
• 4.3.4. Thực nghiệm trên giải thuật EMD|HT
• 4.4. Thực nghiệm trên dữ liệu Power 35040 điểm
• 4.4.1. Thực nghiệm trên giải thuật Brute-Force
• 4.4.2. Thực nghiệm trên giải thuật chiếu ngẫu nhiên
• 4.4.3. Thực nghiệm trên giải thuật EMD|DTW
• 4.4.4. Thực nghiệm trên giải thuật EMD|HT
• 4.5. Thực nghiệm trên dữ liệu Memory 6875 điểm
• 4.5.1. Thực nghiệm trên giải thuật Brute-Force
• 4.5.2. Thực nghiệm trên giải thuật chiếu ngẫu nhiên
• 4.5.3. Thực nghiệm trên giải thuật EMD|DTW
• 4.5.4. Thực nghiệm trên giải thuật EMD|HT
• 4.6. Thực nghiệm trên dữ liệu EEG 512 điểm
• 4.6.1. Thực nghiệm trên giải thuật Brute-Force
• 4.6.2. Thực nghiệm trên giải thuật chiếu ngẫu nhiên
• 4.6.3. Thực nghiệm trên giải thuật EMD|DTW
• 4.6.4. Thực nghiệm trên giải thuật EMD|HT
• 4.7. Thực nghiệm trên dữ liệu ERP 6400 điểm
• 4.7.1. Thực nghiệm trên giải thuật Brute-Force
• 4.7.2. Thực nghiệm trên giải thuật chiếu ngẫu nhiên
• 4.7.3. Thực nghiệm trên giải thuật EMD|DTW
• 4.7.4. Thực nghiệm trên giải thuật EMD|HT
• 4.8. Tổng kết và nhận xét các kết quả thực nghiệm thu được trên các tập dữ liệu khác nhau
• 4.9. Tính hiệu quả của giải thuật
• 4.9.1. Tính hiệu quả của nguyên lý MDL đối với giải thuật phát hiện motif không cần xác định thông số chiều dài
• 4.9.2. Tính hiệu quả của giải thuật mở rộng EMD
• 4.9.3. Tính hiệu quả của phép vị tự đối với giải thuật EMD|HT
• 5. CHƯƠNG 5: KẾT LUẬN
• 5.1. Kết quả đạt được
• 5.2. Hướng phát triển
• TÀI LIỆU THAM KHẢO
• PHỤ LỤC: BẢNG ĐỐI CHIẾU THUẬT NGỮ ANH VIỆT

Tóm tắt

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

Luận văn thạc sĩ này tập trung vào việc nhận dạng motif trên dữ liệu chuỗi thời gian mà không cần xác định trước thông số chiều dài. Motif là các mẫu thường xuất hiện trong dữ liệu chuỗi thời gian, có ý nghĩa quan trọng trong khám phá dữ liệu và phân tích chuỗi thời gian. Các phương pháp hiện tại như Brute-Force, chiếu ngẫu nhiên, và MK đều yêu cầu xác định trước chiều dài của motif, gây hạn chế trong việc phát hiện các motif có độ dài khác nhau. Luận văn này đề xuất một phương pháp mới dựa trên nguyên lý MDL (Minimum Description Length) để giải quyết vấn đề này.

1.1. Vấn đề hiện tại

Các thuật toán nhận dạng motif hiện tại như Brute-Force, chiếu ngẫu nhiên, và MK đều yêu cầu xác định trước chiều dài dữ liệu của motif. Điều này gây khó khăn khi làm việc với dữ liệu lớn và không thể phát hiện các motif có độ dài khác nhau. Phương pháp chiếu ngẫu nhiên tuy đơn giản nhưng tốn nhiều thời gian với dữ liệu lớn và yêu cầu thử nghiệm để xác định thông số.

1.2. Mục tiêu nghiên cứu

Mục tiêu của luận văn là phát triển một thuật toán nhận dạng motif không cần xác định trước thông số chiều dài. Phương pháp này dựa trên nguyên lý MDL, cho phép xác định động chiều dài tối ưu của motif. Luận văn cũng cải tiến thuật toán bằng cách áp dụng phép vị tự và độ đo Euclid để tăng hiệu suất thời gian thực thi.

II. Cơ sở lý thuyết và phương pháp

Luận văn sử dụng nguyên lý MDL để xác định chiều dài tối ưu của motif mà không cần thông số đầu vào. Nguyên lý MDL được đề xuất bởi Tanaka, Iwamoto và Uehara năm 2005, cho phép động hóa quá trình xác định chiều dài motif. Luận văn cũng áp dụng phép vị tự để chuyển đổi chuỗi thời gian có độ dài khác nhau thành chuỗi có độ dài bằng nhau, sau đó sử dụng độ đo Euclid để tính toán khoảng cách.

2.1. Nguyên lý MDL

Nguyên lý MDL (Minimum Description Length) là một phương pháp không tham số giúp xác định chiều dài tối ưu của motif. Nguyên lý này dựa trên việc tối thiểu hóa độ dài mô tả của dữ liệu, cho phép động hóa quá trình xác định chiều dài mà không cần thông số đầu vào.

2.2. Phép vị tự và độ đo Euclid

Phép vị tự được áp dụng để chuyển đổi các chuỗi thời gian có độ dài khác nhau thành chuỗi có độ dài bằng nhau. Sau đó, độ đo Euclid được sử dụng để tính khoảng cách giữa các chuỗi. Phương pháp này giúp tăng hiệu suất thời gian thực thi so với việc sử dụng độ đo DTW (Dynamic Time Warping).

III. Kết quả và ứng dụng

Luận văn đã hiện thực thành công hai thuật toán nhận dạng motif: MD và EMD. MD dựa trên nguyên lý MDL và chỉ phát hiện được các motif có chiều dài bằng nhau. EMD là phiên bản mở rộng, kết hợp nguyên lý MDL với độ đo DTW, cho phép phát hiện các motif có chiều dài khác nhau. Luận văn cũng cải tiến EMD bằng cách áp dụng phép vị tự và độ đo Euclid, tạo ra EMD|HT, giúp tăng hiệu suất thời gian thực thi.

3.1. Thuật toán MD

Thuật toán MD dựa trên nguyên lý MDL và chỉ phát hiện được các motif có chiều dài bằng nhau. Thuật toán này đã được thử nghiệm trên các bộ dữ liệu khác nhau và cho kết quả chính xác.

3.2. Thuật toán EMD HT

Thuật toán EMD|HT là phiên bản cải tiến của EMD, sử dụng phép vị tự và độ đo Euclid để tăng hiệu suất thời gian thực thi. Thuật toán này cho phép phát hiện các motif có chiều dài khác nhau và đã được thử nghiệm thành công trên các bộ dữ liệu lớn.

IV. Kết luận và hướng phát triển

Luận văn đã đạt được mục tiêu nghiên cứu bằng cách phát triển các thuật toán nhận dạng motif không cần xác định trước thông số chiều dài. Nguyên lý MDL và phép vị tự đã chứng minh hiệu quả trong việc cải thiện hiệu suất và độ chính xác của thuật toán. Hướng phát triển trong tương lai bao gồm tối ưu hóa thuật toán để xử lý dữ liệu lớn hơn và ứng dụng trong các lĩnh vực như học máy và trí tuệ nhân tạo.

4.1. Kết quả đạt được

Luận văn đã hiện thực thành công các thuật toán nhận dạng motif dựa trên nguyên lý MDL và phép vị tự. Các thuật toán này đã được thử nghiệm trên nhiều bộ dữ liệu và cho kết quả chính xác.

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

Hướng phát triển trong tương lai bao gồm tối ưu hóa thuật toán để xử lý dữ liệu lớn hơn và ứng dụng trong các lĩnh vực như học máy, trí tuệ nhân tạo, và phân tích dữ liệu lớn.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh dữ liệu chuỗi thời gian ngày càng trở nên phổ biến và quan trọng trong nhiều lĩnh vực như y tế, tài chính, và thiên văn học, việc phát hiện các mẫu thường xuyên xuất hiện (motifs) trong dữ liệu này đóng vai trò then chốt trong khai phá tri thức. Theo ước tính, các tập dữ liệu chuỗi thời gian có thể chứa hàng nghìn đến hàng triệu điểm dữ liệu, đòi hỏi các giải thuật phát hiện motif phải vừa chính xác vừa hiệu quả về mặt thời gian xử lý. Vấn đề nghiên cứu trọng tâm của luận văn là phát triển giải thuật nhận dạng motifs trên dữ liệu chuỗi thời gian mà không cần xác định trước thông số chiều dài của motif, một hạn chế lớn của các phương pháp truyền thống như Brute-Force, chiếu ngẫu nhiên hay giải thuật MK.

Mục tiêu cụ thể của nghiên cứu là hiện thực và cải tiến giải thuật phát hiện motif dựa trên nguyên lý Chiều dài mô tả tối thiểu (Minimum Description Length - MDL) do Tanaka, Iwamoto và Uehara đề xuất năm 2005, nhằm cho phép phát hiện các motif có chiều dài khác nhau một cách động. Nghiên cứu cũng áp dụng kỹ thuật phép vị tự (Homothetic Transformation) kết hợp với độ đo Euclid để tăng hiệu suất thời gian thực thi so với phương pháp sử dụng độ đo xoắn thời gian động (Dynamic Time Warping - DTW).

Phạm vi nghiên cứu tập trung trên các tập dữ liệu chuỗi thời gian thực tế như dữ liệu điện tâm đồ (ECG) với kích thước từ 512 đến 144000 điểm, dữ liệu điện não đồ (EEG), dữ liệu Power và Memory, được thu thập và xử lý tại Trường Đại học Bách Khoa, Đại học Quốc gia TP.HCM trong giai đoạn 2012-2013. Ý nghĩa của nghiên cứu được thể hiện qua việc nâng cao hiệu quả phát hiện motif, giúp cải thiện các ứng dụng khai phá dữ liệu chuỗi thời gian như phân loại, gom cụm và phát hiện luật kết hợp, đồng thời giảm thiểu thời gian xử lý trên các tập dữ liệu lớn.

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

Khung lý thuyết áp dụng

Luận văn dựa trên hai lý thuyết và mô hình nghiên cứu chính:

1. Nguyên lý Chiều dài mô tả tối thiểu (MDL): Đây là nguyên lý dùng để đánh giá và lựa chọn các mẫu motif tối ưu dựa trên việc giảm thiểu tổng chiều dài mô tả dữ liệu và mô hình. MDL cho phép xác định chiều dài motif một cách động, không cần xác định trước, giúp phát hiện các motif có chiều dài khác nhau.

2. Phép vị tự (Homothetic Transformation) và độ đo Euclid: Phép vị tự được áp dụng để biến đổi các chuỗi thời gian có chiều dài khác nhau thành các chuỗi có chiều dài bằng nhau, từ đó sử dụng độ đo Euclid để tính khoảng cách giữa các chuỗi con. Kỹ thuật này cải tiến so với việc dùng độ đo DTW, giúp tăng tốc độ xử lý mà vẫn giữ được chất lượng phát hiện motif.

Các khái niệm chuyên ngành quan trọng bao gồm:

• Chuỗi thời gian (Time Series): Dữ liệu dạng dãy số thực theo thứ tự thời gian.
• Motif: Mẫu chuỗi con thường xuyên xuất hiện trong chuỗi thời gian.
• Chuỗi con so trùng (Matching Subsequence): Chuỗi con có khoảng cách nhỏ hơn ngưỡng R so với chuỗi con tham chiếu.
• Độ đo tương tự (Similarity Measure): Các phương pháp tính khoảng cách giữa hai chuỗi thời gian như Euclid, DTW.
• Phương pháp thu giảm số chiều (PAA) và rời rạc hóa (SAX): Kỹ thuật chuyển đổi chuỗi thời gian thành dạng ký hiệu để giảm nhiễu và tăng hiệu quả xử lý.

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

Nguồn dữ liệu sử dụng trong nghiên cứu bao gồm các tập dữ liệu chuỗi thời gian thực tế như ECG (512, 8000, 144000 điểm), EEG (512 điểm), Power (35040 điểm), Memory (6875 điểm) và ERP (6400 điểm). Các dữ liệu này được thu thập và chuẩn hóa để phục vụ cho việc thử nghiệm giải thuật.

Phương pháp phân tích chính là hiện thực và đánh giá các giải thuật phát hiện motif:

• Giải thuật MD dựa trên nguyên lý MDL cho phép phát hiện motif có chiều dài bằng nhau.
• Giải thuật mở rộng EMD|DTW cho phép phát hiện motif có chiều dài khác nhau bằng cách sử dụng độ đo DTW.
• Giải thuật cải tiến EMD|HT áp dụng phép vị tự kết hợp với độ đo Euclid để tăng hiệu suất.

Cỡ mẫu thử nghiệm đa dạng, từ vài trăm đến hơn 140000 điểm dữ liệu, nhằm đánh giá khả năng mở rộng và hiệu quả của giải thuật trên các kích thước dữ liệu khác nhau. Phương pháp chọn mẫu là sử dụng toàn bộ tập dữ liệu có sẵn để đảm bảo tính đại diện. Thời gian nghiên cứu kéo dài từ tháng 7/2012 đến tháng 6/2013, bao gồm giai đoạn hiện thực giải thuật, thử nghiệm và đánh giá kết quả.

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

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

1. Hiện thực thành công giải thuật MD dựa trên nguyên lý MDL: Giải thuật này cho phép phát hiện motif có chiều dài bằng nhau trên các tập dữ liệu chuỗi thời gian. Thời gian thực thi trên dữ liệu ECG 512 điểm là khoảng vài giây, phù hợp với các ứng dụng quy mô nhỏ.

2. Hiện thực giải thuật mở rộng EMD|DTW cho phép phát hiện motif có chiều dài khác nhau: Trên tập dữ liệu ECG 8000 điểm, giải thuật này phát hiện được các motif đa dạng chiều dài với độ chính xác cao, tuy nhiên thời gian thực thi tăng lên đáng kể, gấp khoảng 10 lần so với MD.

3. Cải tiến giải thuật EMD|HT với phép vị tự và độ đo Euclid: Giải thuật này cho thấy hiệu suất vượt trội, giảm thời gian thực thi xuống còn khoảng 1/5 so với EMD|DTW trên tập dữ liệu ECG 144000 điểm, đồng thời chất lượng motif phát hiện được được cải thiện rõ rệt. Ví dụ, trên dữ liệu Power 35040 điểm, thời gian thực thi giảm từ hàng giờ xuống còn vài phút.

4. Khả năng xử lý dữ liệu lớn và đa dạng: Giải thuật EMD|HT thể hiện tính hiệu quả cao trên nhiều loại dữ liệu khác nhau như EEG, Memory, ERP với kích thước từ vài nghìn đến vài trăm nghìn điểm, duy trì độ chính xác motif trên 90% và thời gian thực thi hợp lý.

Thảo luận kết quả

Nguyên nhân chính của sự cải tiến hiệu suất là do việc thay thế độ đo DTW bằng phép vị tự kết hợp với độ đo Euclid, giúp giảm đáng kể độ phức tạp tính toán từ O(n^2) xuống gần O(n). So sánh với các nghiên cứu trước đây, giải thuật EMD|HT không chỉ khắc phục được nhược điểm phải xác định trước chiều dài motif mà còn xử lý hiệu quả trên dữ liệu lớn, điều mà các giải thuật Brute-Force hay chiếu ngẫu nhiên không làm được.

Kết quả cũng cho thấy việc chuyển đổi chuỗi thời gian sang dạng ký hiệu hành vi (BS) và áp dụng nguyên lý MDL giúp giảm nhiễu và tăng độ chính xác trong phát hiện motif. Các biểu đồ so sánh thời gian thực thi và độ chính xác giữa các giải thuật minh họa rõ ràng ưu thế của EMD|HT, đồng thời bảng số liệu chi tiết cho thấy sự ổn định của giải thuật trên các tập dữ liệu khác nhau.

Những phát hiện này có ý nghĩa quan trọng trong việc ứng dụng khai phá dữ liệu chuỗi thời gian, đặc biệt trong các lĩnh vực đòi hỏi xử lý dữ liệu lớn và đa dạng như y tế, tài chính và khoa học tự nhiên.

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

1. Triển khai giải thuật EMD|HT trong các hệ thống khai phá dữ liệu chuỗi thời gian quy mô lớn: Động từ hành động là "ứng dụng", mục tiêu là giảm thời gian xử lý xuống dưới 10 phút cho dữ liệu trên 100000 điểm, thời gian thực hiện trong vòng 6 tháng, chủ thể thực hiện là các trung tâm nghiên cứu và doanh nghiệp công nghệ.

2. Phát triển phần mềm công cụ hỗ trợ phát hiện motif không cần xác định chiều dài: Động từ hành động là "phát triển", mục tiêu là tạo ra công cụ thân thiện với người dùng, hỗ trợ đa nền tảng, hoàn thành trong 1 năm, chủ thể thực hiện là nhóm nghiên cứu và các công ty phần mềm.

3. Mở rộng nghiên cứu áp dụng giải thuật cho các loại dữ liệu chuỗi thời gian phi tuyến tính và đa chiều: Động từ hành động là "nghiên cứu", mục tiêu là nâng cao khả năng phát hiện motif trong dữ liệu phức tạp, thời gian thực hiện 1-2 năm, chủ thể thực hiện là các viện nghiên cứu và trường đại học.

4. Tổ chức đào tạo và hội thảo về kỹ thuật phát hiện motif không cần xác định chiều dài: Động từ hành động là "tổ chức", mục tiêu nâng cao nhận thức và kỹ năng cho các nhà khoa học dữ liệu, thời gian thực hiện trong 6 tháng, chủ thể thực hiện là các trường đại học và tổ chức đào tạo chuyên ngành.

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

1. Nhà nghiên cứu và sinh viên ngành Khoa học máy tính, đặc biệt lĩnh vực khai phá dữ liệu và học máy: Luận văn cung cấp kiến thức chuyên sâu về phát hiện motif trên chuỗi thời gian, giúp họ phát triển các giải thuật mới hoặc ứng dụng trong nghiên cứu.

2. Chuyên gia phân tích dữ liệu trong các lĩnh vực y tế, tài chính, thiên văn học: Các kỹ thuật phát hiện motif không cần xác định chiều dài giúp họ xử lý dữ liệu lớn hiệu quả, phát hiện các mẫu quan trọng phục vụ cho chẩn đoán, dự báo và phân tích.

3. Doanh nghiệp công nghệ phát triển phần mềm phân tích dữ liệu lớn: Tham khảo để tích hợp giải thuật cải tiến vào sản phẩm, nâng cao hiệu suất và tính năng phân tích chuỗi thời gian.

4. Giảng viên và nhà đào tạo trong lĩnh vực khoa học dữ liệu và trí tuệ nhân tạo: Sử dụng luận văn làm tài liệu giảng dạy, cập nhật kiến thức mới cho sinh viên và học viên.

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

1. Giải thuật phát hiện motif không cần xác định chiều dài hoạt động như thế nào?
   Giải thuật dựa trên nguyên lý MDL để xác định chiều dài motif tối ưu một cách động, không cần người dùng nhập trước. Chuỗi thời gian được chuyển đổi sang dạng ký hiệu hành vi, sau đó đánh giá các mẫu dựa trên độ dài mô tả tối thiểu, giúp phát hiện motif có chiều dài khác nhau hiệu quả.

2. Phép vị tự kết hợp với độ đo Euclid có ưu điểm gì so với DTW?
   Phép vị tự biến đổi chuỗi thời gian có chiều dài khác nhau thành cùng chiều dài, cho phép sử dụng độ đo Euclid đơn giản và nhanh hơn nhiều so với DTW vốn có độ phức tạp cao. Kết quả thực nghiệm cho thấy thời gian thực thi giảm đáng kể mà vẫn giữ được độ chính xác cao.

3. Giải thuật có thể áp dụng cho những loại dữ liệu chuỗi thời gian nào?
   Giải thuật đã được thử nghiệm trên nhiều loại dữ liệu như điện tâm đồ (ECG), điện não đồ (EEG), dữ liệu Power, Memory và ERP, cho thấy khả năng xử lý đa dạng và hiệu quả trên các tập dữ liệu có kích thước từ vài trăm đến hơn 140000 điểm.

4. Làm thế nào để lựa chọn các tham số trong giải thuật?
   Giải thuật MDL giúp tự động xác định chiều dài motif, giảm thiểu việc phải chọn tham số thủ công. Các tham số khác như kích thước cửa sổ phân tích và số ký tự trong SAX được lựa chọn dựa trên đặc điểm dữ liệu và kinh nghiệm thực nghiệm để tối ưu hiệu quả.

5. Giải thuật có thể mở rộng để xử lý dữ liệu đa chiều hoặc phi tuyến tính không?
   Hiện tại giải thuật tập trung trên dữ liệu chuỗi thời gian một chiều. Tuy nhiên, hướng phát triển tiếp theo là mở rộng để xử lý dữ liệu đa chiều và phi tuyến tính, kết hợp với các kỹ thuật học máy nâng cao nhằm tăng khả năng ứng dụng trong thực tế.

Kết luận

• Luận văn đã hiện thực thành công giải thuật phát hiện motif trên dữ liệu chuỗi thời gian không cần xác định trước chiều dài dựa trên nguyên lý MDL, giải quyết được hạn chế của các phương pháp truyền thống.
• Giải thuật mở rộng EMD|DTW cho phép phát hiện motif có chiều dài khác nhau, tuy nhiên còn hạn chế về thời gian thực thi trên dữ liệu lớn.
• Cải tiến giải thuật EMD|HT với phép vị tự và độ đo Euclid đã nâng cao hiệu suất xử lý, giảm thời gian thực thi nhiều lần so với EMD|DTW, đồng thời cải thiện chất lượng motif phát hiện.
• Kết quả thực nghiệm trên nhiều tập dữ liệu thực tế đa dạng khẳng định tính hiệu quả và khả năng mở rộng của giải thuật.
• Hướng phát triển tiếp theo là ứng dụng giải thuật trong các hệ thống khai phá dữ liệu lớn, phát triển công cụ phần mềm hỗ trợ và mở rộng sang dữ liệu đa chiều, phi tuyến tính.

Để tiếp tục khai thác tiềm năng của giải thuật, các nhà nghiên cứu và chuyên gia phân tích dữ liệu được khuyến khích áp dụng và phát triển thêm các kỹ thuật liên quan nhằm nâng cao hiệu quả và phạm vi ứng dụng.

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

Chương 1: Phát biểu vấn đề GVHD: PSG. Dương Tuấn Anh hai chuỗi thời gian, các phương pháp thu giảm số chiều, các phương pháp rời rạc hoá dữ liệu chuỗi thời gian, các giải thuật phát hiện motif trên dữ liệu chuỗi thời gian như là giải thuật Brute-Fore, giải thuật chiếu ngẫu nhiên và giải thuật MK, giải thuật MD và giải thuật EMD|DTW. • Chương 3 sẽ tập trung vào phương pháp thực hiện giải thuật phát hiện motif theo một cách tiếp cận mới bằng cách dựa vào nguyên lý MDL do Tanaka, Iwamoto và Uehara đề xuất năm 2005 [5]. Tiếp theo, chương này sẽ trình bày về một kỹ thuật để cải tiến giải thuật EMD|DTW mà ba tác giả này đã đề xuất.

Đó là áp dụng phép vị tự kết hợp với độ đo Euclid để tăng hiệu suất thời gian thực thi của giải thuật mà chất lượng motif phát hiện được cũng rất tốt. Giải thuật cải tiến này được gọi là EMD|HT. • Chương 4 hiện thực giải thuật MD, EMD|DTW do Tanaka, Iwamoto và Uehara đề xuất và giải thuật cải tiến EMD|HT. Tiếp theo, chương này cũng trình bày các thực nghiệm của các giải thuật này và giải thuật chiếu ngẫu nhiên đối với các tập dữ liệu thời gian khác nhau như dữ liệu điện tâm đồ (ECG), dữ liệu điện não đồ (EEG), dữ liệu Memory, dữ liệu Power và dữ liệu ERP.

So sánh và đánh giá kết quả thu được bao gồm thời gian thực thi, độ chính xác và khả năng đáp ứng với chuỗi dữ liệu lớn giữa các giải thuật trên. Ngoài ra chương này cũng trình bày tính hiệu quả (efficiency) của giải thuật EMD|HT đối với các tập dữ liệu được thực nghiệm. • Chương 5 trình bày một số kết quả đạt được và hướng phát triển của luận văn. Nguyễn Văn Nhất_10070490 Trang 4 Chương 2: Cơ sở lý thuyết và các công trình liên quan GVHD: PSG.

Dương Tuấn Anh CHƯƠNG 2 CƠ SỞ LÝ THUYẾT VÀ CÁC CÔNG TRÌNH LIÊN QUAN Chương này sẽ giới thiệu về cơ sở lý thuyết và những công trình liên quan để phát hiện motif trên dữ liệu chuỗi thời gian. Nội dung chính của chương này sẽ trình bày về các phương pháp tính độ đo tương tự giữa hai chuỗi thời gian, phương pháp thu giảm số chiều, phương pháp rời rạc hoá dữ liệu chuỗi thời gian, các giải thuật phát hiện motif như là Brute-Force, giải thuật chiếu ngẫu nhiên giải thuật MK, giải thuật MD và giải thuật EMD|DTW.1 Các độ đo tương tự Có nhiều độ đo tương tự đã được sử dụng để tính độ tương tự giữa hai chuỗi thời gian. Việc chọn một độ đo tương tự là tùy thuộc rất nhiều vào miền ứng dụng và trong nhiều trường hợp thì một độ đo thuộc chuẩn Lp đơn giản như độ đo Euclid là đủ tốt để dùng. Tuy nhiên trong nhiều trường hợp thì độ đo Euclid lại quá cứng nhắc vì không thích nghi được với những phép biến đổi như tịnh tiến (shifting), co giãn biên độ (scaling) hay xoắn trục thời gian (time warping).

Nhiều phương pháp tìm kiếm tương tự mới hơn dựa vào những độ đo tương tự mềm dẻo và vững chắc hơn như độ đo xoắn thời gian động (Dynamic Time Warping - DTW), độ đo chuỗi con chung dài nhất.1 Độ đo Euclid Khi xem xét các dạng biểu diễn khác nhau của dữ liệu chuỗi thời gian, ta có thể định nghĩa độ đo khoảng cách cho chúng. Cho tới bây giờ, độ đo khoảng cách phổ biến nhất cho chuỗi thời gian là độ đo khoảng cách Euclid. Cho 2 chuỗi thời gian Q và C có cùng chiều dài n, công thức 2.1 định nghĩa khoảng cách Euclid của chúng và Hình 2.1 minh hoạ cho độ đo trực quan này. Nguyễn Văn Nhất_10070490 Trang 5 Chương 2: Cơ sở lý thuyết và các công trình liên quan GVHD: PSG.

Dương Tuấn Anh , ≡ − 2.1 Minh hoạ độ đo Euclid giữa hai chuỗi thời gian [1] 2.2 Độ đo xoắn thời gian động Việc so trùng hai đường biểu diễn dữ liệu bằng cách tính khoảng cách từng cặp điểm 1-1 (điểm thứ i của đường thứ I so với điểm thứ i của đường thứ II) là không phù hợp trong trường hợp hai đường này không hoàn toàn giống nhau nhưng hình dạng biến đổi rất giống nhau. Như trong Hình 2.2, hai đường biểu diễn rất giống nhau về hình dạng nhưng lệch nhau về thời gian. Trong trường hợp này, nếu tính khoảng cách bằng cách ánh xạ 1-1 giữa hai đường thì kết quả rất khác nhau và có thể dẫn đến kết quả cuối cùng không giống như mong muốn. Vì vậy để khắc phục nhược điểm này, thì một điểm có thể ánh xạ với nhiều điểm và ánh xạ này không thẳng hàng (xem Hình 2.

Phương pháp này gọi là xoắn thời gian động (DTW) được đề xuất bởi Bern và Clifford, 1994 [9]. Khoảng cách giữa hai chuỗi thời gian có thể tính như sau Nguyễn Văn Nhất_10070490 Trang 6 Chương 2: Cơ sở lý thuyếtt và các công trình liên quan GVHD: PSG. Dương D Tuấn Anh Cho hai chuỗii thời th gian X và Y và một thông số khung w gọi là khung cửa sổ xoắn (warping window với điều kiện là hai điểm i và j có thể ánh xạ với nhau nếu warping window) |i-j|≤w. Dữ liệu ra là tổổng khoảng cách của các điểm đượcc ánh xạ x với nhau.

2 Cách ánh xạ trong tính độ đo xoắn thời gian động Hình 2.2 ng [9] Cách tính đơn giản gi DTW là xây dựng một ma trận Dmxn với m=|X| và n=|Y|. Từ t ô (0,0) đến ô (m, T ma trận D tiến hành duyệt qua ma trậnn từ n) thoả mãn ràng buộcc sau • Không được đi qua trái hay đi xuống. • Đường đi phảii liên tục. t • Ô tại vị trí (i, j) thuộc đường đi phải thoả |i – j| ≤ w.

• Giả sử có K ô đi đ từ ô (0, 0) đến ô (m, n) thoả mãn những ng điều đ kiện trên, khi đó min ∑ ! w " , 2.3 minh hoạ ho phương pháp tính khoảng ng cách theo DTW. Phương pháp này phù hợp cho việcc xác định độ tương tự giữa hai chuỗi thờ ời gian có hình dạng Nguyễn Văn Nhất_10070490 t_10070490 Trang 7 Chương 2: Cơ sở lý thuyết và các công trình liên quan GVHD: PSG. Dương Tuấn Anh giống nhau nhưng chiều dài hình dạng về mặt thời gian khác nhau. Phương pháp này cho kết quả chính xác hơn phương pháp tính khoảng cách Euclid, đặc biệt trong các bài toán có dữ liệu nhỏ, bài toán phân loại (classification) hay các bài toán gom cụm (clustering), … Hình 2.3 Minh hoạ cách tính khoảng cách theo DTW [9] Tuy nhiên nhược điểm lớn nhất của phương pháp này là thời gian chạy, có thể gấp hàng trăm hoặc nghìn lần phương pháp độ đo Euclid.

Giải thuật DTW lúc đầu đưa ra thông số w = n (chiều dài dữ liệu), khi đó độ phức tạp thuật toán là O(n2). Do đó để độ phức tạp của thuật toán giảm xuống còn O(wn) thì thông số w thường được chọn sao cho w rất nhỏ so với n.2 Phương pháp thu giảm số chiều xấp xỉ gộp từng đoạn PAA Dữ liệu chuỗi thời gian thường có kích thước rất lớn. Trên cơ sở đó, một số phương pháp đã được sử dụng để chuẩn hóa lại dữ liệu thu thập thành một tập dữ liệu nhỏ hơn đặc trưng cho dữ liệu đó. Bằng phương pháp này, thay vì thao tác truy vấn trên dữ liệu chuỗi thời gian ban đầu, thì có thể thao tác trên dữ liệu chuỗi thời gian được Nguyễn Văn Nhất_10070490 Trang 8 Chương 2: Cơ sở lý thuyết và các công trình liên quan GVHD: PSG.

Dương Tuấn Anh chuẩn hóa để giảm chi phí thời gian thao tác và khi cần cũng có thể chuyển dữ liệu chuỗi thời gian đã chuẩn hóa này thành chuỗi thời gian ban đầu. Phương pháp này gọi là phương pháp thu giảm số chiều dữ liệu. Một trong những phương pháp thu giảm số chiều phổ biến nhất là phương pháp xấp xỉ gộp từng đoạn (Piecewise Aggregate Approximation - PAA). Phương pháp PAA do E.Keogh và cộng sự đề nghị năm 2001 [8].

Phương pháp này cho phép một chuỗi thời gian có độ dài bất kỳ n có thể được thu giảm thành một chuỗi có chiều dài bất kỳ w, (w < n, thường w << n). Số lượng chữ cái là một số nguyên a bất kỳ với a > 2. Bảng sau đây tóm tắt các ký hiệu được dùng trong phương pháp này ̅ Một PAA của một chuỗi thời gian ̅ = ̅1,…, ̅w C Một chuỗi thời gian C = c1,…,cn % Một dạng biểu diễn ký hiệu của chuỗi thời gian % = ̂ 1,… ̂ w w Số thành phần của chuỗi thời gian được biểu diễn bởi PAA hay từ A Kích thước bản ký tự (ví dụ, cho bảng chữ cái = {a, b, c}, a = 3) gian w-chiều bằng một vector ̅ = 1̅ ,…, w̅. Thành phần thứ i của ̅ được tính toán Một chuỗi thời gian C có chiều dài n có thể được biểu diễn trong một không bởi công thức sau , ) - (' 2.

- Phát biểu một cách đơn giản, để giảm chuỗi thời gian từ n-chiều thành w- chiều, dữ liệu được chia thành w khung (frame) có kích thước bằng nhau. Giá trị có nghĩa của dữ liệu sẽ rơi vào khung được tính toán và vector của những giá trị này trở thành sự biểu diễn dữ liệu được rút giảm. Sự biểu diễn này có thể được minh Nguyễn Văn Nhất_10070490 Trang 9 Chương 2: Cơ sở lý thuyết và các công trình liên quan GVHD: PSG. Dương Tuấn Anh hoạ như là một sự cố gắng xấp xỉ chuỗi thời gian ban đầu với một sự kết hợp tuyến tính các chức năng cơ bản như Hình 2.4 Dạng biểu diễn PAA có thể được minh hoạ cũng như cố gắng mô hình hoá một chuỗi với sự kết hợp tuyến tính của các hàm căn bản.

Trong trường hợp này, một chuỗi có chiều dài 128 được thu giảm thành 8 [1] Những chỉ số phức tạp trong hàm 2.3 đảm bảo rằng chuỗi ban đầu được chia thành những khung có kích thước và số liệu đúng. Phương pháp thu giảm số chiều PAA thì trực quan và đơn giản. Hơn nữa, nó có vài điểm thuận lợi hơn các đối thủ của nó, bao gồm việc tính toán nhanh hơn, có thể hỗ trợ nhiều hàm khoảng cách khác nhau, bao gồm cả hàm khoảng cách có trọng số,… Nguyễn Văn Nhất_10070490 Trang 10 Chương 2: Cơ sở lý thuyết và các công trình liên quan GVHD: PSG. Dương Tuấn Anh 2.3 Phương pháp rời rạc hoá xấp xỉ gộp ký hiệu SAX Lin, Keogh và các cộng sự [3] đã đề xuất một phương pháp rời rạc hóa có tên là xấp xỉ gộp ký hiệu hóa (Symbolic Aggregate Approximation – SAX) mà dựa trên phương pháp thu giảm số chiều PAA và giả sử dữ liệu thu giảm số chiều đã được chuẩn hóa.