CHƯƠNG 1: TỔNG QUAN VỀ DỮ LIỆU CHUỖI THỜI GIAN 1. Tổng quan 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 số lượng bán xe ô tô hàng tháng tại Quebec từ năm 1960 đến năm 1968 [1].1: Đường biểu diễn một chuỗi thời gian ( [1]). Các phương pháp quen thuộc thường được nghiên cứu trong khai phá dữ liệu chuỗi thời gian là: 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). Đề tài luận văn sẽ tìm hiểu về phương pháp Motif Discovery.
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 5 Gigabyte/1 tuần. 3 Luan van 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 không đồng nhất: định dạng của các loại dữ liệu khác nhau, tần số lấy mẫu khác nhau, bị nhiễu, thậm chí thiếu một vài giá trị hay dữ liệu không sạch,. Phát hiện motif trên dữ liệu chuỗi thời gian Motif của một chuỗi thời gian là một chuỗi con có tần suất xuất hiện cao nhất. Hiện nay, các bài toán về khai phá motif đang được các nhà khoa học nghiên cứu, phát triển và xây dựng các ứng dụng liên quan, đồng thời khai phá motif cũng liên quan tới các bài toán khác trong chuỗi thời gian nên có thể gọi nó là Bài toán cơ bản.
Có nhiều bài toán đã ứng dụng khai phá motif như: tìm hiểu thói quen của khách hàng, tìm các mặt hàng có chu kỳ doanh số giống nhau, phát hiện vi phạm bản quyền trong các bản nhạc, tìm những tháng trong quá khứ có lượng mưa giống như tháng vừa rồi, phát hiện đạ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: 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).
4 Luan van Hiện nay, các nhà khoa học trên thế giới đã và đang đi sâu vào phân tích và khai phá dữ liệu chuỗi thời gian. Từ nền tảng kiến thức đó đã xây dựng ra nhiều ứng dụng trong các lĩnh vực về tài chính, kinh tế, công nghệ. Dữ liệu chuỗi thời gian được sử dụng phổ biến trong các lĩnh vực 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, địa lý. Theo khảo sát của Tufte [4] (1992), từ 4000 hình được lấy ngẫu nhiên trong các báo tin tức trên thế giới được xuất bản trong giai đoạn từ 1974 đến 1989 cho thấy hơn 75% là các hình biểu diễ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ị 5 Luan van CHƯƠNG 2: CÁC KIẾN THỨC CƠ BẢN Để hỗ trợ trong quá trình tìm kiếm motif, trong chương này sẽ trình bày các khái niệm liên quan tới khai phá motif trong chuỗi thời gian và một vài công trình đã được các nhà khoa học nghiên cứu trong những năm gần đây. Chuỗi thời gian Chuỗi thời gian (Time series): Nếu T là một chuỗi thời gian thì T=(t1, t2,…,tn) gồm tập hợp n số có giá trị thực theo thời gian [5]. Cửa số trượt (Sliding Window) Cho một dữ liệu 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 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 C [6].1: Cửa sổ trượt trên dữ liệu chuỗi thời gian ( [7]).
Chuỗi con Cho một chuỗi thời gian T = (t1, t2…, tn), một chuỗi con có chiều dài n của T là một chuỗi Ti, n = (ti, ti+1,…, ti+n-1) với 1≤ i ≤ m-n+1 [5]. So trùng mẫu Cho một số thực R (gọi là phạm vi và do người dùng định nghĩa) và một dữ liệu chuỗi thời gian T chứa một chuỗi con C bắt đầu tại vị trí p và một chuỗi con 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 6 Luan van 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. 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 Ci của T bắt đầu tại vị trí i và một chuỗi con Cj của T bắt đầu tại vị trí j, nếu DISTANCE(Ci , Cj) ≤ R thì Cj được gọi là chuỗi con tương tự của Ci [8]. Các chuỗi con tương tự nhất với một chuỗi con Ci là các chuỗi con 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 Ci. 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ị. Các trường hợp này được gọi là so trùng tầm thường.3: Hai chuỗi con trong chuỗi thời gian T so trùng tầm thường ( [6]).
So trùng không tầm thường Cho chuỗi thời gian T có chiều dài n, chuỗi C và M có chiều dài m và là chuỗi con của chuỗi thời gian T. Chuỗi C bắt đầu tại vị trí p, chuỗi M bắt đầu tại vị trí q. Ta nói chuỗi con M và chuỗi con C so trùng không tầm thường nếu |p-q| ≥ m [6]. 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 không theo thứ tự của các chuỗi thời gian độ dài m (độ dài m có thể khác nhau) [3].
Có nghĩa là cho một chuỗi thời gian dài, sau đó trích các chuỗi con theo một độ dài m, thì lúc này tạo ra được cơ sở dữ liệu chuỗi thời gian. Lúc này ta phải loại bỏ so trùng tầm thường. Trong trường hợp chuỗi con, khi trích các chuỗi con từ một chuỗi thời gian dài ta cũng hình thành một cơ sở dữ liệu chuỗi thời gian. Trong đó, mỗi chuỗi con được coi như là một chuỗi thời gian.
Khi thực hiện các bài toán trong khai phá dữ liệu chuỗi thời gian như tìm kiếm tương tự, phát hiện motif,. trong trường hợp 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 ta phải loại bỏ các trường hợp so trùng tầm thường. Các định nghĩa về Motif Năm 2002, Lin [6] và các cộng sự đã trình bày các định nghĩa về motif trong chuỗi thời gian như sau: Định nghĩa 1: Cho 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 (còn được gọi là 1-Motif) là chuỗi con Ci nào đó trong T có số lượng chuỗi con khớp không tầm thường với nó cao nhất. Motif quan trọng bậc K (còn gọi là K-Motif) là chuỗi con Ck nào đó trong T có số lượng chuỗi con khớp không tầm thường với nó 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 [8].
Định nghĩa 1 còn được gọi là định nghĩa căn bản của motif. Chú ý là Định nghĩa 1 qui định một chuỗi con không thể cùng lúc thuộc về hai motif khác nhau Điều này thể hiện qua điều kiện DISTANCE(Ci, Ck) > 2R, với mọi 1≤ i < k.4 là một ví dụ minh họa cho trường hợp này. 8 Luan van Hình 2.5: Một chuỗi thời gian chứa 3 motif [6] Định nghĩa 2: Chuỗi con motif là một cặp chuỗi con {Ti,n, Tj,n} so trùng không tầm thường của một chuỗi thời gian T giống nhau nhất. Nói cách khác, ∀a,b,i,j cặp {Ti,n, Tj,n} là chuỗi con motif nếu : Dist(Ti,n, Tj,n) ≤ Dist(Ta,n,Tb,n), |i-j| ≥ w và |a-b| ≥ w trong đó w > 0.
[5] Chú ý là w được dùng trong định nghĩa trên giúp ta loại bỏ được những so trùng tầm thường trong trường hợp chuỗi con [4] và Dist(Ci, Cj) là độ đo khoảng cách có nghĩa giữa hai chuỗi thời gian. 9 Luan van Năm 2009, trong [5] Mueen và các cộng sự đã đưa ra khái niệm về motif như một cặp chuỗi thời gian giống nhau nhất trong cơ sở dữ liệu chuỗi thời gian hay cặp chuỗi con giống nhau 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 như sau: Motif trong một cơ sở dữ liệu chuỗi thời gian S là một cặp chuỗi thời gian khác nhau {Ti, Tj}, i ≠ j, trong cơ sở dữ liệu S có khoảng cách nhỏ nhất. Nghĩa là x, y, x ≠ y, i ≠ j, DISTANCE(Ti, Tj) ≤ DISTANCE(Tx, Ty) [3].
Ví dụ về một motif theo định nghĩa 2009 [4]. Các độ đo khoảng cách Đố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 - Dist(Q,C) = Dist(C,Q) - Dist(Q,C) ≥ 0 với mọi Q, C - Dist(Q,C) < Dist(Q, Z) + D(C, Z) Dưới đây là các độ đo thường được sử dụng 2. Độ đo Minkowski 10 Luan van Hầu hết các công trình nghiên cứu trên dữ liệu chuỗi thời gian đều dựa trên độ đo Minkowski để tính khoảng cách (hay mức độ tương tự) giữa hai chuỗi con.