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à cấu trúc của luận văn.1 Giới thiệu vấn đề: Ngày nay, cùng với sự bùng nổ của dữ liệu lớn (Big Data), một dạng dữ liệu thời gian đã xuất hiện và đang dần trở nên phổ biến hơn trong hầu hết các lĩnh vực như chứng khoán, thời tiết, y tế, môi trường … đó là dữ liệu chuỗi thời gian (time series data). Trong khi đó nhu cầu khám phá tri thức của con người từ những nguồn dữ liệu này ngày càng tăng đặt ra vấn đề phân tích dữ liệu dưới hình thức này mà tiêu biểu là bài toán gom cụm dữ liệu chuỗi thời gian, một quá trình học không giám sát (unsupervised learning) với mục đích rút trích ra những đặc trưng và tính chất quan trọng của dữ liệu để gom nhóm chúng thành những cụm (clusters) riêng biệt nhau nhằm phục vụ cho mục đích phân tích, rút trích ra các thông hữu ích. Như chúng ta đã biết, một bài toán gom cụm dữ liệu (clustering) luôn bao gồm 2 thành phần quan trọng mang tính cốt lõi đó là thuật toán gom cụm (clustering algorithm) và độ đo khoảng cách (measure distance calculation), một phương pháp tính toán khoảng cách giữa các cặp đối tượng dữ liệu.
Trước hết, về vấn đề độ đo khoảng cách, có độ đo khoảng cách thường được sử dụng nhất đó là độ đo khoảng cách Euclid (Euclidean distance) do tính đơn giản và dễ dùng của nó. Tuy nhiên, độ chính xác của các độ đo khoảng cách này còn tùy thuộc vào loại dữ liệu cần phân cụm. Vì vậy, trên thực tế, nhiều độ đo khoảng cách khác nhau ra đời để áp dụng tùy vào đặc điểm, tính chất của loại dữ liệu mà một trong số đó chính là độ đo xoắn thời gian động – DTW (Dynamic Time Warping) [1]. Độ đo khoảng cách Euclid tuy dễ hiện thực, dễ dùng nhưng lại thiếu sự linh hoạt đồng thời cho kết quả đo đạt không chính xác so với các độ đo chuyên biệt, đặc thù của từng loại dữ liệu, điển hình là dữ 1 GOM CỤM DỮ LIỆU CHUỖI THỜI GIAN BẰNG GIẢI THUẬT K-MEDOIDS CẢI TIẾN KẾT HỢP ĐỘ ĐO XOẮN THỜI GIAN ĐỘNG CẢI TIẾN PRUNED DTW liệu chuỗi thời gian.
Mặt khác, trong nhiều bối cảnh ứng dụng, chúng ta lại quan tâm đến yếu tố chất lượng gom cụm nhiều hơn là yếu tố thời gian thực thi việc gom cụm. Do đó, nhu cầu áp dụng khoảng cách DTW, cũng như các phương pháp tăng tốc cho chúng, vào bài toán gom cụm là rất thiết thực vì độ phức tạp tính toán cao của khoảng cách này cùng với số lượng cũng như độ dài (length of data) của loại dữ liệu chuỗi thời gian có xu hướng càng tăng cao như hiện nay sẽ làm vấn đề chi phí cho việc gom cụm trên loại dữ liệu đặc thù này vốn đã tốn kém lại càng tốn kém hơn.1 minh họa ảnh hưởng của độ đo khoảng cách với kết quả gom cụm.1: Ảnh hưởng của độ đo đối với kết quả gom cụm (Nguồn [23]). Vấn đề còn lại là thuật toán gom cụm. Như chúng ta đã biết, gom cụm là quá trình gom nhóm các đối tượng dữ liệu (data object), lại với nhau trên tiêu chí các đối tượng có đặc điểm, tính chất tương tự nhau thì sẽ được đặt vào cùng một nhóm và ngược lại các đối tượng khác nhau về đặc điểm và tính chất sẽ thuộc khác nhóm nhau.
Dựa vào điều này, không ít các giải thuật gom cụm hiệu quả đã xuất hiện và một trong số đó là thuật toán k-means. Thuật toán k-means dựa trên việc lặp lại việc cập nhật các điểm trung tâm được dẫn xuất (centroids) mới và tiến hành gom nhóm các đối tượng dựa 2 GOM CỤM DỮ LIỆU CHUỖI THỜI GIAN BẰNG GIẢI THUẬT K-MEDOIDS CẢI TIẾN KẾT HỢP ĐỘ ĐO XOẮN THỜI GIAN ĐỘNG CẢI TIẾN PRUNED DTW trên khoảng cách từ những đối tượng đó đến các điểm trung tâm này. Không may là, thuật toán k-means lại rất nhạy cảm với các điểm dị biệt (outlier). Mặc khác, dù k-means tỏ ra rất hiệu quả về mặt thời gian tính toán, nhưng khi áp dụng với một số loại dữ liệu, như: đồ thị (graph), hình ảnh (image), quỹ đạo 3 chiều (3-D trajectories), dữ liệu biểu diễn gen (gene expression),.
thì việc xác định các điểm trung tâm (centroid) của chúng là vô cùng khó khăn. Vì lý do này, thuật toán gom cụm dựa vào k-medoids (gọi vắn tắt là thuật toán k-medoids) đôi khi được sử dụng như một biện pháp thay thế. Về nguyên tắc hoạt động, thuật toán phân cụm k-medoids cũng tương tự thuật toán k- means, nhưng k-medoids sử dụng các điểm dữ liệu thực làm trung tâm cụm. Trong khi thuật toán k-means cố gắng giảm thiểu tổng sai số bình phương, thì k-medoids giảm thiểu tổng số điểm khác biệt giữa các điểm được phân cùng một cluster với một điểm được chỉ định làm trung tâm (điểm đại diện) của cụm đó.
Vì vậy nên thuật toán k- medoids ít bị ảnh hưởng bởi các điểm dị biệt (có thể là nhiễu dữ liệu – noise) hơn k- means. Một trong số những thuật toán phân cụm sử dụng k-medoids mạnh là thuật toán phân hoạch dựa vào medoids (gọi tắt là PAM – Partitioning Around Medoids). Tuy nhiên, thuật toán PAM có một bất lợi đó là nó hoạt động không hiệu quả trên các bộ dữ liệu lớn (large dataset), đồng nghĩa với thời gian chạy của thuật toán sẽ lâu. Vì vậy, cần thiết nên có thuật toán khác hiệu quả hơn hoặc một số cải tiến cho giải thuật này.2 Động cơ nghiên cứu Mặc dù sự ra đời DTW làm cho 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 hơn so với các độ đo khác cho loại dữ liệu chuỗi thời gian, nhưng với số lượng dữ liệu ngày càng lớn và việc tính khoảng cách DTW bằng phương pháp quy hoạch động là khá phức tạp làm cho việc gom cụm với khoảng cách DTW trở thành gánh nặng về mặt chi phí thời gian.
Vì vậy, việc phát triển các kỹ thuật tính toán thay thế kỹ thuật tính DTW trực tiếp 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 này khó có thể được áp dụng trực tiếp vào gom cụm nên 3 GOM CỤM DỮ LIỆU CHUỖI THỜI GIAN BẰNG GIẢI THUẬT K-MEDOIDS CẢI TIẾN KẾT HỢP ĐỘ ĐO XOẮN THỜI GIAN ĐỘNG CẢI TIẾN PRUNED DTW đối với một số bài toán trong thực tế thì việc gom cụm với DTW vẫn mất thời gian khá lâu. Như vậy, nhu cầu cần có một độ đo khoảng cách và thuật toán phân cụm tốt hơn luôn là mối quan tâm hàng đầu của các nhà nghiên cứu. Trong phạm vi đề tài này, chúng tôi sẽ giới thiệu một thuật toán gom cụm khác cũng dựa trên k-medoids với cách vận hành tương tự thuật toán k-means nhưng có sự cải tiến thêm để đạt được mục tiêu trước hết là sự đơn giản, hiệu quả, gọi là thuật toán k-medoids cải tiến (Park và Jun, 2009 [14]) và sử dụng độ đo khoảng cách xoắn thời gian động cải tiến (PrunedDTW)(Silva and Batista, 2016 [2]) dùng thay cho khoảng cách DTW trực tiếp (TrueDTW)[1], vốn có chi phí tính toán cao, đồng thời khảo sát sự kết hợp giữa chúng với nhau trong việc giải quyết bài toán gom cụm trên dữ liệu chuỗi thời gian.
Đặc điểm nổi bật của sự kết hợp chính là kỹ thuật gom cụm này đòi hỏi sự tính toán khoảng cách giữa các điểm dữ liệu chỉ một lần duy nhất lúc khởi tạo, cũng như cách áp dụng kỹ thuật khởi tạo trung tâm cụm ban đầu cho giải thuật gom cụm k-medoids. Kết quả thực nghiệm đã cho thấy chất lượng gom cụm khá chính xác, thậm chí tốt hơn đối với một số bộ dữ liệu cụ thể, so với giải thuật gom cụm k-means cải tiến [27] với độ đo Euclid. Thêm nữa, việc áp dụng độ đo PrunedDTW vào thuật toán phân cụm trên càng đảm bảo sự chính xác hơn cho kết quả đầu ra của bài toán phân cụm so với độ đo Euclid.3 Mục tiêu nghiên cứu Đề tài tập trung nghiên cứu và giải quyết bài toán phân cụm trên dữ liệu chuỗi thời gian. Các giải thuật được đề xuất trong nghiên cứu dùng để giải quyết các vấn đề của bài toán giảm chi phí cho quá trình tính toán ma trận xoắn DTW, ma trận khoảng cách toàn cặp (all-pairwise distance matrix) ban đầu và đồng thời tăng chất lượng của kết quả gom cụm, tạo tiền đề cho các bài toán sau đó như bài toán phân lớp (classification), một hình thức học có giám sát (supervised learning) và bài toán dự báo (prediction) làm việc hiệu quả hơn.
4 GOM CỤM DỮ LIỆU CHUỖI THỜI GIAN BẰNG GIẢI THUẬT K-MEDOIDS CẢI TIẾN KẾT HỢP ĐỘ ĐO XOẮN THỜI GIAN ĐỘNG CẢI TIẾN PRUNED DTW • Tìm hiểu cách tính ma trận DTW bằng phương pháp PrunedDTW: tuy ưu điểm của DTW đó là cho độ chính xác cao so với các độ đo Euclid, nhưng cách tính của nó khá phức tạp, do đó phát sinh chi phí lớn làm chậm quá trình tính toán. Do đó, đề tài sẽ tìm hiểu phương pháp PrunedDTW này. • Tìm hiểu giải thuật gom cụm k-medoids cải tiến: đây là thuật toán gom cụm dựa trên medoid, có nhiều ưu điểm, như: ít bị ảnh hưởng bởi nhiễu (noise) và các điểm dị biệt (outlier) để cho kết quả phân cụm tốt hơn, nhưng được cải tiến để có khả năng chạy nhanh xấp xỉ thuật toán k-means. • Hiện thực giải thuật gom cụm dữ liệu chuỗi thời gian k-medoids cải tiến.
• Hiện thực phương pháp tính độ đo khoảng cách PrunedDTW. • Phân tích, đánh giá độ hiệu quả của sự kết hợp của hai giải thuật k-medoids cải tiến và PrunedDTW bằng cách so sánh chất lượng phân cụm với phương pháp phân cụm k-means cải tiến [27] với độ đo Euclid trên các tập dữ liệu mẫu.