Loading...
|
Please use this identifier to cite or link to this item:
https://nccur.lib.nccu.edu.tw/handle/140.119/38539
|
| Title: | 有效率的探勘演化重覆性樣式演算法
Efficient algorithms for mining evolutionary repeating patterns |
| Authors: | 陳俊豪 |
| Contributors: | 沈錳坤
陳俊豪 |
| Keywords: | 演化重覆性樣式
音樂動機 |
| Date: | 2007 |
| Issue Date: | 2010-04-09 14:49:28 (UTC+8) |
| Abstract: | 一個片段在序列中重複出現的現像稱之為「重覆性樣式」。這樣的重覆性樣式在許多不同的領域像是音樂分析以及生物資訊演算法上伴演著重要的角色。
在音樂分析上，重覆性樣式即為一段連續的音符在樂曲中重覆出現的現象。在樂理中，這樣的重覆出現的片段即稱之為「音樂動機」，在貝多芬的第五交響曲中，即利用四個簡單的音符“sol sol sol mi”做為音樂動機，並利用這個音樂動機創作出整首交響曲。分析音樂的動機將有助於應用在音樂檢索上為音樂建立出適合的索引。
動機的型式並非永遠一成不變，作曲者可能透過些微的變化，在樂曲中重覆出現。重覆性的片段在序列中未產生任何變變化而重覆出現的現象稱之為「精確重覆」；在序列中的重覆片段果存在些微的變化，且這些變化的序列皆與某一個序列相似則稱之為「近似重覆」。
精確重覆性樣式及近似重覆性樣式的探勘，已在過去的許多研究中被提出。在本篇論文中，我們研究一種新的重覆性樣式，在每個重覆出現的序列中，都和前一個出現的序列相似，而非與某一個特定的序列相似，這樣的重覆樣式稱之為「演化重覆性樣式」。本篇論文提出演算重覆性樣式的問題，並提出兩種基本的演算法，改善在探勘演化重覆性樣式時的效率；最後結合兩種演算法的特性，提出一種綜合演算法，同時擁有上述兩個演算法的優點，獲得更好的效率。最後並在實驗中證明我們所提出的演算法能夠得到良好的執行效率。
A repeating pattern is a substring of a sequence, which repeats several times in the sequence. Repeating patterns play an important role in a variety of applications such as music analysis and bioinformatics.
In music analysis, a repeating pattern is a sequence of notes repeats several times in a music object. In musicology, a repeating pattern corresponds to a motive which is a salient recurring segment of notes that may be used to construct all or some of the melody and themes. The well-know segment "sol-sol-sol-mi" in Beethoven`s Symphony no 5 is an example of motives. The repeating pattern is an efficient semantic representation to index music sequences for content-based music retrieval.
The repetition of a motive may have some variations and not necessarily be an exact repetition in the music object. For example, motivic development is a composition technique that allows a composer to generate the entire music based on a motive which repeats in the form of variations. Moreover, it is possible that a motive may evolve in certain types of composition.
Some exact and approximate repeating pattern mining algorithms have been developed. In this paper, a new form of approximate repeating patterns, evolutionary repeating patterns is investigated.
In evolutionary repeating pattern, each instance is similar to the previous one, rather than the original pattern. We proposed two approaches, matrix-based and Apriori-based ones, to discover the evolutionary repeating patterns. Moreover, we also present a hybrid approach to combine features of the above two approaches. Scale-up experiments show that the proposed algorithms perform well. |
| Reference: | [1] 黎翁斯坦, 潘皇龍譯, “音樂的結構與風格”, 全音樂譜出版社, 1974.
註：Leon Stein, “Structure & Style：The Study and Analysis of Musical Forms”, Summy-Birchard Music, 1979.(expanded edition)
[2] R. Agrawal, and R. Srikant, "Fast Algorithm for Mining Association Rules," Proc. of International Conference on Very Large Data Bases VLDB, 1994.
[3] R. Agrawal, and R. Srikant, “Mining Sequential Patterns,” Proc. of International Conference on Data Engineering ICDE, 1995.
[4] T. Crawford, C. S. Iliopoulos, R. Winder, and H. Yu. “Approximate Musical Evolution,” Proc. of Artificial Intelligence and Simulation of Behaviour Symposium AISB, 1999.
[5] J. Han, G. Dong, and Y. Yin, “Efficient Mining of Partial Periodic Patterns in Time Series Databases,” Proc. of International Conference on Data Engineering ICDE, 1999.
[6] C.S. Iliopoulos, M. Kumar, L. Mouchard, and S. Venkatesh, “Motif Evolution in Polyphonic Musical Sequences,” Proc. of Australasian Workshop on Combinatorial Algorithms AWOCA, 2000.
[7] C. S. Iliopoulos, K. Lemström, M. Nuyad, and Y. J. Pinzón, “Evolution of Musical Motifs in Polyphonic Passages,” Proc. of Symposium on AI and Creativity in Arts and Science AISB, 2002
[8] A. M. Helena “Finding All Maximal Frequent Sequences in Text,” Proc. of International Conference on Machine Learning ICML, 1999.
[9] J. L. Hsu, A. L. P. Chen, and H. C. Chen, “Finding Approximate Repeating Patterns from Sequence Data,” Proc.of Intertional Symposium on Music Information Retrieval ISMIR, 2004.
[10] J. L. Hsu, C. C. Liu, and A. L. P. Chen, “Efficient Repeating Pattern Finding in Music Database,” Proc. of Conference on Information and Knowledge Management CIKM, 1998.
[11] J. L. Hsu, C. C. Liu, and A. L. P. Chen, “Discovering Non-Trivial Repeating Patterns in Music Data,” IEEE Transactions on Multimedia, 2001.
[12] J. L. Koh, and Y. T. Kung “An Efficient Approach for Mining Top-K Fault-Tolerant Repeating Patterns,” Proc. of International Conference on Database Systems for Advanced Applications DASFAA, 2006.
[13] C. C. Liu, J. L. Hsu, and A. L. P. Chen, “Efficient Theme and Non-Trivial Repeating Pattern Discovering in Music Databases,” Proc. of International Conference on Data Engineering ICDE, 1999.
[14] N. H. Liu, Y. H. Wu, and A. L. P. Chen “An Efficient Approach to Extracting Approximate Repeating Pattern in Music Databases,” Proc. of International Conference on Database Systems for Advanced Applications DASFAA, 2005.
[15] Y. L. Lo, and C. Y. Chen “Fault Tolerant Non-trivial Repeating Pattern Discovering for Music Data,” Proc. of International Conference on Computer and Information Science ICIS, 2007.
[16] Y. L. Lo, W. L. Lee, and L. H. Chang “True suffix tree approach for discovering non-trivial repeating patterns in a music object,” Multimedia Tools and Applications, 2007.
[17] Y. L. Lo, and W. L. Li, “Linear Time for Discovering Non-trivial Repeating Pattern in Music Database,” Proc. of International Conference on Multimedia and Expo ICME, 2004.
[18] C. Meek, and W. P. Birmingham “Thematic Extractor,” Proc.of Intertional Symposium on Music Information Retrieval ISMIR, 2001.
[19] H. H. Shin, S. S. Narayanan, and C. C. J. Kuo, “A Dictionary Approach to Repetitive Pattern Finding In Music,” Proc. of International Conference on Multimedia and Expo ICME, 2001.
[20] P. Weiner (1973). “Linear Pattern Matching Algorithm,” Proc. of Symposium on Switching and Automata Theory. pp.1-11, 1973. |
| Description: | 碩士
國立政治大學
資訊科學學系
95753010
96 |
| Source URI: | http://thesis.lib.nccu.edu.tw/record/#G0095753010 |
| Data Type: | thesis |
| Appears in Collections: | [資訊科學系] 學位論文
|
Files in This Item:
| File |
Size | Format | |
|---|
| index.html | 0Kb | HTML2 | 325 | View/Open |
|
All items in 政大典藏 are protected by copyright, with all rights reserved.
|
