Tổng quan luận án

Luận án tiến sĩ "Phát hiện những điểm thay đổi và chuỗi con bất thường trên dữ liệu chuỗi thời gian" được thực hiện bởi nghiên cứu sinh Huỳnh Thị Thu Thủy dưới sự hướng dẫn của PGS. Dương Tuấn Anh và PGS. Võ Thị Ngọc Châu tại Trường Đại học Bách Khoa – Đại học Quốc gia TP. Hồ Chí Minh (chuyên ngành Khoa học máy tính, mã số 62.01, năm 2022).

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

Dữ liệu chuỗi thời gian xuất hiện phổ biến trong nhiều lĩnh vực ứng dụng như y học (điện tâm đồ ECG), tài chính, thương mại điện tử, khí tượng thủy văn, giám sát môi trường và cảm biến mạng. Trong khai phá dữ liệu chuỗi thời gian, phát hiện chuỗi con bất thường nhất (anomaly/discord) là bài toán quan trọng nhằm phát hiện các mẫu dữ liệu khác biệt đáng kể so với phần còn lại. Tuy nhiên, các hướng tiếp cận hiện hữu đối mặt với ba thách thức lớn chưa được giải quyết trọn vẹn:

  1. Yêu cầu phải xác định trước chiều dài của chuỗi con bất thường ($n$), một tham số khó lựa chọn trong thực tế và ảnh hưởng trực tiếp đến kết quả phát hiện;
  2. Đảm bảo độ chính xác của kết quả với chi phí tính toán và bộ nhớ hữu hiệu;
  3. Khả năng mở rộng xử lý dữ liệu chuỗi thời gian có kích thước siêu lớn và đáp ứng yêu cầu tính tức thời trên dữ liệu chuỗi thời gian dạng luồng (streaming time series).

Các phương pháp phát hiện bất thường dựa trên cửa sổ trượt truyền thống (như Brute-Force, HOT SAX) hoặc mạng nơ-ron học sâu (như LSTM) còn tồn tại hạn chế về độ phức tạp tính toán cao ($O(m^2)$), tốn thời gian huấn luyện mô hình, tỷ lệ cảnh báo sai (false positive/false negative) cao do phụ thuộc ngưỡng bất thường, hoặc không xử lý được trường hợp chuỗi con bất thường đôi (twin freak).

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

Luận án xác định hai nhóm mục tiêu cụ thể:

  • Mục tiêu chính:
    1. Đề xuất giải pháp mới để phát hiện hiệu quả chuỗi con bất thường nhất trên dữ liệu chuỗi thời gian dạng tĩnh.
    2. Đề xuất giải pháp mới để phát hiện hiệu quả chuỗi con bất thường nhất trên dữ liệu chuỗi thời gian dạng luồng (xử lý trực tuyến/online). Mở rộng: Phát triển giải thuật phát hiện $k$ chuỗi con bất thường nhất ($k > 1$) trên cả dữ liệu chuỗi thời gian dạng tĩnh và dạng luồng.
  • Mục tiêu phụ: Nghiên cứu, đánh giá và lựa chọn giải pháp phát hiện những điểm thay đổi (change points) và phân đoạn chuỗi thời gian hiệu quả nhằm hỗ trợ rút trích chuỗi con cho mục tiêu chính.

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

  • Đối tượng nghiên cứu: Dữ liệu chuỗi thời gian dạng tĩnh (static time series) và dữ liệu chuỗi thời gian dạng luồng (streaming time series), trong đó giá trị của từng điểm dữ liệu là số thực được ghi nhận tại các mốc thời gian đều đặn (chuỗi thời gian có quy tắc - regular time series).
  • Phạm vi nghiên cứu: Tập trung vào dữ liệu chuỗi thời gian đơn biến (univariate time series). Định hướng tìm kiếm chuỗi con bất thường hướng về chuỗi con ngắn nhất để tối ưu hóa thời gian thực thi mà vẫn bảo đảm bao phủ được mẫu bất thường thực tế.

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

Các hướng tiếp cận phát hiện bất thường

Luận án tổng hợp và phân loại các công trình nghiên cứu phát hiện bất thường thành 4 hướng tiếp cận chính dựa trên nghiên cứu của Chandola và cộng sự (2009), Cheboli (2010), Braei và Wagner (2020):

Tiêu chí Hướng tiếp cận dựa vào cửa sổ trượt (Sliding window based) Hướng tiếp cận dựa vào phân đoạn (Segmentation based) Hướng tiếp cận dựa vào phân lớp (Classification based) Hướng tiếp cận dựa vào dự báo (Prediction based)
Tiền xử lý Trượt cửa sổ qua từng điểm dữ liệu để rút trích các chuỗi con có cùng chiều dài. Trượt cửa sổ qua từng đoạn dữ liệu để rút trích các chuỗi con có chiều dài khác nhau. Thu thập mẫu dữ liệu bình thường và bất thường để huấn luyện mô hình phân lớp. Thu thập mẫu dữ liệu bình thường để huấn luyện mô hình dự báo.
Dấu hiệu kết luận bất thường Chuỗi con có khoảng cách xa nhất đến các chuỗi con trùng khớp không tầm thường của nó. Chuỗi con có hệ số bất thường lớn nhất. Bộ phân lớp xác định chuỗi con là bình thường hay bất thường. Sự chênh lệch giữa giá trị dự báo và giá trị thực vượt quá giá trị ngưỡng cho trước.

Các công trình nghiên cứu được điểm luận

  1. Hướng cửa sổ trượt trên dữ liệu tĩnh:
    • Brute-Force và HOT SAX (Keogh và cộng sự, 2005): Giải thuật chân phương Brute-Force có độ phức tạp $O(m^2)$. HOT SAX sử dụng heuristic dựa trên biểu diễn SAX và cây gia tố (augmented trie) để tăng tốc, nhưng vẫn yêu cầu cố định chiều dài cửa sổ trượt $n$ và gặp khó khăn khi gặp hiện tượng bất thường đôi (Huang và cộng sự, 2015).
    • WAT (Wavelet and Augmented Trie) và AWDD (Adaptive Window-based Discord Discovery): Yêu cầu người dùng xác định chiều dài cửa sổ.
  2. Hướng phân lớp và học máy:
    • Hệ thống miễn nhiễm nhân tạo (Gonzalez và cộng sự, 2003): Sinh mẫu âm để huấn luyện bộ phân lớp.
    • Mạng nơ-ron RBF với giải thuật DDA (Oliveira và cộng sự, 2006): Phân lớp cửa sổ dữ liệu.
    • Học Exemplar (Jones và cộng sự, 2007): Yêu cầu chiều dài chuỗi con.
    • Mô hình học sâu LSTM (Munir và cộng sự, 2018; Zhang và Zou, 2018; Que và cộng sự, 2019; Lee và cộng sự, 2020; Lin và cộng sự, 2020): Không cần xác định trước chiều dài nhưng tốn nhiều thời gian huấn luyện và tỷ lệ cảnh báo sai cao do phụ thuộc ngưỡng cố định.
  3. Hướng dự báo:
    • Mô hình tự hồi quy AR và hồi quy véc-tơ liên quan RVR (Fujimaki và cộng sự, 2005): Áp dụng cho dữ liệu viễn thám tàu không gian.
    • Mô hình ARIMA kết hợp HWDS (Pena và cộng sự, 2013): Giám sát lưu lượng mạng IP.
    • Làm mịn số mũ Brown, phân rã theo mùa và trung bình di chuyển (Bernacki và Kolaczek, 2015): Giám sát lưu lượng mạng.
  4. Hướng phân đoạn và độ đo khoảng cách:
    • Automat hữu hạn trạng thái (Salvador và Chan, 2005): Quá trình xây dựng trạng thái phức tạp.
    • QR-AF (Leng và Li, 2008): Phân đoạn bằng hồi quy bậc hai và đo khoảng cách DTW để tìm $k$-lân cận gần nhất; nhược điểm là chi phí tính toán cao và nhiều tham số phức tạp.
    • FindBCD (Kha và Anh, 2015): Sử dụng giải thuật gom cụm Squeeze, chi phí thời gian còn cao.
    • SJ-DTW-Graph (Do và Anh, 2017): Kết hợp giải thuật EP-M và đồ thị với khoảng cách DTW, độ phức tạp $O(m^2)$.
  5. Phát hiện bất thường trên dữ liệu luồng:
    • Cửa sổ đàn hồi (Zhu và Shasha, 2003); Khung thức DCD (Liu và cộng sự, 2009); Mở rộng HOT SAX trên luồng (Toshniwal và Yadav, 2011); Bounding box và R-tree (Sanchez và Bustos, 2014); HS-Squeezer-Stream (Châu và cộng sự, 2018); SKDIS (Giao và Anh, 2020); Phương pháp của Safia và Aghbari (2011) với DTW.

Khoảng trống luận án lựa chọn giải quyết

Luận án lựa chọn hướng tiếp cận dựa vào phân đoạn nhằm:

  • Loại bỏ yêu cầu phải xác định trước chiều dài cố định của chuỗi con bất thường;
  • Xây dựng độ đo đánh giá chất lượng phân đoạn phù hợp;
  • Thiết kế giải thuật gom cụm nhanh (cải tiến giải thuật Leader) kết hợp độ đo Euclid và khoảng cách xoắn thời gian động DTW kèm kỹ thuật cận dưới ($LB_Keogh$) nhằm đạt tốc độ xử lý tức thời trên chuỗi dữ liệu tĩnh và chuỗi dữ liệu dạng luồng;
  • Giải quyết trường hợp dữ liệu lớn và hiện tượng bất thường đôi bằng kỹ thuật xử lý song song trên GPU.

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

Các định nghĩa và khái niệm nền tảng

  • Chuỗi thời gian (Time series): Chuỗi có thứ tự $T = (t_1, t_2, \dots, t_m)$ gồm $m$ giá trị thực ghi nhận tại các thời điểm đều nhau.
  • Chuỗi thời gian dạng luồng (Streaming time series): Chuỗi quan sát $T = (t_1, t_2, \dots, t_\infty)$ ghi nhận liên tục theo thứ tự thời gian.
  • Chuỗi con (Subsequence): Mẫu $S = (t_p, t_{p+1}, \dots, t_{p+n-1})$ gồm $n$ vị trí liên tục lấy từ $T$ với $n < m$ và $1 \le p \le m - n + 1$.
  • Trùng khớp không tầm thường (Non-self match): Với chuỗi con $C$ bắt đầu tại $p$ chiều dài $n$ và chuỗi con $M$ bắt đầu tại $q$, $M$ là trùng khớp không tầm thường của $C$ nếu $|p - q| > n$.
  • Chuỗi con bất thường nhất (1-discord / top-anomaly): Chuỗi con $C$ trong $T$ có khoảng cách xa nhất đến chuỗi con trùng khớp không tầm thường gần nhất của nó.
  • Chuỗi con bất thường thứ $k$ ($k^{th}$-discord): Chuỗi con $D$ bắt đầu tại $p$ có khoảng cách lớn thứ $k$ đến trùng khớp không tầm thường gần nhất và không đè lấp lên các chuỗi con bất thường thứ $i$ ($|p - p_i| > n$ với $1 \le i < k$).
  • Điểm thay đổi (Change point): Điểm tại đó tính chất dữ liệu thay đổi đột ngột hoặc là điểm kết nối giữa hai phân đoạn kế cận.

Độ đo khoảng cách

  1. Khoảng cách Euclid (Euclidean Distance - ED): Áp dụng cho 2 chuỗi $C_1 = (x_1, \dots, x_m)$ và $C_2 = (y_1, \dots, y_m)$ cùng chiều dài $m$: $$ED(C_1, C_2) = \sqrt{\sum_{i=1}^m (x_i - y_i)^2}$$
  2. Khoảng cách xoắn thời gian động (Dynamic Time Warping - DTW): Ánh xạ phi tuyến 1-nhiều giữa 2 chuỗi $Q = (x_1, \dots, x_m)$ và $C = (y_1, \dots, y_n)$ thông qua ma trận xoắn kích thước $m \times n$ và đường đi xoắn $W = w_1, w_2, \dots, w_K$: $$DTW(Q, C) = \min \sqrt{\sum_{k=1}^K w_k}$$ Khoảng cách tích lũy $D(i, j)$ giải bằng quy hoạch động: $$D(i, j) = |x_i - y_j| + \min { D(i-1, j), D(i-1, j-1), D(i, j-1) }$$ Luận án tích hợp ràng buộc toàn cục (cửa sổ xoắn) và kỹ thuật tính cận dưới $LB_Keogh$ của Keogh và cộng sự (2005) sử dụng đường bao trên $U$ và đường bao dưới $L$ để cắt tỉa sớm không gian tính toán DTW.

Phương pháp thu giảm số chiều và rời rạc hóa

  • Xấp xỉ gộp từng đoạn (Piecewise Aggregate Approximation - PAA): Chia chuỗi thành các khung bằng nhau và lấy giá trị trung bình cộng các điểm trong khung.
  • Xấp xỉ tuyến tính từng đoạn (Piecewise Linear Approximation - PLA): Xấp xỉ chuỗi $T$ chiều dài $m$ thành $N$ đoạn thẳng.
  • Xấp xỉ gộp ký hiệu hóa (Symbolic Aggregate Approximation - SAX): Chuẩn hóa chuỗi bằng z-score, chia đoạn bằng PAA, sau đó ánh xạ giá trị PAA vào bảng chữ cái kích thước $a$ dựa trên các điểm ngắt (breakpoints $\beta_1, \dots, \beta_{a-1}$) theo phân bố chuẩn $N(0, 1)$.

Dữ liệu thực nghiệm và môi trường phần cứng

  • Tập dữ liệu chuỗi thời gian thực nghiệm: ECG (điện tâm đồ, bộ dữ liệu koski-ecg, MIT-BIH_08405), Oil, Trace, Tek16, Thermostat Sales, Expenditure.
  • Thiết bị phần cứng: Card đồ họa GPU chuyên dụng bao gồm NVIDIA Tesla V100 và NVIDIA GeForce GTX 1080 Ti dùng trong lập trình song song.

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

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

Chương 1 thiết lập tổng thể nghiên cứu: phân tích sự cần thiết của khai phá dữ liệu chuỗi thời gian, động cơ giải quyết bài toán phát hiện chuỗi con bất thường nhất và mở rộng ra $k$ chuỗi con bất thường nhất. Chương này trình bày chi tiết ý nghĩa khoa học và thực tiễn trong các hệ thống y tế, quan trắc môi trường và giám sát mạng; xác định rõ 2 mục tiêu chính (dữ liệu tĩnh và dữ liệu dạng luồng), 1 mục tiêu phụ (phát hiện điểm thay đổi/phân đoạn), đối tượng nghiên cứu (chuỗi thời gian đơn biến có quy tắc) và phác thảo cấu trúc gồm 8 chương cùng 4 phụ lục của luận án.

Chương 2: Cơ sở lý thuyết và các công trình liên quan

Chương 2 cung cấp hệ thống định nghĩa toán học chuẩn tắc về chuỗi thời gian tĩnh và dạng luồng, chuỗi con, trùng khớp không tầm thường, chuỗi con bất thường nhất và chuỗi con bất thường thứ $k$. Tác giả phân tích chi tiết giải thuật nền tảng Brute-Force cùng giải thuật heuristic HDD; làm rõ cơ chế tính toán, ưu nhược điểm của độ đo Euclid và khoảng cách DTW kèm kỹ thuật cận dưới $LB_Keogh$. Đồng thời, chương 2 hệ thống hóa các phương pháp biểu diễn rút gọn (PAA, PLA, SAX) và tổng quan 4 hướng tiếp cận phát hiện bất thường trên cả môi trường dữ liệu tĩnh lẫn dữ liệu luồng.

Chương 3: Phát hiện những điểm thay đổi trên chuỗi thời gian và các phương pháp phân đoạn

Chương 3 tập trung giải quyết mục tiêu phụ của luận án. Tác giả khảo cứu các phương pháp xác định điểm thay đổi để phân đoạn chuỗi thời gian:

  • Phương pháp điểm cực trị quan trọng (Important Extreme Point - IEP) bao gồm: cực tiểu quan trọng, cực tiểu quan trọng nghiêm cách, cực tiểu quan trọng bên trái, cực tiểu quan trọng bên phải, cực tiểu quan trọng phẳng;
  • Phương pháp điểm quan trọng cảm nhận được (Perceptually Important Points - PIP);
  • Phương pháp xấp xỉ bình phương tối thiểu đa thức (Polynomial Least-Squares Approximation - PLSA) với đa thức bậc 1 và bậc 2.

Chương này đánh giá các tiêu chí đo lường phân đoạn hiện có do Gensler và Sick đề xuất như Đếm số phân đoạn trung bình (ASC - Average Segmentation Count) và Khoảng cách phân đoạn tuyệt đối (ASD - Absolute Segmentation Distance). Nhận thấy các hạn chế của tiêu chí cũ, tác giả đề xuất độ đo mới PALS (Percentage of Average Length Segments - Phần trăm các phân đoạn chiều dài trung bình) dựa trên vùng phân đoạn ($sz$) để đánh giá chính xác chất lượng các phương pháp phân đoạn. Thực nghiệm trên các bộ dữ liệu đối chuẩn giúp xác định bộ tham số tối ưu cho các phương pháp PIP, IEP và PLSA.

Chương 4: Cải tiến các phương pháp phát hiện chuỗi con bất thường nhất dựa vào cửa sổ trượt truyền thống trên dữ liệu chuỗi thời gian dạng tĩnh

Chương 4 tập trung cải tiến các giải thuật cửa sổ trượt kinh điển:

  1. Giải thuật I-HOTSAX: Tối ưu hóa giải thuật HOT SAX bằng việc cải tiến kỹ thuật sắp xếp thứ tự chuỗi con ở các vòng lặp, giảm số lần gọi hàm tính khoảng cách và rút ngắn thời gian thực thi.
  2. Giải thuật Hash_DD: Thay thế cấu trúc cây gia tố (augmented trie) bằng cấu trúc bảng băm (hash table) hỗ trợ tra cứu trực tiếp ở vòng lặp trong và vòng lặp ngoài; đồng thời áp dụng cơ chế trượt cửa sổ theo từng đoạn xấp xỉ thay vì từng điểm dữ liệu đơn lẻ. Hash_DD giúp tăng tốc độ xử lý và giảm đáng kể chi phí bộ nhớ.
  3. Giải thuật KBF_GPU: Cải tiến giải thuật Brute-Force bằng cách đưa ra điều kiện khoảng cách $K$ (mảng Array-K lưu trữ $K$ khoảng cách đến $K$ chuỗi con trùng khớp gần nhất) để giải quyết triệt để trường hợp chuỗi thời gian xuất hiện bất thường đôi (twin freak). Tác giả ứng dụng kỹ thuật lập trình song song trên GPU (thực nghiệm trên Tesla V100 và GeForce GTX 1080 Ti trên bộ dữ liệu koski-ecg) giúp tăng tốc độ tìm kiếm trên dữ liệu chuỗi thời gian siêu lớn.

Chương 5: Đề xuất các phương pháp phát hiện chuỗi con bất thường nhất dựa vào phân đoạn với độ đo Euclid

Chương 5 hiện thực hóa hướng tiếp cận dựa trên phân đoạn với độ đo Euclid:

  • Giải thuật gom cụm I-Leader: Khắc phục nhược điểm phụ thuộc thứ tự duyệt phần tử của giải thuật Leader truyền thống (Hartigan, 1975) bằng cách bổ sung bước tinh chỉnh cụm sau bước gom cụm ban đầu. Thực nghiệm chứng minh I-Leader đạt giá trị hàm mục tiêu tốt hơn Leader và có tốc độ nhanh hơn $k$-Means.
  • Giải thuật EP-ILeader: Kết hợp kỹ thuật phân đoạn (EP) và giải thuật gom cụm I-Leader để phát hiện chuỗi con bất thường trên chuỗi thời gian tĩnh mà không cần người dùng nhập trước chiều dài chuỗi con. Vị trí bất thường tìm được trùng khớp hoàn toàn với giải thuật Brute-Force nhưng thời gian thực thi giảm vượt bậc so với HOT SAX.
  • Mở rộng phát hiện $k$ chuỗi con bất thường: Đề xuất giải thuật TopK-EP-ALeader cho chuỗi thời gian tĩnh và TopK-EP-ALeader-S cho chuỗi thời gian dạng luồng (sử dụng cơ chế cửa sổ di chuyển và vùng đệm xoay vòng). Kết quả thực nghiệm cho thấy các giải thuật xác định chính xác top-$k$ chuỗi con bất thường trùng khớp với nhãn do chuyên gia đánh dấu.

Chương 6: Đề xuất các phương pháp phát hiện chuỗi con bất thường nhất dựa vào phân đoạn với khoảng cách xoắn thời gian động

Chương 6 mở rộng hướng tiếp cận phân đoạn sang môi trường sử dụng khoảng cách DTW:

  • Giải thuật EP-Leader-DTW (trên chuỗi tĩnh): Sử dụng giải thuật phân đoạn kết hợp gom cụm Leader và khoảng cách DTW có tích hợp kỹ thuật chặn dưới $LB_Keogh$. Giải thuật không yêu cầu tính lại tâm cụm (centroid) phức tạp, nhờ đó duy trì thời gian thực thi rất thấp (chỉ mất khoảng 35 ms để tìm chuỗi con bất thường trên chuỗi có 5.000 điểm dữ liệu).
  • Giải thuật SEP-Leader-DTW (trên chuỗi dạng luồng): Xử lý trực tuyến dòng dữ liệu đến liên tục dưới độ đo DTW, đáp ứng yêu cầu phản hồi tức thời mà vẫn đảm bảo độ chính xác.
  • Kết quả thực nghiệm: So sánh đối chuẩn với giải thuật cơ sở $BF_DTW$ và giải thuật $QR_AF$ trên các tập dữ liệu MIT-BIH_08405, Tek16, ECG. Kết quả của EP-Leader-DTW và SEP-Leader-DTW trùng khớp hoàn toàn với các chuỗi con bất thường do chuyên gia gán nhãn, đồng thời giảm thiểu vượt trội số lần gọi hàm tính khoảng cách DTW và thời gian thực thi so với $QR_AF$.

Chương 7: Ứng dụng phát hiện bất thường để cải thiện chất lượng dự báo dữ liệu chuỗi thời gian

Chương 7 đề xuất khung thức dự báo EPL_S_X ứng dụng kỹ thuật phát hiện và hiệu chỉnh bất thường (Anomaly-Repair) vào giai đoạn tiền xử lý trước khi thực hiện dự báo chuỗi thời gian.

  • Cơ chế hoạt động: Nhận diện các điểm/chuỗi con bất thường (nhiễu, ngoại lai) bằng giải thuật đề xuất, tiến hành khử/hiệu chỉnh giá trị bất thường về mức bình thường, sau đó đưa vào các mô hình dự báo nền tảng $X$.
  • Mô hình dự báo tích hợp ($X$): Hồi quy tuyến tính (LR), $k$-lân cận gần nhất ($k$-NN), Mạng nơ-ron nhân tạo (ANN), và mô hình lai (Hybrid).
  • Kết quả thực nghiệm: Thử nghiệm trên các tập dữ liệu thực tế như Thermostat Sales và Expenditure. Kết quả đánh giá qua các chỉ số sai số: Sai số bình phương trung bình (MSE), Sai số tuyệt đối trung bình (MAE), và Sai số phần trăm tuyệt đối trung bình (MAPE) chứng minh các phiên bản tích hợp (như $EPL_S_kNN$) đạt độ chính xác vượt trội và giảm sai số đáng kể so với các mô hình gốc khi không qua bước hiệu chỉnh bất thường.

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

Chương 8 tổng kết toàn bộ các đóng góp về mặt lý thuyết và thực nghiệm của luận án; hệ thống hóa danh mục các giải thuật cải tiến và giải thuật mới được đề xuất; đồng thời định hình các hướng phát triển tiếp theo của đề tài.

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

Đóng góp về mặt lý luận và khoa học

  1. Đề xuất độ đo PALS: Thiết lập độ đo mới phục vụ việc đánh giá định lượng chất lượng của các phương pháp phân đoạn chuỗi thời gian, khắc phục nhược điểm của các tiêu chí ASC và ASD cũ.
  2. Đề xuất giải thuật gom cụm I-Leader: Cải tiến giải thuật gom cụm gia tăng Leader bằng kỹ thuật tinh chỉnh cụm, nâng cao chất lượng gom cụm với độ phức tạp tính toán tuyến tính.
  3. Đề xuất hướng tiếp cận phát hiện bất thường dựa trên phân đoạn: Loại bỏ hoàn toàn sự phụ thuộc vào việc phải chỉ định trước tham số chiều dài chuỗi con bất thường ($n$), giảm đáng kể không gian tìm kiếm so với kỹ thuật trượt từng điểm.
  4. Phát triển các giải thuật mới cho dữ liệu tĩnh và luồng:
    • EP-ILeader: Phát hiện chuỗi con bất thường nhất trên dữ liệu tĩnh với độ đo Euclid.
    • TopK-EP-ALeader và TopK-EP-ALeader-S: Phát hiện $k$ chuỗi con bất thường nhất trên dữ liệu tĩnh và luồng với độ đo Euclid.
    • EP-Leader-DTW và SEP-Leader-DTW: Phát hiện chuỗi con bất thường nhất trên dữ liệu tĩnh và luồng với khoảng cách DTW kết hợp kỹ thuật chặn dưới $LB_Keogh$.
  5. Cải tiến các giải thuật truyền thống:
    • I-HOTSAX và Hash_DD: Tăng tốc và tối ưu hóa bộ nhớ cho giải thuật HOT SAX bằng kỹ thuật bảng băm và trượt theo đoạn.
    • KBF_GPU: Mở rộng giải thuật Brute-Force với điều kiện khoảng cách $K$ và lập trình song song trên GPU, giải quyết thành công bài toán dữ liệu siêu lớn và hiện tượng bất thường đôi (twin freak).

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

  1. Khung thức dự báo EPL_S_X: Đề xuất thành công quy trình kết hợp phát hiện bất thường và kỹ thuật hiệu chỉnh Anomaly-Repair trong tiền xử lý chuỗi thời gian, cải thiện rõ rệt độ chính xác (giảm MSE, MAE, MAPE) cho nhiều mô hình dự báo phổ biến ($k$-NN, LR, ANN, Hybrid).
  2. Khả năng đáp ứng thời gian thực: Giải thuật EP-Leader-DTW xử lý chuỗi 5.000 điểm chỉ trong khoảng 35 mili-giây, và giải thuật SEP-Leader-DTW đáp ứng tốc độ truyền tức thời của dữ liệu luồng cảm biến thực tế.

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

Hạn chế (theo phạm vi nghiên cứu của luận án)

  • Nghiên cứu tập trung chủ yếu vào đối tượng chuỗi thời gian đơn biến (univariate time series), chưa mở rộng sang chuỗi thời gian đa biến (multivariate time series).
  • Chỉ áp dụng trên chuỗi thời gian có quy tắc (regular time series) với các khoảng thời gian đo đạc đều đặn, chưa xử lý chuỗi thời gian bất quy tắc (irregular time series).
  • Định hướng tìm kiếm tập trung ưu tiên vào chuỗi con bất thường ngắn nhất nhằm tối ưu hóa chi phí thời gian.

Hướng nghiên cứu tiếp (theo Chương 8)

  • Mở rộng các giải thuật phân đoạn và gom cụm đề xuất để áp dụng cho bài toán phát hiện bất thường trên chuỗi thời gian đa biến.
  • Nghiên cứu cơ chế phát hiện chuỗi con bất thường trên chuỗi thời gian bất quy tắc và dữ liệu có tần suất lấy mẫu biến thiên.
  • Tối ưu hóa hơn nữa các cấu trúc dữ liệu lưu trữ động trong giải thuật luồng nhằm giảm thiểu độ trễ bộ nhớ khi dữ liệu đến với tốc độ cực cao.

Giá trị tham khảo

Luận án là tài liệu tham khảo hữu ích cho các nhóm đối tượng học thuật và ứng dụng chuyên sâu:

  • Nghiên cứu sinh, học viên cao học và giảng viên chuyên ngành Khoa học máy tính, Khoa học dữ liệu:
    • Tham khảo phương pháp luận kết hợp giữa phân đoạn chuỗi thời gian, gom cụm gia tăng và các phép đo khoảng cách (Euclid, DTW, $LB_Keogh$).
    • Khai thác mã giả chi tiết của các giải thuật (Brute-Force, HDD, Hash_DD, KBF_GPU, I-Leader, EP-ILeader, TopK-EP-ALeader-S, EP-Leader-DTW, SEP-Leader-DTW, EPL_S_X) trình bày xuyên suốt các chương và phụ lục.
  • Kỹ sư phần mềm và chuyên gia phân tích dữ liệu trong lĩnh vực Y tế, IoT và Viễn thông:
    • Ứng dụng trực tiếp giải thuật SEP-Leader-DTW hoặc TopK-EP-ALeader-S vào hệ thống giám sát tín hiệu y sinh (như điện tâm đồ ECG trực tuyến), hệ thống cảnh báo cảm biến công nghiệp và giám sát lưu lượng mạng viễn thông.
    • Ứng dụng khung thức tiền xử lý EPL_S_X để làm sạch dữ liệu nhiễu và nâng cao độ chính xác cho các bài toán dự báo tài chính, kinh doanh và khí tượng thủy văn.

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

1. Tại sao luận án lựa chọn hướng tiếp cận dựa vào phân đoạn thay vì hướng tiếp cận dựa vào cửa sổ trượt truyền thống?

Hướng tiếp cận dựa vào cửa sổ trượt (như Brute-Force, HOT SAX) bắt buộc người dùng phải xác định trước chiều dài chuỗi con bất thường ($n$) – đây là một bài toán khó chưa có lời giải tối ưu và nếu chọn sai sẽ làm sai lệch kết quả. Ngoài ra, trượt qua từng điểm làm không gian tìm kiếm rất lớn. Hướng tiếp cận phân đoạn chia chuỗi thành các đoạn có ý nghĩa, giúp rút trích chuỗi con mà không cần cố định chiều dài $n$, đồng thời làm giảm đáng kể số lượng chuỗi con cần xét, từ đó tối ưu hóa thời gian thực thi.

2. Độ đo PALS do luận án đề xuất có vai trò gì và khắc phục hạn chế nào của các tiêu chí cũ?

Độ đo PALS (Percentage of Average Length Segments - Phần trăm các phân đoạn chiều dài trung bình) được đề xuất ở Chương 3 nhằm đánh giá chất lượng của các phương pháp phân đoạn chuỗi thời gian (như PIP, IEP, PLSA). Các tiêu chí cũ của Gensler và Sick (ASC, ASD) chưa phản ánh toàn diện tính chính xác của vùng phân đoạn ($sz$). PALS lượng hóa tỷ lệ các phân đoạn đạt chiều dài trung bình hợp lý, tạo cơ sở toán học vững chắc để chọn phương pháp và tham số phân đoạn tối ưu cho bài toán phát hiện bất thường.

3. Giải thuật EP-Leader-DTW giải quyết trở ngại chi phí tính toán cao của khoảng cách DTW bằng cách nào?

Khoảng cách DTW có độ phức tạp bậc hai $O(n^2)$. EP-Leader-DTW giải quyết trở ngại này nhờ hai kỹ thuật: (1) Sử dụng giải thuật gom cụm Leader đơn giản có độ phức tạp tuyến tính thay vì $k$-Medoids hay I-Leader (tránh việc phải tính toán lại tâm cụm centroid vốn cực kỳ tốn kém dưới độ đo DTW); (2) Tích hợp kỹ thuật cận dưới $LB_Keogh$ của Keogh và cộng sự cùng ràng buộc toàn cục (warping window) để loại bỏ sớm các chuỗi không phù hợp mà không cần tính toán toàn bộ ma trận khoảng cách DTW. Nhờ đó, giải thuật chỉ mất khoảng 35 ms trên chuỗi 5.000 điểm.

4. Giải thuật KBF_GPU xử lý hiện tượng bất thường đôi (twin freak) và dữ liệu siêu lớn như thế nào?

Khi xuất hiện hai chuỗi con bất thường giống hệt nhau (bất thường đôi), giải thuật Brute-Force truyền thống sẽ coi chúng là trùng khớp của nhau và bỏ sót cả hai. Giải thuật KBF cải tiến điều kiện phát hiện bằng mảng Array-K lưu trữ khoảng cách đến $K$ chuỗi con trùng khớp gần nhất. Đồng thời, giải thuật KBF_GPU song song hóa quá trình tính toán ma trận khoảng cách trên phần cứng GPU (đã thử nghiệm trên Tesla V100 và GTX 1080 Ti), giúp tăng tốc độ xử lý vượt bậc trên các bộ dữ liệu chuỗi thời gian kích thước siêu lớn.

5. Khung thức EPL_S_X cải thiện độ chính xác của bài toán dự báo chuỗi thời gian ra sao?

Khung thức EPL_S_X tích hợp quy trình phát hiện bất thường và giải thuật Anomaly-Repair vào bước tiền xử lý dữ liệu trước khi đưa vào mô hình dự báo ($k$-NN, LR, ANN, Hybrid). Bằng cách loại bỏ và hiệu chỉnh các điểm nhiễu/ngoại lai về mức phân phối chuẩn của chuỗi, mô hình dự báo tránh được hiện tượng sai lệch do dữ liệu đột biến, qua đó làm giảm rõ rệt các chỉ số sai số thực nghiệm như MSE, MAE và MAPE trên các tập dữ liệu như Thermostat Sales và Expenditure.

Kết luận

Luận án tiến sĩ của tác giả Huỳnh Thị Thu Thủy đã giải quyết trọn vẹn các thách thức cốt lõi trong bài toán phát hiện chuỗi con bất thường trên dữ liệu chuỗi thời gian thông qua hướng tiếp cận dựa trên phân đoạn và gom cụm gia tăng. Hệ thống các giải thuật đề xuất mới (như EP-ILeader, TopK-EP-ALeader-S, EP-Leader-DTW, SEP-Leader-DTW, KBF_GPU) cùng khung thức dự báo EPL_S_X đã khắc phục triệt để yêu cầu cố định chiều dài chuỗi con, xử lý hiệu quả hiện tượng bất thường đôi, và đáp ứng yêu cầu tính toán tức thời trên dữ liệu chuỗi thời gian dạng tĩnh, dữ liệu siêu lớn và dữ liệu dạng luồng. Các đóng góp của luận án đã được công bố trên các tạp chí khoa học quốc tế uy tín (như Intelligent Data Analysis) và kỷ yếu hội nghị chuyên ngành, mang lại giá trị học thuật và thực tiễn ứng dụng cao.