HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
---------------------------------------

Huỳnh Cẩm

PHÁT HIỆN CHUỖI BẤT THƯỜNG TRÊN DỮ LIỆU
CHUỖI THỜI GIAN

Chuyên ngành: HỆ THỐNG THÔNG TIN
Mã số:

8480104

TÓM TẮT LUẬN VĂN THẠC SĨ

THÀNH PHỐ HỒ CHÍ MINH – 2018


Luận văn được hoàn thành tại:
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

Người hướng dẫn khoa học: TS. Dương Thị Thuỳ Vân
Phản biện 1: ...................................................................................................................
Phản biện 2: ...................................................................................................................

Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn thạc sĩ tại Học viện Công
nghệ Bưu chính Viễn thông
Vào lúc: ....... giờ ....... ngày ....... tháng 01 năm 2018

Có thể tìm hiểu luận văn tại:
- Thư viện của Học viện Công nghệ Bưu chính Viễn thông

1

MỞ ĐẦU
Dữ liệu chuỗi thời gian 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 đồ, 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 nhất trong lĩnh vực khai phá dữ liệu
và học máy được thực hiện vào năm 2006 bởi Yang và Wu [1] 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 điển hình trong khai phá dữ liệu chuỗi thời gian bao gồm: Lập chỉ mục
(Indexing), Gom cụm (Clustering), Phân lớp (Classificaition), Tổng hợp (Summarization),
Phát hiện Motif (Motif detection), Phát hiện chuỗi 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
học, 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 nghiên
cứu như y học và dịch vụ tài chính, … thường cần độ chính xác rất cao. Trong khi đó,
những chuỗi bất thường 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. Vì vậy việc xác định các chuỗ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 chuỗi thời gian. Sau đây là một số ứng dụng quan trọng của bài toán phát
hiện chuỗi bất thường trên dữ liệu chuỗi thời gian [2]:
-

Phát hiện bất thường của xung nhịp tim bằng dữ liệu điện tim ECG [3], [4]: 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 có thể chỉ ra rằng có vấn đề về sức khỏe.
-

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 tư vấn, gợi ý trong tương lai [5].

-

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 báy: 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


2

biến có chuỗi bất thường thì có thể hành vi hệ thống của chuyến bay có sai lệch, cần
cảnh báo [6].
-

Phát hiện bất thường về hình dạng: Tìm những hình dạng khác biệt với những hình
dạng khác, với mỗi hình dạng được chuyển thành một chuỗi thời gian [7], [8], [9].
Trong lĩnh vực khai phá dữ liệu y học, cho hình dạng của một số chủng loại, một hình
dạng khác với những hình dạng còn lại có thể cho thấy đó là một sự bất thường do
biến đổi gen tạo ra.

-

Phát hiện những đường cong ánh sáng bất thường trong danh mục các ngôi sao có độ

sáng biến đổi tuần hoàn: phát hiện những bất thường trong các ngôi sao có độ sáng
biến đổi tuần hoàn. Các bất thường tương ứng với một số khác biệt vật lý bên trong,
chẳng hạn như sự thay đổi về chu kỳ hoặc biên độ, thể hiện qua độ nhiễu trong đường
cong ánh sáng [10], [11].

-

Phát hiện thay đổi hệ sinh thái bằng cách sử dụng dữ liệu khoa học trái đất như sự sinh
trưởng của thực vật hay nhiệt độ [12].
Với những phân tích trên, bài toán phát hiện chuỗi bất thường đã thu hút được sự quan

tâm đáng kể của cộng đồng nghiên cứu từ thập niên 1980. Các nhóm nghiên cứu [13], [14],
[1], [15], [16], [17], [3], [4] đã định nghĩa nhiều loại chuỗi bất thường khác nhau như
outlier, anomaly, unusual, discord, … và đã đề xuất nhiều phương pháp phát hiện chuỗi bất
thường. Trong đó, phương pháp phát hiện chuỗi bất thường discord (discord discovery)
được Keogh et al. [14] giới thiệu từ năm 2005 và gần đây được các nhóm [18], [19], [20],
[17], [21], [22] tập trung nghiên cứu.
Luận văn này tập trung nghiên cứu các phương pháp phát hiện chuỗi bất thường trên
dữ liệu chuỗi thời gian. Từ đó, luận văn đề xuất một phương pháp phát hiện chuỗi bất
thường discord dựa vào cửa sổ trượt (Window).
Nội dung của luận văn bên cạnh phần mở đầu và kết luận được trình bày trong 03
chương, bao gồm:
Chương 1: Tổng quan
Chương này giới thiệu và khảo sát về dữ liệu chuỗi thời gian, bài toán phát hiện chuỗi
bất thường trên dữ liệu chuỗi thời gian, mục tiêu nghiên cứu, đối tượng nghiên cứu và phạm
vi nghiên cứu, phương pháp nghiên cứu và ý nghĩa khoa học và thực tiễn của đề tài.
Chương 2: Cơ sở lý thuyết


3


Chương này trình bày cơ sở lý thuyết của đề tài liên quan đến bài toán phát hiện chuỗi
bất thường trên dữ liệu chuỗi thời gian bao gồm thu giảm số chiều chuỗi thời gian, rời rạc
hóa chuỗi thời gian, các kỹ thuật phát hiện chuỗi bất thường.
Chương 3: Đề xuất giải thuật và thực nghiệm đánh giá
Chương này đề xuất một giải thuật phát hiện chuỗi bất thường dựa vào phương pháp
cửa sổ trượt, cài đặt giải thuật, xây dựng các tập dữ liệu kiểm thử, chạy thực nghiệm và
đánh giá kết quả thực nghiệm, so sánh kết quả thực nghiệm của giải thuật đề xuất với các
công trình liên quan.
Kết luận và hướng phát triển
Tổng kết những kết quả đạt được và những hạn chế của luận văn, đề xuất hướng phát
triển tương lai của đề tài.


4

CHƯƠNG 1 – TỔNG QUAN
1.1. Giới thiệu
1.1.1. Dữ liệu chuỗi thời gian
Dữ liệu chuỗi thời gian là một tập hợp các giá trị, được đo theo từng khoảng thời gian
liền nhau theo một trình tự thời gian nhất định. Ví dụ về chuỗi thời gian là: lưu lượng mưa
hàng năm ở Việt Nam, kết quả điện tâm đồ, thời tiết… Hình 1.1 minh họa một ví dụ về
chuỗi thời gian biểu diễn giá vàng thế giới ngày 05/07/2014.

Hình 1.1: Đường biểu diễn một chuỗi thời gian [22]

1.1.2. Các loại dữ liệu chuỗi thời gian
Hầu hết các kỹ thuật phát hiện chuỗi bất thường đều sử dụng dữ liệu chuỗi thời gian
huấn luyện để học mô hình và gán một số điểm bất thường cho chuỗi thời gian thử nghiệm
dựa trên mô hình. Hiệu suất của bất kỳ kỹ thuật phát hiện chuỗi bất thường nào cũng phụ

thuộc vào các đặc tính của dữ liệu chuỗi thời gian.
Chúng ta thảo luận hai đặc tính chính của dữ liệu chuỗi thời gian, bao gồm (1) tính tuần
hoàn và (2) tính đồng bộ. Sự kết hợp của hai đặc tính này sẽ cho ra bốn loại chuỗi thời gian
khác nhau.
-

Tuần hoàn và đồng bộ.

-

Không tuần hoàn và đồng bộ.

-

Tuần hoàn và không đồng bộ.


5

-

Không tuần hoàn và không đồng bộ.

1.1.3. Các bài toán trong dữ liệu chuỗi thời gian
Lập chỉ mục (Indexing): khi tìm kiếm chuỗi thời gian, kết quả hiển thị là chuỗi thời
gian tương tự nhất đã được lưu trữ trong cơ sở dữ liệu.
Gom cụm (Clustering): dựa vào một hàm tính độ đo tương tự, ta gom các cụm dữ liệu
vào từng nhóm phù hợp, mỗi cụm dữ liệu chỉ thuộc về một nhóm nào đó.
Phân lớp (Classificaition): đưa một dữ liệu chuỗi thời gian chưa được gán nhãn vào
một nhóm đã được gán nhãn trước.

Tổng hợp (Summarization): rút trích, tóm tắt những nội dung quan trọng nhất thành
một chuỗi mới ngắn gọn, cô đọng nhưng vẫn giữ nguyên bản chất.
Phát hiện Motif (Motif detection): tìm chuỗi con xuất hiện nhiều lần nhất trong dữ liệu
chuỗi thời gian.
Phát hiện bất thường (Anomaly detection): tìm chuỗi con khác biệt nhất trong dữ liệu
chuỗi thời gian.

1.2.

Tổng quan về bài toán phát hiện chuỗi bất thường
Dữ liệu chuỗi thời gian tồn tại trong nhiều ứng dụng thực tế, từ các lĩnh vực khoa học

kỹ thuật cho đến kinh tế, y tế, tài chính. Trong những ứng dụng này, việc tìm kiếm những
chuỗi con bất thường xuất hiện trong cơ sở dữ liệu chuỗi thời gian là một công việc rất cần
thiết. 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
một trong năm kỹ thuật sau đây:


Dựa vào cửa sổ trượt (Window based)



Dựa vào sự tương tự (Proximity based)



Dựa vào dự đoán (Prediction Based)




Dựa vào mô hình Markov ẩn (Hidden Markow Models Based)



Dựa vào phân đoạn (Segmentation Based)

1.3.

Những khó khăn và thách thức

1.3.1. Những thách thức khi nghiên cứu về dữ liệu chuỗi thời gian
 Dữ liệu thường rất lớn. Chẳng hạn, trong 1 giờ, dữ liệu điện tâm đồ (ECG) có thể
lên đến 1GB.


6

 Phụ thuộc nhiều vào yếu tố chủ quan của người dùng và tập dữ liệu khi đánh giá
mức độ tương tự giữa các chuỗi thời gian.
 Dữ liệu không đồng nhất: định dạng của dữ liệu khác nhau, tần số lấy mẫu khác
nhau. Ngoài ra, dữ liệu có thể bị nhiễu, thiếu một vài giá trị hoặc không sạch.

1.3.2. Những thách thức của bài toán phát hiện chuỗi bất thường
 Có nhiều loại bất thường trong dữ liệu chuỗi thời gian, bao gồm: một phần của
chuỗi thời gian là bất thường hoặc toàn bộ chuỗi thời gian là bất thường.
 Khó xác định chính xác độ dài của chuỗi con trong bài toán phát hiện chuỗi con bất
thường.
 Các chuỗi thời gian kiểm thử và chuỗi thời gian huấn luyện có thể có độ dài khác
nhau.

 Khó xác định các độ đo tương tự/khoảng cách tốt nhất có thể được sử dụng cho các
loại chuỗi thời gian khác nhau. Các độ đo đơn giản như khoảng cách Euclid luôn
luôn không hoạt động tốt vì chúng rất nhạy với những giá trị ngoại lệ và chúng cũng
không thể được sử dụng khi các chuỗi thời gian có độ dài khác nhau.
 Hiệu suất của nhiều thuật toán phát hiện bất thường trong dữ liệu chuỗi thời gian có
nhiễu thường rất thấp, độ nhiễu trong dữ liệu chuỗi thời gian là một thách thức lớn
đối với bài toán phát hiện chuỗi bất thường.
 Chuỗi thời gian trong các ứng dụng 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.

1.4.

Mục tiêu nghiên cứu
Mục tiêu chính của luận văn là nghiên cứu 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. Đề tài này dựa trên nghiên cứu của X. Zhao và cộng sự
đề xuất năm 2014 và giải thuật HOTSAX của E. Keogh và cộng sự đề xuất năm 2005 [14].
Mục tiêu đặt ra là phương pháp phát hiện bất thường được đề xuất trong luận văn có chi phí
thời gian thực thi và chi phí bộ nhớ khi chạy giải thuật giảm so với giải thuật HOTSAX.

1.5.

Đối tượng và phạm vi nghiên cứu

1.5.1. Đối tượng nghiên cứu:


7

Đối tượng nghiên cứu chính của luận văn là nghiên cứu phương pháp phát hiện bất

thường trên dữ liệu chuỗi thời gian. Để đạt được kết quả nghiên cứu, chúng tôi tiến hành
thực hiện các nội dung nghiên cứu sau:


Nghiên cứu về các phương pháp thu giảm số chiều chuỗi thời gian.



Nghiên cứu về các phương pháp rời rạc hóa dữ liệu chuỗi thời gian.



Nghiên cứu các kỹ thuật phát hiện chuỗi bất thường trên dữ liệu chuỗi thời gian.



Đề xuất phương pháp phát hiện chuỗi bất thường trên dữ liệu chuỗi thời gian dựa vào
cửa sổ trượt.



Thực nghiệm trên nhiều tập dữ liệu, so sánh và đánh giá kết quả thực nghiệm của giải
thuật đề xuất với giải thuật HOTSAX.

1.5.2. Phạm vi nghiên cứu:
Dữ liệu chuỗi thời gian có thể có hai hay nhiều chiều. Phạm vi nghiên cứu của luận
văn này là dữ liệu chuỗi thời gian có hai chiều, trong đó có một chiều là thời gian. Theo đó,
chuỗi thời gian được định nghĩa là một chuỗi các số thực X =x1, x2, x3, …, xn với xi là giá trị
đo được ở thời điểm thứ i.


1.6.


Phương pháp nghiên cứu
Nghiên cứu các phương pháp phát hiện bất thường trên dữ liệu chuỗi thời gian đã được
công bố từ trước đến nay để từ đó cải tiến và đề xuất một phương pháp mới cho bài
toán phát hiện bất thường dựa trên cửa sổ trượt.



Cài đặt phương pháp đề xuất sử dụng Matlab.



Xây dựng các bộ dữ liệu thực nghiệm.



Thực nghiệm và đánh giá, so sánh phương pháp được đề xuất trong luận văn với các
phương pháp đã công bố.


8

CHƯƠNG 2 - CƠ SỞ LÝ THUYẾT
2.1. Thu giảm số chiều chuỗi thời gian
Các chuỗi thời gian trong thực tế thường có số điểm dữ liệu rất lớn, nếu thực hiện việc
tìm kiếm chuỗi bất thường trực tiếp trên các chuỗi thời gian gốc này sẽ gặp khó khăn về lưu
trữ và tốc độ tính toán. Do đó, các nhóm nghiên cứu đã đề xuất các phương pháp thu giảm
số chiều để thu giảm độ lớn của dữ liệu mà vẫn giữ được các đặc trưng của dữ liệu. Một số

phương pháp thu giảm số chiều điển hình như biến đổi Fourier rời rạc, biến đổi Wavelet rời
rạc, phương pháp xấp xỉ gộp từng đoạn (PAA), phương pháp xấp xỉ tuyến tính từng đoạn
(PLA), … Trong đó, phương pháp xấp xỉ gộp từng đoạn (PAA) thường được các nhóm
nghiên cứu đề xuất sử dụng vì đơn giản và dễ hiện thực.

2.2. Rời rạc hóa chuỗi thời gian
Rời rạc hóa (discretization) chuỗi thời gian là quá trình biến đổi chuỗi thời gian thành
một chuỗi các ký tự để có thể áp dụng các kỹ thuật xử lý trên dữ liệu chuỗi ký tự để thực
hiện xử lý, phân tích dữ liệu chuỗi thời gian. Trong các phương pháp rời rạc hóa chuỗi thời
gian đã được đề xuất, phương pháp xấp xỉ gộp ký hiệu hoá (Symbolic Aggregate
approXimation – SAX) thường được sử dụng trong bài toán phát hiện motif hoặc phát hiện
bất thường trên chuỗi thời gian.

2.3. Các kỹ thuật phát hiện bất thường
Qui trình phát hiện chuỗi bất thường bao gồm 3 bước chính sau đây:


Tính điểm bất thường (anomaly score) của mỗi chuỗi con được rút trích từ chuỗi thời
gian ban đầu.



Tổng hợp điểm bất thường của các chuỗi con để tính điểm bất thường của chuỗi thời
gian ban đầu. Cách tổng hợp này được thực hiện bằng nhiều phương pháp khác nhau,
ví dụ như (1) lấy trung bình các điểm bất thường của các chuỗi con, (2) lấy trung bình
của k điểm bất thường của k chuỗi con đầu tiên, …



Đánh dấu chuỗi bất thường cho những chuỗi thời gian có điểm bất thường lớn hơn

ngưỡng đã thiết lập.

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).


9

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ó.

2.3.2. Dựa vào sự tương tự (Proximity based)
Kỹ thuật này sử dụng độ tương tự giữa chuỗi thời gian kiểm thử và tập chuỗi thời gian
huấn luyện để tính điểm bất thường (anomaly score) của mỗi chuỗi thời gian kiểm thử. Các
độ đo tương tự hay độ đo khoảng cách (similarity/distance measures) thường được sử dụng
để tính điểm bất thường như độ đo Euclidean, Cosin, DTW, …

2.3.3. Dựa vào dự đoán
Phát hiện bất thường dựa vào dự đoán được sử dụng chủ yếu trong thống kê. Ý nghĩa
của kỹ thuật này là chuỗi thời gian bình thường được tạo ra từ quá trình thống kê và chuỗi
thời gian bất thường không phù hợp với quá trình này. Bước quan trọng là tìm hiểu các
tham số của quá trình này từ cơ sở dữ liệu huấn luyện của chuỗi thời gian bình thường và
sau đó ước tính xác suất mà một chuỗi thời gian kiểm thử được tạo ra từ quá trình học.

2.3.4. Dựa vào mô hình Markov ẩn
Giả thiết của kỹ thuật phát hiện bất thường dựa trên HMM là một chuỗi thời gian cho

trước O=O1…..On là quan sát không trực tiếp của một chuỗi thời gian ẩn Q=Q1…..Qn, sao
cho quá trình sinh ra các chuỗi thời gian ẩn là quá trình Markov. Những chuỗi thời gian bình
thường có thể được mô hình bằng một HMM, trong khi đó, những chuỗi thời gian bất
thường thì không thể.

2.3.5. Dựa vào phân đoạn
Cách tiếp cận cơ bản của phát hiện bất thường chuỗi thời gian dựa trên phân đoạn là
phân chia chuỗi thời gian huấn luyện thành nhiều đoạn đồng nhất và học để mô hình sự biến
đổi giữa các đoạn này. Giả thiết của kỹ thuật phát hiện bất thường dựa vào phân đoạn là các
phân đoạn được sinh ra từ một chuỗi thời gian bất thường sẽ không khớp với mô hình huấn
luyện, trong khi đó các phân đoạn được sinh ra từ một chuỗi thời gian bình thường thì khớp.
Cho một chuỗi thời gian kiểm thử, các phân đoạn của nó được sinh ra và xác suất biến đổi
giữa các phân đoạn này được sử dụng để dự đoán sự bất thường của chúng.

2.4. Một số khái niệm cơ bản
2.4.1. Chuỗi thời gian (Time series)


10

Chuỗi thời gian T = t1, t2, …, tm là tập hợp có thứ tự các quan sát đơn biến hoặc đa biến
được đo sau những khoảng thời gian bằng nhau theo thời gian.

2.4.2. Chuỗi con (Subsequence)
Cho một dữ liệu chuỗi thời gian T có chiều dài là m, một chuỗi con C trong T có chiều
dài w là một mẫu những giá trị liên tục được rút trích từ T.
C = tp, …, tp+w-1 với 1  p  (m - w + 1)

2.4.3. Cửa sổ trượt (Slide windows)
Cho một dữ liệu chuỗi thời gian T có chiều dài m, một cửa sổ trượt có kích thước w

được định nghĩa bởi người dùng (w << m) sẽ trượt qua từng điểm giá trị trên chuỗi T, kết
quả là được một danh sách gồm (m – w + 1) chuỗi con có kích thước w được rút trích từ
chuỗi T.

2.4.4. Trùng khớp (Match)
Cho một số thực R (thường được định nghĩa bởi người dùng) và một dữ liệu chuỗi thời
gian T chứa một chuỗi con C bắt đầu tại vị trí p và một chuỗi con S bắt đầu tại vị trí q, nếu
hàm tính khoảng cách từ C đến S được ký hiệu là D(C, S) và D(C, S)  R thì chuỗi con S là
một trùng khớp của chuỗi con C.

2.4.5. Trùng khớp không tầm thường (Non-Self Match)
Cho chuỗi thời gian T chứa một chuỗi con C có chiều dài n bắt đầu tại vị trí p và trùng
khớp với chuỗi con S bắt đầu tại vị trí q, chúng ta có thể nói S là một “trùng khớp không tầm
thường” tại khoảng cách của D(S, C) nếu |p – q|  n.

2.4.6. Mật độ có trọng số (weighted density)
Công trình nghiên cứu [16] đề xuất một độ đo thông tin (information measure) tính
mật độ có trọng số của mỗi đối tượng dựa trên giá trị thuộc tính của chúng. Để có thể sử
dụng độ đo thông tin trong bài toán phát hiện chuỗi bất thường, mỗi chuỗi con được xem
như một đối tượng với tập các giá trị thuộc tính là tập ký tự của chuỗi con. Do đó, mật độ có
trọng số của mỗi chuỗi con được tính như sau:
Gọi U là tập tất cả chuỗi con, A là tập các thuộc tính trong đó Ck là ký tự thứ k trong
mỗi chuỗi con. Mật độ có trọng số của mỗi chuỗi con được tính lần lượt theo các công thức
sau:
IND(Ck) = {(x, y) ∈ UxU|x.Ck = y.Ck}
[x]Ck = {y ∈ U|(x, y) ∈ IND(Ck)}


11


U/IND(Ck) = {[x]Ck|x ∈ U}

(1)

Giả sử rằng: U/IND(Ck) = {X1, X2, . . ., Xp}.
𝑝

𝐸(𝐶 𝑘 ) = ∑
𝑖=1

|𝑋𝑖 |
|𝑋𝑖 |
(1 −
)
|𝑈|
|𝑈|

(2)

Trong đó |X| là chiều dài của X.
Trọng số của ký tự Ck:
1 − 𝐸(𝐶 𝑘 )
𝑊(𝐶 ) = 𝑤
∑𝑖=1 1 − 𝐸(𝐶𝑘 )
𝑘

(3)

Mật độ của chuỗi con x tương ứng với ký tự Ck
𝐷𝑒𝑛𝐶𝑘 (x) =


|[x]Ck |
|𝑈|

(4)

Mật độ có trọng số của chuỗi con x:
𝑤

𝑊𝐷𝑒𝑛(𝑥) = ∑ 𝐷𝑒𝑛𝐶 𝑖 (𝑥). 𝑊 (𝐶 𝑖 )

(5)

𝑖=1

2.5. Giải thuật phát hiện chuỗi bất thường
2.5.1. Giải thuật Brute force
Giải thuật Brute-Force là phương pháp đơn giản và dễ dàng phát hiện chuỗi con bất
thường. Ý tưởng của giải thuật là chạy hai vòng lặp lồng nhau, trong đó ứng với mỗi chuỗi
con dự tuyển trong tập (|T|- n + 1) chuỗi con của vòng lặp ngoài, vòng lặp trong duyệt
từng chuỗi con trong tập (|T|- n + 1) chuỗi con để tìm ra chuỗi con trùng khớp không tầm
thường (non-self match) với chuỗi con dự tuyển. Sau khi chạy hai vòng lặp lồng nhau, giải
thuật sẽ trả về chuỗi con bất thường. Giải thuật Brute-Force duyệt tất cả chuỗi con nên có
thể trả về chính xác chuỗi con bất thường chỉ với một tham số đầu vào là chiều dài của
chuỗi bất thường. Tuy nhiên, vì giải thuật Brute-Force duyệt tất cả chuỗi con ở hai vòng lặp
lồng nhau nên độ phức tạp tính toán của giải thuật là O(m2) với m là chiều dài của chuỗi thời


12


gian, |T| = m. Giải thuật Brute-Force có độ phức tạp tính toán O(m2) nên giải thuật không
khả thi cho những tập dữ liệu có kích thước m lớn.

2.5.2. Giải thuật phát hiện chuỗi bất thường Heuristic
Để giảm chi phí tính toán của giải thuật Brute force, Keogh cùng cộng sự [14] đã đề xuất
một giải thuật khung (framework) cải tiến giải thuật Brute force dựa trên hai Heuristic.
Heuristic thứ nhất xác định thứ tự chuỗi con dự tuyển được xét duyệt trong vòng lặp ngoài.
Heuristic thứ hai xác định thứ tự chuỗi con dự tuyển được xét duyệt trong vòng lặp trong.
Giải thuật khung này có tên gọi là giải thuật phát hiện chuỗi bất thường Heuristic và được
trình bày chi tiết trong Bảng 2.3.
Bảng 2.1: Giải thuật phát hiện chuỗi bất thường Heuristic

1

Function [dist, loc ]= Heuristic_Search(T, n, Outer, Inner )

2

best_so_far_dist = 0

3

best_so_far_loc = NaN

4

For Each p in T ordered by heuristic Outer

5


nearest_neighbor_dist = infinity

6

For Each q in T ordered by heuristic Inner

7
8

IF | p – q | ≥ n
IF Dist (tp,…,tp+n-1, tq,…,tq+n-1) < best_so_far_dist

9

Break

10

End

11

IF Dist (tp,…,tp+n-1, tq,…,tq+n-1) < nearest_neighbor_dist

12

nearest_neighbor_dist = Dist (tp,…,tp+n-1, tq,…,tq+n-1)

13
14


End
End

15

End

16

IF nearest_neighbor_dist > best_so_far_dist

17

best_so_far_dist = nearest_neighbor_dist

18

best_so_far_loc = p

19
20

End
End


13

21


Return[ best_so_far_dist, best_so_far_loc ]
Trong giải thuật phát hiện chuỗi bất thường Heuristic, các Heuristic xét thứ tự duyệt

của vòng lặp ngoài và vòng lặp trong ảnh hưởng lớn đến hiệu quả thời gian chạy của giải
thuật. Heuristic càng tốt thì càng nhanh thoát khỏi các vòng lặp của giải thuật. Tuy nhiên,
nếu Heuristic tốt mà lại có thời gian tính toán lớn thì giải thuật cũng không có hiệu quả về
thời gian chạy. Bởi vì thời gian tính toán Heuristic cũng là một phần chi phí thời gian chạy
của giải thuật.


14

CHƯƠNG 3 – GIẢI THUẬT VÀ THỰC NGHIỆM
Chương này trình bày về (1) phương pháp giải quyết đề xuất cho bài toán phát hiện
chuỗi bất thường trên dữ liệu chuỗi thời gian dựa trên giải thuật HOTSAX; (2) cài đặt giải
thuật bằng MATLAB, xây dựng các tập dữ liệu kiểm thử, thực nghiệm và đánh giá kết quả
thực nghiệm.

3.1.

Đặt vấn đề
Như đã trình bày trong chương 2, phần 2.5.1, một trong những phương pháp đơn giản

phát hiện chính xác chuỗi con bất thường trên dữ liệu chuỗi thời gian là phương pháp Brute
force. Tuy nhiên, giải thuật Brute force thực hiện vét cạn nên độ phức tạp tính toán là
O(m2), với m là chiều dài của chuỗi thời gian đầu vào. Các chuỗi thời gian thu thập được
trong các ứng dụng thực tế như dữ liệu điện tâm đồ, 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, … thường rất lớn nên giải thuật Brute force khó khả thi
trong thực tế. Để giải quyết vấn đề này, giải thuật HOTSAX đã sử dụng hai Heuristic để

dừng sớm vòng lặp trong và vòng lặp ngoài của giải thuật Brute force thay vì chạy hết hai
vòng lặp lồng nhau như Brute force. Giải thuật HOTSAX sử dụng tần suất xuất hiện của
mỗi chuỗi con để đánh giá khả năng là chuỗi con bất thường, chuỗi con có tần suất xuất hiện
càng nhỏ thì khả năng là chuỗi bất thường càng cao. Đối với vòng lặp ngoài, giải thuật
HOTSAX đề xuất chọn chuỗi con có tần suất xuất hiện nhỏ nhất (nghĩa là có khả năng là
chuỗi con bất thường cao nhất) để ưu tiên xét trước.
Chúng tôi nhận thấy việc lựa chọn chuỗi con có khả năng là chuỗi bất thường càng lớn
để ưu tiên xét trước trong vòng lặp thì vòng lặp càng dừng sớm và trả về kết quả chuỗi con
bất thường tìm được. Do đó, bên cạnh Heuricstic mà giải thuật HOTSAX sử dụng, chúng ta
có thể đề xuất các phương pháp khác để ước lượng khả năng là chuỗi con bất thường. Trong
luận văn này, tác giả đề xuất sử dụng mật độ có trọng số ( weighted densities) của mỗi chuỗi
con được trình bày trong chương 2 để tính độ bất thường của mỗi chuỗi con. Ý tưởng sử
dụng mật độ có trọng số này được xuất phát từ giả thiết nếu tần số của mỗi ký tự càng nhỏ
thì chuỗi con chứa ký tự có khả năng là chuỗi bất thường càng cao. Do đó, mật độ có trọng
số này có thể được sử dụng như Heuristic thay cho tần suất xuất hiện của mỗi chuỗi con
trong giải thuật HOTSAX.


15

3.2.

Hướng giải quyết vấn đề
Bài toán phát hiện chuỗi bất thường trên dữ liệu chuỗi thời gian được giải quyết theo

trình tự các bước được mô tả trong Hình 3.1. Trong đó:


Dữ liệu đầu vào: là chuỗi thời gian chiều dài m (được lấy từ các tập dữ liệu kiểm thử
chuẩn);




Tiền xử lý dữ liệu: bao gồm các bước thu giảm số chiều, rời rạc hóa dữ liệu;



Giải thuật đề xuất: giải thuật phát hiện chuỗi bất thường được đề xuất dựa trên giải
thuật HOTSAX.



Dữ liệu đầu ra: vị trí chuỗi con bất thường chiều dài n trong chuỗi thời gian chiều dài
m đầu vào.

Dữ liệu
đầu vào

Tiền xử
lý

Giải thuật
đề xuất

Dữ liệu
đầu ra

Hình 3.1: Hướng giải quyết vấn đề

3.2.1. Thu giảm số chiều theo phép biến đổi PAA

Như trình bày trong chương 2, phần 2.1, dữ liệu chuỗi thời gian chiều dài m, C =
c1…cm, sau khi chuẩn hóa sẽ được thu giảm số chiều theo phép biến đổi PAA. Chuỗi kết quả

sau thu giảm số chiều, D = d1…dw, có chiều dài w nhỏ hơn rất nhiều so với chiều dài m của
chuỗi thời gian gốc ban đầu.

3.2.2. Rời rạc hóa dữ liệu theo phép biến đổi SAX
Chuỗi thời gian sau khi được thu giảm số chiều theo phép biến đổi PAA sẽ được rời
rạc hóa dữ liệu theo phép biến đổi SAX được trình bày trong chương 2, phần 2.2 Mỗi giá trị
trung bình trong chuỗi thu giảm số chiều D được biểu diễn bằng một ký tự thông qua bảng
Breakpoint của phép biến đổi SAX.

3.2.3. Xây dựng giải thuật đề xuất dựa trên giải thuật HOTSAX
Như đã trình bày ở mục 2.5.2, chương 2, giải thuật HOTSAX cho phép sử dụng các
Heuristic để thiết lập thứ tự chuỗi con dự tuyển được chọn xét tại vòng lặp ngoài và vòng
lặp trong của giải thuật Brute force. Do đó, chúng tôi đề xuất sử dụng mật độ có trọng số
của mỗi chuỗi con như là Heuristic để xác định thứ tự xét của các chuỗi con trong hai vòng
lặp lồng nhau của giải thuật HOTSAX. Ý tưởng của giải thuật đề xuất dựa trên mật độ có


16

trọng số, là một độ đo thông tin (information measure), nên tác giả đặt tên cho giải thuật là
IDD (Information theory based Discord Discovery). Chi tiết về giải thuật phát hiện chuỗi
bất thường IDD được trình bày trong Bảng 3.1 và Bảng 3.2.
Bảng 3.1: Tính mật độ có trọng số cho mỗi chuỗi con

Input: A time series with length of m
Output: 1st discord length of n.
Step 1: Tất cả chuỗi con được rút trích từ chuỗi thời gian gốc chiều dài m bằng

phương pháp cửa sổ trượt và được rời rạc hóa thành chuỗi ký tự bằng phép biến đổi
SAX với chiều dài w.
Step 2: Tính mật độ có trọng số cho mỗi chuỗi con sau phép biến đổi SAX
1
2
3
4
5
6
7

For i = 1 to w do
Compute U/IND(Ci) according to (1)
Compute E(Ci) according to (2)
Compute W (Ci) according to (3)
For i = 1 to m-n+1 do
For j = 1 to w do

8
9
10

Compute DenCj (xi) according to (4)
Compute WDen(xi) according to (5)

Step 3: Dựa vào mật độ có trọng số của mỗi chuỗi con, chúng tôi tạo Heuristic cho
vòng lặp ngoài và vòng lặp trong và chạy giải thuật phát hiện chuỗi bất thường dựa
trên Heuristics được trình bày trong Bảng 3.2.



17
Bảng 3.2: Giải thuật phát hiện chuỗi bất thường dựa trên Heuristics

1

Function [dist, loc]= Heuristics_Search(T, n, Outer, Inner)

2

best_so_far_dist = 0

3

best_so_far_loc = NaN

4

For Each p in T ordered by heuristic Outer

5

nearest_neighbor_dist = infinity

6

For Each q in T ordered by heuristic Inner

7

IF | p-q|  n


//Begin Outer Loop

//Begin Inner Loop

//non-self match?

IF Dist(tp,…,tp+n-1, tq,…,tq+n-1) < best_so_far_dist

8
9

Break

//Break out of Inner Loop

10

End

11

IF Dist(tp,…,tp+n-1, tq,…,tq+n-1)< nearest_neighbor_dist
nearest_neighbor_dist = Dist(tp,…,tp+n-1, tq,…,tq+n-1)

12
13
14
15


End
End
End

//End non-self match test
//End Inner Loop

16

IF nearest_neighbor_dist > best_so_far_dist

17

best_so_far_dist = nearest_neighbor_dist

18

best_so_far_loc = p

19
20
21

End
End

//End Outer Loop

Return[ best_so_far_dist, best_so_far_loc ]


Heuristic vòng lặp ngoài (Outer Loop Heuristic): thứ tự các chuỗi con dự tuyển cho
vòng lặp ngoài được xếp như sau: chuỗi con xi có giá trị WDen(xi) nhỏ nhất được xét đầu
tiên, sau đó các chuỗi con còn lại được xét theo thứ tự ngẫu nhiên. Ý tưởng của Heuristic
này là nếu chuỗi con xi có giá trị WDen(xi) nhỏ nhất thì chuỗi con xi có khả năng là chuỗi bất
thường cao nhất.
Heuristic vòng lặp trong (Inner Loop Heuristic): Giả sử chuỗi con đang được xét ở
vòng lặp ngoài là xi, tác giả tìm những chuỗi con xj có cùng giá trị mật độ với chuỗi con xi,
nghĩa là WDen(xj) = WDen(xi), để chọn xét trước trong vòng lặp trong. Sau đó, những chuỗi
con còn lại được xét theo thứ tự ngẫu nhiên. Ý tưởng của Heuristic này là nếu hai chuỗi con


18

có cùng giá trị mật độ có trọng số thì khả năng là khá giống nhau nên khoảng cách giữa
chúng có khả năng là nhỏ nhất và do đó nên chọn xét chúng trước trong vòng lặp trong để
sớm dừng vòng lặp khi đã tìm thấy chuỗi con bất thường.
Trong giải thuật này, các chuỗi con ký tự sau phép rời rạc hóa chỉ được sử dụng để xét
Heuristic cho vòng lặp ngoài và vòng lặp trong. Đối với việc tính khoảng cách, tác giả tính
khoảng cách Euclidean giữa hai chuỗi con gốc để tìm được chính xác chuỗi con bất thường.

3.3.

Dữ liệu thực nghiệm
Trong luận văn này, tác giả tiến hành thực nghiệm trên năm tập dữ liệu chuẩn được lấy

từ trang web khai phá dữ liệu chuỗi thời gian UCR [33]. Các tập dữ liệu được lấy từ nhiều
lĩnh vực khác nhau như dữ liệu y khoa, dữ liệu doanh nghiệp, công nghiệp, … với chiều dài
khác nhau. Trong tất cả các kịch bản thực nghiệm, chiều dài của chuỗi con bất thường cho
mỗi tập dữ liệu kiểm thử được chọn cố định theo gợi ý của chuyên gia. Chi tiết về các tập
dữ liệu thực nghiệm được trình bày trong Bảng 3.3.

Bảng 3.3: Đặc điểm của các tập dữ liệu thực nghiệm

Data set

3.4.

Time series length Discord length

Video

5000

200

ECG

20000

255

Power

20000

750

Patient

4000


150

Space Shuttle

5000

100

Thiết lập thực nghiệm
Luận văn tiến hành cài đặt thuật toán đề xuất IDD và thuật toán dùng để so sánh

HOTSAX bằng ngôn ngữ lập trình MATLAB. Tất cả kịch bản thực nghiệm được thực hiện
trên máy tính có cấu hình là Core i3 2.53GHz, 4GB RAM, Windows 7 64-bit.
Giải thuật HOTSAX và giải thuật IDD đều có ba tham số cần được thiết lập trước khi
chạy giải thuật, bao gồm:


19

-

Chiều dài chuỗi bất thường (discord length), n;

-

Kích thước từ (word size), w;

-

Kích thước bảng ký tự (alphabe size), a.


Trong những tham số này, w và a không ảnh hưởng đến tính đúng đắn của cả hai giải
thuật nhưng chúng ảnh hưởng đến hiệu quả của cả hai giải thuật. Về lý thuyết, hầu hết các
công trình trước đây đều đánh giá hiệu quả của giải thuật phát hiện chuỗi bất thường dựa
trên số lần gọi hàm tính khoảng cách với tham số được thiết lập giá trị tốt nhất. Phương
pháp đánh giá như vậy có thể không công bằng cho những giải thuật có thời gian thấp trong
việc xác định các Heuristic và chọn giá trị cho các tham số. Do đó, luận văn này đề xuất
đánh giá độ hiệu quả của các giải thuật phát hiện chuỗi bất thường dựa trên hai tiêu chí với
các giá trị khác nhau của mỗi tham số: (1) Số lần gọi hàm tính khoảng cách Euclidean trong
giải thuật; (2) Thời gian chạy (CPU runtime) của giải thuật.
Để đánh giá ảnh hưởng của từng tham số a và w đến hiệu quả của cả hai giải thuật
IDD và HOTSAX, luận văn tiến hành thực nghiệm theo hai nhóm như sau:
Nhóm 1: Tác giả thiết lập w = 5 cho các tập dữ liệu Video, ECG, Power, Patient và w
= 10 cho tập dữ liệu Space Shuttle. Giá trị của w được cố định, giá trị của a được thay đổi để
khảo sát mức độ ảnh hưởng của tham số a đối với hiệu quả của mỗi thuật toán.
Nhóm 2: Giá trị của tham số a được cố định (dựa vào kết quả thực nghiệm Nhóm 1, a
được chọn giá trị 3 cho giải thuật HOTSAX và 21 cho giải thuật IDD), giá trị của tham số w
được thay đổi để khảo sát mức độ ảnh hưởng của tham số w đối với hiệu quả của mỗi giải
thuật

3.5.

Kết quả thực nghiệm và đánh giá
Ứng với mỗi kịch bản thực nghiệm Nhóm 1 và Nhóm 2, kết quả thực nghiệm được ghi

nhận để so sánh độ hiệu quả của các giải thuật dựa trên các tiêu chí sau đây:


Thời gian chạy (CPU runtime) của giải thuật




Số lần gọi hàm tính khoảng cách Euclidean trong giải thuật

Kết quả thực nghiệm Nhóm 1:
Lần lượt thực nghiệm trên 05 tập dữ liệu kiểm thử được trình bày trong phần 3.3, kết
quả thời gian chạy và số lần gọi hàm khoảng cách của cả hai giải thuật HOTSAX và IDD
được trình bày lần lượt trong các bảng từ Bảng 3.4 đến Bảng 3.8 và chuỗi con bất thường
tìm được lần lượt được trình bày trong các hình từ Hình 3.2 đến Hình 3.6.


20

Các kết quả thực nghiệm trong Nhóm 1 cho thấy cả hai giải thuật HOTSAX và IDD
đều trả về cùng chuỗi bất thường nhưng giải thuật IDD có thời gian chạy nhanh hơn đáng kể
so với giải thuật HOTSAX mặc dù số lần gọi hàm khoảng cách của giải thuật IDD cao hơn
một ít so với giải thuật HOTSAX trong một số trường hợp. Giải thuật IDD chạy nhanh hơn
giải thuật HOTSAX là bởi vì giải thuật IDD có được ưu điểm tính toán nhanh của độ đo
thông tin WDen, trong khi đó giải thuật HOTSAX phải mất chi phí cho việc xây dựng một
mảng và một cây để tạo các Heuristic này cho hai vòng lặp trong bước tiếp theo của giải
thuật.
Ngoài ra, kết quả thực nghiệm trong Nhóm 1 cũng cho thấy rằng giải thuật IDD có
hiệu quả ổn định hơn giải thuật HOTSAX khi chạy trên 5 tập dữ liệu kiểm thử khác nhau.
Nhìn chung, hầu hết các thực nghiệm cho thấy giải thuật HOTSAX có hiệu quả cao nhất khi
a = 3 trong khi đó giải thuật IDD có hiệu quả cao nhất khi a = 21. Do đó, trong các thực
nghiệm Nhóm 2 sau đây, tác giả thiết lập cố định a = 3 cho giải thuật HOTSAX và a = 21
cho giải thuật IDD.


21

Bảng 3.4: Cố định giá trị w = 5, thay đổi giá trị a trên tập dữ liệu VIDEO

Tập dữ liệu VIDEO, chiều dài discord n = 200, Kích thước từ w = 5
Running Time (s)
Distance function calls
Alphabet size (a)
HOTSAX
IDD
HOTSAX
IDD
3

169

109

799.163

1.098.983

6

148

74

363.384

856.316


9

141

59

322.863

594.373

12

155

52

308.173

531.289

15

154

48

445.538

493.074


18

158

45

529.700

465.488

21

179

43

716.054

472.678

Hình 3.2: Chuỗi con bất thường của tập dữ liệu VIDEO


22
Bảng 3.5: Cố định giá trị w=5, thay đổi giá trị a trên tập dữ liệu ECG

Tập dữ liệu ECG, chiều dài discord n = 256, kích thước từ w = 5
Alphabet size (a)

Running Time (s)


Distance function calls

HOTSAX

IDD

HOTSAX

3

2.625

1.128

2.115.030

4.173.756

6

2.165

806

2.035.393

3.215.225

9


2.315

691

1.807.239

3.329.775

12

2.126

554

2.367.130

2.845.442

15

2.186

552

2.458.820

2.472.502

18


2.215

495

3.359.932

2.703.755

21

2.221

459

3.687.119

2.713.265

Hình 3.3: Chuỗi con bất thường của tập dữ liệu ECG

IDD


23
Bảng 3.6: Cố định giá trị w=5, thay đổi giá trị a trên tập dữ liệu POWER

Tập dữ liệu POWER, chiều dài discord n = 750, kích thước từ w = 5
Running Time (s)
Distance function calls

Alphabet size (a)
HOTSAX
IDD
HOTSAX
IDD
3

2.343

1.508

7.338.545

10.203.248

6

2.312

1.581

4.890.053

7.566.715

9

2.117

938


2.700.775

7.363.209

12

2.279

1.001

2.119.408

9.615.270

15

2.061

901

1.566.813

7.770.451

18

2.005

867


1.778.374

7.911.583

21

2.011

725

1.483.770

6.676.988

Hình 3.4: Chuỗi con bất thường của tập dữ liệu POWER