臺灣博碩士論文加值系統

In business applications, there have been tremendous interests in analyzing customers’ repeated purchase behavior. Recently, the concepts of periodic pattern and cyclic pattern are used to discover recurring patterns from customer sequence database. Toroslu (2003) proposed cyclic pattern mining, which considers a new parameter, named repetition support, into the mining process. In a customer sequence, the occurrence of a subsequence must satisfy single user-specified repetition minimum support. In real-life applications, however, different items may have different frequencies in the database. If all items are set to have the same minimum repetition support, it may cause rare item problem. To solve this problem, we include the concept of multiple minimum supports (MMS) to allow users to specify multiple minimum item repetition support (MIR) according to the natures of items. In this paper, we first redefine cyclic sequential patterns based on MIR and original form of customer minimum support. A new algorithm, rep-PrefixSpan, is developed to discover complete set of cyclic sequential patterns from sequence database. The experimental result shows that the proposed approach achieves more preferable findings than conventional cyclic pattern mining.

Abstract 1
1. Introduction 2
2. Related work 5
2.1 sequential pattern mining 5
2.2 Periodic pattern and cyclic pattern mining 5
2.3 Multiple minimum supports (MMS) 8
2.4 Summary 10
3. Problem definition 11
4. The rep-PrefixSpan Algorithm 17
4.1 Step 1. Find 1-CSPs 20
4.2 Step 2. Divide search space 20
4.3 Step 3. Find subsets of CSPs 21
5. Experimental study 24
5.1 Data 24
5.1 Performance evaluation 25
6. Conclusion 30
7. Reference 31

[1]M. J. Shaw, C. Subramaniam, G. W. Tan, and M. E. Welge, “Knowledge Management and Data Mining for Marketing”, Decision Support Systems, vol. 31, no. 1, pp. 127-137, 2001.
[2]R. Srikant and Y. Yang, “Mining Web Logs to Improve Website Organization,” in Proceedings of the 10th International World Wide Web Conference, Hong Kong, Hong Kong, pp. 430-437, 2001.
[3]Y. H. Tao, T. P. Hong, and Y. M. Su, “Web Usage Mining with Intentional Browsing Data,” Expert Systems with Applications, vol. 34, no. 3, pp. 1893-1904, April 2008.
[4]F. R. Lin, K. J. Huang, and N. S. Chen, “Integrating Information Retrieval and Data Mining to Discover Project Team Coordination Patterns,” Decision Support Systems, vol. 42, no. 2, pp. 745-758, November 2006.
[5]M. S. Chen, J. Han, and P. S. Yu, “Data Mining: an Overview from A Database Perspective,” IEEE Transaction on Knowledge and Data Engineering, vol. 8, pp. 866-886, 1996.
[6]W. J. Frawley, G. Piatetsky-Shapiro, and C. J. Matheus, “Knowledge Discovery in Databases: An Overview,” Knowledge Discovery in Databases, G. Piatetsky-Shapiro and W .J. Frawley, eds., pp. 1-27. AAAI/MIT Press, 1991.
[7]J. Han, and M. Kamber, “Data Mining: Concepts and Techniques,” Academic Press, New York, 2001.
[8]R. Cooley, B. Mobasher, and J. Srivastava, “Data Preparation for Mining World Wide Web Browsing Patterns,” In Journal of Knowledge & Information Systems, vol. 1, no. 1, 1999.
[9]M. Ester, “A Top-down Method for Mining Most Specific Frequent Patterns in Biological Sequence Data,” In Proceeding the fourth SIAM International Conference on Data Mining, pp.90-104, 2004.
[10]C. A. Kulikowski, “Pattern Recognition Approach to Medical Diagnosis,” IEEE Trans Syst Man Cybern, vol. 6, pp. 173-178, 1970.
[11]S. Vijayalakshmi, V. Mohan, and S. R. Suresh, “Mining Constraint-based Multidimensional Frequent Sequential Pattern in Web Logs,” European Journal of Scientific Research, vol. 36, no. 3, pp. 480-490, 2009.
[12]K. Wang, Y. Xu, and J. X. Yu, “Scalable Sequential Pattern Mining for Biological Sequences,” In Proceeding of the Sixth ACM SIGKDD International Conference on Knowledge Management, pp.178-187, 2004.
[13]I. H. Toroslu, “Repetition Support and Mining Cyclic Patterns,” Expert Systems with Applications, vol. 25, no. 3, pp. 303-311, 2003.
[14]B. Liu, W. Hsu, and Y. Ma, “Mining Association Rules with Multiple Minimum Supports,” In ACM SIGKDD international conference on Knowledge discovery and data mining, San Diego, CA, USA, 1999, pp. 15-18.
[15]M. V. Joshi, G. Karypis, and V. Kumar, “A Universal Formulation of Sequential Patterns,” In Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, 2001, pp. 1–21.
[16]M. J. Zaki, “Sequence mining in categorical domains: incorporating efficient algorithms for mining sequential patterns with time constraints,” in Proceedings of the 9th International Conference on Information and Knowledge Management, McLean, Virginia, USA, p. 422–429, 2000.
[17]Y. H. Hu, and Y. L. Chen, “Mining Association Rules with Multiple Minimum Supports: A New Mining Algorithm and A Support Tuning Mechanism,” Decision Support Systems, vol. 42, pp. 1-24, 2006.
[18]R. Agrawal and R. Srikant, “Mining Sequential patterns,” in Proceeding of 1995 International Conference on Data Engineering, pp. 3-14.
[19]R. Srikant and R. Agrawal, “Mining sequential patterns: Generalizations and Performance Improvements,” in Proceedings of the 5th International Conference on Extending Database Technology, pp. 3–17, 1996.
[20]M. J. Zaki, “SPADE: An efficient algorithm for mining frequent sequences.” Machine Learning Journal, vol. 42, iss. 1, pp. 31–60, 2001.
[21]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 sixth ACM SIGKDD international conference on Knowledge discovery and data mining, New York, USA, pp. 355–359, 2000
[22]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, no. 10, pp. 1424-1440, 2004.
[23]B. Ozden, S. Ramaswamy, and A. Silberschatz, “Cyclic Association Rules,” In Proceedings of the 14th International Conference on Data Engineering, Orlando, Florida, USA, 1998, pp. 412-421.
[24]J. Han, G. Dong, and Y. Yin, “Efficient Mining of Partial Periodic Patterns in Time Series Database,” In Proceedings of the 15th International Conference on Data Engineering, Sydney, NSW, Australia, 1999, pp. 106-115.
[25]D. A. Chiang, C. T. Wang, S. P. Chen, and C. C. Chen, “The Cyclic Model Analysis on Sequential Patterns,” IEEE transactions on knowledge and data engineering, vol. 21, no. 11, 2009.
[26]Y. S. Lee and S. J. Yena, “Incremental and interactive mining of web traversal patterns,” Information Sciences, vol 178, iss 2, pp. 287-306, 2008.
[27]H. F. Li, “A sliding window method for finding top-k path traversal patterns over streaming Web click-sequences,” Expert Systems with Applications, vol 36, iss 3, pp. 4382-4386, 2009.
[28]Y. T. Wang and Anthony J.T. Lee, “Mining Web navigation patterns with a path traversal graph,” Expert Systems with Applications, vol 38, iss 6, pp. 7112-7122, 2011.
[29]P.-H. Wu, W.-C. Peng and M.-S. Chen, “Mining Sequential Alarm Patterns in a Telecommunication Database,” In Proceedings of Workshop on Databases in Telecommunications (VLDB 2001), pp. 37–51, 2001.
[30]S. A. Ibrahim, O. Folorunso, and O. B. Ajayi, “Knowledge discovery of closed frequent calling patterns in a telecommunication database,” in proceeding of the 2005 information science and IT education joint conference, Arizona, USA, pp.137-148, 2005.
[31]J. Yang, W. Wang and P. S. Yu, “InfoMiner: Mining Surprising Periodic Patterns”, ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, pp. 395-400, 2001.
[32]G. Lee, W. Yang, and J. M. Lee, “A Parallel Algorithm for Mining Multiple Partial Periodic Patterns,” Information Sciences, vol. 176, no. 24, 15, pp. 3591-3609, 2006.
[33]A. K. Mahanta, F. A. Mazarbhuiya, and H. K. Baruah, “Finding Calendar-based Periodic Patterns,” Pattern Recognition Letters, vol. 29, no. 9, pp. 1274-1284, 2008.
[34]Bettini, X. S. Wang, and S. Jajodia, “Mining Temporal Relationships with Multiple Granularities in Time Sequences,” Data Engineering Bulletin, vol. 21, pp. 32-38, 1998.
[35]M. Leleu, C. Rigotti, J.-F. Boulicaut, and G. Euvrard, “Constraint-Based Mining of Sequential Patterns over Datasets with Consecutive Repetitions,” In Proceedings of the seventh European conference on principles and practice of knowledge discovery in databases (PKDD 03), pp. 303–314, 2003.C.
[36]B. Ding, D. Lo, J. Han, and S.-C. Khoo, “Efficient Mining of Closed Repetitive Gapped Subsequences from A Sequence Database” in proceeding of the 25th International Conference on Data Engineering (ICDE'09), pp. 1024-1035, 2009.
[37]R. U. Kiran and P. K. Reddy, “Improved Approaches To Mine Rare Association Rules in Transactional Databases,” In Proceeding of the Fourth SIGOD PhD Workshop on Innovative Database Research, Indianapolis, USA, 2010, pp.19-24.
[38]R. U. Kiran and P. K. Reddy, “Mining Periodic-Frequent Patterns with Maximum Items’ Support Constraints,” in Proceedings of the Third Annual ACM Bangalore Conference, Bangalore, India, 2010.
[39]Y. H. Hu, C. K Huang, H. R. Yang, and Y. L. Chen, “On Mining Multi-time-interval Sequential Patterns,” Data & Knowledge Engineering, vol. 68, pp. 1112-1127, 2009.