Tài liệu Khai phá dữ liệu chuỗi thời gian dựa vào rút trích đặc trưng bằng phương pháp điểm giữa và kỹ thuật xén

MỤC LỤC DANH MỤC CÁC HÌNH ẢNH..................................................................................... ix DANH MỤC BẢNG BIỂU .......................................................................................... xiv DANH MỤC CÁC TỪ VIẾT TẮT .............................................................................. xvi CHƢƠNG 1. GIỚI THIỆU .............................................................................................. 1 1.1 Dữ liệu chuỗi thời gian và các bài toán khai phá dữ liệu liên quan. ..................1 1.2 Mục tiêu, đối tƣợng và phạm vi nghiên cứu. ..................................................... 4 1.3 Nhiệm vụ và hƣớng tiếp cận của luận án. .......................................................... 5 1.4 Tóm tắt kết quả đạt đƣợc. ...................................................................................7 1.5 Cấu trúc của luận án. .......................................................................................... 9 CHƢƠNG 2. CƠ SỞ LÝ THUYẾT VÀ CÁC CÔNG TRÌNH LIÊN QUAN .............. 10 2.1 Các độ đo tƣơng tự. .......................................................................................... 10 2.1.1 Độ đo Euclid. ............................................................................................... 10 2.1.2 Độ đo xoắn thời gian động. ..........................................................................11 2.2 Thu giảm số chiều chuỗi thời gian. ..................................................................12 2.2.1 Điều kiện chặn dƣới. .................................................................................... 12 2.2.2 Các phƣơng pháp thu giảm số chiều dựa vào rút trích đặc trƣng. ...............13 2.2.3 Về tính đúng đắn và tính khả chỉ mục của các phƣơng pháp thu giảm số chiều. ............................................................................................................20 2.3 Rời rạc hóa chuỗi thời gian. .............................................................................21 2.4 Cấu trúc chỉ mục. .............................................................................................. 22 2.4.1 R-tree. ...........................................................................................................22 2.4.2 Chỉ mục đƣờng chân trời. ............................................................................24 2.5 Tìm kiếm tƣơng tự trên dữ liệu chuỗi thời gian. ..............................................26 2.5.1 Ý tƣởng tổng quát. ....................................................................................... 26 2.5.2 So trùng toàn chuỗi và so trùng chuỗi con. ..................................................26 2.5.3 Độ đo khoảng cách nhóm và điều kiện chặn dƣới nhóm. ............................ 27 2.5.4 Các phƣơng pháp tìm kiếm tƣơng tự liên quan. ..........................................27 2.6 Tìm kiếm tƣơng tự trên chuỗi thời gian dạng luồng. .......................................28 2.7 Phát hiện motif trên chuỗi thời gian. ................................................................ 31 2.7.1 Các khái niệm cơ bản về motif. ...................................................................31 2.7.2 Tổng quan về một số phƣơng pháp phát hiện motif tiêu biểu. .................... 35 2.8 Gom cụm dữ liệu chuỗi thời gian. ....................................................................40 2.8.1 Giới thiệu. ....................................................................................................40 2.8.2 Giải thuật K-Means. ..................................................................................... 41 vi 2.8.3 Gom cụm bằng thuật toán I-k-Means. ......................................................... 42 CHƢƠNG 3. THU GIẢM SỐ CHIỀU CHUỖI THỜI GIAN BẰNG PHƢƠNG PHÁP MP_C ....................................................................................................... 45 3.1 Phƣơng pháp thu giảm số chiều MP_C (Middle Points_Clipping). ................45 3.2 Độ đo tƣơng tự trong không gian đặc trƣng MP_C. ........................................48 3.3 Độ phức tạp của giải thuật thu giảm số chiều theo phƣơng pháp MP_C. ........51 3.4 Cấu trúc chỉ mục đƣờng chân trời cho các chuỗi thời gian đƣợc biểu diễn bằng MP_C. ...............................................................................................................52 3.4.1 Vùng bao MP_C (MP_C_BR). ....................................................................52 3.4.2 Hàm tính khoảng cách giữa chuỗi truy vấn Q và MP_C_BR. .................... 53 3.4.3 Chỉ mục đƣờng chân trời cho phƣơng pháp biểu diễn MP_C. .................... 55 3.4.4 Xử lý các câu truy vấn có chiều dài khác nhau. ...........................................57 3.5 Tìm kiếm tƣơng tự trên dữ liệu chuỗi thời gian dạng luồng dựa vào phƣơng pháp MP_C và chỉ mục đƣờng chân trời. ......................................................... 59 3.6 Kết quả thực nghiệm. ....................................................................................... 60 3.6.1 Thực nghiệm về bài toán tìm kiếm tƣơng tự trên dữ liệu chuỗi thời gian. ..61 3.6.2 Thực nghiệm về tìm kiếm tƣơng tự trên dữ liệu chuỗi thời gian dạng luồng. . .................................................................................................................... 73 CHƢƠNG 4. PHÁT HIỆN MOTIF DỰA VÀO CẤU TRÚC CHỈ MỤC ĐA CHIỀU HOẶC CHỈ MỤC ĐƢỜNG CHÂN TRỜI ............................................. 78 4.1 Phƣơng pháp phát hiện motif dựa vào cấu trúc chỉ mục đa chiều và kỹ thuật từ bỏ sớm. .............................................................................................................78 4.2 Phát hiện motif xấp xỉ dựa trên phƣơng pháp MP_C với sự hỗ trợ của chỉ mục đƣờng chân trời................................................................................................. 84 4.3 Thực nghiệm về bài toán phát hiện motif......................................................... 87 4.3.1 Thực nghiệm 1: So sánh ba giải thuật dùng R*-tree, RP và R*-tree kết hợp với từ bỏ sớm. .............................................................................................. 88 4.3.2 Thực nghiệm 2: So sánh ba giải thuật dùng R*-tree, RP và MP_C kết hợp với chỉ mục đƣờng chân trời. .......................................................................91 CHƢƠNG 5. GOM CỤM CHUỖI THỜI GIAN ĐƢỢC THU GIẢM THEO PHƢƠNG PHÁP MP_C BẰNG GIẢI THUẬT I-K-MEANS ................................. 96 5.1 Tóm tắt một số kỹ thuật chọn trung tâm cụm khởi động thuật toán k-Means. 96 5.2 Biểu diễn chuỗi thời gian ở nhiều mức xấp xỉ theo phƣơng pháp MP_C. .......98 5.3 Kd-tree. .............................................................................................................98 5.4 Dùng kd-tree để tạo các trung tâm cụm khởi động cho thuật toán I-k-Means. 99 5.5 Dùng CF-tree để tạo các trung tâm cụm khởi động cho thuật toán I-k-Means. ........................................................................................................................102 5.5.1 Đặc trƣng cụm và CF-tree (Cluster Feature tree). .....................................102 vii 5.5.2 Dùng CF-tree để tạo các trung tâm cụm cho thuật toán I-k-Means. ..........104 5.6 Thực nghiệm về bài toán gom cụm. ...............................................................105 5.6.1 Các tiêu chuẩn đánh giá chất lƣợng của giải thuật gom cụm. ...................105 5.6.2 Dữ liệu dùng trong thực nghiệm. ...............................................................107 5.6.3 Kết quả thực nghiệm về bài toán gom cụm. ..............................................108 CHƢƠNG 6. DỰ BÁO DỮ LIỆU CHUỖI THỜI GIAN CÓ TÍNH XU HƢỚNG HOẶC MÙA BẰNG PHƢƠNG PHÁP SO TRÙNG MẪU ................. 114 6.1 Các công trình liên quan. ................................................................................114 6.2 Xu hƣớng và tính mùa trong dữ liệu chuỗi thời gian. ....................................116 6.3 Hai phƣơng pháp dự báo dữ liệu chuỗi thời gian. ..........................................117 6.3.1 Dự báo chuỗi thời gian bằng mạng nơ ron nhân tạo. .................................117 6.3.2 Phƣơng pháp đề xuất: k-lân cận gần nhất. .................................................120 6.4 Đánh giá bằng thực nghiệm. ...........................................................................122 CHƢƠNG 7. KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ............................................. 130 7.1 Các đóng góp chính của luận án. ....................................................................130 7.2 Hạn chế của luận án. .......................................................................................131 7.3 Hƣớng phát triển. ............................................................................................132 CÁC TÀI LIỆU CÔNG BỐ CỦA TÁC GIẢ.............................................................. 133 1. Các công trình liên quan trực tiếp đến luận án. ...................................................133 2. Các công trình liên quan gián tiếp đến luận án. ..................................................134 TÀI LIỆU THAM KHẢO ........................................................................................... 135 Phụ lục A. Chứng minh độ đo DMP_C(Q’, C’) thỏa các tính chất của một không gian metric ..................................................................................................... 147 viii DANH MỤC CÁC HÌNH ẢNH Hình 1.1 Đƣờng biểu diễn một chuỗi thời gian ............................................................... 1 Hình 1.2 Ví dụ về motif là chuỗi con xuất hiện ba lần trong chuỗi thời gian dài hơn. ...3 Hình 2.1 Minh họa hai chuỗi thời gian giống nhau. ...................................................... 10 Hình 2.2 Khoảng cách giữa hai đƣờng biểu diễn rất giống nhau về hình dạng ............11 Hình 2.3 Minh họa phƣơng pháp DFT ..........................................................................14 Hình 2.4 Minh họa phƣơng pháp Haar Wavelet. .......................................................... 15 Hình 2.5 Minh họa phƣơng pháp PAA..........................................................................16 Hình 2.6 Các trƣờng hợp hai đoạn có cùng giá trị trung bình nhƣng khoảng cách Euclid khác nhau. ........................................................................................... 17 Hình 2.7 Minh họa quá trình nhận dạng các điểm PIP..................................................19 Hình 2.8 Minh họa kỹ thuật xén dữ liệu một chuỗi thời gian có chiều dài 64. .............20 Hình 2.9 Minh họa phƣơng pháp SAX với a = 3 .......................................................... 22 Hình 2.10 Minh họa R-tree. ........................................................................................... 23 Hình 2.11 Minh họa các trƣờng hợp MBR có phủ lấp và không phủ lấp ..................... 24 Hình 2.12 Minh họa SBR và SBR xấp xỉ của ba chuỗi thời gian ...................................25 Hình 2.13 Minh họa khung thức do Kontaki và các cộng sự đề xuất. .......................... 30 Hình 2.14 Một ví dụ về các chuỗi tƣơng tự tầm thƣờng ...............................................32 Hình 2.15 (A) Một ví dụ về hai motif có chung một số đối tƣợng và (B) minh họa hai motif thỏa DISTANCE(Ci, Ck) > 2R ............................................................. 33 Hình 2.16 Giải thuật brute-force dùng phát hiện motif bậc nhất theo định nghĩa căn bản. .................................................................................................................34 Hình 2.17 Ví dụ minh họa một chuỗi thời gian T và biểu diễn SAX của các chuỗi con của T ...............................................................................................................36 Hình 2.18 Ví dụ minh họa lần lặp thứ nhất của giải thuật chiếu ngẫu nhiên ................36 Hình 2.19 Một ví dụ minh họa ý tƣởng sử dụng điểm tham chiếu. .............................. 38 Hình 2.20 Các bƣớc chính của thuật toán k-Means. ..................................................... 42 Hình 2.21 Minh họa sự thực thi của thuật toán I-k-Means ...........................................43 Hình 2.22 Các bƣớc chính của thuật toán I-k-Means. ................................................... 43 ix Hình 3.1 Minh họa phƣơng pháp MP_C .......................................................................48 Hình 3.2 Thuật toán thu giảm số chiều chuỗi thời gian bằng phƣơng pháp MP_C. .....48 Hình 3.3 Ví dụ minh họa về MP_C_BR........................................................................53 Hình 3.4 Các bƣớc chính của thuật toán chèn thêm phần tử mới vào cây. ................... 55 Hình 3.5 Thuật toán truy vấn tầm theo ngƣỡng  cho trƣớc. ........................................56 Hình 3.6 Các bƣớc chính của thuật toán tìm k lân cận gần nhất. ..................................56 Hình 3.7 Kết quả thực nghiệm trên các tập dữ liệu khác nhau về độ chặt chặn dƣới của kỹ thuật MP_C so với PAA và xén dữ liệu. (a) So trùng chuỗi con. (b) so trùng toàn chuỗi. ............................................................................................. 63 Hình 3.8 Kết quả thực nghiệm trên các tập dữ liệu khác nhau về độ chặt chặn dƣới của kỹ thuật MP_C so với hai kỹ thuật PAA và xén. (a) So trùng chuỗi con. (b) so trùng toàn chuỗi. ........................................................................................ 63 Hình 3.9 Kết quả thực nghiệm về độ chặt chặn dƣới (trƣờng hợp so trùng chuỗi con) trên năm tập dữ liệu EEG, Economic, Hydrology, Production và Wind, với các tỉ lệ thu giảm số chiều khác nhau: 8 (hình a), 16 (hình b), 32 (hình c), 64 (hình d) và 128 (hình e). .................................................................................64 Hình 3.10 Kết quả thực nghiệm về độ chặt chặn dƣới (trƣờng hợp so trùng chuỗi con) trên năm tập dữ liệu Stock, Consumer, Federal Fund, Mallat Technometrics và Burst, với các tỉ lệ thu giảm số chiều khác nhau: 8 (hình a), 16 (hình b), 32 (hình c), 64 (hình d) và 128 (hình e). ............................................................. 64 Hình 3.11 Kết quả thực nghiệm về độ chặt chặn dƣới (trƣờng hợp so trùng toàn chuỗi) trên năm tập dữ liệu EEG, Economic, Hydrology, Production và Wind, với các tỉ lệ thu giảm số chiều khác nhau: 8 (hình a), 16 (hình b), 32 (hình c), 64 (hình d) và 128 (hình e). .................................................................................65 Hình 3.12 Kết quả thực nghiệm về độ chặt chặn dƣới (trƣờng hợp so trùng toàn chuỗi) trên năm tập dữ liệu Stock, Consumer, Federal Fund, Mallat Technometrics và Burst, với các tỉ lệ thu giảm số chiều khác nhau: 8 (hình a), 16 (hình b), 32 (hình c), 64 (hình d) và 128 (hình e). ............................................................. 65 Hình 3.13 Kết quả thực nghiệm về tỉ lệ thu giảm truy xuất P của so trùng chuỗi con với các tập dữ liệu thực nghiệm khác nhau và chiều dài chuỗi là 1024 (hình a), 512 (hình b). ............................................................................................. 67 x Hình 3.14 Kết quả thực nghiệm về tỉ lệ thu giảm truy xuất P của so trùng toàn chuỗi với các tập dữ liệu thực nghiệm khác nhau và chiều dài chuỗi là 1024 (hình a), 512 (hình b). ............................................................................................. 67 Hình 3.15 Kết quả thực nghiệm về tỉ lệ thu giảm truy xuất P (trục tung) của so trùng chuỗi con (hình a) và so trùng toàn chuỗi (hình b) với các tập dữ liệu thực nghiệm khác nhau (trục hoành). .....................................................................67 Hình 3.16 Kết quả thực nghiệm về tỉ lệ thu giảm truy xuất P (trục tung) theo tỉ lệ thu giảm số chiều khác nhau (trục hoành), với chiều dài chuỗi là 1024. (a). So trùng chuỗi con. (b). So trùng toàn chuỗi....................................................... 68 Hình 3.17 Kết quả thực nghiệm về tỉ lệ lỗi tìm sai theo các tập dữ liệu khác nhau. .....69 Hình 3.18 Kết quả thực nghiệm về chi phí CPU chuẩn hóa theo tỉ lệ thu giảm số chiều khác nhau (a) so trùng toàn chuỗi, (b) và (c) so trùng chuỗi con..................71 Hình 3.19 Kết quả thực nghiệm về chi phí CPU chuẩn hóa theo kích thƣớc dữ liệu, so sánh giữa phƣơng pháp MP_C sử dụng cấu trúc chỉ mục đƣờng chân trời, phƣơng pháp PAA sử dụng chỉ mục đƣờng chân trời và phƣơng pháp PAA sử dụng R*-tree. ............................................................................................. 71 Hình 3.20 (a) Kết quả thực nghiệm về thời gian thu giảm số chiều theo chiều dài chuỗi, (b) thời gian thu giảm số chiều theo tỉ lệ thu giảm khác nhau và (c) thời gian xây dựng cấu trúc chỉ mục theo tỉ lệ thu giảm khác nhau ..............73 Hình 3.21 Kết quả so sánh về tỉ lệ thu giảm truy xuất, thực nghiệm trên dữ liệu Stock với các tỉ lệ thu giảm số chiều khác nhau (8-128) và chiều dài chuỗi truy vấn khác nhau (1024 (a), 512 (b)). ........................................................................74 Hình 3.22 Kết quả so sánh về tỉ lệ thu giảm truy xuất, thực nghiệm trên dữ liệu Consumer với các tỉ lệ thu giảm số chiều khác nhau (8-128) và chiều dài chuỗi truy vấn khác nhau (1024(a), 512 (b)). ................................................74 Hình 3.23 Chi phí CPU chuẩn hóa của MP_C sử dụng chỉ mục đƣờng chân trời so sánh với chỉ mục IDC thực nghiệm trên tập dữ liệu Consumer với (a). Các tỉ lệ thu giảm số chiều khác nhau và (b). Kích thƣớc dữ liệu khác nhau. .........75 Hình 3.24 Chi phí CPU chuẩn của MP_C sử dụng chỉ mục đƣờng chân trời so sánh với chỉ mục IDC thực nghiệm trên tập dữ liệu Stock với các tỉ lệ thu giảm số chiều khác nhau. ............................................................................................. 75 xi Hình 3.25 (a) Thời gian xây dựng chỉ mục; (b) thời gian tính toán gia tăng và cập nhật trì hoãn của kỹ thuật MP_C sử dụng chỉ mục đƣờng chân trời so sánh với chỉ mục IDC. ........................................................................................................76 Hình 4.1 Một ví dụ về cách tính Dregion(s, R).................................................................80 Hình 4.2 Minh họa trực quan ý tƣởng của kỹ thuật từ bỏ sớm .....................................82 Hình 4.3 Thuật toán phát hiện những motif bậc k hàng đầu (theo Định nghĩa 5) với sự hỗ trợ của R*-tree. .......................................................................................... 83 Hình 4.4 Minh họa thuật toán tính khoảng cách Euclid kết hợp với ý tƣởng từ bỏ sớm. ........................................................................................................................ 84 Hình 4.5 Thuật toán phát hiện những motif bậc k hàng đầu (theo Định nghĩa 5) với sự hỗ trợ của chỉ mục đƣờng chân trời. .............................................................. 86 Hình 4.6 Minh họa các bƣớc chính trong hai thuật toán: tìm các lân cận không tầm thƣờng của một chuỗi bằng chỉ mục đƣờng chân trời và chèn chuỗi mới vào chỉ mục. ..........................................................................................................87 Hình 4.7 Các kết quả thực nghiệm về thời gian thực hiện và độ hữu hiệu của ba thuật toán trên tập dữ liệu Stock với chiều dài motif khác nhau và kích thƣớc tập dữ liệu đƣợc chọn cố định (10000 chuỗi). ..................................................... 89 Hình 4.8 Các kết quả thực nghiệm về thời gian thực hiện và độ hữu hiệu của ba thuật toán trên tập dữ liệu Stock với kích thƣớc khác nhau và chiều dài motif cố định là 512. .....................................................................................................89 Hình 4.9 Các kết quả thực nghiệm về thời gian thực hiện và độ hữu hiệu của ba thuật toán trên các tập dữ liệu khác nhau với kích thƣớc cố định (10000 chuỗi) và chiều dài motif cố định là 512. .......................................................................90 Hình 4.10 Kết quả thực nghiệm về thời gian thực hiện của ba thuật toán trên tập dữ liệu Consumer (10000 chuỗi) với chiều dài motif khác nhau. ....................... 91 Hình 4.11 Kết quả thực nghiệm về độ hữu hiệu của ba thuật toán trên tập dữ liệu Consumer (10000 chuỗi) với chiều dài motif khác nhau. .............................. 92 Hình 4.12 Kết quả thực nghiệm về thời gian thực hiện và độ hữu hiệu của ba thuật toán trên tập dữ liệu Consumer có kích thƣớc khác nhau, chiều dài motif đƣợc chọn cố định là 152. ..............................................................................93 xii Hình 4.13 Kết quả thực nghiệm về thời gian thực hiện và độ hữu hiệu của ba thuật toán trên các tập dữ liệu khác có kích thƣớc cố định (10000 chuỗi) và chiều dài motif đƣợc chọn cố định là 152................................................................ 93 Hình 4.14 Minh họa các tập dữ liệu và motif phát hiện đƣợc. ......................................95 Hình 5.1 Sự phân hoạch các đối tƣợng hai chiều và kd-tree tƣơng ứng ....................... 99 Hình 5.2 Ba bƣớc trong quá trình phân hoạch các đối tƣợng hai chiều ......................100 Hình 5.3 Thuật toán dùng kd-tree tạo trung tâm cụm ban đầu ....................................102 Hình 5.4 Minh họa CF-tree. ........................................................................................103 Hình 5.5 Thuật toán dùng CF-tree để tạo trung tâm cụm............................................105 Hình 5.6 Mƣời tập dữ liệu dùng để phát sinh tập dữ liệu Heterogeneous...................107 Hình 5.7 Kết quả thực nghiệm về thời gian gom cụm trên tập dữ liệu Heterogeneous của bốn thuật toán k-Means, I-k-Means, I-k-Means kết hợp với kd-tree và Ik-Means kết hợp với CF-tree .......................................................................109 Hình 5.8 Kết quả thực nghiệm so sánh thời gian thực hiện của bốn thuật toán. .........112 Hình 5.9 Kết quả đếm số lần lặp tích lũy từ mức phân giải thứ hai khi thực hiện ba thuật toán I-k-Means, I-k-Means kết hợp với kd-tree và I-k-Means kết hợp với CF-tree trên tập dữ liệu Production. ......................................................112 Hình 6.1 Quá trình huấn luyện mạng nơ ron dùng cho dự báo dữ liệu chuỗi thời gian ......................................................................................................................118 Hình 6.2 Ý tƣởng cơ bản của cách tiếp cận dựa trên phƣơng pháp so trùng mẫu. .....120 Hình 6.3 Minh họa thuật toán dự báo dựa trên phƣơng pháp so trùng mẫu. ..............121 Hình 6.4 Các bƣớc chính của thuật toán dự báo dựa trên phƣơng pháp so trùng mẫu. ......................................................................................................................122 Hình 6.5 Minh họa bốn tập dữ liệu dùng trong thực nghiệm ......................................123 Hình 6.6 Giải thuật xây dựng mạng nơ ron của Ash. ..................................................124 xiii DANH MỤC BẢNG BIỂU Bảng 2.1 Tổng kết về tính đúng đắn và tính khả chỉ mục của một số phƣơng pháp thu giảm số chiều tiêu biểu. ..................................................................................20 Bảng 4.1 Độ hữu hiệu với chiều dài motif khác nhau (tập dữ liệu Stock). ................... 91 Bảng 4.2 Độ hữu hiệu với các tập dữ liệu khác nhau (chiều dài motif 512). ................91 Bảng 4.3 Độ hữu hiệu với chiều dài motif khác nhau (tập dữ liệu Consumer).............94 Bảng 4.4 Độ hữu hiệu với các tập dữ liệu khác nhau (chiều dài motif 512). ................94 Bảng 5.1 Ví dụ về các xấp xỉ MP_C ở ba mức phân giải đầu tiên................................ 98 Bảng 5.2 Kết quả thực nghiệm về 5 tiêu chuẩn đánh giá trên tập 1000 chuỗi dữ liệu. ......................................................................................................................108 Bảng 5.3 Kết quả thực nghiệm về 5 tiêu chuẩn đánh giá trên tập 2000 chuỗi dữ liệu. ......................................................................................................................108 Bảng 5.4 Kết quả thực nghiệm về 5 tiêu chuẩn đánh giá trên tập 4000 chuỗi dữ liệu. ......................................................................................................................109 Bảng 5.5 Kết quả thực nghiệm về 5 tiêu chuẩn đánh giá trên tập 6000 chuỗi dữ liệu. ......................................................................................................................109 Bảng 5.6 Kết quả thực nghiệm về 5 tiêu chuẩn đánh giá trên tập 8000 chuỗi dữ liệu. ......................................................................................................................109 Bảng 5.7 Kết quả thực nghiệm đánh giá bốn thuật toán bằng hàm mục tiêu theo kích thƣớc dữ liệu.................................................................................................110 Bảng 5.8 Kết quả thực nghiệm đánh giá bốn thuật toán bằng hàm mục tiêu theo năm tập dữ tập khác nhau.....................................................................................111 Bảng 5.9 Kết quả thực nghiệm đánh giá bốn thuật toán bằng hàm mục tiêu theo số cụm khác nhau. .............................................................................................111 Bảng 6.1 Lỗi dự báo khi thực nghiệm trên tập dữ liệu Frazer river với k thay đổi từ 1 đến 10. ..........................................................................................................126 Bảng 6.2 Lỗi dự báo khi thực nghiệm trên tập dữ liệu Frazer river với một số giá trị ngƣỡng T khác nhau. ....................................................................................126 xiv Bảng 6.3 Lỗi dự báo của phƣơng pháp sử dụng thuật toán k lân cận gần nhất so sánh với phƣơng pháp sử dụng thuật toán tìm lân cận trong phạm vi ngƣỡng T cho trƣớc với giá trị k và T tốt nhất. ...................................................................126 Bảng 6.4 Lỗi dự báo của phƣơng pháp sử dụng thuật toán k lân cận gần nhất so sánh với phƣơng pháp ANN. Thực nghiệm đƣợc thực hiện trên tập dữ liệu Temperature. ................................................................................................127 Bảng 6.5 Trung bình lỗi dự báo của phƣơng pháp sử dụng k-NN so sánh với trung bình lỗi dự báo của phƣơng pháp ANN. ......................................................127 Bảng 6.6 Thời gian thực hiện của hai phƣơng pháp thực nghiệm trên bốn tập dữ liệu khác nhau......................................................................................................128 xv DANH MỤC CÁC TỪ VIẾT TẮT ANN Artificial Neural Network CF-tree Cluster Feature tree DTW Dynamic Time Warping DFT Discrete Fourier Transform DWT Discrete Wavelet Transform IDC-Index Incremental Discrete Fourier Transform (DFT) Computation – Index k-NN k-Nearest Neighbors MP_C Middle Points and Clipping MBR Minimum Bounding Rectangle MP_C_BR Middle Points and Clipping Bounding Rectangle MK Mueen Keogh MER Mean error relative to xmean MAE Mean absolute error MLP Multi-layer perceptrons RP Random Projection PAA Piecewise Aggregate Approximation SAX Symbolic Aggregate approXimation SBR Skyline Bounding Region xvi CHƢƠNG 1. GIỚI THIỆU Trong chƣơng này, chúng tôi sẽ trình bày tổng quan về chuỗi thời gian và các bài toán quan trọng trong khai phá dữ liệu chuỗi thời gian. Tiếp theo là mục tiêu, đối tƣợng, phạm vi nghiên cứu của luận án và tóm tắt kết quả nghiên cứu đạt đƣợc. Cuối cùng là cấu trúc của luận án này. 1.1 Dữ liệu chuỗi thời gian và các bài toán khai phá dữ liệu liên quan. Một chuỗi thời gian (time series) là một chuỗi các điểm dữ liệu đƣợc đo theo từng khoảng thời gian liền nhau theo một tần suất thời gian thống nhất. Hình 1.1 minh họa một ví dụ về chuỗi thời gian biểu diễn tỉ giá chuyển đổi trung bình hàng tháng giữa đô la Úc và đô la Mỹ (đơn vị đô la Úc) từ 7/1969 đến 8/1995. Hình 1.1 Đường biểu diễn một chuỗi thời gian ( [1]). Một chuỗi thời gian dạng luồng (streaming time series) C là một chuỗi thời gian trong đó các giá trị mới tới một cách liên tục và đƣợc nối vào cuối chuỗi C theo thứ tự thời gian. Vì một chuỗi thời gian dạng luồng bao gồm một số lớn các giá trị, sự tƣơng tự giữa hai chuỗi thƣờng đƣợc tính dựa trên W giá trị cuối cùng (W là chiều dài cửa sổ trƣợt). Cho nên, nếu W = 1024 thì mỗi chuỗi đƣợc coi nhƣ một điểm trong không gian 1024 chiều. Các bài toán thƣờng đƣợc nghiên cứu trong khai phá dữ liệu chuỗi thời gian gồm tìm kiếm tương tự (similarity search), gom cụm (clustering), phân lớp (classification), 1 phát hiện motif (motif discovery), khai phá luật (rule discovery), phát hiện bất thường (anomaly detection), trực quan hóa (visualization), dự báo (forecast). Những khó khăn và thách thức khi nghiên cứu về dữ liệu chuỗi thời gian [2]: - 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. - 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. Bài toán tìm kiếm tƣơng tự (so trùng) trong cơ sở dữ liệu chuỗi thời gian đã đƣợc nhiều nhà nghiên cứu quan tâm trong những năm qua vì đây là bài toán cơ bản và là một thành phần nền tảng của nhiều bài toán khác trong khai phá dữ liệu chuỗi thời gian. Đây là bài toán khó vì kích thƣớc dữ liệu chuỗi thời gian thƣờng lớn và vì chúng ta không thể lập chỉ mục dữ liệu chuỗi thời gian một cách dễ dàng nhƣ trong hệ thống cơ sở dữ liệu truyền thống. Một vài thí dụ về ứng dụng của tìm kiếm tƣơng tự trên chuỗi thời gian có thể nêu ra nhƣ sau: - Tìm trong quá khứ, những giai đoạn mà số lƣợng sản phẩm bán đƣợc nhƣ tháng vừa rồi. - Tìm những sản phẩm có chu kỳ doanh số giống nhau. - Tìm những đoạn nhạc trong một bài hát giống một đoạn nhạc đã có bản quyền. - Tìm những tháng trong quá khứ mà có lƣợng mƣa giống nhƣ tháng vừa rồi. - Tìm những năm khô hạn mà mực nƣớc các sông đều ở mức thấp. Đặc biệt, bài toán tìm kiếm tƣơng tự trên dữ liệu chuỗi thời gian dạng luồng đã và đang trở thành một chủ đề thời sự và nhận đƣợc nhiều quan tâm nghiên cứu vì tầm quan trọng của nó trong nhiều ứng dụng của các lĩnh vực khác nhau nhƣ dự báo động đất, xem xét lƣu lƣợng mạng Internet, xem xét đối tƣợng đang chuyển động, phân tích thị trƣờng tài chính và phát hiện bất thƣờng ( [3], [4], [5]). Trong bài toán này, các luồng dữ liệu liên tục đƣợc cập nhật khi có các điểm dữ liệu mới tới theo thời gian thực. Đó là một thách thức khi nghiên cứu về bài toán này do chi phí tính toán tăng cao vì thƣờng xuyên phải thu giảm lại số chiều của chuỗi và cập nhật chỉ mục. 2 Gom cụm dữ liệu chuỗi thời gian là một quá trình học không giám sát, là một công cụ độc lập để xem xét sự phân bố dữ liệu trong các tập dữ liệu lớn. Bài toán này đã đƣợc biết đến nhƣ một công cụ hiệu quả cho phép chúng ta tổng quát hóa thông tin từ các tập dữ liệu rất lớn nhằm cung cấp thông tin hữu ích giúp ngƣời dùng có thể dễ dàng truy cập và xử lý những thông tin quan trọng trong tập dữ liệu. Đó là một trong những lý do bài toán gom cụm đƣợc sử dụng rộng rãi trong nghiên cứu khai phá dữ liệu chuỗi thời gian và thƣờng đƣợc dùng nhƣ bƣớc tiền xử lý cho các bài toán khác nhƣ phân lớp, tiên đoán, ra quyết định, ... [6]. Mục tiêu của gom cụm là phân hoạch dữ liệu thành các nhóm sao cho các đối tƣợng trong cụm là tƣơng tự nhau còn các đối tƣợng khác cụm là khác nhau. Do những đặc thù riêng của dữ liệu chuỗi thời gian, nhiều giải thuật gom cụm làm việc hữu hiệu trên dữ liệu thông thƣờng lại thƣờng không thể làm việc một cách hữu hiệu với dữ liệu chuỗi thời gian. Motif trong chuỗi thời gian là mẫu xuất hiện với tần suất cao nhất. Hình 1.2 minh họa ví dụ về motif là chuỗi con xuất hiện ba lần trong chuỗi thời gian dài hơn. Từ khi đƣợc hình thức hóa vào năm 2002, phát hiện motif trong dữ liệu chuỗi thời gian đã và đang đƣợc dùng để giải quyết các bài toán trong nhiều lĩnh vực ứng dụng khác nhau ví dụ nhƣ dùng motif để kiểm tra chữ ký [7], dùng motif để phát hiện những hình ảnh lặp trong cơ sở dữ liệu hình dạng [8], dùng motif để dự báo giá chứng khoán [9] và cũng đƣợc dùng nhƣ bƣớc tiền xử lý trong nhiều công việc khai phá dữ liệu cao cấp hơn, ví dụ nhƣ gom cụm chuỗi thời gian [10], phân lớp chuỗi thời gian [11]. Hình 1.2 Ví dụ về motif là chuỗi con xuất hiện ba lần trong chuỗi thời gian dài hơn ( [12]). Hiển nhiên, độ phức tạp của phƣơng pháp phát hiện chính xác motif theo kiểu brute-force là bậc hai theo số chuỗi trong cơ sở dữ liệu chuỗi thời gian hay chiều dài 3 của chuỗi thời gian mà từ đó các chuỗi con đƣợc trích ra. Vì lý do đó, có nhiều thuật toán phát hiện motif xấp xỉ đã đƣợc giới thiệu ( [13], [14], [12], [15], [16], [17]). Các cách tiếp cận này thƣờng có độ phức tạp tính toán là O(n) hay O(nlogn), với n là số chuỗi trong cơ sở dữ liệu chuỗi thời gian hay chiều dài của chuỗi thời gian mà từ đó các chuỗi con đƣợc trích ra. Độ phức tạp của các giải thuật này giảm hơn so với phƣơng pháp tìm kiếm chính xác. Tuy nhiên, chúng yêu cầu một số lớn các tham số cần xác định trƣớc. Một số thuật toán phát hiện motif xấp xỉ thƣờng dựa trên các kỹ thuật xử lý chuỗi ký tự. Điều này đã khuyến khích các nhà nghiên cứu tìm kiếm các phƣơng pháp biến đổi khác nhau để chuyển chuỗi thời gian thành chuỗi ký tự, sau đó sử dụng các kỹ thuật xử lý chuỗi đã có để phát hiện motif. Trong số các thuật toán đã đƣợc đề xuất, thuật toán thông dụng là phƣơng pháp chiếu ngẫu nhiên do Chiu và các cộng sự giới thiệu [12]. Thuật toán này có thể phát hiện motif trong thời gian tuyến tính. Đây là thuật toán đƣợc trích dẫn nhiều và là cơ sở cho nhiều cách tiếp cận hiện nay trong việc giải bài toán phát hiện motif trên dữ liệu chuỗi thời gian ( [17], [18]). Tuy nhiên, các kỹ thuật xử lý chuỗi ký tự chƣa thật sự hữu hiệu khi làm việc trên chuỗi thời gian dạng số. Dự báo trên dữ liệu chuỗi thời gian đã và đang là một công việc phức tạp và thách thức đối với các nhà nghiên cứu. Tuy có một số phƣơng pháp thƣờng đƣợc sử dụng trên dữ liệu chuỗi thời gian nhƣ phƣơng pháp làm trơn theo hàm mũ, mô hình ARIMA, mạng nơ ron nhân tạo. Nhƣng hai phƣơng pháp đầu chỉ có thể nắm bắt đƣợc các đặc trƣng tuyến tính của chuỗi thời gian, còn việc mạng nơ ron nhân tạo có thể xử lý một cách hiệu quả dữ liệu có tính xu hƣớng và tính mùa hay không đang là một vấn đề gây bàn cãi vì có những nhận định trái ngƣợc nhau trong cộng đồng nghiên cứu về dự báo dữ liệu chuỗi thời gian [19]. Mặt khác, gần đây một số phƣơng pháp dự báo trên dữ liệu chuỗi thời gian dựa vào hƣớng tiếp cận so trùng mẫu đã đƣợc ứng dụng dự báo cho một số lĩnh vực cụ thể (nhƣ thời tiết, chứng khoán, giá điện và nhu cầu sử dụng điện) và là một hƣớng tiếp cận đáng quan tâm. 1.2 Mục tiêu, đối tƣợng và phạm vi nghiên cứu. Dữ liệu chuỗi thời gian đƣợc sử dụng phổ biến trong các lĩnh vực khoa học, công nghệ, tài chính, thƣơng mại, y học, thời tiết, môi trƣờng, địa lý. Một nghiên cứu khảo 4 sát từ 4000 hình đƣợc lấy ngẫu nhiên trong các báo tin tức trên thế giới đƣợc xuất bản trong giai đoạn từ 1974 đến 1989 cho thấy hơn 75% là các hình biểu diễn dữ liệu chuỗi thời gian ( [20]). Năm 2006, Yang và Wu thực hiện cuộc thăm dò ý kiến từ các nhà nghiên cứu hàng đầu trong lĩnh vực khai phá dữ liệu và máy học nhằm xác định các hƣớng nghiên cứu nào sẽ là quan trọng và thách thức nhất cho các nghiên cứu trong tƣơng lai thuộc lĩnh vực khai phá dữ liệu. Kết quả khảo sát nêu trong bài báo “10 Challenging Problems in Data Mining Research” cho thấy 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 sẽ là quan trọng và thách thức nhất [21]. Khi nghiên cứu các bài toán khai phá dữ liệu chuỗi thời gian, ngƣời ta thƣờng vận dụng những kỹ thuật trong các lĩnh vực nhƣ khai phá dữ liệu, học máy, cơ sở dữ liệu, nhận dạng, xử lý tín hiệu, sinh tin học, v.v… . Tuy nhiên, vì dữ liệu chuỗi thời gian thƣờng rất lớn, những giải thuật khai phá chuỗi thời gian phải thỏa mãn hai tính chất: (1) chúng phải hữu hiệu (tức có độ phức tạp tính toán thấp) và (2) đảm bảo đƣa lại kết quả đúng. Trong hai tính chất trên, tính chất (1) thƣờng đƣợc xem là quan trọng hơn tính chất (2). Những giải thuật xử lý trên chuỗi thời gian phải có độ phức tạp tính toán thấp (chẳng hạn độ phức tạp phải là tuyến tính theo độ lớn của kích thƣớc dữ liệu). Những giải thuật có độ phức tạp tính toán cao (bậc hai trở lên) thƣờng không đƣợc chấp nhận vì những giải thuật này sẽ không vận hành đƣợc khi dữ liệu lớn. Đây là một thách thức đã thúc đẩy chúng tôi thực hiện nghiên cứu về lĩnh vực này. Mục tiêu của luận án là đề xuất cách tiếp cận mới cho một số bài toán khai phá dữ liệu chuỗi thời gian. Đối tƣợng nghiên cứu là dữ liệu chuỗi thời gian với chuỗi thời gian đƣợc định nghĩa là một chuỗi các số thực X = x1, x2, x3,.. xn, trong đó xi là giá trị đo đƣợc ở thời điểm thứ i. Phạm vi nghiên cứu của luận án bao gồm nghiên cứu bốn bài toán quan trọng trong khai phá dữ liệu chuỗi thời gian, đó là: tìm kiếm tƣơng tự, gom cụm, phát hiện motif và dự báo trên dữ liệu chuỗi thời gian, trong đó tìm kiếm tƣơng tự là bài toán nền tảng. 1.3 Nhiệm vụ và hƣớng tiếp cận của luận án. Hƣớng tiếp cận chung thƣờng đƣợc sử dụng cho các bài toán trong khai phá dữ liệu chuỗi thời gian là thực hiện chúng trong không gian đặc trưng (feature space) của dữ liệu. Nhƣ vậy điều đầu tiên và cơ bản nhất trƣớc khi thực hiện các bài toán trong 5 khai phá dữ liệu chuỗi thời gian là các chuỗi thời gian cần đƣợc biểu diễn trong không gian đặc trƣng bằng một kỹ thuật thu giảm số chiều nào đó. Sau đó thực hiện các bài toán khai phá dữ liệu trong không gian đặc trƣng của chuỗi thời gian. Các nội dung nghiên cứu trong luận án cũng đƣợc định hƣớng đi theo cách tiếp cận này. Thời gian qua, nhiều phƣơng pháp thu giảm số chiều dựa vào rút trích đặc trƣng đã đƣợc đề xuất và sử dụng. Tuy nhiên có không ít phƣơng pháp thu giảm số chiều mắc phải hai nhƣợc điểm quan trọng: một số phƣơng pháp thu giảm số chiều không chứng minh đƣợc bằng toán học thỏa mãn điều kiện chặn dưới (chƣơng 2, mục 2.2.1), ví dụ nhƣ các phƣơng pháp dựa vào điểm quan trọng [22], [23], [24], [25], [26] và một số phƣơng pháp khác không đề xuất đƣợc cấu trúc chỉ mục đa chiều thích hợp đi kèm để hỗ trợ việc tìm kiếm tƣơng tự hữu hiệu, ví dụ nhƣ phƣơng pháp xén dữ liệu [27]. Vì vậy nhiệm vụ quan trọng đầu tiên của luận án là đề xuất một kỹ thuật thu giảm số chiều mới thỏa yêu cầu là không những có thể lƣu trữ các đặc trƣng về mặt giá trị mà còn cả hình dạng xấp xỉ của dữ liệu chuỗi thời gian nhƣng vẫn phải đảm bảo điều kiện chặn dƣới. Ngoài ra kỹ thuật đó có thể áp dụng cho trƣờng hợp tìm kiếm tƣơng tự với các chuỗi truy vấn có chiều dài khác nhau và có thể kết hợp với một cấu trúc chỉ mục đa chiều hỗ trợ việc tìm kiếm tƣơng tự một cách hữu hiệu. Nhiệm vụ thứ hai là ứng dụng kỹ thuật thu giảm số chiều đƣợc đề xuất vào bài toán gom cụm. Hai giải thuật thƣờng đƣợc sử dụng trong gom cụm dữ liệu chuỗi thời gian là k-Means và I-k-Means. Điểm yếu của thuật toán k-Means là chất lƣợng của gom cụm phụ thuộc vào sự lựa chọn các trung tâm cụm ban đầu. Vì vậy, nếu kết quả lựa chọn các trung tâm cụm để khởi động thuật toán không tốt thì chất lƣợng của kết quả gom cụm sẽ bị giảm và thời gian thực thi của thuật toán sẽ kéo dài hơn. Thuật toán I-k-Means khắc phục đƣợc những điểm yếu này của thuật toán k-Means. Ngoài ra nó còn cho phép ngƣời dùng tạm dừng hoặc kết thúc thuật toán tại bất kỳ thời điểm nào. Tuy nhiên, để có thể áp dụng thuật toán I-k-Means, kỹ thuật thu giảm số chiều sử dụng phải có tính chất đa mức phân giải (multi-resolution) và các trung tâm cụm khởi động thuật toán (ở lƣợt lặp đầu tiên) vẫn còn đƣợc chọn một cách ngẫu nhiên. Dựa vào những ƣu điểm của giải thuật I-k-Means, chúng tôi sử dụng giải thuật này để thực hiện gom cụm dữ liệu chuỗi thời gian, nhƣng đề xuất một phƣơng pháp có thể xác định các trung tâm cụm tốt hơn tại mức khởi động cho giải thuật I-k-Means 6 nhằm khắc phục nhƣợc điểm của giải thuật do cách chọn trung tâm cụm ngẫu nhiên ở lƣợt lặp đầu tiên mang lại. Nhiệm vụ thứ ba của luận án là ứng dụng kỹ thuật thu giảm số chiều đƣợc đề xuất vào bài toán phát hiện motif. Qua nghiên cứu về các phƣơng pháp phát hiện motif trên chuỗi thời gian đã đƣợc giới thiệu, chúng tôi thấy rằng mặc dù gần đây có các nghiên cứu đi theo hƣớng phát hiện motif chính xác, chúng tôi tin rằng cách tiếp cận phát hiện motif xấp xỉ vẫn tiếp tục là lựa chọn tốt nhất trong nhiều ứng dụng của các lĩnh vực khác nhau do tính hiệu quả về mặt thời gian và/hoặc không gian của cách tiếp cận này. Hơn nữa, vấn đề phát hiện motif xấp xỉ mà có thể phân tích trực tiếp trên dữ liệu số vẫn còn là một thách thức khó khăn. Điều này thúc đẩy chúng tôi nghiên cứu một phƣơng pháp phát hiện motif hiệu quả theo hƣớng tiếp cận này. Ngoài ra, hai nhiệm vụ thêm nữa đƣợc đặt ra là ứng dụng phƣơng pháp thu giảm số chiều đƣợc đề xuất vào: (1) bài toán dự báo trên dữ liệu chuỗi thời gian có tính xu hƣớng hoặc biến đổi theo mùa dựa vào hƣớng tiếp cận so trùng mẫu và (2) bài toán tìm kiếm tƣơng tự trên chuỗi thời gian dạng luồng dựa vào ý tƣởng tính toán thu giảm số chiều gia tăng và cập nhật chỉ mục trì hoãn. 1.4 Tóm tắt kết quả đạt đƣợc. Với nhiệm vụ đầu tiên của luận án, chúng tôi đã đề xuất đƣợc một kỹ thuật thu giảm số chiều dữ liệu chuỗi thời gian dựa trên phƣơng pháp điểm giữa kết hợp với kỹ thuật xén, gọi là MP_C (Middle Points and Clipping). Kỹ thuật này đƣợc thực hiện bằng cách chia chuỗi thời gian thành nhiều đoạn, một số điểm trong mỗi đoạn sẽ đƣợc chọn (số điểm này do ngƣời dùng xác định), sau đó dùng kỹ thuật xén để chuyển các điểm đƣợc chọn thành chuỗi bit. Chuỗi bit và các giá trị trung bình của các đoạn đƣợc lƣu trữ nhƣ các đặc trƣng của chuỗi. Ƣu điểm của phƣơng pháp này là không những có thể lƣu đƣợc đặc trƣng về giá trị mà còn lƣu trữ đƣợc cả đặc trƣng về hình dạng xấp xỉ của chuỗi mà vẫn không tốn nhiều không gian lƣu trữ và thời gian thực hiện tăng không đáng kể. Mặt khác, chuỗi bit đƣợc lƣu trữ còn giúp nâng cao độ chính xác của xấp xỉ. Ngoài ra, phƣơng pháp này có thể đƣợc kết hợp với chỉ mục đường chân trời (Skyline index) nhằm hỗ trợ việc tìm kiếm tƣơng tự một cách hữu hiệu. Đồng thời chúng tôi cũng đã xây dựng một độ đo tƣơng tự mới cho hai chuỗi trong không gian đặc trƣng MP_C và đã chứng minh độ đo này thỏa điều kiện chặn 7 dƣới. Thực nghiệm cho thấy phƣơng pháp MP_C hiệu quả hơn so với phƣơng pháp PAA (Piecewise Aggregate Approximation) thƣờng đƣợc sử dụng và kỹ thuật xén (Clipping) về các chỉ số độ chặt của chặn dưới (the tightness of lower bound) và tỉ lệ thu giảm truy xuất (the pruning power). Trong bài toán tìm kiếm tƣơng tự, phƣơng pháp MP_C với sự hỗ trợ của chỉ mục đƣờng chân trời thực thi nhanh hơn so với phƣơng pháp PAA dựa trên R*-tree hoặc chỉ mục đƣờng chân trời. Thực hiện nhiệm vụ tiếp theo, dựa vào tính chất đa phân giải của phƣơng pháp MP_C, chúng tôi đã tiến hành gom cụm dữ liệu chuỗi thời gian đƣợc thu giảm bằng kỹ thuật MP_C theo phƣơng pháp gom cụm có thời gian thực thi tùy chọn bằng giải thuật I-k-Means. Để khắc phục nhƣợc điểm của thuật toán I-k-Means do cách chọn các trung tâm cụm ở mức khởi động (mức 2) một cách ngẫu nhiên gây ra, chúng tôi sử dụng kd-tree để chọn k trung tâm cụm ở mức khởi động. Ngoài ra, chúng tôi cũng thực nghiệm việc tạo các trung tâm cụm khởi động bằng CF-tree nhằm so sánh hai kỹ thuật khởi tạo trung tâm cụm này. Với nhiệm vụ thứ ba, chúng tôi đã đề xuất đƣợc hai phƣơng pháp phát hiện motif xấp xỉ trong chuỗi thời gian: (1) sử dụng R*-tree kết hợp với ý tƣởng từ bỏ sớm việc tính khoảng cách Euclid (chƣơng 4, mục 4.1) và (2) dựa trên phƣơng pháp thu giảm số chiều MP_C với sự hỗ trợ của chỉ mục đƣờng chân trời (chƣơng 4, mục 4.2). Phƣơng pháp (1) có thể phân tích trực tiếp trên dữ liệu chuỗi thời gian dạng số mà không cần phải qua giai đoạn rời rạc hóa nhƣ một số phƣơng pháp phát hiện motif đã đƣợc giới thiệu và phƣơng pháp này đạt hiệu quả về mặt thời gian lẫn không gian lƣu trữ vì chỉ cần lƣu các vùng bao hình chữ nhật nhỏ nhất (Minimum Bounding Rectangle – MBR) của dữ liệu trong bộ nhớ và chỉ cần một lần quét qua toàn bộ dữ liệu cùng với một số ít lần truy cập đĩa để thẩm định lại kết quả. Tuy nhiên phƣơng pháp này có một nhƣợc điểm đó là R*-tree dựa vào vùng bao hình chữ nhật nhỏ nhất có thể thực hiện không tốt trong trƣờng hợp dữ liệu chuỗi thời gian có số chiều cao. Phƣơng pháp (2) khắc phục đƣợc nhƣợc điểm của phƣơng pháp (1) và kết quả thực nghiệm cho thấy phƣơng pháp (2) có thời gian thực thi nhanh hơn và có độ hữu hiệu tốt hơn so với phƣơng pháp (1). Ngoài những yêu cầu ban đầu, chúng tôi còn cho thấy kỹ thuật MP_C có thể sử dụng hiệu quả cho bài toán tìm kiếm tƣơng tự trên dữ liệu chuỗi thời gian dạng luồng 8 dựa trên cách tính toán gia tăng của phƣơng pháp MP_C và ý tƣởng cập nhật trì hoãn nhƣ của phƣơng pháp chỉ mục IDC ( [4], [5]). Chúng tôi cũng ứng dụng phƣơng pháp MP_C kết hợp với chỉ mục đƣờng chân trời vào bài toán dự báo dữ liệu chuỗi thời gian có tính chất xu hƣớng hoặc theo mùa. Phƣơng pháp dự báo này dựa trên phƣơng pháp so trùng mẫu sử dụng thuật toán tìm k lân cận gần nhất (k-nearest neighbors) hoặc các lân cận trong phạm vi một ngƣỡng cho trƣớc. 1.5 Cấu trúc của luận án. Phần còn lại của luận án đƣợc tổ chức nhƣ sau. Trong chƣơng 2, chúng tôi trình bày tóm tắt các công trình liên quan và các khái niệm căn bản liên quan tới các vấn đề đƣợc nghiên cứu. Các đóng góp của luận án về các vấn đề nghiên cứu đƣợc trình bày trong các chƣơng 3, 4, 5 và 6. Trong đó: - Chƣơng 3 trình bày vấn đề thu giảm số chiều chuỗi thời gian bằng phƣơng pháp MP_C, bao gồm: phƣơng pháp thu giảm số chiều MP_C đƣợc đề xuất trong luận án cùng với độ đo tƣơng tự đƣợc định nghĩa dựa trên nó, cấu trúc chỉ mục đƣờng chân trời cho các chuỗi MP_C cùng với độ đo tƣơng tự đƣợc định nghĩa trên cấu trúc này và bài toán tìm kiếm tƣơng tự trên dữ liệu chuỗi thời gian dạng luồng. - Chƣơng 4 trình bày về hai phƣơng pháp phát hiện motif dựa vào cấu trúc chỉ mục đa chiều (R*-tree) và chỉ mục đƣờng chân trời do chúng tôi đề xuất. - Chƣơng 5 trình bày về bài toán gom cụm chuỗi thời gian đƣợc thu giảm bằng kỹ thuật MP_C theo phƣơng pháp gom cụm có thời gian thực thi tùy chọn (sử dụng giải thuật I-k-Means) đƣợc khởi động bằng kd-tree hoặc CF-tree. - Chƣơng 6. Trình bày về ứng dụng phƣơng pháp MP_C kết hợp với chỉ mục đƣờng chân trời vào bài toán dự báo dữ liệu chuỗi thời gian. - Chƣơng 7 là phần kết luận về các công việc đã nghiên cứu, một số hạn chế của luận án và hƣớng phát triển. 9