臺灣博碩士論文加值系統

本論文以刪除的技巧來進行概括性的資料探勘。在此論文中我們假設一個大型資料庫包含有很多的交易,而每一筆交易為一些項目的集合所組成,我們稱之為項目集,且有一個以項目來分類的階層式分類樹,我們就是要發現在階層式分類樹中各階層項目之間的關係,我們並假設原始頻繁的項目集及關連性規則在這之前已經被產生出來,我們的首要挑戰是如何在加入分類樹後避免重新掃描資料庫及利用現有的關連規則及頻繁的項目集來產生新的概括性關連規則,在我們所提出的GMAR及GMFI演算法,使用聯合的方法及刪除技巧來產生新的概括性關連性規則。經由我們數種充份理解的實驗,我們發現我們的演算法比BASIC及Cumulate好上很多倍,因為它們產生較少的候選項目,且GMAR演算法有時會由最小信任度參數來刪除很多不相關的規則。

The goal of the thesis is to mine generalized association rules using pruning techniques. Given a large transaction database and a hierarchical taxonomy tree of the items, we try to find the association rules between the items at different levels in the taxonomy tree under the assumption that original frequent itemsets and association rules have already been generated beforehand. The primary challenge of designing an efficient mining algorithm is how to make use of the original frequent itemsets and association rules to directly generate new generalized association rules, rather than rescanning the database. In the proposed algorithms GMAR and GMFI, we use join methods and/or pruning techniques to generate new generalized association rules. Through several comprehensive experiments, we find that both algorithms are much better than BASIC and Cumulate algorithms, since they generate fewer candidate itemsets, and furthermore the GMAR algorithm prunes a large amount of irrelevant rules based on the minimum confidence.

一、緒論 ----------------------------------------------------1
二、問題描述 ------------------------------------------------3
三、探勘演算法-----------------------------------------------5
3.1 探勘演算法的處理流程--------------------------------5
3.2 垂直交易向量表格------------------------------------6
3.3 建立最大項目集------------------------------------- 6
3.4 計算非樹葉項目的支持度------------------------------9
3.5 建立關連圖-----------------------------------------10
3.6 刪除技巧-------------------------------------------11
3.7 GMFI及GMAR演算法-----------------------------------12
四、效能評估------------------------------------------------20
4.1 模擬模組--------------------------------------------20
4.2實驗結果---------------------------------------------20
五、結論----------------------------------------------------26
參考文獻------------------------------------------------27

[1] R. Agrawal, T. Imielinski, and A. Swami, “Mining association rules between sets of items in large databases,” Proc. ACM International Conference on Management of Data, 1993, pp. 207-216.
[2] R. Agrawal and R. Srikant, “Fast algorithms for mining association rules,” Proc. 20th International Conference on Very Large Data Bases, 1994, pp. 487-499.
[3] Yong-Jian Fu, “Data mining,” IEEE Potentials, Vol. 16, No. 4, 1997, pp. 18-20.
[4] Jia-Wei Han and Yong-Jian Fu, “Mining multiple-level association rules in large databases,” IEEE Transactions on Knowledge and Data Engineering, Vol. 11, No. 5, 1999, pp. 798-805.
[5] Jia-Wei Han and Micheline Kamber, Data Mining: Concepts and Techniques, Morgan Kaufmann Publishers, 2001.
[6] Jia-Wei Han, Jian Pei, and Yi-Wen Yin, “Mining frequent patterns without candidate generation,” Proc. ACM International Conference on Management of Data, 2000, pp. 1-12.
[7] Mon-Fong Jiang, Shian-Shyong Tseng, and Shan-Yi Lia, “Data types generalization for data mining algorithms,” Proc. IEEE International Conference on Systems, Man, and Cybernetics, 1999, pp. 928-933.
[8] Bing Liu, Wynne Hsu, and Yi-Ming Ma, “Mining association rules with multiple minimum supports,” Proc. 5th ACM International Conference on Knowledge Discovery and Data Mining, 1999, pp. 337-341.
[9] J. S. Park, M. S. Chen, and P. S. Yu, “An effective hash-based algorithm for mining association rules,” Proc. ACM International Conference on Management of Data, 1995, pp. 175-186.
[10] A. Savasere, E. Omiecinski, and S. Navathe, “An efficient algorithm for mining association rules in large databases,” Proc. 21st International Conference on Very Large Data Bases, 1995, pp. 432-443.
[11] Pradeep Shenoy, Jayant Haritsa, S. Sudarshan, Gaurav Bhalotia, Mayank Bawa, and Devavrat Shah, “Turbo-charging vertical mining of large databases,” Proc. ACM International Conference on Management of Data, 2000, pp. 22-33.
[12] R. Srikant and R. Agrawal, “Mining generalized association rules,” Proc. 21st International Conference on Very Large Data Bases, 1995, pp. 407-419.
[13] S. Y. Sung, K. Wang, and L. Chua, “Data mining in a large database environment,” Proc. IEEE International Conference on Systems, Man, and Cybernetics, 1996, pp. 988-993.
[14] H. Toivonen, “Sampling large databases for association rules,” Proc. 22nd International Conference on Very Large Data Bases, 1996, pp. 134-145.
[15] Ming-Cheng Tseng, Wen-Yang Lin, and Been-Chian Chien, “Maintenance of generalized + association rules with multiple minimum supports,” Proc. 9th IFSA World Congress and 20th NAFIPS International Conference, 2001, pp. 1294-1299.
[16] Show-Jane Yen and Arbee L. P. Chen, “An efficient data mining technique for discovering interesting association rules,” Proc. 8th International Workshop on Database and Expert Systems Applications, 1997, pp. 664-669.