在資料探勘研究中，循序樣式探勘為重要的探勘問題，目的是從原始資料發生時間作為資料前後順序之依據，找到出現次數超過使用者設定門檻值之頻繁循序樣式。依據循序樣式中，相鄰項目於各個交易之間是否為相鄰情況下，可分為連續、非連續和混合循序樣式三種，根據過去混合循序樣式探勘研究，我們發現探勘其樣式的交易內容都是以一個項目為主，而缺少多項目集的研究。我們提出一個新的演算法MIHSPM(Multiple Itemset Hybrid Sequential Pattern Mining Algorithm)，找出多項目集的混合循序樣式。
MIHSPM演算法有以下四個步驟:1. 掃描資料庫，產生一階頻繁樣式。2. 建立一階頻繁樣式的順序表格。3. 進行樣式順序表格合併，產生二階頻繁樣式。4. 以前序分割樣式順序表格，找出全部的混合循序樣式。
在實驗的部分，我們以模擬資料庫測試其演算法的效能及分析相關模擬參數之敏感度。最後，我們將MIHSPM演算法應用於糖尿病患之病歷資料探勘，病患之血糖的樣式演進型式，以供推測血糖樣式變化之原因。

Sequential pattern mining is an important research topic at data mining. Its main purpose is to find out serial patterns according to orders in occurrence time with frequency exceeding user defined threshold. Based on whether consecutive items in sequential patterns should also be consecutive in the transactions, it could be classified into the following three categories: The first is continuous patterns; the second is discontinuous patterns; the third is hybrid patterns that combine both continuous patterns and discontinuous patterns. Transaction contents of sequential patterns in previous researches are for a single item. We propose a new algorithm, MIHSPM, to find multiple item set hybrid sequential patterns.
The four steps of MISHPM are as follows: 1. Scan database to generate frequent length-1 patterns. 2. Build pattern order table of frequent length-1 patterns. 3. Join all pattern order tables to generate frequent length-2 patterns. 4. Partition pattern order tables according pattern's prefixes and recursively join pattern order tables.
We use synthetic databases to test our algorithm's performance and analyze the sensitivity of related parameter. Finally, we apply our algorithm to mining anamnesis records of diabetes patients, and find out frequent glucose evolution patterns.

目錄
第1章	緒論	1
1.1	研究背景與動機	1
1.2	研究目的	7
1.3	論文架構	7
第2章	文獻探討	9
2.1	探勘資料集特性	9
2.2	探勘循序樣式類型	9
2.2.1.	相似樣式探勘(Finding similar patterns)	10
2.2.2.	週期性樣式探勘(Finding periodic patterns)	10
2.2.3.	常見樣式探勘(Finding frequent patterns)	10
2.2.4.	循序樣式維護(Incremental mining of sequential patterns)	13
2.3	探勘方法(Mining approach)	13
2.3.1.	候選樣式產生與測試方法	13
2.3.2.	樣式成長方法	21
2.3.3.	找出最大項目集循序樣式方法	23
2.3.4.	記憶體索引探勘方法	24
2.3.5.	多支持度的探勘方法	24
2.3.6.	加入正規化表示(regular expression)式探勘方法	25
2.4	目前循序樣式探勘的應用	25
第3章	MIHSPM演算法	26
3.1	演算法定義	27
3.2	掃描資料庫，產生一階頻繁樣式	34
3.3	建立全部一階頻繁樣式的順序表格	34
3.3.1.	順序表格資料結構	35
3.3.2.	順序表格建立	35
3.4	進行樣式順序表格合併，產生二階頻繁樣式	37
3.5	以前序分割全部資料庫，找出所有的混合循序樣式	42
3.6	MIHSPM混合循序樣式與SPADE演算法之比較	46
3.6.1.	頻繁樣式討論與比較	47
3.6.2.	演算過程候選樣式個數討論與比較	48
3.7	二階候選樣式產生討論	50
第4章	完全性證明	52
第5章	實驗	56
5.1	實驗環境和產生交易序列資料庫	56
5.2	實驗數據與討論	57
第6章	MIHSPM應用於糖尿病患資料探勘	64
6.1	糖尿病介紹	64
6.2	資料說明	66
6.3	資料刪除	67
6.4	資料篩選	68
6.5	資料轉換	68
6.6	應用MIHSPM進行探勘	69
6.7	探勘結果樣式分析與解釋	70
第7章	結論	72

圖目錄
圖1. 循序樣式探勘類型	10
圖2. SPADE探勘過程所形成的晶格	18
圖3. GFP2中的候選樹	20
圖4. GFP2中的補償串列	20
圖5. MIHSPM演算法虛擬碼	33
圖6. MIHSPM演算法流程圖	34
圖7. 建立一階頻繁樣式順序表格函數	37
圖8. 表生二階候選樣式之順序表格合併	39
圖9. MIHSPM的generate-frequent-long-sequences函數	40
圖10. 順序樣式表格合併pot_join函數	41
圖11. 前序樣式集合分割(樣式長度為2)	42
圖12. 前序樣式集合分割(樣式長度為3)	43
圖13. 產生三階候選樣式之順序表格合併	45
圖14. 交易序列數和執行時間的比較	58
圖15. 執行時間和項目種類個數的比較	59
圖16. 樣式個數和樣式種類個數的比較	59
圖17. 執行時間和交易序列長度的比較	60
圖18. 樣式個數和交易序列長度的比較	61
圖19. 各長度樣式個數在不同交易長度的分佈	61
圖20. 執行時間和交易項目個數的比較	62
圖21. 樣式個數和交易項目個數的比較	62
圖22.各長度樣式個數在不同交易項目個數的分佈	63
 
表目錄
表1. 範例資料庫	14
表2. 轉換後的顧客序列資料庫	14
表3. 大型項目集轉換表	15
表4. 轉換大型項目集後的顧客序列資料庫	15
表5. AprioriALL演算法探勘表4資料庫的過程pass1	15
表6. AprioriALL演算法探勘表4資料庫的過程pass2	15
表7. AprioriALL演算法探勘表4資料庫的過程pass3	16
表8. AprioriALL演算法探勘表4資料庫的過程pass4	16
表9. 根據表1所建立的各項目出現的位置	17
表10. 以前序分割的等價類別 EC={}	18
表11. 以前序分割的等價類別(EC)合併 EC={30, 40}	18
表12. 根據表2的資料庫建置的投影資料庫以及循序樣式	23
表13. 循序樣式演算法特性比較	27
表14. 顧客交易資料庫	28
表15. 根據表14探勘出的一階頻繁樣式(minSupp=2)	35
表 16. 根據表14和表15.建立一階頻繁樣式順序表格	35
表17. 長度為1的樣式合併情況	38
表18. 合併產生長度為3的候選樣式	43
表 19. 頻繁樣式比較表	47
表 20. 產生候選樣式比較表	48
表21. 模擬資料庫的參數說明	56
表22. 實驗資料庫參數	57
表23. 糖尿病血糖測量標準(單位:mg/dl)	66
表24. 糖尿病資料集記錄格式	66
表25. 檢查項目碼對照表	67
表26. 血糖檢查項目碼對照表	69
表27. 胰島素檢查項目碼對照表	69
表28. 糖尿病病患資料探勘數據	70
表29. 糖尿病患資料探勘結果	70

[1]江美靜、陳彥良，有時間區間的循序挖掘，中央大學資訊管理研究所碩士論文，2002年。
[2]沈清正、陳仕昇、高鴻斌、張元哲、陳家仁、黃琮盛、陳彥良，資料間隱含關係的挖掘與展望，中央大學資訊管理研究所資料挖掘課程專書。
[3]林柏伸，行動環境下之使用者行為樣式研究-以二維度序列型樣進行探勘，中原大學資訊管理研究所碩士論文，2004年。
[4]周清江、原孝任，CHSPM:一個完整的混合循序樣式探勘演算法，淡江大學資訊管理研究所碩士論文，2005年。
[5]孫恬琳，應用資料探勘技術於汽車保險購買行為之研究，國立中正大學企業管理研究所碩士論文，2003年。
[6]陳仕昇，序列樣式探勘之研究，中央大學資訊管理研究所博士論文，2003年。
[7]陳彥文，有效率的循序樣式探勘系統，淡江大學資訊管理研究所碩士論文，2004年。
[8]舒毓竾，在醫學報告資料中探勘連續序列，東華大學資訊工程研究所碩士論文，2004年。
[9]R. Agrawal and R. Srikant, “Fast algorithm for mining association rules”, In proceeding of the 20th international conference on VLDB, Santiago, 1994, 487-499.
[10]R. Agrawal and R. Srikant, “Mining sequential patterns”, In proceedings of the 17th international conference on Data Engineering, Taipei, Taiwan, 1995, 3-14.
[11]R. Agrawal and R. Srikant, “Mining Sequential Patterns: Generalizations and Performance Improvements”, In proceeding of the 15th international conference on Extending Database Technology, 1996, 3-17.
[12]Y. L. Chen, S. S. Chen , P. Y. Hsu, “Mining hybrid sequential patterns and sequential rules”, Information Systems, 2002, Vol. 27, No. 5, 345-362. 
[13]M. N. Garofalakis, R. Rastogi, K. Shim,“SPIRIT:Sequential pattern mining with regular expression contraints”, In proceedings of 25th international conference on Very Large Data Bases, 1999, 223-234.
[14]V. Guralnik and G. Karypis, “Parallel tree-projection-based sequence mining algorithms”, Parallel Computing 30, 2004, 443-472.
[15]J. Han and M. Kamber, Data Mining: Concepts and Techniques, 2nd  Edition, 2001.
[16]M. Y. Lin and S. Y. Lee, “Fast Discovery of Sequential Patterns by Memory Indexing”, In proceedings of 4th international conference on Data Warehousing and Knowledge Discovery, France , 2002, 150-160.
[17]J. S. Park, M. Chen, P. S. Yu, “An Effective Hash-Based Algorithm for Mining Association Rules”, In proceedings of the 1995 ACM SIGMOD international conference Management of Data, 1995, 175-186.
[18]J. Pei, J. Han and Y. Yin, “Mining frequent patterns without candidate generation”, In proceeding of the 2000 ACM SIGMOD international conference on Management of Data, New York: ACM Press, 2000, 1-12. 
[19]J. Pei, J. Han, B. Mortazavi-Asl, H. Zhu, “Mining access pattern efficiently from web logs”, In proceedings of the 2000 Pacific-Asia conference on Knowledge Discovery and Data Mining, Tokyo, 2000, 396-407.
[20]J. Pei, J. Han, B. Mortazavi-Asl, H. Pinto, Q. Chen, U. Dayal, M-C Hsu, “PrefixSpan: Mining Sequential Patterns Efficiently by Prefix Projected Pattern Growth”, In proceedings of the 17th international conference on Data Engineering, Heidelberg, Germany, 2001, 106-115.
[21]J. Pei, J. Han, B. Mortazavi-Asl, Q. Chen, U. Dayal, M. Hsu, “FreeSpan: Frequent pattern-projected sequential pattern mining”, In proceedings of the 6th  ACM SIGKDD International conference on Knowledge Discovery and Data Mining, 2000, 355-359.
[22]R. Ramakrishnan and J. Gehrke, Database Management Systems, 3rd Edition, 2002, 890-925
[23]M. S. Waterman, Introduction to Computational Biology: Maps, sequences, and genomes, Boca Raton: CRC Press, 1995.
[24]Y. Xiong and Y. Y. Zhu, “A Multi-Supports-Based Sequential Pattern Mining Algorithm”, Department of Computing and Information Technology, Fudan University, Shanghai, China, 2000.
[25]X. Yan, J. Han and R. Afshar, “CloSpan: Mining Closed Sequential Patterns in Large Datasets”, In proceeding of 2003 SDM conference, San Francisco, CA, May 2003.
[26]O. Zaiane, M. Xin and J. Han, “Discovering Web Access Patterns and Trend by Applying OLAP and Data Mining Technology on Web Logs”, Virtual-U Research Laboratory and Intelligent Database Systems Research Laboratory, 1997.
[27]M. J. Zaki, “SPADE: An Efficient Algorithm for Mining Frequent Sequences”, Machine Learning Journal, Special Issue on Unsupervised Learning, 2001, Vol. 42 Nos. 1/2, 31-60.