在過去以 Apriori 為基礎的循序樣式探勘方法中，皆單純採用由下而上的方式從長度較短的頻繁樣式成長至較長的候選樣式，一直成長至沒有更長的候選樣式產生為止，因而若需探勘最長頻繁樣式時則必須將所有的頻繁樣式探勘完才可得到(所謂的最長頻繁樣式就是不屬於其它任一頻繁樣式的子樣式稱之)，造成許多不必要的運算。
本研究提出並建構一個優先探勘最長頻繁樣式之演算法PMSPM，結合由下而上以及由上而下兩種方向的探勘方式，進而早一步於由上而下的方向找出大多數的最長頻繁樣式，使得在由下而上方向的探勘不需成長到最後的階段，即可找出所有頻繁且最長的樣式，進而節省大量不需要的候選樣式測試，以減少探勘時間。本研究除了證明演算法之正確性與完整性，並以模擬實驗驗證其效能及可行性，最後，將PMSPM演算法應用於糖尿病病患之病歷資料探勘，找出病患之血糖的最長樣式演進型式，以供推測血糖樣式變化之原因。

Apriori-based sequential pattern mining algorithms use bottom-up method. They merge frequent patterns with shorter length into candidate patterns with longer length, then repeat the process until no more candidate patterns could be generated. However, if we want to obtain frequent maximal sequential patterns, which are not a sub-sequence of any other frequent sequential pattern, these algorithms will have to generate all sequential patterns first, which require lots of computation unrelated to the final results.
For this reason, we propose an algorithm, PMSPM, to find all frequent maximal sequential patterns by cutting most of the intermediate steps. Like pincers, we alternate bottom-up and top-down methods to find most of the maximal sequential patterns in the early top-down stage. Thus, the mining in the bottom-up direction could skip repetitive procedures before the last pass. Therefore, the algorithm could reduce needless support count tests to save time.
We demonstrate the correctness and integrity of PMSPM. We test its performance through experimenting with synthetic databases. 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	研究目的	3
1.3	論文架構	4
第2章	文獻探討	5
2.1	探勘方法	5
2.1.1.	候選樣式產生與測試	5
2.1.2.	樣式成長方法	10
2.2	最長循序樣式相關演算法	12
2.2.1.	最大項目集合演算法	13
2.2.2.	封閉式循序樣式演算法	16
第3章	PMSPM演算法	18
3.1	背景	18
3.2	演算法定義	18
3.3	產生一階頻繁、非頻繁樣式及CMS	26
3.4	由下而上方向的探勘(由下而上)	26
3.4.1.	產生k階候選樣式	27
3.4.2.	計算k階候選樣式支持度	27
3.5	由上而下方向的探勘(由上而下)	30
3.5.1.	更新CMS中的序列	30
3.5.2.	計算CMS中序列的支持度	33
3.5.3.	刪減CMFS中的子樣式並產生未被刪除樣式的長度k+1子頻繁樣式	35
3.6	結束演算法	36
第4章	完整性證明	37
4.1	說明	37
4.2	證明	37
第5章	實驗	39
5.1	實驗環境和模擬資料庫產生	39
5.2	實驗數據與討論	41
5.3	實驗結論	51
第6章	PMSPM應用於糖尿病患資料探勘	52
6.1	糖尿病介紹	52
6.2	資料說明	54
6.3	資料篩選	55
6.4	資料轉換	56
6.5	應用PMSPM進行探勘	57
6.6	探勘結果樣式分析與解釋	58
第7章	結論	60
參考文獻	62

圖目錄
圖1. 由下而上方向的探勘	15
圖2. 由上而下方向的探勘	15
圖3. PMSPM演算法	24
圖4. PMSPM演算法流程圖	25
圖5. 計算候選樣式支持度函數	28
圖6. 候選樹	29
圖7. 更新CMS序列函數	31
圖8. 由上而下方向探勘於K=2時，更新CMS之流程	33
圖9. 由上而下方向探勘於K=3時，更新CMS之流程	33
圖10. 計算CMS中序列支持度函數	34
圖11. 刪除CMFS的子樣式函數	35
圖12. 交易序列平均交易數量在不同方法下執行時間的比較	42
圖13. 各長度的最長樣式個數在不同交易序列平均交易數量下的分佈	42
圖14. 交易序列數量和執行時間的比較	43
圖15. 各長度的最長樣式個數在支持度為0.05%下的分佈	44
圖16. 各長度的最長樣式個數在支持度為0.10%下的分佈	44
圖17. 各長度的最長樣式個數在支持度為0.15%下的分佈	45
圖18. 最長樣式種類數和執行時間的比較	46
圖19. 各長度的最長樣式個數在支持度為0.05%下的分佈	46
圖20. 各長度的最長樣式個數在支持度為0.10%下的分佈	47
圖21. 各長度的最長樣式個數在支持度為0.15%下的分佈	47
圖22. 項目數量和執行時間的比較	48
圖23. 各長度的最長樣式個數在支持度為0.05%下的分佈	49
圖24. 各長度的最長樣式個數在支持度為0.10%下的分佈	49
圖25. 各長度的最長樣式個數在支持度為0.15%下的分佈	50

表目錄
表1. 範例資料庫	7
表2. 轉換後的顧客序列資料庫	7
表3. 大型項目集轉換表	7
表4. 轉換大型項目集後的顧客序列資料庫	8
表5. 依據表4所產生的一階大型序列L1	8
表6. 依據表5所產生的二階候選序列C2	8
表7. 依據表6所產生的二階大型序列L2	8
表8. SPADE根據表11所建立的各項目出現的位置	10
表9. 樣式A與樣式D的時序合併	10
表10. 樣式A→D與樣式D→A 的時序合併	10
表11. 交易資料庫	26
表12. 根據F1合併產生的C2	27
表13. 二階頻繁及非頻繁樣式集合	30
表14. 三階頻繁及非頻繁樣式集合	36
表15. 四階頻繁及非頻繁樣式集合	36
表16. 實驗參數說明	39
表17. 實驗之第一部分參數	40
表18. 實驗之第二部分參數	40
表19. 實驗之第三部分參數	41
表20. 實驗之第四部分參數	41
表21. 糖尿病血糖測量標準(單位:MG/DL)	54
表22. 糖尿病資料集記錄格式	54
表23. 檢查項目碼對照表	55
表24. 血糖值檢查項目碼對照表	57
表25. 胰島素檢查項目碼對照表	57
表26. 糖尿病病患資料探勘數據	58
表27. 糖尿病病患資料探勘結果	58

[1]	許俊傑，MIHSPM:一個多項目集的混合循序樣式探勘演算法，淡江大學資訊管理研究所碩士論文，2007年。
[2]	張家汶，具時限制制之高效率序列樣式探勘演算法，逢甲大學資訊工程研究所碩士論文，2006年。
[3]	孫恬琳，應用資料探勘技術於汽車保險購買行為之研究，中正大學企業管理研究所碩士論文，2003 年。
[4]	舒毓箎，在醫學報告資料中探勘連續序列，東華大學資訊工程研究所碩士論文，2004 年。
[5]	R. Agrawal and R. Srikant, “Fast algorithm for mining association rules”, In proceeding of the 20th international conference on VLDB, Santiago, 1994, 487-499.
[6]	R. Agrawal and R. Srikant, “Mining Sequential Patterns”, In proceedings of the 17th international conference on Data Engineering, Taipei, Taiwan, 1995, 3-14.
[7]	R. Agrawal and R. Srikant, “Mining Sequential Patterns: Generalizations and Performance Improvements”, Proc. of the Fifth International Conference on Extending Database Technology, 1995.
[8]	R. J. Bayardo, “Efficiently Mining Long Patterns from Databases”, Proceedings of the 1998 ACM SIGMOD international conference, 1998, pp.85-93
[9]	D. Burdick, M. Calimlim and J. Gehrke, “MAFIA: A Maximal Frequent Itemset Algorithm for Transactional Databases”, Proceedings of the 17th International Conference on Data Engineering, 2001, pp.443-452.
[10]	D. Lin and Zvi M. Kedem, “Pincer-Search: An Efficient Algorithm for Discovering the Maximum Frequent Set”, IEEE Transactions on Knowledge and Data Engineering, MAY 2002, Vol. 14 Issue 3, pp553-566.
[11]	S. Orlando, R. Perego and C. Silvestri: A new algorithm for gap constrained sequence mining. Symposim on Applied Computing (SAC'04), pp 540-547, 2004.
[12]	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.
[13]	J. Pei, J. Han, B. Mortazavi-Asl, H. Pinto, Q. Chen, U. Dayal and M.C. Hsu, “PrefixSpan: Mining Sequential Patterns Efficiently by Prefix Projected Pattern Growth”, Proceedings of the 17th International Conference on Data Engineering, Heidelberg, Germany, 2001, pp. 106-115.
[14]	J. Pei, J. Han, B. Mortazavi-Asl, Q. Chen, U. Dayal and 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.
[15]	J. Pei, J. Han, B. Mortazavi-Asl and H. Zhu, “Mining access pattern efficiently from web logs”, Proceedings of the 2000 Pacific-Asia Conference on Knowledge Discovery and Data Mining, Tokyo, 2000, pp.396-407.
[16]	M. S. Waterman, “Introduction to Computational Biology: Maps, sequences, and genomes”, Boca Raton: CRC Press, 1995.
[17]	X. Yan, J. Han and R. Afshar, “CloSpan: Mining Closed Sequential Patterns in Large Datasets”, In proceeding of 2003 SDM conference, San Franciso, CA, May 2003.
[18]	M. J. Zaki, “SPADE: An Efficient Algorithm for Mining Frequent Sequences”, Proceeding of Machine Learning Journal, Special Issue on Unsupervised Learning, 2001, Vol. 42 Nos. 1/2, pp.31-6.