Báo cáo Tìm kiếm tương tự trong cơ sở dữ liệu chuỗi thời gian (Phần 1)

Nội dung text: Báo cáo Tìm kiếm tương tự trong cơ sở dữ liệu chuỗi thời gian (Phần 1)

1. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT THÀNH PHỐ HỒ CHÍ MINH BÁO CÁO TỔNG KẾT ĐỀ TÀI KH&CN CẤP TRƯỜNG TÌM KIẾM TƯƠNG TỰ TRONG CƠ SỞ DỮ LIỆU CHUỖI THỜI GIAN S K C 0 0 0 2 8 1 MÃ SỐ: T2011- 06TĐ S K C 0 0 3 3 4 7 THÀNH PHỐ HỒ CHÍ MINH, 2011
2. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT TP. HCM KHOA CÔNG NGHỆ THÔNG TIN  BÁO CÁO TỔNG KẾT ĐỀ TÀI KHOA HỌC VÀ CÔNG NGHỆ CẤP TRƢỜNG TÌM KIẾM TƢƠNG TỰ TRONG CƠ SỞ DỮ LIỆU CHUỖI THỜI GIAN MÃ SỐ: T2011-06TĐ Chủ nhiệm đề tài: GVC. Ths Nguyễn Thành Sơn. Thành viên đề tài: TS. Nguyễn Phƣơng TP. HỒ CHÍ MINH – 07/2011
3. MỤC LỤC trang DANH MỤC CÁC HÌNH ẢNH 3 PHẦN MỞ ĐẦU 5 1. Tình hình nghiên cứu trong và ngoài nước 5 2. Tính cấp thiết của đề tài 5 3. Ý nghĩa lý luận và thực tiễn 6 4. Các đối tượng nghiên cứu 6 5. Phạm vi và các phương pháp nghiên cứu 6 PHẦN NỘI DUNG 7 Chương 1. Các kiến thức cơ sở 7 1.1 Tổng quan về dữ liệu chuỗi thời gian và bài toán tìm kiếm tương tự 7 1.2. Các công trình liên quan 8 1.2.1 Các độ đo tương tự. 8 1.2.2 Thu giảm số chiều chuỗi TSD 10 1.2.3. Các cấu trúc chỉ mục 15 Chương 2. Phương pháp đề xuất 22 2.1 Thu giảm số chiều dựa vào kỹ thuật IPIP 22 2.2 Độ phức tạp của giải thuật thu giảm số chiều IPIP 26 2.3. Cấu trúc chỉ mục Skyline cho phương pháp IPIP 27 2.3.1 Vùng bao IPIP 27 2.3.2. Hàm tính khoảng cách cho IBR 28 2.3.3 Cấu trúc chỉ mục Skyline cho phương pháp biểu diễn IPIP 29 2.4 Xử lý các câu truy vấn có chiều dài khác nhau 31 2.4.1 Xử lý câu truy vấn có chiều dài nhỏ hơn n 31 2.4.2 Xử lý câu truy vấn có chiều dài lớn hơn n 32 2.5. Chi tiết kỹ thuật của các chức năng 33 2.5.1 Qui trình thực hiện tìm kiếm tương tự 33 2.5.2. Chuẩn hóa dữ liệu 34 2.5.3. Xác định các điểm PIP 34 2.5.4. Xây dựng SB-tree 34 Chương 3. Kết quả thực nghiệm 36 3.1 Phương pháp luận thực nghiệm 36 3.2 Thực nghiệm về độ chặt của chặn dưới (Tightness of lower bound) . 37 3.3 Thực nghiệm về tỉ lệ thu giảm truy xuất (pruning power) 40 3.4 Thực nghiệm về hệ thống hiện thực (implemented system) 41 Kết luận và hướng phát triển 45 Tài liệu tham khảo 46 1
4. DANH MỤC CÁC HÌNH ẢNH Hình 1.1. Minh họa 2 TSD giống nhau nhưng (a) đường cơ bản khác nhau và (b) biên độ giao động khác nhau. Hình 1.2. Khoảng cách giữa hai đường biểu diễn. (a) tính theo độ đo Euclid và (b) tính theo độ đo DTW Hình 1.3. Minh họa cách tính khoảng cách theo DTW. Hình 1.4. Minh họa phương pháp DFT Hình 1.5. Minh họa phương pháp DWT Hình1.6. Minh họa phương pháp PAA Hình 1.7. Một xấp xỉ từ 12 điểm mốc của một chuỗi TSD Hình 1.8. Cực tiểu quan trọng (trái) và cực đại quan trọng (phải) Hình 1.9. (a). Minh họa khoảng cách thẳng đứng, (b). Quá trình xác định 5 điểm PIP trong TSD. Hình 1.10. Minh họa R-tree Hình1.1 Một ví dụ về trường hợp xấu khi tìm kiếm. Hình 1.12. Lưu đồ minh họa giải thuật thêm phần tử mới vào cây Hình 1.13. Minh họa thêm thành phần X vào cây. (a) Cấu trúc R*-tree. (b) Minh họa hình chữ nhật bao nhỏ nhất. Hình1.14. Minh họa các trường hợp MBR có phủ lấp và không phủ lấp Hình 1.15. Minh họa SBR và SBR xấp xỉ của ba chuỗi TSD Hình 2.1. Minh họa kỹ thuật IPIP Hình 2.2. Ví dụ minh họa về IBR. (a) Hai chuỗi TSD C1, C2 và biểu diễn IPIP của chúng. (b) IBR của hai chuỗi IPIP C’1 và C’2. Hình 2.3. Giải thuật xác định k PIP trong một đoạn. Hình 2.4. Giải thuật tạo SB-tree. Hình 3.1. Kết quả thực nghiệm về độ chặt chặn dưới của kỹ thuật IPIP so với PIP. (a) So trùng chuỗi con. (b) So trùng toàn chuỗi. Hình từ 3.2 đến 3.6. Kết quả thực nghiệm về độ chặt của chặn dưới của trường hợp so trùng toàn bộ chuỗi. Hình từ 3.7 đến 3.11. Kết quả thực nghiệm về độ chặt của chặn dưới của trường hợp so trùng toàn chuỗi con. Hình 3.12. Kết quả thực nghiệm về tỉ lệ thu giảm truy xuất theo tỉ lệ thu giảm khác nhau. Hình 3.13. Kết quả thực nghiệm về chi phí CPU chuẩn hóa của (a). so trùng toàn chuỗi. (b). so trùng chuỗi con. Hình 3.14. Kết quả thực nghiệm về chi phí CPU chuẩn hóa theo kích thước dữ liệu (so trùng toàn chuỗi). 2
5. Hình 3.15. Kết quả thực nghiệm về chi phí CPU chuẩn hóa theo kích thước dữ liệu của phương pháp IPIP. Hình 3.16. Kết quả thực nghiệm về chi phí CPU chuẩn hóa theo kích thước dữ liệu (so trùng chuỗi con). Hình 3.17. Thời gian xây dựng chỉ mục với các tỉ lệ thu giảm khác nhau và số chuỗi thực nghiệm là 10000 3
6. PHẦN MỞ ĐẦU 6. Tình hình nghiên cứu trong và ngoài nước Bài toán tìm kiếm tương tự trong cơ sở dữ liệu chuỗi thời gian (Time Series Data - TSD) đã được nhiều nhà nghiên cứu quan tâm trong những năm qua. Nhiều kỹ thuật thu giảm số chiều TSD đã được giới thiệu. Trong số đó có các kỹ thuật như biến đổi Fourier rời rạc (Discrete Fourier Transforms - DFT) [1], biến đổi Wavelet rời rạc (Discrete Wavelet Transforms - DWT) [5], xấp xỉ gộp từng đoạn (Piecewise Aggregate Approximation - PAA) [14], xấp xỉ hằng số từng đoạn thích nghi (Adaptive Piecewise Constant Approximations - APCA) [15]. Cũng đã có một số nghiên cứu về kỹ thuật thu giảm số chiều dựa vào các điểm quan trọng như kỹ thuật thu giảm số chiều dựa vào các điểm mốc (landmark points) của Perng và các cộng sự, 2000 [17], kỹ thuật thu giảm số chiều dựa vào các điểm quan trọng (Important points) của Pratt và các cộng sự, 2003 [7], kỹ thuật thu giảm số chiều dựa vào các PIP (Perceptually Important Points) của Fu và Chung, 2001 [6]. Các kỹ thuật này có ưu điểm là (1) có thể cung cấp một biểu diễn xấp xỉ đa mức phân giải, (2) có thể thực hiện so sánh tương tự các chuỗi dữ liệu chuỗi thời gian có chiều dài khác nhau. Ngoài ra, qua thực nghiệm các tác giả của các phương pháp pháp thu giảm số chiều dựa vào các điểm quan trọng đã cho thấy chúng thực thi hiệu quả. Qua nghiên cứu ban đầu của chúng tôi về ba phương pháp dựa vào điểm quan trọng này, PIP là phương pháp hiệu quả và dễ cài đặt nhất. Tuy nhiên, Cả ba phương pháp trên vẫn chưa được chứng minh về mặt lý thuyết là chúng tuân theo điều kiện chặn dưới nhằm đảm bảo không xảy ra lỗi tìm sót (false dismissal). Việc không tuân theo điều kiện chặn dưới gây khó khăn cho sự so sánh các phương pháp điểm quan trọng với các phương pháp thu giảm số chiều khác như PAA, APCA. Ngoài ra chúng cũng không có cấu trúc chỉ mục hỗ trợ lập chỉ mục cho việc tìm kiếm tương tự. Điều này làm giảm hiệu quả của việc tìm kiếm tương tự trên cơ sở dữ liệu chuỗi thời gian lớn. 7. Tính cấp thiết của đề tài Dữ liệu chuỗi thời gian là loại dữ liệu được sử dụng phổ biến trong các lĩnh vực khoa học, công nghệ, y học và thương mại. Chẳng hạn, trong y khoa người ta có thể sử dụng các bài toán về time series để xây dựng chương trình dò tìm tự động trên điện não đồ của bệnh nhân để phát hiện bệnh, hoặc trong lĩnh vực chứng khoán ta có thể ứng dụng các bài toán về time series để xây dựng chương trình dự báo xu thế biến động của chứng khoán trong thời gian sắp tới, 4
7. v.v . Thời gian qua, đã và đang có nhiều quan tâm của các nhà nghiên cứu về bài toán tìm kiếm tương tự (similarity search) trong cơ sở dữ liệu chuỗi thời gian. Bài toán này là một thành phần quan trọng trong nhiều ứng dụng khai phá dữ liệu (data mining) như gom cụm (clustering), phân lớp (classification), phát hiện motif (discovering motif), . 8. Ý nghĩa lý luận và thực tiễn 3.1 Ý nghĩa lý luận Nghiên cứu đề xuất một phương pháp thu giảm số chiều mới nhằm khắc phục nhược điểm của các phương pháp thu giảm số chiều dựa vào điểm quan trọng đã có. Đồng thời đề xuất một cấu trúc chỉ mục hỗ trợ thực hiện bài toán tìm kiếm tương tự trong cơ sở dữ liệu chuỗi thời gian một cách hiệu quả. 3.2 Ý nghĩa thực tiễn Nghiên cứu này sẽ là nền tảng cho những nghiên cứu tiếp theo về các bài toán khác trong khai phá dữ liệu chuỗi thời gian như gom cụm, phân lớp, phát hiện bất thường, tìm kiếm motif, v.v . Từ đó có thể áp dụng cho các ứng dụng cụ thể về chẩn đoán, phân tích, dự báo trong nhiều lĩnh vực khác nhau như chẩn đoán bệnh trong y khoa, dự báo về thị trường chứng khoán, phân tich lưu lượng giao thông, . Ngoài ra, còn có thể áp dụng giảng dạy như một chuyên đề cho sinh viên sau đại học. 9. Các đối tượng nghiên cứu Cơ sở dữ liệu chuỗi thời gian và các kết quả nghiên cứu đã công bố về tìm kiếm tương tự trong cơ sở dữ liệu chuỗi thời gian. 10. Phạm vi và các phương pháp nghiên cứu 10.1 Phạm vi nghiên cứu Phương pháp thu giảm số chiều dữ liệu chuỗi thời gian. Cấu trúc chỉ mục đa chiều sử dụng cho bài toán tìm kiếm tương tự. 10.2 Các phương pháp nghiên cứu Tổng kết các kết quả nghiên cứu liên quan trước đây. Đánh giá hiệu quả của các phương pháp. Thực nghiệm để kiểm tra kết quả. Nghiên cứu tài liệu, ứng dụng mô hình lý thuyết và chứng minh bằng thực nghiệm 5
8. PHẦN NỘI DUNG Chương 1. Các kiến thức cơ sở 1.1 Tổng quan về dữ liệu chuỗi thời gian và bài toán tìm kiếm tương tự Một dữ liệu chuỗi thời gian (Time Series Data - TSD) là một dãy số thực, mỗi số biểu diễn một giá trị tại một thời điểm. Loại dữ liệu này được sử dụng phổ biến trong các lĩnh vực khoa học, công nghệ và thương mại. Thời gian qua, đã và đang có nhiều quan tâm của các nhà nghiên cứu về bài toán tìm kiếm tương tự (similarity search) trong cơ sở dữ liệu chuỗi thời gian. Bài toán này là một thành phần quan trọng trong nhiều ứng dụng khai phá dữ liệu (data mining) như gom cụm (clustering) [12][13], phân lớp (classification) [10]. Bài toán tìm kiếm tương tự được phân làm 2 loại: so trùng toàn bộ chuỗi (whole sequence matching) và so trùng chuỗi con (subsequence matching). Khi so trùng toàn bộ chuỗi, các chuỗi TSD được giả định là có chiều dài bằng nhau, còn trong so trùng chuỗi con ta tìm chuỗi con liên tục trong TSD dài hơn tương tự nhất với chuỗi truy vấn. Độ tương tự giữa 2 chuỗi TSD có thể được tính toán dựa vào một độ đo tương tự. Có nhiều độ đo tương tự các chuỗi TSD đã được đề nghị, trong đó có 2 độ đo được quan tâm sử dụng là độ đo Euclid và độ đo xoắn thời gian động (DTW-Dynamic Time Warping). Những khó khăn và thách thức khi nghiên cứu về TSD: 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 TSD 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. Do giới hạn về bộ nhớ máy tính và thời gian thực hiện, việc phân tích đúng trên các tập dữ liệu chuỗi thời gian rất lớn là điều không thể. Vì vậy, một trong những vấn đề trọng tâm của công việc khai phá dữ liệu chuỗi thời gian là làm sao giảm số chiều của chuỗi dữ liệu nhưng vẫn giữ được các tính chất đặc trưng của chúng. Trong những năm qua, nhiều kỹ thuật thu giảm số chiều TSD đã được giới thiệu. Phần tiếp theo sẽ trình bày tổng quan về các công trình nay. 6
9. 1.2. Các công trình liên quan Bài toán tìm kiếm tương tự trong cơ sở dữ liệu chuỗi thời gian đã và đang được nghiên cứu trong cộng đồng các nhà nghiên cứu về TSD. Các nghiên cứu tập trung vào các kỹ thuật thu giảm số chiều chuỗi dữ liệu thời gian và lập chỉ mục các chuỗi dữ liệu trên không gian đã thu giảm số chiều. Trong phần này, chúng tôi sẽ trình bày tổng quan về một số kỹ thuật thu giảm số chiều, cùng với các độ đo tương tự thường được sử dụng trong bài toán tìm kiếm và các kỹ thuật lập chỉ mục liên quan. 1.2.1 Các độ đo tương tự. Trong các bài toán về TSD, để so sánh hai chuỗi người ta sử dụng các độ đo tương tự. Hai đối tượng được xem là giống nhau khi độ đo tương tự giữa chúng bằng 0, được xem là tương tự nếu độ đo tương tự giữa chúng nhỏ hơn một giá trị  được qui ước trước đó. Để có thể tính toán và so sánh, độ đo này được biểu diễn thành các số thực và phải thỏa các tính chất sau: - D(x,y) = 0 nếu và chỉ nếu x = y - D(x, y) = D(y, x) - D(x, y) 0 với mọi x, y - D(x, y) < D(x, z) + D(y, z) Dưới đây là các độ đo thường được sử dụng: Độ đo Minkowski Ký hiệu là Sim(X,Y) (độ tương tự giữa X và Y) và được định nghĩa như sau: Tuy p có thể có nhiều sự lựa chọn khác nhau, nhưng trong các nghiên cứu đối với dữ liệu chuỗi thời gian thì thường sử dụng p = 2 (khoảng cách Euclid). Độ đo này có ưu điểm tính toán dễ dàng. Tuy nhiên nó cũng có một số nhược điểm là do phương pháp này tính toán dựa trên giá trị nên đối với các trường hợp tính chất của hai mẫu là giống nhau nhưng giá trị khác nhau (có đường căn bản khác nhau hay có biên độ dao động khác nhau) thì khoảng cách hai mẫu sẽ rất khác nhau. Hình 1.1 minh họa trường hợp này. 7