臺灣博碩士論文加值系統

關聯規則探勘在現今是一種重要的資料分析技術，最聞名遐邇的例子就是購物籃分析，賣場或者零售商可以透過商品組合而得到更好的銷售方式，例如啤酒與尿布同時推廣，能為賣場帶來更大的收益。然而，在某些情況下，用戶可能會存在某些事件或者項目的發生，像是醫生懷疑病患的症狀有哪些，因此，這些不確定性的資料也是相當重要。在大數據環境下，資料量是不停的新增，探勘頻繁項目已成為大數據的重要議題。若是遇到新增資料的情況下，只能重新建立模型，則會讓效率大幅下降，為了解決新增資料的問題，需要更多關於增量式資料的演算法。現今，演算法解決不確定性資料的問題的演算法CUF-Growth及PUF-Growth，這兩種演算法改善了傳統的UF-Growth在機率不同時會造成節點分支的問題。本研究中，我們提出了基於CUF-Growth及PUF-Growth的增量式關聯演算法，解決不確定性資料更新的問題。我們提出的方法與傳統演算法所重新建立過後的樹狀結構，擁有相同的結果，減少新增資料時反覆重新建樹的複雜度。實驗結果顯示我們提出的演算法與傳統UF-Growth、CUF-Growth以及PFU-Growth相比，可以有效降低了執行時間，達到更有效率的頻繁項目探勘。

Association rule analysis is an important topic in data mining. Basket analysis is one of the most well-known application. Stores or retailers can get better sales through the analysis of goods combination. For example, placing beer and diapers at the same place can bring greater sales for the stores. However, due to the rapid increase in the amount of data in this big data era, how to mine frequent patterns from big data has become an important issue. Many approaches were proposed to solve the incremental problem of certain data, but these approaches did not address uncertain data. The CUF-Growth and PUF-Growth algorithm preventing branches improves the performance of the traditional UF-Growth. In this paper, we proposed an incremental association algorithm based on CUF-Growth and PUF-Growth to solve the problem of incremental updating of uncertain frequent items. This method retains the advantages of the original CUF-Growth and PUF-Growth, and significantly reduces the complexity of adding new transactions. The experimental results show that the proposed method reduces the execution time and perform better than the traditional UF-Growth, CUF-Growth and PUF-Growth.

第一章 緒論 1
第一節 研究背景 1
第二節 研究動機與目的 2
第二章 文獻探討 4
第一節 關聯演算法研究探討 4
一、 Apriori演算法 4
二、 FP-Growth演算法 6
三、 UF-Growth演算法 9
四、 CUF-Growth演算法 10
五、 PUF-Growth演算法 13
第二節 增量關聯演算法(Incremental Association Rule Mining) 15
一、Incremental Algorithm For Frequent Pattern Mining Based On Bit-Sequence(IFPM-BS)演算法 16
二、 Rapid Update In Frequent Pattern(RUFP)演算法 17
三、 Quick Update Method(QUM)演算法 19
第三章 研究方法 28
第一節 問題定義 28
第二節 方法描述 32
第三節 範例演練 35
一、 CUF-FU快速新增 35
二、 PUF-FU快速新增 40
第四章 實驗結果 45
第一節 實驗環境介紹 45
第二節 執行效率 47
第三節 應用範圍 55
第五章 結論及未來展望 59
參考文獻 60

[1] E. Dumbill, "A Revolution That Will Transform How We Live, Work, and Think: An Interview with the Authors of Big Data," Big Data, vol. 1, no. 2, pp. 73-77, 2013.
[2] L. Hetland, "Listening to music enhances spatial-temporal reasoning: Evidence for the" Mozart Effect"," Journal of Aesthetic Education, vol. 34, no. 3/4, pp. 105-148, 2000.
[3] E. Baralis, L. Cagliero, T. Cerquitelli, and P. Garza, "Generalized association rule mining with constraints," Information Sciences, vol. 194, pp. 68-84, 2012.
[4] J. S. Park, M.-S. Chen, and P. S. Yu, "Using a hash-based method with transaction trimming for mining association rules," IEEE transactions on knowledge and data engineering, vol. 9, no. 5, pp. 813-825, 1997.
[5] T. Bernecker, H.-P. Kriegel, M. Renz, F. Verhein, and A. Zuefle, "Probabilistic frequent itemset mining in uncertain databases," in Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, pp. 119-128, 2009.
[6] T. Calders, C. Garboni, and B. Goethals, "Approximation of frequentness probability of itemsets in uncertain data," in 10th International Conference on Data Mining (ICDM), IEEE, pp. 749-754, 2010.
[7] T. Calders, C. Garboni, and B. Goethals, "Efficient pattern mining of uncertain data with sampling," Advances in Knowledge Discovery and Data Mining, pp. 480-487, 2010.
[8] C. K.-S. Leung and B. Hao, "Mining of frequent itemsets from streams of uncertain data," in 25th International Conference on Data Engineering, IEEE, pp. 1663-1670, 2009.
[9] C. K.-S. Leung and S. K. Tanbeer, "Fast tree-based mining of frequent itemsets from uncertain data," in International Conference on Database Systems for Advanced Applications, Springer, pp. 272-287, 2012.
[10] Q. Zhang, F. Li, and K. Yi, "Finding frequent items in probabilistic data," in Proceedings of the 2008 ACM SIGMOD international conference on Management of data, ACM, pp. 819-832, 2008.
[11] C.-K. Chui, B. Kao, and E. Hung, "Mining frequent itemsets from uncertain data," Advances in knowledge discovery and data mining, pp. 47-58, 2007.
[12] C. Leung and F. Jiang, "Frequent pattern mining from time-fading streams of uncertain data," Data Warehousing and Knowledge Discovery, pp. 252-264, 2011.

[13] C.-W. Lin, T.-P. Hong, and W.-H. Lu, "A new tree structure for mining frequent itemsets from uncertain databases," in Nat’l Conf. on Fuzzy Theory and its App, pp. 575-579, 2009.
[14] R. Agrawal, T. Imieliński, and A. Swami, "Mining association rules between sets of items in large databases," in Acm sigmod record, vol. 22, no. 2, ACM, pp. 207-216, 1993.
[15] R. Agrawal and R. Srikant, "Fast algorithms for mining association rules," in Proc. 20th int. conf. very large data bases, VLDB, vol. 1215, pp. 487-499, 1994.
[16] J. Han, J. Pei, Y. Yin, and R. Mao, "Mining frequent patterns without candidate generation: A frequent-pattern tree approach," Data mining and knowledge discovery, vol. 8, no. 1, pp. 53-87, 2004.
[17] H.-Y. Chang, J.-C. Lin, M.-L. Cheng, and S.-C. Huang, "A Novel Incremental Data Mining Algorithm Based on FP-growth for Big Data," in International Conference on Networking and Network Applications (NaNA), IEEE, pp. 375-378, 2016.
[18] J. Guo and Y.-g. Ren, "Research on improved a priori algorithm based on coding and mapreduce," in Web Information System and Application Conference (WISA), 2013 10th, IEEE, pp. 294-299, 2013.
[19] H. Toivonen, "Sampling large databases for association rules," in VLDB, vol. 96, pp. 134-145, 1996.
[20] J. Pei and J. Han, "Can we push more constraints into frequent pattern mining?," in Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, pp. 350-354, 2000.
[21] J. Han and J. Pei, "Mining frequent patterns by pattern-growth: methodology and implications," ACM SIGKDD explorations newsletter, vol. 2, no. 2, pp. 14-20, 2000.
[22] J. Han et al., "Prefixspan: Mining sequential patterns efficiently by prefix-projected pattern growth," in proceedings of the 17th international conference on data engineering, pp. 215-224, 2001.
[23] C. K.-S. Leung, M. A. F. Mateo, and D. A. Brajczuk, "A tree-based approach for frequent pattern mining from uncertain data," in Pacific-Asia Conference on Knowledge Discovery and Data Mining, Springer, pp. 653-661, 2008.
[24] C. K.-S. Leung and S. K. Tanbeer, "PUF-tree: a compact tree structure for frequent pattern mining of uncertain data," in Pacific-Asia Conference on Knowledge Discovery and Data Mining, Springer, pp. 13-25, 2013.
[25] D. W. Cheung, J. Han, V. T. Ng, and C. Wong, "Maintenance of discovered association rules in large databases: An incremental updating technique," in Proceedings of the Twelfth International Conference on Data Engineering, IEEE, pp. 106-114, 1996.
[26] W. Dong, J. Yi, H. He, and J. Ren, "An incremental algorithm for frequent pattern mining based on bit-sequence," I/ACT: International Journal of Advancements in Computing Technology, vol. 3, no. 9, p. 1313, 2011.
[27] A. Mundra, P. Tomar, and D. Kulhare, "Rapid Update in Frequent Pattern form Large Dynamic Database to Increase Scalability," International Journal of Soft Computing and Engineering (IJSCE) ISSN, pp. 2231-2307.
[28] H.-W. Hu, H.-C. Chang, and W.-S. Lin, "An optimized frequent pattern mining algorithm with multiple minimum supports," in International Conference on Big Data (Big Data), IEEE, pp. 1734-1741, 2016.
[29] J.-C. Lin, "A Rapid Incremental Frequent Pattern Mining Algorithm," Master Thesis, MIS, National Chiayi University, 2016.