CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI Chương này giới thiệu sơ lược các định nghĩa, các vấn đề có liên quan đến đề tài, mục tiêu và giới hạn nghiên cứu của đề tài, tóm lược các kết quả đạt được và bố cục luận văn. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT Chương này trình bày chi tiết về các cơ sở lý thuyết được áp dụng trong đề tài như: thuật toán k-lân cận gần nhất, cách tính độ đo xoắn thời gian động CHƯƠNG 3: TỔNG QUAN CÁC CÔNG TRÌNH LIÊN QUAN Chương này giới thiệu sơ lược một số công trình nghiên cứu về thu gọn tập huấn luyện có liên quan đến đề tài. CHƯƠNG 4 : GIẢI PHÁP THỰC HIỆN Chương này giới thiệu hướng tiếp cận của chúng tôi để thực hiện đề tài. CHƯƠNG 5: KẾT QUẢ THỰC NGHIỆM Chương này tiến hành thực nghiệm trên nhiều bộ dữ liệu khác nhau cho quá trình thu gọn tập huấn luyện, khảo sát thời thời gian thực thi việc thu gọn và độ chính xác phân lớp.
Một số kết luận được rút ra từ kết quả thực nghiệm. CHƯƠNG 6: TỔNG KẾT Chương này trình bày tổng lược lại toàn bộ nội dung quan trọng của luận văn, các đóng góp chính của đề tài, và hướng phát triển. PHẦN TÀI LIỆU THAM KHẢO PHẦN PHỤ LỤC 3 CHƯƠNG 2. CƠ SỞ LÝ THUYẾT Ở chương này chúng tôi tập trung trình bày những cơ sở lý thuyết quan trọng về dữ liệu chuỗi thời gian như: độ đo khoảng cách, giải thuật phân lớp.
Trước hết chúng tôi cần hiểu rõ chuỗi thời gian là gì và các đặc điểm của nó.1 ĐẶC ĐIỂM CỦA DỮ LIỆU CHUỖI THỜI GIAN Chuỗi thời gian (time series) là chuỗi trị số thực, mỗi trị số biểu diễn một giá trị đo tại những thời điểm cách đều nhau. 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, v. Ví dụ kết quả quan sát hiện tượng động đất (đơn vị Richter) qua 99 năm liên tục là chuỗi thời gian như trong hình 2.1: Ví dụ về chuỗi thời gian động đất Ngoài ra, còn có các định nghĩa về chuỗi thời gian đơn biến (univariate time series) và chuỗi thời gian đa biến (multivariate time series). Chuỗi thời gian đơn biến là một chuỗi thời gian chỉ chứa một quan sát được ghi nhận một cách tuần tự tại những khoảng thời gian cách đều nhau.
Chuỗi thời gian đa biến là chuỗi thời gian mà trong đó tại một thời điểm ta có nhiều quan sát (biến) khác nhau.1 Chuỗi con Cho một chuỗi thời gian T có chiều dài n, một chuỗi con (Subsequence) C của T là một dãy có chiều dài m (1 ≤ m ≤ n ) có vị trí liền nhau trong chuỗi thời gian T .2: Ví dụ về chuỗi con và cửa sổ trượt [8]. Một chuỗi con C của T cũng có thể được xem là một chuỗi thời gian với chiều dài m. Một điều cần lưu ý là khái niệm “chuỗi con” khác với khái niệm “chuỗi tuần tự”. Nếu khái niệm “chuỗi tuần tự” cho phép các phần tử của chuỗi có thể không liên tục so với chuỗi ban đầu, thì khái niệm “chuỗi con C ” của một chuỗi thời gian T chỉ chấp nhận những phần tử liên tiếp nhau trong chuỗi thời gian T.
Bên dưới là một ví dụ về chuỗi con của một chuỗi thời gian. Cho chuỗi thời gian T = (3, 5, 1, 12, 4, 7). Khi đó, C1 = (12, 4, 7) được gọi là một chuỗi con của chuỗi thời gian T. Tuy nhiên, C2 = (3, 1, 12, 4) không được xem là một chuỗi con của chuỗi thời gian T , vì 3 và 1 là các giá trị không liên tiếp nhau trong T.
Các công trình nghiên cứu thường áp dụng phương pháp cửa sổ trượt (Sliding Win- dows) để lấy các chuỗi con trong một chuỗi thời gian để phục vụ cho bài toán nghiên cứu. Số lượng của các chuỗi con lấy được là bằng nhau và bằng độ dài của cửa sổ trượt.2 minh họa chuỗi con được xác định bằng phương pháp cửa sổ trượt.2 Trùng khớp Cho một số thực dương R (do người dùng định nghĩa) và một chuỗi thời gian T. Biết rằng T chứa một chuỗi con C bắt đầu tại thời điểm p và một chuỗi con M bắt đầu tại q , nếu khoảng cách D giữa 2 chuỗi nhỏ hơn hoặc bằng R, tức D(C, M ) ≤ R, thì M là một chuỗi con trùng khớp với C và ngược lại.2 ĐỘ ĐO KHOẢNG CÁCH Có nhiều loại độ đo khoảng cách để hỗ trợ tính toán trong quá trình khai phá dữ liệu. Nhưng đối với quá trình phân lớp với tập dữ liệu chuỗi thời gian thì thường sử dụng 2 loại độ đo khoảng cách chủ yếu là độ đo khoảng cách Euclid và và độ đo khoảng cách xoắn thời gian động (Dynamic Time Warping - DTW).
Ở phần này chúng tôi tìm hiểu cách tính của 2 độ đo này trong dữ liệu chuỗi thời gian [5].1 Khoảng cách Euclid Cho 2 chuỗi thời gian Q = Q1 , Q2 ,. Khi đó khoảng cách Euclid giữa hai chuỗi thời gian Q và C được xác định bằng công thức sau: v u n uX D (Q, C) =t (qi − ci )2 (2.1) i=1 Độ đo khoảng cách Euclid có ưu điểm là dễ hiểu, dễ tính toán, dễ mở rộng cho nhiều bài toán khai phá dữ liệu chuỗi thời gian khác như gom cụm, phân lớp, nhận dạng mô típ, v. Nhưng độ đo khoảng cách này có nhược điểm là nhạy cảm với nhiễu và thiếu sự mềm dẻo khi so trùng [4].2 Độ đo xoắn thời gian động (Dynamic Time Warping - DTW) Trên nhiều nghiên cứu đã chứng minh DTW là độ đo xoắn thời gian động tính toán khoảng cách giữa 2 mẫu dữ liệu chuỗi thời gian cho độ chính xác nhiều hơn so với khoảng cách Euclid.1 Phương pháp tính khoảng cách DTW Cho 2 chuỗi thời gian Q và C có chiều dài lần lượt là n và m theo với Q = Q1 , Q2 ,. , Cm công thức DTW được tính như sau: • Bước 1: Xây dựng một ma trận có kích thước n ∗ m với n là số hàng của ma trận và m là số cột của ma trận.
Trong đó phần tử (ith , j th ) của ma trận chứa khoảng cách d(qi , cj ) giữa hai điểm qi , cj trên 2 chuỗi dữ liệu Q và C. • Bước 2: Ma trận chứa khoảng cách d(qi , cj ) được gọi là ma trận xoắn (Warping matrix). Một đường xoắn (warping path) là một tập các phần tử liên tục của ma trận định nghĩa một đường ánh xạ giữa Q và C W = w1 , w2 ,. , wk với max(m, n) ≤ K ≤ m + n − 1 • Bước 3: Có rất nhiều đường xoắn thỏa mãn các điều kiện trên nhưng chúng ta chỉ quan tâm đến đường xoắn có chi phí tối thiểu.
Chi phí của một đường xoắn là tổng khoảng cách của các cặp điểm tương ứng với các ô nằm trên đường xoắn đó. v uuXK DT W (Q, C) = min t Wk (2.2) k=1 6 Đường xoắn tối ưu này có thể tìm được bằng cách sử dụng phương pháp quy hoạch động (dynamic programming). Công thức truy hồi cho khoảng cách tích lũy (cu- mulative distance) được định nghĩa như sau: γ(i − 1, j) γ(i, j) = d(di , cj ) + min γ(i, j − 1) (2.3) γ(i − 1, j − 1) Trong đó, khoảng cách tích lũy γ(i, j) tại ô (i, j) của ma trận được tính bằng khoảng cách của ô tương ứng cộng với giá trị nhỏ nhất của khoảng cách tích lũy của các ô liền kề trước ô đó. Khoảng cách xoắn thời gian động của hai chuỗi thời gian Q và C là căn bậc hai của khoảng cách tích lũy tại ô có chỉ số là (m, n).
Đối với việc tính toán DTW chúng ta có một số ràng buộc sau: – Điều kiện biên: w1 = (1, 1) và wk = (m, n) ràng buộc này yêu cầu đường xoắn phải bắt đầu và kết thúc ở hai góc đối diện của ma trận. – Tính liên tục: wk = (a, b) thì wk−1 = (a0 , b0 ) trong đó a − a0 ≤ 1 và b − b0 ≤ 1. Ràng buộc này yêu cầu đường xoắn phải di chuyển giữa những ô liền kề (kể cả những ô liền kề theo đường chéo). – Tính đơn điệu tăng: wk = (a, b) thì wk−1 = (a0 , b0 ), với a − a0 ≥ 0 và b − b0 ≥ 0.
Ràng buộc này yêu cầu các điểm trong đường xoắn W phải có tính đơn điệu tăng theo thời gian. Algorithm 1 trình bày mã giả giải thuật tính khoảng cách giữa hai chuỗi thời gian Q có chiều dài n và C có chiều dài m. DTW Input: Q : Array[1.m] Output: DT W [n, m] 1: DT W ← emptyArray[n, m] 2: for from i = to n do 3: for from j = 1 to m do 4: // The distance γ(i, j) is calculated using eq.4 5: DT W [i, j] = (Q[i] − C[j])2 + min(DT W [i − 1, j], DT W [i, j − 1], DT W [i − 1, j − 1] 6: end for 7: end for 8: return DT W [n, m] Phương pháp DTW có ưu điểm là cho kết quả khoảng cách chính xác hơn so với 7 độ đo Euclid và cho phép nhận dạng mẫu có hình dạng giống nhau nhưng chiều dài hình dạng về thời gian có thể khác nhau. Phương pháp này có nhược điểm là thời gian chạy lâu, tuy nhiên cũng đã có những công trình nghiên cứu đề xuất các giải pháp tăng tốc độ tìm kiếm tương tự dùng độ đo DTW[16].3 mô tả sự khác biệt giữa độ đo Euclid và độ đo xoắn thời gian động.3: Độ đo Euclid và độ đo xoắn thời gian động [5] Hình 2.4: Ma trận xoắn thời gian động [16] Hình 2.
Để sắp xếp lại hai chuỗi này ta xây dựng ma trận xoắn và tìm đường xoắn tối ưu (hình bên phải).2 Ví dụ tính khoảng cách DTW Giả sử có hai chuỗi thời gian Q và C như sau: Q = (1, 3, 4, 9, 8, 2, 1, 5, 7, 3) C = (1, 6, 2, 3, 0, 9, 4, 3, 6, 3) Hai chuỗi thời gian Q và C được biểu diễn dưới dạng biểu đồ ở hình 2.5: Biểu đồ biểu diễn 2 chuỗi thời gian Q và C Áp dụng Algorithm 1, ta xây dựng ma trận xoắn lưu khoảng cách tích luỹ giữa các điểm dữ liệu tương ứng của hai chuỗi thời gian Q và C .