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.

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.