Luận văn thạc sĩ: Nhận diện motif trên dữ liệu chuỗi thời gian qua điểm cực trị quan trọng

Khám phá luận văn thạc sĩ về nhận diện motif trong dữ liệu chuỗi thời gian, ứng dụng điểm cực trị quan trọng trong khoa học máy tính.

• Tác giả: Huỳnh Nguyễn Tín
• Người hướng dẫn: PGS. Dương Tuấn Anh
• Trường học: Đại học Quốc gia Thành phố Hồ Chí Minh
• Chuyên ngành: Khoa học máy tính
• Đề tài: Nhận diện motif trong chuỗi thời gian dựa vào điểm cực trị quan trọng
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2012
• Địa điểm: TP. HCM

Tóm tắt

I. Giới thiệu về nhận diện motif

Nhận diện motif trong chuỗi thời gian là một kỹ thuật quan trọng trong khai phá dữ liệu. Mục tiêu chính là tìm ra các chuỗi con tương tự nhau, từ đó nhận diện các đặc trưng của dữ liệu. Nhận diện motif giúp phân tích và đánh giá các mẫu lặp lại trong dữ liệu, điều này rất hữu ích trong nhiều lĩnh vực như tài chính, y tế và khoa học. Các phương pháp hiện có như Brute-Force và Random Projection thường gặp khó khăn khi xử lý dữ liệu lớn. Do đó, việc phát triển các phương pháp mới là cần thiết để cải thiện hiệu suất và độ chính xác trong việc nhận diện motif.

1.1. Tầm quan trọng của chuỗi thời gian

Chuỗi thời gian là tập hợp các quan sát được ghi lại theo thời gian. Chúng có thể là dữ liệu tài chính, dữ liệu y tế hoặc bất kỳ loại dữ liệu nào có tính chất tuần tự. Chuỗi thời gian thường rất lớn và phức tạp, đòi hỏi các phương pháp phân tích hiệu quả. Việc nhận diện motif trong chuỗi thời gian không chỉ giúp phát hiện các mẫu lặp lại mà còn hỗ trợ trong việc dự đoán và ra quyết định. Các ứng dụng thực tế của nhận diện motif bao gồm phân tích xu hướng thị trường, theo dõi sức khỏe bệnh nhân và tối ưu hóa quy trình sản xuất.

II. Phương pháp nhận diện motif dựa vào điểm cực trị

Phương pháp nhận diện motif dựa vào điểm cực trị quan trọng (Important Extreme Points) là một cách tiếp cận mới nhằm cải thiện độ chính xác và tốc độ của quá trình nhận diện. Bằng cách xác định các điểm cực trị trong chuỗi dữ liệu, các ứng viên motif được chọn ra và gom cụm bằng các thuật toán như K-Means hoặc phân cấp từ dưới lên. Phương pháp này giúp giảm thiểu thời gian xử lý và tăng cường khả năng phát hiện các motif có chiều dài và biên độ khác nhau. Điểm cực trị đóng vai trò quan trọng trong việc xác định các mẫu lặp lại, từ đó nâng cao hiệu quả của quá trình phân tích.

2.1. Cải tiến thuật toán EP_C

Thuật toán EP_C (Extreme Point Clustering) được đề xuất bởi Gruber và các cộng sự vào năm 2006. Thuật toán này tập trung vào việc gom cụm các ứng viên motif dựa trên các điểm cực trị. Việc cải tiến thuật toán này giúp tăng cường khả năng nhận diện các motif mà các phương pháp trước đó không thể phát hiện. Kỹ thuật này không chỉ giúp giảm thiểu độ phức tạp tính toán mà còn cải thiện độ chính xác của kết quả. Phương pháp phân tích này cho phép xử lý các chuỗi dữ liệu lớn một cách hiệu quả, từ đó mở rộng khả năng ứng dụng trong nhiều lĩnh vực khác nhau.

III. Kết quả thực nghiệm và ứng dụng

Kết quả thực nghiệm cho thấy phương pháp nhận diện motif dựa vào điểm cực trị cho thời gian chạy nhanh hơn và độ chính xác cao hơn so với các phương pháp truyền thống như Random Projection. Các thử nghiệm trên dữ liệu ECG, dữ liệu Memory và dữ liệu Power cho thấy khả năng nhận diện các motif không cùng chiều dài và biên độ khác nhau. Điều này chứng tỏ rằng phương pháp này có thể áp dụng rộng rãi trong các lĩnh vực như y tế, tài chính và phân tích dữ liệu lớn. Kết quả thực nghiệm không chỉ khẳng định tính khả thi của phương pháp mà còn mở ra hướng đi mới cho nghiên cứu trong lĩnh vực khai phá dữ liệu chuỗi thời gian.

3.1. Ứng dụng trong thực tiễn

Phương pháp nhận diện motif có thể được ứng dụng trong nhiều lĩnh vực khác nhau. Trong y tế, nó giúp theo dõi và phân tích các mẫu điện tâm đồ, từ đó phát hiện sớm các vấn đề sức khỏe. Trong tài chính, việc nhận diện các mẫu lặp lại trong dữ liệu giá cổ phiếu có thể hỗ trợ các nhà đầu tư đưa ra quyết định chính xác hơn. Ngoài ra, trong lĩnh vực sản xuất, việc phân tích chuỗi thời gian giúp tối ưu hóa quy trình và giảm thiểu lãng phí. Giá trị thực tiễn của phương pháp này không chỉ dừng lại ở việc nhận diện mà còn mở rộng ra việc dự đoán và ra quyết định dựa trên dữ liệu.

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

CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI 1.1 Dữ liệu chuỗi thời gian Chuỗi dữ liệu thời gian hay chuỗi thời gian là sự quan sát các dữ liệu theo thời gian tuần tự. Đối với loại dữ liệu này, cấu trúc dữ liệu có thể là hai hay nhiều chiều trong đó có chiều thời gian, tức là dữ liệu được theo dõi và ghi lại tại một thời điểm nhất định. Tuy nhiên, trong hầu hết các ứng dụng thực tế, dữ liệu được đo các cách khác nhau trong một khoảng thời gian cố định nên để đơn giản hóa quá trình lưu trữ cũng như độ phức tạp của dữ liệu, người ta chỉ lưu lại thứ tự các giá trị dữ liệu theo một trình tự thời gian nhất định có dạng X=<x1, x2, …xn> trong đó xi là dữ liệu được đo ở 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: S=<14.1> 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 các ứng dụng thực tế, có rất nhiều loại dữ liệu chuỗi thời gian như sự theo dõi biến đổi giá của chứng khoán, dữ liệu đo điện tim đồ, dữ liệu theo dõi mực nước sông hay là sự ghi lại việc truy cập các trang web của người dùng.

Thông thường, các loại dữ liệu chuỗi thời gian này là rất lớn, được đo và lưu trữ lại trong một khoảng thời gian dài cho nên việc lưu trữ và khai phá dữ liệu này thường tốn kém chi phí thời gian. Do đó việc sử dụng các công cụ khai phá dữ liệu này được áp dụng trên nền máy tính đã thu hút sự quan tâm, nghiên cứu và ứng dụng trong rất nhiều các lĩnh vực trong những năm gần đây. Nhận diện motif của dữ liệu chuỗi thời gian dựa vào điểm cực trị quan trọng 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.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: Khối lượng dữ liệu: Một trong những đặc trưng của chuỗi thời gian là dữ liệu rất lớn.Ví dụ khi đo đạc dữ liệu điện tâm đồ trong 1 giờ khoảng 1 Gigabyte. Đây là một trong những vấn đề thách thức trong quá trình phân tích, tính toán và xử lý dữ liệu chuỗi thời gian trong việc tạo ra kết quả được chính xác trong thời gian hợp lý.

Phụ thuộc yếu tố chủ quan: Trong thực tế, các kết quả dữ liệu chuỗi thời gian thu được chịu ảnh hưởng yếu tố chủ quan của người đo dữ liệu, điều kiện và các công cụ đo… Dữ liệu không đồng nhất: Quá trình thu thập dữ liệu chuỗi thời gian được đo trên những định dạng khác nhau, số lượng và tần số lấy mẫu không đồng nhất cũng ảnh hưởng đến tính toàn vẹn của dữ liệu. Thêm vào đó quá trình đo đạc không chính xác do nhiễu, thiếu một vài giá trị hay dữ liệu không sạch.2 Nhận diện Motif trong dữ liệu chuỗi thời gian Một trong những vấn đề được quan tâm trong việc khai phái dữ liệu chuỗi thời gian là nhận diện những chuỗi con tương tự xuất hiện thường xuyên (gọi là motif). Các phương pháp được ứng dụng trong bài toán này thường được dùng là Brute- Force được J.Lin và các cộng sự đề xuất năm 2002[3], phương pháp chiếu ngẫu nhiên (Random Projection) được B.Chiu và các cộng sự giới thiệu năm 2003[2], giải thuật MK của Mueen và các cộng sự đưa ra năm 2009[4] .Tuy nhiên khi áp dụng các phương pháp trên thì ta gặp phải các nhược điểm sau: o Không thích hợp khi chuỗi dữ liệu lớn. Huỳnh Nguyễn Tín – 09070469 2 Nhận diện motif của dữ liệu chuỗi thời gian dựa vào điểm cực trị quan trọng o Cả ba phương pháp này không thể nhận ra được các motif có chiều dài hay biên độ khác nhau.

Hướng giải quyết : Dựa vào phương pháp nhận diện motif do Gruber và các cộng sự đưa ra năm 2006[1]: o Trích lược các điểm cực trị quan trọng của chuỗi dữ liệu thời gian, từ đó chọn ra những ứng viên motif. o Gom cụm các ứng viên motif bằng phương pháp phân cấp từ dưới lên (Hierarchical Bottom-Up) hoặc K-Means. o Cải tiến công thức tính độ tương tự hai ứng viên motif bằng phép biến hình vị tự (homothetic transformation) để đồng nhất chiều dài các ứng viên motif. Sau đó chúng tôi sẽ tiến hành gom cụm các ứng viên motif sau phép biến hình này.

o Sử dụng công thức tính độ tương tự cải tiến để loại trừ biên độ (range) của các ứng viên motif.3 Mục tiêu và giới hạn của đề tài Mục tiêu chính của đề tài là nghiên cứu phương pháp tìm kiếm motif trên dữ liệu chuỗi thời gian. Đề tài này dựa trên nghiên cứu của Gruber và các cộng sự. Phương pháp này dựa vào ý tưởng nén những chuỗi thời gian nhờ vào những điểm cực trị quan trọng (Cực đại và Cực tiểu). Kết quả thu được sẽ so sánh với phương pháp nhận diện motif dựa vào phép chiếu ngẫu nhiên và gom cụm phân cấp từ dưới lên dùng nội suy spline về hai phương diện: Thời gian chạy, sự chính xác của giải thuật… Chúng tôi chọn phương pháp chiếu ngẫu nhiên bởi vì phương pháp này được sử dụng rộng rãi và thường được sử dụng để so sánh với các giải thuật nhận diện motif khác.4 Tóm lược những kết quả thu được: Với việc tập trung vào mục đích chính của luận văn trong suốt quá trình thực hiện và thử nghiệm chúng tôi thấy được ưu điểm của 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 hay K-Means so với phương pháp chiếu ngẫu nhiên như sau: 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.5 Cấu trúc luận văn Huỳnh Nguyễn Tín – 09070469 3 Nhận diện motif của dữ liệu chuỗi thời gian dựa vào điểm cực trị quan trọng 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.

Huỳnh Nguyễn Tín – 09070469 4 Nhận diện motif của dữ liệu chuỗi thời gian dựa vào điểm cực trị quan trọng CHƯƠNG 2: TỔNG THUẬT CÁC CÔNG TRÌNH LIÊN QUAN Chương này sẽ giới thiệu tổng quan các công trình liên quan đã được nghiên cứu bao gồm các công trình về độ đo tương tự, phương pháp thu giảm số chiều, phương pháp rời rạc hóa dữ liệu, nhận diện mẫu lặp (motif) dựa trên phương pháp chiếu ngẫu nhiên và giải thuật nhận diện motif MK.1 Độ đo tương tự Trong các hầu hết các bài toán về chuỗi thời gian, bài toán tìm độ tương tự là một trong những bài toán quan trọng nhất. Cho hai đối tượng O1 và O2, khoảng cách giữa hai đối tượng này sẽ bằng 0 thì chúng được xem là giống nhau. Nếu khoảng cách giữa chúng nhỏ hơn một giá trị r cho trước thì khoảng cách giữa chúng là tương tự nhau. Gọi D(X, Y) là khoảng cách giữa hai đối tượng X và Y, ta có các tính chất sau: a) D(X,Y)=0 nếu và chỉ nếu X=Y b) D(X,Y)=D(Y,X) c) D(X,y)≥0 với mọi X,Y d) D(X,Y)<D(X,Z)+ D(Y,Z) Cho hai chuỗi thời gian X và Y có dạng X=<x1, x2…xn> và Y=<y1, y2,…yn>.

Độ tương tự giữa X và Y ký hiệu là Sim(X, Y). Sau đây là một số phương pháp dùng để xác định độ tương tự giữa hai chuỗi thời gian.1 Độ đo Minkowski Độ đo tương tự giữa hai chuỗi thời gian X và Y được xác định bằng công thức Minkowski như sau: ℎℎℎ Với, a) p=1: Độ đo Manhatan b) p=2: Độ đo Euclid c) p=3: Độ đo Max Ưu điểm Tính toán dễ dàng. Huỳnh Nguyễn Tín – 09070469 5 Nhận diện motif của dữ liệu chuỗi thời gian dựa vào điểm cực trị quan trọng Có khả năng mở rộng cho nhiều bài toán khác như gom cụm (clustering) và phân loại (classification) dữ liệu… và phù hợp với các phép biến đổi thu giảm số chiều như: DFT [18], DWT [6], PAA [7][8]… Nhược điểm: Nhạy cảm với nhiễu. Không thích hợp khi dữ liệu có đường cơ bản khác nhau (Hình 2.

Không thích hợp với dữ liệu có biên độ dao động khác nhau (Hình 2. Phương pháp khắc phục: Chuẩn hóa dữ liệu chuỗi thời gian trước khi áp dụng so trùng mẫu trên dữ liệu dựa trên giá trị trung bình và độ lệch chuẩn X’=X-mean(X) hay X’=(X-mean(X))/Var(X) [9]. Áp dụng phương pháp trung bình di chuyển [20] để làm trơn các đường biểu diễn chuỗi thời gian nghĩa là giá trị của chuỗi thời gian tại thời điểm i được tính như sau: = (2.2) 2 +1 Áp dụng độ đo tương tự có sửa đổi dựa trên khoảng cách Euclid như sau: 1 ( , )= ∑ (! − # ) − (!$ − #$ )% (2.3) & Trong đó: #$ = ∑) *( # , !$ = ∑) *( ! ( ( ) ) Huỳnh Nguyễn Tín – 09070469 6 Nhận diện motif của dữ liệu chuỗi thời gian dựa vào điểm cực trị quan trọng Hình 2-1: Minh họa hình dạng dữ liệu chuỗi thời gian có hai đường giống nhau, nhưng đường cơ bản khác nhau. Hình 2-2: Minh họa hình dạng dữ liệu chuỗi thời gian có hai đường giống nhau nhưng biên độ dao động khác nhau.

Huỳnh Nguyễn Tín – 09070469 7 Nhận diện motif của dữ liệu chuỗi thời gian dựa vào điểm cực trị quan trọng 2.