Tổng quan nghiên cứu

Trong kỷ nguyên vạn vật kết nối và chuyển đổi số toàn diện, dữ liệu chuỗi thời gian (time series) được thu thập liên tục từ hàng triệu thiết bị cảm biến, thiết bị y tế và hệ thống tài chính với tốc độ gia tăng ước tính hơn 25% mỗi năm. Việc khai phá và phân lớp chính xác nguồn dữ liệu đa chiều này đóng vai trò then chốt trong các bài toán chẩn đoán y khoa, nhận dạng tín hiệu và dự báo công nghiệp. Mặc dù thuật toán 1-lân cận gần nhất (1-NN) kết hợp với độ đo xoắn thời gian động (DTW) từ lâu đã được giới khoa học công nhận là tiêu chuẩn vàng khó bị đánh bại, các giải pháp truyền thống vẫn đối mặt với hai rào cản lớn: độ chính xác chưa tối ưu khi xử lý dữ liệu phức tạp và chi phí tính toán có độ phức tạp bậc hai O(n²), gây quá tải cho bộ vi xử lý CPU thông thường.

Nhằm giải quyết triệt để bài toán trên, luận văn thạc sĩ chuyên ngành Khoa học máy tính của tác giả Võ Đại Dương, thực hiện dưới sự hướng dẫn khoa học của PGS.TS Dương Tuấn Anh tại Trường Đại học Bách Khoa - ĐHQG TP.HCM từ tháng 9 năm 2021 đến tháng 6 năm 2022, đã đề xuất giải pháp đột phá: xây dựng tổ hợp bộ phân lớp 1-NN đa độ đo kết hợp tối ưu hóa song song bằng công nghệ GPU qua nền tảng CUDA.

Nghiên cứu tập trung vào hai mục tiêu cốt lõi: nâng cao độ chính xác phân loại bằng cách tích hợp độ đo khoảng cách Hệ Số Nén (CRD) vào mô hình tổ hợp 5 độ đo nền tảng, đồng thời tái cấu trúc thuật toán để khai thác sức mạnh tính toán song song của phần cứng đồ họa. Đánh giá thực nghiệm toàn diện trên 14 bộ dữ liệu chuẩn từ kho lưu trữ UCR cho thấy mô hình đề xuất đạt độ chính xác trung bình 92% và mang lại tốc độ thực thi trên GPU nhanh hơn trung bình 48 lần so với việc xử lý tuần tự trên CPU, mở ra tiềm năng to lớn cho việc xử lý dữ liệu chuỗi thời gian thời gian thực trong môi trường công nghiệp.

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 ba trụ cột lý thuyết vững chắc trong khoa học máy tính:

Thứ nhất, lý thuyết phân lớp dữ liệu và mô hình tổ hợp bộ phân lớp (Ensemble Learning). Thuật toán 1-NN là giải thuật học có giám sát trực tiếp gán nhãn của mẫu thử dựa trên mẫu huấn luyện có khoảng cách gần nhất. Để khắc phục nhược điểm phụ thuộc vào một độ đo đơn lẻ, mô hình tổ hợp liên kết nhiều bộ phân lớp 1-NN thành phần thông qua cơ chế bỏ phiếu có trọng số (weighted voting), trong đó trọng số của mỗi thành phần được điều chỉnh linh hoạt theo tỉ lệ lỗi phân lớp thực tế.

Thứ hai, hệ thống độ đo khoảng cách đàn hồi (elastic) và không đàn hồi (non-elastic). Luận văn tích hợp 6 độ đo chuyên sâu:

  • Khoảng cách Euclid (ED): Độ đo không đàn hồi cơ bản có độ phức tạp tính toán O(n), so sánh trực tiếp từng cặp điểm tương ứng giữa hai chuỗi có cùng chiều dài.
  • Xoắn thời gian động (DTW): Độ đo đàn hồi sử dụng quy hoạch động để tìm đường xoắn tối ưu giữa hai chuỗi thời gian lệch pha, kết hợp ràng buộc dải Sakoe-Chiba và hình bình hành Itakura để giới hạn cửa sổ xoắn.
  • Kỹ thuật tính chặn dưới LB_Keogh (CDTW): Tạo đường bao biên trên và biên dưới nhằm xấp xỉ cận dưới khoảng cách DTW, giúp loại bỏ sớm các ứng viên không tiềm năng mà không gây hiện tượng loại trừ sai.
  • Đạo hàm xoắn thời gian động (DDTW): Biến đổi chuỗi dữ liệu ban đầu thành chuỗi độ dốc bậc một nhằm triệt tiêu hiện tượng ánh xạ kỳ dị do nhiễu biên độ gây ra.
  • Khoảng cách bất biến độ phức tạp (CID): Sử dụng hệ số điều chỉnh chênh lệch độ phức tạp tín hiệu CE(T) kết hợp khoảng cách Euclid để phân biệt các mẫu có hình dạng tương đồng nhưng thuộc các lớp sinh học hoặc vật lý khác nhau.
  • Khoảng cách Hệ Số Nén (CRD): Phát triển trên nguyên lý độ dài mô tả ngắn nhất (MDL) và entropy Shannon, tính toán tỷ số nén giữa hai chuỗi để định lượng mức độ tương đồng cấu trúc thông tin với độ phức tạp tuyến tính O(n).

Thứ ba, kiến trúc tính toán song song khối lượng lớn (Massively Parallel Computing) trên nền tảng GPU CUDA của NVIDIA, tận dụng cấu trúc phân cấp gồm luồng (threads), khối luồng (thread blocks) và lưới khối (grids) để xử lý đồng thời hàng nghìn phép toán khoảng cách.

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

Nghiên cứu sử dụng nguồn dữ liệu chuẩn mực gồm 14 tập dữ liệu đại diện lấy từ kho dữ liệu The UCR Time Series Archive của nhóm nghiên cứu Eamonn Keogh. Quy mô dữ liệu trải rộng với kích thước tập mẫu huấn luyện từ 18 đến 600 mẫu, tập kiểm thử từ 20 đến 900 mẫu, chiều dài mỗi chuỗi thời gian dao động 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 và tiền xử lý áp dụng quy trình chuẩn hóa dữ liệu nghiêm ngặt bằng phương pháp chuẩn hóa trung bình zero (Z-score normalization) và chuẩn hóa Min-Max về đoạn [0, 1]. Bước này đảm bảo các chuỗi thời gian có cùng thang đo, loại trừ ảnh hưởng của biên độ tuyệt đối và bảo tồn đặc trưng hình dạng nguyên bản.

Để kiểm tra và đánh giá mô hình khách quan, nghiên cứu áp dụng kỹ thuật kiểm tra chéo k-phần (k-fold cross-validation). Trong đó, mỗi tập dữ liệu được phân chia đều thành k phần; tại mỗi vòng lặp, k - 1 phần đóng vai trò dữ liệu huấn luyện để cập nhật trọng số lỗi của 6 bộ phân lớp, phần còn lại được dùng để kiểm thử độc lập.

Về phương pháp lập trình tính toán song song, tác giả đã hiện thực hóa thuật toán bằng ngôn ngữ C++ kết hợp CUDA Toolkit trên hệ điều hành Linux. Đối với các phép tính khoảng cách độc lập như ED, CID, CRD, GPU phân bổ mỗi luồng tính toán một cặp mẫu thử. Đối với các thuật toán đệ quy phức tạp như DTW và DDTW, kỹ thuật song song mặt đầu sóng (Wavefront Parallelism) được triển khai để song song hóa việc tính toán các phần tử trên cùng đường chéo của ma trận xoắn quy hoạch động, triệt tiêu hoàn toàn sự phụ thuộc dữ liệu tuần tự. Toàn bộ tiến trình nghiên cứu và thực nghiệm được tiến hành liên tục trong 10 tháng, từ ngày 08/09/2021 đến ngày 10/06/2022.

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 8 mô hình phân lớp trên 14 bộ dữ liệu thực tế đã mang lại 4 phát hiện khoa học mang tính đột phá:

Thứ nhất, mô hình tổ hợp bổ sung độ đo CRD (kỹ thuật 1NN-EN-CRD) đạt độ chính xác phân lớp vượt trội với mức bình quân 92% trên toàn bộ 14 tập dữ liệu. Kết quả này vượt trội rõ rệt so với các bộ phân lớp 1-NN đơn lẻ như Euclid (đạt khoảng 81%), DTW thuần túy (đạt khoảng 86%) và CID (đạt khoảng 87%).

Thứ hai, việc bổ sung độ đo khoảng cách Hệ Số Nén (CRD) giúp giảm thiểu đáng kể tỷ lệ lỗi so với tổ hợp 5 độ đo ban đầu của Phạm Minh Trí (2020). Cụ thể, trên tập dữ liệu hình ảnh mũi tên ArrowHead (gồm 39 mẫu huấn luyện, 175 mẫu kiểm thử, chiều dài 251 điểm), tỷ lệ lỗi của mô hình 1NN-EN-CRD giảm sâu xuống mức dưới 15%, trong khi trên tập dữ liệu quang phổ thực phẩm Beef (30 mẫu huấn luyện, 30 mẫu kiểm thử, chiều dài 470 điểm), tỷ lệ nhận dạng chính xác đạt trên 83%.

Thứ ba, hiệu năng tăng tốc phần cứng bằng GPU đạt mức tăng trưởng vượt bậc. Thời gian thực thi trung bình của tổ hợp 1NN-EN-CRD trên card đồ họa rời NVIDIA GTX 960 (1024 nhân CUDA, bộ nhớ 4GB GDDR5) đạt tốc độ nhanh hơn 48 lần so với khi chạy trên vi xử lý trung tâm CPU Intel Core i7-6700K xung nhịp 4.00 GHz.

Thứ tư, mô hình thể hiện tính ổn định cao trên các dạng dữ liệu đa ngành: từ dữ liệu hình dạng sinh học loài cá Fish (350 chuỗi, chiều dài 463 điểm, 7 lớp), dữ liệu chuỗi tổng hợp mô phỏng sóng CBF (30 mẫu train, 900 mẫu test, chiều dài 128 điểm, 3 lớp) đến dữ liệu cảm biến cảnh báo hỏng hóc Trace trong nhà máy điện hạt nhân (100 mẫu train, 100 mẫu test, 275 chiều dài, 4 lớp) và tín hiệu nhịp tim y tế ECGFiveDays (23 mẫu train, 861 mẫu test, 136 chiều dài, 2 lớp).

Thảo luận kết quả

Sự thành công vượt bậc của tổ hợp 1NN-EN-CRD bắt nguồn từ tính đa dạng và sự bổ trợ lẫn nhau giữa các độ đo khoảng cách. Trong khi các độ đo đàn hồi như DTW và DDTW xuất sắc trong việc co giãn trục thời gian để bắt khớp các pha lệch, chúng lại dễ bị đánh lừa bởi những chuỗi có cấu trúc entropy khác nhau nhưng mang hình bao tương đối giống nhau. Ngược lại, độ đo CRD phân tích dựa trên mức độ nén và độ dài mô tả thông tin (MDL), trong khi CID định lượng sự dao động phức tạp của từng đoạn dốc. Khi kết hợp qua cơ chế bỏ phiếu gán trọng số thích ứng, nhược điểm của từng độ đo riêng lẻ được triệt tiêu hoàn toàn.

Về mặt hiệu năng tính toán, việc áp dụng phương pháp Song song mặt đầu sóng (Wavefront Parallelism) trên kiến trúc GPU đã phá vỡ rào cản tính toán tuần tự của ma trận quy hoạch động DTW. Dữ liệu thực nghiệm có thể được trực quan hóa sinh động qua các đồ thị đường biểu diễn tỷ lệ lỗi giảm dần qua từng bước gán trọng số, cùng với biểu đồ cột logarit thể hiện thời gian tính toán rút ngắn từ hàng trăm giây trên CPU xuống chỉ còn vài giây ngắn ngủi trên GPU.

So sánh với các nghiên cứu tiền nhiệm của Lines và cộng sự (2015) trên tập độ đo đàn hồi hay công trình của Phạm Minh Trí (2020) chỉ dừng lại ở xử lý đơn luồng CPU, nghiên cứu của Võ Đại Dương không chỉ làm giàu thêm không gian đặc trưng bằng độ đo CRD mà còn giải quyết triệt để nút thắt cổ chai về thời gian thực thi, tạo tiền đề ứng dụng trực tiếp vào các hệ thống dữ liệu lớn.

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

Dựa trên những phát hiện thực nghiệm, luận văn đề xuất 4 định hướng chiến lược nhằm ứng dụng và phát triển giải pháp:

Thứ nhất, mở rộng kiểm thử toàn diện mô hình trên toàn bộ 128 tập dữ liệu thuộc kho lưu trữ mở rộng UCR và UEA Time Series Archive. Các nhóm nghiên cứu trí tuệ nhân tạo cần thực hiện bước đánh giá quy mô lớn này trong thời gian 6 tháng tới để thiết lập bảng chỉ số chuẩn hóa độ chính xác cho từng phân nhóm dữ liệu chuyên biệt (âm thanh, chuyển động, y sinh).

Thứ hai, tái cấu trúc thuật toán sang kiến trúc tính toán phân tán đa GPU (Multi-GPU CUDA) và tận dụng nhân chuyên dụng Tensor Cores trên các dòng GPU máy chủ hiện đại. Kỹ sư tối ưu hóa hiệu năng hệ thống cần đặt mục tiêu cải thiện thời gian xử lý thêm từ 3 đến 5 lần đối với các chuỗi thời gian có độ dài vượt mức 1.000 điểm dữ liệu trong lộ trình 12 tháng.

Thứ ba, tích hợp thuật toán lọc chặn dưới đa tầng (Multi-tier Cascading Lower Bounds) kết hợp chặt chẽ giữa LB_Keogh và chỉ số entropy của CRD. Giải pháp này do các nhà phát triển phần mềm lõi thực hiện nhằm loại bỏ sớm trên 75% các phép tính ma trận không cần thiết trước khi đẩy dữ liệu vào bộ nhớ chia sẻ GPU, giúp giảm tối đa độ trễ truyền thông qua bus PCIe.

Thứ tư, chuyển giao và thương mại hóa mô hình vào các hệ sinh thái giám sát thông minh thời gian thực, cụ thể là hệ thống cảnh báo sớm loạn nhịp tim trong y tế số (tương tự mẫu ECGFiveDays) và giám sát an toàn vận hành lò phản ứng hoặc dây chuyền tự động hóa (tương tự mẫu Trace), đảm bảo ngưỡng phản hồi trễ dưới 50 mili-giây.

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

Nội dung và mã nguồn thuật toán của luận văn mang lại giá trị thực tiễn to lớn cho 4 nhóm đối tượng chính:

Nhóm 1: Các chuyên gia dữ liệu (Data Scientists) và kỹ sư học máy (Machine Learning Engineers) đang trực tiếp xây dựng các hệ thống phân loại cảm biến IoT, nhận dạng giọng nói, phát hiện bất thường tài chính và phân tích chuỗi thời gian công nghiệp.

Nhóm 2: Lập trình viên hệ thống và kỹ sư điện toán hiệu năng cao (HPC Engineers) cần tài liệu tham khảo chi tiết về kỹ thuật song song hóa 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 đối với dữ liệu ma trận đa chiều.

Nhóm 3: Các nhà nghiên cứu và phát triển thiết bị y tế thông minh đang tìm kiếm giải pháp thuật toán nhẹ, độ chính xác cao (trên 90%) để nhúng vào phần mềm phân tích tín hiệu điện tim (ECG), điện não đồ (EEG) và hình ảnh y khoa.

Nhóm 4: Giảng viên, nghiên cứu sinh và học viên cao học thuộc các chuyên ngành Khoa học máy tính, Kỹ thuật dữ liệu và Trí tuệ nhân tạo cần tài liệu học thuật hoàn chỉnh từ tổng quan lý thuyết, khảo sát các công trình liên quan đến quy trình thực nghiệm chuẩn mực.

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

Vì sao bộ phân lớp 1-NN vẫn là lựa chọn hàng đầu cho bài toán phân lớp chuỗi thời gian?

Thuật toán 1-NN không yêu cầu giai đoạn huấn luyện phức tạp mà phân lớp trực tiếp dựa trên độ tương đồng giữa các chuỗi dữ liệu. Khi kết hợp cùng các độ đo khoảng cách phù hợp như DTW hay CRD, 1-NN nắm bắt trọn vẹn đặc trưng hình dạng cục bộ và toàn cục mà không làm mất mát thông tin qua các phép biến đổi không gian như một số mô hình học sâu.

Độ đo khoảng cách Hệ Số Nén (CRD) tạo ra sự khác biệt gì so với khoảng cách Euclid?

Khoảng cách Euclid thuần túy rất nhạy cảm với nhiễu và chỉ so sánh từng điểm tại cùng chỉ số thời gian. Ngược lại, CRD dựa trên nguyên lý độ dài mô tả ngắn nhất (MDL) và hàm entropy Shannon để đo lường lượng thông tin chung giữa hai chuỗi, giúp nhận diện chính xác các tín hiệu có dạng sóng tương đồng nhưng lệch biên độ hoặc chứa thành phần tần số khác nhau.

Kỹ thuật Song song mặt đầu sóng (Wavefront Parallelism) giải quyết vấn đề gì trên GPU?

Trong giải thuật DTW, phần tử tại vị trí (i, j) của ma trận tích lũy phụ thuộc trực tiếp vào ba phần tử lân cận trước đó. Phương pháp song song mặt đầu sóng nhóm các ô nằm trên cùng một đường chéo (không có sự phụ thuộc lẫn nhau) để tính toán đồng thời trên hàng trăm luồng CUDA, giúp khai thác tối đa năng lực xử lý SIMD của card đồ họa.

Cơ chế cập nhật trọng số trong tổ hợp bộ phân lớp hoạt động như thế nào?

Ban đầu, tất cả 6 bộ phân lớp thành phần được gán trọng số đóng góp bằng nhau (bằng 1). Sau mỗi lượt kiểm tra chéo, hệ thống tính toán tỷ lệ lỗi của từng độ đo; bộ phân lớp nào có tỷ lệ lỗi càng thấp sẽ được tự động nâng cao tỷ lệ trọng số bỏ phiếu, giúp quyết định phân lớp chung luôn phản ánh ưu thế của các chuyên gia chính xác nhất.

Tác giả đã thực nghiệm trên cấu hình phần cứng nào để đạt được mức tăng tốc 48 lần?

Thực nghiệm được triển khai trên hệ thống máy tính trang bị CPU Intel Core i7-6700K xung nhịp 4.00 GHz, 32GB RAM kết hợp với card đồ họa NVIDIA GeForce GTX 960 (kiến trúc Maxwell, 8 bộ xử lý đa luồng SM, 1024 nhân CUDA, 4GB bộ nhớ GDDR5 băng thông 112 GB/s), chạy trên môi trường ngôn ngữ R và C++ tối ưu.

Kết luận

  • Luận văn đã hoàn thành xuất sắc mục tiêu đề ra khi nghiên cứu, thiết kế và hiện thực hóa thành công tổ hợp 6 bộ phân lớp 1-NN đa độ đo kết hợp công nghệ xử lý song song GPU CUDA.
  • Việc tích hợp thêm độ đo khoảng cách Hệ Số Nén (CRD) đã tạo nên sự đa dạng tối ưu cho không gian đo lường, nâng độ chính xác phân lớp bình quân lên ngưỡng 92% trên 14 bộ dữ liệu mẫu UCR.
  • Ứng dụng kỹ thuật tính toán song song mặt đầu sóng trên GPU giúp rút ngắn thời gian thực thi trung bình 48 lần so với xử lý tuần tự truyền thống trên CPU.
  • Nghiên cứu mở ra hướng tiếp cận hoàn chỉnh, dung hòa hoàn hảo giữa hai mục tiêu: nâng cao độ chính xác nhận dạng và giảm thiểu tối đa chi phí thời gian tính toán.
  • Độc giả, nhà nghiên cứu và các kỹ sư phần mềm quan tâm đến tối ưu hóa thuật toán chuỗi thời gian có thể tải toàn văn công trình luận văn thạc sĩ của tác giả Võ Đại Dương để tham khảo chi tiết công thức toán học và thiết kế thuật toán song song hóa.