臺灣博碩士論文加值系統

隨著網際網路的蓬勃發展，大量流通的音樂資料使得與音樂相關的應用紛紛出現，要有效率地提升這些應用的服務品質，必須要依靠音樂分析、音樂推薦與音樂查詢等自動化技術的支援。在本篇論文中，為了實現互動式音樂家教與遠距音樂教學這兩個應用，我們開發了先進的音樂分析、音樂推薦與音樂查詢技術，並且加以整合。
在音樂分析的領域，我們結合了節奏特徵與樂句外形的觀念，利用分群與資料探勘的技術，發展出一個全新的音樂切割方法，以擷取出一個音樂物件的樂句，並進而分析其整體架構；在音樂推薦的範疇，我們完整考慮了音樂物件的所有特性，加上經由分析歷史瀏覽資料所得到的使用者興趣與行為，在進行個人化推薦時，整合音樂物件的內涵與其他使用者的意見，同時提供了三種不同的推薦機制，以滿足使用者不同的需求；最後，在互動式音樂家教與遠距音樂教學兩個應用中，為了進行內涵式音樂比對，我們發展了一個能夠在串流環境中進行多重查詢比對並且具有容錯能力的完整系統，可以在音樂串流中即時搜尋出滿足查詢要求的音樂片段，我們以傳統n-gram技術為藍圖，從相似查詢的計算分享、減少比對的資料量與重複使用計算的結果等方向，發展出兩個主要的機制來節省大量近似比對所帶來的沈重計算，第一個機制採用分群的技術，並使用分群摘要來評估可能的最小誤差，以進行前期的答案片段篩選，第二個機制則是透過最小誤差評估的方式，有效率地整合已收集的答案片段，以獲得最終的答案。
經過一連串的實驗測試，我們已經驗證了上述的三項技術在正確性與效率上，都領先了現存的其他方法，達成了我們所要的目標。

With the growth of Internet, a large amount of music data is available for many music-related applications. It is almost impractical for these applications to satisfy the user requirements manually. To provide efficient services within these applications, the techniques developed for automatic music analysis, recommendation, and retrieval are urgently necessary. In this paper, we consider the applications of interactive music tutorials and distance education at music school. In the two applications, we need to integrate several techniques to achieve the educational purposes. This demand motives us to develop the advanced techniques for the performances of music services.
In the area of music analysis, the music structure usually needs to be analyzed manually by experts, which is time-consuming and impractical. Therefore, we propose an approach for automatic music segmentation to extract the phrases and sentences of the musical structure. In addition to the rhythmic features, the melodic shape is first-ever used to improve the effectiveness of the music segmentation.
Concerning a large number of music objects available in the databases, the systems that provide the services for users to look for their favorite music objects are urgently needed. One of the most important services for the users to escape from this information-overloading problem is the recommendation service. Due to the complex semantics of the music objects and the difficult derivation of user interests and behaviors, we propose an alternative way of music recommendation, which overcomes the limitations of the previous works. The music objects are first grouped based on the automatically extracted features. Moreover, the user access histories are analyzed to derive the profiles of user interests and behaviors for user grouping. The content-based, collaborative, and statistics-based recommendation methods are proposed based on the favorite degrees of the users to the music groups, and the user groups they belong to.
Many interesting applications based on music streams, such as interactive music tutorials, distance music education, and similar theme searching, make the research of content-based retrieval over music streams much important. Therefore, we consider multiple queries with error tolerances over music streams and address the issue of approximate matching in this environment. To satisfy this demand, we propose a novel approach to continuously process multiple queries over the music streams for finding all the music segments that are similar to the queries. Our approach is based on the concept of n-grams and two mechanisms are designed to reduce the heavy computation of approximate matching. One mechanism uses the clustering of query n-grams to prune the query n-grams that are irrelevant to the incoming data n-gram. The other mechanism records the data n-gram that matches a query n-gram as a partial answer and incrementally merges the partial answers of the same query.
A series of experiments are performed to demonstrate the effectiveness and efficiency of our approaches by comparing with other related works.

1 Introduction 10
1.1 Music Analysis 10
1.2 Music Recommendation 11
1.3 Music Retrieval 12
2 Related Works 13
2.1 Related Works of Music Segmentation for Music Analysis 13
2.2 Related Works of Music Recommendation Approaches 14
2.3 Related Works of Music Retrieval 15
3 Music Segmentation by Rhythmic Features and Melodic Features 18
3.1 Preliminary 18
3.2 Music Segmentation 19
3.2.1 Phrase Extraction 19
3.2.1.1 Decision of Terminative Note 19
3.2.1.2 Heuristic Approach for Phrase-based Segmentation 20
3.2.2 Phrase Clustering 21
3.2.3 Sentence Extraction 22
3.3 Example 22
3.4 Future Works 22
4 A Music Recommendation System Based on Music and User Grouping 23
4.1 Music Recommendation System 23
4.1.1 Track Selection 24
4.1.2 Feature Extraction 24
4.1.3 Classifier 25
4.2 Recommendation Mechanisms 26
4.2.1 The Profile Manager 26
4.2.2 The CB Method 27
4.2.3 The COL Method 28
4.2.4 The STA Method 31
4.3 Conclusion 32
4.4 Future Works 32
5 Continuous Query Processing over Music Streams Based on Approximate Matching Mechanisms 33
5.1 Motivation and Problem 33
5.2 Basic Idea and System Architecture 35
5.3 Query Manager 37
5.3.1 SQ Decomposition 37
5.3.2 Query N-gram Clustering 37
5.3.3 Cluster Summarization 39
5.3.4 Query Buffer Creation 39
5.4 Pruning Mechanism 40
5.5 Merging Mechanism 45
5.6 Future Works 51
6 Experiments 51
6.1 Experimental Results of Our Music Segmentation Approach 51
6.2 Experimental Results of Our Recommendation Approach 52
6.2.1 Effectiveness of the Track Selector 53
6.2.2 Effectiveness of the Feature Selection 53
6.2.3 Quality of Recommendations 53
6.3 Experimental Results of Continuous Query Processing over Music Streams 54
6.3.1 Experiment Setting 54
6.3.2 Experiments on Real-time Requirement 55
6.3.3 Experiments on Scalability 57
6.3.4 Experiments on Influence of Parameter �� 58
6.3.5 Experiments on Influence of Parameter n 59
7 Conclusion 60

[1] Root Cause Analysis Handbook: A Guide to Effective Incident Investigation, by Risk & Reliability Division, ABS Group, Inc. Root Cause Map, ABSG Consulting Inc., 1999.
[2] A movies recommender system, http://www.movielens.umn.edu, 2003.
[3] Agrawal, R. and R. Srikant, “Fast Algorithm for Mining Association Rules,” Proceedings of International Conference on Very Large Data Bases, 1994.
[4] Aggarwel, C.C., J.L. Wolf, and P.S. Yu, “A New Method for Similarity Indexing of Market Basket Data,” Proceedings of ACM International Conference on Management Data, 1999.
[5] Altschul, S., W. Gish, W. Miller, E.W. Myers, and D.J. Lipman, “Basic Local Alignment Search Tool,” Journal of Molecular Biology, 1990.
[6] Avnur, R., and J.M. Hellerstein, “Eddies: Continuous Adaptive Query Processing,” Proceedings of ACM SIGMOD International Conference on Management Data, 2000.
[7] Balabanovic, M. and Y. Shoham, “Fab: Content-based Collaborative Filtering Recommendation,” Communications of the ACM, 1997.
[8] Basu, C., H. Haym, and W. W. Cohen, “Recommendation as classification: Using social and content-based information in recommendation,” Proceedings of National Conference on Artificial Intelligence, 1998.
[9] Beckmann, N., H.P. Kriegel, R. Schneider, and B. Seeger, “The R*-tree: An Efficient and Robust Access Method for Points and Rectangles,” Proceedings of ACM SIGMOD International Conference on Management of Data, 1990.
[10] Bellini, P., J. Barthelemy, P.Nesi, and G. Zoia, “A Proposal for the Integration of Symbolic Music Notation into Multimedia Frameworks,” Proceedings of International Conference on the Web Delivering of Music, 2004.
[11] Bellini, P., P.Nesi, and G. Zoia, “Symbolic Music Representation in MPEG,” IEEE Multimedia, 2005.
[12] Billsus, D. and M. Pazzani, “A Hybrid User Model for News Story Classification,” Proceedings of International Conference on User Modeling, 1999.
[13] Burges, C.J.C., J.C. Platt, and S. Jana, “Distortion Discriminant Analysis for Audio Fingerprinting,” IEEE Transactions on Speech and Audio Processing, 2003.
[14] Cambouroooulos, E., “The Local Boundary Detection Model (LBDM) and its Application in the Study of Expressive Timing,” Proceedings of lntemationol Computer Music Conference, 2001.
[15] Cano, P., E. Batlle, T. Kalker, and J. Haitsma, “A Review of Algorithms for Audio Fingerprinting,” International Workshop on Multimedia Signal Processing, 2002.
[16] Cano, P., E. Batlle, H. Mayer, and H. Neuschmied, “Robust Sound Modeling for Song Detection in Broadcast Audio,” Processing of International Conference on AES, 2002.
[17] Carney, D., U. Cetintemel, M. Cherniack, C. Convey, S. Lee, G. Seidman, M. Stonebraker, N. Tatbul, and S. Zdonik, “Monitoring Streams - A New Class of Data Management Applications,” Proceedings of International Conference on Very Large Data Bases, 2002.
[18] Chandrasekaran, S. and M.J. Franklin, “Streaming Queries over Streaming Data,” Proceedings of International Conference on Very Large Data Bases, 2002.
[19] Chen, J., D.J. DeWitt, F. Tian, and Y. Wang, “NiagraCQ: A scalable continuous query system for internet databases,” Proceedings of ACM SIGMOD International Conference on Management of Data, 2000.
[20] Cheung, K. W. and L. F. Tian, “Learning User Similarity and Rating Style for Collaborative Recommendation,” Proceedings of European Conference on IR Research, 2004.
[21] Chuang, J.C., C.W. Cho, and A.L.P. Chen, “Similarity Search in Transaction Databases with Two-Level Bounding Mechanism,” Proceedings of International Conference on Database Systems for Advanced Applications, 2006.
[22] Clausen, M., R. Engelbrecht, D. Meyer and J. Schmitz, “Proms: A web-based tool for searching in polyphonic music,” Proceedings of International Symposium on Music Information Retrieval, 2000.
[23] Cranor, C, Y. Gao, T. Johnson, V. Shkapenyuk, and O. Spatscheck, “Gigascope: high performance network monitoring with an SQL interface,” Proceedings of ACM SIGMOD Conference on Management of Data, 2003.
[24] Crochemore, M. and W. Rytter, “Text Algorithms,” Oxford University Press, 1994.
[25] Dannenberg, R.B. and N. Hu, “Pattern Discovery Techniques for Music Audio,” Proceedings of International Symposium on Music Information Retrieval, 2002.
[26] Dovey, M.J., “A technique for "regular expression" style searching in polyphonic music,” Proceedings of International Symposium on Music Information Retrieval, 2001.
[27] Downie, S. and M. Nelson, “Evaluation of a Simple and Effective Music Information Retrieval Method,” Proceedings of ACM International Conference on Research and Development in Information Retrieval, 2000
[28] Faloutsos, C. and M. Ranganathan, and Y. Manolopoulos, “Fast Subsequence Matching in Time-series Databases,” Proceedings of ACM SIGMOD International Conference on Management of Data, 1994.
[29] Friberg, A., R. Bresin, L. Fryden, and J. Sunberg, “Musical Punctuation on the Microlevel: Automatic Idnrification and Performance of Small Melodic Units,” Journal of New Music Research, 1998.
[30] Ghias, A., H. Logan, D. Chamberlin, and B.C. Smith, “Query by Humming: Musical Information Retrieval in an Audio Database,” Proceedings of ACM International Conference on Multimedia, 1995.
[31] Ghias, A., J. Logan, D. Chamberlin, and B.C. Smith, “Query by Humming: Music Information Retrieval in An Audio Database,” Proceedings of ACM Multimedia, 1995.
[32] Gionis, A., D. Gunopulos, and N. Kouda, “Efficient and Tunable Similar Set Retrieval,” Proceedings of ACM International Conference on Management Data, 2001.
[33] Golab, L., and M.T. Özsu, “Issues in data stream management,” ACM SIGMOD Record, 2003.
[34] Goldberg, D., D. Nichols, B. M. Oki, and D. Terry, “Using Collaborative Filtering to Weave an Information Tapestry,” Communications of the ACM, 1992.
[35] Gusfield, D., “Algorithms on Strings, Trees, and Sequences,” Cambridge University Press, 1997.
[36] Haitsma, J. and T. Kaller, and J. Oostveen, “Robust Audio Hashing for Content Identification,” Proceedings of IEEE International Workshop on Content-based Multimedia Indexing, 2001.
[37] Haitsma, J. and T. Kalker, “A Highly Robust Audio Fingerprinting System,” Proceedings of International Symposium on Music Information Retrieval, 2002.
[38] Hellerstein, J., M. Franklin, S. Chandrasekaran, A. Deshpande, K. Hildrum, S. Madden, V. Raman, and M.A. Shah, “Adaptive query processing: Technology in evolution,” IEEE Data Engineering Bulletin, 2000.
[39] Hsu, J.L., and A.L.P. Chen, “Building a Platform for Performance Study of Various Music Information Retrieval Approaches,” Proceedings of International Symposium on Music Information Retrieval, 2001.
[40] Hsu, J.L., C.C. Liu, and A.L.P. Chen, “Discovering Non-trivial Repeating Patterns in Music Data,” IEEE Transactions on Multimedia, 2001.
[41] Huron, D., “The Melodic Arch in Western Folksongs,” Computing in Musicology, Volume10, 1995.
[42] Jain, A. K. and R. C. Dubes, “Algorithms for Clustering Data,” 1st Edition, Prentice Hall, 1988.
[43] Jing, Q. and R. Yang, “Localized Signature Table: Fast Similarity Search on Transaction Data,” Proceedings of ACM International Conference on Information and Knowledge Management, 2004.
[44] Joachims, T., D. Freitag, and T. Mitchell, “WebWatcher: A Tour Guide for the World Wide Web,” Proceedings of International Joint Conference on Artificial Intelligence, 1997.
[45] Kageyama, T., K. Mochizuki, and Y. Takashima, “Melody Retrieval with Humming,” Proceedings of International Computer Music Conference, 1993.
[46] Kahveci, T. and A.K. Singh, “An Efficient Index Structure for String Databases,” Proceeding of International Conference on Very Large Data Bases, 2001.
[47] Kang, J., J.F. Naughton, and S.D. Viglas, “Evaluating Window Joins over Unbounded Streams,” Proceedings of IEEE International Conference on Data Engineering, 2003.
[48] Kornstadt, A., “Themefinder: A Web-Based Melodic Search Tool,” Computing in Musicology 11, MIT Press, 1998.
[49] Konstan, J. A., B. N. Miller, D. Maltz, J. L. Herlocker, L. R. Gordon, and J. Riedl, “Grouplens: Applying Collaborative Filtering to Usenet News,” Communications of the ACM, 1997.
[50] Krulwich, B. and C. Burkey, “Learning User Information Interests through Extraction of Semantically Significant Phrases,” Proceedings of AAAI Spring Symposium on Machine Learning in Information Access, 1996.
[51] Krumhansl, C.L., Cognitive Foundations of Musical Pitch, Oxford University Press, New York, 1990.
[52] Kuo, F. F. and M. K. Shan, “A Personalized Music Filtering System Based on Melody Style Classification,” Proceedings of IEEE international Conference on Data Mining, 2002.
[53] Lang, K., “Newsweeder: Learning to Filter Netnews,” Proceedings of International Conference on Machine Learning, 1995.
[54] Lieberman, H., “An agent that assists web browsing,” Proceedings of International Joint Conference on Artificial Intelligence, 1995.
[55] Lemstrőm, K. and S. Perttu, “SEMEX – An Efficient Music Retrieval Prototype,” Proceedings of International Symposium on Music Information Retrieval, 2000.
[56] Liu, N.H., Y.H. Wu and A.L.P. Chen, “Efficient kNN Search in Polyphonic Music Databases Using a Lower Bounding Mechanism,” ACM Multimedia Systems Journal, 2005.
[57] Liu, N.H., Y.H. Wu, and A.L.P. Chen, “An Efficient Approach to Extracting Approximate Repeating Patterns in Music Databases,” Proceedings of International Conference on Database Systems for Advanced Applications, 2005.
[58] Madden, S., M. Shah, J.M. Hellerstein, and V. Raman, “Continuous Adaptive Continuous Queries over Streams,” Proceedings of ACM SIGMOD International Conference on Management Data, 2002.
[59] Mamoulis, N., D.W. Cheung, and W. Lian, “Similarity Search in Sets and Categorical Data Using the Signature Tree,” Proceedings of IEEE International Conference on Data Engineering, 2003.
[60] Mckay, C., and I. Fujinaga, “Automatic Genre Classification Using Large High-level Musical Feature Sets,” Proceedings of International Symposium on Music Information Retrieval, 2004.
[61] McNab, R.J., L.A. Smith, I.H. Witten, C.L. Henderson, and S.J. Cunningham, “Towards the Digital Music Library: Tune Retrieval from acoustic input,” Proceedings of Digital Libraries Conference, 1996.
[62] McNab, R. J., L. A. Smith, D. Bainbridge, and I. H. Witten, “The New Zealand Digital Library MELodyinDEX,” Digital Library Magazine, May 1997.
[63] MIDI Manufaturers Association, Los Angeles, California, The Complete Detailed MIDI 1.0 Specification, 1996.
[64] Mongeau, M., D. Sankoff, “Comparison of Musical Sequences,” Computer and the Humanities, 1990.
[65] Moon, Y.S., K.Y. Whang, and W.S. Han, “General Match: A Subsequence Matching Method in Time-series Databases Based on Generalized Windows,” Proceedings of ACM SIGMOD International Conference on Management of Data, 2002.
[66] Mooney, R. J. and L. Roy, “Content-based book recommending using learning for text categorization,” Proceedings of ACM International Conference on Digital Libraries, 2000.
[67] Motwani, R., J. Widom, A. Arasu, B. Babcock, S. Babu, M. Datar, G. Manku, C. Olston, J. Rosenstein, and R. Varma, “Query processing, approximation, and resource management in a data stream management system,” Proceedings of Biennial Conference on Innovative Data Systems Research, 2003.
[68] MusicXML, http://www.recordare.com/.
[69] Narmour, E., The Analysis and Cognition of Basic Melodic Structure, The University of Chicago Press, Chicago, 1990.
[70] Navarro, G., “A Guided Tour to Approximate String Matching,” ACM Computing Surveys, 2001.
[71] Needleman, S.B. and C.D. Wunsch, “A general method applicable to the search for similarities in the amino acid sequence of two proteins,” Journal of Molecular Biology, 1970.
[72] Ordonez, C., E. Omiecinski, and N. Ezquerra, “A Fast Algorithm to Cluster High Dimensional Basket Data,” Proceedings of IEEE International Conference on Data Mining, 2001.
[73] Park, S., W.W. Chu, J. Yoon, and C. Hsu, “Efficient Searches for Similar Subsequences of Different Lengths in Sequence Databases,” Proceedings of International Conference on Data Engineering, 2000.
[74] Pearson, W.R. and D.J. Lipman, “Improved tools for Biological Sequence Comparison,” Processing of National Academy of Sciences, 1998.
[75] Pei, J., J. Han, B. Mortazavi-Asl, H. Pinto, Q. Chen, U. Dayal, M.C. Hsu, “PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth,” Proceedings of IEEE International Conference on Data engineering, 2001.
[76] Pickens, J., “A Survey of Feature Selection Techniques for Music Information Retrieval,” Proceedings of International Symposium on Music Information Retrieval, 2001.
[77] Pirkola, A., H. Keskustalo, E. Leppanen, A.P. Kansala, and K. Jarvelin, “Targeted s-gram matching: a novel n-gram matching technique for cross- and monolingual word form variants,” Information Research, 2002.
[78] Pirnimaki, A., “Indexing Music Databases Using Automatic Extraction of Frequent Phrases,” Proceedings of International Symposium on Music Information Retrieval, 2002.
[79] Rafiei, D. and A. Mendelzon, “Similarity-Based Queries for Time Series Data,” Proceedings of ACM SIGMOD International Conference on Management of Data, 1997.
[80] Robertson, A.M. and P. Willett, “Applications of n-grams in textual information systems,” Journal of Documentation, 1998.
[81] Rolland, P.Y., “FIExPat: Flexible Extraction of Sequential Patterns,” Proceedings of IEEE International Conference on Data Mining, 2001.
[82] Roussopoulos, N., S. Kelley, and F. Vincent, “Nearest Neighbor Queries,” Proceedings of ACM International Conference on Management of Data, 1995.
[83] Rucker, J. and M. J. Polanco, “Personalized Navigation for the Web,” Communications of the ACM, 1997.
[84] Sakurai, Y., M. Yoshikawa, S. Uemura, and H. Kojima, “The A-tree: An index structure for high dimensional spaces using relative approximation,” Proceedings of International Conference on Very Large Data Bases, 2000.
[85] Salton, G., “Automatic text processing: the transformation, analysis, and retrieval of information by Computer,” Addison Wesley, 1989.
[86] Sayood, K., “Introduction to Data Compression,” 2nd Edition, Morgan Kaufmann, 2000.
[87] Selfridge-Field, E., “Conceptual and representational issues in melodic comparison,” Melodic similarity: concepts, procedures, and applications (Computing in Musiccology:11), The MIT Press, 1998.
[88] Sharadanand, U. and P. Maes, “Social Information Filtering: Algorithms for Automating ‘Word of mouth’,” Proceedings of CHI’95 Conference on Human Factors in Computing Systems, 1995.
[89] Smith, B. and P. Cotter, “A Personalized Television Listings Service,” Communications of the ACM, 2000.
[90] Uitdenbogerd, A. L. and J. Zobel, “Manipulation of Music For Melody Matching,” Proceedings of ACM International conference on Multimedia, 1998.
[91] Uitdenbogerd, A. and J. Zobel, “Melodic Matching Techniques for Large Music Databases,” Proceedings of ACM Multimedia, 1999.
[92] Ukkonen, E., “Algorithms for approximate string matching,” Information and Control, 1985.
[93] Widmer. G., “Learning Expressive Performance: The Structure-Level Approach,” Journal of New Music Research, 1996.
[94] Wu, S. and U. Manber, “Fast text searching allowing errors,” Communications of the ACM, 1992.
[95] Wu, Y. H., Y. C. Chen, and A.L.P. Chen, “Enabling Personalized Recommendation on the Web Based on User Interests and Behaviors,” Proceedings of IEEE International Workshop on Research Issues in Data Engineering (RIDE), 2001.
[96] Yan, H., K. Chen, and L. Liu, “Efficiently Clustering Transactional Data with Weighted Coverage Density,” Proceedings of ACM International Conference on Information and Knowledge Management, 2006.
[97] Yanase, T., “Phrase Based Feature Extraction for Musical Information Retrieval,” Proceedings of IEEE Pacific Rim Conference on Communications, Computers, and Signal Processing, 1999.
[98] Yang, Y. and B. Padmanabhan, “Segmenting Custom Transaction Using a Pattern-Based Clustering Approach,” Proceedings of IEEE international Conference on Data Mining, 2003.
[99] Yao, Y., and J. Gehrke, “Query Processing for Sensor Networks,” Proceedings of Conference on Innovative Data Systems Research, 2003.
[100] Yu, C.F., The new sound from ancestors: a hundred indigenous folk songs in Taiwan, Taiwan Yuan-Yuan Indigenous Culture Troupe, 1998.
[101] Zobel, J. and P. Dart, “Finding approximate matches in large lexicons,” Software – practice and experiences, 1995.