臺灣博碩士論文加值系統

近年來，效益挖掘因具有廣泛的實務應用而受到高度重視，其主因為效益挖掘除了考慮每筆交易紀錄裡的購買項目外，亦考慮購買數量與項目利潤，藉此評估每個項目在資料集中的實際效益值。大部份既存的相關研究皆是僅考慮單一資料集裡的效益挖掘，但在現實生活中，一家大型企業常常擁有多個在不同地點的商店或是分公司。此外，如何靈活地回應來自不同用戶的查詢條件，也是一項很大的挑戰。因此，在本論文中，我們開發了適當的線上挖掘方法來找出在多點環境中的高效益項目集。我們首先提出一個稱為線上多點效益挖掘之新研究議題，其不僅考慮在交易中項目的數量和利潤，也考慮商品在多點環境中的時間週期和地點。而為了能有效處理此問題，我們提出了一個三階段的線上挖掘演算法，並開發一個有用的策略，藉由預測上邊界的效益值來減少在挖掘過程中的候選項目集數量。由於在商店中有不少商品是會多次上下架，因此我們將題目延伸以考量項目的上架資訊。我們也據以提出一個稱為線上多點架位效益挖掘的議題，不僅考慮項目的效益值，也考慮商品在多點環境中的架位時間與地點。最後，透過實驗我們將評估這兩種方法之有效性，同時亦探討在不同參數的設定之下，這兩種方法之執行效率，而結果亦顯示這兩種方法在多點環境中有良好的效能。

Utility mining, which takes the quantities and profits of items in a set of transactions into consideration, has become an emerging research topic due to its wide applications. Most of the existing studies on utility mining, however, only consider data coming from a single database. In reality, large organizations usually have a chain of stores in different locations. Besides, how to flexibly response to different users’ query conditions from multiple data sources is also a big challenge. Accordingly, in this thesis, we develop appropriate online mining approaches for finding high utility itemsets in a multi-site environment. We first introduce a new research issue called online multi-site utility mining, which considers not only the quantities and profits of items in transactions, but also the time periods and locations of the items in a multi-site environment. We then propose a Three-Phase Online Multi-site Utility mining algorithm (abbreviated as TP-OMU) to efficiently and effectively find such patterns. A useful strategy to predict the upper-bounds of utility values of items in a multi-site environment is also designed to reduce the number of candidates in the mining process. We next extend the idea above to on-shelf consideration. Items in the chain stores may be put on the shelf and taken the off shelf multiple times. We thus introduce another research issue called online multi-site on-shelf utility mining, which considers not only the utilities of items, but also the on-shelf locations and time periods of the items in a multi-site environment. Meanwhile, an efficient mining method is developed as well to cope with the problem. Finally, the experiments on synthetic datasets are conducted to show the effectiveness of the two kinds of patterns and the performance of the two proposed approaches under different parameter settings. The results demonstrate that they can perform well in a multi-site environment.

論文審定書 i
致謝 ii
摘要 iii
Abstract iv
Contents v
List of Figures vii
List of Tables viii
CHAPTER 1 Introduction 1
1.1 Motivation 1
1.2 Contributions 4
1.3 Organization of Thesis 5
CHAPTER 2 Related Works 6
2.1 Association-Rule Mining 6
2.2 Temporal Data Mining 7
2.3 Utility Mining 10
2.4 Online Data Mining 12
CHAPTER 3 Online Multi-site Utility Mining 15
3.1 Introduction 15
3.2 Problem Statement and Definitions 16
3.3 The Proposed Algorithm, TP-OMU 26
3.4 An Example of Using TP-OMU 29
CHAPTER 4 Online Multi-site On-shelf Utility Mining 36
4.1 Introduction 36
4.2 Problem Statement and Definitions 37
4.3 Proposed Mining Algorithm, TP-OMOU 44
4.4 An Example of Using TP-OMOU 47
CHAPTER 5 Experimental Evaluation 56
5.1 Introduction 56
5.2 Experimental Datasets 56
5.3 Experimental Results of TP-OMU 58
5. 3. 1 Evaluation on Effectiveness of OMHUs 58
5. 3. 2 Efficiency Evaluation 60
5. 3. 3 Comparison of TP and TP-OMU 63
5.4 Experimental Results of TP-OMOU 65
5. 4. 1 Evaluation on Effectiveness of OMOHUs 65
5. 4. 2 Efficiency Evaluation 67
5. 4. 3 Comparison of TP and TP-OMOU 69
5.5 Comparison of TP-OMU and TP-OMOU 71
CHAPTER 6 Conclusion and Future Work 73
References 75

[1]A. Adhikari, P. R. Rao, and J. Adhikari, "Mining multiple large databases," in Proceedings of the 10th International Conference on Information Technology, pp. 80-84, 2007.
[2]R. Agrawal, T. Imieliński, and A. Swami, "Mining association rule between sets of items in large databases," The ACM SIGMOD International Conference on Management of Data, pp. 207-216, 1993.
[3]R. Agrawal and R. Srikant, "Fast algorithm for mining association rules," The International Conference on Very Large Data Bases, pp. 487-499, 1994.
[4]R. Agrawal and R. Srikant, "Mining sequential patterns," The 11th International Conference on Data Engineering, pp. 3-14, 1995.
[5]R. Agrawal, R. Srikant, and Q. Vu, "Mining association rules with item constraints," The 3th International Conference on Knowledge Discovery in Databases and Data Mining, 1997.
[6]C. F. Ahmed, S. K. Tanbeer, B. S. Jeong, and Y. K. Lee, "Efficient tree structures for high utility pattern mining in incremental databases," IEEE Transactions on Knowledge and Data Engineering, Vol. 21, No. 3, pp. 1708-1721, 2009.
[7]E. B. Ahmed and M. S. Gouider, "Towards an incremental maintenance of cyclic association rules," International Journal of Database Management Systems, Vol. 2, No.4, pp. 46-62, 2010.
[8]E. B. Ahmed, A. Nabli, and F. Gargouri, "Mining cyclic association rules from multidimensional knowledge," The Sixth IEEE International Conference on Digital Information Management, pp. 12-17, 2011.
[9]C. F. Ahmed, S. K. Tanbeer, B. S. Jeong, and Y. K. Lee, "HUC-Prune: An efficient candidate pruning technique to mine high utility patterns," Applied Intelligence, Vol. 34, No. 2, pp. 181-198, 2011.
[10]J. M. Ale and G. H. Rossi, "An approach to discovering temporal association rules," The 2000 ACM Symposium on Applied Computing, pp. 294-300, 2000.
[11]C. Y. Chang, M. S. Chen, and C. H. Lee, "Mining general temporal association rules for items with different exhibition periods," The Third IEEE International Conference on Data Mining, pp. 59-66, 2002.
[12]Z. Chen, J. Luan, and C. Lu, "A fuzzy calendar-based algorithm for mining temporal association rules and its application," The Sixth International Conference on Fuzzy Systems and Knowledge Discovery, pp. 28-33, 2009.
[13]C. J. Chu, Vincent S. Tseng, and T. Liang, "An efficient algorithm for mining high utility itemsets with negative item values in large databases," Applied Mathematics and Computation, Vol. 215, No. 2, pp. 767-778, 2008.
[14]A. Erwin, R. P. Gopalan, and N. R. Achuthan, "CTU-Mine: An efficient high utility itemset mining algorithm using the pattern growth approach," The 7th IEEE International Conferences on Computer and Information Technology, pp. 71–76, 2007.
[15]C. Hidber, "Online association rule mining," in Proceedings of The ACM SIGMOD Conference, pp. 145-156, 1999.
[16]IBM Quest Data Mining Project, Quest synthetic data generation code. Available at (http://www.almaden.ibm.com/cs/quest/syndata.html).
[17]R. Jin, D. Fuhry, and A. Alali, "Cost-based query optimization for complex pattern mining on multiple databases," The 11th international conference on Extending database technology, pp. 380-391, 2008.
[18]H. Kona and S. Chakravarthy, "Partitioned approach to association rule mining over multiple," in Proceedings of The International Conference on Data Warehousing and Knowledge Discovery, pp. 320-330, 2004.
[19]G. C. Lan, T. P. Hong, and V. S. M. Tseng, "A three-scan mining algorithm for high on-shelf utility itemsets," ICIC Express Letters, Vol. 3, No. 4, pp. 1327-1332, 2009.
[20]G. C. Lan, T. P. Hong, and Vincent S. Tseng, "Discovery of high utility itemsets from on-shelf time periods of products," Expert Systems with Applications, Vol. 38, pp. 5851–5857, 2011
[21]G. C. Lan, T. P. Hong, and Vincent S. Tseng, "Reducing database scans for on-shelf utility mining," IETE TECHNICAL REVIEW, Special Issue on Advances on Soft Computing: Theory and Applications, Vol. 2, No. 2, pp. 103-112, 2011.
[22]G. C. Lan, T. P. Hong, and C. C. Wang, "Considering on-shelf situations of items in mining temporal association rules," The Information Technologies, Applications and Management Conference, 2013.
[23]G. C. Lan, T. P. Hong, C. C. Wang, and S. L. Wang, "Online multi-site on-shelf association rule mining," The 2013 National Computer Symposium, 2013.
[24]C. H. Lee, C. R. Lin, and M. S. Chen, "On mining general temporal association rules in a publication database," The 2001 IEEE International Conference on Data Mining, pp. 337-344, 2001.
[25]W. J. Lee, J. Y. Jiang, and S. J. Lee, "An efficient algorithm to discover calendar-based temporal association rules," IEEE International Conference on Systems, Man and Cybernetics, Vol. 4, pp. 3122-3127, 2004.
[26]Y. Li, P. Ning, X. S. Wang, and S. Jajodia, "Discovering calendar-based temporal association rules," Data &; Knowledge Engineering, Vol. 44, No. 2, pp. 193-218, 2003.
[27]Y. C. Li, J. S. Yeh, and C. C. Chang, "Isolated items discarding strategy for discovering high utility itemsets," Data &; Knowledge Engineering, Vol. 64, No. 1, pp. 198-217, 2008.
[28]C. W. Lin, G. C. Lan, and T. P. Hong, "An incremental mining algorithm for high utility itemsets," Expert Systems with Applications, Vol. 39, No. 8, pp. 7173-7180, 2012.
[29]Y. Lin, X. Hu, X. Li, and X. Wu, "Mining stable patterns in multiple correlated databases," Decision Support Systems, Vol. 56, pp. 202-210, 2013.
[30]Y. Liu, W. K. Liao, and A. Choudhary, "A fast high utility itemsets mining algorithm," The International Workshop on Utility-based Data Mining, pp. 90-99, 2005.
[31]A. K. Mahanta, F. A. Mazarbhuiya, and H. K. Baruah, "Finding locally and periodically frequent sets and periodic association rules," Pattern Recognition and Machine Intelligence, pp. 576-582, 2005.
[32]F. Masseglia, F. Cathala, and P. Poncelet, "The PSP approach for mining sequential patterns," The Second European Symposium on Principles of Data Mining and Knowledge Discovery, pp. 176-184, 1998.
[33]T. Mehenni and A. Moussaoui, "Data mining from multiple heterogeneous relational databases using decision tree classification," Pattern Recognition Letters, Vol. 33, No. 13, pp. 1768-1775, 2012.
[34]B. Ozden, S. Ramaswamy, and A. Silberschatz, "Cyclic association rules," The 14th International Conference, pp. 412-421, 1998.
[35]W. C. Peng and Z. X. Liao, "Mining sequential patterns across multiple sequence databases," Data &; Knowledge Engineering, Vol. 68, No. 10, pp. 1014-1033, 2009.
[36]E. Pourabbas and A. Shoshani, "Efficient estimation of joint queries from multiple olap databases," ACM Transactions on Database Systems, Vol. 32, No. 1, 2007.
[37]R. Srikant and R. Agrawal, "Mining generalized association rules," The 21st International Conference on Very Large Data Bases, pp. 407-419, 1995.
[38]R. Srikant and R. Agrawal, "Mining sequential patterns: generalizations and performance improvements," The 5th International Conference on Extending Database Technology, pp. 3-17, 1996.
[39]W. Tebourski and W. B. A. Karaa, "Cyclic association rules mining under constraints," International Journal of Computer Applications, Vol. 49, No. 20, pp. 30-37, 2012.
[40]C. Y. Wang, S. S. Tseng, and T. P. Hong, "Flexible online association rule mining based on multidimensional pattern relations," Information Science, Vol. 176, No. 12, pp. 1752-1780, 2006.
[41]X. Wu and S. Zhang, "Synthesizing high-frequency rules from different data sources," IEEE Transactions on Knowledge and Data Engineering, Vol. 15, No. 2, pp. 353-367, 2003.
[42]K. J. Yang, T. P. Hong, Y. M. Chen, and G. C. Lan, "Projection-based partial periodic pattern mining for event sequences," Expert Systems with Applications, Vol. 40, No. 10, pp. 4232-4240, 2013.
[43]K. J. Yang, T. P. Hong, Y. M. Chen, and G. C. Lan, "An efficient pruning and filtering strategy to mine partial periodic patterns from a sequence of event sets," Accepted and to Appear in Appear International Journal of Data Warehousing and Mining, 2013.
[44]H. Yao, H. J. Hamilton, and C. J. Butz, "A foundational approach to mining itemset utilities from databases," The 4th SIAM International Conference on Data Mining, pp. 482–486, 2004.
[45]H. Yao and H. J. Hamilton, "Mining itemset utilities from transaction databases," Data &; Knowledge Engineering, Vol. 59, No. 3, pp. 603–626, 2006.
[46]S. J. Yen and C. W. Cho, "An efficient approach to discovering sequential patterns in large databases," Principles of Data Mining and Knowledge Discovery, pp. 685-690, 2000.
[47]S. Zhang, X. Wu and C. Zhang, "Multi-database mining," IEEE Computational Intelligence Bulletin, Vol. 2, No. 1, pp. 5–13, 2003.
[48]S. Zhang, X. You, Z. Jin, and X. Wu, "Mining globally interesting patterns from multiple databases using kernel estimation," Expert Systems with Applications, Vol. 36, No. 8, pp. 10863-10869, 2009.
[49]X. Zhu and X. Wu, "Discovering relational patterns across multiple databases," International Conference on Data Engineering, pp. 726-735, 2007.