Luận văn thạc sĩ: Cấu trúc chỉ mục cho dữ liệu chuỗi thời gian sử dụng độ đo khoảng cách động

Chuyên đề nghiên cứu Cấu trúc chỉ mục dữ liệu chuỗi thời gian với độ đo khoảng cách động, cập nhật xu hướng mới, giá trị tham khảo cao cho chuyên gia

• Tác giả: Võ Tuệ Linh
• Người hướng dẫn: PGS. Dương Tuấn Anh
• Trường học: Đại học Bách Khoa - ĐHQG - HCM
• Chuyên ngành: Khoa học máy tính
• Đề tài: Cấu Trúc Chỉ Mục Cho Dữ Liệu Chuỗi Thời Gian Với Độ Đo Khoảng Cách Xoắn Thời Gian Động
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2012
• Địa điểm: TP. Hồ Chí Minh

Tóm tắt

I. Giới thiệu

Dữ liệu chuỗi thời gian đang ngày càng trở nên quan trọng trong các lĩnh vực như khoa học, y tế, công nghiệp và tài chính. Cấu trúc chỉ mục dữ liệu là một phần thiết yếu trong việc xử lý và phân tích dữ liệu chuỗi thời gian, cho phép truy xuất và tìm kiếm thông tin hiệu quả. Đặc biệt, việc áp dụng đo khoảng cách động giúp cải thiện độ chính xác trong việc tìm kiếm tương tự. Sự cần thiết của việc phát triển các phương pháp mới để xử lý dữ liệu chuỗi thời gian là rất rõ ràng, đặc biệt khi phải đối mặt với khối lượng dữ liệu lớn và đa chiều.

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

Chuỗi thời gian được định nghĩa là một tập hợp các quan sát được thu thập theo thời gian, với mỗi giá trị đại diện cho một điểm dữ liệu tại một thời điểm nhất định. Việc phân tích chuỗi thời gian không chỉ giúp phát hiện các mẫu và xu hướng trong dữ liệu mà còn hỗ trợ trong việc dự đoán các sự kiện tương lai. Các ứng dụng thực tiễn bao gồm phân tích giá cổ phiếu, dữ liệu y tế và dự báo thời tiết. Các phương pháp phân tích chuỗi thời gian như tìm kiếm tương tự và phát hiện bất thường đóng vai trò quan trọng trong việc khai thác thông tin từ dữ liệu này.

II. Cấu trúc chỉ mục cho dữ liệu chuỗi thời gian

Cấu trúc chỉ mục cho dữ liệu chuỗi thời gian đã thu hút sự quan tâm của nhiều nhà nghiên cứu. Hầu hết các nghiên cứu trước đây tập trung vào việc sử dụng đo khoảng cách Euclid, một phương pháp đơn giản nhưng có nhiều hạn chế. Để cải thiện độ chính xác trong việc tìm kiếm tương tự, đo khoảng cách động được giới thiệu, cho phép xác định sự tương đồng giữa các chuỗi thời gian ngay cả khi chúng có sự dịch chuyển về thời gian hoặc biên độ. Cấu trúc chỉ mục như R-Tree và cấu trúc dựa trên lưới đã được phát triển để tối ưu hóa việc tìm kiếm trong không gian nhiều chiều.

2.1 Cấu trúc chỉ mục R Tree

R-Tree là một trong những cấu trúc chỉ mục phổ biến nhất cho dữ liệu không gian. Nó cho phép lưu trữ và truy xuất dữ liệu theo cách tối ưu hóa, giúp giảm thiểu số lượng truy vấn cần thiết để tìm kiếm thông tin. Tuy nhiên, trong trường hợp dữ liệu chuỗi thời gian với độ đo khoảng cách động, R-Tree có thể gặp khó khăn do tính chất cao chiều của dữ liệu. Điều này dẫn đến việc cần phát triển các phương pháp mới để cải thiện hiệu suất của R-Tree trong việc xử lý dữ liệu chuỗi thời gian.

2.2 Cấu trúc chỉ mục dựa trên lưới

Cấu trúc chỉ mục dựa trên lưới là một phương pháp khác để tối ưu hóa việc tìm kiếm dữ liệu chuỗi thời gian. Phương pháp này chia không gian thành các ô lưới và lưu trữ dữ liệu theo cách cho phép truy xuất nhanh chóng. Nhờ vào việc sử dụng đo khoảng cách động, cấu trúc này có thể xử lý tốt hơn các trường hợp dữ liệu có sự thay đổi về thời gian và biên độ. Nghiên cứu đã chỉ ra rằng phương pháp này có thể cải thiện đáng kể hiệu suất tìm kiếm so với các phương pháp truyền thống.

III. Kết quả đạt được

Thông qua nghiên cứu, một số kết quả quan trọng đã được đạt được. Việc hiểu rõ hơn về cấu trúc chỉ mục R-Tree và cấu trúc dựa trên lưới đã giúp cải thiện khả năng tìm kiếm dữ liệu chuỗi thời gian. Bên cạnh đó, việc áp dụng các phương pháp như chặn dưới Keogh và đo khoảng cách động đã tạo ra những cải tiến đáng kể trong việc xác định chuỗi con tương đồng. Kết quả thực nghiệm cho thấy rằng cả hai phương pháp đều có những ưu điểm và nhược điểm riêng, và việc lựa chọn phương pháp phù hợp sẽ phụ thuộc vào từng trường hợp cụ thể.

3.1 Hiệu quả của phương pháp

Các thử nghiệm cho thấy rằng phương pháp chặn dưới Keogh có thể cung cấp độ chính xác cao hơn trong việc xác định các chuỗi con tương đồng, trong khi cấu trúc dựa trên lưới cho phép truy xuất nhanh chóng và hiệu quả hơn. Sự so sánh giữa hai phương pháp này đã chỉ ra rằng trong nhiều tình huống, việc kết hợp cả hai phương pháp có thể mang lại hiệu quả tối ưu nhất cho việc tìm kiếm dữ liệu chuỗi thời gian.

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 -------------------- VÕ TUỆ LINH CẤU TRÖC CHỈ MỤC CHO DỮ LIỆU CHUỖI THỜI GIAN VỚI ĐỘ ĐO KHOẢNG CÁCH XOẮN THỜI GIAN ĐỘNG Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số: 00708198 LUẬN VĂN THẠC SĨ TP. HỒ CHÍ MINH, tháng 07 năm 2012 CÔNG TRÌNH ĐƢỢC HOÀN THÀNH TẠI TRƢỜNG ĐẠI HỌC BÁCH KHOA - ĐHQG - 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 : PGS. Lê Hoài Bắc. Cán bộ chấm nhận xét 2 : TS. Võ Thị Ngọc Châu.

Luận văn thạc sĩ đƣợc bảo vệ tại Trƣờng Đại học Bách Khoa, ĐHQG Tp. Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm: \ 1. Bùi Hoài Thắng. Lê Hoài Bắc.

Võ Thị Ngọc Châu. Dƣơng Tuấn Anh. Lê Thanh Vân. 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 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: VÕ TUỆ LINH. Ngày, tháng, năm sinh: 05/09/1984. Nơi sinh: Tiền Giang. Chuyên ngành: Khoa học máy tính.

CẤU TRÚC CHỈ MỤC CHO DỮ LIỆU CHUỖI THỜI GIAN VỚI ĐỘ ĐO KHOẢNG CÁCH XOẮN THỜI GIAN ĐỘNG. NHIỆM VỤ VÀ NỘI DUNG:. Nghiên cứu so sánh hiệu quả của hai cấu trúc chỉ mục: cấu trúc chỉ mục R-Tree và cấu trúc chỉ mục dựa trên lƣới khi áp dụng vào giải thuật tìm kiếm chuỗi con tƣơng đồng nhất trên dữ liệu chuỗi thời gian. NGÀY GIAO NHIỆM VỤ :.

NGÀY HOÀN THÀNH NHIỆM VỤ:. CÁN BỘ HƢỚNG DẪN : PGS. Dƣơng Tuấn Anh. CÁN BỘ HƢỚNG DẪN CHỦ NHIỆM BỘ MÔN ĐÀO TẠO (Họ tên và chữ ký) (Họ tên và chữ ký) TRƢỞNG KHOA….……… (Họ tên và chữ ký) i 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 hƣớng dẫn tôi trong suốt quá trình học Cao học và tạo mọi điều kiện để tôi có thể hoàn thành luận văn này. Tôi cũng xin cảm ơn gia đình, bạn bè đã động viên và tạo mọi điều kiện tốt nhất để tôi có thể tiếp tục theo đuổi việc học tập và nghiên cứu. Tôi trân trọng dành tặng thành quả của luận văn này cho chồng của tôi. Nhờ sự động viên của anh, mà tôi có thể vƣợt qua mọi khó khăn để có đƣợc thành quả nhƣ ngày hôm nay.

ii TÓM TẮT LUẬN VĂN Biểu diễn dữ liệu chuỗi thời gian ngày càng đóng vai trò quan trọng trong các bài toán khai phá dữ liệu chuỗi thời gian. Một trong các bài toán khai phá dữ liệu chuỗi thời gian là bài toán tìm kiếm tƣơng tự. Bài toán tìm kiếm tƣơng tự trong cơ sở dữ liệu chuỗi thời gian là một bài toán thú vị và đầy thử thách. Bởi vì bản chất số chiều cao của dữ liệu, hầu hết những lời giải đƣợc đƣa ra là thu giảm số chiều, và xây dựng cấu trúc chỉ mục nhiều chiều cho dữ liệu thu giảm.

Hầu hết những giải thuật đã đƣợc sử dụng để đánh chỉ mục cho chuỗi thời gian sử dụng độ đo khoảng cách Euclid, nhƣng độ đo Euclid thì rất thô và không chính xác. Điều chúng tôi cần là một phép đo cho phép một phép dịch mềm dẻo trên hệ trục tọa độ. Đó chính là độ đo khoảng cách xoắn thời gian động. Bởi vì sự mềm dẻo của độ đo xoắn thời gian động, nó đƣợc sử dụng rộng rãi trong khoa học, y khoa, công nghiệp và tài chính.

Đề tài này tìm hiểu về các cấu trúc chỉ mục cho dữ liệu chuỗi thời gian với độ đo xoắn thời gian động(DTW). Thông qua hai cấu trúc chỉ mục R-Tree và cấu trúc chỉ mục dựa trên lƣới, chúng tôi so sánh hiệu quả của hai cấu trúc chỉ mục này khi giải quyết bài toán tìm K láng giềng gần nhất với độ đo xoắn thời gian động. iii ABSTRACT The representation of time series plays more and more important role in time series data mining problems. One of problems relating to time series data mining is Similarity Search.

Similarity search in large time series databases is an interesting and challenging problem. Because of the high dimensional nature of the data, the difficulties associated with dimensionality curse arise. The most promising solution is to use dimensionality reduction, and construct a multi-dimensional index structure for the reduced data. Most algorithms used to index time series utilize the Euclidean distance or some variation thereof.

However, it has been forcefully shown that the Euclidean distance is a very brittle distance measure. What is needed is a method that allows an elastic shifting of the time axis. It is Dynamic Time Warping(DTW). Because of this flexiblility, DTW is widely used in science, medicine, industry and finance.

This thesis researchs about indexing for time series using Dynamic Time Warping (DTW). With R-Tree and grid-based indexing, we compare the efficiency of these methods in KNN Search using dynamic time warping. iv 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.tháng…………năm………… Võ Tuệ Linh v MỤC LỤC LỜI CẢM ƠN. iii MỤC LỤC.

v DANH MỤC HÌNH. vii DANH MỤC BẢNG. ix Chƣơng 1: Giới thiệu .1 Dữ liệu chuỗi thời gian .2 Cấu trúc chỉ mục cho dữ liệu chuỗi thời gian với độ đo xoắn thời gian động .3 Mục tiêu nghiên cứu.4 Kết quả đạt đƣợc .5 Cấu trúc của đề cƣơng luận văn. 6 Chƣơng 2: Tổng thuật về các công trình liên quan .1 Các công trình về độ đo tƣơng tự .2 Phƣơng pháp chuỗi con chung dài nhất (Longest Common Subsequence – LCS) .3 Độ đo khoảng cách xoắn thời gian động .2 Các cấu trúc chỉ mục cho dữ liệu chuỗi thời gian .1 Cấu trúc chỉ mục cây hậu tố .2 Cấu trúc chỉ mục R-tree .3 Khung thức GEMINI (GEneric Multimedia INdexIng) .3 Đánh chỉ mục chính xác cho độ đo khoảng cách xoắn thời gian động .1 Chặn dƣới cho DTW .2 Đánh chỉ mục cho DTW sử dụng LB_Keogh.

21 Chƣơng 3: Cơ sở lý thuyết .1 Cấu trúc chỉ mục R-Tree .1 Giới thiệu về R-Tree.2 Cấu trúc chỉ mục R-Tree .3 Tìm kiếm và cập nhật .2 Cấu trúc chỉ mục dựa trên lƣới .1 Tổng quát về cách tiếp cận .2 Biểu diễn dữ liệu .3 Tìm kiếm K láng giềng gần nhất của DTW. 48 Chƣơng 4: Hiện thực và thử nghiệm .1 Giao diện ngƣời dùng .2 Kiến trúc của chƣơng trình. 54 Chƣơng 5: Kết luận và hƣớng phát triển .2 Hƣớng phát triển. 59 Tài liệu tham khảo.

60 PHỤ LỤC A: BẢNG ĐỐI CHIẾU THUẬT NGỮ ANH-VIỆT………………….A1 PHỤ LỤC B: LÝ LỊCH TRÍCH NGANG……………………………………….A3 vii DANH MỤC HÌNH Hình 1.1: Chuỗi thời gian giá trị cổ phiểu của Microsoft từ 29/11/2001 tới 29/11/2002 .2: Một sự so sánh trực quan giữa khoảng cách Euclid và DTW ([21]) .3: Biểu đồ 2 tập dữ liệu thực tế: Shuttle và Koski_ecg ( [21]) .1: Trƣờng hợp 2 chuỗi có đƣờng cơ bản lệch nhau và biên độ dao động khác nhau ([15]) .2: A) Hai chuỗi thời gian tƣơng đồng Q và C nhƣng lệch pha. B) Để đo khoảng cách chuỗi thời gian, chúng tôi xây dựng ma trận xoắn thời gian động và tìm kiếm cho đƣờng xoắn thời gian động tối ƣu nhất, đƣợc trình bày bằng những hình vuông đậm. C) Kết quả của phép đo ( [7]) .3: Cây hậu tố cho các chuỗi S1=babab, S2=aab, S3=baa ([32]) .4: Minh họa cấu trúc R-tree cho dữ liệu không gian([1]) .5: Phƣơng pháp đo chặn dƣới đƣợc đƣa ra bởi Kim ([7]) .6: Chặn dƣới đƣợc đƣa ra bởi Yi ([7]) .7: Ràng buộc toàn cục hạn chế phạm vụ của đƣờng xoắn, hạn chế chúng ra khỏi khu vực màu xám. Hai ràng buộc phổ biến nhất: Sakoe-Chiba và Itakura ([7]) .8: Ví dụ về ràng buộc cục bộ (nguồn [11]) .9: Một minh họa cho chuỗi U và L đƣợc tạo ra cho chuỗi Q.

A đƣợc tạo ra sử dụng dải Sakoe-Chiba và B sử dụng dải Itakura (nguồn [7]) .10: Một minh họa của hàm tính chặn dƣới LB_Keogh(Q,C) ([7]) .11: Biểu diễn PAA cho một chuỗi chiều dài 256 thu giảm tới 16 chiều ([7]) .12: Chúng tôi minh họa U và L nhƣ là những hàm hằng số, mà không có giao giữa U và L([7]) .13: A)Một biểu diễn của MBR. B) Một tập con của truy vấn C) Một minh họa của hàm MINDIST ([7]).1a: Cấu trúc cây R Tree ([1]) .1b: Quan hệ che phủ giữa các hình chữ nhật ([1]) .2: Minh họa việc tách nút ([1]) .3: Thu giảm số chiều dựa trên lƣới, đƣờng dày là đƣờng xấp xỉ chuỗi thời gian ([21]) .4: Chuỗi thời gian thực tế: (A) trƣờng hợp rất hiếm, (B) trƣờng hợp phổ biến ([22]) .5: Xác định những phân đoạn của chuỗi thời gian đƣợc lƣợng tử hóa ([18]) .6: Thu giảm điểm dữ liệu của v với kĩ thuật DDR. Bốn hình chữ nhật màu xám biểu diễn những vùng chịu đựng lỗi ([18]).7: Biểu diễn của một chuỗi thời gian, n bit nhị phân biểu thị dữ liệu nào trong v bị bỏ qua. Những ô vuông xác định giá trị lƣợng tử hóa (i) của điểm dữ liệu (vi)([18]) .8: Chặn trên và chặn dƣới.

(A) qi lớn hơn giá trị chặn trên của giá trị đƣợc lƣợng tử hóa i của vi. (B) qi nhỏ hơn giá trị đƣợc lƣợng tử hóa i của vi .9: Chặn trên và chặn dƣới. (A) qi lớn hơn giá trị chặn trên của giá trị đƣợc lƣợng tử hóa i của vi cộng với một hệ số chịu đựng lỗi. (B) qi nhỏ hơn giá trị đƣợc lƣợng tử hóa i của vi trừ đi hệ số chịu đựng lỗi .1: Phần nhập liệu của form giao diện .2: Phần xuất kết quả của form giao diện .3: Kiến trúc của chƣơng trình .1: Độ chặt chặn dƣới .2:Số lần truy xuất đĩa.

58 ix DANH MỤC BẢNG Bảng 2.1: Mã giả giải thuật xây dựng chỉ mục GEMINI ([4]) .2: Một giải thuật mà sử dụng phƣơng pháp đo chặn dƣới để tăng tốc việc quét tuần tự cho một chuỗi truy vấn Q ([7]) .3: Giải thuật K-NN để tính toán chính xác K láng giềng gần nhất của một chuỗi thời gian truy vấn Q sử dụng cấu trúc chỉ mục đa chiều(nguồn [7]).4: Giải thuật tìm kiếm phạm vi để truy xuất tất cả những chuỗi thời gian trong một phạm vi của  từ chuỗi thời gian truy vấn Q. Hàm này đƣợc gọi nhƣ là RangeSearch(Q, ε, root_node_of_index)([7]).1: Giải thuật xây dựng file chỉ mục DDR ([22]) .2: Giai đoạn tinh lọc sử dụng DDR([22]) .