序列型樣(Sequential Patterns)是企業從事行銷時的一項重要的資訊。但在探勘時序列型樣面臨三個重大的問題：1、序列型樣只有考慮交易的順序性，並沒有考慮時間因素。2、探勘出來的序列型樣太多，並不是全部的序列型樣都是決策者有興趣的。3、挖掘序列型樣的效率不佳。針對以上的問題，本篇論文提出以下的解決方式：1、在傳統序列型樣中加入時間概念，例如：買A產品之後在經過3至5天又會買B產品。2、提供使用者的下達有興趣的限制式(Constraint Formulae)，避免產生過多的序列型樣。3、利用限制式模式來設計較有效率的序列型樣演算法。綜合以上三項解決方式，我們提出具有限制式之時間性序列型樣(CTSP, Constrained Temporal Sequential Patterns)演算法，CTSP演算法包含兩種挖掘時間區間的方法：一種是挖掘時間區間之基因演算法(GAMTI, Genetic Algorithm for Mining Time Intervals) 演算法，GAMTI利用基因演算法的概念找出較合理的時間區間，另一種是變異係數擴張法(EVC, Expanding of Variation Coefficient)，利用統計學上的變異係數概念找出較合理的時間區間。針對限制式方面，提出前因後果限制式(Antecedent Constraints and Consequent Constraints)，並且根據前因後果限制式設計CTSP演算法，找出決策者有興趣的時間性序列型樣。

Sequential patterns are very useful for marketing. Recently, many researchers have been working on mining sequential patterns. However, three problems remain to be resolved. First, only orders between events are considered. The time interval between the occurring of two events is not considered. Second, too many rules are generated and most of them are not useful. Third, the existing mining algorithms are not efficient due to the enormous search space of the mining problem. In this thesis, we propose solutions for the above listing problems. First, we introduce the time interval concept in sequential patterns. For example, we may find a rule states that if a user buys item A then within 3 to 5 days he will buys item B. Second, we allow a user to specify constraints on sequential patterns. As such, only rules that are interesting to the user will be mined. Furthermore, we take the advantage of constraints and develop two efficient mining algorithms. The GAMTI algorithm is a genetic algorithm that finds the optimal time interval between any two related events. While the EVC algorithm applies the concept of variation coefficient in Statistics to find the optimal time interval. Both GAMTI and EVC algorithms take advantage of constraints to find the rules that are interesting to the users efficiently.

目 錄
第一章 緒論 ..............................................1
1.1資料挖掘簡介……………………………………………………1
1.2研究目的與動機…………………………………………………3
1.3論文架構…………………………………………………………4
第二章 相關研究……………………………………………………...5
第三章　挖掘具有限制式之時間性序列型樣………………………….8
3.1挖掘具有限制式之時間性序列型樣之定義與方法…….....11
　　　3.1.1 傳統之序列型樣……………………………………....11
3.1.2時間性之序列型樣……………………………………….13
3.1.3 具有限制式之時間性序列型樣…………………………31
3.2挖掘具有限制式之時間性序列型樣範例…………….......42
3.3挖掘具有限制式之時間性序列型樣演算法………………….47
第四章 實驗與評估…………………………………………........49
4.1實驗資料與說明……………………………………….......49
4.2實驗參數……………………………….………………......50
4.3實驗結果……………………………………………….......51
第五章 結論…………………………….……….................57
參考資料………………………………………………………........58

參考文獻
[1] Rakesh Agrawal and Remakrishnan Srikant. ”Mining Sequential Patterns,” In Proceedings of International Conference on Data Engineering, pages 3-14, 1995.
[2]Rakesh Agrawal, and et al. ”Mining Sequential Patterns:Generalizations and Performance Improvements,” In Proc. Of the EDBT’96,Avignon, France, Sept 1996.
[3] Jiawei Han, Wan Gong and Yiwen Yin. “Mining Segment-Wise Periodic Patterns in Time-Related Databases,” In Proc,1998 Int’l Conf. On Knowledge Discovery and Data Mining (KDD’98), New York City, NY, August 1998.
[4] Jiawei Han, Guozhu Dong and Yiwen Yin,.”Efficient Mining of Partial Patterns in Time Series Database,” In Proc. 1999 Int. Conf. Data Engineering (ICDE'99), Sydney, Australia, April 1999, pages 106-115.
[5] Yingjiu Li, Peng Ning, X.Sea Wang and Sushil Jajodia, “Discovering Calendar-based Temporal Association rules,” To appear in Data and Knowledge Engineering, Elsevier Science, 2002.
[6] Claudio Bettini, X.Sean Wang, Sushil Jajodia, Jia-Ling Lin. “Discovering Temporal Relationships with Multiple Granularities in Time Sequences,” IEEE Transations on Knowledge and Data Engineering, Vol. 10 (2), 1998, pages 222-237.
[7] R. Ng, L. V. S. Lakshmanan, J. Han,and A. Pang. ”Exploratory Mining and Pruning
Optimizations of Constrained Association Rules,” In Proc. 1998 ACM-SIGMOD Int.
Conf. Management of Data(SIGMOD’98), pages 13-24, Seattle, WA, June 1998.
[8] L. V. S. Lakshmanan, J. Han,and A. Pang. ”Optimization of constrained frequent set
queries with 2-variable constraints,” In Proc. 1999 ACM-SIGMOD Int. Conf.
Management of Data(SIGMOD’99), pages 157-168, Philadelphia, PA, June 1999.
[9] J. Pei, J. Han. ”Can we push more constraints into frequent pattern mining?,” In Proc.
2000 Int. Conf. Knowledge Discovery and Data Mining (KDD’00), pages 350-354,
Boston, MA, Aug. 2000.
[10] Pei, J. Han, and L. V. S. Lakshmanan, “Mining Frequent Itemsets with Convertible
Constrants,” Proc. 2001 Int. Conf. On Data Engineering (ICDE’01), Heidelberg,
Germany, April 2001.
[11] S.J. Yen and A.L.P. Chen, “An Efficient Data Mining Technique for Discovering
Interesting Association Rules,” Proceedings of the 8th International Conference and
Workshop on Database and Expert Systems Applications, pp. 664-669, 1997.
[12] S.J. Yen and Yue-Shi Lee, “An Efficient Data Mining Technique for Discovering
Interesting Sequential Patterns,” Proceedings of IEEE International Conference on
Data Mining (ICDM'2001), pp.663-664, 2001.
[13] R. Agrawal and R. Srikant, "Fast Algorithm for Mining Association Rules," In Proc.
1994 Int'l Conf. VLDB, pp. 487-499, Santiago, Chile, Sep. 1994.
[14] A. Savasere, E. Omiecinski, and S. Navathe, "An Efficient Algorithm for Mining
Association Rules in Large Databases," Proc. 21th VLDB, pp. 432-444, 1995.