一個片段在序列中重複出現的現像稱之為「重覆性樣式」。這樣的重覆性樣式在許多不同的領域像是音樂分析以及生物資訊演算法上伴演著重要的角色。 在音樂分析上，重覆性樣式即為一段連續的音符在樂曲中重覆出現的現象。在樂理中，這樣的重覆出現的片段即稱之為「音樂動機」，在貝多芬的第五交響曲中，即利用四個簡單的音符“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.

在音樂中，組曲是一種特別的創作形式。組曲將多首音樂段落組合排列，並且在音樂段落之間加入間奏，形成一首音樂組曲。組曲的編曲重點在於音樂段落的編排順序及段落之間的連結。平時在宴會、舞會、餐廳、賣場等場合中，往往都會連續播放多首流行音樂。利用電腦編曲自動產生流行音樂組曲，將可提升播放音樂的銜接與流暢感。 因此，本研究利用資料探勘技術及音樂編曲理論，將多首音樂重新改編成一首組曲。系統首先將每首音樂分段並找出每首音樂的代表段落。接著，系統根據代表段落間的相似度編排順序。最後，為了達到組曲中音樂段落連接的流暢性，我們以模型訓練的方式在段落連結間加入間奏。系統從訓練資料學習產生旋律發展、和弦進程與節奏的模型，接著分析代表段落的動機、旋律、和弦及節奏，使得組曲編曲後的段落連結更為流暢且完整。本研究以流行音樂鋼琴伴奏曲為測試資料，我們分別邀請三十四位受過音樂訓練與未受音樂訓練的測試者，針對本研究所提出的鋼琴伴奏節奏辨識、代表段落萃取、段落順序編排及間奏產生，評估其效果。實驗結果顯示，本研究所提出的順序編排與間奏產生技術，對於組曲的流暢感，有著相當大的幫助。 / In music, a medley is an organized piece composed from segments of existing pieces. Ordering and bridge for connection between segments are the important elements for medley arrangement. Automatic medley arrangement is helpful for playing a set of music continuously which is common in banquet, party, restaurant, shopping mall, etc.. This thesis aims to develop the automatic medley arrangement method by using data mining techniques and music arrangement theory. The proposed method first segments each music and discovers the significant segment from each music. Then, the linear arrangement based on the similarities between significant segments is generated. Finally, in order to connect segments smoothly in the medley, the bridge between two segments is generated and inserted by using model training. Three models, melody progression, chord progression and rhythm models are learned from training data. For the experiments, testing data is collected from popular piano music and thirty-four people are invited to evaluate the effectiveness of the rhythm recognition of accompaniment, the extraction of significant segment, the linear arrangement of segments, and the creation of bridge. Experimental results show that the proposed medley arrangement method performs well.