GIỚI THIỆU ĐỀ TÀI
Dữ liệu chuỗi thời gian
Trong bối cảnh khoa học kỹ thuật phát triển nhanh chóng, lượng dữ liệu lưu trữ trên các thiết bị điện tử như đĩa cứng, CD-ROM và băng từ ngày càng gia tăng Sự gia tăng này diễn ra với tốc độ chóng mặt, đặt ra thách thức cho con người trong việc khai thác thông tin hữu ích từ khối dữ liệu khổng lồ Do đó, khai phá dữ liệu đã trở thành một vấn đề quan trọng và cần thiết để phục vụ nhu cầu nghiên cứu và sử dụng của con người.
Dữ liệu chuỗi thời gian là một trong những loại dữ liệu quan trọng cần khai thác, được sinh ra từ các thí nghiệm khoa học và hoạt động sản xuất kinh doanh hàng ngày Những ví dụ thực tế về dữ liệu chuỗi thời gian bao gồm giá chứng khoán qua các ngày, giá cả mặt hàng trên thị trường, doanh thu hoặc chi phí của công ty theo thời gian, lượng mưa đo được hàng ngày, và dữ liệu điện tâm đồ Hình 1-1 minh họa cho dữ liệu chuỗi thời gian trong lĩnh vực chứng khoán tại Việt Nam.
Dữ liệu chuỗi thời gian là tập hợp các số thực có thứ tự, mỗi số đại diện cho giá trị tại một thời điểm nhất định Với kích thước lớn, việc khai thác dữ liệu chuỗi thời gian để rút trích thông tin hữu ích ngày càng trở nên cần thiết, thu hút sự quan tâm của nhiều nhà khoa học trong nghiên cứu và ứng dụng.
Dữ liệu chuỗi thời gian là một lĩnh vực nghiên cứu thú vị, nhưng cũng đối mặt với nhiều thách thức, bao gồm kích thước dữ liệu lớn, sự phụ thuộc vào phương pháp đánh giá độ tương tự và tính không đồng nhất của dữ liệu.
Hình 1-1: Dữ liệu chứng khoán Việt Nam được ghi nhận lại.
Phát hiện mô típ trên dữ liệu chuỗi thời gian
Dữ liệu chuỗi thời gian xuất hiện rộng rãi trong nhiều lĩnh vực như khoa học kỹ thuật, kinh tế, tài chính, sinh học và y học Việc tìm kiếm các chuỗi con trong dữ liệu chuỗi thời gian lớn là rất cần thiết, tạo nền tảng cho việc phát triển khai thác dữ liệu hiệu quả hơn Đặc biệt, nhu cầu phát hiện sự lặp lại của các chuỗi con (hay còn gọi là mô típ) trong một chuỗi thời gian lớn đã trở nên quan trọng Hình 1-2 minh họa sự xuất hiện của ba chuỗi con tương tự nhau trong dữ liệu chuỗi thời gian.
Một vài ứng dụng thực tế:
Dự đoán giá vàng, tiền tệ hay chứng khoán dựa vào mô hình biến động giá của nó trong quá khứ
Dự đoán diễn biến của một căn bệnh dựa vào dữ liệu diễn biến của nó trong quá khứ
Nhận dạng những công ty có kiểu mẫu tăng trưởng giống nhau
Xác định những chứng khoán có giá biến động theo một kiểu cách giống nhau
Phát hiện vi phạm bản quyền trong âm nhạc là quá trình xác định xem một đoạn nhạc có giống với các tác phẩm đã được đăng ký bản quyền hay không Điều này giúp bảo vệ quyền lợi của các nghệ sĩ và nhà sản xuất âm nhạc, đồng thời duy trì sự công bằng trong ngành công nghiệp âm nhạc.
Mục tiêu và giới hạn của đề tài
Phát hiện mô típ trong dữ liệu chuỗi thời gian là một vấn đề thú vị và thực tiễn, thu hút sự quan tâm của nhiều nhà khoa học Nhiều nghiên cứu đã đề xuất các giải thuật khác nhau như EMMA, chiếu ngẫu nhiên và Mueen-Keogh để giải quyết vấn đề này Tuy nhiên, một hạn chế phổ biến của các công trình hiện tại là chỉ tập trung vào việc phát hiện các mô típ có chiều dài cố định, yêu cầu chiều dài cần tìm phải được xác định trước Điều này dẫn đến việc các giải thuật chỉ có khả năng phát hiện những mô típ theo chiều dài đã định, bỏ lỡ những mô típ khác với chiều dài khác.
Một thách thức trong việc xác định chiều dài mô típ là độ chính xác thường gặp khó khăn trong thực tế Nếu chiều dài mô típ được chỉ định quá ngắn, chỉ những mô típ nhỏ thuộc một mô típ lớn hơn mới được phát hiện Ngược lại, nếu chiều dài mô típ được cung cấp quá dài, khả năng thuật toán phát hiện mô típ sẽ giảm đi đáng kể.
Với những hạn chế của các giải thuật phát hiện mô típ dựa vào chiều dài cố định, nhu cầu tìm kiếm một giải thuật có khả năng phát hiện mô típ mà không cần biết trước chiều dài trở nên cần thiết Bài viết này sẽ xem xét một giải thuật do Heng Tang và Stephen Liao đề xuất, có khả năng phát hiện tất cả các mô típ với chiều dài khác nhau trong chuỗi thời gian.
Giải thuật này có khả năng phát hiện mô típ mà không cần thông tin trước về dữ liệu Nó dựa trên nền tảng giải thuật chiếu ngẫu nhiên và ma trận đụng độ của các chuỗi con để giải quyết vấn đề.
Trong bài viết này, chúng tôi sẽ tiến hành so sánh kết quả thực nghiệm với thuật toán nhận diện mô típ dựa trên điểm cực trị quan trọng Thuật toán này có khả năng nhận diện các thể hiện của mô típ dù có chiều dài khác nhau và biên độ dao động không giống nhau.
Tóm lược những kết quả thu được
Qua việc nghiên cứu, hiện thực đề tài này và sau đó thử nghiệm trên các tập dữ liệu mẫu, chúng tôi thu được các kết quả sau:
Giải thuật có khả năng phát hiện hầu hết các mô típ có trong dữ liệu chuỗi thời gian được thử nghiệm
Phát hiện được các mô típ có chiều dài khác nhau, các thể hiện trong mô típ cũng có thể có chiều dài khác nhau
Thời gian xử lý dữ liệu khá nhanh đối với các tập dữ liệu vừa và nhỏ, khoảng vài chục ngàn điểm Tuy nhiên, thời gian xử lý sẽ chậm hơn khi làm việc với các tập dữ liệu lớn hoặc khi có sự biến đổi hình thái tương tự xuyên suốt chuỗi thời gian.
Cấu trúc luận văn
Phần còn lại của luận văn được tổ chức theo cấu trúc như sau:
Chương 2 trình bày tổng quan về các công trình liên quan đến bài toán phát hiện mô típ trên dữ liệu chuỗi thời gian
Chương 3 giới thiệu những lý thuyết sẽ được sử dụng để thực hiện đề tài, đồng thời xác định hướng tiếp cận để giải quyết vấn đề của đề tài
Chương 4 tiến hành hiện thực và thực nghiệm giải thuật trên các tập dữ liệu chuỗi thời gian khác nhau Sau đó, chúng tôi so sánh kết quả thu được với giải thuật nhận diện mô típ dựa vào điểm cực trị quan trọng về khả năng phát hiện mô típ có chiều dài khác nhau, độ chính xác, tốc độ của giải thuật
Chương 5 nêu lên một số kết luận sau khi thực hiện đề tài.
TỔNG QUAN CÁC CÔNG TRÌNH LIÊN QUAN
Các độ đo tương tự
Vấn đề then chốt trong bài toán tìm kiếm tương tự trên dữ liệu chuỗi thời gian là cách tính độ tương tự giữa hai chuỗi con Độ tương tự thường được đo bằng khoảng cách, trong đó khoảng cách bằng 0 khi hai chuỗi giống nhau và tăng lên khi chúng khác nhau.
2.1.1 Độ đo Euclid Để xác định độ tương tự của hai chuỗi thời gian, nhiều độ đo tương tự đã được sử dụng Trong đó, độ đo khoảng cách Euclid thường được sử dụng nhất
Cho hai chuỗi thời gian Q = q1,…,qn và C = c1,…,cn độ đo khoảng cách Euclid giữa hai chuỗi thời gian này được cho bởi công thức:
Hình 2-1: Khoảng cách Euclid giữa hai chuỗi thời gian Q và C (Từ nguồn [5])
Phương pháp tính độ tương tự giữa hai chuỗi thời gian bằng độ đo khoảng cách Euclid được thể hiện rõ qua Hình 2-1 Độ đo này nổi bật với tính đơn giản, dễ hiểu và dễ tính toán, đồng thời có khả năng mở rộng cho nhiều bài toán khai thác dữ liệu chuỗi thời gian như gom cụm và phân lớp Ngoài ra, nó cũng tương thích với các phương pháp thu giảm số chiều như DFT, DWT, PAA và APCA Tuy nhiên, độ đo khoảng cách Euclid có nhược điểm là nhạy cảm với nhiễu và không phù hợp khi dữ liệu có đường cơ bản khác nhau.
2.1.2 Độ đo xoắn thời gian động
Khi chuỗi thời gian có hình dạng không hoàn toàn giống nhau nhưng có sự biến đổi tương tự, khoảng cách Euclid không còn phù hợp để đo lường Thay vào đó, độ đo xoắn thời gian động (Dynamic Time Warping - DTW) được sử dụng, một phương pháp được Bernt và Clifford đề xuất vào năm 1994 DTW cho phép ánh xạ một điểm với nhiều điểm khác mà không cần phải thẳng hàng, thay vì chỉ tính khoảng cách từng cặp điểm 1-1 Chi tiết về DTW được trình bày trong tài liệu tham khảo.
Hình 2-2: Độ đo xoắn thời gian động (nguồn [17])
Hình 2-2 thể hiện một cách trực quan phương pháp tính độ tương tự của hai chuỗi thời gian sử dụng độ đo xoắn thời gian động
Phương pháp DTW (Dynamic Time Warping) mang lại độ chính xác cao hơn so với đo lường Euclid DTW có khả năng nhận diện các mẫu có hình dạng tương tự nhưng không hoàn toàn giống nhau, đồng thời cho phép xử lý các hình dạng có chiều dài thời gian khác nhau.
Mặc dù phương pháp DTW mang lại hiệu quả cao trong việc tìm kiếm tương tự, nhưng nó cũng có nhược điểm là thời gian chạy lâu do tính phức tạp hơn so với độ đo Euclid Để khắc phục vấn đề này, nhiều nghiên cứu gần đây đã được thực hiện nhằm cải thiện tốc độ tìm kiếm với độ đo DTW.
2.1.3Độ đo chuỗi con chung dài nhất
Chuỗi con chung dài nhất (Longest Common Subsequence - LCS) là một phương pháp tính toán độ tương tự giữa các chuỗi, được giới thiệu bởi Vlachos và các cộng sự vào năm 2004.
Phương pháp LCS tập trung vào việc xác định các chuỗi con chung giữa hai chuỗi dài hơn, với độ dài chuỗi con chung càng lớn thì mức độ tương đồng giữa hai chuỗi càng cao Thông tin chi tiết về phương pháp này được trình bày trong tài liệu [9].
Trong bài viết này, chúng ta xem xét hai chuỗi X và Y, với X = 3, 2, 5, 7, 4, 8, 10, 7 và Y = 2, 5, 4, 7, 3, 10, 8, 6 Chuỗi con chung dài nhất (LCS) giữa hai chuỗi này là 2, 5, 7, 10, với độ tương tự giữa X và Y được tính là Sim(X, Y) = |LCS| = 4 Một trong những ưu điểm nổi bật của phương pháp LCS là khả năng bỏ qua những điểm bất thường khi thực hiện so sánh.
Các phương pháp thu giảm số chiều
Dữ liệu chuỗi thời gian thường có kích thước lớn, gây khó khăn trong việc tìm kiếm và phân tích Để cải thiện hiệu quả và giảm chi phí, cần thực hiện thu giảm số chiều của dữ liệu Bài viết này sẽ khám phá hai phương pháp thu giảm số chiều: phương pháp biến đổi sang miền tần số và phương pháp xấp xỉ từng đoạn.
2.2.1Các phương pháp biến đổi sang miền tần số
2.2.1.1Phương pháp biến đổi Fourier rời rạc
Phương pháp biến đổi Fourier rời rạc (DFT) là một kỹ thuật quan trọng trong xử lý ảnh và tín hiệu số, được Agrawal và các cộng sự giới thiệu vào năm 1993 DFT được sử dụng rộng rãi nhờ khả năng phân tích và xử lý dữ liệu hiệu quả.
Trong phương pháp biến đổi Fourier thì đường dữ liệu ban đầu được biểu diễn bởi các đường cơ bản là sin và cosin
C(t) đại diện cho chuỗi dữ liệu kết quả, trong khi A k và B k là các hệ số biến đổi đặc trưng cho chuỗi dữ liệu ban đầu Phương pháp này được minh họa rõ ràng trong hình 2.
Phương pháp DFT có nhiều ưu điểm, bao gồm khả năng phù hợp với các loại đường biểu diễn dữ liệu khác nhau, khả năng nén dữ liệu hiệu quả và khả năng chịu nhiễu tốt Nó cho phép so sánh gián tiếp hai chuỗi dữ liệu X và Y thông qua khoảng cách giữa hai chuỗi đã được biến đổi là Xf và Yf Bên cạnh đó, DFT còn hỗ trợ nhiều phương pháp lập chỉ mục như F-index và ST-index.
Nhược điểm lớn nhất của phương pháp này là khó giải quyết khi các chuỗi thời gian có chiều dài khác nhau
2.2.1.2Phương pháp biến đổi Wavelet rời rạc
Phương pháp biến đổi Wavelet rời rạc (Discrete Wavelet Transform), còn gọi là DWT, là một phương pháp thu giảm số chiều do K Chan và W Fu đề xuất năm
Năm 1999, phương pháp biến đổi wavelet rời rạc (DWT) đã được giới thiệu như một sự thay thế cho biến đổi Fourier rời rạc (DFT) bằng cách sử dụng các đường cơ bản như Haar, Daubechies, Coiflet và Symmlet thay vì các hàm lượng giác sin hay cosin Đường Haar ψ i f được định nghĩa bởi công thức ψ i f(t) = 1 với 0≤ t < 0.5, như minh họa trong hình 2-3 (b).
Phương pháp biến đổi Wavelet rời rạc nổi bật với hiệu quả cao nhờ vào khả năng mã hóa đơn giản và nhanh chóng, với độ phức tạp giải thuật ở mức tuyến tính Bên cạnh đó, phương pháp này còn có khả năng khử nhiễu vượt trội, đặc biệt phù hợp cho những dữ liệu tĩnh ít thay đổi, do đặc tính không thay đổi liên tục của đường Haar.
Phương pháp DWT có nhược điểm là chỉ hoạt động hiệu quả khi chuỗi dữ liệu ban đầu có chiều dài là lũy thừa 2 Ngoài ra, chiều dài của chuỗi con truy vấn cũng cần phải là lũy thừa 2 để đảm bảo thuật toán hoạt động hiệu quả.
Hình 2-3: Các phương pháp biến đổi sang miền tần số (nguồn [17])
2.2.2 Các phương pháp xấp xỉ từng đoạn
2.2.2.1 Phương pháp xấp xỉ tuyến tính từng đoạn
Phương pháp xấp xỉ tuyến tính từng đoạn (Piecewise Linear Approximation - PLA) được đề xuất bởi E Keogh và các cộng sự, cho phép biểu diễn dữ liệu ban đầu bằng chuỗi các đoạn thẳng tuyến tính Mỗi đoạn thẳng nối hai điểm ở đầu đoạn để xấp xỉ tốt nhất những điểm trong phân đoạn chuỗi thời gian Các đoạn thẳng này có thể rời nhau hoặc liên tục, giúp giảm số chiều của dữ liệu một cách hiệu quả PLA không chỉ mang lại biểu diễn trực quan mà còn phù hợp để nén các loại dữ liệu chuỗi thời gian khác nhau Một ưu điểm nổi bật của phương pháp này là khả năng tìm kiếm các chuỗi đoạn thẳng nhanh chóng trong thời gian tuyến tính.
2.2.2.2Phương pháp xấp xỉ gộp từng đoạn
Phương pháp xấp xỉ gộp từng đoạn (Piecewise Aggregate Approximation), còn gọi là PAA, do E Keogh và cộng sự đề xuất năm 2001 [3]
Phương pháp PAA (Piecewise Aggregate Approximation) là một kỹ thuật đơn giản, trong đó k điểm liền kề được ánh xạ thành cùng một giá trị thông qua trung bình cộng Quá trình này diễn ra từ trái sang phải, tạo ra một đường thẳng dạng bậc thang Hình 2-4 (b) minh họa việc giảm số chiều sử dụng phương pháp này Ưu điểm nổi bật của PAA là thời gian tính toán nhanh chóng, đồng thời hỗ trợ nhiều độ đo tương tự khác nhau như Euclid và DTW.
Nhược điểm của PAA là việc khó khôi phục chuỗi ban đầu, dẫn đến khả năng xuất hiện lỗi lớn Phương pháp này không chú trọng đến các đặc điểm quan trọng như điểm cực trị trong từng đoạn xấp xỉ.
2.2.2.3Phương pháp xấp xỉ hằng số từng đoạn thích nghi
Phương pháp xấp xỉ hằng số từng đoạn thích nghi (Adaptive Piecewise Constant Approximation - APCA) được giới thiệu bởi E Keogh và các cộng sự vào năm 2001 APCA tương tự như phương pháp PAA, đều xấp xỉ dữ liệu thành các đoạn thẳng nằm ngang, nhưng khác biệt ở chỗ kích thước của các đoạn trong APCA không đồng nhất mà phụ thuộc vào đặc điểm của dữ liệu Những khu vực có biến động lớn sẽ được chia thành các đoạn ngắn, trong khi những khu vực ít biến động hơn sẽ được phân thành các đoạn dài hơn Hình 2-4 (c) minh họa quá trình giảm số chiều bằng phương pháp APCA Một trong những ưu điểm nổi bật của APCA là tỷ lệ nén dữ liệu cao hơn và tỷ lệ lỗi khi khôi phục dữ liệu thấp hơn so với PAA.
Nhược điểm của phương pháp APCA là thời gian tính toán lâu hơn Độ phức tạp của phương pháp này là O(nlog(n))
Hình 2-4: Các phương pháp xấp xỉ từng đoạn (nguồn [17]).
Tổng quan về các công trình liên quan
Phát hiện mô típ trên dữ liệu chuỗi thời gian là một bài toán thu hút sự quan tâm của nhiều nhà khoa học, dẫn đến nhiều nghiên cứu và giải thuật khác nhau nhằm tìm ra lời giải Tuy nhiên, hầu hết các nghiên cứu hiện tại chỉ tập trung vào việc phát hiện mô típ đã biết hoặc có chiều dài cố định trong chuỗi thời gian Một số giải thuật nổi bật trong lĩnh vực này bao gồm EMMA, giải thuật chiếu ngẫu nhiên và Mueen-Keogh.
Giải thuật EMMA, được phát triển bởi Jessica Lin và các cộng sự vào năm 2002, nhằm cải tiến giải thuật Brute Force trong việc tìm kiếm mô típ Để sử dụng giải thuật này, cần cung cấp các thông số đầu vào như chuỗi thời gian T, chiều dài n của cửa sổ trượt, hằng số dương R thể hiện phạm vi lân cận của chuỗi con, chiều dài chuỗi ký tự w khi ánh xạ sang dạng ký tự với giải thuật SAX, và độ lớn a của bảng chữ cái cho SAX Quá trình bắt đầu bằng việc chia chuỗi thời gian thành nhiều chuỗi con thông qua cửa sổ trượt, sau đó giảm số chiều của các chuỗi con bằng phương pháp PAA và chuyển đổi chúng sang dạng chuỗi ký tự bằng phương pháp SAX.
Sau khi chuẩn hóa các chuỗi con thành chuỗi ký tự, một hàm băm được áp dụng để phân loại chúng vào từng nhóm riêng biệt Nhóm có số lượng chuỗi con nhiều nhất sẽ là ứng cử viên hàng đầu trong việc tìm kiếm mô típ.
Giải thuật EMMA tìm kiếm mô típ trong nhóm có nhiều chuỗi con nhất bằng cách sử dụng khoảng cách Euclid để tính toán độ tương tự giữa các chuỗi con Nếu không tìm thấy mô típ, giải thuật sẽ tiếp tục xem xét nhóm có số lượng chuỗi con nhiều thứ hai cho đến khi mô típ được xác định Ưu điểm nổi bật của EMMA là việc áp dụng khoảng cách Euclid đơn giản và sử dụng hàm băm để phân chia nhóm, giúp giảm số lần tính toán khoảng cách So với giải thuật Brute Force, EMMA cho thấy hiệu quả vượt trội hơn.
Giải thuật EMMA có một số hạn chế, bao gồm việc cần xác định trước chiều dài của mô típ, điều này thường rất khó khăn Ngoài ra, để thực hiện giải thuật, cần cung cấp hằng số R, mà tốc độ của giải thuật phụ thuộc vào giá trị này Nếu lựa chọn giá trị không hợp lý, tốc độ tìm kiếm lời giải sẽ bị chậm lại Hạn chế khác là giải thuật chỉ có khả năng phát hiện một mô típ duy nhất, không thể nhận diện tất cả các mô típ trong chuỗi thời gian đang được xem xét.
2.3.2Giải thuật chiếu ngẫu nhiên
Vào năm 2003, Bill Chiu, Eamonn Keogh và các cộng sự đã áp dụng giải thuật chiếu ngẫu nhiên (Random Projection) để phát hiện mô típ trong dữ liệu chuỗi thời gian Giải thuật này được phát triển dựa trên nghiên cứu trước đó, nhằm tạo ra một phương pháp mới có khả năng tìm kiếm mô típ ngay cả khi có sự xuất hiện của nhiễu.
Giải thuật áp dụng phương pháp PAA để giảm số chiều của chuỗi thời gian và sử dụng phương pháp SAX để chuyển đổi chuỗi con thành chuỗi ký tự Các chuỗi con sau khi được mã hóa sẽ được sắp xếp vào một ma trận, trong đó mỗi chuỗi con tương ứng với một dòng của ma trận này.
Sau khi xây dựng ma trận, quá trình chiếu ngẫu nhiên sẽ được thực hiện để tạo ra ma trận đụng độ (CM) với các chuỗi con làm dòng và cột Ban đầu, tất cả các ô trong ma trận CM đều có giá trị 0 Giải thuật sẽ lặp lại k lần, trong mỗi lần lặp, một số cột ngẫu nhiên sẽ được chọn làm mặt nạ Giá trị của các chuỗi con tương ứng với mặt nạ sẽ được tính toán qua một hàm băm, và các chuỗi con có giá trị giống nhau sẽ được nhóm vào cùng một túi Nếu hai chuỗi con i và j được băm vào cùng một túi, giá trị ô (i,j) trong ma trận CM sẽ được tăng lên 1 Quá trình này tiếp tục cho đến khi hoàn tất k lần lặp, cho ra ma trận đụng độ cuối cùng Thông tin chi tiết về giải thuật chiếu ngẫu nhiên sẽ được trình bày trong chương 3.
Hai chuỗi con ứng với ô có giá trị lớn nhất trong ma trận sẽ là ứng cử viên hàng đầu cho mô típ Để xác định xem hai chuỗi con đó có phải là mô típ hay không, thuật toán sẽ tính khoảng cách Euclid giữa chúng Các ô có giá trị lớn tiếp theo cũng có thể được xem xét để tìm kiếm các mô típ mới Một trong những ưu điểm của thuật toán chiếu ngẫu nhiên là khả năng phát hiện mô típ ngay cả trong trường hợp có nhiễu Theo các tác giả, thuật toán này có khả năng phát hiện mô típ với tốc độ nhanh và độ chính xác tương đối cao.
Giải thuật này có nhược điểm chính là yêu cầu cung cấp chiều dài của mô típ, dẫn đến việc không thể phát hiện các mô típ có chiều dài khác nhau Hơn nữa, hiệu quả của giải thuật còn phụ thuộc vào việc xác định số lần lặp chọn mặt nạ và số cột của mặt nạ được sử dụng.
Giải thuật Mueen-Keogh (MK) được phát triển bởi Abdullah Mueen, Eamonn Keogh và các cộng sự vào năm 2009, nhằm phát hiện mô típ trong chuỗi thời gian Mueen-Keogh mang đến một cách tiếp cận mới để xác định các mô típ này.
Giải thuật này hoạt động bằng cách tính toán khoảng cách giữa các chuỗi con để xác định các mô típ Một chuỗi con cụ thể sẽ được chọn làm điểm tham khảo, được gọi là điểm 1 trong hình 2-5 A.
Từ điểm tham khảo, khoảng cách đến các chuỗi con khác được tính toán và sắp xếp vào danh sách tuyến tính theo thứ tự tăng dần khoảng cách so với điểm tham khảo đã chọn.
Hình 2-5: Minh họa ý tưởng giải thuật MK (nguồn [6])
Trong quá trình sắp xếp thứ tự các chuỗi con, khoảng cách tương đối giữa chúng được xác định dựa trên khoảng cách so với điểm tham khảo Khoảng cách này chỉ là sự khác biệt giữa hai khoảng cách so với điểm tham khảo, không phải là khoảng cách thực tế của các chuỗi con Nói cách khác, khoảng cách tương đối giữa các chuỗi con chính là cận dưới của khoảng cách thực giữa chúng.
Khoảng cách giữa hai chuỗi con trong danh sách đã sắp xếp được gọi là khoảng cách tốt nhất hiện tại (best-so-far) Giải thuật dựa trên giả thuyết rằng hai chuỗi con gần nhau trong thực tế cũng sẽ gần nhau trong danh sách tuyến tính Tuy nhiên, hai chuỗi con gần nhau trong danh sách tuyến tính có thể có khoảng cách thực tế rất xa Giải thuật sẽ kiểm tra các cặp chuỗi con liền kề; nếu khoảng cách tương đối giữa chúng nhỏ hơn khoảng cách tốt nhất hiện tại, khoảng cách thực tế sẽ được tính toán Nếu khoảng cách thực tế này cũng nhỏ hơn khoảng cách tốt nhất hiện tại, nó sẽ được cập nhật Hình 2-6 minh họa quá trình duyệt và cập nhật khoảng cách tốt nhất hiện tại, và sau khi hoàn tất, mô típ tìm được hai chuỗi con có khoảng cách tốt nhất.
CƠ SỞ LÝ THUYẾT VÀ PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
Định nghĩa
Định nghĩa 1: Chuỗi thời gian
Một chuỗi thời gian T = t 1 ,…,t m là một tập có thứ tự m biến số thực
Một chuỗi thời gian có thể kéo dài rất lâu, nhưng chúng ta thường chỉ tập trung vào các phần nhỏ của nó, được gọi là chuỗi con Chuỗi con là những đoạn nhỏ hơn trong chuỗi thời gian lớn hơn mà chúng ta phân tích.
Cho chuỗi thời gian T có chiều dài m, một chuỗi con C của T là một lấy mẫu có chiều dài w của các vị trí liên tiếp nhau trong T, ≤
Ta có C = tp,…,tp + w – 1với 1 ≤ ≤ − + 1
Mọi chuỗi con đều có khả năng trở thành mô típ, vì vậy bất kỳ thuật toán nào phát hiện mô típ cần phải trích xuất tập hợp các chuỗi con từ một chuỗi thời gian Việc này có thể được thực hiện thông qua phương pháp cửa sổ trượt.
Cho chuỗi thời gian T có chiều dài m và một chuỗi con có chiều dài w, ta xây dựng ma trận S chứa tất cả các chuỗi con có thể của T bằng cách sử dụng cửa sổ trượt dài w Mỗi chuỗi con Cp sẽ được đặt tại dòng thứ p của ma trận, dẫn đến kích thước ma trận S là (m – w + 1) x w Hình 3-1 minh họa quá trình xác định các chuỗi con từ chuỗi thời gian T thông qua cửa sổ trượt này.
Hình 3-1: Xác định các chuỗi con của chuỗi thời gian bằng cách dùng cửa sổ trượt có kích thước w (Từ nguồn [7]) Định nghĩa 4: Trùng
Cho một tập hợp các số thực dương R, 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 khoảng cách giữa C và M, được xác định bởi hàm D(C,M), nhỏ hơn hoặc bằng một giá trị nhất định, thì chuỗi M được coi là trùng với chuỗi C Hình 3-2 minh họa sự xuất hiện của hai chuỗi con trùng nhau trong dữ liệu chuỗi thời gian.
Hình 3-2: Minh họa chuỗi thời gian T, hai chuỗi con C (nét đậm) và M (nét xám),
M trùng với C (Từ nguồn [4]) Định nghĩa 5: Trùng tầm thường
Trong chuỗi thời gian T có chiều dài m, chuỗi con C bắt đầu tại vị trí p và chuỗi con M bắt đầu tại vị trí q được coi là trùng tầm thường của C nếu p = q hoặc không có chuỗi con M’ nào bắt đầu tại vị trí q’ với D(C,M’) > R, trong đó p < q’ < q hoặc q < q’ < p.
Trong phân tích chuỗi thời gian, các chuỗi con lệch một hoặc hai điểm so với chuỗi con gốc được gọi là trùng tầm thường Hình 3-3 minh họa rõ nét hiện tượng này Để tối ưu hóa danh sách các chuỗi con cần xem xét, những chuỗi con trùng tầm thường cần được loại bỏ vì chúng không mang lại giá trị thông tin.
Hình 3-3 minh họa chuỗi thời gian T và chuỗi con C, cùng với hai chuỗi trùng tầm thường của C lệch về bên trái và bên phải một vài điểm Định nghĩa 6 đưa ra khái niệm về mô típ bậc k.
Trong một chuỗi thời gian T, mô típ bậc 1 (hay 1-Motif) được xác định là chuỗi con C1 có số lượng trùng không tầm thường cao nhất Mô típ bậc k (hay K-Motif) là chuỗi con Ck có số lượng trùng không tầm thường cao nhất, với điều kiện rằng khoảng cách D(Ck, Ci) lớn hơn 2R, trong đó 1 ≤ i ≤ k.
Điều kiện D(C k ,C i ) > 2R được áp dụng cho mô típ quan trọng thứ k nhằm ngăn chặn tình trạng chia sẻ thể hiện giữa các mô típ khác Hình 3-4 minh họa sự trùng lặp thể hiện của hai mô típ khi D(Ck,Ci) > R, đồng thời cho thấy sự tách biệt giữa các thể hiện của hai mô típ khác khi áp dụng điều kiện D(C k ,C i ) > 2R trong không gian 2D.
Hình 3-4 minh họa sự trùng lắp và tách biệt giữa các thể hiện của hai mô típ, với D(Ck, Ci) > R trong trường hợp trùng lắp và D(Ck, Ci) > 2R trong trường hợp tách biệt Định nghĩa 7 liên quan đến ma trận đụng độ, cung cấp khung lý thuyết cho việc phân tích mối quan hệ giữa các mô típ.
Ma trận đụng độ CM của chuỗi thời gian T có kích thước q x q, trong đó mỗi phần tử eij được tính bằng công thức eij = collision_hit(si, sj) Hàm collision_hit đo độ tương tự giữa hai chuỗi con si và sj, với 1 ≤ i, j ≤ q, trong đó q là số lượng chuỗi con của T.
Ma trận đụng độ được tạo ra từ giải thuật chiếu ngẫu nhiên Mỗi ô trong ma trận mang giá trị cao thứ k, và hai chuỗi con tương ứng với ô đó sẽ đại diện cho mô típ quan trọng thứ k.
Thu giảm số chiều
Có nhiều phương pháp để giảm số chiều dữ liệu, bao gồm biến đổi Fourier rời rạc (DFT), biến đổi wavelet rời rạc (DWT), xấp xỉ tuyến tính từng đoạn (PLA) và xấp xỉ gộp từng đoạn (PAA) Trong bài viết này, chúng tôi sẽ tập trung vào phương pháp xấp xỉ gộp từng đoạn (PAA), được đề xuất bởi E Keogh và các cộng sự vào năm 2001, nhằm giảm số chiều của chuỗi thời gian.
Xét một chuỗi thời gian có chiều dài m, ký hiệu là C = c1, c2, , cm, chuỗi này có thể được biểu diễn trong không gian n chiều dưới dạng ̅ = ̅1, ̅2, , ̅n Trong đó, phần tử thứ i của ̅ được tính theo công thức ̅i = j.
Chuỗi thời gian có m chiều sẽ được giảm xuống còn n chiều bằng cách chia thành n khung kích thước bằng nhau Giá trị trung bình của các phần tử trong mỗi khung được tính toán để tạo ra chuỗi có số chiều nhỏ hơn Hình 3-4 minh họa chuỗi thời gian ban đầu và chuỗi kết quả sau khi áp dụng phương pháp PAA để giảm chiều.
Hình 3-5: Thu giảm số chiều của chuỗi thời gian C về chuỗi ̅ ̅ có hình dạng bậc thang (nguồn [5])
Phương pháp PAA là một kỹ thuật hiệu quả giúp giảm số chiều của dữ liệu một cách đơn giản và nhanh chóng So với các phương pháp khác, PAA không chỉ tiết kiệm thời gian tính toán mà còn hỗ trợ nhiều loại độ đo khoảng cách, mang lại sự linh hoạt trong việc phân tích dữ liệu.
Rời rạc hóa dữ liệu
Sau khi giảm số chiều, dữ liệu sẽ được rời rạc hóa để thuận tiện cho việc xử lý Quá trình rời rạc hóa bao gồm việc chia dữ liệu ban đầu thành các đoạn nhỏ hơn Mỗi đoạn nhỏ sẽ được mã hóa dựa trên các đặc trưng của nó, và tập hợp các đặc trưng này sẽ tạo thành một chuỗi ký hiệu đại diện cho dữ liệu gốc.
Rời rạc hóa dữ liệu chuỗi thời gian mang lại lợi ích quan trọng bằng cách chuyển đổi dữ liệu thành dạng rời rạc, giúp dễ dàng xử lý thông qua các cấu trúc dữ liệu và thuật toán trong lĩnh vực xử lý chuỗi ký tự Các phương pháp như cây hậu tố, kỹ thuật băm và mô hình xích Markov có thể được áp dụng hiệu quả để phân tích và xử lý dữ liệu này.
Hiện nay, có nhiều phương pháp rời rạc hóa chuỗi thời gian như xấp xỉ gộp ký hiệu hóa (SAX), ESAX và iSAX Trong bài viết này, chúng tôi sẽ áp dụng giải thuật SAX để thực hiện rời rạc hóa chuỗi thời gian sau khi đã giảm số chiều bằng thuật toán PAA.
Giải thuật xấp xỉ gộp ký hiệu hóa (SAX) được giới thiệu bởi Eamonn Keogh và Jessica Lin vào năm 2002 SAX hoạt động trên dữ liệu đã được giảm số chiều thông qua phương pháp PAA và chuẩn hóa Quá trình này ánh xạ biểu diễn PAA của chuỗi thời gian thành một chuỗi ký tự rời rạc.
Kích thước của bộ ký hiệu được sử dụng để rời rạc hóa chuỗi thời gian được gọi là a Giải thuật chuẩn hóa dựa trên đặc điểm của dữ liệu chuỗi thời gian, thường có phân bố xác suất theo dạng Gauss Hình 3-5 minh họa sự phân bố xác suất của một chuỗi con có chiều dài 128 theo phân bố Gauss.
Hình 3-6: Sự phân bố xác suất của một chuỗi con chiều dài 128 có dạng phân bố
Để ký hiệu hóa chuỗi thời gian, việc xác định các điểm ngắt là rất quan trọng, và điều này được thực hiện thông qua phân bố Gauss Điểm ngắt được định nghĩa là một danh sách có thứ tự các số β = β1,…,βa-1, sao cho diện tích dưới đường cong Gauss N(0,1) từ βi đến βi+1 bằng 1/a, với β0 và βa được coi là -∞ và ∞ Định nghĩa này đảm bảo xác suất bằng nhau (1/a) cho mỗi ký hiệu trong tập ký hiệu Các điểm ngắt βi sẽ được lựa chọn dựa trên bảng tra xác suất của phân bố Gauss, như được thể hiện trong bảng 3-1, với kích thước a từ 3 đến 10.
Bảng 3-1: Bảng tra các điểm ngắt chia phân bố Gauss thành các vùng bằng nhau
Bảng ký hiệu có kích thước a từ 3 đến 10
Bằng cách sử dụng bảng điểm ngắt, chuỗi thời gian từ thuật toán PAA sẽ được chuyển đổi thành dạng rời rạc Sau khi áp dụng thuật toán SAX, các chuỗi con ban đầu sẽ được biểu diễn dưới dạng các chuỗi ký tự, được gọi là từ.
Một từ là cách thể hiện chuỗi thời gian ̅ = ̅1,…, n̅ dưới dạng chuỗi ký tự = ̂1,…, ̂n, trong đó ̂i được tính theo công thức: ̂i= alpha1 ci ≤β1 alphaa ci > βa-1 alphaj βj-1< ci ≤ βj Ở đây, alpha j là ký tự thứ j trong bảng ký hiệu có kích thước a, với các ký tự được sắp xếp theo thứ tự không đổi, ví dụ alpha1 = a, alpha2 = b Hình 3-6 minh họa chuỗi kết quả sau khi chuỗi thời gian được rời rạc hóa bằng phương pháp SAX.
Hình 3-7: Chuỗi thời gian được rời rạc hóa sử dụng PAA và SAX Từ thu được là baabccbc (nguồn [5])
Sau khi áp dụng mã hóa SAX, bài toán so sánh chuỗi thời gian chuyển thành so sánh chuỗi ký tự, giúp đơn giản hóa quá trình Phương pháp mã hóa SAX hiện đang được ưa chuộng nhờ tính đơn giản và hiệu quả của nó so với các phương pháp khác Bằng cách sử dụng SAX, chúng ta có thể tận dụng các cấu trúc dữ liệu và thuật toán hiện có trong lĩnh vực xử lý chuỗi ký tự, bao gồm cả xử lý dòng ký tự và phân tích trình tự sinh học.
Mặc dù SAX có nhiều ưu điểm, nhưng cũng tồn tại một số nhược điểm đáng chú ý Nhược điểm chính là dữ liệu chuỗi thời gian cần phải tuân thủ phân bố xác suất Gauss, tuy nhiên, hầu hết dữ liệu chuỗi thời gian thực tế đều đáp ứng điều kiện này Một nhược điểm khác là SAX không hỗ trợ tốt cho việc tính khoảng cách Euclid, do đó, cần phát triển phương pháp tính khoảng cách Euclid mở rộng cho hai chuỗi ký tự để xác định độ tương tự giữa chúng.
Độ đo tương tự
Để xác định mô típ trong dữ liệu chuỗi thời gian, việc so sánh độ tương tự giữa các công trình khác nhau là cần thiết Độ đo khoảng cách Euclid là công cụ phổ biến nhất cho mục đích này, nhờ vào sự đơn giản, dễ hiểu và khả năng tính toán nhanh chóng Hơn nữa, nó có thể dễ dàng 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 và phân lớp, đồng thời đủ hiệu quả để tính toán độ tương tự giữa hai chuỗi thời gian.
Cho hai chuỗi thời gian Q = q1,…,qm và C = c1,…,cm , độ đo khoảng cách Euclid giữa hai chuỗi thời gian này được cho bởi công thức:
Công thức trên không phù hợp để tính độ tương tự giữa hai chuỗi thời gian Q và C đã được biểu diễn dưới dạng ký hiệu và rời rạc hóa bằng thuật toán SAX Thay vào đó, chúng ta sẽ áp dụng một công thức mở rộng nhằm trả về khoảng cách tối thiểu giữa hai chuỗi thời gian gốc của hai từ Công thức này được trình bày như sau:
Giá trị trả về của hàm dist() có thể được tra trong một bảng giá trị Bảng này được minh họa như trong bảng 3-2
Bảng 3-2 trình bày giá trị của hàm dist() trong công thức tính MINDIST, áp dụng cho tập ký hiệu gồm 4 chữ cái Giá trị của hàm dist() tương ứng với ô tại dòng và cột của hai ký hiệu; ví dụ, dist(a,b) = 0 và dist(a,c) = 0.67 Để xây dựng bảng tra này, cần sử dụng bảng tra các điểm ngắt trên phân bố Gauss Giá trị mỗi ô (r,c) được tính theo công thức: ôr,c = 0 nếu |r – c| ≤ 1, và βmax(r,c) - 1 - βmin(r,c) cho các trường hợp khác.
Giá trị ô(c,a) được tính như sau: ô(3,1) = β2 – β1 = 0 – (-0.67) = 0.67 Tương tự, chúng ta có thể tính giá trị của các ô còn lại trong bảng Đối với một tập ký hiệu có kích thước a, bảng tra dist() chỉ cần được tính một lần và sẽ được lưu lại để tra cứu nhanh chóng Hình 3-7 minh họa khoảng cách giữa hai chuỗi thời gian sau khi đã được rời rạc hóa.
Giải thuật chiếu ngẫu nhiên
Sau khi áp dụng phương pháp PAA để thu giảm số liệu trong chuỗi thời gian T, chúng tôi sử dụng phương pháp SAX để chuyển đổi các chuỗi con thành chuỗi ký tự Tiếp theo, chúng tôi áp dụng giải thuật chiếu ngẫu nhiên để xây dựng ma trận đụng độ.
Giải thuật chiếu ngẫu nhiên (Random Projection) được giới thiệu bởi Jeremy Buhler và Martin Tompa vào năm 2001 để giải quyết bài toán planted(w,d)-motif do Pevzner và Sze đề xuất Năm 2003, Bill Chiu, Eamonn Keogh và các cộng sự đã áp dụng giải thuật này để tìm mô típ trong dữ liệu chuỗi thời gian Các chuỗi con sau khi được mã hóa bằng giải thuật SAX sẽ được sắp xếp vào một ma trận, trong đó mỗi chuỗi con tương ứng với một dòng của ma trận này Hình 3-8 minh họa quy trình xây dựng ma trận.
Trong quá trình xây dựng ma trận từ chuỗi thời gian T với chiều dài 1000 và chiều dài mô típ là 16, ta có thể xác định chiều dài từ là 4 và tập ký hiệu gồm 3 ký tự Số lượng chuỗi con được tính bằng công thức (1000 - 16 + 1) = 985, tương ứng với số dòng của ma trận.
Sau khi hoàn thành việc tạo ma trận, bước tiếp theo là thực hiện quá trình chiếu ngẫu nhiên để xây dựng ma trận đụng độ CM Ma trận này sẽ bao gồm các dòng và cột đại diện cho các chuỗi con trong dữ liệu Ban đầu, tất cả các ô trong ma trận CM đều được gán giá trị 0.
Thuật toán thực hiện k lần lặp, trong mỗi lần lặp, chọn ngẫu nhiên một số cột trong ma trận làm mặt nạ (ví dụ: cột 1, 2) Giá trị của các chuỗi con tương ứng với mặt nạ này sẽ được tính toán qua một hàm băm, và các chuỗi con có giá trị giống nhau sẽ được băm vào cùng một túi Nếu hai chuỗi con i và j được băm vào cùng một túi, giá trị tại ô tương ứng của chúng trong ma trận CM sẽ được tăng lên 1 Quá trình này được minh họa trong hình 3-9, với cột 1 và cột 2 được chọn trong lần lặp đầu tiên.
Hình 3-10 minh họa cách các chuỗi con được băm vào các túi với mặt nạ chọn ở cột 1 và 2 (bên trái), đồng thời trạng thái ma trận đụng độ tại ô (1,58) và ô (2,985) được tăng giá trị lên 1 (bên phải) (nguồn [4]).
Quá trình lặp lại cho đến khi đạt được k lần lặp sẽ cho ra ma trận đụng độ cuối cùng Do tính đối xứng của ma trận, phần trên bên phải sẽ được loại bỏ Hình 3-10 minh họa một lần lặp tiếp theo với cột được chọn là cột.
2 và cột 4 và trạng thái ma trận đụng độ lúc này
Các chuỗi con được băm vào các túi theo mặt nạ chọn ở cột 2 và 4, trong khi trạng thái ma trận đụng độ tại ô (1,58) có giá trị là 2 do được tăng thêm 1.
Giải thuật nối mô típ
Giải thuật nối mô típ (Motif Concatenation) được giới thiệu bởi Heng Tang và Stephen Liao vào năm 2008 nhằm giải quyết vấn đề tìm kiếm các mô típ với chiều dài khác nhau trong dữ liệu chuỗi thời gian Đây là giải thuật chính mà bài viết sẽ tập trung phân tích.
Giải thuật nối mô típ sử dụng ma trận đụng độ từ giải thuật chiếu ngẫu nhiên để tìm kiếm các mô típ Chiều dài w của các chuỗi con được chọn nhỏ nhằm phát hiện tất cả các mô típ với chiều dài w Sau đó, các mô típ nhỏ này sẽ được kết hợp thành một mô típ dài hơn Việc nối mô típ dựa trên tính chất rằng các mô típ con của một mô típ lớn hơn sẽ tạo thành đoạn thẳng hướng lên trong ma trận đụng độ, như được minh họa trong hình 3-11.
Hình 3-12 minh họa ma trận đụng độ của các chuỗi con, trong đó các mô típ nhỏ hơn tạo thành các đoạn thẳng hướng lên (hình bên trái), trong khi các mô típ lớn hơn thể hiện rõ ràng hơn (hình bên phải) (nguồn [7]).
Giải thuật phân tích từng mô típ nhỏ và phân chia chúng thành các phân đoạn riêng biệt, với mỗi phân đoạn bao gồm các mô típ lân cận tạo thành đoạn thẳng trên ma trận đụng độ Quá trình chia phân đoạn dựa vào tính chất hình học của đoạn thẳng, sử dụng một hằng số d để thể hiện phạm vi tìm kiếm, cùng với hai hằng số α1 và α2 để xác định phạm vi độ dốc cho phép của các mô típ.
Giả sử mô típ hiện tại là M i và mô típ tiếp theo là M j Nếu M j nằm trong diện tích tìm kiếm của M i được xác định bởi hằng số d, thì cần tính hệ số góc của đường thẳng nối giữa M i và M j Nếu hệ số góc này nằm trong khoảng [α1, α2], điều này sẽ được ghi nhận.
M j sẽ cùng phân đoạn với M i Hình 3-12 thể hiện một cách trực quan phương pháp chia phân đoạn này
Khu vực tìm kiếm được xác định bởi hằng số d (hình vuông nét đứt), trong đó hai vectơ đại diện cho hai hệ số góc α1 và α2, giúp giới hạn khu vực hợp lệ của hệ số góc (phần gạch chéo) (nguồn [7]).
Sau đây là giải thuật nối mô típ được thể hiện với mã giả
For each Mi in setM, Mi = (si1,si2) Do
For each M i in setM Do
If Mi.segid = 0 then Mi.segid = new(segid)
//Nếu segid = 0 thì tạo một segid mới
For each M j in setM, j > i, if |s i1 – s j1 | ≤ d and |s i2 – s j2 | ≤ d then
// Nếu Mj thuộc không gian tìm kiếm tạo bởi d slope = (sj2 – sj1) / (si2 – si1)
//Nếu hệ số góc slope thuộc đoạn [α 1 , α 2 ]
If Mj.segid = 0 then Mj.segid = Mi.segid
// Nếu Mj chưa thuộc phân đoạn nào thì gán nó thuộc cùng phân đoạn với M i
For each segment ID segidi Do
Cho tất cả các mô típ có cùng segidi vào phân đoạn segi
Sau khi phân chia các mô típ nhỏ thành các phân đoạn, mỗi phân đoạn sẽ kết hợp để tạo thành mô típ lớn hơn Việc chọn giá trị chiều dài w của mô típ ban đầu rất nhỏ khi xây dựng ma trận đụng độ sẽ giúp thuật toán phát hiện tất cả các mô típ có thể với chiều dài khác nhau.
Tìm mẫu chung của các mô típ
Sau khi xác định các mô típ dài hơn bằng giải thuật nối mô típ, bước tiếp theo là tìm ra các mô típ có mẫu chung và mẫu tổng quát của chúng Việc này dựa vào tính chất trùng lặp của các phân đoạn Nếu hai phân đoạn segi và segj có sự trùng lặp trên trục y, thì khả năng cao chúng có nguồn gốc từ một mẫu chung Do ma trận đụng độ có tính chất đối xứng, điều này cũng áp dụng cho trục x Chúng ta sẽ xem xét định nghĩa về trùng lặp phân đoạn.
Cho hai phân đoạn seg i = = và seg j
Độ trùng lắp phân đoạn giữa hai đoạn segi và segj được tính toán bằng công thức x_overlap(seg i ,seg j) = 2 x (min(s jp ,s ip ) – max(s j1 , s i1 ))/ (s jp + s ip –s i1 –s j1) và y_overlap(segi,segj) = 2 x (min(tjp,tip) – max(tj1, ti1))/ (tjp + tip –ti1 –tj1).
Hình 3-14: Sự trùng lắp các phân đoạn và sự đối xứng của chúng (nguồn [7])
Hình 3-13 minh họa sự trùng lắp giữa hai phân đoạn, với giá trị x_overlap và y_overlap thể hiện tỷ lệ trùng lắp so với tổng chiều dài của chúng Hai giá trị này được sử dụng để phân hoạch các phân đoạn vào các lớp tương đương Nếu x_overlap hoặc y_overlap của segi và segj lớn hơn một hằng số θ, chúng sẽ được phân hoạch vào cùng một lớp tương đương.
Sau khi thu thập tất cả các lớp tương đương, mỗi lớp sẽ chứa các phân đoạn có cùng mẫu chung Để xác định mẫu chung tổng quát, các phân đoạn trong cùng một lớp sẽ được sắp xếp lại Những phần dư thừa ở hai đầu sẽ được loại bỏ, và sau đó, giá trị trung bình của chúng tại từng vị trí sẽ được tính toán để tìm ra mẫu tổng quát của mô típ.
Hình 3-15: Tìm mẫu tổng quát bằng cách cắt bỏ phần dư thừa và tính giá trị trung bình của các phân đoạn (nguồn [7]).
Kết luận
Bài viết này trình bày cách tiếp cận sử dụng phương pháp PAA để giảm số chiều dữ liệu, kết hợp với phương pháp SAX để rời rạc hóa thông tin Để tính độ tương tự, bài viết áp dụng độ đo Euclid và sử dụng giải thuật chiếu ngẫu nhiên để xây dựng ma trận đụng độ Tiếp theo, giải thuật nối mô típ được triển khai nhằm tìm ra các mô típ dài hơn, trong khi phương pháp phân hoạch các phân đoạn vào các lớp tương đương giúp tìm kiếm mẫu tổng quát của các mô típ.
Phương pháp tiếp cận nối mô típ giúp khắc phục những hạn chế của các phương pháp khác trong việc tìm kiếm mô típ Nó có khả năng phát hiện mô típ với chiều dài tùy ý trong chuỗi thời gian và có thể nhận diện các mẫu tổng quát của những mô típ nếu có.
HIỆN THỰC VÀ THỬ NGHIỆM
Mô hình hiện thực
Mô hình phát hiện mô típ có chiều dài khác nhau hoạt động dựa trên giải thuật chiếu ngẫu nhiên và giải thuật phát hiện mô típ dựa vào điểm cực trị quan trọng, cung cấp cái nhìn tổng quát về quy trình và hiệu quả của việc nhận diện các mô típ trong dữ liệu.
4.1.1 Phát hiện mô típ có chiều dài khác nhau
Giải thuật phát hiện mô típ có chiều dài khác nhau (giải thuật MC) hoạt động bằng cách chuẩn hóa dữ liệu ban đầu thành dạng zero-mean và unit-norm Tiếp theo, chuỗi thời gian được giảm số chiều thông qua phương pháp PAA và rời rạc hóa bằng phương pháp SAX Cuối cùng, giải thuật chiếu ngẫu nhiên được áp dụng để tạo ra ma trận đụng độ cho các chuỗi con.
Giải thuật nối mô típ được áp dụng để tạo ra các phân đoạn chứa mô típ ngắn từ ma trận đụng độ Bằng cách kết hợp tất cả các mô típ nhỏ trong mỗi phân đoạn, chúng ta có thể tạo ra một mô típ dài hơn.
Cuối cùng, từ các phân đoạn đã thu thập, chúng tôi tính toán sự trùng lặp để xác định mô típ cuối cùng và xây dựng mẫu chung Trong phần này, chúng tôi lựa chọn thể hiện mô típ với chiều dài ngắn nhất làm mẫu chung.
Mô hình tổng quát của phương pháp sẽ như hình 4-1
Hình 4-1: Mô hình hoạt động của phương pháp phát hiện mô típ có chiều dài khác nhau
Các thông số của phương pháp này bao gồm:
Chiều dài khung w_PAA sử dụng thu giảm số chiều PAA
Hệ số a thể hiện độ lớn bảng chữ cái dùng trong SAX
Chiều dài chuỗi con w trong giải thuật chiếu ngẫu nhiên
Số mặt nạ k trong giải thuật chiếu ngẫu nhiên
Số cột c của mỗi mặt nạ trong giải thuật chiếu ngẫu nhiên
Hệ số d là không gian tìm kiếm trong giải thuật nối mô típ
Hệ số α1, α2 là hai hệ số góc giới hạn phạm vi tìm kiếm trong giải thuật nối mô típ
Hệ số trùng lắp θ dùng để phân hoạch các phân đoạn vào các lớp tương đương
4.1.2 Phát hiện mô típ dựa vào điểm cực trị quan trọng
Giải thuật phát hiện mô típ dựa vào điểm cực trị quan trọng (EP_C) được hiện thực hóa và thử nghiệm dựa trên ý tưởng của Gruber và cộng sự từ năm 2006 Bài viết cũng tham khảo luận văn thạc sĩ của Huỳnh Nguyễn Tín tại Đại học Bách Khoa TP.HCM vào năm 2012, với chủ đề "Nhận diện motif trên dữ liệu chuỗi thời gian dựa vào điểm cực trị quan trọng".
Phương pháp phát hiện mô típ dựa vào điểm cực trị quan trọng bắt đầu bằng việc xác định các điểm cực trị quan trọng Sau đó, thuật toán sẽ tạo ra các ứng viên mô típ dựa trên những điểm cực trị này Cuối cùng, mô hình sẽ gom cụm các ứng viên mô típ bằng thuật toán gom cụm phân cấp từ dưới lên, cụ thể là K-means Trong nghiên cứu này, chúng tôi đã áp dụng phương pháp gom cụm K-means để thực hiện phân tích Mô hình hoạt động của phương pháp này được minh họa trong hình 4-2 Các thông số của phương pháp cũng đóng vai trò quan trọng trong quá trình này.
Hệ số nén R là yếu tố quyết định đến mức độ nén dữ liệu Khi R tăng, số lượng điểm cực trị được chọn sẽ giảm và ngược lại, điều này ảnh hưởng đến chất lượng và độ chính xác của dữ liệu được nén.
Chiều dài cực tiểu l_min của các ứng viên motif: nếu một ứng viên mô típ có chiều dài nhỏ hơn l_min thì sẽ được bỏ qua
Chiều dài lấy mẫu lại l_resample của các ứng viên mô típ được xác định thông qua phép vị tự, giúp xác định chiều dài của các ứng viên này.
Hệ số r, nằm trong khoảng từ 0 đến 1, được tính bằng tổng số cụm chia cho tổng số điểm cực trị, là một thông số quan trọng giúp xác định số lượng cụm trong phương pháp K-Means.
Kết quả thực nghiệm
Các giải thuật trong luận văn này được lập trình bằng ngôn ngữ C#, với chương trình demo và thử nghiệm được thực hiện trên Visual Studio 2010 Để hỗ trợ cho các phần đồ họa, chương trình sử dụng thư viện ZedGraph.
Cấu hình máy tính được sử dụng để chạy các thử nghiệm như sau: bộ xử lý Intel® Core™ i3 CPU 540 @3.07 GHz, bộ nhớ 4GB RAM, hệ điều hành Window
Chúng tôi đã thực nghiệm trên các tập dữ liệu sau: điện tâm đồ (ECG) kích thước 7900 điểm, dữ liệu Memory kích thước 6800 điểm, dữ liệu Power kích thước
35000 điểm, dữ liệu điện tâm đồ (ECG) kích thước 144000 điểm
4.2.1 Dữ liệu điện tâm đồ với kích thước 7900 điểm
Dữ liệu trong phần thực nghiệm này bao gồm 7900 điểm điện tâm đồ (ECG), với hình thức biểu diễn được minh họa trong hình 4-3.
Hình 4-3: Biểu diễn của dữ liệu điện tâm đồ có kích thước 7900 điểm
4.2.1.1 Giải thuật phát hiện mô típ có chiều dài khác nhau
Giải thuật được thực hiện với các thông số đầu vào như sau:
Ký hiệu giá trị và chú thích trong bài viết bao gồm: w_PAA là 20, thể hiện chiều dài khung sử dụng để thu giảm số chiều PAA; a là 5, đại diện cho độ lớn bảng chữ cái trong SAX; w là 20, chỉ chiều dài chuỗi con w trong giải thuật chiếu ngẫu nhiên; k là 4, số mặt nạ k trong giải thuật chiếu ngẫu nhiên; c là 10, số cột c của mỗi mặt nạ trong giải thuật chiếu ngẫu nhiên; và d là 1.25, hệ số d biểu thị không gian tìm kiếm trong giải thuật nối mô típ.
Hệ số α1 và α2, nằm trong khoảng từ 0.65 đến 1.35, là các hệ số góc giới hạn trong giải thuật nối mô típ Hệ số trùng lắp θ, có giá trị 0.98, được sử dụng để phân hoạch các phân đoạn vào các lớp tương đương.
Sau khi thực hiện giải thuật với các thông số đã chỉ định, chúng tôi đã thu được 200 phân đoạn, được phân chia vào 140 lớp tương đương Thời gian chạy của giải thuật là 2480ms (2 giây 480 mili giây), như thể hiện trong hình 4-4.
Hình 4-4: Kết quả hiển thị của chương trình sau khi chạy giải thuật MC trên dữ liệu
Bài viết này trình bày một số mô típ được phát hiện thông qua thuật toán, cùng với các biểu diễn của chúng được thể hiện trong các hình 4-5, 4-7, 4-8 và 4-9.
Hình 4-5: Các thể hiện của mô típ dài nhất ứng với lớp tương đương 138 sau khi chạy giải thuật MC trên dữ liệu ECG 7900 điểm với w_PAA = 20, w = 20
Từ kết quả mô típ này, chúng tôi có mẫu chung của mô típ như sau:
Hình 4-6: Mẫu chung thu được của mô típ ứng với lớp 138sau khi chạy giải thuật
MC trên dữ liệu ECG 7900 điểm với w_PAA = 20, w = 20
Qua quan sát trên chúng tôi nhận thấy giải thuật có khả năng phát hiện mô típ có chiều dài rất lớn trong dữ liệu chuỗi thời gian
Hình 4-7: Các thể hiện của mô típ ứng với lớp tương đương 102 sau khi chạy giải thuật MC trên dữ liệu ECG 7900 điểm với w_PAA = 20, w = 20
Hình 4-8: Các thể hiện của mô típ ứng với lớp tương đương 84 sau khi chạy giải thuật MC trên dữ liệu ECG 7900 điểm với w_PAA = 20, w = 20
Hình 4-9: Các thể hiện của mô típ ứng với lớp tương đương 75 sau khi chạy giải thuật MC trên dữ liệu ECG 7900 điểm với w_PAA = 20, w = 20
Chúng tôi đã thực hiện nhiều thử nghiệm khác nhau trên tập dữ liệu này và nhận thấy rằng khi chiều dài w_PAA và w giảm, độ chính xác của giải thuật tăng lên Trong một thử nghiệm cụ thể với các thông số w_PAA = 10, w = 10, c = 5, chúng tôi đã thu được 5280 phân đoạn và 613 lớp, với thời gian chạy giải thuật là 110996ms (1 phút 50 giây 996 mili giây) Kết quả cho thấy các mô típ phát hiện đạt độ chính xác cao hơn.
4.2.1.2 Giải thuật phát hiện mô típ dựa vào điểm cực trị quan trọng
Sau khi thử nghiệm giải thuật phát hiện mô típ với tập dữ liệu điện tâm đồ 7900 điểm, chúng tôi tiếp tục kiểm tra giải thuật dựa trên các điểm cực trị quan trọng Các thông số đầu vào của giải thuật đã được xác định rõ ràng để đảm bảo tính chính xác trong quá trình phân tích.
Ký hiệu Giá trị Chú thích
Hệ số nén R 1.2 đóng vai trò quan trọng trong việc xác định các điểm cực trị, với chiều dài cực tiểu của ứng viên motif là 50 (l_min) Tỉ lệ giữa tổng số các cụm và tổng số các điểm cực trị được xác định bằng r 0.2 Sau khi lấy mẫu, chiều dài của các ứng viên motif sẽ được điều chỉnh thành 500 (l_resample).
Sau khi thực hiện giải thuật, chúng tôi đã thu được 17 thể hiện của mô típ trong thời gian 62ms Kết quả chương trình được trình bày trong hình 4-10, trong khi hình 4-11 minh họa các thể hiện của mô típ đã được tìm thấy.
Hình 4-10: Kết quả hiển thị của chương trình sau khi chạy giải thuật EP_C trên dữ liệu ECG 7900 điểm
Hình 4-11: Biểu diễn mô típ kết quả sau khi chạy giải thuật EP_C trên dữ liệu ECG
Giải thuật này chỉ có khả năng phát hiện các mô típ có mẫu giống như hình 4-9 trong kết quả của giải thuật MC, nhưng không thể nhận diện những mô típ dài hơn.
4.2.1.3 Kết luận kết quả thực nghiệm thu được của hai giải thuật
Kết quả từ các thực nghiệm trên tập dữ liệu điện tâm đồ 7900 điểm cho thấy giải thuật phát hiện mô típ có chiều dài khác nhau vượt trội hơn so với giải thuật phát hiện mô típ dựa vào điểm cực trị quan trọng.
Phát hiện mô típ có chiều dài khác nhau tốt hơn
Phát hiện được hầu hết các mô típ có trong tập dữ liệu
4.2.2 Dữ liệu Memory kích thước 6800 điểm
Dữ liệu trong phần thực nghiệm tiếp theo bao gồm 6800 điểm Memory, với hình thức biểu diễn như được trình bày trong hình 4-12.
Hình 4-12: Biểu diễn của dữ liệu Memory có kích thước 6800 điểm
4.2.2.1 Giải thuật phát hiện mô típ có chiều dài khác nhau
Giải thuật được thực hiện với các thông số đầu vào như sau:
Trong bài viết này, các ký hiệu và giá trị quan trọng được trình bày như sau: w_PAA là 20, đại diện cho chiều dài khung sử dụng để giảm số chiều trong PAA Hệ số a có giá trị 5, thể hiện độ lớn của bảng chữ cái trong SAX Chiều dài chuỗi con w trong giải thuật chiếu ngẫu nhiên là 20, trong khi số mặt nạ k là 4 Số cột c của mỗi mặt nạ trong giải thuật chiếu ngẫu nhiên là 10, và hệ số d, biểu thị không gian tìm kiếm trong giải thuật nối mô típ, có giá trị là 1.25.
Hệ số α1 và α2, với giá trị từ 0.65 đến 1.35, xác định giới hạn phạm vi tìm kiếm trong thuật toán nối mô típ Hệ số trùng lặp θ, có giá trị 0.98, được sử dụng để phân chia các phân đoạn vào các lớp tương đương.
Nhận xét kết quả thực nghiệm
Qua các thí nghiệm, chúng tôi nhận thấy giải thuật phát hiện mô típ với chiều dài khác nhau (MC) đã thành công trong việc phát hiện hầu hết các mô típ có trong dữ liệu chuỗi thời gian.
So sánh với giải thuật phát hiện mô típ dựa vào điểm cực trị quan trọng (EP_C), cả hai giải thuật đều có khả năng phát hiện các mô típ với chiều dài khác nhau Tuy nhiên, giải thuật EP_C không thể nhận diện các mô típ có chiều dài khác nhau trong dữ liệu, trong khi giải thuật MC lại làm được điều này MC có khả năng phát hiện hầu hết các mô típ từ nhỏ đến lớn trong dữ liệu chuỗi thời gian.
Giải thuật Monte Carlo (MC) có độ chính xác phụ thuộc vào kết quả của giải thuật chiếu ngẫu nhiên, dẫn đến việc kết quả có thể không chính xác đối với các mô típ nhỏ Tuy nhiên, đối với những mô típ lớn, giải thuật này thường cho kết quả tương đối chính xác.
Giải thuật MC có thời gian chạy tương đương với giải thuật EP_C trên các tập dữ liệu nhỏ, nhưng khi áp dụng cho các tập dữ liệu lớn hoặc dữ liệu có biến đổi giống nhau như điện tâm đồ, thời gian chạy của MC chậm hơn nhiều so với EP_C Khi xử lý các tập dữ liệu lớn, ma trận đụng độ từ giải thuật chiếu ngẫu nhiên trở nên rất lớn, dẫn đến việc tăng thời gian thực thi của MC Đặc biệt, với dữ liệu có biến đổi giống nhau xuyên suốt chuỗi thời gian, MC phải phát hiện các mô típ dài thông qua phương pháp nối mô típ, làm gia tăng thêm thời gian thực hiện.
Tốc độ thực thi và độ chính xác của thuật toán MC trong việc phát hiện mô típ phụ thuộc vào việc lựa chọn các thông số đầu vào hợp lý Khi giá trị w_PAA và w tăng, thời gian chạy sẽ nhanh hơn, nhưng khả năng phát hiện mô típ và độ chính xác sẽ giảm, và ngược lại.