ĐẠI HỌC QUỐC GIA TP.HCM
TRƯỜNG ĐẠI HỌC BÁCH KHOA

NGUYỄN VĂN NHẤT

NHẬN DẠNG
G MOTIFS TRÊN DỮ LIỆU CH
CHUỖI THỜI
GIAN KHÔNG
G CẦN XÁC ĐỊNH THÔNG SỐ
Ố CHIỀU DÀI

Chuyên ngành: Khoaa hhọc máy tính
Mã số: 60.48.01

LUẬN VĂN THẠC SĨ
TP. HỒ CHÍ MINH, tháng 06 năm 2013


CƠNG TRÌNH ĐƯỢC HỒN THÀNH TẠI
TRƯỜNG ĐẠI HỌC BÁCH KHOA –ĐHQG -HCM

Cán bộ hướng dẫn khoa học: PGS. TS. Dương Tuấn Anh ...................................

Cán bộ chấm nhận xét 1 : TS. Võ Thị Ngọc Châu................................................

Cán bộ chấm nhận xét 2 : TS. Phạm Văn Chung .................................................

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 23 tháng 07 năm 2013

Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm:
1. Chủ tịch: TS. Huỳnh Tường Nguyên…………………….………….……..
2. Thư ký: TS. Lê Thanh Vân………………………………………….……..
3. Giáo viên phản biện 1: TS. Phạm Văn Chung……………………………..
4. Giáo viên phản biện 1: TS. Võ Thị Ngọc Châu……………………..……..
5. Uỷ viên: PGS. TS. Dương Tuấn Anh…………………...............................
Xác nhận của Chủ tịch Hội đồng đánh giá LV và Trưởng Khoa 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


ĐẠI HỌC QUỐC GIA TP.HCM
TRƯỜNG ĐẠI HỌC BÁCH
KHOA

CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT
NAM Độc lập - Tự do - Hạnh phúc

NHIỆM VỤ LUẬN VĂN THẠC SĨ
Họ tên học viên: Nguyễn Văn Nhất ........................................ MSHV:10070490 .....
Ngày, tháng, năm sinh: 26/12/1984 ........................................... Nơi sinh: Bình Định .
Chuyên ngành: Khoa Học và Kỹ Thuật Máy Tính .............. Mã số : 60.48.01…...

I. TÊN ĐỀ TÀI: Nhận dạng motifs trên dữ liệu chuỗi thời gian không cần xác
định thông số chiều dài............................................................................................
II. NHIỆM VỤ VÀ NỘI DUNG:
Hiện thực giải thuật phát hiện motif trên dữ liệu chuỗi thời gian mà không cần
xác định trước thông số chiều dài của motif. Giải thuật này cho phép phát hiện

được các motif có chiều dài khác nhau. Đồng thời luận văn cũng đưa ra một kỹ
thuật cải tiến đó là áp dụng phép vị tự trên dữ liệu chuỗi thời gian kết hợp với độ
đo tương tự Euclid để tăng hiệu suất thời gian thực thi của giải thuật.
III. NGÀY GIAO NHIỆM VỤ: 02/07/2012.............................................................
IV. NGÀY HOÀN THÀNH NHIỆM VỤ: 21/06/2013............................................
V. CÁN BỘ HƯỚNG DẪN: PGS. TS. Dương Tuấn Anh .........................................

Tp. HCM, ngày 21 tháng 06 năm 2013
CÁN BỘ HƯỚNG DẪN

(Họ tên và chữ ký)

CHỦ NHIỆM BỘ MÔN ĐÀO TẠO

(Họ tên và chữ ký)

TRƯỞNG KHOA

(Họ tên và chữ ký)


GVHD: PSG. TS. Dương Tuấn Anh

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 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 nào 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 bất kỳ trường nào khác.
Ngày 10 tháng 06 năm 2013
Nguyễn Văn Nhất


Nguyễn Văn Nhất_10070490

Trang i


GVHD: PSG. TS. Dương Tuấn Anh

LỜI CẢM ƠN
Tôi xin gửi lời cảm ơn chân thành và sâu sắc đến PGS. TS. Dương Tuấn Anh đã
tận tình hướng dẫn, giúp đỡ tơi trong suốt q trình làm luận văn và tạo điều kiện
để tơi có thể hồn thành luận văn này.
Xin chân thành cảm ơn đến quý Thầy Cô trong khoa Khoa học và Kỹ Thuật Máy
Tính đã truyền đạt cho tơi những kiến thức q báu trong suốt q trình học tập tại
trường.
Cuối cùng, tơi cảm ơn gia đình, người thân và bạn bè đã động viên và tạo mọi điều
kiện tốt nhất để tơi hồn thành luận văn này. Qua đây tôi cũng xin cảm ơn các anh
chị và các bạn trong cùng nhóm nghiên cứu đã giúp đỡ, góp ý cho tơi trong suốt q
trình thực hiện luận văn này.

Nguyễn Văn Nhất_10070490

Trang ii


GVHD: PSG. TS. Dương Tuấn Anh

TÓM TẮT LUẬN VĂN
Gần đây, việc nghiên cứu trên sự rút trích hữu hiệu các mẫu không được biết trước,
các mẫu thường xuyên xuất hiện trong dữ liệu chuỗi thời gian, đã thu hút được

nhiều sự quan tâm của các nhà nghiên cứu. Các mẫu này được gọi là các motif. Các
motif thì rất hữu ích cho các công việc khai phá dữ liệu chuỗi thời gian khác nhau.
Do đó, việc tìm kiếm motif của dữ liệu chuỗi thời gian là một trong những kỹ thuật
phổ biến trong việc khai phá dữ liệu chuỗi thời gian.
Một trong những giải thuật phát hiện motif được áp dụng phổ biến là phương
pháp chiếu ngẫu nhiên (Random Projection Algorithm – RP). Phương pháp chiếu
ngẫu nhiên được thực hiện đơn giản và dễ tiếp cận. Tuy nhiên phương pháp này
chạy rất lâu với dữ liệu chuỗi thời gian có kích thước lớn, đồng thời các thơng số
của giải thuật phải được xác định bằng cách ‘thử và sửa sai’. Ngồi ra, hầu hết các
giải thuật phát hiện motif địi hỏi phải cung cấp trước chiều dài của motif cần tìm.
Và đây cũng chính là một trong những trở ngại lớn khi sử dụng các giải thuật phát
hiện motif.
Luận văn này sẽ dựa vào một tiếp cận mới để phát hiện motif mà không cần
xác định trước thông số chiều dài của motif. Cách tiếp cận này dựa trên nguyên lý
chiều dài mô tả tối thiểu (Minimum Description Length - MDL). Nguyên lý MDL
này cho phép xác định một cách động chiều dài tối ưu của motif. Cách tiếp cận này
được Tanaka, Iwamoto và Uehara đề xuất năm 2005.
Luận văn này còn áp dụng một kỹ thuật để cải tiến giải thuật trên trong việc
tính độ tương tự của hai chuỗi thời gian có độ dài khác nhau. Đó là áp dụng phép vị
tự (Homothetic Transformation) trên chuỗi thời gian, sau đó dùng phương pháp tính
độ tương tự Euclid. Cải tiến này đã làm tăng hiệu suất thời gian thực thi của giải
thuật lên rất nhiều so với đề xuất ban đầu của tác giả là dùng phương pháp xoắn
thời gian động (Dynamic Time Warping - DTW) để tính độ tương tự giữa hai chuỗi
thời gian bất kỳ.

Nguyễn Văn Nhất_10070490

Trang iii



GVHD: PSG. TS. Dương Tuấn Anh

ABSTRACT
Recently, the research on efficent extraction of previously unknown, frequently
appearing patterns in a time-series data, has received much attention. These patterns
are called ‘motifs’. Motifs are useful for various time-series data mining. Therefore,
motif discovery in a time-series is one of the popular techniques for data mining.
One of the most popular motif discovery algorithm is Random Projection
Algorithm. The algorithm is implemented simply and easily to understand.
However, it takes this algorimthm a long time to apply for large time-series. In
addition, its parameters are determined by ‘try and correct mistake’. Almost motif
discovery algorithms require to pass the motif length parameter to them. And this is
one of inconveniences when using the algorithms.
The thesis based on a new approach to discover motif without motif length is
Minimum Description Length (MDL) principle. MDL principle dynamically
determines an optimal length of a motif candidate. This approach is proposed by
Tanaka, Iwamoto and Uehara in 2005.
In this thesis, we also apply an technique to improve the algorithm in
calculating of measure of every two different length time-series. It’s an association
between homothetic transformation for time-series and Euclidean measure. This
improvement speeds up our algorithm. And run-time of our algorithm is faster
many times than the algorithm associcated with Dynamic Time Warping measure.

Nguyễn Văn Nhất_10070490

Trang iv


GVHD: PSG. TS. Dương Tuấn Anh


MỤC LỤC
MỤC LỤC ...................................................................................................................v
DANH MỤC HÌNH .................................................................................................. ix
CHƯƠNG 1 PHÁT BIỂU VẤN ĐỀ...........................................................................1
1.1 Giới thiệu đề tài ................................................................................................. 1
1.2 Mục đích nghiên cứu ......................................................................................... 2
1.3 Những kết quả đạt được .................................................................................... 3
1.4 Cấu trúc của luận văn ........................................................................................ 3
CHƯƠNG 2 CƠ SỞ LÝ THUYẾT VÀ CÁC CƠNG TRÌNH LIÊN QUAN ............5
2.1 Các độ đo tương tự ............................................................................................ 5
2.1.1 Độ đo Euclid ...............................................................................................5
2.1.2 Độ đo xoắn thời gian động .........................................................................6
2.2 Phương pháp thu giảm số chiều xấp xỉ gộp từng đoạn PAA ............................ 8
2.3 Phương pháp rời rạc hoá xấp xỉ gộp ký hiệu SAX.......................................... 11
2.4 Một số định nghĩa ............................................................................................ 13
2.4.1 Chuỗi thời gian .........................................................................................13
2.4.2 Chuỗi con ..................................................................................................14
2.4.3 Chuỗi con so trùng ....................................................................................14
2.4.4 Chuỗi con so trùng tầm thường ................................................................15
2.4.5 Motif bậc K ...............................................................................................15
2.5 Giải thuật Brute-Force ..................................................................................... 16
2.6 Các cơng trình liên quan .................................................................................. 18
2.6.1 Giải thuật phát hiện motif dựa vào phương pháp chiếu ngẫu nhiên .........18
2.6.2 Giải thuật phát hiện motif MK .................................................................20

Nguyễn Văn Nhất_10070490

Trang v



GVHD: PSG. TS. Dương Tuấn Anh

2.6.3 Giới thiệu sơ lược giải thuật phát hiện motif của Tanaka, Iwamoto và
Uehara ................................................................................................................26
2.7 Kết luận ........................................................................................................... 28
CHƯƠNG 3 PHƯƠNG PHÁP THỰC HIỆN...........................................................29
3.1 Phương pháp giải quyết vấn đề ....................................................................... 29
3.2 Phương pháp phát hiện motif không cần xác định chiều dài dựa trên nguyên
lý MDL .................................................................................................................. 31
3.2.1 Sơ đồ giải thuật MD..................................................................................31
3.2.2 Chuyển đổi chuỗi thời gian sang dạng ký hiệu.........................................33
3.2.3 Đánh giá ứng viên motif dựa trên nguyên lý MDL ..................................34
3.2.4 Rút trích motif từ chuỗi ký hiệu hành vi BS.............................................35
3.3 Mở rộng và cải tiến giải thuật.......................................................................... 38
3.3.1 Chỉnh sửa dữ liệu thời gian dạng ký hiệu hành vi BS ..............................38
3.3.2 Phép vị tự trên dữ liệu thời gian ...............................................................41
3.3.3 Định nghĩa chiều dài mô tả mới cho chuỗi thời gian................................43
3.3.4 Sơ đồ giải thuật phát hiện motif EMD|DTW............................................46
3.3.5 Sơ đồ giải thuật phát hiện motif EMD|HT ...............................................48
3.3.6 Hiện thực giải thuật mở rộng EMD|DTW ................................................48
3.3.7 Hiện thực giải thuật mở rộng EMD|HT ....................................................50
CHƯƠNG 4 HIỆN THỰC VÀ THỬ NGHIỆM ......................................................53
4.1 Thực nghiệm trên dữ liệu ECG 512 điểm ....................................................... 55
4.1.1 Thực nghiệm trên giải thuật Brute-Force .................................................55
4.1.2 Thực nghiệm trên giải thuật chiếu ngẫu nhiên .........................................56
4.1.3 Thực nghiệm trên giải thuật MD ..............................................................57

Nguyễn Văn Nhất_10070490

Trang vi



GVHD: PSG. TS. Dương Tuấn Anh

4.1.4 Thực nghiệm trên giải thuật EMD|DTW ..................................................58
4.1.5 Thực nghiệm trên giải thuật EMD|HT......................................................59
4.2 Thực nghiệm trên dữ liệu ECG 8000 điểm ..................................................... 60
4.2.1 Thực nghiệm trên giải thuật Brute-Force .................................................61
4.2.2 Thực nghiệm trên giải thuật chiếu ngẫu nhiên .........................................62
4.2.3 Thực nghiệm trên giải thuật EMD|DTW ..................................................63
4.2.4 Thực nghiệm trên giải thuật EMD|HT......................................................64
4.3 Thực nghiệm trên dữ liệu ECG 144000 điểm ................................................. 65
4.3.1 Thực nghiệm trên giải thuật Brute-Force .................................................65
4.3.2 Thực nghiệm trên giải thuật chiếu ngẫu nhiên .........................................65
4.3.3 Thực nghiệm trên giải thuật EMD|DTW ..................................................66
4.3.4 Thực nghiệm trên giải thuật EMD|HT......................................................66
4.4 Thực nghiệm trên dữ liệu Power 35040 điểm ................................................. 67
4.4.1 Thực nghiệm trên giải thuật Brute-Force .................................................68
4.4.2 Thực nghiệm trên giải thuật chiếu ngẫu nhiên .........................................68
4.4.3 Thực nghiệm trên giải thuật EMD|DTW ..................................................68
4.4.4 Thực nghiệm trên giải thuật EMD|HT......................................................69
4.5 Thực nghiệm trên dữ liệu Memory 6875 điểm ............................................... 70
4.5.1 Thực nghiệm trên giải thuật Brute-Force .................................................71
4.5.2 Thực nghiệm trên giải thuật chiếu ngẫu nhiên .........................................72
4.5.3 Thực nghiệm trên giải thuật EMD|DTW ..................................................73
4.5.4 Thực nghiệm trên giải thuật EMD|HT......................................................74
4.6 Thực nghiệm trên dữ liệu EEG 512 điểm ....................................................... 75
4.6.1 Thực nghiệm trên giải thuật Brute-Force .................................................75

Nguyễn Văn Nhất_10070490


Trang vii


GVHD: PSG. TS. Dương Tuấn Anh

4.6.2 Thực nghiệm trên giải thuật chiếu ngẫu nhiên .........................................76
4.6.3 Thực nghiệm trên giải thuật EMD|DTW ..................................................77
4.6.4 Thực nghiệm trên giải thuật EMD|HT......................................................78
4.7 Thực nghiệm trên dữ liệu ERP 6400 điểm ...................................................... 79
4.7.1 Thực nghiệm trên giải thuật Brute-Force .................................................80
4.7.2 Thực nghiệm trên giải thuật chiếu ngẫu nhiên .........................................81
4.7.3 Thực nghiệm trên giải thuật EMD|DTW ..................................................82
4.7.4 Thực nghiệm trên giải thuật EMD|HT......................................................83
4.2 Tổng kết và nhận xét các kết quả thực nghiệm thu được trên các tập dữ liệu
khác nhau ............................................................................................................... 84
4.3 Tính hiệu quả của giải thuật ............................................................................ 86
4.3.1 Tính hiệu quả của nguyên lý MDL đối với giải thuật phát hiện motif
không cần xác định thơng số chiều dài ..............................................................86
4.3.2 Tính hiệu quả của giải thuật mở rộng EMD .............................................87
4.3.2 Tính hiệu quả của phép vị tự đối với giải thuật EMD|HT ........................88
CHƯƠNG 5 KẾT LUẬN..........................................................................................89
5.1 Kết quả đạt được.............................................................................................. 89
5.2 Hướng phát triển .............................................................................................. 89
TÀI LIỆU THAM KHẢO.......................................................................................... A
PHỤ LỤC: BẢNG ĐỐI CHIẾU THUẬT NGỮ ANH VIỆT.................................... D

Nguyễn Văn Nhất_10070490

Trang viii



GVHD: PSG. TS. Dương Tuấn Anh

DANH MỤC HÌNH
Hình 1.1 Chuỗi thời gian thiên văn (ở trên) chứa 3 chuỗi con gần tương đồng nhau.
Bên dưới là hình phóng lớn của 3 chuỗi con ở trên [1] ..............................................2
Hình 2.1 Minh hoạ độ đo Euclid giữa hai chuỗi thời gian [1] ....................................6
Hình 2.2 Cách ánh xạ trong tính độ đo xoắn thời gian động [9] ................................7
Hình 2.3 Minh hoạ cách tính khoảng cách theo DTW [9] ..........................................8
Hình 2.4 Dạng biểu diễn PAA có thể được minh hoạ cũng như cố gắng mơ hình hố
một chuỗi với sự kết hợp tuyến tính của các hàm căn bản. Trong trường hợp này,
một chuỗi có chiều dài 128 được thu giảm thành 8 [1] ............................................10
Hình 2.5 Biểu đồ phân bố xác suất chuẩn của sự phân bố giá trị từ các chuỗi con có
chiều dài 128 từ 8 tập dữ liệu khác nhau. Đường tuyến tính của đồ thị chỉ ra rằng dữ
liệu có được là từ sự phân bố Gauss [1] ....................................................................11
Hình 2.6 Bảng tìm kiếm chứa các điểm cắt mà được chia theo phân bố Gauss của
vùng từ 3 tới 10 [1] ...................................................................................................12
Hình 2.7 Một chuỗi thời gian được rời rạc hoá bằng cách đầu tiên chuyển chuỗi thời
gian sang dạng PAA tương ứng và sau đó dùng các điểm cắt xác định trước để ánh
xạ các hệ số PAA vào các ký hiệu. Trong ví dụ trên, với n = 128, w = 8 và a = 3,
chuỗi thời gian được ánh xạ thành từ baabccbc [1] ..................................................13
Hình 2.8 Minh hoạ trực quan chuỗi thời gian T (nét nhỏ), một chuỗi con C (nét
đậm, màu đen) và một chuỗi con so trùng M (nét đậm màu xám) [1]......................14
Hình 2.9 Đối với hầu hết các chuỗi con C trong một chuỗi thời gian, chuỗi con so
trùng tốt nhất là những chuỗi con thông thường ngay bên trái và bên phải của C [1]
...................................................................................................................................15
Hình 2.10 Một giải thích trực quan của lý do tại sao định nghĩa của motif bậc K yêu
cầu rằng mỗi motif phải cách nhau ít nhất 2R. Nếu các motif chỉ cần thiết cách nhau
R như trong A, vậy thì hai motif có thể chia sẻ phần lớn các thành phần của chúng.

Nguyễn Văn Nhất_10070490

Trang ix


GVHD: PSG. TS. Dương Tuấn Anh

Ngược lại, B cho thấy rằng việc yêu cầu các tâm cách nhau ít nhất 2R đảm bảo
rằng các motif là duy nhất [1] ...................................................................................16
Hình 2.11 Giải thuật Brute-Force [1] ........................................................................17
Hình 2.12 Minh hoạ việc xây dựng ma trận S ̂ với a = 3, w = 4 và n = 16 [2] .........19
Hình 2.13 Trái) Các cột 1, 2 được chọn ngẫu nhiên. Phải) Tăng giá trị các ô tương
ứng trong cột 1, 2 [2].................................................................................................19
Hình 2.14 Trái) Các cột 2, 4 được chọn ngẫu nhiên. Phải) Tăng giá trị các ô tương
ứng trong cột 2, 4 [2].................................................................................................20
Hình 2.15 Giải thuật tìm kiếm motif dữ liệu chuỗi thời gian Brute-Force [6] .........21
Hình 2.16 Chặn dưới của các chuỗi con [6]..............................................................23
Hình 2.17 Mơ tả q trình cập nhật best-so-far [6]...................................................23
Hình 2.18 Tăng tốc giải thuật Brute-Force với một điểm tham chiếu [6] ................24
Hình 2.19 Giải thuật MK – motif [6] ........................................................................25
Hình 3.1 Ràng buộc của mẫu: (a) ‘ràng buộc hành vi’, (b) ‘ràng buộc khoảng cách’
và (c) ‘ràng buộc không chồng lấp lên nhau’. (c) biểu diễn một ví dụ của vi phạm
ràng buộc chồng lấp lên nhau [5] ..............................................................................30
Hình 3.2 Quá trình phát hiện motif ...........................................................................31
Hình 3.3 Sơ đồ tổng quan của giải thuật phát hiện motif MD ..................................32
Hình 3.4 Mơ tả trực quan giải thuật chuyển đổi một chuỗi thời gian sang dạng ký
hiệu. (a) Các chuỗi con thu được bằng cách dịch chuyển cửa sổ phân tích. (b) Mỗi
chuỗi con được chuyển sang một ký hiệu SAX. (c) ‘Ký hiệu hành vi’ được gán cho
mỗi ký chuỗi SAX [5] ...............................................................................................33
Hình 3.5 Mơ tả trực quan giải thuật dị tìm các mẫu bằng ngun lý MDL [5] .......37

Hình 3.6 (a) Chuỗi BS thu được từ chuỗi thời gian. (b) Chuỗi BS được chỉnh sửa [5]
...................................................................................................................................39
Hình 3.7 (a) Chuỗi BS ban đầu và (b) chuỗi BS đã được chỉnh sửa [5] ...................40
Nguyễn Văn Nhất_10070490

Trang x


GVHD: PSG. TS. Dương Tuấn Anh

Hình 3.8 Minh hoạ phép vị tự tâm O, hệ số vị tự k= ½ ............................................41
Hình 3.9 Tính chiều dài mơ tả bằng định nghĩa mới [5] ...........................................45
Hình 3.10 Sơ đồ tổng quan của giải thuật EMD|DTW .............................................47
Hình 3.11 Sơ đồ tổng quan của giải thuật EMD|HT .................................................49
Hình 4.1 Giao diện chương trình phát hiện motif .....................................................54
Hình 4.2 Dữ liệu điện tâm đồ ECG với kích thước 512 điểm ..................................55
Hình 4.3 Motif phát hiện bởi giải thuật Brute-Force với dữ liệu ECG 512 điểm.....56
Hình 4.4 Motif phát hiện bởi giải thuật chiếu ngẫu nhiên với dữ liệu ECG 512 điểm
...................................................................................................................................57
Hình 4.5 Motif phát hiện bởi giải thuật MD với dữ liệu ECG 512 điểm..................58
Hình 4.6 Motif phát hiện bởi giải thuật EMD|DTW với dữ liệu ECG 512 điểm .....59
Hình 4.7 Motif phát hiện bởi giải thuật EMD|HT với dữ liệu ECG 512 điểm .........60
Hình 4.8 Dữ liệu điện tâm đồ ECG với kích thước 8000 điểm ................................61
Hình 4.9 Motif phát hiện bởi giải thuật Brute-Force với dữ liệu ECG 8000 điểm...61
Hình 4.10 Motif phát hiện bởi giải thuật chiếu ngẫu nhiên với dữ liệu ECG 8000
điểm ...........................................................................................................................62
Hình 4.11 Motif phát hiện bởi giải thuật EMD|DTW với dữ liệu ECG 8000 điểm .63
Hình 4.12 Motif phát hiện bởi giải thuật EMD|HT với dữ liệu ECG 8000 điểm .....64
Hình 4.13 Dữ liệu điện tâm đồ ECG với kích thước 144000 điểm ..........................65
Hình 4.14 Motif phát hiện bởi giải thuật EMD|HT với dữ liệu ECG 144000 điểm .67

Hình 4.15 Dữ liệu Power với kích thước 35040 điểm ..............................................67
Hình 4.16 Motif phát hiện bởi giải thuật EMD|DTW với dữ liệu Power 35040 điểm
...................................................................................................................................69
Hình 4.17 Motif phát hiện bởi giải thuật EMD|HT với dữ liệu Power 35040 điểm .70

Nguyễn Văn Nhất_10070490

Trang xi


GVHD: PSG. TS. Dương Tuấn Anh

Hình 4.18 Dữ liệu Memory với kích thước 6875 điểm ............................................71
Hình 4.19 Motif phát hiện bởi giải thuật Brute-Force với dữ liệu Memory 6875
điểm ...........................................................................................................................71
Hình 4.20 Motif phát hiện bởi giải thuật chiếu ngẫu nhiên với dữ liệu Memory 6875
điểm ...........................................................................................................................72
Hình 4.21 Motif phát hiện bởi giải thuật EMD|DTW với dữ liệu Memory 6875 điểm
...................................................................................................................................73
Hình 4.22 Motif phát hiện bởi giải thuật EMD|HT với dữ liệu Memory 6875 điểm
...................................................................................................................................74
Hình 4.23 Dữ liệu điện não đồ với kích thước 512 điểm..........................................75
Hình 4.24 Motif phát hiện bởi giải thuật Brute-Force với dữ liệu EEG 512 điểm ...76
Hình 4.25 Motif phát hiện bởi giải thuật chiếu ngẫu nhiên với dữ liệu EEG 512
điểm ...........................................................................................................................77
Hình 4.26 Motif phát hiện bởi giải thuật EMD|DTW với dữ liệu EEG 512 điểm ...78
Hình 4.27 Motif phát hiện bởi giải thuật EMD|HT với dữ liệu EEG 512 điểm .......79
Hình 4.28 Dữ liệu ERP với kích thước 6400 điểm ...................................................80
Hình 4.29 Motif phát hiện bởi giải thuật Brute-Force với dữ liệu ERP 6400 điểm .80
Hình 4.30 Motif phát hiện bởi giải thuật chiếu ngẫu nhiên với dữ liệu ERP 6400

điểm ...........................................................................................................................81
Hình 4.31 Motif phát hiện bởi giải thuật EMD|DTW với dữ liệu ERP 6400 điểm ..82
Hình 4.32 Motif phát hiện bởi giải thuật EMD|HT với dữ liệu ERP 6400 điểm......83
Hình 4.33 Kết quả thực nghiệm của ba giải thuật trên các tập dữ liệu thời gian khác
nhau ...........................................................................................................................85
Hình 4.34 Tính hữu hiệu của giải thuật EMD|HT đối với các tập dữ liệu khác nhau
...................................................................................................................................86

Nguyễn Văn Nhất_10070490

Trang xii


GVHD: PSG. TS. Dương Tuấn Anh

Hình 4.35 Motif được phát hiện từ dữ liệu chuỗi thời gian [5] ................................86
Hình 4.36 Motif được phát hiện từ chuỗi thời gian. (a) Motif được phát hiện bằng
giải thuật mở rộng EMD. (b) Hình ảnh phóng lớn của ba chuỗi con của motif. (c)
Motif được rút trích bằng giải thuật MD [5] .............................................................87
Hình 5.1 Các chuỗi con BS có chiều dài khác nhau [5] ...........................................90

Nguyễn Văn Nhất_10070490

Trang xiii


Chương 1: Phát biểu vấn đề

GVHD: PSG. TS. Dương Tuấn Anh


CHƯƠNG 1
PHÁT BIỂU VẤN ĐỀ
Chương này sẽ giới thiệu tóm tắt vấn đề, mục tiêu nghiên cứu của luận văn và
những kết quả mà luận văn đã đạt được.

1.1 Giới thiệu đề tài
Các vấn đề liên quan đến xác định vị trí một cách hiệu quả các mẫu (pattern) đã
được biết trước trong một cơ sở dữ liệu chuỗi thời gian (ví dụ, truy vấn theo nội
dung) đã nhận được nhiều sự chú ý và hiện nay phần lớn có thể được coi như
là một vấn đề đã được giải quyết [8, 10, 11, 12, 13, 14, 15, 16].
Tuy nhiên, từ quan điểm khám phá tri thức, một vấn đề thú vị hơn là liệt kê
các mẫu thường xuyên xuất hiện mà chưa được biết trước. Các mẫu như vậy được
gọi là motif, bởi có vì sự tương đồng chặt chẽ với các mẫu rời rạc trong tính tốn
sinh học bằng máy tính [17, 18, 19, 20, 21].
Một thuật tốn phát hiện motif hiệu quả cho chuỗi thời gian sẽ hữu ích như là
một cơng cụ tổng hợp, hình ảnh hóa cơ sở dữ liệu chuỗi thời gian đồ sộ. Ngồi ra,
nó có thể được sử dụng như một chương trình con trong các tác vụ khai thác dữ
khác nhau, bao gồm cả việc khám phá ra các luật kết hợp, gom cụm và phân loại. Ví
dụ, tạo các trung tâm cụm ban đầu cho việc gom cụm dữ liệu chuỗi thời gian trong
giải thuật K-means bằng các motif thay vì chọn trung tâm cụm một cách ngẫu nhiên
có thể làm cho độ hội tụ của giải thuật nhanh hơn. Hình 1.1 minh hoạ một ví dụ của
một motif được phát hiện trong một cơ sở dữ liệu thiên văn.
Tuy nhiên, việc phát hiện motif không được biết trước, đặc biệt là motif
khơng biết trước chiều dài, vẫn cịn là một thử thách lớn. Và hiện này, vấn đề này
đang thu hút nhiều sự quan tâm của các nhà nghiên cứu. Đây cũng chính là mục tiêu
mà luận văn này sẽ thực hiện.

Nguyễn Văn Nhất_10070490

Trang 1



Chương 1: Phát biểu vấn đề

GVHD: PSG. TS. Dương Tuấn Anh

Hình 1.1 Chuỗi thời gian thiên văn (ở trên) chứa 3 chuỗi con gần tương đồng nhau. Bên dưới là hình
phóng lớn của 3 chuỗi con ở trên [1]

1.2 Mục đích nghiên cứu
Hiện nay, đối với vấn đề phát hiện motif thì cũng đã có khá nhiều giải thuật để giải
quyết vấn đề này. Các phương pháp được ứng dụng trong bài toán này thường
được dùng là Brute-Force được J.Lin và các cộng sự đề xuất năm 2002 [1], phương
pháp chiếu ngẫu nhiên được B.Chiu và các cộng sự giới thiệu năm 2003 [2], giải
thuật MK của Mueen và các cộng sự đưa ra năm 2009 [6]. Tuy nhiên khi áp dụng
các phương pháp trên thì gặp phải các nhược điểm sau
• Phải xác định trước chiều dài của motif.
• Khơng thích hợp khi chuỗi dữ liệu lớn.
•

Cả ba phương pháp này khơng thể phát hiện được các motif có chiều dài
khác nhau.
Vì vậy mục đích nghiên cứu của luận văn là nhằm hiện thực được một giải

thuật để giải quyết được ba vấn đề hạn chế trên. Hay nói cách khác luận văn này sẽ

Nguyễn Văn Nhất_10070490

Trang 2



Chương 1: Phát biểu vấn đề

GVHD: PSG. TS. Dương Tuấn Anh

giải quyết vấn đề ‘Nhận dạng motifs trên dữ liệu chuỗi thời gian không cần xác
định thông số chiều dài’.

1.3 Những kết quả đạt được
Luận văn đã đạt được một số kết quả sau đây
• Hiện thực thành cơng giải thuật phát hiện motif (motif discovery - MD) dựa
vào nguyên lý MDL do Tanaka, Iwamoto và Uehara đề xuất 2005 [5]. Giải
thuật này chỉ cho phép phát hiện các motif có chiều dài bằng nhau.
• Hiện thực thành cơng giải thuật mở rộng (extended motif discovery - EMD)
dựa vào nguyên lý MDL kết hợp với độ đo xoắn thời gian động
(EMD|DTW) do Tanaka, Iwamoto và Uehara đề xuất 2005 [5]. Giải thuật
này cho phép phát hiện các motif có chiều dài khác nhau.
• Luận văn đã cải tiến giải thuật EMD|DTW bằng cách áp dụng phép vị tự
(Homothetic Transformation - HT) kết hợp với độ đo Euclid. Giải thuật cải
tiến này được gọi là EMD|HT. Trong giải thuật này, độ đo DTW khơng cịn
được sử dụng nữa mà thay vào đó là dùng phép vị tự để làm cho hai chuỗi
thời gian có độ dài khác nhau thành hai chuỗi thời gian có độ dài bằng nhau.
Sau đó, dùng độ đo Euclid để tính khoảng cách giữa hai chuỗi này. Kết quả
thực nghiệm cho thấy, giải thuật EMD|HT cũng cho phép phát hiện các motif
có chiều dài khác nhau và có thời gian thực thi nhanh hơn rất nhiều lần so
với giải thuật EMD|DTW. Đồng thời chất lượng các motif phát hiện được
bởi EMD|HT cũng tốt hơn so với giải thuật EMD|DTW.

1.4 Cấu trúc của luận văn
Cấu trúc của luận văn gồm năm chương và nội dung của mỗi chương như sau

• Chương 1 giới thiệu tóm tắt vấn đề, mục tiêu nghiên cứu của luận văn và
những kết quả mà luận văn đã đạt được.
• Chương 2 giới thiệu cơ sở lý thuyết và các cơng trình liên quan đến phát hiện
motif. Chương này sẽ giới thiệu về các phương pháp về độ đo tương tự giữa
Nguyễn Văn Nhất_10070490

Trang 3


Chương 1: Phát biểu vấn đề

GVHD: PSG. TS. Dương Tuấn Anh

hai chuỗi thời gian, các phương pháp thu giảm số chiều, các phương pháp rời
rạc hoá dữ liệu chuỗi thời gian, các giải thuật phát hiện motif trên dữ liệu
chuỗi thời gian như là giải thuật Brute-Fore, giải thuật chiếu ngẫu nhiên và
giải thuật MK, giải thuật MD và giải thuật EMD|DTW.
• Chương 3 sẽ tập trung vào phương pháp thực hiện giải thuật phát hiện motif
theo một cách tiếp cận mới bằng cách dựa vào nguyên lý MDL do Tanaka,
Iwamoto và Uehara đề xuất năm 2005 [5]. Tiếp theo, chương này sẽ trình
bày về một kỹ thuật để cải tiến giải thuật EMD|DTW mà ba tác giả này đã đề
xuất. Đó là áp dụng phép vị tự kết hợp với độ đo Euclid để tăng hiệu suất
thời gian thực thi của giải thuật mà chất lượng motif phát hiện được cũng rất
tốt. Giải thuật cải tiến này được gọi là EMD|HT.
• Chương 4 hiện thực giải thuật MD, EMD|DTW do Tanaka, Iwamoto và
Uehara đề xuất và giải thuật cải tiến EMD|HT. Tiếp theo, chương này cũng
trình bày các thực nghiệm của các giải thuật này và giải thuật chiếu ngẫu
nhiên đối với các tập dữ liệu thời gian khác nhau như dữ liệu điện tâm đồ
(ECG), dữ liệu điện não đồ (EEG), dữ liệu Memory, dữ liệu Power và dữ
liệu ERP. So sánh và đánh giá kết quả thu được bao gồm thời gian thực thi,

độ chính xác và khả năng đáp ứng với chuỗi dữ liệu lớn giữa các giải thuật
trên. Ngồi ra chương này cũng trình bày tính hiệu quả (efficiency) của giải
thuật EMD|HT đối với các tập dữ liệu được thực nghiệm.
•

Chương 5 trình bày một số kết quả đạt được và hướng phát triển của luận
văn.

Nguyễn Văn Nhất_10070490

Trang 4


Chương 2: Cơ sở lý thuyết và các cơng trình liên quan

GVHD: PSG. TS. Dương Tuấn Anh

CHƯƠNG 2
CƠ SỞ LÝ THUYẾT VÀ CÁC CƠNG TRÌNH LIÊN
QUAN
Chương này sẽ giới thiệu về cơ sở lý thuyết và những cơng trình liên quan để phát
hiện motif trên dữ liệu chuỗi thời gian. Nội dung chính của chương này sẽ trình bày
về các phương pháp tính độ đo tương tự giữa hai chuỗi thời gian, phương pháp thu
giảm số chiều, phương pháp rời rạc hoá dữ liệu chuỗi thời gian, các giải thuật phát
hiện motif như là Brute-Force, giải thuật chiếu ngẫu nhiên giải thuật MK, giải thuật
MD và giải thuật EMD|DTW.

2.1 Các độ đo tương tự
Có nhiều độ đo tương tự đã được sử dụng để tính độ tương tự giữa hai chuỗi thời
gian. Việc chọn một độ đo tương tự là tùy thuộc rất nhiều vào miền ứng dụng và

trong nhiều trường hợp thì một độ đo thuộc chuẩn Lp đơn giản như độ đo Euclid là
đủ tốt để dùng. Tuy nhiên trong nhiều trường hợp thì độ đo Euclid lại q cứng
nhắc vì khơng thích nghi được với những phép biến đổi như tịnh tiến (shifting), co
giãn biên độ (scaling) hay xoắn trục thời gian (time warping). Nhiều phương pháp
tìm kiếm tương tự mới hơn dựa vào những độ đo tương tự mềm dẻo và vững chắc
hơn như độ đo xoắn thời gian động (Dynamic Time Warping - DTW), độ đo chuỗi
con chung dài nhất.

2.1.1 Độ đo Euclid
Khi xem xét các dạng biểu diễn khác nhau của dữ liệu chuỗi thời gian, ta có thể
định nghĩa độ đo khoảng cách cho chúng. Cho tới bây giờ, độ đo khoảng cách phổ
biến nhất cho chuỗi thời gian là độ đo khoảng cách Euclid.
Cho 2 chuỗi thời gian Q và C có cùng chiều dài n, công thức 2.1 định nghĩa
khoảng cách Euclid của chúng và Hình 2.1 minh hoạ cho độ đo trực quan này.

Nguyễn Văn Nhất_10070490

Trang 5


Chương 2: Cơ sở lý thuyết và các cơng trình liên quan

,

≡

GVHD: PSG. TS. Dương Tuấn Anh

−


2.1

Hình 2.1 Minh hoạ độ đo Euclid giữa hai chuỗi thời gian [1]

2.1.2 Độ đo xoắn thời gian động
Việc so trùng hai đường biểu diễn dữ liệu bằng cách tính khoảng cách từng cặp
điểm 1-1 (điểm thứ i của đường thứ I so với điểm thứ i của đường thứ II) là không
phù hợp trong trường hợp hai đường này khơng hồn tồn giống nhau nhưng hình
dạng biến đổi rất giống nhau. Như trong Hình 2.2, hai đường biểu diễn rất giống
nhau về hình dạng nhưng lệch nhau về thời gian. Trong trường hợp này, nếu tính
khoảng cách bằng cách ánh xạ 1-1 giữa hai đường thì kết quả rất khác nhau và có
thể dẫn đến kết quả cuối cùng khơng giống như mong muốn.
Vì vậy để khắc phục nhược điểm này, thì một điểm có thể ánh xạ với nhiều
điểm và ánh xạ này khơng thẳng hàng (xem Hình 2.2). Phương pháp này gọi là
xoắn thời gian động (DTW) được đề xuất bởi Bern và Clifford, 1994 [9].
Khoảng cách giữa hai chuỗi thời gian có thể tính như sau

Nguyễn Văn Nhất_10070490

Trang 6


Chương 2: Cơ sở lý thuyếtt và các cơng trình liên quan

GVHD: PSG
SG. TS. Dương Tuấn Anh

Cho hai chuỗii thời
th gian X và Y và một thông số khung w gọi là khung cửa sổ
xoắn (warping window

ow) với điều kiện là hai điểm i và j có thể ánh xạ với nhau nếu
|i-j|≤w. Dữ liệu ra là tổổng khoảng cách của các điểm được ánh xạ
x với nhau.

Hình 2.2
2 Cách ánh xạ trong tính độ đo xoắn thời gian độn
ng [9]

Cách tính đơn giản
g
DTW là xây dựng một ma trận Dmxn
xn với m=|X| và n=|Y|.
Khi đó Dij = d(xi, yi).. Từ
T ma trận D tiến hành duyệt qua ma trậnn từ ô (0,0) đến ô (m,
n) thoả mãn ràng buộcc sau
• Khơng được đi qqua trái hay đi xuống.
• Đường đi phảii liên
l tục.
• Ơ tại vị trí (i, j) thuộc đường đi phải thoả |i – j| ≤ w.
•

Giả sử có K ơ đi
đ từ ơ (0, 0) đến ô (m, n) thoả mãn những
ng điều kiện trên, khi
đó
,

min

∑


#

!

w ∀

2.2

Hình 2.3 minhh hoạ
h phương pháp tính khoảng cách theoo DTW.
D
Phương pháp
này phù hợp cho việcc xác định độ tương tự giữa hai chuỗi thờ
ời gian có hình dạng
Nguyễn Văn Nhất_100704
0490

Trang 7


Chương 2: Cơ sở lý thuyết và các cơng trình liên quan

GVHD: PSG. TS. Dương Tuấn Anh

giống nhau nhưng chiều dài hình dạng về mặt thời gian khác nhau. Phương pháp
này cho kết quả chính xác hơn phương pháp tính khoảng cách Euclid, đặc biệt trong
các bài tốn có dữ liệu nhỏ, bài toán phân loại (classification) hay các bài tốn gom
cụm (clustering), …


Hình 2.3 Minh hoạ cách tính khoảng cách theo DTW [9]

Tuy nhiên nhược điểm lớn nhất của phương pháp này là thời gian chạy, có
thể gấp hàng trăm hoặc nghìn lần phương pháp độ đo Euclid. Giải thuật DTW lúc
đầu đưa ra thông số w = n (chiều dài dữ liệu), khi đó độ phức tạp thuật tốn là
O(n2). Do đó để độ phức tạp của thuật tốn giảm xuống cịn O(wn) thì thơng số w
thường được chọn sao cho w rất nhỏ so với n.

2.2 Phương pháp thu giảm số chiều xấp xỉ gộp từng đoạn
PAA
Dữ liệu chuỗi thời gian thường có kích thước rất lớn. Trên cơ sở đó, một số phương
pháp đã được sử dụng để chuẩn hóa lại dữ liệu thu thập thành một tập dữ liệu nhỏ
hơn đặc trưng cho dữ liệu đó. Bằng phương pháp này, thay vì thao tác truy vấn trên
dữ liệu chuỗi thời gian ban đầu, thì có thể thao tác trên dữ liệu chuỗi thời gian được
Nguyễn Văn Nhất_10070490

Trang 8


Chương 2: Cơ sở lý thuyết và các cơng trình liên quan

GVHD: PSG. TS. Dương Tuấn Anh

chuẩn hóa để giảm chi phí thời gian thao tác và khi cần cũng có thể chuyển dữ liệu
chuỗi thời gian đã chuẩn hóa này thành chuỗi thời gian ban đầu. Phương pháp này
gọi là phương pháp thu giảm số chiều dữ liệu. Một trong những phương pháp thu
giảm số chiều phổ biến nhất là phương pháp xấp xỉ gộp từng đoạn (Piecewise
Aggregate Approximation - PAA).
Phương pháp PAA do E.Keogh và cộng sự đề nghị năm 2001 [8]. Phương
pháp này cho phép một chuỗi thời gian có độ dài bất kỳ n có thể được thu giảm

thành một chuỗi có chiều dài bất kỳ w, (w < n, thường w << n). Số lượng chữ cái là
một số nguyên a bất kỳ với a > 2. Bảng sau đây tóm tắt các ký hiệu được dùng
trong phương pháp này
̅ Một PAA của một chuỗi thời gian ̅ = ̅1,…, ̅w

C Một chuỗi thời gian C = c1,…,cn

% Một dạng biểu diễn ký hiệu của chuỗi thời gian % = ̂ 1,… ̂ w

w Số thành phần của chuỗi thời gian được biểu diễn bởi PAA hay từ
A Kích thước bản ký tự (ví dụ, cho bảng chữ cái = {a, b, c}, a = 3)

gian w-chiều bằng một vector ̅ = 1̅ ,…, w̅ . Thành phần thứ i của ̅ được tính tốn

Một chuỗi thời gian C có chiều dài n có thể được biểu diễn trong một không

bởi công thức sau

(∋



)
∗

,
−

,
+

!
−

.

+

2.3

Phát biểu một cách đơn giản, để giảm chuỗi thời gian từ n-chiều thành wchiều, dữ liệu được chia thành w khung (frame) có kích thước bằng nhau. Giá trị có
nghĩa của dữ liệu sẽ rơi vào khung được tính tốn và vector của những giá trị này
trở thành sự biểu diễn dữ liệu được rút giảm. Sự biểu diễn này có thể được minh

Nguyễn Văn Nhất_10070490

Trang 9