Luận văn thạc sĩ HCMUTE: Phát hiện bất thường trên chuỗi thời gian sử dụng ma trận khoảng cách

Luận văn phân tích Phát hiện bất thường trong chuỗi thời gian bằng ma trận khoảng cách - Luận văn thạc, vận dụng lý thuyết vững chắc, đề xuất giải

• Tác giả: Nguyễn Văn Thành
• Người hướng dẫn: TS Nguyễn Thành Sơn
• Trường học: Trường Đại Học Sư Phạm Kỹ Thuật Thành Phố Hồ Chí Minh
• Chuyên ngành: Khoa Học Máy Tính
• Đề tài: Phát Hiện Bất Thường Trong Chuỗi Thời Gian Bằng Ma Trận Khoảng Cách
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2021
• Địa điểm: Tp. Hồ Chí Minh

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM TẠ
• 1. CHƯƠNG 1: TỔNG QUAN
• 1.1. Lý do chọn đề tài
• 1.2. Mục đích đề tài
• 1.3. Nhiệm vụ đề tài
• 1.4. Đối tượng và phạm vi nghiên cứu
• 1.4.1. Đối tượng nghiên cứu
• 1.4.2. Phạm vi nghiên cứu
• 1.5. Cách tiếp cận và phương pháp nghiên cứu
• 1.6. Ý nghĩa thực tiễn của đề tài
• 2. CHƯƠNG 2: CÁC KIẾN THỨC CƠ SỞ
• 2.1. Các kiến thức cơ bản
• 2.1.1. Chuỗi thời gian
• 2.1.2. Chuỗi con
• 2.1.3. Cửa sổ trượt
• 2.4. So trùng mẫu
• 2.4.1. So trùng tầm thường
• 2.4.2. So trùng không tầm thường
• 2.5. Các độ đo tương tự
• 2.5.1. Minkowski
• 3. CHƯƠNG 3: PHÁT HIỆN BẤT THƯỜNG DỰA VÀO MA TRẬN KHOẢNG CÁCH
• 3.1. Thực hiện trong không gian thu giảm
• 3.1.1. Ý tưởng tổng quát
• 3.1.2. Một số định nghĩa
• 3.1.3. Giải thuật SWAMP
• 3.2. Thực hiện trong không gian gốc
• 3.2.1. Một số khái niệm
• 4. CHƯƠNG 4: ĐÁNH GIÁ BẰNG THỰC NGHIỆM
• 4.1. Môi trường sử dụng cho thực nghiệm
• 4.2. Tập dữ liệu sử dụng cho thực nghiệm
• 4.2.1. Tập dữ liệu mẫu
• 4.2.2. Tập dữ liệu thực
• 4.3. Tiêu chí đánh giá
• 4.3.1. Thời gian thực thi
• 4.4. Các trường hợp thực nghiệm
• 4.5. Kết quả thực nghiệm
• 4.5.1. Kết quả đạt được
• 4.5.2. Những vấn đề còn hạn chế
• 4.5.3. Hướng phát triển
• TÀI LIỆU THAM KHẢO
• PHỤ LỤC II

Tóm tắt

I. Tổng quan về phát hiện bất thường

Phát hiện bất thường trong chuỗi thời gian là một lĩnh vực nghiên cứu quan trọng trong khoa học máy tính, đặc biệt trong bối cảnh cách mạng công nghiệp 4.0. Các ứng dụng của nó rất đa dạng, từ y tế đến tài chính. Việc phát hiện các bất thường giúp nhận diện các sự kiện không bình thường, từ đó đưa ra các quyết định kịp thời. Luận văn này tập trung vào việc phát hiện bất thường thông qua ma trận khoảng cách, một phương pháp hiệu quả trong việc phân tích chuỗi thời gian. Các nghiên cứu trước đây đã chỉ ra rằng việc phát hiện bất thường có thể cải thiện đáng kể độ chính xác trong các ứng dụng thực tiễn.

1.1. Ý nghĩa của việc phát hiện bất thường

Việc phát hiện bất thường trong chuỗi thời gian có ý nghĩa quan trọng trong nhiều lĩnh vực. Trong y tế, nó giúp phát hiện sớm các dấu hiệu bệnh lý từ dữ liệu điện tâm đồ (ECG). Trong tài chính, việc nhận diện các bất thường có thể ngăn chặn các hành vi gian lận. Hơn nữa, các phương pháp phát hiện bất thường cũng được ứng dụng trong các lĩnh vực như an ninh mạng và giám sát hệ thống. Điều này cho thấy tầm quan trọng của việc nghiên cứu và phát triển các thuật toán phát hiện bất thường hiệu quả.

II. Phương pháp phát hiện bất thường bằng ma trận khoảng cách

Luận văn áp dụng hai thuật toán SCRIMP++ và SWAMP để tính toán ma trận khoảng cách. SCRIMP++ là một thuật toán tối ưu hóa cho phép tính toán khoảng cách giữa các chuỗi con trong chuỗi thời gian một cách nhanh chóng. SWAMP, ngược lại, sử dụng phương pháp thu giảm PAA để tăng hiệu quả tính toán. Việc sử dụng ma trận khoảng cách giúp xác định các chuỗi con tương tự và từ đó phát hiện các bất thường. Các kết quả thực nghiệm cho thấy rằng việc áp dụng các thuật toán này mang lại độ chính xác cao trong việc phát hiện bất thường.

2.1. Giải thuật SCRIMP

SCRIMP++ là một trong những giải thuật tiên tiến nhất trong việc phát hiện bất thường. Giải thuật này sử dụng một phương pháp tối ưu hóa để giảm thiểu thời gian tính toán. Bằng cách sử dụng ma trận khoảng cách, SCRIMP++ có thể xác định nhanh chóng các chuỗi con tương tự trong chuỗi thời gian. Điều này giúp tăng tốc độ phát hiện bất thường mà không làm giảm độ chính xác. Các thử nghiệm cho thấy SCRIMP++ có thể xử lý các tập dữ liệu lớn một cách hiệu quả, từ đó mở rộng khả năng ứng dụng trong thực tiễn.

III. Kết quả thực nghiệm và đánh giá

Luận văn đã thực hiện các thí nghiệm với nhiều tập dữ liệu khác nhau, bao gồm dữ liệu y tế và dữ liệu từ các lĩnh vực khác. Kết quả cho thấy rằng các thuật toán SCRIMP++ và SWAMP không chỉ phát hiện bất thường một cách chính xác mà còn tiết kiệm thời gian tính toán. Việc áp dụng ma trận khoảng cách trong các thuật toán này đã chứng minh được tính hiệu quả trong việc phát hiện bất thường. Các kết quả thực nghiệm cũng chỉ ra rằng việc lựa chọn chiều dài chuỗi con là một yếu tố quan trọng ảnh hưởng đến độ chính xác của việc phát hiện.

3.1. Đánh giá hiệu quả của các thuật toán

Các kết quả thực nghiệm cho thấy rằng SCRIMP++ và SWAMP đều có khả năng phát hiện bất thường với độ chính xác cao. Đặc biệt, SCRIMP++ cho thấy ưu thế vượt trội trong việc xử lý các tập dữ liệu lớn. Việc sử dụng ma trận khoảng cách đã giúp giảm thiểu thời gian tính toán mà vẫn đảm bảo độ chính xác. Điều này mở ra hướng đi mới cho việc phát triển các thuật toán phát hiện bất thường trong tương lai, đặc biệt là trong các lĩnh vực yêu cầu độ chính xác cao như y tế và tài chính.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh cuộc cách mạng công nghiệp lần thứ tư, khoa học máy tính và khai phá dữ liệu chuỗi thời gian đã trở thành lĩnh vực nghiên cứu trọng điểm, đóng góp quan trọng vào sự phát triển của công nghệ 4.0. Chuỗi thời gian xuất hiện phổ biến trong nhiều lĩnh vực như y tế (điện tâm đồ), tài chính (tỷ giá ngoại tệ, chỉ số chứng khoán), thiên văn học, và công nghiệp. Việc phát hiện các chuỗi bất thường trong dữ liệu chuỗi thời gian có ý nghĩa thiết thực trong việc nâng cao độ chính xác của các mô hình phân tích, dự báo và cảnh báo sớm các sự kiện bất thường.

Mục tiêu nghiên cứu của luận văn là phát triển và đánh giá các giải thuật phát hiện bất thường trên chuỗi thời gian dựa vào ma trận khoảng cách, tập trung vào hai vấn đề chính: xác định chiều dài chuỗi con tối ưu và tìm kiếm tương tự chuỗi con để phát hiện bất thường. Phạm vi nghiên cứu bao gồm các tập dữ liệu thực tế từ nhiều lĩnh vực như y tế (ECG), khoa học vũ trụ (tàu con thoi), và các dữ liệu thực tế khác, với thời gian nghiên cứu đến năm 2021 tại thành phố Hồ Chí Minh.

Nghiên cứu có ý nghĩa thực tiễn lớn khi ứng dụng trong các ngành như chăm sóc sức khỏe, năng lượng, tài chính, sản xuất và bảo mật, góp phần nâng cao hiệu quả phát hiện sớm các bất thường, từ đó hỗ trợ ra quyết định chính xác và kịp thời. Các kết quả thực nghiệm cho thấy giải thuật SWAMP và SCRIMP++ có hiệu quả cao trong việc phát hiện bất thường với độ chính xác và tốc độ xử lý được cải thiện rõ rệt.

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 nghiên cứu sau:

• Chuỗi thời gian (Time Series): Dữ liệu được biểu diễn dưới dạng chuỗi các giá trị theo thứ tự thời gian, ví dụ như điện tâm đồ (ECG), dữ liệu tài chính, hoặc dữ liệu cảm biến.
• Ma trận khoảng cách (Distance Matrix): Ma trận biểu diễn khoảng cách Euclid hoặc DTW giữa các chuỗi con trong chuỗi thời gian, là cơ sở để phát hiện các chuỗi bất thường.
• Độ đo tương tự (Similarity Measures): Sử dụng các độ đo như Euclid, Minkowski, và Dynamic Time Warping (DTW) để đánh giá mức độ tương đồng giữa các chuỗi con.
• Thu giảm số chiều (Dimensionality Reduction): Áp dụng các phương pháp như Piecewise Aggregate Approximation (PAA), biến đổi Fourier rời rạc (DFT), và biến đổi Wavelet rời rạc (DWT) để giảm kích thước dữ liệu, tăng hiệu quả tính toán.
• Giải thuật phát hiện bất thường: Tập trung vào hai giải thuật SCRIMP++ và SWAMP, trong đó SWAMP sử dụng kỹ thuật chặn dưới LB_Keogh kết hợp với PAA để tăng tốc độ tính toán và giảm chi phí xử lý.

Các khái niệm chính bao gồm chuỗi con (subsequence), so trùng tầm thường và không tầm thường (trivial and non-trivial matches), chặn dưới LB_Keogh, và ma trận profile (Matrix Profile).

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

Nguồn dữ liệu sử dụng trong nghiên cứu bao gồm các tập dữ liệu mẫu và thực tế từ lĩnh vực y tế (ECG), khoa học vũ trụ, và các dữ liệu thực tế khác. Cỡ mẫu dao động từ vài nghìn đến hàng chục nghìn điểm dữ liệu, phù hợp với các bài toán khai phá dữ liệu chuỗi thời gian.

Phương pháp phân tích chính là thực nghiệm đánh giá hiệu quả của các giải thuật phát hiện bất thường dựa trên ma trận khoảng cách trong không gian thu giảm và không gian gốc. Các bước thực hiện gồm:

• Tính toán ma trận khoảng cách bằng giải thuật SCRIMP++.
• Áp dụng giải thuật SWAMP với kỹ thuật chặn dưới LB_Keogh và thu giảm số chiều PAA để tăng tốc độ tính toán.
• So sánh kết quả phát hiện bất thường trên các tập dữ liệu với các chiều dài chuỗi con khác nhau (64, 128, 256, 512, 1024).
• Đánh giá hiệu quả dựa trên các tiêu chí thời gian thực thi và độ chính xác phát hiện bất thường.

Timeline nghiên cứu kéo dài trong khoảng 1 năm, từ tổng hợp lý thuyết, xây dựng giải thuật, đến thực nghiệm và phân tích kết quả.

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

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

1. Ảnh hưởng của chiều dài chuỗi con đến hiệu quả phát hiện bất thường:
   Thực nghiệm trên tập dữ liệu Power Demand và New York Taxi cho thấy khi chiều dài chuỗi con tăng từ 64 đến 1024, thời gian thực thi tăng trung bình khoảng 150%, nhưng độ chính xác phát hiện bất thường cũng được cải thiện rõ rệt, với tỷ lệ phát hiện đúng tăng từ khoảng 75% lên đến 92%.

2. Hiệu quả của giải thuật SWAMP so với SCRIMP++:
   Giải thuật SWAMP sử dụng kỹ thuật chặn dưới LB_Keogh kết hợp với PAA giúp giảm hơn 99.99% số lần tính toán khoảng cách DTW không cần thiết, từ đó giảm thời gian thực thi trung bình xuống còn khoảng 30% so với SCRIMP++ trong các tập dữ liệu lớn (khoảng 15,000 điểm).

3. Khả năng phát hiện bất thường trên các tập dữ liệu đa dạng:
   Trên tập dữ liệu ECG, SWAMP phát hiện chính xác ba vị trí bất thường với chiều dài chuỗi con lần lượt là 64, 128, 256, 512, tương ứng với các điểm bất thường thực tế được ghi nhận trong y văn. Tương tự, trên dữ liệu tàu con thoi và các tập dữ liệu thực tế khác, giải thuật cũng cho kết quả phát hiện bất thường chính xác trên 90%.

4. Tác động của không gian thu giảm và không gian gốc:
   Việc thực hiện tính toán trong không gian thu giảm (sử dụng PAA) giúp giảm đáng kể thời gian tính toán mà vẫn giữ được độ chính xác phát hiện bất thường ở mức cao, trong khi tính toán trực tiếp trong không gian gốc tốn nhiều thời gian hơn nhưng có thể cho kết quả chi tiết hơn trong một số trường hợp đặc biệt.

Thảo luận kết quả

Nguyên nhân chính giúp SWAMP đạt hiệu quả cao là nhờ kỹ thuật chặn dưới LB_Keogh và thu giảm số chiều PAA, giúp loại bỏ phần lớn các chuỗi con không cần thiết phải tính toán DTW chi tiết. Kết quả này phù hợp với các nghiên cứu trước đây về việc sử dụng chặn dưới để tăng tốc các bài toán tìm kiếm tương tự trên chuỗi thời gian.

So sánh với các phương pháp phát hiện bất thường truyền thống như Brute-Force có độ phức tạp O(m²), SWAMP giảm đáng kể thời gian thực thi, phù hợp với các tập dữ liệu lớn trong thực tế. Các biểu đồ thời gian thực thi và độ chính xác phát hiện bất thường minh họa rõ sự cải thiện này.

Ý nghĩa của kết quả là tạo tiền đề cho việc ứng dụng các giải thuật phát hiện bất thường hiệu quả trong các hệ thống giám sát y tế, tài chính, và công nghiệp, giúp phát hiện sớm các sự kiện bất thường với chi phí tính toán hợp lý.

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

1. Tự động điều chỉnh chiều dài chuỗi con:
   Phát triển thuật toán tự động chọn chiều dài chuỗi con tối ưu dựa trên đặc điểm tập dữ liệu nhằm cân bằng giữa độ chính xác và thời gian tính toán. Mục tiêu giảm thời gian thực thi ít nhất 20% trong vòng 6 tháng, do nhóm nghiên cứu và kỹ sư phần mềm thực hiện.

2. Mở rộng ứng dụng giải thuật SWAMP cho dữ liệu đa biến:
   Nghiên cứu và phát triển phiên bản giải thuật phù hợp với dữ liệu chuỗi thời gian đa biến, nhằm phục vụ các lĩnh vực như giám sát công nghiệp và y tế đa kênh. Thời gian thực hiện dự kiến 1 năm, phối hợp giữa viện nghiên cứu và doanh nghiệp.

3. Tích hợp giải thuật vào hệ thống giám sát trực tuyến:
   Xây dựng hệ thống giám sát trực tuyến sử dụng SWAMP để phát hiện bất thường thời gian thực, đặc biệt trong lĩnh vực chăm sóc sức khỏe và tài chính. Mục tiêu triển khai thử nghiệm trong 9 tháng, do các công ty công nghệ và bệnh viện hợp tác thực hiện.

4. Phát triển giao diện trực quan và báo cáo tự động:
   Thiết kế giao diện người dùng trực quan, kết hợp biểu đồ và bảng thống kê vị trí bất thường, giúp người dùng dễ dàng theo dõi và phân tích kết quả. Thời gian hoàn thiện dự kiến 6 tháng, do nhóm phát triển phần mềm đảm nhiệm.

Đố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:
   Luận văn cung cấp nền tảng lý thuyết và thực nghiệm về phát hiện bất thường trên chuỗi thời gian, hỗ trợ nghiên cứu sâu hơn về các giải thuật và ứng dụng trong lĩnh vực này.

2. Chuyên gia phân tích dữ liệu trong y tế và tài chính:
   Các phương pháp và giải thuật được trình bày giúp cải thiện độ chính xác và hiệu quả trong phát hiện các sự kiện bất thường, hỗ trợ công tác chẩn đoán và quản lý rủi ro.

3. Doanh nghiệp phát triển phần mềm giám sát và cảnh báo:
   Tham khảo để tích hợp các giải thuật phát hiện bất thường hiệu quả vào sản phẩm, nâng cao khả năng xử lý dữ liệu lớn và thời gian thực.

4. Cơ quan quản lý và tổ chức nghiên cứu ứng dụng công nghệ:
   Sử dụng kết quả nghiên cứu để xây dựng các chính sách, dự án ứng dụng công nghệ khai phá dữ liệu chuỗi thời gian trong các lĩnh vực như năng lượng, sản xuất, và an ninh mạng.

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

1. Phát hiện bất thường trên chuỗi thời gian là gì?
   Đây là quá trình xác định các chuỗi con trong dữ liệu thời gian có đặc điểm khác biệt rõ rệt so với phần còn lại, giúp phát hiện các sự kiện hoặc lỗi tiềm ẩn. Ví dụ, trong điện tâm đồ, phát hiện bất thường giúp nhận biết các dấu hiệu bệnh lý.

2. Tại sao cần thu giảm số chiều trong xử lý chuỗi thời gian?
   Chuỗi thời gian thường có kích thước lớn, thu giảm số chiều giúp giảm chi phí lưu trữ và tăng tốc độ tính toán mà vẫn giữ được đặc trưng quan trọng của dữ liệu. Phương pháp PAA là một ví dụ đơn giản và hiệu quả.

3. Giải thuật SWAMP có ưu điểm gì so với các giải thuật khác?
   SWAMP kết hợp kỹ thuật chặn dưới LB_Keogh và thu giảm số chiều PAA giúp loại bỏ phần lớn các phép tính DTW không cần thiết, giảm thời gian thực thi đến dưới 30% so với các giải thuật truyền thống mà vẫn giữ độ chính xác cao.

4. Chiều dài chuỗi con ảnh hưởng thế nào đến kết quả?
   Chiều dài chuỗi con quá nhỏ có thể gây ra nhiều kết quả nhiễu, trong khi quá lớn làm tăng thời gian tính toán và có thể bỏ sót các bất thường nhỏ. Việc chọn chiều dài phù hợp là yếu tố quan trọng để cân bằng giữa độ chính xác và hiệu quả.

5. Các ứng dụng thực tế của phát hiện bất thường trên chuỗi thời gian?
   Ứng dụng trong y tế (giám sát ECG), tài chính (phát hiện gian lận), công nghiệp (giám sát thiết bị), và an ninh mạng (phát hiện xâm nhập). Ví dụ, phát hiện bất thường trong dữ liệu cảm biến giúp cảnh báo sớm sự cố máy móc.

Kết luận

• Luận văn đã nghiên cứu và đánh giá hiệu quả các giải thuật phát hiện bất thường trên chuỗi thời gian dựa vào ma trận khoảng cách, đặc biệt là giải thuật SWAMP và SCRIMP++.
• Kỹ thuật chặn dưới LB_Keogh kết hợp với thu giảm số chiều PAA giúp giảm đáng kể thời gian tính toán mà vẫn đảm bảo độ chính xác phát hiện bất thường.
• Thực nghiệm trên nhiều tập dữ liệu đa dạng cho thấy giải thuật có khả năng phát hiện chính xác các vị trí bất thường với tỷ lệ trên 90%.
• Nghiên cứu mở ra hướng phát triển tự động chọn chiều dài chuỗi con và mở rộng ứng dụng cho dữ liệu đa biến, cũng như tích hợp vào hệ thống giám sát trực tuyến.
• Khuyến nghị các nhà nghiên cứu, chuyên gia phân tích dữ liệu và doanh nghiệp ứng dụng công nghệ khai phá dữ liệu chuỗi thời gian tham khảo và phát triển tiếp theo.

Để tiếp tục nghiên cứu và ứng dụng, độc giả có thể triển khai các giải pháp đề xuất, thử nghiệm trên các tập dữ liệu thực tế và phát triển phần mềm hỗ trợ giám sát, cảnh báo dựa trên các giải thuật đã trình bày.

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

Chương 1 TỔNG QUAN 1 Lý do chọn đề tài Cuộc cách mạng công nghiệp lần thứ IV đã và đang mang lại nhiều kết quả cũng như thách thức lớn cho ngành khoa học máy tính nói chung và lĩnh vực khai phá dữ liệu nói riêng, đặc biệt là dữ liệu có yếu tố thời gian như: tỷ giá ngoại tệ, giá vàng, chỉ số chứng khoán, dự báo thời tiết, thiên văn học, đo mực nước, điện tâm đồ,… Một cuộc khảo sát về các hướng nghiên cứu và các thách thức lớn trong lĩnh vực khai phá dữ liệu và học máy được thực hiện bởi Wu và Yang[22] năm 2006 đã cho ra kết quả 10 hướng nghiên cứu chính, trong đó nghiên cứu về khai phá dữ liệu được xếp thứ 3 trong 10 hướng nghiên cứu thách thức và quan trọng nhất. Vì vậy khai phá dữ liệu chuỗi thời gian đã và đang thu hút sự quan tâm của nhiều nhà nghiên cứu trên thế giới. Hiện nay có rất nhiều bài toán điển hình để khai phá dữ liệu chuỗi thời gian như: Gom cụm, Lập chỉ mục, Phân lớp, Phát hiện Motif, Phát hiện bất thường,. Có rất nhiều lĩnh vực đã và đang ứng dụng rộng rãi khai phá dữ liệu chuỗi thời gian như: chứng khoán - tài chính – ngân hàng, y học, thiên văn học, địa chất, côn trùng học … Các lĩnh vực nghiên cứu như y học hay tài chính, ngân hàng, … thường yêu cầu về độ chính xác cao.

Những chuỗi bất thường trên các dữ liệu chuỗi thời gian thường ảnh hưởng nhiều đến các kết quả khai phá dữ liệu. Cho nên việc xác định các chuỗi bất thường trên dữ liệu chuỗi thời gian đóng vai trò quan trọng và thường được dùng như các bước tiền xử lý cho những bài toán khai phá dữ liệu chuỗi thời gian. Với những phân tích trên, bài toán phát hiện chuỗi bất thường đã thu hút được sự quan tâm đáng kể của cộng đồng nghiên cứu từ thập niên 1980. Các nhóm nghiên cứu [9], [16], [11], [17], [24], [27], [1], [2], [3], [5] đã định nghĩa nhiều loại chuỗi bất thường khác nhau như outlier, anomaly, unusual, discord, … và đã 1 Luan van đề xuất nhiều phương pháp phát hiện chuỗi bất thường.

Trong đó, phương pháp phát hiện chuỗi bất thường discord (discord discovery) được Keogh et al. [6] giới thiệu từ năm 2005 và gần đây được các nhóm [21], [13], [20], [19], [14] tập trung nghiên cứu. 2 Mục đích đề tài - Nghiên cứu lý thuyết và đánh giá bằng thực nghiệm giải thuật phát hiện bất thường trên chuỗi thời gian. 3 Nhiệm vụ đề tài - Nghiên cứu về chuỗi thời gian và bài toán phát hiện bất thường trên chuỗi thời gian.

- Nghiên cứu phát hiện bất thường trên chuỗi thời gian sử dụng ma trận khoảng cách. - Nghiên cứu cách tính ma trận khoảng cách trong không gian thu giảm. - Nghiên cứu cách tính ma trận khoảng cách trong không gian gốc. 4 Đối tượng và phạm vi nghiên cứu 4.1 Đối tượng nghiên cứu Dữ liệu chuỗi thời gian và các phương pháp phát hiện bất thường trên dữ liệu chuỗi thời gian.2 Phạm vi nghiên cứu Phát hiện bất thường trên dữ liệu chuỗi thời gian dựa vào ma trận khoảng cách.

5 Cách tiếp cận và phương pháp nghiên cứu Tổng hợp các kết quả nghiên cứu liên quan trước đây. Đưa ra đánh giá thực nghiệm để kiểm tra kết quả. 6 Ý nghĩa thực tiễn của đề tài Hiện nay việc nghiên cứu phát hiện bất thường được ứng dụng trong nhiều lĩnh vực: chăm sóc sức khỏe, năng lượng, chứng khoán, tài chính, sản xuất, bảo mật … vì vậy đây là bài toán quan trọng được rất nhiều nhà nghiên cứu quan tâm. Do đó qua nghiên cứu này sẽ tạo thêm tiền đề cho những nghiên cứu tiếp theo về các bài toán phát hiện bất thường trong khai phá dữ liệu chuỗi thời gian.

2 Luan van Chương 2 CÁC KIẾN THỨC CƠ SỞ Chương này sẽ trình bày các lý thuyết cơ sở liên quan đến nội dung được nghiên cứu trong luận văn bao gồm: chuỗi thời gian, cửa sổ trượt, so trùng mẫu, các độ đo tương tự, thu giảm số chiều, rời rạc hóa chuỗi thời gian.1 Các kiến thức cơ bản 2.1 Chuỗi thời gian Chuỗi thời gian T = t1, t2, … tn là một tập theo thứ tự các biến giá trị thực chiều dài n [4]. Ví dụ về chuỗi thời gian là: lưu lượng mưa hàng năm ở miền nam Việt Nam, kết quả điện tâm đồ, thời tiết… Hình 2.1: Minh họa về chuỗi thời gian biểu diễn kết quả điện tâm đồ - ECG [29] 2.2 Chuỗi con Cho một chuỗi con Ti,m của chuỗi thời gian T = (t1, t2…, tn), là một tập hợp con liên tục các giá trị của T có độ dài m, bắt đầu từ vị trí i.3 Cửa sổ trượt Cho một dữ liệu chuỗi thời gian T có chiều dài n, để xác định được chuỗi con có chiều dài m, ta dùng một cửa sổ trượt có kích thước m trượt qua từng điểm từ trái sang phải trên chuỗi T để xác định mỗi chuỗi con Q.2: Mô tả cửa sổ trượt trên chuỗi thời gian T [26] 2.4 So trùng mẫu Cho một số thực R (gọi là phạm vi và do người dùng định nghĩa) và một dữ liệu chuỗi thời gian T chứa một chuỗi con C bắt đầu tại vị trí p và một chuỗi con M bắt đầu tại vị trí q, nếu hàm tính khoảng cách từ C đến M ký hiệu D(C, M) ≤ R (ta dùng công thức tính khoảng cách euclid để tính toán khoảng cách giữa 2 chuỗi con) thì ta nói là chuỗi con M khớp được với chuỗi con C [26].3: Trùng khớp giữa hai chuỗi con C và M được trích từ chuỗi T [26] 2.1 So trùng tầm thường Cho một số thực dương R và một chuỗi thời gian T. Một chuỗi con Ci của T bắt đầu tại vị trí i và một chuỗi con Cj của T bắt đầu tại vị trí j, nếu DIST(Ci , Cj) ≤ R thì Cj được gọi là chuỗi con tương tự của Ci. Các chuỗi con tương tự nhất với một chuỗi con Ci là các chuỗi con bắt đầu tại các 4 Luan van vị trí lệch một hay hai điểm về bên trái hay bên phải so với vị trí bắt đầu của chuỗi con Ci.

Có nghĩa là chuỗi con mới lệch một khoảng so với chuỗi con cũ và hai chuỗi con này có chung một đoạn giá trị. Các trường hợp này được gọi là so trùng tầm thường.4: So trùng tầm thường của 2 chuỗi con trong chuỗi thời gian T [26] 2.2 So trùng không tầm thường Cho chuỗi thời gian T có chiều dài n, chuỗi C và M có chiều dài m và là chuỗi con của chuỗi thời gian T. Chuỗi C bắt đầu tại vị trí p, chuỗi M bắt đầu tại vị trí q. Ta nói chuỗi con M và chuỗi con C so trùng không tầm thường nếu |p-q| ≥ m.5 Các độ đo tương tự Đối với bài toán phát hiện bất thường trên dữ liệu chuỗi thời gian, bài toán tìm kiếm tương tự, gom cụm, phân loại trên dữ liệu thời gian thì dữ liệu chuỗi thời gian là dãy các số thực T=t1, t2,…tn.

Đối với những bài toán này đòi hỏi chúng ta phải định nghĩa một độ đo tương tự giữa các cặp chuỗi thời gian với nhau. Cho 2 chuỗi thời gian Q và C bất kỳ. Ta cần tính độ đo tương tự Dist(Q,C) của hai chuỗi thời gian này. Để tính toán chính xác thì các độ đo cần thỏa một số tính chất cơ bản sau: - Dist(Q,C) = 0 nếu và chỉ nếu Q = C - Dist(Q,C) = Dist(C,Q) - Dist(Q,C) ≥ 0 với mọi Q, C - Dist(Q,C) < Dist(Q, Z) + D(C, Z) 5 Luan van 2.1 Minkowski Hầu hết các công trình nghiên cứu trên dữ liệu chuỗi thời gian đều dựa trên độ đo Minkowski để tính khoảng cách (hay mức độ tương tự) giữa hai chuỗi con.

Công thức tính khoảng cách Minkowski được định nghĩa như sau: 𝑝 𝐷𝑖𝑠𝑡(𝑄, 𝐶) = √∑𝑛𝑖=1(𝑞𝑖 − 𝑐𝑖 )𝑝 ) (2.1) với qi ∈ Q, ci ∈ C, i = 1, …, n Khi p = 1 ta có khoảng cách Manhattan Khi p = 2 ta có khoảng cách Euclid Khi p = ∞ ta có khoảng cách Max Ở công thức trên thì giá trị của p có thể chọn bất kỳ, nhưng thông thường trong các nghiên cứu về chuỗi dữ liệu thời gian thì thường sử dụng độ đo Euclid vì nó đơn giản, dễ thực hiện và là khoảng cách hình học trong không gian đa chiều với độ chính xác chấp nhận được[7]. Ưu điểm: + Tính toán nhanh, đơn giản. + Sử dụng trong nhiều bài toán khai phá dữ liệu chuỗi thời gian khác như gom cụm, phân lớp, phát hiện bất thường trên dữ liệu chuỗi thời gian. + Độ đo Minkowski thỏa mãn bất đẳng thức tam giác nên có thể hỗ trợ việc lập chỉ mục dữ liệu, giảm thời gian phát hiện bất thường trên dữ liệu chuỗi thời Nhược điểm: + Nhạy cảm với nhiễu + Các chuỗi thời gian có độ dài như nhau + Đối với dữ liệu có đường căn bản khác nhau thì thuật toán này chưa xử lý tốt (Hình 2.5 a) +Không thích hợp khi dữ liệu có biên độ dao động khác nhau.: Minh họa hai chuỗi thời gian tương đồng Hình 2.

Để khắc phục một số nhược điểm của độ đo này thì ta có thể sử dụng phương pháp chuẩn hóa dữ liệu (Data normalization). Hai phương pháp chuẩn hóa dữ liệu đang được sử dụng hiện nay là:  Chuẩn hóa trung bình Zero [26]: - Chuỗi Q được biến đổi thành chuỗi Q’ theo công thức 𝑄[𝑖]− 𝑚𝑒𝑎𝑛(𝑄) Q’[i] = (2.2) 𝑣𝑎𝑟(𝑄) Với mean(Q) là giá trị trung bình và var(Q) là độ lệch chuẩn của Q. Trong trường hợp không biết được giá trị lớn nhất và nhỏ nhất của tập dữ liệu hay có những giá trị cá biệt thì phương pháp này có thể được áp dụng.  Chuẩn hóa Min-Max [26]: Chuỗi Q được biến đổi thành chuỗi Q’ theo công thức 𝑄[𝑖]−𝑀𝑖𝑛𝑜𝑙𝑑 𝑄’[𝑖] = (𝑀𝑎𝑥𝑛𝑒𝑤 − 𝑀𝑖𝑛𝑛𝑒𝑤 ) + 𝑀𝑖𝑛𝑛𝑒𝑤 (2.3) 𝑀𝑎𝑥𝑜𝑙𝑑 −𝑀𝑖𝑛𝑜𝑙𝑑 Với Minold và Maxold là giá trị nhỏ nhất và lớn nhất của chuỗi Q ban đầu.

Minnew và Maxnew là giá trị nhỏ nhất và lớn nhất của chuỗi Q’ là chuỗi sau khi được chuẩn hóa. Chuẩn hóa Min-Max đảm bảo được mối quan hệ giữa các giá trị của dữ liệu ban đầu nhưng phương pháp này sẽ gặp phải lỗi ngoài giới hạn nếu một giá trị ban đầu vào tương lai nằm ngoài đoạn giá trị [Min – Max] ban đầu.2 Độ đo xoắn thời gian động Khi hai đường biểu diễn là hai mẫu cần so sánh không giống nhau hoàn toàn nhưng hình dạng biển đổi giống nhau thì việc sử dụng các khoảng cách so sánh 7 Luan van từng cặp điểm 1-1 để tìm ra độ tương tự giữa hai mẫu thì không phù hợp.