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

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CÁM ƠN
• TÓM TẮT
• ABSTRACT
• 1. CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI
• 1.1. Giới thiệu vấn đề
• 1.2. Tóm lược kết quả đạt được
• 1.3. Cấu trúc của luận văn
• 2. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT
• 2.1. Các độ đo khoảng cách chuỗi thời gian
• 2.1.1. Các độ đo trong không gian Euclid
• 2.1.2. Khoảng cách xoắn thời gian động
• 2.1.3. Kỹ thuật ràng buộc toàn cục
• 2.1.4. Kỹ thuật tính chặn dưới
• 2.1.4.1. Phương pháp tính chặn dưới của Kim
• 2.1.4.2. Phương pháp tính chặn dưới của Yi
• 2.1.4.3. Phương pháp tính chặn dưới của Keogh
• 2.2. Các giải thuật gom cụm dữ liệu thường sử dụng
• 2.2.1. Giải thuật gom cụm phân cấp
• 2.2.2. Giải thuật gom cụm phân hoạch
• 2.3. Các giải thuật gom cụm dữ liệu chuỗi thời gian
• 2.4. Các phương pháp chọn số cụm k tối ưu nhất
• 2.5. Các phương pháp đánh giá chất lượng gom cụm dữ liệu
• 3. CHƯƠNG 3: CÁC CÔNG TRÌNH LIÊN QUAN
• 3.1. Phương pháp tính giá trị trung bình hình dạng dùng khoảng cách DTW
• 3.1.1. Phương pháp tính trung bình của Gupta và các đồng sự
• 3.1.2. Giải thuật tính trung bình cụm dữ liệu PSA
• 3.1.3. Giải thuật tính trung bình cụm dữ liệu DBA
• 3.2. Phương pháp gom cụm dữ liệu chuỗi thời gian dựa vào xấp xỉ độ đo xoắn thời gian động
• 3.2.1. Khung thức gom cụm với thời gian thực thi tùy chọn
• 3.2.2. Phương pháp xấp xỉ ma trận khoảng cách DTW
• 3.2.3. Heuristic sắp thứ tự
• 4. CHƯƠNG 4: HỆ THỐNG GOM CỤM DỮ LIỆU CHUỖI THỜI GIAN VỚI THỜI GIAN THỰC THI TÙY CHỌN
• 4.1. Hướng giải quyết
• 4.1.1. Kỹ thuật khởi tạo trung tâm cụm
• 4.1.2. Kỹ thuật lập trình đa luồng để cải tiến DTW
• 4.2. Kiến trúc chi tiết hệ thống
• 5. CHƯƠNG 5: THỰC NGHIỆM
• 5.1. Giới thiệu tập dữ liệu mẫu
• 5.2. Đánh giá thời gian thực thi của kỹ thuật khởi tạo trung tâm cụm
• 5.3. Đánh giá độ hiệu quả của các phương pháp xấp xỉ ma trận DTW
• 5.4. Đánh giá thời gian thực thi của kỹ thuật lập trình đa luồng
• 5.5. Đánh giá kết quả gom cụm và thời gian thực thi của hệ thống
• 5.5.1. Đánh giá chất lượng gom cụm của hệ thống
• 5.5.2. Đánh giá thời gian thực thi của hệ thống
• 5.6. Kết luận
• 6. CHƯƠNG 6: KẾT LUẬN
• 6.1. Những đóng góp của đề tài
• 6.2. Hướng phát triển
• TÀI LIỆU THAM KHẢO
• PHỤ LỤC A: BẢNG ĐỐI CHIẾU THUẬT NGỮ ANH – VIỆT
• PHỤ LỤC B: LÝ LỊCH TRÍCH NGANG

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.

Nội dung chính

Tổng quan nghiên cứu

Trong kỷ nguyên bùng nổ dữ liệu lớn, dữ liệu chuỗi thời gian chiếm hơn 80% dung lượng thông tin được ghi nhận từ các hệ thống giám sát thời gian thực như giao dịch chứng khoán, quan trắc khí tượng, chẩn đoán y tế và cảm biến vạn vật kết nối. Thách thức cốt lõi đặt ra cho ngành khai phá dữ liệu là làm thế nào để trích xuất tri thức và phân nhóm các mẫu hình hữu ích một cách tự động thông qua quá trình học không giám sát. Bài toán gom cụm dữ liệu chuỗi thời gian truyền thống thường áp dụng các độ đo khoảng cách trong không gian Euclid như chuẩn L1 hay chuẩn L2. Tuy nhiên, độ đo Euclid bộc lộ khiếm khuyết lớn do tính cứng nhắc trên trục thời gian, khiến độ chính xác phân cụm suy giảm dưới 55% khi đối mặt với các chuỗi thời gian có hiện tượng tịnh tiến, co dãn hoặc dịch pha.

Để khắc phục hạn chế này, độ đo xoắn thời gian động đã trở thành tiêu chuẩn vàng nhờ khả năng ánh xạ tối ưu giữa các dạng sóng tương tự nhau ngay cả khi không trùng khớp về trục thời gian. Trở ngại lớn nhất của giải thuật xoắn thời gian động nằm ở độ phức tạp tính toán cục bộ đạt mức O(nm) theo thuật toán quy hoạch động, đòi hỏi chi phí tài nguyên rất lớn khi kích thước tập dữ liệu vượt qua ngưỡng 2000 chuỗi. Mục tiêu trọng tâm của luận văn thạc sĩ chuyên ngành Khoa học Máy tính tại Trường Đại học Bách Khoa, Đại học Quốc gia Thành phố Hồ Chí Minh là xây dựng hệ thống gom cụm dữ liệu chuỗi thời gian linh hoạt dựa trên giải thuật phân cụm có thời gian thực thi tùy chọn kết hợp độ đo xoắn thời gian động xấp xỉ.

Nghiên cứu tập trung giải quyết sự đánh đổi giữa thời gian xử lý và độ chính xác phân loại trên các tập dữ liệu chuẩn. Kết quả thử nghiệm thực tế cho thấy hệ thống giúp rút ngắn khoảng 45% đến 65% thời gian tính toán so với các giải thuật xử lý theo lô truyền thống, trong khi vẫn duy trì chỉ số tương đồng phân cụm đạt trên 90% chất lượng tối ưu.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu xây dựng nền tảng dựa trên lý thuyết độ đo xoắn thời gian động, lý thuyết chặn dưới trong không gian chuỗi thời gian và khung thức giải thuật có thời gian thực thi tùy chọn. Độ đo xoắn thời gian động tìm kiếm một đường xoắn tối ưu W trên ma trận khoảng cách tích lũy nhằm tối thiểu hóa tổng chi phí biến dạng giữa hai chuỗi dữ liệu. Để giới hạn không gian tìm kiếm và tránh hiện tượng ánh xạ phi thực tế, hai kỹ thuật ràng buộc toàn cục kinh điển được áp dụng là dải Sakoe-Chiba với cửa sổ xoắn cố định r và hình bình hành Itakura với hàm biến thiên phụ thuộc chỉ số thời gian.

Bên cạnh đó, nghiên cứu tích hợp các kỹ thuật chặn dưới để loại trừ sớm các cặp chuỗi không tương đồng mà không cần thực hiện toàn bộ thuật toán quy hoạch động. Ba phương pháp chặn dưới tiêu biểu được phân tích chuyên sâu gồm:

• Phương pháp chặn dưới của Kim: Rút trích 4 thuộc tính biên và cực trị, tính toán nhanh với độ phức tạp O(1) nhưng độ chặt lỏng lẻo.
• Phương pháp chặn dưới của Yi: Sử dụng kỹ thuật FastMap kết hợp trích xuất giá trị tối thiểu, đạt độ phức tạp thực tế khoảng O(M^2) với M là kích thước tập dữ liệu.
• Phương pháp chặn dưới của Keogh: Xây dựng bao trên U và bao dưới L bao bọc chuỗi tín hiệu, đạt độ phức tạp tuyến tính O(n) và cung cấp cận dưới chặt chẽ nhất trong các ứng dụng thực tế.

Khái niệm giải thuật có thời gian thực thi tùy chọn được ứng dụng nhằm tạo ra tính khả dừng, cho phép hệ thống trả về kết quả phân cụm hợp lệ tại bất kỳ thời điểm nào và liên tục nâng cao chất lượng khi được cấp thêm tài nguyên thời gian thực thi.

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

Nghiên cứu sử dụng nguồn dữ liệu thực nghiệm từ kho chuẩn UCR Time Series Classification Archive, bao gồm các tập dữ liệu đa dạng như CBF, FaceFour, Synthetic Control Chart, Trace và tập dữ liệu tài chính Stock. Kích thước mẫu khảo sát trải rộng từ 100 đến hơn 2100 cá thể chuỗi thời gian với độ dài dao động từ 60 đến 275 điểm đo trên mỗi chuỗi. Phương pháp lấy mẫu phân tầng ngẫu nhiên được áp dụng để chia tách các tập kiểm thử nhằm đảm bảo tính khách quan của phân phối dữ liệu gốc.

Phương pháp phân tích chính là giải thuật phân cụm K-medoids kết hợp xấp xỉ ma trận khoảng cách. Luận văn lựa chọn K-medoids thay vì K-means vì K-medoids sử dụng trực tiếp các phần tử thực tế làm tâm cụm, giúp hạn chế tác động của nhiễu ngoại lai và loại bỏ hoàn toàn yêu cầu tính toán chuỗi trung bình hình dạng phức tạp vốn có độ phức tạp cao của các giải thuật DBA hay PSA. Nhằm tối ưu hóa tốc độ, tác giả đề xuất hai cải tiến then chốt: kỹ thuật khởi tạo trung tâm cụm thông minh nhằm giảm khoảng 35% số vòng lặp hoán đổi đại diện và kỹ thuật lập trình đa luồng xử lý song song các tác vụ tính toán ma trận khoảng cách trên bộ vi xử lý đa nhân. Toàn bộ quá trình thiết kế, hiện thực và đánh giá được thực hiện liên tục trong khoảng thời gian 6 tháng nghiên cứu.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình thực nghiệm đối sánh trên các bộ dữ liệu chuẩn đã ghi nhận những phát hiện mang tính đột phá về cả hiệu năng lẫn độ chính xác:

Thứ nhất, kỹ thuật khởi tạo tâm cụm cho giải thuật K-medoids giúp giảm số lần lặp hội tụ từ 40% đến 52% so với phương pháp chọn ngẫu nhiên cổ điển. Trên tập dữ liệu Synthetic Control Chart gồm 600 chuỗi, thời gian thực thi gom cụm giảm từ 18,4 giây xuống còn 9,6 giây mà không làm suy giảm cấu trúc cụm đích.

Thứ hai, việc áp dụng kỹ thuật lập trình đa luồng song song hóa tính toán ma trận khoảng cách đã cải thiện tốc độ xử lý từ 3,2 đến 3,8 lần trên cấu trúc CPU 4 nhân vật lý. Khi xử lý ma trận toàn vẹn cho tập dữ liệu Trace với 200 đối tượng, thời gian tính toán giảm mạnh từ 45,2 giây xuống còn 12,1 giây.

Thứ ba, giải thuật gom cụm với thời gian thực thi tùy chọn dựa trên xấp xỉ ma trận xoắn thời gian động đạt được chỉ số chất lượng ngoại ARI trên 0,88 chỉ sau khi tiêu tốn 30% tổng thời gian thực thi của giải thuật xử lý theo lô. Khi thời gian chạy đạt mức 60%, độ chính xác phân cụm trên tập FaceFour đạt 94,5% tương đương kết quả tính toán chính xác tuyệt đối.

Thứ tư, hàm heuristic sắp thứ tự cập nhật khoảng cách chứng minh tính ưu việt khi giảm sai số chuẩn hóa của ma trận khoảng cách xuống dưới 0,08 chỉ sau 150 bước lặp đầu tiên, bảo đảm các cặp dữ liệu quan trọng nhất được tinh chỉnh trước.

Thảo luận kết quả

Dữ liệu thực nghiệm phân tích chất lượng gom cụm có thể được mô hình hóa trực quan qua biểu đồ đường biểu diễn sự biến thiên của chỉ số ARI theo trục thời gian thực thi, kết hợp bảng thống kê so sánh thời gian chạy giữa phương pháp xấp xỉ đề xuất và phương pháp duyệt theo lô truyền thống trên 5 tập dữ liệu chuẩn.

Kết quả vượt trội của giải thuật bắt nguồn từ việc tận dụng thành công tính chất bao đóng của khoảng cách Euclid làm chặn trên và hàm chặn dưới của Keogh làm cận dưới. Nhờ cấu trúc này, không gian tìm kiếm của ma trận xoắn được cô lập trong một dải hẹp, cho phép giải thuật xấp xỉ dự đoán chính xác giá trị khoảng cách thật. So sánh với các nghiên cứu trước đây vốn chỉ áp dụng chặn dưới đơn lẻ cho bài toán truy vấn chỉ mục, việc tích hợp hàm heuristic sắp xếp thứ tự ưu tiên cập nhật trong luận văn đã tạo ra bước nhảy vọt về hiệu suất phân cụm. Khi đối sánh với độ đo Euclid thông thường trên tập dữ liệu CBF, phương pháp đề xuất nâng cao độ chính xác phân cụm thêm 38,2%, chứng minh khoảng cách xoắn thời gian động là yếu tố then chốt để xử lý hiện tượng biến dạng tín hiệu trong thực tế.

Đề xuất và khuyến nghị

Nhằm hoàn thiện và nâng cao khả năng ứng dụng thực tiễn của mô hình gom cụm dữ liệu chuỗi thời gian, luận văn đưa ra 4 nhóm giải pháp chiến lược:

• Nâng cấp kiến trúc tính toán sang nền tảng vi xử lý đồ họa GPU: Đội ngũ kỹ sư nghiên cứu và phát triển phần mềm cần chuyển đổi các hàm tính ma trận xoắn thời gian động và chặn dưới từ đa luồng CPU sang kiến trúc xử lý song song hàng loạt CUDA trên GPU. Mục tiêu kỹ thuật là tăng tốc độ xử lý ma trận lên gấp 8 đến 12 lần cho các tập dữ liệu có quy mô trên 50000 chuỗi trong lộ trình 6 tháng.
• Tích hợp kỹ thuật nén chuỗi thời gian đa mức: Các chuyên gia kiến trúc dữ liệu nên triển khai kết hợp giải thuật xấp xỉ gộp từng đoạn hoặc biểu diễn ký hiệu xấp xỉ kết hợp nhằm thu giảm 50% số chiều dữ liệu trước khi tính toán bao biên. Giải pháp này giúp cắt giảm 40% dung lượng bộ nhớ RAM tiêu thụ trong thời gian 3 tháng tới.
• Tự động hóa tiến trình xác định số lượng cụm tối ưu: Bộ phận khoa học dữ liệu cần tích hợp các chỉ số đánh giá nội bộ như hệ số Silhouette hoặc chỉ số Davies-Bouldin vào quy trình chạy tùy chọn thời gian. Hệ thống sẽ tự động quét dải tham số k từ 2 đến 20 để đưa ra khuyến nghị phân hoạch tối ưu với độ tin cậy trên 95% trong khung thời gian 4 tháng.
• Mở rộng kiến trúc gom cụm luồng dữ liệu thời gian thực: Các kỹ sư hệ thống cần phát triển mô hình gom cụm thích nghi dạng dòng chảy trên các nền tảng xử lý phân tán như Apache Flink hoặc Spark Streaming, nhằm đạt độ trễ phân nhóm dưới 100 mili-giây trên các luồng dữ liệu y tế và tài chính trong vòng 12 tháng.

Đối tượng nên tham khảo luận văn

Công trình nghiên cứu mang giá trị thực tiễn và lý thuyết sâu sắc, phù hợp cho 4 nhóm đối tượng trọng tâm:

• Các nhà nghiên cứu và học viên cao học ngành Khoa học Máy tính: Cung cấp tài liệu tham khảo chuẩn mực về phương pháp luận xấp xỉ độ đo phi Euclid, các kỹ thuật tối ưu hóa thuật toán quy hoạch động và mô hình thuật toán có thời gian thực thi tùy chọn trong khai phá dữ liệu nâng cao.
• Kỹ sư dữ liệu và chuyên gia định lượng trong ngành tài chính - chứng khoán: Ứng dụng giải thuật gom cụm chuỗi thời gian để phân nhóm các mã cổ phiếu có quy luật biến động tương đồng nhưng lệch pha về mặt thời gian, từ đó xây dựng danh mục đầu tư phòng ngừa rủi ro với quy mô xử lý hàng triệu điểm dữ liệu lịch sử.
• Chuyên gia phân tích dữ liệu y tế và cảm biến thông minh: Khai thác giải thuật để nhận dạng và gom nhóm các mẫu tín hiệu điện tâm đồ, điện não đồ hoặc dữ liệu giám sát bệnh nhân theo thời gian thực, giúp giảm hơn 50% thời gian tiền xử lý cảnh báo bất thường.
• Kiến trúc sư hệ thống phần mềm và phân tích dữ liệu lớn: Tham khảo giải pháp kết hợp lập trình đa luồng và cấu trúc dữ liệu xấp xỉ để tối ưu hóa tài nguyên phần cứng trong các hệ sinh thái xử lý dữ liệu quy mô lớn.

Câu hỏi thường gặp

Tại sao khoảng cách Euclid không đạt hiệu quả cao khi gom cụm dữ liệu chuỗi thời gian?

Khoảng cách Euclid chỉ so sánh điểm đối điểm tại cùng một chỉ số thời gian cố định, đòi hỏi các chuỗi phải có chiều dài bằng nhau và đồng pha tuyệt đối. Khi dữ liệu xuất hiện độ trễ thời gian, co dãn hoặc dịch pha, khoảng cách Euclid sẽ tính toán sai lệch, dẫn đến độ chính xác phân cụm trong thực tế giảm xuống dưới 60%.

Khung thức giải thuật có thời gian thực thi tùy chọn mang lại lợi ích gì?

Giải thuật có thời gian thực thi tùy chọn mang tính khả dừng, cho phép người dùng dừng chương trình tại bất kỳ thời điểm nào để nhận kết quả phân cụm hợp lệ ngay lập tức. Nếu cấp thêm thời gian, thuật toán sẽ liên tục cập nhật và nâng cao chất lượng phân cụm tiến gần tới mức tối ưu tuyệt đối.

Kỹ thuật chặn dưới của Keogh hoạt động như thế nào trong bài toán tối ưu DTW?

Kỹ thuật của Keogh tạo ra một đường bao trên U và bao dưới L bao quanh chuỗi tín hiệu theo độ rộng cửa sổ xoắn. Bằng cách tính khoảng cách Euclid giữa phần nằm ngoài dải bao của chuỗi thứ hai với đường biên, phương pháp này tạo ra một cận dưới chặt chẽ với độ phức tạp tuyến tính O(n), giúp loại bỏ sớm các phép tính DTW tốn kém.

Tại sao nghiên cứu lại chọn thuật toán K-medoids thay vì K-means kết hợp DBA?

K-medoids sử dụng trực tiếp các phần tử thực tế trong tập dữ liệu làm tâm cụm, giúp hạn chế tác động của nhiễu và triệt tiêu hoàn toàn nhu cầu tính toán chuỗi trung bình hình dạng vốn rất tốn kém tài nguyên tính toán như các giải thuật DBA hay PSA, từ đó bảo toàn tính toàn vẹn của dạng sóng gốc.

Việc lập trình đa luồng giúp cải thiện tốc độ tính toán ma trận như thế nào?

Tính toán khoảng cách xoắn thời gian động cho từng cặp chuỗi là các tác vụ độc lập tuyến tính. Kỹ thuật đa luồng phân chia đồng thời việc tính toán các phần tử ma trận trên các lõi CPU khác nhau, giúp giảm thiểu độ trễ xử lý từ 3,2 đến 3,8 lần trên hệ thống máy tính đa lõi tiêu chuẩn.

Kết luận

• Luận văn đã giải quyết triệt để bài toán thắt nút cổ chai về thời gian tính toán O(nm) của độ đo xoắn thời gian động trong phân tích dữ liệu chuỗi thời gian.
• Hệ thống ứng dụng thành công khung thức giải thuật có thời gian thực thi tùy chọn, cho phép đánh đổi linh hoạt giữa tài nguyên thời gian và độ chính xác phân cụm.
• Đề xuất kỹ thuật khởi tạo trung tâm cụm tối ưu cho giải thuật K-medoids giúp giảm từ 40% đến 52% số vòng lặp hội tụ của hệ thống.
• Hiện thực thành công kỹ thuật lập trình đa luồng giúp tăng tốc độ tính toán ma trận khoảng cách lên hơn 3,5 lần trên phần cứng đa nhân.
• Kết quả kiểm thử trên 5 bộ dữ liệu chuẩn khẳng định chất lượng phân cụm đạt chỉ số tương đồng trên 90% chỉ với 30% đến 40% thời gian thực thi theo lô.

Trong lộ trình 6 đến 12 tháng tới, các hướng mở rộng sẽ tập trung vào việc tăng tốc xử lý trên phần cứng chuyên dụng GPU và phát triển thuật toán phân cụm dòng dữ liệu thời gian thực. Hãy liên hệ và khai thác ngay toàn văn công trình nghiên cứu để áp dụng các giải pháp phân cụm chuỗi thời gian tiên tiến vào hệ thống phân tích dữ liệu của bạn.

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.