循序樣式探勘的目的是從資料庫中，尋找頻繁出現且有順序的樣式，通常這些樣式會再被轉換成先前所不知道的、有用的與有價值的資訊。由於資料庫中通常存在大量且長時間的資料，因此循序樣式探勘往往需要花上大量時間。但是一般的頻繁循序樣式探勘演算法無法針對要尋找之頻繁循序樣式的時間條件加以限制，使得探勘得到的頻繁循序樣式太多且不易應用。探勘最長頻繁循序樣式雖可得到意義相同且較精簡的樣式集合，但針對長度為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.

目錄
第1章	緒論	1
1.1	研究背景	1
1.2	研究動機與目的	2
1.3	論文架構	4
第2章	文獻探討	5
2.1	循序樣式探勘	5
2.1.1	Apriori演算法	5
2.1.2	FP-Growth演算法	6
2.1.3	PrefixSpan演算法	6
2.2	最長頻繁循序樣式與封閉頻繁循序樣式探勘演算法：	7
2.2.1	CloSpan演算法	7
2.2.2	TFP演算法	7
2.2.3	BIDE演算法	8
2.2.4	PMSPM演算法	8
2.2.5	ToMMS演算法	9
2.3	有時間條件的循序樣式探勘演算法	9
2.3.1	PCTP演算法	9
2.3.2	I-Apriori與I-PrefixSpan演算法	10
2.3.3	CTSP演算法	11
2.3.4	CFR-PostfixSpan演算法	11
第3章	PMSPMTC演算法	13
3.1	背景	13
3.2	PMSPMTC演算法基本名詞定義	15
3.3	PMSPMTC演算法的探勘流程	19
第4章	實驗	31
4.1	實驗一	32
4.2	實驗二	37
4.3	實驗三	39
4.4	實驗四	40
4.5	實驗五	41
4.6	實驗結果	42
第5章	PMSPMTC演算法之應用	44
5.1	資料集簡介	44
5.2	資料集處理	45
5.3	資料集調整	46
5.4	車流量變化之頻繁循序樣式探勘	47
5.5	連續的車流量變化之頻繁循序樣式探勘	51
5.6	車流量變化的頻繁循序樣式探勘之問題與解決方式	54
5.7	探勘結果說明	58
第6章	結論	60
參考文獻	62

圖目錄
圖 1：PMSPMTC演算法流程圖	21
圖 2：有無時間限制條件之探勘時間比較	33
圖 3：有無時間條件之二階探勘時間比較	34
圖 4：不同支持度之探勘時間比較	38
圖 5：相同支持度下有無recency與時間範圍限制之探勘時間比較	39
圖 6：不同recency限制之探勘時間比較	41

表目錄
表 一：交易資料庫	20
表 二：1階候選樣式及CMS的內容	22
表 三：掃描資料庫後之F1， N1，CMFS	23
表 四：刪除非頻繁樣式後之交易資料庫	24
表 五：CMS修剪前後比較表	24
表 六：2階候選循序樣式	25
表 七：走訪候選樹後之F2、N2與CMFS	27
表 八：CMS更新過程	29
表 九：判斷CMS中序列是否為頻繁之過程	30
表 十：交易資料庫之探勘結果	30
表 十一：實驗資料集參數說明	32
表 十二：各階段頻繁循序樣式之數量	34
表 十三：資料集：D10kN1000T10S100、無時間條件限制下之各回合所獲得的最長頻繁循序樣式數量	36
表 十四：資料集：D25kN1000T10S100、無時間條件限制下之各回合所獲得的最長頻繁循序樣式數量	37
表 十五：資料集：D50kN1000T10S100、支持度為0.3%、無時間條件限制下之各回合所獲得的最長頻繁循序樣式數量	37
表 十六：相同序列數量不同支持度下之探勘情形	38
表 十七：有無recency與時間範圍限制之探勘情形	40
表 十八：重複記錄、不重複記錄相同最長候選序列之探勘時間比較	42
表 十九：Dodgers.data中部分資料	45
表 二十：調整後序列	47
表 二十一：無時間限制條件、recency為十三點與recency為十九點情況下探勘得到之MFS數量	48
表 二十二：無時間限制條件、recency為十三點情況下之頻繁、非頻繁循序樣式數量比較	49
表 二十三：無時間限制條件、recency為十三點與recency為十九點情況下之11階最長頻繁循序樣式	51
表 二十四：recency為十三點、max_length為三個小時的4階最長頻繁循序樣式	52
表 二十五： recency為下午二點、max_length為三個小時的4階最長頻繁循序樣式	53
表 二十六：資料集中之序列範例	55
表 二十七：車流量分級後之探勘結果	56
表 二十八： recency為十九點、max_length為三個小時的4階最長頻繁循序樣式	57
表 二十九： recency為晚上十點、max_length為三個小時的4階最長頻繁循序樣式	58
表 三十：max_length為三個小時，符合recency為十九點但不符合recency為晚上十點之4階最長頻繁循序樣式	58

[1]	吳鎮成，〈PMSPM:夾擊最長循序樣式探勘演算法〉，淡江大學資訊管理學系研究所碩士論文，2008。
[2]	張家汶，〈具時間限制之高效率序列樣式探勘演算法〉，逢甲大學資訊工程研究所碩士論文，2006。
[3]	張耕，〈考量時間機率之循序樣式探勘方法〉，淡江大學資訊管理學系研究所碩士論文，2007。
[4]	Agrawal, R. and Srikant, R., “Fast algorithm for mining association rules,” in Proceedings of the 20th International Conference on VLDB, pp. 487-499, 1994.
[5]	Agrawal, R. and Srikant, R., “Mining sequential patterns,” in Proceedings of the 17th International Conference on Data Engineering, pp. 3-14, 1995.
[6]	Bayardo, R. J., “Efficiently mining long patterns from databases,” in Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data, pp. 85-93, 1998.
[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.
[10]	Han, J. and Kamber, M., “Data mining: Concepts and techniques,” Academic Press, New York, 2001.
[11]	Han, J., Wang, J., Lu, Y. and Tzvetkov, P., “Mining top-k frequent closed patterns without minimum support,” in Proceedings of IEEE International Conference on Data Mining, pp. 211-218, 2002.
[12]	Lin, M.Y., Hsueh, S. and Chang. C., “Mining closed sequential patterns with time constraints,” Journal of Information Science and Engineering, pp. 33-46, 2008.
[13]	Lin, D., and Kedem, Z. M., “Pincer-search: An efficient algorithm for discovering the maximum frequent set,” IEEE Transactions on Knowledge and Data Engineering, vol. 14, no. 3, pp. 553-566, 2002.
[14]	Pei, J., Han, J., Mortazavi-Asl, B. and Zhu, H., “Mining access pattern efficiently from web logs,” in Proceedings of the 2000 Pacific-Asia Conference on Knowledge Discovery and Data Mining, pp. 396-407, 2000.
[15]	Pei, J., Han, J., Moryazavi-Asl, B., Pinto, H., Chen, Q., Dayal, U. and Hsu, M, C., “PrefixSpan: Mining sequential patterns efficiently by prefix-projected pattern growth,” in Proceedings of the 17th International Conference on Data Engineering , pp. 215-224, 2001.
[16]	Pei, J., Han, J. and Yin, Y., “Mining frequent patterns without candidate generation,” in Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, pp. 1-12, 2000.
[17]	Wang, J. and Han, J., “BIDE: Efficient mining of frequent closed sequences,” in Proceedings of the 2004 International Conference on Data Engineering, pp. 79–90, 2004.
[18]	Yan, X., Han, J. and Afshar, R., “CloSpan: Mining closed sequential patterns in large datasets,” in Proceedings of 2003 SIAM International Conference on Data Mining, pp. 166-177, 2003.