自有文字記載以來，各種文字與數字的紀錄已經充滿於各個領域。科學界詳實的實驗記錄、商業界的交易資料、學生的學習資料、瀏覽網頁序列、大賣場客戶交易資料，隨著電腦的廣泛應用而成指數型成長。尤其是近代資訊自動化，許多領域的資料，鉅細靡遺的紀錄於資料庫當中。這些電子資料可說是真實世界的電子版，我們嘗試透過查詢、統計、繪圖等方法，了解這些雜散的巨量資料背後所隱含的真實意涵，進而更貼近真實的了解真實世界。
在眾多的方法當中，近年資料探勘的研究與應用層面迅速成長並於許多領域獲致驚人成果，而頻繁樣式的探勘屬於較新的研究焦點。本論文主旨在於研究高效率的探勘與維護序列樣式的演算法。在研讀相關研究當中，發現這領域先前研究提出之演算法集中於解決巨量資料的問題，而著重在加快搜尋速度。主要的量測指標有二:掃瞄資料庫次數以及搜尋空間大小。多次掃描資料庫將巨幅拖慢處理資料的速度，因此，掃描資料庫的次數愈少愈好。另外演算法所需要蒐尋的資料空間也是愈小愈有可能完全於記憶體當中運算，加速處理速度。就此，本論文提出之演算法皆僅需掃描資料庫一次，依據序列出現的頻率以及序列長度這二個我們感興趣的兩個屬性建立序列資料庫之資料模型。
以此為題，首先提出FAL演算法，掃描資料庫一次，應用向下封閉特性(Downward Closure Property)建立序列晶格，再依據向上封閉特性(Upward Closure Property)刪除晶格中不頻繁序列，建立完全最大序列(Maximal Sequence)晶格，有效縮小晶格所佔用之空間。其次，提出FMCSP演算法，以等效類別(Equivalent Class)的觀念，建立封閉序列(Closed Sequence)晶格。然而，實際運轉的資料庫都會是動態的、時變的，無法避免繼續新增資料的產生。為此，針對時變遞增的資料庫如何維護序列型樣資料模型?!本論文提出MMSP演算法，探討挖掘序列型樣演算法之遞增特性，充分運用已經挖掘之資訊，減少重複挖掘工作。

Since the invention of characters, all kinds of records with numbers and words, increased dramatically in many domains. The invention of computer had trigger rapid data accumulation in science, education, e-Learning, business and supermarket, exponentially. Automation of information system has urged this situation and result in huge amount of data stored in databases worldwide.  These electronic data is considered to be the mirror of the real world, which we can make full use it, properly. We try to discover interesting information or knowledge that conceived in databases via various methods, such as statistic, query, graphics and data mining, to further understand the world we lived in. A modern day information system is accountable for this purpose.
In these diverse approaches, data mining has caught the eyes of many domain experts, and gain achievements. In the last decade, mining sequential patterns became one promising topic and arouse our interest. The essence of data mining is to dealing with huge amount of data, many previous researches focus on propose efficient algorithm with less search time and run time. Hence, this dissertation has focused on develop algorithms that mining sequential pattern efficiently, and to be maintainable. In our point of view there are two criteria to evaluate mining algorithm: scan times of database, volume of working space and searching space. As we already known the speed of accessing data from hard drive is slower than from main memory, usually by factor of two. This implies that the less scan times the better. Working space is required to host data during mining process. Searching space is the space to store the result, frequent sequence set or data model. The less space required by algorithm the more chance to fit all processed data into main memory. Consequently, both the efficiency and performance will be improved. With these in mind, all three algorithms been proposed in this dissertation have these three characters: scan database once, mining without candidates and mining full set of frequent sequences. 
First algorithm, FAL, is designed to fully utilize both the downward closure property and upward closure property to construct a lattice data model with maximal sequence representation. Second algorithm is FMCSP that inherit the legacy of FAL, but applied closed sequence concept instead of maximal sequence. Note that, closed sequence is the longest sequence in its equivalent class, it can shrink the size of searching space, and furthermore, with adjustable ability for user to set, or tune, the threshold of minimum support after the mining of data model had been constructed. Finally, algorithm MMSP has inherited the legacy of previous algorithms to deal with incremental sequence database. MMSP is capable to handle incremental data added into data model one by one and batch data without rerun whole database from scratch.

Table of Contents
Table of Contents.…………………………………………………………………I
List of Figures……………………………………………………………………IV
List of Tables……………………………………………………………………...VI
Chapter 1 Introduction	………………………………………………………..…1
1.1 Overview………………………………………………………..……1
1.2 Motivations and Research Objectives………………………………3
1.2.1 Changes of Mining Sequential Pattern………..…………5
1.2.2 Adjustable Minimum Support……………………….6
1.3 Organizations of this Dissertation…………………………………..8
Chapter 2 Related Works…………………………………..……………………….9
2.1 Overview……………………………………………………………9
2.2 Apriori………………………………………………………………10
2.2.1 GSP……………………………………………………10
2.2.2 SPADE…………………………………………………11
2.2.3 Drawbacks of GSP and SPADE………………11
2.3 Mining without candidate…………………………………………12
2.3.1 FP-tree………………………………….………………13
2.3.2 FreeSpan………………………………………………13
2.3.3 PrefixSpan……………………………………………14
		2.4 Closed and Maximal sequences……………………………………15
2.4.1 Maximal pattern and Closed Pattern…………..………15
2.4.2 CloSpan………………………………………..………16
2.4.3 FMMSP……………………………………...…………17
2.5 Maintaining……...…………………………………….………...…..17
Chapter 3 Fast Accumulation Lattice Algorithm for Mining Sequential Patterns……………………………………………………………..21
3.1 Overview…………………………………………………………….21
3.2 Introduction………………………………………………………….21
3.3 Preliminary…………………………………..………………………22
3.4 Maximal Sequences……………………………..…………………..23
3.5 FAL Algorithm……………………………………..………………..24
3.6 Performance analysis via example……………………..……………26
3.7 Conclusion……………………………………………...……………31
Chapter 4 Fast Mining of Closed Sequential Patterns……………………………32
4.1 Overview……………………….……………………………………32
4.2 Introduction……………………………………….…………………32
4.3 Preliminary…………………………………………..………………36
4.4 The FMCSP Algorithm…………………………………..………….38
4.5 Conclusion………………………………………………..…………45
Chapter 5 Maintaining and Mining Sequential Patterns in Incremental Sequence Database…………………………………………………………………47
	5.1 Overview……. ……………………………………………………47
			5.1.1 Introduction……………………………………………48
			5.1.2 Contributions…………..………………………..50
	5.2 Preliminary…………………………………………………………50
5.2.1 Incremental Sequence Database………………….53
5.2.2 Linear Algorithm………………………………….55
5.2.3 Nonlinear Algorithm………………………………56
		5.3 Related works………………………………………………………..57
		5.4 Adjustable Minimum Support………………………………………58
		5.5 MMSP Algorithm and Merge Algorithm……………………………59
		5.6 Example and Performance Analysis…………………………………61
		5.7 Conclusions and Future Works………………………………………71
Chapter 6 Conclusions……………….……………………………………………..72
		6.1 Contributions…………………………………………………………72
		6.2 Future Works…………………………………………………………73
Bibliography………………………………………………………………………..76
Vita……………………………………………..………………………………….85

 

List of Figures
Fig 2.1 generation-and-prune concept………………………………...……………19
Fig 2.2 Candidates of C2 and C2’ generated by L1 and C1……………..…………19
Fig. 3.1 Lattice with〈ACD〉and its subsequences……………………….………27
Fig. 3.2 〈ACD〉and 〈ABCE〉 Lattice……………………………………….28
Fig. 3.3 Complete Lattice…………………………………………………..………29
Fig. 3.4　Lattice of frequent sequence……………………………………………..30
Fig. 3.5 Lattice of Maximal Sequences…………………………………………….30
Fig. 4.1 Algorithm of FMCSP……………………………………………..……….38
Fig.4.2 example function of f……………………………………………………….39
Fig.4.3 example of function of g…………………………………………………....40
Fig.4.4 lattice of BD………………………………………………………………...43
Fig.4.5 lattice of BD and ABCD……………………………………………………44
Fig.4.6 lattice of 4 equivalent classes………………………………………………44
Fig. 4.7 Lattice with 10 equivalence classes………………………………………..45
Fig. 5.1  MMSP algorithm………………………………………………………...61
Fig.5.2 MergeFSS algorithm………….…………………...……………………….61
Fig.5.3 sequence database SDB and new appended sequence database ASDB..62
Fig. 5.4  FSS(SDB) contained 〈ACD〉…………………………………………63
Fig. 5.5  FSS with 〈ACD〉 and 〈ABCE〉 and their mutual sequence 〈AC〉…..63
Fig.5.6 example of upgrading mutual sequence…………………………………....65
Fig.5.7 FSS(ASDB) with sequence 〈BE〉……………………………………….65
Fig.5.8 upgrade mutual sequence 〈BE〉to F2……………………………………65
Fig.5.9 Merge FSS(SDB) with FSS(ASDB)………………………………………..66
Fig.5.10 upgrade 〈BE〉to F3…………………………………………………….66
Fig.5.11 Upgrade 〈ACD〉 to F2…………………………………………………66
Fig.5.12 Upgrade 〈AC〉to F3……………………………………………………...67
Fig.5.13 upgrade 〈C〉to F4……………………………………………………….67
Fig.5.14 upgrade 〈ABCE〉to F2………………………………………………….67
Fig.5.15 upgrade 〈BCE〉to F3……………………………………………………68
Fig.5.16 upgrade〈BE〉to F4……………………………………………………….68
Fig.5.17 upgrade 〈BE〉to F4……………………………………………………….68
Fig.5.18 FSS(SDB+ASDB)………….......................................................................69
List of Tables
Table 1-1 transaction database………………………………………………….4
Table 1-2 Sequence Database…………………………………………………..4
Table 1-3 Decompose of original sequence database………………………….5
Table 3.1 sample sequence database………………………………………………...27
Table 4.1 example sequence…………………………………………………...39
Table 4.2 Equivalence Class Table (ECT)…………………………………….41
Table 4.3 Projected ECT (PECT)……………………………………………...42

[1]	R. Agrawal, T. Imielinski, and A. Swami,”Mining Association Rules between Sets of Items in Large Databases,” Proc. of ACM SIGMOD, pages 207—216, May 1993.
[2]	R. Agrawal and R. Srikant. Mining sequential patterns. In Proc. 1995 Int. Conf. Data Engineering (ICDE’95), pages 3–14, Taipei, Taiwan, Mar. 1995.
[3]	M.-S. Chen, J. Han, and P. S. Yu. “Data Mining: An Overview from Database Perspective,” IEEE Transactions on Knowledge and Data Engineering, 8(6):866—883, December 1996.
[4]	 J. Han, ' Data Mining ', in J. Urban and P. Dasgupta (eds.), Encyclopedia of Distributed Computing , Kluwer Academic Publishers, 1999.
[5]	Rakesh Agrawal, Ramakrishnan Srikant , “Mining Sequential Patterns”, Eleventh International Conference on Data Engineering, 1995.
[6]	Ramakrishnan Srikant, Rakesh Agrawal, “Mining Sequential Patterns: Generalizations And Performance Improvements”, Proc. 5th Int. Conf. Extending Database Technology, EDBT, 1996.
[7]	Ming-Syan Chen, Jong Soo Park, Yu, P.S, “Efficient data mining for path traversal patterns”, IEEE Transactions on Knowledge and Data Engineering, Volume 10,  Issue 2,  March-April 1998, pp. 209 – 221.
[8]	Chan, K.C.C., Wong, A.K.C., Chiu, D.K.Y, "Learning sequential patterns for probabilistic inductive prediction,” IEEE Transactions on Systems, Man and Cybernetics, Volume 24,  Issue 10,  Oct. 1994 Page(s):1532 – 1547.
[9]	Ramakrishnan Srikant, Rakesh Agrawal, “Mining Sequential Patterns: Generalizations and Performance Improvements,” Proc. 5th Int. Conf. Extending Database Technology, EDBT, 1996.
[10]	Mohammed Javeed Zaki. , ”Fast mining of sequential patterns in very large databases,” Technical Report 668, Computer Science, University of Rochester, PO Box 270226, Rochester, Ny 14629, U.S.A., November 1997.
[11]	H. Mannila, H. Toivonen, and A. I. Verkamo, “Discovery of frequent episodes in event sequences,” Data Mining Knowl. Discov., vol. 1, no. 3, pp. 259–289, 1997.
[12]	Ky. S. M. N. Garofalakis and R. Rastogi, “SPIRIT: Sequential pattern mining with regular expression constraints,” VLDB J., 1999.
[13]	J. Han, J. Pri, B. Mortazavi-Asl, Q. Chen, U. Dayal, and M.-C. Hsu, FreeSpan: Frequent Pattern-Projected Sequential Pattern Mining, Proc. 2000 ACM SIGKDD Int’l Conf. Knowledge Discovery in Database (KDD ’00), pp. 355-359, Aug. 2000.
[14]	J. Han, J. Pei, and Y. Yin. “Mining frequent patterns without candidate generation”. In Proc.2000 ACM-SIGMOD Int. Conf. Management of Data (SIGMOD’00), pages 1-12, Dallas, TX, May 2000.
[15]	J. Han and J. Pei ' Mining Frequent Patterns by Pattern-Growth: Methodology and Implications,' ACM SIGKDD Explorations (Special Issue on Scalable Data Mining Algorithms), 2(2), December 2000. 
[16]	J. Pei, J. Han, H. Pinto, Q. Chen, U. Dayal, and M.-C. Hsu, ' PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth,' Proc. 2001 Int. Conf. on Data Engineering (ICDE'01), Heidelberg, Germany, April 2001.
[17]	Jian Pei, Jiawei Han, Behzad Mortazavi-Asl, Janyong Wang, Helen Pinto, Qiming Chen, Umeshwar Dayal, Mei-Chun Hsu,” Mining Sequential Patterns by Pattern-Growth: The PrefixSpan Approach,” IEEE Transactions on Knowledge and Data Engineering, vol. 16, No. 11, November 2004. 
[18]	Zhenglu Yang, Kitsuregawa, M., Masaru Kitsuregawa,”PAID: Mining Sequential Patterns by Passed Item Deduction in Large Databases,” Database Engineering and Applications Symposium,” 2006. IDEAS '06. 10th International, Dec. 2006 Page(s):113 – 120.
[19]	Changhai, Hu, Kongfa, Liu, Haidong, Ding, Youwei, Zhang, Chen, Ling, “FMGSP: An Efficient Method of Mining Global Sequential Patterns,” Fuzzy Systems and Knowledge Discovery, 2007. FSKD 2007. Fourth International Conference on, Volume 2,  24-27 Aug. 2007 Page(s):761 – 765.
[20]	Ching-Huang Yun   Ming-Syan Chen, “Mining Mobile Sequential Patterns in a Mobile Commerce Environment,” IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, March 2007, Volume: 37,  Issue: 2, pp 278-295.
[21]	J. Han, J. Wang, Y. Lu, and P. Tzvetkov, “Mining Top-K Frequent Closed Patterns without Minimum Support”, Proc. 2002 Int. Conf. on Data Mining (ICDM'02), Maebashi, Japan, Dec. 2002.
[22]	Seno, M.; Karypis, G., “SLPMiner: an algorithm for finding frequent sequential patterns using length-decreasing support constraint,” 2002 IEEE International Conference on Data Mining, 2002. ICDM 2002. Proceedings. 9-12 Dec. 2002 pp. 418 – 425.
[23]	Ding-Ying Chiu , Yi-Hung Wu , Arbee L. P. Chen, “An Efficient Algorithm for Mining Frequent Sequences by a New Strategy without Support Counting,” Proceedings of the 20th International Conference on Data Engineering, p.375, March 30-April 02, 2004. 
[24]	Ding-Ying Chiu, Yi-Hung Wu, Arbee L. P. Chen, “An Efficient Algorithm for Mining Frequent Sequences by a New Strategy without Support Counting,” ICDE '04: Proceedings of the 20th International Conference on Data Engineering, March 2004.
[25]	Shyue-Liang Wang; Mei-Hwa Wang; Wen-Yang Lin; Tzung-Pei Hong, “Adjustable discovery of adaptive-support association rules for collaborative recommendation systems,” 2004 IEEE International Conference on Systems, Man and Cybernetics, Volume 4,  10-13 Oct. 2004 Page(s):3250 - 3254 vol.4.
[26]	Yun Xiong, Yang-yong Zhu, “A Multi-Supports-Based Sequential Pattern Mining Algorithm,” Fifth International Conference on Computer and Information Technology (CIT'05), pp. 170-174.
[27]	Xiangjun Dong   Zhiyun Zheng   Zhendong Niu   Qiuting Jia, “Mining Infrequent Itemsets Based on Multiple Level Minimum Supports,” Innovative Computing, Information and Control, 2007. ICICIC '07. Second International Conference, Publication Date: 5-7 Sept. 2007, Kumamoto, pp. 528-528. 
[28]	Wei Wang, Jiong Yang, Philip S. Yu,” Mining patterns in long sequential data with noise,” ACM SIGKDD Explorations Newsletter, December 2000, Volume 2, Issue 2.
[29]	Roberto J. Bayardo Jr., “Efficiently Mining Long Patterns from databases,” Proc. of the 1998 ACM-SIGMOD Int’l Conf. on Management of Data, pp85-93.
[30]	N. Pasquier, Y. Bastide, R. Taouil and L. Lakhal,” Discoving frequent closed itemsets for association rules,” In ICDT’99, Jerusalem, Israel, Jan. 1999.
[31]	J. Yang, P. Yu, W. Wang, and J. Han, ' Mining Long Sequential Patterns in a Noisy Environment ', Proc. 2002 ACM-SIGMOD Int. Conf. on Management of Data (SIGMOD'02), Madison, WI, June 2002.
[32]	W. Wang, J. Yang, and P. Yu., “Mining patterns in long sequential data with noice,” ACM SIGKDD Explorations, 2(2)28-33, 2001.
[33]	M. Zaki, and C. Hsiao,” CHARM: An efficient algorithm for closed itemset mining,” In SDM’02, Arlington, VA, April 2002.
[34]	X. Yan, J. Han, and R. Afshar, “CloSpan: Mining Closed Sequential Patterns in Large Datasets”, Proc. 2003 SIAM Int.Conf. on Data Mining (SDM'03), San Fransisco, CA, May 2003.
[35]	Tzvetkov, P.; Yan, X.; Han, J.,” TSP: mining top-K closed sequential patterns” ICDM 2003Third IEEE International Conference on Data Mining, 19-22 Nov. 2003. pp.347 – 354.
[36]	Wang, J.   Han, J.,” BIDE: efficient mining of frequent closed sequences,” 20th International Conference on Data Engineering Proceedings, 30 March-2 April 2004, pp. 79- 90.
[37]	Tao Wang, Yan-Sheng Lu,” Mining of condensed sequential pattern bases,” Fifth World Congress on Intelligent Control and Automation, 2004. WCICA 2004. Volume 5, 15-19 June 2004, pp.4250 - 4254 Vol.5.
[38]	Jian Pei, Jian Liu, Haixun Wang, Ke Wang, Yu, P.S., Jianyong Wang,” Efficiently mining frequent closed partial orders,” Fifth IEEE International Conference on Data Mining, pp. 27-30 Nov. 2005.
[39]	Songram, P., Boonjing, V., Intakosum, S.,” Closed Multidimensional Sequential Pattern Mining,” Third International Conference on Information Technology: New Generations, 2006. ITNG 2006. 10-12 April 2006 pp.512 – 517.
[40]	Lucchese, C., Orlando, S., Perego, R.,” Fast and memory efficient mining of frequent closed itemsets,” IEEE Transactions on Knowledge and Data Engineering,  Volume 18,  Issue 1,  Jan. 2006 pp.21 – 36.
[41]	Jia-dong Ren, Ya-fei Sun, Sheng Guo,” Maximal Sequential Pattern Mining Based on Simultaneous Monotone and Anti-monotone Constraints,” IIHMSP 2007. Third International Conference on Intelligent Information Hiding and Multimedia Signal Processing, 2007. Volume 1, 26-28 Nov. 2007 pp.143 – 146.
[42]	Zhu, Tian, Bai, Sixue,” A Parallel Mining Algorithm for Closed Sequential Patterns,” AINAW '07, 21st International Conference on Advanced Information Networking and Applications Workshops, 2007, Volume 1,  21-23 May 2007 pp.392 – 395.
[43]	J. Han and Y. Fu. “Data driven discovery of quantitative rules in relational databases.” IEEE Trans. Knowledge and Data Engineering, 5:29-40, 1993.
[44]	C.-H. Lee, C.-R. Lin, and M.-S. Chen, “Sliding-window filtering: An efficient algorithm for incremental mining,” in Proc. ACM 10th Int. Conf. Inf. and Knowledge Management, Nov. 2001.
[45]	Florent Masseglia , Pascal Poncelet , Maguelonne Teisseire,” Incremental mining of sequential patterns in large databases,” Data & Knowledge Engineering, v.46 n.1, p.97-121, July 2003.
[46]	Walid G. Aref, Mohamed G. Elfeky, Ahmed K. Elmagarmid,” Incremental, Online, and Merge Mining of Partial Periodic Patterns in Time-Series Databases,” March 2004 IEEE Transactions on Knowledge and Data Engineering,   Volume 16 Issue 3.
[47]	Maged El-Sayed , Carolina Ruiz , Elke A. Rundensteiner,“ FS-Miner: efficient and incremental mining of frequent sequence patterns in web logs,” Proceedings of the 6th annual ACM international workshop on Web information and data management, November 12-13, 2004, Washington DC, USA.  
[48]	Jia-Dong Ren; Xiao-Lei Zhou,” A new maintenance algorithm for mining sequential patterns,” Proceedings of 2005 International Conference on Machine Learning and Cybernetics, 2005. Volume 3,  18-21 Aug. 2005 pp.1605 - 1610 Vol. 3.
[49]	Nock, R., Laur, P.-A., Symphor, J.-E., “Statistical Borders for Incremental Mining Statistical Borders for Incremental Mining,” 18th International Conference on Pattern Recognition, 2006. ICPR 2006. Volume 3, 0-0 0 pp.212 – 215.
[50]	Ming-Cheng Tseng, Wen-Yang Lin and Rong Jeng, "Incremental mining of generalized association rules under classification ontology and support constraint update," Joint 3rd International Conference on Soft Computing and Intelligent Systems and 7th International Symposium on advanced Intelligent Systems, Tokyo, Japan, 2006.
[51]	Chin-Chuan Ho; Hua-Fu Li; Fang-Fei Kuo; Suh-Yin Lee,” Incremental Mining of Sequential Patterns over a Stream Sliding Window,” Sixth IEEE International Conference on Data Mining Workshops, 2006. ICDM Workshops 2006. Dec. 2006 Page(s):677 – 681.
[52]	Ming-Cheng Tseng, Wen-Yang Lin and Rong Jeng, "Incremental maintenance of ontology-exploiting association rules," Proceedings of International Conference on Machine Learning and Cybernetics, Hong Kong, 2007.
[53]	Ching-Yao Wang; Tzung-Pei Hong; Shian-Shyong Tseng,” Maintenance of sequential patterns for record deletion,” Proceedings IEEE International Conference on Data Mining, ICDM 2001, 29 Nov.-2 Dec. 2001 pp.536 – 541.
[54]	Nancy P. Lin, Wei-Hua Hao and Hung-Jen Chen, “Fast Accumulation Lattice Algorithm for Mining Sequential Patterns”, Proceedings of the 6th WSEAS International Conference on Applied Computer Science (ACOS’07), pp. 230-234, Hangzhou, China, April 15-17, 2007.
[55]	Nancy P. Lin, Wei-Hua Hao,  Hung-Jen Chen, Hao-En Chueh and Chung-I  Chang, “Fast Mining Sequential Patterns”, Proceedings of the 7th WSEAS International Conference on Simulation, Modeling and Optimization Applied Computer Science (SMO ’07), pp. 405-408,Beijing ,China ,September 15-17, 2007.
[56]	Nancy P. Lin, Wei-Hua Hao, Hung-Jen Chen, Hao-En Chueh, Chung-I Chang, “Fast Mining of Closed Sequential Patterns”, WSEAS TRANSACTIONS on COMPUTERS, ISSN: 1109-2750 Issue 3, Volume 7, March 2008. (EI)