Nghiên cứu tìm kiếm tương tự trên chuỗi thời gian dạng luồng tại TP.HCM

ĐẠI HỌC QUỐC GIA TP. HÒ CHÍ MINH TRUONG DAI HOC BACH KHOA BUI CONG GIAO TÌM KIEM TUONG TU TREN CHUOI THỜI GIAN DANG LUONG (SIMILARITY SEARCH IN STREAMING TIME SERIES) LUAN AN TIEN SI KY THUAT TP. HÒ CHÍ MINH NAM 2019 ĐẠI HỌC QUỐC GIA TP. HCM TRƯỜNG ĐẠI HỌC BÁCH KHOA TÌM KIEM TUONG TU TREN CHUOI THỜI GIAN DANG LUONG (SIMILARITY SEARCH IN STREAMING TIME SERIES) Chuyén nganh: Khoa hoc may tinh Mã số chuyên ngành: 62.01 Phản biện độc lap 1: PGS.

Võ Đình Bảy Phản biện độc lập 2: PGS. Nguyễn Đình Thuân Phan bién 1: PGS. Lê Hoài Bắc Phản bién 2: PGS. Dé Phuc Phan bién 3: TS.

Lê Văn Quốc Anh NGƯỜI HƯỚNG DẪN KHOA HỌC PGS. Dương Tuấn Anh LỜI CAM ĐOAN Tác giả xin cam đoan đây là công trình nghiên cứu của bản thân tác giả. Các kết quả nghiên cứu và các kết luận trong luận án này là trung thực, và không sao chép từ bất kỳ một nguồn nào và dưới bất kỳ hình thức nào. Việc tham khảo các nguồn tài liệu (nếu có) đã được thực hiện trích dẫn và ghi nguồn tài liệu tham khảo đúng quy định.

Tác giả luận án Chữ ký Bùi Công Giao TÓM TẮT Trong &khai phá dữ liệu chuỗi thời gian, bài toán tìm kiếm tương tự trên chuối thời gian dạng luồng là một thách thức lớn cho các nhà nghiên cứu vì các phương pháp tìm kiếm tương tự trên chuỗi thời gian tĩnh khó có thể phù hợp với môi trường luồng. Thêm nữa, cho tới nay các công trình tìm kiếm tương tự trên chuỗi thời gian dạng luồng vẫn còn một số hạn chế như chỉ phí tính toán cao hoặc không chuẩn hoá đữ liệu. Trong luận án này chúng tôi đề xuất các hướng nghiên cứu và phương pháp nhằm nâng cao hiệu quả cho nhiệm vụ tìm kiếm tương tự trên chuỗi thời gian dạng luồng bằng độ đo Euclid và độ đo DTW. Đề kết quả tìm kiếm có ý nghĩa và chính xác, chuẩn hoá dữ liệu chuỗi thời gian cần được thực hiện trước khi tìm kiếm tương tự.

Trong môi trường luồng, hoạt động tìm kiếm tương tự có độ phức tạp thời gian cao, vì vậy các phương pháp đề xuất đã sử dụng các kỹ thuật tăng tốc cho tính toán khoảng cách giữa hai chuỗi thời gian, và sắp đặt các kỹ thuật này theo &¿ểu xếp tầng đê từ bỏ sớm các tính toán không cần thiết. Thêm nữa, các phương pháp tìm kiếm tương tự trên chuỗi thời gian dạng luồng nên sử dụng các kỹ thuật tính toán gia tăng như chuẩn hoá dữ liệu gia tăng nhằm tối thiểu chỉ phí tính toán. Kế tiếp, phương pháp tìm kiếm tương tự được sử dụng để giải quyết một vài bài toán thực tế như đự báo trực tuyến hay phát hiện bất thường trong chuỗi thời gian đạng luồng. Đề tối thiểu thời gian thực hiện của nhiệm vụ dự báo trực tuyến, phương pháp đề xuất sử dụng các điểm cực trị quan trọng trong chuỗi thời gian dạng luồng như là các điểm mốc cho tìm kiếm tương tự.

Còn đối với phát hiện bat thường trong chuỗi thời gian dang luồng, phương pháp đề xuất sử dụng các kỹ thuật chặn đưới khi tính toán khoảng cách dé nhận diện các chuỗi con có tiềm năng bất thường nhất. Kết quả thực nghiệm của các phương pháp tìm kiếm tương tự trên chuỗi thời gian dạng luồng bằng độ đo Euclid và độ đo DTW chứng tỏ sự hiệu quả của các phương pháp đề xuất. Các phương pháp trả về kết quả chính xác (không có lỗi tìm sót) với chỉ phí tính toán và không gian bộ nhớ thấp. Còn đối với các ứng dụng sử dụng phương pháp tìm kiếm tương tự, đánh giá qua thực nghiệm đã chứng tỏ rằng các ứng dụng thu được kết quả như mong đợi và có thời gian phản hồi nhanh.

il ABSTRACT In time-series data mining, the problem of similarity search in streaming time series is a big challenge for researchers because similarity search methods in static time series are hardly suitable for a streaming environment. Also, so far research works on similarity search in streaming time series have some limitations such as high computational costs and no data normalization. In the dissertation we propose research directions and methods to improve the effectiveness and the efficiency of similarity search in streaming time series under Euclidean measure and DTW measure. In order to acquire meaningful and accurate search results, normalizing time-series data needs conducting prior to similarity search.

In the streaming environment, similarity search is of high time complexity, so the proposed methods have used speed-up techniques for calculating the distance between two time-series sequences, and arrange these techniques in a cascading fashion for early abandoning of unnecessary computations. Furthermore, methods of similarity search in streaming time series should use incremental calculation techniques such as incremental data normalization to minimize the computational costs. We then utilize the methods of similarity search to solve some real problems such as online forecasting or anomaly detection in streaming time series. In order to minimize the execution time of online forecasting, the proposed method use major extrema in streaming time series as turning points for similarity search.

As for anomaly detection in streaming time series, the proposed method use lower-bounding techniques in distance computations to identify the most likely subsequences of anomaly. The experimental results of the methods of similarity search in streaming time series under Euclidean measure and DTW measure indicate that these proposed methods are effective and efficient since they bring out accurate results (no false dismissals) with low computational time and memory space. With respect to applications using the methods of similarity search, the experimental evaluations demonstrate that these applications obtain desirable results and have fast responses. 11 LỜI CÁM ƠN Tôi xin bày tỏ lòng biết ơn sâu sắc đến Thầy PGS.

Dương Tuấn Anh đã tận tình hướng dẫn, động viên, chỉ bảo, và đóng góp ý kiến để tôi có thể nghiên cứu và hoàn thành Luận án tiến sĩ. Tôi xin gửi lời cảm ơn đến các Thầy, Cô trong Khoa Khoa học và Kỹ thuật Máy tính trường Đại học Bách khoa Tp. Hồ Chí Minh, nhóm nghiên cứu về khai phá dữ liệu chuỗi thời gian, và các bạn nghiên cứu sinh đã đóng góp nhiều ý kiến quí báu cho tôi. Tôi cũng xin cảm ơn các đồng nghiệp ở Khoa Điện tử Viễn thông của trường Đại học Sài Gòn và Khoa Công nghệ thông tin của Học viện Công nghệ Bưu Chính Viễn thông cơ sở Tp.

Hồ Chí Minh đã luôn động viên, khích lệ và tạo điều kiện thuận lợi cho tôi hoàn thành luận án. Tôi chân thành cảm ơn Ban Giám hiệu trường Dai hoc Sai Gòn đã hỗ trợ kinh phí và tạo điều kiện công tác thuận lợi để tôi có thể hoàn thành chương trình nghiên cứu sinh. Cuôi cùng, tôi xin bày tỏ lòng biệt ơn sâu sắc và muôn vàn tình yêu đến ba, mẹ, vợ, con, những người đã luôn bên cạnh và hỗ trợ tôi trong suốt thời gian qua. Hồ Chí Minh, tháng 9 năm 2019 Nguyên cứu sinh Bùi Công Giao iv MỤC LỤC LỜI CAM ĐOAN.

DANH MỤC CÁC HÌNH ẢNH DANH MỤC BẢNG BIỂU. xvii CHƯƠNG 1 GIỚI THIỆU.1 Chuỗi thời gian dạng luồng và thách thức xử lý chuỗi thời gian dạng luồng.2 Mục tiêu, đối tượng và phạm vi nghiên CỨU .- -¿- +5 +5+£+e£+e>+>exsersers 2 IS Na oi ái 6) 2ê 0 .4 Tóm tắt kết h)0-Ns b8 021117.1 Tìm kiếm tương tự trên chuối thời gian dạng luỗng bang d6 do Euclid .2 Tìm kiếm tương tự trên chuỗi thời gian dang luong bang dé do DTW.3 Dự báo trực tuyến trên chuỗi thời gian dạng luỗng,.4 Phát hiện k chuỗi con bất thường nhất trong chuỗi thời gian dạng luông.5 _ Cấu trúc của luận án.--:--+22+kkkrtrrttEEErrrrrrriiiirrrrrriirree 13 CHƯƠNG 2 CƠ SỞ LÝ THUYẾT NÊN TẢNG.---55cccccsccccceee 14 PIN? No 0.S SG SE HH HH kết 15 PJNw®? 2.2 Chuẩn hoá dữ liệu. Định nghĩa tìm kiếm tương tự trên chuỗi thời gian.4 _ Định nghĩa tìm kiếm tương tự trên chuỗi thời gian dạng luồng.5 Tăng tốc trong tính toán độ đo tương tự.-------©--++2xc2zx2zxcerxerkeerrcee 22 2.1 Sử dụng bình phương khoảng CáCh.2 Từ bỏ sớm trong khi tính khoảng cách ECÏid. Sắp xếp lại thứ tự từ BO SOM vecccsvessssessssesssssssssssssssssssessssssssssesssesssscssseessseeees 23 P N12 16.5 Kiểu xếp tẳng.6 _ Các kỹ thuật tăng tốc chuyên biệt cho độ đo DTW.1 Giới hạn sự ghép đôi các điỂm.2 Hàm chặn dưới cho DDTÏHỨ.c Sc ct tk EkESEEEkEkESrkErkkkerrerkerkeree 25 2.3 Từ bỏ sớm trong khi tính khoảng cách DTÍW.7 Các phép biến đổi thu giảm số chiều.- 2222222 22EE2EE2EEEEEerkrrrkree 28 lun.8 Cấu trúc chỉ mục ]Ñ-fT€€.

Tính chất của Ñ-tree.1 Xây dựng Ñ-fr€©.2 Tìm kiếm trong R-te€. -c cc SH 1121112112121 ee 38 2.9 Kết chương.01 ca 40 CHƯƠNG 3 TÌM KIỀM TƯƠNG TỰ TRÊN CHUÔI THỜI GIAN DẠNG LUONG BANG DO DO EUCLID wu.1 Tim kiém ving trén chudi thời gian dạng luồng bằng độ đo Euclid.2 Bài toán tìm kiếm tương tự trên nhiều chuỗi thời gian dạng luỗng. Các kỹ thuật hỗ trợ phương pháp đề xuất.1 Chuẩn hóa z-score gia tăng.2 Cấu trúc chỉ mục đa nưức phân giải. Tiên xử lý chuỗi truy vấn.

Ky thuGt da WON vcccsecscsecsssssssssssssssssssssssscsssssssssssssessssssasscsssssesssscssscssvecs 53 3. Mô hình hệ thống tìm kiếm tương tự bằng độ đo Euclid.6 Đánh giá phương pháp Ñange©S€qCh.2 Tìm kiếm # lân cận gần nhất trên chuỗi thời gian dạng luồng bằng độ đo Euclid —-.1 Các công trình liÊH qHđH.2 Phuong phdp dé XUGt ceccccccsecsssscssssssssssssscssssssssssssssssssscsssssssssssssscsesscsssecssvecs 67 3. Đánh giá phương pháp k-NNSearCÌ.3 Cải tiến cách 0900.1 Giới thiệu bài lOÁH. cv SH ST ng rệt 73 3.2 Các công trình liÊH qHđH.

Đường cong lấp đây không gian. nan e<4dHAqg)ậằậHgH. Đánh giá lSTI và ISTÍ2.--2-22+22E22212271271127112711211121112111 2112121 1e ee 88 CHƯƠNG 4 TIM KIEM TUONG TU TREN CHUÔI THỜI GIAN DẠNG LUONG BẢNG ĐỘ ĐO DTÌW. LH HH HH HH nhiệt 90 4.1 Tìm kiếm tương tự trên chuỗi thời gian đạng luồng bằng độ đo DTW.1 Các công trình liÊH qHAH.2 Bộ kỹ thuật UC-DTÏM.

SE ng girệt 92 4. Mô hình hệ thống tìm kiếm tương tự bằng độ đo DTIW. Phương pháp SUCR-DTÏW.5 Đánh giá phương pháp SUCR-DTÍWf.2 Cải tiến phương pháp SPRING.1 Giới thiệu phương pháp SPNINC.2 Phương pháp ISPRINC. Đánh giá phương pháp ISPINC.

Phương pháp ESUCR-DTÌW. HH HH HH Hư 118 4.1 Giới thiệu phương pháp ESUCR-DTÏW. Mở rộng hàm chặn dưới LB keogh 4. Giải thuật ESUCR-DTÌ.

tt ét#*kEkhkrireririririrkeerkei 121 4.4 Đánh giá phương pháp ESUCR-DTMỨ. 5 + sseEsk+kreEseeererseee 121 Vii 4. Nhận xét tông quát về các phương pháp tìm kiếm tương tự bằng độ đo DTW.--- 2622k 22E22212211221122112211111111111111 1E 1E xe 131 CHƯƠNG 5 DU BAO TRUC TUYEN TREN CHUOI THỜI GIAN DẠNG 10/90) c.1 Giới thiệu bài toán dự báo trực tuyến HH ng 1n KT KT ng 132 5.2 Dinh nghia bai toan ose .3 Tiêu chí đo độ chính xác của du D0.4 Làm trơn hàm mũ đơn g1ả1.5 _ Các điểm cực trị cục bộ trong chuỗi thời gian .6 Các công trình liÊn QuaH.- óc SE SE+tE*EEEEEekeEerrkrrrerkrrkrrrrerrre 136 5.7 Phương pháp để xuẤt.1 Ý trưởng chính cho phương pháp.2 Môi trường hoạt động cho phương pháp. Hoạt động của phương Pap wecccccccccccccccsesceseeseeseeeeseeseeseseeseeseeseseeseeseneeaees 5.4 Đánh giá phương pháp để xuất 5.--- 2k2 t2 1 222122121112111121122112212 21221 1e 151 CHƯƠNG 6 PHAT HIEN K CHUOI CON BAT THUONG NHẤT TRONG CHUOI THOI GIAN DANG LUÔNG.