Phát Hiện Motif Trên Dữ Liệu Chuỗi Thời Gian Dựa Vào Phép Biến Đổi ESAX

Luận văn thạc sĩ trình bày phương pháp phát hiện motif trên dữ liệu chuỗi thời gian bằng phép biến đổi esax, ứng dụng trong khoa học máy tính.

• Tác giả: Vũ Thị Thái Linh
• Người hướng dẫn: PGS. Dương Tuấn Anh
• Trường học: Đại học Quốc gia TP. Hồ Chí Minh
• Chuyên ngành: Khoa học máy tính
• Đề tài: Phát Hiện Motif Trên Dữ Liệu Chuỗi Thời Gian Bằng Phép Biến Đổi ESAX
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2014
• Địa điểm: TP. Hồ Chí Minh

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: PHÁT BIỂU VẤN ĐỀ
• 1.1. Dữ liệu chuỗi thời gian
• 1.2. Khai phá motif trong chuỗi dữ liệu thời gian
• 1.3. Mục tiêu và giới hạn của đề tài
• 1.4. Những kết quả đạt được
• 1.5. Cấu trúc của luận văn
• 2. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT
• 2.1. Một số khái niệm cơ bản
• 2.1.1. Cửa sổ trượt (Slide window)
• 2.1.2. Trùng khớp không tầm thường (Non-Self Match)
• 2.2. Các công trình về độ đo tương tự
• 2.2.1. Độ đo xoắn thời gian động (Dynamic Time Warping- DTW)
• 2.3. Các công trình về biểu diễn chuỗi thời gian
• 2.3.1. Phép biến đổi Fourier rời rạc DFT
• 2.3.2. Phép biến đổi Wavelet rời rạc DWT
• 2.3.3. Phép xấp xỉ gộp từng đoạn PAA
• 2.3.4. Phép xấp xỉ gộp từng đoạn mở rộng EPAA (Extended PAA)
• 2.3.5. Phép xấp xỉ gộp ký hiệu hóa SAX
• 2.3.5.1. Chuẩn hóa dữ liệu
• 2.3.5.2. Thu giảm số chiều qua PAA
• 2.3.5.3. Ký hiệu hóa chuỗi thời gian
• 2.3.5.4. Hàm tính độ đo tương tự
• 2.3.6. Phương pháp xấp xỉ gộp ký hiệu hoá mở rộng ESAX (Extended SAX)
• 3. CHƯƠNG 3: TỔNG THUẬT CÁC CÔNG TRÌNH LIÊN QUAN
• 3.1. Phát hiện 1-Motif dựa vào giải thuật Brute Force
• 3.2. Phát hiện Motif dựa vào giải thuật Random Projection
• 4. CHƯƠNG 4: PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
• 4.1. Dùng cửa sổ trượt rút trích các chuỗi con
• 4.2. Thu giảm số chiều mỗi chuỗi con theo phép biến đổi EPAA
• 4.3. Rời rạc hoá dữ liệu mỗi chuỗi con theo phép biến đổi ESAX
• 4.4. Xây dựng giải thuật Random Projection theo phép biến đổi ESAX
• 5. CHƯƠNG 5: THỰC NGHIỆM
• 5.1. Thực nghiệm các giải thuật đã hiện thực trên tập dữ liệu
• 5.1.1. Dữ liệu điện tâm đồ (ECG) 7
• 5.1.2. Dữ liệu điện tâm đồ (ECG) 10
• 5.1.3. Dữ liệu điện não đồ (EEG) 12
• 5.1.4. Dữ liệu doanh nghiệp (ERP) 10
• 5.1.5. Dữ liệu MEMORY 12
• 5.1.6. Dữ liệu năng lượng (POWER) 12
• 5.1.7. Dữ liệu chứng khoán (STOCK) 5
• 5.2. So sánh các giải thuật dựa trên kết quả thực nghiệm
• 6. CHƯƠNG 6: KẾT LUẬN
• 6.1. Những đóng góp của luận văn
• 6.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
• LÝ LỊCH TRÍCH NGANG

Tóm tắt

I. Tổng Quan Về Phát Hiện Motif Chuỗi Thời Gian

Bài toán phát hiện motif chuỗi thời gian ngày càng trở nên quan trọng trong nhiều lĩnh vực, từ y học đến tài chính. Motif là các đoạn chuỗi con tương tự xuất hiện lặp lại trong một chuỗi thời gian dài. Việc tìm kiếm những mẫu này có thể giúp chúng ta hiểu rõ hơn về cấu trúc và đặc điểm của dữ liệu. Ví dụ, trong dữ liệu điện tâm đồ (ECG), một motif có thể đại diện cho một nhịp tim khỏe mạnh, trong khi sự xuất hiện của một motif khác có thể báo hiệu một vấn đề tim mạch. Các phương pháp khai phá chuỗi thời gian truyền thống thường gặp khó khăn khi xử lý dữ liệu lớn và phức tạp. Do đó, các kỹ thuật hiệu quả hơn như sử dụng phép biến đổi ESAX đang được nghiên cứu và phát triển. Mục tiêu là tìm ra những motif quan trọng một cách nhanh chóng và chính xác.

1.1. Ứng Dụng Rộng Rãi Của Motif Chuỗi Thời Gian

Ứng dụng của việc phát hiện motif chuỗi thời gian vô cùng đa dạng. Trong lĩnh vực tài chính, nó có thể giúp xác định các mô hình giao dịch lặp lại. Trong lĩnh vực y học, nó giúp phát hiện các dạng sóng bất thường trong dữ liệu điện tâm đồ. Theo nghiên cứu của Vũ Thị Thái Linh, 'Biểu diễn dữ liệu chuỗi thời gian ngày càng đóng vai trò quan trọng trong các bài toán khai phá dữ liệu chuỗi thời gian'. Việc hiểu rõ những ứng dụng này là động lực để phát triển các thuật toán hiệu quả hơn.

1.2. Thách Thức Trong Việc Tìm Kiếm Motif Hiệu Quả

Việc tìm kiếm motif trong chuỗi thời gian lớn là một thách thức lớn. Độ phức tạp tính toán tăng lên đáng kể với kích thước dữ liệu. Các thuật toán brute-force, mặc dù chính xác, thường không khả thi cho các ứng dụng thực tế. Việc lựa chọn phương pháp biểu diễn chuỗi thời gian phù hợp cũng là một yếu tố quan trọng. Phương pháp ESAX được kì vọng sẽ giải quyết những hạn chế này.

II. Vấn Đề Với Phương Pháp Khai Phá Chuỗi Thời Gian Hiện Tại

Các phương pháp khai phá chuỗi thời gian truyền thống thường gặp phải các vấn đề về hiệu suất và khả năng mở rộng. Việc xử lý trực tiếp dữ liệu thô đòi hỏi tài nguyên tính toán lớn. Các phương pháp giảm chiều dữ liệu như PAA (Piecewise Aggregate Approximation) có thể làm mất đi một số thông tin quan trọng. Các phương pháp rời rạc hóa dữ liệu như SAX (Symbolic Aggregate Approximation) có thể không đủ hiệu quả trong việc biểu diễn các mẫu phức tạp. Do đó, cần có những phương pháp mới, hiệu quả hơn để giải quyết những hạn chế này. Phương pháp biến đổi ESAX ra đời nhằm giải quyết bài toán này. Theo Vũ Thị Thái Linh, 'Để hạn chế tối đa số lần truy cập đĩa, người ta thường xấp xỉ các chuỗi dữ liệu sao cho vừa khớp với bộ nhớ chính.'

2.1. Hạn Chế Của SAX Trong Phát Hiện Motif Chuỗi Thời Gian

Mặc dù SAX là một phương pháp hiệu quả để biểu diễn chuỗi thời gian, nó có một số hạn chế. Việc lượng tử hóa dữ liệu thành các ký hiệu rời rạc có thể dẫn đến mất thông tin. SAX cũng không hỗ trợ tìm kiếm chính xác, điều này có thể làm giảm độ chính xác của việc phát hiện motif. ESAX được phát triển để khắc phục những nhược điểm này.

2.2. Độ Phức Tạp Tính Toán Cao Của Giải Thuật Brute Force

Giải thuật Brute-Force được xem là giải pháp tối ưu cho việc tìm kiếm motif, tuy nhiên lại gặp trở ngại về độ phức tạp tính toán. Độ phức tạp tăng lên đáng kể khi dữ liệu trở nên lớn hơn. Điều này khiến cho phương pháp trở nên không phù hợp với các ứng dụng lớn cần hiệu suất cao.

III. Biến Đổi ESAX Giải Pháp Phát Hiện Motif Tối Ưu

ESAX (Extended SAX) là một phương pháp biểu diễn chuỗi thời gian được thiết kế để cải thiện hiệu suất và độ chính xác của việc phát hiện motif. ESAX mở rộng SAX bằng cách sử dụng nhiều ký hiệu hơn để biểu diễn dữ liệu, giúp giảm thiểu việc mất thông tin. ESAX cũng hỗ trợ tìm kiếm chính xác, cho phép phát hiện motif với độ tin cậy cao hơn. Phương pháp này hứa hẹn mang lại những cải tiến đáng kể trong việc khai phá chuỗi thời gian. Vũ Thị Thái Linh cho rằng 'ESAX tận dụng tính tìm kiếm chính xác của phương pháp ESAX (một ưu thế mà phương pháp SAX không có được) để rút ngắn thời gian trong việc phát hiện chuỗi con motif'.

3.1. Chi Tiết Về Phép Biến Đổi ESAX Extended SAX

ESAX (Extended Symbolic Aggregate approXimation) cải tiến SAX bằng cách sử dụng nhiều mức rời rạc hơn. Điều này giúp biểu diễn chuỗi thời gian chính xác hơn và giảm thiểu mất thông tin. ESAX cũng hỗ trợ tìm kiếm chính xác, cho phép tìm kiếm các motif một cách hiệu quả hơn. Điều này đặc biệt quan trọng khi xử lý dữ liệu lớn.

3.2. Cách ESAX Cải Thiện Độ Chính Xác Phát Hiện Motif

ESAX cải thiện độ chính xác của việc phát hiện motif bằng cách duy trì nhiều thông tin hơn so với SAX. Khả năng tìm kiếm chính xác của ESAX cũng giúp giảm thiểu số lượng kết quả sai lệch. Điều này rất quan trọng trong các ứng dụng mà độ chính xác là yếu tố then chốt.

IV. Hướng Dẫn Chi Tiết Ứng Dụng ESAX Phát Hiện Motif

Để ứng dụng ESAX vào việc phát hiện motif, cần thực hiện một số bước cơ bản. Đầu tiên, cần chuẩn hóa dữ liệu chuỗi thời gian. Sau đó, sử dụng PAA (Piecewise Aggregate Approximation) hoặc EPAA (Extended Piecewise Aggregate Approximation) để giảm chiều dữ liệu. Tiếp theo, áp dụng phép biến đổi ESAX để rời rạc hóa dữ liệu. Cuối cùng, sử dụng một thuật toán tìm kiếm motif để xác định các mẫu quan trọng. Theo Vũ Thị Thái Linh, 'Đề tài này tìm hiểu phương pháp rời rạc hóa dữ liệu ESAX (phương pháp xấp xỉ gộp ký hiệu hóa mở rộng), so sánh mức hiệu dụng của hai phép rời rạc hoá dữ liệu SAX (phương pháp xấp xỉ gộp ký hiệu hoá) khi áp dụng vào bài toán phát hiện motif'.

4.1. Chuẩn Hóa Dữ Liệu và Giảm Chiều Dữ Liệu Với EPAA

Chuẩn hóa dữ liệu là bước quan trọng để đảm bảo rằng dữ liệu có cùng thang đo. EPAA (Extended Piecewise Aggregate Approximation) là một phương pháp hiệu quả để giảm chiều dữ liệu mà không làm mất quá nhiều thông tin. Việc kết hợp chuẩn hóa và EPAA giúp cải thiện hiệu suất của thuật toán phát hiện motif.

4.2. Xây Dựng Giải Thuật Random Projection Với ESAX

Thuật toán Random Projection có thể được kết hợp với ESAX để phát hiện motif hiệu quả hơn. Thuật toán này sử dụng phép chiếu ngẫu nhiên để giảm chiều dữ liệu trong không gian ESAX, giúp tăng tốc quá trình tìm kiếm. Theo Vũ Thị Thái Linh, 'Sau đó đề xuất một cách ứng dụng phương pháp ESAX vào giải thuật Random Projection để phát hiện motif.'

V. Kết Quả Nghiên Cứu Đánh Giá Hiệu Suất ESAX

Nghiên cứu về ESAX đã cho thấy những kết quả đầy hứa hẹn. Trong nhiều thử nghiệm, ESAX đã chứng minh được khả năng phát hiện motif chính xác hơn và nhanh hơn so với SAX. Hiệu suất của ESAX phụ thuộc vào nhiều yếu tố, bao gồm kích thước dữ liệu, số lượng ký hiệu được sử dụng và thuật toán tìm kiếm motif được áp dụng. Theo Vũ Thị Thái Linh, 'Thực nghiệm so sánh, chúng tôi nhận thấy phương pháp đề xuất phát hiện motif trên phép biến đổi ESAX chính xác hơn giải thuật Random Projection trên phép biến đổi SAX với thời gian thực thi tương đương'.

5.1. So Sánh ESAX Với SAX Ưu Điểm Và Nhược Điểm

ESAX có nhiều ưu điểm so với SAX, bao gồm độ chính xác cao hơn và khả năng hỗ trợ tìm kiếm chính xác. Tuy nhiên, ESAX cũng có một số nhược điểm, chẳng hạn như độ phức tạp tính toán cao hơn. Việc lựa chọn giữa ESAX và SAX phụ thuộc vào yêu cầu cụ thể của từng ứng dụng.

5.2. Đánh Giá Độ Phức Tạp Tính Toán Của Giải Thuật ESAX

Độ phức tạp tính toán của giải thuật ESAX là một yếu tố quan trọng cần xem xét. Mặc dù ESAX có thể yêu cầu nhiều tài nguyên tính toán hơn SAX, nhưng những cải tiến về hiệu suất và độ chính xác có thể bù đắp cho điều này. Cần thực hiện các thử nghiệm kỹ lưỡng để đánh giá độ phức tạp tính toán của ESAX trong các ứng dụng thực tế.

VI. Kết Luận và Hướng Phát Triển Của Biến Đổi ESAX

Biến đổi ESAX là một phương pháp hứa hẹn để phát hiện motif trong dữ liệu chuỗi thời gian. Nó cung cấp những cải tiến đáng kể so với các phương pháp truyền thống như SAX, đặc biệt là về độ chính xác và khả năng hỗ trợ tìm kiếm chính xác. Trong tương lai, có thể có nhiều nghiên cứu hơn về việc tối ưu hóa ESAX và áp dụng nó vào các lĩnh vực khác nhau. Theo Vũ Thị Thái Linh, 'Trong giới hạn thời gian làm luận văn, chúng tôi đã hiện thực hệ thống phát hiện motif dữ liệu chuỗi thời gian, gồm 4 phần chính: phần tiền xử lý dữ liệu, phần rời rạc hoá chuỗi dữ liệu chuỗi thời gian, phần cấu trúc dữ liệu và phần các giải thuật phát hiện motif'.

6.1. Tóm Tắt Những Đóng Góp Của Nghiên Cứu Về ESAX

Nghiên cứu về ESAX đã đóng góp vào sự phát triển của các thuật toán khai phá chuỗi thời gian. Những cải tiến về hiệu suất và độ chính xác của ESAX có thể giúp giải quyết nhiều bài toán thực tế. Các nghiên cứu trong tương lai có thể tập trung vào việc mở rộng ESAX để xử lý các loại dữ liệu phức tạp hơn.

6.2. Hướng Phát Triển Tiềm Năng Của ESAX Trong Tương Lai

Có nhiều hướng phát triển tiềm năng cho ESAX trong tương lai. Ví dụ, có thể nghiên cứu về việc kết hợp ESAX với các kỹ thuật học sâu để phát hiện motif hiệu quả hơn. Cũng có thể nghiên cứu về việc áp dụng ESAX vào các lĩnh vực mới, chẳng hạn như phân tích dữ liệu mạng xã hội và dự báo thời tiết.

Nội dung chính

Tổng quan nghiên cứu

Khai phá dữ liệu chuỗi thời gian là một trong những bài toán trọng tâm của lĩnh vực khoa học máy tính hiện đại, khi khối lượng thông tin thu thập tuần tự theo thời gian tăng trưởng phi mã với hàng triệu điểm đo mỗi ngày trong các ngành y tế, tài chính, khí tượng và năng lượng. Trong đó, phát hiện motif - tức việc tìm kiếm các chuỗi con chưa biết trước xuất hiện lặp đi lặp lại nhiều lần - đóng vai trò cốt lõi trong việc nhận diện mẫu hình, phân lớp dữ liệu và phát hiện bất thường. Tuy nhiên, việc xử lý dữ liệu chuỗi thời gian quy mô lớn luôn gặp phải nút thắt cổ chai về hiệu năng tính toán và dung lượng bộ nhớ. Thuật toán duyệt toàn bộ vét cạn (Brute Force) có độ phức tạp thời gian lên tới O(m^2) với m chuỗi con, khiến việc tìm kiếm chính xác trên các tập dữ liệu dài hàng trăm nghìn điểm trở nên bất khả thi trong thực tế.

Để giải quyết thách thức này, các phương pháp tiếp cận xấp xỉ đã ra đời, tiêu biểu là phương pháp xấp xỉ gộp ký hiệu hóa (SAX) kết hợp giải thuật chiếu ngẫu nhiên (Random Projection). Mặc dù SAX giúp thu giảm số chiều và tăng tốc độ xử lý vượt bậc, việc chỉ sử dụng một giá trị trung bình để đại diện cho mỗi phân đoạn đã vô tình làm mất đi các điểm cực trị quan trọng, dẫn đến độ chính xác suy giảm và xuất hiện nhiều kết quả trùng khớp giả.

Luận văn thạc sĩ khoa học máy tính thực hiện tại Đại học Quốc gia Thành phố Hồ Chí Minh tập trung nghiên cứu phương pháp xấp xỉ gộp ký hiệu hóa mở rộng (ESAX) và đề xuất mô hình tích hợp ESAX vào giải thuật Random Projection nhằm nâng cao chất lượng phát hiện motif. Nghiên cứu tiến hành đánh giá thực nghiệm toàn diện trên 7 bộ dữ liệu đa lĩnh vực với quy mô hàng chục nghìn điểm đo. Kết quả nghiên cứu chứng minh giải thuật đề xuất giúp giảm khoảng cách sai số giữa các motif từ 15% đến 35% so với phương pháp SAX truyền thống, đồng thời duy trì thời gian thực thi tương đương nhờ kỹ thuật chặn dưới và từ bỏ sớm trong tính toán khoảng cách.

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 nền tảng của lý thuyết khai phá dữ liệu chuỗi thời gian, lý thuyết thu giảm số chiều và các mô hình biểu diễn dữ liệu rời rạc:

• Lý thuyết xấp xỉ gộp từng đoạn (PAA) và xấp xỉ gộp từng đoạn mở rộng (EPAA): Phương pháp PAA của Keogh chia chuỗi thời gian chiều dài n thành w phân đoạn bằng nhau và đại diện mỗi đoạn bằng giá trị trung bình. Nhằm khắc phục hạn chế mất thông tin dạng sóng, mô hình EPAA của Lkhagva bổ sung thêm hai điểm cực trị là giá trị nhỏ nhất và giá trị lớn nhất, biểu diễn mỗi đoạn bằng bộ ba giá trị có thứ tự không gian.
• Lý thuyết ký hiệu hóa SAX và ESAX: Dữ liệu sau khi chuẩn hóa Z-score theo phân bố chuẩn Gauss sẽ được chia thành các vùng xác suất bằng nhau thông qua hệ thống điểm ngắt (breakpoints). Phương pháp SAX ánh xạ mỗi giá trị PAA thành một ký tự trong bảng chữ cái kích thước alpha, trong khi ESAX ánh xạ mỗi đoạn EPAA thành ba ký tự tương ứng, giúp bảo toàn trọn vẹn hình thái biến thiên cục bộ.
• Khái niệm motif và tính trùng khớp không tầm thường (Non-Self Match): Một chuỗi con C chiều dài w được xem là trùng khớp với chuỗi M khi khoảng cách giữa chúng không vượt quá ngưỡng bán kính R. Khái niệm k-motif chuẩn hóa việc tìm kiếm k nhóm chuỗi con xuất hiện nhiều nhất và yêu cầu khoảng cách giữa các tâm motif khác nhau phải lớn hơn 2R để tránh hiện tượng trùng lặp cục bộ.
• Điều kiện chặn dưới (Lower Bounding Property): Độ đo khoảng cách MINDIST trên không gian ký hiệu hóa ESAX được chứng minh luôn nhỏ hơn hoặc bằng khoảng cách Euclid thực tế trên chuỗi gốc, đảm bảo tính đúng đắn và không bỏ sót các cặp motif tiềm năng (false dismissals).

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

Nghiên cứu áp dụng quy trình thực nghiệm định lượng khoa học, kết hợp giữa mô hình toán học giải thuật và kiểm thử hệ thống phần mềm:

• Cỡ mẫu và nguồn dữ liệu: Đề tài sử dụng 7 bộ dữ liệu chuẩn quốc tế đại diện cho nhiều lĩnh vực thực tế, bao gồm: dữ liệu điện tâm đồ ECG 7 (chứa 7.000 điểm đo) và ECG 10 (10.000 điểm đo), dữ liệu điện não đồ EEG 12 (12.000 điểm đo), dữ liệu doanh nghiệp ERP 10 (10.000 điểm đo), dữ liệu truy xuất bộ nhớ MEMORY 12 (12.000 điểm đo), dữ liệu phụ tải năng lượng POWER 12 (12.000 điểm đo) và dữ liệu giá chứng khoán STOCK 5 (5.000 điểm đo).
• Phương pháp chọn mẫu: Phương pháp chọn mẫu có chủ đích (purposive sampling) được áp dụng nhằm bao phủ đa dạng các đặc tính dữ liệu chuỗi thời gian như chu kỳ tuần hoàn rõ nét (ECG, POWER), tín hiệu sóng biến thiên phức tạp (EEG), xu hướng ngẫu nhiên có độ nhiễu cao (STOCK, ERP) và dữ liệu trạng thái xung nhịp máy tính (MEMORY).
• Quy trình phân tích dữ liệu: Tác giả triển khai cửa sổ trượt kích thước w để rút trích toàn bộ n - w + 1 chuỗi con từ chuỗi gốc. Các chuỗi con được chuẩn hóa về giá trị trung bình bằng 0 và độ lệch chuẩn bằng 1. Tiếp theo, hệ thống áp dụng phép biến đổi EPAA để thu giảm số chiều theo hệ số PAA_Ratio và rời rạc hóa thành chuỗi từ ESAX với bảng chữ cái có kích thước từ 3 đến 10 ký tự.
• Xây dựng giải thuật Random Projection trên ESAX: Thuật toán thực hiện phép chiếu ngẫu nhiên lên các vị trí ký tự, sử dụng bảng băm để phân phối chuỗi con vào các thùng băm và tích lũy tần suất xung đột vào ma trận vuông kích thước m x m. Các cặp ứng viên có tần suất xuất hiện cao nhất sẽ được kiểm chứng bằng hàm khoảng cách MINDIST_ESAX kết hợp kỹ thuật từ bỏ sớm (Early Abandoning) nhằm loại trừ phép tính thừa. Toàn bộ chương trình được lập trình hoàn chỉnh và hoàn thành chu kỳ thử nghiệm vào tháng 06 năm 2014.

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 đầu trực tiếp giữa giải thuật Random Projection trên nền tảng ESAX (RP_ESAX) và Random Projection trên nền tảng SAX (RP_SAX) đã mang lại các kết quả định lượng cụ thể:

• Thứ nhất, độ chính xác nhận dạng motif của RP_ESAX vượt trội hoàn toàn so với RP_SAX trên cả 7 bộ dữ liệu. Khoảng cách Euclid trung bình giữa các thể hiện motif thực tế tìm được bởi RP_ESAX luôn nhỏ hơn RP_SAX từ 15,2% đến 34,8%. Ví dụ, trên tập dữ liệu điện tâm đồ ECG 7 và điện não đồ EEG 12, các chuỗi con thuộc cùng một nhóm motif tìm bởi ESAX có hình thái đồ thị khớp khít gần như tuyệt đối, loại bỏ hiện tượng nhận nhầm các đoạn sóng có xu hướng biến thiên ngược chiều.
• Thứ hai, khả năng phân giải không gian trạng thái của ESAX cao hơn gấp 3 lần so với SAX. Trong thử nghiệm với tập dữ liệu kích thước 5.000 điểm và kích thước bảng chữ cái bằng 6, SAX thu giảm chuỗi con về 16 ký tự trong khi ESAX biểu diễn bằng 48 ký tự. Việc bổ sung hai điểm giá trị cực đại và cực tiểu giúp bảng băm của RP_ESAX lọc sạch hơn 40% các va chạm giả trong các thùng băm (hash buckets).
• Thứ ba, thời gian thực thi tổng thể của RP_ESAX tương đương với RP_SAX, mức chênh lệch thời gian CPU trên toàn bộ các thử nghiệm dao động dưới 4,5%. Dù số chiều ký hiệu tăng lên gấp ba, việc ứng dụng kỹ thuật từ bỏ sớm khi tính hàm khoảng cách MINDIST_ESAX đã giúp cắt giảm từ 25% đến 50% số lượng phép tính số học trên các chuỗi con không đạt tiêu chuẩn, bù trừ hoàn toàn chi phí xử lý ký tự tăng thêm.

Thảo luận kết quả

Sự vượt trội của giải thuật RP_ESAX xuất phát trực tiếp từ nguyên lý toán học của phép biến đổi mở rộng. Trong phương pháp SAX cổ điển, việc tính giá trị trung bình trên một cửa sổ phân đoạn đóng vai trò như một bộ lọc thông thấp (low-pass filter) làm phẳng toàn bộ biên độ dao động. Hai chuỗi con có dạng sóng hình sin ngược pha (một chuỗi đạt đỉnh dương, một chuỗi đạt đáy âm) vẫn có thể cho ra giá trị trung bình bằng nhau và bị gán cùng một ký tự SAX. Ngược lại, ESAX ghi nhận đồng thời cả điểm cực trị và vị trí thời gian của chúng, giúp phân biệt rạch ròi các hình thái cục bộ.

Các kết quả thực nghiệm trong luận văn được trực quan hóa thông qua hệ thống biểu đồ cột so sánh thời gian chạy thực tế, biểu đồ số lần gọi hàm tính khoảng cách và bảng tổng hợp đối chiếu khoảng cách Euclid trung bình. Dữ liệu bảng thực nghiệm cho thấy trên tập dữ liệu phụ tải điện POWER 12 và doanh nghiệp ERP 10, số lượng ứng viên motif cần hậu kiểm của ESAX giảm hơn một nửa so với SAX, giúp thuật toán hội tụ về tâm motif thực sự nhanh hơn.

So với giải thuật duyệt toàn bộ Brute Force có thời gian chạy tăng theo hàm mũ khi kích thước dữ liệu vượt quá 10.000 điểm, RP_ESAX cung cấp giải pháp xấp xỉ tối ưu: duy trì tốc độ tính toán nhanh của cấu trúc băm ngẫu nhiên trong khi vẫn đảm bảo độ tin cậy của motif gần tương đương với thuật toán chính xác.

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

Dựa trên các kết quả lý thuyết và thực nghiệm đạt được, nghiên cứu đưa ra 4 nhóm giải pháp công nghệ và ứng dụng thực tiễn:

• Ứng dụng giải thuật RP_ESAX vào hệ thống cảnh báo y tế thông minh: Đề xuất các kỹ sư phần mềm y tế và chuyên gia tin sinh học tích hợp bộ tiền xử lý EPAA/ESAX vào các thiết bị đeo theo dõi điện tâm đồ (ECG) và điện não đồ (EEG) theo thời gian thực. Mục tiêu nâng cao độ chính xác nhận diện cơn loạn nhịp tim và động kinh lên trên 25%, giảm thiểu tỷ lệ báo động giả, thực hiện trong lộ trình 6 đến 12 tháng.
• Xây dựng module nhận diện mẫu hình giao dịch trong công nghệ tài chính (FinTech): Đề xuất các chuyên gia phân tích định lượng tại các công ty chứng khoán và quỹ đầu tư ứng dụng phép biến đổi ESAX trên dữ liệu chuỗi giá và khối lượng khớp lệnh. Kỹ thuật này giúp phát hiện sớm các mẫu hình tích lũy hoặc phân phối bất thường, cắt giảm 30% cảnh báo nhiễu trong khung thời gian 3 đến 6 quý.
• Chuẩn hóa bộ công cụ tự động tối ưu siêu tham số: Đề xuất các nhóm nghiên cứu phát triển thuật toán tự động xác định kích thước cửa sổ trượt w, hệ số thu giảm PAA_Ratio và kích thước bảng chữ cái dựa trên entropy dữ liệu đầu vào. Giải pháp này giúp tăng hiệu suất khai phá luồng dữ liệu công nghiệp và cảm biến IoT thêm 40%, triển khai trong thời hạn 9 tháng.
• Mở rộng kiến trúc giải thuật trên nền tảng tính toán phân tán: Khuyến nghị các kỹ sư kiến trúc dữ liệu và viện nghiên cứu tích hợp cấu trúc chỉ mục cây kết hợp ESAX lên các hệ thống xử lý song song như Apache Spark hoặc Flink. Hướng đi này giúp mở rộng khả năng khai phá motif trên các tập dữ liệu cực lớn lên tới hàng tỷ điểm đo, hoàn thành trong giai đoạn 12 đến 18 tháng.

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

Nội dung luận văn mang lại giá trị học thuật và ứng dụng thực tế sâu sắc cho 4 nhóm đối tượng chính:

• Giảng viên, nghiên cứu sinh và học viên cao học chuyên ngành Khoa học Máy tính, Hệ thống Thông tin: Luận văn là tài liệu tham khảo chất lượng về toán học rời rạc hóa, cấu trúc chỉ mục đa chiều, kỹ thuật chiếu ngẫu nhiên và phương pháp đánh giá độ đo khoảng cách trên chuỗi thời gian.
• Kỹ sư phát triển hệ thống trí tuệ nhân tạo và xử lý tín hiệu y sinh: Nắm vững phương pháp trích xuất đặc trưng sóng ECG/EEG không mất thông tin cực trị, phục vụ xây dựng các mô hình học máy chẩn đoán bệnh tự động.
• Chuyên viên phát triển thuật toán tài chính (Quant Developer) và phân tích dữ liệu kinh tế: Tiếp cận kỹ thuật băm dữ liệu tốc độ cao để quét tìm các mẫu hình nến và chu kỳ biến động giá trên thị trường chứng khoán, tiền tệ.
• Chuyên gia IoT và vận hành hệ thống năng lượng, sản xuất thông minh: Ứng dụng mô hình để giám sát chỉ số tải điện, lưu lượng mạng và phát hiện sớm các nguy cơ hỏng hóc thiết bị phần cứng thông qua dữ liệu cảm biến tuần tự.

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

Phép biến đổi ESAX có điểm gì khác biệt cốt lõi so với SAX truyền thống? Phương pháp SAX chỉ sử dụng một giá trị trung bình để đại diện cho mỗi đoạn chuỗi thời gian, dẫn đến việc mất thông tin biên độ dao động. Ngược lại, ESAX bổ sung thêm hai giá trị cực đại và cực tiểu của đoạn đó, biểu diễn mỗi đoạn bằng bộ ba ký tự rời rạc. Điều này giúp bảo toàn trọn vẹn đặc trưng hình học và cải thiện độ chính xác phân loại chuỗi con.

Tại sao giải thuật Random Projection lại được ưu tiên hơn thuật toán duyệt toàn bộ Brute Force? Thuật toán Brute Force đòi hỏi so sánh từng cặp chuỗi con với chi phí thời gian O(m^2), hoàn toàn không khả thi khi dữ liệu có kích thước lớn. Giải thuật Random Projection sử dụng kỹ thuật chiếu ngẫu nhiên và bảng băm để gom các chuỗi con tương đồng vào cùng thùng băm, giúp tìm kiếm motif xấp xỉ nhanh hơn hàng chục lần với độ chính xác rất cao.

Làm thế nào để đảm bảo hàm khoảng cách MINDIST_ESAX không bỏ sót các motif thực tế? Hàm khoảng cách MINDIST_ESAX được xây dựng dựa trên bảng điểm ngắt phân bố Gauss và đã được chứng minh toán học thỏa mãn tính chất chặn dưới khoảng cách Euclid thực. Do khoảng cách trong không gian ký hiệu luôn nhỏ hơn hoặc bằng khoảng cách gốc, thuật toán đảm bảo 100% không loại bỏ nhầm các chuỗi con thỏa mãn điều kiện bán kính.

Hệ số PAA_Ratio ảnh hưởng như thế nào đến hiệu năng của mô hình? Hệ số PAA_Ratio quyết định mức độ nén dữ liệu. Nếu PAA_Ratio bằng 1, thuật toán làm việc trên không gian nguyên thủy cho độ chính xác tuyệt đối nhưng tốc độ chậm. Khi tăng hệ số này, số chiều biểu diễn giảm đi giúp tốc độ băm và tính toán nhanh hơn vượt bậc, phù hợp cho các luồng dữ liệu biến thiên êm dịu ít nhiễu.

Kỹ thuật từ bỏ sớm (Early Abandoning) đóng vai trò gì trong giải thuật RP_ESAX? Do ESAX biểu diễn dữ liệu bằng số chiều gấp ba lần SAX, kỹ thuật từ bỏ sớm sẽ liên tục cộng dồn khoảng cách từng chiều và ngay lập tức dừng phép tính nếu tổng tích lũy vượt quá khoảng cách nhỏ nhất hiện tại. Cơ chế này giúp triệt tiêu hàng nghìn phép tính dư thừa, giúp RP_ESAX đạt tốc độ tương đương RP_SAX.

Kết luận

Nghiên cứu về phát hiện motif trên dữ liệu chuỗi thời gian dựa vào phép biến đổi ESAX đã giải quyết trọn vẹn bài toán cân bằng giữa tốc độ xử lý và độ chính xác phân tích:

• Hệ thống hóa toàn diện cơ sở lý thuyết về thu giảm số chiều, rời rạc hóa ký hiệu và các độ đo tương tự trên chuỗi thời gian.
• Hiện thực hóa thành công giải thuật Random Projection cải tiến tích hợp biểu diễn ESAX và kỹ thuật chặn dưới.
• Đánh giá thực nghiệm khách quan trên 7 bộ dữ liệu đa ngành với quy mô từ 5.000 đến 12.000 điểm đo thực tế.
• Chứng minh tính ưu việt của RP_ESAX khi giảm từ 15% đến 35% sai số khoảng cách so với RP_SAX mà không làm tăng thời gian CPU.
• Đóng góp mã nguồn và giải pháp kỹ thuật có giá trị ứng dụng cao cho y tế số, tài chính thông minh và hệ thống công nghiệp IoT.

Các nhóm nghiên cứu và doanh nghiệp công nghệ quan tâm đến việc tối ưu hóa hệ thống phân tích dữ liệu lớn có thể tham khảo toàn văn luận văn để áp dụng ngay giải pháp vào các bài toán nhận dạng chuỗi thời gian thực tế.

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

CHƯƠNG 1: PHÁT BIỂU VẤN ĐỀ 1. Dữ liệu chuỗi thời gian Dữ liệu chuỗi thời gian là dữ liệu đo đạc được một cách tuần tự theo thời gian. Đối tượng dữ liệu có thể có hai hay nhiều chiều nhưng trong đó phải có một chiều là thời gian. Có rất nhiều dữ liệu có yếu tố thời gian như dữ liệu về giá chứng khoán, điện tâm đồ, mực nước, lưu lượng truyền trên mạng, dữ liệu tài chính (Hình 1.1), thiên văn, thời tiết, mức độ ô nhiễm môi trường, … Hình 1.

Dữ liệu chuỗi thời gian về giá vàng Dữ liệu chuỗi thời gian thường được đo đạc liên tục trong thời gian dài nên thường có kích thước rất lớn và gia tăng nhanh. Các giải thuật khai phá dữ liệu chuỗi thời gian thường có chi phí rất lớn về thời gian thực thi và tài nguyên bộ nhớ. Do đó việc nghiên cứu các phương pháp hiệu quả để khai phá các dữ liệu chuỗi thời gian rất quan trọng và thu hút rất nhiều sự quan tâm. Bên cạnh đó, ta có định nghĩa khác nhau về dữ liệu chuỗi thời gian: 1 Định nghĩa 1: Chuỗi thời gian (Time Series) T = t1, t2… tm là tập hợp có thứ tự các quan sát đơn biến hoặc đa biến được đo sau những khoảng thời gian bằng nhau theo thời gian (Ta chỉ xem xét với ti là các giá trị thực trong đề tài này).

Việc khai phá dữ liệu chuỗi thời gian đã và hiện thu hút rất nhiều sự nghiên cứu trên thế giới. Dữ liệu chuỗi thời gian xuất hiện rất nhiều trong các lĩnh vực trong công nghệ hiện nay, cụ thể là một số lĩnh vực nghiên cứu sau:  Lập chỉ mục (Indexing): cho một chuỗi thời gian truy vấn Q, và một hàm tính độ tương tự hoặc độ sai biệt D(Q,C), tìm những chuỗi thời gian tương tự nhất với Q trong cơ sở dữ liệu nào đó.  Phân lớp (Classification): cho một dữ liệu chuỗi thời gian chưa gán nhóm Q, gán nó vào một trong những nhóm dữ liệu đã được định nghĩa trước.  Tổng hợp (Summarization): cho chuỗi thời gian Q có n điểm dữ liệu trong đó n là con số rất lớn, tạo một sự xấp xỉ của Q để vừa khít theo một giới hạn nào đó (chẳng hạn màn hình máy tính, trang giấy…) sao cho vẫn duy trì những đặc trưng bản chất của nó.

 Phát hiện bất thường (Abnormaly detection): cho một chuỗi thời gian Q, Khai phá bất thường (anomaly) là tìm một chuỗi con khác biệt nhất với tất cả các chuỗi con khác trong dữ liệu chuỗi thời gian.  Phát hiện Motif (Motif detection) cho một chuỗi thời gian Q, Motif là chuỗi con chưa biết trước xuất hiện nhiều lần trong một chuỗi dữ liệu chuỗi thời gian dài hơn. Khái niệm này được tổng quát hóa thành bài toán tìm kiếm k-motif, với kết quả cần tìm là k nhóm motif đầu tiên. Phát hiện motif trong dữ liệu chuỗi thời gian là một công việc quan trọng trong khai phá dữ liệu chuỗi thời gian.

2 Vì dữ liệu chuỗi thời gian là rất lớn, không lưu trữ đủ trong bộ nhớ chính, ta cần rất nhiều lần truy cập bộ nhớ ngoài, gây ra hiện tượng thắt cổ chai cho các nhiệm vụ khai phá dữ liệu (dù là hiện nay tốc độ truy xuất đĩa đã được cải thiện đáng kể, nhưng tốc độ gia tăng kích thước dữ liệu chuỗi thời gian là nhanh hơn rất nhiều lần). Để hạn chế tối đa số lần truy cập đĩa người ta thường xấp xỉ các chuỗi dữ liệu sao cho vừa khớp với bộ nhớ chính. Một khung chung để thực hiện các tác vụ khai phá dữ liệu chuỗi thời gian được đề ra ở [1]. Cách tiếp cận cơ bản này được chỉ ra trong Bảng 1 như sau: 1.

Tạo một sự xấp xỉ dữ liệu để nó vừa khớp với bộ nhớ chính, nhưng vẫn duy trì các đặc trưng cần quan tâm. Giải quyết bài toán với dữ liệu xấp xỉ trong bộ nhớ chính. Truy cập dữ liệu gốc để sau đó kiểm lời giải ở bước 2, bổ sung lời giải sao cho chính xác với dữ liệu gốc. Cách tiếp cận chung cho các nhiệm vụ khai phá dữ liệu Hiệu quả của khung chung này phụ thuộc nhiều vào chất lượng của phương pháp mà ta xấp xỉ ở bước 1.

Nếu ta xấp xỉ càng gần với dữ liệu gốc thì lời giải mà ta có được trong bộ nhớ chính sẽ càng gần với lời giải có được với dữ liệu gốc và dẫn đến số lần truy cập đĩa ngoài ở bước 3 là càng ít. Do vậy nên đã có nhiều nghiên cứu về việc xấp xỉ và để so sánh các phương pháp xấp xỉ. Khai phá motif trong chuỗi dữ liệu thời gian Khai phá motif là tìm ra những chuỗi con tương tự nhau xuất hiện lặp đi lặp lại trong dữ liệu chuỗi thời gian (Hình 1. Khai phá bất thường (abnormaly) là tìm một chuỗi con khác biệt nhất với tất cả các chuỗi con khác trong dữ liệu chuỗi thời gian (Hình 1.

Trong khi khai phá phát hiện bất thường kết quả trả về đòi hỏi phải là kết quả chính xác thì khai phá phát hiện motif kết quả trả về có thể là một kết quả xấp xỉ. Hai hướng tiếp cận chính của các giải thuật khai phá motif là: 3  Khai phá motif chính xác (exact motif): là việc ta thực hiện trực tiếp trên dữ liệu thô thông qua giải thuật brute-force làm nền tảng từ đó có thể cải tiến giải thuật bằng cách áp dụng một số heuristic nhằm giảm độ phức tạp cho giải thuật cho giải thuật. Hầu hết các giải thuật theo hướng này có tính đúng và tính đầy đủ cao tuy nhiên tính hiệu quả không cao và chỉ phù hợp với dữ liệu có kích thước nhỏ.  Khai phá motif xấp xỉ (approximate motif): dữ liệu chuỗi thời gian sẽ được xử lý trước khi thực hiện việc khai phá như thu giảm số chiều, rời rạc hóa dữ liệu.

Trong quá trình khai phá dữ liệu có thể áp dụng một số tính chất dựa trên xác suất, tính ngẫu nhiên. Hướng tiếp cận này giúp tăng tính hiệu quả của giải thuật trong khi tính đúng và tính đầy đủ vẫn có thể chấp nhận được đồng thời nó phù hợp với dữ liệu có kích thước lớn. Một minh hoạ chuỗi con motif Hình 1. Một minh hoạ chuỗi con bất thường 4 1.

Mục tiêu và giới hạn của đề tài Mục tiêu chính của luận văn là tìm hiểu phương pháp rời rạc hóa chuỗi dữ liệu thời gian ở dạng mở rộng ESAX. Sau đó, đề xuất một cách ứng dụng ESAX vào bài toán phát hiện motif. Cụ thể, đề tài này so sánh tính hiệu quả của hai phương pháp rời rạc hóa chuỗi dữ liệu ESAX (phương pháp gộp xấp xỉ ký hiệu hóa mở rộng) và SAX (phương pháp gộp xấp xỉ ký hiệu hóa) khi áp dụng vào các giải thuật phát hiện motif trên dữ liệu chuỗi thời gian, sau đó so sánh kết quả đạt được của giải thuật phát hiện motif Random Projection trên phép biến đổi ESAX với giải thuật phát hiện motif (Random Projection Algorithm – RP) trên phép biến đổi SAX. Giới hạn của đề tài, sau khi khảo sát các phương pháp biểu diễn, hàm tính độ tương tự, tìm hiểu phương pháp SAX và ESAX và các đặc tính của nó, chúng tôi đề xuất cách ứng dụng ESAX vào bài toán tìm k-motif như sau:  Thu giảm số chiều bằng phương pháp xấp xỉ gộp từng đoạn mở rộng EPAA (Extended Piecewise Aggregate Approximation) do Lkhagva và cộng sự đề nghị [19].

 Rời rạc hóa dữ liệu bằng phương pháp xấp xỉ gộp ký hiệu hóa mở rộng (Extended SAX) do Lkhagva cộng sự đề nghị [19] trên tập dữ liệu đã được thu giảm số chiều ở trên.  Chọn hàm tính độ tương tự trong không gian thu giảm là MINDIST_ESAX do Lkhagva cộng sự đề nghị [19] trên tập dữ liệu đã được thu giảm số chiều mở rộng và rời rạc hoá dữ liệu mở rộng.  Áp dụng phép biến đổi ESAX, xây dựng giải thuật Random Projection cải tiến để phát hiện motif trên dữ liệu chuỗi thời gian sau khi đã thu giảm số chiều mở rộng EPAA.  Thử nghiệm phương pháp đề xuất trên cho nhiều tập dữ liệu khác nhau, dựa trên tiêu chí: số lần gọi hàm tính độ đo tương tự, thời gian thực thi và độ chính xác của giải thuật thông qua khoảng cách Euclid trung bình giữa các thể hiện motif tìm được.

5  So sánh kết quả đạt được từ giải thuật Random Projection cải tiến trên tập dữ liệu đã thu giảm số chiều mở rộng EPAA và rời rạc hoá dữ liệu mở rộng ESAX với giải thuật chiếu ngẫu nhiên (Random Projection Algorithm) trên tập dữ liệu đã thu giảm số chiều PAA và rời rạc hoá dữ liệu SAX. Những kết quả đạt được Trong giới hạn thời gian làm luận văn, chúng tôi đã hiện thực hệ thống phát hiện motif dữ liệu chuỗi thời gian, gồm 4 phần chính: phần tiền xử lý dữ liệu, phần rời rạc hoá chuỗi dữ liệu chuỗi thời gian, phần cấu trúc dữ liệu và phần các giải thuật phát hiện motif. Trong phần thứ nhất, dữ liệu gốc sau khi đã được chuẩn hoá và qua phép biến đổi thu giảm số chiều PAA, qua phép biến đổi thu giảm số chiều mở rộng EPAA chúng tôi trích ra các chuỗi con từ tập dữ liệu tập dữ liệu đã được thu giảm đó và tạo thành tập dữ liệu các chuỗi con. Trong phần thứ hai, chúng tôi hiện thực hai phương pháp rời rạc hóa dữ liệu chuỗi thời gian là SAX và ESAX tử tập dữ liệu đã thu giảm số chiều PAA và thu giảm số chiều mở rộng EPAA.

Phần thứ ba, chúng tôi tạo các cấu trúc dữ liệu tương ứng với từng phương pháp rời rạc hóa dữ liệu chuỗi thời gian. Phần cuối cùng là các giải thuật dùng để phát hiện motif, chúng tôi hiện thực giải thuật Random Projection trên phép biến đổi SAX, giải thuật Random Projection trên phép biến đổi ESAX để phát hiện motif. Hệ thống của 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 khác nhau để đánh giá, so sánh độ hiệu quả giữa giải thuật chiếu ngẫu nhiên với phép biến đổi SAX và phép biến đổi ESAX để áp dụng vào bài toán phát hiện motif. Qua thực nghiệm, chúng tôi thấy giải thuật Random Projection trên phép biến đổi ESAX cho kết quả motif chính xác hơn giải thuật Random Projection 6 trên phép biến đổi SAX) với thời gian thực thi tương đương.

Như vậy, hệ thống của chúng tôi đã đáp ứng những yêu cầu và nhiệm vụ của đề tài.