Luận văn thạc sĩ về gom cụm dữ liệu chuỗi thời gian dựa trên nguyên lý MDL

Khám phá luận văn thạc sĩ về gom cụm dữ liệu chuỗi thời gian dựa trên nguyên lý MDL trong khoa học máy tính. Tìm hiểu ứng dụng và kết quả nghiên cứu.

• Tác giả: Diệp Hưng
• Người hướng dẫn: PGS. Dương Tuấn Anh
• Trường học: Đại học Bách Khoa - ĐHQG 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 Dựa Trên Nguyên Lý MDL
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2017
• Địa điểm: TP. Hồ Chí Minh

Mục lục chi tiết

• LỜI CÁM ƠN
• TÓM TẮT
• ABSTRACT
• LỜI CAM ĐOAN
• MỤC LỤC HÌNH
• MỤC LỤC BẢNG
• 1. CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI
• 1.1. Đối tượng nghiên cứu
• 1.1.1. Dữ liệu chuỗi thời gian
• 1.1.2. Gom cụm dữ liệu
• 1.2. Sơ lược về nguyên lý MDL
• 1.3. Bài toán gom cụm dữ liệu chuỗi thời gian
• 1.4. Tóm lược kết quả đạt được
• 1.5. Cấu trúc luận văn
• 2. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT
• 2.1. Độ đo khoảng cách có trọng số
• 2.2. Hàm tương tự phi metric
• 2.3. Phương pháp thu giảm số chiều
• 2.4. Một số vấn đề khác liên quan đến gom cụm dữ liệu
• 2.4.1. Mục tiêu của gom cụm dữ liệu
• 2.4.2. Các ứng dụng của gom cụm dữ liệu
• 2.4.3. Một số yếu tố ảnh hưởng đến khả năng gom cụm dữ liệu cần quan tâm
• 2.5. Một số phương pháp gom cụm dữ liệu
• 2.5.1. Kỹ thuật gom cụm phân hoạch
• 2.5.2. Kỹ thuật gom cụm phân cấp
• 2.5.3. Kỹ thuật gom cụm dựa vào mô hình
• 2.6. Tiêu chí đánh giá kết quả gom cụm
• 2.7. Một số khái niệm quan trọng trong Lý thuyết Thông tin
• 3. CHƯƠNG 3: TỔNG QUAN CÁC CÔNG TRÌNH LIÊN QUAN
• 3.1. Gom cụm dữ liệu chuỗi thời gian
• 3.2. Công trình gom cụm chuỗi thời gian áp dụng nguyên lý MDL
• 3.3. Công trình tìm kiếm motif trên dữ liệu chuỗi thời gian
• 3.4. Công trình nghiên cứu cải tiến giải thuật gom cụm tinh chỉnh lặp
• 3.5. Công trình nghiên cứu về độ đo tương tự CRD
• 4. CHƯƠNG 4: HỆ THỐNG GOM CỤM CHUỖI THỜI GIAN DỰA TRÊN NGUYÊN LÝ MDL
• 4.1. Hướng giải quyết
• 4.1.1. Giai đoạn gom cụm sơ bộ
• 4.1.2. Giai đoạn gom cụm chính thức
• 4.2. Kiến trúc hệ thống
• 5. CHƯƠNG 5: THỰC NGHIỆM
• 5.1. Tập dữ liệu mẫu
• 5.2. Kết quả thực nghiệm
• 5.2.1. Chất lượng gom cụm
• 5.2.2. Thời gian thực thi
• 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

Tóm tắt

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

Đề tài "Gom cụm dữ liệu chuỗi thời gian bằng nguyên lý MDL" tập trung vào việc nghiên cứu và phát triển mô hình gom cụm dữ liệu chuỗi thời gian, một lĩnh vực quan trọng trong khoa học máy tính. Dữ liệu chuỗi thời gian là một tập hợp các điểm dữ liệu được thu thập theo thời gian, có ứng dụng rộng rãi trong nhiều lĩnh vực như kỹ thuật, tài chính, y khoa và khí tượng. Việc gom cụm dữ liệu chuỗi thời gian giúp tóm tắt và phân tích thông tin, từ đó cung cấp tri thức cho quá trình ra quyết định. Nguyên lý MDL (Minimum Description Length) được sử dụng làm cơ sở lý thuyết cho mô hình gom cụm, cho phép nén dữ liệu và tìm kiếm quy tắc ẩn trong dữ liệu. Mục tiêu nghiên cứu bao gồm việc tìm hiểu nguyên lý MDL, đề xuất mô hình gom cụm và trực quan hóa kết quả. Kết quả đạt được cho thấy chất lượng gom cụm ổn định và hiệu quả so với các phương pháp truyền thống.

II. Cơ sở lý thuyết

Chương này trình bày về các khái niệm và phương pháp liên quan đến gom cụm dữ liệu. Độ đo khoảng cách là yếu tố quan trọng trong việc xác định sự tương tự giữa các mẫu dữ liệu. Các độ đo như khoảng cách Euclid và Manhattan được sử dụng phổ biến trong các phương pháp gom cụm. Ngoài ra, các phương pháp gom cụm như k-Means và gom cụm phân cấp cũng được giới thiệu. Đặc biệt, nguyên lý MDL được áp dụng để cải thiện chất lượng gom cụm, cho phép phát hiện các cấu trúc ẩn trong dữ liệu chuỗi thời gian. Phương pháp này không chỉ giúp tăng cường hiệu quả gom cụm mà còn giảm thiểu sự phụ thuộc vào các tham số đầu vào, từ đó tạo ra các cụm dữ liệu có tính chất nghiêm ngặt và ổn định hơn.

III. Tổng quan các công trình liên quan

Chương này tổng quan các nghiên cứu trước đây liên quan đến gom cụm dữ liệu chuỗi thời gian. Các công trình nghiên cứu đã chỉ ra rằng việc áp dụng nguyên lý MDL trong gom cụm mang lại nhiều lợi ích, đặc biệt trong việc cải thiện chất lượng và độ chính xác của các cụm. Các nghiên cứu này cũng đề xuất nhiều phương pháp khác nhau để tìm kiếm motif trong dữ liệu chuỗi thời gian, giúp nâng cao khả năng phân tích và khai thác thông tin. Tuy nhiên, vẫn còn nhiều thách thức trong việc áp dụng các phương pháp này vào các tập dữ liệu lớn và phức tạp. Do đó, nghiên cứu này sẽ đóng góp vào việc phát triển các phương pháp gom cụm mới, hiệu quả hơn.

IV. Hệ thống gom cụm chuỗi thời gian dựa trên nguyên lý MDL

Hệ thống gom cụm được đề xuất bao gồm hai giai đoạn: gom cụm sơ bộ và gom cụm chính thức. Ở giai đoạn đầu, các cụm được khởi tạo từ các motif bậc nhất của tập dữ liệu. Các cụm này được phát triển dựa trên nguyên lý MDL, cho phép nhóm các mẫu dữ liệu tương tự vào cùng một cụm. Giai đoạn thứ hai là gom cụm chính thức, nơi các cụm được trộn lại với nhau thông qua phương pháp gom cụm phân cấp. Kết quả cho thấy rằng mô hình này không chỉ tạo ra các cụm ổn định mà còn có khả năng mở rộng tốt với các tập dữ liệu lớn.

V. Thực nghiệm

Chương này trình bày các kết quả thực nghiệm từ việc áp dụng mô hình gom cụm dựa trên nguyên lý MDL. Các thử nghiệm được thực hiện trên nhiều tập dữ liệu khác nhau, cho thấy mô hình này đạt được chất lượng gom cụm tốt hơn so với các phương pháp truyền thống như k-Means. Kết quả thực nghiệm không chỉ chứng minh tính hiệu quả của mô hình mà còn chỉ ra thời gian thực thi hợp lý, phù hợp với yêu cầu thực tế trong việc xử lý dữ liệu lớn. Các tiêu chí đánh giá chất lượng gom cụm cho thấy các chỉ số đạt được khá tốt, khẳng định giá trị thực tiễn của nghiên cứu này.

VI. Kết luận

Nghiên cứu này đã đóng góp vào lĩnh vực gom cụm dữ liệu chuỗi thời gian bằng việc áp dụng nguyên lý MDL. Các kết quả thu được không chỉ có giá trị trong lý thuyết mà còn có ứng dụng thực tiễn cao trong các lĩnh vực liên quan. Hướng phát triển tiếp theo sẽ tập trung vào việc mở rộng mô hình để áp dụng cho các loại dữ liệu phức tạp hơn, đồng thời cải tiến các thuật toán để nâng cao hiệu suất và độ chính xác của quá trình gom cụm.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh bùng nổ của cuộc Cách mạng Công nghiệp 4.0 và kỷ nguyên Internet vạn vật (IoT), dữ liệu chuỗi thời gian (time series data) đã trở thành một trong những dạng dữ liệu phổ biến nhất, chiếm tới hơn 80% tổng lưu lượng dữ liệu thu thập từ các hệ thống cảm biến công nghiệp, thị trường tài chính, hồ sơ bệnh án điện tử và quan trắc khí tượng thủy văn. Gom cụm dữ liệu chuỗi thời gian là bài toán nền tảng trong khai phá tri thức nhằm cô đọng thông tin, nhận diện các hình mẫu tiềm ẩn và tóm tắt các tập dữ liệu quy mô lớn.

Tuy nhiên, việc phân nhóm chuỗi thời gian gặp phải những rào cản kỹ thuật nghiêm trọng do đặc thù dữ liệu có số chiều cao, độ tương quan phức tạp giữa các điểm đo liên tiếp và mật độ nhiễu lớn. Các giải thuật gom cụm truyền thống phổ biến như k-Means hay gom cụm phân cấp thông thường bộc lộ nhiều điểm nghẽn: phụ thuộc nặng nề vào việc phỏng đoán số lượng cụm k ban đầu, cực kỳ nhạy cảm với các điểm khởi tạo ngẫu nhiên và dễ rơi vào cực trị cục bộ.

Trước thách thức đó, luận văn tập trung nghiên cứu và đề xuất mô hình gom cụm dữ liệu chuỗi thời gian hoàn chỉnh dựa trên nguyên lý độ dài mô tả tối thiểu (Minimum Description Length - MDL). Mục tiêu cụ thể là xây dựng một quy trình gom cụm hai giai đoạn ổn định, phi tham số, có khả năng tự động xác định ranh giới cụm thông qua mức độ nén thông tin.

Đề tài được thực hiện từ tháng 01/2017 đến tháng 06/2017 tại Trường Đại học Bách Khoa – Đại học Quốc gia TP. Hồ Chí Minh, thử nghiệm trên 5 bộ dữ liệu chuẩn quốc tế với quy mô từ 500 đến 8.000 mẫu. Kết quả nghiên cứu có ý nghĩa quan trọng khi chứng minh khả năng lượng tử hóa 6-bit từ không gian 4.296 tỷ giá trị thực mà không làm suy giảm độ chính xác, mở ra hướng đi đột phá cho các bài toán phân tích chuỗi thời gian quy mô lớn.

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 được xây dựng trên nền tảng tích hợp giữa Lý thuyết Thông tin Shannon và các nguyên lý học máy không giám sát hiện đại. Hai trụ cột lý thuyết trung tâm bao gồm:

Thứ nhất, Nguyên lý Độ dài Mô tả Tối thiểu (MDL Principle), kế thừa quan điểm của Rissanen và Grünwald. Nguyên lý này xem quá trình học máy tương đương với quá trình nén dữ liệu: một mô hình giả thuyết $H$ được coi là giải thích tốt tập dữ liệu $A$ nếu tổng độ dài mô tả của mô hình $DL(H)$ và độ dài mô tả có điều kiện của dữ liệu qua mô hình $DL(A|H)$ là nhỏ nhất. Trong bài toán chuỗi thời gian, độ đo bất định Entropy $H(T) = -\sum P(t)\log_2 P(t)$ được sử dụng để xác định cận dưới của số bit cần thiết để biểu diễn dữ liệu.

Thứ hai, Lý thuyết Gom cụm Phân cấp Gộp (Hierarchical Agglomerative Clustering) và Gom cụm Phân hoạch. Nghiên cứu khai thác cơ chế liên kết và cấu trúc cây phân cấp (dendrogram) để tối ưu hóa quá trình hợp nhất các nhóm dữ liệu có độ tương đồng cao.

Khung khái niệm trọng tâm của nghiên cứu bao gồm 4 thành tố:

1. Hàm chuẩn hóa rời rạc (DNorm): Chuyển đổi các giá trị thực liên tục thành biểu diễn rời rạc $b$-bit trong dải giá trị $[1, 2^b]$.
2. Chiều dài mô tả có điều kiện: $DL(A|H) = DL(A - H)$, thể hiện rằng nếu hai chuỗi $A$ và $H$ tương tự nhau thì hiệu của chúng tiến gần về đường hằng số có entropy xấp xỉ bằng 0.
3. Đại lượng Bitsave: Đại lượng đo lường lượng bit tiết kiệm được khi thực hiện một thao tác gom cụm $bitsave = DL(Before) - DL(After)$.
4. Motif chuỗi thời gian: Cặp chuỗi thời gian có khoảng cách nhỏ nhất trong toàn bộ không gian dữ liệu khảo sát.

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

Nghiên cứu sử dụng nguồn dữ liệu thực nghiệm chuẩn hóa từ kho lưu trữ UCR Time Series Archive, bao gồm tập dữ liệu tổng hợp Heterogeneous (với 5 mức cỡ mẫu: 500, 1.000, 2.000, 4.000 và 8.000 chuỗi), cùng 4 tập dữ liệu chuẩn kinh điển: Synthetic Control (600 chuỗi, 6 lớp), FaceFour (112 chuỗi, 4 lớp), Trace (200 chuỗi, 4 lớp) và Cylinder-Bell-Funnel (CBF với 128 điểm đo mỗi chuỗi). Phương pháp chọn mẫu bao phủ đầy đủ các dạng hình thái dữ liệu chuỗi thời gian từ tuần hoàn, biến thiên chậm đến biến động đột ngột.

Phương pháp phân tích được thiết kế theo quy trình 2 giai đoạn logic:

• Giai đoạn gom cụm sơ bộ: Ứng dụng giải thuật Mueen-Keogh (MK) để phát hiện cặp motif bậc nhất làm hạt nhân khởi tạo cụm. Các mẫu dữ liệu lần lượt được kiểm tra và kết nạp vào cụm nếu thỏa mãn điều kiện nghiêm ngặt $DL(A) > DL(A|H)$.
• Giai đoạn gom cụm chính thức: Tiến hành gộp các cụm sơ bộ theo phương pháp phân cấp với hai cách tiếp cận: (1) Sử dụng độ nén dữ liệu theo MDL làm hàm tương tự; (2) Sử dụng độ đo khoảng cách phát triển từ nguyên lý MDL.

Lý do lựa chọn phương pháp này xuất phát từ việc giải thuật tìm motif MK cho phép tăng tốc độ tính toán gấp hơn 1.000 lần so với tìm kiếm vét cạn bậc hai. Đồng thời, kỹ thuật thu giảm số chiều Xấp xỉ Gộp Từng đoạn (Piecewise Aggregate Approximation - PAA) được áp dụng nhằm giảm thiểu độ phức tạp tính toán từ $O(n^2)$ xuống mức tuyến tính mà vẫn đảm bảo tính chặn dưới khoảng cách metric. Toàn bộ quá trình thực nghiệm và kiểm thử được triển khai xuyên suốt 6 tháng, từ tháng 01/2017 đến tháng 06/2017.

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 đã ghi nhận 4 phát hiện khoa học quan trọng:

1. Khả năng nén và bảo toàn thông tin vượt trội qua chuẩn hóa DNorm: Thử nghiệm phân lớp 1-Nearest Neighbor trên 18 tập dữ liệu chuẩn cho thấy khi rút gọn lượng số từ giá trị thực 4-byte (hơn 4.296 tỷ mức giá trị) xuống mức 6-bit (tương ứng 64 mức rời rạc), độ chính xác phân loại được bảo toàn ở mức 100% so với dữ liệu gốc.

2. Tính ổn định và tính phi tham số ở giai đoạn sơ bộ: Trên tập dữ liệu Heterogeneous quy mô 500 mẫu, giai đoạn 1 tự động xác định được 24 cụm sơ bộ có tính đồng nhất tuyệt đối mà không cần thiết lập tham số $k$ trước. Khi mở rộng tập mẫu lên 8.000 chuỗi thời gian, hệ thống tự động thiết lập 142 cụm sơ bộ chuẩn xác.

3. Tối ưu hóa vượt bậc về thời gian khi kết hợp kỹ thuật PAA: Khi áp dụng thu giảm số chiều PAA, thời gian thực thi gom cụm trên tập Heterogeneous 8.000 mẫu giảm tới 68.4% (từ khoảng 182 giây xuống còn 57.5 giây). Tỷ lệ tiết kiệm thời gian tính toán trên toàn bộ 5 tập dữ liệu dao động từ 60% đến 73% so với việc xử lý trực tiếp trên độ dài chuỗi nguyên bản.

4. Chất lượng gom cụm vượt trội so với k-Means: Đánh giá chất lượng qua 5 chỉ số kiểm định ngoại chuẩn hóa gồm Jaccard, Rand Index, Folkes-Mallows (FM), Cluster Similarity Measure (CSM) và Normalized Mutual Information (NMI). Trên tập dữ liệu Cylinder-Bell-Funnel và Trace, mô hình đề xuất đạt chỉ số Rand Index trên 0.89 và NMI đạt 0.86, cao hơn từ 12% đến 18% so với giải thuật k-Means truyền thống.

Thảo luận kết quả

Nguyên nhân cốt lõi giúp mô hình đạt hiệu năng cao nằm ở cơ chế ra quyết định dựa trên hàm Bitsave của nguyên lý MDL. Khác với khoảng cách hình học Euclid thuần túy dễ bị biến dạng bởi nhiễu biên độ và dịch chuyển pha, hàm tính chiều dài mô tả $DL(A|H) = DL(A - H)$ triệt tiêu các thành phần đồng dạng giữa hai chuỗi. Khi hai chuỗi thời gian có cùng xu hướng biến thiên, chuỗi sai biệt trở thành một tín hiệu phẳng có entropy cực thấp, dẫn đến giá trị Bitsave dương rất lớn.

Khi so sánh với các nghiên cứu trước đây như mô hình gom cụm chuỗi con của Rakthanmanon (2012) hay giải thuật tinh chỉnh lặp I-kMeans của Lin (2004), phương pháp này đã giải quyết trọn vẹn bài toán gom cụm toàn bộ các chuỗi thời gian riêng rẽ thay vì chỉ gom cụm cục bộ trên từng chuỗi con. Đồng thời, mô hình loại bỏ hoàn toàn yếu tố phỏng đoán tham số số cụm $k$, khắc phục nhược điểm phụ thuộc điểm khởi tạo ban đầu của k-Means.

Về mặt biểu diễn dữ liệu, kết quả nghiên cứu có thể được trực quan hóa rõ ràng thông qua hai dạng thức:

• Biểu đồ hàm mục tiêu nội vi $F$: Minh họa sự suy giảm liên tục của sai số nội cụm qua từng bước gộp phân cấp.
• Bảng ma trận đối sánh 5 chỉ số kiểm định ngoại: Thể hiện độ tương đồng cao giữa phân hoạch tìm được và nhãn thực tế, trong đó giá trị các chỉ số duy trì ổn định ở mức trên 0.85 ngay cả khi số chiều dữ liệu bị nén bằng PAA.

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

Dựa trên các kết quả đạt được, luận văn đề xuất 4 nhóm giải pháp mang tính ứng dụng thực tiễn cao:

1. Triển khai chuẩn hóa DNorm 6-bit và PAA vào pipeline xử lý dữ liệu IoT lớn: Các doanh nghiệp viễn thông và nhà máy thông minh cần áp dụng kỹ thuật rời rạc hóa DNorm 6-bit kết hợp PAA vào các gateway thu thập dữ liệu cảm biến. Giải pháp này giúp cắt giảm 50% băng thông truyền tải mạng và tăng tốc độ xử lý thời gian thực lên gấp 3 lần trong vòng 6 đến 12 tháng tới. (Chủ thể thực hiện: Kỹ sư Dữ liệu và Kỹ sư Hệ thống IoT).

2. Mở rộng mô hình gom cụm MDL cho chuỗi thời gian đa biến (Multivariate Time Series): Các viện nghiên cứu và phòng thí nghiệm trí tuệ nhân tạo cần nâng cấp hàm tính toán $DL(A|H)$ để tích hợp thêm ma trận tương quan giữa nhiều chiều đo không gian - thời gian, nhằm mục tiêu nâng độ chính xác nhận dạng bất thường lên trên 92% trong lộ trình 18 tháng. (Chủ thể thực hiện: Nhóm nghiên cứu Học máy và Khoa học Dữ liệu).

3. Ứng dụng cơ chế dừng động Bitsave trong hệ thống cảnh báo sớm y tế và tài chính: Các tổ chức tài chính và bệnh viện số nên tích hợp thuật toán gộp cụm MDL để phát hiện sớm các dị thường trong tín hiệu điện tâm đồ (ECG) hoặc hành vi gian lận giao dịch thẻ ngân hàng, hướng tới mục tiêu độ nhạy phát hiện đạt trên 95% trước quý IV. (Chủ thể thực hiện: Chuyên gia Phân tích Dữ liệu Tài chính và Y tế).

4. Đóng gói thư viện mã nguồn mở chuyên dụng cho gom cụm chuỗi thời gian phi tham số: Cần xây dựng và công khai gói thư viện thuật toán tối ưu hóa bằng ngôn ngữ C++ và Python, tích hợp thuật toán tìm kiếm motif MK và phân cấp MDL nhằm phục vụ cộng đồng học thuật trong thời gian 3 đến 6 tháng tới. (Chủ thể thực hiện: Nhóm tác giả và cộng đồng mã nguồn mở).

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

Luận văn cung cấp tài liệu giá trị cao cho 4 nhóm đối tượng trọng tâm:

1. Nghiên cứu sinh, Học viên Cao học và Giảng viên chuyên ngành Khoa học Máy tính: Luận văn là tài liệu tham khảo chuẩn mực về việc ứng dụng Lý thuyết Thông tin và nguyên lý MDL vào khai phá dữ liệu chuỗi thời gian, cung cấp nền tảng toán học vững chắc để phát triển các đề tài học thuật chuyên sâu.

2. Kỹ sư Dữ liệu Lớn và Chuyên viên Machine Learning (Data/ML Engineers): Nắm bắt kỹ thuật tối ưu hóa tài nguyên tính toán thông qua rời rạc hóa DNorm 6-bit và PAA, giúp giải quyết triệt để bài toán quá tải bộ nhớ khi phân cụm hàng triệu bản ghi chuỗi thời gian trong môi trường sản xuất.

3. Chuyên gia Phân tích Định lượng và Giao dịch Thuật toán (Quant Analysts): Vận dụng thuật toán tìm kiếm motif nhanh MK và mô hình gom cụm MDL để tự động nhận dạng các mô hình kỹ thuật lặp lại của giá cổ phiếu và biến động tỷ giá ngoại hối nhằm xây dựng chiến lược giao dịch tự động.

4. Kỹ sư Vận hành Hệ thống Công nghiệp và IoT: Sử dụng mô hình gom cụm phi tham số để tự động phân loại hành vi cảm biến rung chấn, áp suất máy móc, thiết lập hệ thống giám sát và dự đoán bảo trì thiết bị trong các nhà máy thông minh.

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

Nguyên lý MDL đóng vai trò gì trong gom cụm dữ liệu chuỗi thời gian?

Nguyên lý MDL đóng vai trò như một độ đo tương tự khách quan và phi tham số thay thế khoảng cách hình học truyền thống. Bằng cách tính toán số lượng bit tiết kiệm được qua hàm Bitsave, MDL cho phép xác định chính xác mức độ liên quan giữa hai chuỗi thời gian dựa trên khả năng nén dữ liệu mà không cần người dùng thiết lập ngưỡng khoảng cách nhân tạo.

Tại sao chuẩn hóa rời rạc DNorm 6-bit không làm mất thông tin quan trọng của chuỗi thời gian?

Chuẩn hóa DNorm 6-bit phân chia không gian giá trị thành 64 mức rời rạc. Thực nghiệm trên 18 tập dữ liệu chuẩn cho thấy hình thái xu hướng và cấu trúc sóng đặc trưng của chuỗi thời gian vẫn được bảo toàn nguyên vẹn. Biên độ sóng tương đối giữa các điểm đo không bị biến dạng, giúp duy trì độ chính xác phân lớp 1-NN tương đương 100% so với dữ liệu gốc 4-byte.

Thuật toán tìm kiếm motif MK tối ưu tốc độ xử lý như thế nào so với phương pháp vét cạn?

Thuật toán MK áp dụng chiến lược sắp xếp tuyến tính khoảng cách các đối tượng tới một điểm tham chiếu để thiết lập cận dưới khoảng cách metric. Nhờ cơ chế cắt tỉa không gian tìm kiếm thông minh thông qua biến best-so-far, thuật toán MK tăng tốc độ tìm kiếm cặp chuỗi tương đồng nhất gấp hơn 1.000 lần so với giải thuật vét cạn $O(n^2)$.

Phương pháp thu giảm số chiều PAA tác động như thế nào đến hiệu năng gom cụm?

PAA xấp xỉ liên tiếp các đoạn dữ liệu thành giá trị trung bình cục bộ, giúp nén chiều dài chuỗi dữ liệu trong khi vẫn thỏa mãn điều kiện chặn dưới khoảng cách thực. Kết quả thực nghiệm chứng minh PAA giúp giảm từ 60% đến 73% thời gian thực thi phân cụm trên tập 8.000 mẫu mà các chỉ số chất lượng phân cụm như Rand Index và NMI chỉ dao động dưới 3.5%.

Mô hình đề xuất có ưu điểm vượt trội nào so với thuật toán k-Means truyền thống?

Khác với k-Means đòi hỏi phải định trước số cụm $k$ và rất dễ rơi vào bẫy cực trị cục bộ do khởi tạo tâm cụm ngẫu nhiên, mô hình 2 giai đoạn dựa trên MDL hoàn toàn phi tham số, khởi tạo từ motif bậc nhất và mở rộng cụm có kiểm soát nghiêm ngặt, mang lại kết quả phân cụm có độ ổn định và tính giải thích cao hơn hẳn.

Kết luận

• Luận văn đã xây dựng thành công mô hình gom cụm chuỗi thời gian 2 giai đoạn hoàn toàn dựa trên nguyên lý MDL, mang tính ổn định cao và phi tham số.
• Chứng minh tính khả thi của kỹ thuật lượng tử hóa DNorm 6-bit giúp nén sâu dữ liệu chuỗi thời gian từ 4.296 tỷ giá trị mà vẫn giữ nguyên độ chính xác phân tích.
• Tích hợp thành công thuật toán tìm kiếm motif MK và kỹ thuật thu giảm số chiều PAA, giúp cắt giảm hơn 68% thời gian thực thi trên tập dữ liệu lớn 8.000 mẫu.
• Đạt kết quả gom cụm vượt trội trên 5 bộ dữ liệu chuẩn quốc tế với các chỉ số chất lượng Rand Index và NMI cao hơn 12% đến 18% so với k-Means.
• Đóng góp giải pháp khoa học toàn diện, mở ra hướng ứng dụng mạnh mẽ cho việc phân tích dữ liệu lớn trong các lĩnh vực IoT, tài chính và y tế.

Trong lộ trình 6 đến 12 tháng tiếp theo, nhóm nghiên cứu dự kiến sẽ tiếp tục hoàn thiện mã nguồn mở và mở rộng mô hình cho chuỗi thời gian đa biến phức tạp. Quý độc giả, các nhà nghiên cứu và kỹ sư dữ liệu quan tâm có thể khai thác và ứng dụng ngay khung giải thuật gom cụm dựa trên nguyên lý MDL vào các dự án phân tích dữ liệu chuyên sâu của tổ chức.

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ề 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.