Tổng quan luận án

Luận án tiến sĩ kỹ thuật chuyên ngành Khoa học máy tính (mã số: 62.01) của nghiên cứu sinh Bùi Công Giao, được thực hiện dưới sự hướng dẫn khoa học của PGS. Dương Tuấn Anh tại Trường Đại học Bách khoa – Đại học Quốc gia TP. Hồ Chí Minh (năm 2019), mang tiêu đề: "Tìm kiếm tương tự trên chuỗi thời gian dạng luồng" (Similarity Search in Streaming Time Series).

Tính cấp thiết và khoảng trống nghiên cứu

Dữ liệu chuỗi thời gian dạng luồng xuất hiện phổ biến trong nhiều ứng dụng thực tế như phân tích lưu lượng mạng máy tính, giám sát thiết bị di động trong thời gian thực, theo dõi tín hiệu thiên văn và giám sát giao dịch chứng khoán. Theo phân tích của tác giả, xử lý chuỗi thời gian dạng luồng đặt ra nhiều thách thức lớn:

  • Dữ liệu đến trực tuyến, liên tục, hệ thống không thể kiểm soát thứ tự dữ liệu tới.
  • Khối lượng dữ liệu tiềm năng là vô hạn, không thể lưu trữ toàn bộ trong bộ nhớ chính; một phần tử sau khi xử lý chỉ được lưu trữ tạm thời trong một khoảng thời gian xác định rồi bị giải phóng hoặc hủy bỏ.
  • Thuật toán xử lý bắt buộc phải có độ phức tạp thời gian thấp và xử lý theo cơ chế quét một lần (one-pass scan).

Khoảng trống nghiên cứu then chốt mà tác giả xác định là: Các phương pháp tìm kiếm tương tự trên chuỗi thời gian tĩnh không tương thích trực tiếp với môi trường luồng. Các công trình nghiên cứu về chuỗi thời gian dạng luồng trước đó thường mắc phải hai hạn chế lớn: hoặc có chi phí tính toán rất cao, hoặc bỏ qua bước chuẩn hóa dữ liệu (data normalization). Việc không chuẩn hóa dữ liệu dẫn đến các sai số nghiêm trọng, cụ thể là gây ra hiện tượng tìm sót (false dismissals) do sự khác biệt về biên độ hoặc độ lệch pha của tín hiệu.

Mục tiêu nghiên cứu

Luận án xác định hai nhiệm vụ nghiên cứu trọng tâm với các mục tiêu cụ thể:

  • Nhiệm vụ 1: Xây dựng các phương pháp tìm kiếm tương tự trên chuỗi thời gian dạng luồng
    1. Mục tiêu 1.1: Xây dựng các phương pháp tìm kiếm tương tự bằng độ đo khoảng cách Euclid (Euclidean distance), kết hợp các phép biến đổi thu giảm số chiều, chuẩn hóa z-score gia tăng và cấu trúc chỉ mục đa mức phân giải dựa trên cây R-tree/R*-tree.
    2. Mục tiêu 1.2: Xây dựng các phương pháp tìm kiếm tương tự bằng độ đo xoắn thời gian động (Dynamic Time Warping - DTW), kết hợp chuẩn hóa gia tăng và các kỹ thuật tăng tốc như hàm chặn dưới, cập nhật hình bao chuỗi con gia tăng, mở rộng cho các chuỗi có chiều dài khác nhau.
  • Nhiệm vụ 2: Ứng dụng các phương pháp tìm kiếm tương tự để giải quyết hai bài toán khai phá dữ liệu luồng thực tế
    1. Mục tiêu 2.1: Giải quyết bài toán dự báo trực tuyến (online forecasting) trên chuỗi thời gian dạng luồng có xu hướng và tính mùa vụ bằng độ đo DTW, kết hợp điểm cực trị quan trọng và kỹ thuật học trì hoãn (lazy learning).
    2. Mục tiêu 2.2: Giải quyết bài toán phát hiện $k$ chuỗi con bất thường nhất (top-k discords detection) trong chuỗi thời gian dạng luồng bằng độ đo Euclid và bộ kỹ thuật cắt tỉa xếp tầng.

Đối tượng và phạm vi nghiên cứu

  • Đối tượng nghiên cứu: Bài toán tìm kiếm tương tự xấp xỉ trên chuỗi thời gian dạng luồng đơn biến (univariate streaming time series).
  • Phạm vi nghiên cứu:
    • Về dạng truy vấn: Đối với nhiệm vụ 1, phạm vi tập trung vào truy vấn tĩnh (static query) trên luồng dữ liệu. Đối với nhiệm vụ 2, phạm vi được mở rộng cho truy vấn dạng luồng (streaming query), trong đó chuỗi truy vấn thay đổi liên tục theo từng mốc thời gian.
    • Về cơ chế dữ liệu: Dữ liệu được thu thập và lưu giữ trong bộ đệm xoay vòng quy mô lớn (large-scaled circular buffer).

Tổng quan tài liệu và vị trí của luận án

Các hướng nghiên cứu trước đây

Luận án tiến hành khảo cứu và hệ thống hóa các hướng nghiên cứu nền tảng:

  • Tìm kiếm tương tự bằng độ đo Euclid và lập chỉ mục: Agrawal và cộng sự (1993, 1995) thiết lập khung phân tích GEMINI, sử dụng biến đổi Fourier rời rạc (DFT) kết hợp cấu trúc chỉ mục R-tree để tìm kiếm chuỗi thời gian tĩnh. Các nghiên cứu sau đó mở rộng sang biến đổi Wavelet (DWT) và biến đổi xấp xỉ gộp từng đoạn (PAA). Tuy nhiên, các công trình này phần lớn mặc định dữ liệu đã chuẩn hóa hoặc bỏ qua chuẩn hóa trong môi trường luồng.
  • Tăng tốc tính toán khoảng cách Euclid: Rakthanmanon và cộng sự (2012) đề xuất bộ kỹ thuật UCR-ED trên chuỗi thời gian tĩnh, kết hợp chuẩn hóa z-score và kỹ thuật từ bỏ sớm (early abandoning).
  • Độ đo xoắn thời gian động (DTW) và kỹ thuật chặn dưới: Berndt và Clifford (1994) áp dụng DTW vào chuỗi thời gian; Sakoe và Chiba (1978), Itakura (1975) đề xuất các dải giới hạn không gian tính toán quy hoạch động; Kim và cộng sự (2001) đề xuất hàm chặn dưới LB_Kim; Keogh và Ratanamahatana (2005) đề xuất hàm chặn dưới LB_Keogh. Rakthanmanon và cộng sự (2012) tổng hợp bộ kỹ thuật UCR-DTW với LB_Keogh nghịch và cơ chế xếp tầng. Silva và cộng sự (2018) phát triển PrunedDTW để cắt tỉa các ô tính toán không triển vọng.
  • Tìm kiếm DTW trên luồng dữ liệu: Sakurai và cộng sự (2007) đề xuất thuật toán SPRING cho phép tìm kiếm chuỗi con tương tự trên luồng dữ liệu bằng DTW với thời gian thực thi nhanh, nhưng SPRING không hỗ trợ dữ liệu chuẩn hóa.
  • Phát hiện bất thường và dự báo: Keogh và cộng sự (2005) đề xuất thuật toán HOT SAX phát hiện chuỗi con bất thường (time series discord) trên dữ liệu tĩnh.

Khoảng trống nghiên cứu được luận án giải quyết

Luận án định vị trọng tâm giải quyết các bất cập tồn tại:

  1. Thiếu kỹ thuật chuẩn hóa dữ liệu trực tuyến hiệu quả: Luận án xây dựng các thuật toán chuẩn hóa z-score gia tăng và chuẩn hóa min-max gia tăng cho luồng dữ liệu.
  2. Rào cản chiều dài cố định trong UCR-DTW: UCR-DTW chỉ so khớp hai chuỗi có cùng chiều dài $m = n$; luận án mở rộng hàm chặn dưới LB_Keogh để xử lý các chuỗi có chiều dài chênh lệch trong biên độ dải Sakoe-Chiba.
  3. Hạn chế của SPRING: Cải tiến thuật toán SPRING để hoạt động chính xác trên dữ liệu được chuẩn hóa min-max gia tăng.
  4. Tối ưu hóa cấu trúc chỉ mục không gian: Cải tiến kỹ thuật đóng gói STR cho cây R-tree nhằm giảm thời gian truy vấn vùng đa mức phân giải.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết và khái niệm nền tảng

  • Độ đo khoảng cách Euclid: Tính toán theo công thức $D(A, B) = \sqrt{\sum_{i=1}^{n} (a_i - b_i)^2}$, thỏa mãn các tiên đề của không gian metric (đối xứng, không âm, bất đẳng thức tam giác), có độ phức tạp $O(n)$, thích hợp với các phép biến đổi trực giao và cấu trúc chỉ mục không gian.
  • Độ đo xoắn thời gian động (DTW): Ánh xạ phi tuyến một-nhiều giữa hai chuỗi thời gian $C = {c_1, \dots, c_m}$ và $Q = {q_1, \dots, q_n}$ thông qua ma trận chi phí tích lũy kích thước $m \times n$ bằng quy hoạch động: $$\gamma(i, j) = d(c_i, q_j) + \min{\gamma(i-1, j-1), \gamma(i-1, j), \gamma(i, j-1)}$$ DTW có độ phức tạp thời gian $O(mn)$, không thỏa mãn bất đẳng thức tam giác (không phải không gian metric).
  • Chuẩn hóa dữ liệu:
    • Chuẩn hóa min-max đưa dữ liệu về khoảng $[0, 1]$: $x_{\text{norm}} = (x - x_{\min}) / (x_{\max} - x_{\min})$.
    • Chuẩn hóa z-score: $x_{\text{norm}} = (x - \mu) / \sigma$, với $\mu$ là giá trị trung bình và $\sigma$ là độ lệch chuẩn.
  • Các định nghĩa tác vụ tìm kiếm:
    • Best-so-far search: Tìm chuỗi con $X[x_s : x_e]$ có khoảng cách chuẩn hóa nhỏ nhất tới mẫu $Y$.
    • k-NN search: Tìm tập hợp $k$ chuỗi con có khoảng cách nhỏ nhất tới mẫu $Y$.
    • Range search: Tìm tất cả chuỗi con thỏa mãn khoảng cách $D(NX, NY) \le \varepsilon$ theo cơ chế truy vấn tách rời (disjoint query).
  • Kỹ thuật tăng tốc và chặn dưới:
    • Sử dụng bình phương khoảng cách, từ bỏ sớm (early abandoning), sắp xếp thứ tự tính toán theo biên độ giảm dần.
    • Sắp xếp các kỹ thuật theo kiểu xếp tầng (cascading fashion): kỹ thuật có độ phức tạp thấp nhất ($O(1)$) được thực thi trước, kỹ thuật phức tạp hơn ($O(n)$) chỉ kích hoạt khi ứng viên chưa bị loại bỏ.
    • Các hàm chặn dưới DTW: LB_Kim ($O(1)$), LB_Keogh ($O(n)$) dựa trên hình bao cận trên $U$ và cận dưới $L$, LB_Keogh nghịch.
  • Các phép biến đổi thu giảm số chiều: Biến đổi Fourier rời rạc (DFT) bảo toàn năng lượng và khoảng cách Euclid theo Định lý Parseval; biến đổi Wavelet rời rạc (DWT/Haar wavelet); biến đổi xấp xỉ gộp từng đoạn (PAA). Tất cả đều thỏa mãn tính chất chặn dưới ($D_{\text{feature}}(F(C), F(Q)) \le D(C, Q)$), đảm bảo không gây ra lỗi tìm sót.

Phương pháp nghiên cứu thực nghiệm

  • Mô phỏng dữ liệu luồng: Sử dụng các chuỗi thời gian đơn biến thực tế và chuỗi thời gian tổng hợp, đưa vào hệ thống theo từng mốc thời gian (time tick).
  • Cơ chế lưu trữ: Sử dụng bộ đệm xoay vòng (circular buffer) quy mô lớn để lưu trữ các điểm dữ liệu mới nhất, tự động ghi đè các điểm dữ liệu cũ mà không làm tràn bộ nhớ.
  • Kiến trúc xử lý: Áp dụng kỹ thuật đa luồng (multi-threading) để xử lý song song nhiều luồng dữ liệu và tối ưu hóa thời gian phản hồi.

Nguồn tư liệu và dữ liệu thực nghiệm

Luận án sử dụng các tập dữ liệu chuẩn từ các kho lưu trữ chuỗi thời gian quốc tế:

  • Bộ dữ liệu dự báo: Fraser River (1913–1990), Milk Production in the UK, Carbon Dioxide, Retail and Food Services Sales in the USA.
  • Bộ dữ liệu phát hiện bất thường: mitdbx_mitdbx_108, qtdbsele0606, chfdbchf15, nprs44, nprs43, power_data.
  • Dữ liệu tài chính minh họa: Tỷ giá hối đoái USD/VND.

Nội dung chính theo từng chương

Chương 1: Giới thiệu

Chương 1 thiết lập bức tranh tổng quan về khai phá dữ liệu chuỗi thời gian dạng luồng. Tác giả trình bày các đặc trưng của luồng dữ liệu, phân tích sự cần thiết của việc chuẩn hóa dữ liệu trực tuyến, làm rõ tính cấp thiết, mục tiêu, đối tượng, phạm vi nghiên cứu (truy vấn tĩnh và truy vấn dạng luồng), phương pháp tiếp cận và cấu trúc tổng thể của luận án qua 7 chương cùng danh mục công trình đã công bố (từ CT1 đến CT9).

Chương 2: Cơ sở lý thuyết nền tảng

Chương 2 trình bày chi tiết các cơ sở toán học và thuật toán nền tảng:

  • Phân tích chi tiết hai độ đo cốt lõi: Euclid ($O(n)$) và DTW ($O(mn)$), so sánh ưu nhược điểm về tính chất metric và khả năng xử lý lệch pha.
  • Định nghĩa các công thức chuẩn hóa min-max và z-score.
  • Trình bày nguyên lý chặn dưới của các phép biến đổi thu giảm số chiều (DFT, DWT, PAA) và định lý Parseval.
  • Phân tích các hàm chặn dưới cho DTW (LB_Kim, LB_Keogh, LB_Keogh nghịch) và nguyên lý xếp tầng.
  • Mô tả cấu trúc chỉ mục không gian cây R-tree, R*-tree và giải thuật đóng gói STR (Sort-Tile-Recursive).

Chương 3: Tìm kiếm tương tự trên chuỗi thời gian dạng luồng bằng độ đo Euclid

Chương này tập trung vào 3 đóng góp kỹ thuật chính cho độ đo Euclid:

  1. Phương pháp RangeSearch: Thực hiện truy vấn vùng trên nhiều chuỗi thời gian luồng. Phương pháp tích hợp chuẩn hóa z-score gia tăng, cấu trúc chỉ mục đa mức phân giải (mảng R*-tree tương ứng với các mức lọc), kỹ thuật phân đoạn chuỗi truy vấn (không chồng lấp và chồng lấp), bộ đệm xoay vòng và kiến trúc đa luồng. Kết quả thực nghiệm cho thấy RangeSearch cho kết quả chính xác hoàn toàn như phương pháp duyệt tuần tự cải tiến SUCR-ED nhưng thời gian thực thi nhanh hơn đáng kể.
  2. Phương pháp k-NNSearch: Mở rộng từ RangeSearch để tìm kiếm $k$ lân cận gần nhất. Phương pháp điều chỉnh thủ tục truy vấn vùng trong R-tree để xử lý đồng thời nhiều bán kính tìm kiếm và tích hợp cơ chế đồng bộ hóa tránh xung đột khi nhiều luồng cùng cập nhật tập kết quả $k$-NN.
  3. Cải tiến kỹ thuật đóng gói cây R-tree (ISTR1 và ISTR2): Tác giả đề xuất 2 chiến lược kết nối đường chạy của các điểm đặc trưng (kết hợp đường cong lấp đầy không gian Z-order và Hilbert). Thực nghiệm chứng minh ISTR1 và ISTR2 giảm số lượng nút của cây R-tree, nâng cao tỷ lệ nút đầy và giảm thời gian tìm kiếm so với R-tree truyền thống, R*-tree và STR gốc.
Phương pháp / Kỹ thuật Cơ chế cốt lõi Đặc điểm thực nghiệm chính
RangeSearch Chuẩn hóa z-score gia tăng + mảng R*-tree đa mức phân giải Chính xác 100% (không tìm sót), tốc độ vượt trội so với SUCR-ED
k-NNSearch Truy vấn vùng đa ngưỡng + quản lý luồng đồng thời Phản hồi nhanh, loại bỏ hoàn toàn xung đột dữ liệu
ISTR1 & ISTR2 Cải tiến giải thuật STR qua Z-order và Hilbert curve Tối ưu hóa dung lượng cây R-tree, giảm thời gian truy vấn chỉ mục

Chương 4: Tìm kiếm tương tự trên chuỗi thời gian dạng luồng bằng độ đo DTW

Chương 4 giải quyết bài toán tìm kiếm tương tự bằng DTW qua 3 phương pháp đề xuất:

  1. Phương pháp SUCR-DTW: Cải tiến bộ kỹ thuật UCR-DTW sang môi trường luồng bằng cách áp dụng đa luồng và cập nhật gia tăng hình bao $U$ và $L$ của chuỗi con khi cửa sổ trượt dịch chuyển. Kết quả đảm bảo tính chính xác tuyệt đối như UCR-DTW tĩnh với thời gian phản hồi tức thời.
  2. Phương pháp ISPRING: Cải tiến thuật toán SPRING nổi tiếng nhằm kết hợp chuẩn hóa min-max gia tăng. ISPRING cho phép tìm kiếm các chuỗi con tương tự có chiều dài khác nhau trên dữ liệu chuẩn hóa, khắc phục triệt để điểm yếu không chuẩn hóa của SPRING gốc.
  3. Phương pháp ESUCR-DTW: Mở rộng hàm chặn dưới LB_Keogh thành LB_Keogh_extended, cho phép tính toán khoảng cách DTW trên hai chuỗi có chiều dài khác nhau trong phạm vi $[l - \beta : l + \alpha]$ (với $\alpha, \beta$ nằm trong độ rộng $w$ của dải Sakoe-Chiba). ESUCR-DTW đạt tốc độ cao hơn ISPRING và giữ vững tính chính xác khi so khớp chuỗi có độ dài biến thiên.
Thuật toán Chuẩn hóa dữ liệu Chiều dài chuỗi so khớp Kỹ thuật tăng tốc nổi bật
SUCR-DTW z-score gia tăng Chiều dài bằng nhau ($m = n$) Cập nhật hình bao gia tăng + Xếp tầng LB_Kim, LB_Keogh, LB_Keogh nghịch
ISPRING min-max gia tăng Chiều dài khác nhau Ma trận xoắn STWM + Cập nhật min-max trực tuyến
ESUCR-DTW z-score / min-max Chiều dài khác nhau ($[l-\beta : l+\alpha]$) Hàm chặn dưới mở rộng LB_Keogh_extended + Đa luồng

Chương 5: Dự báo trực tuyến trên chuỗi thời gian dạng luồng

Chương 5 hiện thực hóa bài toán ứng dụng dự báo chuỗi thời gian có xu hướng và tính mùa:

  • Tác giả đề xuất kỹ thuật phân đoạn chuỗi dựa trên việc nhận diện các điểm cực trị quan trọng (major extrema: cực đại, cực tiểu, nghiêm ngặt, bằng phẳng) làm các điểm mốc biên phân đoạn.
  • Quá trình dự báo áp dụng mô hình học trì hoãn (lazy learning): Tìm kiếm $k$ chuỗi con trong quá khứ có hình dạng biến đổi tương tự nhất với pha hiện tại bằng độ đo DTW.
  • Mô hình được kết hợp lai (hybrid) với phương pháp làm trơn hàm mũ đơn giản (SES) để tăng độ chính xác dự báo.
  • Đánh giá thực nghiệm trên 4 bộ dữ liệu thực tế (Fraser River 1913–1990, Milk Production in the UK, Carbon Dioxide, Retail and Food Services Sales in the USA) cho thấy đường dự báo bám sát các quan sát thực tế với sai số thấp và thời gian tính toán thực thi không đáng kể.

Chương 6: Phát hiện k chuỗi con bất thường nhất trong chuỗi thời gian dạng luồng

Chương 6 đề xuất phương pháp SKDIS (Search for top-k discords in streaming time series) nhằm tìm $k$ chuỗi con bất thường nhất bằng độ đo Euclid:

  • SKDIS tổ chức quy trình lọc 3 mức theo mô hình xếp tầng: (1) Ngưỡng chặn dưới dựa trên khoảng cách của các chuỗi con đến sớm; (2) Hàm chặn dưới dựa trên phép biến đổi thu giảm số chiều (DFT/DWT/PAA); (3) Bộ kỹ thuật tính khoảng cách chính xác UCR-ED cải tiến trong môi trường luồng.
  • Đánh giá thực nghiệm so sánh SKDIS với HOT SAX và SHOT SAX trên 6 tập dữ liệu chuẩn (mitdbx_mitdbx_108, qtdbsele0606, chfdbchf15, nprs44, nprs43, power_data).
  • Kết quả cho thấy SKDIS có khả năng cắt tỉa không gian ứng viên vượt trội, thời gian phản hồi nhanh hơn SHOT SAX và phát hiện chính xác các chuỗi bất thường trong dữ liệu có tính chu kỳ mà HOT SAX bỏ sót.

Chương 7: Kết luận

Chương 7 tổng kết toàn bộ các kết quả đạt được tương ứng với hai nhiệm vụ nghiên cứu, khẳng định việc hoàn thành các mục tiêu khoa học đặt ra, tóm lược các đóng góp mới, nêu rõ các hạn chế kỹ thuật hiện tại và đề xuất các hướng phát triển trong tương lai.

Kết quả và những đóng góp mới

Đóng góp về mặt lý luận và phương pháp

  1. Xây dựng khung xử lý gia tăng cho chuỗi thời gian luồng: Đề xuất và chứng minh tính đúng đắn của các giải thuật chuẩn hóa z-score gia tăng, chuẩn hóa min-max gia tăng, và giải thuật cập nhật hình bao gia tăng cho dải Sakoe-Chiba.
  2. Mở rộng lý thuyết chặn dưới của DTW: Phát triển thành công hàm chặn dưới mở rộng LB_Keogh_extended, phá vỡ giới hạn chiều dài bằng nhau của bộ kỹ thuật UCR-DTW truyền thống mà vẫn bảo toàn tính chất chặn dưới không tìm sót.
  3. Cải tiến cấu trúc chỉ mục không gian: Đề xuất 2 chiến lược ISTR1 và ISTR2 kết hợp đường cong lấp đầy không gian Hilbert và Z-order, tối ưu hóa quá trình xây dựng mảng R-tree đa mức phân giải cho truy vấn luồng.
  4. Mô hình kết hợp phân đoạn cực trị và học trì hoãn: Xây dựng khung phương pháp dự báo trực tuyến chuỗi thời gian xu hướng - mùa vụ bằng cách tích hợp điểm cực trị quan trọng, $k$-NN bằng DTW và làm trơn hàm mũ SES.

Đóng góp về mặt thực tiễn và ứng dụng

  • Cung cấp hệ thống giải thuật hoàn chỉnh, mã nguồn giải quyết trọn vẹn hai bài toán lớn trong khai phá dữ liệu luồng: dự báo trực tuyến và phát hiện bất thường trực tuyến.
  • Các phương pháp đề xuất được kiểm chứng thực nghiệm nghiêm ngặt trên nhiều bộ dữ liệu thực tế và dữ liệu mô phỏng, chứng minh tốc độ phản hồi nhanh, tiêu tốn ít bộ nhớ và không xảy ra lỗi tìm sót.
Nhóm đóng góp Phương pháp đề xuất Vấn đề giải quyết Công bố khoa học
Tìm kiếm bằng Euclid RangeSearch, k-NNSearch, ISTR1/ISTR2 Chuẩn hóa gia tăng, chỉ mục đa mức phân giải, tối ưu cây R-tree [CT5], [CT7], [CT8], [CT9]
Tìm kiếm bằng DTW SUCR-DTW, ISPRING, ESUCR-DTW Cập nhật hình bao gia tăng, chuẩn hóa cho SPRING, so khớp độ dài khác nhau [CT3], [CT4], [CT6]
Bài toán ứng dụng Dự báo DTW + SES, Thuật toán SKDIS Dự báo trực tuyến xu hướng/mùa vụ, phát hiện top-$k$ discords trực tuyến [CT1], [CT2]

Kiến nghị và giải pháp đề xuất

  • Đối với bài toán tìm kiếm Euclid: Áp dụng mảng R*-tree đa mức phân giải kết hợp chuẩn hóa z-score gia tăng và bộ đệm xoay vòng để tối ưu hóa việc quản lý bộ nhớ.
  • Đối với bài toán tìm kiếm DTW: Sử dụng ESUCR-DTW khi cần so khớp các chuỗi có chiều dài biến thiên trong khoảng dải Sakoe-Chiba, và sử dụng ISPRING khi cần tìm kiếm tức thời trên toàn miền dữ liệu chuẩn hóa min-max.
  • Trong dự báo chuỗi mùa vụ: Rút trích các điểm cực trị quan trọng làm biên phân đoạn pha trước khi thực hiện tìm kiếm lân cận gần nhất.

Hạn chế và hướng nghiên cứu tiếp

Hạn chế của luận án

Dựa trên phạm vi và các nội dung được văn bản đề cập, luận án tồn tại một số giới hạn:

  1. Phạm vi dữ liệu: Các nghiên cứu chỉ tập trung giải quyết trên chuỗi thời gian đơn biến (univariate time series), chưa mở rộng trực tiếp cho chuỗi thời gian đa biến (multivariate time series).
  2. Giới hạn độ dài trong ESUCR-DTW: Mặc dù ESUCR-DTW xử lý được các chuỗi có chiều dài khác nhau, độ chênh lệch chiều dài giữa chuỗi con và chuỗi truy vấn vẫn bị ràng buộc trong phạm vi độ rộng $w$ của dải Sakoe-Chiba ($[l - \beta : l + \alpha]$).
  3. Chi phí tính toán của ISPRING: ISPRING phải tính toán lại khoảng cách ma trận STWM mỗi khi các hệ số min-max trong cửa sổ trượt thay đổi, dẫn đến thời gian phản hồi còn chậm hơn so với các phương pháp tiếp cận theo chặn dưới xếp tầng.
  4. Phụ thuộc cấu trúc bộ đệm: Các giải thuật phụ thuộc vào kích thước của bộ đệm xoay vòng; khi kích thước luồng dữ liệu vượt quá quy mô bộ đệm, dữ liệu cũ bắt buộc phải bị hủy bỏ.

Hướng phát triển tiếp theo

  • Mở rộng các phương pháp tìm kiếm tương tự và phát hiện bất thường cho chuỗi thời gian đa biến dạng luồng.
  • Nghiên cứu nới lỏng các ràng buộc về độ rộng dải xoắn trong ESUCR-DTW để so khớp các chuỗi có độ dài chênh lệch lớn hơn.
  • Cải tiến cấu trúc dữ liệu ma trận của ISPRING nhằm giảm thiểu chi phí tính toán lại khi cập nhật hệ số min-max.
  • Nghiên cứu cơ chế tự động điều chỉnh ngưỡng khoảng cách $\varepsilon$ và kích thước cửa sổ trượt thích ứng với sự thay đổi phân phối (concept drift) của luồng dữ liệu.

Giá trị tham khảo

Luận án mang lại giá trị tham khảo học thuật và thực tiễn chuyên sâu:

  • Đối với nghiên cứu sinh và học viên cao học ngành Khoa học máy tính / Khoa học dữ liệu: Chương 2 và Chương 4 cung cấp hệ thống lý thuyết chi tiết, chuẩn xác về các kỹ thuật chặn dưới DTW (LB_Kim, LB_Keogh, LB_Keogh nghịch), các phép biến đổi thu giảm số chiều (DFT, DWT, PAA) và định lý Parseval. Phụ lục A cung cấp chi tiết giải thuật UCR-DTW và các cấu trúc dữ liệu hỗ trợ.
  • Đối với giảng viên và nhà nghiên cứu khai phá dữ liệu: Phương pháp luận tiếp cận bài toán luồng (xử lý một lượt, chuẩn hóa gia tăng, bộ đệm xoay vòng, kiến trúc đa luồng) là tài liệu tham khảo giá trị cho các môn học Khai phá dữ liệu nâng cao và Xử lý dữ liệu lớn.
  • Đối với kỹ sư phát triển hệ thống và chuyên gia phân tích dữ liệu: Các giải thuật RangeSearch, ESUCR-DTW và SKDIS (trình bày tại Chương 3, 4, 6) có thể ứng dụng trực tiếp vào việc xây dựng các hệ thống giám sát mạng, cảnh báo bất thường trong y tế (tín hiệu điện tâm đồ ECG), phân tích tài chính chứng khoán và dự báo các chỉ số quan trắc môi trường.

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

1. Tại sao phải chuẩn hóa dữ liệu trước khi tìm kiếm tương tự trên chuỗi thời gian dạng luồng?

Nếu không chuẩn hóa dữ liệu, hai chuỗi thời gian có cùng hình dạng dao động nhưng khác nhau về độ cao trung bình (altitude/offset) hoặc biên độ dao động (amplitude/scale) sẽ bị tính ra khoảng cách rất lớn. Điều này dẫn đến hiện tượng tìm sót (false dismissals), khiến hệ thống bỏ qua các chuỗi con thực sự tương tự. Chuẩn hóa (z-score hoặc min-max) đưa các chuỗi về cùng một thang đo, giúp việc so sánh hình dạng đạt độ chính xác cao.

2. Sự khác biệt cốt lõi giữa độ đo Euclid và độ đo DTW trong luận án là gì?

Độ đo Euclid so khớp từng cặp điểm thẳng hàng 1-1 theo trục thời gian, có độ phức tạp $O(n)$, thỏa mãn bất đẳng thức tam giác (không gian metric) nên dễ lập chỉ mục không gian (R-tree), nhưng rất nhạy cảm với nhiễu và hiện tượng lệch pha. Độ đo DTW cho phép ánh xạ 1-nhiều không thẳng hàng bằng quy hoạch động, khử được hiện tượng lệch pha và co giãn thời gian, nhưng có độ phức tạp $O(mn)$ và không thỏa mãn bất đẳng thức tam giác, đòi hỏi các hàm chặn dưới (LB_Kim, LB_Keogh) để tăng tốc.

3. Phương pháp RangeSearch trong Chương 3 hoạt động theo cơ chế nào để tăng tốc tìm kiếm?

RangeSearch sử dụng kiến trúc đa luồng trên bộ đệm xoay vòng, kết hợp chuẩn hóa z-score gia tăng để giảm chi phí tính toán thống kê. Dữ liệu đặc trưng được lưu trữ trong một mảng R*-tree tổ chức theo đa mức phân giải (mức lọc từ thô đến tinh). Chuỗi truy vấn được phân đoạn và lọc qua từng mức; các ứng viên không thỏa mãn ngưỡng khoảng cách sẽ bị loại bỏ sớm trước khi thực hiện bước hậu kiểm trên dữ liệu gốc.

4. Thuật toán ESUCR-DTW trong Chương 4 đã giải quyết hạn chế nào của bộ kỹ thuật UCR-DTW?

UCR-DTW nguyên bản chỉ tính toán khoảng cách DTW giữa hai chuỗi có chiều dài bằng nhau ($m = n$). ESUCR-DTW mở rộng hàm chặn dưới LB_Keogh_extended, cho phép tính toán khoảng cách DTW và chặn dưới giữa hai chuỗi có chiều dài khác nhau trong phạm vi cửa sổ trượt $[l - \beta : l + \alpha]$ (với độ lệch nằm trong độ rộng $w$ của dải Sakoe-Chiba), đảm bảo không gây ra lỗi tìm sót.

5. Phương pháp SKDIS trong Chương 6 sử dụng chiến lược gì để phát hiện k chuỗi con bất thường nhất?

SKDIS áp dụng mô hình cắt tỉa xếp tầng 3 mức: (1) Khởi tạo và cập nhật ngưỡng chặn dưới từ các chuỗi con đến sớm; (2) Sử dụng hàm chặn dưới dựa trên phép biến đổi thu giảm số chiều (DFT/DWT/PAA) để loại bỏ sớm các chuỗi con thông thường; (3) Áp dụng bộ kỹ thuật UCR-ED cải tiến trong môi trường luồng để tính toán khoảng cách chính xác cho các chuỗi con ứng viên còn lại.

Kết luận

Luận án tiến sĩ của tác giả Bùi Công Giao đã giải quyết một cách có hệ thống các thách thức cốt lõi trong bài toán tìm kiếm tương tự trên chuỗi thời gian dạng luồng bằng cả hai độ đo Euclid và DTW. Bằng việc tích hợp các kỹ thuật chuẩn hóa dữ liệu gia tăng, cấu trúc chỉ mục đa mức phân giải cải tiến và các hàm chặn dưới xếp tầng mở rộng, luận án đã xây dựng thành công các phương pháp tìm kiếm chính xác, tốc độ cao và tối ưu bộ nhớ. Đồng thời, các giải pháp đề xuất đã được ứng dụng hiệu quả vào hai bài toán thực tiễn quan trọng là dự báo trực tuyến và phát hiện bất thường trên luồng dữ liệu thời gian thực.