Tổng quan nghiên cứu

Khai phá dữ liệu chuỗi thời gian đang là một trong những bài toán trọng tâm của lĩnh vực khoa học dữ liệu và trí tuệ nhân tạo, đặc biệt trong bối cảnh dữ liệu chuỗi thời gian phát sinh liên tục với dung lượng lớn từ các thiết bị thông minh, cảm biến IoT, thiết bị y tế và thị trường tài chính. Thách thức cốt lõi đặt ra là dữ liệu chuỗi thời gian thường có số chiều cao, tồn tại nhiễu, có sự co giãn về biên độ và lệch pha theo thời gian, khiến các mô hình học máy truyền thống gặp nhiều trở ngại về cả độ chính xác lẫn hiệu năng tính toán.

Mục tiêu chính của đề tài là xây dựng mô hình phân lớp chuỗi thời gian có độ chính xác cao dựa trên tổ hợp bộ phân lớp 1-lân cận gần nhất (1-NN) kết hợp 6 độ đo khoảng cách đa dạng, đồng thời giải quyết triệt để nút thắt về thời gian thực thi bằng cách song song hóa toàn diện trên kiến trúc GPU sử dụng mô hình lập trình CUDA. Nghiên cứu được triển khai và hoàn thành trong giai đoạn 2021 - 2022 tại Trường Đại học Bách Khoa, Đại học Quốc gia Thành phố Hồ Chí Minh thuộc chuyên ngành Khoa học máy tính.

Ý nghĩa thực tiễn của công trình thể hiện rõ nét qua các chỉ số định lượng cụ thể: mô hình phân lớp đề xuất đạt độ chính xác trung bình lên tới 92% (tương ứng tỷ lệ lỗi giảm xuống chỉ còn khoảng 8%) trên 14 bộ dữ liệu chuẩn quốc tế từ kho lưu trữ UCR. Đồng thời, việc ứng dụng công nghệ xử lý song song trên 1024 nhân CUDA của GPU giúp rút ngắn thời gian xử lý trung bình tới 48 lần so với việc thực thi tuần tự trên CPU, mang lại giải pháp đột phá cho các hệ thống phân loại dữ liệu lớn theo thời gian thực.

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 giải thuật 1-lân cận gần nhất (1-NN), vốn được cộng đồng khoa học quốc tế công nhận là chuẩn mực hiệu quả trong phân loại chuỗi thời gian, kết hợp cùng lý thuyết học tổ hợp (ensemble learning). Để khắc phục hạn chế của các bộ phân lớp đơn lẻ, mô hình tổ hợp tích hợp 6 độ đo khoảng cách thuộc hai nhóm chính:

  • Nhóm độ đo khoảng cách đàn hồi (elastic distance): Độ đo xoắn thời gian động DTW (Dynamic Time Warping) với độ phức tạp tính toán cơ sở nhằm căn chỉnh sự lệch pha thời gian; độ đo xoắn thời gian động cải tiến DDTW (Derivative Dynamic Time Warping) dựa trên đạo hàm để triệt tiêu các điểm kỳ dị; và độ đo DTW tích hợp kỹ thuật tính chặn dưới của Keogh (LB_Keogh hay CDTW) giúp thu hẹp không gian tìm kiếm ma trận xoắn.
  • Nhóm độ đo khoảng cách không đàn hồi (non-elastic distance): Độ đo khoảng cách Euclid truyền thống (ED); độ đo bất biến với độ phức tạp CID (Complexity-invariant Distance) với hệ số điều chỉnh độ phức tạp tuyến tính; và độ đo khoảng cách hệ số nén CRD (Compression Rate Distance) dựa trên nguyên lý độ dài mô tả ngắn nhất (MDL) và hàm entropy thông tin có độ phức tạp thời gian tuyến tính.

Về mặt tính toán hiệu năng cao, nghiên cứu áp dụng khung kiến trúc tính toán song song CUDA (Compute Unified Device Architecture) của NVIDIA và thuật toán song song mặt đầu sóng (Wavefront parallelism) nhằm phân rã các tính toán đệ quy phức tạp của ma trận quy hoạch động trên GPU.

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

Nguồn dữ liệu thực nghiệm bao gồm 14 tập dữ liệu chuẩn mực từ kho lưu trữ chuỗi thời gian quốc tế UCR (The UCR Time Series Archive), đại diện cho nhiều lĩnh vực thực tế như hình ảnh biên dạng (ArrowHead, BeetleFly, DistalPhalanxOutlineCorrect, Fish, FaceFour), tín hiệu quang phổ thực phẩm (Beef, Ham), chuỗi tín hiệu cảm biến công nghiệp và giao thông (Trace, Chinatown), dữ liệu y sinh điện tâm đồ (ECGFiveDays), dữ liệu tổng hợp nhân tạo (CBF) và dữ liệu sinh học (Fungi, InsectEPGRegularTrain).

Quy mô mẫu thử nghiệm bao quát nhiều kích cỡ đa dạng, từ các tập dữ liệu nhỏ gồm 20 mẫu huấn luyện và 20 mẫu kiểm thử cho đến các tập dữ liệu lớn lên tới 600 mẫu huấn luyện và 900 mẫu kiểm thử, với độ dài chuỗi biến thiên từ 24 đến 512 điểm dữ liệu và số lượng lớp phân loại từ 2 đến 18 lớp. Phương pháp chọn mẫu áp dụng quy chuẩn phân tách tập huấn luyện và kiểm thử độc lập kết hợp với quy trình kiểm tra chéo k-phần (k-fold cross-validation với 4 phân đoạn dữ liệu) nhằm liên tục cập nhật và tối ưu hóa trọng số đóng góp của từng độ đo thành phần dựa trên tỷ lệ lỗi thực tế.

Lý do lựa chọn giải pháp phân tích này là nhằm tận dụng sự bổ khuyết lẫn nhau giữa các độ đo đàn hồi và không đàn hồi, giúp bộ phân lớp có khả năng thích ứng linh hoạt trước mọi dạng biến dạng hình học của chuỗi dữ liệu. Quá trình thực nghiệm được triển khai từ tháng 9 năm 2021 đến tháng 6 năm 2022 trên hệ thống máy tính trang bị CPU Intel Core i7-6700K 4.00 GHz, 32GB RAM và card đồ họa chuyên dụng NVIDIA GeForce GTX 960 với 1024 nhân xử lý CUDA.

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 sánh giữa 8 phương pháp phân loại khác nhau trên toàn bộ 14 bộ dữ liệu chuẩn UCR đã đem lại những phát hiện quan trọng:

Thứ nhất, tổ hợp bộ phân lớp đề xuất kết hợp 6 độ đo khoảng cách (1NN-EN-CRD) đạt độ chính xác trung bình 92%, vượt trội rõ rệt so với tổ hợp 5 độ đo truyền thống (1NN-EN) vốn chỉ đạt khoảng 88%, đồng thời vượt xa tất cả các bộ phân lớp 1-NN đơn lẻ sử dụng từng độ đo độc lập như Euclid hay DTW thuần túy.

Thứ hai, việc bổ sung độ đo khoảng cách hệ số nén CRD tạo ra sự cải thiện độ chính xác đột phá trên các tập dữ liệu có độ biến thiên phức tạp; ví dụ trên tập dữ liệu hình ảnh ArrowHead gồm 175 mẫu kiểm thử 3 lớp, tỷ lệ lỗi phân lớp giảm mạnh từ 20% xuống mức dưới 15%.

Thứ ba, việc ứng dụng công nghệ tính toán song song trên GPU đem lại hiệu năng tăng tốc vượt bậc với tốc độ phân loại nhanh hơn trung bình 48 lần so với việc xử lý tuần tự trên vi xử lý CPU tiêu chuẩn.

Thứ tư, thuật toán song song mặt đầu sóng đã giải quyết thành công sự phụ thuộc dữ liệu trong quá trình tính toán ma trận DTW và DDTW, giúp khai thác tối đa băng thông bộ nhớ 112.1 GB/s và năng lực xử lý dấu phẩy động 2.644 TFLOPS của GPU.

Thảo luận kết quả

Nguyên nhân chính dẫn đến sự gia tăng vượt bậc về độ chính xác là do độ đo CRD khai thác hiệu quả sự tương quan entropy và độ dài mô tả giữa hai chuỗi, giúp phân biệt chuẩn xác các đối tượng có giá trị khoảng cách Euclid tương đồng nhưng cấu trúc hình thái khác biệt. Khi kết hợp cùng độ đo bất biến độ phức tạp CID và các độ đo xoắn thời gian DTW, DDTW, mô hình tổ hợp sở hữu góc nhìn đa chiều, triệt tiêu tối đa các trường hợp phân lớp sai cục bộ của từng phương pháp riêng lẻ.

Khi đối sánh với các công trình quốc tế kinh điển như nghiên cứu của nhóm tác giả Lines cùng cộng sự chỉ thuần túy sử dụng các độ đo đàn hồi hay công trình năm 2020 của Phạm Minh Trí chưa tối ưu hóa phần cứng, phương pháp đề xuất thể hiện ưu thế áp đảo về cả tính toàn diện của các phép đo lẫn tốc độ tính toán thực tế.

Trong các báo cáo phân tích học thuật, các kết quả này có thể được trực quan hóa tối ưu thông qua hai dạng biểu diễn:

  • Biểu đồ thanh nhóm (grouped bar chart) so sánh trực quan thời gian thực thi (tính bằng giây) giữa môi trường CPU và GPU trên từng tập dữ liệu, làm nổi bật khoảng cách chênh lệch tốc độ lên tới hàng chục lần.
  • Đồ thị đường kết hợp bảng đối chiếu ma trận nhầm lẫn (confusion matrix) biểu diễn tỷ lệ suy giảm sai số phân loại của mô hình 1NN-EN-CRD so với 7 cấu hình thuật toán còn lại trên 14 bộ dữ liệu mẫu.

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

Nhằm phát huy tối đa các kết quả đạt được của luận văn và mở rộng phạm vi ứng dụng thực tế, các giải pháp và khuyến nghị hành động cụ thể bao gồm:

  • Nâng cấp thuật toán song song mặt đầu sóng trên các kiến trúc GPU hiện đại: Đội ngũ phát triển phần mềm cần tái cấu trúc các nhân CUDA (kernels) để khai thác bộ nhớ Tensor Core trên các dòng GPU thế hệ mới, đặt mục tiêu cắt giảm độ trễ tính toán xuống dưới 0.05 giây đối với các chuỗi thời gian dài hơn 1000 điểm dữ liệu trước quý 4 năm 2023.
  • Mở rộng tập độ đo đặc trưng miền tần số: Nhóm nghiên cứu xử lý tín hiệu nên tích hợp thêm các phép biến đổi như Fourier biến đổi nhanh (FFT) hoặc biến đổi Wavelet vào tổ hợp phân lớp, hướng tới mục tiêu nâng tỷ lệ phân lớp chính xác đạt mốc 95% trên các tập dữ liệu có độ nhiễu cao trong vòng 12 tháng tới.
  • Triển khai ứng dụng vào hệ thống giám sát y tế và công nghiệp thông minh: Các kỹ sư hệ thống nhúng cần tích hợp mô hình 1NN-EN-CRD tăng tốc GPU vào các thiết bị phân tích nhịp tim ECG và cảm biến phát hiện sự cố nhà máy điện, đảm bảo năng lực phân loại tự động hơn 1000 chuỗi tín hiệu mỗi giây trong giai đoạn 2024 - 2025.
  • Chuẩn hóa và phát hành thư viện mã nguồn mở: Phòng thí nghiệm chuyên ngành cần tiến hành đóng gói toàn bộ mã nguồn C++/CUDA và giao diện R thành một thư viện phần mềm chuẩn hóa, dự kiến thu hút hơn 500 lượt triển khai thử nghiệm từ cộng đồng nghiên cứu học máy trong vòng 2 năm tới.

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

Luận văn là tài liệu tham khảo giá trị và thiết thực cho nhiều nhóm chuyên gia và tổ chức:

  • Học viên cao học, nghiên cứu sinh và giảng viên chuyên ngành Khoa học máy tính, Khoa học dữ liệu và Trí tuệ nhân tạo: Cung cấp cơ sở lý thuyết toàn diện về khai phá dữ liệu chuỗi thời gian, các giải thuật 1-NN đa độ đo và phương pháp đánh giá thực nghiệm chuẩn mực trên kho dữ liệu UCR.
  • Kỹ sư công nghệ và lập trình viên hệ thống tính toán hiệu năng cao (HPC): Cung cấp hướng dẫn chi tiết về kỹ thuật song song hóa thuật toán quy hoạch động, mô hình lập trình CUDA và phương pháp tối ưu hóa bộ nhớ GPU để đạt mức tăng tốc xử lý 48 lần.
  • Chuyên gia phân tích dữ liệu y tế và xử lý tín hiệu sinh học: Nắm bắt phương pháp phân loại chính xác các tín hiệu điện tim ECG (như bộ dữ liệu ECGFiveDays với 861 mẫu kiểm thử) phục vụ chẩn đoán bệnh lý tim mạch tự động.
  • Kỹ sư nghiên cứu và phát triển hệ thống IoT công nghiệp: Ứng dụng mô hình phân loại chuỗi thời gian đa lớp để giám sát dữ liệu cảm biến (như bộ dữ liệu Trace mô phỏng nhà máy điện hạt nhân) nhằm cảnh báo sớm rủi ro hỏng hóc thiết bị.

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

  • Tại sao giải thuật 1-NN lại được xem là chuẩn mực vượt trội trong phân loại chuỗi thời gian? Giải thuật 1-NN giữ nguyên vẹn cấu trúc hình học và đặc tính phụ thuộc thời gian của chuỗi dữ liệu mà không làm biến dạng thông tin như một số mô hình trích xuất đặc trưng. Khi kết hợp với các độ đo khoảng cách phù hợp như DTW hay CRD, 1-NN đạt độ chính xác trung bình trên 90% và rất khó bị đánh bại bởi các thuật toán học máy phức tạp khác.

  • Độ đo khoảng cách hệ số nén CRD mang lại ưu thế gì so với khoảng cách Euclid truyền thống? Khoảng cách Euclid chỉ so sánh điểm đối điểm trên các chuỗi có cùng biên độ và pha, trong khi CRD tích hợp thêm hệ số nén dựa trên hàm entropy thông tin. Điều này giúp CRD phân biệt chính xác hai chuỗi có cùng khoảng cách hình học nhưng khác biệt về bản chất cấu trúc, với chi phí tính toán tối ưu chỉ ở mức tuyến tính.

  • Kỹ thuật song song mặt đầu sóng (Wavefront) giải quyết khó khăn gì trên GPU? Trong thuật toán DTW và DDTW, việc tính toán từng phần tử trong ma trận xoắn phụ thuộc đệ quy vào ba phần tử lân cận trước đó. Thuật toán song song mặt đầu sóng phân nhóm các phần tử độc lập trên cùng đường chéo thành từng mặt sóng, cho phép hàng nghìn nhân CUDA xử lý đồng thời mà không bị xung đột dữ liệu.

  • Tốc độ xử lý của mô hình trên GPU nhanh hơn CPU cụ thể là bao nhiêu? Qua thực nghiệm chi tiết trên 14 bộ dữ liệu mẫu, hệ thống GPU NVIDIA GeForce GTX 960 với 1024 nhân tính toán đạt tốc độ xử lý nhanh hơn trung bình 48 lần so với vi xử lý CPU Intel Core i7-6700K 4.00 GHz, giúp các tác vụ phân loại tốn hàng giờ trên CPU rút ngắn xuống chỉ còn vài giây.

  • Phương pháp đề xuất đã được kiểm chứng trên những dạng dữ liệu thực tế nào? Mô hình đã được thử nghiệm thành công trên 14 bộ dữ liệu chuẩn UCR với đa dạng ứng dụng: nhận dạng hình ảnh 7 loài cá (Fish), phân loại quang phổ 5 nhóm thịt bò (Beef), nhận diện nhịp tim 2 lớp (ECGFiveDays), mô phỏng sự cố cảm biến thiết bị (Trace) và phân loại 18 loài nấm (Fungi).

Kết luận

  • Luận văn đã thiết kế và hiện thực thành công tổ hợp bộ phân lớp 1-NN tích hợp 6 độ đo khoảng cách bao gồm Euclid, DTW, DTW chặn dưới LB_Keogh, DDTW, CID và độ đo mới CRD.
  • Bổ sung độ đo khoảng cách hệ số nén CRD giúp nâng cao độ chính xác phân loại toàn diện của mô hình tổ hợp lên mức trung bình 92% trên 14 bộ dữ liệu thực nghiệm chuẩn UCR.
  • Tối ưu hóa thuật toán song song mặt đầu sóng trên nền tảng GPU CUDA, giúp cải thiện tốc độ thực thi vượt trội với mức tăng tốc trung bình 48 lần so với CPU.
  • Đề xuất lộ trình phát triển rõ ràng trong giai đoạn 2023 - 2025 nhằm mở rộng các độ đo miền tần số và nhúng mô hình vào các hệ thống chẩn đoán y tế và giám sát công nghiệp thời gian thực.
  • Các nhà nghiên cứu và kỹ sư dữ liệu quan tâm có thể khai thác khung kiến trúc và giải pháp thuật toán của công trình này để giải quyết các bài toán phân tích chuỗi thời gian quy mô lớn.