臺灣博碩士論文加值系統

近年來，效益探勘已成為一個有趣且重要的研究問題。與關聯規則探勘相比，它還考慮了其他的因素，例如使用市場數據庫中每種產品的利潤和銷售量來計算高效益值，若其值滿足給定最小閾值，則稱為高效益項目集。然而，用戶不容易理解高效益項目集中的數量信息。此外，產品也可能有不同的權重考量因素。因此，在本文中，我們擴展了黃等人的模糊效益探勘方法來處理不同權重的項目。我們認為產品可能具有不同的權重/重要性。由於模糊加權效益探勘問題不能保持向下封閉性，因此我們開發了一種上限模糊加權效益模型，以避免資料在資料探勘中遺失。為了解決這個問題，我們設計了一種稱為模糊加權效益探勘的高效算法來找出高模糊加權效益項目集。我們還設計了三種策略，將項目集中的不同權重與兩個以上的項目組合，分別用於樂觀，悲觀和中立的方式。最後，進行了一些實驗來驗證所提出的方法和策略的性能。

Utility mining has emerged as an interesting and important research issue in recent years. Compared with association-rule mining, it considers additional factors, such as the profit and the quantity sold of each product in a market database for calculating high utility values, which were then used to discover high utility itemsets satisfying a given minimum threshold. However, high utility itemsets are not easily comprehended by users to know the quantitative information. Besides, items may have different weight consideration. In this paper, we thus extend Huang et al.’s fuzzy utility mining approach to handle different weights of items. consider that items may have different weight/significance. Because, the fuzzy weighted utility mining problem cannot hold the downward-closure property, we thus develop an upper-bound fuzzy weighted utility model to avoid information loss in data mining. To cope with this issue, an efficient algorithm called fuzzy weighted utility mining is designed to discover high fuzzy weighted utility itemsets. We also design three strategies of combining different weights in an itemset with more than two items, respectively for optimistic, pessimistic and neutral ways. Finally, some experiments are made to verify the performance of the proposed approach and strategies.

論文審定書----------------------------------------------i
致謝---------------------------------------------------ii
摘要--------------------------------------------------- iii
Abstract---------------------------------------------------iv
Content---------------------------------------------------vi
List of Figures---------------------------------------------------viii
List of Tables---------------------------------------------------x
Chapter 1---------------------------------------------------1
Introduction------------------------------------------------1
1.1 Background and Motivation---------------------------1
1.2 Thesis Organization---------------------------------4
Chapter 2---------------------------------------------------5
Related Works-----------------------------------------------5
2.1 Fuzzy Association-rule Mining-----------------------5
2.2 Fuzzy Utility Mining--------------------------------6
2.3 Weighted Association-rule Mining--------------------8
Chapter 3---------------------------------------------------11
3.1 Problem Statement-----------------------------------11
Chapter 4---------------------------------------------------18
The Proposed FWUMmax Algorithm------------------------------18
4.1 The Proposed Upper-Bound Model For Keeping the Downward-Closure Property----------------------------------------------------18
4.2 The Theorem For Keeping the Downward-Closure Property------------------------------------------------------------------------------20
4.3 The Proposed Mining Approach------------------------22
4.4 An Example For the Proposed FWUMmax Approach--------26
Chapter 5---------------------------------------------------39
5.1 Other Approach--------------------------------------39
Chapter 6---------------------------------------------------40
Experiments and Results-------------------------------------40
6.1 Varying Threshold Values----------------------------40
6.2 Changing T Parameters-------------------------------41
6.3 Changing N Parameters-------------------------------43
6.4 Changing D Parameters-------------------------------45
6.5 Real Dataset----------------------------------------47
Chapter 7---------------------------------------------------49
Conclusions and Future Works--------------------------------49
References--------------------------------------------------50

[1] R. Agrawal and R. Srikant, “Fast algorithms for mining association rules,” The 20th International Conference on Very Large Data Bases, Vol. 1215, pp. 487-499, 1994.
[2] H. Bui, B. Vo, and H. Nguyen, “WUN-Miner: a new method for mining frequent weighted utility itemsets,” The 2016 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pp. 1365-1370, 2016.
[3] C. H. Cai, A. W. C. Fu, C. H. Cheng, and W. W. Kwong, “Mining association rules with weighted items,” The International Database Engineering and Applications Symposium (IDEAS), pp. 68-77, 1998.
[4] R. Chan, Q. Yang, and Y.D. Shen, “Mining high utility itemsets,” The Third IEEE International Conference on Data Mining, pp. 19-26, 2003.
[5] C. J. Chu, V. S. Tseng, and T. Liang, “Mining temporal rare utility itemsets in large databases using relative utility thresholds,” International Journal of Innovative Computing, Information and Control, Vol. 4, No. 11, pp. 2775-2792, 2008.
[6] Z. H. Dong, “An efficient structure for fast mining high utility itemsets,” Applied Intelligence, Vol. 48, Issue 9, pp. 3161-3177, 2018.
[7] A. Erwin, R. P. Gopalan, and N. R. Achuthan, “A bottom-up projection based algorithm for mining high utility itemsets,” The 2nd international workshop on Integrating artificial intelligence and data mining, pp. 3-11, 2007.
[8] 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.
[9] T. P. Hong, C. S. Kuo, and S. C. Chi, “Trade-off between computation time and number of rules for fuzzy mining from quantitative data,” International Journal of Uncertainty Fuzziness and Knowledge-Based Systems, Vol. 9, No. 5, pp. 587-604, 2001.
[10] T. P. Hong, K. Y. Lin, and B. C. Chien, “Mining fuzzy multiple-level association rules from quantitative data,” Applied Intelligence, Vol. 18, Issue 1, pp. 79-90, 2003.
[11] T. P. Hong and Y. C. Lee, “An overview of mining fuzzy association rules,” The Fuzzy Sets and Their Extensions: Representation, Aggregation and Models, pp. 397-410, 2008.
[12] IBM Quest Data Mining Project, “Quest synthetic data generation code,” http://www.almaden.ibm.com/cs/quest/syndata.html, 1994.
[13] C. M. Kuok, A. W. C. Fu, and M. H. Wong, “Mining fuzzy association rules in databases,” The ACM SIGMOD Record, Vol. 27, Issue 1, pp. 41-46, 1998.
[14] M. S. Khan, M. Muyeba, and F. Coenen, “A weighted utility framework for mining association rules,” The Second UKSIM European Symposium on Computer Modeling and Simulation, pp. 87-92, 2008.
[15] S. Krishnamoorthy, “HMiner: efficiently mining high utility itemsets,” Expert Systems with Applications, Vol. 90, pp. 168-183, 2017.
[16] G. C. Lan, T. P. Hong, Y. H. Lin, and S. L. Wang, “Fuzzy utility mining with upper-bound measure,” Applied Soft Computing, Vol. 30, pp. 767-777, 2015.
[17] J. C. W. Lin, T. P. Hong, and W. H. Lu, “Linguistic data mining with fuzzy FP-trees,” Expert Systems with Applications, Vol. 37, Issue 6, pp. 4560-4567, 2010.
[18] J. C. W. Lin, W. Gan, P. Fournier-Viger, and T. P. Hong, “RWFIM: recent weighted-frequent itemsets mining,” Engineering Applications of Artificial Intelligence, Vol. 45, pp. 18-32, 2015.
[19] J. C. W. Lin, W. Gan, P. Fournier-Viger, T. P. Hong, and Vincent S. Tseng, “Weighted frequent itemset mining over uncertain databases,” Applied Intelligence, Vol. 44, Issue 1, pp 232-250, 2016.
[20] J. C. W. Lin, W. Gan, P. Fournier-Viger, T. P. Hong, and H. C. Chao, “Mining weighted frequent itemsets without candidate generation in uncertain databases,” International Journal of Information Technology & Decision Making, Vol. 16, No. 6, pp. 1549-1579, 2017.
[21] Y. Liu, W. K. Liao, and A. Choudhary, “A fast high utility itemsets mining algorithm,” The Proceedings of the 1st international workshop on Utility-based data mining, pp. 90-99, 2005.
[22] S. Lu, H. Hu, and F. Li, “Mining weighted association rules,” The Intelligent Data Analysis, Vol. 5, No. 3, pp. 211-225, 2001.
[23] D. L. Olson and Y. H. Li, “Mining fuzzy weighted association rules,” The 40th Hawaii International Conference on System Sciences, pp. 53-62, 2007.
[24] K. Singh, H. K. Shakya, A. Singh, and B. Biswas, “Mining of high-utility itemsets with negative utility,” Expert Systems, Vol. 35, Issue 6, 2018.
[25] K. Singh, S. S. Singh, A. Kumar, and B. Biswas, “TKEH: an efficient algorithm for mining top-k high utility itemsets,” Applied Intelligence, Vol. 49, Issue 3, pp. 1078-1097, 2019.
[26] R. Srikant and R. Agrawal, “Mining quantitative association rules in large relational tables,” The Proceedings of the ACM SIGMOD international conference on Management of data, Vol. 25, Issue 2, pp. 1-12, 1996.
[27] V. S. Tseng, C. J. Chu, and T. Liang, “Efficient mining of temporal high utility itemsets from data streams,” The ACM KDD Workshop on Utility-Based Data Mining, Vol. 18, 2006.
[28] B. Vo, B. Le, and J. J. Jung, “A tree-based approach for mining frequent weighted utility itemsets,” The International Conference on Computational Collective Intelligence, pp.114-123, 2012.
[29] B. Y. Wang and S. M. Zhang, “A mining algorithm for fuzzy weighted association rules,” The Second International Conference on Machine Learning and Cybernetics, Vol. 4, No. 3, pp. 2495-2499, 2003.
[30] C. M. Wang, S. H. Chen, and Y. F. Huang, “A fuzzy approach for mining high utility quantitative itemsets,” The IEEE International Conference on Fuzzy Systems, pp. 1909-1913, 2009.
[31] K. Wang, Y. He, and J. Han, “Pushing support constraints into association rules mining,” The IEEE Transactions on Knowledge and Data Engineering, Vol. 15, Issue 3, pp. 642-658, 2003.
[32] H. Yao and H. J. Hamilton, “Mining itemset utilities from transaction databases,” The Data & Knowledge Engineering, Vol. 59, Issue 3, pp. 603-626, 2006.
[33] 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.
[34] G. Yu, K. Li, and S. Shao, “Mining high utility itemsets in large high dimensional data,” The International Workshop on Knowledge Discovery and Data Mining (WKDD), pp. 17-20, 2008.