ĐẠI HỌC QUỐC GIA TP. HCM TRƯỜNG ĐẠI HỌC BÁCH KHOA ---------------------- TRẦN NHẬT TUẤN KẾT HỢP THU GIẢM SỐ CHIỀU VÀ KỸ THUẬT LẬP TRÌNH ĐA LUỒNG ĐỂ TĂNG TỐC GOM CỤM DỮ LIỆU CHUỖI THỜI GIAN VỚI ĐỘ ĐO XOẮN THỜI GIAN ĐỘNG LUẬN VĂN THẠC SĨ TP. HỒ CHÍ MINH, tháng 07 năm 2017 ĐẠI HỌC QUỐC GIA TP. HCM TRƯỜNG ĐẠI HỌC BÁCH KHOA ---------------------- TRẦN NHẬT TUẤN KẾT HỢP THU GIẢM SỐ CHIỀU VÀ KỸ THUẬT LẬP TRÌNH ĐA LUỒNG ĐỂ TĂNG TỐC GOM CỤM DỮ LIỆU CHUỖI THỜI GIAN VỚI ĐỘ ĐO XOẮN THỜI GIAN ĐỘNG Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số: 60.01 LUẬN VĂN THẠC SĨ PGS.
DƯƠNG TUẤN ANH TP. HỒ CHÍ MINH, tháng 07 năm 2017 CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH Cán bộ hướng dẫn khoa học : PGS. DƯƠNG TUẤN ANH. Cán bộ chấm nhận xét 1 : TS.
Cán bộ chấm nhận xét 2 : TS. LÊ VĂN QUỐC ANH. Luận văn thạc sĩ được bảo vệ tại Trường Đại học Bách Khoa, ĐHQG Tp. HCM ngày 18 tháng 07 năm 2017.
Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm: 1. QUẢN THÀNH THƠ (Chủ tịch). NGUYỄN AN KHƯƠNG (Thư ký). LÊ VĂN QUỐC ANH (Phản biện 2).
TRẦN TUẤN ANH (Ủy viên). CHỦ TỊCH HỘI ĐỒNG TRƯỞNG KHOA KH&KT MT ĐẠI HỌC QUỐC GIA TP.HCM CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM TRƯỜNG ĐẠI HỌC BÁCH KHOA Độc lập - Tự do - Hạnh phúc NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ tên học viên: TRẦN NHẬT TUẤN MSHV: 1570236 Ngày, tháng, năm sinh: 02/06/1988 Nơi sinh: Nghệ An Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số : 60480101 I. TÊN ĐỀ TÀI: Kết hợp thu giảm số chiều và kỹ thuật lập trình đa luồng để tăng tốc gom cụm dữ liệu chuỗi thời gian với độ đo xoắn thời gian động. NHIỆM VỤ VÀ NỘI DUNG: - Tìm hiểu cách tính khoảng cách DTW.
- Tìm hiểu phương pháp xấp xỉ gộp từng đoạn PAA để thu giảm số chiều và giải thuật PDTW để tính độ đo DTW cho dữ liệu chuỗi thời gian đã thu giảm số chiều bằng PAA. - Ứng dụng kỹ thuật lập trình đa luồng để tăng tốc việc tính toán độ đo DTW. - Tìm hiểu giải thuật K-medoids cải tiến được dùng làm giải thuật gom cụm chính. NGÀY GIAO NHIỆM VỤ: 16/01/2017 IV.
NGÀY HOÀN THÀNH NHIỆM VỤ: 18/06/2017 V. CÁN BỘ HƯỚNG DẪN: PGS. DƯƠNG TUẤN ANH Tp. HCM, ngày … tháng … năm …… CÁN BỘ HƯỚNG DẪN TRƯỞNG KHOA KH&KT MT (Họ tên và chữ ký) (Họ tên và chữ ký) LỜI CÁM ƠN Đầu tiên tôi xin được gửi lời cảm ơn tập thể các thầy cô của khoa Khoa học & Kỹ thuật Máy tính trường Đại học Bách Khoa đã tận tình chỉ dạy và trang bị cho tôi những kiến thức cần thiết đề làm nền tảng cho việc thực hiện luận văn cũng như những kinh nghiệm quý báu để tôi vững tin hơn trong môi trường làm việc sau này.
Xin chân thành cảm ơn thầy Dương Tuấn Anh đã tận tình giúp đỡ, định hướng và cung cấp ý tưởng cũng như tài liệu tham khảo trong thời gian tôi làm luận văn. Ngoài ra, tôi xin được gửi lời cảm ơn chân thành đến gia đình và bạn bè - những người luôn ở bên cạnh động viên tôi về vật chất lẫn tinh thần và hỗ trợ tôi hoàn thành luận văn này. TÓM TẮT Dữ liệu chuỗi thời gian đã trở nên rất cần thiết và phổ biến trong nhiều lĩnh vực ứng dụng. Ý tưởng về việc thu thập và phân tích dữ liệu chuỗi thời gian đã có từ lâu.
Tuy nhiên, vẫn có những thách thức nhất định khi làm việc với dữ liệu chuỗi thời gian, cụ thể là gom cụm dữ liệu, bài toán đóng vai trò quan trọng trong rất nhiều ứng dụng dữ liệu. Với nhiều trường hợp thì độ đo Euclid tỏ ra quá cứng nhắc vì không thích nghi được với những phép biến đổi như tịnh tiến, co giãn biên độ hay xoắn trục thời gian. Hơn nữa, độ đ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. Sự ra đời của độ đo xoắn thời gian động (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.
Tuy độ đo DTW cho kết quả tốt hơn độ đo khoảng cách Euclid trên gần như mọi bài toán, nhưng lại thời gian tính toán rất lâu. Vì vậy, một số giải pháp được đưa ra để tăng tốc DTW. Đề tài nghiên cứu này tập trung vào việc xây dựng chương trình gom cụm dữ liệu dựa vào giải thuật K-medoids với độ đo xoắn thời gian động DTW, kết hợp kỹ thuật thu giảm số chiều PAA và kỹ thuật lập trình đa luồng để tăng tốc thời gian gom cụm. Đặc điểm nổi bật của phương pháp này là đánh đổi giữa thời gian thực thi và kết quả đạt được.
Kết quả thực nghiệm cho thấy chất lượng gom cụm vẫn tương đối chính xác nhưng đã rút ngắn đáng kể về mặt thời gian. ABSTRACT Time series data have become a ubiquitous, necessary data source in many application domains. About the idea of collecting and analyzing time series data, there are still certain challenges in working with them, namely cluster analysis – which plays an important role in a wide variety of data applications. In most cases, using Euclidean dissimilarity for time series data is inelastic in regards to transformation methods, such as shifting, scaling or time warping.
Moreover, its result is not good and unexpected in some application domains, for example, multimedia data. Dynamic Time Warping, as a dissimilarity measure, overcomes the problem by mapping analogous shapes, even those are not matched on time axis. Although being better than Euclidean dissimilarity at quality of results in most of clustering problems, DTW calculation takes a very long time to finish execution. Therefore, it requires techniques to accelerate DTW calculation.
This study focuses on building clustering system based on K-medoids algorithm and DTW distance, combining dimensionality reduction and multithreading technique to speed up time series clustering. The outstanding feature of this method is the tradeoff between execution time and clustering quality. Experimental results show that clustering quality is acceptably accurate, while taking significantly less time to execute. LỜI CAM ĐOAN Tôi xin cam đoan các kết quả báo cáo trong luận văn này và chương trình là sản phẩm do công sức lao động của chính tôi thực hiện, không có sự sao chép từ những công trình nào khác, ngoại trừ những kết quả từ các công trình khác đã ghi rõ trong luận văn.
Tất cả các kiến thức tôi học hỏi được từ những tài liệu tham khảo đều được trích dẫn nguồn đầy đủ. Nếu có bất cứ sai phạm nào so với lời cam đoan, tôi xin chịu các hình thức xử lý theo quy định. MỤC LỤC GIỚI THIỆU ĐỀ TÀI .1 Dữ liệu chuỗi thời gian và vấn đề khai phá dữ liệu chuỗi thời gian .1 Khai phá dữ liệu .2 Dữ liệu chuỗi thời gian .3 Khai phá dữ liệu chuỗi thời gian .2 Bài toán gom cụm trong dữ liệu chuỗi thời gian .4 Phương pháp nghiên cứu .5 Ý nghĩa của luận văn .6 Những kết quả đạt được của luận văn .7 Nội dung chính của luận văn .1 Các độ đo khoảng cách chuỗi thời gian.1 Các độ đo trong không gian Euclid .2 Độ đo xoắn thời gian động .2 Các giải thuật gom cụm dữ liệu thường dùng .1 Giải thuật K-means .2 Giải thuật K-medoids .3 Các phương pháp thu giảm số chiều dựa vào đặc trưng .1 Các phương pháp biến đổi sang miền tần số.2 Các phương pháp xấp xỉ tuyến tính từng đoạn .4 Các tiêu chí đánh giá chất lượng gom cụm. 23 CÁC CÔNG TRÌNH NGHIÊN CỨU LIÊN QUAN .1 Cách biểu diễn xấp xỉ gộp từng đoạn (PAA) .2 Độ đo xoắn thời gian động với biểu diễn dữ liệu đã thu giảm số chiều bằng PAA 28 3.3 Giải thuật gom cụm K-medoids cải tiến .4 Kỹ thuật lập trình đa luồng để tăng tốc tính toán độ đo DTW.
30 HỆ THỐNG GOM CỤM DỮ LIỆU CHUỖI THỜI GIAN .2 Hướng giải quyết .1 Kỹ thuật tính khoảng cách PDTW.2 Kỹ thuật khởi tạo trung tâm cụm của giải thuật K-medoids cải tiến .3 Kỹ thuật lập trình đa luồng.3 Kiến trúc chi tiết hệ thống .1 Module giao diện người dùng .2 Module xử lý chuỗi thời gian .3 Module gom cụm dữ liệu .4 Module đánh giá kết quả gom cụm .5 Module trực quan hóa dữ liệu và kết quả .1 Giới thiệu tập dữ liệu mẫu .2 Đánh giá thời gian thực thi của kỹ thuật lập trình đa luồng .3 Đánh giá chất lượng gom cụm và thời gian thực thi của hệ thống .1 Tập dữ liệu Face Four .2 Tập dữ liệu Trace .3 Tập dữ liệu CBF .4 Tập dữ liệu Heterogeneous .5 Tập dữ liệu CC .6 Tập dữ liệu Inline Skate. 62 GIẢI THUẬT GOM CỤM DỰA VÀO CÁC ĐỈNH MẬT ĐỘ .1 Giới thiệu giải thuật .2 Chi tiết giải thuật .3 Hiện thực giải thuật gom cụm dựa vào các đỉnh mật độ trong hệ thống .1 Tính toán mật độ cục bộ 𝝆 .2 Tính toán khoảng cách 𝜹 .3 Lựa chọn trung tâm cụm .4 Gán các đối tượng vào các cụm .1 So sánh thời gian thực thi của giải thuật Density Peaks với giải thuật K-medoids cải tiến .2 Thực nghiệm giải thuật gom cụm Density Peaks với các tập dữ liệu .3 So sánh chất lượng gom cụm của giải thuật Density Peaks với giải thuật K-medoids cải tiến .2 Những đóng góp của đề tài .3 Hướng phát triển. 75 TÀI LIỆU THAM KHẢO. 76 DANH SÁCH HÌNH VẼ Hình 1.1 Minh họa đường biểu diễn dữ liệu chuỗi thời gian chứng khoán .2 Minh họa quá trình gom cụm dữ liệu chuỗi thời gian .3 Minh họa gom cụm chuỗi thời gian dùng độ đo khoảng cách Euclid (trái) và độ đo DTW (phải) .1 (a) Tính khoảng cách theo Euclid và (b) tính khoảng cách theo DTW .2 Ma trận xoắn và đường xoắn tối ưu [10] .3 Đồ thị biểu diễn hai chuỗi thời gian .4 Ma trận xoắn tính DTW cho hai chuỗi thời gian.5 Quá trình gom cụm dùng K-means [11] .6 Các trường hợp thay thế của giải thuật K-medoids [11].7 Minh họa cách biến đổi dữ liệu theo các phương pháp DFT, DWT [30] .1 Minh họa cho kỹ thuật thu giảm số chiều dữ liệu .2 Chuỗi X và xấp xỉ PAA của nó X' .3 Hai chuỗi thời gian tương tự và sắp xếp khoảng cách xoắn giữa chúng.
Hình trên là sắp xếp bởi DTW. Hình dưới là sắp xếp PDTW trên biểu diễn thu giảm số chiều PAA của chúng.4 Minh họa kỹ thuật cải tiến tốc độ tính toán DTW .1 Lưu đồ giải thuật cho phương thức tính PAA .2 Lưu đồ giải thuật K-medoids cải tiến .
