CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI Thông tin luôn là điều sống còn của xã hội, nhờ có thông tin mà chúng ta mới có được tri thức và kinh nghiệm. Tất cả những thứ thông tin rối rắm đó đều có thể biểu diễn ở một dạng cô đọng gọi là dữ liệu. Xã hội càng phát triển thì thông tin càng phức tạp và dữ liệu càng phức tạp. Có một điều hiển nhiên là dữ liệu không phải bất biến mà luôn luôn thay đổi theo thời gian.
Trong cuộc sống chúng ta gặp vô vàn những loại dữ liệu thay đổi theo thời gian như thế trong hầu hết các lĩnh vực của cuộc sống như các dữ liệu kinh tế, tài chính (tỷ giá ngoại tệ, chứng khoán,…), các dữ liệu y học (EEG, ECG,…), các dữ liệu thủy văn (mực nước biển, lượng mưa,…). Các dữ liệu trên gọi chung là dữ liệu chuỗi thời gian (time series), dữ liệu chuỗi thời gian biến đổi liên tục, sản sinh ra một khối lượng dữ liệu khổng lồ thay đổi theo thời gian. Và câu hỏi lớn nhất mà các nhà khoa học đặt ra trong thời gian qua là làm thế nào để quản lý dữ liệu đó một cách hiệu quả nhất nhằm phục vụ tốt nhất nhu cầu của cuộc sống. Tổng quan về dữ liệu chuỗi thời gian 1.
Giới thiệu dữ liệu chuỗi thời gian Một chuỗi thời gian (time series) là một chuỗi trị số thực, mỗi trị biểu diễn một giá trị đo được tại những thời điểm cách đều nhau. Theo khảo sát của Tufte tiến hành năm 1992 thì có đến 75% trong số bốn nghìn bức ảnh ngẫu nhiên trên các tạp chí xuất bản giai đoạn 1974 - 1989 là các hình biểu diễn dữ liệu chuỗi thời gian. Những tập dữ liệu chuỗi thời gian thường rất lớn, xuất hiện trong nhiều lĩnh vực như y tế, kỹ thuật, tài chính,… - Lĩnh vực tài chính, thương mại như giá cả, thị trường chứng khoán, sản phẩm…. + Tìm trong quá khứ, những giai đoạn mà số lượng sản phẩm bán được như tháng vừa rồi.
+ Tìm những sản phẩm có chu kỳ bán hàng giống nhau. + Tìm đoạn nhạc bản quyền trong một bài hát. Nguyễn An Hồ Hưng - 09070439 Trang 1 Khảo sát sự hiệu quả của cấu trúc chỉ mục Skyline trong dữ liệu chuỗi thời gian - Lĩnh vực khoa học như dữ liệu thu được của các bộ cảm biến thời tiết, môi trường, địa lý, … + Tìm những tháng trong quá khứ mà lượng mưa giống như tháng vừa rồi. + Tìm những năm khô hạn, mực nước các sông ở mức thấp.
Các lĩnh vực khác có dữ liệu không phải là chuỗi thời gian nhưng từ dữ liệu này ta có thể chuyển về dạng dữ liệu chuỗi thời gian. Các bài toán nhận dạng chữ viết hay các bài toán trong lĩnh vực xử lý ảnh được chuyển thành các bài toán về xử lý dữ liệu chuỗi thời gian.1 minh họa chuỗi thời gian, hình (a) là biểu diễn chuỗi thời gian của dữ liệu chứng khoán và hình (b) là biểu diễn chuỗi thời gian của dữ liệu điện tâm đồ.1- Dữ liệu chuỗi thời gian. (a) dữ liệu chứng khoán. Keogh, khi nghiên cứu chuỗi thời gian chúng ta sẽ gặp các vấn đề khó khăn sau [26], [27]: - Dữ liệu chuỗi thời gian quá lớn do nhu cầu lưu trữ dữ liệu qua một khoảng thời gian dài để phân tích, đánh giá [25].
+ Trong một giờ, dữ liệu điện tâm đồ (ECG) là 1GB. + Trong một tuần, dữ liệu ghi nhận số lần truy cập website là 5GB. - Việc đánh giá độ tương tự phụ thuộc phần lớn vào con người, và tính chất của tập dữ liệu đang dùng. - Dữ liệu quá đa dạng và dễ bị nhiễu.
Nguyễn An Hồ Hưng - 09070439 Trang 2 Khảo sát sự hiệu quả của cấu trúc chỉ mục Skyline trong dữ liệu chuỗi thời gian Thao tác tìm kiếm tương tự (similarity search) là thao tác căn bản nhất để khai phá dữ liệu chuỗi thời gian (Data Mining in Time Series). Các bài toán của dữ liệu 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à dữ liệu 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) 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ự trong cơ sở dữ liệu chuỗi thời gian là một hướng nghiên cứu quan trọng và được nhiều nhà nghiên cứu quan tâm.
Bài toán tìm kiếm tương tự là thao tác căn bản nhất, là thành phần không thể thiếu trong các bài toán khai phá dữ liệu chuỗi thời gian. Nhiều phương pháp đã được đề xuất để cung cấp những giải thuật xử lý truy vấn hiệu quả trên dữ liệu chuỗi thời gian. Có một số nhóm các bài toán khai phá dữ liệu chuỗi thời gian như dưới đây [5]. - Bài toán gom cụm (Clustering).
- Bài toán phân lớp (Classification). - Bài toán tìm mô típ (Finding motif) [11]. - Bài toán phát hiện mẫu bất thường (Anomaly Detection). - Bài toán khám phá luật kết hợp (Association Rules).
- Bài toán trực quan hóa dữ liệu (Visualization). So trùng toàn bộ và so trùng chuỗi con trên dữ liệu chuỗi thời gian Trong bài toán tìm kiếm tương tự, có hai loại thao tác cơ bản nhất để truy vấn trên dữ liệu chuỗi thời gian, đó là so trùng toàn bộ (whole matching) và so trùng chuỗi con (subsequence matching) [5], [11], [17], [22], [32]. - So trùng toàn bộ (whole matching): Đối với những truy vấn so trùng toàn bộ thì 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. 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 nào thay đổi giống nhau. Nguyễn An Hồ Hưng - 09070439 Trang 3 Khảo sát sự hiệu quả của cấu trúc chỉ mục Skyline trong dữ liệu chuỗi thời gian Hình 1.2 ở dưới minh họa việc so trùng toàn bộ trong chuỗi thời gian, trong đó câu truy vấn và các đối tượng trong cơ sở dữ liệu có chiều dài bằng nhau.2- So trùng toàn bộ (nguồn [22]) - So trùng chuỗi con (subsequence matching): Trong trường hợp so trùng chuỗi con thì 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. 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.3 minh họa việc so trùng chuỗi con trong chuỗi thời gian, trong đó câu truy vấn có chiều dài nhỏ hơn nhiều so với đối tượng trong cơ sở dữ liệu.3- So trùng chuỗi con (nguồn [22]) Bài toán so trùng chuỗi con là bài toán rất căn bản của lĩnh vực nghiên cứu về dữ liệu chuỗi thời gian.
Từ bài toán so trùng chuỗi con trên dữ liệu chuỗi thời gian thì ta có thể mở rộng thành so trùng toàn bộ. Một số bài toán khác cũng sử dụng kết quả dựa trên bài toán so trùng chuỗi con như bài toán gom cụm (clustering), phân Nguyễn An Hồ Hưng - 09070439 Trang 4 Khảo sát sự hiệu quả của cấu trúc chỉ mục Skyline trong dữ liệu chuỗi thời gian lớp (classification), tìm quy luật của dữ liệu (rule discovery), phát hiện điểm bất thường (novelty detection), dự báo dữ liệu trong tương lai (prediction). Các dạng truy vấn tương tự trên dữ liệu chuỗi thời gian Định nghĩa truy vấn tương tự (similarity search): Cho trước một đối tượng truy vấn Q, tìm tất cả các đối tượng Qx, trong cơ sở dữ liệu tương tự với Q ở một mức nào đó. Truy vấn tương tự đã được nghiên cứu để áp dụng cho các đối tượng đa chiều, chuỗi thời gian và một số loại dữ liệu khác.
Có 3 loại truy vấn tương tự được sử dụng rộng rãi trong những công trình nghiên cứu và trong các tài liệu: - Truy vấn tương tự vùng (similarity range query): cho trước một đối tượng truy vấn q, một tập các đối tượng A và khoảng cách e, tìm ra tất cả các đối tượng a ϵ A sao cho dist(q, a) ≤ e. - Truy vấn tương tự k-láng-giềng-gần-nhất (similarity k-nearest neighbors): cho trước một đối tượng truy vấn q, một tập các đối tượng A và một số nguyên k, tìm tất cả k đối tượng ai ϵ A (1 ≤ i ≤ | A |) sao cho với bất kỳ đối tượng aj ϵ A (1 ≤ j ≤ |A| và j≠i) thì dist(q, ai) ≤ dist(q, aj). - Truy vấn tương tự kết nối (similarity join query): cho hai tập đối tượng A , B và khoảng cách e, tìm tất cả các cặp (a, b) với a ϵ A và b ϵ B sao cho dist(a, b) ≤ e. Bài toán tìm kiếm tương tự có thể được áp dụng so trùng toàn bộ hay 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.
Vấn đề của truy vấn tương tự trên dữ liệu chuỗi thời gian Chi phí của tìm kiếm tương tự quá lớn nếu như phải so sánh và tính toán độ tương tự giữa câu truy vấn và toàn bộ chuỗi thời gian trong cơ sở dữ liệu. Do đó cần phải có cấu trúc chỉ mục lưu trữ hợp lý để chỉ truy vấn những chuỗi thời gian có liên quan đến câu truy vấn mà không cần phải truy vấn vét cạn cơ sở dữ liệu [5]. Theo phương pháp truyền thống thì dữ liệu chuỗi thời gian có chiều dài l (l điểm) thì có thể ánh xạ qua thành một véc tơ l chiều và dùng một phương pháp đánh chỉ Nguyễn An Hồ Hưng - 09070439 Trang 5 Khảo sát sự hiệu quả của cấu trúc chỉ mục Skyline trong dữ liệu chuỗi thời gian mục không gian như R-Tree [7], [19] để đánh chỉ mục chúng. Như vậy, trong suy nghĩ của chúng ta, chỉ cần đem một tập các chuỗi thời gian đi đánh chỉ mục cho chúng để việc thực hiện tìm kiếm tương tự đơn giản hơn.
Tuy nhiên, có một vấn đề phức tạp ở đây là dữ liệu của một chuỗi thời gian thường gồm khá nhiều điểm nên chiều dài của chuỗi là rất lớn, nên khi ánh xạ qua véc tơ nhiều chiều thì số chiều của véc tơ rất lớn, vì vậy áp dụng một phương pháp truyền thống xem ra không hiệu quả. Theo phân tích ở trên, chúng ta dễ dàng nhận thấy rằng với dữ liệu chuỗi thời gian, yêu cầu tối ưu về mặt lưu trữ và truy đạt là những vấn đề quan trọng nhất.
