Chương 1: Tổng quan về dữ liệu chuỗi thời gian; - Chương 2: Các kiến thức cơ bản; - Chương 3: Các công trình liên quan; - Chương 4: Thuật toán SKIMP; - Chương 5: Đánh giá bằng thực nghiệm; - Chương 6: Kết luận và hướng phát triển. 3 o CHƯƠNG 2 CÁC KIẾN THỨC CƠ BẢN Để hiểu rõ hơn về motif và thuật toán SKIMP, chương này sẽ trình bày các khái niệm cơ bản về chuỗi thời gian và các khái niệm phục vụ quá trình tìm kiếm motif trên tất cả độ dài chuỗi con của chuỗi thời gian. Khái niệm chuỗi thời gian Chuỗi thời gian T là một dãy số thực T = t1, t2, t3,…, tn với n là độ dài chuỗi thời gian T [4].1: Hình ảnh minh họa chuỗi thời gian từ mức độ tăng trưởng GDP của Mỹ qua các giai đoạn từ 1950 đến 2010 Nguồn: aptech. Cửa sổ trượt Ta có chuỗi thời gian T có chiều dài n, để xác định được chuỗi con có chiều dài m, ta dùng một cửa sổ trượt có kích thước m x m di chuyển (trượt) từ trái sang phải trên chuỗi thời gian T [5].2: Ví dụ về cửa sổ trượt với kích thước m = 3, thu được 2 chuỗi con t1 t2 t3 và chuỗi con t2 t3 t4 4 o 2.
Chuỗi con Chuỗi con Ti của chuỗi thời gian T (có chiều dài n) là một tập hợp liên tục các giá trị trên chuỗi thời gian T bắt đầu từ vị trí i và có chiều dài m sao cho (theo [4]): Ti,m = t i , t i+1 , … , t i+m−1, 1 ≤ i ≤ n − m + 1. Trong ảnh minh hoạ bên dưới, các chuỗi S(1, 5), S(2, 5), S(3, 5) được gọi là chuỗi con của chuỗi thời gian T, có chiều dài m = 5 và bắt đầu lần lượt tại các vị trí 1, 2, 3.3: Ví dụ về chuỗi con trong chuỗi thời gian T với chiều dài chuỗi con là 5 và thu được 03 chuỗi con S(1, 5), S(2, 5), S(3, 5) 2. So trùng mẫu Cho một số thực R (hay gọi là phạm vi do người dùng tự định nghĩa) và chuỗi thời gian T. Chuỗi con A bắt đầu tại vị trí a và chuỗi con B bắt đầu tại vị trí b được gọi là trùng (khớp) nhau khi khoảng cách giữa chúng D(A, B) ≤ R [5].4: Ví dụ về so trùng mẫu 2 chuỗi con A, B Khi thực nghiệm, chúng ta có thể quan sát thấy kết quả phù hợp nhất của chuỗi con đang xét với một chuỗi con bất kỳ (ngoài chính nó) thường có xu hướng là các chuỗi con bắt đầu tại các vị trí chỉ lệch một hoặc vài điểm về bên trái hoặc bên phải so với chuỗi con đang được đề cập.5: Kết quả so trùng mẫu tốt nhất là chính nó hoặc chuỗi con bắt đầu một vài điểm về bên trái hoặc bên phải so với chuỗi con đang xét [6] Và các mẫu so trùng như hình trên thông thường sẽ được loại bỏ ngay trong quá trình tính toán để tránh trường hợp tìm thấy quá nhiều motif vô nghĩa.
Và các mẫu trên được gọi là so trùng tầm thường, được nghĩa tại mục 2. So trùng tầm thường Cho 2 chuỗi con Ti và Tj, ta thấy có thể chuỗi con Tj bắt đầu tại các vị trí lệch một hay hai điểm về bên trái hay bên phải so với vị trí bắt đầu của chuỗi con Ti. Có nghĩa là chuỗi con mới lệch một khoảng so với chuỗi con cũ và hai chuỗi con này có chung một đoạn giá trị. Ví dụ 02 chuỗi con A bắt đầu tại vị trí a và B bắt đầu tại vị trí b.
Nếu a = b hoặc không tồn tại chuỗi con B’ bắt đầu tại b’ sao cho D(A, B’) > R, và thoả một trong hai điều kiện b < b’ < a hoặc a < b’ < b. Các trường hợp này được gọi là so trùng tầm thường [5].6: Ví dụ về so trùng tầm thường [6] 2. So trùng không tầm thường Cho chuỗi thời gian T có chiều dài n và hai chuỗi con có chiều dài m: chuỗi con A bắt đầu tại vị trí a và B bắt đầu tại vị trí b. Ta nói hai chuỗi con A và B là so trùng không tầm thường nếu |a - b| ≥ m [6].
Chuỗi con phủ nhau Từ khái niệm so trùng không tầm thường (trình bày tại phần 2.2), ta có thể định nghĩa thêm một trường hợp 2 chuỗi con phủ nhau. Chuỗi con Ti,m và chuỗi con Tu,p được gọi là phủ nhau (p ≤ m) nếu khoảng trùng lặp giữa 2 chuỗi con Ti,m và Tu,p lớn hơn ngưỡng c (do người dùng định nghĩa) [7]. Vậy, 02 chuỗi con được gọi là phủ nhau nếu thoả một trong hai điều kiện sau: i − u ≥ 0 && i − u ≤ (1 − c%) ∗ p (2.1) i − u < 0 && m + i − u ≥ c% ∗ p Từ khái niệm này, có thể áp dụng vào thuật toán để loại bỏ các motif phủ nhau sau khi tìm motif của tất cả độ dài chuỗi con của chuỗi thời gian. Cụ thể như sau: - Từ hai motif thu được, giả sử motif A( a1, a2) có độ dài ma và B(b1, b2) có độ dài mb ta sẽ tiến hành kiểm tra motif phủ cho các trường hợp + Ta1, ma vs Tb1, mb; + Ta1, ma vs Tb2, mb; + Ta2, ma vs Tb1, mb; + Ta2, ma vs Tb2, mb.
- Áp dụng công thức (2.1) và giả sử tham số c% = 0.1 thì có thể diễn giải công thức trên như sau: + Nếu chuỗi con Ti nằm phía sau chuỗi con Tu và khoảng cách giữa 2 vị trí bắt đầu của 2 chuỗi con (i và u) nhỏ hơn hoặc bằng 90% độ dài chuỗi con Tu thì chuỗi con Tu bị chuỗi con Ti phủ lên.7: Minh hoạ trường hợp i – u >= 0 trong công thức (2.1) + Nếu chuỗi con Ti nằm phía trước chuỗi con Tu và khoảng cách giữa vị trí kết thúc của chuỗi con Ti (m + i) và vị trí bắt đầu của chuỗi con Tu (u) lớn hơn hoặc bằng 10% độ dài chuỗi con Tu thì chuỗi con Tu bị chuỗi con Ti phủ lên.8: Minh hoạ trường hợp i – u < 0 trong công thức (2. Các định nghĩa về motif Hiện tại, có 02 định nghĩa motif được sử dụng: định nghĩa motif năm 2002 của Lin và các cộng sự [6] và định nghĩa motif năm 2009 của Mueen và các cộng sự [4]. Định nghĩ motif của Lin và các cộng sự Định nghĩa 1: Cho chuỗi thời gian T có chiều dài n và số thực R, motif quan trọng nhất trong T (hay 1-Motif) là chuỗi con Ti nào đó trong T mà nó có số lượng chuỗi con khớp không tầm thường cao nhất và motif quan trọng bậc k (hay k-Motif) là chuỗi con Tk nào đó có số lượng chuỗi con khớp không tầm thường cao thứ k và phải thỏa mãn điều kiện D(Tk, Ti) > 2R, với 1 ≤ i ≤ k [6]. Lưu ý rằng định nghĩa trên quy định rằng các điểm thuộc 2 chuỗi con trong motif phải được bỏ qua, nếu không bỏ qua thì hai motif có thể có phần lớn các điểm trùng nhau hay về cơ bản là giống nhau.7 minh họa sự cần thiết của điều kiện này trên không gian 2D.9: Ví dụ giải thích điều kiện các motif phải cách nhau ít nhất 2R [6] Định nghĩa 2: Motif là một cặp chuỗi con Ti,n, Tj,n so trùng không tầm thường và giống nhau nhất.
Hay nói cách khác, ⩝ a, b, i, j cặp Ti,n, Tj,n là motif nếu (theo [4]): D(Ti,n, Tj,n) ≤ D(Ta,n,Tb,n), |i - j| ≥ w và |a - b| ≥ w trong đó w > 0. Với w là tham số người dùng định nghĩa, dùng để làm ngưỡng loại bỏ những chuỗi con so trùng tầm thường. Định nghĩa motif của Mueen và các cộng sự Theo Mueen và các cộng sự thì motif là một cặp chuỗi con giống nhau nhất trong chuỗi thời gian. Cụ thể như sau: Motif trong chuỗi thời gian T là một cặp chuỗi con Ti, Tj, i ≠ j có khoảng cách nhỏ nhất [4].10: Ví dụ hình ảnh motif trong chuỗi thời gian T [8] 2.
Độ đo Euclide Có nhiều độ đo được sử dụng trong quá trình tìm kiếm motif như độ đo Dynamic Time Warping, Minkowski bao gồm các độ đo: Manhattan, Max và Euclide,… thì độ do Euclide được dùng nhiều hơn hết vì nó đơn giản, dễ thực hiện và 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 [9]. Cho 2 chuỗi thời gian A và B có độ dài m thì công thức tính khoảng cách Euclide giữa A và B như sau: 𝑚 𝐷 (𝐴, 𝐵) = √∑ (𝐴𝑖 − 𝐵𝑖 )2 𝑣ớ𝑖 𝐴𝑖 ∈ 𝐴, 𝐵𝑖 ∈ 𝐵, 𝑖 = 1, … , 𝑚 (2.2) 𝑖=1 Mặc dù được sử dụng phổ biến, tuy nhiên khoảng cách Euclide có nhược điểm là độ chính xác không cao đối với các trường hợp có biên độ dao động khác nhau. Thông thường, để sử dụng khoảng cách Euclide, dữ liệu cần phải được chuẩn hoá trước, và một trong các phương pháp chuẩn hoá đang được sử dụng là chuẩn hoá Z sẽ được trình bày trong phần 2. Chuẩn hoá Z Chuẩn hóa Z lần đầu tiên được Goldin & Kanellakis đề cập đến [10].
Quy trình đảm bảo rằng tất cả các phần tử của vectơ đầu vào được chuyển đổi thành vectơ đầu ra có giá trị trung bình xấp xỉ 0 trong khi độ lệch chuẩn nằm trong phạm vi gần bằng 1. Công thức của phép biến đổi được hiển thị bên dưới: 9 o 𝑥𝑖 − 𝜇 𝑥𝑖′ = , 𝑣ớ𝑖 𝑖 ∈ 𝑁, μ là giá trị trung bình và δ là độ lệch chuẩn.11: Hình ảnh minh hoạ 2 chuỗi con sau khi chuẩn hoá Z Nguồn: jmotif.io Đầu tiên, lấy giá trị ban đầu xi trừ cho giá trị trung bình µ của chuỗi thời gian, sau đó chia cho giá trị độ lệch chuẩn δ. Theo hầu hết các nghiên cứu liên quan đến chuỗi thời gian thì chuẩn hóa Z là một bước tiền xử lý thiết yếu. Tuy nhiên, lưu ý rằng trong một số trường hợp, việc xử lý trước này không được khuyến khích vì nó gây ra các sai lệch (ví dụ trường hợp phương sai tín hiệu nhỏ đáng kể).
Distance Profile Distance Profile D là một vectơ khoảng cách Euclide giữa chuỗi con Ti,m với các chuỗi con còn lại trong chuỗi thời gian T (các chuỗi con có cùng chiều dài m) [11]. Hay Di = [di,1, di,2,., di,n-m + 1], trong đó di, j (1 ≤ j ≤ n - m + 1) là khoảng cách giữa Ti, m và Tj, m. Và biểu diễn tất cả các Distance Profile trong chuỗi thời gian T theo từng hàng và từng cột, ta gọi đó là Matrix Distance.