Luận văn thạc sĩ về 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

Khám phá luận văn thạc sĩ về 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, ứng dụng trong phân tích dữ liệu.

• 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 Tp. Hồ Chí Minh
• Chuyên ngành: Khoa học máy tính, Khoa Công nghệ thông tin
• Đề tài: Phát hiện bất thường trên dữ liệu chuỗi thời gian bằng ma trận khoảng cách
• Loại tài liệu: Luận văn
• 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Ạ
• TÓM TẮT
• ABSTRACT
• MỤC LỤC
• DANH MỤC CÁC TỪ VIẾT TẮ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.1.4. So trùng mẫu
• 2.1.4.1. So trùng tầm thường
• 2.1.4.2. So trùng không tầm thường
• 2.1.5. Các độ đo tương tự
• 2.1.5.1. Minkowski
• 2.1.5.2. Độ đo xoắn thời gian động
• 2.1.6. Thu giảm số chiều chuỗi thời gian
• 2.2. Phát hiện bất thường trên dữ liệu chuỗi thời gian
• 2.2.1. Các khái niệm cơ bản
• 2.2.2. Giải thuật phát hiện bất thường theo Vét cạn
• 2.2.3. Tổng quan về một số phương pháp phát hiện bất thường tiêu biểu
• 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
• 6. KẾT QUẢ THỰC NGHIỆM
• 6.1. Các tập dữ liệu điện tâm đồ - ECG
• 6.2. Các tập dữ liệu khác
• DANH MỤC CÁC TỪ VIẾT TẮT
• DANH MỤC HÌNH ẢNH
• DANH MỤC BẢNG

Tóm tắt

I. Tổng quan về phát hiện bất thường trong chuỗi thời gian

Phát hiện bất thường trong chuỗi thời gian là một lĩnh vực quan trọng trong khoa học dữ liệu. Nó giúp nhận diện các mẫu không bình thường trong dữ liệu có yếu tố thời gian, từ đó hỗ trợ trong việc ra quyết định và phân tích. Các ứng dụng của nó rất đa dạng, từ y tế đến tài chính. Việc áp dụng các phương pháp như ma trận khoảng cách giúp cải thiện độ chính xác trong việc phát hiện các bất thường.

1.1. Khái niệm chuỗi thời gian và bất thường

Chuỗi thời gian là một dãy số liệu được thu thập theo thời gian. Bất thường trong chuỗi thời gian có thể là các giá trị ngoại lệ, không phù hợp với xu hướng chung. Việc phát hiện những bất thường này có thể giúp nhận diện các vấn đề tiềm ẩn trong dữ liệu.

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 có vai trò quan trọng trong nhiều lĩnh vực như y tế, tài chính và an ninh mạng. Nó giúp phát hiện sớm các vấn đề, từ đó có biện pháp xử lý kịp thời.

II. Thách thức trong phát hiện bất thường trên chuỗi thời gian

Mặc dù phát hiện bất thường mang lại nhiều lợi ích, nhưng cũng tồn tại nhiều thách thức. Một trong những thách thức lớn nhất là xác định chiều dài chuỗi con hợp lý để phát hiện bất thường. Ngoài ra, việc tìm kiếm tương tự trong dữ liệu cũng gặp khó khăn do kích thước lớn của dữ liệu chuỗi thời gian.

2.1. Vấn đề xác định chiều dài chuỗi con

Chiều dài chuỗi con ảnh hưởng lớn đến kết quả phát hiện bất thường. Việc chọn chiều dài không hợp lý có thể dẫn đến việc bỏ sót các bất thường quan trọng hoặc phát hiện sai.

2.2. Khó khăn trong tìm kiếm tương tự

Tìm kiếm tương tự trong chuỗi thời gian lớn là một thách thức lớn. Các thuật toán cần phải tối ưu hóa để giảm thiểu thời gian tính toán mà vẫn đảm bảo độ chính xác.

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

Ma trận khoảng cách là một công cụ mạnh mẽ trong việc phát hiện bất thường. Nó cho phép tính toán khoảng cách giữa các chuỗi con trong dữ liệu chuỗi thời gian, từ đó xác định các bất thường. Các thuật toán như SCRIMP++ và SWAMP được sử dụng để tối ưu hóa quá trình này.

3.1. Giới thiệu về ma trận khoảng cách

Ma trận khoảng cách là một cấu trúc dữ liệu cho phép lưu trữ khoảng cách giữa các chuỗi con. Nó giúp dễ dàng so sánh và phát hiện các bất thường trong dữ liệu.

3.2. Các thuật toán SCRIMP và SWAMP

SCRIMP++ và SWAMP là hai thuật toán nổi bật trong việc tính toán ma trận khoảng cách. Chúng giúp giảm thiểu thời gian tính toán và tăng độ chính xác trong việc phát hiện bất thường.

IV. Ứng dụng thực tiễn của phát hiện bất thường trong chuỗi thời gian

Phát hiện bất thường trong chuỗi thời gian đã được áp dụng rộng rãi trong nhiều lĩnh vực. Từ y tế, nơi phát hiện các bất thường trong điện tâm đồ, đến tài chính, nơi phát hiện gian lận trong giao dịch. Các kết quả nghiên cứu cho thấy tính hiệu quả của các phương pháp hiện tại.

4.1. Ứng dụng trong y tế

Trong y tế, phát hiện bất thường giúp nhận diện sớm các vấn đề sức khỏe. Ví dụ, phân tích điện tâm đồ để phát hiện các bất thường trong nhịp tim.

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. Các thuật toán phát hiện bất thường có thể giúp bảo vệ tài sản và giảm thiểu rủi ro.

V. Kết luận và tương lai của phát hiện bất thường trong chuỗi thời gian

Phát hiện bất thường trong chuỗi thời gian là một lĩnh vực đ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 hơn. Tương lai của lĩnh vực này hứa hẹn sẽ mang lại nhiều ứng dụng thực tiễn hơn nữa.

5.1. Xu hướng phát triển trong nghiên cứu

Nghiên cứu trong lĩnh vực phát hiện bất thường sẽ tiếp tục phát triển, với sự chú trọng vào việc cải thiện độ chính xác và giảm thiểu thời gian tính toán.

5.2. Tương lai của ứng dụng trong các lĩnh vực khác nhau

Các ứng dụng của phát hiện bất thường sẽ mở rộng ra nhiều lĩnh vực khác nhau, từ an ninh mạng đến quản lý rủi ro trong kinh doanh.

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 đề 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 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 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 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 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.