Phát hiện bất thường trên chuỗi thời gian với kỹ thuật rời rạc hóa dữ liệu

Chuyên khảo kỹ thuật phân tích Hcmute phát hiện bất thường trên chuỗi thời gian dựa vào kỹ thuật rời rạc hóa dữ liệu, đánh giá các khía cạnh quan trọng, đề xuất hướng nghiên cứu

• Tác giả: Nguyễn Thành Sơn
• Trường học: Trường Đại Học Sư Phạm Kỹ Thuật Thành Phố Hồ Chí Minh
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: Phát Hiện Bất Thường Trong Chuỗi Thời Gian Dựa Vào Kỹ Thuật Rời Rạc Hóa Dữ Liệu
• Loại tài liệu: báo cáo tổng kết đề tài KH&CN cấp trường
• Năm xuất bản: 2020
• Địa điểm: Thành Phố Hồ Chí Minh

Mục lục chi tiết

• PHẦN MỞ ĐẦU
• 1. CHƯƠNG 1: CÁC KIẾN THỨC CƠ SỞ
• 1.1. Tổng quan về đề tài
• 1.2. Các kiến thức cơ bản
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Phát hiện bất thường trong chuỗi thời gian

Phần này tập trung vào khái niệm phát hiện bất thường trong ngữ cảnh chuỗi thời gian. Tài liệu đề cập đến việc xác định các chuỗi con bất thường (unusual, abnormal, discord), tức là những đoạn dữ liệu khác biệt rõ rệt so với phần còn lại của chuỗi thời gian. Đây là một bài toán quan trọng trong nhiều lĩnh vực, bao gồm chẩn đoán lỗi, phát hiện gian lận, giám sát hệ thống, và phân tích dữ liệu. Tài liệu nhấn mạnh tính cấp thiết của việc nghiên cứu các thuật toán hiệu quả hơn cho phát hiện bất thường, đặc biệt khi xử lý các chuỗi thời gian lớn. Nhiều thuật toán đã được đề xuất, nhưng hầu hết tập trung vào tìm kiếm trong không gian gốc, dẫn đến thời gian tính toán cao. Do đó, việc tìm kiếm các phương pháp tối ưu về thời gian và không gian lưu trữ là rất cần thiết. Phát hiện điểm bất thường là một nhiệm vụ then chốt trong quá trình này.

1.1 Tổng quan về các phương pháp phát hiện bất thường

Tài liệu trình bày tổng quan về một số thuật toán phát hiện bất thường đã có, bao gồm Brute Force Discord Discovery (BFDD), Heuristic Discord Discovery (HDD), Hot SAX, WAT, HotiSAX, WATiSAX, và Disk Aware Discord Discovery. Các thuật toán này đa phần thực hiện tìm kiếm trong không gian gốc của dữ liệu chuỗi thời gian. Mặc dù không cần thu giảm số chiều, phương pháp này thường dẫn đến độ phức tạp tính toán cao, thậm chí là hàm mũ theo kích thước dữ liệu trong trường hợp xấu nhất. Tài liệu cũng đề cập đến các phương pháp sử dụng biến đổi Fourier rời rạc (DFT), biến đổi Wavelet rời rạc, và xấp xỉ gộp từng đoạn (PAA) để giảm chiều dữ liệu trước khi thực hiện phát hiện bất thường. Kỹ thuật rời rạc hóa dữ liệu được xem là một giải pháp tiềm năng để cải thiện hiệu quả. Việc lựa chọn phương pháp rời rạc hóa thích hợp sẽ ảnh hưởng đến độ chính xác và tốc độ của quá trình phát hiện bất thường. Thuật toán phát hiện bất thường dựa trên kỹ thuật rời rạc hóa được xem là trọng tâm của nghiên cứu này. Giám sát chuỗi thời gian và phân tích dữ liệu thời gian là những ứng dụng thực tế quan trọng.

1.2 Thách thức và cơ hội

Một trong những thách thức lớn nhất trong phát hiện bất thường trong chuỗi thời gian là xử lý khối lượng dữ liệu khổng lồ. Dữ liệu chuỗi thời gian thường rất lớn, ví dụ như dữ liệu điện tâm đồ (ECG) có thể lên tới 1GB chỉ trong 1 giờ. Ngoài ra, việc đánh giá độ tương tự giữa các chuỗi thời gian cũng phụ thuộc nhiều vào yếu tố chủ quan của người dùng và đặc điểm của tập dữ liệu. Dữ liệu không đồng nhất về định dạng, tần suất lấy mẫu, và sự hiện diện của nhiễu cũng gây khó khăn. Tuy nhiên, kỹ thuật rời rạc hóa dữ liệu mở ra cơ hội để giải quyết những thách thức này. Bằng cách giảm số chiều dữ liệu, kỹ thuật rời rạc hóa giúp giảm thời gian tính toán và dung lượng lưu trữ. Việc kết hợp kỹ thuật rời rạc hóa với các thuật toán phát hiện bất thường thông minh có thể tạo ra các hệ thống hiệu quả và chính xác hơn. Xử lý ngoại lệ là một lĩnh vực ứng dụng quan trọng. An ninh mạng và giám sát hệ thống là những ví dụ điển hình.

II. Kỹ thuật rời rạc hóa dữ liệu và ứng dụng trong phát hiện bất thường

Phần này tập trung vào kỹ thuật rời rạc hóa dữ liệu như một công cụ quan trọng để xử lý chuỗi thời gian. Rời rạc hóa dữ liệu chuyển đổi dữ liệu liên tục thành dạng rời rạc, giúp giảm độ phức tạp của chuỗi thời gian và đơn giản hóa quá trình tính toán. Tài liệu đề cập đến một số phương pháp rời rạc hóa, bao gồm Symbolic Aggregate approXimation (SAX), Piecewise Aggregate Approximation (PAA), và Adaptive Piecewise Constant Approximation (APCA). Sự lựa chọn phương pháp phụ thuộc vào đặc điểm của dữ liệu chuỗi thời gian và yêu cầu của bài toán. Rời rạc hóa chuỗi thời gian giúp giảm kích thước dữ liệu, tăng tốc độ tính toán và cải thiện hiệu quả của thuật toán phát hiện bất thường. Phân tích dữ liệu chuỗi thời gian dựa trên dữ liệu rời rạc sẽ hiệu quả hơn. Giảm số chiều chuỗi thời gian là một lợi ích chính của kỹ thuật này.

2.1 Các phương pháp rời rạc hóa phổ biến

Tài liệu mô tả chi tiết các phương pháp rời rạc hóa như SAX, PAA, và APCA. SAX chuyển đổi chuỗi thời gian thành một chuỗi các ký tự, trong khi PAA chia chuỗi thời gian thành các đoạn và tính giá trị trung bình của mỗi đoạn. APCA là một phương pháp cải tiến của PAA, cho phép thích ứng với các biến đổi khác nhau trong chuỗi thời gian. Mỗi phương pháp có ưu điểm và nhược điểm riêng. SAX hiệu quả về mặt không gian nhưng có thể làm mất một số thông tin chi tiết. PAA đơn giản và nhanh nhưng có thể không chính xác trong một số trường hợp. APCA tìm kiếm sự cân bằng giữa độ chính xác và hiệu quả. Sự lựa chọn phương pháp rời rạc hóa phụ thuộc vào yêu cầu của bài toán và đặc điểm của dữ liệu chuỗi thời gian. Xử lý dữ liệu chuỗi thời gian bằng kỹ thuật rời rạc hóa là trọng tâm nghiên cứu. Thuật toán rời rạc hóa là một thành phần quan trọng trong hệ thống. Chỉ mục đường chân trời cũng được đề cập đến.

2.2 Ứng dụng trong phát hiện bất thường

Sau khi rời rạc hóa dữ liệu, thuật toán phát hiện bất thường được áp dụng lên dữ liệu rời rạc để tìm kiếm các điểm bất thường. Việc sử dụng dữ liệu rời rạc giúp giảm thời gian tìm kiếm và tăng hiệu quả của thuật toán. Tài liệu đề cập đến việc kết hợp kỹ thuật rời rạc hóa với các thuật toán phát hiện bất thường như HDD và các phương pháp vét cạn. Kết quả thực nghiệm cho thấy phương pháp này có hiệu quả cao hơn so với các phương pháp truyền thống. Việc lựa chọn thuật toán phát hiện bất thường phù hợp sau khi rời rạc hóa là rất quan trọng. Khai phá dữ liệu chuỗi thời gian được tối ưu hóa nhờ phương pháp rời rạc hóa. Phân tích hội quy chuỗi thời gian cũng có thể được ứng dụng. Mô hình chuỗi thời gian được đơn giản hóa.

III. Kết luận và ứng dụng thực tiễn

Nghiên cứu đề xuất một phương pháp phát hiện bất thường mới dựa trên kỹ thuật rời rạc hóa dữ liệu. Phương pháp này có hiệu quả cao về thời gian và không gian lưu trữ, nhờ việc tìm kiếm trong không gian thu giảm của chuỗi thời gian. Kết quả thực nghiệm trên các tập dữ liệu khác nhau chứng minh tính hiệu quả của phương pháp. Đóng góp của đề tài là việc đề xuất một thuật toán mới, tối ưu hơn về mặt hiệu năng. Hạn chế của đề tài có thể là tính chính xác của kết quả, phụ thuộc vào phương pháp rời rạc hóa được sử dụng. Hướng phát triển trong tương lai có thể tập trung vào việc cải tiến thuật toán, mở rộng ứng dụng cho các loại chuỗi thời gian khác nhau, và tích hợp với các hệ thống giám sát thực tế.

3.1 Ứng dụng trong các lĩnh vực khác nhau

Phương pháp phát hiện bất thường dựa trên kỹ thuật rời rạc hóa có tiềm năng ứng dụng rộng rãi trong nhiều lĩnh vực. Giám sát hệ thống, phát hiện gian lận, an ninh mạng, và chẩn đoán y tế là một số ví dụ. Trong giám sát hệ thống, phương pháp này giúp phát hiện các lỗi hoặc sự cố bất thường trong hoạt động của hệ thống. Trong phát hiện gian lận, phương pháp này giúp phát hiện các giao dịch đáng ngờ. Trong an ninh mạng, phương pháp này giúp phát hiện các cuộc tấn công hoặc hoạt động bất thường. Trong chẩn đoán y tế, phương pháp này giúp phát hiện các bệnh tật dựa trên dữ liệu chuỗi thời gian từ các thiết bị y tế. Quản lý rủi ro cũng là một lĩnh vực ứng dụng quan trọng.

3.2 Giá trị và ý nghĩa nghiên cứu

Nghiên cứu này có ý nghĩa lý luận và thực tiễn quan trọng. Về mặt lý luận, nghiên cứu đóng góp vào việc phát triển các thuật toán phát hiện bất thường hiệu quả hơn. Về mặt thực tiễn, nghiên cứu cung cấp một công cụ hữu ích cho việc phân tích và xử lý dữ liệu chuỗi thời gian trong nhiều lĩnh vực. Mô hình ARIMA, mô hình LSTM, và mô hình Prophet là một số mô hình có thể được tích hợp với phương pháp này. Nghiên cứu này cũng có giá trị trong giảng dạy và nghiên cứu sau đại học về khai phá dữ liệu chuỗi thời gian. Học máy chuỗi thời gian và thống kê chuỗi thời gian là những lĩnh vực liên quan.

Nội dung chính

Báo Cáo Khoa Học: Phát Hiện Bất Thường Trên Chuỗi Thời Gian Dựa Vào Kỹ Thuật Rời Rạc Hóa Dữ Liệu

Thông tin đề tài:

• Tên đề tài: Phát hiện bất thường trên chuỗi thời gian dựa vào kỹ thuật rời rạc hóa dữ liệu chuỗi thời gian
• Mã số đề tài: T2019-30TĐ
• Chủ nhiệm đề tài: TS. Nguyễn Thành Sơn
• Đơn vị chủ trì: Trường Đại học Sư phạm Kỹ thuật TP. Hồ Chí Minh (Khoa Công nghệ Thông tin)
• Thời gian nghiệm thu: Tháng 02/2020

---

1. Tóm tắt nghiên cứu (Research Summary)

Phát hiện bất thường trên chuỗi thời gian (Time Series Discord Discovery) là một trong những bài toán cốt lõi và thách thức nhất trong lĩnh vực khai phá dữ liệu (Data Mining). Câu hỏi nghiên cứu trọng tâm của đề tài là: Làm thế nào để xác định chính xác và nhanh chóng các chuỗi con bất thường (discord) trong cơ sở dữ liệu chuỗi thời gian có dung lượng lớn mà không chịu ảnh hưởng bởi sự bùng nổ chi phí tính toán $O(m^2)$ của các phương pháp truyền thống?

Để giải quyết thách thức này, nghiên cứu đề xuất một khung thuật toán hai giai đoạn đột phá:

1. Giai đoạn 1: Ứng dụng kỹ thuật xấp xỉ gộp từng đoạn (Piecewise Aggregate Approximation - PAA) kết hợp với kỹ thuật rời rạc hóa chuỗi thời gian (Symbolic Aggregate approXimation - SAX) nhằm thu giảm số chiều và ánh xạ dữ liệu số thực sang không gian ký hiệu biểu trưng, từ đó sàng lọc nhanh chóng danh sách ứng viên bất thường qua một lần quét dữ liệu duy nhất.
2. Giai đoạn 2: Tiến hành thẩm định và loại bỏ các ứng viên sai trong không gian gốc bằng khoảng cách Euclid kết hợp kỹ thuật từ bỏ sớm (Early Abandoning).

Kết quả thực nghiệm trên các tập dữ liệu thực tế đa dạng (Stock, Discord Anomaly - EEG, Federal Fund) với kích thước lên đến 15.000 chuỗi và độ dài chuỗi bất thường từ 64 đến 1024 điểm chứng minh rằng: Thuật toán đề xuất có tốc độ thực thi vượt trội hơn hẳn so với thuật toán Disk Aware Discord Discovery của Yankov et al., đồng thời bảo toàn độ chính xác tuyệt đối (100%) tương đương với giải thuật quy chuẩn vét cạn (Brute-force). Kết quả này mở ra tiềm năng ứng dụng to lớn trong giám sát tín hiệu y sinh học, quản trị rủi ro tài chính và an ninh mạng.

---

2. Bối cảnh và tầm quan trọng (Context & Significance)

Thực trạng nghiên cứu hiện tại

Trong kỷ nguyên số hóa và vạn vật kết nối (IoT), dữ liệu chuỗi thời gian (Time Series Data) được sinh ra liên tục với khối lượng khổng lồ từ nhiều lĩnh vực: thiết bị cảm biến y tế (điện tâm đồ ECG, điện não đồ EEG), thị trường chứng khoán, giao dịch tài chính, nhật ký mạng máy tính và khí tượng thủy văn. Chỉ riêng một giờ theo dõi tín hiệu điện tâm đồ đã có thể tạo ra dung lượng dữ liệu vượt quá 1GB. Dữ liệu này mang đặc trưng phức tạp: số chiều lớn, tần số lấy mẫu không đồng nhất và thường xuyên chứa nhiễu.

Khoảng trống nghiên cứu (Research Gap)

Khái niệm "chuỗi con bất thường" (Time Series Discord) do Eamonn Keogh định nghĩa là chuỗi con có khoảng cách tới lân cận không tầm thường (non-trivial nearest neighbor) gần nhất là lớn nhất. Phát hiện chuỗi con này có vai trò sống còn trong việc phát hiện sớm bệnh lý tim mạch, gian lận thanh toán hay các cuộc tấn công mạng xâm nhập.

Tuy nhiên, rào cản lớn nhất nằm ở độ phức tạp tính toán:

• Thuật toán vét cạn (Brute-force) duyệt toàn bộ các cặp chuỗi con với chi phí thời gian bậc hai $O(m^2)$, hoàn toàn bất khả thi khi dữ liệu lớn.
• Các thuật toán cải tiến trong không gian gốc (Raw Data Space) tuy không phải trải qua khâu thu giảm số chiều nhưng lại tiêu tốn tài nguyên xử lý và chi phí truy xuất đĩa (Disk I/O) vô cùng lớn.
• Các giải pháp heuristic trước đây như Hot SAX, WAT, HOTiSAX hay WATiSAX dù đã cải thiện tốc độ nhưng vẫn tồn tại hạn chế về tính tổng quát hóa hoặc cấu trúc chỉ mục phức tạp khi dữ liệu gia tăng.

Tính cấp thiết và tác động

Đề tài được thực hiện nhằm lấp đầy khoảng trống này bằng cách kết hợp sức mạnh biểu diễn của kỹ thuật rời rạc hóa SAX trên không gian thu giảm và kỹ thuật cắt tỉa khoảng cách thông minh Early Abandoning. Giải pháp này vừa giảm thiểu việc truy cập đĩa cứng (chỉ cần một lần quét toàn bộ cơ sở dữ liệu), vừa thu hẹp không gian tìm kiếm, đem lại tác động thiết thực cả về mặt học thuật lẫn triển khai thực tiễn.

---

3. Phương pháp luận và cách tiếp cận (Methodology & Approach)

Nghiên cứu áp dụng quy trình thiết kế giải thuật chặt chẽ, dựa trên nền tảng toán học của đại số chuỗi thời gian và lý thuyết xấp xỉ tín hiệu:

[Dữ liệu chuỗi thời gian gốc T] 
               │
               ▼ (Chuẩn hóa Z-score / Min-Max)
[Chuỗi đã chuẩn hóa]
               │
               ▼ (Giảm chiều PAA: n điểm -> w đoạn)
[Chuỗi hệ số PAA]
               │
               ▼ (Rời rạc hóa SAX dựa trên Điểm ngắt Gauss)
[Chuỗi ký hiệu SAX]
               │
               ▼ (Giai đoạn 1: Quét đơn & Tính khoảng cách DSAX)
[Tập ứng viên bất thường tiềm năng C]
               │
               ▼ (Giai đoạn 2: Hậu kiểm không gian gốc + Early Abandoning)
[Danh sách các chuỗi Discord thực sự chính xác 100%]

1. Khung tiền xử lý và thu giảm số chiều (Dimensionality Reduction)

• Chuẩn hóa dữ liệu: Sử dụng chuẩn hóa Z-score (Zero-Mean Normalization) $Q'[i] = \frac{Q[i] - \text{mean}(Q)}{\text{var}(Q)}$ nhằm triệt tiêu sự sai khác về biên độ và đường cơ sở (baseline offset).
• Thu giảm số chiều PAA: Chia chuỗi dữ liệu gốc có độ dài $n$ thành $w$ đoạn con bằng nhau ($w \ll n$) và lấy giá trị trung bình từng đoạn, giúp giảm mạnh chiều dữ liệu nhưng vẫn giữ nguyên đường bao xu hướng.

2. Kỹ thuật rời rạc hóa SAX và nguyên lý Chặn Dưới (Lower Bounding)

• Rời rạc hóa SAX: Ánh xạ các giá trị trung bình PAA thành chuỗi ký tự rời rạc thông qua các điểm ngắt (breakpoints) xác định từ bảng xác suất phân bố chuẩn Gauss (với kích thước bảng chữ cái $a$ từ 3 đến 7).
• Đảm bảo tính hợp lệ: Độ đo khoảng cách $D_{SAX}$ được thiết kế thỏa mãn Bổ đề chặn dưới (Lower Bounding Lemma): $$D_{SAX}(\bar{Q}, \bar{C}) \le D_{Euclid}(Q, C)$$ Điều này đảm bảo không bao giờ xảy ra lỗi tìm sót (false dismissals), nghĩa là các chuỗi bất thường thực sự chắc chắn nằm trong tập ứng viên được chọn.

3. Quy trình thuật toán hai giai đoạn

• Giai đoạn 1 - Lọc ứng viên: Quét cơ sở dữ liệu đúng một lần. Mỗi chuỗi thời gian sau khi biến đổi thành chuỗi SAX sẽ được so sánh với các ứng viên hiện có trong tập $C$. Nếu khoảng cách $D_{SAX}(S_i, S_j) < \epsilon_1$ (ngưỡng tương tự trong không gian SAX), ứng viên đó sẽ bị loại vì đã tìm thấy lân cận tương đồng.
• Giai đoạn 2 - Hậu kiểm với Kỹ thuật từ bỏ sớm (Early Abandoning): Duyệt lại tập ứng viên $C$ trên không gian gốc. Khi tính khoảng cách Euclid giữa ứng viên $T_j$ và các chuỗi trong cơ sở dữ liệu, ngay khi tổng lũy kế khoảng cách bình phương vượt qua ngưỡng $\text{dist}_j$ hiện tại hoặc ngưỡng $\epsilon_2$, thuật toán lập tức dừng việc tính toán (abandon). Cơ chế này loại bỏ đến 80-90% các phép tính căn thức và cộng dồn không cần thiết.

---

4. Các phát hiện chính (Key Findings)

Thực nghiệm được triển khai độc lập bằng ngôn ngữ C# trên hệ thống máy tính trang bị CPU Intel Core i5 (2.50GHz), đối chiếu trực tiếp giữa Phương pháp đề xuất, thuật toán quy chuẩn Brute-force, và thuật toán đối chuẩn tiên tiến Yankov's Disk Aware Discord Discovery.

| Tập dữ liệu | Kích thước tập dữ liệu ($|T|$) | Chiều dài Discord ($n$) | Thời gian Yankov (s) | Thời gian Đề xuất (s) | Tỷ lệ cải thiện tốc độ | | :--- | :--- | :--- | :--- | :--- | :--- | | Stock (Chứng khoán) | 8.000 chuỗi | Thay đổi (64 - 1024) | ~190s (tại $n=1024$) | ~110s (tại $n=1024$) | Nhanh hơn ~42% | | Discord Anomaly (EEG) | 4.000 chuỗi | Thay đổi (64 - 1024) | ~45s (tại $n=1024$) | ~28s (tại $n=1024$) | Nhanh hơn ~38% | | Federal Fund (Lãi suất) | 10.000 chuỗi | Thay đổi (64 - 1024) | ~150s (tại $n=1024$) | ~90s (tại $n=1024$) | Nhanh hơn ~40% | | Stock (Quy mô mở rộng) | 2.000 - 15.000 chuỗi | Cố định ($n = 512$) | ~135s (tại 15k mẫu) | ~75s (tại 15k mẫu) | Nhanh hơn ~44% | | EEG (Quy mô mở rộng) | 2.000 - 15.000 chuỗi | Cố định ($n = 512$) | ~78s (tại 15k mẫu) | ~42s (tại 15k mẫu) | Nhanh hơn ~46% | | Federal (Quy mô mở rộng)| 2.000 - 15.000 chuỗi | Cố định ($n = 512$) | ~138s (tại 15k mẫu) | ~80s (tại 15k mẫu) | Nhanh hơn ~42% |

Đánh giá chuyên sâu về kết quả:

1. Hiệu năng xử lý vượt bậc: Thuật toán đề xuất liên tục vượt qua phương pháp của Yankov trên tất cả các kịch bản kiểm thử. Khi kích thước cơ sở dữ liệu tăng từ 2.000 lên 15.000 chuỗi, đường cong thời gian thực thi của thuật toán đề xuất có độ dốc thấp hơn rõ rệt, chứng minh tính mở rộng (scalability) rất cao.
2. Độ chính xác tuyệt đối (100% Precision & Recall): Kiểm chứng trực quan hình thái dạng sóng của các đoạn dị biệt phát hiện được cho thấy: các bất thường do phương pháp đề xuất tìm ra hoàn toàn trùng khớp với kết quả chuẩn của thuật toán vét cạn Brute-force và thuật toán của Yankov trên mọi tập dữ liệu thử nghiệm.
3. Cắt giảm tối đa chi phí Disk I/O: Việc chỉ cần duy nhất 1 lượt quét tuyến tính toàn bộ dữ liệu trên đĩa và một số ít thao tác đọc ngẫu nhiên trong pha 2 giúp giải thuật vận hành mượt mà ngay cả khi tài nguyên RAM bị giới hạn.

---

5. Đóng góp khoa học và giá trị học thuật (Scientific Contributions)

Đóng góp về mặt lý thuyết

• Làm sáng tỏ cơ chế tối ưu hóa tìm kiếm lân cận trong không gian biểu trưng bằng việc kết hợp đồng thời xấp xỉ PAA, rời rạc hóa SAX và bổ đề khoảng cách chặn dưới.
• Chứng minh tính đúng đắn về mặt toán học trong việc triệt tiêu so trùng tầm thường (trivial match elimination) khi xử lý các chuỗi con trượt liên tiếp.

Đổi mới về mặt phương pháp luận

• Xây dựng thành công thuật toán phát hiện bất thường kết hợp 2 pha: Lọc thô trong không gian ký hiệu $\rightarrow$ Tinh chỉnh trong không gian thực nghiệm bằng Early Abandoning.
• Giảm thiểu độ phức tạp tính toán trung bình từ $O(m^2)$ xuống tiệm cận mức tuyến tính đối với pha quét dữ liệu, giải quyết bài toán nghẽn cổ chai I/O trên đĩa từ.

Ý nghĩa thực tiễn và ứng dụng

• Công bố khoa học: Đề tài đã công bố bài báo khoa học chất lượng cao trên Tạp chí Khoa học Giáo dục Kỹ thuật (Journal of Technical Education Science - HCMUTE) với tiêu đề: "Discovering Time Series Discord Based On A Discrete Method".
• Giảng dạy và Đào tạo: Cung cấp học liệu, thuật toán mẫu và bài giảng chuyên đề chuyên sâu cho chương trình đào tạo Thạc sĩ, Tiến sĩ ngành Khoa học Máy tính và Kỹ thuật Phần mềm.

---

6. Đối tượng quan tâm và Giá trị ứng dụng (Target Audience & Benefits)

Nghiên cứu này mang lại giá trị thiết thực cho nhiều nhóm đối tượng:

• Nhà nghiên cứu học thuật (Data Mining & AI Researchers): Tham khảo kiến trúc giải thuật kết hợp giữa biểu diễn tượng trưng (Symbolic Representation) và tối ưu hóa không gian metric để phát triển các mô hình khai phá mẫu (Motif Discovery) hoặc phân lớp chuỗi thời gian.
• Kỹ sư Y sinh & Y tế số (Healthcare & Biomedical Engineers): Tích hợp vào hệ thống máy theo dõi bệnh nhân tự động để phát hiện các cơn co thắt cơ tim bất thường qua điện tâm đồ (ECG) hoặc sóng động kinh qua điện não đồ (EEG) theo thời gian thực.
• Chuyên gia Phân tích Tài chính & Định lượng (Financial Analysts & Quants): Nhận diện nhanh các biến động giá bất thường, phát hiện giao dịch gian lận hoặc biến động lãi suất liên ngân hàng bất thường.
• Kỹ sư Hệ thống IoT & An toàn thông tin (IoT & Cybersecurity Engineers): Giám sát lưu lượng mạng viễn thông để ngăn chặn tấn công DDoS, rò rỉ dữ liệu hoặc phát hiện lỗi hỏng hóc trong cảm biến dây chuyền sản xuất tự động.

---

7. Các câu hỏi thường gặp (FAQ)

1. Điểm mấu chốt nào giúp thuật toán đạt tốc độ nhanh hơn thuật toán của Yankov et al.?

Thuật toán tận dụng sự phối hợp giữa việc rời rạc hóa SAX trong không gian PAA để loại bỏ cực nhanh các ứng viên không tiềm năng ngay trong bộ nhớ, kết hợp cùng kỹ thuật Early Abandoning ở pha hậu kiểm, giúp ngắt sớm các phép tính khoảng cách Euclid đắt đỏ ngay khi vượt ngưỡng.

2. Rời rạc hóa dữ liệu từ số thực sang ký tự có làm mất mát thông tin và bỏ sót dị biệt không?

Hoàn toàn không. Thuật toán tuân thủ nguyên lý Bổ đề chặn dưới ($D_{SAX} \le D_{Euclid}$). Khoảng cách trong không gian ký hiệu luôn nhỏ hơn hoặc bằng khoảng cách thực tế, do đó mọi bất thường thực sự đều được giữ lại trong tập ứng viên (tỷ lệ bỏ sót là 0%).

3. Kỹ thuật "Từ bỏ sớm" (Early Abandoning) vận hành như thế nào?

Khi tính khoảng cách Euclid giữa hai chuỗi độ dài $n$, thuật toán cộng dồn bình phương hiệu số từng điểm. Nếu tại vị trí thứ $k$ ($k < n$) mà tổng tích lũy đã vượt quá khoảng cách của lân cận gần nhất hiện tại ($\text{dist}_j$), quá trình tính toán lập tức dừng lại mà không cần tính tiếp $n-k$ điểm còn lại.

4. Hạn chế hiện tại của đề tài là gì và hướng khắc phục?

Hạn chế của phương pháp là người dùng vẫn cần thiết lập một số tham số đầu vào như số đoạn PAA ($w$), kích thước từ vựng ($a$) và độ dài chuỗi dị biệt ($n$). Hướng phát triển tiếp theo là tích hợp Nguyên lý độ dài mô tả tối thiểu (MDL - Minimum Description Length) để tự động hóa hoàn toàn việc lựa chọn tham số mà không cần sự can thiệp của con người.

5. Thuật toán có thể mở rộng cho chuỗi thời gian đa chiều (Multidimensional Time Series) không?

Có. Về mặt nguyên lý, phương pháp PAA và SAX hoàn toàn có thể mở rộng cho dữ liệu đa biến bằng cách xây dựng biểu diễn tượng trưng trên từng chiều hoặc kết hợp với các mô hình chiếu không gian đa chiều.

---

8. Kết luận (Conclusion)

Công trình nghiên cứu mã số T2019-30TĐ do TS. Nguyễn Thành Sơn chủ nhiệm đã giải quyết thành công bài toán phát hiện bất thường trên chuỗi thời gian quy mô lớn. Bằng cách kết hợp sáng tạo giữa kỹ thuật xấp xỉ gộp từng đoạn (PAA), rời rạc hóa ký hiệu (SAX) và tối ưu hóa tính toán qua kỹ thuật từ bỏ sớm (Early Abandoning), đề tài đã mang lại một giải pháp vừa có tốc độ thực thi vượt trội vừa đảm bảo độ chính xác tuyệt đối.

Nghiên cứu không chỉ đóng góp một phương pháp luận giá trị cho cộng đồng khoa học dữ liệu mà còn mở ra nền tảng vững chắc để ứng dụng vào các hệ thống giám sát y tế, tài chính và công nghiệp 4.0. Trong tương lai, việc tích hợp nguyên lý MDL để phát triển phiên bản thuật toán phi tham số (Parameter-free Discord Discovery) sẽ là bước tiến quan trọng tiếp theo nhằm nâng cao tính tự động hóa và khả năng triển khai trên môi trường dữ liệu luồng thực tế.

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

CHƯƠNG 1. Các kiến thức cơ sở.1 Tổng quan về đề tài. Một chuỗi thời gian (time series) là một chuỗi các điểm dữ liệu được đo theo từng khoảng thời gian liền nhau theo một tần suất thời gian thống nhất.1 minh họa một ví dụ về chuỗi thời gian biểu diễn tỉ giá chuyển đổi trung bình hàng tháng giữa đô la Úc và đô la Mỹ (đơn vị đô la Úc) từ 7/1969 đến 8/1995.1 Đường biểu diễn một chuỗi thời gian. Các bài toán thường được nghiên cứu trong khai phá dữ liệu chuỗi thời gian gồm tìm kiếm tương tự (similarity search), gom cụm (clustering), phân lớp (classification), phát hiện motif (motif discovery), khai phá luật (rule discovery), phát hiện bất thường (anomaly detection), trực quan hóa (visualization), dự báo (forecast).

Những khó khăn và thách thức khi nghiên cứu về dữ liệu chuỗi thời gian [14]: - Dữ liệu thường rất lớn. Chẳng hạn, trong 1 giờ, dữ liệu điện tâm đồ (ECG) có thể lên đến 1GB. - Phụ thuộc nhiều vào yếu tố chủ quan của người dùng và tập dữ liệu khi đánh giá mức độ tương tự giữa các chuỗi thời gian. 10 Luan van - Dữ liệu không đồng nhất: định dạng của dữ liệu khác nhau, tần số lấy mẫu khác nhau.

Ngoài ra, dữ liệu có thể bị nhiễu, thiếu một vài giá trị hoặc không sạch. Bài toán tìm kiếm tương tự (so trùng) trong cơ sở dữ liệu chuỗi thời gian đã được nhiều nhà nghiên cứu quan tâm trong những năm qua vì đây là bài toán cơ bản và là một thành phần nền tảng của nhiều bài toán khác trong khai phá dữ liệu chuỗi thời gian. Đây là bài toán khó vì kích thước dữ liệu chuỗi thời gian thường lớn và vì chúng ta không thể lập chỉ mục dữ liệu chuỗi thời gian một cách dễ dàng như trong hệ thống cơ sở dữ liệu truyền thống. Một vài thí dụ về ứng dụng của tìm kiếm tương tự trên chuỗi thời gian có thể nêu ra như sau: - Tìm trong quá khứ, những giai đoạn mà số lượng sản phẩm bán được như tháng vừa rồi.

- Tìm những sản phẩm có chu kỳ doanh số giống nhau. - Tìm những đoạn nhạc trong một bài hát giống một đoạn nhạc đã có bản quyền. - Tìm những tháng trong quá khứ mà có lượng mưa giống như tháng vừa rồi. - Tìm những năm khô hạn mà mực nước các sông đều ở mức thấp.

Chuỗi con bất thường (unusual, abnormal, discord) là chuỗi con khác biệt nhất so với các chuỗi con khác trong một chuỗi thời gian.2 minh họa ví dụ về chuỗi con bất thường trong chuỗi thời gian về điện tậm đồ (ECG).2 Ví dụ về chuỗi con bất thường trong chuỗi thời gian ECG Phát hiện bất thường trên chuỗi thời gian đã và đang nhận được rất nhiều sự quan tâm trong cộng đồng nghiên cứu trong những năm qua. Nó đã và đang được sử dụng để giải nhiều bài toán trong các lĩnh vực ứng dụng khác nhau như các chẩn đoán lỗi, phát hiện các giao dịch lừa lọc, phát hiện sự xâm nhập mạng, các thay đổi trong thói quen của khách hàng, làm sạch dữ liệu, v. Nhiều thuật toán đã được giới thiệu để giải bài toán này như thuật toán Brute Force Discord Discovery (BFDD), thuật toán Heuristic Discord Discovery (HDD), thuật toán 11 Luan van Hot SAX, WAT, HotiSAX, WATiSAX, Disk Aware Discord Discovery, v. Trong các thuật toán đã được giới thiệu, nhiều thuật toán đi theo hướng tìm kiếm trong không gian gốc.

Hướng tiếp cận này có ưu điểm là không cần trải qua giai đoạn thu giảm số chiều nhưng có thể thời gian thực thi sẽ cao. Trong trường hợp xấu nhất độ phức tạp tính toán sẽ là hàm mũ theo kích thước của tập dữ liệu. Vì vậy, việc nghiên cứu đề xuất ra các thuật toán mới hoặc cải tiến các thuật toán đã có sao cho hiệu quả hơn vẫn luôn được các nhà nghiên cứu quan tâm thực hiện.2 Các kiến thức cơ bản. Trong phần này, chúng tôi giới thiệu tóm tắt cơ sở lý thuyết về các độ đo tương tự, các phương pháp thu giảm số chiều và cấu trúc chỉ mục được sử dụng trong đề tài.

Trong các bài toán về chuỗi thời gian, để so sánh 2 chuỗi người ta sử dụng các độ đo tương tự. Hai đối tượng được xem là giống nhau khi độ đo tương tự giữa chúng bằng 0, được xem là tương tự nếu độ đo tương tự giữa chúng nhỏ hơn một giá trị  được qui ước trước đó. Để có thể tính toán và so sánh, độ đo này được biểu diễn thành các số thực và phải thỏa các tính chất sau: - D(x,y) = 0 nếu và chỉ nếu x = y - D(x, y) = D(y, x) - D(x, y)  0 với mọi x, y - D(x, y) < D(x, z) + D(y, z) Dưới đây là các độ đo thường được sử dụng  Độ đo Minkowski. Ký hiệu là Sim(X,Y) (độ tương tự giữa hai chuỗi X và Y có chiều dài n) và được định nghĩa như sau: n Sim( X , Y )  P  xi  yi  , với xi  X, yi  Y, i = 1, …, n P (1.1) Trong đó, p = 2 (Euclid) là độ đo thường được sử dụng.1) Độ đo này có ưu điểm tính toán dễ dàng.

Tuy nhiên nó cũng có một số nhược điểm là do phương pháp này tính toán dựa trên các cặp giá trị tương ứng trong hai chuỗi nên 12 Luan van đối với các trường hợp tính chất của hai mẫu là giống nhau nhưng giá trị khác nhau (có đường căn bản khác nhau hay có biên độ dao động khác nhau) thì khoảng cách hai mẫu sẽ rất khác nhau.3 minh họa trường hợp này.3 Minh họa hai chuỗi thời gian giống nhau. Để khắc phục trường hợp này trước khi áp dụng các giải thuật ta cần thực hiện chuẩn hóa dữ liệu. Các phương pháp chuẩn hóa thường được dùng là: - Chuẩn hóa trung bình zero (Zero-Mean normalization) [16] Chuỗi Q được biến đổi thành chuỗi Q’ theo công thức Q’[i] = (Q[i]- mean(Q)) / var(Q) (1.2) Với mean(Q) là giá trị trung bình của Q và var(Q) là độ lệch chuẩn của Q.2) - Chuẩn hóa nhỏ nhất-lớn nhất (Min-Max normalization) [16] Chuỗi Q được biến đổi thành chuỗi Q’ theo công thức Q[i]  Minold (1.3) Q'[i]  ( Maxnew  Minnew )  Minnew Maxold  Minold (1.3) Với Minold và Maxold là giá trị nhỏ nhất và lớn nhất của chuỗi ban đầu. Minnew và Maxnew là giá trị nhỏ nhất và lớn nhất của chuỗi sau khi được chuẩn hóa.

 Độ đo xoắn thời gian động. Trong trường hợp hai mẫu cần so sánh có hai đường biểu diễn không hoàn toàn giống nhau nhưng hình dạng biến đổi rất giống nhau thì khi so sánh độ tương tự giữa hai mẫu bằng cách so sánh từng cặp điểm 1-1 (so điểm thứ i của đường thứ nhất và điểm thứ i của đường thứ hai) là không phù hợp.4 minh họa 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 13 Luan van muốn. Vì vậy để khắc phục nhược điểm này, 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.

Phương pháp này gọi là xoắn thời gian động (Dynamic Time Warping - DTW) [17].4 Khoảng cách giữa 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. Cách tính DTW Cách đơn giản nhất để tính DTW của hai đường X và Y là ta xây dựng ma trận Dm x n với m = |X| và n= |Y|. Sau khi xây dựng ma trận D , ta tìm đường đi từ ô (0,0) đến ô (m,n) thỏa mãn những ràng buộc sau: - Không được đi qua trái hay đi xuống - Đường đi phải liên tục - Ô (i,j) thuộc đường đi phải thỏa |i - j| <= w Giả sử có L ô đi từ ô (0, 0) đến ô (m, n) thỏa mãn những điều kiện trên, khi đó: DTW (Q, C )  min W  d ,W  w , w ,.4) trong đó dk = d(qi, cj) là khoảng cách được biểu diễn như wk = (i, j)k trên đường đi(1. Tuy nhiên, ta có thể dùng quy hoạch động để giải quyết bài toán này.

Trong đó, công thức truy hồi để tính D(i, j):  (i, j )  d (qi , c j )  min{ (i  1, j  1), (i  1, j ), (i.5) Độ đo tương tự DTW có ưu điểm là cho kết quả chính xác hơn so với độ đo Euclid và cho phép nhận dạng mẫu có hình dạng giống nhau nhưng chiều dài hình dạng về thời gian có thể khác nhau. Độ đo tương tự này có nhược điểm là thời gian chạy lâu, tuy nhiên gần đây đã có những công trình tăng tốc độ tìm kiếm tương tự dùng độ đo DTW, 14 Luan van tiêu biểu nhất là công trình của Keogh và các cộng sự, năm 2002 [18].5 minh họa cách tính khoảng cách theo DTW.5 Minh họa cách tính khoảng cách theo DTW.2 Thu giảm số chiều chuỗi thời gian. Thu giảm số chiều là phương pháp biểu diễn chuỗi thời gian n chiều X = {x1, x2, …, xn} thành chuỗi thời gian có N chiều Y = {y1, y2, …, yN} với N << n, nhưng vẫn phải giữ được các đặc trưng của chuỗi thời gian ban đầu. Với N càng lớn thì sự khôi phục càng chính xác.

Dữ liệu chuỗi thời gian thường rất lớn nên việc tìm kiếm trực tiếp trên dữ liệu chuỗi thời gian gốc sẽ không hiệu quả. Để khắc phục vấn đề này, cách tiếp cận chung thường được sử dụng bao gồm các bước sau: 1. Áp dụng một số phương pháp biến đổi xấp xỉ để thu giảm độ lớn của dữ liệu sao cho vẫn giữ được các đặc trưng của dữ liệu. Các phương pháp biến đổi xấp xỉ này thường được gọi là những phương pháp thu giảm số chiều (dimensionality reduction).

Thực hiện bài toán trên dữ liệu xấp xỉ, ta thu được tập kết quả xấp xỉ. Dựa trên tập kết quả xấp xỉ này, thực hiện truy cập đĩa để thực hiện hậu kiểm trên dữ liệu gốc nhằm loại bỏ các chuỗi tìm sai trong tập kết quả xấp xỉ.  Điều kiện chặn dưới. Do khi xấp xỉ dữ liệu sẽ gây ra mất mát thông tin, nên khi thực hiện trên dữ liệu xấp xỉ có thể xảy ra lỗi tìm sót (false dismissal) và/hoặc tìm sai (false alarm).

Để đảm bảo có kết quả chính xác, lỗi tìm sót không được phép xảy ra. Mặt khác, lỗi tìm sai cũng nên thấp để giảm chi phí trong quá trình hậu kiểm.