Bối cảnh và vấn đề nghiên cứu

Phát hiện bất thường trên chuỗi thời gian là một trong những bài toán trọng tâm của lĩnh vực khai phá dữ liệu và học máy, nhận được sự quan tâm nghiên cứu liên tục từ thập niên 80 của thế kỷ XX. Dữ liệu chuỗi thời gian xuất hiện phổ biến trong nhiều ứng dụng thực tế như theo dõi tình trạng bệnh nhân qua tín hiệu điện tâm đồ, phát hiện gian lận giao dịch tài chính, giám sát an toàn hệ thống mạng và chẩn đoán lỗi trong các hệ thống thiết bị cảm biến IoT.

Trong khai phá chuỗi thời gian, khái niệm chuỗi con bất hòa (time series discord) được định nghĩa là chuỗi con có khoảng cách tới lân cận gần nhất không tự khớp lớn nhất. Mặc dù phương pháp tiếp cận dựa trên discord đã chứng minh được hiệu quả cao, các kỹ thuật truyền thống vẫn bộc lộ ba hạn chế lớn:

  1. Hiện tượng "twin-freak": Khi một chuỗi con bất thường xuất hiện từ hai lần trở lên trong chuỗi thời gian, các lần xuất hiện này sẽ trở thành lân cận gần nhất của nhau, làm mất đi tính chất bất hòa theo định nghĩa khoảng cách cực đại.
  2. Phương thức xử lý: Đa số thuật toán chỉ áp dụng cho dữ liệu tĩnh theo lô (batch mode), gặp khó khăn khi triển khai trong môi trường dữ liệu luồng trực tuyến (online mode) với yêu cầu độ trễ bằng 0.
  3. Khả năng mở rộng: Chi phí tính toán lớn khiến các giải thuật khó đáp ứng được các bộ dữ liệu quy mô hàng triệu đến hàng tỷ điểm dữ liệu.

Sự ra đời của thuật toán DAMP (Discord Aware Matrix Profile) do Yue Lu và các cộng sự công bố năm 2022 đã khắc phục được các hạn chế trên bằng cách chỉ báo cáo lần xuất hiện đầu tiên của chuỗi con bất thường, hỗ trợ xử lý trực tuyến và đạt thông lượng tính toán vượt 300.000 Hz. Tuy nhiên, khi cần tìm kiếm chuỗi con bất thường trong một dải chiều dài $[MinL, MaxL]$ thay vì một chiều dài cố định, thuật toán DAMP nguyên bản thực thi theo thứ tự tuần tự qua từng kích thước cửa sổ trượt, dẫn đến tổng thời gian tính toán tăng cao. Do đó, việc cải tiến thuật toán DAMP bằng kỹ thuật tính toán song song là vấn đề có tính cấp thiết kỹ thuật.

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

Mục tiêu của đề tài là tìm hiểu thuật toán phát hiện bất thường trên chuỗi thời gian dưới độ đo Euclid do Yue Lu và các cộng sự đề xuất năm 2022, đánh giá thực nghiệm hiệu quả của thuật toán; sau đó tiến hành nghiên cứu cải tiến tốc độ tính toán bằng phương pháp song song hóa, thực nghiệm và so sánh với thuật toán MERLIN.

Nhiệm vụ nghiên cứu

Văn bản xác định 5 nhiệm vụ cụ thể:

  1. Nghiên cứu môi trường cài đặt song song trong MATLAB.
  2. Nghiên cứu cải tiến thuật toán DAMP bằng phương pháp song song hóa.
  3. Cài đặt thuật toán DAMP trong môi trường xử lý song song.
  4. Tìm hiểu và cài đặt thuật toán MERLIN.
  5. Thực nghiệm, đánh giá và so sánh thuật toán DAMP đơn luồng, DAMP đa luồng, MERLIN đơn luồng và MERLIN đa luồng.

Đố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 và các điểm, chuỗi con bất thường xuất hiện trên chuỗi thời gian.
  • Phạm vi nghiên cứu: Bài toán phát hiện chuỗi con bất thường trên chuỗi thời gian sử dụng độ đo khoảng cách Euclid; cài đặt, thực nghiệm và so sánh thuật toán trên nền tảng phần mềm MATLAB với các tập dữ liệu chuỗi thời gian chuẩn.

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

Cơ sở lý thuyết và các khái niệm nền tảng

Khóa luận xây dựng nội dung dựa trên các khái niệm chuẩn tắc của bài toán khai phá dữ liệu chuỗi thời gian:

  • Chuỗi thời gian (Time series): Dãy các điểm dữ liệu số thực $T = [t_1, t_2, \dots, t_n]$ được thu thập theo các khoảng thời gian liền nhau với bước thời gian bằng nhau, trong đó $n$ là độ dài của chuỗi.
  • Chuỗi con (Subsequence): Dãy con $T_{i,m}$ là tập con liên tục các điểm dữ liệu từ $T$ có độ dài $m$, bắt đầu từ vị trí $i$.
  • Cửa sổ trượt (Sliding Window): Kỹ thuật trích xuất toàn bộ các chuỗi con $C_p$ độ dài $m$ bằng cách trượt một cửa sổ kích thước $m$ dọc theo chuỗi thời gian $T$.
  • Hồ sơ khoảng cách (Distance Profile): Mảng $D_i = [d_{i,1}, d_{i,2}, \dots, d_{i,n-m+1}]$ lưu trữ các khoảng cách Euclid giữa chuỗi con truy vấn $T_{i,m}$ với tất cả các chuỗi con khác trong $T$.
  • Không tự khớp (Non-self match): Hai chuỗi con $T_{p,m}$ và $T_{q,m}$ là không tự khớp khi $|p - q| \ge m$. Nếu $|p - q| < m$, hai chuỗi con được coi là khớp tầm thường (trivial match).
  • Chuỗi thời gian bất hòa (Discord): Chuỗi con $T_{d,m}$ trong $T$ được coi là bất hòa nếu khoảng cách từ nó đến chuỗi con không tự khớp gần nhất đạt giá trị lớn nhất: $\min(d_{d, MD}) > \min(d_{c, MC})$.
  • Hồ sơ ma trận (Matrix Profile - MP): Vectơ $P = [\min(D_1), \min(D_2), \dots, \min(D_{n-m+1})]$ lưu trữ khoảng cách Euclid chuẩn hóa Z giữa mỗi chuỗi con và lân cận không tự khớp gần nhất của nó.
  • Hồ sơ ma trận bên trái (Left-MP): Vectơ $P_L$ chỉ ghi nhận khoảng cách giữa chuỗi con truy vấn hiện tại và các chuỗi con xuất hiện trước nó trong chuỗi thời gian.
  • Độ đo khoảng cách Euclid và Chuẩn hóa Z: Đề tài sử dụng khoảng cách Euclid đa chiều kết hợp chuẩn hóa Z ($v' = \frac{v_i - E_i}{std(E)}$) nhằm đưa giá trị trung bình về xấp xỉ 0 và độ lệch chuẩn về xấp xỉ 1 trước khi tính khoảng cách.

Các thuật toán đối sánh liên quan

  • SAX (Symbolic Aggregate approXimation): Thuật toán do Lin và các cộng sự đề xuất, chuyển đổi chuỗi thời gian liên tục thành các ký tự rời rạc dựa trên phép xấp xỉ tích hợp từng đoạn (PAA).
  • Isolation Forest: Thuật toán phát hiện điểm ngoại lệ do Fei Tony Liu và Zhi-Hua Chu (2008) giới thiệu, sử dụng cấu trúc cây nhị phân cô lập dữ liệu với độ phức tạp thời gian tuyến tính.
  • MERLIN (Matrix Profile XXI): Thuật toán do Takaaki Nakamura và các cộng sự (2020) công bố tại hội nghị IEEE ICDM, có khả năng tìm kiếm discord ở mọi độ dài mà không cần tham số hóa kích thước chuỗi con, hoạt động bằng cách tối ưu thuật toán DRAG và dự đoán ngưỡng khoảng cách $r$.

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

Khóa luận áp dụng phương pháp nghiên cứu tài liệu lý thuyết kết hợp phương pháp thực nghiệm khoa học máy tính:

  • Phân tích nguyên lý thuật toán DAMP và cơ chế tìm kiếm tương tự nhanh MASS (Mueen's Algorithm for Similarity Search).
  • Áp dụng kỹ thuật tính toán song song sử dụng Parallel Computing Toolbox trên MATLAB để tái cấu trúc quy trình thực thi trên dải tham số độ dài chuỗi con.
  • Đánh giá thực nghiệm đối sánh thời gian xử lý và độ chính xác định vị bất thường trên các tập dữ liệu thực tế.

Thiết kế và triển khai giải pháp song song hóa

Nguyên lý hoạt động của thuật toán DAMP

Thuật toán DAMP sử dụng hai vectơ có chiều dài $n - m + 1$:

  • Left-aMP (Left approximate Matrix Profile): Vectơ xấp xỉ hồ sơ ma trận bên trái. Nếu vị trí $j$ là điểm bất hòa trái thực sự thì giá trị tại vị trí đó bằng giá trị thực; các giá trị khác được chặn trên bởi giá trị discord tốt nhất hiện có ($BSF$ - Best-So-Far).
  • PV (Prune Vector): Vectơ logic đánh dấu các chuỗi con có thể loại bỏ. Ban đầu toàn bộ phần tử bằng 1.

Quá trình xử lý mỗi chuỗi con $T_{i,m}$ gồm hai bước:

  1. Xử lý ngược (Backward Processing - BP): Xác định xem chuỗi con hiện tại có phải là discord hay không bằng cách tính khoảng cách tới các chuỗi con phía trước vị trí $i$. Bước nhảy tìm kiếm được khởi tạo bằng lũy thừa của 2 kế tiếp ($\text{prefix} = 2^{\lceil \log_2(m) \rceil}$) và sử dụng hàm MASS. Nếu tìm được lân cận có khoảng cách nhỏ hơn $BSF$, thuật toán dừng sớm; ngược lại, $\text{prefix}$ được nhân đôi liên tiếp cho đến khi chạm về đầu chuỗi thời gian. Nếu chạm vị trí 1 mà khoảng cách vẫn lớn hơn $BSF$, điểm $BSF$ được cập nhật mới.
  2. Xử lý tiến (Forward Processing - FP): So sánh chuỗi con hiện tại với các chuỗi con phía sau từ $i + m$ đến vị trí giới hạn bởi tham số lookahead ($\text{start} = i + m$, $\text{end} = \min(\text{start} + \text{lookahead} - 1, n)$). Những chuỗi con có khoảng cách nhỏ hơn $BSF$ được đánh dấu bit 0 trong $PV$ để bỏ qua trong các vòng lặp tiếp theo.
  • Độ phức tạp: Độ phức tạp không gian của DAMP là $O(n)$, độ phức tạp thời gian trường hợp xấu nhất là $O(n \log n)$ cho mỗi điểm dữ liệu được xử lý qua hàm MASS.

Giải pháp song song hóa trên MATLAB

Để giải quyết bài toán phát hiện chuỗi con bất thường có chiều dài thay đổi trong khoảng $[MinL, MaxL]$, nhóm nghiên cứu thiết kế giải pháp song song hóa chia dải độ dài cho nhiều tác vụ (workers) chạy đồng thời:

Bước Tên bước Nội dung kỹ thuật thực hiện
Bước 1 Khởi tạo thông số Tiếp nhận chuỗi thời gian $T$, độ dài tối thiểu $MinL$, độ dài tối đa $MaxL$, số tác vụ song song noOfTask.
Bước 2 Phân hoạch dải độ dài Tính toán ranges = MaxL - MinL + 1 và steps = ranges / noOfTask. Chia dải độ dài thành noOfTask khoảng con gán cho các worker.
Bước 3 Thực thi song song Sử dụng cấu trúc parfor của Parallel Computing Toolbox để gọi hàm DAMP_2_0_Parallel tính toán độc lập trên các lõi CPU.
Bước 4 Hợp nhất dữ liệu Thu thập mảng kết quả discord_score và position từ các worker, ghép nối tuần tự vào mảng kết quả tổng hợp.
Bước 5 Lọc trùng và kết xuất Loại bỏ các kết quả so trùng tầm thường (các điểm phát hiện nằm quá gần nhau), xuất vị trí và vẽ đồ thị chuỗi con bất thường.

Hàm Parallel điều phối việc phân chia đoạn chiều dài [min, max] cho từng vòng lặp parfor, trong khi hàm DAMP_2_0_Parallel thực hiện quét các độ dài đơn lẻ trong phạm vi được phân công thông qua hàm DAMP_2_0.

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

Chương 1: Tổng quan về dữ liệu chuỗi thời gian

Chương 1 trình bày tổng quan về định nghĩa và đặc điểm của dữ liệu chuỗi thời gian trong thực tế. Tác giả phân tích các tác vụ khai phá chính bao gồm mô hình tự hồi quy (Auto-Regressive), dự báo (Forecast), tìm kiếm tương tự (Similarity search), phát hiện motif (Motif discovery) và phát hiện bất thường (Anomaly detection). Chương này làm rõ 4 thách thức kỹ thuật khi giải quyết bài toán phát hiện bất thường:

  • Sự thiếu hụt dữ liệu được gán nhãn bất thường trong môi trường thực tế.
  • Kích thước dữ liệu lớn (đặc biệt trong các ứng dụng IoT) đòi hỏi năng lực xử lý cao.
  • Hiện tượng mất cân bằng dữ liệu nghiêm trọng giữa các biến cố bình thường và biến cố bất thường hiếm gặp.
  • Tính phi tuyến và độ phức tạp cao của các quy luật dao động thời gian.

Chương 2: Các kiến thức cơ bản

Chương 2 thiết lập hệ thống định nghĩa toán học làm cơ sở cho toàn bộ đồ án, bao gồm chuỗi thời gian, chuỗi con, cửa sổ trượt, hồ sơ khoảng cách, không tự khớp, chuỗi thời gian bất hòa, hồ sơ ma trận và hồ sơ ma trận bên trái. Tác giả hệ thống hóa các tính chất tiên đề của độ đo khoảng cách và công thức khoảng cách Euclid từ không gian 1 chiều, 2 chiều đến đa chiều, cùng quy trình chuẩn hóa Z. Phần cuối chương điểm luận các phương pháp phát hiện bất thường đã công bố gồm thuật toán SAX, thuật toán Isolation Forest và thuật toán MERLIN (phân tích chi tiết quy trình dự đoán khoảng cách $r$ qua 3 bước dựa trên thuật toán DRAG).

Chương 3: Phương pháp phát hiện bất thường với thuật toán DAMP

Chương 3 đi sâu vào cơ chế hoạt động của thuật toán DAMP do Yue Lu đề xuất năm 2022. Tác giả mô tả chi tiết thuật toán qua mã giả của ba hàm: hàm chính DAMP, hàm xử lý ngược BackwardProcessing và hàm xử lý tiến ForwardProcessing. Chương này phân tích chi tiết quy trình nhân đôi tiền tố theo hàm mũ 2, cơ chế cắt tỉa chuỗi con bằng lookahead, phân tích độ phức tạp thuật toán và giải thích hiện tượng "vấn đề gây hiểu lầm" (misleading issues) trên đồ thị Left-aMP khi có forward processing. Tiếp đó, tác giả trình bày kiến trúc tính toán song song trong MATLAB với Parallel Computing Toolbox, cơ chế hoạt động của parfor và triển khai chi tiết mã nguồn song song hóa DAMP qua hai hàm Parallel và DAMP_2_0_Parallel.

Chương 4: Đánh giá bằng thực nghiệm

Chương 4 mô tả toàn bộ cấu hình môi trường thử nghiệm phần cứng, phần mềm và 5 tập dữ liệu thực nghiệm chuẩn từ kho UCR Anomaly Archive. Tác giả tiến hành thiết lập các kịch bản thực nghiệm đo đạc thời gian thực thi và độ chính xác định vị bất thường, đối sánh giữa 4 biến thể: DAMP đơn luồng, DAMP đa luồng, MERLIN đơn luồng và MERLIN đa luồng. Chương này cũng thực hiện khảo sát tham số lookahead trên nhiều mức giá trị khác nhau để đánh giá sự biến thiên về thời gian xử lý và độ chính xác.

Chương 5: Kết luận và định hướng phát triển

Chương 5 đúc kết các kết quả đạt được của khóa luận sau quá trình cài đặt và thực nghiệm, khẳng định tính hiệu quả của giải pháp song song hóa dải chiều dài chuỗi con trên nền tảng MATLAB. Đồng thời, chương này chỉ ra các hạn chế kỹ thuật hiện tại và đề xuất các hướng nghiên cứu hoàn thiện giải thuật trong tương lai.

Kết quả và đóng góp

Cấu hình môi trường và các tập dữ liệu thực nghiệm

Thực nghiệm được thực hiện trên thiết bị phần cứng Laptop Lenovo Legion 5 (CPU AMD Ryzen 5 5600H, RAM 16GB) sử dụng phần mềm MATLAB R2019b. Dữ liệu đánh giá gồm các tập dữ liệu thực nghiệm từ UCR Anomaly Archive:

Tên tập dữ liệu Chiều dài chuỗi Mô tả hiện tượng bất thường thực nghiệm
073_UCR_Anomaly_DISTORTEDpark3m 90.000 điểm Dáng đi của bệnh nhân Parkinson; hoán đổi dữ liệu chân phải và chân trái trong một chu kỳ.
167_UCR_Anomaly_gait1 65.000 điểm Dáng đi bất đối xứng của bệnh nhân Huntington; thay thế dữ liệu chân lành sang chân trái trong một chu kỳ.
165_UCR_Anomaly_apneaecg4 38.269 điểm Nhịp tim hỗn hợp; tác động vào một nhịp co tâm thất sớm để làm thay đổi đường xu hướng dữ liệu.
154_UCR_Anomaly_PowerDemand3 29.931 điểm Nhu cầu sử dụng điện tại Ý (1995–1998); thay thế dữ liệu điện 3 ngày bằng dữ liệu huyết áp động mạch.
168_UCR_Anomaly_gait2 65.000 điểm Cảm biến bàn chân trái bị lỗi; lấy dữ liệu lỗi thay cho chân phải và dịch chuyển lệch nửa chu kỳ.

Kết quả đo lường và khảo sát thực nghiệm

Các kịch bản thực nghiệm trong khóa luận ghi nhận các kết quả cụ thể:

  • Hiệu năng thời gian thực thi: Việc áp dụng cấu trúc parfor phân chia dải độ dài $[MinL, MaxL]$ giúp thuật toán DAMP đa luồng rút ngắn đáng kể thời gian xử lý so với DAMP đơn luồng trên toàn bộ các tập dữ liệu thử nghiệm. DAMP đa luồng duy trì ưu thế thời gian khi so sánh với thuật toán MERLIN đơn luồng và đa luồng trong các thử nghiệm tương ứng.
  • Độ chính xác định vị bất thường:
    • Trên tập dữ liệu 073_UCR_Anomaly_DISTORTEDpark3m (độ dài 90.000, $minL = 40$, bước nhảy = 1, $maxL$ từ 50 đến 70, lookahead = 0), thuật toán phát hiện chính xác các chuỗi con bất thường tại các vị trí 33450, 85651, 1392, 263 và 1395.
    • Trên tập dữ liệu 167_UCR_Anomaly_gait1 (độ dài 65.000, $minL = 40$, bước nhảy = 1, $maxL$ từ 50 đến 70, lookahead = 0), thuật toán xác định các vị trí bất thường tại 279, 1692, 25479, 9918 và 64895.
    • Trên tập dữ liệu 165_UCR_Anomaly_apneaecg4 (độ dài 38.269, $minL = 40$, bước nhảy = 1, $maxL$ từ 50 đến 70, lookahead = 0), thuật toán định vị các điểm bất thường tại các vị trí 27824, 5808, 27823 và 1150.
    • Trên tập dữ liệu 154_UCR_Anomaly_PowerDemand3 (độ dài 29.931, $minL = 40$, bước nhảy = 1, $maxL$ từ 80 đến 160, lookahead = 1024), thuật toán tìm thấy các chuỗi con bất thường tại vị trí 8711, 2521, 5388 và 14210.
  • Khảo sát tham số lookahead: Trên tập 165_UCR_Anomaly_apneaecg4 ($maxL$ từ 60 đến 100), tác giả thực nghiệm đo thời gian thực hiện qua các mốc lookahead bằng 0, 128, 512, 2048 và 8196 (8192). Trên tập 154_UCR_Anomaly_PowerDemand3 ($maxL$ từ 80 đến 160), tác giả thực nghiệm với các mức lookahead bằng 512, 1024, 2048, 4096 và 8192, từ đó chỉ ra mức độ ảnh hưởng của phạm vi nhìn trước đến thời gian tính toán của quy trình Forward Processing.

Đóng góp của đề tài

  • Cài đặt và thực nghiệm thành công thuật toán DAMP trong môi trường MATLAB, kiểm chứng cơ chế hoạt động của Backward Processing và Forward Processing trên dữ liệu chuỗi thời gian thực tế.
  • Thiết kế giải pháp phân chia dải độ dài chuỗi con $[MinL, MaxL]$ kết hợp với cấu trúc song song parfor của Parallel Computing Toolbox, giúp cải thiện tốc độ phát hiện discord trên dải chiều dài thay đổi.
  • Cung cấp kết quả so sánh thực nghiệm toàn diện giữa 4 mô hình: DAMP đơn luồng, DAMP đa luồng, MERLIN đơn luồng và MERLIN đa luồng, làm rõ sự khác biệt về thời gian và độ chính xác.

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

Hạn chế

  • Phạm vi dữ liệu: Nghiên cứu chỉ tập trung giải quyết bài toán trên chuỗi thời gian đơn biến (univariate time series); chưa mở rộng đánh giá trên các hệ thống chuỗi thời gian đa biến phức tạp.
  • Độ đo khoảng cách: Thuật toán hoàn toàn phụ thuộc vào độ đo khoảng cách Euclid chuẩn hóa Z, chưa hỗ trợ các độ đo phi tuyến khác như DTW (Dynamic Time Warping).
  • Cấp độ song song hóa: Giải pháp song song hóa dừng lại ở mức phân chia khoảng độ dài chuỗi con $[MinL, MaxL]$ trên các luồng CPU thông qua parfor, chưa can thiệp sâu vào việc song song hóa quy trình tính toán hồ sơ khoảng cách MASS bên trong thuật toán DAMP trên nền tảng GPU.
  • Tối ưu hóa tham số lookahead: Việc lựa chọn giá trị lookahead cho quy trình xử lý tiến vẫn dựa trên khảo sát thực nghiệm thủ công, chưa có cơ chế tự động thích ứng với đặc tính dữ liệu.

Hướng nghiên cứu tiếp

  • Mở rộng thuật toán DAMP song song để phát hiện bất thường trên dữ liệu chuỗi thời gian đa biến (multivariate time series).
  • Nghiên cứu cơ chế tự động xác định tham số lookahead tối ưu cho từng loại dữ liệu cụ thể nhằm nâng cao hơn nữa tỷ lệ cắt tỉa của quy trình Forward Processing.
  • Phát triển cài đặt giải thuật DAMP trên nền tảng tính toán đồ họa GPU (sử dụng CUDA hoặc các thư viện tính toán song song chuyên dụng) nhằm khai thác tối đa năng lực xử lý dữ liệu quy mô hàng tỷ điểm.

Giá trị tham khảo

Tài liệu khóa luận có giá trị tham khảo thiết thực cho các đối tượng và mục đích học thuật sau:

  • Sinh viên và học viên chuyên ngành Kỹ thuật dữ liệu, Khoa học dữ liệu và Công nghệ thông tin: Là tài liệu tham khảo chi tiết về lý thuyết Matrix Profile, thuật toán DAMP và thuật toán MERLIN trong bài toán phát hiện chuỗi con bất thường.
  • Người nghiên cứu về tính toán hiệu năng cao trong xử lý dữ liệu: Tham khảo phương pháp sử dụng Parallel Computing Toolbox và vòng lặp parfor trong MATLAB để phân chia tải tính toán theo dải tham số.
  • Các phần nội dung đáng tham khảo:
    • Chương 3 cung cấp giải thích chi tiết kèm mã giả thuật toán DAMP, cơ chế hoạt động của Backward Processing (nhân đôi tiền tố theo lũy thừa 2) và Forward Processing (cắt tỉa bằng lookahead).
    • Phân tích về "vấn đề gây hiểu lầm" khi diễn giải các đỉnh trên đồ thị Left-aMP, giúp người triển khai tránh sai sót khi đánh giá các vị trí bất thường.
    • Chương 4 cung cấp bộ kịch bản thực nghiệm chi tiết trên các tập dữ liệu chuẩn từ UCR Anomaly Archive, hữu ích cho các nghiên cứu đối sánh giải thuật phát hiện bất thường sau này.

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

1. Vấn đề "twin-freak" trong phát hiện chuỗi con bất thường là gì và thuật toán DAMP giải quyết như thế nào?

"Twin-freak" là hiện tượng một chuỗi con bất thường xuất hiện từ hai lần trở lên trong cùng một chuỗi thời gian. Trong các định nghĩa discord truyền thống, mỗi lần xuất hiện của chuỗi này lại chính là lân cận gần nhất của lần xuất hiện kia, dẫn đến khoảng cách lân cận gần nhất bị thu nhỏ và chuỗi không còn được xem là bất hòa. Thuật toán DAMP giải quyết triệt để vấn đề này bằng cách sử dụng hồ sơ ma trận bên trái (Left-MP), theo đó mỗi chuỗi con chỉ so sánh với các chuỗi con xuất hiện trước nó; do đó, DAMP luôn phát hiện và báo cáo chính xác lần xuất hiện đầu tiên của điểm bất thường mà không bị triệt tiêu bởi các lần xuất hiện tiếp theo.

2. Hai quy trình xử lý ngược (Backward Processing) và xử lý tiến (Forward Processing) trong DAMP đóng vai trò gì?

  • Xử lý ngược (BP): Tìm kiếm ngược từ vị trí hiện tại về các chuỗi con phía trước để kiểm tra xem chuỗi con hiện tại có phải là discord hay không. BP bắt đầu với độ dài tiền tố $\text{prefix} = 2^{\lceil \log_2(m) \rceil}$ và nhân đôi dần kích thước tìm kiếm; nếu khoảng cách nhỏ hơn giá trị discord tốt nhất hiện có ($BSF$), thuật toán dừng sớm để tiết kiệm chi phí.
  • Xử lý tiến (FP): Lấy chuỗi con hiện tại so sánh với các chuỗi con phía sau trong một phạm vi giới hạn bởi tham số lookahead. Nếu tìm thấy các chuỗi con có khoảng cách nhỏ hơn $BSF$, FP sẽ đánh dấu bit 0 vào vectơ cắt tỉa ($PV$) để thuật toán bỏ qua việc xử lý tốn kém đối với các chuỗi con này ở các bước sau.

3. "Vấn đề gây hiểu lầm" khi đọc đồ thị Left-aMP có áp dụng Forward Processing là gì?

Khi áp dụng Forward Processing, đồ thị Left-aMP chỉ phản ánh chính xác vị trí và độ cao của $k$ đỉnh cao nhất (top-$k$ discord). Các đỉnh từ $k+1$ trở đi có thể xuất hiện dưới dạng một đoạn giá trị cao bằng phẳng kéo dài, nhưng đây không phải là biểu hiện của các điểm bất thường nhỏ hơn, mà thực chất chỉ là vùng dữ liệu đã được cắt tỉa do thuật toán tìm thấy chuỗi con phù hợp thấp hơn $BSF$ hiện tại.

4. Nhóm tác giả thực hiện giải pháp song song hóa thuật toán DAMP như thế nào trong MATLAB?

Nhóm tác giả nhận thấy DAMP nguyên bản phải duyệt tuần tự từng giá trị chiều dài khi tìm kiếm bất thường trong dải $[MinL, MaxL]$. Giải pháp song song hóa được xây dựng bằng cách chia dải $[MinL, MaxL]$ thành các đoạn con độc lập dựa trên số lượng worker (noOfTask), sau đó sử dụng cấu trúc vòng lặp parfor của Parallel Computing Toolbox trong hàm Parallel để phân phối tính toán đồng thời trên các nhân CPU. Kết quả tính toán từ hàm con DAMP_2_0_Parallel được tổng hợp lại và tiến hành lọc trùng tầm thường để kết xuất vị trí bất thường cuối cùng.

5. Khóa luận sử dụng các tập dữ liệu thực nghiệm nào và chúng mô phỏng những hiện tượng bất thường gì?

Nghiên cứu sử dụng 5 tập dữ liệu chuẩn từ kho dữ liệu UCR Anomaly Archive:

  • 073_UCR_Anomaly_DISTORTEDpark3m (90.000 điểm): Dáng đi bệnh Parkinson bị hoán đổi chân phải và chân trái trong 1 chu kỳ.
  • 167_UCR_Anomaly_gait1 (65.000 điểm): Dáng đi bệnh Huntington bị thay thế dữ liệu chân lành sang chân trái trong 1 chu kỳ.
  • 165_UCR_Anomaly_apneaecg4 (38.269 điểm): Nhịp tim bị tác động một nhịp co tâm thất sớm làm đổi đường xu hướng.
  • 154_UCR_Anomaly_PowerDemand3 (29.931 điểm): Nhu cầu sử dụng điện tại Ý bị thay thế 3 ngày bằng dữ liệu huyết áp động mạch.
  • 168_UCR_Anomaly_gait2 (65.000 điểm): Dữ liệu cảm biến bàn chân trái bị lỗi được dùng để thay thế cho chân phải và lệch nửa chu kỳ.

Kết luận

Đồ án tốt nghiệp đã nghiên cứu và cài đặt thành công thuật toán phát hiện chuỗi con bất thường DAMP cùng thuật toán đối sánh MERLIN trên nền tảng phần mềm MATLAB. Nhóm tác giả đã đề xuất và triển khai giải pháp song song hóa quy trình quét dải chiều dài chuỗi con $[MinL, MaxL]$ thông qua Parallel Computing Toolbox, giúp cải thiện đáng kể thời gian thực thi so với phương pháp đơn luồng truyền thống trong khi vẫn đảm bảo độ chính xác định vị các điểm bất thường. Các kết quả thực nghiệm trên 5 tập dữ liệu chuẩn thuộc kho UCR Anomaly Archive cung cấp cơ sở dữ liệu đối sánh tin cậy cho các nghiên cứu tiếp theo về khai phá dữ liệu chuỗi thời gian hiệu năng cao.