隨著時代的快速變遷，以往資訊不易流通的封閉性社會，逐漸轉變成資訊爆炸的開放性社會，所有的資訊，皆可由電視、廣播或是網際網路等資訊科技來獲得，但如此龐大的資訊數量，已超出了人們頭腦所能處理的極限，所以如何避免「GIGO(Garbage In Garbage Out)」，需要靠資訊科技的技術來解決，「資料探勘(Data Mining)」即是其中一個，目的就是要從巨量的資料量中，粹取(Extract)出使用者所特定、渴望的資訊或知識，而資料探勘可分為很多方面，本篇論文是以「序列型樣(Sequential Pattern)」來做為研究的主題。
所以，本篇論文即是提出一新的「快速序列拆解(Fast Sequence Decomposition)」演算法(以下皆以FSD簡稱)，其優點如下：1.只需掃描資料庫一次。2.減少大量候選序列的產生。3.可使用於漸進式探勘(Incremental Mining)。藉著以上這些特點，讓使用者能在較短時間內得到序列型樣，以獲得最佳的實質效益，達到使用者和消費者雙贏的局面。
另外，由於網路環境的使用率越來越趨於普遍，如被應用於網路拍賣、網路教學等方面，所以本篇論文即針對教學網站為對象，提出一新的「快速學習序列拆解(Fast Learning Sequence Decomposition)」演算法(以下皆以FLSD簡稱)，以快速地找出學習者的學習序列，作為網路設計者的參考依據，進而修改網站架構，以吸引更多學習者上線使用，優點如下：1.只需掃描資料庫一次。2.允許有重複瀏灠行為的發生。3.利用「型樣化對映」的方式，產生候選學習序列。而也藉著以上這些特點，使得學習序列能快速地被探勘出來，以提高執行方面的效能。

Along with time fast vicissitude, the former information is not easy the seal society which circulates, gradually transforms the open society which the information explodes. All information could get by information science and technology. For example, the television, broadcast or Internet and so on.But so huge information quantity has surpassed the limit which the people brains can process.Therefore, how to avoid “GIGO (Garbage In Garbage Out)”, needs to depend on the information science and technology to solve. Data Mining is a very good method. The goal is extracts particular and useful information or knowledge of users from huge data. And data mining may divide into very variously, this paper is does take “Sequential Pattern” as the research subject.
Therefore, this paper is proposed a new algorithm-Fast Sequence Decomposition algorithm (bellow all by FSD abbreviation). Its advantage as follows：1. Only scan database a time. 2. Reduces to production the massive candidate sequences. 3. Could use to in Incremental Mining. By above these characteristics, enable the user to obtain the sequence pattern in a shorter time and get the best substantive benefit.Finally, achieved the user and the consumer double win aspect.
Moreover, because the network environment utilization ratio more and more frequent.For example, applied to network auction or network teaching and so on.Therefore this paper focus on teaching website to propose a new algorithm-Fast Learning Sequence Decomposition algorithm (bellow all by FLSD abbreviation).By fast discovers the Learning Sequence as network designer’s reference, then revises the website construction so as to attract more and more people using it. It advantage as follows：1. Only scan database a time. 2. The permission has the repetition travel behavior the occurrence. 3. Using Pattern Mapping to produce candidate learning sequence.By above these characteristics, enables the learning sequence fast to come out by mining and improve performance of algorithm.

摘要 IV
ABSTRACT V
誌謝辭 VI
目次 VII
表目錄 X
圖目錄 XIII
第一章 緒論 1
1.1資料探勘簡介 1
1.1.1序列型樣與關聯規則的不同 6
1.2研究動機 7
1.3研究目的 8
1.4論文架構 9
第二章 相關文獻探討 10
2.1 序列型樣問題定義 11
2.2 序列型樣相關演算法 13
2.2.1 AprioriAll演算法 13
2.2.2 GSP演算法 18
2.2.3 FreeSpan演算法 19
2.2.4 PrefixSpan演算法 20
2.2.5 QSD演算法 25
2.2.6 FUP運算法 29
2.3 學習序列問題定義 33
2.4 學習序列相關演算法 34
2.4.1 MF演算法、FS演算法、SS演算法： 34
2.4.2 FDLP演算法： 36
第三章 研究方法 38
3.1資料探勘之快速序列拆解演算法 38
3.1.1 FSD演算法 38
3.1.2 FSD演算法流程圖說明 40
3.1.3 FSD演算法說明 42
3.1.4「二次新增法」說明 45
3.1.5單筆拆解結果「資料格式轉換」的說明 49
3.1.6 FSD演算法實例說明 54
3.1.7 FSD演算法之漸進式探勘 58
3.2快速學習序列拆解演算法 60
3.2.1 FLSD演算法流程圖說明 61
3.2.2 FLSD演算法說明 63
3.2.2.1 FLSD型樣產生方式實例說明 65
3.2.2.2 FLSD對映方式實例說明 67
3.2.3 FLSD演算法實例說明 68
第四章 實驗結果及分析 71
4.1 實驗環境及相關說明 71
4.2實驗設計、測試數據與效能評估 72
4.2.1　FSD演算法在不同資料量下的效能比較 72
4.2.2　FSD演算法在不同支持度下的效能比較 73
4.2.3　FSD演算法在不同項目數下的效能比較 75
4.2.4 FSD演算法在不同序列長度下的效能比較 76
4.2.5　FSD演算法漸進式探勘上的效能比較 77
4.3 FLSD演算法效能圖示說明 78
4.3.1　FLSD演算法在不同資料量下的效能說明 79
4.3.2　FLSD演算法在不同網頁數目下的效能說明 80
4.3.3　FLSD演算法在不同序列長度下的效能說明 81
4.4 本論文演算法的限制 82
第五章 結論與未來研究方向 83
參考文獻 85

1.余忠慶，多維度序列樣式挖掘之研究，中央大學資訊管理研究所碩士論文，民國九十一年六月。
2.李建億, 吳孟淞, 李育強, 吳政道，「在全球資訊網學習環境中學習歷程樣式發掘法之研究」，2000年台灣區網際網路研討會(TANET''2000)，台南：國立成功大學主辦，頁448-455。
3.徐家馴，「在教學網站的環境中發掘熱門學習路線」，輔仁大學資訊工程研究所碩士論文，民國八十九年。
4.陳秀如，高效率之關聯法則探勘演算法暨應用其探採具多重支持度之加權數量關聯規則，南台科技大學資訊管理研究所技術論文MIS-BI-93-06-06-001，民國九十三年。
5.楊朝富， 使用SQL查詢多維度序列型樣之研究，元智大學資訊管理研究所碩士論文，民國九十一年六月。
6.R.Agrawal and R.Srikant, “Mining Sequential Patterns”, Proceedings of the International Conference on Data Engineering (ICDE), Taipei, Taiwan, March, 1995, pp.3-14.
7.R. Agrawal and R. Srikant, "Fast Algorithm for Mining Assoication Rule in Large Databases", In Proc. 1994 Int’l Conf. VLDB, Santiago, Chile, Sep.1994, pp. 487-499,.
8.R. Agrawal, C. Faloutsos and A. Swami, “Efficient Similarity Search in Sequence Databases,” In Lecture Notes in Computer Science 730, Springer Verlag, 1993, pp. 69-84.
9.S. Brin, R. Motwani, J. D. Ullman, and S. Ts ur, "Dynamic Itemset Counting and Implication Rules for Marketing Basket Data", 1997 ACM SIGMOD Conference on Management of Data, 1997, pp. 255-264.
10.Berry, M. J. A. and Linoff, G., “Data Mining Technique for Marketing, Sale, and Customer Support,” Wiley Computer, 1997.
11.M.S. Chen, J. Han, and P.S. Yu, “Data mining: an overview from a database perspective,” IEEE Transactions on Knowledge and Data Engineering, Vol. 8, No. 6, 1996, pp. 866-883.
12.M.S. Chen, J. S. Park, & P. S.Yu, "Data Mining for Path Traversal Patterns in a Web Environment", Proc 16th Int’l Conf. on Distributed Computing Systems, 1996, pp. 385-392.
13.Ming-Syan Chen, Jong Soo Park, and Philip S. Yu,“Efficient Data Mining for Path Traversal Patterns.’’ IEEE Trans. on Knowledge and Data Eng., Vol. 10, no. 2, Mar./Apr., 1998, pp.209-221.
14.W. Cheung, S. D. Lee, and B. Kao, "A general incremental technique for maintaining discovered association rules", in Proceedings of Database Systems for Advanced Applications, DASFAA’97, Melbourne, Australia,1997, pp.185-194.
15.C.Faloutsos, M.Ranganathan and Y.Manolopoulos, “Fast Subsequence Matching in Time-Series Databases,” SIGMOD Conference, 1994, pp. 419-429.
16.F.Masseglia, F.Cathala and P.Poncelet, “The PSP Approach for Mining Sequential Patterns,” In Proc. 1998 2nd European Symposium on Principles of Data Mining and Knowledge Discovery (PKDD’98), Vol. 1510, Nantes, France, LNAI. Sept. 1998, pp. 176-184.
17.Frawley, W. J, Paitetsky-Shapiro, G. and Matheus, C. J., “Knowledge Discovery in Databases: An Overview”, Knowledge Discovery in Databases, California , AAAI/MIT Press, 1991, pp.1-30.
18.Grupe, F. H. and Owrang, M. M., “database Mining Discovering New Knowledge and Cooperative Advantage,” Information Systems Management, Vol.12, No.4, 1995, pp. 26-31.
19.J. Han, J. Pei, B. Mortazavi-Asl, Q. Chen, U. Dayal, and M.C. Hsu, FreeSpan: frequentpattern-projected sequential pattern mining, Proceedings of the ACM SIGKDDInternational Conference on Knowledge Discovery and Data Mining, 2000, pp. 355-359.
20.J. Han, J. Pei, H. Pinto, Q. Chen, U. Dayal, and M.-C. Hsu, ''''PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth'''', Proc. of 2001 Int’l Conference on Data Engineering (ICDE''01), Heidelberg, Germany, April 2001.
21.Kleissner, C., “Data Mining for the Enterprise”, IEEE Proc. 31st Annual Hawaii　International Conference on System Sciences, Vol. 7, 1998, pp. 295-304.
22.L. Kaufman and P. J. Rousseeuw, "Finding Groups in Data: an Introduction to Cluster Analysis", John Wiley & Sons, 1990.
23.H. Mannila, H. Toivonen, and A. I. Verkamo, “Discovery of Frequent Episode InEvent Sequences,” Data Mining and Knowledge Discovery, No. 1, Nov. 1997, pp.259-289.
24.H. Mannila, H. Toivonen, and A. I. Verkamo, “Discovering Frequent Episodes in Sequences,” In Proc. 1995 Int. Conf. On Knowledge Discovery and Data Mining (KDD’95), Montreal, Canada, Aug 1995, pp. 210-215.
25.S. Park, M. S. Chen, and P. S. Yu, "An Effective Hash Based Algorithm for Mining Association Rules", Proc. ACM SIGMOD, 1995, pp. 175-186.
26.J.R. Quinlan, “Induction of Decision Trees,” Machine Learning, Vol. 1, 1986, pp. 81-106.
27.Ramakrishnan Srikant, Rakesh Agrawal, “Minging Sequenctial Patterns: Generalizations and Performance Improvements,” EDBT 1996, pp.3-17.
28.H. Toivonen, "Sampling Large Database for association Rule", VLDB, pp. 134-145.
29.M. J. Zaki, “SPADE: An Efficient Algorithm for Mining Frequent Sequences,” In Proc. of Machine Learning Journal, special issue on Unsupervised Learning (Doug Fisher, ed.), Vol. 42 Nos. 1/2, Jan/Feb 2001, pp. 31-60.