CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI Chương giới thiệu đề tài này sẽ trình bày nội dung sơ lược và mục tiêu của đề tài. Đồng thời chương này cũng nêu lên những động cơ trong nghiên cứu và trong thực tiễn đòi hỏi cần phải thực hiện đề tài này.1 Dữ liệu chuỗi thời gian Chuỗi thời gian (time series) là dữ liệu có yếu tố thời gian được quan sát tuần tự theo thời gian. Dữ liệu này có thể có nhiều hơn hai chiều nhưng trong đó bắt buộc phải có một chiều là thời gian. Có rất nhiều loại dữ liệu khác nhau có yếu tố thời gian và thông thường đây là những dữ liệu rất lớn.
Những tập dữ liệu chuỗi thời gian rất lớn xuất hiện trong nhiều lãnh vực khác nhau như y khoa, kỹ thuật, kinh tế, tài chính, … Hình 1-1: Ví dụ về dữ liệu chuỗi thời gian (dữ liệu chứng khoán) (Nguồn [19]) E. Keogh đã nêu lên những khó khăn và thách thức khi nghiên cứu dữ liệu chuỗi thời gian [11] như sau: Nguyễn Trường Mạnh Hùng 1 Tìm kiếm tương tự trên chuỗi thời gian dạng luồng • Dữ liệu quá lớn o Dữ liệu điện tâm đồ khoảng 1 Gigabyte/giờ, dữ liệu ghi nhận các lần truy cập của một website khoảng 5 Gigabytes/tuần. • Phụ thuộc nhiều vào cách đánh giá độ tương tự o Độ tương tự được định nghĩa tùy thuộc vào người dùng, tập dữ liệu, miền bài toán … • Dữ liệu thường không đồng nhất o Định dạng dữ liệu khác nhau, tần số lấy mẫu khác nhau, bị nhiễu, thiếu giá trị, dữ liệu không sạch … 1.2 Dữ liệu chuỗi thời gian dạng luồng M. Kontaki và các cộng sự đã phân loại chuỗi thời gian thành 2 loại là chuỗi thời gian tĩnh (static time series) và chuỗi thời gian dạng luồng (streaming time series) [19].
Chuỗi thời gian tĩnh là chuỗi thời gian bao gồm một số lượng hữu hạn các giá trị mẫu. Còn đối với chuỗi thời gian dạng luồng kích thước bài toán tăng lên rất nhiều vì giá trị mới được cập nhật liên tục. Tùy theo nhu cầu mà chúng ta có thể tiếp cận một chuỗi thời gian như là chuỗi thời gian tĩnh hay chuỗi thời gian dạng luồng. Trong ví dụ Hình 1-1 (a), nếu dữ liệu tương ứng với giá cổ phiếu trong năm 2004, thì chúng ta có thể xem đây là chuỗi thời gian tĩnh.
Nhưng nếu chúng ta có nhu cầu theo dõi giá chứng khoán liên tục theo thời gian thì đây chính là chuỗi thời gian dạng luồng. Chuỗi thời gian dạng luồng là một trường hợp đặc biệt của dữ liệu dạng luồng (stream data). Ngày nay, một số lượng lớn ứng dụng đòi hỏi phải thao tác với dữ liệu dạng luồng [2], [6], [7], [25], [26], [27], [31]. Đặc trưng của dữ liệu dạng luồng là khối lượng dữ liệu lớn thậm chí có thể là vô tận, thay đổi nhanh chóng đòi hỏi Nguyễn Trường Mạnh Hùng 2 Tìm kiếm tương tự trên chuỗi thời gian dạng luồng đáp ứng nhanh, thời gian thực và truy xuất ngẫu nhiên là rất tốn kém.
Kamber đã tổng hợp các phương pháp xử lý dữ liệu dạng luồng như sau [9]: Lấy mẫu ngẫu nhiên (Random sampling), Biểu đồ tần số (Histograms), Cửa sổ trượt (Sliding windows), Mô hình đa phân giải (Multi-resolution model), Bản tóm tắt (Sketches), Thuật toán ngẫu nhiên (Randomized algorithms). Một loạt các giải thuật xử lý chuỗi thời gian dạng luồng tập trung vào quá khứ gần nhất của chuỗi thời gian dạng luồng bằng cách áp dụng cửa sổ trượt (sliding windows) đã được đề xuất [7], [17], [26], [27], [31].3 Bài toán tìm kiếm tương tự trên chuỗi thời gian Khác với cơ sở dữ liệu truyền thống, cơ sở dữ liệu chuỗi thời gian có thể chứa dữ liệu bị nhiễu và sai. Do đó khả năng tồn tại hai chuỗi thời gian có cùng giá trị trong cùng thời điểm là rất nhỏ. Vì vậy, tìm kiếm tương tự (similarity search) là thích hợp hơn so với tìm kiếm chính xác (exact search).
Tìm kiếm tương tự (similarity search) trong cơ sở dữ liệu chuỗi thời gian là một hướng nghiên cứu quan trọng. Một số phương pháp đã được đề xuất để cung cấp những giải thuật xử lý truy vấn hiệu quả trong trường hợp của chuỗi thời gian tĩnh và chuỗi thời gian dạng luồng. Các yêu cầu truy vấn trên dữ liệu chuỗi thời gian có thể chia làm 2 loại: • So trùng toàn bộ (whole matching): Chiều dài của chuỗi dữ liệu truy vấn và chiều dài chuỗi dữ liệu ban đầu là bằng nhau. Minh họa truy vấn so trùng toàn bộ được thể hiện trong Hình 1-2.
Bài toán này thường được dùng trong việc gom cụm, hay phân loại dữ liệu chuỗi thời gian. Ví dụ, tìm giá chứng khoán của những công ty thay đổi giống nhau. Nguyễn Trường Mạnh Hùng 3 Tìm kiếm tương tự trên chuỗi thời gian dạng luồng Hình 1-2 Truy vấn so trùng toàn bộ • So trùng chuỗi con (subsequence matching): Chiều dài của dữ liệu truy vấn ngắn hơn rất nhiều so với chiều dài của dữ liệu ban đầu. Vì vậy, nhiệm vụ chính là tìm những đoạn trong dữ liệu ban đầu tương tự với dữ liệu truy vấn.
Minh họa truy vấn so trùng toàn bộ được thể hiện trong Hình 1-3. Một số ứng dụng của bài toán này là tìm những mẫu dữ liệu quan trọng hay những thay đổi bất thường trong dữ liệu ban đầu. Hình 1-3 Truy vấn so trùng chuỗi con M. Kontaki và các cộng sự đã tổng kết được 3 loại truy vấn tương tự được sử dụng trong các công trình nghiên cứu [17], được định nghĩa như sau: • Truy vấn tương tự vùng (similarity range query): cho đối tượng truy vấn Q, tập các đối tượng A và khoảng cách e, lấy tất cả các đối tượng a ∈ A sao cho dist(q, a) ≤ e.
Nguyễn Trường Mạnh Hùng 4 Tìm kiếm tương tự trên chuỗi thời gian dạng luồng • Truy vấn tương tự k-lân-cận-gần-nhất (similarity k-nearest neighbors query): cho đối tượng truy vấn Q, tập các đối tượng A và giá trị nguyên k, lấy k đối tượng cơ sở dữ liệu ai ∈ A (1 ≤ i ≤ |A|) sao cho với bất kỳ aj ∈ A (1 ≤ j ≤ |A| và j ≠ i) dist(q, ai) ≤ dist(q, aj). • Truy vấn tương tự ghép nối (similarity join query): cho 2 tập các đối tượng A và B và khoảng cách e lấy các cặp (a, b) với a∈A và b∈B sao cho dist(a,b) ≤ e. Rõ ràng từ 3 loại truy vấn tương tự nêu trên, để thể hiện sự tương tự giữa 2 chuỗi thời gian, cần phải dựa trên độ đo khoảng cách. Bài toán tìm kiếm tương tự có thể được áp dụng so trùng toàn bộ cũng như so trùng chuỗi con và có thể áp dụng trên chuỗi thời gian tĩnh hoặc chuỗi thời gian dạng luồng.4 Mục tiêu và giới hạn của đề tài Đề tài này dựa vào phương pháp tìm kiếm tương tự thích nghi trên chuỗi thời gian dạng luồng do M.
Kontaki và các cộng sự đề xuất năm 2007 [17]. Mục tiêu chính của đề tài là mở rộng framework tìm kiếm tương tự trên dữ liệu chuỗi thời gian dạng luồng mà M. Kontaki đã đề xuất bằng cách thay thế phương pháp thu giảm số chiều và cấu trúc chỉ mục. Đề tài sẽ tiếp cận với phương pháp xấp xỉ gộp từng đoạn PAA và tận dụng các ưu điểm của cấu trúc chỉ mục Skyline giới thiệu bởi Q.
Li và các cộng sự năm 2004 [23]. Cũng giống như công trình [17], đề tài chỉ khảo sát trên 2 dạng truy vấn tương tự là truy vấn tương tự vùng và truy vấn tương tự lân cận gần nhất. Các thông số đánh giá hiệu suất có thể được khảo sát bao gồm: thời gian CPU (CPU time), số truy cập đĩa (disk access), thời gian tạo cấu trúc chỉ mục (index building time), thời gian đáp ứng truy vấn (query response time), số lượng đoạn thu giảm (number of segments).5 Cấu trúc luận văn Tổ chức của phần còn lại của luận văn theo cấu trúc như sau: Nguyễn Trường Mạnh Hùng 5 Tìm kiếm tương tự trên chuỗi thời gian dạng luồng • Chương 2 trình bày tổng quan về các công trình liên quan đến bài toán tìm kiếm tương tự trên chuỗi dữ liệu thời gian. Những công trình này nhằm cải tiến quá trình tìm kiếm tương tự và các công trình nghiên cứu này có thể chia làm 4 nhóm sau: nhóm các công trình nghiên cứu về độ tương tự, nhóm các công trình về thu giảm số chiều, nhóm các công trình về xây dựng cấu trúc chỉ mục và nhóm các công trình về tìm kiếm tương tự trên chuỗi thời gian dạng luồng.
• Chương 3 giới thiệu những lý thuyết mà sẽ được sử dụng để thực hiện đề tài, đồng thời xác định rõ hướng tiếp cận của đề tài. Trong phần này chúng tôi sẽ trình bày kỹ về framework đã được để xuất bao gồm phép biến đổi Fourier rời rạc cùng với cách tính toán gia tăng cho phép biến đổi này và cấu trúc chỉ mục IDC-Index dựa trên R*-Tree. Sau đó cấu trúc chỉ mục Skyline và phương pháp xấp xỉ gộp từng đoạn sẽ được trình bày. • Chương 4 trình bày nội dung nghiên cứu.
• Chương 5 trình bày về một số kết quả thực nghiệm. • Chương 6 trình bày kết luận và hướng mở rộng của đề tài Nguyễn Trường Mạnh Hùng 6 Tìm kiếm tương tự trên chuỗi thời gian dạng luồng CHƯƠNG 2: TỔNG HỢP CÁC CÔNG TRÌNH LIÊN QUAN Chương 2 sẽ tổng hợp các công trình về độ đo tương tự, các phương pháp thu giảm số chiều và các cấu trúc chỉ mục không gian.1 Các độ đo tương tự Vấn đề quan trọng nhất của bài toán tìm kiếm tương tự là cách tính khoảng cách của 2 đối tượng x, y bất kỳ trong tập dữ liệu. Trong trường hợp hai đối tượng này giống nhau thì khoảng cách này sẽ là 0 và ngược lại càng khác nhau thì khoảng cách càng lớn. Để có thể tính toán và so sánh thì cách khoảng cách này được biểu diễn thành các số thực.
Độ đo khoảng cách giữa các đối tượng nên thỏa các tính chất sau: 1) dist (x, y) = 0 ⇔ x = y 2) dist (x, y) = dist (y, x) 3) dist (x, y) ≥ 0 ∀x, y 4) dist (x, y) < dist (x, z) + dist (y, z) Trong các tính chất về độ đo tương tự, tính chất 1, 2 và 3 là trực quan dễ thấy. Tính chất 4 không phải là tính chất mang tính bắt buộc nhưng cần thiết cho kỹ thuật lập chỉ mục.
