Phát hiện bất thường trên chuỗi thời gian dựa vào ma trận khoảng cách

Phát hiện bất thường trên chuỗi thời gian dựa vào ma trận khoảng cách Phát hiện bất thường trên chuỗi thời gian dựa vào ma trận khoảng cách Phát hiện bất thường trên chuỗi thời gian dựa vào ma trận khoảng cách Phát hiện bất thường trên chuỗi thời gian dựa vào ma trận khoảng cách

Đối tượng nghiên cứu

Dữ liệu chuỗi thời gian và các phương pháp phát hiện bất thường trên dữ liệu chuỗi thời gian.

Phạm vi nghiên cứu

Phát hiện bất thường trên dữ liệu chuỗi thời gian dựa vào ma trận khoảng cách

5 Cách tiếp cận và phương pháp nghiên cứu

Tổng hợp các kết quả nghiên cứu liên quan trước đây Đưa ra đánh giá thực nghiệm để kiểm tra kết quả

6 Ý nghĩa thực tiễn của đề tài

Hiện nay, nghiên cứu và phát hiện bất thường đang được áp dụng rộng rãi trong nhiều lĩnh vực như chăm sóc sức khỏe, năng lượng, chứng khoán, tài chính, sản xuất và bảo mật.

Nghiên cứu về phát hiện bất thường trong khai phá dữ liệu chuỗi thời gian đang thu hút sự chú ý của nhiều nhà nghiên cứu, vì đây là một bài toán quan trọng Nghiên cứu này sẽ tạo ra cơ sở cho các nghiên cứu tiếp theo trong lĩnh vực này.

Các kiến thức cơ bản

Chuỗi thời gian T = t 1 , t 2 , … t n là một tập theo thứ tự các biến giá trị thực chiều dài n [4]

Ví dụ về chuỗi thời gian là: lưu lượng mưa hàng năm ở miền nam Việt Nam, kết quả điện tâm đồ, thời tiết…

Hình 2.1: Minh họa về chuỗi thời gian biểu diễn kết quả điện tâm đồ - ECG [29]

Cho một chuỗi con T i,m của chuỗi thời gian T = (t 1 , t 2 …, t n ), là một tập hợp con liên tục các giá trị của T có độ dài m, bắt đầu từ vị trí i T i,m = (t i ,t i+1 ,…,t i+m-1 ) với 1≤ i ≤ n-m+1 [26]

Để xác định chuỗi con có chiều dài m từ dữ liệu chuỗi thời gian T với chiều dài n, ta sử dụng một cửa sổ trượt kích thước m Cửa sổ này sẽ trượt qua từng điểm từ trái sang phải trên chuỗi T để xác định mỗi chuỗi con Q.

Hình 2.2: Mô tả cửa sổ trượt trên chuỗi thời gian T [26]

Chọn một tập hợp các số thực R, được xác định bởi người dùng, và một dữ liệu chuỗi thời gian T, trong đó chứa một chuỗi con C bắt đầu tại vị trí p.

M bắt đầu tại vị trí q, nếu hàm tính khoảng cách từ C đến M ký hiệu D(C, M) ≤ R

(ta dùng công thức tính khoảng cách euclid để tính toán khoảng cách giữa 2 chuỗi con) thì ta nói là chuỗi con M khớp được với chuỗi con C [26]

Hình 2.3: Trùng khớp giữa hai chuỗi con C và M được trích từ chuỗi T [26]

Cho một số thực dương R và một chuỗi thời gian T Một chuỗi con C_i của T bắt đầu tại vị trí i và một chuỗi con C_j của T bắt đầu tại vị trí j, nếu khoảng cách DIST(C_i, C_j) thỏa mãn điều kiện nhất định, thì chúng ta có thể xác định mối liên hệ giữa các chuỗi con này.

≤ R thì Cj được gọi là chuỗi con tương tự của C i

Các chuỗi con tương tự nhất với một chuỗi con C i là các chuỗi con bắt đầu tại các

Có 5 vị trí lệch một hoặc hai điểm sang trái hoặc phải so với vị trí bắt đầu của chuỗi con C i Điều này có nghĩa là chuỗi con mới sẽ lệch một khoảng so với chuỗi con cũ, và cả hai chuỗi con này sẽ chia sẻ một đoạn giá trị chung Những trường hợp này được gọi là so trùng tầm thường.

Hình 2.4: So trùng tầm thường của 2 chuỗi con trong chuỗi thời gian T [26]

2.1.4.2 So trùng không tầm thường

Cho chuỗi thời gian T có độ dài n, với các chuỗi con C và M có độ dài m Chuỗi C bắt đầu tại vị trí p, trong khi chuỗi M bắt đầu tại vị trí q Hai chuỗi con C và M được coi là trùng không tầm thường nếu khoảng cách giữa chúng, được tính bằng |p-q|, lớn hơn hoặc bằng m.

2.1.5 Các độ đo tương tự Đối với bài toán phát hiện bất thường trên dữ liệu chuỗi thời gian, bài toán tìm kiếm tương tự, gom cụm, phân loại trên dữ liệu thời gian thì dữ liệu chuỗi thời gian là dãy các số thực T=t1, t2,…tn Đối với những bài toán này đòi hỏi chúng ta phải định nghĩa một độ đo tương tự giữa các cặp chuỗi thời gian với nhau

Cho 2 chuỗi thời gian Q và C bất kỳ Ta cần tính độ đo tương tự Dist(Q,C) của hai chuỗi thời gian này Để tính toán chính xác thì các độ đo cần thỏa một số tính chất cơ bản sau:

- Dist(Q,C) = 0 nếu và chỉ nếu Q = C

Hầu hết các nghiên cứu về dữ liệu chuỗi thời gian sử dụng độ đo Minkowski để tính toán khoảng cách hoặc mức độ tương tự giữa hai chuỗi con Công thức tính khoảng cách Minkowski được định nghĩa rõ ràng và là công cụ quan trọng trong phân tích chuỗi thời gian.

Khi p = 1 ta có khoảng cách Manhattan

Khi p = 2 ta có khoảng cách Euclid

Khi p = ∞, khoảng cách Max được xác định Trong các nghiên cứu chuỗi dữ liệu thời gian, giá trị p thường được chọn là độ đo Euclid do tính đơn giản và dễ thực hiện của nó Độ đo này cũng là khoảng cách hình học trong không gian đa chiều với độ chính xác chấp nhận được.

+ Tính toán nhanh, đơn giản

Độ đo Minkowski là công cụ hữu ích trong khai phá dữ liệu chuỗi thời gian, hỗ trợ các bài toán như gom cụm, phân lớp và phát hiện bất thường Nhờ thỏa mãn bất đẳng thức tam giác, nó giúp lập chỉ mục dữ liệu hiệu quả, từ đó giảm thiểu thời gian phát hiện bất thường trên dữ liệu chuỗi thời gian.

+ Các chuỗi thời gian có độ dài như nhau

+ Đối với dữ liệu có đường căn bản khác nhau thì thuật toán này chưa xử lý tốt (Hình 2.5 a)

+ Không thích hợp khi dữ liệu có biên độ dao động khác nhau (Hình 2.5 b)

Đường cơ bản và biên độ giao động có sự khác biệt đáng kể Để khắc phục nhược điểm của phương pháp đo lường này, việc áp dụng chuẩn hóa dữ liệu (Data normalization) là cần thiết Hiện nay, có hai phương pháp chuẩn hóa dữ liệu phổ biến được sử dụng.

 Chuẩn hóa trung bình Zero [26]:

- Chuỗi Q được biến đổi thành chuỗi Q’ theo công thức

Với mean(Q) là giá trị trung bình và var(Q) là độ lệch chuẩn của Q

Khi không xác định được giá trị lớn nhất và nhỏ nhất trong tập dữ liệu hoặc khi xuất hiện các giá trị cá biệt, phương pháp này có thể được sử dụng để phân tích.

Chuỗi Q được biến đổi thành chuỗi Q’ theo công thức

𝑀𝑎𝑥 𝑜𝑙𝑑 −𝑀𝑖𝑛 𝑜𝑙𝑑 (𝑀𝑎𝑥 𝑛𝑒𝑤 − 𝑀𝑖𝑛 𝑛𝑒𝑤 ) + 𝑀𝑖𝑛 𝑛𝑒𝑤 (2.3) Với Min old và Max old là giá trị nhỏ nhất và lớn nhất của chuỗi Q ban đầu

Min new và Max new là giá trị nhỏ nhất và lớn nhất của chuỗi Q’ là chuỗi sau khi được chuẩn hóa

Chuẩn hóa Min-Max giữ nguyên mối quan hệ giữa các giá trị trong dữ liệu gốc, tuy nhiên, phương pháp này có thể gặp vấn đề khi giá trị mới nằm ngoài khoảng [Min – Max] ban đầu, dẫn đến lỗi ngoài giới hạn.

2.1.5.2 Độ đo xoắn thời gian động

Khi hai đường biểu diễn cần so sánh hoàn toàn khác nhau nhưng lại có hình dạng biến đổi tương tự, việc áp dụng các khoảng cách so sánh là rất cần thiết.

Hình 2.5: Minh họa hai chuỗi thời gian tương đồng

Đo độ tương tự giữa hai mẫu bằng cách sử dụng từng cặp điểm 1-1 không hiệu quả Theo độ đo Euclid, một điểm trên chuỗi thời gian này chỉ ánh xạ với một điểm tương ứng trên chuỗi thời gian khác, và các chuỗi cần so sánh phải có cùng độ dài Để khắc phục nhược điểm này, một điểm có thể ánh xạ với nhiều điểm khác nhau mà không cần phải thẳng hàng Phương pháp này được gọi là xoắn thời gian động (Dynamic Time Warping – DTW), được đề xuất bởi Bernt và Clifford vào năm 1994.

Hình 2.6: Minh họa về độ đo xoắn thời gian động Dynamic Time Warping và độ đo Euclidean [12]

D m x n với m = |X| và n= |Y| Khi đó, D ij = d(x i , y j )

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| min(Dist(C, MC)

Hình 2.12: Chuỗi con bất thường [6]

Phát hiện bất thường, hay còn gọi là phân tích ngoại lệ, là quy trình trong khai thác dữ liệu nhằm xác định các điểm dữ liệu và sự kiện không tuân theo hành vi thông thường của bộ dữ liệu Dữ liệu bất thường có thể báo hiệu các sự cố nghiêm trọng như trục trặc kỹ thuật hoặc mở ra cơ hội mới, chẳng hạn như thay đổi trong hành vi tiêu dùng Hiện nay, máy học đang ngày càng được áp dụng để tự động hóa quá trình phát hiện sự bất thường.

2.2.2 Giải thuật phát hiện bất thường theo Vét cạn

Giải thuật Brute-Force là một phương pháp đơn giản để phát hiện chuỗi con bất thường Nó hoạt động bằng cách sử dụng hai vòng lặp lồng nhau: vòng lặp ngoài duyệt qua từng chuỗi con trong tập (|T|- n + 1) và vòng lặp trong kiểm tra các chuỗi con để tìm các chuỗi trùng khớp không tầm thường (non-self match) với chuỗi con dự tuyển.

Sau khi thực hiện hai vòng lặp lồng nhau, thuật toán sẽ xác định chuỗi con bất thường Thuật toán Brute-Force kiểm tra tất cả chuỗi con và có khả năng trả về chính xác chuỗi con bất thường chỉ với một tham số đầu vào là chiều dài của chuỗi Tuy nhiên, do thuật toán này duyệt qua tất cả chuỗi con với độ phức tạp tính toán là O(m²), trong đó m là chiều dài của chuỗi thời gian |T| = m, nên nó không khả thi cho các tập dữ liệu lớn.

1 Function [dist, loc ]= Brute_Force(T, n)

3 best_so_far_loc = NaN

8 IF Dist(t p , ,t p+n-1 ,t q , ,t q+n-1 ) < nearest_neighbor_dist

13 IF nearest_neighbor_dist > best_so_far_dist

14 best_so_far_dist = nearest_neighbor_dist

18 Return[ best_so_far_dist, best_so_far_loc ]

Bảng 2.1: Giải thuật Brute-Force tìm kiếm chuỗi con bất thường

Trong đoạn từ 4 đến 17, hai vòng lặp lồng nhau được sử dụng để xử lý các chuỗi con trong tập dữ liệu Vòng lặp ngoài duyệt qua từng chuỗi con dự tuyển trong số (|T|- n + 1) chuỗi con, trong khi vòng lặp trong kiểm tra từng chuỗi con trong cùng tập để xác định các chuỗi con trùng khớp không tầm thường (non-self match) với chuỗi con dự tuyển Sau khi hoàn thành quá trình này, thuật toán sẽ trả về các chuỗi con bất thường.

2.2.3 Tổng quan về một số phương pháp phát hiện bất thường tiêu biểu

Dữ liệu chuỗi thời gian được ứng dụng rộng rãi trong nhiều lĩnh vực như khoa học kỹ thuật, kinh tế, y tế và tài chính Việc phát hiện các chuỗi con bất thường trong cơ sở dữ liệu chuỗi thời gian là rất quan trọng Kể từ thập niên 1980, nhiều phương pháp đã được các nhóm nghiên cứu đề xuất nhằm phát hiện các chuỗi bất thường trong dữ liệu này.

Trong thời gian gần đây, nhiều công trình nghiên cứu đã đề xuất các thuật toán mới nhằm phát hiện bất thường trên chuỗi thời gian Dưới đây là một số công trình tiêu biểu trong lĩnh vực này.

Phương pháp phát hiện bất thường dựa trên phân tích chuỗi thời gian sử dụng mô hình ARMA được đề xuất bởi Jingxiang Qi và các cộng sự Phương pháp này áp dụng một quy trình lặp để phát hiện các bất thường, với mỗi lần lặp thuật toán nhằm cải thiện độ chính xác của kết quả.

17 sẽ phải phát hiện bất thường đầu tiên một cách tự động bằng cách chọn những tham số mô hình ARMA tốt nhất

Một phương pháp phát hiện bất thường mới được đề xuất bởi Md Rakibul Alam và cộng sự, nhằm phát hiện bất thường trong dữ liệu chuỗi thời gian đơn biến về giao thông Dữ liệu này được thu thập từ các bộ cảm biến, sau đó tính toán giá trị trung vị (median) theo từng tuần Các dữ liệu trung vị sẽ được phân cụm bằng thuật toán K-Means, với độ đo Dynamic Time Warping Cuối cùng, dựa trên kết quả phân cụm và kiến thức chuyên gia, phương pháp này xác định các bất thường trong dữ liệu.

Tác giả Max Landauer và cộng sự đã phát triển một phương pháp phát hiện bất thường động cho dữ liệu log thông qua việc tạo ra nhiều bản đồ cụm và kết nối chúng bằng kỹ thuật gom cụm cải tiến Phương pháp này cho phép phân tích chuỗi thời gian thu thập để phát hiện hành vi bất thường của hệ thống, nhờ vào việc theo dõi từ những cụm cải tiến đó.

Để nâng cao chất lượng dịch vụ trực tuyến của sản phẩm tại Microsoft, việc giám sát rủi ro tiềm ẩn từ các bất thường là rất quan trọng Do đó, tác giả Hansheng Ren và các cộng sự đã đề xuất phương pháp phát hiện bất thường trực tuyến không giám sát trong dữ liệu chuỗi thời gian đơn biến, sử dụng giải thuật SR (Spectral Residual) kết hợp với Mạng thần kinh chuyển đổi (CNN - Convolutional Neural Network).

Tác giả Moa Samuelsson đã phát triển một ứng dụng giám sát dữ liệu chuỗi thời gian tại Eurocon MOPSsys AB, chuyên về ngành công nghiệp giấy và bột giấy Ứng dụng này sử dụng giải thuật khớp mô hình thống kê cùng với tập huấn luyện về giới hạn kiểm soát kích thước do máy tính điều khiển trong không gian không giám sát Nhờ đó, hệ thống có khả năng phát hiện bất thường khi có một tính năng vượt quá giới hạn từ dữ liệu được cập nhật liên tục và trích xuất từ công ty MOPSsys.

Tác giả Feng Ye và cộng sự đã tiến hành khai thác dữ liệu và tính toán chuỗi thời gian trong lĩnh vực thủy văn nhằm phát hiện hiệu quả.

Nghiên cứu này trình bày phương pháp phát hiện bất thường trong chuỗi thời gian dữ liệu cảm biến thủy văn lớn, sử dụng thuật toán Flink kết hợp với cửa sổ trượt và mô hình ARIMA để dự đoán luồng dữ liệu Kết quả dự đoán được tính khoảng tin cậy, và những giá trị nằm ngoài khoảng này được xác định là dữ liệu bất thường Cuối cùng, thuật toán K-Means++ được áp dụng để phân cụm dữ liệu Dữ liệu thực nghiệm được thu thập từ cảm biến thủy văn tại sông Chu, Trung Quốc.

Tác giả Cynthia Freeman và cộng sự đã phát triển một khung thông minh cho các phương pháp phát hiện bất thường tối ưu dựa trên các đặc điểm của chuỗi thời gian Để đảm bảo tính chính xác trong việc phát hiện bất thường, họ đã cung cấp một xác nhận thử nghiệm toàn diện cho nhiều phương pháp khác nhau, nhằm hình thành các hướng dẫn hiệu quả trong việc phát hiện bất thường trên chuỗi thời gian.

Thực hiện trong không gian thu giảm

3.1.1 Ý tưởng tổng quát Ý tưởng bài toán phát hiện bất thường trong không gian thu giảm được xuất phát từ giải thuật SWAMP của Sara Alaee và cộng sự [23] (2020) đưa ra là phát hiện chuỗi bất thường từ dữ liệu chuỗi thời gian một chiều dựa trên phương pháp chính xác có thể mở rộng đầu tiên để khám phá các bất thường chuỗi thời gian theo Độ xoắn thời gian động (DTW) Phương pháp của tác giả tự động thực hiện sự cân bằng tốt nhất giữa thời gian tính toán và độ chặt của chặn dưới (tightness- of-lower-bounds) Việc giảm số lần tính toán khoảng cách DTW thực tế là một chiến lược hiệu quả của việc tăng tốc trong các bài toán tìm kiếm tương tự dựa trên DTW Một trong những cách tiếp cận phổ biến nhất là cắt tỉa những chuỗi con dựa vào ràng buộc chặn dưới Ở đây "chặn dưới" có nghĩa là chặn dưới của khoảng cách DTW của chuỗi con và chuỗi truy vấn Trong quá trình tìm kiếm tương tự, nếu chặn dưới của một chuỗi con vượt quá ngưỡng đã cho, khoảng cách DTW của chuỗi con với chuỗi truy vấn đó sẽ lớn hơn ngưỡng đã cho Độ phức tạp tính toán của chặn dưới thường thấp hơn nhiều so với khoảng cách DTW, vì vậy kỹ thuật này được sử dụng để loại bỏ gần 99.99% việc tính các khoảng cách DTW của các chuỗi con không cần thiết [23], trước khi tính toán các khoảng cách DTW thực tế cần thiết của những chuỗi con còn lại

3.1.2 Một số định nghĩa Định nghĩa 1: LB_Keogh chặn dưới giữa hai chuỗi thời gian C, Q, cho độ rộng cửa sổ xoắn w, được xác định như là khoảng cách từ cửa sổ gần nhất của chặn trên đến bao đóng của chặn dưới quanh Q đến T theo công thức (3.1)[23]

Nơi mà bao đóng trên (Ui) và bao đóng dưới (Li) của chuỗi Q được đinh nghĩa như:

Ui = max(qi-w, qi-w+1, …, qi+w)

Li = min(qi-w, qi-w+1, …, qi+w)

Để giảm thời gian tính toán cận dưới cho chuỗi thời gian, tác giả áp dụng phương pháp PAA (Piecewise Aggregate Approximation) để lấy mẫu xuống Cụ thể, PAA của chuỗi thời gian T có chiều dài n được tính bằng cách chia chuỗi thành k cửa sổ bằng nhau và tính giá trị trung bình của dữ liệu trong mỗi cửa sổ Các giá trị này tạo thành một vec-tơ đại diện cho chuỗi thời gian.

Hình 3.1: Minh họa chuỗi thời gian Q được lấy mẫu xuống theo PAA theo 2 tỉ lệ nén khác nhau Hình trái: 4:1, hình phải: 16:1 [23]

Để lấy mẫu xuống chuỗi thời gian, chúng ta có thể tổng quát LBKeogh theo cách sau: LBKeoghD:1 (D>=1) Định nghĩa 3: Lấy mẫu chặn dưới LBKeoghD:1(Q,T) giữa chuỗi thời gian Q và chuỗi thời gian khác T được xác định là khoảng cách từ cửa sổ gần nhất của lấy mẫu bao đóng trên và dưới quanh Q, đến lấy mẫu T theo công thức [23].

Ta có: 𝑇 _ 𝐷 = PAA (T, D), 𝑈 _ 𝐷 = PAA (U 𝑄 , D), và 𝐿 _ 𝐷 = PAA (L 𝑄 , D)

Hình 3.3: Minh họa tham số hóa LBKeogh

Thuật toán SWAMP được thực hiện trong 2 pha [23]:

Quy trình ComputeDSMP(T,C,w) nhận đầu vào là chuỗi thời gian T, chuỗi con có chiều dài C và cửa sổ xoắn kích thước w Kết quả đầu ra bao gồm LBKeoghD:1 được mở rộng với giá trị LBMP, LBKeoghD:1 được mở rộng kèm theo chỉ số LB_index, vị trí chuỗi thời gian bị loại bỏ và khoảng cách tốt nhất hiện tại của ứng viên.

1 ED_mp ← ComputeMatrixProfile(T,C) // Using SCRIMP [26]

2 ED_motif_idx ← argmin(ED_mp)

3 best-so-far ← dtw_distance(ED_motif_idx)

6 while D>0: // iterate over increasing fine approximations

7 [LBMP,LB_index] ← LBKeoghDSMP(T,C,D,pruned) // bảng 3.2

8 LB_motif_dist, LB_motif_idx ← min(LBMP)

9 if LB_motif_dist < best-so-far:

10 best-so-far ← LB_motif_dist

11 pruned(LBMP > best-so-far) ← true

13 D ← floor(D/2) // next iteration will be twice as fine

Tác giả tính toán Matrix profile cổ điển cho chuỗi thời gian T với độ dài dãy con C, nhằm cung cấp chặn trên cho khoảng cách giữa các vị trí DTW Sử dụng Matrix profile này, chúng tôi xác định vị trí bất thường dựa trên khoảng cách ED, tức là giá trị cao nhất.

23 cách giữa những vị trí đó sử dụng khoảng cách DTW thay vì khoảng cách ED, để khởi tạo khoảng cách xa nhất (dòng 2-3)

Bắt đầu với hệ số lấy mẫu giảm xuống theo độ dài của dãy con, chúng ta nhanh chóng tính toán chặn dưới cho toàn bộ chuỗi thời gian bằng thuật toán trong Bảng 3.2 Đối với những khu vực có mức độ loại bỏ yếu, tác giả sẽ tính toán ràng buộc chặt chẽ hơn và lặp lại quy trình tương tự.

Khi tính toán chặn dưới ở bất kỳ mức độ nào, tác giả sẽ loại bỏ các vị trí ở các cấp thấp hơn, tức là không xem xét chặn dưới cho những vùng này Quá trình tính toán chặn dưới được trình bày chi tiết trong Bảng 3.2.

Quy trình LBKeoghDSMP(T,C,D,pruned) nhận vào chuỗi thời gian T, chuỗi con có chiều dài C, số lượng mẫu D và vị trí của các phần tử bị loại bỏ trong chuỗi thời gian đã được tinh chỉnh (pruned) Kết quả đầu ra bao gồm LBKeoghD:1 với giá trị LBMP và LBKeoghD:1 với chỉ số LB_index được mở rộng.

3 MP_D, LB_index ← LBKeogh(T_D, C_D, pruned_D)

4 LBMP ← interpolate(MP_D, floor(length(T) / length(T_D)))

5 LBMP ← sqrt(length(T) / length(T_D)) × LBMP

Bảng 3.2 trình bày phương pháp LBKeoghDSMP, trong đó dòng 1 thực hiện việc lấy mẫu bằng cách giảm PAA cho chuỗi thời gian T Đồng thời, vecto kiểu Boolean D được sử dụng để xác định các vị trí đã được lược bỏ và không lược bỏ trong quá trình này.

Dòng 2 giảm độ dài chuỗi con C tương đối theo tỷ lệ thu giảm (là kết quả của phép chia lấy phần nguyên giữa độ dài chuỗi đã thu giảm T_D và độ dài chuỗi T)

Dòng 3 đến 6 tính lại chặn dưới LBKeoghD:1

Procedure SWAMP(T,C,w) Đầu vào: chuỗi thời gian T, chiều dài chuỗi con C, kích thước cửa sổ xoắn w Đầu ra: vị trí bất thường

1 [LBMP, pruned, best-so-far, LB_index] ← ComputeDSMP(T,C,w) //Bảng 3.1

2 candids,candids_index] ← sorted(LBMP) // bắt đầu pha 2

8 neigh_idx ← candid_idx + C: length(candids)

9 swap(neigh_idx[1], neigh_idx[LB_index[candid_idx]])

16 if LBKimFL(a,b) >= best-so-far

18 elseif LBKeogh(a,b) >= best-so-far

21 dist ← dtw_distance(a, b, w, best-so-far)

22 if dist < best-so-far

24 motif_pair ← [candid_idx, neigh_idx]

25 pruned(candid_idx(candids >= best-so-far)) ← true

Tác giả đã tối ưu hóa quy trình bằng cách thực hiện 04 bước để loại bỏ các chuỗi không cần thiết trong việc tính toán khoảng cách DTW, được trình bày tại các dòng 5, 11, 16 và 18.

Dòng 16 và dòng 18 tác giả sử dựng chặn dưới LBKeogh và LBKim nhằm giảm chi phí cho việc tính khoảng cách DTW một số chuỗi con loại bỏ Tác giả gọi đây là từ bỏ sớm phiên bản LBKeogh [23]

Nếu các nỗ lực lược bỏ trước đó không thành công, tác giả sẽ phải tính toán khoảng cách DTW và áp dụng phương pháp từ bỏ sớm phiên bản DTW, đồng thời cập nhật lại khoảng cách tối ưu nhất (best-so-far).

Môi trường sử dụng cho thực nghiệm

- Thực nghiệm được thực hiện đánh giá trên máy tính Dell Latitude, Intel® Core™ i7-56000U 2.60GHz, RAM 16GB, hệ điều hành Windows 10Pro

- Sử dụng trên Python 3.6, Thư viện Pyqt5 và Matlab 2018A, thư viện Matlab Engine API for Python.

Tập dữ liệu sử dụng cho thực nghiệm

Luận văn này thực hiện thí nghiệm với 15 tập dữ liệu chuẩn, bao gồm 10 tập dữ liệu mẫu có vị trí chuỗi con bất thường đã biết và các tập dữ liệu thực tế chưa xác định vị trí chuỗi con bất thường Các tập dữ liệu được thu thập từ nhiều lĩnh vực khác nhau như y khoa, khoa học vũ trụ và dữ liệu doanh nghiệp, với độ dài đa dạng.

Bài viết này bao gồm các tập kết quả điện tim, tàu con thoi và nhu cầu tiêu thụ điện tại Hà Lan, được tải về từ trang của nhóm GS Eammon Koegh.

STT Tên tập dữ liệu Độ dài Giải thích

1 Chfdb_chf01_275 3,751 ECG: các tập dữ liệu từ kết quả siêu âm tim

6 TEK16 5,000 Space Shuttle: Tàu con thoi

Nhu cầu tiêu thụ điện tại Hà Lan đã được thu thập với tổng công suất 35,040 MW Mục tiêu là kiểm tra sự bất thường trong biến động nhu cầu điện, bao gồm các trường hợp tăng hoặc giảm đột ngột.

Bảng 4.1: Danh sách các tập dữ liệu mẫu sử dụng cho thực nghiệm

Tập dữ liệu về sóng địa chấn trong lĩnh vực khoa học, cùng với các dữ liệu về lượt đề cập trên Twitter của các tập đoàn lớn Mỹ như Google, UPS, Amazon, Apple, và IBM, tạo nên nguồn thông tin phong phú Ngoài ra, các bộ cảm biến nhiệt độ của máy móc và văn phòng khi gặp lỗi, cũng như các dữ liệu thu thập về lỗi CPU của máy chủ tại trung tâm dữ liệu của Amazon (bờ Đông) đóng góp vào việc phân tích và cải thiện hiệu suất hệ thống.

STT Tên tập dữ liệu Độ dài Giải thích

9 Seismology 40,000 Tập dữ liệu về sóng địa chấn

10 Twitter_GOOGE 15,842 Số lượt truy cập các tập đoàn hàng đầu của Mỹ trên Twitter

15 New-York Taxi 10,320 Dữ liệu về hoạt động của

Bảng 4.2: Danh sách các tập dữ liệu thực sử dụng cho thực nghiệm

Tiêu chí đánh giá

Các thuật toán phát hiện bất thường nghiên cứu trong đề tài được đánh giá qua hai tiêu chí: thời gian thực thi và độ chính xác

Trong phương pháp này, chúng tôi sử dụng các tập dữ liệu mẫu thực nghiệm thông qua ba giải thuật: không gian gốc, không gian thu giảm và Brute-force Kết quả thực nghiệm được kiểm tra và so sánh với các kết quả từ các tập dữ liệu mẫu đã được sử dụng trong các bài báo đã công bố Điều này cho phép chúng tôi sử dụng các kết quả này để so sánh với các giải thuật trong luận văn, nhằm đảm bảo độ chính xác cao trong nghiên cứu.

• Đối với tập dữ liệu mẫu: kết quả phát hiện bất thường của thuật toán được so sánh với vị trí bất thường đã biết trong chuỗi mẫu

Đối với tập dữ liệu thực, độ chính xác của thuật toán phát hiện bất thường được đề xuất phụ thuộc vào phân tích của con người về các bất thường do thuật toán phát hiện Nếu các vị trí bất thường được xác định bởi thuật toán này tương tự với các vị trí do thuật toán Brute-Force phát hiện trên hầu hết các tập dữ liệu thực nghiệm, chúng ta có thể kết luận rằng độ chính xác của thuật toán phát hiện bất thường đề xuất là tương đương với thuật toán cơ sở.

Các trường hợp thực nghiệm

Các trường hợp thực nghiệm trong luận văn bao gồm:

Giữ nguyên độ dài các tập dữ liệu, tiến hành thay đổi độ dài chuỗi con với các kích thước 64, 128, 256, 512, 1024, hoặc 700 cho các tập có độ dài dưới 4,000.

- Cố định độ dài chuỗi con là: 128, 256 và 512 thực nghiệm với độ lớn tập dữ liệu thay đổi là: 2.000, 4.000, 8.000, 12.000, 15.000

ĐÁNH GIÁ BẰNG THỰC NGHIỆM

Theo lý thuyết đã trình bày trong chương ba, chương này sẽ tiến hành thực nghiệm và đánh giá kết quả các giải thuật:

- Giải thuật phát hiện bất thường trong không gian gốc

- Giải thuật phát hiện bất thường trong không gian thu giảm

- Giải thuật phát hiện bất thường BRUTE-FORCE

4.1 Môi trường sử dụng cho thực nghiệm

- Thực nghiệm được thực hiện đánh giá trên máy tính Dell Latitude, Intel® Core™ i7-56000U 2.60GHz, RAM 16GB, hệ điều hành Windows 10Pro

- Sử dụng trên Python 3.6, Thư viện Pyqt5 và Matlab 2018A, thư viện Matlab Engine API for Python

4.2 Tập dữ liệu sử dụng cho thực nghiệm

Luận văn này thực hiện thí nghiệm với 15 tập dữ liệu chuẩn, bao gồm 10 tập dữ liệu mẫu đã biết vị trí chuỗi con bất thường và các tập dữ liệu thực chưa xác định vị trí chuỗi con bất thường Các tập dữ liệu được thu thập từ nhiều lĩnh vực khác nhau như y khoa, khoa học vũ trụ và dữ liệu doanh nghiệp, với chiều dài đa dạng.

Bài viết này bao gồm các tập dữ liệu về kết quả điện tim, tàu con thoi và nhu cầu tiêu thụ điện tại Hà Lan, được tải về từ trang của nhóm GS Eammon Koegh.

STT Tên tập dữ liệu Độ dài Giải thích

1 Chfdb_chf01_275 3,751 ECG: các tập dữ liệu từ kết quả siêu âm tim

6 TEK16 5,000 Space Shuttle: Tàu con thoi

Nhu cầu tiêu thụ điện tại Hà Lan đã được ghi nhận với con số 35,040 MW Dữ liệu này được thu thập nhằm kiểm tra sự bất thường trong biến động nhu cầu điện, bao gồm cả những tăng giảm đột ngột.

Bảng 4.1: Danh sách các tập dữ liệu mẫu sử dụng cho thực nghiệm

Bài viết này tập trung vào các tập dữ liệu quan trọng trong lĩnh vực khoa học địa chấn, bao gồm dữ liệu về sóng địa chấn và lượt đề cập trên Twitter của các tập đoàn lớn tại Mỹ như Google, UPS, Amazon, Apple và IBM Ngoài ra, nó cũng đề cập đến các tập dữ liệu liên quan đến cảm biến nhiệt độ của máy móc và văn phòng khi gặp sự cố, cũng như thông tin về lỗi CPU của máy chủ tại trung tâm dữ liệu của Amazon ở Bờ Đông.

STT Tên tập dữ liệu Độ dài Giải thích

9 Seismology 40,000 Tập dữ liệu về sóng địa chấn

10 Twitter_GOOGE 15,842 Số lượt truy cập các tập đoàn hàng đầu của Mỹ trên Twitter

15 New-York Taxi 10,320 Dữ liệu về hoạt động của

Bảng 4.2: Danh sách các tập dữ liệu thực sử dụng cho thực nghiệm

Các thuật toán phát hiện bất thường nghiên cứu trong đề tài được đánh giá qua hai tiêu chí: thời gian thực thi và độ chính xác

Phương pháp này áp dụng các tập dữ liệu mẫu thực nghiệm thông qua ba giải thuật: không gian gốc, không gian thu giảm và Brute-force Kết quả thực nghiệm sẽ được kiểm tra và so sánh với các kết quả từ các tập dữ liệu mẫu đã sử dụng, làm cơ sở cho những phát hiện trong một số bài báo đã công bố Do đó, các kết quả này có thể được sử dụng để so sánh với các giải thuật trong luận văn, đảm bảo tính chính xác và độ tin cậy của nghiên cứu.

• Đối với tập dữ liệu mẫu: kết quả phát hiện bất thường của thuật toán được so sánh với vị trí bất thường đã biết trong chuỗi mẫu

Đối với tập dữ liệu thực, độ chính xác của thuật toán phát hiện bất thường được đề xuất phụ thuộc vào phân tích của con người về các bất thường mà thuật toán phát hiện Nếu các vị trí bất thường do thuật toán đề xuất trong luận văn này xác định tương tự như các vị trí bất thường mà thuật toán phát hiện cơ sở, cụ thể là thuật toán Brute-Force, thì chúng ta có thể kết luận rằng độ chính xác của thuật toán phát hiện bất thường mới tương đương với thuật toán cơ sở.

4.4 Các trường hợp thực nghiệm:

Các trường hợp thực nghiệm trong luận văn bao gồm:

Giữ nguyên độ dài các tập dữ liệu, chúng ta sẽ thay đổi độ dài chuỗi con với các kích thước lần lượt là 64, 128, 256, 512, và 1024, hoặc 700 đối với các tập dữ liệu có độ dài dưới 4,000.

- Cố định độ dài chuỗi con là: 128, 256 và 512 thực nghiệm với độ lớn tập dữ liệu thay đổi là: 2.000, 4.000, 8.000, 12.000, 15.000

4.5.1 Thực nghiệm với trường hợp chuỗi con thay đổi:

4.5.1.1 Tập dữ liệu Power Demand:

Hình 4.1: Kết quả thục nghiệm trên tập dữ liệu Power demand cho các chuỗi con: 64, 128, 256, 512 và 1024

Kết quả thực nghiệm trên tập dữ liệu Power Demand với chuỗi thời gian dài 35,040 cho thấy rằng thời gian thực thi của thuật toán đạt hiệu quả tốt nhất trong không gian thu giảm với các chuỗi con có độ dài lần lượt là 64, 128, 256, 512 và 1024.

Thời gian thực thi của thuật toán trong không gian thu gọn luôn mang lại kết quả tốt hơn gấp đôi so với thuật toán trong không gian gốc, như được thể hiện trong Hình 4.1 và Bảng 4.3.

Kết quả sau khi chạy thực nghiệm cho thấy độ chính xác của các giải thuật khá tốt, hoàn toàn trùng khớp với giải thuật cơ sở Brute-Force

37 4.5.1.2 Tập dữ liệu New York City Taxi:

Hình 4.2: Kết quả thực nghiệm trên tập dữ liệu New York Taxi với chiều dài chuỗi con: 64, 128, 256, 512, 1024

Kết quả thực nghiệm trên tập dữ liệu NY Taxi cho thấy với độ dài chuỗi thời gian 10,320 và các chuỗi con có độ dài 64, 128, 256, 512, 1024, thời gian thực thi của thuật toán đạt hiệu quả tốt nhất trong không gian thu giảm.

Thời gian thực thi của thuật toán trong không gian thu giảm mang lại hiệu quả tốt hơn gần 100 lần so với thuật toán trong không gian gốc, như được minh họa trong Hình 4.43 và Bảng 4.21.

Kết quả sau khi chạy thực nghiệm cho thấy độ chính xác của các giải thuật khá tốt, hoàn toàn trùng khớp với giải thuật cơ sở Brute-Force

Vị trí bất thường từ kết quả của các giải thuật và so với kết quả từ tập mẫu không gian gốc Không gian thu giảm Tập mẫu

Vị trí bất thường từ kết quả của các giải thuật so với giải thuật cơ sở BruteForce không gian gốc Không gian thu giảm Brute-Force

Bảng 4.3: Bảng thống kê vị trí từ kết quả của các tập dữ liệu trong thực nghiệm

Thời gian thực thi từ kết quả của các giải thuật so với giải thuật cơ sở BruteForce không gian gốc Không gian thu giảm Brute-Force

Bảng 4.4: Bảng thống kê thời gian thực thi của các tập dữ liệu trong thực nghiệm khi thay đổi độ dài chuỗi con

42 4.5.2 Thực nghiệm với trường hợp độ lớn chuỗi thay đổi:

Hình 4.3: Kết quả thực nghiệm với trường hợp độ lớn chuỗi thay đổi 2000, 4000,

8000, 15000 khi chuỗi con không thay đổi chiều dài: 128

Hình 4.4: Kết quả thực nghiệm với trường hợp độ lớn chuỗi thay đổi 2000, 4000,

8000, 15000 khi chuỗi con không thay đổi chiều dài: 256

Hình 4.5: Kết quả thực nghiệm với trường hợp độ lớn chuỗi thay đổi 2000, 4000,

8000, 15000 khi chuỗi con không thay đổi chiều dài: 512

03 Vị trí bất thường từ kết quả của các giải thuật khi thay đổi độ dài chuỗi thời gian không gian gốc Không gian thu giảm BruteForce

Bảng 4.5: Bảng thống kê các vị trị bất thường từ các tập dữ liệu trong thực nghiệm khi thay đổi độ dài chuỗi thời gian

Thời gian thực thi với chuỗi con 128

Power Demand Twitte_UPS Twitte_AMAZONE Twitte_APPLE Twitte_GOOGE Twitte_IBM

Thời gian thực thi với chuỗi con 256

Power Demand Twitte_UPS Twitte_AMAZONE Twitte_APPLE Twitte_GOOGE Twitte_IBM

Thời gian thực thi với chuỗi con 512

Power Demand Twitte_UPS Twitte_AMAZONETwitte_APPLE Twitte_GOOGE Twitte_IBM

Hình 4.6 Thời gian thực thi của các tập dữ liệu

Kết quả từ các vị trí bất thường và biểu đồ thời gian thực thi của thực nghiệm cố định chuỗi con cho thấy sự thay đổi đáng kể khi độ dài chuỗi được điều chỉnh, với các giá trị lớn như 2000 và 4000.

Giải thuật trong không gian gốc cho các chuỗi có độ dài 8000, 12000 và 15000 cho thấy thời gian thực thi vượt trội, với thời gian thực thi cao nhất phụ thuộc vào độ dài chuỗi lớn, đặc biệt là ở độ dài 15.000 Đối với kích thước 8000, thời gian thực thi cao nhất xuất hiện ở hầu hết các chuỗi, điều này có thể được lý giải bởi đặc tính của chuỗi thời gian.

2000 4000 8000 12000 15000 2000 4000 8000 12000 15000 không gian gốc Không gian thu giảm

Thời gian thực thi hai giải thuật không gian gốc và không gian thu giảm khi thay đổi độ lớn chuỗi

Power 128 Power 256 Power 512 UPS 128 UPS 256

UPS 512 AMAZONE 128 AMAZONE 256 AMAZONE 512 APPLE 128

APPLE 256 APPLE512 GOOGE 128 GOOGE 256 GOOGE 512