HCMUTE Phát Hiện Motif Trên Chuỗi Thời Gian Dựa Vào Cấu Trúc Chỉ Mục Đa Chiều

Tài liệu nghiên cứu Hcmute phát hiện motif trên chuỗi thời gian dựa vào cấu trúc chỉ mục đa chiều và ý tưởng từ bỏ sớm, tổng hợp lý thuyết và thực hành, cung cấp kiến thức chuyên

• Tác giả: Nguyễn Thành Sơn
• Trường học: Trường Đại Học Sư Phạm Kỹ Thuật Thành Phố Hồ Chí Minh
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: Phát Hiện Motif Trên Chuỗi Thời Gian Dựa Vào Cấu Trúc Chỉ Mục Đa Chiều Và Ý Tưởng Từ Bỏ Sớm
• Loại tài liệu: luận văn
• Năm xuất bản: 2014
• Địa điểm: Thành Phố Hồ Chí Minh

Mục lục chi tiết

• PHẦN MỞ ĐẦU
• 1. CHƯƠNG 1: CÁC KIẾN THỨC CƠ SỞ
• 1.1. Tổng quan về đề tài
• 1.2. Các công trình liên quan
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Phân tích chuỗi thời gian và trích xuất motif

Phần này tập trung vào phân tích chuỗi thời gian, đặc biệt là trích xuất motif. Motif trong chuỗi thời gian được định nghĩa là các mẫu lặp lại có ý nghĩa. Trích xuất motif là một bước quan trọng trong việc hiểu dữ liệu chuỗi thời gian. Các phương pháp phát hiện motif hiện có thường gặp khó khăn với dữ liệu lớn. Bài toán này liên quan đến tìm kiếm mẫu trong chuỗi thời gian và nhận dạng motif. Mô hình chuỗi thời gian đóng vai trò quan trọng trong việc hiểu cấu trúc dữ liệu. Xử lý chuỗi thời gian hiệu quả đòi hỏi việc lựa chọn đúng các thuật toán tìm kiếm motif. Một trong những thách thức chính là hiệu quả tìm kiếm motif, đặc biệt là đối với các chuỗi thời gian dài và phức tạp. Phân tích dữ liệu chuỗi thời gian cần xem xét cả khía cạnh định lượng và định tính của motif. Phân tích motif định lượng tập trung vào các thuộc tính số học, trong khi phân tích motif định tính tập trung vào ý nghĩa ngữ cảnh.

1.1 Tổng quan về các phương pháp trích xuất motif

Nhiều thuật toán tìm kiếm motif đã được phát triển, mỗi thuật toán có ưu và nhược điểm riêng. Thuật toán brute-force, mặc dù chính xác, nhưng lại rất tốn kém về mặt tính toán. Các phương pháp xấp xỉ, như phương pháp chiếu ngẫu nhiên, được sử dụng để giảm thời gian tính toán, tuy nhiên độ chính xác có thể bị ảnh hưởng. So sánh các thuật toán tìm kiếm motif là cần thiết để lựa chọn phương pháp phù hợp cho từng trường hợp cụ thể. Việc đánh giá hiệu năng thuật toán tìm kiếm motif cần dựa trên nhiều yếu tố, bao gồm thời gian tính toán, độ chính xác và khả năng mở rộng. Tối ưu hóa thuật toán tìm kiếm motif là một lĩnh vực nghiên cứu đang phát triển mạnh mẽ. Thực hiện tìm kiếm motif hiệu quả đòi hỏi hiểu biết sâu sắc về cả lý thuyết và thực tiễn. Ứng dụng của trích xuất motif trong nhiều lĩnh vực, từ y học đến tài chính, cho thấy tầm quan trọng của việc nghiên cứu này. Việc quản lý dữ liệu chuỗi thời gian cũng là một yếu tố quan trọng ảnh hưởng đến hiệu quả của trích xuất motif. Cơ sở dữ liệu chuỗi thời gian cần được thiết kế sao cho thuận tiện cho việc tìm kiếm và xử lý.

1.2 Thách thức và hướng phát triển trong trích xuất motif

Mặc dù đã có nhiều tiến bộ, nhưng vẫn còn nhiều thách thức trong trích xuất motif. Dữ liệu chuỗi thời gian thường rất lớn và phức tạp, gây khó khăn cho việc xử lý. Độ nhiễu trong dữ liệu cũng ảnh hưởng đến độ chính xác của kết quả. Việc xác định ngưỡng tương đồng giữa các motif cũng là một vấn đề cần được nghiên cứu kỹ lưỡng. Phát triển các thuật toán mới hiệu quả hơn, chính xác hơn và có khả năng mở rộng tốt hơn là rất cần thiết. Khai thác dữ liệu chuỗi thời gian hiệu quả đòi hỏi sự kết hợp giữa các phương pháp thống kê, học máy và xử lý tín hiệu. Học máy sâu (deep learning) có tiềm năng lớn trong việc cải thiện độ chính xác của phát hiện motif. Học máy chuỗi thời gian và deep learning chuỗi thời gian là các lĩnh vực đang được nghiên cứu tích cực. Ứng dụng thực tiễn của trích xuất motif còn cần được mở rộng và hoàn thiện hơn nữa. Việc tích hợp trích xuất motif vào các hệ thống xử lý dữ liệu lớn cũng là một hướng phát triển quan trọng.

II. Cấu trúc chỉ mục đa chiều và thuật toán tìm kiếm motif

Phần này tập trung vào cấu trúc chỉ mục đa chiều, cụ thể là ứng dụng của chỉ mục đa chiều trong việc tăng tốc thuật toán tìm kiếm motif. Cấu trúc chỉ mục R-tree được xem xét như một giải pháp khả thi. Việc sử dụng cấu trúc chỉ mục giúp giảm thời gian tìm kiếm, cải thiện hiệu quả tìm kiếm motif. Quản lý dữ liệu chuỗi thời gian hiệu quả là yếu tố quyết định. Khai phá dữ liệu chuỗi thời gian được hỗ trợ bởi các kỹ thuật chỉ mục. Thuật toán tìm kiếm motif cần được thiết kế để tận dụng tối đa lợi ích của cấu trúc chỉ mục. Tra cứu motif trở nên nhanh hơn nhờ cấu trúc này. So khớp motif được tối ưu hóa. Ứng dụng của cấu trúc chỉ mục đa chiều không chỉ giới hạn trong tìm kiếm motif, mà còn mở rộng đến nhiều bài toán khác trong phân tích chuỗi thời gian. Độ phức tạp thuật toán được giảm đáng kể.

2.1 Ứng dụng của cấu trúc chỉ mục R tree trong tìm kiếm motif

Cấu trúc chỉ mục R-tree được sử dụng để tổ chức và truy vấn dữ liệu chuỗi thời gian. Cấu trúc này cho phép tìm kiếm nhanh chóng các motif có độ tương đồng cao. Thuật toán tìm kiếm được cải tiến để tận dụng cấu trúc R-tree. Việc xây dựng chỉ mục R-tree cần được tối ưu hóa để đảm bảo hiệu quả tìm kiếm. Quá trình tìm kiếm motif được chia thành các bước nhỏ hơn, giúp giảm thời gian tính toán. So sánh hiệu quả giữa việc sử dụng và không sử dụng chỉ mục R-tree cho thấy sự cải thiện đáng kể. Tối ưu hóa cấu trúc R-tree là một lĩnh vực nghiên cứu quan trọng. Khả năng mở rộng của R-tree cho phép xử lý các tập dữ liệu lớn. Cơ sở dữ liệu chuỗi thời gian được quản lý hiệu quả hơn nhờ R-tree. Phân tích hiệu năng cho thấy R-tree là một giải pháp tối ưu.

2.2 Kỹ thuật tối ưu hóa thuật toán tìm kiếm motif dựa trên cấu trúc chỉ mục

Kỹ thuật từ bỏ sớm được tích hợp vào thuật toán tìm kiếm motif. Kỹ thuật này giúp loại bỏ các phép tính không cần thiết, giảm thời gian tính toán. Tối ưu hóa thuật toán dựa trên việc phân tích đặc điểm của cấu trúc chỉ mục. Hiệu quả thuật toán được đánh giá dựa trên thời gian xử lý và độ chính xác. Đa chiều của chỉ mục cho phép tìm kiếm nhanh hơn. So sánh các kỹ thuật tối ưu hóa khác nhau. Phát hiện motif trở nên nhanh hơn và hiệu quả hơn. Phân tích định lượng về hiệu quả của thuật toán được trình bày. Ứng dụng thực tế của các kỹ thuật tối ưu hóa được đề cập. Phát triển các thuật toán mới dựa trên các kỹ thuật tối ưu hóa hiện có.

III. Kết luận và ứng dụng

Nghiên cứu này đã giới thiệu một phương pháp mới để phát hiện motif trong chuỗi thời gian bằng cách kết hợp cấu trúc chỉ mục đa chiều và kỹ thuật từ bỏ sớm. Phương pháp này cải thiện đáng kể hiệu quả tìm kiếm motif. Ứng dụng của phương pháp này trong nhiều lĩnh vực được đề cập. Kết quả thực nghiệm chứng minh tính hiệu quả của phương pháp. Hạn chế của phương pháp cũng được nêu ra, tạo cơ sở cho các nghiên cứu tiếp theo. Hướng phát triển trong tương lai được đề xuất. Khai thác dữ liệu chuỗi thời gian được thúc đẩy bởi các nghiên cứu này. Phân tích xu hướng chuỗi thời gian được hỗ trợ.

3.1 Đóng góp của nghiên cứu

Nghiên cứu đã đóng góp vào việc phát triển các thuật toán tìm kiếm motif hiệu quả hơn. Phương pháp đề xuất cải thiện đáng kể hiệu quả tìm kiếm motif so với các phương pháp truyền thống. Ứng dụng thực tiễn của nghiên cứu được đề cập. Kết quả nghiên cứu đã được công bố trên các tạp chí khoa học. Nghiên cứu đã đóng góp vào việc khai thác dữ liệu chuỗi thời gian hiệu quả hơn. Phát hiện bất thường trong chuỗi thời gian cũng được hỗ trợ bởi các nghiên cứu này. Dự báo chuỗi thời gian được cải thiện nhờ các kết quả nghiên cứu. Phân tích chuỗi thời gian với R và phân tích chuỗi thời gian với Python có thể được ứng dụng để thực hiện nghiên cứu này. Thư viện phân tích chuỗi thời gian hỗ trợ việc triển khai thuật toán.

3.2 Hạn chế và hướng phát triển

Nghiên cứu vẫn còn một số hạn chế. Phương pháp này có thể không hiệu quả với các chuỗi thời gian có độ nhiễu cao. Khả năng mở rộng của phương pháp cần được cải thiện. Các hướng phát triển trong tương lai bao gồm việc tích hợp các kỹ thuật học máy sâu. Tối ưu hóa thuật toán và xây dựng thư viện hỗ trợ là cần thiết. Dữ liệu bảo mật là một vấn đề cần được xem xét. Ứng dụng rộng rãi của phương pháp vẫn cần được nghiên cứu thêm. Các ví dụ về motif trong các ứng dụng thực tế cần được minh họa rõ hơn. Mô hình hóa motif trong các trường hợp phức tạp hơn cần được nghiên cứu thêm. Triển khai motif trong các hệ thống thực tế đòi hỏi sự tối ưu hóa cao hơn.

Nội dung chính

Tổng quan nghiên cứu

Phát hiện motif trên chuỗi thời gian là một bài toán quan trọng trong khai phá dữ liệu chuỗi thời gian, được ứng dụng rộng rãi trong nhiều lĩnh vực như y học, tài chính, thương mại và khoa học công nghệ. Theo ước tính, dữ liệu chuỗi thời gian có thể rất lớn, ví dụ như dữ liệu điện tâm đồ (ECG) trong một giờ có thể lên đến 1GB, gây khó khăn cho việc xử lý và phân tích. Bài toán phát hiện motif nhằm tìm ra các mẫu chuỗi con xuất hiện nhiều lần trong chuỗi thời gian dài, giúp nhận diện các đặc trưng lặp lại có ý nghĩa trong dữ liệu.

Mục tiêu nghiên cứu của luận văn là đề xuất một phương pháp mới phát hiện motif trên chuỗi thời gian dựa vào cấu trúc chỉ mục đa chiều R*-tree kết hợp với kỹ thuật từ bỏ sớm trong tính toán khoảng cách Euclid. Phương pháp này cho phép phân tích trực tiếp trên dữ liệu chuỗi thời gian dạng số mà không cần qua giai đoạn rời rạc hóa, đồng thời đạt hiệu quả cao về thời gian và không gian lưu trữ. Nghiên cứu được thực hiện trong khoảng thời gian từ tháng 6/2013 đến tháng 10/2014 tại Trường Đại học Sư phạm Kỹ thuật Thành phố Hồ Chí Minh.

Ý nghĩa của nghiên cứu thể hiện qua việc cải thiện hiệu quả tìm kiếm motif trong các tập dữ liệu lớn, giảm thiểu chi phí tính toán và tăng tốc độ xử lý, từ đó hỗ trợ các ứng dụng thực tiễn như dự báo chứng khoán, phân tích điện não đồ, và khai phá dữ liệu nâng cao. Kết quả nghiên cứu có thể áp dụng trong giảng dạy sau đại học và làm cơ sở phát triển các phần mềm ứng dụng trong lĩnh vực khai phá dữ liệu chuỗi thời gian.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu dựa trên các lý thuyết và mô hình sau:

• Chuỗi thời gian (Time Series): Là chuỗi các điểm dữ liệu được đo theo từng khoảng thời gian liên tục với tần suất thống nhất. Chuỗi con là đoạn liên tiếp trong chuỗi thời gian dài hơn.

• Motif trong chuỗi thời gian: Là chuỗi con xuất hiện nhiều lần với độ tương tự cao, được định nghĩa theo ngưỡng khoảng cách Euclid hoặc Dynamic Time Warping (DTW). Motif bậc k là chuỗi con có số lượng chuỗi con tương tự không tầm thường nhiều thứ k.

• Độ đo khoảng cách Euclid và Dynamic Time Warping (DTW): Euclid tính khoảng cách trực tiếp giữa các điểm tương ứng, trong khi DTW cho phép ánh xạ không thẳng hàng để xử lý các chuỗi có biến dạng về thời gian.

• Cấu trúc chỉ mục đa chiều R-tree:* Là cây cân bằng cao dùng để lưu trữ và truy vấn dữ liệu đa chiều, trong đó mỗi nút chứa vùng bao chữ nhật nhỏ nhất (MBR) bao quanh các đối tượng con. R*-tree cải tiến so với R-tree bằng kỹ thuật tách nút tối ưu, giúp tăng hiệu quả truy vấn.

• Kỹ thuật từ bỏ sớm (Early Abandoning): Giảm chi phí tính toán khoảng cách Euclid bằng cách dừng tính toán khi tổng tích lũy khoảng cách vượt quá ngưỡng cho phép.

Phương pháp nghiên cứu

• Nguồn dữ liệu: Thực nghiệm được tiến hành trên bốn tập dữ liệu chuỗi thời gian thực tế gồm ECG, Waveform, Stock và Consumer, với kích thước từ 10,000 đến 30,000 chuỗi con, chiều dài motif từ 128 đến 1024.

• Phương pháp phân tích: Phương pháp đề xuất sử dụng cấu trúc chỉ mục R*-tree để lưu trữ các chuỗi con dưới dạng MBR trong không gian đặc trưng giảm chiều, kết hợp với kỹ thuật từ bỏ sớm trong tính toán khoảng cách Euclid để tăng tốc độ tìm kiếm motif. So sánh hiệu quả với thuật toán chiếu ngẫu nhiên (Random Projection - RP) và phương pháp chỉ dùng R*-tree.

• Timeline nghiên cứu: Nghiên cứu được thực hiện trong 16 tháng (6/2013 - 10/2014), bao gồm tổng hợp lý thuyết, thiết kế giải thuật, triển khai thực nghiệm và đánh giá kết quả.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Hiệu quả thời gian thực hiện: Phương pháp R*-tree kết hợp kỹ thuật từ bỏ sớm có thời gian thực hiện thấp hơn đáng kể so với thuật toán chiếu ngẫu nhiên và phương pháp chỉ dùng R*-tree. Ví dụ, trên tập dữ liệu Stock với 10,000 chuỗi và chiều dài motif 512, thời gian thực hiện của phương pháp kết hợp chỉ khoảng 4 giây, trong khi RP mất đến 20 giây.

2. Độ hữu hiệu (Efficiency): Độ hữu hiệu của phương pháp đề xuất và phương pháp chỉ dùng R*-tree tương đương, đều tốt hơn so với RP. Độ hữu hiệu được đo bằng tỉ số số lần gọi hàm tính khoảng cách Euclid so với brute-force, với giá trị thấp hơn biểu thị cải tiến tốt hơn.

3. Khả năng mở rộng: Khi tăng kích thước tập dữ liệu từ 10,000 đến 30,000 chuỗi, phương pháp kết hợp vẫn duy trì thời gian thực hiện thấp hơn đáng kể so với RP, chứng tỏ khả năng xử lý dữ liệu lớn hiệu quả.

4. Độ chính xác: Phương pháp đề xuất cho phép phát hiện motif chính xác trên dữ liệu chuỗi thời gian dạng số mà không cần rời rạc hóa, giữ nguyên đặc trưng dữ liệu gốc.

Thảo luận kết quả

Nguyên nhân chính giúp phương pháp đề xuất vượt trội là do việc sử dụng cấu trúc chỉ mục R*-tree giúp giảm không gian tìm kiếm bằng cách loại bỏ nhanh các vùng không phù hợp dựa trên MBR, đồng thời kỹ thuật từ bỏ sớm giảm đáng kể chi phí tính toán khoảng cách Euclid trong giai đoạn hậu kiểm. So với thuật toán chiếu ngẫu nhiên, phương pháp không cần nhiều lần lặp để hội tụ, giảm chi phí tính toán tổng thể.

Kết quả phù hợp với các nghiên cứu trước đây về hiệu quả của R*-tree trong truy vấn dữ liệu đa chiều và kỹ thuật từ bỏ sớm trong tính toán khoảng cách. Tuy nhiên, điểm hạn chế của R*-tree là sự phủ lấp giữa các MBR trên cùng một mức có thể làm giảm hiệu quả tìm kiếm, đây là vấn đề cần cải tiến trong nghiên cứu tiếp theo.

Dữ liệu có thể được trình bày qua biểu đồ so sánh thời gian thực hiện và độ hữu hiệu giữa các phương pháp trên các tập dữ liệu và chiều dài motif khác nhau, giúp minh họa rõ ràng sự vượt trội của phương pháp đề xuất.

Đề xuất và khuyến nghị

1. Cải tiến cấu trúc chỉ mục: Nghiên cứu và phát triển các biến thể của R*-tree hoặc cấu trúc chỉ mục mới nhằm giảm thiểu sự phủ lấp giữa các MBR, nâng cao hiệu quả truy vấn.

2. Tối ưu thuật toán từ bỏ sớm: Áp dụng các kỹ thuật heuristic hoặc học máy để dự đoán ngưỡng từ bỏ sớm phù hợp hơn, giảm thêm chi phí tính toán khoảng cách.

3. Mở rộng ứng dụng: Áp dụng phương pháp phát hiện motif vào các lĩnh vực thực tiễn như phân tích tín hiệu y tế, dự báo tài chính, và khai phá dữ liệu lớn, với mục tiêu cải thiện độ chính xác và tốc độ xử lý.

4. Phát triển phần mềm hỗ trợ: Xây dựng công cụ phần mềm tích hợp phương pháp đề xuất để phục vụ giảng dạy sau đại học và nghiên cứu chuyên sâu về chuỗi thời gian.

Các giải pháp trên nên được thực hiện trong vòng 1-2 năm tới, với sự phối hợp giữa các nhà nghiên cứu và chuyên gia công nghệ thông tin.

Đối tượng nên tham khảo luận văn

1. Nghiên cứu sinh và sinh viên sau đại học ngành Công nghệ Thông tin, Khoa học Dữ liệu: Có thể sử dụng luận văn làm tài liệu tham khảo để hiểu sâu về phát hiện motif trên chuỗi thời gian và áp dụng trong các đề tài nghiên cứu.

2. Chuyên gia và kỹ sư phát triển phần mềm khai phá dữ liệu: Áp dụng phương pháp đề xuất để xây dựng các hệ thống phân tích dữ liệu chuỗi thời gian hiệu quả, đặc biệt trong lĩnh vực tài chính và y tế.

3. Giảng viên và nhà đào tạo: Sử dụng nội dung luận văn làm giáo trình hoặc tài liệu giảng dạy chuyên đề về khai phá dữ liệu chuỗi thời gian và cấu trúc chỉ mục đa chiều.

4. Nhà quản lý dự án nghiên cứu và phát triển công nghệ: Tham khảo để đánh giá và lựa chọn phương pháp xử lý dữ liệu chuỗi thời gian phù hợp cho các dự án ứng dụng thực tế.

Câu hỏi thường gặp

1. Phương pháp đề xuất có thể áp dụng cho dữ liệu chuỗi thời gian có chiều dài khác nhau không?
   Phương pháp sử dụng cấu trúc chỉ mục R*-tree và kỹ thuật từ bỏ sớm có thể áp dụng cho chuỗi con có chiều dài cố định trong chuỗi thời gian dài hơn. Để xử lý chuỗi có chiều dài khác nhau, cần thực hiện tiền xử lý hoặc mở rộng thuật toán.

2. Tại sao không sử dụng phương pháp rời rạc hóa dữ liệu trước khi phát hiện motif?
   Phương pháp đề xuất phân tích trực tiếp trên dữ liệu dạng số, tránh mất mát thông tin do rời rạc hóa, đồng thời giảm chi phí tính toán và tăng độ chính xác phát hiện motif.

3. Kỹ thuật từ bỏ sớm hoạt động như thế nào trong tính toán khoảng cách Euclid?
   Kỹ thuật này dừng tính toán khoảng cách ngay khi tổng tích lũy vượt quá ngưỡng cho phép, giúp tiết kiệm thời gian khi các chuỗi không đủ gần để là motif.

4. Phương pháp đề xuất có thể xử lý dữ liệu lớn như thế nào?
   Thực nghiệm trên tập dữ liệu đến 30,000 chuỗi cho thấy phương pháp duy trì hiệu quả về thời gian và độ hữu hiệu, phù hợp với các ứng dụng khai phá dữ liệu lớn.

5. Có thể kết hợp phương pháp này với các kỹ thuật giảm chiều khác không?
   Có thể áp dụng các phương pháp thu giảm số chiều như PAA, APCA, DFT, DWT để biến đổi dữ liệu trước khi xây dựng chỉ mục R*-tree, giúp tăng tốc độ xử lý mà vẫn giữ được đặc trưng dữ liệu.

Kết luận

• Đề xuất thành công phương pháp phát hiện motif trên chuỗi thời gian dựa vào cấu trúc chỉ mục đa chiều R*-tree kết hợp kỹ thuật từ bỏ sớm, cho hiệu quả vượt trội về thời gian và độ hữu hiệu so với các phương pháp hiện có.
• Phương pháp cho phép phân tích trực tiếp trên dữ liệu chuỗi thời gian dạng số mà không cần rời rạc hóa, giữ nguyên đặc trưng dữ liệu gốc.
• Thực nghiệm trên nhiều tập dữ liệu thực tế với kích thước và chiều dài motif khác nhau chứng minh tính khả thi và hiệu quả của phương pháp.
• Hạn chế hiện tại là sự phủ lấp giữa các MBR trong R*-tree, ảnh hưởng đến hiệu quả tìm kiếm, cần được cải tiến trong nghiên cứu tiếp theo.
• Khuyến nghị phát triển các biến thể chỉ mục mới, tối ưu thuật toán từ bỏ sớm và mở rộng ứng dụng trong các lĩnh vực thực tiễn.

Để tiếp tục nghiên cứu, đề nghị triển khai cải tiến cấu trúc chỉ mục và phát triển phần mềm ứng dụng. Mời các nhà nghiên cứu và chuyên gia trong lĩnh vực khai phá dữ liệu chuỗi thời gian cùng hợp tác phát triển các giải pháp mới nhằm nâng cao hiệu quả và ứng dụng rộng rãi hơn.

Trích đoạn nội dung tài liệu

CHƯƠNG 1. Các kiến thức cơ sở.1 Tổng quan về đề tài. Một chuỗi thời gian (time series) là một chuỗi các điểm dữ liệu được đo theo từng khoảng thời gian liền nhau theo một tần suất thời gian thống nhất.1 minh họa một ví dụ về chuỗi thời gian biểu diễn tỉ giá chuyển đổi trung bình hàng tháng giữa đô la Úc và đô la Mỹ (đơn vị đô la Úc) từ 7/1969 đến 8/1995.1 Đường biểu diễn một chuỗi thời gian ([16]). Các bài toán thường được nghiên cứu trong khai phá dữ liệu chuỗi thời gian gồm tìm kiếm tương tự (similarity search), gom cụm (clustering), phân lớp (classification), phát hiện motif (motif discovery), khai phá luật (rule discovery), phát hiện bất thường (anomaly detection), trực quan hóa (visualization), dự báo (forecast).

Những khó khăn và thách thức khi nghiên cứu về dữ liệu chuỗi thời gian [19]: - Dữ liệu thường rất lớn. Chẳng hạn, trong 1 giờ, dữ liệu điện tâm đồ (ECG) có thể lên đến 1GB. - Phụ thuộc nhiều vào yếu tố chủ quan của người dùng và tập dữ liệu khi đánh giá mức độ tương tự giữa các chuỗi thời gian. - Dữ liệu không đồng nhất: định dạng của dữ liệu khác nhau, tần số lấy mẫu khác nhau.

Ngoài ra, dữ liệu có thể bị nhiễu, thiếu một vài giá trị hoặc không sạch. 10 Luan van Bài toán tìm kiếm tương tự (so trùng) trong cơ sở dữ liệu chuỗi thời gian đã được nhiều nhà nghiên cứu quan tâm trong những năm qua vì đây là bài toán cơ bản và là một thành phần nền tảng của nhiều bài toán khác trong khai phá dữ liệu chuỗi thời gian. Đây là bài toán khó vì kích thước dữ liệu chuỗi thời gian thường lớn và vì chúng ta không thể lập chỉ mục dữ liệu chuỗi thời gian một cách dễ dàng như trong hệ thống cơ sở dữ liệu truyền thống. Một vài thí dụ về ứng dụng của tìm kiếm tương tự trên chuỗi thời gian có thể nêu ra như sau: - Tìm trong quá khứ, những giai đoạn mà số lượng sản phẩm bán được như tháng vừa rồi.

- Tìm những sản phẩm có chu kỳ doanh số giống nhau. - Tìm những đoạn nhạc trong một bài hát giống một đoạn nhạc đã có bản quyền. - Tìm những tháng trong quá khứ mà có lượng mưa giống như tháng vừa rồi. - Tìm những năm khô hạn mà mực nước các sông đều ở mức thấp.

Motif trong chuỗi thời gian là mẫu xuất hiện với tần suất cao nhất.2 minh họa ví dụ về motif là chuỗi con xuất hiện ba lần trong chuỗi thời gian dài hơn.2 Ví dụ về motif là chuỗi con xuất hiện ba lần trong chuỗi thời gian dài hơn ([6]) Từ khi được hình thức hóa vào năm 2002, phát hiện motif trong dữ liệu chuỗi thời gian đã và đang được dùng để giải quyết các bài toán trong nhiều lĩnh vực ứng dụng khác nhau ví dụ như dùng motif để kiểm tra chữ ký [14], dùng motif để phát hiện những hình ảnh lặp trong cơ sở dữ liệu hình dạng [42], dùng motif để dự báo giá chứng khoán [18], và cũng được dùng như bước tiền xử lý trong nhiều công việc khai phá dữ liệu cao cấp hơn, ví dụ như gom cụm chuỗi thời gian [33], phân lớp chuỗi thời gian [3]. 11 Luan van Hiển nhiên, độ phức tạp của phương pháp phát hiện chính xác motif theo kiểu brute-force là bậc hai theo số chuỗi trong cơ sở dữ liệu chuỗi thời gian hay chiều dài của chuỗi thời gian mà từ đó các chuỗi con được trích ra. Vì lý do đó, có nhiều thuật toán phát hiện motif xấp xỉ đã được giới thiệu ([6], [2], [28], [29], [36], [43]). Các cách tiếp cận này thường có độ phức tạp tính toán là O(n) hay O(nlogn), với n là số chuỗi trong cơ sở dữ liệu chuỗi thời gian hay chiều dài của chuỗi thời gian mà từ đó các chuỗi con được trích ra.

Độ phức tạp của các giải thuật này giảm hơn so với phương pháp tìm kiếm chính xác. Tuy nhiên, chúng yêu cầu một số lớn các tham số cần xác định trước. Một số thuật toán phát hiện motif xấp xỉ thường dựa trên các kỹ thuật xử lý chuỗi ký tự. Điều này đã khuyến khích các nhà nghiên cứu tìm kiếm các phương pháp biến đổi khác nhau để chuyển chuỗi thời gian thành chuỗi ký tự, sau đó sử dụng các kỹ thuật xử lý chuỗi đã có để phát hiện motif.

Trong số các thuật toán đã được đề xuất, thuật toán thông dụng là phương pháp chiếu ngẫu nhiên do Chiu và các cộng sự giới thiệu [6]. Thuật toán này có thể phát hiện motif trong thời gian tuyến tính. Đây là thuật toán được trích dẫn nhiều và là cơ sở cho nhiều cách tiếp cận hiện nay trong việc giải bài toán phát hiện motif trên dữ liệu chuỗi thời gian ([43], [39]). Tuy nhiên, các kỹ thuật xử lý chuỗi ký tự chưa thật sự hữu hiệu khi làm việc trên chuỗi thời gian dạng số.2 Các công trình liên quan.

Trong phần này, chúng tôi giới thiệu tóm tắt cơ sở lý thuyết về các độ đo tương tự, các phương pháp thu giảm số chiều, các cấu trúc chỉ mục thường dùng và các công trình liên quan tới bài toán được nghiên cứu. Trong các bài toán về chuỗi thời gian, để so sánh 2 chuỗi người ta sử dụng các độ đo tương tự. Hai đối tượng được xem là giống nhau khi độ đo tương tự giữa chúng bằng 0, được xem là tương tự nếu độ đo tương tự giữa chúng nhỏ hơn một giá trị  được qui ước trước đó. Để có thể tính toán và so sánh, độ đo này được biểu diễn thành các số thực và phải thỏa các tính chất sau: - D(x,y) = 0 nếu và chỉ nếu x = y - D(x, y) = D(y, x) 12 Luan van - D(x, y)  0 với mọi x, y - D(x, y) < D(x, z) + D(y, z) Dưới đây là các độ đo thường được sử dụng  Độ đo Minkowski.

Ký hiệu là Sim(X,Y) (độ tương tự giữa hai chuỗi X và Y có chiều dài n) và được định nghĩa như sau: n Sim( X , Y )  P  xi  yi  , với xi  X, yi  Y, i = 1, …, n P (1.1) Trong đó, p = 2 (Euclid) là độ đo thường được sử dụng.1) Độ đo này có ưu điểm tính toán dễ dàng. Tuy nhiên nó cũng có một số nhược điểm là do phương pháp này tính toán dựa trên các cặp giá trị tương ứng trong hai chuỗi nên đối với các trường hợp tính chất của hai mẫu là giống nhau nhưng giá trị khác nhau (có đường căn bản khác nhau hay có biên độ dao động khác nhau) thì khoảng cách hai mẫu sẽ rất khác nhau.3 minh họa trường hợp này.3 Minh họa hai chuỗi thời gian giống nhau. Để khắc phục trường hợp này trước khi áp dụng các giải thuật ta cần thực hiện chuẩn hóa dữ liệu. Các phương pháp chuẩn hóa thường được dùng là: - Chuẩn hóa trung bình zero (Zero-Mean normalization) [17] Chuỗi Q được biến đổi thành chuỗi Q’ theo công thức Q’[i] = (Q[i]- mean(Q)) / var(Q) (1.2) Với mean(Q) là giá trị trung bình của Q và var(Q) là độ lệch chuẩn của Q.2) - Chuẩn hóa nhỏ nhất-lớn nhất (Min-Max normalization) [17] Chuỗi Q được biến đổi thành chuỗi Q’ theo công thức 13 Luan van Q[i]  Minold (1.3) Q'[i]  ( Maxnew  Minnew )  Minnew Maxold  Minold (1.3) Với Minold và Maxold là giá trị nhỏ nhất và lớn nhất của chuỗi ban đầu.

Minnew và Maxnew là giá trị nhỏ nhất và lớn nhất của chuỗi sau khi được chuẩn hóa.  Độ đo xoắn thời gian động. Trong trường hợp hai mẫu cần so sánh có hai đường biểu diễn không hoàn toàn giống nhau nhưng hình dạng biến đổi rất giống nhau thì khi so sánh độ tương tự giữa hai mẫu bằng cách so sánh từng cặp điểm 1-1 (so điểm thứ i của đường thứ nhất và điểm thứ i của đường thứ hai) là không phù hợp.4 minh họa hai đường biểu diễn rất giống nhau về hình dạng nhưng lệch nhau về thời gian. Trong trường hợp này, nếu tính khoảng cách bằng cách ánh xạ 1-1 giữa hai đường thì kết quả rất khác nhau và có thể dẫn đến kết quả cuối cùng không giống như mong muốn.

Vì vậy để khắc phục nhược điểm này, một điểm có thể ánh xạ với nhiều điểm và ánh xạ này không thẳng hàng. Phương pháp này gọi là xoắn thời gian động (Dynamic Time Warping - DTW) [5].4 Khoảng cách giữa hai đường biểu diễn rất giống nhau về hình dạng nhưng lệch nhau về thời gian. Cách tính DTW Cách đơn giản nhất để tính DTW của hai đường X và Y là ta xây dựng ma trận Dm x n với m = |X| và n= |Y|. Sau khi xây dựng ma trận D , ta tìm đường đi từ ô (0,0) đến ô (m,n) thỏa mãn những ràng buộc sau: - Không được đi qua trái hay đi xuống - Đường đi phải liên tục - Ô (i,j) thuộc đường đi phải thỏa |i - j| <= w Giả sử có K ô đi từ ô (0,0) đến ô (m,n) thỏa mãn những điều kiện trên, 14 Luan van khi đó: Tuy nhiên, ta có thể dùng quy hoạch động để giải quyết bài toán này.

Trong đó, công thức truy hồi để tính D(i, j): Độ đo tương tự DTW có ưu điểm là cho kết quả chính xác hơn so với độ đo Eu- clid và cho phép nhận dạng mẫu có hình dạng giống nhau nhưng chiều dài hình dạng về thời gian có thể khác nhau. Độ đo tương tự này có nhược điểm là thời gian chạy lâu, tuy nhiên gần đây đã có những công trình tăng tốc độ tìm kiếm tương tự dùng độ đo DTW, tiêu biểu nhất là công trình của Keogh và các cộng sự, năm 2002 [21].5 minh họa cách tính khoảng cách theo DTW.5 Minh họa cách tính khoảng cách theo DTW.2 Thu giảm số chiều chuỗi thời gian. Thu giảm số chiều là phương pháp biểu diễn chuỗi thời gian n chiều X = {x1, x2, …, xn} thành chuỗi thời gian có N chiều Y = {y1, y2, …, yN} với N << n, nhưng vẫn phải giữ được các đặc trưng của chuỗi thời gian ban đầu. Với N càng lớn thì sự khôi phục càng chính xác.

Dữ liệu chuỗi thời gian thường rất lớn nên việc tìm kiếm trực tiếp trên dữ liệu chuỗi thời gian gốc sẽ không hiệu quả. Để khắc phục vấn đề này, cách tiếp cận chung thường được sử dụng bao gồm các bước sau: 15 Luan van 1. Áp dụng một số phương pháp biến đổi xấp xỉ để thu giảm độ lớn của dữ liệu sao cho vẫn giữ được các đặc trưng của dữ liệu. Các phương pháp biến đổi xấp xỉ này thường được gọi là những phương pháp thu giảm số chiều (dimensionality reduc- tion).