Luận văn thạc sĩ khoa học máy tính khảo sát và đánh giá hiệu quả của phương pháp phát hiện chuỗi con bất thường trên dữ liệu chuỗi thời gian dựa vào máy vector hỗ trợ

Luận văn thạc sĩ khoa học máy tính khảo sát hiệu quả phương pháp phát hiện chuỗi con bất thường trên dữ liệu chuỗi thời gian sử dụng máy vector hỗ trợ.

• Tác giả: Nguyễn Bá Thu
• Người hướng dẫn: PGS. Dương Tuấn Anh
• Trường học: Đại học Bách Khoa, Đại học Quốc gia Thành phố Hồ Chí Minh
• Chuyên ngành: Khoa học máy tính
• Đề tài: Khảo sát và đánh giá hiệu quả phương pháp phát hiện chuỗi con bất thường trên dữ liệu chuỗi thời gian bằng máy vector hỗ trợ
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2014
• Địa điểm: Thành phố Hồ Chí Minh

Tóm tắt

I. Giới thiệu

Luận văn tập trung vào việc khảo sát và đánh giá hiệu quả của phương pháp phát hiện chuỗi con bất thường trên dữ liệu chuỗi thời gian sử dụng máy vector hỗ trợ (SVM). Vấn đề phát hiện bất thường trong dữ liệu chuỗi thời gian có ý nghĩa quan trọng trong nhiều lĩnh vực như y tế, tài chính và công nghiệp. Các phương pháp truyền thống như Brute-Force và HOTSAX đã được áp dụng, nhưng vẫn tồn tại những hạn chế. Luận văn đề xuất sử dụng máy vector hỗ trợ hai lớp để cải thiện độ chính xác và hiệu quả trong việc phát hiện bất thường.

1.1. Bối cảnh nghiên cứu

Phát hiện bất thường trong dữ liệu chuỗi thời gian là một bài toán quan trọng, đặc biệt trong các lĩnh vực như y tế và tài chính. Các phương pháp hiện có như Brute-Force và HOTSAX đã được sử dụng, nhưng chúng có những hạn chế về độ chính xác và khả năng áp dụng. Luận văn này tập trung vào việc cải tiến phương pháp bằng cách sử dụng máy vector hỗ trợ hai lớp.

1.2. Mục tiêu nghiên cứu

Mục tiêu chính của luận văn là khảo sát và đánh giá hiệu quả của phương pháp phát hiện chuỗi con bất thường trên dữ liệu chuỗi thời gian sử dụng máy vector hỗ trợ hai lớp. Nghiên cứu cũng nhằm so sánh hiệu quả của phương pháp này với các phương pháp truyền thống như HOTSAX.

II. Cơ sở lý thuyết

Luận văn trình bày các khái niệm cơ bản về dữ liệu chuỗi thời gian, chuỗi con bất thường, và các phương pháp phát hiện bất thường hiện có. Phương pháp máy vector hỗ trợ hai lớp được giới thiệu như một giải pháp mới để cải thiện độ chính xác trong việc phát hiện bất thường. Phương pháp này sử dụng quá trình nhúng thời gian trễ để chuyển đổi dữ liệu chuỗi thời gian thành các vector đặc trưng.

2.1. Dữ liệu chuỗi thời gian

Dữ liệu chuỗi thời gian là một chuỗi các điểm dữ liệu được thu thập theo thời gian. Việc phát hiện các chuỗi con bất thường trong dữ liệu này có ý nghĩa quan trọng trong việc dự đoán các sự kiện bất thường như hỏng hóc hệ thống hoặc biến động tài chính.

2.2. Máy vector hỗ trợ hai lớp

Phương pháp máy vector hỗ trợ hai lớp được sử dụng để phân loại các vector đặc trưng thành hai lớp: bình thường và bất thường. Phương pháp này yêu cầu một tập huấn luyện bao gồm cả vector bình thường và bất thường, nhưng trong thực tế, tập huấn luyện thường chỉ chứa vector bình thường. Để khắc phục vấn đề này, phương pháp vùng bao được áp dụng để tạo ra các vector bất thường nhân tạo.

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

Luận văn đề xuất một phương pháp mới để phát hiện chuỗi con bất thường trên dữ liệu chuỗi thời gian sử dụng máy vector hỗ trợ hai lớp. Phương pháp này bao gồm các bước chính: chuyển đổi dữ liệu chuỗi thời gian thành các vector đặc trưng, tạo tập huấn luyện bằng phương pháp vùng bao, và sử dụng máy vector hỗ trợ hai lớp để phân loại các vector đặc trưng.

3.1. Chuyển đổi dữ liệu chuỗi thời gian

Dữ liệu chuỗi thời gian được chuyển đổi thành các vector đặc trưng bằng quá trình nhúng thời gian trễ. Quá trình này giúp tạo ra các vector đặc trưng phù hợp để sử dụng trong máy vector hỗ trợ hai lớp.

3.2. Phương pháp vùng bao

Phương pháp vùng bao được sử dụng để tạo ra các vector bất thường nhân tạo từ các vector bình thường trong tập huấn luyện. Điều này giúp tăng cường độ chính xác của máy vector hỗ trợ hai lớp trong việc phát hiện bất thường.

IV. Kết quả và đánh giá

Luận văn trình bày các kết quả thực nghiệm trên các bộ dữ liệu chuẩn và dữ liệu mô phỏng. Phương pháp máy vector hỗ trợ hai lớp được so sánh với phương pháp HOTSAX về độ chính xác và thời gian thực hiện. Kết quả cho thấy phương pháp mới có khả năng phát hiện bất thường với độ chính xác cao hơn, đặc biệt trong các trường hợp chuỗi bất thường có độ dài bất kỳ.

4.1. Thực nghiệm trên dữ liệu chuẩn

Phương pháp máy vector hỗ trợ hai lớp được thử nghiệm trên các bộ dữ liệu chuẩn như Koski, ERP, và Memory. Kết quả cho thấy phương pháp này có khả năng phát hiện bất thường với độ chính xác cao hơn so với HOTSAX.

4.2. So sánh với phương pháp HOTSAX

Phương pháp máy vector hỗ trợ hai lớp được so sánh với HOTSAX về độ chính xác và thời gian thực hiện. Kết quả cho thấy phương pháp mới có ưu điểm trong việc phát hiện các chuỗi bất thường có độ dài bất kỳ, trong khi HOTSAX chỉ phát hiện được các chuỗi bất thường có độ dài cố định.

V. Kết luận và hướng phát triển

Luận văn kết luận rằng phương pháp máy vector hỗ trợ hai lớp là một giải pháp hiệu quả để phát hiện chuỗi con bất thường trên dữ liệu chuỗi thời gian. Phương pháp này có độ chính xác cao hơn so với các phương pháp truyền thống như HOTSAX. Hướng phát triển trong tương lai bao gồm việc tối ưu hóa thời gian thực hiện và mở rộng ứng dụng của phương pháp trong các lĩnh vực khác.

5.1. Kết luận

Phương pháp máy vector hỗ trợ hai lớp đã chứng minh hiệu quả trong việc phát hiện chuỗi con bất thường trên dữ liệu chuỗi thời gian. Phương pháp này có độ chính xác cao hơn so với HOTSAX, đặc biệt trong các trường hợp chuỗi bất thường có độ dài bất kỳ.

5.2. Hướng phát triển

Hướng phát triển trong tương lai bao gồm việc tối ưu hóa thời gian thực hiện của phương pháp và mở rộng ứng dụng của nó trong các lĩnh vực khác như y tế, tài chính và công nghiệp.

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

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.