CHƯƠNG 1. GIỚI THIỆU TỔNG QUAN VỀ ĐỀ TÀI Chương này giới thiệu sợ lược về đề tài cũng như giới thiệu các định nghĩa, các vấn đề có liên quan như: Dữ liệu chuỗi thời gian, Bài toán phân lớp, Bài toán phân lớp bán giám sát, Mục tiêu nghiên cứu của đề tài, Tóm lược các kết quả đạt được của đề tài và Cấu trúc của luận văn. NHỮNG CÔNG TRÌNH LIÊN QUAN Chương này trình bày sơ lược về các công trình có liên quan đến bài toán phân lớp bán giám sát dữ liệu chuỗi thời gian như: Các độ đo tương tự trên dữ liệu chuỗi thời gian, Các phương pháp thu giảm số chiều trên dữ liệu chuỗi thời gian, Các giải thuật gom cụm, Vấn đề phân lớp có giám sát dựa trên k-láng giềng-gần nhất (k-NN), Các mô hình phân lớp bán giám sát dữ liệu chuỗi thời gian, Các công trình về tiêu chuẩn dừng cho phân lớp bán giám sát dữ liệu chuỗi thời gian cho mô hình của Wei và Keogh. CƠ SỞ LÝ THUYẾT Chương này trình bày chi tiết về các kỹ thuật được áp dụng trong đề tài như: độ đo xoắn thời gian động, ràng buộc dải Sakoe-Chiba trong độ đo xoắn thời gian động, thu giảm số chiều dữ liệu chuỗi thời gian bằng phương pháp xấp xỉ gộp từng đoạn, giải thuật gom cụm X-means, mô hình phân lớp bán giám sát dữ liệu chuỗi thời gian của Wei và Keogh, Các tiêu chuẩn dừng trong phân lớp bán giám sát dữ liệu chuỗi thời gian cho mô hình của Wei và Keogh, phương pháp phân lớp bán giám sát dữ liệu chuỗi thời gian SUCCESS của Marussy và Buza.
Chương này cũng 7 trình bày một số nhận xét về các phương pháp trước đây và đề xuất một số hướng cải tiến. PHƯƠNG PHÁP ĐỀ NGHỊ Chương này trình bày mô hình phân lớp bán giám sát được sử dụng trong đề tài, Một cải tiến trong tiêu chuẩn dừng dựa trên nguyên lý Chiều dài Mô tả Nhỏ nhất và trình bày đề xuất thêm một bước tinh chế cho tập huấn luyện (Refinement step). THỰC NGHIỆM Chương này trình bày hai kết quả thực nghiệm quan trọng là so sánh tiêu chuẩn dừng MDL cải tiến (Phương pháp đề nghị) so với các tiêu chuẩn dừng trước đó và thực nghiệm so sánh tập huấn luyện trước và sau khi tinh chế (Phương pháp đề nghị). Bên cạnh đó cũng trình bày thêm một số thực nghiệm khác như: so sánh phương pháp đề nghị với phương pháp SUCCESS của Marussy và Buza, thực nghiệm phân lớp bán giám sát dựa trên X-means (X-means-Classifier), thời gian thực thi của các giải thuật.
Kết quả các thực nghiệm cho thấy tiểu chuẩn dừng dựa trên MDL cải tiến và quá trình tinh chế góp phần làm cho tập huấn luyện kết quả trở nên tốt hơn. TỔNG KẾT Chương này trình bày tóm lược về phân lớp bán giám sát dữ liệu chuỗi thời gian, rút ra một số nhận xét, các kết quả đạt được của đề tài, rút ra kết luận về các kết quả đã đạt được và hướng phát triển của đề tài. NHỮNG CÔNG TRÌNH LIÊN QUAN Phần đầu của chương trình bày những công trình về độ đo tương tự trên dữ liệu chuỗi thời gian như độ đo Minkowski, độ đo xoắn thời gian động và độ đo chuỗi con chung dài nhất. Phần thứ hai trình bày về một số phương pháp thu giảm số chiều dữ liệu chuỗi thời gian.
Phần thứ ba trình bày một số phương pháp gom cụm trong khai phá dữ liệu như giải thuật K-means, giải thuật X-means, phương pháp gom cụm phân cấp. Phần phần cuối cùng trình bày những công trình liên quan đến bài toán phân lớp trên dữ liệu chuỗi thời gian như phân lớp có giám sát dựa trên tìm kiếm k-láng giềng-gần nhất, phân lớp bán giám sát dữ liệu chuỗi thời gian với mô hình của Wei và Keogh cùng với những công trình về tiêu chuẩn dừng trong phân lớp bán giám sát dữ liệu chuỗi thời gian theo mô hình của Wei và Keogh, các phương pháp phân lớp bán giám sát dữ liệu chuỗi thời gian dựa vào gom cụm như: LCLC và En-LCLC của Nhut và các cộng sự, phương pháp SUCCESS của Murassy và Buza. NHỮNG CÔNG TRÌNH VỀ ĐỘ ĐO TƯƠNG TỰ Phần này trình bày một số nghiên cứu về cách đánh giá độ tương tự cho dữ liệu chuỗi thời gian. Cho đến thời điểm hiện tại, nhiều tác giả đã đề nghị nhiều độ đo tương tự khác nhau, mỗi độ đo tương tự thích hợp với từng loại dữ liệu trong từng hoàn cảnh khác nhau.
Vấn đề quan trọng của bài toán phân lớp dựa vào sự tương tự là việc đánh giá khoảng cách của hai đối tượng dữ liệu Oi, Oj. Trong trường hợp hai đối tượng này hoàn toàn giống nhau thì khoảng cách này sẽ là 0 và ngược lại chúng càng khác nhau thì khoảng cách càng lớn. Để có thể tính toán và so sánh với nhau thì các khoảng cách này được biểu diễn thành các số thực. 9 Độ đo khoảng cách giữa các đối tượng nên thỏa các tính chất sau: 1.
D(x, y) = 0 nếu và chỉ nếu x = y 2. D(x, y) < D(x, z) + D(y, z) Độ đo tương tự có ý nghĩa quan trọng trong hầu hết các bài toán trên dữ liệu chuỗi thời gian. Trong các mô hình có dùng rút trích đặc trưng hay thu giảm số chiều, độ đo tương tự phải thỏa mãn tính chất sau. Gọi Xf, Yf là biểu diễn của X,Y sau khi trích xuất đặc trưng hay thu giảm số chiều, độ đo khoảng cách D phải đảm bảo: D(Xf, Yf) ≤ D(X, Y).
Trong phần này, độ đo tương tự được định nghĩa trên hai chuỗi có chiều dài bằng nhau X, Y và được ký hiệu Sim(X, Y) [1]. Sau đây là những phương pháp đánh giá độ tương tự đã được một số tác giả đề nghị: 2. Độ đo Minkowski Hầu hết các công trình đều dựa trên độ đo khoảng cách này. Khoảng cách Minkowski được định nghĩa như sau: 𝑝 𝑆𝑖𝑚(𝑋, 𝑌) = √∑𝑛𝑖=1(𝑥𝑖 − 𝑦𝑖 )𝑝 , trong đó 𝑝 = 1 … ∞ Tuy p có thể có nhiều giá trị khác nhau nhưng trong các nghiên cứu p thường nhận các giá trị 1 (khoảng cách Manhattan), 2 (khoảng cách Euclid), (khoảng cách Max).
Giá trị p = 2 được dùng phổ biến nhất. Một số ưu điểm và nhược điểm của phương pháp này: Ưu điểm - Quá trình tính toán đơn giản và dễ dàng. 10 - Phù hợp khi sử dụng các biến đổi: Discrete Fourier Tranform (DFT), Discrete Wavelet Transform (DWT), Piecewise Aggregate Approximation (PAA), Adaptive Piecewise Constant Approximation (APCA), SAX (Symbolic Aggregate approXimation). Nhược điểm - Nhạy cảm với nhiễu.
- Không hiệu quả với dữ liệu được đo ở nhiều thang đo khác nhau. Để khắc phục những nhược điểm trên, nhiều tác giả đã đưa ra những phương pháp sau đây: Das, G. và các cộng sự (1997) [1] đề nghị nên chuẩn hóa dữ liệu chuỗi thời gian trước khi áp dụng các giải thuật so trùng mẫu dựa trên giá trị trung bình và độ lệch chuẩn X’ = X - mean(X) hoặc X’ = (X- mean(X)) / var(X). Phương pháp xoắn thời gian động Phương pháp xoắn thời gian động (Dynamic Time Warping – DTW) tương tự cách tính khoảng cách Minkowski nhưng thay vì so trùng hai đường biểu diễn dữ 11 liệu bằng cách tính khoảng cách từng cặp điểm 1 - 1 (điểm thứ i của chuỗi thứ nhất so với điểm thứ i của chuỗi thứ hai) thì một điểm có thể ánh xạ với nhiều điểm và ánh xạ này không tuyến tính.1 minh họa cách ánh xạ điểm trong độ đo xoắn thời gian động so với độ đo Euclid.
Cách tính khoảng cách xoắn thời gian động sẽ được trình bày chi tiết trong phần 3. So sánh cách ánh xạ cặp điểm trong độ đo Euclid và độ đo DTW (nguồn [11]) Một số ưu điểm và nhược điểm của phương pháp này: Ưu điểm - Phương pháp DTW cho phép nhận dạng những mẫu có hình dạng giống nhau nhưng chiều dài hình dạng về mặt thời gian có thể khác nhau. - Phương pháp DTW thì hiệu quả hơn rất nhiều so với phương pháp tính khoảng cách theo Euclid. Đặc biệt trong các bài toán phân loại (classfication), gom cụm (clustering) hay trong các các ứng dụng nhận dạng giọng nói.
Nhược điểm - Nhược điểm lớn nhất của DTW là thời gian chạy rất lâu, độ phức tạp là O(wn), trong đó w là chiều dài cửa sổ xoắn, n là chiều dài chuỗi. Để khắc phục nhược điểm trên, một số tác giả đã đưa ra những phương pháp sau đây nhằm tăng tốc quá trình tính khoảng cách DTW trong những hoàn cảnh cụ thể như sau: 12 Sakoe, H. (1978) [9] đã đưa ra ràng buộc gọi là dải Sakoe- Chiaba. (1975) [10] đã đưa ra ràng buộc hình bình hành Itakura, đây là những ràng buộc đường xoắn khi tính khoảng cách xoắn thời gian động.
Các ràng buộc này sẽ được trình bày chi tiết trong phần 3. và các cộng sự (2002) [11] đã đề xuất phương pháp tính chặn dưới gọi là chặn dưới LB_Keogh. Phương pháp này nhằm giải quyết vấn đề so sánh độ tương tự trong quá trình tìm kiếm. Nếu giá trị của chặn dưới là lớn hơn khoảng cách tốt nhất hiện tại thì chúng ta không cần tính khoảng cách thực.
Trong quá trình tính khoảng cách xoắn thời gian động, nếu khoảng cách đang tính là lớn hơn khoảng cách tốt nhất hiện tại thì chúng ta không cần phải tính tiếp khoảng cách này.2 minh họa việc từ bỏ sớm khi tính khoảng cách xoắn thời gian động. Hình ảnh minh họa việc từ bỏ sớm trong tính khoảng cách giữa hai chuỗi thời gian (nguồn [21]) 2. Phương pháp chuỗi con chung dài nhất Trong phương pháp này, độ tương tự Sim(X, Y) được tính bằng chiều dài của chuỗi con chung dài nhất (Longest Common Subsequence - LCS). Giải thuật chi tiết cho việc tìm LCS có thể được tìm thấy trong [4][1].3 diễn tả ý tưởng của phương pháp chuỗi con chung dài nhất.
13 Đoạn này có thể bỏ qua khi so trùng Hình 2. Hình Phương pháp 2. Phương pháp chuỗi chuỗi con con chung chung dài dài nhất nhất (nguồn (nguồn [1]) [1]) Một số ưu điểm và nhược điểm của phương pháp chuỗi con chung dài nhất: Ưu điểm: cho phép bỏ qua những điểm bất thường khi so sánh. Nhược điểm: phải chuẩn hóa dữ liệu ban đầu thông qua các phép biến đổi như tịnh tiến (shifting) đường căn bản hay phép co giãn biên độ (scaling) trước khi thực hiện giải thuật.
NHỮNG CÔNG TRÌNH LIÊN QUAN ĐẾN THU GIẢM SỐ CHIỀU DỮ LIỆU CHUỖI THỜI GIAN Dữ liệu chuỗi thời gian thường rất lớn. Do đó, việc tìm kiếm trực tiếp trên loại dữ liệu này sẽ rất phức tạp và không hiệu quả. Để khắc phục vấn đề này, chúng ta nên áp dụng một số phương pháp biến đổi để thu giảm độ lớn của dữ liệu.
