- 學位論文
廣度優先之序列性規則資料探勘方法
Efficient Sequential Pattern Mining by Breadth-First Approach
摘要
自從GSP演算法提出之後，許多相關的演算法被提出來且大多專注在找尋所有序列樣式。CloSpan演算法首先提出找尋封閉集合。封閉集合比全集合更精簡有效，且具有相同的表達能力。因此，CloSpan就以PrefixSpan演算法為基礎，加上兩個其稱為backward sub-pattern與backward super-pattern的刪減技巧，有效地找出封閉集合。 因此我們提出一個新的演算法以找尋封閉集合。然而不同於之前演算法多採深度優先的策略，我們的演算法是屬於廣度優先的方法。另外，之前提出的演算法鮮有明顯地利用項目的順序關係(item ordering)來強化找尋樣式的效率。我們利用定位資料串列(positional data list)來保存項目的順序關係。我們利用這些資料來幫助樣式(pattern)的產生，並依此提出了兩種刪減技巧分別為backward super-pattern condition與same positional data condition。為了確保儲存最後結果的柵格(lattice)的正確性與簡潔，我們另外還針對一些特殊情況做處理。由實驗的結果顯示，我們的演算法相較於CloSpan在中大型的資料庫與小的支持度（support）的狀況下都有較優良的表現。
並列摘要
Since the GSP algorithm is proposed to mine sequential patterns in sequence databases, many methods have been proposed and mostly focused on mining the complete set of frequent patterns. The CloSpan algorithm first suggested that the closed set of sequential patterns is more compact and has the same expressive power with respect to the full set. Based on the PrefixSpan algorithm, CloSpan added two pruning techniques, backward sub-pattern and backward super-pattern, to efficiently mine the closed set. Therefore, in this thesis, we propose a new sequential pattern mining algorithm to mine closed sequences. However, instead of depth-first searching used in many previous methods, we adopt a breadth-first approach. Besides, previous methods seldom utilize the property of item ordering to enhance efficiency. We used a list of positional data to reserve the information of item ordering. By using these positional data, we developed two main pruning techniques, backward super-pattern condition and same positional data condition. To ensure correct and compact resulted lattice, we also manipulated some special conditions. From the experimental results, our algorithm outperforms CloSpan in the cases of moderately large datasets and low support threshold.