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

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

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.

Luận Văn Thạc Sĩ Khoa Học Máy Tính: 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