GIỚI THIỆU
Chuỗi thời gian dạng luồng và thách thức xử lý chuỗi thời gian dạng luồng
Chuỗi thời gian (time series) là tập hợp các giá trị hoặc sự kiện được ghi nhận tại các thời điểm cách đều nhau theo trục thời gian, trong đó ít nhất một chiều phải là thời gian Ví dụ, tỷ giá hối đoái USD/VND được ghi nhận hàng ngày từ 02/01/2017 đến 29/08/2017 minh họa cho khái niệm này.
Hình 1.1 Đường biểu diễn chuỗi thời gian thể hiện tỷ giá USD/VND (nguồn [1])
Dữ liệu chuỗi thời gian có thể có các tính chất như sau:
(ii) mối tương quan cao giữa các điểm giá trị, và
(iii) dữ liệu có thể bị nhiễu
Các tính chất này khiến cho việc khai phá dữ liệu chuỗi thời gian gặp nhiều thách thức
Chuỗi thời gian dạng luồng (streaming time series) là một loại chuỗi thời gian trong đó các giá trị mới được ghi nhận liên tục và được thêm vào cuối chuỗi theo trình tự thời gian Ví dụ, tỷ giá hối đoái USD/VND được ghi nhận hàng ngày, minh họa cho cách thức hoạt động của chuỗi thời gian dạng luồng.
Ngày 30/8/2017 sẽ được bổ sung vào cuối chuỗi thời gian, tạo thành một luồng dữ liệu liên tục được ghi nhận theo từng ngày làm việc.
Theo G Li và các cộng sự [2], chuỗi thời gian dạng luồng có các đặc trưng:
• Các phần tử dữ liệu tới trực tuyến
• Hệ thống không thể điều khiển thứ tự dữ liệu tới
• Khối lượng dữ liệu nhiều đến mức có thể là vô tận, do vậy bộ nhớ chứa dữ liệu không thể lưu trữ tất cả dữ liệu
Khi một phần tử dữ liệu được xử lý, nó sẽ được lưu trữ trong bộ nhớ trong một khoảng thời gian nhất định Sau đó, phần tử này sẽ được chuyển đến một vị trí khác để lưu trữ hoặc bị xóa bỏ và không thể phục hồi.
Để xử lý dữ liệu chuỗi thời gian dạng luồng trong thời gian thực, cần áp dụng phương pháp có độ phức tạp thời gian thấp và quét dữ liệu chỉ một lần Hai yêu cầu này đặt ra thách thức lớn cho các phương pháp xử lý chuỗi thời gian tĩnh, do đó cần phát triển các kỹ thuật mới hoặc cải tiến các kỹ thuật hiện có Mục tiêu là đảm bảo hiệu quả trong việc xử lý chuỗi thời gian dạng luồng, dựa trên hai tiêu chí chính: chất lượng kết quả và thời gian thực hiện.
Theo khảo sát của chúng tôi, nhu cầu xử lý dữ liệu chuỗi thời gian dạng luồng ngày càng tăng trong nhiều ứng dụng như phân tích lưu lượng mạng máy tính, giám sát vị trí thiết bị di động, theo dõi các tia bất thường trong thiên văn và giám sát giao dịch cổ phiếu Sự phức tạp và khó khăn trong việc xử lý loại dữ liệu này đã khiến Fu vào năm 2011 nhận định rằng đây là một trong hai hướng nghiên cứu chính trong lĩnh vực khai phá dữ liệu chuỗi thời gian.
Mục tiêu, đối tượng và phạm vi nghiên cứu
Trong khai phá dữ liệu chuỗi thời gian, các bài toán chính thường được nghiên cứu bao gồm tìm kiếm tương tự, phát hiện bất thường và phát hiện mô típ Những vấn đề này đóng vai trò quan trọng trong việc phân tích và xử lý dữ liệu theo thời gian, giúp phát hiện các xu hướng và bất thường trong các chuỗi dữ liệu phức tạp.
Trong các bài toán như phát hiện mẫu, dự báo, kết chuỗi con và rút trích luật, tìm kiếm tương tự đóng vai trò quan trọng và là nền tảng cho nhiều giải pháp khác Trong khi tìm kiếm dữ liệu trong cơ sở dữ liệu truyền thống thường yêu cầu sự so trùng chính xác, thì tìm kiếm tương tự trên chuỗi thời gian lại dựa vào sự so trùng xấp xỉ Điều này có nghĩa là khoảng cách giữa hai chuỗi thời gian được xác định qua một độ đo nhất định, và chỉ khi khoảng cách này nhỏ hơn một ngưỡng đã định, hai chuỗi thời gian mới được coi là tương tự nhau.
Các nghiên cứu hiện tại về tìm kiếm tương tự trên chuỗi thời gian dạng luồng thường gặp phải vấn đề chi phí tính toán cao và thiếu chuẩn hóa dữ liệu, dẫn đến kết quả không chính xác Để khắc phục những khuyết điểm này, luận án này sẽ tập trung vào việc nghiên cứu bài toán tìm kiếm tương tự trên chuỗi thời gian dạng luồng.
Luận án bao gồm hai nhiệm vụ nghiên cứu và mục tiêu cụ thể của từng nhiệm vụ là
Nhiệm vụ 1: Xây dựng các phương pháp tìm kiếm tương tự trên chuỗi thời gian dạng luồng bằng
• Độ đo Euclid (Euclidean measure) có vận dụng các phép biến đổi thu giảm số chiều và cấu trúc chỉ mục đa mức phân giải
• Độ đo xoắn thời gian động (Dynamic Time Warping measure) hay còn gọi là độ đo
DTW và các kỹ thuật tăng tốc cho độ đo này
Nhiệm vụ 2: Ứng dụng các phương pháp tìm kiếm tương tự trên chuỗi thời gian dạng luồng để giải quyết các bài toán sau
• Dự báo trực tuyến (online forecating) trên chuỗi thời gian dạng luồng có xu hướng và tính mùa (trend and seasonal) bằng độ đo DTW
• Phát hiện k chuỗi con bất thường nhất (top-k discords detection) trong chuỗi thời gian dạng luồng bằng độ đo Euclid
Tìm kiếm tương tự trên chuỗi thời gian dạng luồng được chia thành hai loại chính: truy vấn tĩnh và truy vấn dạng luồng Truy vấn tĩnh (static query) cho phép người dùng truy xuất dữ liệu từ một tập hợp cố định, trong khi truy vấn dạng luồng (streaming query) liên tục xử lý và trả về kết quả từ dữ liệu đang được cập nhật theo thời gian thực.
Trong lĩnh vực tài chính, đặc biệt là thị trường chứng khoán, có nhiều mẫu cổ phiếu và chuỗi thời gian thể hiện sự biến động giá trị cổ phiếu của các công ty Những chuỗi thời gian này được coi là luồng dữ liệu, và yêu cầu là tìm các chuỗi con có hình dạng tương tự với các mẫu cổ phiếu đã có Truy vấn tĩnh cũng được áp dụng trong giám sát mạng, nơi có nhiều luồng dữ liệu liên tục cần so sánh với các mẫu cần phát hiện Trong khai phá dữ liệu chuỗi thời gian, mẫu thường được biểu diễn bằng chuỗi truy vấn đã xác định trước, và chức năng tìm kiếm tương tự cho chuỗi truy vấn tĩnh trên chuỗi thời gian dạng luồng được sử dụng để đáp ứng yêu cầu này.
Trong lĩnh vực môi trường, đặc biệt là biến đổi khí hậu, truy vấn dạng luồng là phương pháp quan trọng để ghi nhận và cập nhật liên tục các thông số thời tiết theo thời gian Chuỗi thời gian này không ngừng thay đổi do yêu cầu truy vấn cũng như sự biến động của môi trường Điều này dẫn đến việc chuỗi truy vấn cũng phải linh hoạt, với dữ liệu cũ được thay thế bởi dữ liệu mới, đảm bảo tính liên tục và kế thừa Do đó, chức năng tìm kiếm cho chuỗi truy vấn dạng luồng trên chuỗi thời gian dạng luồng trở nên cần thiết để quản lý và truy xuất thông tin hiệu quả.
Tùy thuộc vào ứng dụng, các nghiên cứu trong luận án sử dụng các kiểu truy vấn khác nhau Truy vấn tĩnh thường dễ nhận diện và phổ biến hơn so với truy vấn dạng luồng, đồng thời việc xử lý truy vấn tĩnh cũng đơn giản hơn Truy vấn dạng luồng chỉ xuất hiện trong một số ứng dụng đặc biệt Do đó, trong nhiệm vụ nghiên cứu thứ nhất về tìm kiếm tương tự trên chuỗi thời gian dạng luồng, luận án sẽ tập trung vào tìm kiếm tương tự cho truy vấn tĩnh Trong nhiệm vụ nghiên cứu thứ hai, vì tính chất của các bài toán yêu cầu xử lý truy vấn dạng luồng, luận án sẽ mở rộng giải pháp tìm kiếm tương tự từ truy vấn tĩnh sang truy vấn dạng luồng.
Phương pháp nghiên cứu
Tìm kiếm tương tự trên chuỗi thời gian bằng độ đo Euclid bắt đầu từ việc tìm kiếm trên đặc trưng của dữ liệu, giúp giảm đáng kể độ phức tạp thời gian so với việc tìm kiếm trực tiếp trên dữ liệu chuỗi thời gian Đặc trưng này thường được thu nhận từ phép biến đổi giảm chiều, và để tránh lỗi tìm sót, phép biến đổi cần có tính chất chặn dưới Để tăng tốc tìm kiếm, đặc trưng dữ liệu thường được lưu trong cấu trúc chỉ mục không gian, như R-tree và các biến thể của nó Cấu trúc chỉ mục này nên được tổ chức theo đa mức phân giải để phù hợp với các chuỗi truy vấn có độ dài và yêu cầu thời gian tìm kiếm khác nhau, với mức phân giải có chức năng lọc kết quả, từ mức lọc thô đến mức lọc tinh, nhằm đảm bảo hiệu quả và độ chính xác trong tìm kiếm.
Trước đây, nhiều nghiên cứu đã được thực hiện về tìm kiếm tương tự trên chuỗi thời gian bằng độ đo Euclid, nhưng hầu hết không chuẩn hóa dữ liệu trước khi tiến hành tìm kiếm, dẫn đến việc các tác giả cho rằng các công trình này ít có giá trị thực tiễn Mặc dù vậy, việc bỏ qua chuẩn hóa dữ liệu hoặc giả định rằng dữ liệu gốc đã được chuẩn hóa vẫn mang lại một số thuận lợi.
Chuẩn hoá dữ liệu là yếu tố quan trọng giúp tăng tốc độ tìm kiếm, đặc biệt trong việc tính toán hệ số đặc trưng của điểm dữ liệu mới từ các điểm dữ liệu trước đó Ví dụ, khi so sánh hai chuỗi thời gian, một ghi nhận lượng mưa và một ghi nhận độ ẩm, việc sử dụng các đơn vị đo khác nhau khiến cho việc so sánh trực tiếp trở nên khó khăn Hình 1.2 minh hoạ một phân đoạn chuỗi thời gian từ dữ liệu EEG, trong đó chỉ có một chuỗi con tương tự được tìm thấy trong khi hai chuỗi con khác bị bỏ sót do khác biệt về cao độ Nếu thực hiện chuẩn hoá dữ liệu trước khi tìm kiếm, khả năng bị bỏ sót sẽ giảm thiểu đáng kể.
Hình 1.2 Lỗi tìm sót xảy ra khi không chuẩn hoá dữ liệu trước khi tìm kiếm tương tự
Dựa trên những nhận xét đã nêu, luận án đề xuất hai yêu cầu bổ sung cho bài toán tìm kiếm tương tự trên chuỗi thời gian dạng luồng bằng độ đo Euclid.
1 Thực hiện chuẩn hóa dữ liệu trước khi tìm kiếm tương tự Chuẩn hóa dữ liệu nên thực hiện theo cách tính toán gia tăng (incremental computation) nhằm giảm chi phí tính toán
2 Cải tiến cấu trúc chỉ mục không gian để tối ưu không gian lưu trữ và giảm thiểu thời gian tìm kiếm trong cấu trúc chỉ mục
Tìm kiếm tương tự trên chuỗi thời gian bằng độ đo DTW thường cho kết quả chính xác hơn so với độ đo Euclid, nhưng chi phí tính toán cao của DTW khiến quá trình này mất nhiều thời gian Nhiều kỹ thuật tăng tốc đã được đề xuất, như giới hạn không gian tính toán và sử dụng hàm chặn dưới Đặc biệt, bộ kỹ thuật UCR-DTW do Rakthanmanon và cộng sự phát triển rất hiệu quả cho việc tìm kiếm tương tự trên chuỗi thời gian tĩnh, với ưu điểm nổi bật là chuẩn hóa dữ liệu trước khi tìm kiếm và kết hợp nhiều kỹ thuật tăng tốc Tuy nhiên, UCR-DTW chỉ có thể tính khoảng cách DTW giữa hai chuỗi có chiều dài bằng nhau, làm giảm thế mạnh của DTW Do đó, luận án này sẽ tập trung vào cải tiến UCR-DTW để phù hợp với tìm kiếm tương tự trên chuỗi thời gian dạng luồng Hai cải tiến đáng kể cho UCR-DTW sẽ được đề xuất.
1 Cập nhật hình bao (envelope) của chuỗi con của chuỗi thời gian dạng luồng theo cách thức tính toán gia tăng nhằm giảm chi phí tính toán Hình bao này được sử dụng trong một hàm chặn dưới cho độ đo DTW
2 Thay đổi một hàm chặn dưới cho độ đo DTW để UCR-DTW có thể tính khoảng cách DTW giữa hai chuỗi thời gian có chiều dài khác nhau
Phương pháp SPRING của Sakurai và các cộng sự là một kỹ thuật tìm kiếm tương tự trên chuỗi thời gian dạng luồng, sử dụng độ đo DTW và có thời gian thực hiện nhanh Tuy nhiên, phương pháp này chỉ áp dụng cho dữ liệu không được chuẩn hóa Do đó, luận án sẽ cải tiến SPRING để cho phép tìm kiếm tương tự trên dữ liệu đã được chuẩn hóa.
Dựa trên các giải pháp đã đề xuất cho việc tìm kiếm tương tự trên chuỗi thời gian dạng luồng bằng độ đo Euclid và DTW, luận án trình bày hai ứng dụng cụ thể.
1 Dự báo trực tuyến trên chuỗi thời gian dạng luồng có xu hướng và tính mùa bằng độ đo DTW Chuỗi thời gian có tính mùa có các yếu tố mùa tác động lên chuỗi thời
Các pha biến đổi tương tự trong quá khứ có thể giúp suy ra các điểm dữ liệu theo sau pha biến đổi hiện tại Để nhận diện các pha biến đổi trong chuỗi thời gian có tính mùa, ta cần xác định các điểm cực trị trong chuỗi Việc tìm kiếm k lân cận gần nhất (k nearest neighbours) trên chuỗi thời gian dạng luồng bằng độ đo DTW cho phép xác định các pha biến đổi tương tự Phương pháp này phù hợp với học trì hoãn (lazy learning) và kết quả dự báo sẽ được so sánh với dữ liệu thực tế để kiểm tra độ chính xác của phương pháp đề xuất.
2 Phát hiện k chuỗi con bất thường nhất trong chuỗi thời gian dạng luồng bằng độ đo Euclid Chuỗi con bất thường nhất là chuỗi con khác biệt nhiều nhất với các chuỗi con còn lại Để giải quyết bài toán này trong môi trường luồng thì cần dùng một hàm chặn dưới trên một phép biến đổi thu giảm số chiều chuỗi thời gian như biến đổi DFT [13], biến đổi Haar wavelet [15], hoặc biến đổi PAA [35], và một bộ kỹ thuật tính khoảng cách Euclid hiệu quả như UCR-ED của Rakthanmanon và các cộng sự
Hàm chặn dưới và bộ kỹ thuật UCR-ED cần được cải tiến để hoạt động hiệu quả trong môi trường luồng Để đánh giá hiệu quả của phương pháp đề xuất, kết quả thu được sẽ được so sánh với giải thuật HOT SAX, một phương pháp tìm kiếm bất thường trong chuỗi thời gian tĩnh, và giải thuật SHOT SAX, là phiên bản cải biên của HOT SAX để phù hợp với môi trường luồng.
Các phương pháp giải quyết hai bài toán ứng dụng này sử dụng tìm kiếm tương tự cho chuỗi truy vấn trên chuỗi thời gian dạng luồng Đặc điểm nổi bật của hai bài toán là chuỗi truy vấn sẽ thay đổi khi có điểm dữ liệu mới trong chuỗi thời gian Vì vậy, các phương pháp đề xuất cần có cách xử lý đặc biệt cho truy vấn dạng luồng.
Để lưu trữ dữ liệu chuỗi thời gian, việc sử dụng bộ đệm có qui mô lớn là cần thiết do xu hướng bùng nổ kích thước lưu trữ theo thời gian Bộ đệm này sẽ giúp lưu trữ dữ liệu hiệu quả và cho phép thực hiện các hoạt động tìm kiếm tương tự trên chuỗi thời gian dạng luồng.
Tóm tắt kết quả đạt được
Luận án đã xác định bài toán tìm kiếm tương tự trên nhiều chuỗi thời gian dạng luồng từ nhiệm vụ nghiên cứu đầu tiên và đề xuất các giải pháp cho từng mục tiêu của nhiệm vụ này.
1.4.1 Tìm ki ếm tương tự tr ên chu ỗ i th ời gian dạng luồng b ằng độ đo Euclid
Luận án giới thiệu một mô hình hệ thống tìm kiếm tương tự cho các chuỗi thời gian dạng luồng, sử dụng độ đo Euclid Bên cạnh đó, nó cũng đề xuất một phương pháp tìm kiếm vùng hiệu quả.
(range search) để hiện thực mô hình hệ thống Hệ thống tìm kiếm tương tự sử dụng
Bài viết trình bày 10 kỹ thuật đa luồng để thực hiện đồng thời việc tìm kiếm tương tự trên nhiều chuỗi thời gian dạng luồng, hỗ trợ bởi cấu trúc chỉ mục đa mức phân giải từ mảng R*-tree Phương pháp đề xuất sử dụng các phép biến đổi giảm số chiều như DFT, biến đổi Haar walet, hoặc biến đổi PAA, cho kết quả chính xác tương tự như SUCR-ED, một cải tiến của UCR-ED trong tìm kiếm chuỗi thời gian Đặc biệt, phương pháp này có thời gian thực hiện nhanh hơn đáng kể so với SUCR-ED và đã được công bố trong hai công trình nghiên cứu [CT9] và [CT5].
Chuẩn hóa z-score gia tăng, được giới thiệu trong bài báo [CT9], giúp giảm chi phí tính toán trong môi trường luồng nhờ vào việc tối ưu hóa quy trình chuẩn hóa Kỹ thuật này cũng được áp dụng trong hầu hết các phương pháp đề xuất khác trong luận án.
Để tìm kiếm tương tự hiệu quả trong cấu trúc chỉ mục đa mức phân giải, chuỗi truy vấn có thể được phân đoạn theo hai cách: không chồng lấp và chồng lấp Kỹ thuật phân đoạn không chồng lấp đã được trình bày trong bài báo [CT9], trong khi kỹ thuật phân đoạn chồng lấp được mô tả trong bài báo [CT5].
Luận án giới thiệu một phương pháp tìm kiếm k lân cận gần nhất trên các chuỗi thời gian dạng luồng, dựa trên phương pháp tìm kiếm vùng từ tài liệu [CT9], với các cải tiến nhằm hỗ trợ hiệu quả hơn cho việc tìm kiếm Phương pháp này điều chỉnh thủ tục truy vấn vùng trong R-tree để cho phép truy vấn nhiều ngưỡng khoảng cách đồng thời Hơn nữa, nó còn giải quyết vấn đề xung đột khi nhiều tiến trình luồng cùng cập nhật tập hợp k lân cận gần nhất cho một chuỗi truy vấn Kết quả thực nghiệm cho thấy phương pháp mang lại độ chính xác cao và thời gian phản hồi nhanh, và đã được công bố trong nghiên cứu [CT8].
Luận án này trình bày việc cải tiến kỹ thuật STR để tối ưu hóa cấu trúc dữ liệu R-tree, nhằm tăng tốc độ tìm kiếm tương tự trên chuỗi thời gian Cải tiến này giúp nâng cao hiệu quả trong việc xử lý và truy xuất dữ liệu thời gian, mang lại kết quả chính xác và nhanh chóng hơn cho các ứng dụng liên quan.
Hai chiến lược kết nối các điểm đặc trưng của chuỗi thời gian trong các nút của R-tree giúp tăng tốc độ tìm kiếm so với các kỹ thuật tạo R-tree khác như Quadratic R-tree, R*-tree và kỹ thuật STR Việc cải thiện thời gian tìm kiếm trong R-tree dẫn đến thời gian phản hồi kết quả tìm kiếm trên chuỗi thời gian cũng nhanh hơn Các chiến lược này đã được công bố trong nghiên cứu [CT7].
1.4.2 Tìm ki ếm tương tự t rên chu ỗ i th ời gian dạng luồng b ằng độ đo DTW
Luận án giới thiệu một mô hình hệ thống tìm kiếm tương tự cho các chuỗi thời gian dạng luồng dựa trên độ đo DTW, kèm theo một phương pháp hiện thực hóa mô hình này Phương pháp được cải tiến từ bộ kỹ thuật UCR-DTW, với hai cải tiến chính là áp dụng kỹ thuật đa luồng và cập nhật hình bao của chuỗi con theo cách tính toán gia tăng, nhằm giảm chi phí tính toán Thực nghiệm cho thấy phương pháp này có thời gian phản hồi nhanh và cho kết quả chính xác tương đương với UCR-DTW Tuy nhiên, giống như UCR-DTW, phương pháp chỉ có thể tính khoảng cách DTW giữa hai chuỗi thời gian có chiều dài bằng nhau Phương pháp này đã được công bố trong nghiên cứu [CT6].
Phương pháp SPRING đã được cải tiến để chuẩn hóa dữ liệu trước khi thực hiện tìm kiếm tương tự trên chuỗi thời gian dạng luồng Cụ thể, SPRING sử dụng kỹ thuật chuẩn hóa min-max gia tăng (incremental min-max normalization) nhằm tối ưu hóa quá trình tính toán khoảng cách.
Phương pháp DTW có khả năng so sánh hai chuỗi thời gian với chiều dài khác nhau Kết quả của phương pháp SPRING cải tiến cho thấy hiệu quả tìm kiếm tương tự tốt hơn so với phương pháp trong bài báo [CT6], nhờ vào khả năng phát hiện các cặp chuỗi thời gian tương tự mặc dù có độ dài khác nhau Tuy nhiên, thời gian phản hồi của SPRING cải tiến lâu hơn do cần tính toán lại khoảng cách DTW mỗi khi hệ số min-max thay đổi Phương pháp này đã được công bố trong nghiên cứu [CT3].
Luận án này mở rộng phương pháp đã được trình bày trong bài báo [CT6], nhằm tính toán khoảng cách DTW giữa hai chuỗi thời gian có độ dài khác nhau.
Hàm chặn dưới LB_ Keogh được điều chỉnh để áp dụng cho hai chuỗi thời gian có độ dài khác nhau trong dải Sakoe-Chiba Phương pháp này cho phép tìm kiếm tương tự trên các chuỗi thời gian dạng luồng bằng độ đo DTW, mang lại kết quả là các cặp chuỗi tương tự với chiều dài khác nhau Phương pháp đã được công bố trong nghiên cứu [CT4].
Từ nhiệm vụ nghiên cứu thứ hai, luận án đã đề xuất giải pháp cho từng bài toán ứng dụng như sau
1.4.3 D ự báo trự c tuy ến trên chuỗ i th ời gian dạng luồng
Luận án giới thiệu phương pháp dự báo trực tuyến cho chuỗi thời gian dạng luồng có xu hướng và tính mùa, sử dụng tìm kiếm k lân cận gần nhất với độ đo DTW Trước khi tìm kiếm, các chuỗi con tương tự được rút trích qua kỹ thuật phân đoạn dựa vào điểm cực trị quan trọng Phương pháp tìm kiếm k chuỗi con tương tự trong quá khứ được thực hiện trên chuỗi thời gian dạng luồng bằng độ đo DTW Để nâng cao độ chính xác, phương pháp dự báo trực tuyến có thể kết hợp với kỹ thuật làm trơn hàm mũ đơn giản Kết quả thực nghiệm trên các bộ dữ liệu thực tế cho thấy phương pháp đạt được độ chính xác cao và thời gian thực hiện không đáng kể Phương pháp này đã được công bố trong công trình nghiên cứu [CT2].
1.4.4 Phát hi ện k chuỗi con bất thường nhấ t trong chuỗ i th ời gian dạng luồng
Luận án trình bày một phương pháp phát hiện chuỗi con bất thường trong dữ liệu thời gian dạng luồng, sử dụng độ đo Euclid Phương pháp này áp dụng một ngưỡng chặn dưới và một hàm chặn dưới thông qua phép biến đổi giảm số chiều để tối ưu hóa chuỗi thời gian Đồng thời, bộ kỹ thuật UCR-ED được sử dụng để loại bỏ sớm các chuỗi con không bất thường Các thành phần này được điều chỉnh để phù hợp với môi trường luồng, nhằm nâng cao hiệu quả phát hiện.
Cấu trúc của luận án
Luận án được chia thành sáu chương, trong đó Chương 2 cung cấp cơ sở lý thuyết cho các đề xuất Chương 3 giới thiệu ba phương pháp tìm kiếm tương tự trên chuỗi thời gian dạng luồng sử dụng độ đo Euclid Chương 4 trình bày ba đề xuất tương tự nhưng áp dụng độ đo DTW Chương 5 đề xuất một phương pháp dự báo trực tuyến cho chuỗi thời gian dạng luồng Chương 6 tập trung vào phát hiện k chuỗi con bất thường nhất trong chuỗi thời gian Cuối cùng, Chương 7 tổng kết các phương pháp đã đề xuất, nêu bật những đóng góp của luận án và thảo luận về các hạn chế cùng hướng nghiên cứu tương lai.
Phụ lục A sẽ trình bày một số phương pháp và giải thuật phức tạp liên quan đến nghiên cứu trong luận án, bao gồm hai phương pháp sử dụng cấu trúc chỉ mục đa mức phân giải để hỗ trợ tìm kiếm tương tự trên chuỗi thời gian, cùng với giải thuật UCR-DTW.
CƠ SỞ LÝ THUYẾT NỀN TẢNG
Độ đo tương tự
Tính khoảng cách giữa hai đối tượng A và B trong tập dữ liệu chuỗi thời gian là tác vụ quan trọng nhất để giải quyết bài toán tìm kiếm tương tự.
Khi A và B càng giống nhau, khoảng cách giữa chúng càng gần 0; ngược lại, nếu chúng khác nhau, khoảng cách sẽ lớn hơn A và B được coi là tương tự khi khoảng cách nhỏ hơn một ngưỡng đã định Do đó, việc tìm kiếm sự tương tự trong dữ liệu chuỗi thời gian được thực hiện theo phương pháp xấp xỉ thay vì chính xác.
Giả sử A và B là hai chuỗi số thực được biểu diễn dưới dạng véc tơ hàng, với A = [a1, a2, …, am] và B = [b1, b2, …, bn] Để tính khoảng cách giữa hai véc tơ này, ta sử dụng hàm D(A, B) để xác định giá trị khoảng cách.
Hàm D tính khoảng cách giữa hai véc tơ phải thỏa ba tính chất sau:
Năm 2008, Ding và các cộng sự đã tiến hành nghiên cứu về tìm kiếm tương tự trên chuỗi thời gian, sử dụng nhiều độ đo tương tự dựa trên khoảng cách để đánh giá hiệu quả của chúng Trong nghiên cứu, các tác giả đã áp dụng độ đo Euclid để thực hiện phân tích.
This thesis explores similarity search in time series data using various distance measures, including Dynamic Time Warping (DTW), Longest Common Subsequence (LCSS), Edit Distance with Real Penalty (ERP), and Edit Distance on Real Sequence (EDR).
15 luồng sẽ sử dụng độ đo Euclid và độ đo DTW do đây là hai độ đo thường được dùng trong khai phá dữ liệu chuỗi thời gian
2.1.1 Độ đo Euclid Độ đo Euclid được thực hiện trên hai véc tơ A và B có số phần tử bằng nhau, nghĩa là m
= n Độ đo này tính khoảng cách của từng cặp điểm của A và B mà tương ứng với nhau theo trục thời gian
Công thức tính độ đo Euclid:
Độ đo Euclid dễ tính toán với độ phức tạp thời gian O(n) và thỏa mãn bất đẳng thức tam giác, bên cạnh ba tính chất tương tự đã được nêu.
D(A, B) < D(A, C) + D(C, B) Vì vậy độ đo Euclid là độ đo trong không gian metric 1
Độ đo Euclid có khả năng thích ứng linh hoạt với kỹ thuật lập chỉ mục và phù hợp với các phép biến đổi giảm số chiều như DFT, DWT và PAA Khi khoảng cách giữa các cặp điểm trong công thức (2.1) được gán trọng số, nó được gọi là khoảng cách Euclid có trọng số.
Hình 2.1 (a) A không tương tự với B bằng độ đo Euclid (b) A tương tự với B bằng độ đo DTW (nguồn [42])
Không gian metric là một tập hợp trong đó khoảng cách giữa các phần tử được xác định rõ ràng Trong không gian này, sự lân cận của các đối tượng được xác định thông qua một hàm khoảng cách, hàm này phải thỏa mãn các tính chất dương, đối xứng và bất đẳng thức tam giác.
Độ đo Euclid có nhược điểm là chỉ áp dụng cho các véc tơ có cùng số chiều và dễ bị ảnh hưởng bởi nhiễu Hình 2.1 (a) cho thấy hai đối tượng A và B có hình dạng tương tự, nhưng do nhiễu, chúng bị lệch pha trên trục thời gian Khi so khớp từng cặp điểm dữ liệu của A và B theo trục thời gian, khoảng cách Euclid giữa hai véc tơ trở nên rất lớn, dẫn đến kết luận rằng hai đối tượng này không tương tự.
2.1.2 Độ đo DTW Độ đo xoắn thời gian động (Dynamic Time Warping (DTW)) có nguồn gốc từ yêu cầu nhận dạng tiếng nói Tiếng nói rất nhạy cảm với các yếu tố như tốc độ nói, nhiễu, v.v
Hai mẫu tiếng nói có thể tương tự nhau nhưng lại lệch pha về trục thời gian do nhiều yếu tố khác nhau Trong trường hợp này, việc áp dụng độ đo Euclid để so sánh sẽ không phát hiện được sự tương tự giữa chúng.
Vào năm 1971, Sakoe giới thiệu phương pháp quy hoạch động tối ưu cho nhận dạng tiếng nói, dựa trên kỹ thuật chuẩn hoá thời gian Kỹ thuật này giúp loại bỏ sự khác biệt về thời gian giữa hai mẫu tiếng nói bằng cách xoắn trục thời gian của một mẫu để tối ưu hóa sự trùng khớp với mẫu còn lại Sau khi chuẩn hoá thời gian, khoảng cách giữa hai mẫu được tính toán và coi là khoảng cách tối thiểu Quy trình xử lý khoảng cách này được thực hiện rất hiệu quả thông qua quy hoạch động.
Vào năm 1994, Berndt và Clifford đã áp dụng độ đo DTW để xác định khoảng cách giữa các chuỗi thời gian, và từ đó, độ đo này đã trở thành một công cụ phổ biến trong lĩnh vực khai thác dữ liệu chuỗi thời gian.
Khác với độ đo Euclid, phương pháp này không so sánh trực tiếp từng cặp điểm giữa hai đường biểu diễn dữ liệu A và B Thay vào đó, nó sử dụng một cách tiếp cận khác để đánh giá sự tương đồng giữa các tập dữ liệu.
B) thì trong độ đo DTW, một điểm của A có thể ánh xạ với nhiều điểm của B và ánh xạ này không thẳng hàng Mục đích của ánh xạ cặp điểm trong độ đo DTW là tìm khoảng cách nhỏ nhất (tối ưu) giữa A và B Hình 2.1 (b) thể hiện rằng mặc dù A và B lệch pha với nhau về trục thời gian nhưng với khả năng ánh xạ cặp điểm không thẳng hàng trong độ đo DTW thì khoảng cách giữa A và B là nhỏ và hai đường biểu diễn dữ liệu này tương
Chuẩn hoá dữ liệu
Chuẩn hoá dữ liệu là quá trình xử lý để chuyển đổi dữ liệu về cùng một tỷ lệ, giúp việc so sánh giữa các dữ liệu trở nên khả thi Ví dụ, khi so sánh nhiệt độ trung bình của hai thành phố trong tháng 9, một thành phố sử dụng độ Celsius và thành phố còn lại sử dụng độ Fahrenheit; việc so sánh chỉ có thể thực hiện được khi dữ liệu được chuẩn hoá về cùng một đơn vị nhiệt độ.
Cho chuỗi thời gian X = {x 1, x 2,…, x n }, có hai cách chuẩn hoá thông dụng cho X:
Chuẩn hóa min-max là phương pháp chuyển đổi giá trị x trong chuỗi thời gian X thành giá trị x norm trong khoảng [0, 1], với x min và x max là giá trị nhỏ nhất và lớn nhất của chuỗi Hai giá trị này được gọi là các hệ số min-max.
𝜎𝜎 với 𝜇𝜇 là giá trị trung bình, và 𝜎𝜎 là độ lệch chuẩn được tính bằng công thức:
𝜇𝜇 và 𝜎𝜎 được gọi là các hệ số z-score
Han và các cộng sự đã chỉ ra rằng việc chuẩn hóa z-score là một công cụ hữu ích trong việc phát hiện các điểm bất thường (outlier), tức là những giá trị quá cao hoặc quá thấp không phản ánh đúng đặc điểm của dữ liệu, có thể xuất phát từ lỗi trong quá trình lấy mẫu.
Cả hai phương pháp chuẩn hóa đều giữ nguyên hình dạng của chuỗi dữ liệu thời gian gốc, nhưng chuẩn hóa z-score tạo ra hình dạng chuỗi chuẩn hóa gần giống với chuỗi dữ liệu ban đầu hơn Do đó, chuẩn hóa z-score thường được ưa chuộng hơn trong khai phá dữ liệu chuỗi thời gian Tuy nhiên, gần đây, nhiều ứng dụng khai phá dữ liệu chuỗi thời gian cũng đã bắt đầu sử dụng chuẩn hóa min-max vì một số lý do nhất định.
Chuẩn hóa z-score không đảm bảo rằng các chuỗi chuẩn hóa có biên độ dao động nằm trong một miền trị xác định trước Ví dụ, trong xử lý hình ảnh, cường độ điểm ảnh cần được chuẩn hóa trong khoảng từ 0 đến 255 cho dải màu RGB, hoặc một số thuật toán mạng nơ ron yêu cầu dữ liệu nằm trong miền giá trị [0, 1] Do đó, chuẩn hóa min-max được áp dụng để đảm bảo các giá trị chuẩn hóa nằm trong miền giá trị đã định sẵn.
Chuẩn hóa min-max có chi phí tính toán thấp hơn so với chuẩn hóa z-score do chi phí tìm hệ số min-max ít hơn Hệ số min-max được xác định sau khi duyệt qua tất cả các phần tử của chuỗi thời gian, trong khi chuẩn hóa z-score yêu cầu thêm hai phép tính: tính giá trị trung bình μ và độ lệch chuẩn σ theo công thức (2.6).
Hình 2.3 Hai kiểu chuẩn hoá thường được dùng trong khai phá dữ liệu chuỗi thời gian
Định nghĩa tìm kiếm tương tự trên chuỗi thời gian
Theo Agrawal và các cộng sự, trong các nhiệm vụ tìm kiếm tương tự trên chuỗi thời gian tĩnh, có hai loại so trùng chính Định nghĩa 2.1 nêu rõ về so trùng toàn bộ chuỗi (Whole matching), trong đó, người ta tìm kiếm các chuỗi thời gian tương tự với chuỗi truy vấn có chiều dài bằng nhau Định nghĩa 2.2 đề cập đến so trùng chuỗi con (Subsequence matching), nơi mà chuỗi thời gian có chiều dài lớn hơn chuỗi truy vấn, và mục tiêu là tìm các chuỗi con trong chuỗi thời gian tương tự với chuỗi truy vấn.
Định nghĩa tìm kiếm tương tự trên chuỗi thời gian dạng luồng
Cho X là một chuỗi thời gian dạng luồng được thể hiện bằng một dãy các số thực x 1, x 2,…, x n … với x n là giá trị được ghi nhận tại mốc thời gian (time tick) mới nhất là n
Chuỗi thời gian X là một chuỗi đơn biến đang tiến triển, với sự gia tăng của n tại mỗi mốc thời gian Định nghĩa X[x s : x e ] là chuỗi con bắt đầu từ mốc thời gian s đến mốc thời gian e, trong khi NX[nx s : nx e ] là chuỗi chuẩn hóa tương ứng của X Chuỗi truy vấn Y[y 1 : y m ], hay còn gọi là mẫu, có độ dài m, và chuỗi chuẩn hóa của Y được ký hiệu là NY[ny 1 : ny m ].
Trong tìm kiếm tương tự cho chuỗi thời gian X, nhiệm vụ chính là xác định chuỗi con X[x s : x e ] có khoảng cách D(NX, NY) nhỏ nhất, tức là chuỗi chuẩn hóa NX gần nhất với chuỗi chuẩn hóa NY Khoảng cách nhỏ nhất này được gọi là giá trị bsf của Y, và chuỗi con X[x s : x e ] là chuỗi tương tự nhất với Y Bên cạnh đó, tìm kiếm k lân cận gần nhất (k nearest neighbor search) nhằm xác định tập hợp k chuỗi con X[x s : x e ] có chuỗi chuẩn hóa NX tương tự với NY Các chuỗi con này cần đáp ứng các tiêu chí nhất định để đảm bảo tính chính xác trong việc tìm kiếm.
22 cận gần nhất chứa k chuỗi con này Nếu có một chuỗi con 𝑈𝑈 ∉ 𝑘𝑘-𝑁𝑁𝑁𝑁 thì ∀𝑉𝑉 ∈ 𝑘𝑘-𝑁𝑁𝑁𝑁 ta có D(NV, NY) ≤ D(NU, NY)
Khi k = 1, tìm kiếm k lân cận gần nhất trở thành phương pháp tìm kiếm chuỗi con tốt nhất hiện tại Định nghĩa tìm kiếm vùng (Range search) là tìm kiếm bất kỳ chuỗi con X[x s : x e ] nào mà chuỗi chuẩn hóa NX của nó thỏa mãn điều kiện D(NX, NY) ≤ ε với một ngưỡng khoảng cách ε đã cho.
ε được coi là bán kính truy vấn vùng của Y Các chuỗi con tương tự có thể chồng lấp lên nhau, do đó tìm kiếm vùng được điều chỉnh thành truy vấn tách rời Điều này có nghĩa rằng trong số tất cả các chuỗi con tương tự chồng lấp, truy vấn tách rời chỉ giữ lại chuỗi con có giá trị D(NX, NY) nhỏ nhất.
Tăng tốc trong tính toán độ đo tương tự
Việc tính toán khoảng cách giữa hai chuỗi thời gian thường tốn nhiều thời gian trong quá trình tìm kiếm tương tự, dẫn đến nhiều nghiên cứu nhằm giảm chi phí tính toán Nổi bật trong số đó là bộ kỹ thuật UCR (UCR suite) được giới thiệu vào năm 2012, cho thấy khả năng tăng tốc tính toán khoảng cách một cách đáng kể Bộ kỹ thuật này bao gồm các phương pháp tăng tốc tính toán khoảng cách hiệu quả.
2.5.1 S ử dụng bình phương khoảng cách Độ đo Euclid sử dụng phép tính căn bậc hai; tuy nhiên, nếu bỏ qua phép tính này, thứ hạng tương đối của các chuỗi con tương tự với chuỗi truy vấn không thay đổi vì hàm tính khoảng cách Euclid có tính đơn điệu và lõm (monotonic and concave) Việc không tính căn bậc hai làm cho việc tính toán khoảng cách Euclid nhanh hơn
2.5.2 T ừ b ỏ s ớ m trong khi tính khoảng cách Euclid
Trong quá trình tính toán khoảng cách Euclid, nếu tổng các bình phương khoảng cách chênh lệch giữa các cặp điểm dữ liệu của hai chuỗi thời gian vượt quá ngưỡng khoảng cách, quá trình tính toán sẽ dừng lại Ngưỡng này được sử dụng để xác định độ tương đồng giữa hai chuỗi thời gian Ý tưởng từ bỏ sớm (early abandoning) cũng được áp dụng trong tính toán khoảng cách DTW.
Thông thường, khoảng cách giữa hai chuỗi thời gian được tính từ trái sang phải, và việc từ bỏ sớm cũng diễn ra theo thứ tự này Tuy nhiên, có một cách khác để tối ưu hóa quá trình từ bỏ sớm, đó là dựa trên biên độ giảm dần của các điểm dữ liệu trong chuỗi thời gian.
Gọi D là hàm đo khoảng cách giữa hai chuỗi thời gian và F là hàm thu giảm số chiều hoặc rút trích đặc trưng của chuỗi thời gian Để xác định xem chuỗi thời gian C có phải là chuỗi ứng viên tương tự với chuỗi truy vấn Q hay không, ta cần sử dụng hàm chặn dưới d F Hàm d F được coi là có tính chất chặn dưới nếu nó thoả mãn một số điều kiện nhất định.
Hàm chặn dưới d F có độ phức tạp thời gian và không gian thấp hơn đáng kể so với hàm tính khoảng cách D, cho phép phát hiện sớm các chuỗi thời gian không tương tự với chuỗi truy vấn với chi phí tính toán thấp Nếu C là chuỗi con của một chuỗi thời gian và thỏa mãn bất đẳng thức (2.7), thì C được gọi là chuỗi con ứng viên.
Hiệu quả của hàm d F được đánh giá qua khả năng cắt tỉa (pruning power), tức là nếu d F có khả năng cắt tỉa cao, nó sẽ phát hiện sớm một số lượng lớn chuỗi ứng viên không tương tự với Q, từ đó loại bỏ chúng khỏi tập kết quả Gọi g là số chuỗi ứng viên bị loại bỏ sớm bởi d F và G là tổng số chuỗi ứng viên, khả năng cắt tỉa của d F được định nghĩa dựa trên tỷ lệ này.
Khi áp dụng các kỹ thuật loại bỏ khoảng cách không cần thiết, nên sắp xếp chúng theo thứ tự xếp tầng, với kỹ thuật có độ phức tạp thời gian thấp nhất được thực hiện trước Nếu kỹ thuật đầu tiên không phát hiện được các ứng viên có thể loại bỏ, thì sẽ chuyển sang kỹ thuật tiếp theo có độ phức tạp d F (F(C), F(Q)) ≤ D(C, Q).
Khi áp dụng phương pháp sử dụng 24 gian thấp nhất kế tiếp, các kỹ thuật sẽ được triển khai theo thứ tự tăng dần về độ phức tạp thời gian Điều này cho phép các ứng viên không phù hợp được loại bỏ sớm nhất, giúp giảm thiểu chi phí tính toán.
Các kỹ thuật tăng tốc chuyên biệt cho độ đo DTW
Các kỹ thuật chuyên biệt này thường thuộc ba loại sau:
2.6.1 Gi ớ i h ạn s ự ghép đôi các điể m
Kỹ thuật này nhằm hạn chế số lượng các ô được đánh giá trong ma trận chi phí tích lũy
Có hai phương pháp tiêu biểu cho kỹ thuật DTW trong nhận dạng tiếng nói là hình bình hành Itakura và dải Sakoe-Chiba Các tác giả đã điều chỉnh thuật toán DTW để đảm bảo rằng một điểm dữ liệu trong chuỗi thời gian chỉ có thể ghép đôi với một số điểm lân cận gần gũi, thay vì các điểm quá xa Ví dụ, trong hình minh họa, một điểm dữ liệu của chuỗi C có thể ghép cặp với tối đa 7 điểm lân cận.
Q Vì vậy đường xoắn P trong ma trận chi phí tích lũy bị giới hạn trong một vùng cố định xung quanh đường chéo chính của ma trận Do đó độ phức tạp thời gian và không gian của độ đo DTW đã giảm một cách đáng kể
(a) (b) Hình 2.4 (a) Ghép đôi các điểm dữ liệu của C và Q bằng độ đo DTW và dải Sakoe-
Chibavới độ rộng w = 3 (b) Đường xoắn P bị giới hạn bởi w
Dải Sakoe-Chiba được ưa chuộng nhờ tính đơn giản và hiệu quả trong việc tăng tốc tính toán khoảng cách DTW Hình 2.4 (b) minh họa dải Sakoe-Chiba với độ rộng w = 3, tạo ra một cửa sổ xoắn giữa hai đường song song với đường chéo chính Điều này giúp dải Sakoe-Chiba ngăn ngừa hiện tượng đường xoắn trong quá trình tính toán.
P có thể biến dạng một cách kỳ lạ khi một điểm dữ liệu trong chuỗi thời gian được kết hợp với quá nhiều điểm dữ liệu từ chuỗi thứ hai, như minh họa trong Hình 2.2.
Keogh và Ratanamahatana đã chỉ ra rằng việc giới hạn kích thước của cửa sổ xoắn không chỉ giúp tăng tốc độ tính toán khoảng cách DTW, mà còn giảm thiểu phần ma trận chi phí tích lũy cần thiết phải tính toán, đồng thời làm chặt chẽ tính chất chặn dưới của công thức.
Silva và các cộng sự (2018) đã phát triển một kỹ thuật tăng tốc cho phép tính toán độ đo DTW bằng cách loại bỏ các cặp điểm không hứa hẹn giữa hai chuỗi thời gian Họ cải tiến khả năng loại bỏ sớm các chuỗi con không tương tự với chuỗi truy vấn trong bộ kỹ thuật UCR-DTW thông qua việc áp dụng kỹ thuật PrunedDTW Kết quả thực nghiệm cho thấy phương pháp của họ chỉ nâng cao hiệu quả tìm kiếm tương tự khi chiều dài chuỗi truy vấn và ràng buộc xoắn (warping constraint) lớn, trong đó ràng buộc xoắn được xác định bởi độ rộng w của dải Sakoe-Chiba.
2.6.2 Hàm ch ặn dưới cho DTW
Có hai hàm chặn dưới thường được sử dụng:
Hàm chặn dưới LB_Kim, được giới thiệu bởi Kim và các cộng sự, sử dụng bốn cặp điểm đặc trưng để tính khoảng cách giữa hai chuỗi thời gian.
Hình 2.5 LB_ Kim trên C và Q đã được chuẩn hoá
Rakthanmanon và các cộng sự cho rằng khi các chuỗi thời gian được chuẩn hóa, khoảng cách giữa điểm có giá trị lớn nhất và nhỏ nhất thường rất nhỏ, vì vậy có thể bỏ qua hai cặp điểm này Do đó, độ phức tạp thời gian của thuật toán LB_Kim được giảm thiểu.
O(1) Hình 2.5 minh hoạ hàm chặn dưới LB_ Kim sử dụng cặp điểm đầu tiên và cặp điểm cuối cùng của C và Q
Hàm chặn dưới LB_ Keogh, được giới thiệu bởi Keogh và Ratanamahatana, hoạt động trên hai chuỗi thời gian có chiều dài tương đương, tức là |C|.
Các tác giả nhận thấy rằng hầu hết các ứng dụng sử dụng độ đo DTW để so sánh hai chuỗi thời gian đều có đường xoắn bị giới hạn toàn cục, tức là các chỉ số i và j trong p k = (i, j) k bị ràng buộc bởi j - w ≤ i ≤ j + w, với w là một yếu tố độc lập trong trường hợp dải Sakoe-Chiba Dựa trên điều này, chúng tôi xây dựng hai chuỗi thời gian U và L, tương ứng là đường cận trên và đường cận dưới của Q, sao cho U và L tạo thành một hình bao mà Q phải nằm bên trong Điểm dữ liệu của chuỗi thời gian U và L được tính bằng công thức: u i = max{q i - w , q i – w + 1,…, q i + w - 1 , q i + w } và l i = min{q i - w , q i – w + 1,…, q i + w - 1 , q i + w }.
Hàm chặn dưới LB_ Keogh được minh hoạ trong Hình 2.6, cho thấy cách tính toán giữa hai chuỗi C và Q, với hình bao Q được xác định bởi U và L Hàm này tổng hợp khoảng cách của các điểm dữ liệu trong C nằm ngoài hình bao Q Các tác giả khẳng định rằng LB_ Keogh hoạt động hiệu quả trên hai chuỗi thời gian có chiều dài tương đương, đồng thời đường xoắn bị giới hạn bởi độ rộng w của dải Sakoe-Chiba sẽ không gây ra lỗi tìm sót.
Hình 2.6 LB_ Keogh trên C và Q có cùng chiều dài là n, do đó độ phức tạp thời gian của hàm chặn dưới này là O(n)
27 giới thiệu, độ đo DTW đã trở thành một công cụ rất mạnh trong khai phá dữ liệu chuỗi thời gian
Khi C và Q có cùng chiều dài và ta có U và L của Q, hàm LB_ Keogh được định nghĩa:
Từ hàm chặn dưới LB_ Keogh , Rakthanmanon và các cộng sự [25] đề xuất hàm chặn dưới
LB_ Keogh nghịch (reversed LB_ Keogh ) Trong hàm chặn dưới này, vai trò của C và Q trong
Trong nghiên cứu, LB_ Keogh được so sánh với hình bao của C như trong Hình 2.7 Các tác giả áp dụng LB_ Kim, LB_ Keogh và LB_ Keogh nghịch theo kiểu xếp tầng trong bộ kỹ thuật UCR-DTW để tìm kiếm tương tự trên chuỗi thời gian tĩnh bằng độ đo DTW Đáng chú ý, trong UCR-DTW, hàm chặn dưới LB_ Keogh nghịch chỉ được gọi khi cần thiết, tức là theo cách "just-in-time" Khi LB_ Kim và LB_ Keogh không phát hiện được các chuỗi con không tương tự với chuỗi truy vấn, LB_ Keogh nghịch sẽ được sử dụng Nhờ đó, bộ kỹ thuật UCR-DTW có tốc độ thực hiện rất nhanh.
Ratanamahatana và Keogh cho rằng việc sắp đặt các hàm chặn dưới theo kiểu xếp tầng giúp tăng tốc độ tính toán khoảng cách DTW đáng kể, gần như đạt đến giới hạn tối đa.
2.6.3 T ừ b ỏ s ớ m trong khi tính khoảng cách D TW
Hàm chặn dưới LB_ Keogh có khả năng hỗ trợ việc từ bỏ sớm trong quá trình tính toán khoảng cách DTW Khi áp dụng thuật toán chân phương cho đo lường DTW, hiệu suất tính toán sẽ được cải thiện đáng kể.
(2.10) Hình 2.7 LB_ Keogh nghịch trên C và Q
Khoảng cách DTW được tính toán theo thứ tự từ trái sang phải giữa hai chuỗi thời gian C và Q, với k là chỉ số xác định Tổng tích lũy DTW đến k cùng với sự đóng góp của từng phần tử sẽ được xem xét để đánh giá sự tương đồng giữa các chuỗi.
Các phép biến đổi thu giảm số chiều
Cơ sở dữ liệu chuỗi thời gian có quy mô lớn, dẫn đến chi phí cao trong việc truy xuất và tính toán dữ liệu thô Do đó, việc áp dụng kỹ thuật thu giảm số chiều cho chuỗi thời gian là cần thiết để giảm chi phí quản lý và tính toán Qua phép biến đổi thu giảm số chiều, chuỗi thời gian được đại diện bằng các hệ số đặc trưng, cho phép lưu trữ chỉ k hệ số y1, y2,…, yk thay vì tất cả các giá trị x1, x2,…, xn, với k