Luận văn thạc sĩ khoa học máy tính gom cụm dữ liệu chuỗi thời gian với độ đo xoắn thời gian động dựa vào một kỹ thuật xấp xỉ

Luận văn thạc sĩ khoa học máy tính nghiên cứu gom cụm dữ liệu chuỗi thời gian sử dụng độ đo xoắn thời gian động và kỹ thuật xấp xỉ hiệu quả.

• Tác giả: Văn Thế Huy
• Người hướng dẫn: PGS. Dương Tuấn Anh
• Trường học: Đại học Bách Khoa, Đại học Quốc gia TP. Hồ Chí Minh
• Chuyên ngành: Khoa học máy tính
• Đề tài: Gom cụm dữ liệu chuỗi thời gian với độ đo xoắn thời gian động dựa vào một kỹ thuật xấp xỉ
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2015
• Địa điểm: TP. Hồ Chí Minh

Tóm tắt

I. Giới thiệu đề tài

Luận Văn Thạc Sĩ này tập trung vào việc gom cụm dữ liệu chuỗi thời gian sử dụng độ đo xoắn thời gian động (DTW) dựa trên một kỹ thuật xấp xỉ. Với sự phát triển của khoa học dữ liệu, việc phân tích và xử lý chuỗi thời gian trở nên quan trọng trong nhiều lĩnh vực như tài chính, y tế, và môi trường. Độ đo DTW được chọn vì khả năng xử lý linh hoạt các chuỗi thời gian không đồng bộ, nhưng độ phức tạp tính toán cao của nó đặt ra thách thức lớn. Đề tài này nhằm giải quyết vấn đề này bằng cách đề xuất các cải tiến trong thuật toán gom cụm và tối ưu hóa dữ liệu.

1.1. Vấn đề nghiên cứu

Gom cụm dữ liệu chuỗi thời gian là một bài toán quan trọng trong phân tích dữ liệu. Tuy nhiên, các phương pháp truyền thống sử dụng độ đo Euclid thường thiếu linh hoạt và không chính xác. Độ đo DTW giải quyết được vấn đề này nhưng lại có độ phức tạp tính toán cao. Đề tài này tập trung vào việc tìm kiếm các kỹ thuật xấp xỉ để giảm thiểu thời gian tính toán mà vẫn đảm bảo chất lượng gom cụm.

1.2. Mục tiêu nghiên cứu

Mục tiêu chính của đề tài là xây dựng một hệ thống gom cụm dữ liệu chuỗi thời gian sử dụng độ đo DTW dựa trên kỹ thuật xấp xỉ. Cụ thể, đề tài tập trung vào việc tìm hiểu các phương pháp tính xấp xỉ DTW, áp dụng thuật toán gom cụm với thời gian thực thi tùy chọn, và đề xuất các cải tiến để tối ưu hóa quá trình gom cụm.

II. Cơ sở lý thuyết

Chương này trình bày các khái niệm cơ bản về chuỗi thời gian, độ đo DTW, và các thuật toán gom cụm liên quan. Độ đo DTW được giới thiệu như một giải pháp thay thế cho độ đo Euclid trong việc đo lường khoảng cách giữa các chuỗi thời gian. Các kỹ thuật như ràng buộc toàn cục và tính chặn dưới cũng được đề cập để giảm thiểu độ phức tạp tính toán của DTW.

2.1. Độ đo khoảng cách chuỗi thời gian

Độ đo DTW cho phép so sánh các chuỗi thời gian không đồng bộ bằng cách tìm đường đi tối ưu trong ma trận xoắn. Điều này giúp DTW trở thành một công cụ mạnh mẽ trong phân tích chuỗi thời gian. Tuy nhiên, việc tính toán DTW đòi hỏi nhiều tài nguyên và thời gian, đặc biệt với các tập dữ liệu lớn.

2.2. Thuật toán gom cụm

Các thuật toán gom cụm như K-medoids và phân cấp được sử dụng để nhóm các chuỗi thời gian dựa trên độ đo DTW. Các thuật toán này cần được tối ưu hóa để giảm thiểu thời gian tính toán mà vẫn đảm bảo chất lượng gom cụm.

III. Phương pháp nghiên cứu

Đề tài sử dụng các phương pháp xấp xỉ để giảm thiểu độ phức tạp của DTW và áp dụng thuật toán gom cụm với thời gian thực thi tùy chọn. Các kỹ thuật như khởi tạo trung tâm cụm và lập trình đa luồng được đề xuất để cải thiện hiệu suất của hệ thống.

3.1. Kỹ thuật xấp xỉ DTW

Các phương pháp xấp xỉ như tính chặn dưới và ràng buộc toàn cục được sử dụng để giảm thiểu thời gian tính toán DTW. Các kỹ thuật này giúp hệ thống đạt được kết quả gom cụm chính xác trong thời gian ngắn hơn.

3.2. Thuật toán gom cụm tùy chọn

Thuật toán gom cụm với thời gian thực thi tùy chọn cho phép người dùng đánh đổi giữa chất lượng gom cụm và thời gian thực thi. Điều này đặc biệt hữu ích trong các ứng dụng thời gian thực hoặc với các tập dữ liệu lớn.

IV. Kết quả và đánh giá

Các thử nghiệm được thực hiện trên các tập dữ liệu mẫu cho thấy hệ thống đạt được chất lượng gom cụm tương đương với các phương pháp truyền thống nhưng với thời gian thực thi ngắn hơn. Các kỹ thuật xấp xỉ và tối ưu hóa dữ liệu đã chứng minh hiệu quả trong việc cải thiện hiệu suất của hệ thống.

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

Kết quả thử nghiệm cho thấy hệ thống đạt được chất lượng gom cụm cao trên các tập dữ liệu mẫu. Độ đo DTW và các kỹ thuật xấp xỉ đã giúp hệ thống xử lý các chuỗi thời gian không đồng bộ một cách hiệu quả.

4.2. Đánh giá thời gian thực thi

Thời gian thực thi của hệ thống được cải thiện đáng kể nhờ các kỹ thuật xấp xỉ và lập trình đa luồng. Điều này giúp hệ thống phù hợp với các ứng dụng thời gian thực và các tập dữ liệu lớn.

V. Kết luận và hướng phát triển

Luận Văn Thạc Sĩ này đã đề xuất các phương pháp hiệu quả để gom cụm dữ liệu chuỗi thời gian sử dụng độ đo DTW dựa trên kỹ thuật xấp xỉ. Các kết quả thử nghiệm cho thấy hệ thống đạt được chất lượng gom cụm cao với thời gian thực thi ngắn. Hướng phát triển trong tương lai bao gồm việc áp dụng các kỹ thuật học máy và phân tích thống kê để tiếp tục cải thiện hiệu suất của hệ thống.

5.1. Đóng góp của đề tài

Đề tài đã đóng góp vào việc cải thiện hiệu suất của các thuật toán gom cụm dựa trên độ đo DTW bằng cách áp dụng các kỹ thuật xấp xỉ và tối ưu hóa dữ liệu. Các kết quả nghiên cứu có thể được áp dụng trong nhiều lĩnh vực như tài chính, y tế, và môi trường.

5.2. Hướng phát triển

Trong tương lai, đề tài có thể được mở rộng bằng cách tích hợp các kỹ thuật học máy và phân tích thống kê để tiếp tục cải thiện hiệu suất và độ chính xác của hệ thống. Ngoài ra, việc áp dụng hệ thống vào các tập dữ liệu lớn hơn và phức tạp hơn cũng là một hướng nghiên cứu tiềm năng.

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

CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI Chương này sẽ trình bày vấn đề mà đề tài tập trung nghiên cứu, động cơ để thực hiện đề tài này và mục tiêu của đề tài. Ngoài ra, chúng tôi cũng trình bày sơ lược các kết quả đạt được cũng như là nội dung của đề tài. Giới thiệu vấn đề Ngày nay, khi các công nghệ máy tính ngày càng phát triển thì nhu cầu thông tin và dữ liệu của con người ngày càng cao. Hầu hết các giao dịch kinh doanh, từ dữ liệu về chỉ số chứng khoán hay các giao dịch trong các siêu thị, đều được lưu trữ bằng máy tính.

Do đó, thách thức đặt ra đó là quá trình khám phá tri thức trong các tập dữ liệu đó, mà một trong số đó là quá trình gom cụm dữ liệu. Gom cụm dữ liệu (data clustering) là quá trình nhóm các tập đối tượng dữ liệu lại thành các nhóm hay các cụm sao cho các đối tượng trong cùng một cụm có độ tương tự cao nhưng có độ tương tự thấp đối với các đối tượng trong các cụm khác. Độ tương tự hay bất tương tự đó có thể được đánh giá dựa trên các giá trị thuộc tính mô tả đối tượng và thường liên quan tới các độ đo khoảng cách. Mặt khác, các đối tượng dữ liệu hiện nay, như dữ liệu chứng khoán hay thời tiết, đều vốn dĩ có thêm chiều thời gian đi kèm theo hay còn gọi là dữ liệu chuỗi thời gian (time series data).

Việc gom cụm dữ liệu chuỗi thời gian trở thành vấn đề thách thức cộng đồng khai phá dữ liệu bởi vì những giải thuật gom cụm hiện nay đều được thực hiện với các độ đo trong không gian Euclid. Tuy nhiên, các độ đo này đã được chứng minh là ít chính xác và thường cho kết quả không mong muốn trong một số lĩnh vực ứng dụng như dữ liệu đa phương tiện. Vì vậy, sự ra đời của độ đo xoắn thời gian động (Dynamic Time Warping - DTW) đã góp phần giải quyết vấn đề trên bằng cách cho phép ánh xạ các hình dạng tương tự nhau thậm chí khi các hình dạng đó không còn khớp về trục thời gian. 1 GOM CỤM DỮ LIỆU CHUỖI THỜI GIAN VỚI ĐỘ ĐO DTW DỰA VÀO MỘT KỸ THUẬT XẤP XỈ Hình 1.1: Ảnh hưởng của độ đo đối với kết quả gom cụm (Nguồn [12]).

Động cơ Mặc dù sự ra đời DTW đã góp phần giúp việc gom cụm dữ liệu chuỗi thời gian chính xác hơn, thậm chí DTW trở thành độ đo ưu việt, nhưng với số lượng dữ liệu ngày càng lớn (hiện nay con người đang bước vào thời đại dữ liệu Big Data) và cách tính khoảng cách DTW bằng phương pháp quy hoạch động phức tạp đã làm cho việc gom cụm với khoảng cách DTW trở nên chậm hơn. Chính vì vậy, việc phát triển các kỹ thuật thay thế phần lớn cách tính toán phức tạp của DTW bằng các cách tính toán chặn dưới (lower bounding) đơn giản và tiết kiệm chi phí hơn đang trở thành xu hướng hiện nay. Tuy nhiên, các kỹ thuật chặn dưới này khó có thể được áp dụng trực tiếp vào gom cụm nên đối với một vài vấn đề thực tế thì gom cụm với DTW vẫn mất thời gian khá lâu. Do đó, trong nghiên cứu này chúng tôi nghiên cứu giải pháp tiến hành gom cụm với DTW bằng giải thuật gom cụm với thời gian thực thi tùy chọn (anytime clustering algorithm) tức là đánh đổi giữa thời gian thực thi và chất lượng của kết quả gom cụm, chất lượng gom cụm sẽ được cải thiện với thời gian thực thi.

Giải thuật này ra đời trong bối cảnh cả thế giới bước vào thời đại dữ liệu lớn mà độ phức tạp trong cách tính khoảng cách DTW sẽ là một trở ngại về mặt thời gian để chúng ta có thể đạt được kết quả mong muốn. Sự phát triển của kiểu giải 2 GOM CỤM DỮ LIỆU CHUỖI THỜI GIAN VỚI ĐỘ ĐO DTW DỰA VÀO MỘT KỸ THUẬT XẤP XỈ thuật này đã đáp ứng được tình hình nhu cầu thực tế đó và đem lại tính mềm dẻo và linh hoạt cho người dùng nhờ vào tính khả dừng của giải thuật, tức là giải thuật có thể dừng bất kỳ lúc nào và có thể cho ra kết quả tốt nhất nếu giải thuật này được phép thực thi lâu hơn hoặc cho đến khi hoàn tất. Thời điểm dừng giải thuật sẽ do người dùng quyết định, tùy vào số lượng thời gian mà người dùng cho phép giải thuật thực thi mà kết quả đạt được sẽ đáp ứng được yêu cầu của người dùng. Mục tiêu Mục tiêu nghiên cứu của đề tài này trên cơ sở dữ liệu chuỗi thời gian là xây dựng hệ thống gom cụm dữ liệu dựa vào giải thuật gom cụm K-medoids và giải thuật với thời gian thực thi tùy chọn, với các vấn đề chính sau:  Tìm hiểu cách tính xấp xỉ khoảng cách DTW: ưu điểm của DTW đó là độ chính xác cao so với các độ đo Euclid, nhưng cách tính toán phức tạp và chậm.

Do đó, đề tài sẽ tìm hiểu các phương pháp tính xấp xỉ khoảng cách DTW.  Tìm hiểu giải thuật gom cụm với thời gian thực thi tùy chọn: do việc áp dụng trực tiếp các cách tính xấp xỉ khoảng cách DTW vào giải thuật xử lý theo lô còn gặp khó khăn vì có thể cho ra kết quả chậm so với mong muốn của người dùng nên đề tài sẽ áp dụng giải thuật gom cụm với thời gian thực thi tùy chọn để đánh đổi giữa chất lượng gom cụm với thời gian thực thi.  Đề xuất một số cải tiến khi hiện thực giải thuật gom cụm dữ liệu chuỗi thời gian với khoảng cách DTW dựa vào một kỹ thuật xấp xỉ và thử nghiệm độ hiệu quả của giải thuật trên một số tập dữ liệu mẫu. Tóm lược kết quả đạt được Sau một thời gian nghiên cứu và hiện thực, chúng tôi đã đạt được các kết quả tích cực đó là:  Xây dựng được hệ thống gom cụm sử dụng giải thuật gom cụm với thời gian thực thi tùy chọn dùng khoảng cách DTW dựa vào một kỹ thuật xấp xỉ, đánh đổi chất lượng gom cụm với thời gian thực thi, nhưng vẫn 3 GOM CỤM DỮ LIỆU CHUỖI THỜI GIAN VỚI ĐỘ ĐO DTW DỰA VÀO MỘT KỸ THUẬT XẤP XỈ cho ra kết quả tương đối chính xác trong thời gian ngắn so với hệ thống gom cụm dữ liệu chuỗi thời gian mà không áp dụng hai phương pháp trên.

 Đưa vào một kỹ thuật khởi tạo trung tâm cụm cho giải thuật K-medoids nhằm rút ngắn thời gian tính toán.  Đề xuất được kỹ thuật lập trình đa luồng kết hợp xử lý song song tác vụ để giảm thời gian tính toán khoảng cách DTW nhưng vẫn cho kết quả chính xác như cách tính cổ điển.  Đưa ra được các kết luận đánh giá chất lượng gom cụm cũng như so sánh độ hiệu quả của các phương pháp khác nhau được áp dụng trong đề tài này.  Cho phép người dùng thực hiện gom cụm với các thông số k khác nhau và đánh giá kết quả đạt được để chọn trị k tối ưu.

Như vậy, hệ thống này cơ bản đã đáp ứng được các yêu cầu của bài toán đặt ra mà chúng tôi sẽ trình bày chi tiết ở các phần sau. Cấu trúc của luận văn Tổ chức phần còn lại của luận văn gồm những phần như sau: Chương 2 là các cơ sở lý thuyết mà chúng tôi sử dụng trong nghiên cứu này. Chúng bao gồm các lý thuyết về độ đo khoảng cách của chuỗi thời gian, các kỹ thuật về ràng buộc toàn cục (global constraints) và tính chặn dưới cũng như các kỹ thuật về gom cụm dữ liệu thường và dữ liệu chuỗi thời gian. Chương 3 để giới thiệu về các công trình nghiên cứu liên quan.

Những công trình này trình bày về các phương pháp tính giá trị trung bình dựa trên khoảng cách DTW để áp dụng kỹ thuật gom cụm K-means như phương pháp của Gupta và các đồng sự, giải thuật PSA và giải thuật DBA. Ngoài ra, chúng tôi còn giới thiệu một công trình gom cụm dữ liệu chuỗi thời gian với thời gian thực thi tùy chọn dựa vào cách xấp xỉ khoảng cách DTW. Chương 4 bao gồm nội dung chi tiết thiết kế và hiện thực hệ thống gom cụm với thời gian thực thi tùy chọn. 4 GOM CỤM DỮ LIỆU CHUỖI THỜI GIAN VỚI ĐỘ ĐO DTW DỰA VÀO MỘT KỸ THUẬT XẤP XỈ Chương 5 trình bày các kết quả thực nghiệm đạt được, qua đó đánh giá chất lượng gom cụm của hệ thống cũng như đánh giá thời gian chạy của giải thuật.

Chương 6 là một số kết luận, đóng góp của đề tài cũng như hướng phát triển trong tương lai của đề tài. 5 GOM CỤM DỮ LIỆU CHUỖI THỜI GIAN VỚI ĐỘ ĐO DTW DỰA VÀO MỘT KỸ THUẬT XẤP XỈ CHƯƠNG 2: CƠ SỞ LÝ THUYẾT Trong chương này chúng tôi sẽ trình bày các khái niệm được sử dụng trong đề tài này như là giải thuật tính độ đo xoắn thời gian động, kỹ thuật ràng buộc toàn cục, các kỹ thuật tính chặn dưới, các giải thuật gom cụm dữ liệu thông thường và dữ liệu chuỗi thời gian cũng như giới thiệu về cách xác định số cụm k tối ưu nhất trong giải thuật gom cụm K-medoids và các phương pháp đánh giá chất lượng gom cụm dữ liệu. Các độ đo khoảng cách chuỗi thời gian Các bài toán tìm kiếm mẫu, phân loại hay gom cụm dữ liệu chuỗi thời gian đều sử dụng kiểu dữ liệu mà ở đó được biểu diễn thành một chuỗi các số thực. Vì vậy, để giải quyết các bài toán này ta phải sử dụng các độ đo khoảng cách giữa các cặp chuỗi thời gian với nhau.

Giả sử ta có hai chuỗi thời gian Q và C với các độ dài n và m tương ứng là và. Ta cần phải xác định độ đo khoảng cách Dist(Q,C) của hai chuỗi thời gian này. Các độ đo trong không gian Euclid Hiện nay, có rất nhiều độ đo khoảng cách đã được sử dụng cho gom cụm dữ liệu chuỗi thời gian tùy thuộc vào từng miền ứng dụng và trong đó các độ đo trong không gian Euclid là đủ khả năng để giải quyết bài toán này. Tuy nhiên, vì sự thiếu linh hoạt để áp dụng trong các kỹ thuật biến đổi như tịnh tiến (shifting), kéo dãn (stretching) hay co lại (contracting) trên trục thời gian nên các độ đo này ngày càng trở nên thiếu chính xác [1].

Sau đây, chúng tôi sẽ giới thiệu một vài độ đo trong không gian Euclid.