Tổng quan nghiên cứu

Khai phá dữ liệu chuỗi thời gian là một trong những lĩnh vực then chốt của khoa học máy tính hiện đại khi khối lượng thông tin số hóa tăng trưởng theo cấp số nhân. Trong thực tế, việc ghi nhận tín hiệu y sinh như điện tâm đồ liên tục trong 1 giờ có thể tạo ra dung lượng xấp xỉ 1 Gigabyte dữ liệu, hoặc hàng triệu chỉ số biến động giá chứng khoán được cập nhật từng giây trên các sàn giao dịch. Thuật toán K-Means là phương pháp gom cụm phân hoạch phổ biến nhờ cấu trúc cài đặt trực quan và chi phí tính toán chấp nhận được. Tuy nhiên, giải thuật này mang bản chất leo đồi nên rất dễ rơi vào trạng thái tối ưu cục bộ, đồng thời độ ổn định và thời gian hội tụ phụ thuộc hoàn toàn vào việc khởi tạo ngẫu nhiên các tâm cụm ban đầu. Khi xử lý các tập dữ liệu lớn có số chiều lên tới 512 hay 1024 điểm đo, chi phí tính toán khoảng cách giữa các chuỗi thời gian tăng cao đột biến.

Đề tài luận văn thạc sĩ chuyên ngành Khoa học Máy tính của tác giả Lê Phú, thực hiện tại Trường Đại học Bách Khoa thuộc Đại học Quốc gia Thành phố Hồ Chí Minh dưới sự hướng dẫn khoa học của Phó Giáo sư Tiến sĩ Dương Tuấn Anh, đã giải quyết triệt để thách thức trên. Mục tiêu cốt lõi của nghiên cứu là đề xuất quy trình gom cụm dữ liệu chuỗi thời gian mới thông qua việc nhận dạng các môtíp đại diện để định hướng khởi tạo tâm cụm cho thuật toán K-Means. Công trình hoàn thành vào tháng 7 năm 2011, tiến hành thử nghiệm trên các tập dữ liệu chuỗi thời gian chuẩn từ kho lưu trữ The VCR Time Series Data Mining Archive. Kết quả nghiên cứu mang lại giá trị thực tiễn cao khi giúp rút ngắn thời gian xử lý từ 28% đến 44%, giảm từ 35% đến 52% số vòng lặp hội tụ và nâng cao vượt bậc tính ổn định của hệ thống phân tích dữ liệu.

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 dựa trên sự giao thoa giữa hai nền tảng lý thuyết chính trong khai phá dữ liệu chuỗi thời gian: lý thuyết gom cụm phân hoạch K-Means và mô hình nhận dạng mẫu lặp thường xuyên (môtíp chuỗi thời gian) do nhóm tác giả Jessica Lin và Eamonn Keogh đề xuất năm 2002. Bên cạnh đó, luận văn tích hợp các phương pháp thu giảm số chiều dữ liệu không thích nghi như xấp xỉ gộp từng đoạn (Piecewise Aggregate Approximation - PAA), biến đổi Fourier rời rạc (DFT), biến đổi Wavelet rời rạc (DWT) và phương pháp rời rạc hóa xấp xỉ gộp ký hiệu hóa (Symbolic Aggregate Approximation - SAX).

Khung lý thuyết của đề tài tập trung vào 4 khái niệm cốt lõi:

  1. Chuỗi thời gian và chuỗi con: Một chuỗi thời gian gồm m giá trị quan sát tuần tự, trong đó chuỗi con là một đoạn trích xuất có độ dài n (với n nhỏ hơn m).
  2. Môtíp chuỗi thời gian (1-Motif và K-Motifs): Mẫu chuỗi con xuất hiện lặp lại thường xuyên nhất và có số lượng khớp không tầm thường (non-trivial match) lớn nhất dưới một ngưỡng khoảng cách R xác định.
  3. Độ đo khoảng cách Euclid và tính chất đối xứng: Độ đo hình học dùng để định lượng khoảng cách giữa hai chuỗi thời gian cùng chiều.
  4. Kỹ thuật dừng sớm (Early Abandoning): Cơ chế tối ưu hóa việc kiểm tra điều kiện khoảng cách bằng cách cộng dồn sai số theo từng chiều và ngắt ngay khi tổng vượt ngưỡng R.

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 quốc tế gồm tập dữ liệu đa dạng Heterogeneous và tập dữ liệu tài chính chứng khoán được trích xuất từ The VCR Time Series Data Mining Archive. Cỡ mẫu thử nghiệm bao gồm hàng trăm chuỗi thời gian có độ dài từ 128, 256, 512 đến 1024 chiều. Phương pháp chọn mẫu là chọn mẫu có chủ đích nhằm bao quát các dạng hình thái sóng phức tạp, dữ liệu có độ biến động cao và chiều không gian lớn để kiểm thử năng lực chịu tải của thuật toán.

Quy trình phân tích được thiết kế theo mô hình hai giai đoạn:

  • Giai đoạn 1: Trích xuất các môtíp đặc trưng cho từng chuỗi thời gian bằng giải thuật Brute-Force cải tiến. Thuật toán này tận dụng tính chất đối xứng của khoảng cách Euclid, bất đẳng thức tam giác và kỹ thuật kiểm tra kết thúc sớm để loại bỏ các phép tính thừa. Sau đó, tiến hành gom cụm các môtíp này thành k cụm bằng K-Means để suy dẫn ra các chuỗi thời gian ban đầu đại diện làm tâm khởi tạo.
  • Giai đoạn 2: Áp dụng thuật toán K-Means trên tập dữ liệu chuỗi thời gian ban đầu (dữ liệu thô RAW hoặc dữ liệu nén PAA) với các tâm cụm khởi đầu có điều khiển từ giai đoạn 1.

Lý do lựa chọn giải thuật Brute-Force cải tiến thay vì thuật toán xấp xỉ EMMA là nhằm bảo toàn tính chính xác tuyệt đối của các mẫu đặc trưng mà không làm méo mó cấu trúc dữ liệu do quá trình rời rạc hóa SAX gây ra. Toàn bộ timeline nghiên cứu, xây dựng thuật toán và thực nghiệm kiểm chứng được thực hiện liên tục trong giai đoạn khóa học 2008 đến 2011.

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 đối chứng nghiêm ngặt giữa hai phương pháp K-Means kết hợp môtíp (K-Means/RAW+Motif, K-Means/PAA+Motif) và K-Means truyền thống (K-Means/RAW, K-Means/PAA) đã ghi nhận 4 phát hiện quan trọng:

  1. Giảm thiểu số vòng lặp gom cụm: Phương pháp tích hợp môtíp giúp giảm từ 35% đến 52% số vòng lặp hội tụ. Cụ thể trên tập dữ liệu Heterogeneous 1024 chiều với k = 5 cụm, số vòng lặp của K-Means/RAW giảm từ mức trung bình 18 vòng xuống chỉ còn 8 đến 9 vòng khi có sự hỗ trợ của môtíp đại diện.
  2. Tiết kiệm thời gian thực thi: Tổng thời gian tính toán của hệ thống giảm từ 28% đến 44%. Trên tập dữ liệu chứng khoán 512 chiều, thời gian thực thi của K-Means/RAW giảm từ 12,4 giây xuống còn 7,1 giây khi áp dụng khởi tạo tâm bằng môtíp.
  3. Tăng cường độ ổn định phân cụm: Độ phân tán và khoảng cách thời gian giữa các lần chạy sớm nhất và trễ nhất qua 20 lần thử nghiệm độc lập giảm hơn 60%, loại bỏ triệt để hiện tượng hội tụ bấp bênh do tâm ngẫu nhiên gây ra.
  4. Tối ưu hóa thuật toán nhận diện môtíp: Thuật toán Find-1-Motif Brute-Force cải tiến giúp cắt giảm từ 40% đến 65% số lần gọi hàm tính khoảng cách Euclid so với phiên bản Brute-Force truyền thống nhờ cơ chế dừng sớm và lưu vết quy hoạch động.

Thảo luận kết quả

Nguyên nhân chính giúp phương pháp đạt hiệu năng vượt trội là việc chuyển đổi bài toán khởi tạo tâm từ không gian ngẫu nhiên sang không gian có điều khiển. Môtíp chuỗi thời gian đại diện cho các hình thái dao động điển hình nhất của chuỗi, do đó việc gom cụm trên tập môtíp đã gom nhóm chính xác các đặc trưng cốt lõi trước khi áp dụng lên toàn bộ dữ liệu. So với các nghiên cứu trước đây như thuật toán I-kMeans của Eamonn Keogh (năm 2004) hay phương pháp HAC kết hợp phân tích thành phần chính PCA của Gavrilov (năm 1998), giải pháp của luận văn không đòi hỏi phân giải đa mức Haar Wavelet phức tạp mà vẫn duy trì chất lượng phân cụm tối ưu.

Khi trực quan hóa qua biểu đồ đường biểu diễn thời gian thực thi theo số chiều dữ liệu (từ 128 đến 1024 chiều), đường đồ thị của phương pháp K-Means kết hợp môtíp luôn duy trì độ dốc thấp và nằm tách biệt phía dưới so với đường biểu diễn của K-Means truyền thống. Bảng đối sánh giá trị hàm mục tiêu nội cụm và khoảng cách trung bình giữa các cụm khẳng định rằng độ chính xác phân hoạch của K-Means/RAW+Motif và K-Means/PAA+Motif tương đương nhau, chứng minh kỹ thuật thu giảm số chiều PAA kết hợp môtíp là giải pháp hoàn hảo để xử lý dữ liệu lớn.

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

Từ các kết quả nghiên cứu và thực nghiệm đạt được, luận văn đưa ra 4 khuyến nghị ứng dụng thực tiễn mang tính khả thi cao:

  1. Ứng dụng mô hình gom cụm định hướng môtíp vào hệ thống giám sát công nghiệp: Các kỹ sư hệ thống cần triển khai giải pháp này trong vòng 6 tháng tới tại các trung tâm điều hành IoT nhằm giảm 30% tải tính toán trên máy chủ biên khi phân loại dữ liệu từ hơn 1000 cảm biến áp suất và nhiệt độ.
  2. Tự động hóa việc xác định tham số chiều dài môtíp n và bán kính ngưỡng R: Nhóm nghiên cứu phát triển thuật toán cần xây dựng module tự thích nghi tham số trong vòng 3 quý, đặt mục tiêu nâng độ chính xác nhận diện phân hoạch dữ liệu lên trên 92% mà không cần sự can thiệp tham số thủ công từ người dùng.
  3. Song song hóa thuật toán trích xuất môtíp trên phần cứng đồ họa chuyên dụng: Đội ngũ phát triển phần mềm cần thực hiện tái cấu trúc mã nguồn để tính toán trên GPU trong vòng 12 tháng, hướng tới mục tiêu xử lý thời gian thực các luồng dữ liệu chuỗi thời gian có lưu lượng vượt quá 10 Gigabyte mỗi giờ.
  4. Chuẩn hóa quy trình tiền xử lý và giảm chiều dữ liệu bằng PAA trong phân tích tài chính: Các chuyên gia phân tích dữ liệu tại các công ty chứng khoán cần áp dụng kết hợp PAA và môtíp để phân nhóm hơn 500 mã cổ phiếu có quy luật biến động tương đồng, rút ngắn thời gian tạo báo cáo kỹ thuật định kỳ xuống dưới 2 giây mỗi phiên phân tích.

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

Luận văn thạc sĩ này là tài liệu tham khảo giá trị cho 4 nhóm đối tượng chuyên môn:

  1. Học viên cao học và nghiên cứu sinh chuyên ngành Khoa học Máy tính: Cung cấp nền tảng toán học chặt chẽ về thuật toán phân hoạch, kỹ thuật xấp xỉ chuỗi thời gian và phương pháp tối ưu hóa chi phí tính toán O(m2) trong tìm kiếm môtíp.
  2. Kỹ sư dữ liệu và chuyên gia phát triển hệ thống trí tuệ nhân tạo: Nắm bắt kiến trúc hệ thống gom cụm hai giai đoạn để tích hợp vào các pipeline xử lý dữ liệu lớn, giúp giảm 40% chi phí tài nguyên điện toán đám mây khi huấn luyện mô hình.
  3. Chuyên gia phân tích dữ liệu thị trường chứng khoán và tài chính định lượng: Vận dụng mô hình phân nhóm chuỗi thời gian 512 chiều để nhận diện các nhóm tài sản có mẫu hình kỹ thuật tương đồng, nâng cao hiệu quả phân bổ danh mục đầu tư.
  4. Bác sĩ và chuyên gia công nghệ y tế: Ứng dụng cơ chế trích xuất môtíp để phát hiện các đoạn sóng bất thường trên tín hiệu điện tim đồ (ECG) hoặc điện não đồ (EEG), hỗ trợ chẩn đoán tự động cho hơn 1000 ca bệnh mỗi ngày.

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

Nhận dạng môtíp chuỗi thời gian là gì và đóng vai trò như thế nào trong bài toán gom cụm?
Môtíp chuỗi thời gian là các chuỗi con có tần suất lặp lại nhiều nhất và mang tính đại diện cao nhất cho toàn bộ chuỗi dữ liệu. Trong bài toán gom cụm, thay vì chọn ngẫu nhiên các tâm ban đầu dễ rơi vào điểm tối ưu cục bộ, việc gom cụm trên môtíp giúp xác định các điểm hội tụ chuẩn xác, từ đó định hướng chọn tâm khởi đầu chất lượng cao cho toàn bộ tập dữ liệu.

Kỹ thuật kiểm tra kết thúc sớm (Early Abandoning) giúp tối ưu hiệu năng ra sao?
Kỹ thuật dừng sớm thực hiện tính toán khoảng cách tích lũy từng chiều theo công thức Euclid. Ngay khi tổng khoảng cách tích lũy tại chiều thứ k vượt quá bán kính ngưỡng R, thuật toán lập tức ngắt vòng lặp mà không cần tính tiếp các chiều từ k+1 đến m. Trong thực nghiệm trên dữ liệu 1024 chiều, kỹ thuật này loại bỏ hơn 60% phép tính dư thừa.

Vì sao nghiên cứu sử dụng thuật toán Brute-Force cải tiến thay vì thuật toán EMMA?
Thuật toán EMMA sử dụng phương pháp rời rạc hóa SAX nên tuy có tốc độ nhanh nhưng lại làm mất mát thông tin hình học của chuỗi, dẫn đến việc tìm môtíp thiếu chính xác. Giải thuật Brute-Force cải tiến của luận văn khắc phục nhược điểm tốc độ bằng bất đẳng thức tam giác và kiểm tra dừng sớm, vừa giữ nguyên độ chính xác 100% của khoảng cách Euclid vừa rút ngắn thời gian xử lý.

Phương pháp gom cụm kết hợp môtíp có áp dụng hiệu quả trên dữ liệu thu giảm số chiều PAA không?
Phương pháp hoạt động đặc biệt hiệu quả trên dữ liệu PAA. Thử nghiệm trên tập Heterogeneous cho thấy phương pháp K-Means/PAA+Motif đạt độ chính xác gom cụm tương đương khi chạy trên dữ liệu gốc 1024 chiều, trong khi thời gian tính toán giảm đi hơn 45% và số vòng lặp giảm từ 15 vòng xuống còn khoảng 7 vòng.

Hạn chế cần lưu ý khi ứng dụng phương pháp của luận văn là gì?
Hạn chế chính là người dùng cần xác định trước hai tham số đầu vào gồm chiều dài môtíp n và bán kính ngưỡng R tương thích với đặc thù dữ liệu. Nếu chọn bán kính R quá nhỏ hoặc quá lớn, thời gian quét môtíp có thể tăng thêm khoảng 15% trước khi bước vào giai đoạn gom cụm chính thức.

Kết luận

  • Luận văn đã giải quyết thành công nhược điểm bẫy tối ưu cục bộ và tính bất định của thuật toán K-Means trên dữ liệu chuỗi thời gian bằng cách đề xuất mô hình khởi tạo tâm có điều khiển dựa trên môtíp đại diện.
  • Đóng góp giải thuật Find-1-Motif Brute-Force cải tiến kết hợp tối ưu tính chất đối xứng Euclid, bất đẳng thức tam giác và kỹ thuật dừng sớm, giúp giảm hơn 50% số phép tính khoảng cách.
  • Minh chứng thực nghiệm vững chắc trên các tập dữ liệu chuẩn 512 chiều và 1024 chiều, khẳng định khả năng cắt giảm từ 28% đến 44% thời gian thực thi và từ 35% đến 52% số vòng lặp gom cụm.
  • Khẳng định tính tương thích cao của mô hình khi kết hợp với phương pháp thu giảm số chiều PAA, mở ra giải pháp tối ưu cho bài toán khai phá dữ liệu lớn đa chiều.
  • Tạo tiền đề cho các hướng nghiên cứu mở rộng trong vòng 12 đến 24 tháng tới về việc tự động hóa cấu hình siêu tham số và tính toán phân tán trên GPU.

Độc giả và các nhà nghiên cứu quan tâm có thể khai thác toàn văn luận văn thạc sĩ của tác giả Lê Phú tại Thư viện Đại học Bách Khoa - Đại học Quốc gia Thành phố Hồ Chí Minh để ứng dụng trực tiếp các thuật toán tối ưu vào dự án phân tích dữ liệu chuỗi thời gian thực tế.