Luận văn: Tìm kiếm motif trên chuỗi thời gian bằng giải thuật SCRIMP++

Nghiên cứu tìm kiếm motif trên chuỗi thời gian bằng giải thuật SCRIMP trong luận văn thạc sĩ. Phân tích nguyên lý, hiệu năng và ứng dụng thực tiễn.

• Tác giả: Trần Thị Dung
• Người hướng dẫn: TS. 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: Khoa học máy tính
• Đề tài: Tìm kiếm motif trên chuỗi thời gian bằng giải thuật SCRIMP++
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2020
• Địa điểm: Hồ Chí Minh

Tóm tắt

I. Tổng quan về luận văn thạc sĩ motif chuỗi thời gian SCRIMP

Luận văn thạc sĩ 'Tìm kiếm motif trên chuỗi thời gian bằng giải thuật SCRIMP++' của tác giả Trần Thị Dung nghiên cứu phương pháp phát hiện motif trong dữ liệu chuỗi thời gian. Motif là chuỗi con lặp lại phổ biến nhất trong chuỗi thời gian, đóng vai trò quan trọng trong khai phá dữ liệu. Nghiên cứu tập trung vào thuật toán SCRIMP++ - phiên bản cải tiến của SCRIMP nhằm nâng cao hiệu quả phát hiện motif. SCRIMP++ sử dụng kỹ thuật loại bỏ so trùng tầm thường và tối ưu hóa quá trình tìm kiếm. Luận văn cung cấp khung lý thuyết vững chắc về motif, định nghĩa chính xác và ứng dụng trong thực tế. Kết quả nghiên cứu chứng minh tính hiệu quả của thuật toán trong xử lý dữ liệu thời gian thực. Đây là đề tài có ý nghĩa khoa học và thực tiễn cao trong lĩnh vực khoa học máy tính.

1.1. Khái niệm motif trong chuỗi thời gian

Motif trong chuỗi thời gian là chuỗi con xuất hiện lặp lại nhiều lần trong dữ liệu. Năm 2002, Lin và cộng sự định nghĩa motif quan trọng nhất (1-Motif) là chuỗi con có số lượng chuỗi con khớp không tầm thường cao nhất. Định nghĩa này được mở rộng thành K-Motif - motif quan trọng bậc K. Điều kiện D(Ck, Ci) > 2R đảm bảo sự phân biệt giữa các motif. Một chuỗi con không thể thuộc hai motif khác nhau đồng thời. Ví dụ minh họa cho thấy ba motif xuất hiện trong cùng một chuỗi thời gian. Tính chất này quan trọng trong việc xây dựng thuật toán phát hiện motif chính xác.

1.2. Ứng dụng của motif trong khai phá dữ liệu

Phát hiện motif có ứng dụng rộng rãi trong nhiều lĩnh vực như y tế (phân tích nhịp tim), tài chính (dự báo xu hướng), khoa học môi trường (phân tích dữ liệu khí tượng). Trong chuỗi thời gian dài, việc trích xuất chuỗi con tạo thành cơ sở dữ liệu motif. Loại bỏ so trùng tầm thường là bước quan trọng để đảm bảo kết quả chính xác. Nghiên cứu này cung cấp nền tảng lý thuyết cho các ứng dụng thực tế. SCRIMP++ cải tiến thuật toán SCRIMP bằng cách tập trung vào các điểm cực tiểu, nâng cao hiệu quả xử lý.

II. Phân tích các vấn đề trong phát hiện motif chuỗi thời gian

Phát hiện motif trong chuỗi thời gian đối mặt nhiều thách thức. Thuật toán SCRIMP ban đầu yêu cầu kiểm tra toàn bộ chuỗi con, dẫn đến thời gian thực hiện lâu. Việc xác định motif chính xác đòi hỏi loại bỏ các so trùng tầm thường. Định nghĩa motif theo Lin (2002) gây khó khăn trong phân biệt ranh giới giữa các motif. Thuật toán preSCRIMP cải tiến từ SCRIMP tập trung vào các điểm cực tiểu, nhưng vẫn tồn tại hạn chế trong xử lý dữ liệu lớn. Tính chất Consecutive Neighborhood Preserving (CNP) giúp tối ưu hóa nhưng chưa giải quyết triệt để vấn đề hiệu suất. Nghiên cứu này phân tích sâu các vấn đề này để đề xuất giải pháp cải tiến.

2.1. Hạn chế của thuật toán SCRIMP ban đầu

Thuật toán SCRIMP ban đầu yêu cầu đánh giá tất cả các cặp chuỗi con, dẫn đến độ phức tạp O(n²). Thời gian thực hiện lâu do phải đợi thuật toán hoàn thành mới xác định được motif chính xác. Việc loại bỏ so trùng tầm thường tốn nhiều tài nguyên tính toán. Ma trận profile index chứa nhiều khoảng giá trị liên tiếp, gây khó khăn trong phân tích. Thuật toán chỉ hoạt động hiệu quả trên dữ liệu nhỏ. Những hạn chế này thúc đẩy nghiên cứu cải tiến thuật toán SCRIMP++.

2.2. Thách thức trong định nghĩa motif chính xác

Định nghĩa motif theo Lin (2002) yêu cầu D(Ck, Ci) > 2R, gây khó khăn trong việc thiết lập tham số R phù hợp. Một chuỗi con không thể thuộc hai motif khác nhau cùng lúc. Tính chất này hạn chế khả năng phát hiện motif chồng lấn. Trong thực tế, dữ liệu thường chứa nhiễu, ảnh hưởng đến độ chính xác. Việc phân biệt motif chính xác và xấp xỉ trở nên phức tạp. Nghiên cứu này đề xuất phương pháp cải tiến để giải quyết các thách thức trên.

III. Giải pháp phương pháp SCRIMP phát hiện motif

Nghiên cứu đề xuất giải pháp SCRIMP++ cải tiến từ thuật toán SCRIMP ban đầu. SCRIMP++ tập trung vào các điểm cực tiểu thay vì đánh giá toàn bộ chuỗi con, nâng cao hiệu quả xử lý. Thuật toán sử dụng kỹ thuật loại bỏ sớm (early abandon) khi phát hiện chuỗi con không tiềm năng. Tính chất Consecutive Neighborhood Preserving (CNP) giúp tối ưu hóa quá trình tìm kiếm. SCRIMP++ cải thiện độ chính xác bằng cách kết hợp các tiêu chí lựa chọn motif. Kết quả thực nghiệm chứng minh thuật toán mới vượt trội về thời gian và độ chính xác. Phương pháp này phù hợp xử lý dữ liệu thời gian thực lớn.

3.1. Cải tiến thuật toán SCRIMP

SCRIMP++ cải tiến từ SCRIMP bằng cách tập trung vào các điểm cực tiểu, giảm độ phức tạp tính toán. Thuật toán sử dụng kỹ thuật loại bỏ sớm (early abandon) khi phát hiện chuỗi con không đạt ngưỡng. Ma trận profile index được tối ưu hóa bằng tính chất CNP. Việc đánh giá đường chéo trong thuật toán được cải tiến để tăng tốc độ xử lý. SCRIMP++ cung cấp kết quả motif chính xác hơn so với phiên bản gốc. Nghiên cứu chứng minh thuật toán mới hoạt động hiệu quả trên dữ liệu đa dạng.

3.2. Ứng dụng tính chất CNP trong tối ưu hóa

Tính chất Consecutive Neighborhood Preserving (CNP) cho phép thuật toán SCRIMP++ dự đoán các lân cận gần nhất. Nếu i và j là lân cận, khả năng i+1 cũng là lân cận của j+1 cao. Tính chất này giúp giảm số lượng đánh giá cần thiết. Ma trận index chứa các khoảng giá trị liên tiếp, tương ứng với các chuỗi con lân cận. SCRIMP++ tận dụng CNP để tối ưu hóa quá trình tìm kiếm motif. Kết quả cho thấy thuật toán mới giảm đáng kể thời gian xử lý. Tính chất CNP là nền tảng quan trọng trong cải tiến thuật toán.

IV. Kết luận và ứng dụng luận văn thạc sĩ motif

Luận văn thạc sĩ trình bày nghiên cứu toàn diện về phát hiện motif trong chuỗi thời gian bằng thuật toán SCRIMP++. Kết quả chứng minh SCRIMP++ vượt trội về hiệu quả và độ chính xác so với phiên bản gốc. Thuật toán mới cải tiến bằng cách tập trung vào các điểm cực tiểu, sử dụng kỹ thuật loại bỏ sớm. Tính chất CNP được ứng dụng hiệu quả trong tối ưu hóa. Kết quả thực nghiệm trên dữ liệu đa dạng xác nhận tính khả thi của phương pháp. Nghiên cứu mở ra hướng phát triển mới trong lĩnh vực khai phá dữ liệu chuỗi thời gian. Kết luận nhấn mạnh tầm quan trọng của thuật toán trong xử lý dữ liệu thời gian thực.

4.1. Đánh giá kết quả nghiên cứu

Nghiên cứu đánh giá SCRIMP++ trên nhiều bộ dữ liệu khác nhau. Thuật toán mới đạt hiệu suất vượt trội về thời gian xử lý. Độ chính xác trong phát hiện motif được cải thiện đáng kể. So sánh với thuật toán gốc cho thấy sự vượt trội của phiên bản cải tiến. Kết quả thực nghiệm chứng minh tính khả thi của phương pháp. SCRIMP++ phù hợp xử lý dữ liệu lớn trong thời gian thực. Nghiên cứu này đóng góp quan trọng vào lĩnh vực khoa học máy tính.

4.2. Hướng phát triển tương lai

Nghiên cứu đề xuất các hướng phát triển tương lai như tích hợp trí tuệ nhân tạo. SCRIMP++ có thể kết hợp với học máy để nâng cao độ chính xác. Áp dụng thuật toán trong lĩnh vực y tế và tài chính hứa hẹn nhiều tiềm năng. Nghiên cứu mở rộng sang phát hiện motif đa chiều. Tối ưu hóa thuật toán cho môi trường điện toán đám mây. Những hướng phát triển này sẽ góp phần thúc đẩy lĩnh vực khai phá dữ liệu chuỗi thời gian.

Trích đoạn nội dung tài liệu

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  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 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 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 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.5: Một chuỗi thời gian chứa 3 motif [6] 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 : Đị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 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 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 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. Công thức tính khoảng cách Minkowski được định nghĩa như sau: Dist(Q, C) = √∑ ( − ) ) (2.