臺灣博碩士論文加值系統

在以滿足顧客需求為競爭關鍵的時代中，管理者若能有效掌握顧客的行為脈動，適時提供正確的服務滿足顧客的需求，便能提升企業競爭優勢，也因此瞭解顧客行為的變化就成為企業獲利與否的關鍵因素。雖然目前已有很多研究在於探討顧客行為的規則，卻鮮少於討論隨時間變動的行為變化議題。有鑑於此，本研究應用序列樣式探勘技術探討在兩個不同時間區段下的顧客行為變化，並且運用Microsoft SQL Server 2000中的範例證實本研究之可行性。本研究首先應用AprioriAll演算法分別挖掘不同時間下的序列樣式。接著將挖掘出的序列樣式依照序列樣式比對方式計算其間的改變程度，再根據三種不同類型的定義對序列樣式進行分類(即分類為emerging sequential patterns, unexpected sequence changed and added/perished sequential patterns)。最後，再由每種類型中選出顯著改變的行為樣式分析討論，以供為管理著制定策略的參考方針。

To satisfy customer’s requirements and increase competition in market, it is critical for an enterprise to understand changes of customer behavior. If managers can understand changes of customer behavior, they can retain customers through providing appropriate products and services to satisfy their needs. Although many researches have focused on knowing the regularity of customer’s purchase behavior, little attention has been paid to mine change of sequence in databases collected over time. Therefore, the objective of this research is to develop a systematic method to discover the change of customer behavior, and provide an implementation case to demonstrate the feasibility of the proposed method. The proposed method uses sequential pattern mining to explore the change of behavior sequence in different two time-periods. First, the AprioriAll algorithm is used to discover all sequential patterns in different time-periods. Then sequential patterns are clarified as one of three change types (emerging sequential patterns, unexpected sequence changed and added/perished sequential patterns) through proposed sequential pattern matching method to understand the degree of change. Finally, a set of sequential patterns with significant change are retrieved. With the useful information, managers can make better business decision.

ABSTRACT i
摘要 ii
致謝 iii
TABLE OF CONTENT iv
LIST OF TABLE vii
CHAPTER 1 INTRODUCTION 1
1.1 Research Background 1
1.2 Research Motivation 1
1.3 Research Objectives 3
1.4 Thesis Organization 3
CHAPTER 2 LITERATURE REVIEW 5
2.1 Data Mining 5
2.2 The Apriori Algorithm 7
2.3 Sequential Pattern Mining 9
2.3.1 Classification for the Sequential Pattern Mining 10
2.3.2 The Frequent Sequential Pattern Algorithms 11
2.3.3 Related Researches 12
2.4 The AprioriAll Algorithm 14
2.5 Data Mining in a Change Environment 18
CHAPTER 3 MINING CHANGE OF SEQUENTIAL PATTERNS 23
3.1 Research Framework 23
3.2 Basic Concepts 25
3.3 AprioriAll Algorithm 26
3.4 The Definitions for Three Sequential Change Patterns 28
3.5 The Definition for MT 30
3.6 Sequence Change Detection Method 31
3.6.1 Difference Measures 31
3.6.2 The Sequential Pattern Matching Algorithm 34
3.6.3 Minimal Differences 38
3.6.4 Change Pattern Evaluation Standards 39
3.6.5 An Example Illustration 40
3.7 Evaluating Degree of Change 46
CHAPTER 4 IMPLEMENTATION AND EXPERIMENTAL RESULTS 48
4.1 Development Environment 48
4.2 Data Source 48
4.3 Sequential Patterns Generation 50
4.3.1 Intelligent Miner 50
4.3.2 Sequential Pattern Sets for Two Time Periods 55
4.4 Change Detection Analysis 58
4.5 Significant Changed Pattern Analysis 64
4.5.1 Significant Emerging Sequential Pattern 64
4.5.2 Significant Unexpected Sequence Change 67
4.5.3 Significant Added/Perished Sequential Pattern 72
CHAPTER 5 CONCLUSION AND FUTURE WORKS 79
5.1 Conclusion 79
5.2 Future Works 80
REFERENCE 82

Agrawal, R. and Srkant, R., 1994, Fast algorithm for mining association rules. Proceedings of the 20th VLDB Conference, Santige, Chile.

Agrawal, R. and Srkant, R., 1995, Mining sequential pattern. Proceedings of the 11th International Conference on Data Engineering, 3-14.

Agrawal, R., Faloutsos, C. and Swami, A., 1993, Efficient similarity search in sequence databases. 4th International Conference on Foundations of Data Organization and Algorithms, 69-84.

Altiparmak, F., Ferhatosmanoglu, H., Erdal, S. and Trost, D. C., 2006, Information Mining Over Heterogeneous and High-Dimensional Time-Series Data in Clinical Trials Databases. IEEE Transactions on Information Technology in Biomedicine, 10(2), 254 – 263.

Bettini, C., Wang, S., Jajodia, S., and Lin, J. L., 1998, Discovering frequent event patterns with multiple granularities in time sequences. IEEE Transactions on Knowledge and Data engineering, 10(2), 222-237.

Chen, L. C., 2003a, Using data mining techniques to enhance customer relationship management for credit card gold customers. Department of Industrial Engineering and Management, Yuan-Ze University.

Chen, M. C., Chiu, A. L., and Chang, H. H., 2005, Mining changes in customer behavior in retial marketing. Expert Systems with Applications, 28, 773-781.

Chen, M. S., Park, J. S., and Yu, P. S., 1998, Efficient data mining for path traversal patterns. IEEE Transactions on Knowledge and Data Engineering, 10(2), 209-221.

Chen, P. C., 2002, The research and implementation for the sequential patterns mining system. Department of Information Engineering, Nation Taiwan University.

Chen, S. S., 2003b, The research of mining frequent sequential patterns. Department of Information Management, Nation Central University.

Chen, Z., 2001, Data mining and uncertain reasoning. A wiley-interscience publication.

Cheung, D. W., Han, J., Ng, V. T. and Wong, C. Y., 1996a, Maintenance of discovered association rules in large databases: an incremental updating technique. Processings of the 12th International Conference on Data Engineering, 106-114.

Cheung, D. W., Ng, V. T. and Tam, B. W., 1996b, Maintenance of discovered knowledge : a case in multi-level association rules. Processings of the 2th International Conference on Knowledge Discovery and Data Mining, 307-310.

Chiang, D. A., Wang, Y. F., Lee, S. L., and Lin, C. J., 2003, Goal-oriented sequential pattern for network banking churn analysis. Expert System with Applications, 25, 293-302.

Chou, S. H., 2003, Application of ant system on clustering analysis in data mining. Department of Production System Engineering and Management. National Taipei University of Technology.

Cooley, R., Mobasher, B., and Srivastava, J., 1997, Web mining: information and pattern discovery on the world wide web. Proceedings of the 9th IEE International
Conference on Tools with Artificial Intelligence.
Das, G., Lin, K., Mannila, H., Renganathan, G., and Smyth, P., 1998, Rule discovery from time series. Proceedings of the 4th International Conference on Knowledge Discovery and Data Mining, 16-22.

Dong, G. and Li, J., 1999, Efficient mining of emerging patterns: discovering trends and differences. Proceedings of the 5th International Conference on Knowledge Discovery and Data Mining, 43-52.

Duda, R., O., Hart, P. E. and Stork, D. G., 2001, Pattern Classification, the second edition (New York: John Wiley).

Dunham, M. H., 2002, Data mining introductory and advanced topics. An Alan R. Apt Book, Prentice Hall.

Fan, H., and Ramamohanarao, K., 2003, Efficiently mining interesting emerging patterns. Advances in Web-Age Information Management, 2762, pp. 189–201.

Frawley, W. J., Piatetsky-Shapiro, G.., and Matheus, C. J., 1991, Knowledge discovery in databases: an Overview. Knowledge Discovery in Databases, Cambridge, MA:AAA/MT, 213-228.

Ganti, V., Gehrke, J., and Ramakrishman, R., 1999, A framework for measuring changes in data characteristics. Proceedings of the 18th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 126-137.

Giudici, P., and Passersone, G., 2002, Data mining of association structures to model consumer behavior. Computational Statistics and Data Analysis, 38,533-541.

Gunopulos, D. and Das, G., 2001, Time series similarity measures and time series indexing. ACM SIGMOD, California USA, 30(2), 624.

Han, J., and Kamber, M., 2001a, Data mining concepts and technique. Morgan Kaufmann Publishers.

Han, J., Dong, G. and Yin, Y.,1999, Efficient mining of partial periodic patterns in time series database. Proceedings of the 5th International Conference on Data Engineering, 106-115.

Han, J., Pei, J., Mortazvi-Asl, B., Chen, Q., Dayal, U. and Hsu, M., 2000, FreeSpan: frequent pattern-projected sequential pattern mining. Proceedings of the International Conference on Knowledge Discovery and Data Mining, 355-359, Boston.

Han, J., Pei, J., Pinto, H., Chen, Q., Dayal, U. and Hsu, M., 2001b, PrefixSpan: mining sequential pattern efficiently by prefix-projected pattern growth. Proceedings of the 17th International Conference on Data Mining, 215-224, Germany.

Hand, D. J., Blunt, G., Kelly M. G. and Adams, N. M., 2000, Data mining for fun and profit. Statistical Science, 15(2), 111-131.

Holland, J. H., 1992, Adaptation in natural and artificial system: an introductory analysis with applications to biology, control, and artificial intelligence. MIT Press, Reprint edition.

IBM Crop. Using the Intelligent Miner for Data. First Edition, September 1998.

Kung, S. H., 2003, Applying genetic algorithm and weight item to association rule. Department of Industrial Engineering and Management, Yuan-Ze University.

Lanquillon, C., 1999, Information filtering in changing domains. Proceedings of the International Joint Conference on Artificial Intelligence, 41-48.

Lee, C. H., Lin, C. R., and Chen, M. S., 2005, Sliding window filtering: an efficient method for incremental mining on a time-variant database. Information Systems, 30(3), 227-244.

Li, J., and Wong, L., 2002, Identifying good diagnostic gene groups from gene expression profiles using the concept of emerging patterns. Invited talk at Singapore MicroArray Meeting 2002.

Li, J., Dong, G., and Ramamohanarao K. 2001, Making use of the most expressive jumping emerging patterns for classification. Knowledge and Information Systems, 3,131-145.

Li, J., Dong, G., and Ramamohanarao K. 2004, Deeps: A new instance-base lazy discovery and classification. Machine Learning, 54(2), 99-124.

Lin, Y. C., 2002, Sequence-based text retrieval design and implementation. Department of Information Management, National Taiwan University.

Liu, B. and Hsu, W., 1996, Post-analysis of learned rules. Proceeding of the 13th National Conference on Artificial Intelligence, 828-834.

Liu, B., Hsu, W., Chen, S. and Ma, Y., 2000, Analyzing the subjective interestingness of association rules. IEEE Intelligent Systems, 15(5), 47-55.

Liu, B., Hsu, W., Han, H. S. and Xia, Y., 2000, Mining changes for real-life applications. 2th International Conference on Data Warehousing and Knowledge Discovery, 337-346.

Liu, B., Hsu, W., Ma, Y., and Chen, S.,1999, Mining interesting knowledge using DM-II. Proceedings of the 5th International Conference on Knowledge Discovery and Data Mining, 430-434.

Liu, T., Chen, Z., Zhang, B., Ma W. Y. and Wu G., 2004, Improving text classification using local latent semantic indexing. , 2004. Proceedings of the 4th IEEE International Conference on Data Mining, 162 – 169.

Majumder, S. K., Gupta, A., Gupta, S., Ghosh, N. and Gupta, P. K., 2006, Multi-class classification algorithm for optical diagnosis of oral cancer. Journal of Photochemistry and Photobiology B: Biology, 85, 109-117.

Masseglia, F., Poncelet P., and Teisseire, M., 2003, Incremental mining of sequential patterns in large databases. Data and Knowledge Engineering, 46, 97-121.

Mobasher, B., Jain, N., Han, E., and Srivastava, J., 1996, Web mining: pattern discovery from world wide web transactions. Technical Report TR96-050, Department of Computer Science, University of Minnesota.

Nakhaeizadeh, G., Taylor, C., and Lanquillon, C., 1998, Evaluating usefulness of dynamic classification. Proceedings of the 4th International Conference on Knowledge Discovery and Data Mining.

Padmanabhan, B., and Tuzhilin, A.,1999, Unexpectedness as a measure of interestingness in knowledge discovery. Decisiion Support System, 27,303-318.

Padmanabhan, B., and Tuzhilin, A.,2006, On characterization and discovery of minimal unexpected patterns in rule discovery. IEEE Transactions on Knowledge and Data Engineering, 18(2), 202 – 216.

Pei, J., Han, J., Mortazavi-asl, B., and Zhu, H., 2000, Mining access patterns efficiently from web logs. Proceedings of 2000 Pacific-Asia Conference on Knowledge Discovery and Data Mining, Kyoto, Japan.

Piatetsky-Shapior, G., 1993, An overview of knowledge discovery in databases: recent progress and challenges. Proceeding of the International Workshop on Rough Sets and Knowledge Discovery, Banff, Alberta, Canada.

Ramirez, J. C. G., Cook, D. J., Peterson, L. L., Peterson, D. M., 2000, Temporal pattern discovery in course-of-disease data. IEEE Engineering in Medicine and Biology Magazine, 19 (4), 63-71.

Sadakane, k., and Imai, H., 1999, Text retrieval by using k-word proximity search. Database Applications in Non-Traditional Environments.

Shieh, S. F., 2002, An efficient approach for maintaining association rules based on adjusting Fp-tree structure. Department of Information and Computer Education, National Taiwan Normal University.

Soldacki, P., and Protaziuk, G., 2002, Discovering interesting rules from financial data. Proceedings of the IIS’2002 Symposium on Intelligent Information system, 109-119.

Song H. S., Kim, J. K. and Kim, S. H., 2001, Mining the change of customer behavior in an internet shopping mall. Expert Systems with Applications, 21, 157-168.

Terlecki, P. and Walczak, K., 2006, On the relation between rough set reducts and jumping emerging patterns. Information Sciences.

Wagner, R. A. and Fischer, M. J., 1974, The string-to-string correction problem. Journal of the Association for Computing Machinery, 21(1), 168-173.

Wang, C. Y., Hong, T. P. and Tseng, S. S., 2002, Maintenance of sequential patterns for record modification using Pre-large sequences. IEEE international Conference on Data Mining, 693-696.

Wong, M. L., L. Wai, L., Leung, K. S., Ngan, P. S., and Cheng J. C. Y., 2000, Discovering knowledge from medical databases using evolutionary algorithms. IEEE Engineering in Medicine and Biology Magazine, 19, 45-55.

Wu, P. H., Pen, W. C., and Chen, M. S., 2001, Mining sequential alarm patterns in a telecommunication database. Proceedings of Workshop on Databases in telecommunications, 37-51.

Yen, Y. H., 2005, A study of applying sequential pattern mining to the college entrance examination databases. Department of Industrial Engineering and Management, Yuan-Ze University.

Yu, F., Chen, F. and Dong, K., 2005, A granulation-based method for finding similarity between time series. IEEE International Conference on Granular Computing, 2, 700-703.

Zaiane, O. R., Xin, M., and Han, J., 1998, Discovering wed access patterns and trends by applying OLAP and data mining technology on web logs. Proceedings Advances in Digital Libraris Conference, Santa Barbara, CA, 19-29.

Chen, Y. L., 資料間隱含關係的回顧與展望,
http://www.mgt.ncu.edu.tw/~ylchen/datamining.html