Tài liệu Phát hiện bất thường trên chuỗi thời gian dựa vào mạng nơ ron học sâu lstm

ĐẠI HỌC QUỐC GIA TP.HCM TRƯỜNG ĐẠI HỌC BÁCH KHOA ———————————– TRẦN LONG HOÀI PHÁT HIỆN BẤT THƯỜNG TRÊN CHUỖI THỜI GIAN DỰA VÀO MẠNG NƠ-RON HỌC SÂU LSTM Chuyên ngành: Khoa Học Máy Tính Mã số: 8.48.01.01 LUẬN VĂN THẠC SĨ TP. HỒ CHÍ MINH, tháng 8 năm 2021 CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐHQG-HCM Cán bộ hướng dẫn khoa học : PGS.TS Dương Tuấn Anh Cán bộ chấm nhận xét 1 : PGS.TS Nguyễn Thanh Hiên Cán bộ chấm nhận xét 2 : TS. Lê Văn Quốc Anh Luận văn thạc sĩ được bảo vệ tại Trường Đại học Bách Khoa, ĐHQG Tp. HCM ngày 5 tháng 8 năm 2021 (Trực tuyến). Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm: (Ghi rõ họ, tên, học hàm, học vị của Hội đồng chấm bảo vệ luận văn thạc sĩ) 1. Chủ Tịch: PGS.TS Huỳnh Tường Nguyên 2. Thư Ký: TS. Nguyễn Tiến Thịnh 3. Phản Biện 1: TS. Lê Văn Quốc Anh 4. Phản Biện 2: PGS.TS. Nguyễn Thanh Hiên 5. Ủy Viên: PGS.TS. Dương Tuấn Anh Xác nhận của Chủ tịch Hội đồng đánh giá LV và Trưởng Khoa quản lý chuyên ngành sau khi luận văn đã được sửa chữa (nếu có). CHỦ TỊCH HỘI ĐỒNG TRƯỞNG KHOA KHOA HỌC VÀ KỸ THUẬT MÁY TÍNH ĐẠI HỌC QUỐC GIA TP.HCM CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM TRƯỜNG ĐẠI HỌC BÁCH KHOA Độc lập - Tự Do - Hạnh Phúc NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ và tên học viên: Trần Long Hoài MSHV: 1970122 Ngày, tháng năm sinh: 26/04/1993 Nơi sinh: Hà Tĩnh Ngành: Khoa học Máy Tính Mã số: 8.48.01.01 I. TÊN ĐỀ TÀI: Phát hiện bất thường trên chuỗi thời gian dựa vào mạng nơ-ron học sâu LSTM NHIỆM VỤ VÀ NỘI DUNG : - Tìm hiểu bài toán phát hiện bất thường trên dữ liệu chuỗi thời gian. - Tìm hiều về mạng nơ-ron học sâu LSTM. - Ứng dụng mạng nơ-ron học sâu LSTM để phát hiện bất thường trên dữ liệu chuỗi thời gian. - Hiện thực và thử nghiệm chương trình dùng mạng nơ-ron để phát hiện bất thường trên chuỗi thời gian. - So sánh hiệu quả của mạng nơ-ron học sâu LSTM và giải thuật HOT SAX trong phát hiện bất thường trên chuỗi thời gian. II. NGÀY GIAO NHIỆM VỤ: 20/01/2021 III. NGÀY HOÀN THÀNH NHIỆM VỤ: 20/06/2021 IV. CÁN BỘ HƯỚNG DẪN: PGS.TS. Dương Tuấn Anh Tp. HCM, ngày ........ tháng ......... năm 2021 CÁN BỘ HƯỚNG DẪN CHỦ NHIỆM BỘ MÔN ĐÀO TẠO (Họ tên và chữ ký) (Họ tên và chữ ký) TRƯỞNG KHOA KHOA HỌC VÀ KỸ THUẬT MÁY TÍNH (Họ tên và chữ ký) Lời cảm ơn Lời đầu tiên, tôi muốn gửi lời cảm ơn chân thành đến thầy PGS.TS Dương Tuấn Anh, trong thời gian qua, đã hướng dẫn và giúp đỡ tôi trong quá trình thực hiện luận văn tốt nghiệp. Những lời nhận xét, góp ý và hướng dẫn của Thầy đã giúp tôi có hướng đi đúng trong quá trình thực hiện đề tài, giúp chúng tôi thấy được những thuận lợi và hạn chế của các phương pháp tiếp cận khác nhau và từng bước khắc phục để ngày một tốt hơn. Đồng thời tôi cũng muốn gửi lời cảm ơn sâu sắc đến gia đình và bạn bè đã động viên, cổ vũ tinh thần và góp ý trong suốt quá trình học tập và thực hiện đề tài, đặc biệt là gia đình đã chăm lo và hy sinh rất nhiều để tôi có thể chuyên tâm học tập. Sau cùng, tôi xin kính chúc quý Thầy Cô trong khoa Khoa Học và Kĩ Thuật Máy Tính thật dồi dào sức khỏe, niềm tin để tiếp tục thực hiện sứ mệnh cao đẹp của mình là truyền đạt kiến thức cho thế hệ mai sau. Thành phố Hồ Chí Minh, 06/2021 Trần Long Hoài i Tóm tắt Bài toán phát hiện bất thường bằng phương pháp dự báo là bài toán toán được nhiều nhà nghiên cứu trong cộng đồng phát hiện bất thường quan tâm. Bởi vì đây là một cách tiếp cận mới, tận dụng được sự bùng nổ của các mạng nơ-ron học sâu. Phương pháp này gồm hai công tác chính là dự báo dữ liệu và phát hiện bất thường. Các bộ dữ liệu dùng để phát hiện bất thường là các bộ dữ liệu được các nhà nghiên cứu sử dụng nhiều trong công tác phát hiện bất thường, các bộ dữ liệu này là một chuỗi thời gian, có tương quan với nhau. Để có thể dự báo chính xác với dữ liệu chuỗi thời gian có tương quan với nhau, nghiên cứu này đề xuất mô hình sử dụng mạng nơ-ron học sâu LSTM xếp chồng. Ngoài ra để nâng cao khả năng dự báo, chúng tôi cũng áp dụng kỹ thuật dự báo nhiều bước cho mô hình đề xuất. Sai số dự báo sẽ được sử dụng cho công tác phát hiện bất thường. Để đánh giá mô hình, chúng tôi so sánh với giải thuật HOTSAX về kết quả phát hiện bất thường và thời gian thực thi. Kết quả thực nghiệm trên 07 bộ dữ liệu cho thấy mô hình đề xuất của chúng tôi đã khắc phục được hạn chế của việc dựa vào kích thước cửa sổ trượt trong giải thuật HOTSAX, đồng thời cũng khẳng định tiềm năng của phương pháp phát hiện bất thường bằng dự báo. ii Abstract Anomaly detection algorithm with prediction-based technique is the problem in which many researchers in anomaly detection community have been interested. Because this is a new approach, taking advantage of the explosion of deep learning neural networks. This method consists of two main tasks: data prediction and anomaly detection. The data sets used for anomaly detection are the data sets that are widely used by researchers in anomaly detection, these data sets are time series, which are correlated with each other. To be able to accurately predict with correlated time series data, this thesis proposes a model using a stacked LSTM network. In addition to improving the forecasting ability, we also apply multi-step-ahead prediction for this model. Forecast error may be used for anomaly detection. To evaluate the model, we make a comparison with the HOTSAX algorithm on the anomaly detection results and execution time. Experimental results on 07 data sets show that our proposed model has overcome the limitation when relying on sliding window size in the HOTSAX algorithm, and also confirms the potential of anomaly detection algorithm with prediction-based technique. iii Lời cam đoan Tôi là Trần Long Hoài học viên cao học khoa Khoa Học và Kĩ Thuật Máy Tính, Đại học Bách Khoa TP. HCM, MSHV 1970122. Tôi xin cam đoan rằng luận văn thạc sĩ "Phát Hiện Bất Thường Trên Chuỗi Thời gian Dựa Vào Mạng Nơ-Ron Học Sâu LSTM" là kết quả tìm hiểu, nghiên cứu độc lập của chính bản thân. Tôi xin cam đoan: 1. Luận văn được thực hiện cho mục đích tìm hiểu và nghiên cứu ở bậc cao học 2. Các công trình, bài báo tham khảo để xây dựng nên luận văn này đều được trích dẫn, tham khảo. Tất cả các tài liệu được trích dẫn và có tính kế thừa từ các tạp chí và các công trình nghiên cứu đã được công bố 3. Những công cụ, phần mềm cho quá trình thực hiện luận văn đều là phần mềm mã nguồn mở 4. Hình ảnh và số liệu được trích dẫn nguồn tham khảo rõ ràng 5. Kết quả nghiên cứu được trình bày trung thực dựa trên số liệu thực tế khi chạy chương trình TP. Hồ Chí Minh, Ngày ..... Tháng ..... Năm 2021. Học viên Trần Long Hoài iv Mục lục 1 Giới thiệu đề tài 1.1 Đặt vấn đề . . . . . . . 1.2 Mục tiêu nghiên cứu . 1.3 Ý nghĩa đề tài . . . . . 1.4 Kết quả đạt được . . . 1.5 Cấu trúc của luận văn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Cơ sở lý thuyết 2.1 Chuỗi thời gian và dự báo chuỗi thời gian . . . . . . . . . . . . . . 2.2 Chuỗi con và chuỗi con bất thường . . . . . . . . . . . . . . . . . 2.2.1 Chuỗi con . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 Chuỗi con bất thường . . . . . . . . . . . . . . . . . . . . 2.3 Phương pháp xấp xỉ gộp từng đoạn . . . . . . . . . . . . . . . . . 2.4 Phương pháp xấp xỉ gộp ký hiệu hóa . . . . . . . . . . . . . . . . 2.5 Mạng nơ-ron nhân tạo (Artiticial Neural Networks - ANN) . . . . 2.6 Mạng nơ-ron hồi quy (Recurrent Neural Network – RNN) . . . . . 2.6.1 Kiến trúc và cách thức hoạt động . . . . . . . . . . . . . . 2.6.2 Vấn đề của RNN . . . . . . . . . . . . . . . . . . . . . . . 2.7 Mạng nơ-ron học sâu Long Short-Term Memory (LSTM) . . . . . 2.8 Mạng nơ-ron học sâu LSTM xếp chồng (Stacked LSTM Network) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 6 7 7 8 . . . . . . . . . . . . 9 9 11 11 11 12 12 14 18 18 19 20 22 3 Những nghiên cứu liên quan 3.1 Dự báo nhiều bước trong dữ liệu chuỗi thời gian (multi-step ahead predictions) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Chiến lược hồi quy (Recursive Strategy) . . . . . . . . . . . . . 3.1.2 Chiến lược trực tiếp (Direct Strategy) . . . . . . . . . . . . . . . 3.1.3 Kết hợp chiến lược hồi quy và chiến lược trực tiếp (DirREC Strategy) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.4 Chiến lược nhiều đầu vào – nhiều đầu ra (MIMO Strategy) . . . 3.1.5 Kết hợp chiến lược trực tiếp và chiến lược nhiều đầu vào - nhiều đầu ra (DirMO Strategy) . . . . . . . . . . . . . . . . . . . . . . 3.2 Giải thuật HOT SAX . . . . . . . . . . . . . . . . . . . . . . . . . . . . v 24 24 25 25 26 27 28 29 MỤC LỤC 3.3 3.4 3.5 3.6 3.7 3.8 3.9 Mạng LSTM xếp chồng trong phát hiện chuỗi con bất thường . . . . . Kết hợp mạng nơ-ron học sâu và mô hình xác suất truyền thống . . . . Dự báo dữ liệu và chỉnh sửa bất thường dựa trên mạng LSTM . . . . . Phát hiện bất thường bằng LSTM và so sánh dự báo với giải thuật AMIRA Phát hiện bất thường bằng LSTM sử dụng Kernel Quantile Estimator . Khảo sát về các kỹ thuật phát hiện bất thường sử dụng mạng LSTM . 3.8.1 Phân loại bất thường . . . . . . . . . . . . . . . . . . . . . . . . 3.8.2 Phát hiện bất thường sử dụng mạng LSTM . . . . . . . . . . . Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Phương pháp giải quyết vấn đề 4.1 Các bộ dữ liệu . . . . . . . . . . . . . . . . . 4.1.1 Bộ dữ liệu điện tâm đồ ECG . . . . . 4.1.2 Bộ dữ liệu nhiệt độ máy Numenta . . 4.1.3 Bộ dữ liệu power_demand . . . . . . 4.1.4 Bộ dữ liệu TEK16 . . . . . . . . . . 4.1.5 Bộ dữ liệu chứng khoán stock_20_0 4.1.6 Bộ dữ liệu memory . . . . . . . . . . 4.1.7 Bộ dữ liệu ann_gun_CentroidA . . . 4.2 Đề xuất mô hình . . . . . . . . . . . . . . . 4.3 Phương pháp phát hiện bất thường . . . . . 4.3.1 Dự báo dữ liệu . . . . . . . . . . . . 4.3.2 Phát hiện bất thường . . . . . . . . . 4.3.3 Các giả định . . . . . . . . . . . . . . 4.3.4 Các bước của giải thuật . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Kết quả thực nghiệm 5.1 Tiêu chí đánh giá . . . . . . . . . . . . . . . . . . . 5.2 Thực nghiệm . . . . . . . . . . . . . . . . . . . . . 5.2.1 Giải thuật HOTSAX . . . . . . . . . . . . . 5.2.2 Mô hình đề xuất . . . . . . . . . . . . . . . 5.2.3 Duy trì trạng thái LSTM trong Keras (State 5.3 Kết quả thực nghiệm . . . . . . . . . . . . . . . . . 5.3.1 Bộ dữ liệu điện tâm đồ ECG . . . . . . . . . 5.3.2 Bộ dữ liệu nhiệt độ máy Numenta . . . . . . 5.3.3 Bộ dữ liệu power_demand . . . . . . . . . . 5.3.4 Bộ dữ liệu TEK16 . . . . . . . . . . . . . . 5.3.5 Bộ dữ liệu chứng khoán stock_20_0 . . . . 5.3.6 Bộ dữ liệu memory . . . . . . . . . . . . . . 5.3.7 Bộ dữ liệu ann_gun_CentroidA . . . . . . . 5.4 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . vi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Maintenance) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 32 34 36 38 40 40 40 42 . . . . . . . . . . . . . . 43 43 44 45 46 47 47 48 48 49 50 51 52 52 53 . . . . . . . . . . . . . . 55 55 58 58 59 62 62 62 65 67 69 71 73 75 79 MỤC LỤC 6 Kết Luận 6.1 Kết quả đạt được . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Hướng nghiên cứu tiếp theo . . . . . . . . . . . . . . . . . . . . . . . . 82 82 84 Tài liệu tham khảo 85 A Bảng đối chiếu thuật ngữ Anh - Việt A1 vii Danh sách hình vẽ 1.1 1.2 Chuỗi con bất thường trên dữ liệu điện tim đồ [1] . . . . . . . . . . . . Một ví dụ về mạng nơ-ron nhân tạo nhiều tầng . . . . . . . . . . . . . 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 2.10 2.11 2.12 2.13 2.14 Chuỗi thời gian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Phương pháp PAA . . . . . . . . . . . . . . . . . . . . . . . . . . . Phương pháp SAX . . . . . . . . . . . . . . . . . . . . . . . . . . . Bảng tra tìm các giá trị β theo từng giá trị a tương ứng . . . . . . Mô hình mạng MLP với một tầng ẩn . . . . . . . . . . . . . . . . . Mô hình mạng MLP với hai tầng ẩn . . . . . . . . . . . . . . . . . Quy ước đánh chỉ số các trọng số ghép nối giữa các nơ-ron . . . . . Cấu trúc mạng MLP với một tầng vào, một tầng ẩn và một tầng ra Cấu trúc mạng RNN . . . . . . . . . . . . . . . . . . . . . . . . . . Sự lặp lại của các khối nơ-ron trong kiến trúc RNN tiêu chuẩn . . . Sự lặp lại của các khối nơ-ron trong kiến trúc LSTM . . . . . . . . Kiến trúc một đơn vị LSTM . . . . . . . . . . . . . . . . . . . . . . Kiến trúc LSTM xếp chồng . . . . . . . . . . . . . . . . . . . . . . Mạng LSTM xếp chồng . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 Kiến trúc chiến lược hồi quy [2] . . . . . . . . . . . . . . . . . . . . . . Kiến trúc chiến lược trực tiếp [2] . . . . . . . . . . . . . . . . . . . . . Kiến trúc kết hợp chiến lược hồi quy và trực tiếp [2] . . . . . . . . . . . Kiến trúc chiến lược nhiều đầu vào – nhiều đầu ra [2] . . . . . . . . . . Kiến trúc kết hợp chiến lược trực tiếp và nhiều đầu vào–nhiều đầu ra [2] Một chuỗi thời gian được biến đổi PAA rồi mã hóa thành các ký hiệu [1] (a) LSTM cell (b) Kiến trúc LSTM xếp chồng [3] . . . . . . . . . . . . Kiến trúc mô hình kết hợp mạng học sâu và mô hình xác suất [4] . . . Quy trình huấn luyện và dự báo bằng mạng LSTM [5] . . . . . . . . . Sơ đồ hoàn chỉnh của phương pháp tiếp cận được đề xuất [5] . . . . . . Kết quả dự báo dựa trên dữ liệu chưa được hiệu chỉnh [5] . . . . . . . . Dự báo bằng mô hình LSTM và giải thuật AMIRA . . . . . . . . . . . Kết quả phát hiện bất thường . . . . . . . . . . . . . . . . . . . . . . . viii . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 4 9 12 13 13 15 15 16 16 19 20 20 21 23 23 25 26 27 28 28 29 31 32 34 35 36 38 39 DANH SÁCH HÌNH VẼ 3.14 Point anomaly (trái), collective anomaly (giữa) và contextual anomaly (phải) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.15 Kiến trúc hỗn hợp CNN và LSTM để phát hiện bất thường . . . . . . . 3.16 Hướng tiếp cận dựa trên đồ thị trong phát hiện bất thường . . . . . . . 3.17 Hướng tiếp cận dựa trên Transfer Learning trong phát hiện bất thường 40 41 42 42 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10 4.11 4.12 Dữ liệu ECG bình thường . . . . . . Dữ liệu ECG bất thường 1 . . . . . . Dữ liệu ECG bất thường 2 . . . . . . Bộ dữ liệu nhiệt độ máy Numenta . . Bộ dữ liệu power_demand . . . . . . Tuần dữ liệu bình thường . . . . . . Tuần dữ liệu bất thường . . . . . . . Bộ dữ liệu TEK16 . . . . . . . . . . Bộ dữ liệu chứng khoán stock_20_0 Bộ dữ liệu memory . . . . . . . . . . Bộ dữ liệu ann_gun_CentroidA . . . Kiến trúc mô hình đề xuất . . . . . . 44 44 44 45 46 46 46 47 47 48 48 50 5.1 5.2 5.3 5.4 5.5 Mô hình giải thuật HOT SAX . . . . . . . . . . . . . . . . . . . . . . . Mô hình đề xuất . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Phát hiện bất thường trên bộ dữ liệu ECG của mô hình đề xuất . . . . Phát hiện bất thường trên bộ dữ liệu ECG của HOTSAX . . . . . . . . Phát hiện bất thường trên bộ dữ liệu nhiệt độ máy Numenta của mô hình đề xuất . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Phát hiện bất thường trên bộ dữ liệu nhiệt độ máy Numenta của HOTSAX Phát hiện bất thường trên bộ dữ liệu power_demand của mô hình đề xuất . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Phát hiện bất thường trên bộ dữ liệu power_demand của HOTSAX . . Phát hiện bất thường trên bộ dữ liệu TEK16 của mô hình đề xuất . . . Phát hiện bất thường trên bộ dữ liệu TEK16 của HOTSAX . . . . . . Phát hiện bất thường trên bộ dữ liệu stock_20_0 của mô hình đề xuất Phát hiện bất thường trên bộ dữ liệu stock_20_0 của HOTSAX . . . . Phát hiện bất thường trên bộ dữ liệu memory của mô hình đề xuất . . Phát hiện bất thường trên bộ dữ liệu memory của HOTSAX . . . . . . Phát hiện bất thường trên bộ dữ liệu ann_gun_CentroidA kênh X của mô hình đề xuất . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Phát hiện bất thường trên bộ dữ liệu ann_gun_CentroidA kênh Y của mô hình đề xuất . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Phát hiện bất thường trên bộ dữ liệu ann_gun_CentroidA kênh X của HOTSAX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Phát hiện bất thường trên bộ dữ liệu ann_gun_CentroidA kênh Y của HOTSAX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Phát hiện bất thường trên bộ dữ liệu ECG nhân bản của mô hình đề xuất 5.6 5.7 5.8 5.9 5.10 5.11 5.12 5.13 5.14 5.15 5.16 5.17 5.18 5.19 ix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 59 63 64 65 66 67 68 70 70 72 72 74 74 76 77 77 78 80 DANH SÁCH HÌNH VẼ 5.20 Phát hiện bất thường trên bộ dữ liệu ECG nhân bản của HOTSAX . . x 80 Danh sách bảng 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 Thông số thiết lập của HOTSAX và mô hình đề xuất . . . Thời gian thực thi trên bộ dữ liệu ECG . . . . . . . . . . . Thời gian thực thi trên bộ dữ liệu nhiệt độ máy Numenta . Thời gian thực thi trên bộ dữ liệu power_demand . . . . . Thời gian thực thi trên bộ dữ liệu TEK16 . . . . . . . . . Thời gian thực thi trên bộ dữ liệu stock_20_0 . . . . . . . Thời gian thực thi trên bộ dữ liệu memory . . . . . . . . . Thời gian thực thi trên bộ dữ liệu ann_gun_CentroidA . . xi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 64 66 68 70 73 75 78 Chương 1 Giới thiệu đề tài 1.1 Đặt vấn đề Dữ liệu chuỗi thời gian (time series data) là dữ liệu đo đạc được một cách tuần tự theo thời gian. Có rất nhiều loại dữ liệu có yếu tố thời gian như vậy, ví dụ như dữ liệu điện tâm đồ (ECG), dữ liệu thiên văn, thời tiết, mực nước, dữ liệu tài chính, giá chứng khoán. . . Một nghiên cứu khảo sát về các hướng nghiên cứu quan trọng và đang là thách thức trong lĩnh vực khai thác dữ liệu (data mining) và học máy (Machine Learning) được thực hiện vào năm 2006 bởi Yang và Wu [6] cho kết quả 10 hướng nghiên cứu chính. Trong đó, hướng nghiên cứu về khai phá dữ liệu chuỗi thời gian được xếp thứ 3 trong 10 hướng nghiên cứu quan trọng và thách thức nhất. Do đó, việc khai phá dữ liệu chuỗi thời gian đã và đang thu hút rất nhiều sự quan tâm nghiên cứu trên thế giới. Các bài toán tiêu biểu trong khai phá chuỗi dữ liệu thời gian bao gồm: Lập chỉ mục (Indexing), Gom cụm (Clustering), Phân tầng (Classification), Tổng hợp (Summarization), Phát hiện Motif (Motif detection), Phát hiện chuỗi con bất thường (Anomaly detection). Khai phá dữ liệu chuỗi thời gian được ứng dụng rộng rãi trong nhiều lĩnh vực như y tế, kinh tế, tài chính, chứng khoán, quản lý mạng truyền thông. . . Các lĩnh vực này thường cần độ chính xác cao. Trong khi đó, những chuỗi con bất thường (anomalous subsequences) trên dữ liệu chuỗi thời gian thường ảnh hưởng rất nhiều đến kết quả khai phá dữ liệu. Hình 1.1 mô tả một chuỗi con bất thường trên đoạn dữ liệu điện tâm đồ (ECG). Vì vậy, việc phát hiện chuỗi con 1 CHƯƠNG 1. GIỚI THIỆU ĐỀ TÀI bất thường trên dữ liệu chuỗi thời gian đóng vai trò rất quan trọng và thường được dùng như bước tiền xử lý cho những bài toán khai phá dữ liệu sau này. Sau đây là một vài ứng dụng quan trọng của bài toán phát hiện chuỗi con bất thường: Hình 1.1: Chuỗi con bất thường trên dữ liệu điện tim đồ [1] Phát hiện bất thường của xung nhịp tim trên dữ liệu điện tim đồ (ECG) [7] [1]: thông thường dữ liệu điện tim ECG là những chuỗi thời gian tuần hoàn ghi lại các biến thiên của các điện lực do tim phát ra trong hoạt động co. Một bất thường trong dữ liệu này có thể là một mẫu không phù hợp (non-conforming pattern) về mặt chu kỳ hoặc biên độ, điều này chỉ ra rằng bệnh nhân có vấn đề về sức khoẻ. Phát hiện bất thường của chuyến bay sử dụng dữ liệu cảm biến từ máy bay: hành vi hệ thống của chuyến bay được thể hiện bởi dữ liệu cảm biến thông qua các thông số khác nhau. Các thông số này có giá trị thay đổi trong suốt quá trình bay. Nếu dữ liệu cảm biến có chuỗi con bất thường thì có thể hành vi hệ thống chuyến bay đang có sai lệch, cần cảnh báo [8]. Phát hiện tấn công trong các hệ thống tư vấn (Recommender system): tấn công Shilling, trong đó kẻ tấn công đưa ra các xếp hạng, đánh giá có thiên vị để ảnh hưởng đến những kết quả tư vấn, gợi ý trong tương lai [9]. Như vậy, phát hiện chuỗi con bất thường là một bài toán quan trọng, nhưng cũng nhiều thách thức trong dữ liệu chuỗi thời gian. Bởi vì dữ liệu đầu vào có thể chịu ảnh hưởng của nhiều yếu tố, dẫn đến sự không ổn định, hỗn loạn và có nhiều thành phần nhiễu (ví dụ như giá chứng khoán) [10]. Chính vì thế, không thể có một thông tin đầy đủ nào có thể biễu diễn chính xác mối quan hệ giữa giá trị tương lai với những giá trị trong quá khứ. Do đó, đối với bài toán phát hiện bất thường, các nhà nghiên cứu thường giả định rằng dữ liệu trong quá khứ có thể đại diện cho tất cả yếu tố tác động trong quá khứ, và dùng nó để dự 2 CHƯƠNG 1. GIỚI THIỆU ĐỀ TÀI đoán cho dữ liệu tương lai. Trong thời gian gần đây, nhiều phương pháp phát hiện bất thường trong dữ liệu chuỗi thời gian đã được các nhà nghiên cứu áp dụng và mang lại hiệu quả trong các bài toán thực tế. Nổi bật trong số đó, có thể kể đến các phương pháp như: phương pháp dựa trên cửa sổ trượt (sliding-window-based method), phương pháp dựa trên bài toán phân loại (classification-based method), phương pháp dựa trên bài toán phân đoạn (segmentation-based method). Gần đây nhất là phương pháp phát hiện bất thường dựa trên bài toán dự báo (prediction-based method). Đối với phương pháp phát hiện bất thường dựa trên bài toán dự báo, chúng ta có thể chia nó thành hai bài toán con. Thứ nhất là bài toán dự báo đối với dữ liệu chuỗi thời gian. Thứ hai là bài toán phát hiện bất thường dựa trên dữ liệu được dự báo. Đi sâu vào bài toán dự báo dữ liệu chuỗi thời gian, nhiều năm trước, các nhà nghiên cứu đã sử dụng nhiều kỹ thuật tuyến tính để giải quyết bài toán này, một trong số đó là mô hình Auto-Regressive Intergrated Moving Average (AMIRA) [11]. Vì đơn giản và phổ biến, nên phương pháp này thường được dùng để so sánh với các phương pháp hiện tại. Tuy nhiên, việc giả định chuỗi dữ liệu tuyến tính và không ổn định là không phù hợp với dữ liệu thực tế, vốn phi tuyến và hỗn loạn. Với ưu điểm có thể mô hình hoá các dữ liệu phi tuyến, các mạng nơ-ron học sâu đã và đang thể hiện hiệu quả của mình trong các bài toán dự báo. Đầu tiên có thể kể đến mạng nơ-ron nhân tạo (Artiticial Neural Networks - ANN). Nhiều nghiên cứu đã chứng minh rằng, ANN là một kỹ thuật hiệu quả để dự báo chuỗi dữ liệu thời gian. Tang và Fishwich [12], Wang và Leu [13], Jan và các cộng sự [14] đã chỉ ra rằng, ANN cho kết quả tốt hơn mô hình AMIRA, đặc biệt với dữ liệu không ổn định. Kết quả này có được là do khả năng mô hình hoá các hàm phi tuyến mà không cần bất cứ giả định nào của dữ liệu đầu vào. Bên cạnh đó, ANN cũng bộc lộ điểm yếu khi số lượng kết nối giữa các tầng quá lớn, dẫn đến trọng số của kiến trúc này nhiều. Điều này làm cho ANN không thể xây dựng được các mô hình phức tạp và dễ bị hiện tượng quá khớp (overfitting) mà không thể làm tốt với dữ liệu ngoài thực tế. Theo các giáo sư LeCun, Bengio và Hinton, học sâu (deep learning) cho phép các mô hình tính toán gồm nhiều tầng xử lý để học biểu diễn dữ liệu với nhiều 3 CHƯƠNG 1. GIỚI THIỆU ĐỀ TÀI mức trừu tượng khác nhau [15]. Thời gian gần đây, học sâu dựa trên mạng nơron nhân tạo (ANN) đang chứng minh được sự hiệu quả. Với việc sử dụng nhiều tầng nơ-ron, mạng nơ-ron học sâu đã biểu diễn dữ liệu tốt hơn so với các mạng truyền thống khác. Hình 1.2 mô tả một ví dụ về mạng nơ-ron nhân tạo có nhiều tầng. Hình 1.2: Một ví dụ về mạng nơ-ron nhân tạo nhiều tầng Phần bên trái hình 1.2 cho thấy một mạng nơ-ron gồm nhiều tầng, trong đó nơ-ron của tầng trước kết nối đầy đủ (fully-connected) với các nơ-ron của tầng sau. Mạng nơ-ron dạng này là mạng nơ-ron truyền thẳng (Feed-forward Neural Networks – FNN) hay mạng perceptron nhiều tầng (Multilayer Perceptron – MLP). Phần bên phải của hình 1.2 mô tả cơ chế lan truyền ngược để tính đạo hàm của hàm chi phí (hàm J) theo tham số ở từng tầng của mô hình. Với kiến trúc độc đáo, mạng nơ-ron hồi quy (Recurrent Neural Network - RNN) [16] [17] được biết đến nhiều trong các bài toán có dữ liệu chuỗi thời gian: dịch máy, chuyển giọng nói thành chữ và ngược lại, ECG, giá chứng khoán. . . Một điểm nổi bật của RNN chính là ý tưởng kết nối các thông tin phía trước để dự đoán cho hiện tại, các thông tin này khá gần với hiện tại. Nhưng, RNN lại thể hiện rõ khuyết điểm với dữ liệu có tính phụ thuộc xa (long-term dependency), hay nói cách khác là dữ liệu tại thời điểm hiện tại chịu ảnh hưởng của dữ liệu khá lâu trong quá khứ. Như một điều tất yếu, mạng nơ-ron học sâu Long Short 4 CHƯƠNG 1. GIỚI THIỆU ĐỀ TÀI Time Memory (LSTM) [18] xuất hiện như phiên bản nâng cấp của RNN, với sự kế thừa các ưu điểm của RNN, và giải quyết được vấn đề đối với dữ liệu có tính phụ thuộc xa trong mô hình RNN truyền thống. Mạng nơ-ron học sâu LSTM được giới thiệu bởi Hochreiter và Schmidhuber (1997), và sau đó đã được cải tiến rất nhiều. Chúng hoạt động rất hiệu quả trên nhiều bài toán khác nhau nên dần đã trở nên phổ biến như hiện nay. Mạng nơ-ron học sâu LSTM được thiết kế để tránh được vấn đề phụ thuộc xa. Đi sâu vào bài toán con thứ hai, phát hiện bất thường là một trong những bài toán thú vị và đầy thách thức. Mỗi kiểu dữ liệu chúng ta lại có một phương pháp đặc thù để xác định bất thường. Từ thập niên 1980, các nhóm nghiên cứu đã đề xuất nhiều phương pháp phát hiện chuỗi bất thường trên dữ liệu chuỗi thời gian. Nhìn chung, các phương pháp này dựa vào các kỹ thuật như: dùng xác suất thống kê đơn giản như Cu-Mulative Sum (CUSUM) hoặc Exponentially Weighted Moving Average (EWMA), hoặc phương pháp phát hiện bất thường dựa vào mật độ và khoảng cách. Bên cạnh đó cũng có các phương pháp đã được đề cập ở đầu chương như: phương pháp dựa vào cửa sổ trượt, sự tương tự, mô hình Markov ẩn, phân lớp hoặc phân đoạn. Các phương pháp này bộc lộ nhược điểm như: có nhiều loại bất thường trong dữ liệu, khó xác định độ dài chuỗi con, chuỗi thời gian kiểm thử và chuỗi thời gian huấn luyện có độ dài khác nhau, chuỗi thời gian trong thực tế thường dài và khi độ dài tăng thì độ phức tạp tính toán cũng tăng lên. Trong nhóm phương pháp dựa vào cửa sổ trượt, có hai phương pháp để giải quyết bài toán phát hiện chuỗi con bất thường này được nhiều nhà nghiên cứu quan tâm và ưa chuộng, đó là giải thuật HOT SAX của Keogh và các cộng sự [1], giải thuật WAT của Fu và các cộng sự [19]. Một hướng đi khác, năm 2015, Malhotra và các cộng sự đã sử dụng ưu thế của mạng nơ-ron học sâu để giải quyết bài toán phát hiện bất thường [3], bằng việc sử dụng mạng LSTM xếp chồng và sử dụng phân phối sai số dự báo để phát hiện bất thường. Bên cạnh đó, Buda và cộng sự đã kết hợp ưu thế của mạng nơ-ron học sâu, cũng như tính hiệu quả của mô hình AMIRA đối với dữ liệu tuyến tính và có tính ổn định để tăng hiệu quả cho bài toán dự báo, từ đó góp phần tăng độ 5 CHƯƠNG 1. GIỚI THIỆU ĐỀ TÀI chính xác cho bài toán dự báo [4]. 1.2 Mục tiêu nghiên cứu Với những tiềm năng đầy hứa hẹn của các mạng nơ-ron học sâu, trong nghiên cứu này chúng tôi sẽ áp dụng ưu thế của mạng nơ-ron học sâu trong bài toán dự báo, và dựa vào đó để phát hiện chuỗi con bất thường trên dữ liệu chuỗi thời gian. Để giải quyết được bài toán đề ra, chúng tôi sẽ xây mô hình học sâu, trọng tâm sử dụng mạng nơ-ron học sâu LSTM, vì các tập dữ liệu đều có sự tương quan giữa giá trị lịch sử tới giá trị hiện tại. Mặt khác, trong những năm gần đây, các nhà nghiên cứu đã sử dụng mạng nơ-ron học sâu LSTM trong các bài toán dự đoán giá trị của chuỗi thời gian và đạt kết quả tốt so với các kỹ thuật khác. Một bước tiến xa là các kết quả nghiên cứu này còn có thể được sử dụng trong các ứng dụng thực tế. Kế thừa nghiên cứu của Malhotra và các cộng sự [3], chúng tôi sẽ xây dựng mạng nơ-ron học sâu LSTM xếp chồng cho bài toán dự báo và sử dụng giải thuật phân phối sai số dự báo [20] cho bài toán phát hiện chuỗi con bất thường. Bên cạnh đó, kỹ thuật dự báo nhiều bước (multi-step ahead prediction) cũng sẽ được chúng tôi áp dụng để tăng tính hiệu quả cho chặng dự báo của công tác phát hiện bất thường [2]. Nghiên cứu sẽ sử dụng những bộ dữ liệu mẫu từ các công trình đi trước. Những bộ dữ liệu này đã được đánh dấu chuỗi con bất thường. Nghiên cứu sẽ sử dụng những chuỗi con bất thường này để huấn luyện và đánh giá. Ngoài ra, nghiên cứu cũng so sánh với giải thuật HOT SAX, một phương pháp nhận dạng chuỗi con bất thường được nhiều nhà nghiên cứu ưa chuộng. Chúng tôi sẽ so sánh về độ chính xác của các chuỗi con bất thường được phát hiện. Từ những kết luận rút ra được, chúng ta sẽ biết được phương pháp nào hiệu quả hơn trong công tác phát hiện chuỗi con bất thường trên dữ liệu chuỗi thời gian. Những điều này là những yếu tố quan trong khi sử dụng trong thực tế. 6