Please use this identifier to cite or link to this item:
Efficient Algorithms for the Discovery of Frequent Superset
Frequent Superset Mining
Frequent Pattern Mining
|Issue Date: ||2009-09-17 13:54:33 (UTC+8)|
在實驗的部份，我們比較了各演算法的效率，並且分別改變實驗資料庫的下列四種變因：1) 交易資料的筆數、2) 每筆交易資料的平均長度、3) 資料庫中項目的總數和4) 最小門檻值。在最後的分析當中，可以清楚地看出我們提出的各種方法皆十分有效率並且具有可延伸性。
The algorithms for the discovery of frequent itemset have been investigated widely. These frequent itemsets are subsets of database. In this thesis, we propose a novel mining task: mining frequent superset from the database of itemsets that is useful in bioinformatics, E-learning systems, jobshop scheduling, and so on. A frequent superset means that the number of transactions contained in it is not less than minimum support threshold. Intuitively, according to the Apriori algorithm, the level-wise discovering starts from 1-itemset, 2-itemset, and so forth. However, such steps cannot utilize the property of Apriori to reduce search space, because if an itemset is not frequent, its superset maybe frequent. In order to solve this problem, we propose three methods. The first is the Apriori-based approach, called Apriori-C. The second is the Eclat-based approach, called Eclat-C, which is a depth-first approach. The last is the proposed data complement technique (DCT) that we utilize original frequent itemset mining approach to discover frequent superset.
The experimental studies compare the performance of the proposed three methods by considering the effect of the number of transactions, the average length of transactions, the number of different items, and minimum support. The analysis shows that the proposed algorithms are time efficient and scalable.
|Reference: || R. Agrawal, T. Imielinski, and A. Swami, “Mining Association Rules between Sets of Items in Large Databases,” Proc. of ACM Special Interest Group on Management of Data, ACM SIGMOD’93, 1993.|
 R. Agrawal and R. Srikant, ”Fast Algorithms for Mining Association Rules,” Proc. of the 20th International Conference on Very Large Data Bases, VLDB’94, 1994.
 J. Han, J. Pei, and Y. Yin, “Mining Frequent Patterns without Candidate Generation,” Proc. of ACM Special Interest Group on Management of Data, ACM SIGMOD’00, 2000.
 M. Zaki, S. Parthasarathy, M. Ogihara, and W. Li, “New Algorithms for Fast Discovery of Association Rules,” Proc. of the 3rd ACM Special Interest Group on Knowledge Discovery in Data and Data Mining, ACM SIGKDD’97, 1997.
 R. Agarwal, C. Aggarwal, and V. Prasad, “A Tree Projection Algorithm for Generation of Frequent Itemsets,” Journal on Parallel and Distributed Computing (Special Issue on High Performance Data Mining), Vol. 61, Issue 3, 2000.
 J. Pei, J. Han, H. Lu, S. Nishio, S. Tang, and D. Yang, “H-Mine: Hyper-Structure Mining of Frequent Patterns in Large Database,” Proc. of the 1st IEEE International Conference on Data Mining, ICDM’01, 2001.
 J. Park, M. Chen, and P. Yu, “An Effective Hash-Based Algorithm for Mining Association Rules,” Proc. of ACM Special Interest Group on Management of Data, ACM SIGMOD’95, 1995.
 J. Han and M. Kamber, “Data Mining: Concepts and Techniques,” Morgan Kaufman Publishers, 2000.
 J. Hipp, U. Guntzer, and G. Nakhaeizadeh, “Algorithms for Association Rule Mining – A General Survey and Comparison,” ACM SIGKDD Explorations, Vol. 2, Issue 1, 2000.
 D. Burdick, M. Calimlim, and J. Gehrke, “MAFIA: A Maximum Frequent Itemset Algorithm for Transactional Databases,” Proc. of the 17th International Conference on Data Engineering, ICDE’01, 2001.
 R. Agarwal, C. Aggarwal, and V. Prasad, “Depth First Generation of Long Patterns,” Proc. of ACM Special Interest Group on Knowledge Discovery in Data and Data Mining, ACM SIGKDD’00, 2000.
 M. Holsheimer, M. Kersten, H. Mannila, and H. Toivonen, “A Perspective on Databases and Data Mining,” Proc. of the 1st International Conference on Knowledge Discovery and Data Mining, KDD’95, 1995.
 G. Gardarin, P. Pucheral, and F. Wu, “Bitmap Based Algorithm for Mining Association Rules,” Proc. of Actes des journes Bases de Donnes Avances, 1998.
 A. Savasere, E. Omiecinski, and S. Navathe, “An Efficient Algorithm for Mining Association Rules in Large Databases,” Proc. of the 21st International Conference on Very Large Data Bases, VLDB’95, 1995.
 F. Bodon, “A Fast APRIORI Implementation,” Proc. of the 3rd IEEE International Conference on Data Mining, ICDM’03, Workshop on Frequent Itemset Mining Implementions, FIMI’03, 2003.
 Synthetic Data Generation Code for Associations and Sequential Patterns. http://www. almaden.ibm.com/software/quest/Resources/index.shtml Intelligent Information System, IBM Almaden Research Center.
 T. Urdan and C. Weggen, “Corporate E-learning: Exploring a New Frontier,” WR Hambrecht + Co, 2000.
 R. Beasley and M. Waugh, “The Effects of Content-Structure Focusing on Learner Structural Knowledge Acquisition, Retention, and Disorientation in a Hypermedia Environment,” Journal of Research on Computing in Education, Vol. 28, Issue 3, 1996.
 R. Beasley and M. Waugh, “Cognitive Mapping Architectures and Hypermedia Disorientation: An Empirical Study,” Journal of Educational Multimedia and Hypermedia, Vol. 4, Issue 2-3, 1995.
 C. Chang, “Cognitive Problem and Suggestions in Information Space Navigation–An Introduction and Survey,” Hua Fan Annual Journal, Vol. 4, No. 1, 1997.
 G. Chen, C. Liu, K. Ou, and M. Lin, “Web Learning Portfolios: A Tool for Supporting Performance Awareness,” Innovations in Education and Training International, IETI, Vol. 38, Issue 1, 2000.
 C. Liu, G. Chen, K. Ou, B. Liu, and J. Horng, "Managing Activity Dynamics of Web Based Collaborative Applications," International Journal of Artificial Intelligence Tools, JAIT, Vol. 8, Issue 2, 1999.
 D. Wang, Y. Bao, G. Yu, and G. Wang, “Using Page Classification and Association Rule mining for Personalized recommendation in distance learning,” Proc. of the 1st International Conference on Web-based learning, ICWL’02, 2002.
 D. Chiu, Y. Wu, and A. Chen, “An Efficient Algorithm for Mining Frequent Sequences by New Strategy without Support Counting,” Proc. of the 20th International Conference on Data Engineering, ICDE’03, 2003.
 R. Agrawal and R. Srikant, “Mining Sequential Patterns,” Proc. of the 12th International Conference on Data Engineering, ICDE’95, 1995.
 J. Setubal and J. Meidanis, Introduction to Computational Molecular Biology, PWS Publishing Company, 1997.
 F. Gandon, “Ontology Engineering: a Survey and a Return on Experience,” Research Report of INRIA, RR4396, 2002.
 N. Noy and M. Musen, “SMART: Automated Support for Ontology Merging and Alignment,” Proc. of the 12th Banff Workshop on Knowledge Acquisition, Modeling, and Management, KAW’99, 1999.
 N. Noy and M. Musen, “PROMPT: Algorithm and Tool for Automated Ontology Merging and Alignment,” Proc. of the 7th National Conference on Artificial Intelligence and 12th Conference on Innovative Applications of Artificial Intelligence, AAAI’00, 2000.
 G. Stumme and A. Maedche, “FCA-MERGE: Bottom-Up Merging of Ontologies,” Proc. of the 17th Internation Joint Conference on Artificial Intelligence, IJCAI’01, 2001.
 S. Itoga, “The String Merging Problem,” BIT, Vol. 21, No. 1, 1981.
|Source URI: ||http://thesis.lib.nccu.edu.tw/record/#G0091753013|
|Data Type: ||thesis|
|Appears in Collections:||[資訊科學系] 學位論文|
All items in 政大典藏 are protected by copyright, with all rights reserved.