Luận văn thạc sĩ: Gom cụm dữ liệu chuỗi thời gian dựa vào điểm cực đại mật độ

Luận văn thạc sĩ nghiên cứu máy tính gom cụm dữ liệu chuỗi thời gian dựa vào các điểm cực đại mật độ, đánh giá hiện trạng, phân tích vấn đề, đề xuất biện pháp hoàn thiện trong

• Tác giả: Phan Thị Thanh Phương
• 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 Dựa Vào Các Điểm Cực Đại Mật Độ
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2018
• Địa điểm: Thành phố Hồ Chí Minh

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CÁM ƠN
• TÓM TẮT
• ABSTRACT
• DANH SÁCH HÌNH VÀ BẢNG
• 1. CHƯƠNG 1: TỔNG QUAN VỀ ĐỀ 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. Khai phá dữ liệu chuỗi thời gian
• 1.1.3. Gom cụm dữ liệu
• 1.2. BÀI TOÁN GOM CỤM TRONG DỮ LIỆU CHUỖI THỜI GIAN
• 1.3. PHƯƠNG PHÁP NGHIÊN CỨU
• 1.4. Ý NGHĨA CỦA ĐỀ TÀI
• 1.5. NHỮNG KẾT QUẢ ĐẠT ĐƯỢC CỦA LUẬN VĂN
• 1.6. CẤU TRÚC 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. Độ đo xoắn thời gian động
• 2.2. BÀI TOÁN GOM CỤM TRONG DỮ LIỆU CHUỖI THỜI GIAN
• 2.3. CÁC TIÊU CHÍ ĐÁNH GIÁ GOM CỤM
• 2.4. CÁC GIẢI THUẬT GOM CỤM DỮ LIỆU THƯỜNG SỬ DỤNG
• 2.4.1. Giải thuật gom cụm phân cấp
• 2.4.2. Giải thuật gom cụm phân hoạch
• 3. CHƯƠNG 3: TỔNG THUẬT CÁC CÔNG TRÌNH LIÊN QUAN
• 3.1. GOM CỤM DỮ LIỆU CHUỖI THỜI GIAN
• 3.2. GIẢI THUẬT K-MEANS
• 3.3. CÁC PHƯƠNG PHÁP CHỌN SỐ CỤM K TỐI ƯU NHẤT
• 3.4. GIẢI THUẬT GOM CỤM DỮ LIỆU DỰA VÀO CÁC ĐIỂM CỰC ĐẠI MẬT ĐỘ TRÊN DỮ LIỆU CHUỖI THỜI GIAN
• 3.5. ƯỚC LƯỢNG MẬT ĐỘ KERNEL KIỂU GAUSS
• 3.6. ƯỚC LƯỢNG MẬT ĐỘ DỰA TRÊN K-NEAREST NEIGHBORS
• 3.7. ÁP DỤNG ĐỘ ĐO XOẮN THỜI GIAN ĐỘNG VÀO GIẢI THUẬT GOM CỤM DỮ LIỆU DỰA VÀO CÁC ĐIỂM CỰC ĐẠI MẬT ĐỘ
• 4. CHƯƠNG 4: PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
• 4.1. HƯỚNG GIẢI QUYẾT
• 4.1.1. Tính toán mật độ cục bộ
• 4.1.2. Tính toán khoảng cách
• 4.1.3. Lựa chọn trung tâm cụm
• 4.1.4. Gán các đối tượng vào các cụm
• 5. CHƯƠNG 5: KẾT QUẢ THỰC NGHIỆM
• 5.1. MÔI TRƯỜNG THỰC NGHIỆM
• 5.2. TẬP DỮ LIỆU MẪU
• 5.3. KẾT QUẢ THỰC NGHIỆM
• 5.3.1. Tập dữ liệu Symbol
• 5.3.2. Tập dữ liệu CBF
• 5.3.3. Tập dữ liệu Trace
• 5.3.4. Tập dữ liệu FaceFour
• 5.3.5. Tập dữ liệu Inline Skate
• 5.3.6. Tập dữ liệu Italy Power Demand
• 5.3.7. So sánh giải thuật đã cải tiến khi áp dụng độ đo Euclid và DTW
• 5.4. NHẬN XÉT CHUNG
• 6. CHƯƠNG 6: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
• 6.1. NHỮNG KẾT QUẢ ĐẠT ĐƯỢC CỦA ĐỀ TÀI
• 6.2. HƯỚNG PHÁT TRIỂN CỦA ĐỀ TÀI
• 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. Tổng quan về đề tài

Đề tài 'Gom cụm dữ liệu chuỗi thời gian bằng điểm cực đại mật độ' tập trung vào việc nghiên cứu và phát triển các phương pháp gom cụm dữ liệu chuỗi thời gian. Dữ liệu chuỗi thời gian là một dãy các điểm dữ liệu được thu thập theo thứ tự thời gian, có ứng dụng rộng rãi trong nhiều lĩnh vực như kinh tế, tài chính, y khoa, và sinh học. Việc gom cụm dữ liệu là một kỹ thuật quan trọng trong khai phá dữ liệu, nhằm phát hiện các mẫu và cấu trúc trong tập dữ liệu lớn. Đề tài này sẽ áp dụng giải thuật Density Peak để thực hiện việc gom cụm, với mục tiêu tạo ra các cụm dữ liệu ổn định và chất lượng cao.

1.1 Đối tượng nghiên cứu

Đối tượng nghiên cứu chính của đề tài là dữ liệu chuỗi thời gian. Dữ liệu này thường được sử dụng trong các lĩnh vực như tài chính, y tế, và sinh học. Việc phân tích và gom cụm dữ liệu chuỗi thời gian gặp nhiều thách thức do tính chất phức tạp và đa chiều của nó. Đề tài sẽ tìm hiểu các phương pháp gom cụm hiện có và đề xuất mô hình mới dựa trên các điểm cực đại mật độ, nhằm cải thiện hiệu quả và độ chính xác trong việc phân nhóm dữ liệu.

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

Phương pháp nghiên cứu được áp dụng trong đề tài bao gồm việc tìm hiểu và áp dụng giải thuật Density Peak cho việc gom cụm dữ liệu chuỗi thời gian. Đề tài sẽ sử dụng đo lường Euclid để tính toán khoảng cách giữa các điểm dữ liệu, từ đó xác định các cụm. Một trong những điểm nổi bật của phương pháp này là khả năng xử lý các dữ liệu có hình dạng phức tạp mà các phương pháp truyền thống như K-means không thể thực hiện. Việc cắt tỉa tính toán lân cận gần nhất từ danh sách mật độ cao hơn cũng sẽ được thực hiện để tăng tốc độ xử lý.

2.1 Giải thuật Density Peak

Giải thuật Density Peak được đề xuất bởi Rodriguez và Laio vào năm 2014, cho phép gom cụm dữ liệu mà không cần phải xác định số lượng cụm trước. Phương pháp này dựa trên việc xác định các điểm cực đại mật độ trong không gian dữ liệu, từ đó phân nhóm các điểm dữ liệu xung quanh chúng. Điều này giúp tạo ra các cụm có hình dạng tùy ý, phù hợp với đặc điểm của dữ liệu chuỗi thời gian.

III. Kết quả thực nghiệm

Kết quả thực nghiệm cho thấy rằng mô hình gom cụm dựa trên các điểm cực đại mật độ cho kết quả ổn định và chất lượng cao. Các tiêu chí đánh giá chất lượng gom cụm cho thấy các chỉ số đánh giá tốt hơn so với các phương pháp gom cụm truyền thống. Việc áp dụng giải thuật này trên nhiều tập dữ liệu mẫu đã chứng minh tính khả thi và hiệu quả của nó trong việc xử lý dữ liệu chuỗi thời gian. Các cụm dữ liệu được tạo ra không chỉ chính xác mà còn có thể được trực quan hóa một cách dễ dàng.

3.1 So sánh với các phương pháp khác

Khi so sánh với các phương pháp gom cụm khác như K-means, giải thuật dựa trên điểm cực đại mật độ cho thấy ưu thế vượt trội trong việc xử lý các dữ liệu có hình dạng phức tạp. Kết quả thực nghiệm cho thấy rằng mô hình này không chỉ cải thiện độ chính xác mà còn giảm thiểu thời gian tính toán. Điều này mở ra hướng đi mới cho việc áp dụng các phương pháp gom cụm trong khai thác dữ liệu và học máy.

IV. Ý nghĩa và ứng dụng thực tiễn

Đề tài không chỉ có giá trị lý thuyết mà còn có ứng dụng thực tiễn cao trong nhiều lĩnh vực. Việc gom cụm dữ liệu chuỗi thời gian có thể hỗ trợ trong việc phát hiện các xu hướng, mẫu hình trong dữ liệu, từ đó giúp các nhà nghiên cứu và doanh nghiệp đưa ra quyết định chính xác hơn. Các ứng dụng có thể bao gồm phân tích tài chính, dự đoán xu hướng tiêu dùng, và phát hiện bất thường trong dữ liệu y tế.

4.1 Ứng dụng trong các lĩnh vực

Các kết quả đạt được từ nghiên cứu có thể được áp dụng trong nhiều lĩnh vực khác nhau như tài chính, y tế, và sinh học. Ví dụ, trong lĩnh vực tài chính, việc phân tích dữ liệu chuỗi thời gian có thể giúp dự đoán giá cổ phiếu, trong khi trong y tế, nó có thể hỗ trợ trong việc phát hiện các bất thường trong dữ liệu sức khỏe. Điều này cho thấy tầm quan trọng của việc phát triển các phương pháp gom cụm hiệu quả cho dữ liệu chuỗi thời gian.

Nội dung chính

Tổng quan nghiên cứu

Trong kỷ nguyên chuyển đổi số và Internet vạn vật (IoT), dữ liệu chuỗi thời gian chiếm hơn 70% tổng khối lượng dữ liệu phát sinh liên tục trong các lĩnh vực quan trọng như tài chính, y tế, khí tượng và vận hành lưới điện thông minh. Khai phá dữ liệu chuỗi thời gian đóng vai trò then chốt trong việc trích xuất tri thức, phát hiện bất thường và hỗ trợ ra quyết định. Tuy nhiên, phân tích gom cụm chuỗi thời gian đang đối mặt với những thách thức lớn do số chiều dữ liệu cao, độ tương quan thời gian phức tạp và độ nhiễu lớn. Các giải thuật gom cụm phân hoạch truyền thống như K-means thường xuyên rơi vào điểm cực trị cục bộ, phụ thuộc nặng nề vào việc khởi tạo tâm cụm ngẫu nhiên và chỉ nhận diện tốt các cụm dạng hình cầu đồng đều.

Nghiên cứu của tác giả Phan Thị Thanh Phương, dưới sự hướng dẫn khoa học của Phó Giáo sư Tiến sĩ Dương Tuấn Anh tại Trường Đại học Bách Khoa – Đại học Quốc gia Thành phố Hồ Chí Minh (hoàn thành tháng 06/2018), tập trung giải quyết triệt để bài toán trên. Mục tiêu cụ thể của luận văn là nghiên cứu, hiện thực và cải tiến giải thuật gom cụm dựa vào các điểm cực đại mật độ (Density Peaks Clustering - DPC) kết hợp độ đo khoảng cách Euclid trên dữ liệu chuỗi thời gian. Đề tài xây dựng cơ chế ước lượng khoảng cách ngưỡng cắt thông qua hàm kernel Gauss tự động và tích hợp kỹ thuật cắt tỉa không gian tìm kiếm nhằm tăng tốc độ xử lý.

Nghiên cứu được thực nghiệm toàn diện trên 6 tập dữ liệu chuẩn thuộc kho lưu trữ UCR Time Series Data Mining Archive trong giai đoạn từ tháng 01/2018 đến tháng 06/2018. Kết quả cho thấy mô hình cải tiến giúp nâng cao độ chính xác phân cụm từ 15% đến 25% so với K-means trên các chỉ số đo lường học thuật, đồng thời cắt giảm hơn 35% chi phí tính toán khoảng cách. Công trình mang lại ý nghĩa khoa học sâu sắc và giá trị ứng dụng thực tiễn cao cho việc xử lý dữ liệu cảm biến 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

Luận văn xây dựng trên nền tảng lý thuyết gom cụm dựa vào các điểm cực đại mật độ do Rodriguez và Laio đề xuất năm 2014, kết hợp với lý thuyết ước lượng mật độ phi tham số bằng hàm Kernel Gauss của Mehmood và cộng sự năm 2016. Khung mô hình hoạt động dựa trên giả định cốt lõi: các tâm cụm thực sự luôn có mật độ cục bộ cao hơn các điểm lân cận xung quanh và duy trì khoảng cách tương đối lớn đối với bất kỳ điểm nào có mật độ cao hơn.

Các khái niệm và thành phần toán học trọng tâm bao gồm:

• Mật độ cục bộ: Số lượng các điểm lân cận nằm trong phạm vi khoảng cách ngưỡng cắt, được tính toán thông qua hàm suy giảm Gaussian Kernel để đảm bảo tính liên tục và giảm thiểu độ nhạy tham số.
• Khoảng cách lân cận mật độ cao hơn: Khoảng cách ngắn nhất từ một điểm dữ liệu đến một điểm khác có giá trị mật độ cục bộ lớn hơn nó; riêng điểm có mật độ cực đại toàn cục sẽ nhận khoảng cách bằng giá trị khoảng cách lớn nhất trong toàn bộ không gian.
• Đồ thị quyết định mật độ: Không gian biểu diễn trực quan tương quan giữa mật độ cục bộ và khoảng cách lân cận, hỗ trợ xác định tâm cụm vượt trội một cách trực quan và tự động loại bỏ các điểm nhiễu ngoại biên.
• Độ đo khoảng cách chuỗi thời gian: So sánh đặc tính không gian giữa độ đo Euclid truyền thống với độ phức tạp tuyến tính và độ đo xoắn thời gian động (DTW) với độ phức tạp bậc hai.

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 dữ liệu quốc tế UCR Time Series Data Mining Archive. Tổng cỡ mẫu thử nghiệm bao gồm 2.465 chuỗi thời gian phân bổ trên 6 bộ dữ liệu đại diện cho các miền ứng dụng đa dạng: Symbol (998 chuỗi, độ dài 398 điểm, 6 cụm), Cylinder-Bell-Funnel (150 chuỗi, độ dài 128 điểm, 3 cụm), Trace (100 chuỗi, độ dài 275 điểm, 4 cụm), FaceFour (88 chuỗi, độ dài 350 điểm, 4 cụm), Inline Skate (100 chuỗi, độ dài 1.882 điểm, 7 cụm) và Italy Power Demand (1.029 chuỗi, độ dài 24 điểm, 2 cụm).

Phương pháp chọn mẫu áp dụng kỹ thuật lấy mẫu phân tầng ngẫu nhiên có kiểm soát từ nguồn chuẩn UCR, đảm bảo cấu trúc phân lớp nguyên bản của dữ liệu gốc để phục vụ đánh giá kiểm định ngoại vi.

Lý do lựa chọn phương pháp phân tích: Luận văn lựa chọn khoảng cách Euclid kết hợp giải thuật cắt tỉa ma trận chặn trên (UBMatrix) và ma trận chặn dưới (LBMatrix) thay vì tính toán toàn bộ khoảng cách cặp. Phương pháp này đảm bảo duy trì độ chính xác nhận dạng hình dạng sóng tương đương trong khi giảm thiểu tối đa tài nguyên bộ nhớ và thời gian CPU. Toàn bộ chương trình được lập trình và chạy thực nghiệm 100 lần liên tiếp trên môi trường MATLAB 2016a, vi xử lý Intel Core i7-4510U xung nhịp 2,6GHz và bộ nhớ RAM 8GB để lấy kết quả trung bình thống kê tin cậy.

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

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

Quá trình phân tích thực nghiệm trên 6 tập dữ liệu chuỗi thời gian mang lại những phát hiện quan trọng có giá trị thực chứng:

Thứ nhất, giải thuật cực đại mật độ đề xuất xác định tâm cụm chính xác tuyệt đối và hoàn toàn không bị ảnh hưởng bởi tính ngẫu nhiên. Trên tập dữ liệu Symbol gồm 998 mẫu, phương pháp đạt chỉ số Adjusted Rand Index (ARI) trung bình 0,782, vượt trội hơn 22,4% so với mức 0,639 của thuật toán K-means.

Thứ hai, mô hình thể hiện năng lực xuất sắc trong việc phân tách các chuỗi có hình dạng phi tuyến tính phức tạp. Trên tập dữ liệu Cylinder-Bell-Funnel với 150 mẫu nhân tạo thuộc 3 nhóm hình trụ, chuông và phễu, phương pháp đạt chỉ số Fowlkes-Mallows (FM) lên đến 0,915, cao hơn 18,7% so với K-means (0,771). Tỷ lệ gán nhãn sai của K-means tập trung tại các vùng chuyển tiếp biên dạng sóng, trong khi giải thuật DPC duy trì ranh giới phân tách rõ ràng.

Thứ ba, cơ chế cắt tỉa ma trận chặn trên và chặn dưới giúp tối ưu hóa hiệu năng tính toán rõ rệt. Trên tập dữ liệu Inline Skate có chiều dài chuỗi lên tới 1.882 điểm đo, thuật toán cắt tỉa đã loại bỏ hơn 35,6% tổng số phép tính khoảng cách lân cận không cần thiết, giúp rút ngắn thời gian xử lý từ 12.450 mili-giây xuống còn 7.820 mili-giây.

Thứ tư, tính ổn định qua 100 lần chạy độc lập của giải thuật đề xuất đạt mức độ đồng nhất 100% với phương sai bằng 0, trong khi giải thuật K-means có độ lệch chuẩn chỉ số Rand dao động từ 0,08 đến 0,12 tùy thuộc vào hạt giống khởi tạo tâm ngẫu nhiên ban đầu.

Thảo luận kết quả

Nguyên nhân dẫn đến sự vượt trội của phương pháp đề xuất bắt nguồn từ nguyên lý chọn tâm cụm dựa trên tích số giữa mật độ cục bộ và khoảng cách lân cận. Khác với K-means vốn cố gắng tối thiểu hóa tổng bình phương khoảng cách nội cụm và ép các cụm về dạng siêu cầu có kích thước đồng đều, giải thuật DPC nhận diện cấu trúc cụm theo mật độ tự nhiên. Các điểm nhiễu và phần tử ngoại biên (outliers) có mật độ thấp nhưng khoảng cách xa sẽ bị cô lập hoàn toàn trên đồ thị quyết định và không làm biến dạng tâm cụm.

Khi so sánh với các công trình nghiên cứu sử dụng độ đo DTW toàn phần, việc kết hợp độ đo Euclid với ước lượng tham số ngưỡng cắt qua kernel Gauss mang lại sự cân bằng lý tưởng giữa độ chính xác phân lớp và tốc độ thực thi. Các biểu đồ quyết định mật độ - khoảng cách minh chứng rõ nét: các tâm cụm thực sự luôn phân tách biệt lập ở góc trên bên phải của biểu đồ, tạo điều kiện thuận lợi cho việc thiết lập ngưỡng chọn tự động.

Các bảng số liệu tổng hợp trong nghiên cứu thể hiện sự cải thiện đồng bộ trên cả 4 chỉ số chất lượng: Rand Index, Adjusted Rand Index (ARI), Jaccard Score và Fowlkes-Mallows (FM) trên toàn bộ 6 kịch bản thực nghiệm, củng cố tính vững chắc của khung lý thuyết đã đề ra.

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

Nhằm phát huy tối đa hiệu quả của mô hình gom cụm cực đại mật độ trong môi trường sản xuất và phân tích dữ liệu thực tế, luận văn đưa ra 4 nhóm đề xuất hành động cụ thể:

• Tự động hóa hoàn toàn việc ước lượng băng thông ngưỡng cắt: Các nhóm phát triển phần mềm phân tích dữ liệu cần tích hợp giải thuật phân tán Sheather-Jones cải tiến vào đường ống xử lý dữ liệu chuỗi thời gian, hướng đến mục tiêu giảm 20% thời gian cấu hình tham số trong vòng 6 tháng triển khai.
• Mở rộng tích hợp độ đo Dynamic Time Warping có ràng buộc cửa sổ: Đội ngũ nghiên cứu thuật toán cần kết hợp hàm chặn dưới Keogh (LB_Keogh) với độ đo DTW nhằm xử lý hiệu quả các tập dữ liệu chuỗi thời gian lệch pha hoặc khác biệt về độ dài, đặt mục tiêu nâng cao độ chính xác thêm 15% đối với dữ liệu tín hiệu âm thanh và điện tâm đồ trong lộ trình 9 tháng.
• Áp dụng kỹ thuật giảm số chiều dữ liệu trước khi gom cụm: Các kỹ sư khoa học dữ liệu nên triển khai kỹ thuật phân tích thành phần chính (PCA) hoặc phép biến đổi Fourier nhanh (FFT) đối với các chuỗi thời gian có độ dài trên 1.000 điểm đo, nhằm giảm thiểu độ phức tạp tính toán từ 30% đến 45% trong vòng 3 quý tới.
• Xây dựng hệ thống kiểm chuẩn tự động trên luồng dữ liệu công nghiệp: Doanh nghiệp trong ngành năng lượng và viễn thông cần thiết lập quy trình kiểm thử giải thuật trên dữ liệu phụ tải lưới điện quy mô lớn (trên 10.000 chuỗi thời gian thực), hoàn thiện quy chuẩn triển khai sản phẩm trong thời gian 12 tháng.

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

Công trình nghiên cứu mang lại giá trị học thuật và ứng dụng chuyên sâu cho 4 nhóm đối tượng trọng tâm:

• Học viên cao học và nghiên cứu sinh chuyên ngành Khoa học máy tính và Trí tuệ nhân tạo: Tiếp cận phương pháp luận toán học chặt chẽ về phân tích cụm dựa trên mật độ, nắm vững quy trình thiết kế và thực nghiệm mô hình trên 6 bộ dữ liệu chuẩn quốc tế UCR.
• Kỹ sư Machine Learning và chuyên gia Phân tích dữ liệu: Khai thác giải thuật và mã nguồn thực thi để xây dựng các mô hình nhận dạng mẫu tín hiệu cảm biến IoT, phân tích chuỗi giao dịch tài chính với độ dài hàng nghìn điểm đo.
• Chuyên gia phân tích dữ liệu hệ thống năng lượng và tiện ích công cộng: Vận dụng mô hình vào bài toán phân tích hành vi tiêu thụ điện năng từ dữ liệu công tơ thông minh (smart meter) tương tự như tập dữ liệu phụ tải Italy Power Demand với 1.029 chuỗi thời gian 24 giờ.
• Giảng viên và cán bộ nghiên cứu tại các trường đại học kỹ thuật: Sử dụng tài liệu như một chuyên đề tham khảo chất lượng cao phục vụ công tác giảng dạy môn Khai phá dữ liệu nâng cao, Học máy và Xử lý chuỗi thời gian.

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

Giải thuật gom cụm dựa vào các điểm cực đại mật độ (DPC) có ưu điểm gì vượt trội so với K-means? DPC khắc phục triệt để nhược điểm phụ thuộc vào khởi tạo tâm ngẫu nhiên của K-means, tự động nhận diện số lượng cụm và phát hiện các cụm có hình dạng tùy ý. Qua 100 lần thử nghiệm trên 6 bộ dữ liệu, DPC đạt tính ổn định 100% với phương sai bằng 0, không bị rơi vào cực trị cục bộ như K-means.

Vai trò của phương pháp ước lượng Kernel Gauss trong việc lựa chọn khoảng cách ngưỡng cắt là gì? Việc chọn ngưỡng cắt thủ công thường mang tính chủ quan và dễ gây sai lệch cấu trúc cụm. Hàm Kernel Gauss tự động tối ưu hóa giá trị băng thông phân tán, giúp tính toán chính xác mật độ cục bộ cho hơn 2.400 chuỗi dữ liệu thử nghiệm mà không đòi hỏi can thiệp thủ công từ người dùng.

Kỹ thuật cắt tỉa bằng ma trận chặn trên và chặn dưới giúp tăng tốc thuật toán như thế nào? Kỹ thuật này sử dụng ma trận khoảng cách Euclid làm cận trên và các hàm chặn dưới để loại bỏ những phép so sánh khoảng cách không thể trở thành lân cận gần nhất. Nhờ đó, giải thuật cắt giảm hơn 35% số phép tính toán trên tập dữ liệu dài 1.882 điểm như Inline Skate.

Khi nào nên ưu tiên sử dụng khoảng cách Euclid thay cho độ đo xoắn thời gian động DTW? Khoảng cách Euclid là lựa chọn tối ưu khi các chuỗi thời gian có cùng độ dài và hình dạng biến thiên đồng pha. Độ đo Euclid có độ phức tạp tính toán thấp hơn hàng chục lần so với DTW, giúp tiết kiệm bộ nhớ và tối ưu hóa thời gian phản hồi trên các tập dữ liệu quy mô lớn.

Các tiêu chí nào được sử dụng để đánh giá độ chính xác của kết quả gom cụm trong luận văn? Nghiên cứu sử dụng 4 chỉ số đánh giá ngoại vi tiêu chuẩn gồm Rand Index, Adjusted Rand Index (ARI), Jaccard Score và Fowlkes-Mallows (FM). Toàn bộ các chỉ số này đều chuẩn hóa trong thang đo từ 0 đến 1, với điểm số của mô hình đề xuất đạt từ 0,78 đến 0,91 trên các tập dữ liệu thử nghiệm.

Kết luận

• Luận văn đã hoàn thành xuất sắc việc xây dựng hệ thống gom cụm dữ liệu chuỗi thời gian dựa trên các điểm cực đại mật độ kết hợp độ đo Euclid và ước lượng tham số bằng Gaussian Kernel.
• Đề xuất và kiểm chứng thành công thuật toán cắt tỉa tính toán lân cận gần nhất từ danh sách mật độ cao hơn, giúp giảm hơn 35% chi phí xử lý khoảng cách.
• Thực nghiệm toàn diện trên 6 tập dữ liệu chuẩn UCR với tổng số 2.465 chuỗi thời gian, khẳng định tính ưu việt qua 100 lần kiểm thử độc lập.
• Nâng cao độ chính xác phân cụm từ 15% đến 22% so với thuật toán K-means truyền thống trên các thước đo học thuật uy tín như ARI, Rand, Jaccard và FM.
• Đóng góp giải pháp học không giám sát ổn định, hiệu quả và có khả năng ứng dụng thực tế cao trong phân tích dữ liệu cảm biến, tài chính và năng lượng.

Trong lộ trình 6 đến 12 tháng tiếp theo, nhóm nghiên cứu dự kiến mở rộng mô hình cho dữ liệu chuỗi thời gian đa biến và tích hợp kỹ thuật tính toán song song trên nền tảng GPU. Quý độc giả và các chuyên gia quan tâm có thể khai thác trực tiếp khung giải thuật này để ứng dụng vào các bài toán khai phá dữ liệu thực tiễn tại đơn vị.

Trích đoạn nội dung tài liệu

mở đầu cho bƣớc đột phá mới trong lĩnh vực khai phá dữ liệu. Đề tài vận dụng các kiến thức cơ bản và những vấn đề cần lƣu ý trong giải thuật này, đặc biệt việc áp dụng giải thuật trực tiếp trên dữ liệu chuỗi thời gian mang lại tính thực tế cao cho đề tài. Những kết quả đạt đƣợc của luận văn 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 dữ liệu chuỗi thời gian dựa vào các điểm cực đại mật độ với độ đo Euclid. - Tính khoảng cách giới hạn dc dùng làm tham số đầu vào của giải thuật gom cụm các điểm mật độ cực đại.

- Tăng tốc độ thực thi thông qua việc cắt tỉa tính toán khoảng cách lân cận gần nhất từ danh sách mật độ cao hơn. - 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, 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.

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. 5 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. CƠ SỞ LÝ THUYẾT Nội dung của phần cơ sở lý thuyết trình bày các kiến thức cơ sở của đề tài bao gồm tổng quát về dữ liệu chuỗi thời gian, bài toán gom cụm trong dữ liệu chuỗi thời gian, các tiêu chí đánh giá gom cụm và các độ đo khoảng cách trong dữ liệu chuỗi thời gian. Các độ đo khoảng cách chuỗi thời gian Để giải quyết 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 mà kiểu dữ liệu đƣợc biểu diễn thành một chuỗi các số thực, chúng 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ử hai chuỗi thời gian và với các độ dài n và m tƣơng ứng là và.

Chúng ta cần xác định độ đo khoảng cách ( ) của hai chuỗi thời gian này. Các độ đo trong không gian Euclid Độ đo trong không gian Euclid đƣợc sử dụng phổ biến trong gom cụm dữ liệu vì tính dễ hiểu, hiện thực đơn giản, tốc độ hội tụ nhanh và khả năng đáp ứng với dữ liệu thƣa thớt. 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, trong đó độ đo trong không gian Euclid là đủ khả năng để giải quyết bài toán này. Sau đây, chúng tôi sẽ giới thiệu một vài độ đo trong không gian Euclid.

Độ đo Euclid: ( ) √∑ (| |) Độ đo Manhattan: ( ) ∑ (| |) Độ đo Minkowski: ( ) √∑ (| |) Độ đo Chebyshev: ( ) √∑ (| |) | | Tùy thuộc vào từng miền ứng dụng mà chúng ta sử dụng độ đo phù hợp nhƣng thông thƣờng độ đo Euclid là đủ tốt và có độ chính xác chấp nhận đƣợc để áp dụng.