臺灣博碩士論文加值系統

前K項高效益項目集探勘的目的，是在交易資料庫中同時考慮物品的價值與數量下，找出前K個最有效益的項目集。先前的高效益項目集探勘，必須要先設定最低效益閥值才能進行。這也就意味著，一個完美的閥值可以得到完美的結果，但是只要最低效益閥值設得不好，使用者就無法得到滿意的結果。對使用者而言，要找出有興趣的高效益項目集，指定K值比指定閥值更容易且結果更有具體意義。
在本論文中，我們提出一個探勘前K項高效益項目集的方法，稱為KHUI。KHUI採用了垂直表示法來儲存所有項目在交易資料庫中的效益資訊，僅需掃瞄資料庫兩次即可完成探勘。我們使用了兩個提升閥值的方法與提出三個削減搜尋空間的策略。兩個提昇閥值的方法分別是在第一次掃描與第二次掃描的時候完成，分別是用長度為一以及長度為二的項目集真實效益值來進行閥值的提升。三個削減搜尋空間的策略則是使用長度為二的項目集的交易權重，利用垂直表示的資料結構中來進行削減、以及利用項目集本身的效益值以及殘餘效益值的總和來進行削減、還有透過估計的方式來計算效益值。我們採用一般高效益項目集探勘研究中常用的真實資料集進行實驗，透過與著名的HUI-Miner方法比較執行時間。實驗結果顯示KHUI能快速地提升閥值以找出前K名高效益項目集，比起閥值最佳化的HUI-Miner平均快3.5倍。

The goal of top-k high utility itemset mining is discovering all the itemsets whose utility value is at least the K largest, by considering both quantities and profits of items in a transactional database. Previous methods of high utility itemset mining need to specify a minimum threshold first to discover the interesting patterns. Therefore, an inappropriate threshold can never produce a satisfactory result for the user so the mining is a lengthy process. In order to discover the interesting itemsets of high utility, specifying the K value is easier and more meaningful than specifying the minimum threshold because the former may generate a manageable result for the user.
In this thesis, we propose an algorithm called KHUI to discover the top-k high utility itemsets. KHUI adopts vertical representation of itemsets as the utility-list and generates the utility information of itemsets within two scans of the database. KHUI uses two strategies to swiftly raise the threshold and three pruning strategies to reduce the search space of patterns during the mining. The 1U and 2U strategies update the minimum utility value with respect to the k-th itemsets found in-progress. The SIR strategy then computes the sum of item utility and remaining utility so that impossible patterns are pruned first. The AU strategy approximates the utility by considering possible extensions of an itemset to prune the unqualified patterns. The CTWU strategy stores the transaction-weighted-utility regarding two-itemsets in the utility-list to eagerly and effectively prune the search space. In the experiments using two real datasets, we have compared KHUI with the state-of-art utility mining algorithm HUI-Miner. The experimental results show that KHUI increases the threshold rapidly and is 3.5 times faster in average than the threshold-optimized HUI-Miner.

誌謝 i
摘要 ii
Abstract iii
Table of Contents v
List of Figures vii
List of Tables viii
Chapter 1 Introduction 1
1.1 Background 1
1.2 Motivation 3
1.3 Research Objective 4
1.4 Problem Definition 4
1.5 Organization of This Thesis 7
Chapter 2 Related Work 8
2.1 Frequent Itemset Mining 8
2.1.1 Apriori Algorithm 8
2.1.2 FP-Growth Algorithm 9
2.2 High Utility Mining 10
2.2.1 UMining and UMining_H Algorithm 10
2.2.2 Two-Phase Algorithm 11
2.2.3 HUI-Miner Algorithm 12
2.2.4 FHM Algorithm 14
2.3 Mining Top-K High Utility Itemset Algorithms 15
2.3.1 TKU Algorithm 15
2.3.2 TopK-SW Algorithm 15
Chapter 3 An Efficient Algorithm for Mining Top-K High Utility Itemsets 16
3.1 Overview of the Proposed Algorithm 16
3.2 Definitions 16
3.3 Scan Phase 17
3.3.1 Increasing Threshold Technique: 1-itemset Utilities(1U) 17
3.3.2 Increasing Threshold Technique 2: Partial 2-itemset Utilities(P2U) 19
3.4 Mining Phase: Baseline 21
3.5 Mining Phase: Pruning Strategies 22
3.5.1 Pruning Strategy 1: SIR (Sum of itemset utility and remaining utility) 24
3.5.2 Pruning Strategy 2: AU (Approximation of itemset utility) 26
3.5.3 Pruning Strategy 3: CTWU (Corresponding 2-itemset TWU of 1-itemset) 27
Chapter 4 Experimental Results 29
4.1 Execution Time Evaluation 29
4.2 Increasing Threshold 30
4.3 Evaluation of search space reduction 35
4.4 Evaluation of Memory Usage 35
Chapter 5 Conclusions 40
5.1 Contributions 40
5.2 Future Work 40
References 41

[1]R. Agrawal and R. Srikant, "Fast Algorithms for Mining Association Rules," Proceedings of 20th International Conference on Very Large Databases, , pp. 487-499, September 12-15, 1994, Santiago, Chile.
[2]R. Argrawl, T. Imielinskl, and T. Swami, "Mining Association Rules between Sets of Items in Large Databases," Proceedings of the 1993 ACM SIGMOD International Conference in Management of Data, pp. 207-216, May 26-28, 1993, Washington, D.C, USA.
[3]P. Fournier-Viger. SPMF: A Java Open-Source Data Mining Library. URL: http://www.philippe-fournier-viger.com/spmf/, June 2015.
[4]P. Fournier-Viger, C. -W. Wu, S. Zida, and V. S. Tseng, "FHM: Faster High utility Itemset Mining Using Estimated Utility Co-occurrence Pruning," Proceedings of Foundations of Intelligent Systems - 21st International Symposium, pp. 83-92, June 25-27, 2014, Roskilde, Denmark.
[5]J. Han, Y. Pei, Y. Yin, and R. Mao, "Mining frequent patterns without candidate generation: A Frequent-Pattern Tree Approach," Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, Vol. 8, pp. 1-12, May 16-18, 2000, Dallas, Texas, USA.
[6]B. Le, H. Nguyen, T. A. Cao, and B. Vo, "A Novel Algorithm for Mining High Utility Itemsets," First Asian Conference on Intelligent Information and Database Systems, pp. 13-17, April 1-3, 2009, Quang binh, Vietnam.
[7]Y. Liu, W. -K. Liao, and A. N. Choudhary, "A Fast High Utility Itemsets Mining Algorithm," Proceedings of Utility-Based Data Mining Workshop, pp. 90-99, 2005.
[8]Y. Liu, W. -K. Liao, and A. N. Choudhary, "A Two-Phase Algorithm for Fast Discovery of High Utility Itemsets," Proceedings of Advances in Knowledge Discovery and Data Mining, 9th Pacific-Asia Conference, pp. 689-695, May 18-20, 2005, Hanoi, Vietnam.
[9]M. Liu and J. Qu, "Mining High Utility Itemsets without Candidate Generation," 21st ACM International Conference on Information and Knowledge Management, pp. 55–64, October 29 - November 2, 2012, Maui, HI, USA.
[10]Y. -C. Li, J. -S. Yeh, and C. -C. Chang, "Isolated Items Discarding Strategy for Discovering High Utility Itemsets," Data and Knowledge Engineering, Vol. 64, No. 1, pp. 198-217, January 2008.
[11]T. Lu, Y. Liu, and L. Wang, "An Algorithm of Top-k High Utility Itemsets Mining over Data Stream," Journal of Software, Vol. 9, No. 9, pp. 2342-2347, 2014.
[12]J. Pisharath, Y. Liu, J. Parhi, and W. -K. Liao. U-MineBench version 2.0 Source Code and Datasets. URL: http://cucis.ece.northwestern.edu/projects/DMS/MineBench.html, July 2015.
[13]V. S. Tseng, B. -E. Shie, C. -W. We, and P. S. Yu, "Efficient Algorithms for Mining High Utility Itemsets from Transactional Databases," IEEE Transactions on Knowledge and Data Engineering, Vol. 25, No. 8, pp. 1772-1786, August, 2013.
[14]V. S. Tseng, C. -W. Wu, B. -E. Shie, and P. S. Yu, "UP-Growth: An Efficient Algorithm for High Utility Itemset Mining," Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 253-262, July 25-28, Washington, DC, USA.
[15]C. -W. Wu, P. Fournier-Viger, P. S. Yu, and V. S. Tseng, "Efficient Mining of a Concise and Lossless Representation of High Utility Itemsets," Proceedings of 11th IEEE International Conference on Data Mining, ICDM 2011, pp. 824-833, December 11-14, 2011, Vancouver, BC, Canada.
[16]C. -W. Wu, B. -E. Shie, V. S. Tseng, and P. S. Yu, "Mining Top-K high utility itemsets," The 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 78-86, August 12-16, Beijing, China.
[17]H. Yao and H. J. Hamilton, "Mining itemset utilities from transaction databases," Data and Knowledge Engineering, Vol. 59, No. 3, pp. 603-626, December, 2006.
[18]H. Yao, H. J. Hamilton, and C. J. Butz, "A Foundational Approach to Mining Itemset Utilities from Databases," Proceedings of the Fourth SIAM International Conference on Data Mining, pp. 482-486, April 22-24, 2004, Lake Buena Vista, Florida, USA.