Đại học quốc gia TP. Hồ Chí Minh
TRƢỜNG ĐẠI HỌC BÁCH KHOA

VÕ ĐÌNH QUANG

PHÁT HIỆN BẤT THƢỜNG DỮ
LIỆU CHUỖI THỜI GIAN SỬ DỤNG
SUPPORT VECTOR MACHINE
Chuyên ngành: Khoa học máy tính

LUẬN VĂN THẠC SĨ

TP. HỒ CHÍ MINH, tháng 1 năm 2011


CƠNG TRÌNH ĐƢỢC HỒN THÀNH TẠI
TRƢỜNG ĐẠI HỌC BÁCH KHOA
ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH
Cán bộ hƣớng dẫn khoa học: T.S Quản Thành Thơ
Cán bộ chấm nhận xét 1: TS. Phạm Văn Chung ..........................................................
Cán bộ chấm nhận xét 2: PGS. TS. Dƣơng Tuấn 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 27 tháng 01 năm 2011
Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm:
1. PGS. TS. Đỗ Phúc ...................................................................................................
2. TS. Bùi Hoàng Thắng .............................................................................................
3. TS. Quản Thành Thơ ...............................................................................................
4. PGS. TS. Dƣơng Tuấn Anh ....................................................................................
5. TS. Phạm Văn Chung ..............................................................................................
Xác nhận của Chủ tịch Hội đồng đánh giá LV và Bộ môn 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 đánh giá LV

Bộ môn quản lý chuyên ngành


Võ Đình Quang

Trang 3

TRƢỜNG ĐH BÁCH KHOA TP. HCM

CỘNG HỊA XÃ HỘI CHỦ NGHĨA VIỆT NAM

PHÒNG ĐÀO TẠO SĐH

Độc lập – Tự do – Hạnh phúc

Tp. HCM ngày 27 tháng 01 năm 2011

NHIỆM VỤ LUẬN VĂN THẠC SĨ
Họ tên học viên: Võ Đình Quang ............................... Phái: Nam ................................
Ngày, tháng, năm sinh: 29/03/1984 ........................... Nơi sinh: Nghệ An ...................
Chuyên ngành: Khoa học máy tính ............................ MSHV: 00708207 ...................

I- TÊN ĐỀ TÀI:
PHÁT HIỆN BẤT THƯỜNG DỮ LIỆU CHUỖI THỜI GIAN SỬ DỤNG SUPPORT
VECTOR MACHINE.

II- NHIỆM VỤ VÀ NỘI DUNG:
-


Tìm hiểu phương pháp phát hiện bất thường cho dữ liệu chuỗi thời gian của các
tác giả J. Ma và S.Perkins

-

Nghiên cứu đề nghị phương pháp cải tiến cho phương pháp phát hiện bất
thường của J. Ma và S. Perkins

III- NGÀY GIAO NHIỆM VỤ: 25/01/2010
IV- NGÀY HOÀN THÀNH NHIỆM VỤ: 02/12/2010
V- CÁN BỘ HƢỚNG DẪN:
TS. Quản Thành Thơ

CÁN BỘ HƢỚNG DẪN

CN BỘ MÔN
QL CHUYÊN NGÀNH


Trang 4

Võ Đình Quang

LỜI CAM ĐOAN
Tơi cam đoan rằng, ngoại trừ các kết quả tham khảo từ các cơng trình nghiên cứu
khác nhƣ đã ghi rõ trong luận văn, các cơng việc trình bày trong luận văn này là do
chính tơi thực hiện và chƣa có phần nội dung của luận văn này đƣợc nộp để lấy một
bằng cấp ở trƣờng này hoặc trƣờng khác.
Ngày 01 tháng 12 năm 2010


Võ Đình Quang


Trang 5

Võ Đình Quang

LỜI CẢM ƠN
Tơi xin gửi lời cảm ơn chân thành và sâu sắc nhất đến TS. Quản Thành Thơ, ngƣời
thầy đã tận tình hƣớng dẫn và tạo mọi điều kiện để tơi có thể hồn thành tốt luận
văn này.
Tơi xin cảm ơn gia đình đã động viên và tạo mọi điều kiện tốt nhất có thể để tôi tiếp
tục theo đuổi việc học tập nghiên cứu. Tôi trân trọng dành tặng những thành quả
này cho cha, mẹ. Nhờ công lao dƣỡng dục của cha, mẹ mà con mới có đƣợc thành
quả của ngày hơm nay.


Trang 6

Võ Đình Quang

TĨM TẮT LUẬN VĂN
Phát hiện bất thƣờng cho dữ liệu chuỗi thời gian là một ứng dụng có tính thực tế
cao. Phát hiện bất thƣờng cho dữ liệu chuỗi thời gian sử dụng Support Vector
Machine (SVM) là một phƣơng pháp có tốc độ phát hiện nhanh.
Luận văn này nghiên cứu việc áp dụng phƣơng pháp Support Vector Machine để
phát hiện bất thƣờng cho chuỗi dữ liệu thời gian, mà cụ thể là phƣơng pháp SVM
một lớp. Luận văn nghiên cứu nhằm cải tiến phƣơng pháp phát hiện bất thƣờng của
J. Ma và S. Perkins bằng việc áp dụng phƣơng pháp thu giảm số chiều APCA, và

tìm kiếm tham số tốt nhất trong tập tham số của phƣơng pháp SVM một lớp.
Nghiên cứu thực nghiệm cho thấy việc áp dụng phƣơng pháp thu giảm số chiều
APCA không đạt hiệu quả tốt trên nhiều tập dữ liệu, và việc tìm kiếm tham số địi
hỏi lựa chọn tập dữ liệu huấn luyện cẩn thận thì kết quả phân loại mới đạt hiệu quả
tốt.


Trang 7

Võ Đình Quang

MỤC LỤC
CHƢƠNG 1. GIỚI THIỆU ĐỀ TÀI ........................................................................1
1.1.

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

1.2.

Phát hiện bất thƣờng cho dữ liệu chuỗi thời gian ..............................1

1.3.

Nội dung và giới hạn đề tài ................................................................4

1.4.

Tóm tắt kết quả đã đạt đƣợc ...............................................................4

1.5.


Cấu trúc của luận văn .........................................................................5

CHƢƠNG 2. NHỮNG CƠNG TRÌNH LIÊN QUAN .............................................6
2.1.

Phát hiện bất thƣờng với Support Vector Machine một lớp ..............6

2.1.1.

Phƣơng pháp Support Vector Machine một lớp ................................6

2.1.2.

Phát hiện bất thƣờng với SVM một lớp .............................................6

2.2.

Phát hiện bất thƣờng dữ liệu chuỗi thời gian với SVM một lớp ........6

2.3.

Rời rạc hóa và biểu diễn dữ liệu chuỗi thời gian ...............................7

2.3.1.

Phƣơng pháp biến đối Furier rời rạc (DFT) .......................................8

2.3.2.


Phƣơng pháp biến đổi Wavelet rời rạc (DWT) ..................................8

2.3.3.

Phƣơng pháp phân rã giá trị riêng (SVD) ..........................................9

2.3.4.

Phƣơng pháp xấp xỉ gộp từng đoạn (PAA) ......................................10

2.3.5.

Phƣơng pháp xấp xỉ từng đoạn thích nghi (APCA) .........................10

2.3.6.

Phƣơng pháp xấp xỉ tuyến tính từng đoạn (PLA) ............................11

2.3.7.

Phƣơng pháp xấp xỉ gộp kí hiệu hóa (SAX) ....................................12

2.3.8.

Phƣơng pháp cây hậu tố (Suffix Tree) .............................................12

2.3.9.

Phƣơng pháp vector lƣợng tử (VQ) .................................................13


2.4.

Kết luận ............................................................................................13

CHƢƠNG 3. CƠ SỞ LÝ THUYẾT NỀN TẢNG .................................................14
3.1.

Biểu diễn dữ liệu chuỗi thời gian .....................................................14

3.2.

Phát hiện bất thƣờng dữ liệu chuỗi thời gian với SVM một lớp ......14

3.2.1.

Vector hóa dữ liệu chuỗi thời gian ...................................................15


Trang 8

Võ Đình Quang

3.2.2.

Phƣơng pháp SVM một lớp .............................................................16

3.2.3.

Phát hiện bất thƣờng.........................................................................18


3.2.4.

Lựa chọn tham số .............................................................................20

CHƢƠNG 4. HỆ THỐNG PHÁT HIỆN BẤT THƢỜNG ....................................22
4.1.

Giới thiệu ..........................................................................................22

4.2.

Quy trình thực hiện ..........................................................................22

4.3.

Lựa chọn tham số .............................................................................24

4.4.

Thu giảm số chiều dữ liệu ................................................................25

4.5.

Vector hóa dữ liệu ............................................................................27

4.6.

Phát hiện bất thƣờng.........................................................................27

CHƢƠNG 5. THỰC NGHIỆM ..............................................................................29

5.1.

Các tiêu chuẩn thực nghiệm .............................................................29

5.2.

Đánh giá kết quả thực nghiệm .........................................................29

5.2.1.

Áp dụng phƣơng pháp APCA vào phát hiện bất thƣờng .................30

5.2.2.

Áp dụng phƣơng pháp chiếu dữ liệu ................................................32

5.2.3.

Lựa chọn tham số .............................................................................34

5.3.

Kết luận ............................................................................................36

CHƢƠNG 6. KẾT LUẬN ......................................................................................37
6.1.

Tổng kết............................................................................................37

6.2.


Những đóng góp của luận văn .........................................................37

6.3.

Hƣớng phát triển ..............................................................................38


Trang 9

Võ Đình Quang

DANH SÁCH HÌNH ẢNH
Hình 1.1: Đƣờng cong biểu diễn dữ liệu chuỗi thời gian và chuỗi thời gian
có chứa bất thƣờng x2(t) ................................................................................ 3
Hình 2.1: Các phƣơng pháp biểu diễn dữ liệu DFT, DWT, SVD ............................... 10
Hình 2.2: Các phƣơng pháp biểu diễn dữ liệu APCA, PAA, PLA ............................. 12
Hình 3.1: Chuỗi dữ liệu thời gian và những vector trong khơng gian pha
chiếu với kích thƣớc nhúng E=3. ................................................................ 16
Hình 3.2: Áp dụng phƣơng pháp SVM một lớp trong thực tế .................................... 16
Hình 4.1: Quy trình thực hiện của hệ thống ................................................................ 23


Trang 10

Võ Đình Quang

DANH SÁCH CÁC BẢNG
Bảng 5.1. Bảng so sánh độ chính xác (R) và thời gian (T) theo giây giữa
phƣơng pháp không sử dụng APCA và sử dụng APCA ở kích

thƣớc thu giảm cịn lại là 800, 400. ............................................................. 31
Bảng 5.2. Bảng so sánh độ chính xác(R) và thời gian (T) theo giây khi sử
dụng chiếu và không sử dụng chiếu lên khơng gian con vng góc
với đƣờng chéo đơn vị. ................................................................................ 33
Bảng 5.3. Bảng so sánh độ chính xác (R) của phƣơng pháp phát hiện bất
thƣờng với các tham số thu đƣợc từ 2 phƣơng pháp lựa chọn tham
số. ................................................................................................................. 35


Trang 1

Võ Đình Quang

CHƢƠNG 1. GIỚI THIỆU ĐỀ TÀI
1.1. Dữ liệu chuỗi thời gian
Dữ liệu chuỗi thời gian xuất hiện trong nhiều ứng dụng, các cơng trình nghiên cứu,
và ngày càng đƣợc quan tâm hơn.
Dữ liệu chuỗi thời gian là tập hợp các quan sát tuần tự theo thời gian. Dữ liệu có thể
có hai hay nhiều chiều, và có một chiều là chiều thời gian. Trong thực tế, có rất
nhiều dữ liệu có yếu tố thời gian nhƣ dữ liệu chứng khoán, điện tâm đồ, mức độ
rung động của cầu, … Dữ liệu thời gian thƣờng rất lớn, và có thể chứa nhiều nhiễu.
Trong thực tế, nhiều ứng dụng đặt ra cho chuỗi dữ liệu thời gian nhƣ gom cụm,
phân loại, phát hiện bất thƣờng… Trong đó, phát hiện bất thƣờng cho một chuỗi dữ
liệu thời gian có rất nhiều ứng dụng thực tế. Trong một bệnh viện, phát hiện đƣợc
bất thƣờng khi theo dõi chuỗi dữ liệu điện tâm đồ một cách tự động rất có hữu ích.
Từ một chuỗi dữ liệu chứng khốn, tài chính rất lớn, phát hiện ra những điểm bất
thƣờng có thể sẽ giúp ích cho việc dự báo, ứng phó với các sự cố. Việc theo dõi
rung động và phát hiện bất thƣờng nhằm chuẩn đốn hỏng hóc cho các hệ thống
máy móc, cầu đƣờng cũng là những ứng dụng thực tế…


1.2. Phát hiện bất thƣờng cho dữ liệu chuỗi thời gian
Dữ liệu thời gian đƣợc gọi là bất thƣờng khi nó chênh lệch (hay khác biệt) với dữ
liệu “trung bình”. Nó có thể là một điểm bất thƣờng hay một đoạn bất thƣờng.
Nghiên cứu phƣơng pháp để phát hiện bất thƣờng trong dữ liệu chuỗi thời gian hiện
đang đƣợc quan tâm và nghiên cứu rất nhiều. Việc phát hiện bất thƣờng trong chuỗi
dữ liệu thời gian có thể đƣợc xem nhƣ việc phân loại chuỗi dữ liệu thời gian. Dữ
liệu chuỗi thời gian sau khi đƣợc rời rạc hóa sẽ đƣợc phân vào một trong hai loại:
dữ liệu bình thƣờng, và dữ liệu bất thƣờng. Dữ liệu bất thƣờng đơi khi cịn đƣợc
xem là các điểm ngoại vi (outlier). Việc phân loại dữ liệu này có thể liên quan đến
việc xem xét độ tƣơng tự của các mẩu dữ liệu thời gian đã đƣợc rời rạc hóa này. Dữ

Phát hiện bất thường dữ liệu chuỗi thời gian sử dụng Support Vector Machine


Trang 2

Võ Đình Quang

liệu thời gian thƣờng rất lớn, trƣớc khi phân loại dữ liệu, dữ liệu rời rạc hóa có thể
đƣợc thu giảm số chiều để làm tăng tốc độ, nhƣng sẽ giảm đi độ chính xác của việc
phân loại.
Nhiều phƣơng pháp phát hiện bất thƣờng đã đƣợc đƣa ra. Một số phƣơng pháp giả
định đã có mơ hình lý thuyết chính xác của bài tốn (phƣơng pháp sử dụng mạng
neural do R. Kozma, M. Kitamura, M. Sakuma, và Y. Yokoyama đề nghị [3]), hay
giả định biết trƣớc điều kiện bất thƣờng (phƣơng pháp xác định lỗi do R. Isermann
đề nghị [18], phƣơng pháp phát hiện bất thƣờng sử dụng mạng neural của C. M.
Bishop [4], hay phƣơng pháp sử dụng mạng cấp phát tài nguyên có xác xuất của S.
Roberts và L. Tarassenko [5]). Tuy nhiên các điều kiện giả định này thƣờng khơng
có thực trong các bài toán thực tế. C. Shahabi, X. Tian, và W. Zhao đề nghị phƣơng
pháp phát hiện hƣớng chuyển dịch tín hiệu dựa trên tín hiệu wavelet [19]. Nhƣng

phƣơng pháp này khơng thể phát hiện đƣợc các mẩu bất thƣờng ngắn lẫn trong tín
hiệu bình thƣờng. Mingwei Leng, Xinsheng Lai, Guolv Tan, và Xiaohui Xu đã đề
nghị một phƣơng pháp biểu diễn chuỗi thời gian sử dụng các điểm quan trọng (key
point) để phân đoạn, sau đó đo độ bất thƣờng dựa vào độ tƣơng tự giữa các mẫu. D.
Dasgupta và S. Forrest lấy ý tƣởng từ hệ miễn dịch, đề nghị phƣơng pháp sử dụng
giải thuật phủ định lựa chọn (negative-selection) để phát hiện bất thƣờng cho chuỗi
thời gian [2]. E. Keogh và các cộng sự đã đề nghị phƣơng pháp TARZAN năm
2002 [20], dựa trên việc chuyển dữ liệu về chuỗi ký tự. Tuy nhiên việc mã hóa
chuỗi thời gian theo cách này có thể làm mất các điểm có ý nghĩa trong dữ liệu ban
đầu. Một số phƣơng pháp khác nhƣ sử dụng Support vector machines (SVM) phân
loại một lớp (của các tác giả B. Scholkopf, R.C. Williamson, A.J. Smola, J. ShaweTaylor, và J. Platt [6], và sau đó là J. Ma và S. Perkins [1]), hay sử dụng quy hoạch
tuyến tính (do các tác giả C. Campbell và K. P. Bennett để nghị [11]) thì xem các
điểm bất thƣờng nhƣ các điểm ngoại biên của sự phân bố dữ liệu. Ý tƣởng này có
nền tảng lý thuyết khá tốt. Trong các phƣơng pháp sử dụng SVM này thì phƣơng
pháp của các tác giả J. Ma và S. Perkins là phƣơng pháp chạy tƣơng đối nhanh, độ
chính xác khá cao.

Phát hiện bất thường dữ liệu chuỗi thời gian sử dụng Support Vector Machine


Trang 3

Võ Đình Quang

Nhìn chung, các phƣơng pháp bất thƣờng trên đều trên cơ sở bắt đầu từ “chuẩn hóa”
dữ liệu chuỗi thời gian (biến đổi dữ liệu sang một dạng thích hợp, chẳng hạn sử
dụng các phƣơng pháp thu giảm số chiều) và phân đoạn dữ liệu, sau đó phân loại dữ
liệu. Các đoạn dữ liệu chuỗi thời gian này sẽ đƣợc phân vào 2 loại: dữ liệu bình
thƣờng, và dữ liệu bất thƣờng (dữ liệu mới lạ, hay dữ liệu ngoại biên).
Và hiện nay, phƣơng pháp SVM đƣợc xem là một phƣơng pháp tốt, có tốc độ cao

để phân loại dữ liệu so với các phƣơng pháp khác. Phƣơng pháp SVM tỏ ra hiệu
quả hơn so với các phƣơng pháp nhƣ phân loại dựa trên xác xuất Bayes (đòi hỏi dữ
liệu huấn luyện rất lớn), sử dụng mạng neural (khá phức tạp, nhạy cảm với dữ liệu),
sử dụng cây quyết định (dựa trên lý thuyết xác suất và lý thuyết thơng tin, cũng địi
hỏi dữ liệu huấn luyện rất lớn). Tuy nhiên phƣơng pháp SVM chỉ áp dụng cho dữ
liệu vector.
Do đó, một phƣơng pháp có thể tốt để phát hiện bất thƣờng cho dữ liệu chuỗi thời
gian là “chuẩn hóa” và vector hóa dữ liệu sau đó áp dụng phƣơng pháp SVM để
phân loại dữ liệu thành 2 nhóm: một nhóm dữ liệu bình thƣờng, và nhóm dữ liệu bất
thƣờng.

Hình 1.1: Đường cong biểu diễn dữ liệu chuỗi thời gian và chuỗi thời gian có chứa
bất thường x2(t)

Phát hiện bất thường dữ liệu chuỗi thời gian sử dụng Support Vector Machine


Trang 4

Võ Đình Quang

1.3. Nội dung và giới hạn đề tài
Phƣơng pháp sử dụng SVM để phát hiện bất thƣờng cho dữ liệu chuỗi thời gian đã
đƣợc một số tác giả nghiên cứu và đề nghị (nhƣ phần trƣớc đã nêu).
Phƣơng pháp phát hiện bất thƣờng do J. Ma và S. Perkins đề nghị là một phƣơng
pháp đáng chú ý. Phƣơng pháp này dùng cửa sổ trƣợt phân dữ liệu thành từng đoạn
có kích thƣớc bằng nhau (bằng số chiều của vector trong không gian pha – phase
space) rồi vector hóa đoạn đó, rồi áp dụng phƣơng pháp SVM một lớp để xác định
các điểm ngoại biên. Sau đó, giải thuật lần lƣợt thay đổi kích thƣớc đoạn (hay số
chiều của vector) theo những giá trị định trƣớc, rồi tổng hợp kết quả phân loại ngoại

biên lại để xác định điểm ngoại biên thực sự. Đây là một phƣơng pháp khá tốt, mặc
dù vẫn cịn có một vài hạn chế.
Phƣơng pháp của các tác giả J. Ma và S. Perkins giả định dữ liệu đã đƣợc rời rạc
hóa. Vì vậy, với dữ liệu chuỗi thời gian tƣơng tự (analog), trƣớc khi áp dụng
phƣơng pháp này, cần đƣợc rời rạc hóa.
Phƣơng pháp của tác giả này chƣa sử dụng các phƣơng pháp tìm tham số tối ƣu cho
phƣơng pháp SVM với tập dữ liệu xác định nên chƣa đạt độ chính xác cao. Ta có
thể áp dụng phƣơng pháp tìm tham số tối ƣu cho phƣơng pháp SVM. Với những
tham số tối ƣu này, việc phát hiện bất thƣờng sẽ đạt độ chính xác cao hơn.
Ngồi ra, phƣơng pháp của các tác giả này chỉ đề cập đến việc phân loại cho dữ liệu
1D (dữ liệu chuỗi thời gian chỉ có 2 chiều, một chiều là chiều thời gian). Do đó, khi
áp dụng phƣơng pháp này cho dữ liệu nhiều chiều hơn, cần phải có một số thay đổi
nhỏ khi sử dụng.
Do đó, mục tiêu của đề tài này là nghiên cứu và đƣa ra một cải tiến nhƣ đã nói ở
trên có thể làm tăng hiệu năng của phƣơng pháp do các tác giả J. Ma và S. Perkins
đề nghị.

1.4. Tóm tắt kết quả đã đạt đƣợc
Với những yêu cầu của luận văn, sau thời gian nghiên cứu và thực hiện, tôi đã hiện
thực một hệ thống phát hiện bất thƣờng sử dụng Support Vector Machine đơn giản.

Phát hiện bất thường dữ liệu chuỗi thời gian sử dụng Support Vector Machine


Trang 5

Võ Đình Quang

Hệ thống này áp dụng phƣơng pháp phát hiện bất thƣờng của J. Ma và S. Perkins
cho dữ liệu chuỗi thời gian nhiều chiều (không kể chiều thời gian).

Hệ thống sử dụng thƣ việc Support Vector Machine SVM.NET, phiên bản .NET do
Matthew Johnson chuyển đổi từ phiên bản thƣ viện libSVM 2.89 của Chih-Chung
Chang and Chih-Jen Lin.
Khi phát hiện bất thƣờng, hệ thống có thể đƣợc chỉ định để áp dụng phƣơng pháp
thu giảm số chiều APCA cho tập dữ liệu chuỗi thời gian nhiều chiều (không kể
chiều thời gian) trƣớc khi tìm kiếm bất thƣờng. Hệ thống cũng hỗ trợ tìm kiếm tham
số tƣơng đối tốt cho phƣơng pháp Support Vector Machine ứng với tập huấn luyện
xác định.

1.5. Cấu trúc của luận văn
Phần còn lại của luận văn đƣợc tổ chức theo cấu trúc sau:
Chƣơng 2 trình bày tổng quan về các cơng trình liên quan. Các cơng trình này
nghiên cứu về các phƣơng pháp rời rạc hóa và thu giảm số chiều cho dữ liệu chuỗi
thời gian. Ngồi ra, cịn có cơng trình nghiên cứu về việc áp dụng phƣơng pháp
Support Vector Machine trong việc phát hiện bất thƣờng cho dữ liệu vector và dữ
liệu chuỗi thời gian.
Chƣơng 3 trình bày các cơ sở lý thuyết đƣợc sử dụng trong luận văn: biểu diễn
chuỗi dữ liệu, vector hóa dữ liệu chuỗi thời gian, phƣơng pháp sử dụng Support
Vector Machine một lớp để phát hiện bất thƣờng cho dữ liệu chuỗi thời gian, và
phƣơng pháp tìm kiếm tham số tối ƣu cục bộ cho phƣơng pháp SVM một lớp.
Chƣơng 4 trình bày hệ thống phát hiện bất thƣờng cho dữ liệu chuỗi thời gian sử
dụng SVM một lớp, bao gồm quy trình thực hiện và những phần chính trong hệ
thống: vector hóa dữ liệu, thu giảm số chiều, lựa chọn tham số và phát hiện bất
thƣờng cho dữ liệu.
Chƣơng 5 sẽ trình bày về các kết quả thực nghiệm và đánh giá các kết quả đó.
Chƣơng 6 là kết luận sau khi thực hiện luận văn.

Phát hiện bất thường dữ liệu chuỗi thời gian sử dụng Support Vector Machine



Trang 6

Võ Đình Quang

CHƢƠNG 2. NHỮNG CƠNG TRÌNH LIÊN QUAN
2.1. Phát hiện bất thƣờng với Support Vector Machine một lớp
2.1.1. Phương pháp Support Vector Machine một lớp
Phƣơng pháp Support Vector Machine (SVM) một lớp đƣợc các tác giả B.
Scholkopf, A. Smola, R. C. Williamson và P. L. Bartlett đƣa ra vào năm 2000 [21].
Đây là một phƣơng pháp SVM mới, cho phép phân loại dữ liệu theo “biên mềm”,
có khả năng chịu đựng nhiễu (lỗi).

2.1.2. Phát hiện bất thường với SVM một lớp
Các tác giả B. Scholkopf, R. C. Williamson, J. Shawe-Taylor và J. Platt đề nghị
phƣơng pháp sử dụng SVM một lớp để phát hiện bất thƣờng cho dữ liệu vào năm
2000 [6].
Dữ liệu ban đầu là một tập các vector. Phƣơng pháp SVM một lớp đƣợc sử dụng để
phân tập dữ liệu ra thành 2 phần: Một phần nhỏ chứa phần lớn dữ liệu, đƣợc xem là
bình thƣờng, và phần cịn lại chứa một số ít dữ liệu đƣợc coi là bất thƣờng.
Phƣơng pháp này có tốc độ, và độ chính xác khá cao, nhƣng địi hỏi phải xác định
kernel và tham số v thích hợp với loại dữ liệu tƣơng ứng.
Ngồi ra, phƣơng pháp này chỉ có thể áp dụng cho dữ liệu dạng vector, nên không
thể áp dụng trực tiếp lên dữ liệu chuỗi thời gian.

2.2. Phát hiện bất thƣờng dữ liệu chuỗi thời gian với SVM một
lớp
Năm 2003, các tác giả Junshui Ma và Simon Perkins đƣa ra phƣơng pháp áp dụng
SVM một lớp để phát hiện bất thƣờng cho dữ liệu chuỗi thời gian.
Phƣơng pháp SVM chỉ hoạt động trên dữ liệu vector, do vậy, để áp dụng phƣơng
pháp SVM cho dữ liệu chuỗi thời gian thì cần phải vector hóa dữ liệu chuỗi thời

gian. Các tác giả này đã đề nghị phƣơng pháp trải dữ liệu vào không gian pha sử
dụng nhúng trễ thời gian cho dữ liệu chuỗi thời gian để vector hóa dữ liệu. Dữ liệu

Phát hiện bất thường dữ liệu chuỗi thời gian sử dụng Support Vector Machine


Trang 7

Võ Đình Quang

đã vector hóa sẽ mất tính phân bố đồng nhất và độc lập (independent and identically
distributed – i.i.d). Điều này có thể dẫn đến đánh mất một số thuộc tính cho kết quả
bất thƣờng phát hiện đƣợc nhƣ biên hiệu suất đúng xấp xỉ xác suất (PAC
performance bound). Tuy nhiên việc áp dụng SVM một lớp phát hiện bất thƣờng
trên dữ liệu vector hóa này khơng bị ảnh hƣởng, do phƣơng pháp SVM một lớp
không dựa trên giả thiết dữ liệu phân bố đồng nhất và độc lập.
Ngồi ra, đối với một số loại dữ liệu có tần số thấp, các vector sau khi vector hóa sẽ
có xu hƣớng phân bố quanh đƣờng chéo đơn vị. Khi đó, kết quả phát hiện bất
thƣờng sẽ thiên về những điểm dữ liệu thời gian có giá trị cách biệt lớn (đặc biệt lớn
hay đặc biệt nhỏ). Mặc dù các điểm này không phải luôn luôn là giá trị bất thƣờng.
Vì thế, các tác giả đề nghị chiếu dữ liệu đã vector hóa lên khơng gian con vng
góc với vector đƣờng chéo đơn vị. Việc này cũng tƣơng tự nhƣ áp dụng bộ lọc cho
phép băng tần cao lên dữ liệu thời gian (nhƣng không cần xác định tham số nhƣ đối
với bộ lọc thực sự).
Dữ liệu chuỗi thời gian sẽ đƣợc vector hóa theo nhiều kích thƣớc nhúng khác nhau.
Sau đó sử dụng SVM một lớp để phát hiện ra các điểm ngoại vi ở từng kích thƣớc
nhúng rồi kết hợp các kết quả này lại để ra đƣợc kết quả cuối cùng.
Phƣơng pháp phát hiện bất thƣờng này có ƣu điểm là tốc độ và độ chính xác cao khi
đã xác định đƣợc tham số thích hợp cho SVM một lớp ứng với dữ liệu cụ thể.
Tuy nhiên, các tác giả chƣa đƣa ra một phƣơng pháp xác định tham số thích hợp

cho SVM một lớp. Bên cạnh đó, các tác giả cũng chƣa đƣa ra phƣơng pháp chọn
các kích thƣớc nhúng thích hợp để tránh phát hiện sai mà vẫn giữ đƣợc tốc độ phát
hiện.

2.3. Rời rạc hóa và biểu diễn dữ liệu chuỗi thời gian
Dữ liệu chuỗi thời gian thƣờng rất lớn dẫn đến chi phí cao trong việc xử lý trên dữ
liệu thơ. Do đó, các cơng trình về chuỗi thời gian cố gắng biểu diễn chuỗi dữ liệu
dƣới dạng khác nhằm thu giảm kích thƣớc dữ liệu và nâng cao hiệu năng tính tốn,
xử lý. Ngồi ra, dữ liệu chuỗi thời gian cũng có thể đƣợc rời rạc hóa và mã hóa

Phát hiện bất thường dữ liệu chuỗi thời gian sử dụng Support Vector Machine


Trang 8

Võ Đình Quang

thành các chuỗi bit hay chuỗi kí tự để dễ dàng sử dụng các kỹ thuật nén, khai phá
dữ liệu trên dữ liệu chuỗi bit, hay chuỗi kí tự.
Bên cạnh đó, biễu diễn dữ liệu chuỗi thời gian ở một dạng thích hợp có thể giúp ích
cho việc phát hiện bất thƣờng dữ liệu chuỗi thời gian. Dữ liệu chuỗi thời gian đƣợc
biến đổi, biểu diễn ở một dạng thích hợp có thể giúp phát bất thƣờng hiện nhanh,
chính xác hơn khi áp dụng phƣơng pháp phát hiện bất thƣờng với SVM. Tuy nhiên,
việc lựa chọn đƣợc dạng biểu diễn thích hợp là rất khó.
Phƣơng pháp thu giảm số chiều là phƣơng pháp biểu diễn dữ liệu chuỗi thời gian ở
một dạng nén. Phƣơng pháp này cho phép chuỗi n chiều X = {x1, x2, …, xn} có thể
đƣợc biểu diễn và lƣu trữ thành chuỗi k chiều Y = {y1, y2, …, yk}, với k < n. Từ
chuỗi Y, ta có thể khơi phục lại chuỗi n chiều X ban đầu. Nhƣ vậy, thay vì tính tốn
trên chuỗi n chiều X, ta chỉ cần tính tốn trên chuỗi k chiều Y.


2.3.1. Phương pháp biến đối Furier rời rạc (DFT)
Phƣơng pháp biến đổi Furier rời rạc (Discrete Fourier Transform – DFT) do R.
Agrawal và cộng sự đề nghị năm 1993. Trong phƣơng pháp này, đƣờng dữ liệu ban
đầu đƣợc biểu diễn bởi các đƣờng cơ bản, những đƣờng cơ bản trong trƣờng hợp
này là đƣờng sin và cosin

Phƣơng pháp này có khả năng nén và chịu nhiễu tốt, và có thể so sánh gián tiếp 2
chuỗi X, Y thông qua 2 chuỗi đã đƣợc biến đổi Xf, Yf, do D(X, Y) ≥ αD(Xf, Yf),
trong đó α là hằng số. Tuy nhiên, phƣơng pháp này khó giải quyết khi các đƣờng
biểu diễn có chiều dài khác nhau. Phƣơng pháp này có độ phức tạp O(nlgn), với n là
số lƣợng điểm.

2.3.2. Phương pháp biến đổi Wavelet rời rạc (DWT)
Phƣơng pháp biến đổi Wavelet rời rạc (Discrete Walet Transform – DWT) do K.
Chan và cộng sự đề nghị năm 1999. Phƣơng pháp này biểu diễn chuỗi thời gian
thành các đƣờng Haar cơ bản. Đƣờng Haar đƣợc định nghĩa theo công thức:

Phát hiện bất thường dữ liệu chuỗi thời gian sử dụng Support Vector Machine


Trang 9

Võ Đình Quang

Trong đó:

Phƣơng pháp này có độ phức tạp tuyến tính, khả năng khử nhiễu cao, thíc hợp với
những dữ liệu tĩnh, ít thay đổi do đƣờng Haar cũng không thay đổi liên tục. Tuy
nhiên, phƣơng pháp này đòi hỏi chiều dài chuỗi dữ liệu ban đầu vào chuỗi truy vẫn
phải là một số lũy thừa của 2.


2.3.3. Phương pháp phân rã giá trị riêng (SVD)
Phƣơng pháp phân rã giá trị riêng (Singular Value Decomposition – SVD) do F.
Korn và cộng sự đề xuất năm 1997. Phƣơng pháp này biểu diễn chuỗi thời gian
thành các đƣờng eigenwave. Việc xác định đƣờng eigenwave dựa vào giá trị riêng
và vector riêng của ma trận Dm×n với m là tập các chuỗi thời gian, n là số chiều. Mỗi
tập dữ liệu khác nhau có các đƣờng eigenwave khác nhau.
Phƣơng pháp này cho phép thấy đƣợc hình dạng dữ liệu, và hỗ trợ truy vẫn ngẫu
nhiên. Tuy nhiên, độ phức tạp của giải thuật này cao, và phải chạy lại giải thuật khi
chỉnh sửa tập dữ liệu.

Phát hiện bất thường dữ liệu chuỗi thời gian sử dụng Support Vector Machine


Trang 10

Võ Đình Quang

Hình 2.1: Các phương pháp biểu diễn dữ liệu DFT, DWT, SVD

2.3.4. Phương pháp xấp xỉ gộp từng đoạn (PAA)
Phƣơng pháp xấp xỉ gộp từng đoạn (Piecewise Aggregate Approximation – PAA)
do E. Keogh và cộng sự đề nghị năm 2000. Phƣơng pháp này tuần tự xấp xỉ k giá trị
liền kề nhau thành cùng một giá trị bằng trung bình cộng của k điểm đó. Kết quả
cuối cùng là một đƣờng có dạng bậc thang.
Phƣơng pháp này có thời gian tính tốn nhanh, hỗ trợ dạng truy vẫn có chiều dài
khác nhau. Tuy nhiên, phƣơng pháp này khó xây dựng lại chuỗi ban đầu và sinh lỗi
lớn. Ngồi ra, phƣơng pháp này khơng quan tâm đến những điểm đặc biệt(điểm giá
trị nhỏ nhất, lớn nhất, …) trong từng đoạn xấp xỉ.


2.3.5. Phương pháp xấp xỉ từng đoạn thích nghi (APCA)
Phƣơng pháp xấp xỉ từng đoạn thích nghi (Adaptive Piecewise Constant
Approximation – APCA) do E. Keogh và cộng sự đề xuất năm 2001. Tƣơng tự
phƣơng pháp PAA, APCA xấp xỉ dữ liệu thành những đoạn thẳng nằm ngang. Tuy

Phát hiện bất thường dữ liệu chuỗi thời gian sử dụng Support Vector Machine


Trang 11

Võ Đình Quang

nhiên, khác với PAA là các đoạn có kích thƣớc bằng nhau, phƣơng pháp này xấp xỉ
thành những đoạn có kích thƣớc khác nhau. Những thời điểm giá trị dao động nhiều
đƣợc biểu diễn bởi những phân đoạn dữ liệu ngắn, những thời điểm giá trị ít dao
động đƣợc biểu diễn bởi những phân đoạn dài.
Phƣơng pháp này có tỉ lệ nén cao hơn phƣơng pháp PAA, tỉ lệ lỗi khi xây dựng lại
dữ liệu gốc thấp hơn phƣơng pháp PAA. Độ phức tạp của giải thuật này là
O(nlogn).

2.3.6. Phương pháp xấp xỉ tuyến tính từng đoạn (PLA)
Phƣơng pháp xấp xỉ tuyến tính từng đoạng (Piecewise Linear Approximation –
PLA) do E. Keogh và cộng sự đề nghị năm 1999. Phƣơng pháp này biểu diễn chuỗi
dữ liệu ban đầu thành các đoạn thẳng tuyến tính, có thể rời nhau hay liên tục.
Phƣơng pháp này có tính trực quan, tỉ lệ lỗi thấp khi xây dựng lại dữ liệu ban đầu.
Giải thuật tìm các chuỗi đoạn thẳng có thể đƣợc thực hiện trong thời gian tuyến
tính.
Ban đầu, phƣơng pháp này chỉ hiệu quả với dữ liệu offline. Nhƣng đến 2001, E.
Keogh và cộng sự đã đề nghị giải thuật phân đoạn cho dữ liệu trực tuyến (online).
sử dụng phƣơng pháp PLA và cửa sổ trƣợt có hiệu năng tƣơng tƣơng với giải thuật

cho dữ liệu offline.

Phát hiện bất thường dữ liệu chuỗi thời gian sử dụng Support Vector Machine


Trang 12

Võ Đình Quang

Hình 2.2: Các phương pháp biểu diễn dữ liệu APCA, PAA, PLA

2.3.7. Phương pháp xấp xỉ gộp kí hiệu hóa (SAX)
Phƣơng pháp xấp xỉ gộp kí hiệu hóa (Symbolic Aggregate approXimation) do J. Lin
và cộng sự đề xuất năm 2003. Dữ liệu ban đầu đƣợc chia thành từng đoạn theo
phƣơng pháp PAA. Sau đó dựa trên giá trị trung bình cộng của từng đoạn, ta sẽ biểu
diễn đặc trƣng của đoạn thành các kí tự. Chuỗi dữ liệu ban đầu đƣợc rời rạc và mã
hóa thành chuỗi ký tự.
Phƣơng pháp này hữu dụng trên tập dữ liệu lớn. Tuy nhiên, phƣơng pháp này lựa
chọn điểm ngắt để biểu diễn đặc trƣng dựa trên phân phối Gauss. Tuy nhiên, khơng
phải tất cả dữ liệu đều có phân phối Gauss, do đó, cần phải huấn luyện dữ liệu để
tìm các điểm ngắt thích hợp.

2.3.8. Phương pháp cây hậu tố (Suffix Tree)
Phƣơng pháp sử dụng cây hậu tố đƣợc S. Park và cộng sự đề nghị năm 2000.
Phƣơng pháp này rời rạc dữ liệu dựa vào sự phân loại dữ liệu. Sau đó dùng cây hậu
tố để đánh chỉ mục. Park đã đƣa ra 3 phƣơng pháp phân loại dữ liệu dựa trên:

Phát hiện bất thường dữ liệu chuỗi thời gian sử dụng Support Vector Machine



Trang 13

Võ Đình Quang

-

Khoảng cách phân loại bằng nhau (Equal Length Interval Categorization)

-

Giá trị hỗn độn thông tin lớn nhất (Maximum-Entropy Categorization)

-

Nhát cắt nhỏ nhất (Minimum-Cut Categorization)

2.3.9. Phương pháp vector lượng tử (VQ)
Phƣơng pháp vector lƣợng tử (Vector Quantization – VQ) do V. Megalooikonomou
và cộng sự đề xuất năm 2005. Phƣơng pháp này rút trích đặc trƣng của chuỗi bằng
vector lƣợng tử, mỗi phần tử của vector là từ mã (codeword). Tập các từ mã là sách
mã (codebook). Bài báo sử dụng giải thuật GLA (Generalized Lloyd Algorithm)
nhằm huấn luyện dữ liệu, tìm ra những từ mã đặc trƣng của dữ liệu, sau đó tính
khoảng cách dựa trên các thơng tin của từ mã nhƣ khoảng cách từ mã, chuỗi con từ
mã chung dài nhất, tần số xuất hiện của từ mã, …
Phƣơng pháp này hỗ trợ đa phân giải. Tuy nhiên thời gian huấn luyện dữ liệu lớn và
bị ảnh hƣởng bởi nhiễu cao

2.4. Kết luận
Phƣơng pháp SVM một lớp cho phép phát hiện bất thƣờng cho một tập dữ liệu
vector. Vì thế, khơng thể trực tiếp áp dụng phƣơng pháp SVM một lớp để phát hiện

bất thƣờng cho dữ liệu chuỗi thời gian.
Trƣớc khi áp dụng phƣơng pháp SVM một lớp cho việc phát hiện bất thƣờng, dữ
liệu chuỗi thời gian cần đƣợc biến đổi thành dữ liệu vector.
Ngoài ra, dữ liệu chuỗi thời gian thƣờng rất lớn, nên trƣớc khi tìm kiếm bất thƣờng
cho dữ liệu này, ta có thể áp dụng một số phƣơng pháp thu giảm số chiều mà không
làm mất những điểm dữ liệu bất thƣờng mong muốn. Nhƣ vậy, tốc độ phát hiện sẽ
đƣợc cải thiện. Tuy nhiên, ta còn cần nghiên cứu thêm để lựa chọn phƣơng pháp thu
giảm số chiều thích hợp. Nếu thu giảm số chiều khơng thích hợp có thể dẫn đến bỏ
sót các điểm bất thƣờng hoặc xác định thừa các điểm bất thƣờng.

Phát hiện bất thường dữ liệu chuỗi thời gian sử dụng Support Vector Machine


Trang 14

Võ Đình Quang

CHƢƠNG 3. CƠ SỞ LÝ THUYẾT NỀN TẢNG
3.1. Biểu diễn dữ liệu chuỗi thời gian
Dữ liệu chuỗi thời gian ban đầu là một chuỗi các điểm (một hay nhiều chiều) đƣợc
quan sát theo thời gian. Tập các điểm này thƣờng rất lớn, nên nếu tìm kiếm bất
thƣờng trực tiếp lên chuỗi dữ liệu này có thể tốn nhiều thời gian. Nếu có thể thu
giảm số chiều và biễu diễn dữ liệu chuỗi thời gian mà không làm mất đi các điểm,
mẩu (đoạn) dữ liệu bất thƣờng thì có thể giúp tìm kiếm bất thƣờng nhanh hơn. Tuy
nhiên, việc lựa chọn một dạng biễu diễn thích hợp cho một dữ liệu cụ thể là rất khó
khăn. Nếu lựa chọn dạng biểu diễn khơng thích hợp, có thể làm mất các điểm, mẩu
bất thƣờng trên dữ liệu.
Quá trình biến đổi dữ liệu thời gian về một dạng thích hợp cũng ảnh hƣởng đến tốc
độ phát hiện bất thƣờng cho dữ liệu. Nếu phƣơng pháp biến đổi quá phức tạp, thời
gian phát hiện bất thƣờng sẽ tăng đáng kể.

Do chƣa có phƣơng pháp xác định dạng biểu diễn thích hợp cho dữ liệu chuỗi thời
gian, nên ở đây tôi sẽ sử dụng thử một phƣơng pháp biểu diễn bất kỳ để thu giảm số
chiều cho dữ liệu. Cụ thể, phƣơng pháp xấp xỉ từng đoạn thích nghi (APCA) sẽ
đƣợc sử dụng.

3.2. Phát hiện bất thƣờng dữ liệu chuỗi thời gian với SVM một
lớp
Phƣơng pháp phát hiện bất thƣờng cho dữ liệu chuỗi thời gian sử dụng SVM một
lớp do các tác giả J. Ma và S. Perkins đề nghị có hiệu quả cao với nhiều loại dữ liệu.
Ở phƣơng pháp này, dữ liệu chuỗi thời gian sẽ đƣợc vector hóa ở nhiều kích thƣớc
nhúng khác nhau và sử dụng SVM một lớp để phát hiện bất thƣờng. Sau đó kết hợp
các kết quả này lại. Dữ liệu chuỗi thời gian đƣợc vector hóa bằng cách trải dữ liệu
vào khơng gian pha sử dụng nhúng trễ thời gian. Sau đó, các vector sẽ đƣợc biến

Phát hiện bất thường dữ liệu chuỗi thời gian sử dụng Support Vector Machine


Trang 15

Võ Đình Quang

đổi vào khơng gian chiếu (chiếu lên khơng gian con vng góc với vector đƣờng
chéo đơn vị).

3.2.1. Vector hóa dữ liệu chuỗi thời gian
Phƣơng pháp SVM một lớp chỉ có thể áp dụng trực tiếp lên dữ liệu vector để phát
hiện bất thƣờng. Do đó, dữ liệu chuỗi thời gian ban đầu cần phải đƣợc vector hóa
trƣớc khi sử dụng phƣơng pháp.
Các tác giả J. Ma và S. Perkins đã đề nghị phƣơng pháp vector hóa bằng cách đƣa
dữ liệu chuỗi thời gian vào không gian pha sử dụng nhúng trễ thời gian.

Giả sử chúng ta có dữ liệu chuỗi thời gian x(t), t=1..N. Khi đó, kết quả của việc
vector hóa một điểm dữ liệu này vào không gian E chiều sẽ là:
xE(t)=[x(t – E + 1) x(t – E + 2) … x(t)]
Và dữ liệu chuỗi thời gian x(t) ban đầu có thể chuyển thành một tập vector TE(N)
TE(N) = {xE(t), t = E..N}
Không gian của dữ liệu vector hóa này cịn đƣợc gọi là khơng gian pha (phase
space).
Dữ liệu sau khi vector hóa sẽ mất đi tính phân bố đồng nhất và độc lập (i.i.d).
Nhƣng điều này không ảnh hƣởng đến việc phát hiện bất thƣờng với phƣơng pháp
SVM một lớp, do phƣơng pháp này khơng dựa trên giả thiết dữ liệu có tính chất đó.
Tuy nhiên, trên thực tế, một số dữ liệu chuỗi thời gian bao gồm hầu hết các thành
phần có tần số thấp. Khi đó, dữ liệu vector hóa có xu hƣớng tập trung quanh vector
đƣờng chéo đơn vị 1 (I=[1 1 … 1]T). Việc áp dụng phƣơng pháp SVM phân loại
một lớp trên loại dữ liệu này sẽ đƣa ra kết quả các bất thƣờng là các điểm có giá trị
quá lớn hay quá nhỏ, mặc dù trong nhiều trƣờng hợp thì đó khơng phải là điểm bất
thƣờng. Vì thế cần phải chuẩn hóa dữ liệu trƣớc khi áp dụng phƣơng pháp SVM
phân loại một lớp.
Các tác giả đề nghị chiếu dữ liệu đã vector hóa vào khơng gian con vng góc với
vector đƣờng chéo đơn vị 1. Tuy nhiên tùy thuộc loại dữ liệu, có thể chiếu dữ liệu
lên một vector khác. Tuy không phải mọi dữ liệu đề có tính chất này, tuy nhiên
phƣơng pháp chuẩn hóa này rất hữu dụng trong nhiều bài tốn thực tế. Khơng gian

Phát hiện bất thường dữ liệu chuỗi thời gian sử dụng Support Vector Machine