CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI Chương này sẽ trình bày về vấn đề mà đề tài tập trung nghiên cứu, sơ lược cơ sở lý thuyết, động cơ thực hiện và mục tiêu của đề tài,. Ngoài ra, chúng tôi cũng sẽ tóm lược các kết quả đã đạt được trong quá trình nghiên cứu, thực nghiệm, đồng thời giới thiệu cấu trúc của luận văn. Đối tượng nghiên cứu 1. Dữ liệu chuỗi thời gian Dữ liệu chuỗi thời gian (Time Series) là một dãy các điểm dữ liệu được liệt kê theo thứ tự thời gian.
Thông thường, mỗi điểm dữ liệu được thu thập tại những thời điểm cách đều nhau. Dữ liệu chuỗi thời gian có thể được biểu diễn như sau [7]: Một chuỗi thời gian T là chuỗi trị số thực, mỗi trị số biểu diễn một giá trị đo tại những thời điểm cách đều nhau: T = t1, t2,. Hơn nữa, một chuỗi thời gian có thể được xem như là một đối tượng nhiều chiều trong không gian metric. Dữ liệu chuỗi thời gian phổ biến ở rất nhiều lĩnh vực như kỹ thuật, tài chính, kinh tế, y khoa, sinh học, địa lý, khí tượng thủy văn,.
Ví dụ: giá đóng cửa hàng ngày của một cổ phiếu trên thị trường chứng khoán, dữ liệu về lượng mưa hàng tháng tại một khu vực,. dưới đây trình bày đường biểu diễn một chuỗi thời gian.2 Gom cụm dữ liệu Gom cụm (clustering) là một kỹ thuật trong lĩnh vực khai phá dữ liệu, nhằm tìm kiếm, phát hiện các cụm, các mẫu dữ liệu tự nhiên, tiềm ẩn và quan trọng trong tập dữ liệu lớn để từ đó cung cấp thông tin, tri thức cho việc ra quyết định. Có rất nhiều định nghĩa khác nhau về kỹ thuật gom cụm, nhưng về bản chất, đó là một quá trình tìm cách gom, nhóm các đối tượng, các loại dữ liệu không có nhãn 1 LUẬN VĂN CAO HỌC – Gom cụm dữ liệu chuỗi thời gian dựa trên nguyên lý MDL (unlabelled data) đã cho vào các cụm (cluster), sao cho các đối tượng trong cùng một cụm thì tương tự nhau (similar) và các đối tượng khác cụm thì không tương tự (dissimilar) hay sai biệt nhau [2]. Điều này được minh họa với tập dữ liệu hai chiều như hình 1.
Đường biểu diễn một chuỗi thời gian Hình 1. Quá trình gom cụm 2 LUẬN VĂN CAO HỌC – Gom cụm dữ liệu chuỗi thời gian dựa trên nguyên lý MDL 1. Sơ lược về nguyên lý MDL Nguyên lý MDL (Minimum Description Length Principle) là một khái niệm quan trong trong Lý thuyết thông tin. Đây là một phương pháp suy luận quy nạp xuất hiện khá gần đây, nguyên lý này đưa ra giải pháp tổng quát hóa để giải quyết bài toán lựa chọn mô hình (model selection) [3].
MDL dựa vào ý tưởng: các quy tắc bất kỳ trong dữ liệu có thể được dùng để nén dữ liệu, tức là mô tả dữ liệu dùng ít ký hiệu hơn số lượng các ký hiệu được dùng để mô tả dữ liệu theo đúng với nguyên gốc của nó. Nói cách khác, nếu chúng ta có thể nén dữ liệu càng nhiều, tức tìm thấy càng nhiều quy tắc ẩn trong nó, thì có thể “học” được càng nhiều từ chúng. Bài toán gom cụm dữ liệu chuỗi thời gian Việc gom cụm dữ liệu chuỗi thời gian cũng có cách thức và mục tiêu tương tự như bài toán gom cụm dữ liệu tổng quát bên trên, tức là: phân nhóm dữ liệu chuỗi thời gian dựa vào một độ đo tương tự hay độ đo khoảng cách nào đó. Đầu tiên, lựa chọn một độ đo tương tự thích hợp, rồi dùng các kỹ thuật như k-Means, gom cụm phân cấp,.
để tìm các cấu trúc cụm. Mặc dù đã và đang có rất nhiều nghiên cứu về gom cụm nói chung, tuy nhiên hầu hết các giải thuật khai phá dữ liệu và máy học cổ điển đều không làm việc tốt trên chuỗi thời gian do bởi cấu trúc độc đáo của chúng. Đặc biệt: số chiều nhiều, độ tương quan giữa các đặc tính rất cao, và số lượng nhiễu lớn, góp phần làm cho việc biểu diễn chuỗi thời gian là một thách thức khó khăn. Động cơ Bài toán gom cụm dữ liệu chuỗi thời gian đã và đang được sự quan tâm rất lớn trong cộng đồng nghiên cứu, rất nhiều bài báo nghiên cứu, các phương pháp thực hiện đã được đề xuất.
Các phương pháp này rất hữu ích trong việc tóm lược và trực quan hóa các tập dữ liệu lớn. Ngoài ra, gom cụm thường được dùng như là một quá trình phụ 3 LUẬN VĂN CAO HỌC – Gom cụm dữ liệu chuỗi thời gian dựa trên nguyên lý MDL trong các các giải thuật khai phá dữ liệu khác như là tìm kiếm tương tự, phân lớp và khai phá luật kết hợp. Các giải thuật gom cụm truyền thống, được sử dụng phổ biến như k-Means, thường yêu cầu các tham số đầu vào, kết quả lời giải không ổn định, phụ thuộc vào các khởi tạo ban đầu. Các nghiên cứu áp dụng nguyên lý MDL trong việc gom cụm các chuỗi con trong dữ liệu chuỗi thời gian mở ra khả năng phát triển một cách thức gom cụm các chuỗi thời gian riêng rẽ, đơn biến, phi tham số.
Mục tiêu Mục tiêu nghiên cứu của đề tài trên cơ sở dữ liệu chuỗi thời gian là nghiên cứu giải pháp gom cụm dữ liệu chuỗi thời gian dựa trên nguyên lý MDL với các nội dung sau: • Tìm hiểu nguyên lý MDL áp dụng trong việc gom cụm dữ liệu chuỗi thời gian. • Đề xuất mô hình gom cụm dựa hoàn toàn trên nguyên lý MDL. • Trực quan hóa kết quả gom cụm dữ liệu chuỗi thời gian. Tóm lược kết quả đạt được Chúng tôi đã đề xuất một mô hình gom cụm dựa trên nguyên lý MDL gồm hai giai đoạn: gom cụm sơ bộ và gom cụm chính thức.
Trong đó, ở giai đoạn gom cụm sơ bộ, chúng tôi bắt đầu bằng việc tạo cụm từ cặp motif bậc nhất của tập dữ liệu, gom nhóm các mẫu dữ liệu còn lại vào cụm khởi tạo và lặp lại cho đến hết dữ liệu. Kết quả của quá trình là các cụm dữ liệu chuỗi thời gian có tính chất nghiêm ngặt theo nguyên lý MDL. Ở giai đoạn gom cụm chính thức, chúng tôi sử dụng phương pháp gom cụm phân cấp gộp để trộn các cụm đã được tạo ra trước đó cho đến khi đạt đủ số lượng cụm đã được thiết lập theo hai cách tiếp cận khác nhau. Đặc biệt, tại giai đoạn này, chúng tôi đã đề xuất được phương pháp đo độ tương tự của các cụm dựa trên nguyên lý MDL, 4 LUẬN VĂN CAO HỌC – Gom cụm dữ liệu chuỗi thời gian dựa trên nguyên lý MDL không dựa vào các độ đo khoảng cách truyền thống.
Kết quả của toàn bộ quá trình này, các cụm dữ liệu được tạo ra một cách ổn định và phi tham số, các tiêu chí đánh giá chất lượng gom cụm cho thấy các chỉ số đánh giá khá tốt so với với các phương pháp gom cụm truyền thống. Cấu trúc luận văn Tổ chức của phần còn lại của luận văn gồm những phần 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. Phần này sẽ trình bày lý thuyết về độ đo khoảng cách, các tiêu chí đánh giá kết quả gom cụm, các vấn đề khác có liên quan đến nguyên lý MDL. Chương 3 là tổng quan về các công trình có liên quan.
Phần này trình bày về các nghiên cứu về gom cụm chuỗi thời gian, các công trình nghiên cứu áp dụng nguyên lý MDL trong gom cụm dữ liệu chuỗi thời gian. Chương 4 trình bày về hệ thống gom cụm dữ liệu chuỗi thời gian của chúng tôi. Chương 5 trình bày các kết quả thực nghiệm trên các tập dữ liệu chuỗi thời gian, qua đó đánh giá kết quả đạt được so với giải thuật k-Means truyền thống. Chương 6 gồm một số kết luận, đóng góp của đề tài và hướng phát triển.
5 LUẬN VĂN CAO HỌC – Gom cụm dữ liệu chuỗi thời gian dựa trên nguyên lý MDL CHƯƠNG 2: CƠ SỞ LÝ THUYẾT Chương này trình bày các mảng kiến thức có liên quan đến đề tài nghiên cứu như các độ đo tương tự, một số phương pháp gom cụm dữ liệu, tiêu chí đánh giá kết quả gom cụm và các vấn đề khác có liên quan đến nguyên lý MDL. Độ đo tương cận Khi thực hiện các kỹ thuật phân lớp, gom cụm các mẫu dữ liệu trong lĩnh vực nhận diện mẫu, khai phá dữ liệu, các mẫu cần được so sánh với nhau, theo một tiêu chuẩn nào đó. Nói cách khác, sự tương cận (proximity) của các mẫu với nhau cần được khám phá, sử dụng các độ đo tương cận (proximity measures). Một số độ đo tương tự (similarity) và sai biệt (dissimilarity) có thể được sử dụng, được mô tả dưới đây [2].
Độ đo khoảng cách Một độ đo khoảng cách được dùng để tìm sai biệt giữa các đại diện mẫu. Các mẫu càng tương tự nhau thì càng gần nhau hơn. Hàm khoảng cách có thể có tính metric hoặc phi metric (non-metric). Một độ đo có tính metric có các tính chất sau: 1.
Tính phản xạ tích cực (positive reflexivity): d(x, x) = 0 2. Tính đối xứng (symmetry): d(x, y) = d(y, x) 3. Thỏa bất đẳng thức tam giác (triangular inequality): d(x, y) ≤ d(x, z) + d(z, y) Độ đo khoảng cách metric được sử dụng phổ biến có tên gọi là Minkowski metric, có dạng: 1 𝑑𝑑 𝑚𝑚 𝑑𝑑 𝑚𝑚 (𝑋𝑋, 𝑌𝑌) = �� |𝑥𝑥𝑘𝑘 − 𝑦𝑦𝑘𝑘 |𝑚𝑚 � 𝑘𝑘=1 6 LUẬN VĂN CAO HỌC – Gom cụm dữ liệu chuỗi thời gian dựa trên nguyên lý MDL Trong đó: X, Y: các mẫu dữ liệu, có số chiều d. m: thành tố Minkowski Khi m = 1, độ đo trên được gọi là khoảng cách Manhattan hay khoảng cách L1.
Độ đo được sử dụng phổ biến nhất là độ đo khoảng cách Euclid (Euclidean distance) hay khoảng cách L2, khi đó m có giá trị là 2. Công thức tính khoảng cách có dạng: 𝑑𝑑2 (𝑋𝑋, 𝑌𝑌) = �(𝑥𝑥1 − 𝑦𝑦1 )2 + (𝑥𝑥2 − 𝑦𝑦2 )2 +. + (𝑥𝑥𝑑𝑑 − 𝑦𝑦𝑑𝑑 )2 Ngoài ra, còn có độ đo khoảng cách Mahalanobis, cũng là độ đo khoảng cách được sử dụng rộng rãi trong kỹ thuật phân lớp có giám sát và trong gom cụm dữ liệu. Độ đo này thích hợp trong trường hợp, nếu chúng ta quan tâm không chỉ là giá trị trung tâm (mean) của tập dữ liệu, mà còn độ phân tán của các mẫu dữ liệu trong tập dữ liệu.
Khi đó, các mẫu ngoại vi là các mẫu có khoảng cách Mahalanobis tới trung tâm lớn hơn rất nhiều so với các mẫu còn lại. Độ đo khoảng cách có trọng số Khi dữ liệu có các thuộc tính nào đó được đánh giá quan trọng hơn các thuộc tính khác, có thể thêm trọng số vào các giá trị của chúng.
