CHƯƠNG 1 GIỚI THIỆU VỀ ĐỀ TÀI 1.1 Tổng quan về đề tài Chuỗi dữ liệu thời gian phát sinh trong nhiều ứng dụng về khoa học và kỹ thuật, tài chính, y học hay âm thanh kỹ thuật,. Motif trong chuỗi thời gian là các chuỗi con được lặp lại tương tự nhau một cách đơn lẻ hoặc trong nhiều tập hợp dữ liệu. Tìm kiếm các motif trên chuỗi dữ liệu thời gian là vấn đề có liên quan chặt chẽ và rất hữu ích trong nhiều lĩnh vực [3]. Vì vậy, gần đây việc nghiên cứu tìm kiếm motif trên dữ liệu chuỗi thời gian đang nhận được rất nhiều sự quan tâm trên khắp mọi nơi.
Thông thường kích thước của dữ liệu chuỗi thời gian rất lớn do đó trước khi thực hiện giải thuật phát hiện motif thì phải tiến hành thu giảm. Hiện nay, các nhà nghiên cứu cũng đang tập trung vào kỹ thuật khai thác motif trên dữ liệu chuỗi thời gian. Vì khi khám phá motif trên chuỗi thời gian thì sẽ biết được sự biến động của thị trường từ đó có thể đưa ra những phương hướng, chính sách phù hợp và đúng đắn trong tương lai. Biết được nhu cầu này, luận văn tiến hành nghiên cứu về vấn đề tìm kiếm các motif và xác định motif trên lượng dữ liệu lớn.
Sau đó, hiện thực dữ liệu đó trên giải thuật để đánh giá độ hiệu quả.2 Tổng quan các hướng tiếp cận Phương pháp chiếu ngẫu nhiên (Random Projection Algorithm - RP) [7] là giải thuật tìm kiếm motif phổ biến. Từ ý tưởng này luận văn trình bày về hai giải thuật đó là giải thuật Sequitur và Hashing. Hai giải thuật này phù hợp với những dữ liệu chuỗi thời gian có kích thước lớn. Tiến hành tạo dữ liệu xấp xỉ để cho tương khớp với bộ dữ liệu chính, nhưng vẫn phù hợp với các đặc trưng.
Từ dữ liệu thô (raw data) ban đầu sau khi thực hiện bước chuẩn hóa (normalization) sẽ tiếp tục thực hiện thu giảm số chiều (dimensionality reduction) và rời rạc hóa (discretization) về dạng chuỗi các ký tự. Sử dụng cửa sổ trượt (sliding window) có kích thước w (w do người dùng định nghĩa) trượt qua tất cả các ký tự trong chuỗi dữ liệu. Các chuỗi con sinh ra từ cửa sổ trượt gọi là các từ (word), mỗi từ được xem 4 như một đặc trưng (feature). Tìm thùng băm có kích thước lớn nhất, các phần tử của thùng băm này sẽ là ứng viên motif.
Thực hiện tìm motif thực sự từ ứng viên motif và ngưỡng khoảng cách tối đa ThresholdMax (ThresholdMax do người dùng định nghĩa) dựa trên hàm tính khoảng cách Euclid. Kết quả tìm được là motif xấp xỉ. Giải quyết bài toán tìm kiếm motif xấp xỉ. Thực hiện tìm kiếm motif từ các ứng viên dựa trên các hàm tính toán.
Từ đó, đưa ra được kết quả tìm kiếm tất cả motif và đánh giá kết quả.3 Khó khăn và thách thức Chiều dài của các motif vẫn do người nghiên cứu tự định nghĩa bằng các phương pháp phù hợp như phương thử,. Đối với các loại dữ liệu phân bố thưa thì giải thuật không được nhạy. Dữ liệu chuỗi thời gian thường rất lớn và không đồng nhất do khác nhau về định dạng hay tần số lấy mẫu. Chẳng hạn, trong một giờ, dữ liệu điện tâm đồ (Electrocardiogram viết tắt là 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 chuỗi thời gian.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ị. Từ khi được hình thức hóa vào năm 2002, phát hiện motif trên dữ liệu chuỗi thời gian đã và đang được dùng để giải quyết các bài toán trong nhiều lĩnh vực ứng dụng khác nhau ví dụ như dùng motif để kiểm tra chữ ký [2], dùng motif để phát hiện những hình ảnh lặp trong cơ sở dữ liệu hình dạng [3], dùng motif để dự báo giá chứng khoán [4] và cũng được dùng như bước tiền xử lý trong nhiều công việc khai thác dữ liệu cao cấp hơn, ví dụ như gom cụm chuỗi thời gian [5], phân lớp chuỗi thời gian [6]. Hiển nhiên, độ phức tạp của phương pháp phát hiện chính xác motif theo kiểu brute-force là bậc hai theo số chuỗi trong cơ sở dữ liệu chuỗi thời gian hay chiều dài 5 của chuỗi thời gian mà từ đó các chuỗi con được trích ra.
Vì lý do đó, có nhiều thuật toán phát hiện motif xấp xỉ đã được giới thiệu. Các cách tiếp cận này thường có độ phức tạp tính toán là O(n) hay O(nlogn), với n là số chuỗi trong cơ sở dữ liệu chuỗi thời gian hay chiều dài của chuỗi thời gian mà từ đó các chuỗi con được trích ra. Độ phức tạp của các giải thuật này giảm hơn so với phương pháp tìm kiếm chính xác. Tuy nhiên, chúng yêu cầu một số lượng lớn các tham số cần xác định trước.
Vì vậy, việc nghiên cứu đề xuất các thuật toán mới hoặc cải tiến các thuật toán đã có sao cho hiệu quả hơn vẫn luôn được các nhà nghiên cứu quan tâm thực hiện.4 Đề xuất hướng giải quyết Tối ưu thuật toán để chạy dữ liệu chuẩn xác và hiệu quả hơn. Tuy nhiên sẽ nghiên cứu trong tương lai cách tối ưu này. Ước lượng chính xác độ dài từng motif bằng phương pháp mang lại kết quả tốt nhất. 6 CHƯƠNG 2 CƠ SỞ LÝ THUYẾT 2.1 Dữ liệu chuỗi thời gian Motif chuỗi thời gian là những motiflặp đi lặp lại trong chuỗi thời gian dài và ồn ào.
Motifs thường được sử dụng để hiểu động lực của nguồn vì các mô hình lặp đi lặp lại với độ tương đồng cao rõ ràng loại trừ sự hiện diện của nhiễu. Gần đây, các motif chuỗi thời gian cũng đã được sử dụng để phân cụm, tóm tắt, khám phá quy tắc và nén dưới dạng các tính năng [1]. Các motif chuỗi thời gian thường gợi ý thông tin hữu ích về các mối liên hệ theo mùa hoặc thời gian giữa các sự kiện và việc phát hiện các mô hình như vậy có thể rất hữu ích trong thực tế.[10] Chuỗi thời gian được sử dụng trong một loạt các ứng dụng, mô hình hóa dữ liệu thay đổi theo thời gian. Ví dụ, thay đổi kho, tín hiệu âm thanh, tín hiệu địa chấn, điện tâm đồ, có thể được biểu diễn dưới dạng dữ liệu chuỗi thời gian.
[2] Ví dụ về chuỗi thời gian như hình 2.1 Minh họa về chuỗi thời gian thay đổi của kho và điện tâm đồ [2] 2.2 Khai thác motif trên dữ liệu chuỗi thời gian Motif của một chuỗi thời gian là một chuỗi con có tần suất xuất hiện cao nhất. Hiện nay, các bài toán về khai thác motif đang được các nhà khoa học nghiên cứu, phát triển và xây dựng các ứng dụng liên quan, đồng thời khai thác motif cũng liên quan tới các bài toán khác trong chuỗi thời gian nên có thể gọi nó là bài toán cơ bản. 7 Có nhiều bài toán đã ứng dụng khai thác motif như: tìm hiểu thói quen của khách hàng, tìm các mặt hàng có chu kỳ doanh số giống nhau, phát hiện vi phạm bản quyền trong các bản nhạc, tìm những tháng trong quá khứ có lượng mưa giống như tháng vừa rồi, phát hiện đạo văn,. Phát hiện motif là tìm những 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 như hình 2.2 Ví dụ về một motif của dữ liệu chuỗi thời gian [3] Hiện nay, các nhà khoa học trên thế giới đã và đang đi sâu vào phân tích và khai thác dữ liệu chuỗi thời gian.
Từ nền tảng kiến thức đó đã xây dựng ra nhiều ứng dụng trong các lĩnh vực về tài chính, kinh tế, công nghệ. Dữ liệu chuỗi thời gian được sử dụng phổ biến trong các lĩnh vực khoa học, công nghệ, tài chính, thương mại, y học, thời tiết, môi trường, địa lý.1 Cửa số trượt (Sliding Window) Cho một dữ liệu chuỗi thời gian T có chiều dài n, để xác định được chuỗi con có chiều dài m, ta dùng một cửa sổ trượt có kích thước m trượt qua từng điểm từ trái sang phải trên chuỗi T để xác định mỗi chuỗi con c [6].3 Cửa sổ trượt trên dữ liệu chuỗi thời gian ([7]).2 Chuỗi con Cho một chuỗi thời gian T= (ti, t2., tn), một chuỗi con có chiều dài n của T là một chuỗi Ti, mà n = (ti, ti + 1,.3 So trùng mẫu Cho một số thực R (gọi là phạm vi và do người dùng định nghĩa) và một dữ liệu chuỗi thời gian T chứa một chuỗi con c bắt đầu tại vị trí p và một chuỗi con M bắt đầu tại vị trí q, nếu hàm tính khoảng cách từ c đến M ký hiệu D(C, M) < R (ta dùng công thức tính khoảng cách Euclid để tính toán khoảng cách giữa hai chuỗi con) thì ta nói là chuỗi con M khớp được với chuỗi con c [6], Có hai kiểu so trùng mẫu: so trùng tầm thường và so trùng không tầm thường Hình 2.4 So trùng khớp giữa chuỗi con c và M được cắt ra từ chuỗi thời gian T ([6]) 9 2.4 So trùng tầm thường Cho một số thực dương R và một chuỗi thời gian T. Một chuỗi con Ci của T bắt đầu tại vị trí i và một chuỗi con Cj của T bắt đầu tại vị trí j, nếu DISTANCE(G, Cj) < R thì Cj được gọi là chuỗi con tương tự của c, [8], Các chuỗi con tương tự nhất với một chuỗi con Ci là các chuỗi con bắt đầu tại các vị trí lệch một hay hai điểm về bên trái hay bên phải so với vị trí bắt đầu của chuỗi con Ci. Có nghĩa là chuỗi con mới lệch một khoảng so với chuỗi con cũ và hai chuỗi con này có chung một đoạn giá trị.
Các trường hợp này được gọi là so trùng tầm thường.5 Hai chuỗi con trong chuỗi thời gian T so trùng tầm thường ([6]).5 So trùng không tầm thường Cho chuỗi thời gian T có chiều dài n, chuỗi c và M có chiều dài m và là chuỗi con của chuỗi thời gian T. Chuỗi c bắt đầu tại vị trí p, chuỗi M bắt đầu tại vị trí q. Ta nói chuỗi con M và chuỗi con c so trùng không tầm thường nếu |p - q| > m [6].6 k -motif Cho một dữ liệu chuỗi thời gian T có chiều dài n, và một số thực R, motif quan trọng nhất trong T (còn được gọi là 1- Motif) là chuỗi con Cj nào đó trong T có số lượng chuỗi con khớp không tầm thường với nó cao nhất.