ĐẠI HỌC QUỐC GIA TP. HCM TRƯỜNG ĐẠI HỌC BÁCH KHOA PHAM THANH XUAN NHAN DANG MOTIF VA BAT THUONG TREN DU LIEU CHUOI THOI GIAN DUA VAO KY THUAT BAM CHUYEN NGANH: Khoa học máy tính MÃ SỐ: 60.01 LUẬN VÁN THẠC SĨ ĐẠI HỌC QUỐC GIA TP. HCM TRƯỜNG ĐẠI HỌC BÁCH KHOA PHAM THANH XUAN NHAN DANG MOTIF VA BAT THUONG TREN DU LIEU CHUOI THOI GIAN DUA VAO KY THUAT BAM CHUYEN NGANH: Khoa học máy tính MÃ SỐ: 60.01 LUẬN VÁN THẠC SĨ CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI TRUONG ĐẠI HỌC BACH KHOA —DHQG -HCM Cán bộ hướng dẫn khoa học : PGS. Dương Tuan Anh.
Cán bộ cham nhận xét 1: TS.----5- 52 5c scsccee Cán bộ chấm nhận xét 2 : TS. Võ Thị Ngọc Châu.--------<<<<2 Luận văn thạc sĩ được bảo vệ tại Trường Đại học Bach Khoa, DHQG Tp. HCM ngày 22 thang 07 năm 2013. Thanh phan Hội đồng đánh giá luận văn thạc sĩ gồm: I.
Lê Thanh Vân. Võ Thị Ngọc Châu. Dương Tuan 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 TRƯỞNG KHOA ĐẠI HỌC QUỐC GIA TP. HCM CỘNG HOÀ XÃ HỘI CHỦ NGHIÃ VIỆT NAM TRƯỜNG ĐẠI HỌC BÁCH KHOA Độc Lập - Tự Do - Hạnh Phúc eens eee nese esses een ---000--- Tp. HCM, ngay 22 thang 07 nam 2013. NHIEM VU LUẬN VAN THAC SĨ Họ và tên học viên: Pham Thanh Xuân.
Giới tính: Nam ¡'/ Nữ L¡ Ngày, tháng, năm sinh: 21/06/19&%3.- 2 1222221111221 11k xsegNơi sinh: Long An. Chuyên ngành: Khoa học máytính. ne bee cà. ee Sàn anes Khoá: 2011.
n2 vee vee vee vat ves evs visser Hà te nà nà Hà nà nà nh H h Hà. 1-TÊN DE TÀI: NHAN DANG MOTIF VÀ BAT THUONG TREN DU LIEU CHUOI THỜI GIAN DUA VAO KY THUAT BAM 2-NHIEM VU LUAN VAN: — Để xuất một phương pháp hiệu quả vừa khai pha motif vừa khai phá bat thường trên dữ liệu chuỗi thời gian dựa vào kỹ thuật băm. — Hiện thực và thử nghiệm trên phương pháp đã dé xuất. 3-NGÀY GIAO NHIỆM VỤ: 21/01/2013 4-NGÀY HOÀN THÀNH NHIỆM VỤ: 21/06/2013 5-HỌ VA TÊN CÁN BỘ HƯỚNG DAN: PGS.
Dương Tuấn Anh. Nội dung va dé cương Luận Văn Thạc Sĩ đã được Hội Đồng Chuyên Ngành thông qua. CAN BO HUONG DAN CHU NHIEM BO MON (Ho tên và chữ ki) QUAN LÝ CHUYÊN NGANH (Họ tên và chữ kí) PGS.Dương Tuan 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 nay 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 trường khác. Ngày 22/07/2013 Phạm Thanh Xuân LỜI CẢM ƠN Đề có thể hoàn thành tốt luận văn này, trước tiên tôi xin chân thành gửi lời cảm ơn đến PGS.Dương Tuấn Anh, người Thây đã luôn tận tâm chỉ bảo và hướng dẫn tôi trong suốt thời gian tôi thực hiện luận văn này.
Tôi xin cảm ơn các quí thầy cô, những người đã gián tiếp và trực tiếp chỉ bảo và giảng dạy giúp tôi có những kiến thức cần thiết dé thực hiện luận văn này. Tôi cũng xin cảm ơn gia đình va bạn bè đã quan tâm giúp đỡ và tạo điều kiện dé tôi hoàn thành tốt luận văn này. Tôi xin gửi lời cam ơn chân thành dén tat cả mọi người. TÓM TAT LUẬN VĂN Motif trong dit liệu chuỗi thời gian là những chuỗi con (Subsequense) tương tự xuất hiện lặp đi lặp lại nhiều lần trong tập dữ liệu.
Bat thường trong đữ liệu chuỗi thời gian là một chuỗi con chỉ xuất hiện duy nhất một lần và khác biệt nhất với tất cả các chuỗi con còn lại trong tập dữ liệu. Kích thước cua dữ liệu chuỗi thời gian thường rất lớn và ngày càng gia tăng là van dé gây khó khăn cho các giải thuật khai phá motif cũng như các giải thuật khai phá bất thường. Trong luận văn nay, chúng tôi đề xuất một giải thuật mới, giải thuật FMG (Feature Match Grouping) có thé vừa phát hiện motif vừa phát hiện bat thường trên tập dữ liệu chuỗi thời gian có kích thước rất lớn. Từ dữ liệu thô (raw data) ban đầu sau khi thực hiện bước chuẩn hóa (normalization) sẽ tiếp tục thực hiện thu giảm số chiều (dimensionality reduction) và rời rac hóa (discretization) vé dang chuỗi ký tự.
Sử dụng cửa số trượt (sliding window) có kích thước w (w do người dùng định nghĩa) trượt qua tất cả các ký tự trong chuỗi dữ liệu. Các chuỗi con sinh ra từ cửa số trượt gọi là các từ (word), mỗi từ được xem như một đặc trưng (feature). Tìm thùng băm có kích thước lớn nhất, khóa tương ứng của thing băm này sé là ứng viên motif. Các thùng băm chỉ chứa duy nhất một đặc trưng thì những đặc trưng này là những ứng viên bất thường.
Thực hiện tìm các thể hiện motif từ ứng viên motif và ngưỡng không tương tự tối đa Ra (Rimax do người dùng định nghĩa) dựa trên hàm tính khoảng cach Euclid. Một ứng viên bat thuong vẫn có thé là một thé hiện motif với ngưỡng Rạax, nếu một ung viên bất thường là một thé hiện motif thì ứng viên đó được loại khỏi danh sách những ứng viên bat thường. Bấy giờ, các ứng viên bất thường còn lại sẽ được loại trừ dân bằng giải thuật tiễn_ lài (forward_backward) dé nhận diện ứng viên bất thường thật sự. Giải thuật FMG giải quyết bài toán vừa khai phá motif vừa khai phá bất thường trong thời gian tuyến tính với kích thước tập dữ liệu, không gian sử dụng bộ nhớ là hăng số.
Qua kết quả thực nghiệm cho thấy giải thuật FMG tốt hơn rất nhiều so với giải thuật khai phá motif chiéu ngẫu nhiên (Random Projection) và giải thuật khai pha bất thường HOTSAX. ABSTRACT Motif in time series data is the similar subsequences which appear repeatedly many times in the data set. Anomaly in time series data is that a subsequence appears only once and is most different from the rest of subsequence in the data set. Usually, the size of the time series data is very large and growing more and more.
This is the challenge that makes it difficult for the motif discovery algorithms as well as the anomaly discovery algorithms. In this thesis, we propose a new algorithm, FMG (Feature Match Grouping) algorithm which can find motif as well anomaly on the very large time series data. From the initial raw data, after executing normalization step, we will perform dimensionality reduction and discretization. Using the sliding window of size w (w defined by the user), it slides through all the symbols in the string.
The subsequence generated by the sliding window are called the word, each word is considered as a feature. A hash table is used to contain these features, two match features will be stored together in the same bucket. Finding bucket with the largest size, the corresponding key of this bucket will be the motif candidate. For the buckets containing only a single feature, these features are anomaly candidates.
We can find motif instances from the motif candidate and basing on the dissimilarity maximum threshold R„max (Rimax defined by user based on Euclid distance function). An anomaly candidate still can be any motif instance with the threshold R„ax, if an anomaly candidate is also an motif instance, it will be eliminated from the anomaly candidate list. Then, the remaining candidates will be excluded by forward_backward algorithm to identify the real anomaly subsequence. FMG algorithm solves the motif discovery and anomaly discovery problem in linear time with the size of the data set, using memory space is a constant.
The experimental results show that the FMG algorithm is much better than the Random Projection algorithm in motif discovery and much better than HOTSAX algorithm in anomaly discovery. vi TÓM TAT LUẬN VAN.cccccccsscscssssssssssssscsssssssvsscsssssvsvescscsssvasessassssssvsssssassvsveecssssavsssssasssaseusssisssssesesssassesesesscossesensees vi CHUONG 1: GIỚI THIEU DE TÀI. -- -- 22552 S5 2E‡EE2EEEE‡EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEkrkrrkerrrkerrree 1 1.1 Dữ liệu chuỗi thời gian.---- 5-55 22 3Sề 2v ch HT.2 Truy xuất thông tin trên dữ liệu chuỗi thời gian.--- ¿5-5 5S cxcrrxersrrrrvree 1 13 Khai phá motif và bất thường trên dữ liệu chuỗi thời gian.4 Hướng (iếp cận của luận văn.---¿- 5: - 5625 St SE 2E E111 1111210112111 111111111 xe. 3 l5 Ý nghĩa của luận văn .-- HH HH HH 4 1.6 Cấu trúc của luận văn.0 4 CHUONG 2: TONG THUẬT NHỮNG CONG TRÌNH LIEN QUAN.1 Một số khái niệm cơ bản.---- ¿S6 St SE E1 E111 210171111 11111111111 1x11 krrkd 5 2.2 Các phương pháp tính độ đo tương ự.
LH HH HH kh 8 2.2 Độ do Dynamic Time Warping (D TW). HH HH HH ke 9 2.3 Các phương pháp biểu diễn dữ liệu chuỗi thời gian .1 Các phương pháp thu giảm số chiều .2 Phương pháp rời rac hóa dữ liệu.-- - -- Ă- - Ă ES< 1n ST ng re 15 2.4 Giải thuật khai phá motif chính xác. - - -- - SH HH HH HH, 16 2.5 Giải thuật khai phá motif XẤp XỈ. ce Sàn tt TH HE H111 11111111 17 2.6 Giải thuật khai phá bất thường .7 Giải thuật kết hợp khai phá motif và khai phá bat thường.: cà tì HT THHHHHHHH1 TT 111 1H11 1g 24 CHƯƠNG 3: PHƯƠNG PHÁP GIẢI QUYẾT VAN Đ.-- - ch HE krrrrrrki 25 3.1 Thu giảm số chiều với phương pháp PAA .2 Ròi rạc hóa dữ liệu với phương pháp SAX.3 Độ đo tương tự MINDISTT.
ccc HH TH HH HH nh 28 TT.5 Giải thuật REÌMG.- nh ch HH TH 111111111.6 So sánh phương pháp thực hiện của các giải thuật đo trước. Sàn nh TH TH 1111 11g11 go 41 CHƯƠNG 4: HIỆN THỰC VÀ THU NGHIỆMA.1 Mô hình hiện thực các giải thuật. -- -- Gà HH ng ngư, 43 4.1 Giải thuật chiếu ngẫu nhiên RP. 5-5-5 5c SE SE SE EEEExrkrrrkerkrrrred 43 4.2 Giải thuật nhận dang bất thường HOTSAX .3 Giải thuật vừa khai phá motif vừa khai phá bat thường EMG.4 Giải thuật khai phá motif REIMG.2 Thực nghiệm các giải thuật đã hiện thực .1 Dữ liệu điện tim đồ (ECG) 100.2 Dữ liệu điện tim đồ (ECG) 300.3 Dữ liệu điện não đồ (EEG) 10.4 Dữ liệu doanh nghiệp (ERP) 198.5 Dữ liệu MEMORY 6.-- 5-5 5S tt SE 2111211111111 rrrkd 59 4.6 Dữ liệu năng lượng (POWER) 35.- - Sàn tt rrrkererrrrea 62 4.7 Dữ liệu chứng khoán (STOCK) 12.3 So sánh các giải thuật dựa trên kết quả thực nghiệm .- 2-5 5555 cesses 66 CHƯƠNG 5: KẾT LUẬN.
tk THE TH HH H111 1 1111111111111 re 69 5.2 __ Những đóng góp của luận văn.3 Hướng phát triển của luận văn.--¿- - 6-5 SE EEEEEEEEEEEEEEEEEEEEEEEEEkrkrrkrrrrkrrkrkee 70 TÀI LIEU THAM KHHẢO. 1xx 71 PHU LUC A: BANG DOI CHIEU THUẬT NGỮ ANH-VIỆTT.-- + 25c S2x+EEzxererxrrrrrrsrree A PHU LUC B: LY LICH TRÍCH NGANG.-- ¿E255 StSESt‡x#ESEEEEEEEEEEEEEEEEEEEErkkrkrkrrrrrrerrrrrrrrris B vill DANH MỤC HÌNH ẢNH Hình 1.1: Dữ liệu chuỗi thời gian biéu diễn giá cỗ phiếu [I].---- ¿+ + 25 +5 2s+Se>+zx+Eerxzxerszxsre 1 Hình 1.2: (a) Một minh hoa motif. (b) Một minh hoa bat thường.
