Mục tiêu nghiên cứu
Mục tiêu của bài viết là nghiên cứu và triển khai thuật toán SCRIMP++ cho việc phát hiện motif trong dữ liệu chuỗi thời gian Bên cạnh đó, bài viết cũng sẽ xem xét các phương pháp cải tiến nhằm nâng cao tốc độ xử lý của thuật toán SCRIMP++.
Cách tiếp cận và phương pháp nghiên cứu
Tổng kết các kết quả nghiên cứu liên quan trước đây Đánh giá hiệu quả của các phương pháp Thực nghiệm để kiểm tra kết quả
Nghiên cứu tài liệu, ứng dụng mô hình lý thuyết và chứng minh bằng thực nghiệm.
Ý nghĩa thực tiễn của đề tài
Nghiên cứu này sẽ tạo nền tảng cho các nghiên cứu tiếp theo liên quan đến phát hiện motif trong khai thác dữ liệu chuỗi thời gian, đồng thời cung cấp tài liệu tham khảo hữu ích cho các nhà khoa học quan tâm đến lĩnh vực này.
TỔNG QUAN VỀ DỮ LIỆU CHUỖI THỜI GIAN
Tổng quan
Một chuỗi thời gian (time series) là tập hợp các điểm dữ liệu được thu thập theo từng khoảng thời gian liên tiếp, với tần suất thời gian đồng nhất.
Hình 1.1 minh họa một ví dụ về chuỗi thời gian biểu diễn số lượng bán xe ô tô hàng tháng tại Quebec từ năm 1960 đến năm 1968 [1]
Hình 1.1: Đường biểu diễn một chuỗi thời gian ( [1])
Trong khai phá dữ liệu chuỗi thời gian, các phương pháp phổ biến bao gồm tìm kiếm tương tự, gom cụm, phân lớp, phát hiện motif, khai phá luật, phát hiện bất thường, trực quan hóa và dự báo Luận văn này sẽ tập trung nghiên cứu phương pháp phát hiện motif (Motif Discovery).
Theo E Keogh (2002) [2] khi nghiên cứu trên dữ liệu chuỗi thời gian thường gặp những khó khăn và thách thức:
Dữ liệu rất lớn: dữ liệu điện tâm đồ (ECG) trong một giờ có thể lên đến 1 Gigabyte, dữ liệu lưu vết các truy cập trên một website khoảng
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
Dữ liệu thường gặp vấn đề không đồng nhất, với định dạng và tần số lấy mẫu khác nhau, có thể bị nhiễu hoặc thiếu một số giá trị, dẫn đến tình trạng dữ liệu không sạch.
Phát hiện motif trên dữ liệu chuỗi thời gian
Motif trong chuỗi thời gian là chuỗi con có tần suất xuất hiện cao nhất Hiện tại, nghiên cứu về khai phá motif đang được các nhà khoa học chú trọng, nhằm phát triển ứng dụng và giải quyết các bài toán liên quan Do đó, khai phá motif được xem là một bài toán cơ bản trong lĩnh vực chuỗi thời gian.
Khai phá motif đã được ứng dụng rộng rãi trong nhiều bài toán, bao gồm việc phân tích thói quen của khách hàng, xác định các mặt hàng có chu kỳ doanh số tương tự, phát hiện vi phạm bản quyền trong âm nhạc, so sánh lượng mưa của tháng hiện tại với các tháng trong quá khứ, và nhận diện hành vi đạo văn.
Phát hiện motif là tìm 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.2)
Hình 1.2: Ví dụ về motif trong chuỗi thời gian ( [3])
Motif là hai chuỗi con màu đỏ và màu xanh trong dữ liệu chuỗi thời gian (hình trên)
So sánh chi tiết hai chuỗi con là motif (hình dưới)
Hiện nay, các nhà khoa học đang tích cực phân tích và khai thác dữ liệu chuỗi thời gian, từ đó phát triển nhiều ứng dụng hữu ích trong các lĩnh vực tài chính, kinh tế và công nghệ.
Dữ liệu chuỗi thời gian là một công cụ quan trọng trong nhiều lĩnh vực như khoa học, công nghệ, tài chính, thương mại, y học, thời tiết, môi trường và địa lý Một khảo sát của Tufte (1992) cho thấy từ 4000 hình ảnh ngẫu nhiên trong các báo tin tức toàn cầu từ 1974 đến 1989, hơn 75% trong số đó là các biểu đồ thể hiện dữ liệu chuỗi thời gian.
Cấu trúc luận văn
Luận văn được trình bày 5 chương
+ Chương 1: Tổng quan về dữ liệu chuỗi thời gian
+ Chương 2: Nền tảng kiến thức
+ Chương 3: Phương pháp phát hiện motif dựa vào giải thuật SCRIMP++ + Chương 4: Đánh giá bằng thực nghiệm
+ Chương 5: Kết luận và kiến nghị
CÁC KIẾN THỨC CƠ BẢN
Các khái niệm
Chuỗi thời gian (Time series): Nếu T là một chuỗi thời gian thì T=(t 1 , t 2 ,…,t n ) gồm tập hợp n số có giá trị thực theo thời gian [5]
2.1.2 Cửa số trượt (Sliding Window)
Để xác định chuỗi con có chiều dài m từ dữ liệu chuỗi thời gian T có 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 từng chuỗi con C.
Hình 2.1: Cửa sổ trượt trên dữ liệu chuỗi thời gian ( [7])
Cho một chuỗi thời gian T = (t 1 , t 2 …, t n ), một chuỗi con có chiều dài n của T là một chuỗi T i, n = (t i , t i+1 ,…, t i+n-1 ) với 1≤ i ≤ m-n+1 [5]
Cho một số thực R (được định nghĩa bởi người dùng) và một dữ liệu chuỗi thời gian T với chuỗi con C bắt đầu tại vị trí p và chuỗi con M bắt đầu tại vị trí q, nếu khoảng cách giữa C và M, ký hiệu là D(C, M), thỏa mãn điều kiện D(C, M) ≤ R, thì
7 dùng công thức tính khoảng cách euclide để 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 [6]
Có hai kiểu so trùng mẫu: so trùng tầm thường và so trùng không tầm thường
Hình 2.2: So trùng khớp giữa hai chuỗi con C và M được cắt ra từ chuỗi thời gian T ( [6]) 2.1.4.1 So trùng tầm thường
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 DISTANCE(C_i, C_j) nhỏ hơn hoặc bằng R, thì chúng ta có thể xác định mối quan hệ giữa các chuỗi con này trong ngữ cảnh của chuỗi thời gian T.
C j ) ≤ R thì Cj được gọi là chuỗi con tương tự của C i [8]
Các chuỗi con tương tự nhất với chuỗi con C i là những chuỗi con bắt đầu tại các vị trí lệch một hoặc hai điểm so với vị trí bắt đầu của 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à chúng 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.3: Hai chuỗi con trong chuỗi thời gian T so trùng tầm thường ( [6])
2.1.4.2 So trùng không tầm thường
Cho chuỗi thời gian T có độ dài n, chuỗi C và M là các chuỗi con 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 M và C được coi là so trùng không tầm thường nếu khoảng cách giữa chúng thỏa mãn điều kiện |p-q| ≥ m.
2.1.5 Cơ sở dữ liệu chuỗi thời gian (A time series database)
Cơ sở dữ liệu chuỗi thời gian là tập hợp các chuỗi thời gian không theo thứ tự với độ dài m, trong đó m có thể khác nhau Để tạo ra cơ sở dữ liệu này, ta sẽ trích xuất các chuỗi con từ một chuỗi thời gian dài, đồng thời cần loại bỏ các trường hợp trùng lặp không cần thiết.
Khi trích xuất các chuỗi con từ một chuỗi thời gian dài, chúng ta tạo ra một cơ sở dữ liệu chuỗi thời gian mới Mỗi chuỗi con này được xem như một chuỗi thời gian độc lập.
Khi giải quyết các bài toán trong khai thác dữ liệu chuỗi thời gian, như tìm kiếm sự tương tự hay phát hiện motif, cần phải loại bỏ các trường hợp trùng lặp tầm thường, đặc biệt khi cơ sở dữ liệu là tập hợp các chuỗi con trong một chuỗi thời gian dài.
2.1.6 Các định nghĩa về Motif
Năm 2002, Lin và các cộng sự đã đưa ra định nghĩa về motif trong chuỗi thời gian Cụ thể, đối với một chuỗi thời gian T có chiều dài n và một số thực R, motif quan trọng nhất trong T, hay còn gọi là 1-Motif, là một chuỗi con Ci nào đó trong T.
Motif quan trọng bậc K (K-Motif) là chuỗi con Ck trong chuỗi T, 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(Ck, Ci) > 2R với mọi 1 ≤ i ≤ K Định nghĩa này, còn được gọi là định nghĩa căn bản của motif, quy định rằng một chuỗi con không thể thuộc về hai motif khác nhau cùng lúc, thể hiện qua điều kiện DISTANCE(Ci, Ck) > 2R với mọi 1 ≤ i < k Hình 2.4 minh họa cho trường hợp này.
Chuỗi con motif được định nghĩa là một cặp chuỗi con {T i,n, T j,n} có sự trùng lặp không tầm thường trong một chuỗi thời gian T giống nhau nhất Cụ thể, với mọi a, b, i, j, cặp {T i,n, T j,n} sẽ được xem là chuỗi con motif nếu đáp ứng các điều kiện nhất định.
Dist( T i,n , T j,n ) ≤ Dist( T a,n , T b,n ), | i-j | ≥ w và | a-b | ≥ w trong đó w > 0 [5]
Trong định nghĩa trên, việc sử dụng w giúp loại bỏ những so sánh tầm thường giữa các chuỗi con [4] Đồng thời, Dist(Ci, Cj) được xác định là độ đo khoảng cách có nghĩa giữa hai chuỗi thời gian.
Vào năm 2009, Mueen và các cộng sự đã giới thiệu khái niệm "motif" như một cặp chuỗi thời gian tương đồng nhất trong cơ sở dữ liệu chuỗi thời gian, hoặc như cặp chuỗi con tương đồng nhất trong một chuỗi thời gian dài hơn Các khái niệm này được định nghĩa cụ thể để phục vụ cho việc phân tích dữ liệu chuỗi thời gian.
Motif trong cơ sở dữ liệu chuỗi thời gian S được định nghĩa là một cặp chuỗi thời gian khác nhau {Ti, Tj}, với i ≠ j, có khoảng cách nhỏ nhất Điều này có nghĩa là đối với mọi x, y trong S, khoảng cách giữa Ti và Tj là tối thiểu.
≠ y, i ≠ j, DISTANCE(Ti, Tj) ≤ DISTANCE(Tx, Ty) [3]
Hình 2.5 Ví dụ về một motif theo định nghĩa 2009 [4].
Các độ đo khoảng cách
Trong bài toán phát hiện bất thường trên dữ liệu chuỗi thời gian, việc tìm kiếm tương tự, gom cụm và phân loại yêu cầu định nghĩa độ đo tương tự giữa các chuỗi thời gian Cụ thể, với hai chuỗi thời gian Q và C, cần tính toán độ đo tương tự Dist(Q,C) Để đảm bảo tính chính xác trong các phép đo này, chúng cần thỏa mãn một số tính chất cơ bản nhất định.
- Dist(Q,C) = 0 nếu và chỉ nếu Q = C
Dưới đây là các độ đo thường được sử dụng
Hầu hết các nghiên cứu về dữ liệu chuỗi thời gian sử dụng độ đo Minkowski để xác định 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 một cách cụ thể để phục vụ cho việc phân tích và so sánh dữ liệu hiệu quả.
Khi p = 1 ta có khoảng cách Manhattan
Khi p = 2 ta có khoảng cách Euclid
Khi p = ∞, ta đạt được khoảng cách tối đa Trong nghiên cứu chuỗi dữ liệu thời gian, giá trị của p có thể được chọn tùy ý, nhưng thường sử dụng độ đo Euclid vì tính đơn giản và dễ thực hiện Đây 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 được ứng dụng rộng rãi trong các bài toán khai thác dữ liệu chuỗi thời gian, bao gồm 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, độ đo này hỗ trợ hiệu quả trong việc lập chỉ mục dữ liệu, từ đó giảm thời gian cần thiết để phát hiện các bất thường trong 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.6 a)
+ Không thích hợp khi dữ liệu có biên độ dao động khác nhau (Hình 2.6 b)
Hình 2.6: Minh họa hai chuỗi thời gian giống nhau
Đườ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 [11]:
- 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 của Q 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 có những giá trị ngoại lệ, phương pháp này có thể được sử dụng để phân tích hiệu quả.
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 đảm bảo được mối quan hệ giữa các giá trị của dữ liệu
Phương pháp này có thể gặp lỗi ngoài giới hạn nếu giá trị đầu vào trong tương lai nằm ngoài khoảng giá trị [Min – Max] ban đầu.
2.2.2 Độ đo xoắn thời gian động
Khi so sánh hai mẫu khác nhau nhưng có hình dạng biến đổi tương tự, việc sử dụng khoảng cách so sánh từng cặp điểm 1-1 không hiệu quả Theo đo lường Euclid, mỗi điểm trên chuỗi thời gian này chỉ ánh xạ với một điểm trên chuỗi thời gian khác, yêu cầu các chuỗi có cùng độ dài Để khắc phục nhược điểm này, phương pháp Dynamic Time Warping (DTW) cho phép một điểm ánh xạ với nhiều điểm không thẳng hàng, được đề xuất bởi Bernt và Clifford vào năm 1994.
Hình 2.7: Độ đo Dynamic Time Warping và độ đo Euclidean ( [13])
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|