Luận văn thạc sĩ khoa học máy tính phát hiện motif trên dữ liệu chuỗi thời gian dựa vào giải thuật sequitur

Luận văn thạc sĩ khoa học máy tính nghiên cứu phát hiện motif trên dữ liệu chuỗi thời gian sử dụng giải thuật Sequitur, ứng dụng hiệu quả trong phân tích dữ liệu.

• Tác giả: Nguyễn Ngọc Phiên
• Người hướng dẫn: PGS. Dương Tuấn Anh
• Trường học: Đại học Bách Khoa - Đại học Quốc gia Thành phố Hồ Chí Minh
• Chuyên ngành: Khoa học máy tính
• Đề tài: Phát hiện motif trên dữ liệu chuỗi thời gian dựa vào giải thuật Sequitur
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2017
• Địa điểm: Thành phố Hồ Chí Minh

Tóm tắt

I. Giới thiệu đề tài

Luận văn tập trung vào phát hiện motif trên dữ liệu chuỗi thời gian bằng giải thuật Sequitur, một phương pháp mới trong khoa học máy tính. Dữ liệu chuỗi thời gian là dữ liệu được đo đạc tuần tự theo thời gian, xuất hiện trong nhiều lĩnh vực như tài chính, y tế, và môi trường. Việc phân tích chuỗi thời gian và tìm kiếm motif là một nhiệm vụ quan trọng trong khai phá dữ liệu. Luận văn đề xuất một cách tiếp cận mới dựa trên giải thuật Sequitur để phát hiện motif mà không cần xác định trước tham số chiều dài của motif, đồng thời ứng dụng kết quả để phát hiện tính chu kỳ trên dữ liệu chuỗi thời gian.

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

Dữ liệu chuỗi thời gian là dữ liệu được đo đạc liên tục theo thời gian, thường có kích thước lớn và gia tăng nhanh. Các lĩnh vực ứng dụng bao gồm tài chính, y tế, và môi trường. Việc xử lý dữ liệu và phân tích chuỗi thời gian đòi hỏi các phương pháp hiệu quả để giảm thiểu thời gian và tài nguyên tính toán.

1.2. Phát hiện motif

Phát hiện motif là quá trình tìm kiếm các chuỗi con tương tự nhau xuất hiện lặp đi lặp lại trong dữ liệu chuỗi thời gian. Các phương pháp truyền thống như Random Projection có nhược điểm là tốn nhiều thời gian với dữ liệu lớn. Luận văn đề xuất sử dụng giải thuật Sequitur để khắc phục hạn chế này.

II. Cơ sở lý thuyết

Luận văn trình bày các khái niệm cơ bản về chuỗi thời gian, cửa sổ trượt, và độ đo tương tự như Dynamic Time Warping (DTW). Các phương pháp biểu diễn chuỗi thời gian như PAA, SAX, và ESAX được giới thiệu để thu giảm số chiều và rời rạc hóa dữ liệu. Giải thuật Sequitur được phân tích chi tiết như một phương pháp hiệu quả để phát hiện motif.

2.1. Độ đo tương tự

Các độ đo tương tự như DTW được sử dụng để so sánh các chuỗi thời gian. DTW cho phép đo lường sự tương tự giữa các chuỗi có độ dài khác nhau, phù hợp cho việc phân tích chuỗi thời gian.

2.2. Biểu diễn chuỗi thời gian

Các phương pháp PAA, SAX, và ESAX được sử dụng để biểu diễn chuỗi thời gian dưới dạng rời rạc, giúp giảm thiểu kích thước dữ liệu và tăng hiệu quả tính toán trong phát hiện motif.

III. Phương pháp giải quyết vấn đề

Luận văn đề xuất một phương pháp mới dựa trên giải thuật Sequitur để phát hiện motif trên dữ liệu chuỗi thời gian. Phương pháp này bao gồm các bước: thu giảm số chiều bằng EPAA, rời rạc hóa dữ liệu bằng ESAX, và áp dụng giải thuật Sequitur để tìm motif. Kết quả motif được sử dụng để ước lượng chiều dài motif và phát hiện tính chu kỳ trên dữ liệu.

3.1. Thu giảm số chiều

Phương pháp EPAA được sử dụng để thu giảm số chiều của dữ liệu chuỗi thời gian, giúp giảm thiểu kích thước dữ liệu mà vẫn duy trì các đặc trưng quan trọng.

3.2. Rời rạc hóa dữ liệu

Phương pháp ESAX được áp dụng để rời rạc hóa chuỗi thời gian, biến đổi dữ liệu thành các ký hiệu rời rạc, phù hợp cho việc phát hiện motif bằng giải thuật Sequitur.

IV. Thực nghiệm và kết quả

Luận văn tiến hành thực nghiệm trên các tập dữ liệu khác nhau như ECG, RIVER, và WINDING. Kết quả cho thấy giải thuật Sequitur với ESAX cho kết quả phát hiện motif chính xác và nhanh hơn so với các phương pháp truyền thống như Random Projection. Phương pháp đề xuất cũng được ứng dụng để phát hiện tính chu kỳ trên dữ liệu, mang lại hiệu quả cao trong phân tích chuỗi thời gian.

4.1. So sánh kết quả

Kết quả thực nghiệm cho thấy giải thuật Sequitur với ESAX tìm được nhiều motif hơn và nhanh hơn so với Random Projection trên các tập dữ liệu lớn.

4.2. Ứng dụng phát hiện chu kỳ

Các motif tìm được được sử dụng để phát hiện tính chu kỳ trên dữ liệu chuỗi thời gian, mang lại kết quả chính xác và hiệu quả trong các ứng dụng thực tế.

V. Kết luận

Luận văn đã đề xuất và thực hiện thành công phương pháp phát hiện motif trên dữ liệu chuỗi thời gian dựa trên giải thuật Sequitur. Phương pháp này không chỉ hiệu quả trong việc tìm kiếm motif mà còn ứng dụng được trong phát hiện tính chu kỳ. Các kết quả thực nghiệm cho thấy phương pháp đề xuất vượt trội so với các phương pháp truyền thống, mở ra hướng nghiên cứu mới trong khoa học máy tính và xử lý dữ liệu.

5.1. Đóng góp của đề tài

Luận văn đã đóng góp một phương pháp mới trong phát hiện motif và phân tích chuỗi thời gian, mang lại hiệu quả cao trong các ứng dụng thực tế.

5.2. Hướng phát triển

Hướng phát triển tiếp theo bao gồm cải tiến giải thuật Sequitur để xử lý các tập dữ liệu lớn hơn và ứng dụng phương pháp này trong các lĩnh vực khác như y tế và tài chính.

Trích đoạn nội dung tài liệu

ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH TRƢỜNG ĐẠI HỌC BÁCH KHOA ---------------------------------- NGUYỄN NGỌC PHIÊN PHÁT HIỆN MOTIF TRÊN DỮ LIỆU CHUỖI THỜI GIAN DỰA VÀO GIẢI THUẬT SEQUITUR CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH MÃ SỐ: 60.01 LUẬN VĂN THẠC SĨ THÀNH PHỐ HỒ CHÍ MINH, tháng 06 năm 2017 ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH TRƢỜNG ĐẠI HỌC BÁCH KHOA ---------------------------------- NGUYỄN NGỌC PHIÊN PHÁT HIỆN MOTIF TRÊN DỮ LIỆU CHUỖI THỜI GIAN DỰA VÀO GIẢI THUẬT SEQUITUR CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH MÃ SỐ: 60.01 LUẬN VĂN THẠC SĨ HƢỚNG DẪN KHOA HỌC: PGS. DƢƠNG TUẤN ANH THÀNH PHỐ HỒ CHÍ MINH, tháng 06 năm 2017 CÔNG TRÌNH ĐƢỢC HOÀN THÀNH TẠI TRƢỜNG ĐẠI HỌC BÁCH KHOA – ĐHQG TP HCM Cán bộ hƣớng dẫn khoa học: PGS.

Dƣơng Tuấn Anh Cán bộ chấm nhận xét 1: TS. Phạm Văn Chung Cán bộ chấm nhận xét 2: TS. Lê Văn Quốc Anh 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 18 tháng 07 năm 2017. Thành phần hội đồng đánh giá luận văn thạc sỹ gồm: 1.

Quản Thành Thơ – Chủ tịch. Nguyễn An Khƣơng – Thƣ ký. Phạm Văn Chung – Phản biện 1. Lê Văn Quốc Anh – Phản biện 2.

Trần Tuấn Anh – Ủy viên. Xác nhận của chủ tịch hội đồng đánh giá luận văn 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 HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM TRƢỜNG ĐẠI HỌC BÁCH KHOA Độ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 NGỌC PHIÊN. Ngày, tháng, năm sinh: 16/11/1992.

Nơi sinh:Quảng Ngãi Chuyên ngành: Khoa học máy tính. TÊN ĐỀ TÀI: Phát hiện motif trên dữ liệu chuỗi thời gian dựa vào giải thuật Sequitur. NHIỆM VỤ VÀ NỘI DUNG:. NGÀY GIAO NHIỆM VỤ : 16/01/2017.

NGÀY HOÀN THÀNH NHIỆM VỤ : 18/06/2017. CÁN BỘ HƢỚNG DẪN : PGS. DƢƠNG TUẤN ANH. CÁN BỘ HƢỚNG DẪN TRƢỞNG KHOA………………… (Họ tên và chữ ký) (Họ tên và chữ ký) PGS.

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. Dƣơng Tuấn Anh, ngƣời Thầy đã tận tình chỉ bảo tôi trong suốt quá trình thực hiện luận văn và tạo mọi điều kiện tốt nhất để tôi có thể hoàn thành luận văn này. Tôi xin cảm ơn quý thầy cô ở trƣờng Đại học Bách Khoa đã truyền đạt các kiến thức cần thiết trong quá trình học tập tại trƣờng. Tôi xin cảm ơn gia đình, bạn bè và đồng nghiệp đã động viên và tạo mọi điều kiện thuận lợi để tôi có thể tiếp tục theo đuổi việc học tập và nghiên cứu.

i TÓM TẮT LUẬN VĂN Việc khai phá dữ liệu chuỗi thời gian đã và đang thu hút rất nhiều sự nghiên cứu trên thế giới. Trong đó việc nghiên cứu phát hiện motif rất hữu ích cho các công 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 dùng phổ biến là chiếu ngẫu nhiên (Random Projection). Phƣơng pháp này đƣợc thực hiện đơn giản, dễ tiếp cận.

Tuy nhiên phƣơng pháp này có nhƣợc điểm chạy rất lâu với dữ liệu chuỗi thời gian có kích thƣớc lớn. Ngoà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 tham số chiều dài motif cho trƣớc, đây 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 tham số chiều dài của motif. Cách tiếp cận này dựa vào giải thuật Sequitur.

Luận văn cũng đề xuất sử dụng các độ dài motif tìm đƣợc từ cách tiếp cận này để làm tham số chiều dài cho các giải thuật phát hiện motif khác, đồng thời áp dụng các motif tìm đƣợc để phát hiện tính chu kì trên dữ liệu chuỗi thời gian. ii ABSTRACT Time series data mining has been attracted a huge range of reseach in the world, in which the invention and discovery of motifs are very useful for time series data mining. Random Projection is one of the most common methods that are used in the motif detection algorithms. This method is simple and accessible.

However, this kind of work has some weaknesses such as processing time, and large size data cosumming. Moreover, most of the algorithms require a given length parameter motif. That is one of the major obstacles of motif detection algorithms. This thesis applies a new approach which is based on the Sequitur algorithm to detect motif without identifying pre-length parameter of the motif.

Besides, the use of motif length delivered from this approach for other motif detection algorithms is suggested, and detects the period on time series data. iii 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 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 trƣờng khác. Ngày 07 tháng 06 năm 2017 Nguyễn Ngọc Phiên iv MỤC LỤC LỜI CẢM ƠN. iii LỜI CAM ĐOAN.

iv CHƢƠNG 1: GIỚI THIỆU ĐỀ TÀI. Dữ liệu chuỗi thời gian. Khai phá thông tin trên dữ liệu chuỗi thời gian. Phát hiện motif trên chuỗi dữ liệu thời gian.

Mục tiêu và giới hạn của đề tài. Những kết quả đạt đƣợc. Cấu trúc của luận văn.6 CHƢƠNG 2: CƠ SỞ LÝ THUYẾT. Một số khái niệm cơ bản.

Chuỗi thời gian (Time series). Cửa sổ trƣợt (Slide window). Trùng khớp không tầm thƣờng (Non-Self Match). Các công trình về độ đo tƣơng tự.

Độ đo xoắn thời gian động (Dynamic Time Warping- DTW). Các công trình về biểu diễn chuỗi thời gian. Phƣơng pháp xấp xỉ gộp từng đoạn (PAA). Phƣơng pháp xấp xỉ gộp từng đoạn mở rộng EPAA (Extended PAA).

Phép xấp xỉ gộp ký hiệu hóa SAX. Phƣơng pháp xấp xỉ gộp ký hiệu hoá mở rộng ESAX (Extended SAX) .24 CHƢƠNG 3: TỔNG THUẬT CÁC CÔNG TRÌNH LIÊN QUAN. Phát hiện 1-Motif dựa vào giải thuật Brute Force. Phát hiện Motif dựa vào giải thuật Random Projecttion.

Phát hiện Motif dựa vào giải thuật Sequitur .1 Giải thuật Sequitur .2 Phát hiện motif dựa vào giải thuật Sequitur .31 CHƢƠNG 4: PHƢƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ .2 Hƣớng giải quyết. Thu giảm số theo phép biến đổi EPAA. Rời rạc hoá dữ liệu theo phép biến đổi ESAX. Xây dựng phƣơng pháp đề xuất dựa vào giải thuật Sequitur.

Ƣớc lƣợng chiều dài 1-motif. Phát hiện tính chu kì dựa vào motif .36 CHƢƠNG 5: THỰC NGHIỆM. Thực nghiệm 1: so sánh kết quả motif của giải thuật Sequitur trên phép biến đổi SAX và ESAX. Tập dữ liệu ECG 3500 điểm.

Tập dữ liệu ECG 14000 điểm. Tập dữ liệu RIVER 7500 điểm. Tập dữ liệu WINGDING 2500 điểm. Dữ liệu ERP 10120 điểm.

Thực nghiệm 2: ƣớc lƣợng độ dài 1-motif và phát hiện 1-motif. Ƣớc lƣợng độ dài 1-motif và phát hiện 1-motif. Chất lƣợng motif. Thời gian thực thi.

Thực nghiệm 3: Ứng dụng phát hiện chu kì dựa vào motif. Dữ liệu điện tâm đồ ECG 14000 điểm. Dữ liệu điện tâm đồ ECG 7000 điểm. Dữ liệu dòng chảy RIVER 7500 điểm.

Dữ liệu công nghiệp WINDING 5990 điểm .62 CHƢƠNG 6: KẾT LUẬN. Những đóng góp của đề tài. Hƣớng phát triển .64 TÀI LIỆU THAM KHẢO. 65 PHỤ LỤC: BẢNG ĐỐI CHIẾU THUẬT NGỮ ANH-VIỆT .A LÝ LỊCH TRÍCH NGANG.

C vii DANH SÁCH BẢNG VÀ HÌNH ẢNH Hình 1. Dữ liệu điện tâm đồ. Cách tiếp cận chung cho các nhiệm vụ khai phá dữ liệu. Một minh hoạ chuỗi con motif.

Một minh hoạ chuỗi con bất thƣờng. Một minh hoạ về chuỗi con. Chuỗi C và M khớp với nhau. Khoảng cách hai motif < 2R (A); Khoảng cách hai motif > 2R (B) ([8]).

Minh hoạ sự khác nhau giữa hai độ đo Euclid và DTW. Một ví dụ đƣờng xoắn [5]. Phƣơng pháp biểu diễn PAA với n = 128, w=8 ([7]). Vài điểm quan trọng bị mất khi chỉ biểu diễn bằng PAA [1].

Minh hoạ các vị trí Pmin, Pmax, Pmid [1]. Phƣơng pháp chuẩn hóa trung bình zero [12]. Bảng thống kê dùng để tra những điểm ngắt theo phân bố Gauss với số vùng phân bố từ 3 đến 10. Minh họa về rời rạc hóa dữ liệu ([7]).

Minh họa 3 dạng biểu diễn chuỗi thời gian và các hàm tính khoảng cách tƣơng ứng. A) Chuỗi thời gian ban đầu và hàm tính khoảng cách Euclid. B) Dạng biểu diễn PAA của chuỗi thời gian và hàm tính khoảng cách DR. C) Dạng biểu diễn SAX và hàm tính khoảng cách MINDIST ([7]).

Dữ liệu tài chính đƣợc biểu diễn bằng ESAX ([1]). Trung bình kết quả tìm kiếm trên tập dữ liệu 5000, với kích thƣớc tập ký tự alphabetsize = 6, số chiều thu giảm của SAX là 16 và số chiều thu giảm của ESAX là 48 [1]. Minh hoạ tìm kiếm bằng phép biến đổi SAX và ESAX, (a) chuỗi cần tìm kiếm, (b) (c) các kết quả đƣợc tìm thấy bởi ESAX, (d) (e) (f) (i) (j) các kết quả đƣợc tìm thấy bởi SAX [1]. Giải thuật Brute Force phát hiện 1- Motif [8].

Bảng chứa tất cả các chuỗi con từ cửa sổ trƣợt. Minh họa việc chiếu ngẫu nhiên lên cột 1 và 2, cập nhật vào 28 Hình 3. Minh họa việc chiếu ngẫu nhiên lên cột 2 và 4, cập nhật vào 28 Bảng 3. Ví dụ về giải thuật Sequitur.

Giải thuật Sequitur [8]. Ví dụ về giải thuật Sequitur. Giải thuật phát hiện chu kì [15]. Giải thuật tính chu kì dựa vào motif [15].

Biểu diễn motif của giải thuật Sequitur_SAX trên dữ liệu ECG. Biểu diễn motif của giải thuật Sequitur_ESAX trên dữ liệu ECG. Biểu diễn motif của giải thuật Sequitur_SAX trên dữ liệu ECG. Biểu diễn motif của giải thuật Sequitur_ESAX trên dữ liệu ECG.

Biểu diễn motif của giải thuật Sequitur_SAX trên dữ liệu RIVER. Biểu diễn motif của giải thuật Sequitur_ESAX trên dữ liệu RIVER. Biểu diễn motif của giải thuật Sequitur_SAX trên dữ liệu WINDING. Biểu diễn motif của giải thuật Sequitur_ESAX trên dữ liệu WINDING.

Biểu diễn motif của giải thuật Sequitur_SAX trên dữ liệu ERP. Biểu diễn motif của giải thuật Sequitur_ESAX trên dữ liệu ERP. So sánh kết quả số lƣợng motif tìm thấy bởi Sequitur_SAX và Sequitur_ESAX. Kết quả mọi motif tìm thấy của giải thuật Sequitur_ESAX của dữ liệu ECG.

Ví dụ một phần luật văn phạm thu đƣợc của dữ liệu ECG 3500 điểm. Kết quả 1-motif tìm thấy của giải thuật RP_SAX của dữ liệu ECG46 Hình 5. Kết quả mọi motif tìm thấy của giải thuật Sequitur_ESAX của dữ liệu ECG .