Luận văn thạc sĩ: Nhận dạng motif trên dữ liệu chuỗi thời gian hỗ trợ gom cụm dữ liệu

Luận văn thạc sĩ phân tích máy tính ứng dụng nhận dạng motif trên dữ liệu chuỗi thời gian vào việc hỗ trợ gom cụm dữ liệu, đánh giá thực trạng, chỉ ra hạn chế, đề xuất giải pháp

• Tác giả: Lê Phú
• Người hướng dẫn: PGS TS. 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: Ứng Dụng Nhận Dạng Motif Trên Dữ Liệu Chuỗi Thời Gian Và Vào Việc Hỗ Trợ Gom Cụm Dữ Liệu Chuỗi Thời Gian
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2011
• Địa điểm: Thành phố Hồ Chí Minh

Tóm tắt

I. Nhận dạng motif trong chuỗi thời gian

Nhận dạng motif trong chuỗi thời gian là một quá trình quan trọng trong việc phân tích và khai thác dữ liệu. Motif được định nghĩa là các mẫu lặp lại trong chuỗi thời gian, giúp nhận diện các đặc trưng quan trọng của dữ liệu. Việc nhận dạng motif không chỉ giúp giảm kích thước dữ liệu mà còn tăng cường khả năng phân tích. Các phương pháp nhận dạng motif thường sử dụng các thuật toán như Brute-Force, Dynamic Programming, và các kỹ thuật tối ưu hóa khác. Kết quả của quá trình này là các motif đại diện, từ đó có thể tiến hành các bước tiếp theo trong việc gom cụm dữ liệu. Việc nhận dạng motif có thể được áp dụng trong nhiều lĩnh vực như tài chính, y tế, và khoa học môi trường.

1.1. Phân tích chuỗi thời gian

Phân tích chuỗi thời gian là một lĩnh vực nghiên cứu quan trọng trong khai thác dữ liệu. Dữ liệu chuỗi thời gian thường rất lớn và phức tạp, bao gồm nhiều yếu tố như độ dài, tần suất và độ chính xác. Việc phân tích chuỗi thời gian giúp xác định các xu hướng, mô hình và các yếu tố ảnh hưởng đến dữ liệu. Các phương pháp phân tích thường được sử dụng bao gồm phân tích thống kê, mô hình hóa và khai thác dữ liệu. Đặc biệt, việc phân tích chuỗi thời gian có thể giúp phát hiện các motif và xu hướng lặp lại, từ đó hỗ trợ cho việc ra quyết định trong các lĩnh vực như tài chính và sản xuất.

II. Gom cụm dữ liệu hiệu quả

Gom cụm dữ liệu là một kỹ thuật quan trọng trong khai thác dữ liệu, giúp nhóm các đối tượng có đặc điểm tương đồng lại với nhau. Kỹ thuật này thường được áp dụng trong các lĩnh vực như phân tích thị trường, nhận diện mẫu và phân tích hành vi người dùng. Một trong những thuật toán phổ biến nhất cho việc gom cụm là K-Means. Tuy nhiên, K-Means có một số nhược điểm như dễ rơi vào tối ưu cục bộ và phụ thuộc vào việc chọn ngẫu nhiên các trung tâm cụm ban đầu. Để khắc phục những nhược điểm này, việc sử dụng các motif đại diện trong quá trình gom cụm có thể giúp cải thiện hiệu suất và độ chính xác của thuật toán. Kết quả thực nghiệm cho thấy rằng việc áp dụng nhận dạng motif vào gom cụm dữ liệu chuỗi thời gian giúp giảm thời gian tính toán và tăng cường độ chính xác.

2.1. Kỹ thuật gom cụm

Kỹ thuật gom cụm dữ liệu sử dụng nhiều phương pháp khác nhau để phân nhóm các đối tượng. Trong đó, K-Means là một trong những thuật toán phổ biến nhất. K-Means hoạt động bằng cách chọn ngẫu nhiên k trung tâm cụm và phân loại các đối tượng dựa trên khoảng cách đến các trung tâm này. Tuy nhiên, K-Means có thể gặp khó khăn khi dữ liệu có kích thước lớn hoặc không đồng nhất. Việc áp dụng nhận dạng motif vào quy trình gom cụm giúp tạo ra các trung tâm cụm ban đầu có điều khiển, từ đó cải thiện hiệu suất và độ chính xác của quá trình gom cụm. Kết quả cho thấy rằng việc sử dụng motif đại diện giúp giảm số vòng lặp và thời gian tính toán, đồng thời nâng cao chất lượng gom cụm.

III. Ứng dụng thực tiễn

Việc ứng dụng nhận dạng motif trong gom cụm dữ liệu chuỗi thời gian có nhiều giá trị thực tiễn. Trong lĩnh vực tài chính, việc phân tích dữ liệu chứng khoán có thể giúp phát hiện các xu hướng và mô hình giao dịch. Trong y tế, nhận dạng motif có thể hỗ trợ trong việc phân tích dữ liệu điện tâm đồ, giúp phát hiện các bất thường trong nhịp tim. Ngoài ra, trong khoa học môi trường, việc phân tích dữ liệu khí hậu có thể giúp nhận diện các mẫu thời tiết lặp lại, từ đó hỗ trợ cho việc dự báo thời tiết. Các ứng dụng này không chỉ giúp cải thiện hiệu suất phân tích mà còn cung cấp thông tin quý giá cho các quyết định chiến lược.

3.1. Tính khả thi và hiệu quả

Tính khả thi và hiệu quả của việc ứng dụng nhận dạng motif vào gom cụm dữ liệu chuỗi thời gian đã được chứng minh qua nhiều nghiên cứu thực nghiệm. Các kết quả cho thấy rằng việc sử dụng motif đại diện giúp giảm thiểu thời gian tính toán và tăng cường độ chính xác của các thuật toán gom cụm. Hơn nữa, việc áp dụng các kỹ thuật này trong các lĩnh vực khác nhau đã mở ra nhiều cơ hội mới cho việc khai thác dữ liệu. Các nhà nghiên cứu và chuyên gia trong lĩnh vực này có thể tận dụng những lợi ích này để phát triển các ứng dụng mới, từ đó nâng cao hiệu quả công việc và chất lượng dịch vụ.

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

Đặt vấn đề Bài toán gom cụm dữ liệu (clustering) là một trong những công tác khai phá 2 Ứng dụng nhận dạng motif vào việc gom cụm dữ liệu chuỗi thời gian dữ liệu chuỗi thời gian rất phổ biến hiện nay. Ý tưởng của phương pháp này là sắp xếp các giá trị của dữ liệu có liên quan với nhau thuộc về một nhóm cụ thể mang đặc trưng chung của nhóm. Một trong những kỹ thuật gom cụm dữ liệu phổ biến hiện này là dùng giải thuật K-Means. Ý tưởng của thuật toán K-Means là cho trước một số nguyên k với k là số cụm cần gom.

Đầu tiên, ta chọn ngẫu nhiên k giá trị trong không gian dữ liệu làm trung tâm cụm ban đầu, sau đó ta duyệt qua tất cả các đối tượng của tập dữ liệu, dựa vào hàm tính khoảng cách để đưa giá trị dữ liệu tương ứng về cụm gần nó nhất. Sau khi duyệt qua tập dữ liệu này, ta tính lại trung tâm cụm, quá trình này cứ tiếp diễn cho đến khi trung tâm cụm không thay đổi theo một tiêu chuẩn đánh giá cụ thể. Khi đó giải thuật K-Means sẽ dừng. Trong một số ứng dụng thực tế có nhu cầu gom cụm (clustering) để đưa ra đánh giá dữ liệu.

Ví dụ gom các loại dữ liệu chứng khoán Việt nam mà có độ tương tự nhau, tìm những con sông trong một vùng có mực nước lên xuống giống nhau… Bằng phương pháp phổ biến trên, ta sẽ có được các cụm dữ liệu được gom tương ứng. Tuy nhiên, khi áp dụng gom cụm trên chuỗi thời gian gặp phải hai nhược điểm sau: o Dữ liệu chuỗi thời gian có đặc điểm là rất lớn nên việc gom cụm dữ liệu bằng phương pháp trên sẽ tốn chi phí thời gian và tài nguyên. o Việc gom cụm dữ liệu chuỗi thời gian là chọn ngẫu nhiên các trung tâm cụm ban đầu dẫn đến quá trình thực hiện gom cụm xảy ra không được hiệu quả về mặt thời gian vì có thể làm tăng quá trình tính toán trung tâm cụm.  Hướng giải quyết Để khắc phục hai nhược điểm khi gom cụm chuỗi thời gian như trên, chúng ta có thể vận dụng nhận dạng môtíp trên dữ liệu chuỗi thời gian vào việc hỗ trợ gọm cụm dữ liệu chuỗi thời gian, bao gồm các bước sau: 3 Ứng dụng nhận dạng motif vào việc gom cụm dữ liệu chuỗi thời gian  Nhận dạng motif (môtíp): Từ các các chuỗi thời gian riêng biệt ta nhận dạng các môtíp đặc trựng cho từng dữ liệu chuỗi thời gian này.

 Gom cụm trên motif (môtíp): Thực hiện gom cụm trên các môtíp đại diện tương ứng với các chuỗi thời gian này bằng giải thuật K-Means.  Dùng kết quả gom cụm trên môtíp để xác định các trung tâm cụm khởi đầu cho tập chuỗi thời gian ban đầu và sau đó áp dụng giải thuật K-Means trên các trung tâm cụm này.3 Mục tiêu và giới hạn của đề tài Mục tiêu nghiên cứu đề tài trên cơ sở dữ liệu chuỗi thời gian tập trung vào hai vấn đề chính:  Nghiên cứu các giải thuật nhận dạng môtíp trên dữ liệu chuỗi thời gian Trong cơ sở dữ liệu chuỗi thời gian, dữ liệu thường rất lớn. Vì vậy, việc nhận dạng các môtíp đặc trưng cho dữ liệu chuỗi thời gian và gom cụm trên các môtíp đại diện này sẽ giúp cho quá trình gom cụm xảy ra nhanh hơn. Trong phần này chúng ta sẽ tập trung vào giải thuật thuật K-Means để gom cụm trên các môtíp  Ứng dụng việc nhận dạng môtíp vào hỗ trợ việc gom cụm dữ liệu chuỗi thời gian để làm cho giải thuật gom cụm trên dữ liệu chuỗi thời gian ban đầu trở nên hữu hiệu hơn.

Sau khi nhận dạng trung tậm cụm cho các môtíp đại diện chuỗi thời gian, ta xác định trung tâm cụm khởi đầu cho chuỗi thời gian ban đầu tương ứng với các môtíp trung tâm. Sau đó chúng ta áp dụng giải thuật K-Means để gom cụm trên tập dữ liệu chuỗi thời gian này. Quá trình gom cụm dựa vào nhận diện môtíp đã giúp cho quá trình gom cụm dữ liệu được thực hiện cho ra kết quả nhanh hơn và chính xác hơn quá trình gom cụm trên tập dữ liệu ban đầu sử dụng giải thuật K-Means. Tuy nhiên quá trình 4 Ứng dụng nhận dạng motif vào việc gom cụm dữ liệu chuỗi thời gian nghiên cứu của luận văn này cũng gặp phải một số giới hạn như sau:  Việc nhận diện môtíp là tốn kém thời gian và cần phải xác định đặc trưng của dữ liệu cụ thể để xác định thông số nhận diện môtíp bao gồm chiều dài môtíp và bán kính nhận diện cũng như khai thác được đặc trưng phân hoạch của dữ liệu ban đầu.

 Do giới hạn về thời gian nghiên cứu cho nên quá trình thực nghiệm chỉ đo đạc trên dữ liệu Heterogeneous và chứng khoán tham khảo được lấy từ nguồn The VCR Time Series Data Mining Archive [24].4 Tóm lược những kết quả đạt đượ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 thu được các kết quả như sau:  Quá trình gom cụm trên tập dữ liệu chuỗi thời gian dựa vào kết quả gom cụm trên các môtíp đại diện có thời gian thực hiện nhanh hơn gom cụm trực tiếp trên tập dữ liệu ban đầu sử dụng giải thuật K-Means và thời gian chạy này càng nhanh hơn khi thông tin nhận diện môtíp đại diện phù hợp với đặc trưng của tập dữ liệu chuỗi thời gian, số cụm cần gom phù hợp với sự phân hoạch dữ liệu.  Quá trình gom cụm trên tập dữ liệu chuỗi thời gian dựa vào kết quả gom cụm trên các môtíp đại diện có độ ổn định tốt hơn gom cụm trực tiếp trên tập dữ liệu ban đầu sử dụng giải thuật K-Means.  Độ chính xác quá trình gom cụm trên tập dữ liệu chuỗi thời gian dựa vào kết quả gom cụm trên các môtíp đại diện tốt hơn gom cụm trực tiếp trên cả tập dữ liệu chuỗi thời gian ban đầu và trên tập dữ liệu chuỗi thời gian sau khi thu giảm số chiều sử dụng giải thuật K-Means.  Độ chính xác quá trình gom cụm trên tập dữ liệu chuỗi thời gian ban đầu và trên tập dữ liệu chuỗi thời gian sau khi thu giảm số chiều dựa vào kết quả gom cụm trên các môtíp là tương đương như nhau.

5 Ứng dụng nhận dạng motif vào việc gom cụm dữ liệu chuỗi thời gian  Số vòng lặp gom cụm quá trình gom cụm trên tập dữ liệu chuỗi thời gian dựa vào kết quả gom cụm trên các môtíp là ổn định hơn số vòng lặp gom cụm trực tiếp trên tập dữ liệu ban đầu sử dụng giải thuật K-Means.5 Cấu trúc của luận văn Dựa theo hướng nghiên cứu chính của luận văn, chúng tôi tổ chức luận văn bao gồm những phần chính sau:  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. Đặc biệt chúng tôi tập trung vào các phương pháp gom cụm dữ liệu nói chung và cụ thể là gom cụm trên tập dữ liệu chuỗi thời gian. Ngoài ra chúng tôi cũng tập trung các công trình nhận diện các mẫu lặp (môtíp) chuỗi dữ liệu thời gian.  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 mô hình kiến trúc hệ thống gom cụm dữ liệu chuỗi thời gian thông qua các môtíp đại diện.

Trong chương này chúng tôi cũng phân tích, đi sâu và tối ưu giải thuật nhận diện môtíp Bruce-Force được J.Lin và các cộng sự đề xuất vào năm 2002 [1].  Chương IV chúng tôi thực hiện hiện thực hệ thống gom cụm tập dữ liệu chuỗi thời gian dựa vào kết quả gom cụm trên các môtíp đại diện và so sánh thời gian chạy, số vòng lặp gom cụm cũng như độ ổn định hệ thống so với quá trình gom cụm trên tập dữ liệu chuỗi thời gian ban đầu không dựa vào nhận diện môtíp. Trong chương này cũng thực nghiệm và đo đạc độ chính xác kết quả gom cụm của việc gom cụm trên tập dữ liệu chuỗi thời gian dựa vào kết quả gom cụm trên các môtíp đại diện.  Chương V là một số kết luận sau khi thực hiện đề tài.

6 Ứng dụng nhận dạng motif vào việc gom cụm dữ liệu chuỗi thời gian CHƯƠNG II: TỔNG QUAN 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 dạng mẫu lặp (môtíp) và gom cụm dữ liệu chuỗi thời gian.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. 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 7 Ứng dụng nhận dạng motif vào việc gom cụm dữ liệu chuỗi thời gian thức Minkowski như sau: n Sim( X , Y )  p  ( X i  Yi ) p (2.1) i 1 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  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 [7], DWT [4], PAA [10] [23]… 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.  Không thích hợp với dữ liệu có biên độ giao động khác nhau.

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 bằng 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) [6].