臺灣博碩士論文加值系統

探勘頻繁項目集是從交易資料中找出頻繁被購買的商品，企業可組合這些商品來增加客戶的購買率，但未必可使公司獲得較大的利益。探勘高效益項目集（Mining High Utility）可找出讓企業獲利較大的商品組合，但是使用者必須自行設定高效益的門檻來找出高效益項目集。若門檻值設得太高，會找不出任何的高效益項目集；若門檻值設得太低，會產生出巨量且無用的項目集，導致執行時間和占用記憶體的情況大幅增加。為了解決設定門檻值的問題，我們可以找出前k高效益項目集（Mining Top-k High Utility Itemset）。先前探勘前k高效益項目集的方法都致力於盡可能提升效益門檻值，以減少項目組合的個數，但是必須使用許多方法才能有效提升門檻值。所以我們提出了一個kPU演算法，重新訂製了新定義使得更貼近項目真實的效益值，並且根據此定義提供了一個新的提升門檻方法，提升門檻值的效果可逼近其他演算法中兩個方法，來有效的節省執行時間。

High utility mining is a novel issue in data mining area. A high utility itemset is an itemset which satisfies a user-specified utility threshold. However, it is difficult to specify the utility threshold: if the utility threshold is set to be too high, there is not any high utility itemsets can be found; If the utility threshold is set to be too low, there will be a large number of high utility itemsets ca be generated, leading to increase execution time and memory space. For this problem, some researchers proposed top-k high utility itemset mining, which is to find the first k itemsets with largest utilitities. In this paper, we propose a new algorithm kPU-Algorithm for mining top-k high utility itemsets. The algorithm use a new definition PU replacing TWU. PU greatly reduce the estimate and decrease the search space. kPU-Algorithm discovers high utility itemsets scanning twice the dataset. Furthermore, it employs new one strategy named RDIU to raise the minimum utility threshold effectively, and new one structure named Transaction-List to raise the efficacy mining the high utility itemsets.

摘要 i
Abstract ii
致謝 iii
目錄 iv
表目錄 v
圖目錄 vi
第1章 緒論 1
第2章 相關研究 5
1. 高效益項目集探勘(High Utility Itemset Mining) 5
2. 前k高效益項目集探勘(Top-k High Utility Itemset Mining) 6
第3章 研究方法 8
第4章 實驗結果 17
第5章 結論 26
參考文獻 27

[1]R. Agrawal, and R. Srikant, “Fast Algorithms for Mining Association Rules,” Proc. of 20th International Conference on Very Large Databases, Santiago, Chile, September 1994, pp. 487-499.
[2]Q.H. Duong, B. Liao, P. Fournier-Viger, T.L. Dam, “An efficient algorithm for mining the top-k high utility itemsets, using novel threshold raising and pruning strategies,” Knowledge-Based Systems 104(2016) 106-122, April
[3]P. Fournier-Viger , C. Wu , S. Zida , V.S. Tseng , FHM: Faster high-utility itemset mining using estimated utility co-occurrence pruning, in: Foundations of In- telligent Systems - 21st International Symposium, ISMIS 2014, Roskilde, Den- mark, June 25–27, 2014. Proceedings, 2014, pp. 83–92 .
[4]J. Han, J. Pei, and Y. Yin, “Mining frequent patterns without candidate　generation,” in Proc. ACM SIGMOD Int. Conf. Manag. Data,2000, pp. 1–12.
[5]M. Liu and J. Qu, “Mining high utility itemsets without candidate generation,” in Proc. ACM Int. Conf. Inf. Knowl. Manag., 2012, pp. 55–64.
[6]C.F. Lee and T.H. Shen. An FP_split method for fast association rules mining.In: IEEE pp. 459-463. 2005.
[7]Y. Liu, W. Liao, A. Choudhary: A fast high utility itemsets mining algorithm. In:　Proc. of the 1st Int. Workshop on Utility-Based Data Mining. pp. 90–99 (August 2005)
[8]H. Ryang and U. Yun, “Top-k high utility pattern mining with effective threshold raising Strategies,” Knowl.-Based Syst., vol. 76, pp. 109–126, 2015.
[9]V. S. Tseng, C. Wu, B. Shie, and P. S. Yu, “UP-Growth: An efficient algorithm for high utility itemset mining,” in Proc. ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining, 2010, pp. 253–262.
[10]V.S. Tseng , C.W. Wu , P. Fournier-Viger , P.S. Yu , Efficient algorithms for mining top-k high utility itemsets, IEEE Trans. Knowl. and Data Eng., 28 (1) (2015) 54–67 .
[11]S.J. Yen, C.C. Chen, and Y.S. Lee, "A fast algorithm for mining high utility itemsets, " Proceedings of the 15th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, pp. 171-182, 2011.
[12]Frequent itemset mining implementations repository, 2012, URL http://fimi.cs.helsinnki.fi