Chương 1: Giới thiệu ñề tài 1.1 Dữ liệu chuỗi thời gian Một chuỗi thời gian là một chuỗi số thực ñại diện cho các phép ño của một biến thực tế tại các khoảng thời gian bằng nhau. Dữ liệu chuỗi thời gian tồn tại trong nhiều ứng dụng thực tế, từ các lĩnh vực khoa học kỹ thuật cho ñến kinh tế, tài chính. Đặc biệt trong thời ñiểm hiện nay, việc khai phá thông tin ngày càng ña dạng và cần thiết. Vì vậy, ñã có nhiều nghiên cứu nhằm mục ñích quản lý, xử lý một cách hiệu quả những yêu cầu có liên quan ñến dữ liệu chuỗi thời gian.
Có rất nhiều dữ liệu có yếu tố thời gian như dữ liệu về giá chứng khoán, ñiện tâm ñồ, mực nước, lưu lượng truyền trên mạng, dữ liệu tài chính… Việc khai phá dữ liệu chuỗi thời gian ñã thu hút rất nhiều sự nghiên cứu trên thế giới. Cụ thể là một số lĩnh vực nghiên cứu sau: • Lập chỉ mục (Indexing): cho một chuỗi thời gian truy vấn Q, và một hàm tính ñộ tương tự hoặc ñộ sai biệt D(Q,C), tìm những chuỗi thời gian tương tự nhất với Q trong cơ sở dữ liệu DB nào ñó. Phương pháp này giúp ta tổ chức dữ liệu và hổ trợ tìm kiếm nhanh nhất. • Phân lớp (Classification): cho một chuỗi thời gian chưa gán nhóm Q, gán nó vào một trong những nhóm ñã ñược ñịnh nghĩa trước.
• Tóm tắt (Summarization):cho chuỗi thời gian Q có n ñiểm dữ liệu trong ñó n là con số rất lớn, tạo một sự xấp xỉ của Q ñể vừa khít theo một giới hạn nào ñó (chẳng hạn màn hình máy tính, trang giấy…) sao cho vẫn duy trì những ñặc trưng bản chất của nó. 1 Tìm kiếm dựa trên giai ñiệu • Dự ñoán (Predict) : cho chuỗi thời gian Q với n ñiểm. Dự ñoán giá trị thứ n+1 của chuỗi. • Phát hiện bất thường (Anomaly detection): cho một chuỗi thời gian Q, và một vài mô hình hành vi bình thường (normal behavior), tìm tất cả những phần thuộc Q có chứa bất thường.
Ngoài ra còn có nhiều tên gọi khác cho lĩnh vực này như phát hiện những hành vi gây ngạc nhiên (surprising behavior), hành vi quan tâm (interesting behavior), hành vi không mong ñợi (unexpected behavior), hành vi lạ thường (novel behavior). Đồng thời có rất nhiều ñịnh nghĩa như thế nào gọi là bất thường.2 Biểu diễn chuỗi thời gian và bài toán so trùng mẫu con Trong các bài toán về chuỗi thời gian, như thu giảm số chiều (dimensional reduction), lập chỉ mục (indexing), …, việc biểu diễn chuỗi dữ liệu ảnh hưởng rất lớn ñến hiệu suất cũng như kết quả của bài toán. Do vậy, việc tìm kiếm ra những phương pháp biểu diễn chuỗi thời gian hiệu quả cũng là một bài toán thách thức trong cộng ñồng nghiên cứu về chuỗi thời gian. Biểu diễn chuỗi thời gian hợp lý sẽ giúp khắc phục ñược những khó khăn ñặc thù của chuỗi thời gian như là dữ liệu quá lớn (tốn chí phí I/O và CPU khi truy xuất và tính toán), sự không ñồng nhất về dữ liệu, …Hình 1.1 tóm lược về các công trình biểu diễn chuỗi thời gian.
2 Tìm kiếm dựa trên giai ñiệu Hình 1.1 Các phương pháp biểu diễn chuỗi thời gian Bài toán so trùng chuỗi thời gian là việc tìm ra phương pháp sao cho việc tìm kiếm chuỗi con vừa nhanh và hiệu quả. Đây là bài toán rất cơ bản trong lĩnh vực nghiên cứu chuỗi thời gian. Một số dạng truy vấn mà ta thường gặp : • Tình hình tăng trưởng của công ty trong tháng. • Tìm xem những giai ñiệu giống nhau trong một bài nhạc ñể có thể ñánh giá trong việc quy phạm bản quyền.
• Tìm những sản phẩm có chu kỳ bán giống nhau. Mặc dù có nhiều loại khác nhau nhưng các yêu cầu truy vấn trên dữ liệu chuỗi thời gian có thể chia làm 2 loại : • So trùng toàn bộ (whole matching) : Đối với những truy vấn so trùng toàn bộ thì chiều dài của chuỗi truy vấn và chuỗi dài dữ liệu ban ñầu là bằng nhau. Bài toán này người ta thường dùng trong việc gom cụm, hay phân loại dữ liệu chuỗi thời gian. Ví dụ, “tìm giá chứng khoán của những công ty nào thay ñổi giống nhau”.
3 Tìm kiếm dựa trên giai ñiệu • So trùng chuỗi con (subsequence matching) : Trong trường hợp so trùng một phần thì chiều dài của dữ liệu truy vấn ngắn hơn rất nhiều so với chiều dài của dữ liệu ban ñầu. Vì vậy, nhiệm vụ chính là tìm những ñoạn trong dữ liệu ban ñầu tương tự với dữ liệu truy vấn. Một số ứng dụng của bài toàn này là tìm những mẫu dữ liệu quan trọng hay những thay ñổi bất thường trong dữ liệu ban ñầu. Ví dụ: “tìm những khoảng thời gian mà giá của thị trường chứng khoán không ñổi trong một khoảng thời gian”,“tìm những thời ñiểm mà giá chứng khoán giảm ñột ngột”, hay “những thời ñiểm nào mà giá chứng khoán thay ñổi theo dạng hình răng cưa”, … 1.3 Biểu diễn giai ñiệu dưới dạng chuỗi thời gian Có nhiều ñịnh dạng tập tin nhạc như : midi, wma, mp3… Vì vậy việc tìm kiếm dựa trên giai ñiệu cũng có nhiều hướng phát triển khác nhau.
Việc truy vấn dựa trên giai ñiệu là một hình thức truy vấn nội dung (“Query by content”) trong cơ sở dữ liệu truyền thông. Hiện tại thì việc truy vấn dựa trên những biểu tượng của giai ñiệu thì tốt hơn là việc truy vấn dựa trên âm thanh của giai ñiệu. Vì vậy, việc truy xuất các cơ sở dữ liệu dựa trên âm thanh của giai ñiệu (Querying acoustic databases) là một vấn ñề rất ñược quan tâm ngày nay. Hầu hết việc nghiên cứu chỉ tập trung sử dụng các khái niệm của “Contour”.
“Contour” trong giai ñiệu là tập các khác biệt trong cường ñộ (pitch) giữa các nốt nhạc kế tiếp nhau. Người nghe có thể nhận ra ñược sự khác biệt giữa các nốt nhạc nhờ sự khác nhau về thông tin “contour” ñó. Tuy nhiên, sự khó khăn trong phương pháp này là tuy chúng hoạt ñộng hiệu quả với dữ liệu âm thanh chuẩn do nhạc sĩ chuyên nghiệp hoặc chương trình máy tính trình diễn, nhưng lại không chính xác và hiệu quả khi thể hiện những giai ñiệu ñược con người ngân nga, thường là không chuẩn và có nhiều thông tin nhiễu [40]. Để giải quyết vấn ñề này, một phương pháp tiếp cận hiệu quả là sử dụng chuỗi thời gian, vì phương pháp này cho phép biểu diễn chính xác các thông tin về ngân ñộ và cao ñộ của nốt nhạc ngay cả khi người sử dụng ngân nga không “chuẩn”.
Kết quả thực nghiệm trong bài 4 Tìm kiếm dựa trên giai ñiệu báo [4] của Zhu và Shasha cho thấy rằng giải pháp sử dụng chuỗi thời gian có kết quả tối ưu hơn so với phương pháp dựa trên contour hiện nay.4 Mục tiêu và giới hạn của ñề tài Chắc hẳn khi muốn tìm một bài hát nào ñó bạn thường hay dựa vào tên ca sĩ trình bày hay tác giả của bài hát, hoặc cũng có thề tìm bài hát dựa trên lời của nó. Tuy nhiên trong trường hợp bạn chỉ nghe hoặc nhớ một ñoạn trong bài hát nhưng không biết bất cứ thông tin gì về bài hát thì xem như việc tìm kiếm bài hát ñó sẽ rất khó khăn. Hệ thống tìm kiếm dựa trên giai ñiệu sẽ cho người sử dụng có thể tìm những bài hát dựa trên một phần giai ñiệu của nó. Người sử dụng nhập vào một ñoạn bài hát và hệ thống sẽ trả về những bài hát có giai ñiệu tương tự như giai ñiệu mà người sử dụng ñã nhập.
Việc tìm kiếm dựa trên giai ñiệu là một chủ ñề ít phổ biến hơn việc xử lý ngôn ngữ tự nhiên nhưng nó sẽ rất phát triển trong tương lai gần. Luận văn tập trung giải quyết các vấn ñề chính : - Việc tìm kiếm dựa vào những nốt nhạc (contour matching) thì sẽ không chính xác và hiệu quả bởi vì dữ liệu của chúng tôi là những giai ñiệu ñược con người ngân nga. Do ñó chúng tôi ñã chuyển về dữ liệu chuỗi thời gian ñể số hóa những giai ñiệu ñó một cách linh ñộng hơn. 5 Tìm kiếm dựa trên giai ñiệu - Dữ liệu tập thời gian quá lớn và không ñồng nhất.
Chúng tôi ñã sử dụng phương pháp PAA ñể nhằm thu giảm số chiều của dữ liệu và ñồng nhất về số chiều ñể việc tính toán trở nên dễ dàng và hợp lý hơn. - Với những giai ñiệu không ñược tự nhiên như là có nhịp ñộ (tempo) nhanh hoặc chậm ; cường ñộ (pitch) cao hoặc thấp hơn bình thường. Chúng tôi dùng các phương pháp tỉ lệ (scale) và tịnh tiến (shifting) ñưa chúng về 0 ñể bảo ñảm dữ liệu không bị bất biến. - Vì tập dữ liệu tìm kiếm là rất lớn, chúng tôi ñã xây dựng các phương pháp cận dưới khoảng cách ñể nhằm hạn chế vùng tìm kiếm chuỗi tương ñồng.
- Để hỗ trợ việc tìm kiếm, chúng tôi ñã sử dụng phương pháp rời rạc hóa SAX và cây chỉ mục hậu tố ñể tìm ra những chuỗi dữ liệu tương ñồng nhau. Hệ thống chưa xử lý ñược những tập tin dạng phức tạp với nhiều tạp âm (như tiếng bass, tiếng trống,. Đề tài chưa thể thử qua hết tất cả các phương pháp nhằm hổ trợ tìm kiếm giai ñiệu một cách tốt nhất. Đề tài chỉ mới dừng lại là ñưa ra một số phương pháp xử lý chuỗi thời gian và có những bước cải tiến ñể xử lý việc tìm kiếm dựa trên giai ñiệu.
Ngoài ra việc biến ñổi dữ liệu nhiều sẽ có thể ảnh hưởng ñến kết quả kém chính xác.5 Tóm lược những kết quả ñạt ñược Trong giới hạn thời gian hiện thực, chúng tôi ñã hiện thực hệ thống tìm kiếm dựa trên âm ñiệu gồm 4 môñun chính: môñun tạo tập dữ liệu thực nghiệm từ tập tin MIDI, môñun biểu diễn dữ liệu chuỗi thời gian, môñun cấu trúc dữ liệu và môñun tìm kiếm chuỗi con tương ñồng. Trong môñun thứ nhất, chúng tôi rút trích chuỗi thời gian từ tập tin midi. Một bản nhạc bao gồm một bộ các âm ñiệu (note) và khoảng thời gian các âm ñiệu ñược ngân (duration). 6 Tìm kiếm dựa trên giai ñiệu Trong môñun thứ hai, chúng tôi hiện thực phương pháp thu giảm số chiều PAA và phương pháp rời rạc SAX.
Môñun thứ ba, chúng tôi tạo các cấu trúc dữ liệu tương ứng với từng phương pháp thu giảm số chiều và rời rạc hóa dữ liệu chuỗi thời gian. Cụ thể, áp dụng phương pháp cận dưới ( lower bounding) of Keogh cho phương pháp thu giảm số chiều PAA, cấu trúcchỉ mụccủa cây hậu tố cho phương pháp SAX. Ở môñun tìm kiếm chuỗi con tương ñồng, chúng tôi hiện thực giải thuật tìm kiếm nhánh và cận trên cấu trúc chỉ mục cây hậu tố.
