具有時間限制條件的最長頻繁循序樣式探勘演算法

Maximal Sequential Patterns Mining with Timing Constraints

林師晟(Shi-Cheng Lin)

指導教授 ： 周清江

淡江大學/管理學院/資訊管理學系碩士班/碩士(2010年)

https://doi.org/10.6846/TKU.2010.00835

摘要

循序樣式探勘的目的是從資料庫中，尋找頻繁出現且有順序的樣式，通常這些樣式會再被轉換成先前所不知道的、有用的與有價值的資訊。由於資料庫中通常存在大量且長時間的資料，因此循序樣式探勘往往需要花上大量時間。但是一般的頻繁循序樣式探勘演算法無法針對要尋找之頻繁循序樣式的時間條件加以限制，使得探勘得到的頻繁循序樣式太多且不易應用。探勘最長頻繁循序樣式雖可得到意義相同且較精簡的樣式集合，但針對長度為k之最長頻繁循序樣式探勘，不論是以PrefixSpan或是Apriori為基礎的演算法皆必須經過k個回合的探勘。當k值越大，所需的探勘回合數越多，探勘所需時間也越久。
本研究提出具有時間限制條件的最長頻繁循序樣式探勘演算法，可針對最長頻繁循序樣式所發生的時間加以限制，且具有不需k回合即可找出長度為k之最長頻繁循序樣式探勘的特性，並以實驗證明此演算法在設定時間條件後可以加快最長頻繁循序樣式探勘的速度。最後，我們將演算法應用於探勘車流量紀錄之資料庫，說明加上不同的時間限制條件後，可以得到具有不同時間意義之最長頻繁循序樣式。

關鍵字

循序樣式 ； 資料探勘 ； 最長頻繁循序樣式

並列摘要

The purpose of frequent sequential pattern mining is to find sequential patterns which occur more frequently than a given threshold. Normally these patterns are then transformed into previously-unknown useful and valuable information. Because of accumulated huge number of records in the database, frequent sequential pattern mining often takes a lot of time. Since most frequent sequential pattern mining algorithms do not have timing constraints, lots of frequent sequential patterns are found. It is difficult to decide which patterns among them are useful. Maximal frequent sequential pattern mining could obtain more compact patterns without losing any results obtained in frequent sequential pattern mining. However, most of these algorithms must complete k rounds to obtain maximal frequent sequential patterns with length k. The longer the maximal frequent sequential patterns, the more rounds the mining requires. The required mining time would be longer accordingly.
We propose an algorithm which obtains maximal frequent sequential patterns with timing constraints. This algorithm can restrict the occurring time-interval of the obtained maximal sequential patterns. It could obtain maximal frequent sequential patterns with length k in less than k rounds. We demonstrate that the timing constraints could speed up the mining process. Finally, we apply our algorithm to a database of traffic flow records, and illustrate how to obtain maximal frequent sequential patterns with different timing meaning according to selected timing constraints.

並列關鍵字

sequential pattern ； data mining ； maximal frequent sequential pattern

參考文獻

[1] 吳鎮成，〈PMSPM:夾擊最長循序樣式探勘演算法〉，淡江大學資訊管理學系研究所碩士論文，2008。

[3] 張耕，〈考量時間機率之循序樣式探勘方法〉，淡江大學資訊管理學系研究所碩士論文，2007。

[7] Chen, Y. L., Chiang, M. C. and Ko, M. T., “Discovering time-interval sequential patterns in sequence databases,” Expert Systems with Applications, vol. 25, no. 3, pp. 343-354, 2003.

[8] Chen, Y. L. and Hu, Y. H., “Constraint-based sequential pattern mining: The consideration of recency and compactness,” Decision Support Systems, vol. 42, no. 2, pp. 1203-1215, 2006.

[9] Ester, M. and Zhang, X., “A top-down method for mining most specific frequent patterns in biological sequence data,” in Proceedings of the 4th SIAM International Conference on Data Mining, pp. 90-101, 2004.