GIỚI THIỆU ĐỀ TÀI
Dữ liệu chuỗi thời gian
Chuỗi dữ liệu thời gian, hay còn gọi là chuỗi thời gian, là tập hợp các quan sát dữ liệu được thu thập theo thứ tự thời gian Cấu trúc của loại dữ liệu này có thể là hai hoặc nhiều chiều, trong đó có chiều thời gian, cho phép theo dõi và ghi lại dữ liệu tại những thời điểm cụ thể Trong thực tế, dữ liệu thường được đo lường theo nhiều cách khác nhau trong một khoảng thời gian nhất định Để đơn giản hóa việc lưu trữ và giảm độ phức tạp, người ta thường lưu lại các giá trị dữ liệu theo trình tự thời gian, được biểu diễn dưới dạng X=, trong đó xi là dữ liệu được ghi nhận tại thời điểm thứ i.
Ví dụ chúng ta có chuỗi thời gian theo dõi quá trình đo nhiệt độ như sau:
Hình 1-1: Minh họa về dữ liệu chuỗi thời gian theo dõi quá trình đo nhiệt độ
Trong thực tế, dữ liệu chuỗi thời gian xuất hiện trong nhiều ứng dụng như theo dõi biến động giá chứng khoán, đo điện tâm đồ, giám sát mực nước sông và ghi lại truy cập trang web của người dùng Những dữ liệu này thường rất lớn và được lưu trữ trong thời gian dài, dẫn đến chi phí cao cho việc lưu trữ và khai thác Vì vậy, việc sử dụng các công cụ khai thác dữ liệu trên nền tảng máy tính đã trở thành xu hướng được nghiên cứu và áp dụng rộng rãi trong nhiều lĩnh vực trong những năm gần đây.
Hình 1-2: Đồ thị biễu diễn chuỗi dữ liệu thời gian điện tâm đồ (ECG)
Hình 1.1 và 1.2 mô tả quá trình đo nhiệt độ trong ngày và điện tâm đồ
Một số vấn đề khi nghiên cứu chuỗi dữ liệu thời gian:
Một trong những đặc điểm nổi bật của chuỗi thời gian là khối lượng dữ liệu lớn, chẳng hạn như khi ghi lại dữ liệu điện tâm đồ trong vòng 1 giờ, có thể đạt tới khoảng 1 Gigabyte Điều này tạo ra thách thức lớn trong việc phân tích, tính toán và xử lý dữ liệu chuỗi thời gian, nhằm đảm bảo kết quả chính xác trong thời gian hợp lý.
Phụ thuộc yếu tố chủ quan:
Kết quả dữ liệu chuỗi thời gian thường bị ảnh hưởng bởi yếu tố chủ quan của người thực hiện đo lường, cũng như các điều kiện và công cụ sử dụng trong quá trình đo.
Dữ liệu không đồng nhất:
Quá trình thu thập dữ liệu chuỗi thời gian gặp nhiều thách thức do sự đa dạng về định dạng, số lượng và tần suất lấy mẫu không đồng nhất, ảnh hưởng đến tính toàn vẹn của dữ liệu Hơn nữa, các vấn đề như nhiễu, thiếu giá trị và dữ liệu không sạch cũng làm giảm độ chính xác của quá trình đo đạc.
Nhận diện Motif trong dữ liệu chuỗi thời gian
Một trong những vấn đề quan trọng trong khai thác dữ liệu chuỗi thời gian là nhận diện các chuỗi con tương tự thường xuyên, được gọi là motif Các phương pháp phổ biến cho bài toán này bao gồm Brute-Force do J Lin và cộng sự đề xuất năm 2002, phương pháp chiếu ngẫu nhiên (Random Projection) của B Chiu và cộng sự năm 2003, cùng với giải thuật MK của Mueen và cộng sự năm 2009 Tuy nhiên, các phương pháp này gặp phải một số nhược điểm, như không phù hợp với chuỗi dữ liệu lớn và không thể nhận diện các motif có chiều dài hoặc biên độ khác nhau.
Dựa vào phương pháp nhận diện motif của Gruber và các cộng sự (2006), quá trình bắt đầu bằng việc trích lược các điểm cực trị quan trọng trong chuỗi dữ liệu thời gian để chọn ra ứng viên motif Tiếp theo, các ứng viên này được gom cụm bằng phương pháp phân cấp từ dưới lên hoặc K-Means Để cải tiến độ tương tự giữa các ứng viên motif, chúng tôi áp dụng phép biến hình vị tự nhằm đồng nhất chiều dài của chúng Cuối cùng, sau khi thực hiện biến hình, chúng tôi sẽ tiến hành gom cụm lại các ứng viên motif và sử dụng công thức tính độ tương tự đã cải tiến để loại trừ biên độ của các ứng viên này.
Mục tiêu và giới hạn của đề tài
Mục tiêu chính của nghiên cứu là phát triển phương pháp tìm kiếm motif trên dữ liệu chuỗi thời gian, dựa trên công trình của Gruber và các cộng sự Phương pháp này tập trung vào việc nén chuỗi thời gian thông qua việc xác định các điểm cực trị quan trọng, bao gồm cả cực đại và cực tiểu.
Kết quả sẽ được so sánh với phương pháp nhận diện motif sử dụng phép chiếu ngẫu nhiên và gom cụm phân cấp từ dưới lên, dựa trên hai yếu tố chính: thời gian chạy và độ chính xác của thuật toán.
Chúng tôi đã lựa chọn phương pháp chiếu ngẫu nhiên do tính phổ biến của nó, thường được áp dụng để so sánh hiệu quả với các thuật toán nhận diện motif khác.
Tóm lược những kết quả thu được
Trong quá trình thực hiện và thử nghiệm luận văn, chúng tôi nhận thấy rằng phương pháp nhận diện motif dựa vào các điểm cực trị, kết hợp với giải thuật gom cụm phân cấp từ dưới lên hoặc K-Means, mang lại nhiều ưu điểm hơn so với phương pháp chiếu ngẫu nhiên.
Thời gian đáp ứng rất nhanh
Thích nghi được chuỗi dữ liệu lớn (lên đến hàng trăm ngàn)
Có thể nhận thấy được các thể hiện motif không cùng chiều dài và có biên độ dao động khác nhau.
Cấu trúc luận văn
Chương II chúng tôi sẽ giới thiệu qua các công trình liên quan đến luận văn bao gồm giới thiệu về các phương pháp về độ đo tương tự giữa hai chuỗi thời gian, các phương pháp về thu giảm số chiều trên chuỗi thời gian ban đầu, cách tiếp cận về các phương pháp rời rạc hóa dữ liệu Đồng thời, chúng tôi cũng giới thiệu lý thuyết về nhận diện motif trên dữ liệu chuỗi thời gian, phương pháp chiếu ngẫu nhiên và giải thuật MK [4]
Chương III chúng tôi sẽ tập trung vào cơ sở lý thuyết và phương pháp giải quyết vấn đề của luận văn bao gồm định nghĩa các điểm cực trị quan trọng, giải thuật gom cụm phân cấp từ dưới lên (HAC) do Gruber và các cộng sự giới thiệu năm 2006[1]
Chương IV chúng tôi giới thiệu một phương thức mới trong việc tính độ tương tự của hai chuỗi dữ liệu con dùng phép biến hình vị tự và loại trừ biên độ dao động Cuối cùng, chúng tôi tiến hành thực nghiệm hệ thống nhận diện motif dựa vào phương pháp chiếu ngẫu nhiên và các điểm cực trị quan trọng kết hợp với HAC hay K-Means So sánh kết quả thu được bao gồm thời gian chạy, độ chính xác và khả năng đáp ứng với chuỗi dữ liệu lớn giữa các phương pháp trên
Chương V là một số kết luận sau khi thực hiện đề tài.
TỔNG THUẬT CÁC CÔNG TRÌNH LIÊN QUAN
Độ đo tương tự
Trong các bài toán chuỗi thời gian, bài toán tìm độ tương tự giữa hai đối tượng O1 và O2 là rất quan trọng Nếu khoảng cách giữa hai đối tượng này bằng 0, chúng được coi là giống nhau; nếu khoảng cách nhỏ hơn một giá trị r cho trước, chúng được xem là tương tự Định nghĩa khoảng cách D(X, Y) giữa hai đối tượng X và Y có các tính chất sau: a) D(X,Y)=0 khi và chỉ khi X=Y; b) D(X,Y)=D(Y,X); c) D(X,Y)≥0 với mọi X,Y; d) D(X,Y) a iMax then iMax = i i = i + 1 output (a iMax ; iMax) return i
Thuật toán FIND_FIRST_TWO xác định hai điểm cực đại và cực tiểu quan trọng đầu tiên trong chuỗi dữ liệu Hàm FIND_MINIMUM(i) tìm kiếm điểm cực tiểu quan trọng bắt đầu từ vị trí thứ i, trong khi hàm FIND_MAXIMUM(i) tìm kiếm điểm cực đại từ vị trí i.
Phương pháp nhận diện motif dựa vào Điểm Quan Trọng
Gruber và các cộng sự đã áp dụng phương pháp nén chuỗi thời gian dựa trên điểm quan trọng để phát hiện các ứng viên motif Họ sử dụng giải thuật gom cụm phân cấp từ dưới lên để phân loại các ứng viên này Đồng thời, Gruber cũng đã đề xuất công thức tính độ đo tương tự, giúp loại bỏ độ lệch giữa biên độ và tỷ lệ của hai chuỗi con.
Một vấn đề quan trọng trong việc nhận diện motif trong khai phá dữ liệu chuỗi thời gian là xác định độ đo tương tự Thông thường, độ đo Euclid và phương pháp phức tạp như xoắn thời gian động được áp dụng Tuy nhiên, cả hai phương pháp này đều rất nhạy cảm với biên độ của hai chuỗi dữ liệu Trong một số trường hợp, khi hai chuỗi dữ liệu được ánh xạ bởi phép biến hình như phép vị tự, độ đo Euclid và DWT không thể phát hiện được sự tương đồng.
Công thức tính độ đo tương tự dưới đây sẽ xem xét đến phép biến đổi tuyến tính với những hằng số được nguời dùng định nghĩa
Cho hai chuỗi dữ liệu thời gian T(t 1 ,t 2 ,….t N ) và Q(q 1 ,q 2 …q N ) cùng có chiều dài
N Độ đo cực tiểu d min (T,Q) của T và Q được cho bởi : b )(-, ) = min ( ? + c − d ) &
Các giá trị a min, a max và b min, b max được người dùng xác định, với a thường dao động quanh giá trị 1 và b quanh giá trị 0 Khi hai tập hợp T và Q hoàn toàn giống nhau, a sẽ bằng 1 và b bằng 0 Điều này cho thấy công thức không có tính đối xứng, tức là d min (T,Q) không bằng d min (Q,T).
Từ công thức trên, tác giả định nghĩa độ đo tương tự hai chuỗi thời gian T và Q như sau:
Công thức trên phụ thuộc vào chiều dài của T và Q Chuẩn hóa công thức trên ta có công thức sau:
< + gh (-, ) (3.3) Để ý rằng +)efb gh không thỏa mãn bất đẳng thức tam giác
Khi làm việc với hai chuỗi dữ liệu T và Q có chiều dài khác nhau, cần phải điều chỉnh để chúng có cùng chiều dài Cụ thể, với T = (T1 TN) và Q = (Q1 … QM) trong đó M>N, chuỗi Q sẽ được lấy mẫu lại bằng phương pháp nội suy spline để đồng nhất chiều dài với T Độ đo tương tự giữa T và Q sẽ được tính toán theo công thức đã được xác định.
+fij gh(-, ) = +)efb gh (-, Rk X[k ) (3.4)
Trong luận văn này, chúng tôi đã dùng phương pháp nội suy spline bậc một để lấy mẫu lại chuỗi Q Giải thuật lấy mẫu lại như sau:
Trong khi chiều dài Q vẫn còn lớn hơn T thì làm các bước sau:
Giải thuật lấy mẫu lại ứng viên Motif T sử dụng nội suy spline bậc I, với ý tưởng chính là lặp lại việc lấy giá trị trung điểm của Q cho đến khi chiều dài của nó bằng với chuỗi T Sau mỗi lần lặp, chiều dài của Q sẽ giảm đi 1.
3.2.2 Tìm ứng viên Motif Đầu tiên, phương pháp này sẽ trích lược các điểm cực trị quan trọng của chuỗi thời gian T, tạm gọi là EP(T) Motif ứng viên MCi(T) với i=1,….l-2 là những chuỗi con của T nằm giữa hai điểm cực trị ep i và ep i+2 Tham số MAX_MOTIF_LENGTH do người dùng định nghĩa Khi chiều dài của ứng viên motif lớn hơn tham số này, motif sẽ được lấy mẫu lại nhờ phương pháp nội suy Kết quả của thuật toán là một chuỗi các ứng viên motif
MCS(T)=(MC 1 (T),MC 2 (T)….MC l-2 (T)) của một chuỗi thời gian đơn biến T=(t 1 , t N ) với MC i (T)=(t epi ,… t epi+2 ), i=1,… l-2
5 for i = 1 to (length (EP)−2) do
7 | if length (motifCandidate)> maxLength then
3.2.3 Giải thuật gom cụm phân cấp theo hướng từ dưới lên
Sau khi trích lược các ứng viên motif, ta thu được tập MCS = {MCS(T1), …, MCS(Tk)} Bước tiếp theo là phân loại các ứng viên motif, trong đó những ứng viên tương tự sẽ được gộp lại thành một motif duy nhất thông qua giải thuật gom cụm phân cấp từ dưới lên.
Phương pháp gom cụm phân cấp từ trên xuống trái ngược với phương pháp từ dưới lên Bắt đầu với tất cả các đối tượng dữ liệu nằm trong một cụm lớn, phương pháp này tiến hành tách cụm thành các cụm nhỏ hơn Quá trình này tiếp tục cho đến khi các đối tượng dữ liệu được phân chia thành những cụm riêng lẻ hoặc đạt được điều kiện dừng như số lượng cụm cần gom.
Hình 3.3 mô tả cả hai giải thuật gom cụm phân cấp: từ dưới lên (đi từ trái qua phải) và từ trên xuống (đi từ phải qua trái)
Hình 3-3: Giải thuật gom cụm phân cấp từ dưới lên và trên xuống HAC
Sau khi giải thuật gom cụm thực hiện xong, số phần tử trong cụm đông nhất chính là các thể hiện (instance) của motif.
Giải thuật gom cụm K-Means
Chúng ta cũng có thể gom cụm ứng viên Motif bằng giải thuật Kmean như sau:
Thuật toán K-Means gom cụm các chuỗi thời gian
1 Chọn một giá trị k, với k là số cụm cần gom cụm các chuỗi thời gian
2 Tạo ngẫu nhiên k trung tâm cụm bằng cách chọn k giá trị trong dữ liệu đại diện trong tập các chuỗi thời gian
3 Áp dụng hàm tính toán trên N đối tượng chuỗi thời gian trong tập dữ liệu để đưa chúng vào cụm gần nhất
4 Nếu N đối tượng chuỗi thời gian trong vòng lặp sau cùng không làm thay đổi trung tâm cụm, dừng thuật toán, ngược lại, quay lại bước 3
Thuật toán K-Means gom cụm chuỗi thời gian
HIỆN THỰC VÀ THỬ NGHIỆM
Cải tiến giải thuật bằng phương pháp biến hình vị tự trên các motif ứng viên và công thức tính độ tương tự loại trừ độ lệch biên độ
tự loại trừ độ lệch biên độ
Để tính độ tương tự giữa hai ứng viên Motif, tác giả áp dụng phương pháp nội suy spline nhằm đồng nhất chiều dài của hai motif, với ứng viên có chiều dài lớn hơn Tuy nhiên, việc sử dụng công thức 3.4 để tính độ tương tự có thể làm giảm tốc độ chương trình do độ phức tạp cao Phương pháp nội suy spline giúp giảm số chiều với bậc I bằng cách lặp lại việc lấy trung điểm của hai điểm liên tiếp cho đến khi đạt được chiều dài mong muốn, mang lại ưu điểm là dễ thực hiện Dù vậy, nhược điểm lớn nhất là nếu chiều dài sau khi lấy mẫu quá lớn so với chiều dài ban đầu, hình dạng của mẫu sẽ thay đổi đáng kể, như được minh họa trong Hình 4.1, 4.2 và 4.3.
Hình 4-1: Chuỗi dữ liệu ban đầu có chiều dài 470 điểm
Việc lấy mẫu lại chuỗi dữ liệu dài 470 điểm bằng nội suy spline bậc I đã dẫn đến sự thay đổi đáng kể về hình dạng so với chuỗi dữ liệu gốc, điều này cho thấy nhược điểm của phương pháp này.
Hình 4.2 và 4.3 cho chúng ta thấy sự thay đổi hình dạng đáng kể của phương pháp nội suy spline so với hình dạng ban đầu
Chúng tôi sẽ giới thiệu một phương pháp lấy mẫu mới sử dụng phép biến hình vị tự, đảm bảo rằng hình dạng của chuỗi dữ liệu ban đầu được duy trì sau khi thực hiện lấy mẫu.
Hình 4-2: Chuỗi dữ liệu sau khi lấy mẫu có chiều dài 400 dùng phương pháp nội suy spline bậc I
Hình 4-3: Chuỗi dữ liệu sau khi lấy mẫu có chiều dài 300 dùng phương pháp nội suy spline bậc I
4.1.1 Khái niệm về phép biến hình vị tự :
Phép vị tự (Homothetic Transformation) là một phép biến hình trong không gian affine
Cho một điểm O và một số k khác 0, phép biến đổi điểm M thành M’ sao cho lm′oooooooop = lmoooooop được gọi là phép vị tự tâm O với tỷ số k Hình 4.4 minh họa phép vị tự tâm O với tỷ số k=1/2, trong đó tam giác MNP sẽ trở thành một tam giác mới.
Phép vị tự tâm O với hệ số vị tự k = 1/2 có những đặc điểm quan trọng: Ảnh của 3 điểm thẳng sẽ tạo thành 3 điểm thẳng hàng, ảnh của hình tròn sẽ là hình tròn mới với bán kính R’ = k.R, và ảnh của đoạn thẳng AB sẽ trở thành đoạn thẳng A’B’ = k.AB.
Nói một cách khác, phép vị tự không bảo toàn về ‘kích thước’ nhưng lại bảo toàn về ‘hình dạng’ của đường cong ban đầu
Dựa vào đặc điểm trên, chúng tôi đã ứng dụng phép vị tự để lấy mẫu lại các ứng viên motif
4.1.2 Lấy mẫu các ứng viên motif bằng phép vị tự
Trong bài viết này, chúng tôi đã tiến hành phép biến hình vị tự cho tất cả các ứng viên motif Sau khi thực hiện biến hình, mỗi ứng viên motif được biểu diễn bằng một chuỗi dữ liệu tương ứng Các chuỗi dữ liệu này có chiều dài đồng nhất, được xác định bởi người dùng.
Việc gom cụm các motif sẽ được thực hiện trên các chuỗi dữ liệu đại diện này
Khi chọn tâm vị tự cho ứng viên motif, cần lưu ý rằng các ứng viên này bắt đầu và kết thúc tại các điểm cực đại hoặc cực tiểu Điều này giúp xác định hình chữ nhật bao quanh ứng viên motif một cách dễ dàng Tâm của phép vị tự sẽ tương ứng với tâm của hình chữ nhật này, trong khi hệ số vị tự được tính bằng tỷ số giữa chiều dài mong muốn và chiều dài thực của ứng viên motif.
Giải thuật tìm các motif đại diện bằng phép biến hình của ứng viên motif có chiều dài N: T={Y 1 … Y n } thành T’ có chiều dài N’
2 Tìm kiếm tâm I của phép biến hình vị tự: X_Center= N/2, Y_Center=(Y_Max+Y_min)/2
3 Thực hiện phép biến hình vị tự với tâm I, hệ số vị tự k=N’/N
Hình 4-5: Chuỗi dữ liệu sau khi lấy mẫu có chiều dài 150 điểm dùng phương pháp vị tự
Hình 4-6: Chuỗi dữ liệu sau khi lấy mẫu có chiều dài 2000 điểm dùng phương pháp vị tự
Từ các hình 4.1, 4.5 và 4.6 chúng ta thấy rằng phép biến đổi vị tự cho kết quả rất khả quan Hình dạng của chuỗi dữ liệu không bị biến dạng
Việc áp dụng phép biến hình giúp loại bỏ sự khác biệt về tỷ lệ giữa hai ứng viên Motif Tuy nhiên, phép vị tự không thể xác định hai motif giống nhau nếu chúng có biên độ khác nhau.
Cho hai chuỗi dữ liệu thời gian T’: {T’ 1 ,T’ 2 … T’ N’ } và Q’: {Q’ 1 ,Q’ 2 ,… Q’ N’ } có cùng chiều dài N’ Thông thường độ tương tự T’ và Q’ sẽ được tính bằng công thức Euclid như sau:
Khi hai chuỗi T và Q có hình dạng giống nhau nhưng bị lệch biên độ, công thức (3.5) sẽ không cho kết quả như mong đợi Để khắc phục vấn đề này, chúng tôi đề xuất một thông số nhằm triệt tiêu độ lệch b.
Ta dễ dàng xác định được giá trị của b như sau: c = 1
Phần tiếp theo chúng tôi sẽ giới thiệu mô hình hiện thực các phương pháp nhận diện motif được thực hiện trong luận văn này.
Mô hình hiện thực các phương pháp
Trong phần này chúng tôi đưa ra các mô hình nhận diện motif như sau:
Dùng phương pháp chiếu ngẫu nhiên
Dùng phương pháp gom cụm phân cấp từ dưới lên với nội suy spline để lấy mẫu các ứng viên motif
Dùng phương pháp phân cụm từ dưới lên hoặc K-Means kết hợp với phép biến hình vị tự và công thức tính độ tương tự cải tiến (3.5’)
4.2.1 Mô hình nhận diện Motif dùng phép chiếu ngẫu nhiên
Trong mô hình này, dữ liệu ban đầu được giảm số chiều thông qua phương pháp PAA Sau khi giảm, chuỗi dữ liệu sẽ được rời rạc hóa bằng phương pháp SAX Cuối cùng, thuật toán chiếu ngẫu nhiên sẽ được áp dụng để nhận diện các motif.
Các thông số của giải thuật bao gồm:
Hệ số thu giảm số chiều w_PAA
Số lượng các kí tự rời rạc hóa trong a trong giải thuật SAX
Số vòng lặp của phép chiếu i, kích thước cửa sổ trượt w và số lỗi d trong phép chiếu ngẫu nhiên
4.2.2 Mô hình giải thuật phân cấp từ dưới lên kết hợp với phương pháp tính độ tương tự dùng nội suy spline
Hình 4-8: Mô hình EP_C\HAC\SI
Mô hình nhận diện motif được mô tả trong Hình 4.8 dựa trên điểm cực trị quan trọng và nội suy spline Phương pháp này bắt đầu bằng việc xác định các điểm cực trị quan trọng, sau đó đưa ra các ứng viên motif dựa trên những điểm này Cuối cùng, mô hình sử dụng thuật toán HAC để gom cụm các ứng viên motif, đặc biệt trong trường hợp hai ứng viên có độ dài khác nhau.
Các thông số của phương pháp này bao gồm:
Hệ số nén R sử dụng để tìm các điểm cực trị quan trọng
Chiều dài cực tiểu l_min của các ứng viên Motif
Hệ số r là tổng số các cụm trên tổng số các điểm cực trị (0