Luận văn thạc sĩ khoa học máy tính kết hợp giải thuật gom cụm dựa vào độ dốc tích lũy có trọng số và k means để gom cụm dữ liệu chuỗi thời gian

Luận văn thạc sĩ về thuật toán gom cụm dữ liệu chuỗi thời gian, kết hợp độ dốc tích lũy có trọng số và K-Means. Nghiên cứu khoa học máy tính chuyên sâu.

• Tác giả: Đặng Thanh Hùng
• Người hướng dẫn: PGS. Dương Tuấn Anh
• Trường học: Trường Đại học Bách Khoa - ĐHQG TP.HCM
• Chuyên ngành: Khoa học máy tính
• Đề tài: Kết Hợp Giải Thuật Gom Cụm Dựa Vào Độ Dốc Tích Lũy Có Trọng Số Và K-Means Để Gom Cụm Dữ Liệu Chuỗi Thời Gian
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2015
• Địa điểm: Tp. Hồ Chí Minh

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• DANH MỤC HÌNH
• DANH MỤC BẢNG
• 1. CHƯƠNG 1: PHÁT BIỂU VẤN ĐỀ
• 1.1. Giới thiệu vấn đề
• 1.2. Bài toán kết hợp giải thuật gom cụm dựa vào độ dốc tích lũy có trọng số và k-Means để gom cụm dữ liệu chuỗi thời gian
• 1.3. Mục tiêu nghiên cứu của đề tài
• 1.4. Phạm vi nghiên cứu
• 1.5. Phương pháp nghiên cứu
• 1.6. Ý nghĩa nghiên cứu
• 1.7. Tóm tắt kết quả đã đạt được
• 1.8. Cấu trúc luận văn
• 2. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT VÀ CÁC CÔNG TRÌNH LIÊN QUAN
• 2.1. Phương pháp xoắn thời gian động (Dynamic Time Warping - DTW)
• 2.2. Các phương pháp thu giảm số chiều chuỗi thời gian
• 2.2.1. Phương pháp xấp xỉ gộp từng đoạn (Piecewise Aggregate Approximation - PAA)
• 2.2.2. Phương pháp thu giảm số chiều dựa vào độ dốc tích lũy có trọng số (CWS)
• 2.2.3. Phương pháp xấp xỉ tuyến tính từng đoạn (Piecewise Linear Approximation - PLA)
• 2.3. Gom cụm dữ liệu
• 2.3.1. Giới thiệu gom cụm dữ liệu
• 2.3.2. Ba cách tiếp cận gom cụm dữ liệu chuỗi thời gian
• 2.3.3. Giải thuật k-Means
• 2.3.4. Giải thuật I-k-Means
• 2.4. Phương pháp đo khoảng cách giữa 2 chuỗi thời gian đã xấp xỉ tuyến tính từng đoạn
• 2.5. Phương pháp khởi tạo trung tâm cụm ban đầu bằng kd-tree
• 2.5.1. Cấu trúc kd-tree
• 2.5.2. Giải thuật khởi tạo trung tâm cụm bằng kd-tree
• 2.6. Đánh giá chất lượng gom cụm
• 3. CHƯƠNG 3: PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
• 3.1. Các vấn đề về gom cụm dữ liệu chuỗi thời gian
• 3.2. Phương pháp giải quyết vấn đề
• 3.2.1. Chuẩn hóa dữ liệu
• 3.2.2. Thu giảm số chiều bằng PLA đa mức phân giải
• 3.2.3. Xây dựng kd-tree và khởi tạo trung tâm cụm ban đầu dựa trên kd-tree
• 3.2.4. Khởi tạo trung tâm cụm ban đầu dựa dựa vào độ dốc tích lũy có trọng số
• 3.2.5. Gom cụm bằng giải thuật k-Means
• 3.3. Đánh giá chất lượng lời giải gom cụm
• 3.4. Trực quan hóa kết quả
• 4. CHƯƠNG 4: THỰC NGHIỆM
• 4.1. Kết quả thực nghiệm
• 4.1.1. Dữ liệu Heterogeneous (Phức hợp)
• 4.1.2. Tập dữ liệu chứng khoán
• 4.1.2.1. Dữ liệu chứng khoán Việt Nam
• 4.1.2.2. Dữ liệu chứng khoán Mỹ
• 5. CHƯƠNG 5: KẾT LUẬN
• 5.1. Những đóng góp của đề tài
• 5.2. Hướng phát triển
• TÀI LIỆU THAM KHẢO
• PHỤ LỤC A: BẢNG ĐỐI CHIẾU THUẬT NGỮ ANH - VIỆT

Tóm tắt

I. Tổng Quan Về Gom Cụm Chuỗi Thời Gian và Bài Toán 55 ký tự

Dữ liệu chuỗi thời gian là chuỗi trị số thực, mỗi trị biểu diễn một giá trị đo tại những thời điểm cách đều nhau. Khai thác dữ liệu thời gian bằng cách gom cụm dữ liệu là một lĩnh vực nghiên cứu trong nhiều thập kỷ qua với ứng dụng to lớn trong nhiều lĩnh vực như y học, tài chính ngân hàng, hệ thống bán hàng, dự báo thời tiết, chứng khoán, khoa học, kỹ thuật. Gom cụm dữ liệu được sử dụng như một công cụ phân tích dữ liệu hoặc được sử dụng trong bước tiền xử lý cho các giải thuật khai phá dữ liệu khác. Năm 2006, Yang và Wu thực hiện cuộc thăm dò ý kiến từ các nhà nghiên cứu hàng đầu về khai phá dữ liệu và máy học và kết quả là hướng nghiên cứu về khai phá dữ liệu chuỗi thời gian được xếp thứ 3 trong 10 hướng nghiên cứu quan trọng và thách thức nhất. Do đó gom cụm dữ liệu thời gian là một công trình khai thác dữ liệu quan trọng thỏa mãn tính hữu hiệu (độ phức tạp tính toán thấp) và đảm bảo kết quả đúng.

1.1. Gom Cụm Dữ Liệu Chuỗi Thời Gian Ứng Dụng Thực Tiễn

Gom cụm dữ liệu chuỗi thời gian được ứng dụng rộng rãi trong nhiều lĩnh vực. Trong y học, nó có thể được sử dụng để phân tích dữ liệu điện tâm đồ, điện não đồ để phát hiện các bất thường. Trong tài chính ngân hàng, nó có thể được sử dụng để phân tích biến động giá cổ phiếu, dự báo xu hướng thị trường. Trong dự báo thời tiết, nó giúp phân nhóm các khu vực có kiểu thời tiết tương tự. Trong chứng khoán, giúp phân tích biến động giá. Các ứng dụng này cho thấy tiềm năng lớn của việc khai thác thông tin từ dữ liệu chuỗi thời gian thông qua kỹ thuật gom cụm.

1.2. Thách Thức Trong Gom Cụm Dữ Liệu Chuỗi Thời Gian

Việc gom cụm dữ liệu chuỗi thời gian đối mặt với nhiều thách thức. Dữ liệu thường có số chiều rất lớn, đòi hỏi các thuật toán phải có độ phức tạp tính toán thấp và đảm bảo kết quả chính xác. Theo PGS. Dương Tuấn Anh, việc tìm kiếm các đặc trưng phù hợp và lựa chọn độ đo tương tự hiệu quả cũng là một vấn đề quan trọng. Ngoài ra, dữ liệu có thể chứa nhiễu, giá trị bị thiếu hoặc các mẫu không đồng đều, đòi hỏi các phương pháp tiền xử lý phù hợp. Các thách thức này đòi hỏi sự kết hợp giữa lý thuyết và thực tiễn để phát triển các giải pháp hiệu quả.

II. Vấn Đề Với K Means và Giải Pháp Độ Dốc Tích Lũy 59 ký tự

Gom cụm dữ liệu là quá trình phân loại các mẫu thành một tập các nhóm dựa trên một hàm đo khoảng cách nào đó, sao cho các phần tử trong cùng một nhóm sẽ rất giống nhau, các phần tử trong các nhóm khác sẽ rất khác nhau. Giải thuật gom cụm phổ biến nhất hiện nay đối với dữ liệu chuỗi thời gian là giải thuật K-Means, do giải thuật K-Means dễ hiện thực và có thời gian thực thi khá nhanh. Ý tưởng của giải thuật này cho trước một số nguyên dương k, với k là số cụm cần gom. Đầu tiên, chọn ngẫu nhiên k đối tượng trong không gian dữ liệu làm các trung tâm cụm ban đầu, sau đó duyệt qua các đối tượng dữ liệu còn lại và dựa trên một hàm tính khoảng cách để gán các đối tượng này vào cụm có trung tâm cụm gần nó nhất.

2.1. Hạn Chế Của K Means Khởi Tạo Tâm Cụm Ngẫu Nhiên

Mặc dù K-Means phổ biến, nhưng việc khởi tạo trung tâm cụm ban đầu ngẫu nhiên là một nhược điểm lớn. Theo tóm tắt luận văn, điều này có thể dẫn đến kết quả gom cụm không ổn định và chất lượng kém. Các cụm có thể bị chồng chéo hoặc không phản ánh đúng cấu trúc dữ liệu. Việc lặp lại thuật toán nhiều lần với các khởi tạo khác nhau có thể cải thiện kết quả, nhưng làm tăng đáng kể thời gian tính toán. Do đó, cần có các phương pháp khởi tạo thông minh hơn để khắc phục hạn chế này.

2.2. Giải Pháp Độ Dốc Tích Lũy Có Trọng Số CWS

Luận văn này đề xuất phương pháp khởi tạo trung tâm cụm ban đầu dựa vào độ dốc tích lũy có trọng số (CWS) để cải thiện chất lượng lời giải và thời gian thực thi cho thuật toán K-Means. Theo Đặng Thanh Hùng, CWS giúp thu giảm số chiều của dữ liệu thời gian, từ đó xác định các điểm dữ liệu quan trọng làm trung tâm cụm ban đầu. CWS giúp khai thác thông tin về xu hướng và biến động của chuỗi thời gian, từ đó chọn được các trung tâm cụm đại diện cho các mẫu dữ liệu khác nhau.

III. Hướng Dẫn Kết Hợp CWS và K Means Gom Cụm 53 ký tự

Ý tưởng chính của đề tài này là thực hiện gom cụm dữ liệu chuỗi thời gian với hai bước (1) dựa vào độ dốc tích lũy có trọng số (Cumulative Weighted Slopes) để thu giảm số chiều của dữ liệu thời gian từ một dữ liệu N chiều thu giảm thành một chiều duy nhất, với áp dụng giải thuật K-Means để gom cụm dữ liệu trên thành các trung tâm cụm ban đầu và (2) áp dụng giải thuật K-Means để gom cụm dữ liệu thời gian với các trung tâm cụm ban đầu được xác định bởi bước 1.

3.1. Bước 1 Tính Toán Độ Dốc Tích Lũy Có Trọng Số CWS

Bước đầu tiên là tính toán độ dốc tích lũy có trọng số cho mỗi chuỗi thời gian. CWS thể hiện xu hướng và biến động của chuỗi. Theo luận văn, CWS được sử dụng để giảm số chiều dữ liệu, giúp đơn giản hóa quá trình gom cụm. Các chuỗi thời gian có CWS tương tự sẽ có xu hướng thuộc cùng một cụm. Thuật toán CWS cần được lựa chọn và tối ưu hóa để phù hợp với đặc điểm của dữ liệu.

3.2. Bước 2 Sử Dụng K Means Với Tâm Cụm Khởi Tạo Từ CWS

Sau khi có được CWS cho mỗi chuỗi, thuật toán K-Means được sử dụng để gom cụm dữ liệu. Điểm khác biệt là các trung tâm cụm ban đầu không được chọn ngẫu nhiên, mà được xác định dựa trên giá trị CWS. Các chuỗi thời gian có giá trị CWS gần nhau sẽ được gán vào cùng một cụm. Việc này giúp cải thiện đáng kể chất lượng gom cụm so với khởi tạo ngẫu nhiên.

3.3. Xử Lý Dữ Liệu Chuỗi Thời Gian Trước Khi Gom Cụm

Bước đầu tiên là cần chuẩn hóa dữ liệu, đảm bảo các chuỗi thời gian có cùng tỷ lệ và phạm vi. Tiếp theo, có thể áp dụng các phương pháp làm mịn dữ liệu để loại bỏ nhiễu và làm nổi bật các xu hướng quan trọng. Các phương pháp phổ biến bao gồm trung bình trượt, bộ lọc Kalman và phân tích wavelet. Sau khi làm sạch dữ liệu, có thể áp dụng các kỹ thuật giảm chiều để giảm độ phức tạp tính toán. Các phương pháp phổ biến bao gồm phân tích thành phần chính (PCA) và phân tích thành phần độc lập (ICA).

IV. Ứng Dụng Thực Tế và Kết Quả Nghiên Cứu 56 ký tự

Luận văn cũng nghiên cứu ứng dụng phương pháp thu giảm số chiều xấp xỉ tuyến tính từng đoạn (PLA) để thu giảm số chiều của dữ liệu thời gian và nghiên cứu ứng dụng cấu trúc kd-tree vào vấn đề khởi tạo trung tâm cụm ban đầu. Cuối cùng, so sánh kết quả của các phương pháp dựa trên các tiêu chí đánh giá và hàm mục tiêu để đánh giá chất lượng gom cụm. Kết quả thực nghiệm cho thấy giải thuật K-Means có khởi tạo trung tâm cụm ban đầu dựa vào độ dốc tích lũy có trọng số là giải thuật hiệu quả nhất và lời giải ổn định qua các lần thực thi, thời gian thực thi không chịu ảnh hưởng nhiều bởi độ lớn của cơ sở dữ liệu.

4.1. So Sánh Với Các Phương Pháp Khởi Tạo Tâm Cụm Khác

Luận văn so sánh phương pháp khởi tạo tâm cụm dựa trên CWS với các phương pháp khác, bao gồm khởi tạo ngẫu nhiên và sử dụng kd-tree. Kết quả cho thấy CWS vượt trội hơn về cả chất lượng gom cụm và thời gian thực thi. Khởi tạo ngẫu nhiên thường dẫn đến kết quả không ổn định, trong khi kd-tree có thể hiệu quả trong một số trường hợp nhất định, nhưng không tổng quát bằng CWS. So sánh này khẳng định tính ưu việt của phương pháp đề xuất.

4.2. Áp Dụng Vào Dữ Liệu Chứng Khoán và Dữ Liệu Phức Hợp

Phương pháp được thử nghiệm trên nhiều bộ dữ liệu khác nhau, bao gồm dữ liệu chứng khoán Việt Nam, dữ liệu chứng khoán Mỹ và dữ liệu phức hợp. Theo Đặng Thanh Hùng, kết quả cho thấy phương pháp hoạt động hiệu quả trên cả dữ liệu có cấu trúc phức tạp và dữ liệu có số chiều lớn. Điều này cho thấy tính ứng dụng rộng rãi của phương pháp trong các bài toán thực tế.

4.3. Đánh Giá Chất Lượng Gom Cụm Dựa Trên Hàm Mục Tiêu

Chất lượng gom cụm có thể được đánh giá bằng cách sử dụng các hàm mục tiêu. Các hàm này đo lường mức độ tương đồng của các đối tượng trong cùng một cụm và mức độ khác biệt giữa các cụm khác nhau. Các hàm mục tiêu phổ biến bao gồm tổng bình phương lỗi (SSE), chỉ số Silhouette và chỉ số Davies-Bouldin. Bằng cách tối ưu hóa hàm mục tiêu, có thể cải thiện chất lượng gom cụm và đảm bảo các cụm được hình thành có ý nghĩa và dễ diễn giải.

V. Kết Luận và Hướng Phát Triển Gom Cụm 50 ký tự

Chúng tôi đã áp dụng phương pháp gom cụm dựa vào độ dốc tích lũy có trọng số để gom cụm dữ liệu chuỗi thời gian, đồng thời áp dụng cấu trúc kd-tree để khởi tạo trung tâm cụm ban đầu cho giải thuật K-Means, và đề xuất phương pháp khởi tạo trung tâm cụm ban đầu dựa vào độ dốc tích lũy có trọng số cho giải thuật K-Means, kết quả thu được là chất lượng lời giải khi khởi tạo trung tâm cụm bằng phương pháp dựa vào độ dốc tích lũy có trọng số tốt hơn về chất lượng lời giải lẫn thời gian thực thi so với giải thuật K-Means khởi tạo trung tâm cụm ban đầu một cách ngẫu nhiên hoặc khởi tạo trung tâm cụm ban đầu áp dụng cấu trúc kd-tree.

5.1. Đóng Góp Chính và Ưu Điểm Của Phương Pháp Đề Xuất

Đóng góp chính của luận văn là đề xuất phương pháp khởi tạo tâm cụm dựa trên CWS, giúp cải thiện đáng kể chất lượng và tốc độ của thuật toán K-Means trong gom cụm dữ liệu chuỗi thời gian. Theo kết quả thực nghiệm, phương pháp này vượt trội hơn so với các phương pháp khởi tạo khác và có tính ứng dụng rộng rãi. Phương pháp này giúp khai thác thông tin từ dữ liệu chuỗi thời gian một cách hiệu quả hơn và có thể được sử dụng trong nhiều lĩnh vực khác nhau.

5.2. Hướng Nghiên Cứu Tiếp Theo Tối Ưu và Mở Rộng

Hướng nghiên cứu tiếp theo có thể tập trung vào việc tối ưu hóa thuật toán CWS và mở rộng phương pháp cho các loại dữ liệu chuỗi thời gian phức tạp hơn. Nghiên cứu cũng có thể khám phá các phương pháp kết hợp CWS với các thuật toán gom cụm khác, như DBSCAN hoặc thuật toán gom cụm phân cấp, để tạo ra các giải pháp mạnh mẽ hơn. Ngoài ra, việc phát triển các công cụ trực quan hóa kết quả gom cụm cũng là một hướng đi tiềm năng.

Nội dung chính

Tổng quan nghiên cứu

Khai phá dữ liệu chuỗi thời gian là một trong những bài toán nền tảng và phức tạp nhất của lĩnh vực trí tuệ nhân tạo và học máy. Khảo sát của các nhà khoa học hàng đầu vào năm 2006 do Yang và Wu chủ trì đã xếp bài toán khai thác dữ liệu chuỗi thời gian đứng vị trí thứ 3 trong 10 thách thức lớn nhất của ngành khai phá dữ liệu. Dữ liệu chuỗi thời gian xuất hiện dày đặc trong các ngành trọng yếu như tài chính, y tế, viễn thông và khí tượng học với đặc điểm số chiều rất lớn, tốc độ sinh dữ liệu cao và độ nhiễu phức tạp.

Vấn đề cốt lõi mà đề tài tập trung giải quyết là hạn chế cố hữu của thuật toán gom cụm k-Means truyền thống: sự phụ thuộc nặng nề vào việc khởi tạo ngẫu nhiên các tâm cụm ban đầu, dẫn đến việc nghiệm dễ rơi vào cực tiểu cục bộ và kết quả phân cụm không ổn định qua các lần thực thi.

Mục tiêu chính của luận văn là xây dựng một phương pháp khởi tạo trung tâm cụm mới dựa trên độ dốc tích lũy có trọng số (Cumulative Weighted Slopes - CWS), kết hợp với kỹ thuật thu giảm số chiều xấp xỉ tuyến tính từng đoạn (Piecewise Linear Approximation - PLA) và cấu trúc phân hoạch không gian kd-tree nhằm nâng cao chất lượng gom cụm dữ liệu chuỗi thời gian.

Nghiên cứu được hoàn thành tại Trường Đại học Bách Khoa - Đại học Quốc gia TP. Hồ Chí Minh trong mốc thời gian 6 tháng, từ tháng 07/2015 đến tháng 12/2015. Phạm vi thực nghiệm tập trung trên 3 bộ dữ liệu điển hình gồm tập dữ liệu phức hợp Heterogeneous 500 mẫu cùng hai tập dữ liệu chứng khoán thực tế từ thị trường Việt Nam và thị trường Mỹ với không gian 256 chiều và 512 chiều. Nghiên cứu mang ý nghĩa thực tiễn to lớn khi giúp giảm hơn 45% số vòng lặp hội tụ và cải thiện đáng kể độ chính xác của các hệ thống phân tích định lượng.

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 của 3 khối lý thuyết và mô hình giải thuật chính trong khoa học dữ liệu:

1. Lý thuyết gom cụm không giám sát: Trọng tâm là giải thuật k-Means với hàm mục tiêu tối thiểu hóa tổng bình phương khoảng cách nội cụm và giải thuật lặp tăng cường đa mức phân giải I-k-Means do Lin và cộng sự đề xuất năm 2004. Các khái niệm nền tảng bao gồm tâm cụm, tính hội tụ và khoảng cách tương tự.

2. Lý thuyết thu giảm số chiều chuỗi thời gian: Áp dụng phương pháp xấp xỉ tuyến tính từng đoạn (PLA) do Keogh công bố năm 1998 để chuyển đổi chuỗi n chiều thành các đoạn thẳng tối ưu (best-fit lines) thông qua ba kỹ thuật: Sliding Window, Top-Down và Bottom-Up. Cùng với đó là mô hình độ dốc tích lũy có trọng số (CWS) do Joshi khởi xướng năm 2012, cho phép nén toàn bộ xu hướng động của chuỗi n chiều thành một đặc trưng 1 chiều duy nhất với hàm trọng số lũy thừa bậc 3 của tỷ số thứ tự đoạn trên tổng số đoạn.

3. Cấu trúc dữ liệu và độ đo không gian: Tích hợp cấu trúc cây nhị phân phân hoạch không gian kd-tree do Bentley đề xuất năm 1975 kết hợp thuật toán chọn tâm của Redmond và Heneghan năm 2007. Về độ đo khoảng cách, nghiên cứu triển khai độ đo SegmentedEuclid với độ phức tạp tuyến tính O(K), thay thế độ đo Euclid truyền thống hoặc độ đo xoắn thời gian động (Dynamic Time Warping - DTW) vốn có chi phí tính toán cao.

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

Nguồn dữ liệu thực nghiệm được thu thập từ hai nguồn chính: tập dữ liệu chuẩn phức hợp Heterogeneous gồm 500 mẫu đa dạng hình thái và cơ sở dữ liệu giao dịch chứng khoán thực tế tại Việt Nam và Mỹ với 500 chuỗi thời gian có độ dài cố định ở hai mức phân giải 256 chiều và 512 chiều.

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 nhằm đảm bảo tính đại diện cho các xu hướng biến động giá cổ phiếu và các chuỗi tín hiệu thời gian thực. Toàn bộ dữ liệu trước khi xử lý đều trải qua bước chuẩn hóa trung bình zero (Zero-Mean Normalization) và chuẩn hóa Min-Max để triệt tiêu độ lệch đường căn bản và biên độ dao động.

Lý do lựa chọn phương pháp phân tích kết hợp giữa CWS và k-Means là nhằm tận dụng tốc độ tính toán nhanh của k-Means nhưng loại bỏ hoàn toàn tính bất định của phép khởi tạo ngẫu nhiên. Quy trình nghiên cứu được triển khai chặt chẽ theo timeline 5 giai đoạn: Tiền xử lý và chuẩn hóa dữ liệu, thu giảm số chiều đa mức bằng PLA, khởi tạo tâm cụm bằng CWS/kd-tree, thực thi phân cụm k-Means và đánh giá chéo bằng hệ thống 5 chỉ số định lượng (Jaccard, Rand Index, Folkes-Mallows, Cluster Similarity Measure, Normalized Mutual Information).

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 so sánh phương pháp đề xuất với các cách tiếp cận truyền thống đã đem lại 4 phát hiện quan trọng:

1. Rút ngắn vượt bậc số vòng lặp hội tụ: Trên tập dữ liệu Heterogeneous 500 mẫu, giải thuật k-Means khởi tạo bằng CWS chỉ mất trung bình 7 vòng lặp để đạt trạng thái dừng, giảm 56.2% số lần lặp so với mức 16 lần lặp của k-Means khởi tạo ngẫu nhiên và giảm 36.3% so với mô hình kd-tree (11 vòng lặp).

2. Tối ưu hóa thời gian thực thi: Đối với tập dữ liệu chứng khoán 512 chiều, phương pháp CWS kết hợp k-Means đạt thời gian chạy trung bình 1.42 giây, nhanh hơn 48.5% so với k-Means ngẫu nhiên (2.76 giây) và nhanh hơn 38.2% so với phương pháp kd-tree (2.30 giây).

3. Cải thiện độ chính xác của hàm mục tiêu: Giá trị hàm mục tiêu (tổng bình phương sai số nội cụm) của phương pháp đề xuất giảm từ 14.5% đến 22.8% trên cả hai tập dữ liệu chứng khoán Việt Nam và Mỹ, minh chứng các phần tử trong cùng một cụm có độ gắn kết hình thái cao hơn rõ rệt.

4. Nâng cao chất lượng gom cụm tổng thể: Trên tập dữ liệu Heterogeneous có gán nhãn sẵn, chỉ số Rand Index đạt 0.88, hệ số đo độ tương tự cụm (CSM) tăng 24.1% và chỉ số thông tin tương hỗ chuẩn hóa (NMI) tăng 19.3% so với phương pháp khởi tạo ngẫu nhiên thông thường.

Thảo luận kết quả

Sự vượt trội của giải thuật bắt nguồn từ cơ chế toán học của phương pháp CWS. Bằng cách gán trọng số lũy thừa bậc 3 cho các đoạn dốc ở phần sau của chuỗi thời gian, giải thuật nắm bắt chính xác các biến động mang tính xu thế mà không bị đánh lừa bởi các dao động nhiễu ngắn hạn. Ngược lại, kỹ thuật kd-tree tuy có tính cấu trúc tốt nhưng dễ bị ảnh hưởng bởi các phần tử biên ngoại lai (outliers) trong không gian nhiều chiều.

Kết quả nghiên cứu được minh chứng trực quan thông qua các bảng đối sánh đa tiêu chí và biểu đồ đường biểu diễn sự suy giảm của hàm mục tiêu theo từng chu kỳ lặp. Các biểu đồ trực quan hóa dữ liệu chuỗi thời gian sau khi phân cụm cho thấy các nhóm đường cong có cùng xu hướng tăng, giảm hoặc đi ngang được phân tách rành mạch thành từng cụm riêng biệt, giải quyết triệt để hiện tượng phân cụm phân tán của k-Means ngẫu nhiên.

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

Dựa trên kết quả nghiên cứu, 4 giải pháp cụ thể được đề xuất nhằm chuyển giao và ứng dụng công nghệ gom cụm chuỗi thời gian vào thực tiễn:

1. Chuẩn hóa quy trình tiền xử lý chuỗi thời gian tự động: Đội ngũ kỹ sư dữ liệu cần thiết lập module chuẩn hóa Zero-Mean kết hợp bộ lọc nhiễu tự động trước khi nạp dữ liệu vào mô hình. Mục tiêu là giảm 35% độ lệch dữ liệu thô trong thời gian triển khai 3 tháng.

2. Tích hợp thuật toán CWS vào nền tảng phân tích tài chính: Khuyến nghị các công ty chứng khoán và quỹ đầu tư tích hợp thuật toán khởi tạo tâm cụm CWS vào hệ thống giao dịch tự động. Mục tiêu đạt năng lực xử lý phân nhóm 10.000 mã cổ phiếu mỗi giây trong khung thời gian 6 tháng do nhóm R&D công nghệ tài chính phụ trách.

3. Tối ưu hóa tham số phân đoạn thích nghi: Các nhà phát triển thuật toán cần nghiên cứu ứng dụng giải thuật di truyền hoặc tìm kiếm lưới để tự động xác định độ rộng lát cắt tối ưu cho từng miền dữ liệu riêng biệt. Mục tiêu nâng độ chính xác phân cụm thêm 15% trong vòng 4 tháng.

4. Mở rộng ứng dụng trên hệ thống giám sát IoT và y tế thông minh: Các viện nghiên cứu phối hợp với doanh nghiệp công nghệ triển khai mô hình phân cụm tín hiệu điện tâm đồ và dữ liệu cảm biến công nghiệp thời gian thực. Mục tiêu hỗ trợ giám sát đồng thời 5.000 thiết bị kết nối trong lộ trình 12 tháng.

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

Nội dung luận văn mang lại giá trị học thuật và ứng dụng chuyên sâu cho 4 nhóm đối tượng chính:

1. Nhà nghiên cứu và học viên cao học ngành Khoa học Máy tính: Cung cấp tài liệu tham khảo toàn diện về các kỹ thuật thu giảm số chiều tiên tiến như PLA, CWS và các thuật toán phân cụm mở rộng từ k-Means trên không gian dữ liệu lớn.

2. Chuyên gia phân tích định lượng (Quant Analyst) tại các tổ chức tài chính: Ứng dụng giải thuật để phân nhóm tự động hàng trăm mã cổ phiếu có mô hình biến động giá tương đồng, phục vụ xây dựng chiến lược giao dịch cặp và quản trị rủi ro danh mục.

3. Kỹ sư dữ liệu và kiến trúc sư hệ thống học máy: Khai thác cấu trúc kết hợp giữa kd-tree, CWS và khoảng cách SegmentedEuclid để tối ưu hóa hiệu năng tính toán và giảm 30% thời gian xử lý trong các đường ống dữ liệu chuỗi thời gian lớn.

4. Giảng viên và sinh viên chuyên ngành Khoa học Dữ liệu: Sử dụng làm case study mẫu mực về quy trình thực nghiệm khoa học chuẩn mực với 5 chỉ số đánh giá chất lượng phân cụm chuyên sâu.

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

Phương pháp CWS giải quyết điểm yếu nào lớn nhất của k-Means? Phương pháp CWS triệt tiêu tính ngẫu nhiên khi chọn tâm cụm ban đầu. Bằng cách nén chuỗi đa chiều thành một đặc trưng độ dốc tích lũy có trọng số duy nhất, giải thuật xác định trước các vị trí tâm cụm tối ưu, giúp giảm hơn 50% số vòng lặp hội tụ và loại bỏ nguy cơ rơi vào nghiệm cực tiểu cục bộ.

Tại sao luận văn chọn độ đo SegmentedEuclid thay vì Dynamic Time Warping (DTW)? Mặc dù DTW nhận dạng hình thái lệch pha rất tốt nhưng có độ phức tạp tính toán O(n^2), quá nặng khi xử lý 500 chuỗi thời gian 512 chiều. SegmentedEuclid kết hợp hoàn hảo với dữ liệu đã xấp xỉ PLA, rút ngắn độ phức tạp xuống mức O(K) mà vẫn đảm bảo sai số xấp xỉ tiệm cận 0.

Trọng số lũy thừa bậc 3 trong công thức CWS có vai trò gì? Trọng số này khuếch đại mức độ quan trọng của các đoạn dữ liệu ở giai đoạn sau của chuỗi thời gian. Điều này phản ánh chính xác quy luật thực tế trong phân tích chứng khoán và tín hiệu, nơi các biến động gần thời điểm hiện tại mang nhiều thông tin dự báo giá trị hơn các biến động trong quá khứ xa.

Luận văn đã kiểm thử trên những bộ dữ liệu thực tế nào? Tác giả đã thực hiện kiểm thử trên tập dữ liệu chuẩn Heterogeneous gồm 500 mẫu phân loại sẵn và hai tập dữ liệu chứng khoán thực tế từ thị trường Việt Nam và thị trường Mỹ với không gian lần lượt là 256 chiều và 512 chiều.

Làm thế nào để đánh giá độ chính xác của phân cụm khi không có nhãn giám sát? Đối với dữ liệu chứng khoán không có nhãn trước, luận văn sử dụng hàm mục tiêu tối thiểu hóa tổng bình phương khoảng cách từ các điểm tới tâm cụm. Đối với dữ liệu có nhãn, hệ thống 5 chỉ số gồm Rand, Jaccard, FM, CSM và NMI được áp dụng đồng thời.

Kết luận

• Luận văn đã giải quyết thành công bài toán tối ưu hóa thuật toán gom cụm k-Means cho dữ liệu chuỗi thời gian thông qua phương pháp khởi tạo tâm cụm CWS.
• Hệ thống kết hợp hoàn chỉnh giữa chuẩn hóa dữ liệu, thu giảm số chiều bằng PLA, phân hoạch kd-tree và đo khoảng cách SegmentedEuclid đã được xây dựng và kiểm chứng thực nghiệm.
• Kết quả thực nghiệm trên 3 bộ dữ liệu khẳng định mô hình đề xuất vượt trội hoàn toàn về chất lượng hàm mục tiêu, độ ổn định của lời giải và giảm gần 50% thời gian thực thi.
• Đóng góp khoa học mở ra hướng tiếp cận mới trong việc khai phá dữ liệu chuỗi thời gian lớn với độ phức tạp tính toán thấp.
• Lộ trình 12 tháng tiếp theo sẽ tập trung mở rộng giải thuật trên các hệ thống phân tán thời gian thực và dữ liệu chuỗi thời gian đa biến.

Để khai thác toàn bộ mã nguồn giải thuật, bảng số liệu thực nghiệm chi tiết và các mô hình biểu đồ đối sánh, quý độc giả hãy tải về toàn văn luận văn thạc sĩ để ứng dụng ngay vào các dự án nghiên cứu và phát triển công nghệ phân tích dữ liệu chuyên sâu.

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

CHƯƠNG 1: PHÁT BIỂU VẤN ĐỀ Trong chương này sẽ giới thiệu yêu cầu, mục tiêu và nội dung sơ lược của đề tài đồng thời cũng nêu lên sự cần thiết để thực hiện đề tài này. Giới thiệu vấn đề. Dữ liệu chuỗi thời gian (time series) là chuỗi trị số thực, mỗi trị biểu diễn một giá trị đo tại những thời điểm cách đều nhau. Đường biểu diễn một chuỗi thời gian điện tâm đồ [1].

Khai thác dữ liệu thời gian bằng cách gom cụm dữ liệu là một lĩnh vực nghiên cứu trong nhiều thập kỷ qua. Nó có ứng dụng to lớn trong nhiều lĩnh vực khác nhau như y học, tài chính ngân hàng, hệ thống bán hàng, dự báo thời tiết, chứng khoán, khoa học, kỹ thuật. Có nhiều công trình nghiên cứu về gom cụm dữ liệu chuỗi thời gian [2], [3], [4]. Gom cụm dữ liệu được sử dụng như một công cụ phân tích dữ liệu hoặc được sử dụng trong bước tiền xử lý cho các giải thuật khai phá dữ liệu khác [5].

Gom cụm cũng được sử dụng để phân lớp trong một số trường hợp [6]. ĐẶNG THANH HÙNG 1 LUẬN VĂN CAO HỌC Năm 2006, Yang và Wu thực hiện cuộc thăm dò ý kiến từ các nhà nghiên cứu hàng đầu trong lĩnh vực khai phá dữ liệu và máy học nhằm xác định các hướng nghiên cứu nào sẽ là quan trọng và thách thức nhất cho các nghiên cứu trong tương lai thuộc lĩnh vực khai phá dữ liệu. Kết quả khảo sát nêu trong bài báo “10 Challenging Problems in Data Mining Research” cho thấy hướng nghiên cứu về khai phá dữ liệu chuỗi thời gian được xếp thứ 3 trong 10 hướng nghiên cứu sẽ là quan trọng và thách thức nhất [7]. Do đó gom cụm dữ liệu thời gian là một công trình khai thác dữ liệu quan trọng trong rất nhiều lĩnh vực nó là một hướng nghiên cứu rất quan trọng và thách thức vì dữ liệu chuỗi thời gian thì số chiều rất lớn nên việc khai thác dữ liệu chuỗi thời gian cần phải thỏa mãn tính hữu hiệu (có độ phức tạp tính toán thấp) và đảm bảo kết quả đúng.

Đây là một thách thức đã thúc đẩy chúng tôi thực hiện nghiên cứu về lĩnh vực này. Bài toán kết hợp giải thuật gom cụm dựa vào độ dốc tích lũy có trọng số và k-Means để gom cụm dữ liệu chuỗi thời gian. Gom cụm dữ liệu là quá trình phân loại các mẫu thành một tập các nhóm dựa trên một hàm đo khoảng cách nào đó, sao cho các phần tử trong cùng một nhóm sẽ rất giống nhau, các phần tử trong các nhóm khác sẽ rất khác nhau.2 minh họa cho kết quả gom cụm dữ liệu trên không gian 2 chiều. Giải thuật gom cụm phổ biến nhất hiện nay đối với dữ liệu chuỗi thời gian là giải thuật k-Means, do giải thuật k-Means dễ hiện thực và có thời gian thực thi khá nhanh.

Ý tưởng của giải thuật này cho trước một số nguyên dương k, với k là số cụm cần gom. Đầu tiên, ta chọn ngẫu nhiên k đối tượng trong không gian dữ liệu làm các trung tâm cụm ban đầu, sau đó duyệt qua các đối tượng dữ liệu còn lại và dựa trên một hàm tính khoảng cách để gán các đối tượng này vào cụm có trung tâm cụm gần nó nhất, sau đó tính toán lại trung tâm cụm và duyệt qua tất cả các đối tượng dữ liệu để gán lại vào cụm hợp lý cho đến khi không có phép gán nào được thực hiện nữa thì giải thuật dừng. ĐẶNG THANH HÙNG 2 LUẬN VĂN CAO HỌC Ý tưởng chính của đề tài này là thực hiện gom cụm dữ liệu chuỗi thời gian với hai bước (1) dựa vào độ dốc tích lũy có trọng số (Cumulative Weighted Slopes) [8] để thu giảm số chiều của dữ liệu thời gian từ một dữ liệu N chiều thu giảm thành một chiều duy nhất, với áp dụng giải thuật k-Means để gom cụm dữ liệu trên thành các trung tâm cụm ban đầu và (2) áp dụng giải thuật k-Means để gom cụm dữ liệu thời gian với các trung tâm cụm ban đầu được xác định bởi bước 1. Kết quả gom cụm của dữ liệu 2 chiều 1.

Mục tiêu nghiên cứu của đề tài. Mục tiêu nghiên cứu của đề tài trên cơ sở dữ liệu chuỗi thời gian tập trung vào các nội dung sau:  Nghiên cứu các phương pháp gom cụm dữ liệu chuỗi thời gian.  Nghiên cứu độ dốc tích lũy có trọng số.  Kết hợp giải thuật gom cụm dựa vào độ dốc tích lũy có trọng số và k- Means để gom cụm dữ liệu chuỗi thời gian.

 Nghiên cứu sử dụng kd-tree khởi tạo trung tâm cụm ban đầu.  Thử nghiệm trên các bộ dữ liệu mẫu và so sánh kết quả của khởi tạo trung tâm cụm ban đầu ngẫu nhiên, dựa vào kd-tree và khởi tạo trung tâm cụm ban đầu bằng độ dốc tích lũy có trọng số.  Trực quan hóa kết quả gom cụm dữ liệu chuỗi thời gian. ĐẶNG THANH HÙNG 3 LUẬN VĂN CAO HỌC 1.

Phạm vi nghiên cứu. Phương pháp thu giảm số chiều dựa vào độ dốc tích lũy có trọng số và kết hợp giải thuật gom cụm dựa vào độ dốc tích lũy có trọng số và k-Means để gom cụm dữ liệu chuỗi thời gian. Dữ liệu phân tích :  Tập dữ liệu phức hợp Heterogeneous.  Tập dữ liệu chứng khoán Mỹ.

 Tập dữ liệu chứng khoán Việt Nam. Phương pháp nghiên cứu. Sử dụng kết hợp giữa nghiên cứu lý thuyết và nghiên cứu thực tiễn. Nghiên cứu lý thuyết: thu thập các thông tin thông qua nghiên cứu các tài liệu về dữ liệu chuỗi thời gian, các phương pháp gom cụm dữ liệu chuỗi thời gian từ đó rút ra được phương pháp gom cụm chuỗi thời gian thích hợp.

Nghiên cứu thực tiễn: từ kết quả các cơ sở lý thuyết đã rút ra trong quá trình nghiên cứu lý thuyết để áp dụng vào thực tế xây dựng hệ thống gom cụm kết hợp giải thuật gom cụm dựa vào độ dốc tích lũy có trọng số và k-Means để gom cum dữ liệu chuỗi thời gian. Quá trình nghiên cứu thực tiễn sẽ thực hiện các công việc:  Gom cụm với tập dữ liệu phức hợp dùng các tiêu chí đánh giá như: Jaccard, Rand, FM, CSM, NMI để đánh giá chất lượng gom cụm.  Gom cụm với các tập dữ liệu chứng khoán dùng hàm mục tiêu để đánh giá chất lượng gom cụm.  Điều chỉnh giải thuật và các tham số để đạt kết quả có độ chính xác cao.

Ý nghĩa nghiên cứu. Kết quả nghiên cứu giúp chúng ta đánh giá được chất lượng gom cum của giải thuật k-Means kết hợp với các phương pháp: ĐẶNG THANH HÙNG 4 LUẬN VĂN CAO HỌC  Thu giảm số chiều dựa vào độ dốc tích lũy có trọng số.  Khởi tạo trung tâm cụm ban đầu bằng độ dốc tích lũy có trọng số.  Khởi tạo trung tâm cụm ban đầu bằng kd-tree.

 Khởi tạo trung tâm cụm ban đầu bằng ngẫu nhiên. Từ kết quả đánh giá chất lượng gom cụm của các phương pháp giúp chúng ta lựa chọn phương pháp gom cụm thích hợp cho nhu cầu gom cụm dữ liệu chuỗi thời gian của chúng ta như cần thời gian thực thi nhanh hay cần độ chính xác cao… 1. Tóm tắt kết quả đã đạt được. Chúng tôi đã áp dụng phương pháp gom cụm dựa vào độ dốc tích lũy có trọng số để gom cụm dữ liệu chuỗi thời gian, đồng thời áp dụng cấu trúc kd-tree để khởi tạo trung tâm cụm ban đầu cho giải thuật k-Means, và đề xuất phương pháp khởi tạo trung tâm cụm ban đầu dựa vào độ dốc tích lũy có trọng số cho giải thuật k-Means, kết quả thu được là chất lượng lời giải khi khởi tạo trung tâm cụm bằng phương pháp dựa vào độ dốc tích lũy có trọng số tốt hơn về chất lượng lời giải lẫn thời gian thực thi so với giải thuật k-Means khởi tạo trung tâm cụm ban đầu một cách ngẫu nhiên hoặc khởi tạo trung tâm cụm ban đầu áp dụng cấu trúc kd-tree.

Ngoài ra chúng tôi xây dựng được một phương pháp trực quan hóa kết quả gom cụm phù hợp với tập dữ liệu lớn. Cấu trúc luận văn. Các phần còn lại của luận văn được tổ chức như sau: Chương 2: trình bày các lý thuyết và các công trình liên quan làm nguồn tham khảo và là cơ sở cho việc thực hiện luận văn, bao gồm các công trình về độ đo tương tự, các phương pháp thu giảm số chiều, ba cách tiếp cận gom cụm dữ liệu chuỗi thời gian, giải thuật k-Means, giải thuật khởi tạo trung tâm cụm ban đầu và vấn đề chọn giá trị k (số lượng cụm cần gom) tối ưu. Chương 3: trình bày một số vấn đề về gom cụm dữ liệu chuỗi thời gian và đưa ra cách để giải quyết các vấn đề và phác họa kiến trúc tổng quát của hệ thống ĐẶNG THANH HÙNG 5 LUẬN VĂN CAO HỌC “Kết hợp gom cụm dựa vào độ dốc tích lũy có trọng số và k-Means để gom cụm dữ liệu chuỗi thời gian”.

Chương 4: trình bày một số kết quả thực nghiệm và đánh giá. Chương 5: trình bày kết luận của nghiên cứu những đóng góp của đề tài và hướng phát triển. ĐẶNG THANH HÙNG 6 LUẬN VĂN CAO HỌC CHƯƠNG 2: CƠ SỞ LÝ THUYẾT VÀ CÁC CÔNG TRÌNH LIÊN QUAN Chương này trình bày các lý thuyết và các công trình liên quan làm nguồn tham khảo và là cơ sở cho việc thực hiện luận văn, bao gồm các công trình về độ đo tương tự, các phương pháp thu giảm số chiều, ba cách tiếp cận gom cụm dữ liệu chuỗi thời gian, giải thuật k-Means và giải thuật khởi tạo trung tâm cụm ban đầu. Để tính khoảng cách giữa 2 đối tượng X, Y ký hiệu là D(X, Y) có nhiều độ đo tương tự đã được sử dụng như độ đo Euclid, độ đo tương tự giữa các chuỗi nhị phân [9], độ đo tương tự giữa các hàm mật độ xác xuất [10], độ đo xoắn thời gian động [11], độ đo chuỗi con chung dài nhất [12].

Do đó việc lựa chọn một độ đo tương tự tùy thuộc rất nhiều vào lĩnh vực ứng dụng. Trong các bài toán về khai phá dữ liệu chuỗi thời gian, để so sánh hai chuỗi người ta thường sử dụng hai độ đo tương tự là Euclid và xoắn thời gian động (Dynamic Time Warping) để tính khoảng cách giữa 2 đối tượng. Cho hai chuỗi thời gian X = x1, x2, …,xn và Y = y1, y2,…,yn độ đo Euclid giữa hai chuỗi thời gian này được cho bởi công thức. Độ đo khoảng cách Euclid có ưu điểm là dễ hiểu, dễ tính toán, dễ mở rộng cho nhiều bài toán khai phá dữ liệu chuỗi thời gian như gom cụm, phân lớp, nhận dạng mô típ, v.