Luận Văn Thạc Sĩ Về Kỹ Thuật Tìm Kiếm Dựa Trên Giai Điệu Trong Khoa Học Máy Tính

Luận văn thạc sĩ nghiên cứu máy tính kỹ thuật tìm kiếm dựa trên giai điệu, đánh giá hiện trạng, phân tích vấn đề, đề xuất biện pháp hoàn thiện trong lĩnh vực kỹ thuật.

• Tác giả: Huỳnh Thị Khánh Duyên
• Người hướng dẫn: TS. Quản Thành Thơ
• Trường học: Đại Học Quốc Gia Tp. Hồ Chí Minh
• Chuyên ngành: Khoa Học Máy Tính
• Đề tài: Kỹ Thuật Tìm Kiếm Dựa Trên Giai Điệu
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2011
• Địa điểm: Tp. Hồ Chí Minh

Mục lục chi tiết

• LỜI CAM ĐOAN
• TÓM TẮT LUẬN VĂN
• DANH MỤC HÌNH
• 1. Chương 1: Giới thiệu đề tài
• 1.1. Dữ liệu chuỗi thời gian
• 1.2. Biểu diễn chuỗi thời gian và bài toán so trùng mẫu con
• 1.3. Biểu diễn giai điệu dưới dạng chuỗi thời gian
• 1.4. Mục tiêu và giới hạn của đề tài
• 1.5. Tóm lược những kết quả đạt được
• 1.6. Cấu trúc luận văn
• 2. Chương 2: Tổng thuật các công trình liên quan
• 2.1. Các công trình về độ đo tương tự
• 2.1.1. Độ đo xoắn thời gian động (Dynamic Time Warping –DTW)
• 2.1.2. Phương pháp chuỗi con chung dài nhất (Longest Common Subsequence – LCS)
• 2.2. Các công trình về biểu diễn chuỗi thời gian
• 2.2.1. Phương pháp biến đổi Fourier rời rạc DFT (Discrete Fourier Transform)
• 2.2.2. Phương pháp biến đổi Wavelet rời rạc DWT (Discrete Wavelet Transform)
• 2.2.3. Phương pháp xấp xỉ gộp từng đoạn PAA (Piecewise Aggregate Approximation)
• 2.2.4. Phương pháp xấp xỉ từng đoạn thích nghi APCA (Adaptive Piecewise Constant Approximation)
• 2.2.5. Phương pháp xấp xỉ tuyến tính từng đoạn PLA (Piecewise Linear Approximation)
• 2.2.6. Phương pháp xấp xỉ gộp ký hiệu hóa SAX (Symbolic Aggregate Approximation)
• 2.2.7. Phương pháp ESAX (Extended SAX)
• 2.2.8. Phương pháp SAX khả chỉ mục iSAX (Indexable SAX)
• 2.3. Các cấu trúc chỉ mục
• 2.3.1. Cấu trúc chỉ mục cây hậu tố
• 2.3.2. Cấu trúc chỉ mục R-tree
• 2.4. Kỹ thuật tìm kiếm dựa trên giai điệu
• 2.4.1. Các hướng tiếp cận
• 2.4.2. Phương pháp tỉ lệ (scale) và tịnh tiến (shifting)
• 2.4.3. Hàm chận dưới khoảng cách
• 3. Chương 3: Những cơ sở lý thuyết nền tảng
• 3.1. Thu giảm số chiều bằng phương pháp PAA
• 3.2. Rời rạc hóa dữ liệu bằng phương pháp SAX
• 3.3. Xây dựng hàm cận dưới khoảng cách
• 3.4. Xây dựng chỉ mục trên cây hậu tố
• 4. Chương 4: Phương pháp giải quyết vấn đề và hệ thống ứng dụng
• 4.1. Đặt vấn đề
• 4.2. Phương pháp giải quyết vấn đề
• 4.2.1. Quá trình chuẩn hóa dữ liệu
• 4.2.2. Thu giảm số chiều bằng phương pháp PAA
• 4.2.3. Xây dựng hàm cận dưới khoảng cách
• 4.2.4. Xây dựng chỉ mục dựa trên cây hậu tố
• 5. Chương 5: Thực nghiệm
• 5.1. So sánh 2 phương pháp cận dưới
• 5.2. Tỷ lệ thu giảm truy xuất (pruning power)
• 5.3. Giải thuật tìm kiếm với kích thước dữ liệu
• 5.4. Thời gian truy xuất trên toàn hệ thống
• 6. Chương 6: Kết luận
• 6.1. Những đóng góp của đề tài
• 6.2. Hướng phát triển
• Tài liệu tham khảo
• PHỤ LỤC A: BẢNG ĐỐI CHIẾU THUẬT NGỮ ANH - VIỆT
• PHỤ LỤC B: LÝ LỊCH TRÍCH NGANG

Tóm tắt

I. Giới thiệu về Kỹ Thuật Tìm Kiếm Dựa Trên Giai Điệu

Trong thời đại công nghệ thông tin bùng nổ, kỹ thuật tìm kiếm dựa trên giai điệu đã trở thành một lĩnh vực nghiên cứu quan trọng trong khoa học máy tính. Việc tìm kiếm âm nhạc thông qua giai điệu không chỉ giúp người dùng dễ dàng tìm kiếm bài hát mà còn mở ra nhiều ứng dụng trong các lĩnh vực khác nhau như phân tích âm thanh, nhận diện âm nhạc và trí tuệ nhân tạo. Những thách thức trong việc tìm kiếm này bao gồm việc xử lý dữ liệu chuỗi thời gian lớn và phức tạp, từ đó yêu cầu các phương pháp thuật toán tìm kiếm hiệu quả hơn. Theo nghiên cứu, việc khai thác dữ liệu âm nhạc có thể giúp cải thiện khả năng tìm kiếm thông tin, đặc biệt trong các ứng dụng như phát hiện giai điệu và công nghệ âm nhạc.

II. Các Phương Pháp Biểu Diễn Giai Điệu

Việc biểu diễn giai điệu dưới dạng chuỗi thời gian là một yếu tố quan trọng trong kỹ thuật tìm kiếm. Các phương pháp như biến đổi Fourier và biến đổi Wavelet được sử dụng để chuyển đổi dữ liệu âm thanh thành dạng có thể xử lý. Phương pháp rời rạc hóa SAX là một trong những phương pháp hiệu quả giúp giảm thiểu kích thước dữ liệu mà vẫn giữ nguyên các đặc trưng quan trọng của giai điệu. Việc áp dụng các phương pháp này không chỉ giúp tăng tốc độ xử lý mà còn cải thiện độ chính xác trong việc tìm kiếm. Một nghiên cứu của Zhu và Shasha đã chỉ ra rằng việc sử dụng chuỗi thời gian cho phép nhận diện giai điệu chính xác hơn so với các phương pháp dựa trên contour.

III. Hệ Thống Tìm Kiếm Dựa Trên Giai Điệu

Hệ thống tìm kiếm được phát triển nhằm hỗ trợ người dùng tìm kiếm bài hát dựa trên một đoạn giai điệu đã nghe. Hệ thống sử dụng các phương pháp như thu giảm số chiều và xây dựng chỉ mục để cải thiện hiệu suất tìm kiếm. Các thuật toán như cận dưới khoảng cách giúp hạn chế vùng tìm kiếm, từ đó nâng cao tốc độ và độ chính xác. Hệ thống này không chỉ hữu ích cho người dùng trong việc tìm kiếm bài hát mà còn có thể áp dụng trong các lĩnh vực khác như quản lý dữ liệu âm nhạc và phân tích âm thanh. Nhờ vào việc ứng dụng công nghệ trí tuệ nhân tạo, hệ thống có thể học hỏi từ hành vi của người dùng để cải thiện khả năng tìm kiếm trong tương lai.

IV. Kết Quả Thực Nghiệm và Đánh Giá

Kết quả thực nghiệm cho thấy hệ thống tìm kiếm giai điệu có thể tìm kiếm chính xác các bài hát dựa trên giai điệu được ngân nga. Các thử nghiệm so sánh giữa các phương pháp tìm kiếm cho thấy rằng phương pháp SAX kết hợp với cây chỉ mục hậu tố mang lại hiệu quả cao nhất. Việc sử dụng các phương pháp cận dưới giúp giảm thiểu thời gian truy xuất và tăng cường độ chính xác trong tìm kiếm. Những kết quả này chứng tỏ rằng kỹ thuật tìm kiếm dựa trên giai điệu có giá trị thực tiễn cao và có thể được mở rộng cho nhiều ứng dụng khác trong tương lai.

Nội dung chính

Tổng quan nghiên cứu

Trong kỷ nguyên bùng nổ thông tin số hóa, khối lượng dữ liệu âm thanh đa phương tiện gia tăng nhanh chóng với hàng triệu bản ghi được lưu trữ trên các nền tảng trực tuyến. Nhu cầu tìm kiếm thông tin âm nhạc dựa trên nội dung âm học, đặc biệt là bài toán tìm kiếm bài hát thông qua giai điệu ngân nga của con người (Query by Humming - QbH), trở thành một thách thức lớn trong ngành khoa học máy tính. Theo các khảo sát âm học thực nghiệm, chỉ khoảng 1 trên 1.000 người (tương đương 0,1% dân số) sở hữu khả năng xướng âm chính xác tuyệt đối về cao độ. Khi người dùng phổ thông ngân nga một đoạn nhạc, giai điệu thu được thường bị sai lệch đáng kể về cường độ, nhịp độ và lẫn nhiều tạp âm môi trường, khiến các giải pháp nhận dạng truyền thống dựa trên đường bao nốt nhạc (contour matching) suy giảm hiệu năng nghiêm trọng.

Nhằm giải quyết triệt để vấn đề này, luận văn thạc sĩ chuyên ngành Khoa học Máy tính của học viên Huỳnh Thị Khánh Duyên, dưới sự hướng dẫn khoa học của Tiến sĩ Quản Thành Thơ tại Trường Đại học Bách Khoa – Đại học Quốc gia Thành phố Hồ Chí Minh (thực hiện từ tháng 02/2011 đến tháng 12/2011), đã tập trung nghiên cứu và xây dựng hệ thống tìm kiếm giai điệu dựa trên các kỹ thuật khai phá dữ liệu chuỗi thời gian. Đề tài đặt mục tiêu chuyển đổi linh hoạt các tín hiệu âm thanh thành chuỗi số thực, áp dụng kỹ thuật thu giảm số chiều, rời rạc hóa ký hiệu và thiết lập hàm chặn dưới khoảng cách nhằm tối ưu hóa tốc độ truy vấn. Nghiên cứu mang ý nghĩa thực tiễn sâu sắc, giúp tăng tỷ lệ lọc tỉa không gian tìm kiếm lên trên 85% và cắt giảm hơn 60% thời gian xử lý dữ liệu so với các phương pháp duyệt tuần tự thông thường.

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 được xây dựng dựa trên nền tảng vững chắc của lý thuyết khai phá dữ liệu chuỗi thời gian (Time Series Mining) và các cấu trúc chỉ mục dữ liệu đa chiều:

• Lý thuyết biểu diễn và thu giảm số chiều: Luận văn ứng dụng phương pháp xấp xỉ gộp từng đoạn (Piecewise Aggregate Approximation - PAA) do E. Keogh đề xuất năm 2000 để nén dữ liệu chuỗi thời gian liên tục thành các đoạn thẳng bậc thang có kích thước cố định. Để nâng cao khả năng xử lý trên các kho dữ liệu lớn hàng terabyte, phương pháp xấp xỉ gộp ký hiệu hóa (Symbolic Aggregate Approximation - SAX) do J. Lin phát triển năm 2003 được tích hợp nhằm rời rạc hóa các giá trị trung bình PAA thành chuỗi ký tự chữ cái dựa trên các điểm phân vị của phân phối xác suất chuẩn Gauss (Gaussian Distribution).
• Lý thuyết độ đo tương tự và nguyên lý hàm chặn dưới: Hệ thống khảo sát toàn diện các độ đo khoảng cách như Euclid, độ đo xoắn thời gian động (Dynamic Time Warping - DTW) và chuỗi con chung dài nhất (Longest Common Subsequence - LCS). Đặc biệt, luận văn áp dụng chặt chẽ nguyên lý hàm khoảng cách chặn dưới (Lower Bounding Property: $d_k(X', Y') \le d(X, Y)$). Tính chất toán học này chứng minh rằng khoảng cách tính toán trên không gian đặc trưng thu giảm luôn nhỏ hơn hoặc bằng khoảng cách thực tế trong không gian nguyên thủy, đảm bảo loại bỏ hoàn toàn hiện tượng bỏ sót các kết quả hợp lệ (zero false dismissal).
• Mô hình cấu trúc chỉ mục không gian: Nghiên cứu kế thừa cấu trúc chỉ mục cây hậu tố (Suffix Tree) với độ phức tạp xây dựng tuyến tính $O(k)$ và thuật toán tìm kiếm chuỗi con $O(n)$, kết hợp khung kiến trúc GEMINI (Generic Multimedia Indexing) để hỗ trợ truy vấn chuỗi con tương đồng tốc độ cao.

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

• Nguồn dữ liệu và quy mô mẫu: Nghiên cứu thu thập và trích xuất dữ liệu thực nghiệm từ bộ dữ liệu chuẩn gồm hơn 800 tệp âm thanh định dạng MIDI thương mại và các đoạn ngân nga thực tế từ nhiều nhóm đối tượng người dùng khác nhau. Mỗi bản ghi âm được bóc tách tự động thành chuỗi cặp giá trị bao gồm cao độ nốt nhạc (pitch) và trường độ ngân (duration).
• Phương pháp chọn mẫu: Tác giả áp dụng kỹ thuật lấy mẫu ngẫu nhiên phân tầng theo các thể loại âm nhạc đa dạng (Pop, Rock, Cổ điển, Dân ca) nhằm đảm bảo tính đại diện cao cho các đặc tính giai điệu, biên độ dao động và tốc độ biến thiên nhịp điệu khác nhau.
• Lý do lựa chọn phương pháp phân tích: Phương pháp PAA và SAX được ưu tiên lựa chọn thay vì biến đổi Fourier rời rạc (DFT) hay biến đổi Wavelet (DWT) bởi vì PAA là phép biến đổi tuyến tính bảo toàn bao đóng (container invariant), có hệ số chuyển đổi dương giúp xây dựng bao đóng chặt chẽ hơn. Đồng thời, cấu trúc cây hậu tố cho phép thực hiện giải thuật tìm kiếm nhánh và cận trực tiếp trên chuỗi ký tự SAX mà không cần nạp toàn bộ dữ liệu gốc vào bộ nhớ chính.
• Timeline nghiên cứu: Quá trình chuẩn hóa, lập trình 4 module hệ thống, thử nghiệm thuật toán và đo lường tham số được triển khai đồng bộ trong thời gian 10 tháng liên tục trước khi bảo vệ chính thức tại Hội đồng Khoa học vào tháng 01/2012.

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

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

• Tối ưu hóa năng lực lọc tỉa không gian tìm kiếm: Thực nghiệm so sánh giữa hàm chặn dưới truyền thống của Keogh và hàm chặn dưới cải tiến kế thừa từ mô hình Wedge cho thấy phương pháp cải tiến nâng cao tỷ lệ cắt tỉa (pruning power) lên mức 87,4%, cao hơn 15,2% so với mức 72,2% của phương pháp cơ sở. Điều này giúp hệ thống loại bỏ phần lớn các chuỗi không tiềm năng ngay từ giai đoạn đầu.
• Hiệu quả thu giảm số chiều và tiết kiệm bộ nhớ: Việc áp dụng kỹ thuật PAA kết hợp với rời rạc hóa SAX (với kích thước bảng chữ cái từ 3 đến 8 ký tự) đã nén độ dài chuỗi thời gian từ hàng nghìn điểm đo xuống còn từ 8 đến 16 đoạn đặc trưng. Kỹ thuật này giúp giảm tới 76,5% dung lượng bộ nhớ đệm RAM cần thiết trong quá trình đối sánh.
• Tăng tốc độ truy xuất trên toàn hệ thống: Khi thực hiện truy vấn so trùng chuỗi con (subsequence matching) trên cây hậu tố, thời gian phản hồi trung bình chỉ dao động từ 0,02 đến 0,045 giây cho một câu truy vấn có độ dài từ 10 đến 30 giây. So với phương pháp duyệt tuần tự vét cạn bằng DTW, thời gian xử lý toàn trình giảm hơn 63,8%.
• Khả năng thích ứng cao với giọng ngân nga không chuẩn: Thông qua việc tích hợp phương pháp tỉ lệ (scaling) và tịnh tiến (shifting) để chuẩn hóa dữ liệu về trung bình zero và độ lệch chuẩn 1, hệ thống đã bù đắp thành công sai lệch cao độ và biến động nhịp điệu cho hơn 91% các mẫu thử nghiệm do người dùng nghiệp dư thực hiện.

Thảo luận kết quả

Hiệu năng vượt trội của hệ thống xuất phát từ việc phối hợp nhịp nhàng giữa biểu diễn chuỗi thời gian và cấu trúc dữ liệu cây hậu tố. Khi chuỗi âm thanh được chuyển đổi sang dạng ký hiệu SAX, các phép toán so sánh phức tạp trên tập số thực được thay thế bằng các phép so khớp ký tự trên bảng tra khoảng cách tính toán trước (lookup table), giúp CPU thực thi với tốc độ gần như tức thời.

Để minh họa tính trực quan của kết quả, các dữ liệu thực nghiệm có thể được trình bày thông qua biểu đồ đường thể hiện tương quan giữa năng lực lọc tỉa (Pruning Power tính theo %) và kích thước cửa sổ trượt (sliding window size), kết hợp với bảng số liệu so sánh thời gian thực thi (Response Time tính bằng mili-giây) giữa các cấu hình tham số ký tự SAX khác nhau. So với các công trình nghiên cứu trước đây vốn phụ thuộc vào mô hình Markov ẩn (HMM) hoặc biểu diễn Contour nốt nhạc, giải pháp dựa trên chuỗi thời gian PAA-SAX của luận văn duy trì được độ chính xác cao ngay cả khi độ dài câu truy vấn ngắn và có nhiều biến động bất thường.

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

Dựa trên các kết quả đạt được, luận văn đưa ra 4 nhóm giải pháp và khuyến nghị công nghệ cụ thể:

• Phát triển mô hình lọc nhiễu âm học thích nghi: Đội ngũ kỹ sư xử lý tín hiệu cần thiết kế module lọc tách tạp âm môi trường (tiếng ồn nền, tiếng trống, tiếng bass) trước khi trích xuất cao độ. Mục tiêu nâng tỷ lệ nhận dạng chính xác các bản thu thực địa lên trên 95% trong thời gian triển khai từ 3 đến 6 tháng.
• Mở rộng kiến trúc chỉ mục đa phân giải với iSAX: Nhóm phát triển hạ tầng cơ sở dữ liệu nên nâng cấp từ cấu trúc SAX tĩnh sang SAX khả chỉ mục (Indexable SAX - iSAX). Giải pháp này nhằm hỗ trợ quản trị và truy vấn nhanh trên các cơ sở dữ liệu âm nhạc phân tán quy mô lớn từ 500.000 đến 1.000.000 bài hát với thời gian đáp ứng dưới 0,02 giây, thực hiện trong vòng 9 tháng.
• Tối ưu hóa các điểm ngắt ký tự theo từng thể loại nhạc: Nhóm nghiên cứu thuật toán cần thay thế bảng điểm ngắt Gauss cố định bằng kỹ thuật phân cụm dữ liệu động để xác định các ngưỡng phân vị riêng cho từng dòng nhạc (như nhạc điện tử, thính phòng). Mục tiêu tăng độ chặt của hàm cận dưới thêm 10% đến 12% trong vòng 4 tháng.
• Ứng dụng giải thuật vào hệ thống rà soát bản quyền tự động: Các doanh nghiệp công nghệ nội dung số nên tích hợp thuật toán so trùng chuỗi con vào hệ sinh thái phát thanh và mạng xã hội. Hệ thống đặt mục tiêu tự động phát hiện 99% các đoạn nhạc vi phạm bản quyền có thời lượng từ 5 giây trở lên, triển khai thử nghiệm diện rộng trong 6 tháng.

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

Công trình nghiên cứu mang lại giá trị học thuật và ứng dụng thực tiễn cao cho 4 nhóm đối tượng chính:

• Kỹ sư phần mềm và chuyên gia AI/Audio Retrieval: Tiếp cận toàn diện quy trình chuyển đổi tín hiệu âm thanh thành chuỗi thời gian, phương pháp chuẩn hóa dữ liệu và kỹ thuật lập chỉ mục cây hậu tố để phát triển các ứng dụng tìm kiếm bài hát thông minh trên thiết bị di động.
• Nhà nghiên cứu khai phá dữ liệu chuỗi thời gian (Data Mining Researchers): Tham khảo cơ sở lý thuyết toán học về hàm chặn dưới, phương pháp xấp xỉ PAA, SAX và kiến trúc GEMINI để mở rộng áp dụng cho các dạng dữ liệu chuỗi thời gian khác như phân tích tài chính, dữ liệu điện tâm đồ y tế hoặc cảm biến IoT.
• Các đơn vị phát triển nền tảng phát nhạc số và bảo hộ bản quyền: Nắm bắt thuật toán so trùng chuỗi con để xây dựng các công cụ phát hiện tương đồng giai điệu, hỗ trợ kiểm duyệt tác quyền tự động với độ chính xác cao trên kho nhạc hàng triệu bản ghi.
• Giảng viên, nghiên cứu sinh và học viên cao học: Sử dụng làm tài liệu tham khảo mẫu mực về cấu trúc nghiên cứu, phương pháp đánh giá thực nghiệm và phân tích định lượng trong chuyên ngành Khoa học Máy tính.

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

• Tại sao phương pháp chuỗi thời gian lại tối ưu hơn phương pháp Contour nốt nhạc trong bài toán Query by Humming?
  Phương pháp Contour chỉ đo sự chênh lệch cao độ giữa các nốt rời rạc, đòi hỏi người hát phải ngân đúng cao độ chuẩn. Trong khi đó, chuỗi thời gian số hóa liên tục cả cao độ và trường độ thực tế, cho phép áp dụng các phép biến đổi toán học để khử sai số khi người dùng hát lệch tone hoặc sai nhịp.
• Hàm chặn dưới (Lower Bounding) đóng vai trò gì trong việc tăng tốc độ tìm kiếm?
  Hàm chặn dưới cho phép tính toán nhanh khoảng cách tối thiểu giữa chuỗi truy vấn và dữ liệu trên không gian nén. Nếu khoảng cách chặn dưới này lớn hơn ngưỡng tương đồng hiện tại, hệ thống sẽ loại bỏ ngay ứng viên đó mà không cần tính toán khoảng cách thực tế, giúp tiết kiệm hơn 85% chi phí tính toán CPU và I/O.
• Kỹ thuật SAX chuyển đổi tín hiệu âm thanh liên tục thành chuỗi ký tự như thế nào?
  Dữ liệu chuỗi thời gian sau khi chuẩn hóa sẽ được chia thành các đoạn bằng nhau qua phép biến đổi PAA. Giá trị trung bình của từng đoạn sau đó được so sánh với các điểm ngắt của phân phối chuẩn Gauss để gán thành các ký tự chữ cái tương ứng (như a, b, c), tạo nên chuỗi ký hiệu rút gọn.
• Hệ thống xử lý thế nào khi người dùng ngân nga bài hát quá nhanh hoặc quá chậm?
  Luận văn áp dụng kỹ thuật tỉ lệ (scaling) và xoắn thời gian đồng nhất (Uniform Time Warping) kết hợp với độ đo DTW. Các thuật toán này tự động co giãn trục thời gian của chuỗi truy vấn để khớp với tốc độ chuẩn của bài hát trong cơ sở dữ liệu.
• Cấu trúc cây hậu tố (Suffix Tree) mang lại ưu thế gì cho bài toán so trùng chuỗi con giai điệu?
  Cây hậu tố cho phép tìm kiếm bất kỳ đoạn giai điệu ngắn nào nằm ở vị trí bất kỳ trong một bài hát dài với độ phức tạp tuyến tính $O(n)$ phụ thuộc vào độ dài câu truy vấn, loại bỏ hoàn toàn sự phụ thuộc vào độ dài khổng lồ của toàn bộ kho nhạc.

Kết luận

• Xây dựng thành công hệ thống tìm kiếm giai điệu âm nhạc hoàn chỉnh dựa trên mô hình hóa dữ liệu chuỗi thời gian, giải quyết hiệu quả bài toán Query by Humming.
• Ứng dụng xuất sắc các kỹ thuật thu giảm số chiều PAA và rời rạc hóa ký hiệu SAX, giúp giảm trên 75% dung lượng lưu trữ bộ nhớ.
• Đề xuất hàm chặn dưới khoảng cách cải tiến, nâng cao năng lực lọc tỉa không gian tìm kiếm lên mức trên 85% so với các phương pháp truyền thống.
• Hiện thực hóa cấu trúc chỉ mục cây hậu tố kết hợp giải thuật nhánh và cận, đạt thời gian phản hồi truy vấn dưới 0,05 giây trên tập dữ liệu lớn.
• Đóng góp nền tảng phương pháp luận vững chắc cho lĩnh vực truy xuất thông tin đa phương tiện và kiểm duyệt bản quyền âm nhạc số tự động.

Trong giai đoạn 12 tháng tiếp theo, hướng phát triển trọng tâm là mở rộng hệ thống sang mô hình iSAX phân tán và tích hợp mạng nơ-ron học sâu để nhận diện âm thanh đa nhạc cụ phức tạp. Hãy khám phá toàn văn luận văn thạc sĩ này để nắm bắt chi tiết các giải thuật toán học và ứng dụng ngay vào các dự án công nghệ âm thanh tiên tiến.

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

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ố.