MỞ ĐẦU Ngày nay cùng với sự gia tăng của “dữ liệu” (data) sinh ra theo thời gian từ cảm biến và các thiết bị đo thì việc chẩn đoán và phát hiện những “bất thường” (novelty) trong “dữ liệu chuỗi thời gian” (time series data) để cảnh báo lỗi có thể xảy ra ngày càng dành được nhiều sự quan tâm nghiên cứu. Trong lĩnh vực y tế, việc phát hiện những bất thường trong chuỗi tín hiệu thu được từ các máy đo điện tâm đồ hay điện não đồ để phát hiện những triệu chứng bệnh và thực hiện những biện pháp chữa trị thích hợp sẽ giúp cứu sống nhiều bệnh nhân. Bên cạnh đó trong lĩnh vực tài chính, chứng khoán, ngân hàng việc phát hiện những dấu hiệu của suy thoái sẽ giúp tổ chức đưa ra những biện pháp xử lý hợp lý đảm bảo sự ổn định và phát triển của tổ chức. Từ những yêu cầu cấp thiết trên đã nảy sinh ra vấn đề “Phát hiện bất thường trong dữ liệu chuỗi thời gian”.
Được phát biểu là tự động xác định những sự kiện bất thường xuất hiện trong chuỗi những điểm bình thường trên dữ liệu chuỗi thời gian. Đây là một vấn đề mang đầy thách thức vì kiến thức không đủ và không chính xác về thể hiện của bất thường trong hệ thống đã đề cập. Dù có những thách thức về kỹ thuật, nhưng vấn đề phát hiện bất thường đã nhận được rất nhiều sự quan tâm trong thời gian qua vì tầm quan trọng và ý nghĩa của nó. Nhiều giải pháp đã được đề xuất để giải quyết vấn đề trên.
Những giải pháp này đã được hiện thực hóa và chứng minh tính hiệu quả của nó trong một số trường hợp nhưng lại không hiệu quả thậm chí không áp dụng được trong một số trường hợp khác do những giả định và tiến trình mà dựa trên đó giải pháp này được hiện thực. Ta có thể kể đến như “Giải pháp phát hiện bất thường bằng mô hình mạng neural” [17] được đề xuất bởi R. Yokayama năm 1994 hay “Phát hiện bất thường dựa trên mô hình hóa và tối ưu hóa mô hình” [16] được đề xuất bởi Rolf Isermamn năm 1984. Những giải phát này dựa trên giả định là đã có kiến thức hay mô hình lý thuyết chính xác của bất thường mà không phải lúc nào cũng có trong thực tế.
Hay như phương pháp TARZAN [9] thì dựa trên việc chuyển dữ liệu chuỗi thời gian thành chuỗi các ký tự. Tuy nhiên quá trình chuyển đổi này có thể làm mất đi những mẫu có ý nghĩa trong dữ liệu chuỗi thời gian gốc. Ngoài ra còn có một số phương pháp khác như “Máy vector hỗ trợ (Support vector. machine SVMs) để pháp hiện bất thường”[3] do B.
Trang 1 Smola và J.Platt đề xuất năm 2000 và “Lập trình tuyến tính để phát hiện bất thường”[5] của C. Trong các phương pháp này, sự kiện bất thường được thể hiện như những “đoạn ngoại biên” (outliers) của hàm phân bố chuẩn. Cách tiếp cận này có nền tảng lý thuyết chắc chắn và được định nghĩa rõ ràng. Tuy nhiên phương pháp này chỉ áp dụng cho vector mà không ứng dụng trực tiếp cho dữ liệu chuỗi thời gian.
Tiếp theo hướng phát hiện của B. Sch o lkopf trong bài báo của mình “Phát hiện bất thường trong dữ liệu chuỗi thời gian sử dụng Máy vector hỗ trợ một lớp” [11] năm 2003. Perkins đã đề xuất giải pháp để ứng dụng SVMs trong việc phát hiện bất thường trong dữ liệu chuỗi thời gian. Tuy nhiên nghiên cứu của Ma và các cộng sự tồn tại một số bất cập: Chỉ đưa ra giải pháp và thực hiện một số thực nghiệm trên dữ liệu tổng hợp là dữ liệu hình sin với bất thường tự thêm vào mà không phải những bộ dữ liệu chuẩn thực tế.
Không so sánh giải pháp được đưa ra với các phương pháp hiện có để chứng minh ưu và nhược điểm của giải pháp đề xuất. Để phân loại dữ liệu kiểm tra ông dùng tích các kết quả khi áp dụng giải thuật với các số chiều khác nhau cho vector dữ liệu. Trong thực tế chiều dài của chuỗi bất thường là cố định ứng với mỗi loại dữ liệu nên phương pháp của ông là không hợp lý trong thực tế. Việc ứng dụng thư viện LIBSVM[22] để tạo mô hình và phát hiện bất thường sử dụng máy vector hỗ trợ một lớp là không khả thi với dữ liệu thực.
Vì mô hình được tạo ra với chỉ các mẫu bình thường thường không chính xác và không phân loại được bất thường trong dữ liệu kiểm tra. Trong luận văn này chúng tôi sẽ tiếp tục phát triển ý tưởng mà J.Ma và các cộng sự đã đưa ra là dùng máy vector hỗ trợ để phát hiện bất thường. Tuy nhiên để đánh giá và tăng hiệu quả của phương pháp phát hiện bất thường dùng máy vector hỗ trợ. Chúng tôi thực hiện một số cải tiến sau: Sử dụng máy vector hỗ trợ hai lớp thay vì máy vector hỗ trợ một lớp để gia tăng độ chính xác khi phát hiện bất thường.
Để khắc phụ tình trạng thiếu những mẫu bất thường trong dữ liệu huấn luyện và để tăng độ chính xác của giải thuật chúng tôi áp dụng phương pháp “vùng Trang 2 bao” (envelope) [1] để tạo ra những mẫu bất thường nhân tạo ngẫu nhiên và mẫu bình thường nhân tạo ngẫu nhiên từ mẫu bình thường. Giải pháp đưa ra sẽ được kiểm tra trên các tập dữ liệu kiểm tra chuẩn và tập dữ liệu mô phỏng. Qua thực nghiệm chúng tôi sẽ tìm ra số chiều tối ưu và các hệ số của Máy vector hỗ trợ hai lớp tương ứng tập dữ liệu huấn luyện. Để đánh giá hiệu quả của giải thuật mới chúng tôi cũng tiến hành so sánh với giải thuật HOTSAX là giải thật dùng để phát hiện bất thường phổ biến hiện nay.
Phép so sánh là tính chính xác trong phát hiện bất thường. Phép so sánh về thời gian thực thi cũng được thực hiện nhưng chỉ mang tính chất tham khảo do phương pháp phát hiện bất thường dùng máy vector hỗ trợ thường chậm hơn đo tính chất vốn có của SVMs. Chúng tôi cũng thiết kế phần mềm để hiển thị kết quả phát hiện bất thường trên chuỗi dữ liệu thời gian. Qua thực nghiệm trên dữ liệu mô phỏng (dữ liệu hình sin) và dự liệu thực tế (Koski, ERP, Memory, Temperature), phương pháp dùng máy vector hỗ trợ hai lớp (two class SVMs) đã thể hiện được ưu điểm trong việc phát hiện được tất cả những đoạn bất thường với các chiều dài khác nhau khi so sánh với giải thuật HOTSAX chỉ phát hiện được 1 chuỗi con bất thường với chiều dài bằng kích thước cửa sổ trượt.
Quá trình thực nghiệm cũng cho thấy nhược điểm về thời gian thực thi của phương pháp được đề xuất. Do việc khai triển dữ liệu lên không gian pha chiếu với số chiều lớn (320 với dữ liệu ERP và memory, 400 với dữ liệu Koski) làm cho bộ phân loại tốn quá nhiều thời gian cho việc tính toán tích vô hướng các vector. Phương pháp máy vector hỗ trợ kém hiệu quả với những dữ liệu có nhiều motif bình thường và dữ liệu phức tạp. Việc bộ phân loại cần được huấn luyện với các mẫu bình thường trước dẫn đến việc phân loại sai những mẫu bình thường mới.
Cũng như các phương pháp khác, phương pháp sử dụng Máy vector hỗ trợ không thể giải quyết mọi vấn đề, nhưng ít nhất nó cũng có thể giải quyết những vấn đề mà các phương pháp khác không giải quyết được hay giải quyết được như với độ chính xác thấp. Phần còn lại của luận văn được tổ chức như sau. Chương 2 liệt một số khái niệm cơ bản được dùng trong luận văn và giới thiệu sơ lược một số phương pháp phát hiện bất thường được dùng hiện nay. Chương 3 đi sâu vào phân tích nền tảng lý thuyết của phương pháp máy vector hỗ trợ hai lớp.
Phương pháp “vùng bao” để tạo mẫu bình Trang 3 thường nhân tạo ngẫu nhiên và bất thường nhân tạo ngẫu nhiên cũng được giới thiệu. Chương 4 trình bày kết quả thực nghiệm của phương pháp được đề xuất với cái loại dữ liệu khác nhau và với các chiều dài chuỗi con khác nhau, cung cấp một cái nhìn sơ lược về phần mềm được thiết kế trong luận văn và phương pháp sử dụng. Kết quả thực nghiệm cũng được so sánh với giải thuật HOTSAX dựa trên hai thước đo về tính chính xác và thời gian thực hiện. Và chương 5 sẽ tổng kết những gì đã thực hiện trong luận văn, kết quả và hướng phát triển.
Trang 4 Chương 2: TỔNG THUẬT VỀ CÁC CÔNG TRÌNH LIÊN QUAN Chương này nhắc lại một số khái niệm cơ bản được sử dụng trong phát hiện bất thường, sau đó giới thiệu một số công trình tiêu biểu về phát hiện bất thường có liên quan đến luận văn này.1 Một số định nghĩa: 2.1 Dữ liệu chuỗi thời gian Dữ liệu chuỗi thời gian (time series data) là những tập hợp dữ liệu được thu thập, lưu trữ, quan sát và đo đạc theo sự tăng dần của thời gian. Ví dụ như là các chuỗi dữ liệu thời gian trong lĩnh vực tài chính dự báo số lượng hàng hóa bán được theo từng quý các chuỗi dữ liệu thời gian dùng trong khoa học dự báo sự gia tăng của công nghệ xử lý tốc độ của CP và Memmory.1 là chuỗi dữ liệu về giá cổ phiếu qua các năm.0-1 : Dữ liệu chuỗi thời gian biễu diễn giá cổ phiếu. Ta ký kiệu chuỗi thời gian là {Xt} với t là các số tự nhiên tương ứng với các mốc thời gian mà ta quan sát, đo đạc được hay c n gọi là độ trễ. Xt là các biến ngẫu nhiên rút ra từ một phân bố xác suất tùy theo nhu cầu của người muốn phân tích trên dữ liệu chuỗi thời gian này.2 Chuỗi con Cho một dữ liệu chuỗi thời gian T có chiều dài là n, một chuỗi con (subsequence)[8] C trong T có chiều dài m là một mẫu của những giá trị liên tục trích từ T, C = tp,….2 là ví dụ cho chuỗi con có chiều dài w được trích ra từ chuỗi dữ liệu ban đầu.0-2 : Ví dụ về chuỗi con.3 Cửa sổ trượt Cho một dữ liệu chuỗi thời gian T có chiều dài n, một cửa sổ trượt (slide window)[8] có kích thước w do người dùng định nghĩa (thường w << n) sẽ trượt qua từng điểm giá trị trên chuỗi T, kết quả là ta được một danh sách n-w+1 các chuỗi con có kích thước w được rút trích từ chuỗi T.4 Trùng khớp Trùng khớp (match)[8] được định nghĩa như sau.