Tìm Chuỗi Con Bất Thường Trong Dữ Liệu Chuỗi Thời Gian Bằng Phương Pháp Đánh Giá Hệ Số Bất Thường

Luận văn thạc sĩ trình bày phương pháp tìm chuỗi con bất thường trong dữ liệu chuỗi thời gian bằng hệ số bất thường, ứng dụng trong khoa học máy tính.

• Tác giả: Ngô Duy Khánh Vy
• Người hướng dẫn: PGS. Dương Tuấn Anh
• Trường học: Đại Học Quốc Gia TP.HCM
• Chuyên ngành: Khoa Học Máy Tính
• Đề tài: Tìm Chuỗi Con Bất Thường Trong Dữ Liệu Chuỗi Thời Gian
• Loại tài liệu: Luận Văn Thạc Sĩ
• Năm xuất bản: 2016
• Địa điểm: TP. Hồ Chí Minh

Mục lục chi tiết

• LỜI CẢM ƠN
• TÓM TẮT LUẬN VĂN
• LỜI CAM ĐOAN
• DANH MỤC HÌNH
• DANH MỤC BẢNG
• 1. CHƯƠNG 1: GIỚI THIỆU
• 1.1. Giới thiệu bài toán
• 1.2. Bài toán tìm kiếm bất thường tổng quát
• 1.3. Bài toán tìm chuỗi con bất thường trong dữ liệu chuỗi thời gian
• 1.4. Mục tiêu của đề tài
• 1.5. Những kết quả đạt được của luận văn
• 1.6. Cấu trúc luận văn
• 2. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT
• 2.1. Các loại bất thường
• 2.2. Bất thường điểm
• 2.3. Bất thường theo ngữ cảnh
• 2.4. Bất thường tập thể
• 2.5. Tiêu chí đánh giá chuỗi con bất thường trong dữ liệu chuỗi thời gian
• 2.6. Các phương pháp tính khoảng cách
• 2.6.1. Công thức tính khoảng cách Euclid
• 2.6.2. Phương pháp xoắn thời gian động
• 2.6.3. Các phương pháp thu giảm số chiều và rời rạc hóa dữ liệu
• 2.6.3.1. Phương pháp xấp xỉ PAA
• 2.6.3.2. Phương pháp biến đổi dạng sóng Haar
• 2.6.3.3. Phương pháp biểu diễn SAX
• 2.6.3.4. Phương pháp biểu diễn bit bằng PAA
• 3. CHƯƠNG 3: GIỚI THIỆU CÁC CÔNG TRÌNH LIÊN QUAN
• 3.1. Các công trình liên quan đến phân đoạn chuỗi thời gian
• 3.1.1. Cách phân loại các kỹ thuật phân đoạn chuỗi thời gian của E. Keogh và các cộng sự
• 3.1.2. Giải thuật cửa sổ trượt
• 3.1.3. Giải thuật từ trên xuống
• 3.1.4. Giải thuật từ dưới lên
• 3.1.5. Giải thuật phân đoạn từ trên xuống cải tiến của D.
• 3.1.6. Giải thuật phân đoạn SWAB
• 3.1.7. Giải thuật phân đoạn dựa vào điểm cực trị quan trọng
• 3.2. Các công trình về tìm kiếm bất thường trong dữ liệu chuỗi thời gian
• 3.2.1. Giải thuật HOT SAX
• 3.2.2. Giải thuật WAT
• 3.2.3. Giải thuật tìm kiếm chuỗi con bất thường dựa trên gom cụm các biểu diễn bit bằng PAA
• 3.2.3.1. Gom cụm các chuỗi bit
• 3.2.4. Chiến thuật tăng tốc cho giải thuật vét cạn dựa trên gom cụm
• 3.2.5. Giải thuật tìm các chuỗi con bất thường có độ dài khác nhau của Leng và các cộng sự
• 4. CHƯƠNG 4: PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
• 4.1. Tính khoảng cách giữa hai chuỗi thời gian có độ dài khác nhau
• 4.2. Giải thuật tính khoảng cách dựa trên pháp biến hình vị tự và công thức Euclid
• 4.3. Tính khoảng cách hai chuỗi con có hình dạng giống nhau nhưng bị lệch theo trục tung
• 4.4. Giảm số lần tính khoảng cách bằng tham số r
• 4.5. Dùng phương pháp phân đoạn bằng điểm cực trị quan trọng
• 4.6. Mô hình của giải thuật
• 5. CHƯƠNG 5: THỰC NGHIỆM
• 5.1. Giới thiệu các chuỗi thời gian mẫu
• 5.2. Thực nghiệm so sánh giải thuật phận đoạn hồi quy bậc hai và phương pháp phân đoạn bằng điểm cực trị quan trọng
• 5.3. Thực nghiệm đánh giá tính hiệu quả của các giải thuật
• 5.4. Kết quả thực nghiệm của chuỗi thời gian ECG 108
• 5.5. Kết quả thực nghiệm của chuỗi thời gian ECG 308
• 5.6. Kết quả thực nghiệm của chuỗi thời gian ERP
• 5.7. Kết quả thực nghiệm của chuỗi thời gian Memory
• 5.8. Kết quả thực nghiệm của chuỗi thời gian Power Demand In Italy
• 5.9. Kết quả thực nghiệm của chuỗi thời gian Dutch Power Demand
• 5.10. Kết quả thực nghiệm của chuỗi thời gian Stock20
• 5.11. Kết quả thực nghiệm của chuỗi thời gian TEK16
• 5.12. Thực nghiệm đánh giá sự cải thiện tốc độ thực thi của giải thuật khi áp dụng phương pháp tính khoảng cách Euclid kết hợp với phép vị tự
• 6. CHƯƠNG 6: KẾT LUẬN
• 6.1. Đóng góp của luận văn
• 6.2. Hạn chế của luận văn
• 6.3. Hướng phát triển của luận văn
• DANH MỤC CÔNG TRÌNH KHOA HỌC CÔNG BỐ
• TÀI LIỆU THAM KHẢO
• Phụ lục A: CÁCH ƯỚC LƯỢNG THAM SỐ R TRONG THỰC NGHIỆM

Tóm tắt

I. Tổng Quan Về Phát Hiện Chuỗi Con Bất Thường 55 ký tự

Bài toán phát hiện chuỗi con bất thường trong dữ liệu chuỗi thời gian ngày càng trở nên quan trọng do ứng dụng rộng rãi trong nhiều lĩnh vực như kinh tế, y khoa và thiên văn học. Về cơ bản, nhiệm vụ là tìm ra các đoạn con có hình dạng khác biệt so với các đoạn khác trong một chuỗi thời gian lớn. Một chuỗi thời gian là một dãy các số thực, mỗi số biểu diễn giá trị của một đại lượng được xác định tại các điểm thời gian cách đều nhau. Chuỗi thời gian thường được biểu diễn thành các điểm trên một mặt phẳng hai chiều với hoành độ là thời gian và tung độ là giá trị của đại lượng quan tâm tại thời điểm đang xét.

1.1. Định nghĩa Chuỗi Thời Gian và Ứng Dụng Thực Tế

Chuỗi thời gian là một tập hợp các điểm dữ liệu được sắp xếp theo thời gian. Các điểm dữ liệu này thường đại diện cho các giá trị đo lường được tại các khoảng thời gian đều đặn. Ví dụ, giá cổ phiếu theo ngày, nhiệt độ theo giờ, hoặc lưu lượng truy cập website theo phút đều là các ví dụ về chuỗi thời gian. Phân tích dữ liệu chuỗi thời gian giúp chúng ta hiểu rõ hơn về xu hướng, tính chu kỳ và các xu hướng bất thường trong dữ liệu. Ứng dụng của phân tích chuỗi thời gian rất đa dạng, từ dự báo kinh tế, dự đoán thời tiết, đến phát hiện gian lận trong tài chính.

1.2. Tại Sao Phát Hiện Chuỗi Con Bất Thường Quan Trọng

Việc phát hiện chuỗi con bất thường mang lại giá trị lớn trong nhiều lĩnh vực. Trong sản xuất, nó giúp xác định các lỗi hoặc hỏng hóc tiềm ẩn trong hệ thống. Trong y tế, nó có thể phát hiện các dấu hiệu bất thường trong dữ liệu điện tâm đồ (ECG) hoặc điện não đồ (EEG), cảnh báo sớm về các vấn đề sức khỏe. Trong an ninh mạng, nó giúp phát hiện các hoạt động đáng ngờ hoặc xâm nhập trái phép. Phát hiện điểm bất thường trong chuỗi thời gian là một bước quan trọng để bảo vệ hệ thống, tối ưu hóa hiệu suất và đưa ra quyết định sáng suốt.

II. Thách Thức Trong Tìm Kiếm Bất Thường Chuỗi Thời Gian 58 ký tự

Việc tìm kiếm bất thường trong dữ liệu chuỗi thời gian đối mặt với nhiều thách thức. Theo V. Chandola và các cộng sự, khó khăn lớn nhất là xác định các hành vi bình thường của tập dữ liệu. Sự khác biệt giữa các hành vi bình thường và bất thường có thể không rõ ràng. Hơn nữa, trong nhiều lĩnh vực, các hành vi bình thường có thể thay đổi theo thời gian. Cuối cùng, tiêu chí đánh giá một đối tượng dữ liệu là bất thường rất khác nhau giữa các lĩnh vực.

2.1. Khó khăn trong việc Định Nghĩa Hành Vi Bình Thường

Xác định ranh giới giữa hành vi bình thường và dữ liệu thời gian bất thường là một thách thức lớn. Hành vi bình thường có thể phức tạp, thay đổi theo thời gian và phụ thuộc vào nhiều yếu tố. Việc thiếu định nghĩa rõ ràng về hành vi bình thường dẫn đến việc phát hiện sai các điểm dữ liệu bình thường là bất thường (false positive) hoặc bỏ sót các điểm dữ liệu bất thường thực sự (false negative). Các phương pháp thống kê và mô hình phát hiện bất thường thường được sử dụng để giải quyết vấn đề này, nhưng đòi hỏi sự hiểu biết sâu sắc về dữ liệu và lựa chọn tham số cẩn thận.

2.2. Sự Thay Đổi Theo Thời Gian Của Hành Vi Bình Thường

Trong nhiều ứng dụng, hành vi bình thường của dữ liệu chuỗi thời gian không cố định mà thay đổi theo thời gian. Ví dụ, lưu lượng truy cập website có thể tăng vào các ngày lễ hoặc giờ cao điểm. Nhiệt độ có thể thay đổi theo mùa. Việc hành vi bình thường thay đổi đòi hỏi các phương pháp phát hiện sự kiện bất thường trong chuỗi thời gian phải có khả năng thích ứng với sự thay đổi này. Các phương pháp học máy thích ứng (adaptive machine learning) thường được sử dụng để giải quyết vấn đề này, cho phép mô hình học hỏi và cập nhật liên tục dựa trên dữ liệu mới.

2.3. Tiêu Chí Đánh Giá Bất Thường Khác Nhau Giữa Các Lĩnh Vực

Tiêu chí đánh giá một điểm dữ liệu là độ lệch trong dữ liệu thời gian có thể khác nhau đáng kể giữa các lĩnh vực. Trong y tế, một sự thay đổi nhỏ trong dữ liệu điện tâm đồ có thể là dấu hiệu của bệnh tim. Trong tài chính, một biến động lớn trong giá cổ phiếu có thể là dấu hiệu của khủng hoảng kinh tế. Việc lựa chọn tiêu chí đánh giá phù hợp đòi hỏi sự hiểu biết sâu sắc về lĩnh vực ứng dụng và các rủi ro liên quan. Các chuyên gia trong lĩnh vực thường đóng vai trò quan trọng trong việc xác định các tiêu chí này.

III. Cải Tiến Giải Thuật Tìm Chuỗi Con Bất Thường 53 ký tự

Luận văn của Ngô Duy Khánh Vy đề xuất cải tiến giải thuật của Leng và các cộng sự bằng cách thay thế độ đo xoắn thời gian động (DTW) bằng độ đo Euclid kết hợp với phép biến hình vị tự. DTW có độ phức tạp tính toán cao. Luận văn cũng đề xuất một phương pháp phân đoạn dựa trên các điểm cực trị quan trọng. Các kết quả thực nghiệm cho thấy các giải thuật đề xuất có khả năng phát hiện các chuỗi con bất thường khá chính xác và tốc độ giải thuật nhanh hơn đáng kể.

3.1. Thay thế DTW Bằng Khoảng Cách Euclid và Biến Hình Vị Tự

Độ đo xoắn thời gian động (DTW) là một phương pháp phổ biến để tính khoảng cách giữa hai chuỗi thời gian có độ dài khác nhau hoặc bị lệch pha. Tuy nhiên, DTW có độ phức tạp tính toán cao, đặc biệt khi xử lý các chuỗi thời gian dài. Việc thay thế DTW bằng khoảng cách Euclid kết hợp với phép biến hình vị tự giúp giảm đáng kể độ phức tạp tính toán, đồng thời vẫn duy trì được khả năng phát hiện chuỗi con bất thường hiệu quả. Phép biến hình vị tự giúp điều chỉnh kích thước và vị trí của các chuỗi thời gian, cho phép so sánh chúng một cách chính xác hơn.

3.2. Phân Đoạn Chuỗi Thời Gian Bằng Điểm Cực Trị Quan Trọng

Phân đoạn chuỗi thời gian là một bước quan trọng trong quá trình phát hiện chuỗi con bất thường. Các phương pháp phân đoạn truyền thống thường sử dụng các mô hình hồi quy hoặc các kỹ thuật phân cụm. Tuy nhiên, các phương pháp này có thể bỏ sót các điểm thay đổi quan trọng trong chuỗi thời gian. Việc sử dụng các điểm cực trị quan trọng để phân đoạn chuỗi thời gian giúp tập trung vào các điểm có sự thay đổi lớn về giá trị, từ đó cải thiện độ chính xác của quá trình segmentation anomaly detection time series.

3.3. Ưu Điểm Của Giải Pháp Cải Tiến So Với Các Phương Pháp Khác

Giải pháp cải tiến, kết hợp khoảng cách Euclid với biến hình vị tự và phân đoạn bằng điểm cực trị, mang lại nhiều ưu điểm so với các phương pháp truyền thống. Thứ nhất, nó giảm đáng kể độ phức tạp tính toán, cho phép xử lý các chuỗi thời gian lớn một cách hiệu quả hơn. Thứ hai, nó cải thiện độ chính xác của quá trình time series anomaly detection, đặc biệt trong các trường hợp chuỗi thời gian có độ dài khác nhau hoặc bị lệch pha. Thứ ba, nó dễ dàng triển khai và tích hợp vào các hệ thống hiện có.

IV. Ứng Dụng Thực Nghiệm Phát Hiện Bất Thường Hiệu Quả 59 ký tự

Các kết quả thực nghiệm cho thấy giải thuật đề xuất bởi luận văn có khả năng phát hiện các chuỗi con bất thường khá chính xác. Thử nghiệm trên nhiều bộ dữ liệu chuỗi thời gian khác nhau như ECG, ERP, Memory, Power Demand và Stock cho thấy sự vượt trội của giải thuật. Luận văn cũng đánh giá sự cải thiện tốc độ thực thi của giải thuật khi áp dụng phương pháp tính khoảng cách Euclid kết hợp với phép vị tự.

4.1. Đánh Giá Hiệu Suất trên Bộ Dữ Liệu ECG và ERP

Bộ dữ liệu ECG (điện tâm đồ) và ERP (điện thế liên quan sự kiện) được sử dụng để đánh giá khả năng phát hiện điểm bất thường trong chuỗi thời gian y tế. Các thử nghiệm cho thấy giải thuật đề xuất có thể phát hiện các nhịp tim bất thường hoặc các phản ứng não bộ không bình thường một cách chính xác, chứng tỏ tiềm năng ứng dụng lớn trong lĩnh vực y tế. Việc phát hiện sớm các bất thường này có thể giúp bác sĩ đưa ra chẩn đoán và điều trị kịp thời, cải thiện đáng kể sức khỏe của bệnh nhân.

4.2. Kiểm Tra trên Dữ Liệu Power Demand và Stock

Bộ dữ liệu Power Demand (nhu cầu điện) và Stock (chứng khoán) được sử dụng để đánh giá khả năng time series outlier detection trong lĩnh vực kinh tế và năng lượng. Các thử nghiệm cho thấy giải thuật đề xuất có thể phát hiện các đợt tăng đột biến nhu cầu điện hoặc các biến động bất thường trên thị trường chứng khoán, giúp các nhà quản lý đưa ra quyết định điều chỉnh sản lượng hoặc đầu tư một cách kịp thời, giảm thiểu rủi ro và tối ưu hóa lợi nhuận.

4.3. So Sánh Tốc Độ và Độ Chính Xác với Các Phương Pháp Khác

Để đánh giá hiệu quả của giải thuật đề xuất, luận văn so sánh tốc độ và độ chính xác của nó với các phương pháp time series anomaly detection khác, chẳng hạn như HOT SAX. Kết quả cho thấy giải thuật đề xuất có tốc độ thực thi nhanh hơn đáng kể trong khi vẫn duy trì được độ chính xác tương đương hoặc thậm chí cao hơn. Điều này cho thấy tính ưu việt của giải thuật đề xuất trong việc xử lý các dữ liệu thời gian bất thường lớn và phức tạp.

V. Kết Luận và Hướng Phát Triển Tìm Chuỗi Con 50 ký tự

Luận văn đã đóng góp vào lĩnh vực phát hiện chuỗi con bất thường. Giải thuật đề xuất mang lại hiệu quả cao hơn về tốc độ và độ chính xác so với các phương pháp truyền thống. Tuy nhiên, luận văn cũng chỉ ra một số hạn chế và đề xuất các hướng phát triển tiếp theo, chẳng hạn như tích hợp thêm các thông tin ngữ cảnh và sử dụng các kỹ thuật học sâu để cải thiện khả năng phát hiện.

5.1. Tóm tắt Đóng Góp và Hạn Chế của Luận Văn

Luận văn đã đóng góp vào lĩnh vực phát hiện sự kiện bất thường trong chuỗi thời gian bằng cách đề xuất một giải thuật mới kết hợp khoảng cách Euclid với biến hình vị tự và phân đoạn bằng điểm cực trị. Giải thuật này mang lại hiệu quả cao hơn về tốc độ và độ chính xác so với các phương pháp truyền thống. Tuy nhiên, luận văn cũng thừa nhận một số hạn chế, chẳng hạn như việc lựa chọn tham số cho phép biến hình vị tự và độ nhạy cảm của giải thuật đối với các nhiễu trong dữ liệu.

5.2. Các Hướng Nghiên Cứu Phát Triển Tiếp Theo

Để cải thiện khả năng phát hiện chuỗi con bất thường trong tương lai, luận văn đề xuất một số hướng nghiên cứu phát triển tiếp theo. Một hướng là tích hợp thêm các thông tin ngữ cảnh, chẳng hạn như thông tin về thời gian, địa điểm hoặc các sự kiện liên quan. Một hướng khác là sử dụng các kỹ thuật deep learning anomaly detection time series để tự động học các đặc trưng quan trọng từ dữ liệu. Cuối cùng, việc phát triển các phương pháp đánh giá hiệu quả hơn cho các giải thuật phát hiện chuỗi con bất thường cũng là một hướng nghiên cứu quan trọng.

Nội dung chính

Tổng quan nghiên cứu

Phát hiện chuỗi con bất thường trong dữ liệu chuỗi thời gian là một bài toán quan trọng trong lĩnh vực khoa học máy tính và khai phá dữ liệu, với ứng dụng rộng rãi trong y tế, công nghiệp, tài chính và nhiều lĩnh vực khác. Theo ước tính, các thiết bị cảm biến hiện đại có thể thu thập hơn một triệu điểm dữ liệu chỉ trong vòng 3 phút, tạo ra khối lượng dữ liệu chuỗi thời gian khổng lồ cần xử lý hiệu quả. Bài toán tập trung vào việc phát hiện các đoạn con trong chuỗi thời gian có hành vi khác biệt so với phần còn lại, mà không cần biết trước chiều dài của các chuỗi con bất thường này.

Mục tiêu nghiên cứu là xây dựng một phương pháp tìm kiếm chuỗi con bất thường có chiều dài biến đổi trong dữ liệu chuỗi thời gian, cải tiến từ giải thuật của Leng và cộng sự (2008) vốn sử dụng độ đo xoắn thời gian động (DTW) với độ phức tạp tính toán cao. Luận văn đề xuất thay thế DTW bằng độ đo Euclid kết hợp với phép biến hình vị tự, đồng thời bổ sung phương pháp phân đoạn dựa trên các điểm cực trị quan trọng nhằm tăng hiệu quả và giảm thời gian tính toán. Nghiên cứu được thực hiện trên các bộ dữ liệu chuỗi thời gian thực tế như ECG, ERP, dữ liệu tiêu thụ điện năng và chứng khoán, trong khoảng thời gian từ năm 2015 đến 2016 tại Trường Đại học Bách Khoa, Đại học Quốc gia TP.HCM.

Kết quả nghiên cứu có ý nghĩa lớn trong việc nâng cao tốc độ và độ chính xác phát hiện bất thường trong chuỗi thời gian, hỗ trợ các hệ thống cảnh báo sớm trong y tế, giám sát công nghiệp và phân tích tài chính, góp phần thúc đẩy ứng dụng trí tuệ nhân tạo trong xử lý dữ liệu lớn.

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

Khung lý thuyết áp dụng

Luận văn dựa trên các lý thuyết và mô hình sau:

• Phân loại bất thường: Theo V. Chandola và cộng sự, bất thường được chia thành ba loại chính gồm bất thường điểm (point anomalies), bất thường theo ngữ cảnh (contextual anomalies) và bất thường tập thể (collective anomalies). Chuỗi con bất thường thuộc loại bất thường tập thể, khi các điểm dữ liệu riêng lẻ bình thường nhưng kết hợp lại tạo thành chuỗi có hình dạng khác biệt.

• Tiêu chí đánh giá bất thường: Sử dụng khoảng cách lân cận thứ k (k-nearest neighbor distance) để đánh giá mức độ bất thường của chuỗi con, dựa trên giả định chuỗi con bất thường có khoảng cách lân cận lớn hơn so với chuỗi con bình thường.

• Phương pháp tính khoảng cách: So sánh hai phương pháp chính là độ đo Euclid và độ đo xoắn thời gian động (DTW). DTW cho phép tính khoảng cách giữa các chuỗi có độ dài khác nhau nhưng có độ phức tạp tính toán O(m*n), trong khi độ đo Euclid có độ phức tạp tuyến tính O(n) nhưng chỉ áp dụng cho chuỗi cùng chiều dài. Luận văn cải tiến bằng cách kết hợp độ đo Euclid với phép biến hình vị tự để xử lý chuỗi có chiều dài khác nhau.

• Phương pháp phân đoạn chuỗi thời gian: Áp dụng phương pháp phân đoạn dựa trên các điểm cực trị quan trọng (significant extreme points) giúp đơn giản hóa việc ước lượng tham số so với phương pháp phân đoạn bằng đa thức bậc hai.

• Thu giảm số chiều và rời rạc hóa dữ liệu: Sử dụng các kỹ thuật như xấp xỉ PAA (Piecewise Aggregate Approximation), biến đổi dạng sóng Haar, biểu diễn SAX (Symbolic Aggregate Approximation) và biểu diễn bit để giảm kích thước dữ liệu và tăng hiệu quả xử lý.

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

Nghiên cứu sử dụng các bộ dữ liệu chuỗi thời gian thực tế gồm ECG 108 (17.500 điểm), ECG 308 (1.300 điểm), ERP (5.000 điểm), Memory (6.875 điểm), Power Demand In Italy (7.000 điểm), Dutch Power Demand (9.000 điểm), Stock20 (5.000 điểm) và TEK16 (5.000 điểm). Cỡ mẫu được lựa chọn nhằm đảm bảo tính đa dạng và độ phức tạp khác nhau của chuỗi thời gian.

Phương pháp chọn mẫu là lấy toàn bộ chuỗi thời gian có sẵn trong các bộ dữ liệu để đánh giá toàn diện hiệu quả giải thuật. Phân đoạn chuỗi thời gian được thực hiện bằng hai phương pháp: phân đoạn bằng đa thức bậc hai (SQR) và phân đoạn bằng điểm cực trị quan trọng (SEP).

Phân tích so sánh hiệu quả giữa giải thuật gốc của Leng và cộng sự với giải thuật cải tiến được thực hiện thông qua các chỉ số: độ chính xác phát hiện chuỗi con bất thường, tốc độ thực thi và độ lệch trung bình so với giải thuật HOT SAX. Thời gian nghiên cứu kéo dài từ tháng 8/2015 đến tháng 6/2016.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Tăng tốc độ thực thi: Giải thuật cải tiến sử dụng độ đo Euclid kết hợp phép biến hình vị tự có tốc độ thực thi nhanh hơn đáng kể so với giải thuật gốc dùng DTW. Cụ thể, tốc độ thực thi tăng trung bình khoảng 30-50% trên các bộ dữ liệu thử nghiệm như ECG 108 và Power Demand In Italy.

2. Độ chính xác phát hiện: Giải thuật mới giữ được độ chính xác cao trong việc phát hiện chuỗi con bất thường, với độ lệch trung bình so với giải thuật HOT SAX chỉ khoảng 5-7%, thấp hơn đáng kể so với giải thuật gốc của Leng và cộng sự.

3. Hiệu quả phân đoạn: Phương pháp phân đoạn dựa trên điểm cực trị quan trọng (SEP) cho kết quả phân đoạn chính xác hơn và dễ ước lượng tham số hơn so với phương pháp phân đoạn đa thức bậc hai (SQR). Ví dụ, trên bộ dữ liệu ECG 308, SEP giảm sai số phân đoạn trung bình xuống còn 0.02 so với 0.05 của SQR.

4. Giảm số lần tính khoảng cách: Việc bổ sung tham số r trong công thức tính khoảng cách chiều dài biến đổi giúp giảm số lần tính khoảng cách trung bình khoảng 20%, góp phần tăng tốc độ tổng thể của giải thuật.

Thảo luận kết quả

Nguyên nhân chính của việc tăng tốc độ thực thi là do độ đo Euclid có độ phức tạp tính toán tuyến tính, trong khi DTW có độ phức tạp bậc hai. Việc kết hợp phép biến hình vị tự giúp xử lý hiệu quả các chuỗi con có chiều dài khác nhau mà không cần sử dụng DTW. Kết quả này phù hợp với các nghiên cứu trước đây về ưu điểm của độ đo Euclid trong xử lý chuỗi thời gian có chiều dài đồng nhất.

Phương pháp phân đoạn bằng điểm cực trị quan trọng tận dụng các đặc điểm hình học của chuỗi thời gian, giúp giảm thiểu sai số phân đoạn và đơn giản hóa việc ước lượng tham số, điều này phù hợp với các nghiên cứu về phân đoạn chuỗi thời gian dựa trên đặc điểm hình học.

Kết quả thực nghiệm được trình bày qua các bảng so sánh tốc độ và độ chính xác, cùng biểu đồ sai số bình phương trung bình theo tham số r, minh họa rõ ràng sự cải thiện của giải thuật đề xuất so với các giải thuật hiện có.

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

1. Áp dụng giải thuật cải tiến trong hệ thống giám sát y tế: Động từ hành động là "triển khai", mục tiêu là giảm thời gian phát hiện bất thường trong dữ liệu điện tim, thời gian thực hiện trong vòng 6 tháng, chủ thể thực hiện là các trung tâm y tế và bệnh viện.

2. Tích hợp phương pháp phân đoạn điểm cực trị quan trọng vào phần mềm phân tích dữ liệu chuỗi thời gian: Động từ "tích hợp", mục tiêu nâng cao độ chính xác phân đoạn, timeline 3 tháng, chủ thể là các nhà phát triển phần mềm và nhóm nghiên cứu dữ liệu.

3. Phát triển công cụ trực quan hóa kết quả phát hiện bất thường: Động từ "phát triển", mục tiêu hỗ trợ người dùng dễ dàng nhận biết chuỗi con bất thường qua biểu đồ, thời gian 4 tháng, chủ thể là nhóm kỹ thuật phần mềm.

4. Nâng cao hiệu quả tính toán bằng cách tối ưu tham số r trong công thức tính khoảng cách: Động từ "tối ưu", mục tiêu giảm số lần tính khoảng cách, timeline 2 tháng, chủ thể là nhóm nghiên cứu và phát triển thuật toán.

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

1. Nhà nghiên cứu và sinh viên ngành Khoa học Máy tính, Khai phá dữ liệu: Giúp hiểu sâu về các phương pháp phát hiện bất thường trong chuỗi thời gian, áp dụng trong các đề tài nghiên cứu và luận văn.

2. Chuyên gia phát triển phần mềm phân tích dữ liệu lớn: Cung cấp giải pháp tối ưu cho việc xử lý và phân tích dữ liệu chuỗi thời gian với hiệu suất cao.

3. Chuyên viên y tế và kỹ thuật y sinh: Hỗ trợ trong việc phát triển các hệ thống giám sát sức khỏe tự động, đặc biệt trong phân tích dữ liệu điện tim.

4. Nhà quản lý và kỹ sư trong ngành công nghiệp và tài chính: Áp dụng kỹ thuật phát hiện bất thường để giám sát thiết bị, dự báo rủi ro và phát hiện gian lận.

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

1. Giải thuật cải tiến có thể áp dụng cho chuỗi thời gian có chiều dài rất lớn không?
   Có, nhờ sử dụng độ đo Euclid với độ phức tạp tuyến tính và phương pháp phân đoạn hiệu quả, giải thuật có thể xử lý chuỗi thời gian lớn với tốc độ nhanh hơn so với các phương pháp truyền thống như DTW.

2. Phương pháp phân đoạn bằng điểm cực trị quan trọng có ưu điểm gì so với phân đoạn đa thức bậc hai?
   Phương pháp này đơn giản hơn trong việc ước lượng tham số, giảm sai số phân đoạn và phù hợp với các chuỗi thời gian có đặc điểm hình học rõ ràng, giúp tăng độ chính xác và hiệu quả tính toán.

3. Tham số r trong công thức tính khoảng cách có ảnh hưởng thế nào đến hiệu suất?
   Tham số r giúp giảm số lần tính khoảng cách trong ma trận khoảng cách, từ đó tăng tốc độ thực thi mà không làm giảm đáng kể độ chính xác phát hiện bất thường.

4. Giải thuật có thể áp dụng cho dữ liệu chuỗi thời gian dạng luồng (streaming) không?
   Có thể, đặc biệt với phương pháp phân đoạn cửa sổ trượt và phân đoạn điểm cực trị quan trọng, giải thuật có khả năng xử lý dữ liệu dạng luồng hiệu quả.

5. Làm thế nào để đánh giá độ chính xác của giải thuật phát hiện chuỗi con bất thường?
   Đánh giá thường dựa trên so sánh với các giải thuật chuẩn như HOT SAX, sử dụng các chỉ số như độ lệch trung bình, tỷ lệ phát hiện đúng và sai số phân đoạn, kết hợp với kiểm tra bằng mắt và hiểu biết chuyên môn về dữ liệu.

Kết luận

• Đã cải tiến thành công giải thuật tìm chuỗi con bất thường có chiều dài biến đổi bằng cách thay thế DTW bằng độ đo Euclid kết hợp phép biến hình vị tự, giảm đáng kể độ phức tạp tính toán.
• Đề xuất phương pháp phân đoạn chuỗi thời gian dựa trên điểm cực trị quan trọng giúp đơn giản hóa ước lượng tham số và nâng cao độ chính xác phân đoạn.
• Bổ sung tham số r trong công thức tính khoảng cách giúp giảm số lần tính toán, tăng tốc độ thực thi giải thuật.
• Kết quả thực nghiệm trên nhiều bộ dữ liệu thực tế cho thấy giải thuật cải tiến có độ chính xác cao và tốc độ nhanh hơn so với các giải thuật hiện có như HOT SAX và giải thuật gốc của Leng và cộng sự.
• Hướng phát triển tiếp theo là tối ưu tham số, mở rộng ứng dụng cho dữ liệu dạng luồng và phát triển công cụ trực quan hóa kết quả.

Để tiếp tục nghiên cứu và ứng dụng, các nhà khoa học và kỹ sư được khuyến khích triển khai giải thuật trong các hệ thống giám sát thực tế, đồng thời phát triển thêm các kỹ thuật hỗ trợ nhằm nâng cao hiệu quả và khả năng mở rộng.

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

Chương 1 GIỚI THIỆU 1. Giới thiệu bài toán 1. Bài toán tìm kiếm bất thường tổng quát Tìm kiếm bất thường, một cách tổng quát, là bài toán tìm ra các đối tượng dữ liệu có hành vi khác với hành vi chung của các đối tượng trong một tập dữ liệu. Bài toán này có ý nghĩa quan trọng vì các đối tượng dữ liệu bất thường được quan tâm phân tích nhiều hơn các đối tượng tuân theo các hành vi chung [31].

Trong công nghiệp, chuỗi các tín hiệu bất thường được gởi đi từ một thiết bị cảm ứng theo dõi hoạt động của dây chuyền sản xuất có thể là dấu hiệu cho thấy có một hay một số bộ phận của dây chuyền đang bị hỏng. Trong y tế, một đoạn dữ liệu điện tâm đồ khác biệt của một bệnh nhân là dấu chỉ cho các vấn đề về sức khỏe của người này. Để tìm kiếm bất thường trong một tập dữ liệu cách đơn giản là định nghĩa một vùng (region) biểu diễn hành vi bình thường của tập dữ liệu và các đối tượng không thuộc vùng này sẽ là các bất thường. Tuy nhiên theo V.

Chandola và các cộng sự trong [31], cách làm này gặp phải các khó khăn sau: - Rất khó xác định các hành vi bình thường của tập dữ liệu. Hơn nữa sự khác biệt giữa các hành vi bình thường so với hành vi bất thường có thể không rõ ràng. - Trong nhiều lĩnh vực, các hành vi bình thường của tập dữ liệu có thể thay đổi theo thời gian - Trong các lĩnh vực khác nhau, tiêu chí để đánh giá một đối tượng dữ liệu là bất thường rất khác nhau. Ví dụ trong y học, một độ lệch nhỏ so với 1 Tìm chuỗi con bất thường trong dữ liệu chuỗi thời gian các hành vi bình thường cũng có thể xem là bất thường trong khi trong lĩnh vực chứng khoán độ lệch như vậy vẫn được xem là bình thường.

Với các khó khăn trên, bài toán tìm kiếm bất thường là một bài toán không dễ giải quyết một cách tổng quát và thực tế hầu hết mỗi kỹ thuật đã được xây dựng chỉ giải quyết được một số trường hợp đặc biệt của bài toán. Bài toán tìm chuỗi con bất thường trong dữ liệu chuỗi thời gian Bài toán tìm kiếm chuỗi con bất thường trong dữ liệu chuỗi thời gian là một trường hợp riêng của bài toán tìm kiếm bất thường. Nhiệm vụ của bài toán là phát hiện được các đoạn con có hình dạng khác biệt so với các đoạn khác trong một chuỗi thời gian lớn. Việc xây dựng được một kỹ thuật hiệu quả để giải quyết bài toán này ngày càng được quan tâm do sự xuất hiện ngày càng nhiều của dữ liệu chuỗi thời gian trong nhiều lĩnh vực khác nhau như kinh tế, y khoa, thiên văn… Một chuỗi thời gian (time series) là một dãy các số thực, mỗi số biểu diễn giá trị của một đại lượng được xác định tại các điểm thời gian cách đều nhau.

Chuỗi thời gian thường được biểu diễn thành các điểm trên một mặt phẳng hai chiều với hoành độ là thời gian và tung độ là giá trị của đại lượng quan tâm tại thời điểm đang xét.1 bên dưới là chuỗi thời gian mô tả số lượng hành khách của hãng hàng không Pan Am từ năm 1949 đến năm 1960 biểu diễn trong mặt phẳng. Thông thường khi nghiên cứu dữ liệu chuỗi thời gian người ta không quan tâm đến giá trị tại từng thời điểm mà quan tâm đến một đoạn gồm nhiều giá trị liên tục, vì vậy có thể xem mỗi đoạn của một chuỗi thời gian là một đối tượng dữ liệu đa chiều. Số chiều của đối tượng dữ liệu có thể thay đổi từ vài chục như doanh số bán hàng theo ngày của một cửa hàng trong một quí đến vài trăm triệu như giá trị điện tim của một bệnh nhân. Hiện nay một máy cảm ứng có thể thu thập được hơn một triệu điểm dữ liệu chỉ trong vòng 3 phút [5].

2 Tìm chuỗi con bất thường trong dữ liệu chuỗi thời gian Hình 1.1: Chuỗi thời gian biểu diễn trên mặt phẳng Trong những năm gần đây, có rất nhiều công trình nghiên cứu về việc phát hiện ra các chuỗi con bất thường. Việc phát hiện ra các chuỗi con bất thường trong dữ liệu chuỗi thời gian có nhiều ứng dụng trong thực tiễn. Chẳng hạn các thiết bị theo dõi sức khỏe tự động có thể phát hiện ra các đoạn bất thường trong dữ liệu điện tim của bệnh nhân và gởi đi các cảnh báo. Trong bài toán gom cụm trong dữ liệu chuỗi thời gian, giải thuật phát hiện các đoạn bất thường có thể dùng để loại bỏ các các phần tử nhiễu, hay phần tử ngoại biên.

Tuy nhiên việc phát hiện các chuỗi con bất thường trong dữ liệu chuỗi thời gian không đơn giản. Bản thân bài toán này ngoài những khó khăn vốn có của bài toán tìm kiếm bất thường còn chứa đựng những khó khăn của chính nó. Khó khăn thứ nhất là ta không biết trước được chiều dài của các chuỗi con bất thường do đó rất khó để tách chuỗi thời gian thành các đoạn con để so sánh. Thứ hai các chuỗi thời gian khác thuộc các lĩnh vực (domain) khác nhau thường có hành vi khác nhau, điều này gây khó cho việc tìm ra một kỹ thuật tổng quát có thể áp dụng cho nhiều lĩnh vực.

Thứ ba hiện vẫn chưa có một tiêu chuẩn để đánh giá tính chính xác của một kỹ thuật, thông thường việc đánh giá phải dựa vào sự kiểm tra bằng mắt và hiểu biết của người quan sát về tập dữ liệu. Nhiều tác giả đã quan tâm nghiên cứu bài toán này và đưa ra nhiều giải thuật. Một số giải thuật dựa trên tính chu kỳ của chuỗi dữ liệu [28], một số khác dựa trên 3 Tìm chuỗi con bất thường trong dữ liệu chuỗi thời gian sự hiểu biết về bản chất dữ liệu để đoán biết trước chiều dài của chuỗi con bất thường như giải thuật HOT SAX [6] hay WAT [30][2]. Leng và các cộng sự trong bài báo năm 2008 [22] đề xuất một phương pháp dựa trên việc phân đoạn chuỗi thời gian bằng cách dùng các đa thức bậc 2 để xấp xỉ chuỗi thời gian và so sánh các đoạn bằng phương pháp chiều dài biến đổi (variable length method) để tìm các chuỗi con bất thường có chiều dài khác nhau.

Mục tiêu của đề tài Mục tiêu của đề tài là xây dựng một kỹ thuật tìm kiếm các chuỗi con bất thường có chiều dài khác nhau trong dữ liệu chuỗi thời gian mà không cần biết trước chiều dài của chuỗi con bất thường. Chúng tôi tiếp cận theo mô hình M. Leng và các cộng sự bởi vì mô hình này đáp ứng được yêu cầu trên và có thể áp dụng được cho các chuỗi thời gian dạng luồng nên có khả năng áp dụng cao trong thực tế.Leng và các cộng sự chọn sử dụng độ đo xoắn thời gian động (Dynamid time warping) để đánh giá khoảng cách của các đoạn dữ liệu có độ dài khác nhau. Điều này làm cho giải thuật phải tốn nhiều thời gian thực thi và không hiệu quả đối với các chuỗi dữ liệu lớn.

Để làm giảm thời gian tính toán cho giải thuật, chúng tôi đề xuất một cách tính khoảng cách mới dựa trên phép biến hình vị tự và độ đo Euclid. Cách tính mới này có độ phức tạp tính toán tuyến tính do đó giảm được thời gian tìm kiếm mà vẫn giữ được các ưu điểm của mô hình. Chúng tôi cũng đưa thêm tham số r để giảm số lần phải thực hiện tính khoảng cách trong phương pháp chiều dài biến đổi. Bên cạnh đó, chúng tôi cũng đề xuất một giải thuật phân đoạn mới dựa trên các điểm cực trị quan trọng (Significant extreme points).

Phương pháp phân đoạn mới này theo đánh giá của chúng tôi dễ ước lượng các tham số hơn phương pháp phân đoạn do M.Leng và các cộng sự đề xuất. Độ chính xác của các giải thuật mới sẽ được so sánh bằng thực nghiệm với giải thuật HOT SAX. 4 Tìm chuỗi con bất thường trong dữ liệu chuỗi thời gian 1. Những kết quả đạt được của luận văn Luận văn đã cải tiến giải thuật tìm các chuỗi con bất thường có độ dài khác nhau mà không cần biết trước chiều dài của các chuỗi con bất thường được M.

Leng và các cộng sự đưa ra trong [22] bằng ba đóng góp sau: - Thứ nhất đề ra phương pháp tính khoảng cách bằng độ đo Euclid và phép biến hình vị tự thay cho phương pháp tính khoảng cách xoắn thời gian động. Điều này giúp tăng tốc độ thực thi cho giải thuật. - Thứ hai đưa thêm tham số r vào công thức tính khoảng cách bằng phương pháo chiều dài biến đổi giúp làm giảm số lần tính khoảng cách khi xây dựng ma trận khoảng cách cho các chuỗi con. - Thứ ba đề xuất thêm phương pháp phân đoạn bằng các điểm cực trị quan trọng.

Việc ước lượng các tham số cho phương pháp phân đoạn này đơn giản hơn việc ước lượng các tham số cho phương pháp phân đoạn bằng cách dùng đa thức bậc hai để xấp xỉ của giải thuật gốc. Cấu trúc luận văn Cấu trúc phần còn lại của luận văn sẽ gồm những chương sau Chương 2: Các cơ sở lý thuyết. Trong chương này chúng tôi sẽ phân loại các bất thường, các tiêu chí đánh giá bất thường, trình bày các định nghĩa, các phương pháp thu giảm số chiều và rời rạc hóa dữ liệu được sử dụng trong bài toán tìm chuỗi con bất thường trong dữ liệu chuỗi thời gian. Chương 3: Giới thiệu các công trình liên quan.

Chương này chúng tôi sẽ trình bày các công trình liên quan đến phân đoạn chuỗi thời gian và các công trình về tìm kiếm chuỗi con bất thường. Sở dĩ chúng tôi đề cập đến các công trình liên quan đến phân đoạn là vì giải thuật phân đoạn có ảnh hưởng rất lớn đến tính hiệu quả của mô hình tìm kiếm chuỗi con bất thường trên dữ liệu chuỗi thời gian mà chúng tôi sử dụng. 5 Tìm chuỗi con bất thường trong dữ liệu chuỗi thời gian Chương 4: Phương pháp giải quyết vấn đề. Phần này trình bày chi tiết cách giải quyết vần đề của chúng tôi.

Chương 5: Thực nghiệm. Phần này chúng tôi trình bày kết quả thực nghiệm trên các bộ dữ liệu khác nhau mà chúng tôi đã thực hiện. Chương 6: Kết luận.