循序樣式探勘是一門研究如何從序列資料庫裡找出頻繁循序樣式的資料探勘方法，過去的序列資料探勘方法大致可分成兩大類[2]：Apriori-like methods [7][8][9][23]和Pattern-growth methods [10][12][16][17][20]。在一個循序樣式中，兩事件間隔發生的時間機率可以提供更多資訊給決策者分析與預測關聯樣式的變化。然而先前的研究並沒有發展出能於探勘樣式的過程裡同時找出此機率的技術。因此，為了提供這樣的資訊，我們擴充PrefixSpan演算法且發展成一套新的演算法PCTP(PrefixSpan Considering Time Probability)。此方法也可以藉由考量最小機率的限制，來減少探勘過程中產生的樣式數量。
　　本研究以實驗來比較PCTP與現存的循序樣式探勘方法，結果顯示PCTP可彌補過去相關方法的不足。由效能研究中亦証明－PCTP是一個能精減關聯樣式並可為循序樣式提供額外時間機率資訊的有效方法。

Sequential Pattern Mining is a data mining method that is used to find frequent sequential patterns in a sequential database. The conventional sequence data mining methods can be divided into two categories[2]: Apriori-like methods [7][8][9][23] and Pattern-growth methods[10][12][16][17][20].  Time-interval probability between two events in a sequential pattern can provide more information for decision maker to analyze and predict the behavior of correlated pattern.  However, in the previous studies there is no technique developed to simultaneously discover the probability in the pattern mining process.  Thus, to provide such information, we extend the PrefixSpan method and develop a new sequential pattern mining approach, PCTP(PrefixSpan Considering Time Probability).  The proposed approach can also reduce the number of patterns produced in the mining process by considering the minimize probability constraint.
  The proposed approach is compared to existing sequential pattern mining methods to show how they complement each other to discover association rules.  Our performance study shows that PCTP is a valuable approach to condense the correlated patterns and provide additional time-interval probability information for sequential pattern.

目錄
目錄	I
圖目錄	II
表目錄	III
1	緒論	1
1.1	前言	1
1.2	研究背景	2
1.3	研究動機與目的	5
1.4	論文架構	6
2	文獻探討	7
2.1	循序樣式探勘裡的常用術語	7
2.2	AprioriAll演算法[17]	9
2.3	GSP演算法[9]	13
2.4	FreeSpan演算法[16]	17
2.5	PrefixSpan演算法[20]	21
3	考量時間機率之循序樣式探勘方法	24
3.1	符號定義	24
3.2	PCTP：演算法	26
3.3	使用PCTP探勘：範例說明	30
4	實驗研究	35
4.1	系統模擬	35
4.2	PCTP和PrefixSpan產生樣式比較	37
4.3	效能評估	40
5	結論與未來展望	44
參考文獻	46
附錄	49


圖目錄
圖2-1：以Customer Id和Transaction Time排序的資料庫	9
圖2-2：顧客序列的資料庫	10
圖2-3：大項目集	10
圖2-4：轉換後的資料庫	11
圖2-5：AprioriAll演算法	11
圖2-6：長度為1的大序列集合L1	12
圖2-7：長度為2的候選樣式集(僅列出部分，未包含同時發生)	12
圖2-8：長度為2的大序列集合L2	12
圖2-9：左圖為L3，右圖為L4	12
圖2-10：一個分類層級的例子	14
圖2-11：資料庫範例	15
圖2-12：候選樣式產生範例	16
圖2-13：資料序列範例(左)、替換表示(右)	16
圖2-14：FreeSpan演算法流程步驟	20
圖2-15：PrefixSpan演算法流程步驟	21
圖3-1：演算法流程圖	27
圖3-2：Procedure cal_probability	29
圖4-1：交易與交易明細資料表	37
圖4-2：顧客與產品資料表	37
圖4-3：interval對執行時間、樣式個數與階數的影響	40
圖4-4：支持度閥值 vs. 執行時間	41
圖4-5：支持度閥值 vs. 頻繁樣式個數	41
圖4-6：序列筆數 vs. 執行時間	42
圖4-7：序列筆數 vs. 頻繁樣式個數	43


表目錄
表2-1：一個序列資料庫	17
表2-2：掃描表2-1後的頻繁項目矩陣	18
表2-3：產生自頻繁項目矩陣的樣式	18
表2-4：四個映射資料庫和其循序樣式	19
表2-5：一個序列資料庫	22
表2-6：一階頻繁樣式映射資料庫	23
表2-7：所有的頻繁樣式	23
表3-1：一個時間序列資料庫	30
表3-2：PCTP一階頻繁樣式	31
表3-3：Prefix a的映射資料庫	32
表3-4：Prefix a映射資料庫裡的頻繁項目	32
表3-5：計算頻繁樣式抵達率所需的相關參數值	32
表3-6：抵達率λ計算過程(以ab為例)	32
表3-7：Prefix ab的映射資料庫	33
表3-8：Prefix af的映射資料庫	33
表3-9：prefix a的二階頻繁樣式時間機率	34
表4-1：序列資料生成參數	36
表4-2：PCTP(60)和PrefixSpan產生的樣式數比較	38
表4-3：比較PCTP(100)和PrefixSpan產生的樣式數	39

[1]	 李官陵、阮士峰，「資料探勘在股市序列型樣的應用」，東華大學資訊工程所碩士論文，July 2004。
[2]	 陳彥良、許秉瑜、陳仕昇，「序列樣式探勘之研究」，中央大學資訊管理所博士論文，June 2003。
[3]	 張昭憲、郭家君，「應用於分散式系統之平行循序樣本探勘」，淡江大學資訊管理所碩士論文，June 2007。
[4]	 楊燕珠、陳仕昇、林哲民，「利用多重支持度探勘部分週期性樣式」，大同大學資訊經營所碩士論文，June 2005。
[5]	 蔣定安、李紹綸，「從交易資料庫中探勘時序性序列型樣」，淡江大學資訊工程所博士論文，June 2004。
[6]	 謝浩明、黃盈彬，「不連續序列資料挖掘之研究－以股市為例」，中央大學資管所碩士論文，May 2002。
[7]	 Agrawal, R., Srikant, R., “Fast Algorithms for Mining Association Rules,” In Proc. 1994 Int. Conf. Very Large Data Bases (VLDB’94), Santiago, Chile, September 1994, pp. 487-499.
[8]	 Agrawal, R., Srikant, R., “Mining Sequential Patterns,” In Proc. 1995 Int. Conf. Data Engineering (ICDE’95), Taipei, Taiwan, March 1995, pp. 3-14.
[9]	 Agrawal, R., Srikant, R., “Mining Sequential Patterns: Generalizations and Performance Improvements,” In 5th Int. Conf. Extending Database Technology, March 1996.
[10]	 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, 2003, pp. 343-354.
[11]	 Chen, Y.L., Chen, S.S., and Hsu, P.Y., “Mining hybrid sequential patterns and sequential rules,” Information Systems, Vol. 27, No.5, 2004, pp. 345-362.
[12]	 Chen, Y.L., Hu, Y.H., “Constraint-based sequential pattern mining: The consideration of recency and compactness,” Decision Support Systems (DSS’42), 2006, pp. 1203-1215.
[13]	 Elsayed, A.E., Reliability Engineering, New York, NJ: Addison Wesley Longman Inc., 1996, pp. 263-278.
[14]	 Garofalakis, M., Rastogi, R., and Shim, K., “Mining Sequential Patterns with Regular Expression Constrains,” IEEE Transactions on Knowledge and Data Engineering, Vol. 14, No.3, May/June 2002, pp. 530-552.
[15]	 Han, J., Pei, J., and Yin, Y., “Mining Frequent Patterns without Candidate generation,” In Proc. ACM-SIGMOD Int. Conf. Management of Data (SIGMOD’00), Dallas, TX, May 2000, pp. 1-12.
[16]	 Han, J., Pei, J., Mortazavi-Asl, B., Chen, Q., Dayal, U., and Hsu, M.-C., “FreeSpan: Frequent Pattern-Projected Sequential Pattern Mining,” In Proc. Int. Conf. Knowledge Discovery and Data Mining (KDD’00), Boston, MA, August 2000, pp. 355-359.
[17]	 Han, J., Pei, J., and Wang, W., “Mining Sequential Patterns with Constraints in Large Databases,” In Proc. 2002 Int. Conf. on Information and Knowledge Management (CIKM’02), Washington, D.C., November 2002.
[18]	 IBM, Quest Data Mining Project, IBM Almaden Research Center, San Jose, CA 95120.
<http://www.almaden.ibm.com/software/quest/Resources/index.shtml>
[19]	 Orlando, S., Perego, R. and Silvestri, C., “A new algorithm for gap constrained sequence mining,” Symposium on Applied Computing (SAC’04), 2004, pp. 540-547.
[20]	 Pei, J., Han, J., Mortazavi-Asl, B., Pinto, H., Chen, Q., Dayal, U., and Hsu, M.-C., “PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth,” In Proc. 2001 Int. Conf. Data Engineering (ICDE’01), 2001, pp. 215-224.
[21]	 Pei, J., Han, J., Mortazavi-Asl, B., Wang, J., Pinto, H., Chen, Q., Dayal, U., and Hsu, M.-C., “Mining Sequential Patterns by Pattern-Growth: The PrefixSpan Approach,” IEEE Transactions on Knowledge and Data Engineering, Vol. 16, No. 11, November 2004, pp. 1424-1440.
[22]	 Wikipedia, “Poisson process”　<http://en.wikipedia.org/wiki/Poisson_process>, 2008. (Accessed February 18, 2008)
[23]	 Zaki, M. J., “Sequence mining in categorical domains: Incorporating constraints,” CIKM, 2000, pp. 422-429.