臺灣博碩士論文加值系統

一般而言，序列樣式探勘常會使用資料庫中的交易編號、商品編號、會員編號與交易的發生時間，其中交易時間往往只使用了事件開始的時間點，而忽略了結束時間，以至於探勘結果所獲得的資訊只是某部份的訊息，殊為可惜。此外在實務的應用上，固定資料庫或累加資料庫為基礎的資料探勘已無法滿足即時資訊的需求，而使得其結果與現實所需產生不同步的情況。
因此，本研究在事件的符號表示法上加入起、迄點之間的時間距離概念，除了提出新的區間樣式表示法，將傳統上以時間點為基礎的序列樣式探勘轉變為以事件為基礎的序列區間樣式探勘作為資料探勘之用，以彌補過去單純項目符號上的限制，以獲取更多有用的資訊。此外在累進序列區間樣式探勘上，針對使用者對取得最新資訊的需求，我們提出興趣視窗的概念，並利用累進資料庫的做法，不僅加入新的資料而且刪除舊有的資料，以期除了在節省空間之外並探勘出最新的頻繁序列區間樣式。
實驗結果顯示，本研究針對以事件為主的序列區間樣式探勘所提出的AprioriAll-Like演算法和SP&EPPF演算法均能達到我們對於以事件為主的資料探勘需求。其中，SP&EPPF演算法將資料庫中以事件為主的序列，先分別以事件發生時間的起始點和結束點分割成為DB+與DB-兩個資料庫，各自找出其所有的頻繁樣式集，再利用事件本身起訖點成對的特性做序列樣式的結合，此一方法不僅只於有效率，對於尋找個別資料庫中的頻繁序列樣式演算法均可以套用任何的序列樣式探勘演算法於其中。
而在累進資料庫的區間樣式序列樣式探勘上，本研究則是提出興趣視窗的概念與BUUL演算法，以滿足使用者對於即時資訊的需求，此外並利用晶格架構來維護所記錄的頻繁區間樣式，此一方法不僅增加新的序列資料到資料庫中，並且刪除舊有的資料，以保持相同的序列數。而實驗結果在效能與空間上均能取得有效的平衡，並且較單一時間點的序列樣式探勘更能提供我們有用的資訊。

Abstract
Generally speaking, the sequential pattern mining usually utilizes the transaction ID, item number, customer number, and the occurrence time to discover useful patterns. Among these records in the database, the sequential pattern mining usually only employs the starting points to mine frequent patterns, but ignores the ending points. This result may fail to obtain some useful patterns. In the addition of practical applications, mining in the static database and incremental database has already can not satisfied with up-to-date demand. This may has no simultaneous solution.
For these reasons, this research employs the concept of period of time which includes the starting point and the ending point. By using this method, we can change the sequential point-based pattern mining into sequential interval-based pattern mining and avoid the limit of symbol. It is now our demand to propose a concept of window of interest and mining the up-to-date sequential interval-based patterns with the progressive database while the data in the database may be inserted or deleted.
The experimental results show that both proposed algorithms, AprioriAll-Like and SP&EPPF, can be employed in the sequential interval-based pattern mining. Besides, SP&EPPF algorithm is not only effective and efficient in the performance, but also can utilize any traditional sequential pattern mining algorithm in it. Moreover, in order to deal with the sequential interval-based pattern mining in the progressive database, this study also proposes the BUUL algorithm, which employs bottom-up lattice structure to maintain the frequent interval-based patterns. The experimental results show that BUUL-based algorithm not only significantly outperforms the prior methods in execution time by orders of magnitude but also possesses graceful scalability.
Keywords： Interval-based pattern, Progressive database, Window of interest, Lattice structure, Sequential interval-based pattern mining

中文摘要………………………………………………………………………...i Abstract…………………………………………………………………………ii
致謝………………..……………………………………………………………iii
Contents………………………………………………….………..……………iv
List of Tables………..…………………….……………………..…………..….v
List of Figures……………………………………………………………….…vi
Chapter 1 Introduction 1
Chapter 2 Related Work 3
2.1 Temporal Data Concept 3
2.2 Association Rule Mining 6
2.3 Dynamic database 8
Chapter 3 Sequential Interval-based Pattern Mining 12
3.1 Problem Definition 12
3.2 Sequential Interval-based Pattern Mining (SIPM) 15
3.2.1 Data transformation 15
3.2.2 The AprioriAll-Like Algorithm 15
3.2.3 The SP&EPPF Algorithm 17
Chapter 4 Progressive Sequential Interval-based Pattern Mining (PSIPM) 20
4.1 The Bottom-Up Update Lattice (BUUL) Algorithm 20
4.2 The PSIPM Lattice Tree 21
Chapter 5 Experimental Results 25
5.1 Data generation 25
5.2 Runtime comparisons 26
Chapter 6 Conclusions 31
Reference………………………………………………………………………33

1.R. Agrawal and R. Srikant, “Mining sequential patterns,” In Proceedings of the 11th International Conference on Data Engineering (ICDE ’95), pp. 3-14, 1995.
2.J. Han and M. Kamber, “Data Mining: Concepts and Techniques,” Academic Press, 2001.
3.J. F. Allen, “Maintaining knowledge about temporal intervals,” Communications of the ACM, vol. 26, no. 11, pp. 832-843, 1983.
4.S. Y Wu and Y. L. Chen, “Mining nonambiguous temporal patterns for interval-based events,” IEEE Transactions on Knowledge and Data Engineering, vol. 19, pp. 742-758, 2007.
5.J. Pei, J. Han, B. Mortazavi-Asl, J. Wang, H. Pinto, Q. Chen, U. Dayal, and M.-C. Hsu, “Mining sequential patterns by pattern-growth: The PrefixSpan approach,” IEEE Transactions on Knowledge and Data Engineering, vol. 16, pp. 1424-1440, 2004.
6.R. Srikant and R. Agrawal, “Mining sequential patterns: generalizations and performance improvements,” In Proceedings of the 5th International Conference Extending Database Technology (EDBT ’96), pp. 3-17, 1996.
7.M. J. Zaki, “SPADE: An efficient algorithm for mining frequent sequences,” Machine Learning, vol. 42, no. 1-2, pp. 31-60, 2001.
8.F. Mörchen, “Unsupervised pattern mining from symbolic temporal data,” ACM SIGKDD Explorations Newsletter, vol. 9, no. 1, pp. 41-55, 2007.
9.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,” In Proceedings of 17th International Conference on Data Engineering (ICDE ’01), pp. 215-224, 2001.
10.G. Chen, X. Wu, and X. Zhu, “Sequential pattern mining in multiple streams,” In Proceedings of 5th International Conference on Data Mining (ICDM ’05), pp. 585-588, Nov. 2005.
11.S. Nguyen, X. Sun, and M. Orlowska, “Improvements of INCSPAN: Incremental mining of sequential patterns in large database,” In Proceedings of 9th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), pp. 442-451, 2005.
12.J. W. Huang, C. Y. Tseng, J. C. Ou, and M. S. Chen, “A general model for sequential pattern mining with a progressive database,” IEEE Transactions on Knowledge and Data Engineering, vol. 20, pp. 1153-1167, 2008.
13.P.S. Kam and A. W.-C. Fu, “Discovering temporal patterns for interval-based events,” In Proceedings of the 2nd International Conference on Data Warehousing and Knowledge Discovery (DaWaK’00), pp. 317-326, 2000.
14.F. Mörchen and A. Ultsch, “Efficient mining of understandable patterns from multivariate interval time series,” Data Mining and Knowledge Discovery, vol. 15, no. 2, pp. 181-215, 2007.
15.J. Lin, E. Keogh, S. Lonardi, and B. Chiu. “A symbolic representation of time series, with implications for streaming algorithms,” In Proceedings of the 2003 ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, pp. 2-11, 2003.
16.H. Mannila, H. Toivonen, and A. I. Verkamo. “Discovery of frequent episodes in event sequences,” Data Mining and Knowledge Discovery, vol. 1, no. 3, pp. 259-289, 1997.
17.E. Keogh, S. Chu, D. Hart, and M. Pazzani. “Segmenting time series: A survey and novel approach,” In M. Last, A. Kandel, and H. Bunke, editors, Data Mining In Time Series Databases, chapter 1, pp. 1-22. World Scientific, Singapore, 2004.
18.F. H¨oppner. “Learning dependencies in multivariate time series,” In Workshop on Knowledge Discovery in (Spatio-) Temporal Data at the 15th European Conference on Artificial Intelligence (ECAI’02), pp. 25–31, 2002.
19.M. Last, Y. Klein, and A. Kandel. “Knowledge discovery in time series databases,” IEEE Transactions on Systems, Man, and Cybernetics, vol. 31, no . 1, pp. 160-169, 2001.
20.R. Agrawal, T. Imielinski, and A. N. Swami, “Mining association rules between sets of items in large databases,” In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, pp. 207-216, 1993.
21.R. Agrawal and R. Srikant, “Fast algorithms for mining association rules,” In Proceedings of the 20th International Conference on Very Large Data Bases (VLDB’94), pp. 487-499, 1994.
22.J. Han, J. Pei, and Y. Yin, “Mining frequent patterns without candidate generation,” In Proceedings of ACM SIGMOD International Conference on Management of Data (SIGMOD ’00), pp. 1-12, 2000.
23.S. Aseervatham, A. Osmani, and E. Viennet, “bitSpade: A Lattice-Based Sequential Pattern Mining Algorithm Using Bitmap Representation,” In Proceedings of the 6th International Conference on Data Mining (ICDM), pp. 792-797, 2006.
24.J. Ayres, J. Gehrke, T. Yiu, and J. Flannick, “Sequential pattern mining using a bitmap representation,” In Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’02), pp. 429-435, July 2002.
25.J. Han, J. Pei, B. Mortazavi-Asl, Q. Chen, U. Dayal, and M.-C. Hsu, “FreeSpan: Frequent Pattern-Projected Sequential Pattern Mining,” In Proceedings of the 6th ACM/SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’00), pp. 355-359, 2000.
26.H. Cheng, X. Yan, and J. Han, “INCSPAN: Incremental Mining of Sequential Patterns in Large Database,” In Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’04), pp. 527-532, 2004.
27.M.-Y. Lin and S.-Y. Lee, “Incremental Update on Sequential Patterns in Large Databases by Implicit Merging and Efficient Counting,” Information System, vol. 29, no. 5, pp. 385-404, July 2004.
28.F. Masseglia, P. Poncelet, and M. Teisseire, “Incremental Mining of Sequential Patterns in Large Databases,” Data and Knowledge Engineering, vol. 46, pp. 97-121, July 2003.
29.S. Parthasarathy, M.J. Zaki, M. Ogihara, and S. Dwarkadas, “Incremental and Interactive Sequence Mining,” In Proceedings of the 8th ACM International Conference on Information and Knowledge Management (CIKM ’99), pp. 251-258, 1999.
30.S. Cong, J. Han, and D. Padua, “Parallel Mining of Closed Sequential Patterns,” In Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’05), pp. 562-567, Aug. 2005.
31.J. Wang and J. Han, “Bide: Efficient Mining of Frequent Closed Sequences,” In Proceedings of the 20th International Conference on Data Engineering (ICDE ’04), pp. 79-91, 2004.
32.X. Yan, J. Han, and R. Afshar, “Clospan: Mining Closed Sequential Patterns in Large Datasets,” In Proceedings of the 3th SIAM International Conference on Data Mining (SDM ’03), pp. 166-177, May 2003.
33.M.N. Garofalakis, R. Rastogi, and K. Shim, “Spirit: Sequential Pattern Mining with Regular Expression Constraints,” In Proceedings of the 25th International Conference on Very Large Data Bases (VLDB ’99), pp. 223-234, 1999.
34.Y. Hirate and H. Yamana, “Sequential Pattern Mining with Time Interval,” In Proceedings of the 10th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD ’06), pp. 775-779, 2006.
35.J.-Z. Ouh, P. Wu, and M.-S. Chen, “Constrained Based Sequential Pattern Mining,” In Proceedings of the International Workshop Web Technology, Dec. 2001.
36.J. Pei, J. Han, and W. Wang, “Mining Sequential Patterns with Constraints in Large Databases,” In Proceedings of the 11th ACM International Conference on Information and Knowledge Management (CIKM), 2002.
37.C. Luo and S.M. Chung, “Efficient Mining of Maximal Sequential Patterns Using Multiple Samples,” In Proceedings of the 5th SIAM International Conference on Data Mining (SDM), 2005.
38.H. Cao, N. Mamoulis, and D.W. Cheung, “Mining Frequent Spatio-Temporal Sequential Patterns,” In Proceedings of the 5th International Conference on Data Mining (ICDM ’05), pp. 82-89, Nov. 2005.
39.J.-K. Guo, B.-J. Ruan, and Y.-Y. Zhu, “A Top-Down Algorithm for Web Log Sequential Pattern Mining,” In Proceedings of the 9th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), 2005.
40.K. Wang, Y. Xu, and J.X. Yu, “Scalable Sequential Pattern Mining for Biological Sequences,” In Proceedings of the 13th ACM International Conference on Information and Knowledge Management (CIKM ’04), pp. 178-187, Nov. 2004.
41.C.-C. Ho, H.-F. Li, F.-F. Kuo, and S.-Y. Lee, “Incremental Mining of Sequential Patterns over a Stream Sliding Window,” In Proceedings of the IEEE International on Workshop Mining Evolving and Streaming Data (IWMESD ’06), Dec. 2006.
42.A. Marascu and F. Masseglia, “Mining Sequential Patterns from Temporal Streaming Data,” In Proceedings of the 1th ECML/PKDD Workshop Mining Spatio-Temporal Data (MSTD ’05), Oct. 2005.
43.A. Marascu and F. Masseglia, “Mining Sequential Patterns from Data Streams: A Centroid Approach,” Journal of Intelligent Information Systems, vol. 27, no. 3, pp. 291-307, Nov. 2006.
44.C.-R. Lin, C.-H. Yun, and M.-S. Chen, “Utilizing Slice Scan and Selective Hash for Episode Mining,” In Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’01), Aug. 2001.
45.M.-S. Chen, J.-S. Park, and P.S. Yu, “Efficient Data Mining for Path Traversal Patterns,” IEEE Transactions Knowledge and Data Engineering, vol. 10, no. 2, pp. 209-221, Mar./Apr. 1998.
46.A. Balachandran, G.M. Voelker, P. Bahl, and P.V. Rangan, “Characterizing User Behavior and Network Performance in a Public Wireless LAN,” In Proceedings of the ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS’02), June 2002.
47.Q. Yang and H.H. Zhang, “Web-Log Mining for Predictive Web Caching,” IEEE Transactions Knowledge and Data Engineering, vol. 15, no. 4, pp. 1050-1053, July/Aug. 2003.
48.Q. Yang, H.H. Zhang, and T. Li, “Mining Web Logs for Prediction Models in WWW Caching and Prefetching,” In Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’01), pp. 473-478, Aug. 2001.
49.A.B. Pandey, J. Srivastava, and S. Shekhar, “Web Proxy Server with Intelligent Prefetcher for Dynamic Pages Using Association Rules,” Technical Report 01-004, Univ. of Minnesota, Jan. 2001.
50.A.B. Pandey, R.R. Vatsavai, X. Ma, J. Srivastava, and S. Shekhar, “Data Mining for Intelligent Web Prefetching,” In Proceedings of the Workshop Mining Data Across Multiple Customer Touchpoints for CRM (MDCRM ’02), May 2002.
51.C. Romero, S. Ventura, J.A. Delgado, and P.D. Bra, “Personalized Links Recommendation Based on Data Mining. In Adaptive Educational Hypermedia Systems,” In Proceedings of the 2th European Conference on Technology Enhanced Learning (EC-TEL ’07), Sept. 2007.
52.M. Zhang, B. Kao, D. Cheung, and C. L. Yip, “Efficient Algorithms for Incremental Update of Frequent Sequences,” In Proceedings of the 6th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD ’02), 2002.