CHƯƠNG 2 CƠ SỞ LÝ THUYẾT
2.3. Các kỹ thuật phát hiện bất thường
2.3.1. Dựa vào cửa sổ trượt (Window based)
Giả thiết của kỹ thuật này là sự bất thường trong một chuỗi thời gian có thể do một hoặc nhiều chuỗi con bất thường gây ra. Do đó, kỹ thuật này dùng cửa sổ trượt để chia chuỗi thời gian thành các cửa sổ có kích thước xác định (gọi là chuỗi con - subsequences). Cửa sổ trượt (sliding) trên chuỗi thời gian gốc một lúc một hay nhiều ký hiệu để rút trích ra các cửa sổ có cùng chiều dài m (chuỗi con chiều dài m).
Giá trị điểm bất thường (anomaly score) của một chuỗi thời gian được tính bằng cách tổng hợp giá trị điểm bất thường của các chuỗi con được rút trích từ nó. Một cơ chế dựa trên cửa sổ trượt được mô tả tổng quát như sau:
Cho một tập chuỗi thời gian huấn luyện Straining= {S1, S2, …, Sn}, mỗi chuỗi thời gian Si được rút trích p cửa sổ, tương ứng là si1, si2 , . . . sip. Tương tự, cho tập chuỗi thời gian kiểm thử Stest={T1, T2, …, Tn}, chia mỗi chuỗi thời gian Ti thành p’ cửa sổ, tương ứng là ti1, ti2 , . . ., tip’
Điểm bất thường của mỗi cửa sổ kiểm thử (A(tij)) được tính dựa trên độ đo tương tự giữa nó và cửa sổ huấn luyện. Hàm đo độ tương tự này có thể là độ đo khoảng cách như Euclidean, Manhattan hoặc các giá trị tương quan, …
Các chuỗi con thu được bằng cách trượt cửa sổ kích thước m trên chuỗi thời gian và di chuyển nó với một bước nhảy (h) nhất định mỗi lần. Trường hợp bước
nhảy h = 1, nghĩa là trượt lần lượt từng ký hiệu, số lượng cửa sổ rút trích gần bằng kích thước chuỗi thời gian, do đó khối lượng tính toán lớn. Trường hợp bước nhảy h quá lớn thì có khả năng mất thông tin. Trường hợp đặc biệt là bước nhảy bằng kích thước cửa sổ (h = m), giữa các cửa sổ không có sự chồng chéo.
Với cửa sổ kích thước m, nếu h = 1 thì xác suất bất thường được phát hiện bởi ít nhất 1 cửa sổ là 1, nếu h > 1 thì xác suất này sẽ giảm. Cho tập huấn luyện chứa n chuỗi thời gian tương tự abcabcabc, với mỗi ký tự là một giá trị thực. Nếu kích thước cửa sổ là 3, cửa sổ huấn luyện cho bất kỳ bước nhảy h nào cũng chỉ gồm các chuỗi con sau: abc, bca, cab. Cho chuỗi kiểm thử abccabcabc, với sự xuất hiện của c sau chuỗi con abc đầu tiên là bất thường. Bảng 2.1 liệt kê tất cả các cửa sổ kiểm thử được rút trích với các bước nhảy h khác nhau:
Bảng 2.1: Giá trị hop thay đổi, kích thước cửa sổ cố định là 3
hop (h) Windows
1 abc, bcc, cca, cab, abc, bca, cab, abc
2 abc, cca, abc, cab
3 abc, cab, cab
4 abc, abc
Khi h = 1 và h = 2, sự xuất hiện bất thường của ký tự c trong chuỗi kiểm thử abccabcabc được phát hiện bởi cửa sổ bcc và cca vì không có bất kỳ sự tương tự nào giữa 02 cửa sổ này với những cửa sổ huấn luyện. Khi h có giá trị 3 hoặc 4 thì sự xuất hiện bất thường của ký tự c không được phát hiện vì ký tự c bị bỏ qua trong quá trình trượt cửa sổ. Do đó, giá trị của h cần phải được chọn cẩn thận.
Các kỹ thuật phát hiện chuỗi bất thường dựa trên cửa sổ trượt có thể sử dụng các phương pháp khác nhau để gán điểm bất thường (anomaly score) cho cửa sổ (chuỗi con). Ví dụ, điểm bất thường của một cửa sổ kiểm thử có thể là khoảng cách giữa nó và cửa sổ lân cận thứ k (kth nearest neighbor) của nó trong tập cửa sổ huấn luyện. Một phương pháp khác được đề xuất trong công trình, Ma cùng cộng sự [32]
phân loại tập cửa sổ huấn luyện thành một lớp SVM. Điểm bất thường của mỗi cửa
sổ kiểm thử có giá trị 0 hoặc 1 nếu nó được phân loại là bình thường hay là bất thường dựa trên lớp huấn luyện SVM.
Ưu nhược điểm:
Kỹ thuật dựa vào cửa sổ trượt có thể phát hiện được một chuỗi thời gian bất thường hoặc một chuỗi con bất thường trong chuỗi thời gian. Vì toàn bộ chuỗi thời gian được chia thành các chuỗi con nhỏ nên có thể dễ dàng xác định được một chuỗi con là bất thường. Nếu toàn bộ chuỗi thời gian là bất thường thì tất cả các chuỗi con cũng là bất thường, do đó kỹ thuật dựa trên cửa sổ trượt cũng sẽ tìm được sự bất thường khá tốt.
Hạn chế của kỹ thuật dựa vào cửa sổ trượt là kích thước cửa sổ phải được lựa chọn cẩn thận để nó có thể phát hiện được sự bất thường. Kích thước tối ưu của cửa sổ phụ thuộc vào độ dài của vùng bất thường trong chuỗi thời gian bất thường. Ví dụ, trong tập dữ liệu Power ở Hình 2.2, vùng bất thường có kích thước bằng với chu kỳ của chuỗi thời gian. Do đó, nếu m được chọn nhỏ hơn kích thước của chu kỳ thì hiệu quả sẽ giảm. Một hạn chế khác của kỹ thuật dựa trên cửa sổ trượt là chi phí tính toán lớn. Vì mỗi cặp cửa sổ kiểm thử và cửa sổ huấn luyện đều được tính toán nên độ phức tạp tính toán là O((nl)2), với l là chiều dài trung bình của chuỗi thời gian, n là số chuỗi thời gian kiểm thử và huấn luyện trong cơ sở dữ liệu.
Hình 2.3: Một chuỗi thời gian bất thường (màu đỏ), một chuỗi thời gian bình thường (màu xanh). Chuỗi bất thường bỏ qua chu kỳ cuối (vùng bất thường)