循序樣式探勘主要是從序列資料庫中，找出與時間相關的行為樣式。過去針對循序樣式探勘所提出的方法中，多半沒有考慮到樣式的可信程度(confidence)。除此之外，探勘循序樣式雖然能夠得到事件發生的先後順序，但對於事件間的時間資訊卻非常有限。
本篇論文提出一個新的演算法E-PrefixSpan，目的是從序列資料庫中探勘頻繁且更具可信度的關聯規則。我們以PrefixSpan演算法[20]為基礎，利用樣式成長(pattern-growth)[21]的探勘方法，來發掘時間相關的循序樣式。E-PrefixSpan演算法會記錄項目間的時間間隔，並建立映射資料庫來降低資料庫的掃描次數，在產生樣式過程中會依據樣式的可信度，來減少探勘中會產生龐大的樣式數量，同時確保不會造成重要樣式資訊的遺漏。
我們與現存的循序樣式演算法比較，並說明我們演算法在其他方法上更能補足的地方。效能評估實驗顯示E-PrefixSpan能有效縮減所產生的關聯樣式，更能提供探勘結果額外的時間間隔資訊。

Sequential pattern mining technique is developed to determine time-related behavior in sequence databases.  Most of the previous proposed methods discover frequent subsequences as patterns but do not consider the confidence issue.  Besides, although the discovered sequential patterns can reveal the order of events, but the time between events is not well determined.  
This dissertation presents, E-PrefixSpan, a new method for mining frequent and more confident association rules from sequential databases.  The method is based on the PrefixSpan[20] algorithm.  To take the advantage of the pattern-growth[21] mining approach and discover the time related sequential patterns, E-PrefixSpan records the time-intervals between items and creates projected databases to reduce the times of database scanning.  Sequential pattern mining often generates a huge number of rules. To reduce the number of the correlated pattern without information loss, E-PrefixSpan applys the confidence pattern mining technique . 
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 E-PrefixSpan is a valuable approach to condense the correlated patterns and provide additional time-interval information for sequential pattern.

目錄
第1章	緒論	1
1.1	研究背景與動機	1
1.2	研究目的	5
1.3	論文架構	6
第2章	文獻探討	7
2.1	關聯式規則	7
2.2	候選樣式產生與測試方法	10
2.3	樣式成長方法	18
2.4	I-PrefixSpan演算法	20
第3章	E-PrefixSpan演算法	25
3.1	時間間隔定義	25
3.2	支持度計算	27
3.3	信賴度篩選定義	28
3.4	E-PrefixSpan演算法	31
3.5	E-PrefixSpan範例說明	34
3.6	頻繁樣式討論與比較	38
第4章	實驗	41
4.1	模擬資料的產生	41
4.2	E-PrefixSpan與PrefixSpan效能之比較	41
4.3	E-PrefixSpan與I-PrefixSpan探勘樣式比較	47
第5章	結論	53
參考文獻	55
附錄一	59
附錄二	61

圖目錄
圖2.1  Taxonomy項目階層分類例子	15
圖2.2  I-PrefixSpan時間間隔定義	21
圖3.1  E-PrefixSpan時間間隔的定義	27
圖3.2 機率觀點下的Confidence說明	29
圖3.3  E-PrefixSpan演算法	32
圖3.4  E-PrefixSpan的Get-TimeInterval函數	33
圖3.5  E-PrefixSpan的Get-TimeInterval函數	34
圖4.1 執行時間的比較	43
圖4.2 產生樣式數的比較	43
圖4.3 資料庫大小和執行時間的比較	44
圖4.4 資料庫大小和產生樣式數比較	44
圖4.5 信賴度提升對執行時間的變化	46
圖4.6 信賴度提升對產生樣式數的變化	46

表目錄
表2.1交易資料庫	9
表2.2 依顧客ID及交易時間排序的資料庫	11
表2.3 轉換後的顧客序列資料庫	11
表2.4 頻繁項目集轉換表	12
表2.5 轉換頻繁項目集後的顧客序列資料庫	12
表2.6 序列資料庫	12
表2.7  AprioriAll-長度1的頻繁序列	13
表2.8  AprioriAll-長度2的頻繁序列	13
表2.9  AprioriAll-長度3的頻繁序列	13
表2.10  AprioriAll-長度4的頻繁序列	13
表2.11 水平資料庫範例	16
表2.12 根據表2.11所建立的Id-list	17
表2.13  Id-list時序結合	17
表2.14  PrefixSpan範例資料庫	19
表2.15  Prefix映射後的資料庫及最終的循序樣式	19
表2.16  I-PrefixSpan範例資料	21
表2.17 以(a)為prefix所分割的映射資料庫	22
表2.18 以(a)為prefix，支持度計算表	23
表2.19 以(a)為prefix的2-時間區間頻繁樣式	23
表2.20 以(a)為prefix的4-時間區間頻繁樣式	23
表3.1  PrefixSpan以(a)為prefix的2-頻繁樣式	25
表3.2  E-PrefixSpan時間間隔計算規則	28
表3.3 序列資料庫-信賴度說明	30
表3.4  E-PrefixSpan範例資料庫	35
表3.5  E-PrefixSpan以L1建立的映射資料庫	36
表3.6支持度計算說明(<ab>代表的時間間隔)	37
表3.7  E-PrefixSpan以(a)為prefix的2-時間間隔頻繁樣式	37
表3.8 (a)-映射資料庫最後探勘結果	38
表3.9 頻繁樣式比較表	39
表4.1 模擬資料庫的參數	42
表4.2 頻繁樣式各階長度個數比較	45
表4.3  E-PrefixSpan與I-PrefixSpan頻繁樣式比較	49
表4.4  I-PrefixSpan頻繁樣式計算	50
表4.5  E-PrefixSpan頻繁樣式計算<529,770>	51
表4.6  E-PrefixSpan頻繁樣式計算<529,781>	51
表4.7  E-PrefixSpan頻繁樣式計算<529,991>	51
附表1：資料庫產生器可用之參數	59
附表2：C10T8S4I1.25資料庫前10筆序列	63

[1]	江美靜、陳彥良，有時間區間的循序挖掘，中央大學資訊管理所碩士論文，2002年。
[2]	林旻宏、許中川，探勘醫療時間序列資料，雲林科技大學資訊管理所碩士論文，2003年。
[3]	林昭妏、蔡介元，發展一個序列樣式變化之偵測模型-考慮間隔時間因素，元智大學工業工程與管理學系碩士論文，2006年。
[4]	黃盈彬、謝浩明，不連續序列資料挖掘之研究-以股市為例，中央大學資訊管理所碩士論文，2002年。
[5]	許俊傑、周清江，MIHSPM：一個多項目集的混合循序樣式探勘演算法，淡江大學資訊管理所碩士論文，2007年。
[6]	Agrawal R. and Srikant R., “Fast Algorithms for Mining Association Rules in Large Databases”, Proceeding of the 20th International Conference on Very Large Data Bases, 1994, 487-499.
[7]	Agrawal R. and Srikant R., “Mining sequential patterns”, Proceedings of the 11th International Conference on Data Engineering , 1995, 3-14.
[8]	Agrawal R. and Srikant R., “Mining Sequential Patterns: Generalizations and Performance Improvements”, Proceedings of the 5th International Conference on Extending Database Technology, 1996, 3-17.
[9]	Brin, S., Motwani, R., Ullman, J. D., & Tsur, S., “Dynamic Itemset Counting and Implication Rules for Market Basket Data”, ACM SIGMOD Conference on Management of Data, 1997, 255-264.
[10]	Coker J. S. and Davies E., “Identifying Adaptor Contamination When Mining DNA Sequence Data”, Bio Techniques, Vol. 37, No.2, 2004, 194-198.
[11]	Chen C.-J., “A Pre-fetch Mechanism for Proxy Servers: Using Association Rules”, Master Thesis, Institute of Computer Science, National Chung-Hsing University, 1998.
[12]	Chen Y. L., Chiang M.C., Ko M.T., “Discovering time-interval sequential patterns in sequence databases”, Proceedings of the Expert Systems with Applicatons 25, 2003, 343-354.
[13]	Chen Y. L., Chen S. S., and Hsu P. Y., “Mining hybrid sequential patterns and sequential rules”, Information Systems, Vol.27, No.5, 2002, 345-362.
[14]	Chen Y. L., Hu Y. H., “Constraint-based sequential pattern mining: The consideration of recency and compactness”, Decision Support Systems (DSS’42), 2006, 1203-1215.
[15]	Han, Jiawei and Micheline kamber, “Data Mining: Concepts and Techniques”, New York: John Wiley & Son, 2001.
[16]	IBM.http://www.almaden.ibm.com./software/quest/Resources/index.shtml. Quest Data Mining Project, IBM Almaden Research Center, San Jose, CA95120.
[17]	Jea K.F. and Lai L.J., “Mining Sequential Paths from XML Documents to Support XML Indexing”. Proceedings of the 7th Conference on Artificial Intelligence and Applications, 2002, 323-350.
[18]	Pei J., Han J., Mortazavi-Asl B., and Zhu H., “Mining access pattern efficiently from web logs”, Pacific-Asia Conference on Knowledge Discovery and Data Mining, 2000, 396-407.
[19]	Pei J., Han J., Mortazavi-Asl B., Chen Q., Dayal U., and Hsu M., “FreeSpan: Frequent pattern-projected sequential pattern mining”, Proceedings of the sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2000, 355-359.
[20]	Pei J., Han J., Pinto H., Chen Q., Dayal U., and Hsu M. C., “PrefixSpan: mining sequential patterns efficiently by prefix-projected pattern growth”. Proceedings of the 17th International Conference on Data Engineering, 2001, 215-224.
[21]	Pei J., Han J. and Yin Y., “Mining frequent patterns without candidate generation” In: Chen WD, Naughton J. F., Bernstein P. A., Eds. Proceeding of the 2000 ACM SIGMOD International Conference on Management of Data, 2000, 1-12.
[22]	Orlando S., Perego R, Silvestri C., “A new algorithm for gap constrained sequence mining”. Symposim on Applied Computing (SAC’04), 540-547, 2004.
[23]	Wu P. H., Peng W. C. and Chen M. S. “Mining Sequential Alarm Patterns in a Telecommunication Database.” Workshop on Databases in Telecommunications, Sept. 2001.
[24]	Zaki M. J., “SPADE: An Efficient Algorithm for Mining Frequent Sequences”, Proceeding of Machine Learning Journal, Special Issue on Unsupervised Learning, 2001, Vol.42 Nos. 1/2, 31-60.