So sánh hiệu quả của hai độ đo Euclide và DTW được sử dụng trong bài toán phát hiện Motif trên chuỗi thời gian :Luận văn thạc sĩ - Chuyên ngành: Khoa học máy tính

iv

LỜI CAM ĐOAN

Trong bài luận văn này, tôi xin cam đoan các kết quả báo cáo, kết quả thực nghiệm

và chương trình trong luận văn này do chính tôi nghiên cứu và thực hiện, ngoài các

tài liệu tham khảo đã được trích dẫn tôi không có sự sao chép từ những công trình

nghiên cứu khác.

Tất cả kiến thức tôi được học ở trường, các tài liệu tham khảo và từ thầy hướng dẫn,

tôi khẳng định rằng bài luận văn này do chính tôi thực hiện. Nếu có bất cứ sai phạm

nào trong luận văn này, tôi xin chịu trách nhiệm.

Xin cám ơn.

Học viên

Nguyễn Tài Dư

v

MỤC LỤC

1. Đặt vấn đề ...............................................................................................................1

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

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

4. Cách tiếp cận và phương pháp nghiên cứu .............................................................5

5. Ý nghĩa thực tiễn của đề tài.....................................................................................5

1.1 Các khái niệm cơ bản ............................................................................................6

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

Khai thác dữ liệu chuỗi thời gian .....................................................................7

Phát hiện motif trên chuỗi thời gian.................................................................8

Chuỗi thời gian (Timeseries )...........................................................................9

Chuỗi con (Subsequence).................................................................................9

Cửa sổ trượt (Slide window)..........................................................................10

Khớp (Match).................................................................................................10

Khớp tầm thường (Trivial match)..................................................................11

Khớp không tầm thường (Non-Trivial matches) ...........................................11

K-Motif...........................................................................................................12

1.2 Các độ đo khoảng cách chuỗi thời gian..............................................................12

1.2.1 Các độ đo trong không gian Euclide ..............................................................13

1.2.2 Độ đo xoắn thời gian động (DTW) ................................................................15

1.3 Các phương pháp thu giảm số chiều dựa vào đặc trưng ....................................18

Các phương pháp biến đổi sang miền tần số..................................................19

vi

Phương pháp biến đổi Fourier (DFT)...........................................................19

Phương pháp Wavelet (DWT ).....................................................................19

Các phương pháp xấp xỉ tuyến tính từng đoạn ..............................................20

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

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

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

Phương pháp xấp xỉ gộp từng đoạn mở rộng EPAA....................................23

1.4 Phương pháp rời rạc hóa dữ liệu ........................................................................24

Phương pháp rời rạc hóa xấp xỉ gộp ký tự SAX...........................................24

1.4.2 Phương pháp rời rạc hóa dữ liệu theo phép biến đổi ESAX..........................25

2.1 Độ đo Euclide .....................................................................................................27

2.2 Độ đo Dynamic Time Warping (DTW) .............................................................28

2.3 Chuẩn hóa dữ liệu...............................................................................................33

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

2.5 Rời rạc hóa dữ liệu với phương pháp SAX........................................................37

2.6 Hàm tính độ đo tương tự MinDIST....................................................................38

2.7 Cải tiến thuật toán xoắn thời gian động..............................................................40

3.1 Định nghĩa motif trên chuỗi thời gian ................................................................42

3.2 Độ hiệu quả của giải thuật tìm kiếm motif.........................................................42

3.3 Tìm 1-Motif bằng thuật toán Brute-force...........................................................43

3.4 Tìm 1-Motif bằng thuật toán MK.......................................................................45

3.5 Giới hạn dưới của DTW.....................................................................................49

Giới hạn dưới của Kim và cộng sự. ...............................................................50

Giới hạn dưới của Yi và cộng sự....................................................................51

FTW (Fast search method for dynamic Time Warping)................................51

LB_ Improved được cải thiện bởi Lemire, 2009............................................53

3.5.5 LB_Keogh giới thiệu bởi Keogh và cộng sự, 2002 .......................................55

vii

4.1 Môi trường và dữ liệu thực nghiệm....................................................................57

Môi trường thực nghiệm ................................................................................57

Dữ liệu thực nghiệm.......................................................................................57

4.2 Chương trình thực nghiệm .................................................................................58

Mô hình thực nghiệm các giải thuật...............................................................60

Kết quả thực nghiệm trên các bộ dữ liệu .......................................................60

Thực nghiệm trên dữ liệu gốc.......................................................................61

Thực nghiệm trên dữ liệu thu giảm chiều.....................................................75

1. Kết luận .................................................................................................................90

2. Kiến nghị...............................................................................................................90

viii

DANH MỤC HÌNH ẢNH

Hình 01 Chuỗi thời gian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

Hình 02 Motif trong chuỗi thời gian là mẫu xuất hiện với tần suất cao nhất . . . . 03

Hình 03 Motif có chiều dài 640, từ vị trí 589 và 8,895 . . . . . . . . . . . . . . . . . . . . . 03

Hình 1.1 Chuỗi thời gian lượng mưa tại trạm khí tượng Điện Biên (1961-2011) . 06

Hình 1.2 Một motif của chuỗi dữ liệu thời gian . . . . . . . . . . . . . . . . . . . . . . . . . . 08

Hình 1.3 Chuỗi con Y1,Y2 … Yi, được trích xuất từ chuỗi thời gian T . . . . . . . . 10

Hình 1.4 Chuỗi con được trích xuất bởi một cửa sổ trượt . . . . . . . . . . . . . . . . . . 10

Hình 1.5 Chuỗi con C (dòng in đậm) và chuỗi M tương ứng khớp với C . . . . . . 10

Hình 1.6 Chuỗi con C khớp tầm thường . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

Hình 1.7 Khoảng cách hai motif < 2R (A); Khoảng cách hai motif > 2R (B) . . . . 12

Hình 1.8 Độ đo Minkowski giữa hai chuỗi con . . . . . . . . . . . . . . . . . . . . . . . . . . 13

Hình 1.9 (a) Đường cơ bản khác nhau; (b) Độ giao động khác nhau . . . . . . . . . . 14

Hình 1.10 Đường xoắn ( Waping path) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

Hình 1.11 (A) Độ đo Euclide; (B) Dynamic Time Warping giữa hai chuỗi con . . 16

Hình 1.12 Hai chuỗi thời gian Q, C trên mặt phẳng lưới n ×m và đường xoắng . . 16

Hình 1.13 Phép biến đổi DFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

Hình 1.14 Phép biến đổi DWT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

Hình 1.15 Phép biến đổi PLA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

Hình 1.16 Phép biến đổi PAA với n =128, w = 8 . . . . . . . . . . . . . . . . . . . . . . . . . 21

Hình 1.17 Phép biến đổi APCA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

Hình 1.18 Vài điểm quang trọng bị mất khi chỉ biểu diễn bằng PAA . . . . . . . . . 23

Hình 1.19 Vị trí của ba giá trị quan trọng, pmax, pmid,pmin là vị trí tương ứng . . . 24

Hình 1.20 Phép biến đổi rời rạc hóa SAX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

Hình 1.21 Dữ liệu chuỗi thời gian tài chính được biểu diễn bởi Extended SAX . 26

Hình 2.1 Phần tử thứ i của chuỗi Q tương ứng với phần tử i chuỗi C . . . . . . . . . . 27

Hình 2.2 Các phần tử i chuỗi Q ánh xạ đến từng phần tử i của chuỗi C . . . . . . . 28

Hình 2.3 Đường xoắn W của hai chuỗi con dữ liệu thời gian Q,C . . . . . . . . . . . . 29

Hình 2.4 Đồ thị biểu diễn hay chuỗi thời gian Q,C . . . . . . . . . . . . . . . . . . . . . . . 30

ix

Hình 2.5 Giới hạn dưới: Sakoe-Chiba band & Itakura parallelogram . . . . . . . . . . 32

Hình 2.6 Những điểm cho phép ánh xạ phải nằm trong cửa sổ xoắn r . . . . . . . . . 32

Hình 2.7 Phương pháp chuẩn hóa trung bình zero . . . . . . . . . . . . . . . . . . . . . . . . . 34

Hình 2.8 Phương pháp thu giảm số chiều dữ liệu xấp xỉ PAA . . . . . . . . . . . . . . . 36

Hình 2.9 Chuỗi X biến đổi thu giam chiều thành X’ bằng xấp xỉ PAA . . . . . . . . 36

Hình 2.10 Bảng thống kê dùng để tra những điểm ngắt theo phân bố Gauss . . . . 37

Hình 2.11 Rời rạc hóa về chuỗi ký tự từ chuỗi dữ liệu gốc . . . . . . . . . . . . . . . . . . 38

Hình 2.12 Khoảng cách giữa hai chuỗi gốc (A) và hai chuỗi thu giảm chiều (B) . . . . 38

Hình 2.13 (A) Alphabet size: a = 3, (B) khoảng cách Q̂ và Ĉ khi đã rời rạc hóa . . 39

Hình 2.14 (a) bảng tra cứu hàm Dist, (b) công thức tính các giá trị trong bảng . . . 39

Hình 2.15 Độ chặt chặn dưới của hàm MINDIST với hệ số a và w tương ứng . . . 40

Hình 2.16 (A) hai chuỗi thời gian được tính DTW. Và được tính bởi PDTW (B) . 41

Hình 3.1 (A) Tập dữ liệu chuỗi thời gian 2 chiều trong không gian gốc, (B) Những

đối tượng được sắp xếp đến điểm tham chiếu O1. (C) Khoảng cách giữa các cặp liền

kề chiếu trên không gian 1 chiều . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

Hình 3.2 Tính khoảng cách thực của các đối tượng từ trái qua phải . . . . . . . . . . 46

Hình 3.3 Điều kiện cần khi cả hai đối tượng phải giao nhau qua một cửa sổ trượt . . . . 47

Hình 3.4 Giới hạn phạm vi của đường xoắn, hạn chế chúng đến vùng màu xám . 50

Hình 3.5 Phương pháp giới hạn dưới được giới thiệu bởi Kim et.a. . . . . . . . . . . . 50

Hình 3.6 Phương pháp giới hạn dưới được giới thiệu bởi Yi et.a . . . . . . . . . . . . . 51

Hình 3.7 Một chuỗi thời gian xấp xỉ bằng cách chia nó thành ba phân đoạn . . . 52

Hình 3.8 (A) LB_Keogh lower bounding và (B) LB_Improved lower bounding 54

Hình 3.9 Các dãy U và L được tạo cho chuỗi thời gian Q trong hai trường hợp . . 55

Hình 3.10 Giới hạn dưới LB_Keogh trong hai trường hợp . . . . . . . . . . . . . . . . . 56

Hình 4.1 Giao diện chương trinh thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

Hình 4.2 Sơ đồ cây chương trình thực nghiệm trên dữ liệu gốc & thu giảm chiều .60

Hình 4.3 Cặp motif tìm được trên Brute-force (EEG; 500; 80) . . . . . . . . . . . . . . . 62

Hình 4.4 Cặp motif tìm được trên MK (EEG; 500; 80) . . . . . . . . . . . . . . . . . . . . . 62

Hình 4.5 Cặp motif tìm được trên Brute-force (EEG; 500; 128) . . . . . . . . . . . . . . 63

Hình 4.6 Cặp motif tìm được trên MK (EEG; 500; 128) . . . . . . . . . . . . . . . . . . . . 63

x

Hình 4.7 Cặp motif tìm được trên Brute-force (EEG; 1000; 80) . . . . . . . . . . . . . . 64

Hình 4.8 Cặp motif tìm được trên MK (EEG; 1000; 80) . . . . . . . . . . . . . . . . . . . . 65

Hình 4.9 Cặp motif tìm được trên Brute-force (EEG; 1000; 128) . . . . . . . . . . . . . 65

Hình 4.10 Cặp motif tìm được trên (EEG; 1000; 128) . . . . . . . . . . . . . . . . . . . . . 66

Hình 4.11 Cặp motif tìm được trên Brute-force (Chromosome; 500; 80) . . . . . . . . 67

Hình 4.12 Cặp motif tìm được trên MK (Chromosome; 500; 80) . . . . . . . . . . . . . . 67

Hình 4.13 Cặp motif tìm được trên Brute-force (Chromosome; 500; 128) . . . . . . . 68

Hình 4.14 Cặp motif tìm được trên MK (Chromosome; 500; 128) . . . . . . . . . . . . . 68

Hình 4.15 Cặp motif tìm được trên Brute-force (Chromosome;1000; 80) . . . . . . . 69

Hình 4.16 Cặp motif tìm được trên MK (Chromosome;1000; 80) . . . . . . . . . . . . . 69

Hình 4.17 Cặp motif tìm được trên Brute-force (Chromosome;1000; 128) . . . . . . 70

Hình 4.18 Cặp motif tìm được trên MK (Chromosome;1000; 128) . . . . . . . . . . . . 70

Hình 4.19 Cặp motif tìm được trên Brute-force (Stock;500; 80) . . . . . . . . . . . . . . 71

Hình 4.20 Cặp motif tìm được trên MK (Stock;500; 80) . . . . . . . . . . . . . . . . . . . . 72

Hình 4.21 Cặp motif tìm được trên Brute-force (Stock;500; 128) . . . . . . . . . . . . . 72

Hình 4.22 Cặp motif tìm được trên MK (Stock;500; 128) . . . . . . . . . . . . . . . . . . . 73

Hình 4.23 Cặp motif tìm được trên Brute-force (Stock;1000; 80) . . . . . . . . . . . . . 74

Hình 4.24 Cặp motif tìm được trên MK (Stock;1000; 80) . . . . . . . . . . . . . . . . . . . 74

Hình 4.25 Cặp motif tìm được trên Brute-force (Stock;1000; 128) . . . . . . . . . . . . 75

Hình 4.26 Cặp motif tìm được trên MK (Stock;1000; 128) . . . . . . . . . . . . . . . . . . 75

Hình 4.27 Cặp motif tìm được trên Brute-force (EEG; 800; 256; 32) . . . . . . . . . . 77

Hình 4.28 Cặp motif tìm được trên MK (EEG; 800; 256; 32) . . . . . . . . . . . . . . . . 77

Hình 4.29 Cặp motif tìm được trên Brute-force (EEG; 800; 512; 32) . . . . . . . . . . 78

Hình 4.30 Cặp motif tìm được trên MK (EEG; 800; 512; 32) . . . . . . . . . . . . . . . 78

Hình 4.31 Cặp motif tìm được trên Brute-force (EEG; 3000; 256; 32) . . . . . . . . . 80

Hình 4.32 Cặp motif tìm được trên MK (EEG; 3000; 256; 32) . . . . . . . . . . . . . . . 80

Hình 4.33 Cặp motif tìm được trên Brute-force (EEG; 3000; 512; 32) . . . . . . . . . 81

Hình 4.34 Cặp motif tìm được trên MK (EEG; 3000; 512; 32) . . . . . . . . . . . . . . . 81

Hình 4.35 Cặp motif tìm được trên Brute-force (Chromosome; 800; 256; 32) . . . 82

Hình 4.36 Cặp motif tìm được trên MK (Chromosome; 800; 256; 32) . . . . . . . . . 83

xi

Hình 4.37 Cặp motif tìm được trên Brute-force (Chromosome; 800; 512; 32) . . . 84

Hình 4.38 Cặp motif tìm được trên MK (Chromosome; 800; 512; 32) . . . . . . . . . 84

Hình 4.39 Cặp motif tìm được trên Brute-force (Chromosome; 3000; 256; 32) . . 85

Hình 4.40 Cặp motif tìm được trên MK (Chromosome; 3000; 256; 32) . . . . . . . . 85

Hình 4.41 Cặp motif tìm được trên Brute-force (Chromosome; 3000; 512; 32) . . 86

Hình 4.42 Cặp motif tìm được trên MK (Chromosome; 3000; 512; 32) . . . . . . . . 87

Hình 4.43 Cặp motif tìm được trên Brute-force (Stock; 800; 256; 32) . . . . . . . . . 88

Hình 4.44 Cặp motif tìm được trên MK (Stock; 800; 256; 32) . . . . . . . . . . . . . . . . 88

Hình 4.45 Cặp motif tìm được trên Brute-force (Stock; 3000; 256; 32) . . . . . . . . . 89

Hình 4.46 Cặp motif tìm được trên MK (Stock 3000; 256; 32) . . . . . . . . . . . . . . . 89

xii

DANH MỤC BẢNG BIỂU

Bảng 2.1 Ma trận tính khoảng cách tích lũy của hai chuỗi thời gian Q,C . . . . . . . 30

Bảng 2.2 Kết quả chuẩn hóa Min max . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

Bảng 3.1 Giải thuật Brute-force tìm 1-Motif trên dữ liệu chuỗi thời gian . . . . . . . 44

Bảng 3.2 Giải thuật Mueen – Keogh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

Bảng 4.1 Mô tả chức năng của chương trình thực ngiệm . . . . . . . . . . . . . . . . . . . 58

Bảng 4.2 Kết quả thực nghiệm trên Brute-force & MK (EEG; 500; 80) . . . . . . . . 61

Bảng 4.3 Kết quả thực nghiệm trên Brute-force & MK (EEG; 500; 128) . . . . . . . 63

Bảng 4.4 Kết quả thực nghiệm trên Brute-force & MK (EEG; 1000; 80) . . . . . . . 64

Bảng 4.5 Kết quả thực nghiệm trên Brute-force & MK (EEG; 1000; 128) . . . . . . 65

Bảng 4.6 Kết quả thực nghiệm trên Brute-force & MK (Chromosome; 500; 80) . 66

Bảng 4.7 Kết quả thực nghiệm trên Brute-force & MK (Chromosome; 500; 128) .67

Bảng 4.8 Kết quả thực nghiệm trên Brute-force & MK (Chromosome;1000;80) . 68

Bảng 4.9 Kết quả thực nghiệm trên Brute-force & MK (Chromosome;1000;128) .70

Bảng 4.10 Kết quả thực nghiệm trên Brute-force & MK (Stock;500; 80) . . . . . . . 71

Bảng 4.11 Kết quả thực nghiệm trên Brute-force & MK (Stock;500; 128) . . . . . . 72

Bảng 4.12 Kết quả thực nghiệm trên Brute-force & MK (Stock;1000; 80) . . . . . . 73

Bảng 4.13 Kết quả thực nghiệm trên Brute-force & MK (Stock;1000; 128) . . . . . 74

Bảng 4.14 Kết quả thực nghiệm trên Brute-force & MK (EEG; 800; 256) . . . . . . 76

Bảng 4.15 Kết quả thực nghiệm trên Brute-force & MK (EEG; 800; 512) . . . . . . 77

Bảng 4.16 Kết quả thực nghiệm trên Brute-force & MK (EEG; 3000; 256) . . . . . 79

Bảng 4.17 Kết quả thực nghiệm trên Brute-force & MK (EEG; 3000; 512) . . . . . 80

Bảng 4.18 Kết quả thực nghiệm trên Brute-force & MK(Chromosome;800;256) 82

Bảng 4.19 Kết quả thực nghiệm trên Brute-force & MK(Chromosome;800;512) 83

Bảng 4.20 Kết quả thực nghiệm trên Brute-force &MK(Chromosome;3000;256) 84

Bảng 4.21 Kết quả thực nghiệm trên Brute-force &MK(Chromosome;3000;512) 86

Bảng 4.22 Kết quả thực nghiệm trên Brute-force & MK (Stock; 800; 256;32) . . 87

Bảng 4.23 Kết quả thực nghiệm trên Brute-force & MK (Stock; 3000; 256;32) . . 89

xiii

DANH MỤC TỪ VIẾT TẮT

APCA Adaptive Piecewise Constant Approximation

DFT Discrete Fourier Transform

DTW Dynamic Time Warping

DWT Discrete Wavelet Transform

EMD Extended Motif Discovery

EPAA Extanded Piecewise Aggregate Approximation

ESAX Extended Symbolic Aggregate approximation

FTW Fast search method for dynamic Time Warping

LB_ Improved Lower Bounding Improved

LB_Keogh Lower Bounding Keogh

MK Mueen Keogh

PAA Piecewise Aggregate Approximation

PDTW Piecewise Dynamic Time Warping

PLA Piecewise Linear Approximation

SAX Symbolic Aggregate approXimation