Luận văn thạc sĩ về gom cụm chuỗi thời gian trong khoa học máy tính theo xu hướng

Chuyên đề gom cụm chuỗi thời gian trong khoa học máy tính theo xu hướng, tiếp cận liên ngành, kết quả nghiên cứu có giá trị ứng dụng cao trong khoa

• Tác giả: Thiều Xuân Khánh
• Người hướng dẫn: PGS TS. Dương Tuấn Anh
• Trường học: Đại học Quốc gia TP.HCM
• Chuyên ngành: Khoa học máy tính
• Đề tài: Gom Cụm Chuỗi Thời Gian Dựa Theo Xu Hướ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. Hồ Chí Minh

Tóm tắt

I. Giới thiệu về gom cụm dữ liệu chuỗi thời gian

Gom cụm dữ liệu chuỗi thời gian là một kỹ thuật quan trọng trong lĩnh vực khoa học máy tính, đặc biệt trong khai phá dữ liệu. Mục tiêu chính của việc gom cụm này là tìm ra các phân hoạch và đặc trưng của các chuỗi thời gian để thực hiện các đánh giá chính xác hơn. Gom cụm dữ liệu có thể được phân loại thành ba loại: gom cụm trực tiếp trên dữ liệu thô, gom cụm dựa trên các đặc trưng được rút trích từ dữ liệu thô, và gom cụm dựa trên các mô hình được xây dựng từ dữ liệu thô. Các phương pháp này thường gặp khó khăn trong việc duy trì chất lượng cao khi xử lý dữ liệu lớn. Do đó, việc áp dụng thuật toán phân cụm như k-means trong việc gom cụm chuỗi thời gian trở nên cần thiết hơn bao giờ hết.

1.1. Đặc điểm của dữ liệu chuỗi thời gian

Dữ liệu chuỗi thời gian có đặc điểm lớn về khối lượng và thường được ghi lại theo các khoảng thời gian cố định. Điều này dẫn đến việc lưu trữ và xử lý dữ liệu trở nên phức tạp và tốn kém. Các vấn đề như dữ liệu không đồng nhất và phụ thuộc vào yếu tố chủ quan của người đo cũng gây khó khăn trong việc phân tích. Việc sử dụng các công cụ học máy để phân tích dữ liệu chuỗi thời gian là một xu hướng đang được nghiên cứu và ứng dụng rộng rãi.

II. Phương pháp gom cụm chuỗi thời gian

Phương pháp gom cụm chuỗi thời gian thường gặp phải hai nhược điểm chính: chi phí thời gian và tài nguyên khi xử lý dữ liệu lớn, và việc chọn ngẫu nhiên các trung tâm cụm ban đầu có thể dẫn đến hiệu suất không tốt. Để khắc phục những vấn đề này, việc sử dụng các dãy xu hướng đại diện cho dữ liệu chuỗi thời gian là một giải pháp khả thi. Các dãy xu hướng này giúp giảm thiểu kích thước dữ liệu và cải thiện hiệu suất của thuật toán k-means. Nghiên cứu cho thấy rằng việc chuyển đổi dữ liệu chuỗi thời gian thành các dãy xu hướng có thể làm tăng tốc độ và độ chính xác của quá trình gom cụm.

2.1. Kỹ thuật bitmap trong gom cụm

Kỹ thuật bitmap là một phương pháp hữu ích trong việc gom cụm dữ liệu chuỗi thời gian. Kỹ thuật này cho phép chuyển đổi các chỉ số xu hướng thành các biểu diễn nhị phân, từ đó giúp giảm thiểu kích thước dữ liệu và tối ưu hóa quá trình xử lý. Việc sử dụng bitmap indexing giúp cải thiện đáng kể hiệu suất của thuật toán gom cụm, đặc biệt khi làm việc với các tập dữ liệu lớn. Các nghiên cứu trước đây đã chỉ ra rằng việc áp dụng kỹ thuật bitmap có thể giúp nâng cao chất lượng của các cụm dữ liệu được hình thành.

III. Kết quả thực nghiệm và đánh giá

Kết quả thực nghiệm cho thấy rằng việc gom cụm chuỗi thời gian dựa trên xu hướng có số vòng lặp gom cụm ít hơn và tính ổn định cao hơn so với các phương pháp truyền thống. Sử dụng đường trung bình di động số mũ thay vì đường trung bình đơn giản đã cải thiện đáng kể hiệu suất và thời gian chạy của thuật toán. Các kết quả này cho thấy rõ ràng rằng việc áp dụng các dãy xu hướng đại diện không chỉ giúp tăng tốc độ gom cụm mà còn nâng cao chất lượng của các cụm dữ liệu được tạo ra.

3.1. Đánh giá chất lượng gom cụm

Đánh giá chất lượng gom cụm được thực hiện dựa trên nhiều tiêu chí khác nhau như độ chính xác, thời gian thực thi và số lần lặp. Kết quả cho thấy rằng phương pháp gom cụm dựa trên xu hướng có độ chính xác cao hơn và thời gian thực thi ngắn hơn so với các phương pháp gom cụm truyền thống. Điều này chứng minh rằng việc áp dụng các chỉ số xu hướng và kỹ thuật bitmap trong gom cụm chuỗi thời gian là một hướng đi đúng đắn, có tiềm năng ứng dụng rộng rãi trong thực tiễn.

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á 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 3 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 để đư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 nhược điểm đầu tiên trong 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 dùng các dãy xu hướng đại diệ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: 4  Chuyển đổi các chuỗi thời gian thành các dãy xu hướng (trend sequence): Từ các các chuỗi thời gian riêng biệt ta biến đổi thành các dãy xu hướng đặc trưng cho từng dữ liệu chuỗi thời gian này.

 Gom cụm trên các dãy xu hướng này : Thực hiện gom cụm trên các dãy xu hướng đạ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.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 phương pháp chuyển đổi dữ liệu chuỗi thời gian thành dãy xu hướng 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 chuyển đổi thành các dãy xu hướng đặc trưng cho dữ liệu chuỗi thời gian và gom cụm trên các dãy xu hướng đại diện này sẽ giúp cho quá trình gom cụm xảy ra nhanh hơn và có độ tương tự cao hơn. Trong phần này chúng ta sẽ tập trung vào giải thuật k-means để gom cụm trên các dãy xu hướng  Ứng dụng việc dùng các dãy xu hướng đặc trưng 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 hiệu quả hơn. Sau khi chuyển đổi thành các dãy xu hướng đại diện chuỗi thời gian, áp dụng giải thuật k-means để gom cụm trên các dãy xu hướng này.

Sau đó lấy kết quả gom cụm này chuyển thành kết quả gom cụm của tập dữ liệu chuỗi thời gian này. Quá trình gom cụm dựa vào xu hướng đã 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 trong quá trình thực hiện luận văn này cũng gặp phải một số giới hạn như sau: 5  Việc chuyển đổi thành dãy xu hướng là tốn kém thời gian và cần dùng kỹ thuật bitmap các chỉ số xu hướng của dãy xu hướng.  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 hai tập 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 [23].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 dựa trên xu hướng 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à chất lượng gom cụm cao hơn.

 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 dựa trên các dãy xu hướng đạ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 dựa trên các dãy xu hướng đạ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 dãy xu hướng là tương đương như nhau.  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 dãy xu hướng 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 6 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ông trình liên quan đến gom cụm dựa trên xu hướng đại diện các 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 các phương pháp biến đổi chuỗi thời gian thành dãy xu hướng và kỹ thuật bitmap của gom cụm dữ liệu chuỗi thời gian thông qua các dãy xu hướng đại diện. Trong chương này chúng tôi cũng tập trung vào cách tiếp cận bitmap để gom cụm dựa trên xu hướng được Jong P.

Yoon, Yixin Luo và Junghyun Nam đề xuất vào năm 2001 [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 dãy xu hướng đạ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 có thu giảm số chiếu. 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 dãy xu hướng đại diện.  Chương V là một số kết luận sau khi thực hiện đề tài.

7 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, chuyển đổi xu hướng 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ì chúng được xem 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 thức Minkowski như sau: 8 n Sim( X , Y )  p  ( X i  Yi ) i 1 p (2.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 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], DTW [4], PAA [9] [22]… 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.1 minh họa cho trường hợp này)  Không thích hợp với dữ liệu có biên độ giao động khác nhau.2 minh họa cho trường hợp này) 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) [6].  Áp dụng tính độ tương tự có sửa đổi dựa trên khoảng cách Euclid [4] như sau:  (( yi  xi) ( y A  x A)) 2 Sim( X , Y )  (2.2) 9 1 n1 1 n1 Trong đó: x A   xi , y A   yi n i 0 n i 0 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.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 độ giao động khác nhau.