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

Khám phá các phương pháp phát hiện điểm thay đổi và chuỗi con bất thường trong dữ liệu chuỗi thời gian để nâng cao phân tích dữ liệu.

• Tác giả: Huỳnh Thị Thu Thủy
• Người hướng dẫn: PGS. Dương Tuấn Anh
• Trường học: Đại học Quốc gia TP. Hồ Chí Minh
• Chuyên ngành: Khoa học máy tính
• Đề tài: Phát Hiện Chuỗi Con Bất Thường Trong Dữ Liệu Chuỗi Thời Gian
• Loại tài liệu: luận án tiến sĩ
• Năm xuất bản: 2022
• Địa điểm: TP. Hồ Chí Minh

Tóm tắt

I. Tổng Quan Về Phát Hiện Chuỗi Con Bất Thường Trong Dữ Liệu Chuỗi Thời Gian

Phát hiện chuỗi con bất thường trong dữ liệu chuỗi thời gian là một lĩnh vực nghiên cứu quan trọng, đặc biệt trong các ứng dụng như y tế, tài chính và thương mại điện tử. Dữ liệu chuỗi thời gian thường chứa nhiều thông tin quý giá, nhưng cũng tiềm ẩn nhiều thách thức trong việc phát hiện các mẫu bất thường. Việc phát hiện này không chỉ giúp nhận diện các sự kiện quan trọng mà còn hỗ trợ trong việc ra quyết định kịp thời.

1.1. Định Nghĩa Dữ Liệu Chuỗi Thời Gian

Dữ liệu chuỗi thời gian là tập hợp các giá trị được thu thập theo thời gian. Chúng thường được sử dụng để phân tích xu hướng và dự đoán tương lai. Việc hiểu rõ về dữ liệu này là rất quan trọng trong việc phát hiện các chuỗi con bất thường.

1.2. Tầm Quan Trọng Của Phát Hiện Bất Thường

Phát hiện bất thường giúp nhận diện các sự kiện không bình thường trong dữ liệu, từ đó có thể đưa ra các biện pháp kịp thời. Điều này đặc biệt quan trọng trong các lĩnh vực như y tế, nơi mà sự phát hiện sớm có thể cứu sống bệnh nhân.

II. Những Thách Thức Trong Phát Hiện Chuỗi Con Bất Thường

Phát hiện chuỗi con bất thường trong dữ liệu chuỗi thời gian đối mặt với nhiều thách thức. Các thách thức này bao gồm việc xác định chiều dài của chuỗi con bất thường, đảm bảo tính chính xác và hiệu quả trong thời gian thực. Những vấn đề này cần được giải quyết để cải thiện độ tin cậy của các phương pháp phát hiện.

2.1. Xác Định Chiều Dài Chuỗi Con Bất Thường

Một trong những thách thức lớn nhất là xác định chiều dài của chuỗi con bất thường trước khi thực hiện phát hiện. Việc này đòi hỏi các phương pháp phải có khả năng tự động hóa trong việc xác định chiều dài phù hợp.

2.2. Đảm Bảo Tính Chính Xác Trong Kết Quả

Tính chính xác của kết quả phát hiện là rất quan trọng. Các phương pháp cần phải đảm bảo rằng các chuỗi con bất thường được phát hiện phải chính xác và đáng tin cậy, tránh gây ra những hiểu lầm không cần thiết.

III. Phương Pháp Phát Hiện Chuỗi Con Bất Thường Hiệu Quả

Để giải quyết các thách thức trong phát hiện chuỗi con bất thường, nhiều phương pháp đã được phát triển. Các phương pháp này bao gồm việc sử dụng các thuật toán tiên tiến và các kỹ thuật phân đoạn để cải thiện độ chính xác và hiệu quả.

3.1. Thuật Toán EP ILeader

Thuật toán EP-ILeader là một trong những phương pháp hiệu quả trong việc phát hiện chuỗi con bất thường. Nó sử dụng các kỹ thuật phân đoạn để giảm độ phức tạp trong việc xác định chuỗi con bất thường.

3.2. Giải Thuật SEP Leader DTW

Giải thuật SEP-Leader-DTW được thiết kế để phát hiện bất thường trong dữ liệu chuỗi thời gian dạng luồng. Nó đảm bảo tính chính xác và thời gian thực thi nhanh chóng, đáp ứng yêu cầu của các ứng dụng thực tế.

IV. Ứng Dụng Thực Tiễn Của Phát Hiện Chuỗi Con Bất Thường

Phát hiện chuỗi con bất thường có nhiều ứng dụng thực tiễn trong các lĩnh vực khác nhau. Từ y tế đến tài chính, việc phát hiện sớm các bất thường có thể giúp cải thiện chất lượng dịch vụ và giảm thiểu rủi ro.

4.1. Ứng Dụng Trong Y Tế

Trong y tế, phát hiện bất thường có thể giúp nhận diện sớm các bệnh lý, từ đó đưa ra các biện pháp điều trị kịp thời. Điều này có thể cứu sống bệnh nhân và giảm thiểu chi phí điều trị.

4.2. Ứng Dụng Trong Tài Chính

Trong lĩnh vực tài chính, phát hiện bất thường giúp nhận diện các giao dịch gian lận hoặc bất thường, từ đó bảo vệ tài sản và giảm thiểu rủi ro cho các tổ chức tài chính.

V. Kết Luận Và Tương Lai Của Phát Hiện Chuỗi Con Bất Thường

Phát hiện chuỗi con bất thường trong dữ liệu chuỗi thời gian là một lĩnh vực nghiên cứu đang phát triển mạnh mẽ. Với sự tiến bộ của công nghệ và các thuật toán mới, khả năng phát hiện bất thường sẽ ngày càng chính xác và hiệu quả hơn.

5.1. Những Đóng Góp Chính Của Nghiên Cứu

Nghiên cứu đã đóng góp nhiều phương pháp mới và cải tiến cho việc phát hiện chuỗi con bất thường, giúp nâng cao độ chính xác và hiệu quả trong các ứng dụng thực tiễn.

5.2. Hướng Phát Triển Tương Lai

Trong tương lai, việc phát triển các phương pháp phát hiện bất thường sẽ tiếp tục được chú trọng, đặc biệt là trong bối cảnh dữ liệu ngày càng lớn và phức tạp. Các nghiên cứu sẽ tập trung vào việc cải thiện tính chính xác và thời gian thực thi của các thuật toán.

Trích đoạn nội dung tài liệu

CHƯƠNG 1 GIÓI THIỆU.1 Động cơ nghiên cứu của đề tài.2 Ý nghĩa khoa học và ý nghĩa thực tiễn của đề tài.3 Mục tiêu, đổi tượng và phạm vi nghiên cứu.4 Các đóng góp chính cùa luận án.5 Cấu trúc luận án. 13 CHƯƠNG 2 Cơ SỎ LÝ THUYẾT VÀ CÁC CÔNG TRÌNH LIÊN QUAN. Dữ liệu chuỗi thời gian. Dữ liệu chuồi thời gian dạng luồng.

Trùng khớp không tầm thường. Chuồi con bất thường. Chuỗi con bất thường nhất. Chuồi con bất thường thứ k.8 Điểm thay dổi.2 Khoảng cách xoắn thời gian động.3 Thu giảm số chiều.1 Phương pháp xấp xi gộp từng đoạn.2 Phương pháp xấp xỉ gộp tuyến tính từng đoạn.4 Rời rạc hóa dừ liệu.

23 Phương pháp xấp xỉ gộp ký hiệu hóa.5 Các công trình phát hiện chuỗi con bất thường trên dừ liệu chuỗi thời gian dạng tĩnh 25 2.6 Các công trình phát hiện chuỗi con bất thường trên dữ liệu chuỗi thời gian dạng luồng 29 vii 2.7 Kết chương. 31 CHƯƠNG 3 PHÁT HIỆN NHỮNG ĐIÉM THAY ĐỒĨ TRÊN CHUỔI THÒĨ GIAN VÀ CÁC PHƯƠNG PHÁP PHÂN ĐOẠN.1 Từ phương pháp phát hiện các điếm thay đôi đến phương pháp phân đoạn .1 Phương pháp điểm cực trị quan trọng.2 Phương pháp điểm quan trọng càm nhận được.3 Phương pháp xấp xi bình phương tối thiểu đa thức.2 Tiêu chí đánh giá các phương pháp phân đoạn do Gensler và Sick đề xuất .3 Đe xuất tiêu chí dánh giá các phương pháp phân đoạn.1 Đề xuất độ đo PALS đánh giá chấtlượng phương pháp phân đoạn.2 Kết quả thực nghiệm.4 Ket chương. 45 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.1 Giới thiệu vấn đề.1 Giải thuật HOT SAX.2 Giới thiệu về các giải thuật cải tiến.2 Giải thuật cải tiến I-HOTSAX.1 Các kỹ thuật hỗ trợ.2 Giải thuật cải tiến I-HOTSAX phát hiện chuồi con bất thường.3 Giải thuật cải tiến Hash DD.4 Giải thuật cải tiến KBF_GPU.1 Chuỗi con bất thường theo khoáng cách K.2 Tìm kiếm chuỗi con bất thường theo khoảng cách K.3 Tăng tốc giải thuật KBF với GPU.5 Đánh giá các giải thuật cái tiến.1 Đánh giá giải thuật I-HOTSAX.2 Đánh giá giải thuật Hash DD.3 Đánh giá giải thuật KBF GPU.4 So sánh các giải thuật cải tiến.6 Kết chương.75 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.1 Phát hiện chuỗi con bất thường nhất.1 Giải thuật đề xuất cải tiến 1-Lcadcr cho bài toán gom cụm các chuỗi con 77 5.2 Giải thuật đề xuất mới EP-ILeader cho 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 tĩnh.3 Đánh giá các giái thuật phát hiện chuồi con bất thường nhất.2 Phát hiện k chuỗi con bất thường nhất.1 Giới thiệu vấn đề.2 Các kỳ thuật hồ trợ.3 Các giải thuật chính được đề xuất.4 Đánh giá các giải thuật phát hiện k chuồi con bất thường nhất.3 Kết chương. 108 CHƯƠNG 6 ĐỀ XUẤT CÁC PHƯƠNG PHÁP PHÁT HIỆN CHUỎ1 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 110 6.1 Giới thiệu vấn đề.2 Đe xuất giải thuật EP-Leader-DTW trên chuỗi thời gian dạng tình.1 Giải thuật EP-Leader-DTW.2 Biện luận về giải thuật EP-Leader-DTW.3 Đồ xuất giải thuật SEP-Lcadcr-DTW trôn chuỗi thời gian dạng luồng.1 Giải thuật SEP-Lcadcr-DTW.2 Biện luận về giải thuật SEP-Lcadcr-DTW.4 Đánh giá các đề xuất.1 Thực nghiệm 1: So sánh kết quá cúa việc sử dụng DTW và Euclid trong phát hiện chuồi con bất thường trẽn dữ liệu chuỗi thời gian.2 Thực nghiệm 2: Kiếm tra tinh chính xác của EP-Leader-DTW phát hiện chuồi con bất thường trên chuồi thời gian dạng tĩnh.3 Thực nghiệm 3: Kiểm tra tính hữu hiệu của EP-Leader-DTW so với giải thuật QR-AF khi phát hiện chuỗi con bất thường trên chuồi thời gian.4 Thực nghiệm 4: Kiểm tra tính chính xác cùa SEP-Leader-DTW phát hiện chuồi con bất thường trên dữ liệu chuỗi thời gian dạng luồng.5 Thực nghiệm 5: Kiểm tra tính hữu hiệu của SEP-Leader-DTW phát hiện chuồi con bất thường trên chuỗi thời gian dạng luồng.5 Kct chương.

130 CHƯƠNG 7 ỦNG DỤNG PHÁT HIỆN BÁT THƯỜNG ĐÉ CAI THIỆN CHÁT LƯỢNG Dự BÁO DỮ LIỆU CHUỎI THỜI GIAN.1 Giới thiệu vấn đề.2 Đe xuất hướng tiếp cận mới EPLSX cho dự báo dữ liệu chuồi thời gian.1 Hướng tiếp cận EPL S X dựa vào hiệu chỉnh bất thường để dự báo dữ liệu chuỗi thời gian.2 Chi tiết của hướng tiếp cận EPLSX dự báo dừ liệu chuỗi thời gian.3 Đặc diêm của hưởng tiếp cận EPLSX dự báo dừ liệu chuồi thời gian 137 7.3 Đánh giá đề xuất EPL-S-X.1 Các câu hỏi nghiên cứu.2 Các thiết lập thực nghiệm.3 Các kết quả thực nghiệm và thảo luận.4 Kểt chương. 148 CHƯƠNG 8 KẾT LUẬN.1 Những đóng góp chính của luận án.2 Hướng phát triển. 153 DANH MỤC CÔNG TRÌNH ĐÃ CÒNG BÓ. 154 TÀI LIỆU THAM KHẢO.

173 X DANH MỤC CÁC HÌNH ẢNH Hình 2.1: Dừ liệu chuồi thời gian giá cổ phiếu của một công ty.2: Chuồi thời gian điện tâm đồ - ECG với một chuỗi con bất thường nhất.3: Minh họa các điểm thay đổi (dấu sao) trên chuỗi thời gian điện tâm đồ ECG .4: Minh họa các điểm thay đổi trên bộ dừ liệu Oil [62J.5: Minh họa khoảng cách Euclid giừa hai chuồi Cl, C2 giống nhau về hình dạng nhưng lệch nhau về thời gian.6: Minh họa khoảng cách DTW giữa hai chuỗi Cl, C2 giống nhau về hình dạng nhưng lệch nhau về thời gian.7: Ma trận xoắn và đường xoắn để tính khoảng cách DTW giữa hai chuỗi Q và c.8: Phép biến đổi PAA [76].9: Minh họa phương pháp xấp xỉ gộp tuyến tính từng đoạn PLA [77].10: Phương pháp SAX [50].1: Điếm cực tiêu quan trọng Hình 3.2: Diêm cực tiêu quan trọng nghiêm cách [25].3: Điểm cực tiểu quan trọng bên trái Hình 3.4: Điểm cực tiêu quan trọng bên phải.5: Điểm cực tiểu quan trọng phăng.7: Ví dụ vê chuôi thời gian được mô hình hóa bơi đa thức với bậc khác nhau (a) Đa thức bậc 1 và (b) đa thức bậc 2 [26].8: Sơ đồ mô tả cách xác định giá trị cúa tiêu chí ASC.1: cấu trúc bảng băm hồ trợ vòng lặp trong và vòng lặp ngoài của Hash_DD 53 Hình 4.2: Mã giả của giải thuật xây dựng bảng băm từ một chuồi dừ liệu thời gian.3: Mã già cùa giải thuật phát hiện bất thường HashJDD.4: Mã giả của giải thuật phát hiện bất thường KBF.5: Mang Array-K lưu trữ K khoảng cách (K = 5) liên quan đến K chuỗi con trùng khớp gần nhất của chuỗi con đang xét. (a) Trạng thái hiện tại của mảng Array-K, (b) xi Trạng thái cập nhật của mảng sau khi có chuồi con có khoảng cách 2.7 đến chuỗi con đang xét.6: Mã già cùa giải thuật phát hiện bất thường KBF_GPU.7: Chuồi con bất thường tìm được bởi Brute-Force và KBF-GPU.8: Các chuồi con bất thường tìm được bới KBF_GPU.9: Biểu đồ thời gian thực thi của HOT SAX và KBF GPU khi thay đổi chiều dài cúa chuồi thời gian (trên bộ dữ liệu koski-ecg).1: Giải thuật I-Leader: (a) Sau bước gom cụm đầu tiên, (b) Sau bước tinh chinh cụm.2: Mã giả của giải thuật phát hiện bất thường EP-ILcadcr.3: Kết qua gom cụm của I-Leader và Leader trên tập dừ liệu Trace.4: Hình dạng các chuồi con bất thường được tìm thấy bơi 2 giài thuật Brutc- Force và EP_ILeader.5: Minh họa độ đo Euclid có sứ dụng kỹ thuật từ bo sớm.6: Cửa sổ di chuyển.7: Vùng đệm xoay vòng.8: Mã giả cua giái thuật phát hiện k chuồi con bất thường nhất trên dừ liệu chuỗi thời gian dạng luồng TopK-EP-ALeader-S.9: Chuồi con bất thường tim được bởi Brute-Force, EP-ILeader, và EP-ALeader .10: Chuỗi con bẩt thường tìm được bới Brute-Force và TopK-EP-ALeader.11: Ba chuỗi con bất thường nhất do TopK-EP-ALeader-S tìm được.12: Ba chuồi con bất thường nhất được đánh dấu bởi chuyên gia [51.1: Ý tướng phát hiện bất thường trên chuồi thời gian với khoáng cách DTW112 Hình 6.2: Mã giả của giải thuật EP-Leader-DTW phát hiện chuồi con bất thường nhất trên chuỗi thời gian dạng tĩnh.3: Mã giả của giải thuật SEP-Leader-DTW phát hiện chuỗi con bất thường nhất trên chuồi thời gian dạng luồng.4: Tập dừ liệu chuỗi thời gian MIT-BIH_08405 và chuồi con bất thường tìm được khi sử dụng giải thuật Brute-Force với độ đo Euclid và BF DTW dùng khoảng cách DTW.5: Sự chồng lên nhau giữa chuồi con bất thường tìm được bởi EP-Leader-DTW và chuồi con bất thường do BF-DTW tim được.6: Hình ảnh cua các chuồi con bất thường do EP-Lcadcr-DTW phát hiện và những chuồi con bất thường được phát hiện bởi giải thuật cơ sở BF-DTW.7: Chuỗi con bất thường trên bộ Tckl6 được đánh dấu bởi chuyên gia [6].8: Chuỗi con bẩt thường do SEP-Leader-DTW tìm được trên chuồi thời gian Tekl6 mô phóng dạng luồng và chuồi con bất thường do chuyên gia dánh dấu [6J .9: Minh họa 3 chuồi con bất thường được đánh dấu bời chuyên gia [51 và các chuỗi con bất thường do SEP-Leader-DTW tìm được trên tập dữ liệu điện tâm đồ ECG.1: Mã giả của hướng tiếp cận dự báo EPL_S_X.2: Mã giả cùa kỳ thuật hiệu chinh bất thường Anomaly-Repair.3: Dừ liệu chuồi thời gian Thermostat Sales được dự báo bời EPL_S_kNN (nét vẽ có hình tròn) và k-NN (nét vẽ có hình sao) và dữ liệu thực (nét vẽ liền) trong hai trường hợp có vị trí bất thường khác nhau: (a) vị trí bất thường là 35, (b) vị trí bất thường là 7.4: Dừ liệu thực (nét vẽ liền), dữ liệu dự báo bới EPL_S_kNN (nét vẽ có hình tròn) và dừ liệu dự báo bởi k-NN (nét vẽ có hình sao) trên dữ liệu chuồi thời gian Expenditure. 148 Hình AI: Hai cấu trúc dừ liệu hồ trợ cho heuristic vòng lặp ngoài và heuristic vòng lặp trong. I: Ràng buộc toàn cục cùa khoảng cách xoắn thời gian động [50].2: Mô tá đường bao u và L của chuồi Q [72].3: Mô tả kỹ thuật cận dưới cúa Keogh [72].

176 xiii DANH MỤC BẢNG BIẺU Báng 1.1: Các đặc trưng cúa 4 hướng tiếp cận phát hiện bất thường.1: Mã giả cúa giải thuật chân phương Brute-Force [5].2: Báng tra tìm các giá trị p theo từng giá trị a tương ứng [76].1: Các ký hiệu khi sử dụng độ đo dựa vào vùng phân đoạn sz.2: Mô tả các tập dừ liệu thực nghiệm.3: Ma trận đúng sai cho kết quả phân đoạn của phương pháp PIP trong trường hợp Casel (a) và Casell (b).4: Giá trị các tiêu chí đánh giá phương pháp PIP ở cả 2 Trường hợp Casel và Casell trên tập dữ liệu thứ nhất.5: Tham số tốt nhất cho 3 phương pháp.6: Giá trị các tiêu chí đánh giá cho 3 phương pháp phân đoạn.1: Các tham sổ, chiều dài của chuồi con bất thường và kích thước khung PAA .2: Vị trí chuồi con bất thường do BFDD, HOT SAX và I-HOTSAX tìm được .3: số lần gọi hàm tính khoảng cách của Bruce Force, HOT SAX và I-HOTSAX .4: Thời gian thực thi của Brute-Force, HOT SAX và I-HOTSAX.5: Chiều dài cùa chuồi con bất thường và kích thước khung PAA.6: Vị trí chuồi con bất thường tìm được bởi Brute-Force, Hash_DD và HOT SAX.